Паралельні машини баз даних
Наприкінці другого тисячоліття людство зробило крок з індустріальної ери в інформаційну еру. Якщо раніше головними були матеріальні
ресурси і робоча сила, то тепер вирішальними факторами розвитку суспільства стають інтелект і доступ до інформації. В інформаційному суспільстві люди в
основному будуть зайняті у сфері створення, розподілу та обміну інформації, а кожна людина зможе отримати необхідні продукт або послугу в будь-якому місці і в
будь-який час.
У напрямку до баз даних
Як відомо, основний інструмент зберігання та переробки інформації - електронні обчислювальні машини (ЕОМ). Перехід до інформаційного
суспільству супроводжується лавиноподібним зростанням обсягів інформації, що зберігається в них. Це в свою чергу породжує проблему ефективної організації та пошуку
інформації. Для представлення в машинах великих обсягів даних використовують технології баз даних. База даних являє собою сукупність
структурованих і взаємозалежних даних, що зберігаються більш-менш постійно в ЕОМ на магнітних (поки що) носіях, і використовуваних одночасно багатьма
користувачами в рамках певного підприємства, організації або спільноти. Для роботи з базами даних використовується спеціальне системне програмне
забезпечення, зване СУБД (Система управління базами даних). Обчислювальний комплекс, що включає в себе відповідну апаратуру (ЕОМ з пристроями
зберігання) та працює під управлінням СУБД, називається машиною баз даних.
Перші такі машини з'явилися в другій половині 60-х років минулого століття. В даний час на ринок програмного забезпечення поставляються
сотні різних комерційних СУБД практично для всіх моделей ЕОМ. До недавнього часу більшість машин баз даних включали в себе тільки один
процесор. Однак в останнє десятиріччя виник цілий ряд завдань, які потребують зберігання і обробки надвеликих об'ємів даних. Один з найбільш вражаючих
прикладів рішення задач такого типу - створення бази даних Системи спостереження Землі. Ця система (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. Алгоритм балансування завантаження для кластера з двома процесорними вузлами. На дисках D 1 і D 2
розташовані дві копії відносини R. Процесор P 1 дозволений доступ до копії, що зберігається на диску D 1 , а процесору P 2
- До копії на D 2 . У початковий момент часу t 0 фрагменти відносини R діляться між процесорами P 1 і P 2
приблизно в однаковій пропорції. У момент часу t 1 процесор P 1
обробив своїй частині відносини R, у той час як процесор P2 встиг виконати лише половину призначеної йому роботи. У момент часу t 2
відбувається перерозподіл необробленої частини відношення R між двома процесорами. Перерозподіл продовжується до тих пір, поки відношення R не
буде опрацьовано повністю (момент часу t 3 ).
У момент часу t1 процесор P1 обробив своїй частині відносини R, у той час як процесор P2
встиг виконати тільки частину призначеної йому роботи. У цьому випадку відбувається повторне перерозподіл необробленої частини відношення R між двома
процесорами (момент часу t2 на рис.7). Процес продовжується до тих пір, поки відношення R не буде повністю оброблено (до моменту часу t3).
Алгоритм очевидним чином узагальнюється на довільну кількість процесорів.
Запропонований алгоритм балансування завантаження процесорів дозволяє уникнути переміщення по сполучної мережі великих обсягів даних.
Це, зрештою, і забезпечує такій системі продуктивність, порівнянну з продуктивністю SE-кластерів навіть за наявності сильних перекосів даних.
Підіб'ємо підсумки
Очевидно, що паралельні машини баз даних з однорівневою архітектурою на сьогоднішній день практично вже вичерпали ресурс подальшого
ефективного масштабування. На зміну їм приходять нові системи з ієрархічною архітектурою, які можуть включати в себе на два порядки більше
процесорів і дисків.
Однак при побудові ієрархічних систем по дворівневому принципом, коли кластери процесорів з пам'яттю, що розділяється та дисками
об'єднуються в єдину систему "без спільного використання ресурсів", виникає проблема забезпечення високої готовності даних у разі відмов
апаратури. Дійсно, при великій кількості кластерів в системі вірогідність відмови одного з кластерів стає досить великий, і нам
необхідно дублювати одні й ті ж дані на декількох різних кластерах, що по суті зводить нанівець усі переваги ієрархічної організації.
Тому слід очікувати, що подальший розвиток ієрархічних архітектур паралельних машин баз даних піде шляхом створення
багаторівневих гібридних схем, здатних забезпечити високу готовність даних на конфігураціях з кількома сотнями тисяч процесорних вузлів. В якості
прототипу таких систем пропонується паралельна система баз даних "Омега", що розробляється в Челябінському державному університеті, яка має
трирівневу ієрархічну архітектуру типу CD2 і може включати в себе сотні SD2-кластерів. Але оптимальну архітектуру SD2-кластеру ще належить знайти. Ми
плануємо випробувати різні конфігурації SD2-кластерів, варіюючи топологію міжпроцесорних з'єднань, кількість процесорних модулів, кількість
дискових підсистем і кількість дисків у окремої дискової підсистеми.
Робота виконана за підтримки Російського фонду фундаментальних досліджень. Проект 00-07-90077.
Література
1. Ігнатович Н.// СУБД. 1997. № 2. C.5-17.
2.Compaq NonStop SQL/MP. http://www.tandem.com/prod_des/nssqlpd/nssqlpd.htm
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 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.Левін В.К. Вітчизняні суперкомп'ютери сімейства МВС. http://parallel.ru/mvs/levin.html
