Користувач:Cthuj/MapReduce (2)

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

Завдання програми складається з карти() процедура (спосіб), який виконує функції фільтрації і сортування (наприклад, сортування студентів по імені в черзі, одна черга для кожного імені) і Reduce() (зменшення) метод, який виконує операцію додавання (наприклад, підрахунок кількості студентів в кожній черзі, поступаючись назва частотах). У "mapreduce система" (також званої "інфраструктури" або "рамки") організує обробку на сортувальних розподіленого сервера, виконавши різні завдання паралельно, управління зв'язку і передачі даних між різними частинами системи, і забезпечення надмірності і відмовостійкості.

Огляд

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

"Map" крок: кожен робочий вузол застосовує функцію "map()" для локальних даних, і записує вихідні дані на тимчасове зберігання. Головний вузол гарантує, що тільки одна копія надлишкових вхідних даних обробляється.
"Shuffle" крок: робочі вузли перерозподіляють дані, що засновані на вихідних ключах (виробляються функцією "map()"), таким чином, що всі дані, що належать до одного ключа знаходиться в тому ж робочому вузлі.
"Reduce" крок: робочі вузли тепер паралельно обробляють кожну групу вихідних даних за ключем.

Інший спосіб поглянути на MapReduce - 5-кроків паралельних і розподілених обчислень:

Підготовка вхідних даних функції Map() – на "в mapreduce система" означає карті процесори, призначає введення значення ключа К1 , що кожен процесор буде працювати на, і передбачає, що процесор всі вхідні дані, пов'язані з цим ключове значення.
Виконання користувацької функції Map() – функція Map() виконується рівно один раз для кожного ключового значення К1, генеруючи вихідні організовані ключові значення К2.
"Тасування" вихідних даних функції Map до процесорів Reduce – система MapReduce позначає процесори Reduce, привласнює значення ключа K2 на кожен процесор, який має працювати далі, і передбачає, що процесор з усіма даними, що генеруються функцією Map пов'язані з цим значенням ключа.
Виконання користувацької функції Reduce() – Reduce() виконується рівно один раз для кожного значення ключа k2, що повернула функція map на кроці.
Вироблення остаточного виходу – до MapReduce система збирає всі вихідні дані функції Reduce(), і сортує її за k2, щоб зробити остаточний результат.

Ці п'ять кроків можуть виконуватися в певній послідовності – кожен крок починається тільки після того, як попередній крок завершено, хоча на практиці вони можуть чергуватися доки це не вплине на остаточний результат.

Логічний вид

Функції Map і Reduce фреймворку MapRecude визначені з урахуванням структурованих в пари даних (ключ, значення). Функція Map бере одну пару даних з типом в одній предметній області, і повертає список пар в іншому домені:

Map(k1,v1) → list(k2,v2)

Функція Map застосовується паралельно для кожної пари (з ключем k1) у вхідному наборі даних. Це виробляє список пар (з ключем k2) для кожного виклику. Після цього фреймворк MapReduce збирає всі пари з однаковим ключем (k2) з усіх списків і групує їх разом, створюючи одну групу для кожного ключа.

Функція Reduce застосовується паралельно до кожної групи, яка в свою чергу виробляє набір значень в одному домені:

Reduce(k2, list (v2)) → list(v3)

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

Таким чином, фреймворк MapReduce перетворює список пар (ключ, значення) в список значень. Це поведінка відрізняється від типового функціонального програмування комбінацій map і reduce, яка приймає список довільних значень і повертає одне єдине значення, яке об'єднує всі значення, що повертаються функцією map.

Приклади

Яскравий приклад MapReduce для підрахунку появи кожного слова в наборі документів:^[1]

function map(String name, String document):
  // name: ім'я документу
  // document: вміст документу
  for each word w in document:
    emit (w, 1)

function reduce(String word, Iterator partialCounts):
  // word: слово
  // partialCounts: список агрегованих часткових графів
  sum = 0
  for each pc in partialCounts:
    sum += pc
  emit (word, sum)

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

В якості іншого прикладу, уявіть, що для бази 1.1 мільярда людей, хотілося б, щоб обчислити середню кількість соціальних контактів у людини в залежності від віку. В середовищі SQL, такий запит може бути виражений так:

  SELECT age, AVG(contacts)
    FROM social.person
GROUP BY age
ORDER BY age

Використовуючи MapReduce, ключові значення k1 можуть бути цілими числами від 1 до 1100, кожен з яких представляє партію на 1 млн. записів, значення ключа k2 може бути віком людини в роках, а такий розрахунок може бути досягнуто з допомогою наступних функцій:

function Map is
    input: integer K1 between 1 and 1100, representing a batch of 1 million social.person records
    for each social.person record in the K1 batch do
        let Y be the person's age
        let N be the number of contacts the person has
        produce one output record (Y,(N,1))
    repeat
end function

function Reduce is
    input: age (in years) Y
    for each input record (Y,(N,C)) do
        Accumulate in S the sum of N*C
        Accumulate in C_new the sum of C
    repeat
    let A be S/C_new
    produce one output record (Y,(A,C_new))
end function

Система MapReduce, яка буде вибудовувати 1100 Map-процесорів, і забезпечить кожного відповідним 1 млн. записів. Map-крок буде виробляти 1,1 млрд. (Y,(N,1)) записів з Y-значеннями в діапазоні, скажімо, між 8 і 103. Система MapReduce буде потім вирівнювати 96 Reduce-процесорів шляхом виконання операції перемішування в пари ключ/значення через те, що нам треба дізнатись середній вік, і забезпечити кожного з його мільйонами відповідних вхідних записів. Зменшення кроку призведе до значного скоротчення набору тільки 96 вихідних записів (Y,А), які будуть пущені в кінцевому результуючому файлі, відсортованому за Y.

Граф інфо в записі - це важливо, якщо обробка знижується більш ніж один раз. Якщо ми не додамо лічильник записів, розраховане середнє, буде неправильно пораховане, наприклад:

-- map output #1: вік, кількість контактів
10, 9
10, 9
10, 9

-- map output #2: вік, кількість контактів
10, 9
10, 9

-- map output #3: вік, кількість контактів
10, 10

Якщо ми зменшуємо файли #1 і #2, ми будемо мати новий файл з середніми 9 контактами для 10-річного чоловіка ((9+9+9+9+9)/5):

-- reduce step #1: вік, кількість контактів
10, 9

Якщо ми зменшимо її з файлу #3, ми втратимо точність, скільки записів ми вже бачили, так що ми в кінцевому підсумку в середньому 9.5 контакти для 10-річного чоловіка ((9+10)/2), а це неправильно. Правильна відповідь - 9.166 = 55 / 6 = (9*3+9*2+10*1)/(3+2+1).

Потік даних (dataflow)

"Гарячі точки", що визначає додаток MapReduce є:

зчитувач
функція Map

'

функція розділення/поділу
функція порівняння
функція Reduce
записувач

Зчитувач

Зчитувач ділить вхідні дані на відповідні розміри "куски" (на практиці, як правило, 64-128 МБ) і фреймворк призначає один кусок кожній функції Map. Зчитувач зчитує дані зі стабільного сховища (зазвичай розподілена файлова система) і генерує пари ключ/значення.

Типовим прикладом є зчитування повного каталогу текстових файлів і повернення кожного рядку як запису.

Функція Map

Функція Map приймає набір пар ключ/значення, обробляє кожен, і генерує нуль або більше вихідних пар ключ/значення. Вхідні і вихідні дані типу map може бути (і часто так і є) відрізнятися один від одного.

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

Функція поділу

Кожен результат функції Map виділений для конкретного reducer (зменшувача) на розділ функцій додатка функції для сегментування цілей. Функція поділу видає ключ і кількість зменшувачів і повертає індекс потрібного зменшувача.

Функція порівняння

Вихідні дані для кожного Зменшення (reduce) витягуються з машини, на якій Карта (map) запустила і посортувала з використанням функції порівняння в додатку.

Функції зменшення (reduce)

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

Функція Зменшення приймає вхідні значення, підсумовує їх і генерує одине вихідне слово і остаточну суму.

Записувач

Записувач записує вихідні дані до стійкої пам'яті.

Розподіл і надійність

MapReduce забезпечує надійність за рахунок парцеляції ряду операцій по набору даних для кожного вузла в мережі. Кожен вузол періодично звітує з завершеними роботи і оновленням статусу. Якщо вузол не відповідає довше ніж цей інтервал, головний вузол (за аналогією з головним сервером в файлової системі Google) записує вузол, як мертвий, і посилає призначену для цього вузла роботу на інші вузли. Окремі операції використовують атомарні операції для іменування файлів виходів в якості перевірки, щоб переконатися, що не запущені конфліктні паралельні теми. Коли файли перейменовуються, можна скопіювати їх з іншим ім'ям на додаток до імені завдання (з урахуванням побічних ефектів).

Використання

MapReduce корисний в широкому спектрі додатків, в тому числі в розподіленому пошуку на основі шаблонів, розподіленого сортування, веб-посилання, сингулярної декомпозиції,^[2] веб-доступу до журналу статистики, інвертованого індексу будівництва, документу кластеризації, машинного навчання,^[3] і статистичного машинного перекладу. Крім того, в MapReduce модель була адаптована для декількох обчислювальних середовищ, таких як Multi-Core і багатоядерних систем^[4]^[5]^[6] GRID-станцій,^[7] волонтерських обчислювальних середовищ^[8] динамічних хмарних середовищ,^[9] і мобільних середовищ.^[10]

Обмежені рамки програмування

Завдання MapReduce повинні бути написані у вигляді програм ациклічного потоку, тобто без зіставлення з подальшим редуктор без громадянства, які виконуються за допомогою пакетного планувальника завдань. Ця парадигма робить повторні запити наборів даних складними і накладає обмеження, які є суттєвими в таких областях, як машинне навчання, де повторення алгоритмів, які повертають один робочий набір кілька разів - це норма.^[11]

Конференції і групи користувачів

Перший міжнародний семінар по MapReduce та її додаткам (MAPREDUCE'10) була проведена в червні 2010 року з конференцією ЛСД і зустрічі в Чікаго, Іллінойс.
Mapreduce для груп користувачів по всьому світу.

Дивіться також

Застосування MapReduce

Посилання

↑ Example: Count word occurrences.
↑ Bosagh Zadeh, Reza; Carlsson, Gunnar. Dimension Independent Matrix Square Using MapReduce (PDF). Процитовано 12 July 2014.
↑ Ng, Andrew Y.; Bradski, Gary; Chu, Cheng-Tao; Olukotun, Kunle; Kim, Sang Kyun; Lin, Yi-An; Yu, YuanYuan. Map-Reduce for Machine Learning on Multicore. NIPS 2006. {{cite web}}: Cite має пустий невідомий параметр: |1= (довідка)
↑ Ranger, C.; Raghuraman, R.; Penmetsa, A.; Bradski, G.; Kozyrakis, C. (2007). Evaluating MapReduce for Multi-core and Multiprocessor Systems. 2007 IEEE 13th International Symposium on High Performance Computer Architecture. с. 13. doi:10.1109/HPCA.2007.346181. ISBN 1-4244-0804-0.
↑ He, B.; Fang, W.; Luo, Q.; Govindaraju, N. K.; Wang, T. (2008). Mars: a MapReduce framework on graphics processors. Proceedings of the 17th international conference on Parallel architectures and compilation techniques - PACT '08 (PDF). с. 260. doi:10.1145/1454115.1454152. ISBN 9781605582825.
↑ Chen, R.; Chen, H.; Zang, B. (2010). Tiled-MapReduce: optimizing resource usages of data-parallel applications on multicore with tiling. Proceedings of the 19th international conference on Parallel architectures and compilation techniques - PACT '10. с. 523. doi:10.1145/1854273.1854337. ISBN 9781450301787.
↑ Tang, B.; Moca, M.; Chevalier, S.; He, H.; Fedak, G. (2010). Towards MapReduce for Desktop Grid Computing. 2010 International Conference on P2P, Parallel, Grid, Cloud and Internet Computing (PDF). с. 193. doi:10.1109/3PGCIC.2010.33. ISBN 978-1-4244-8538-3.
↑ Lin, H.; Ma, X.; Archuleta, J.; Feng, W. C.; Gardner, M.; Zhang, Z. (2010). MOON: MapReduce On Opportunistic eNvironments. Proceedings of the 19th ACM International Symposium on High Performance Distributed Computing - HPDC '10 (PDF). с. 95. doi:10.1145/1851476.1851489. ISBN 9781605589428.
↑ Marozzo, F.; Talia, D.; Trunfio, P. (2012). P2P-MapReduce: Parallel data processing in dynamic Cloud environments (PDF). Journal of Computer and System Sciences. Т. 78, № 5. с. 1382. doi:10.1016/j.jcss.2011.12.021.
↑ Dou, A.; Kalogeraki, V.; Gunopulos, D.; Mielikainen, T.; Tuulos, V. H. (2010). Misco: a MapReduce framework for mobile systems. Proceedings of the 3rd International Conference on PErvasive Technologies Related to Assistive Environments - PETRA '10. с. 1. doi:10.1145/1839294.1839332. ISBN 9781450300711.
↑ {{cite conference}}: Порожнє посилання на джерело (довідка)

[[Категорія:Паралельні обчислення]]

[1] Example: Count word occurrences.

[2] Bosagh Zadeh, Reza; Carlsson, Gunnar. Dimension Independent Matrix Square Using MapReduce (PDF). Процитовано 12 July 2014.

[mrml-3] Ng, Andrew Y.; Bradski, Gary; Chu, Cheng-Tao; Olukotun, Kunle; Kim, Sang Kyun; Lin, Yi-An; Yu, YuanYuan. Map-Reduce for Machine Learning on Multicore. NIPS 2006. {{cite web}}: Cite має пустий невідомий параметр: |1= (довідка)

[evalMR-4] Ranger, C.; Raghuraman, R.; Penmetsa, A.; Bradski, G.; Kozyrakis, C. (2007). Evaluating MapReduce for Multi-core and Multiprocessor Systems. 2007 IEEE 13th International Symposium on High Performance Computer Architecture. с. 13. doi:10.1109/HPCA.2007.346181. ISBN 1-4244-0804-0.

[graphicsMR-5] He, B.; Fang, W.; Luo, Q.; Govindaraju, N. K.; Wang, T. (2008). Mars: a MapReduce framework on graphics processors. Proceedings of the 17th international conference on Parallel architectures and compilation techniques - PACT '08 (PDF). с. 260. doi:10.1145/1454115.1454152. ISBN 9781605582825.

[tiledMR-6] Chen, R.; Chen, H.; Zang, B. (2010). Tiled-MapReduce: optimizing resource usages of data-parallel applications on multicore with tiling. Proceedings of the 19th international conference on Parallel architectures and compilation techniques - PACT '10. с. 523. doi:10.1145/1854273.1854337. ISBN 9781450301787.

[gridMR-7] Tang, B.; Moca, M.; Chevalier, S.; He, H.; Fedak, G. (2010). Towards MapReduce for Desktop Grid Computing. 2010 International Conference on P2P, Parallel, Grid, Cloud and Internet Computing (PDF). с. 193. doi:10.1109/3PGCIC.2010.33. ISBN 978-1-4244-8538-3.

[volunteerMR-8] Lin, H.; Ma, X.; Archuleta, J.; Feng, W. C.; Gardner, M.; Zhang, Z. (2010). MOON: MapReduce On Opportunistic eNvironments. Proceedings of the 19th ACM International Symposium on High Performance Distributed Computing - HPDC '10 (PDF). с. 95. doi:10.1145/1851476.1851489. ISBN 9781605589428.

[dynCloudMR-9] Marozzo, F.; Talia, D.; Trunfio, P. (2012). P2P-MapReduce: Parallel data processing in dynamic Cloud environments (PDF). Journal of Computer and System Sciences. Т. 78, № 5. с. 1382. doi:10.1016/j.jcss.2011.12.021.

[mobileMR-10] Dou, A.; Kalogeraki, V.; Gunopulos, D.; Mielikainen, T.; Tuulos, V. H. (2010). Misco: a MapReduce framework for mobile systems. Proceedings of the 3rd International Conference on PErvasive Technologies Related to Assistive Environments - PETRA '10. с. 1. doi:10.1145/1839294.1839332. ISBN 9781450300711.

[11] {{cite conference}}: Порожнє посилання на джерело (довідка)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]