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

Question

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

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

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

Answer 1

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

Так "Top 10% зарплаты" можно было бы сделать примерно так:

Определить общее:

1. MAP: Идентичность
2. УМЕНЬШИТЬ: агрегировать данные всех записей, которые проходят через и создайте новую «специальную» запись с «итогом». Обратите внимание, что вы хотите масштабировать

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

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

1. MAP: Подготовка к SecondarySort
2. SHUFFLE/Sort: Сортировка записей, так что записи с "общей" являются первым в редукторе.
3. УМЕНЬШЕНИЕ: В зависимости от вашей реализации редуктор может получить кучу этих общих записей (суммировать их), а для всех последующих записей определить, где они находятся по отношению ко всему остальному.

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

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

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

Answer 2

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

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

Комбинирователь/редуктор: объединить сортировку списков. В основном я делаю то же самое, что и в картографе, создавая десятиэлементный массив, а затем перебираю все массивы, соответствующие ключу, объединяя их в соответствии с той же самой последовательностью сравнения/замены/перемещения вниз, что и в преобразователе

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

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

Answer 3

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

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

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

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

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

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

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

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

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

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

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