Паралельні машини баз даних

Параллельные машини баз даних.

.

.

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

По до баз даних.

Как відомо, основний інструмент збереження і переробки інформації - електронні обчислювальні машини (ЕОМ). Перехід до інформаційного суспільству супроводжується обвальним зростанням обсягів інформації, береженої у яких. Це своє чергу породжує проблему ефективної організації та пошуку інформації. Для подання у машинах великих обсягів даних використовуються технології баз даних. База даних є сукупність структурованих і взаємозалежних даних, збережених більш-менш постійно в ЕОМ на магнітних (поки) носіях, і використовуваних одночасно багатьма користувачами у межах деякого підприємства, організації, або співтовариства. Робота з базами даних використовується спеціальне системне програмне забезпечення, зване СУБД (Систему керування базами даних). Обчислювальний комплекс, до складу якого у собі відповідну апаратуру (ЕОМ з пристроями зберігання) та працює під керівництвом СУБД, називається машиною баз даних.

Первые такі машини з’явилися у другій половині 1960;х років минулого століття. Нині ринку програмного забезпечення поставляються сотні різноманітних комерційних СУБД практично всім моделей ЕОМ. Донедавна більшість машин баз даних включали у собі лише одне процесор. Однак у останнє десятиліття виник низку завдань, потребують збереження і обробки надвеликих обсягів даних. Одне з найбільш вражаючих прикладів вирішення завдань подібного типу — створення бази даних Системи спостереження Землі. Цю систему (Earth Observing System, EOS) включає у собі безліч супутників, які збирають інформацію, необхідну вивчення довгострокових тенденцій стану атмосфери, океанів, земної поверхні. Супутники поставляють на Землю 1/3 петабайтів інформацією рік (petabyte — 1015 байт), що можна з обсягом інформації (в кодах ASCII), що зберігається у Російської державної бібліотеці. Отримана зі супутників, вона накопичується базі даних EOSDIS (EOS Data and Information System) небачених колись розмірів.

Другая грандіозна завдання, теж потребує використання надвеликих баз даних, ставлять у проекті створення Віртуальною астрономічної обсерваторії. Така обсерваторія має об'єднати дані, одержувані усіма обсерваторіями світу у результаті спостереження за зоряним небом; обсяг цієї бази становитиме десятки петабайтів. Вочевидь, навіть дуже потужні однопроцессорные ЕОМ не впораються з обробкою цього потоку.

Естественное розв’язання проблеми обробки надвеликих баз даних — використовувати як машин баз даних многопроцессорные ЕОМ, дозволяють організувати паралельну обробку інформації. Інтенсивні дослідження у сфері паралельних машин були розпочаті 80-ті роки. Протягом двох десятиліть такі машини виконали шлях від екзотичних експериментальних прототипів, розроблюваних з науково-дослідницькою лабораторіях, до повнофункціональним комерційним продуктам, яке поставляється ринку високопродуктивних інформаційних систем.

В ролі прикладів успішних комерційних проектів створення паралельних систем баз даних може бути DB2 Parallel Edition [1], NonStop SQL [2] і NCR Teradata [3]. Такі системи об'єднують близько тисячі процесорів і магнітних дисків і здатні обробляти бази даних кілька десятків терабайт. Проте й у час тут доводиться ряд проблем, потребують додаткових наукових досліджень. Один із них — розвиток апаратної архітектури паралельних машин. Як у Асиломарском звіті про напрямах досліджень у сфері баз даних [4], найближчим часом великі організації володітимуть базами даних обсягом кілька петабайтів. Для обробки подібних обсягів інформації знадобляться паралельні машини з десятками тисяч процесорів, що у в сотні разів перевищує число у сприйнятті сучасних системах. Проте традиційні архітектури паралельних машин баз даних навряд чи допускають просте масштабирование на два порядку величини.

Сила і слабкість паралельних систем.

В основі сучасної технології систем баз даних лежить реляційна модель, запропонована Е. Ф. Коддом ще 1969 р. [5]. Перші реляционные системи побачили ринку 1983 р., і тепер вони міцно зайняли домінують. Реляційна база даних складається з відносин, які найлегше уявити як двовимірні (пласких) таблиць, містять інформацію про деякі класах об'єктів із предметної області. Що стосується бази даних, яке береже список телефонних номерів, таким класом об'єктів будуть абоненти міського телефонного мережі. Кожна таблиця складається з набору однорідних записів, званих кортежами. Усі кортежі щодо містять і той ж набір атрибутів, які можна як стовпчики таблиці. Атрибути представляють властивості конкретних примірників об'єктів певного класу. Прикладами атрибутів відносини Телефонная_книга можуть бути Прізвище, Номер, Адреса. Сукупність взаємин держави і утворює базі даних, що у вигляді файлів спеціального формату зберігається на магнітних дисках чи інших пристроях зовнішньої пам’яті.

Над реляционными відносинами визначено набір операцій, їхнім виокремленням реляционную алгебру. Аргументами і результатами реляционных операцій стосунки. Запити до реляционным баз даних формулюються на спеціальному мові запитів SQL (раніше званому SEQUEL) [6]. На мал.1 показаний приклад запиту мовою SQL, виконує операції селекції і проекції. У нашому випадку зі ставлення Телефонный_справочник здійснюється вибірка (селекція) всіх записів, які мають атрибут Прізвище приймає значення ‘Іванов'. У результуюче ставлення проектуються лише стовпчики Номер і Адреса.

.

Рис. 1. Приклад запиту мовою SQL, выбирающего зі ставлення Телефонная_книга номери телефонів, і адреси всіх абонентів з прізвищем Иванов..

Если вихідне ставлення дуже багато, виконання операції селекції швидше за все потребує значних витрат машинного часу. Для прискорення ми можемо спробувати організувати паралельне виконання запиту на кількох процессорных вузлах многопроцессорной системи. На щастя, реляційна модель найкраще адресований «розпаралелювання» запитів. У самій загальної формі той процес можна описати так. Кожне ставлення ділиться на фрагменти, які розташовуються в різних дискових пристроях. Запит застосовується немає відношенню загалом, а до даних фрагментами. Кожен фрагмент обробляється на окремому процесорі. Результати, отримані в різних процесорах, потім об'єднуються (зливаються) на загальне результуюче ставлення, як і схематично показано на мал.2. Отже, розбиваючи ставлення на n фрагментів в паралельної машині баз даних із n процессорными вузлами, ми зменшуємо час виконання запиту в n раз!

.

Рис. 2. Паралельне виконання запиту. Вихідний ставлення розбивається на фрагменти за двома цифр телефонного номери. Кожен фрагмент має власні диск для збереження і процесор в обробці. Результуюче ставлення об'єднує дані, що їх окремими вузлами системы..

Однако в повному обсязі так усе просто, як здається спочатку. Перша проблема, з якою ми зіштовхнемося, — за яким критерієм виробляти розподіл стосунки фрагменти? У прикладі на мал.2 ми застосували зване упорядкований поділ, що використовує два цифри телефонного номери як у ролі критерію розподілу кортежів по дискам. Але такий спосіб розбивки зовсім на ідеальний, позаяк у результаті ми швидше за все одержимо фрагменти, істотно різняться між собою за величиною, але це своєю чергою можуть призвести до сильних перекосів у завантаженні процесорів. При невдалої розбивці стосунки фрагменти однією з процесорів може випасти понад 50 відсотків% від загального обсягу навантаження, що знизить продуктивність нашої многопроцессорной системи рівня системи з однією процесором!

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

Другая серйозні проблеми, що з використанням паралельних машин баз даних, виникає через обмеженою масштабируемости. У многопроцессорной системі процесори ділять між собою деякі апаратні ресурси: пам’ять, диски і сполучну мережу, яка б пов’язала окремі процесори між собою. Додавання кожної нової процесора призводить до уповільнення роботи інших, використовують самі ресурси. При великому числі учасників може виникнути ситуація, що вони будуть довше чекати тієї чи іншої загального ресурсу, ніж працювати. І тут говорять про обмеженою масштабируемости системи.

Само число процесорів і дисків тягне у себе й третю серйозною проблемою, з якою ми зіштовхнемося під час створення паралельних машин, — забезпечення отказоустойчивости системи. Справді, ймовірність виходу з експлуатації магнітного диска в однопроцессорной системі невідь що велика. Проте, коли наша паралельна система включає у собі кілька тисяч процесорів і дисків, ймовірність відмови зростає у тисячі разів. Це міркування можна застосувати до будь-який масової апаратної компоненті, входить до складу многопроцессорной системи. Тож паралельних машин баз даних проблема отказоустойчивости стає особливо важливою.

Четвертая проблема пов’язані з забезпеченням високої готовності даних: система повинна відновлювати втрачені дані в такий спосіб, щоб це були «невідь що» помітно для користувача, виконує запити до бази даних. Якщо у процесі відновлення 80−90% ресурсів системи витрачається виключно на мети відновлення бази даних, така система може бути непридатній випадків, коли у відповідь запит повинен бути отриманий негайно.

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

Архитектура буває різна.

В 1986 р. М. Стоунбрейкер [8], запропонував розбити архітектури паралельних машин баз даних втричі класу: архітектури з поділюваної пам’яттю і дисками, архітектури з поділюваними дисками й архітектури без спільного використання ресурсів (рис.3).

.

Рис. 3. Три класичні архітектури: SE-архитектура з поділюваної пам’яттю і дисками, SD-архитектура з поділюваними дисками, SN-архитектура без спільного використання ресурсів. У SE-системах все процесори P з допомогою загальної шини підключаються до поділюваної пам’яті M і дискам D. Процесорам передають одна одній дані через загальну пам’ять. У SD-системах кожен процесор має власну власну пам’ять, проте диски як і поділяються усіма процесорами. Для зв’язку процесорів друг з одним використовується високошвидкісна сполучна мережу N. У SN-системах кожен процесор має власну пам’ять й викохує власний диск. Обмін даними між процесорами, як і попереднього разі, відбувається після високошвидкісну сполучну сеть..

В системах з поділюваної пам’яттю і дисками все процесори з допомогою загальної шини поєднано з аналітичними поділюваної пам’яттю і дисками. Означимо таку архітектуру як SE (Shared-Everything). У SE-системах межпроцессорные комунікації можна реалізувати дуже ефективно через поділювану пам’ять. Оскільки тут кожному процесору доступні вся пам’ять і будь-яка диск, проблема балансування завантаження процесорів бракує принципових труднощів (непрацюючий процесор можна легко переключити з однієї диска в інший). Через це SE-системы демонструють для невеликих конфігурацій (які перевищують 20 процесорів) вищу продуктивність проти іншими архітектурами.

Однако SE-архитектура має низку вад, дуже неприємні у тому числі - обмежена масштабованість і низька апаратна отказоустойчивость. При велику кількість процесорів тут настає конфлікт доступу до поділюваної пам’яті, що може спричинити до серйозного деградації загальної продуктивності системи (тому масштабованість реальних SE-систем обмежується 20−30 процесорами). Не можуть забезпечити такі і високі готовність даних при відмовах апаратури. Вихід із ладу практично будь-який апаратної компоненти фатальний для всієї системи. Справді, відмова модуля пам’яті, шини доступу до пам’яті чи шини вводу-виводу виводить з експлуатації систему загалом. Що ж до дисків, то забезпечення високої готовності даних вимагає дублювання одним і тієї ж даних різними дисках. Проте підтримку ідентичності всіх копій може істотно знизити загальну продуктивність SE-системы з обмеженою пропускну здатність шини вводу-виводу. Усе це виключає використання SE-архитектуры в чистому вигляді для систем з високими вимогами до готовності даних.

В системах з поділюваними дисками кожен процесор має власну власну пам’ять. Процесорам з'єднуються друг з одним і з дисковими підсистемами високошвидкісної сполучної мережею. У цьому будь-який процесор має доступом до кожному диску. Означимо таку архітектуру як SD (Shared-Disk). SD-архитектура проти SE-архитектурой демонструє кращу масштабованість вищу ступінь отказоустойчивости. Проте за реалізації SD-систем виникає чимало серйозних технічні проблеми, які мають розв’язання. На думку більшості фахівців, сьогодні немає вагомих причин на підтримку SD-архитектуры в чистому вигляді.

В системах без спільного використання ресурсів кожен процесор має власну пам’ять й викохує власний диск. Процесорам з'єднуються друг з одним з допомогою високошвидкісної сполучної мережі. Означимо таку архітектуру як SN (Shared-Nothing). SN-архитектура має найкращі показники по масштабируемости і отказоустойчивости. Однак ніщо загалом немає задарма: основним її недоліком стає складність із забезпеченням збалансованої завантаження процесорів. Справді, в SN-системе неможливо безпосередньо переключити непрацюючий процесор на обробку даних, що зберігаються на «чужому» диску. Щоб розвантажити певний процесорний вузол, слід частина «необроблених» даних перемістити по сполучної мережі в інший, вільний вузол. На це призводить до суттєвого падіння загальної ефективності роботи системи через високу вартість пересилки великих обсягів даних. Тому перекоси в розподілі даних із процессорным вузлам можуть викликати повну деградацію загальної продуктивності SN-системы.

Иерархические архітектури.

Для подолання недоліків, властивих SEі SN-архитектурам, А. Бхайд 1988 р. запропонував розглядати ієрархічні (гібридні) архітектури [9], у яких SE-кластеры об'єднують у єдину SN-систему, як і показано на рис. 4. SE-кластер є фактично самостійний мультипроцессор з поділюваної пам’яттю і дисками. Поміж себе SE-кластеры поєднано з аналітичними допомогою високошвидкісної сполучної мережі N. Означимо таку архітектуру як CE (Clustered-Everything). Вона має хорошою масштабністю, подібно SN-архитектуре, і дозволяє досягати прийнятного балансу завантаження, подібно SE-архитектуре.

.

Рис. 4. CE-архитектура. Цю систему об'єднує кілька SE-кластеров з допомогою високошвидкісної сполучної мережі. Кожен окремий кластер фактично є самостійний мультипроцессор з SE-архитектурой..

Основные недоліки CE-архитектуры криються у потенційних труднощі із забезпеченням готовності даних при відмовах апаратури лише на рівні SE-кластера. Щоб запобігти втрати даних через відмов необхідно дублювати одні й самі дані різними SE-кластерах. Проте підтримка ідентичності різних копій одним і тієї ж даних вимагає пересилки по сполучної мережі значні обсяги інформації. І це може істотним чином знизити загальну продуктивність системи як нормально функціонувати і призвести до з того що SE-кластеры почнуть працювати з продуктивністю, як в однопроцессорных конфігурацій.

Чтобы позбутися зазначених недоліків, ми запропонували [10] альтернативну трирівневу ієрархічну архітектуру (див. мал.5), основу якої лежить поняття SD2-кластера. Такий кластер складається з несиметричних двухпроцессорных модулів PM з поділюваної пам’яттю і набору дисків, об'єднаних за схемою SD. Означимо цю архітектуру як CD2 (Clustered-Disk with 2-processor modules).

.

Рис. 5. CD2-архитектура. Система будується як набір SD2-кластеров, об'єднаних високошвидкісної сполучної мережею у стилі «без спільного використання ресурсів». Кожен кластер — це система з поділюваними дисками і двухпроцессорными модулями..

Структура процесорного модуля зображено на див. мал.6. Процесорний модуль має архітектуру з поділюваної пам’яттю і включає у собі обчислювальний і комунікаційний процесори. Їх взаємодія здійснюється через загальну оперативну пам’ять (RAM). Крім цього, комунікаційний процесор має власну пам’ять; він оснащений високошвидкісними зовнішніми каналами (линками) для з'єднання з іншими процессорными модулями. Його присутність дозволяє значною мірою звільнити обчислювальний процесор від навантаження, що з організацією передачі повідомлень між процессорными вузлами. Такі процессорные модулі випускаються вітчизняної промисловістю для комплектування багатопроцесорних обчислювальних систем МВС-100/1000 [11].

.

Рис. 6. Несиметричний двухпроцессорный модуль з поділюваної пам’яттю. Модуль оснащений двома процесорами, взаємодіючими через поділювану пам’ять (RAM). Комунікаційний процесор має приватну пам’ять і оснащений високошвидкісними каналами (линками) для зв’язки з іншими модулями..

Такую CD2-архитектуру ми використовували при реалізації прототипу паралельної системи управління даними «Омега» для вітчизняних багатопроцесорних комплексів МВС-100/1000. Як засвідчили експерименти, CD2-система здатна досягти загальної продуктивності, можна з продуктивністю CE-системы, навіть за наявності сильних перекосів у розподілі даних із дискам. У той самий час CD2-архитектура дозволяє забезпечити вищу готовність даних, ніж CE-архитектура.

А досягти цього допомогли нові алгоритми розміщення даних, і балансування завантаження.

Как влаштована система «Омега».

Иерархическая архітектура системи «Омега» передбачає два рівня фрагментації. Кожне ставлення поділяється на фрагменти, що міститимуться в різних SD2-кластерах (межкластерная фрагментація). Натомість кожна така фрагмент дробиться ще на менші частини, распределяемые різноманітні вузлам SD2-кластера (внутрикластерная фрагментація). Цей підхід робить процес балансування завантаження гнучкішим, бо воно може виконуватися на двох рівнях: локальному, серед процессорных модулів всередині SD2-кластера, і глобальному, серед самих SD2-кластеров.

В системі «Омега» диски, належать одному кластеру, на логічному рівні діляться на непересічні підмножини фізичних дисків, кожна з яких утворює так званий віртуальний диск. Кількість віртуальних дисків в SD2-кластере постійно зростає і збігаються з кількістю процессорных модулів. У найпростішому разі одному віртуальному диску відповідає один фізичний диск. Отже, на логічному рівні SD2-кластер може розглядатися як система з SN-архитектурой, тоді як фізично це система з SD-архитектурой.

В основі алгоритму балансування завантаження лежить механізм реплікації даних, під назвою внутрикластерным дублюванням. Суть його у цьому, кожен фрагмент відносини дублюється усім віртуальних дисках кластера (далі для простоти ми опускати термін «віртуальний»).

Схема роботи запропонованого алгоритму балансування завантаження ілюструється з прикладу кластера з цими двома процесорами (див. мал.7). Тут процесору P1 сопоставлен диск D1, а процесору P2 — диск D2. Припустимо, що мені необхідні деяку операцію, аргументом якої є ставлення R. Ми ділимо фрагменти, куди розбите ставлення R всередині SD2-кластера, на приблизно однакові частини. Перша частина призначається в обробці процесору P1, друга — процесору P2 (на див. мал.7 даної стадії відповідає час t0).

.

Рис. 7. Алгоритм балансування завантаження для кластера з цими двома процессорными вузлами. На дисках D1 і D2 розташовані дві копії відносини R. Процесору P1 дозволено доступом до копії, що зберігається на диску D1, а процесору P2 — до копії на D2. У початковий час t0 фрагменти відносини R діляться між процесорами P1 і P2 приблизно рівної пропорції. У час часу t1 процесор P1 закінчив обробку своєї частині ставлення R, тоді як процесор P2 встиг виконати половину призначеної йому роботи. У час часу t2 відбувається перерозподіл необробленої частині ставлення R між двома процесорами. Перерозподіл триває до того часу, поки ставлення R не буде оброблено повністю (час t3)..

В час t1 процесор P1 закінчив обробку своєї частині ставлення R, тоді як процесор P2 встиг виконати частина призначеної йому роботи. І тут стається повторний перерозподіл необробленої частині ставлення R між двома процесорами (час t2 на див. мал.7). Процес триває до того часу, поки ставлення R нічого очікувати повністю оброблено (на момент часу t3). Алгоритм вочевидь узагальнюється на довільне число процесорів.

Предложенный алгоритм балансування завантаження процесорів дозволяє уникнути пересування сполучної мережі великих обсягів даних. Це кінцевому підсумку і відданість забезпечує такої системи продуктивність, порівнянну з продуктивністю SE-кластеров навіть за наявності сильних перекосів даних.

Подведем підсумки.

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

Однако при побудові ієрархічних систем по двухуровневому принципу, коли кластери процесорів з поділюваної пам’яттю і дисками об'єднують у єдину систему «без спільного використання ресурсів», виникають проблеми забезпечення високої готовності даних у разі відмов апаратури. Справді, при велику кількість кластерів у системі ймовірність відмови однієї з кластерів стає досить великий, і ми необхідно дублювати одні й самі дані на кількох різних кластерах, що у суті зводить нанівець всі переваги ієрархічної організації.

Поэтому можна очікувати, подальший розвиток ієрархічних архітектур паралельних машин баз даних піде шляхом створення багаторівневих гібридних схем, здатних забезпечити високу готовність даних на конфігураціях з кількома сотнями тисяч процессорных вузлів. Як прототипу таких систем пропонується паралельна система баз даних «Омега», розроблювана в Челябінськом державному університеті, має трирівневу ієрархічну архітектуру типу CD2 і може охоплювати у собі сотні SD2-кластеров. Але оптимальну архітектуру SD2-кластера ще попереду знайти. Ми плануємо випробувати різні конфігурації SD2-кластеров, варіюючи топологію межпроцессорных сполук, кількість процессорных модулів, кількість дискових підсистем і кількість дисків у окремої дискової підсистеми.

Работа виконано з допомогою Російського фонду фундаментальних досліджень. Проект 00−07−90 077.

1. Ігнатович М. // СУБД. 1997. № 2. C.5−17.

2.Compaq NonStop SQL/MP. internet.

3. Лисянський До., Слободяников Д. // СУБД. 1997. № 5−6. C.25−46.

4. Бернштейн Ф. та інших. // Відкриті системи. 1999. № 1. C.61−68.

5. Кодд Е. Ф. // СУБД. 1995. № 1. C.145−169.

6. Чамберлин Д. Д. та інших. // СУБД. 1996. № 1. C.144−159.

7. Девитт Д., Грей Д. // СУБД. 1995. № 2. C.8−31.

8. Stonebraker M. // Database Engineering Bulletin. March 1986. V.9. № 1. P.4−9.

9. Bhide A. An Analysis of Three Transaction Processing Architectures // Proceedings of 14-th Internat. Conf. on Very Large Data Bases (VLDB «88), 29 August — 1 September 1988. Los Angeles, California, USA, 1988. P.339−350.

10.Sokolinsky L.B., Axenov O., Gutova P. S. Omega: The Highly Parallel Database System Project // Proceedings of the First East-European Symposium on Advances in Database and Information Systems (ADBIS'97), St.-Petersburg. September 2−5, 1997.V.2. P.88−90.

11.Левин В. К. Вітчизняні суперкомп’ютери сімейства МВС. internet.