Сортировка значений перед отправкой в редуктор
Вопрос
Я подумываю о создании небольшого приложения для тестирования в Hadoop, чтобы освоить систему.
Приложение, которое я имею в виду, будет связано с ведением статистики.Я хочу получить «10 худших значений для каждого ключа» из моей функции редуктора (где я должен предположить возможность огромного количества значений для некоторых ключей).
Я запланировал, чтобы значения, которые входят в мой редуктор, в основном представляли собой комбинацию «Фактического значения» и «Качества/релевантности фактического значения».В зависимости от релевантности я «просто» хочу взять 10 худших/лучших значений и вывести их из редуктора.
Как мне это сделать (при условии огромного количества значений для определенного ключа)?Есть ли способ отсортировать все значения ДО того, как они будут отправлены в редуктор (и просто прекратить чтение ввода, когда я прочитаю первые 10), или это нужно сделать по-другому?
Может ли кто-нибудь указать мне на пример кода, на который я могу взглянуть?
Обновлять:Я нашел две интересные проблемы с Jira ХАДОП-485 и ХАДОП-686.
У кого-нибудь есть фрагмент кода о том, как использовать это в API Hadoop 0.20?
Решение
Похоже, вы хотите использовать Объединитель, который определяет, что делать со значениями, которые вы создаете на стороне Карты, прежде чем они будут отправлены в Редюсер, но после того, как они сгруппированы по ключу.Комбайнер часто устанавливается просто как класс редуктора (поэтому вы уменьшаете на стороне карты, а затем снова на стороне уменьшения).
Посмотрите, как в примере wordCount используется объединитель для предварительного вычисления частичных значений:
http://wiki.apache.org/hadoop/WordCount
ОбновлятьВот что я имею в виду для вашей проблемы;хотя возможно, я неправильно понял, что вы пытаетесь сделать.
Каждый картограф излучает <key, {score, data}>
пары.
Комбинатор получает частичный набор этих пар: <key, [set of {score, data}>
и выполняет локальную сортировку (все еще на узлах картографа) и выводит <key, [sorted set of top 10 local {score, data}]>
пары.
Редуктор получит <key, [set of top-10-sets]>
-- все, что ему нужно сделать, это выполнить этап слияния сортировки-слияния (сортировка не требуется) для каждого из членов наборов значений и прекратить слияние, когда будут извлечены первые 10 значений.
обновление 2
Итак, теперь, когда мы знаем, что ранжирование является совокупным, и, как следствие, вы не можете фильтровать данные на ранней стадии с помощью объединителей, единственное, что вы предлагаете, — запустить вторичную сортировку.Вы нашли нужные билеты;пример того, как это сделать в Hadoop 20, есть в src/examples/org/apache/hadoop/examples/SecondarySort.java (или, если вы не хотите загружать все дерево исходников, вы можете посмотреть пример вставить https://issues.apache.org/jira/browse/HADOOP-4545 )
Другие советы
Звучит определенно как проблема вторичной сортировки.Взгляните на «Hadoop:Полное руководство», если хотите.Это от О'Рейли.Вы также можете получить к нему доступ онлайн.Там описывают довольно хорошую реализацию.
Я тоже реализовал это сам.В основном это работает следующим образом:Разделитель будет заботиться обо всех парах ключ-значение, при этом один и тот же ключ будет передаваться в один редуктор.Здесь нет ничего особенного.Но есть еще GroupingComparator, который будет формировать группы.Одна группа фактически передается в качестве итератора одному вызову метода уменьшения().Таким образом, раздел может содержать несколько групп.Но количество разделов должно быть равно количеству редукторов.Но группировка также позволяет выполнять некоторую сортировку, поскольку она реализует метод CompareTo.
С помощью этого метода вы можете контролировать, чтобы 10 лучших/худших/самых высоких/самых низких ключей первыми достигли редуктора.Итак, после того, как вы прочитаете эти 10 ключей, вы можете оставить метод сокращения без дальнейших итераций.
Надеюсь, это было полезно :-)
Если я правильно понял вопрос, вам нужно будет использовать Тоталордерпартиционер.