MapReduce - как рассчитать относительные значения (среднее, top k и т. Д.)?

Question

Я ищу способ вычисления «глобальных» или «относительных» значений во время процесса MapReduce - среднего, суммы, вершины и т. Д. Скажем, у меня есть список работников с их идентификаторами, связанными с их зарплатами (и куча других вещей). На каком-то этапе обработки я хотел бы знать, кто такие рабочие, которые получают 10% лучших зарплат. Для этого мне нужно некоторое «глобальное» представление значений, которое я не могу понять.

Если у меня есть все значения, отправленные в один редуктор, он имеет это глобальное представление, но тогда я теряю параллелизм, и это кажется неловким. Есть ли лучший способ?

(Фреймворк, который я хотел бы использовать, - это Google, но я пытаюсь разобраться в технике - не нужно никаких специфических трюков для фреймворка)

Answer 1

Моя первая мысль - сделать что-то вроде этого:

MAP: использовать какое-нибудь фиктивное значение в качестве ключа, возможно, пустую строку для эффективности, и создать класс, который будет содержать как зарплату, так и идентификатор сотрудника.В каждом Mapper создайте массив, который содержит 10 элементов.Заполните его первыми десятью зарплатами, которые вы видите, отсортированными (таким образом, местоположение 0 - самая высокая зарплата, местоположение 9 - 10-е самое высокое).Для каждой зарплаты после этого, посмотрите, входит ли она в первую десятку, и, если она есть, вставьте ее в правильное место, а затем, при необходимости, переместите более низкую зарплату вниз.

Combiner / Reducer: объединить сортировать списки.Я бы сделал то же самое, что и в mapper, создав массив из десяти элементов, а затем перебрал все массивы, соответствующие ключу, объединив их в соответствии с той же последовательностью сравнения / замены / перемещения вниз, что и в mapper * 1005.*

Если вы запускаете это с одним редуктором, это должно обеспечить вывод 10 самых высоких зарплат.

Я не вижу способа сделать это при использовании более одного редуктора.Если вы используете комбинатор, тогда редуктор должен объединять массив из десяти элементов только для каждого узла, на котором выполнялись мапперы (который должен быть управляемым, если вы не работаете на тысячах узлов).

Answer 2

Я бы сделал что-то вроде этого

1. Маппер будет использовать UUID как часть ключа, созданного в методе setup () маппера.Картограф выдает ключ, UUID добавляется либо с 0, либо с окладом.Картограф накапливает количество и общее количество.

2. В методе cleanup () преобразователь генерирует UUID с добавлением 0 в качестве ключа и счетчиком и итогом в качестве значения.В методе map () маппер генерирует UUID с добавленным окладом в качестве ключа и окладом в качестве значения.

3. Поскольку ключи отсортированы, первый вызов в объединитель будет иметьрассчитывать и общее в качестве значения.Объединитель может хранить их как членов класса.Мы также могли бы выяснить, что такое 10% от общего количества, и сохранить это, а также учащегося (назовите его сверху).Мы инициализируем список и сохраняем его как члена класса.

4. Последующие вызовы объединителя будут содержать оклад в качестве значения, поступающего в отсортированном порядке.Мы добавляем значение в список и одновременно увеличиваем счетчик.Когда счетчик достигает значения top, мы больше не сохраняем значения в нашем списке.Мы игнорируем значения в остальных вызовах объединителя.

5. В очистке объединителя () мы выполняем излучение.Объединитель будет излучать только UUID в качестве ключа.Значение будет содержать count и total, за которыми следуют 10% верхних значений.Таким образом, выходные данные объединителя будут иметь частичные результаты, основанные на подмножестве данных, которые прошли через преобразователь.

6. Редуктор будет вызываться столько раз, сколько число преобразователей вв этом случае, поскольку каждый преобразователь / сумматор выдает только один ключ.

7. Редуктор будет накапливать значения счетчиков, итогов и 10% верхних значений в методе Reduce ().В методе cleanup () вычисляется среднее значение.Верхние 10% также рассчитываются в методе cleanup () из совокупности верхних 10%, поступающих при каждом вызове редуктора.По сути, это сортировка слиянием.

8. Метод cleanser () редуктора может выполнить несколько излучений, так что среднее значение находится в первой строке, за которой следуют первые 10% зарплат в последующемстрок.

9. Наконец, для обеспечения того, чтобы итоговая статистическая статистика была глобальной, необходимо установить число редукторов равным единице.

10. Поскольку существуетЭто накопление и сортировка данных в редукторе, хотя при частичном наборе данных могут быть проблемы с памятью.

Answer 3

[Редактировать: я неправильно понял.Обновление для верхних 10%] Для выполнения чего-либо, связанного с «итогом», нет другого способа, кроме как сначала определить итоговое значение, а затем выполнить расчеты.

Таким образом, «10% окладов» могут быть выполнены.примерно следующим образом:

Определить итог:

1. MAP: Identity
2. REDUCE: объединить информацию обо всех проходящих записях и создать новую «специальную» записьс «итогом».Обратите внимание, что вы хотели бы масштабировать

Это также можно сделать, разрешив MAP вывести 2 записи (данные, итого), и тогда редуктор будет касаться только «итоговых» записей путем агрегирования.

Использовать итог:

1. MAP: подготовка к SecondarySort
2. SHUFFLE / SORT: сортировать записи так, чтобы записи с «итогом» были первыми в редукторе.
3. СНИЖЕНИЕ: В зависимости от вашей реализации редуктор может получить кучу этих итоговых записей (объединить их) и для всех последующих записей определить, где они находятся по отношению ко всему остальному.

Самый большой вопрос по этому виду обработки: «Будет ли масштаб?»

Помните, что вы нарушаете самое большое «необходимое» для масштабирования: независимые порции информации.Это делает их зависимыми от «общей» стоимости.Я ожидаю, что технически иной способ сделать «общее» значение доступным для второго шага крайне важно для выполнения этой работы над «большими данными».

« Hadoop - полное руководство »В книге Тома Уайта есть очень хорошая глава о вторичной сортировке.