Логістика - чудова штука. Варто заглянути в сховище якогось гіпермаркету - і стає ясно: без ретельного впорядкування товарів в ньому і мови не може йти про будь-якої ефективної торгівлі. Тим часом гігантські торгові доми спокійнісінько відкривають свої двері десяткам тисяч споживачів і легко розшукують в надрах своїх бездонних складів необхідні товари.
З інформацією справа йде приблизно так само. Зберегти її - тільки одна з задач. Інформація вимагає обробки. Яким би ефективним не було сховище даних, воно не допоможе її обробити.
У компанії Google з цією проблемою знайомі не з чуток. Її працьовиті боти цілодобово збирають контент все більше розростається інтернету і передають його в кластер Google, де править бал розподілена файлова система GFS. Вона розподіляє петабайт даних по сотням тисяч чанк-серверів не гірше досвідченого фахівця з логістики, по ходу справи забезпечуючи їм можливість безпечно зберігати, якому не шкодять ані можливі збої, ні відмови устаткування.
Але пошукова система - це не стільки склад контенту, скільки система швидкого знаходження його частин за ключовими словами, що вводиться користувачем в рядок пошуку.
Як дізнатися, на яких веб-сторінках є ці ключові слова? Який ресурс містить всього одне ключове слово, а який - відразу кілька? Тут без хорошої індексної бази не обійтися.
Сформувати таку базу на петабайтного масиві даних - завдання нетривіальне. Фактично потрібно по черзі «пройтися» по кожному документу і визначити, чи містить він потрібне слово. Як не крути, процес лінійний.
Але тільки не для компанії, що володіє кластером з півмільйона комп'ютерів.
З ним легко можна застосовувати відому парадигму інформатики «розділяй і володарюй», поділивши інформаційний масив на частини і віддавши кожну з них індексувати єдиного сервера. Ну а після виконання індексації по частинах залишається зібрати знайдене рішення воєдино.
Саме для такої роботи Google і була розроблена технологія MapReduce - засіб ефективного розпаралелювання задач, в звичайних умовах вирішуються лінійно.
Натхнення з минулого
Пам'ятайте, в дитинстві на уроках рідної мови нам давали завдання на уважність? Знайти, наприклад, на сторінці з «Золотої рибки» всі букви «О» і підрахувати їх кількість. Школярі скрупульозно, рядок за рядком, виглядали «О», підкреслювали їх, а потім підсумовували підкреслене.
Тепер уявіть, наскільки швидше пішло б справа, якби ми роздали по рядку кожного учня з класу, який, підрахувавши кількість букв, повідомив би його заздалегідь призначеного «головному по буквах». Якщо не вдаватися в подробиці, технологія MapReduce працює саме таким чином.
Звичайно, розробляючи MapReduce, співробітники Google Джеффрі Дін (Jeffrey Dean) і Санджай Гемават (Sanjay Ghemawat) надихає не шкільними завданнями. Вони мали інший чудовий джерело ентузіазму. Ще в кінці п'ятдесятих років минулого століття для обробки даних, представлених лінійними списками, була розроблена мова програмування Lisp - предок цілого сімейства мов, які використовують парадигму функціонального програмування.
Lisp і інші функціональні мови підтримують цікаву програмну модель, іменовану Map / Reduce. З її назви випливає, що працюють в ній дві процедури - map, що застосовує потрібну функцію до кожного елементу списку, і reduce, яка об'єднує результати роботи map.
Операції, що виконуються функціями map і reduce. У найпростішому випадку це агрегування даних за значенням «ключ».
Щоб виконати індексацію зберігається в кластері Google веб-контенту, розробники MapReduce пристосували загальну модель функціональних мов програмування до своїх цілей.
Вони припустили, що вся оброблювана MapReduce інформація може бути представлена у вигляді списку пар, кожна з яких складається з ключа і значення. У масиві веб-контенту ключем, звичайно ж, є шукане слово, а його значенням - число 1, яке підтверджує присутність цього слова.
У найпростішому варіанті програмної моделі Google MapReduce процедура map отримує на вхід список слів, що містяться в оброблюваних документах. Вона перетворює кожен елемент в пару, одним елементом якої є слово, а іншим - число 1.
Потім за список береться процедура reduce, яка групує елементи списку з однаковими ключами (тобто словами) і підсумовує одинички. В результаті на виході виявляється список всіх ключових слів з кількістю їх згадок в тих чи інших документах. А це і є індексна база пошукової системи.
Наочний приклад роботи функцій map і reduce.
Як бачите, нічого нового творці MapReduce не винайшли. Їх справжня заслуга в іншому. Насправді MapReduce - це не тільки програмна модель, використовуючи яку можна вирішувати задачі сортування і угрупування даних. Це - ціла архітектура, що забезпечує:
- автоматичне розпаралелювання даних з величезного масиву по безлічі вузлів обробки, виконують процедури Map / Reduce;
- ефективну балансування завантаження цих обчислювальних вузлів, що не дає їм простоювати або бути перевантаженими надміру;
- технологію відмовостійкої роботи, що передбачає той факт, що при виконанні загального завдання частина вузлів обробки може вийти з ладу або з якої-небудь іншої причини перестати обробляти дані.
Таким чином, Google MapReduce, з одного боку, надає користувачеві процедури обробки його даних, а з іншого - робить для нього прозорим процес розпаралелювання цієї обробки на могутньому кластері Google.
Як же їм це вдалося?
Паралельні обчислювачі, GFS і все той же кластер
Найбільш світлою думкою при проектуванні MapReduce була ідея розмістити модулі, що реалізують процедури map і reduce, на тих самих чанк-серверах - основі файлової системи GFS. Такий підхід наближає зберігаються в GPS модулі до функцій їх обробки. Економія мережевого трафіку в наявності.
Дальше більше. Як і GFS, технологія MapReduce побудована за принципом «головний - підлеглі». «Голова» MapReduce - процедура Master - управляє безліччю розкиданих по чанк-серверам «працівників» (workers), частина з яких відповідає за функцію map (їх звуть mappers, або «меппери»), а інші, відповідно, за reduce (reducers - «редьюсери»).
В результаті з'являється новий, розділений на частини масив проміжних даних, що містять неврегульовані списки пар ключ - значення. В ідеалі кількість частин цього проміжного масиву має дорівнювати R, тобто збігатися з кількістю «працівників», що відповідають за операцію reduce. Однак на практиці масив пар, що містять один і той же ключ, може бути значно більше (наприклад, якщо ключ - це одне з найпопулярніших слів в пошукових запитах).
Щоб скоротити його розмір, MapReduce дотримується процедур попереднього агрегування даних, привласнюючи таким популярним парам нове проміжне значення. Ця процедура називається combine і за своєю суттю дуже схожа на reduce. Необхідно зауважити, що combine можна використовувати лише в тих випадках, коли функція, яку використовують на стадії reduce для об'єднання даних, має властивості коммутативности і асоціативності.
Агрегований до необхідного розміру масив проміжних даних може надходити на R «працівників», що виконують reduce. Варто нагадати, що reduce в найпростішому вигляді працює з усіма значеннями одного ключа - наприклад, з кількістю згадок будь-якого слова. Це означає, що на кожного «працівника» бажано подати пари з однаковим ключем. Проблема полягає в тому, що вони розкидані по різних частинах списку, сформованого мепперамі. Як же бути?
MapReduce - це не тільки сам процес обчислень. Це система з централізованим управлінням, распараллелівать його і стежить за помилками в ході його виконання.
Останнім етапом перед виконанням процедури reduce є процедура розподілу (partitioning), в результаті якої пари з однаковим ключем потрапляють на одних і тих же «працівників». Так, процес вимагає часу і значного мережевого трафіку, але все це компенсується швидкістю роботи на наступному етапі.
Кожен редьюсер в кінцевому підсумку створює файл, де зберігаються відсортоване (наприклад, за алфавітом) список ключів, за які він відповідав, і результат обробки значень цих ключів (наприклад, їх сума).
Щоб зменшити кількість результатів обчислень, MapReduce ретельно розподіляє проміжні дані по вузлах reduce.
Так в надрах кластера Google і народжується індексна база інтернету, будуються графи популярності URL і виконуються інші необхідні для роботи пошукової системи операції.
І не тільки для неї. Розробники додатків Google, в яких потрібна обробка великих масивів даних, швидко оцінили переваги паралельного обчислювача MapReduce і написали свої варіанти процедур map і reduce. Саме так поповнюється словникова база перекладача Google Translate, так формує дані про орфографію десятків мов спеллчекер Google Docs і індексує голосові морфеми Google Voice. Застосувань MapReduce було знайдено безліч.
Як і у випадку з файлової системою GFS, Google пояснила тільки ідеологію MapReduce, не розкриваючи конкретних реалізацій її алгоритмів. Однак і цього вистачило, щоб співтовариство open source в рамках проекту Hadoop реалізувало планувальник розподілу завдань по вузлах обчислювального кластера Hadoop YARN і фреймворк Hadoop MapReduce, що дозволяє створювати власні меппери і редьюсери.
Технологія ж MapReduce, орієнтована на пакетну обробку даних (майстер роздав завдання, почекав, зібрав результати) не могла ефективно враховувати ці постійні зміни.
Більш наочно переваги архітектури Caffeine перед попередніми рішеннями Google і не уявити.
Використовуючи свої кращі напрацювання і ретельно досліджуючи тенденції нашої з вами роботи в інтернеті, Google намагається робити попереджувальні кроки в розвитку свого серця - пошукової системи.