avlasov (avlasov) wrote,
avlasov
avlasov

Category:

Мини-учебнег по распределенным системам/протоколам. MapReduce как пример, оптимизации

Рассмотрим некоторые возможные оптимизации в той схеме, что мы рассмотрели ранее. Отмечу, что я рассматриваю общую схему, а не конкретную реализацию типа Hadoop MapReduce - т.е. в чем-то оно пересекается, а в чем-то и нет.

Map Reduce архитектура не совсем гибкая (нет итеративности, грубо говоря, графов задач), посему можно предположить что основное ее назначение - это обработка гигантских объемов данных. Конечно, ее и для Machine Learning умудряются использовать, но все же для этого у нее есть определенные недостатки. Таким образом, будем считать, что основной проблемой будет перемещение данных по сети, а не собственно вычисления - для вычислительно-емких задач имеет смысл использовать какие-то другие архитектуры (ну может тот же Hadoop Tez, в котором есть граф вычислений, или там Spark, или там еще чего). Итого основная задача - минимизация перемещения данных по сети (ну с диска на диск тоже). Так же считаем, что поскольку данных много, то в память они с большой вероятностью не помещаются, и рано или поздно мы их записываем на диск - либо локальный либо на диск на другой ноде в сети. На мой взгляд, если таких ограничений нет, то лучше использовать не Hadoop MR, а что-то другое. Посему примем за основу эти допущения.

Перемещаем вычисления к данным

Поскольку данных много, то лучше перемещать вычисления к данным. Т.е. map задачи нужно запускать по возможности на тех нодах, где расположены соответствующие куски данных. Ну и разбивать данные на подзадачи для разных мапперов нужно с учетом их размещения.

Однако, данные для редьюсеров придется перемещать по сети, и тут трудно что сделать. Ведь каждый маппер потенциально может выдать ключи для всех редьюсеров. Если редьюсеров достаточно много, то данные придется таскать с почти всех маппер-нод на почти все редьюсер-ноды. Конечно, какие-то данные можно и не таскать, ибо редьсер может запуститься на ноде, где только что закончил работать тот или иной маппер (или мапперы). Но в целом данные таскать надо.

Компрессия данных

Очевидный способ ускорить перемещение данных - это их закомпрессировать. Тем более, что часто удается сжать данные в разы, а порой и в десятки раз. Есть даже специальные алгоритмы сжатия ориентированные на подобные случаи (когда нужно быстро сжать данные, для записи на диск или передачи по сети), типа LZF, LZO, LZ4, Snappy. Еще это зависит от того, как конкретно сериализуются данные map тасками.
Однако, нужно отметить, что компрессия затруднит группировку и сортировку данных, так что ее надо применять хитро. Можно например, компрессировать только values, а ключи не компрессировать. Или же компрессировать их по отдельности.
В любом случае, компрессировать лучше непосредственно перед передачей по сети, а до это лучше манипулировать в исходном формате. Если конечно хватает дискового пространства, но я бы сказал, что если тут есть проблемы, то лучше подумать над улучшением сериализации.

Совмещение фаз

Я ранее предположил, что мы в конце каждой (под)фазы записываем данные на диск. Это такое начальное допущение, на практике, конечно, для оптимизации, стоит подумать какие операции можно совместить, чтобы избежать записи с последующим чтением.
Например, когда маппер выдал какие-то результаты, их можно не тупо записать на диск, а сразу начать partition'ить данные - т.е. посчитать партишн функцию, определить на какой редьюсер она пойдет, ну и дописать соответствующие результат в файл, предназначенный для соответствующего редьюсера. Так как HDFS поддерживает конкурентные аппенды, то нет никакой проблемы, чтобы мапперы одновременно делали и partition подзадачу. Например, они могут кэшировать результаты в памяти, а при сбросе кэша на диск раскидывать их по разным партициям.
Итого, на выходе map задачи мы будем сразу иметь partioned данные, пропустив одну (под)фазу.

Частичный редьюс

Данные для каждого редьюсера (каждого ключа) раскиданы по разным нодам, в общем случае. Так что прежде чем начать редьюс операцию, нужно эти данные собрать (конечно же, можно запустить перекачку и редьюс параллельно, ну типа там редьюсер подождет прибытие, но это уже детали).
Однако, часто операция редуцирования бывает ассоциативной - ну или если не строго ассоциативной то близкой к этому. Например, сложение ассоциативная операция, но если мы проводим вычисления с плавающей точкой, то из-за ошибок округления, разный порядок может выдавать разные результаты. Тем не менее, зачастую это будет не принципиально (тем более что хрен знает в каком порядке они попадут на редьюсер). Т.е. перед перемещением всех данных для редуцирования на другую ноду, можно выполнить частичное редуцирование данных на локальной ноде.
Т.е. можно сгруппировать результаты работы каждого маппера по ключам и применить к ним частичную операцию редуцирования - в Hadoop MR это называется Combine.
Точно так же, если на ноде работало несколько мапперов, то результаты их работы тоже можно частично редуцировать. Ну или сперва их разбить по партициям, потом сгруппировать и частично-редцуировать.

На этом пожалуй завершим рассмотрение MapReduce как примера распределенной системы и перейдем к web-системам.
Subscribe
  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 0 comments