Статьи

В заключение! Привет мир Hadoop, который не является хромым Количество слов!

Сентябрь 25, 2018

Так что мне надоел старый WordCount Hello World, и, будучи довольно математичным человеком, я решил создать свой собственный Hello World, в котором я уговорил Hadoop транспонировать матрицу!

…

Какая? Что ты говоришь? Вы думаете, что матрица транспонирования MapReduce более хромая,  чем количество слов? Ну, я не говорил, что мы собираемся спасти мир с помощью этой работы MapReduce, просто немного напрягая наши умственные мышцы. Как правило, когда вы запускаете пример WordCount, вы даже не смотрите на код Java. Вы просто похлопываете себя по спине, когда слово «неизменно» оказывается самым популярным словом в английском языке.

Цель этого упражнения  — представить новую задачу и простую задачу, чтобы мы могли практиковаться в размышлениях о решении БОЛЬШИХ проблем в иногда не интуитивных ограничениях MapReduce. В конечном итоге я намереваюсь продолжить этот пост с чрезвычайно сложными проблемами MapReduce, чтобы бросить вам вызов и призвать вас решать свои собственные проблемы.

Итак, без лишних слов:

Матричная задача транспонирования

Транспонирование матрицы — довольно простая концепция. Допустим, у вас есть некоторая матрица M. Вот строки M (с предшествующим номером строки):

079361429824661

Вы перемещаете эту матрицу, «переворачивая» значения по диагонали. Вот транспонирование (M):

0744192623963681

Для крошечных матриц, подобных этой, транспонирование является тривиальным, но для гигантских, супер-гигантских матриц больших данных это может быть затруднительно в условиях ограничения ОЗУ одной машины. Таким образом, матрица транспонирования является хорошим кандидатом на MapReduce.

План простой работы MapReduce

Как вы, возможно, уже знаете, MapReduce — это двухфазный процесс, состоящий из  фазы отображения и фазы  восстановления  . Упрощенно, на этапе отображения преобразователю дается содержимое каталога Hadoop по одному за раз в виде пары ключ-значение. В этом примере пусть ключ будет значением,  rowIndex а значение будет  values связано с этой строкой.

{0:[7936]}{1:[4298]}{2:[4661]}

Задача маппера состоит в том, чтобы использовать эту информацию, обрабатывать ее, а затем генерировать ряд других пар ключ-значение  K и  V. Ключи и значения могут быть любого типа, который вам нравится, и для каждой итерации функции карты вы можете генерировать столько  {K: V} пар, сколько пожелаете.

Между фазой отображения и фазой восстановления все эти значения  V сгруппированы в соответствии с соответствующими ключами  K. Затем, по одному, редуктору дается ключ  Kвместе со  всеми  соответствующими значениями  V[]. Цель редуктора — использовать эту информацию, обрабатывать ее и генерировать больше пар ключ-значение. В нашем примере этот новый набор пар ключ-значение будет представлять транспонирование исходной матрицы. Ключи будут  transposeRowIndexs, а связанные значения будут ассоциированными элементами в той строке, которую мы называем  transposeValuess. Итак, для примера этого поста редуктор вернет:

{0:[744]}{1:[926]}{2:[396]}{3:[681]}

Тюрьма игры, то просто написать две функции,  map и  reduce, которые достигают все выше:

map(rowIndex,values):#DO STUFFreturn{K:V}

reduce(K,V[]):#DO STUFFreturn{transposeRowIndex: transposeValues}

Итак, как вы реализуете это? Думаю об этом! Не заглядывать .

…

Мое решение

Вот мое решение

map(rowIndex,values):for(columnIndex =1 to length(values)):
    K = columnIndex
    V ={rowIndex: values[columnIndex]}return{K:V}

reduce(K,V[]):
  transposeValues =[]for(x in V[]):
    transposeValues[x.key]= x.value
  transposeRowIndex = K
  return{transposeRowIndex: transposeValues}

И если мы запустим наш алгоритм MapReduce, на этапе отображения мы получим

map(0,[7936])#=> {0:{0,7}},  {1:{0,9}},  {2:{0,3}},  {3:{0,6}}
map(1,[4298])#=> {0:{1,4}},  {1:{1,2}},  {2:{1,9}},  {3:{1,8}}
map(2,[4661])#=> {0:{2,4}},  {1:{2,6}},  {2:{2,6}},  {3:{2,1}}

За время «перемешивания и сортировки» перед фазой сокращения мы группируем значения в соответствии с ключом

{0:[{0,7},{1,4},{2,4}]}{1:[{0,9},{1,2},{2,6}]}{2:[{0,3},{1,9},{2,6}]}{3:[{0,6},{1,8},{2,1}]}

И, наконец, на этапе сокращения мы получаем

reduce({0:[{0,7},{1,4},{2,4}]})#=>  {0: [7 4 4]}
reduce({1:[{0,9},{1,2},{2,6}]})#=>  {1: [9 2 6]}
reduce({2:[{0,3},{1,9},{2,6}]})#=>  {2: [3 9 6]}
reduce({3:[{0,6},{1,8},{2,1}]})#=>  {3: [6 8 1]}

И теперь, когда мы проверили алгоритм, пришло время перенести что-то немного большее …

На практике

Я  собираю сборник уроков по Hadoop и  называю его Hadoopadoop . Проверьте это! Загрузив его, вы можете быстро запустить мой пример MatrixTranspose, введя команду  ./build.sh MatrixTranspose. Но, пожалуйста, не позволяйте этому быть похожим на типичный пример WordCount. Вместо этого взгляните на скрипт сборки и посмотрите, что он делает для сборки проекта. Я намеренно держу все как можно легче. Никаких дополнительных библиотек, никаких Maven, только некоторые java-файлы, некоторые zip-файлы с данными и немного споров по bash.

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

Пока вы смотрите на мой  Hadoopadoop , взгляните на учебник WordCount, который я адаптировал из примера WordCount, поставляемого с Hadoop. Хотя это может быть хромым, но он по-прежнему остается отличным и простым примером MapReduce.

33
Share: