Автор: Джанаев Сослан Игоревич

Рубрика: Технические науки

Опубликовано в Молодой учёный №12 (116) июнь-2 2016 г.

Дата публикации: 07.06.2016

Статья просмотрена: 14 раз

Библиографическое описание:

Джанаев С. И. Обзорное описание метода Multi-Fragment-ReplicationJoin (MFRJ) доступа к многомерному хранилищу данных по технологии MapReduce // Молодой ученый. — 2016. — №12. — С. 244-247.



MapReduce

Технология MapReduce, поддерживается в среде баз данных NoSQL. Но существуют специальные каркасы MapReduce, имеющие файловые системы, оптимизированные под эту технологию. Примером такого каркаса является Hadoopс файловой системой HDFS.

Общий процесс обработки записей <ключ, значение> по технологии MapReduceвыглядит так:

map: → list ,

reduce: → list.

В одном j-ом узле может выполняться несколько экземпляров функции «map». Она должна осуществлять следующие действия: разобрать входную запись и вернуть одну или несколько новых записей {ji, rji>}i. При этом значение ключа mji может повторяться. Записи хешируются по значению ключа mji, формируются разделы записей, номер раздела совпадает со значением хеш-функции. Число разделов обозначим через s. Система объединяет выходные записи программы «map» в s-массивах и сохраняет их на локальном диске узла (один массив на одно значение хеш-ключа). Таким образом, формируются nsфайлов, n — число узлов.

После завершения фазы Map каждый результирующий массив Fji записей (j= 1...n, i= 1...s) пересылается с j-го узла на узел, где выполняется i-й экземпляр функции «reduce». Важно подчеркнуть, что этот механизм пересылки массивов позволяет обрабатывать записи с одинаковыми значениями ключа в одном узле. Поступившие в узел записи массивов сортируются, объединяются и передаются на вход соответствующей функции «reduce». Программа «reduce» должна обработать записи объединенного массива и выполнить их «свертку» в соответствии с поставленной задачей. Функция «reduce» возвращает выходной массив(как правило, меньшей размерности), и система сохраняет его в виде записей <ключ, значение> в файловой системе MapReduce. Эти записи могут быть использованы в качестве входных данных для других заданий MapReduce.

Ниже приведен сложный пример: соединение двух таблиц, хранящихся в файлах File1 и File2, по значению ключа (Рисунок 3).

На одном узле функция Mapчитает записи файла File1, а на втором узле два экземпляра функции Mapчитают записи файла File2 (записи ). Записи этих файлов имеют одинаковую структуру: ij, Vmj>. Т. е. ключ и значение записи являются составными. Здесь j (0 или 1) определяет принадлежность записи файлу: 0 — запись прочитана из файла File1, 1 — из файла File2.Результаты чтения показаны на рисунке справа. Функции Map просто, без обработки, помещают эти записи в выходной поток (list).

Далее система автоматически выполняет хеширование записей по значению Ki первого поля ключа (создаются разделы) и реализует фазу «перетасовки» (shuffle). Записи с одинаковыми значениями Kiпопадают в один и тот же узел, так как разделы с одинаковыми значениями хеш-функции передаются в один узел. Система выполняет сортировку записей по составному ключу (см. Sorting) на каждом принимающем узле. Затем записи группируются по первому полю ключа (т. е. по Ki). Поля значений записей, попавших в группу, помещаются в поле значения новой записи (, см. Grouping). Порядок составных значений в списке соответствует порядку отсортированных записей. То есть сначала записываются значения файла File 1 (признак 0), а затем — значения файла File2 (признак 1). Эти значения соответствуют одному значению Ki первого поля ключа.

C:\Yura\MSTU\KURS\Aspirant\Мои статьи и пособия\Подготовка монографии\Рис 1.tif

Рис. 1. Пример соединения таблиц по технологии MapReduce

И только после этого сформированная запись передается на вход функции Reduce. Эта функция анализирует запись и выполняет операцию декартова произведения значений файлов File 1 и File2 (ведь эти значения имеют один и тот же ключ соединения Ki). Ниже показан результат соединения (list):

первыйReduce: 1, VAVK>

второйReduce:4, VСVP>, 4, VСVL>

6, VDVM>, 6, VDVR>

Эти записи, в свою очередь, также могут быть сгруппированыи для них можно применить операции агрегирования (конечно, если Vm–это числовые значения).

Можно выделить следующие преимущества MapReduceHadoop:

  1. Простота установкиMapReduce(MR), ее относительно низкая стоимость.
  2. В функции «map» запроса к MR достаточно просто реализовать разбор (парсер) документа, а в функции «reduce» — объединение результатов разбора.
  3. Технология MapReduce обладает возможностью восстанавливать процесс обработки записей после сбоев в середине выполнения запроса с применением метода, не свойственного параллельным СУБД.

Метод доступа MFRJ

Таблицы измерений продублированы по всем узлам системы MapReduce (MR). Они хранятся по строкам. Таблица фактов делится на несколько групп: в 1-ю группу входят столбцы (колонки) внешних ключей измерений (fki), столбец каждого факта (mi) образует отдельную группу (группы 2,…,к+1). Все блоки таблиц измерений и групп таблицы фактов распределены MapReduce по узлам (автоматически) произвольным образом (MR пытается это делать равномерно).

Рис. 2. Таблица фактов для варианта 1.

Доступ к данным выполняется следующим образом.

Map (в каждом узле):

  1. Для измерений, которые участвуют в запросе, строятся хеш-индексы в оперативной памяти.
  2. Читаются записи внешних ключей измерений таблицы фактов (группа 1), хранящиеся в узле (fki), для каждой строки (позиции) и каждого внешнего ключа проверяется наличие значения этого ключа в соответствующем хеш-индексе; при успешном сравнении в выходной поток помещает запись:

<позиция1, (vd1,…,vdn)>

где «позиция1» — номер строки в группе внешних ключей (нумерация сквозная по всем строкам группы 1); (vd1,…,vdn) — список значений требуемых по условию запроса столбцов таблиц измерений (выбираются из хеш-индексов).

  1. Читаются значения колонки i-го факта (группа i+1), хранящиеся в узле; для каждого значения факта проверяется условие CF1 запроса, и это значение помещается в выходной поток:

<позиция2i, vmi>,

где «позиция2i» — номер строки в группе i+1 (нумерация сквозная по всем строкам группы i+1), vmi — значение i-го факта.

Значения «позиций1» и «позиций2» могут не совпадать, т. к. по условию блоки групп таблицы фактов распределены по узлам произвольно.

  1. Далее пункт 3 повторяется для других колонок фактов, блоки которых хранятся в данном узле (i=1,…,k).

Reduce:

1. Если в полученной функцией Reduce записи (после группирования по позиции) число элементов в области значения равно n+k (n — число измерений, k — число фактов) и она удовлетворяет условию запроса (проверяются заданные отношения между столбцами), то эта запись помещается в выходной поток как строка результирующей таблицы:

<позиция, (vd1,…,vdn,vm1,…,vmk)>.

Литература:

  1. Zhou, G. Zhu, Y. Wang,G.Cache Conscious Star-Join in MapReduceEnvironments. Cloud-I '13 Proceedings of the аnd International Workshop on Cloud Intelligence, August 26 2013.
  2. Lee, RubaoHuai, Shao, Yin Zheng etc. RCFile: A fast and space-efficient data place-ment structure in MapReduce-based warehouse systems. ICDE 2011, pp. 1199–1208.
  3. KonstantinaPalla. A Comparative Analysis of Join Algorithms Using the Hadoop Map/Reduce Framework. Master of Science School of Informatics University of Edinburgh, 2009, pp 1–93.
  4. Уайт Т.Hadoop: Подробное руководство. — СПб: Питер, 2013. — 672 с.
  5. ЧакЛэм. Hadoop в действии. — М.: ДМК Пресс, 2012. — 424 с.
Основные термины (генерируются автоматически): выходной поток, значению ki первого, значению ключа, первого поля ключа, одинаковыми значениями, Ki первого поля, внешних ключей измерений, функции «reduce», записи файла, таблицы фактов, групп таблицы фактов, значения файла, значения новой записи, одинаковыми значениями ключа, записи файла file2, записи файла file1, j-ом узле, Таблица фактов, значения файла file2, узле функция.

Обсуждение

Социальные комментарии Cackle
Задать вопрос