Більшість галузевих аналітиків сходяться на думці, що з періодом приблизно в шість років сумарна кількість даних, що накопичуються в комп'ютерних базах, збільшується на три порядки, а це істотно вище приросту продуктивності комп'ютерів. З певною натяжкою можна стверджувати, що продуктивність процесорів збільшується за ті ж шість років на один порядок - терабайтниє диски дозволяють створити петабайтного сховище без особливої складності, але стримуючим фактором стає швидкість обробки.
База даних без загальних ресурсів
Якщо база даних побудована на загальному інформаційному ресурсі, то розділити її на частини для паралельної обробки неможливо, отже, предметом розпаралелювання повинна бути не класична реляційна база, а база, спочатку розрахована на архітектуру без поділу ресурсів (Shared Nothing, SN). До сих пір у фахівців з СУБД архітектура SN залишалася на периферії уваги, втім, іноді її протиставляють централізованим рішенням, порівнюють з рішеннями на основі реляційних СУБД і серверів додатків, але не розглядають в якості реального конкурента ім. Найчастіше уявлення про SN обмежують різного роду Web-додатками. Це здасться особливо дивним, якщо згадати, що першим ідею бази даних з архітектурою SN висунув сам Майкл Стоунбрейкер, один з першопрохідців реляційних СУБД, причому зробив це задовго до появи WWW. У 1986 році в статті The Case for Shared Nothing він виділив три категорії систем, здатних зберігати дані: з пам'яттю (Shared Memory, SM), з розділяються дисками (Shared Disk, SD) і які не поділяють нічого (SN). Першим двом відповідало безліч різних систем, а архітектура SN була представлена тільки мережевими за своєю природою комп'ютерами Tandem (сьогодні їх спадкоємцями є HP NonStop Himalaya S-Series). І все ж Стоунбрейкер вдалося показати, що гіпотетично архітектура SN найбільш краща, в тому числі і з економічної точки зору. Але двадцять років тому мережеві архітектури не були достатньо розвинені, а рішення Tandem, незважаючи на всю їх витонченість, залишалися пропрієтарними і в силу цього занадто дорогими. Немає нічого дивного, що еволюція серверів пішла іншим шляхом. Але сьогодні до SN повертаються вже на іншому витку розвитку технологій, і в даному випадку пріоритет відродження належить Google, архітектура SN втілена в конструкції, іменованої MapReduce.
Додатки, побудовані на основі MapReduce, в принципі можна розглядати і як бази даних, але не в тому сенсі, що в їх основі обов'язково лежить реляційна модель з доступом до даних за допомогою мови SQL, а як спираються на альтернативну модель і розраховані на дуже великі сховища даних.
три архітектури
При створенні апаратних систем, що підтримують бази даних, можливий вибір між трьома архітектурними варіантами: share-everything, share-disk і share-nothing ( Мал. 1 ).
Мал. 1. Архітектури сховищ даних
Найбільш масовими є рішення share-everything, де розділяються всі ресурси. Вони передбачають використання універсальних серверів з безліччю симетричних процесорів SMP (Symmetric Multi-Processing) в поєднанні з реляційними, рідше об'єктними або постреляціонних СУБД. У цих рішеннях втілені основні ідеологічні принципи, на яких будувалися комп'ютери для корпоративних додатків, - з кінця 60-х років якість комп'ютерів оцінювалося за їхньою здатністю до розподілу ресурсів. Реляційні бази створювалися в розрахунку на трансакціонної обробку даних (OLTP) на потужних SMP-серверах, що забезпечують повний розподіл всіх ресурсів. Навіть коли в дев'яностих роках стали поступово усвідомлювати переваги систем з масовим паралелізмом (MPP), з точки зору СУБД перевага зберігалося за SMP, головним чином через наступності і сумісності програмного забезпечення. Але з часом з більшою гостротою стали проявлятися два основних недоліки shared-everything. Кожен процесор має бути обізнаний про діяльність інших - частина потужності йде на підтримку «комунальної життя», що в кінцевому підсумку ставить межа числа процесорів в одній системі, оскільки витрати зростають експоненціально. Користування спільним дисковим простором веде до перевантаження каналу, що зв'язує процесори з пам'яттю, і сервери цього типу мають вроджений межа зростання.
В якості однієї з альтернатив SMP-серверів можна розглядати кластерні архітектури, в яких розподіляється є тільки дисковий простір, системи цього класу підтримуються, наприклад, в Oracle RAC (Real application Cluster). Кластер з розділяються дисками, на якому працює сховище даних, збирається з декількох серверів і через SAN підключається до розподіляються системам зберігання даних. Найбільш повно RAC реалізований в продукті HP Oracle Database Machine. Ця машина баз даних складається з програмних компонентів від Oracle, серверів стандартної архітектури від HP і структурно являє собою дві grid-системи - на одній (8 серверів Oracle Database Server на HP Proliant DL360 G5) працює СУБД, а друга (14 серверів Oracle Exadata Storage на HP ProLiant DL180 G5) призначена для зберігання даних. Ці спеціалізовані сервери відрізняються від звичайних Linux-серверів тим, що в них вбудовано програмне забезпечення, що дозволяє частину функцій по обробці запитів виконувати в паралельному режимі, тобто деяка частина роботи з базою виконується локально, що природним чином прискорює роботу. Разом дві системи об'єднані через InfiniBand. Обрана архітектура і високошвидкісне межсоединение позбавляють HP Oracle Database Machine від проблем, пов'язаних з «пляшковим горлом».
Третє рішення - використання стандартних серверів за принципом «ніяких загальних ресурсів». Подібні архітектури відмінно зарекомендували себе стосовно високопродуктивних обчисленнях, але їх впровадження в інших областях обмежується труднощами, пов'язаними з розпаралелюванням додатків. Ідея баз даних без загальних ресурсів (shared-nothing database) протягом тривалого терміну жила в продуктах компанії Teradata, яка випускає MPP-системи з власної комутаційної інфраструктурою BYNET. До останнього часу єдиною альтернативою виробам від Teradata були спеціалізовані сервери Netezza Performance Server (NPS). Верхній рівень цих серверів - хост на базі SMP-сервера, що працює під управлінням Linux, а нижній рівень - сотні лез Snippet Processing Unit (SPU), що утворюють кластер. Завдання хоста складається в перетворенні призначених для користувача запитів в клаптеві SPU і повернення результатів користувачам. Кожен з SPU відповідає за виконання окремої частини запиту. Ці системи орієнтовані в основному на бізнес-аналітику.
Нещодавно до цієї невеликої групи розробників приєдналася компанія Greenplum, яка почала з нуля, але підійшла до справи радикально, зібравши команду висококваліфікованих фахівців і написавши абсолютно нову СУБД. Відмінність альтернативної архітектури в тому, що кожен окремий компонент цієї СУБД відіграє роль закінченою, самодостатньою міні-СУБД, яка сама володіє і оперує окремої порцією довірених їй даних. Ця міні-СУБД автоматично розподіляє дані і навантаження по обробці запитів за доступними їй апаратними ресурсів. Для свого старту компанія Greenplum обрала вдалий з точки зору технічної кон'юнктури момент - вона вирішила стати першим постачальником «убивчого додатки» багатоядерних процесорів. Наріжним каменем її стратегії поставлена ідея збірки систем, аналогічних за своєю функціональністю продуктам компаній Teradata і Netezza, але відрізняються тим, що в них використовується широко поширене апаратне забезпечення. Можна сказати, що Greenplum вирішила повторити Google, але стосовно до баз даних. Іншими словами, розробники Greenplum вирішили забезпечити доступ до даних не тільки засобами пошуку, а й через SQL. Оскільки Greenplum виключно програмна компанія, основним моментом запозичення стала програмна конструкція MapReduce, розроблена в Google.
Технологічне починання Greenplum заслужило високу оцінку в експертному співтоваристві - в звіті Gartner «Магічний квадрант СУБД для сховищ даних» від 24 січня 2008 року лише ця компанія перебуває в частині квадранта visionaries (провидці), що свідчить про безсумнівну перспективність, але ще недостатньою масовості запропонованих технологій або продуктів. У звіті про Greenplum підкреслюється як гідність монопродуктового орієнтація - компанія поставляє виключно системи управління базами даних для сховищ. Її продукти орієнтовані на системи з масовим паралелізмом, в них використовується модернізована версія PostgreSQL, об'єктно-реляційної СУБД з відкритими кодами, створеної в кінці 90-х років як логічне продовження СУБД Ingress. Продукція Greenplum поширюється в комплекті зі спеціалізованими програмованими пристроями (appliance). Постачальником обладнання є Sun Microsystems - дві компанії випускають Sun Data Warehouse Appliance, що складаються зі спеціалізованих серверів Sun Fire X4540 і Greenplum Dtabase.
Введення в MapReduce
Програмна конструкція MapReduce пішла від Google, відомої не тільки своїми технологічними досягненнями, а й здатністю їх приховувати. Саме в такому дусі витримана стаття Джефрі Діна і Санжая Чемавата «MapReduce: спрощена обробка даних на великих кластерах» (MapReduce: Simplied Data Processing on Large Clusters), недомовленості якої компенсує робота Ральфа ламмелей з Дослідницького центру Microsoft в Редмонді «Модель програмування MapReduce компанії Google »(Google's MapReduce Programming Model). У вступі ламмелей заявляє, що він проаналізував статтю Діна і Чемавата, яку він неодноразово і з повагою називає seminal (доленосною), використовуючи метод, який називається «зворотного інженерією» (reverse engineering). Тобто, не виходячи за рамки обмежень на авторські права, він постарався розкрити зміст того, що ж в ній насправді представлено. Ламмелей пов'язує MapReduce з функціональним програмуванням, мовами Лисп і Haskell, що природним чином вводить читача в контекст.
Але робота ламмелей орієнтована виключно на програмістів-розробників, тому, перш ніж викласти в адаптованій формі програмну концепцію MapReduce, зупинимося на тому, що у ламмелей не сказано, але що критично важливо для розуміння передумов. Справа в тому, що MapReduce - це не просто програмний каркас (framework), як її попередники в Лісп, а скоріше інфраструктурне рішення, здатне ефективно використовувати сьогодні кластерні, а в майбутньому багатоядерні архітектури, своєю перспективністю вона і привертає до себе підвищену увагу.
Чому ж значимість MapReduce виходить за межі тих додатків, для яких цей програмний каркас використовується в Google, і привертає до себе загальну увагу? Ті величезні кластери, на яких вона застосовується, і пошукові завдання насправді всього лише окремий випадок. На думку одного з видатних умів сучасності, професора Каліфорнійського університету
в Берклі Дейва Паттерсона, MapReduce стане одним з основних інструментів програмування в майбутньому (див. презентацію The Parallel Revolution Has Started), коли життя буде залежати не тільки класичного, а й модифікованого закону Мура, який стверджує, що з певною періодичністю буде подвоюватися і число транзисторів на кристалі, і число ядер, при цьому складність ядер і тактова частота залишаться практично незмінними. Використання MapReduce дозволить реалізовувати архітектури, що потрапляють в категорію SPMD (Single Program Multiple Data).
Одним з найважливіших моментів майбутньої революції стане відмова від нинішньої послідовної моделі комп'ютингу, заснованої на вихідній редакції схеми фон Неймана, і перехід до паралельної. Відбуватиметься поступова відмова від SISD (Single Instruction Single Data - «один потік команд, один потік SPMD даних») і перехід до SIMD (Single Instruction Multiple Data - «один потік команд, багато потоків даних») і MIMD (Multiple Instruction Multiple Data - «багато потоків команд, багато потоків даних»). Така класифікація, що поділяє простір можливостей на чотири частини SISD, SIMD, MISD, Multiple Instruction Single Data - «багато потоків команд, один потік даних», і MIMD - була запропонована Майклом Флінном на початку 70-х років, коли розпаралелювання здавалося можливим тільки на рівні машинних інструкцій. Сьогодні, з появою компактних серверів і багатоядерних процесорів можна, виконувати паралельно не тільки інструкції, але і фрагменти кодів, і вона може бути уточ-нена - SIMD і MIMD перетворюються в SPMD і MPMD (Multiple Program Multiple Data), в тому і в іншому випадку інструкцію замінила програма.
Більшість сучасних паралельних комп'ютерів, зокрема переважна частина супер комп'ютерів, що входять в список Tор500, належить до категорії MPMD. Кожен вузол виконує фрагмент загального завдання, працюючи зі своїми власними даними, а на додаток існує складна система обміну повідомленнями, що забезпечує узгодження спільної роботи. Такий вид паралелізму раніше називали паралелізмом на рівні команд (instruction-level parallelism, ILP), а зараз паралелізмом на рівні завдань (task level parallelism), але іноді його ще називають функціональним паралелізмом або паралелізмом з управління. Його реалізація зводиться до розподілу завдань по вузлах і забезпечення синхронності процесів, що відбуваються.
Альтернативний тип паралелізму називають паралелізмом даних (data parallelism), який за класифікацією Флінна потрапляє в категорію SIMD. Ідея SIMD вперше була реалізована ще в 70-і роки на комп'ютерах CDC Star-100 і Texas Instruments ASC, а популярність ця архітектура набула завдяки зусиллям Сеймура Крея, особливо успішним виявився комп'ютер Cray X-MP, який називали векторних процесором за здатність працювати з одновимірними масивами. Реалізація SPMD передбачає, що спочатку дані повинні бути якимось чином розподілені між процесорами, оброблені, а потім зібрані. Цю сукупність операцій можна назвати map-reduce, як прийнято в функціональному програмуванні, хоча точніше було б split-aggregate, тобто розбиття та збирання, але прищепилося перше. Можливо кілька способів реалізації SPMD: мови високого рівня, директиви типу loop directives і бібліотеки OpenMP, що зручніше на багатопроцесорних конфігураціях із загальною пам'яттю. На кластерах типу Beowulf можна використовувати обмін повідомленнями і бібліотеку MPI.
Реалізація SPMD вимагає виділення провідної частини коду, її називають Master або Manager, і підлеглих їй частин Worker. Майстер «роздає» завдання Робітникам і потім їх збирає. До появи MapReduce ця модель розглядалася як малоперспективна через наявність «пляшкового горла» на тракті обміну між безліччю Робочих і одним Майстром. Створення MapReduce дозволило цю проблему і відкрило можливість для обробки величезних масивів даних з використанням архітектури SPMD.
Припустимо, що слід вирішити просту задачу: обробити масив, розбивши його на подмассіви. У такому випадку робота Майстра зводиться до того, що він ділить цей масив на частини, надсилає кожному з Робочих покладений йому подмассів, а потім отримує результати і об'єднує їх ( рис.2 ). У функцію Робочого входить отримання даних, обробка та повернення результатів Майстру. Розподіл навантажень може бути статичним (static load balancing) або динамічним (dynamic load balancing). Концепція створена за мотивами комбінації map і reduce в функціональній мові програмування Липс. У ньому map використовує в якості вхідних параметрів функцію і набір значень, застосовуючи цю функцію по відношенню до кожного з значень, а reduce комбінує отримані результати.
Мал. 2. Спрощена схема потоку даних в конструкції MapReduce
Створена в Google конструкція MapReduce Робить примерно ті ж, но по відношенню до гігантськіх обсягів Даних. У цьом випадка map - це функція запиту від користувача, вміщена в бібліотеку MapReduce. Ее робота зводу до Вибори вхідних парі, ее обробці и Формування результату у виде значення и Деяк проміжного ключа, что служити Дороговказ для reduce. Конструкція MapReduce збірає разом всі значення з однакової проміжнімі ключами и передает їх у функцію reduce, такоже написання користувачем. Ця функція сприймає проміжні значення, якимось чином їх збирає і відтворює результат, швидше за все виражений меншою кількістю значень,
ніж вхідна множина.
Тепер зв'яжемо функціональну ідею MapReduce зі схемою SPMD. Виклики map розподіляються між безліччю машин шляхом ділення вхідного потоку даних на М зрізів (splits або shard), кожен зріз обробляється на окремій машині. Виклики reduce розподілені на R частин, кількість яких визначається користувачем.
При виконанні функції з бібліотеки MapReduce виконується приблизно така послідовність операцій ( Мал. 3 ).
Вхідні файли розбиваються на зрізи розміром від 16 до 64 Мбайт кожен, і на кластері запускаються копії програми. Одна з них Майстер, а решта - Робочі. Всього створюється M завдань map і R завдань reduce. Пошуком вільних вузлів і призначенням на них завдань займається Майстер.
В процесі виконання Робітники, призначені на виконання завдання map, зчитують вміст відповідних зрізів, здійснюють їх граматичний розбір, виділяють окремі пари «ключ і відповідне йому значення», а потім передають ці пари в обробну їх функцію map. Проміжне значення у вигляді ідентифікатора і значення буферизується в пам'яті.
Періодично буферізованние пари скидаються на локальний диск, розділений на R областей. Розташування цих пар передається Майстру, який відповідає за подальшу передачу цих адрес Робочим, які виконують reduce.
Робітники, які виконують завдання reduce, чекають повідомлення від Майстра про місцезнаходження проміжних пар. За його отриманні вони, використовуючи процедури віддаленого виклику, зчитують буферізованние дані з локальних дисків тих Робочих, які виконують map. Завантаживши все проміжні дані, Робочий сортує їх за проміжними ключам і, якщо є необхідність, групує.
Робочий обробляє дані за проміжними ключам і передає їх у відповідну функцію reduce для виведення результатів.
Коли всі завдання map і reduce завершуються, конструкція MapReduce відновлює роботу викликає програми і та продовжує виконувати призначений для користувача код.
Мал. 3. Хід виконання виклику MapReduce (цифри вказують порядок виконання)
Одне з найважливіших переваг цієї, хитромудрої на перший погляд конструкції полягає в тому, що вона дозволяє надійно працювати на платформах з низькими показниками надійності. Для виявлення потенційних збоїв Майстер періодично опитує Робочих, і, якщо якийсь з них затримується з відповіддю понад заданого нормативу, Майстер вважає його дефектним і передає виконання на вільні вузли. Різниця між завданнями map і reduce в даному випадку полягає в тому, що map зберігає проміжні результати на своєму диску, і вихід з ладу такого вузла призводить до їх втрати і вимагає повторного запуску, а reduce зберігає свої дані в глобальному сховище.
СУБД Greenplum Database
СУБД Greenplum Database 3.2 відрізняє можливість масштабування до петабайтних значень з лінійним зростанням витрат, розпаралелювання запитів, що прискорює швидкість роботи на один-два порядки, і ряд інших експлуатаційних переваг. З технологічної точки зору цю СУБД відрізняє використання програмної структури MapReduce, розробленої в Google, яка забезпечує не тільки високу продуктивність за рахунок застосування великої кількості процесорів, а в перспективі і ядер, але і високу надійність, а також технології компресії, від 3 до 10 разів скорочує обсяги переданих і збережених даних. Greenplum Database 3.2 має вбудовані можливості для аналітики і статистичної обробки засобами спеціалізованого мови програмування R.
Функції для map і reduce можуть бути написані на різних скриптових мовах, наприклад на Python і Perl: використовуючи звичні засоби, розробник отримує доступ до файлів і Web-сайтів безпосередньо за місцем їх знаходження (where it lives), причому робиться це простіше і природніше, ніж при використанні технологій, пов'язаних з реляційними СУБД. СУБД Greenplum є одночасно і комерційною реалізацією конструкції MapReduce, що забезпечує роботу з великими документами в різних форматах, і класичної СУБД, орієнтованої на роботу з реляційними таблицями ( Мал. 4 ). Такого роду універсальність досягається за рахунок машини для роботи з паралельними потоками даних - СУБД може не тільки незалежно працювати з кожним із двох джерел, а й поєднувати роботу з ними двома одночасно. Зокрема, засобами MapReduce можна оптимізувати доступ до великих СУБД або забезпечити виконання SQL-запитів до таблиць і до файлів.
Мал. 4. Greenplum Database: два джерела даних і два методи доступу
Ядро Greenplum Database - Parallel Dataflow Engine, машина для обробки паралельних потоків даних, яка може оптимізувати процеси, збираючи дані з зовнішніх джерел (файлів і додатків) і працюючи з локальними дисками або дисками на сегментах, об'єднаних в загальну мережу фірмових межсоединения gNet. Машина задумана так, що в перспективі може підтримувати системи, що складаються з багатьох тисяч процесорних ядер і при цьому підтримувати SQL в характерній для неї паралельної манері.
Апаратно-програмні сховища
Для підтримки оперативного доступу до дедалі більших обсягів інформації потрібні нові архітектури платформ сховищ даних.
Багатоядерні процесори і майбутня паралельна революція
Протягом тривалого часу прогрес в області мікропроцесорів ототожнювався з тактовою частотою, але мали рацію ті, хто зробив ставку на багатоядерні архітектури.
Мал. 1. Архітектури сховищ даних
Мал. 2. Спрощена схема потоку даних в конструкції MapReduce
Мал. 3. Хід виконання виклику MapReduce (цифри вказують порядок виконання)
Мал. 4. Greenplum Database: два джерела даних і два методи доступу
Чому ж значимість MapReduce виходить за межі тих додатків, для яких цей програмний каркас використовується в Google, і привертає до себе загальну увагу?