У кінці другого тисячоліття людство зробило крок з індустріальної ери в еру інформаційну. Якщо раніше головними були матеріальні ресурси і робоча сила, то тепер вирішальними факторами розвитку суспільства стають інтелект і доступ до інформації. В інформаційному суспільстві люди в основному будуть зайняті у сфері створення, розподілу та обміну інформації, а кожна людина зможе отримати необхідні продукт або послугу в будь-якому місці і в будь-який час.
У напрямку до баз даних
Як відомо, основний інструмент зберігання і переробки інформації - електронні обчислювальні машини (ЕОМ). Перехід до інформаційного суспільства супроводжується лавиноподібним зростанням обсягів інформації, що зберігається в них. Це в свою чергу породжує проблему ефективної організації та пошуку інформації. Для представлення в машинах великих обсягів даних використовуються технології баз даних. База даних являє собою сукупність структурованих і взаємозалежних даних, що зберігаються більш-менш постійно в ЕОМ на магнітних (поки що) носіях, і використовуються одночасно багатьма користувачами в рамках деякого підприємства, організації чи спільноти. Для роботи з базами даних використовується спеціальне системне програмне забезпечення, зване СУБД (Система керування базами даних). Обчислювальний комплекс, що включає в себе відповідну апаратуру (ЕОМ з пристроями зберігання) і працює під управлінням СУБД, називається машиною баз даних.
Перші такі машини з'явилися в другій половині 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 LB, 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