MapReduce

MapReduce - модель розподілених обчислень, представлена ​​компанією Google, використовувана для паралельних обчислень над дуже великими, кілька петабайт, [1] наборами даних в комп'ютерних кластерах.


1. Огляд

MapReduce - це фреймворк для обчислення деяких наборів розподілених задач з використанням великої кількості комп'ютерів (званих "нодамі"), що утворюють кластер.

Робота MapReduce складається з двох кроків: Map і Reduce.

На Map-кроці відбувається попередня обробка вхідних даних. Для цього один з комп'ютерів (званий головним вузлом - master node) отримує вхідні дані задачі, розділяє їх на частини і передає іншим комп'ютерам (робочим вузлам - worker node) для попередньої обробки. Назва даний крок отримав від однойменної функції вищого порядку.

На Reduce-кроці відбувається згортка попередньо оброблених даних. Головний вузол отримує відповіді від робочих вузлів і на їх основі формує результат - рішення задачі, яка спочатку формулювалася.

Перевага MapReduce полягає в тому, що він дозволяє розподілений проводити операції попередньої обробки і згортки. Операції попередньої обробки працюють незалежно один від одного і можуть проводитися паралельно (хоча на практиці це обмежена джерелом вхідних даних і / або кількістю використовуваних процесорів). Аналогічно, безліч робочих вузлів можуть здійснювати згортку - для цього необхідно лише щоб всі результати попередньої обробки з одним конкретним значенням ключа оброблялися одним робочим вузлом в один момент часу. Хоча цей процес може бути менш ефективним в порівнянні з більш послідовними алгоритмами, MapReduce може бути застосований до великих обсягів даних, які можуть оброблятися великою кількістю серверів. Так, MapReduce може бути використаний для сортування петабайта даних, що займе всього лише кілька годин. Паралелізм також дає деякі можливості відновлення після часткових збоїв серверів: якщо в робочому вузлі, що виробляє операцію попередньої обробки або згортки, виникає збій, то його робота може бути передана іншому робітникові вузлу (за умови, що вхідні дані для проведеної операції доступні).

Фреймворк у великій мірі заснований на функціях map і reduce, широко використовуваних в функціональному програмуванні, [2] хоча фактично семантика фреймворку відрізняється від прототипу. [3]


2. Приклад

Канонічний приклад програми, написаної за допомогою MapReduce - це процес, що підраховує, скільки разів різні слова зустрічаються в наборі документів:

 / / Функція, використовувана робочими нодамі на Map-кроці  / / Для обробки пар ключ-значення з вхідного потоку  void  map  (  String name  ,  String document  )  :  / / Вхідні дані:  / / Name - назва документа  / / Document - вміст документа  for  each word w in document  :  EmitIntermediate  (  w  ,  "1"  )  ;  / / Функція, використовувана робочими нодамі на Reduce-кроці  / / Для обрабокі пар ключ-значення, отриманих на Map-кроці  void  reduce  (  String word  ,  Iterator partialCounts  )  :  / / Вхідні дані:  / / Word - слово  / / PartialCounts - список групувати проміжних результатів. Кількість записів в partialCounts і є  / / Необхідну значення  int  result  =  0  ;  for  each v in partialCounts  :  result  + =  parseInt  (  v  )  ;  Emit  (  AsString  (  result  )  )  ; 

У цьому коді на Map-кроці кожен документ розбивається на слова, і повертаються пари, де ключем є саме слово, а значенням - "1". Якщо в документі одне і те ж слово зустрічається кілька разів, то в результаті попередньої обробки цього документа буде стільки ж цих пар, скільки разів зустрілося це слово.

Бібліотека об'єднує всі пари з однаковим ключем і передає їх на вхід функції reduce, якій залишається скласти їх, щоб отримати загальну кількість входжень даного слова у всі документи.


3. Наявні реалізації

  • Google реалізував MapReduce на C + + з інтерфейсами на мовах Python і Java
  • Greenplum - комерційна реалізація MapReduce з підтримкою мов Python, Perl, SQL і інших. [4]
  • GridGain - безкоштовна реалізація MapReduce з відкритим вихідним кодом на мові Java.
  • Проект Apache Hadoop - безкоштовна реалізація MapReduce з відкритим вихідним кодом на мові Java
  • Phoenix [1] - реалізація MapReduce на мові С з використанням розділяється пам'яті
  • MapReduce також реалізована Cell Broadband Engine на мові C [2]
  • MapReduce реалізована в графічних процесорах NVIDIA з використанням CUDA [3].
  • Qt Concurrent - спрощена версія фреймворку, реалізована на C + +, яка використовується для розподілу задачі між декількома ядрами одного комп'ютера.
  • CouchDB використовує MapReduce для визначення уявлень поверх розподілених документів
  • MongoDB дозволяє використовувати MapReduce для паралельної обробки запитів на декількох серверах
  • Skynet - реалізація з відкритим вихідним кодом на мові Ruby
  • Disco - реалізація MapReduce, створена компанією Nokia. Її ядро ​​написано на мові Erlang, а додатки для неї можна писати на мові Python
  • Hive framework - надбудова з відкритим вихідним кодом від Facebook, що дозволяє комбінувати підхід MapReduce і доступ до даних на SQL -подібному мовою.
  • Qizmt - реалізація MapReduce з відкритим вихідним кодом від MySpace, написана на C #.
  • DryadLINQ - реалізація MapReduce, створена підрозділом Microsoft Research в тому числі на основі PLINQ і Dryad.

Примітки

  1. Google spotlights data center inner workings | Tech news blog - CNET News.com - news.cnet.com/8301-10784_3-9955184-7.html
  2. "Our abstraction is inspired by the map and reduce primitives present in Lisp and many other functional languages." - "MapReduce: Simplified Data Processing on Large Clusters" - labs.google.com / papers / mapreduce.html, by Jeffrey Dean and Sanjay Ghemawat; from Google Labs
  3. "Google's MapReduce Programming Model - Revisited" - www.cs.vu.nl/ ~ ralf / MapReduce / paper.pdf - paper by Ralf Lammel; from Microsoft
  4. Parallel Programming in the Age of Big Data - gigaom.com/2008/11/09/mapreduce-leads-the-way-for-parallel-programming /