Дві класичні експериментальні системи

System R: загальна організація системи, основи мови SQL
Система управління реляційними базами даних System R розроблялася в дослідницькій лабораторії фірми IBM в 1975-1979 рр. Ця робота вплинула революціонізований чином на розвиток теорії і практики реляційних систем у всьому світі. Саме System R практично довела життєздатність реляційного підходу до управління базами даних.
Після успішного завершення робіт по створенню цієї системи і отримання експериментальних результатів її використання був розроблений цілий ряд комерційно доступних реляційних систем, в тому числі і на основі безпосереднього розвитку System R (можливості однієї з комерційно доступних реляційних систем - DB2 - описуються в перекладеній на російську мову книзі К. Дейта "Керівництво по реляційній СУБД DB2”). Виключно важливий досвід, придбаний при розробці цієї системи. Практично у всій більш пізній реляційній СУБД в тій або іншій мірі використовуються методи, застосовані в System R.
Після завершення розробки System R фірма IBM активно продовжувала роботи по реляційній СУБД, причому в декількох напрямах. Перший напрям ми вже відмічали - розробка комерційної реляційної СУБД. Другий напрям - побудова розподіленої реляційної СУБД на основі ідей System R. Експериментальний варіант такої системи, System R*, був успішно розроблений в IBM. Ця робота також істотно збагатила досвід дослідників і розробників розподіленої СУБД. Нарешті, третій напрям - дослідження і розробка реляційних систем, призначених для нетрадиційних додатків.
Організації СУБД System R присвячена величезна бібліографія. Хоч офіційно розробка цієї системи почалася в 1975 р., перші публікації, пов'язані з цією системою, з'явилися ще в 1974 р. Зокрема, в одній з перших публікацій була запропонована основа базової мови System R SQL (тоді ця мова називалася SEQUEL, і досі багато хто називає його саме так; до речі, розробники System R (а тепер і компанія Oracle) рекомендують вимовляти назву SQL саме як SEQUEL). Оскільки публікації з'являлися по ходу практичної реалізації системи, кожна з них відображає стан справ (ідейне і практичне) саме на тому етапі роботи, коли була написана відповідна стаття. Деякі ідеї і уявлення, природно, змінювалися по ходу роботи. Порівняно закінчене уявлення про систему загалом дають тільки заключні публікації. З іншого боку, багато які цікаві моменти абсолютно не відображені в цих останніх статтях, і ми постараємося привести більш повний огляд ідей і методів, застосованих в System R. При цьому ми будемо зупинятися і на деяких можливих альтернативних рішеннях, які були знайдені розробниками System R, але практично не були використані.
7.1. Термінологія, що використовується
Що стосується загальної термінології реляційного підходу, ми будемо активно користуватися відповідними термінами. До таких термінів відносяться назви реляційних операцій - селекція, проекція, з'єднання; назви теоретико-множинних операцій - об'єднання, перетин, різниця і т.д.
У тих випадках, коли традиційна термінологія System R розходиться із загальноприйнятою, ми будемо віддавати перевагу термінології System R. Зокрема, це стосується використання терміну "поле відношення" замість "атрибут відношення".
У самої System R при переході до комерційних систем також сталася деяка зміна термінології. Зокрема, в деяких останніх публікаціях з'явилася тенденція до вживання більше за звичних в середовищі користувачів IBM термінів: файл, запис і т.д. Ми будемо використати терміни System R, більш близькі реляційним системам. Далі ми опишемо деякі основні терміни System R, виходячи при цьому в основному не з теоретичних міркувань, а прагнучи відобразити практичні аспекти відповідних понять.
Базовим поняттям System R є поняття таблиці (наближений до реалізації еквівалент основного поняття реляційного підходу відношення; іноді, в залежності від контексту, ми будемо використати і цей термін). Таблиця - це деяка регулярна структура, що складається з кінцевого набору однотипних записів - кортежів. Кожний кортеж одного відношення складається з кінцевого (і однакового) числа полів кортежу, причому i-те поле кожного кортежу одного відношення може містити дані тільки одного типу, і набір допустимих типів даних в System R приречений і фіксований. Внаслідок регулярності структури відношення поняття поля кортежу розширяється до поняття поля таблиці. I-те поле таблиці можна трактувати як набір одномісних кортежів, отриманих вибіркою i-тих полів з кожного кортежу цієї таблиці, тобто в загальноприйнятій термінології як проекцію відношення на i-тий атрибут. У термінологію System R не входить поняття домену, воно замінюється тут поняттям типу поля, тобто типом даних, зберігання яких в даному полі допускається (це не цілком еквівалентна заміна, але така реальність System R).
Таблиці, що складають базу даних System R, можуть фізично зберігатися в одному або декількох сегментах, які простіше усього розуміти як файли зовнішньої пам'яті (і це цілком відповідає дійсності). Сегменти розбиваються на сторінки, в яких розташовуються кортежі відносин і допоміжні службові структури даних індекси. Відповідно, кожний сегмент містить дві групи сторінок - сторінки даних і сторінки індексної інформації. Сторінки кожної групи мають фіксований розмір, але сторінки з індексною інформацією менше по розміру, ніж сторінки даних. У сторінках даних можуть розташовуватися кортежі більш, ніж одного відношення (ця дуже важлива властивість фізичної організації баз даних System R; наступні з цієї організації переваги роз'яснимо пізніше).
Цим, звичайно, не вичерпується набір понять System R, але інші терміни ми будемо пояснювати по ходу викладу, оскільки для цього потрібний відповідний понятійний контекст.
7.2. Основні цілі System R і їх зв'язок з архітектурою системи
Основними цілями розробників System R були наступні:
забезпечити ненавігаційний інтерфейс високого рівня користувача з системою, що дозволяє досягнути незалежності даних і дати можливість користувачам працювати максимально ефективно;
забезпечити різноманіття допустимих способів використання СУБД, включаючи транзакції, що програмуються, діалогові транзакції і генерацію звітів;
підтримувати динамічно змінну середу баз даних, в якій відносини, індекси, уявлення, транзакції і інші об'єкти можуть легко додаватися і знищуватися без припинення нормального функціонування системи;
забезпечити можливість паралельної роботи з однією базою даних багатьох користувачів з допущенням паралельної модифікації об'єктів бази даних при наявності необхідних засобів захисту цілісності бази даних;
забезпечити засоби відновлення узгодженого стану баз даних після різного роду збоїв апаратури або програмного забезпечення;
забезпечити гнучкий механізм, що дозволяє визначати різні представлення даних, що зберігаються і обмежувати цими уявленнями доступ користувачів до бази даних по вибірці і модифікації на основі механізму авторизації;
забезпечити продуктивність системи при виконанні згаданих функцій, порівнянну з продуктивністю існуючої СУБД низького рівня.
Передусім зазначимо, що в основному поставлені цілі при розробці System R були досягнуті. Розглянемо тепер, якими Засобами були досягнуті ці цілі, і як більш точно можна інтерпретувати їх в контексті System R.
Основою System R є реляційна мова SQL. Іноді його називають мовою запитів або мовою маніпулювання даними, але насправді його можливості набагато ширше. Засобами SQL (з відповідною системною підтримкою) вирішуються багато які з поставлених цілей. Мова SQL включає засоби динамічної компіляції запитів, на основі чого можлива побудова діалогових систем обробки запитів. Допускається динамічна параметризація статично відкомпільованих запитів, внаслідок чого можлива побудова ефективних (що не вимагають динамічної компіляції) діалогових систем зі стандартними наборами (що параметризуються) запитів.
Засобами SQL визначаються всі доступні користувачеві об'єкти баз даних: таблиці, індекси, уявлення. Є засоби знищення будь-якого такого об'єкта. Відповідні оператори мови можуть виконуватися в будь-який момент, і можливість виконання операції даним користувачем залежить від раніше наданих йому прав.
Що стосується цілісності баз даних, то в System R під цілісним станом бази даних розуміється стан, що задовольняє набору даних предикатів цілісності, що зберігаються при базі. Ці предикати, звані в System R умовами цілісності (assertions), задаються також Засобами мови SQL. Будь-яка пропозиція мови виконується в межах деякої транзакції - неподільної в значенні стану бази даних послідовності пропозицій мови. Неподільність означає, що всі зміни, вироблені в межах однієї транзакції або цілком відображаються в стані бази даних, або повністю в ньому відсутні. Остання можливість виникає при відкаті транзакції, який може статися з ініціативи користувача (при виконанні відповідного оператора SQL) або з ініціативи системи.
Однієї з причин відкату транзакції з ініціативи системи є якраз порушення цілісності бази даних внаслідок дій даної транзакції (інші можливі умови відкату транзакції з ініціативи системи ми розглянемо пізніше). Мова SQL містить засіб установки так званих точок збереження (savepoint). При відкаті транзакції, що ініціюється користувачем можна указати номер точки збереження, вище за яке відкат не розповсюджується. Відкат транзакції, що Ініціюється системою проводиться до найближчої точки збереження, в якій умова, що викликала відкат, вже відсутній. Зокрема, відкат ініційований внаслідок порушення умови цілісності, проводиться до найближчої точки збереження, в якій умови цілісності додержані. (Помітимо, що засоби установки точок збереження відсутні в комерційних розширеннях System R).
Природно, що для реального виконання відкату транзакції необхідно запам'ятовування деякої інформації про виконання транзакції. У System R для цих і інших цілей використовується спеціальний набір даних - журнал, в який вміщуються записи про всі, що міняють стан бази дані операції всіх транзакцій. При відкаті транзакції відбувається процес зворотного виконання транзакції (undo), в ході якого в зворотному порядку виконуються всі зміни, що записані в журналі.
У мові SQL є засіб визначення так званих умовних впливів (triggers), що дозволяють автоматично підтримувати цілісність бази даних при модифікаціях її об'єктів. Умовний вплив - це каталогізована операція модифікації, для якої задана умова її автоматичного виконання. Особливо істотна наявність такого апарату в зв'язки з наявністю представлень, що розглядаються нижче бази даних, якими може бути обмежений доступ до бази даних для ряду користувачів. Можлива ситуація, коли такі користувачі просто не можуть дотримувати цілісність бази даних без автоматичного виконання умовних впливів, оскільки вони просто "не бачать" всієї бази даних і, зокрема, не можуть представити всіх обмежень її цілісності. Помітимо, що, за винятком ранніх публікацій по System R, реалізація механізму умовних впливів ніде не описувалася, хоч в принципі підходи до реалізації досить зрозумілі. Цей механізм не реалізований в комерційних системах, що виникли на базі System R. Видимо, це пов'язано з виникаючими додатковими непередбачуваними для користувачів накладними витратами при виконанні транзакцій.
Мова SQL містить засоби визначення уявлень. Уявлення - це записаний іменований запит на вибірку даних (з однієї або декількох таблиць). Оскільки SQL - це реляційна мова, то результатом виконання будь-якого запиту на вибірку є таблиця, і тому концептуально можна відноситися до будь-якого уявлення як до таблиці (при визначенні уявлення можна, зокрема, привласнити імена полям цієї таблиці). У мові допускається використання раніше певних уявлень практично скрізь, де допускається використання таблиць (з деякими обмеженнями з приводу можливостей модифікації через уявлення). Наявність можливості визначати уявлення в сукупності з розвиненою системою авторизації дозволяє обмежити доступ деяких користувачів до бази даних виділеним набором уявлень.
Авторизація доступу до бази даних заснована також на засобах SQL. При створенні будь-якого об'єкта бази даних виконуючу цю операцію користувач стає повновладним власником цього об'єкта, тобто може виконувати по відношенню до цього об'єкта будь-яку функцію з приреченого набору. Далі цей користувач може виконати оператор SQL, що означає передачу всіх його прав на цей об'єкт (або їх підмножини) будь-якому іншому користувачеві. Зокрема, цьому користувачеві може бути передане право на передачу всіх переданих йому прав (або їх частини) третьому користувачеві і т.д. Одним з прав користувача по відношенню до об'єкта є право на вилучення у інших користувачів всіх або деяких прав, які раніше ним були передані. Ця операція розповсюджується транзитивно на всіх подальших спадкоємців цих прав.
Наявність в мові засобів визначення представлень і авторизації в принципі дозволяє обійтися при експлуатації System R без традиційного адміністратора баз даних, оскільки практично всі системні дії проводяться на основі засобів SQL. Проте, якщо організаційно адміністратор баз даних потрібно, то його робота досить спрощується за рахунок уніфікованого набору засобів управління. Крім того, в System R каталоги баз даних підтримуються також у вигляді таблиць, і до них застосовані всі запити мови SQL. Помітимо, що в комерційній СУБД з'явився ряд додаткових утиліт, не пов'язаних з мовою SQL (наприклад, утиліти збору статистики або масового завантаження бази даних), і в цих системах, видимо, без адміністратора бази даних не обійтися.
По частині забезпечення паралельної роботи багатьох користувачів з однією базою даних, основний підхід System R полягає в тому, що користувач не зобов'язаний знати про наявність інших, конкуруючих з ним за доступ до бази даних, користувачів, тобто система відповідальна за забезпечення ізольованості користувачів з гарантією відсутності їх взаємного впливу в межах транзакцій. З цього слідує, по-перше, що в інтерфейсі користувача з системою (тобто в мові SQL) не повинно бути засобів регулювання взаємодій з іншими користувачами і, по-друге, що система повинна забезпечити автоматичну серіалізацію набору транзакцій, тобто забезпечити режим виконання цього набору транзакцій, еквівалентний за кінцевим результатом деякому послідовному виконанню цих транзакцій. Ця проблема вирішується в System R за рахунок автоматичного виконання синхронізаційних захоплень по відношенню до всіх змінних об'єктів бази даних. Є ряд тонкості, пов'язаної з такою синхронізацією, на якій ми зупинимося нижче.
Одним з основних вимог до СУБД взагалі і до System R зокрема є забезпечення надійності баз даних по відношенню до різного роду збоям. До таких збоїв можуть відноситися програмні помилки прикладного і системного рівня, збої процесора, поломки зовнішніх носіїв і т.д. Зокрема, до одного з видів збоїв можна віднести згадувані вище порушення цілісності бази даних, і автоматичний відкат транзакції, що ініціюється системою - це системний засіб відновлення бази даних після збоїв такого роду. Як ми відмічали, таке відновлення відбувається шляхом зворотного виконання транзакції на основі інформації про внесені нею зміни, записані в журналі. На інформації журналу засноване відновлення бази даних і після збоїв іншого роду. Управління журналізацією і відновленням в System R вельми цікаве, методи, що застосовуються в ряді випадків відрізняються від методів, що використовуються в іншій СУБД.
Що стосується природних вимог до ефективності системи, то тут основні рішення пов'язані зі специфікою фізичної організації баз даних на зовнішній пам'яті, буферизацією сторінок бази даних, що використовуються в оперативній пам'яті і розвиненою технікою оптимізації запитів, сформульованих на SQL, що проводиться на стадії їх компіляції.
Структурна організація System R цілком узгодиться з поставленими при її розробці цілями і вибраними рішеннями. Основними структурними компонентами System R є система управління реляційною пам'яттю (Relational Storage System - RSS) і компілятор запитів мови SQL. RSS забезпечує інтерфейс досить низького, але достатнього для реалізації SQL, рівня для доступу до даних, що зберігаються в базі. Синхронізація транзакцій, журналізація змін і відновлення баз даних після збоїв також відносяться до числа функцій RSS. Компілятор запитів використовує інтерфейс RSS для доступу до різноманітної довідкової інформації (каталоги відносин, індексів, прав доступу, умов цілісності, умовних впливів і т.д.) і виробляє робочі програми, що виконуються надалі також з використанням інтерфейсу RSS. Таким чином, система природно розділяється на два рівні - рівень управління пам'яттю і синхронізацією, фактично, що не залежить від базової мови запитів системи, і язиковий рівень (рівень SQL), на якому вирішується більшість проблем System R. Помітимо, що ця незалежність швидше умовна, чим абсолютна: мову SQL можна замінити на іншу мову, але він повинен володіти приблизно такою ж семантикою.
Далі ми послідовно розглянемо особливості організації RSS, процес компіляції і оптимізації запитів і техніку виконання відкомпілювати транзакцій (включаючи відмічену вище можливість динамічної компіляції запитів).
7.3. Організація зовнішньої пам'яті в базах даних System R
Як ми відмічали, база даних System R розташовується в одному або декількох сегментах зовнішньої пам'яті. Кожний сегмент складається з сторінок даних і сторінок індексної інформації. Розмір сторінки даних в сегменті може бути вибраний рівним або 4, або 32 кілобайтам; розмір сторінки індексної інформації рівний 512 байтам. Крім того, при роботі RSS підтримується додатковий набір даних для ведення журналу. Для підвищення надійності журналу (а це найбільш критична інформація; при її втраті відновлення бази даних після збоїв неможливе) цей набір даних дублюється на двох зовнішніх носіях.
У кожній сторінці даних зберігаються кортежі одного або декількох відносин. Фундаментальним поняттям RSS є ідентифікатор кортежу (tuple identifier - tid). Гарантується незмінність tid'а під весь час існування кортежу в базі даних незалежно від переміщень кортежу всередині сторінки і навіть при переміщенні кортежу в іншу сторінку. Реально tid являє собою парі . При цьому кортеж може реально розташовуватися в даній сторінці:
або в іншій сторінці:
У другому випадку описувач кортежу містить не координати кортежу в даній сторінці, а tid, що вказує на реальне положення кортежу в іншій сторінці. Легко бачити, що застосування такого підходу дозволяє обмежитися максимум одним рівнем непрямого відношення.
Оскільки допускається знаходження в одній сторінці даних кортежів різних відносин, кожний кортеж повинен, крім змістовної частини, включати службову інформацію, що ідентифікує відношення, якому належить даний кортеж. Крім того, в System R (точніше, в мові SQL) допускається динамічне доповнення полів до існуючих відносин. При цьому реально відбувається лише модифікація описувача відношення у відношенні-каталозі відносин. У існуючому кортежі відношення нове поле виникає тільки при модифікації цього кортежу, що торкається нове поле. Це дозволяє уникнути масової перебудови відношення, що зберігається при доданні до нього нових полів, але, природно, вимагає зберігання при кортежі додаткової службової інформації, що визначає реальне число полів в даному кортежі. (Помітимо, що видаляти існуючі поля існуючого відношення в SQL System R не дозволяється).
На основі наявності незмінних під час існування кортежів tid'ів в System R підтримуються додаткові керуючі структури - індекси. Кожний індекс визначений на одному або декількох полях відношення, значення яких складають його ключ, і дозволяє проводити прямий пошук по ключу кортежів (їх tid'ів) і послідовне сканування відношення по індексу, починаючи з вказаного ключа, в порядку зростання або убування значень ключа. Деякі індекси при їх створенні можуть володіти атрибутом унікальності. У такому індексі не допускаються дублікати ключа. Цей єдиний засіб SQL вказівки системі первинного ключа відношення (фактично, набору первинного і всіх альтернативних ключів відношення).
Для організації індексів в System R застосовується техніка В-дерев. Кожний індекс займає окремий набір сторінок, номер кореневої сторінки запам'ятовується в описувачі індексу. Використання В-дерев дозволяє досягнути ефективності при прямому пошуку, оскільки вони в силу своєї сильної гіллястості володіють невеликою глибиною. Крім того, В-дерева зберігають порядок ключів в листових блоках ієрархії, що дозволяє проводити послідовне сканування відношення в порядку зростання або убування значень полів, на яких визначений індекс. Фундаментальна властивість В-дерев - автоматичне балансування дерева - допускає вироблення лише локальних модифікацій індексу при переповненнях і спустошеннях сторінок індексу. (Ми досить вільно використовуємо тут термін В-дерево. Насправді в System R використовується модифікований в порівнянні з вихідним варіант В-дерев, який називають В*-, а іноді В+-деревами). У самих В-деревах System R нічого особливого ні; більш детально ми на цьому зупинятися не будемо. Зазначимо тільки, що System R, наскільки нам відомо, була першою системою, в якій для організації індексів використовувалися В-дерева. Цю традицію дотримує більшість реляційних систем, що виникли після System R.
Видимо, найбільш важливою особливістю фізичної організації баз даних в System R є можливість забезпечення кластеризації пов'язаних кортежів одного або декількох відносин. Під кластеризацією кортежів розуміється фізично близьке розташування (в межах однієї сторінки даних) логічно пов'язаних кортежів. Забезпечення відповідної кластеризації дозволяє добитися високої ефективності системи при виконанні виділеного класу запитів. Внаслідок великої важливості поняття кластеризації в System R і її розвитках розглянемо історію питання більш детально.
У остаточному варіанті System R існує тільки один засіб визначення умов кластеризації відношення - оголосити до заповнення відношення один (і тільки один) індекс, визначений на полях цього відношення, кластеризованим. Тоді, якщо заповнення відношення кортежами виготовляється в порядку зростання або убування значень полів кластеризації (в залежності від атрибутики індексу), система фізично розташовує кортежі в сторінках даних в тому ж порядку. Крім того, в кожній сторінці даних кластеризованого відношення залишається деякий резервний вільний простір. При подальших вставках кортежів в таке відношення система прагне вмістити кожний кортеж в одну з сторінок даних, в яких вже знаходяться кортежі цих відносин з такими ж (або близькими) значеннями полів кластеризації. Природно, що підтримувати ідеальну кластеризацію відношення можна тільки до певної межі, поки не вичерпається резервна пам'ять в сторінках. Далі цієї межі міра кластеризації відношення починає меншати, і для відновлення ідеальної кластеризації відношення потрібна фізична реорганізація відношення (її можна виробити коштами SQL).
Очевидною перевагою кластеризації відношення є те, що при послідовному скануванні кластеризованого відносин з використанням кластеризованого індексу буде потрібне рівне стільки читання сторінок даних із зовнішньої пам'яті, скільки сторінок займають кортежі цього відношення. Отже, при правильно вибраних критеріях кластеризації запити, пов'язані із завданням умов на полях кластеризації можна виконати майже оптимально.
У ранніх версіях System R існував ще один спосіб фізичного доступу до кортежів відношення і, відповідно, ще один спосіб вказівки умови кластеризації з використанням так званих зв'язків (links). На рівні фізичного уявлення зв'язок - це фізичне посилання (tid) з одного кортежу на інший (не обов'язково одного відношення). У мові SEQUEL (до того моменту, коли його сталі називати SQL) існували засоби визначення зв'язків в ієрархічній манері: можна було оголосити деяке відношення батьківським по відношенню до того ж або іншому відношенню-нащадку. При цьому вказувалися поля батьківського відношення і відношення-нащадка, у відповідності зі значеннями яких утворювалася ієрархія. Правила побудови були дуже простими - проводилися зв'язки між кортежем батьківського відношення до всіх кортежів відношення-нащадка з тими ж значеннями полів скріплення. Насправді, всі кортежі відношення-нащадка із загальним значенням полів скріплення утворювали кільцевий список, на який проводився один зв'язок з відповідного кортежу батьківського відношення. Природно, від відношення-родителя була потрібна унікальність по відношенню до значень полів скріплення.
Потрібно помітити, що ми описали спосіб використання механізму зв'язків, який підтримувався в ранніх версіях SEQUEL. У інтерфейсі RSS System R цього періоду допускалася можливість довільного проведення зв'язків без урахування збігу значень полів скріплення. Тим самим, в системі загалом не використовувалися всі можливості RSS, які з лишком перевершували потребі організації ієрархічних бінарних зв'язків по збігу полів скріплення.
Для одного відношення допускалося створення багатьох зв'язків: кортеж відношення міг бути родителем декількох ієрархій і входити в дещо інших ієрархій як нащадок. При цьому один зв'язок міг бути оголошений кластеризованим. Тоді система прагнула вмістити в одну сторінку даних всі кортежі однієї ієрархії. При цьому, природно, використовувалася можливість розміщення в одній сторінці даних кортежів декількох відносин. Основне значення такої кластеризації полягало в можливості оптимізації виконання деяких запитів, що включають (екві)з'єднання двох пов'язаних відносин у відповідності зі значеннями полів скріплення.
У більш пізніх публікаціях по System R згадки про механізм зв'язків зникли, з чого можна укласти, що розробники відмовилися від його використання. Думається, що основними причинами відмови від використання зв'язків були наступні. По-перше, засоби побудови зв'язків, що забезпечуються RSS, були дуже низького рівня, набагато більш низького, ніж засоби підтримки індексів. Якщо при занесенні кортежу RSS забезпечувала автоматичну корекцію всіх індексів, то для корекції зв'язків був потрібен виконати ряд додаткових звертань до RSS, через що час виконання операції занесення кортежу, звичайно, збільшувалося (те ж торкається операцій видалення і модифікації кортежу). По-друге, при реалізації цього механізму, виникають додаткові синхрозаційні проблеми нижнього рівня (рівня спільного доступу до сторінок даних). Зокрема, наявність прямих посилань між сторінками даних збільшує імовірність виникнення синхронізаційних тупиків. Нарешті, по-третє, всі ці додаткові накладні витрати не окупалися що надаються механізмом зв'язків перевагами. Дійсно, максимального ефекту від використання зв'язків можна досягнути тільки при виконанні операції з'єднання двох кластеризованих по цьому зв'язку відносин, якщо поле з'єднання співпадає з полем скріплення, і умови, що накладаються на батьківське відношення, виділяють в ньому рівне один кортеж. Очевидно, що такі запити на практиці рідкі. (Зазначимо, що приведені міркування належать автору і не викладалися в публікаціях по System R, так що насправді причини могли бути і іншими.)
Крім відносин і індексів при роботі System R на зовнішній пам'яті можуть розташовуватися ще і тимчасові об'єкти - списки (lists). Список - це миттєвий знімок деякої вибірки з проекцією кортежів одного відношення, можливо, впорядкований у відповідності зі значеннями деяких полів. Засоби роботи зі списками є в інтерфейсі RSS, але їх, природно, ні в SQL. Відповідно, ці засоби використовуються тільки всередині системи при виконанні запитів (зокрема, один з найбільш ефективних алгоритмів виконання з'єднань заснований на використанні відсортованих списків кортежів). Публікації по System R не дають точного уявлення про структури даних, що використовуються при організації списків, але виходячи із здорового глузду можна передбачити, що вони влаштовані не так, як відносини (наприклад, для кортежу, що входить в список, не потрібна адресація через tid), і що розташовуються вони у тимчасових файлах (у разі збою системи всі тимчасові об'єкти пропадають).
7.4. Інтерфейс RSS
Ми опишемо своє уявлення про інтерфейс RSS, яке не відповідає в точності жодній з публікацій з приведеного списку літератури, а є швидше деякою компіляцією, що узгоджується із завершальними публікаціями.
Як ми вже відмічали, на рівні RSS відсутнє іменування об'єктів бази даних, що вживається на рівні SQL. Замість імен об'єктів використовуються їх унікальні ідентифікатори, що є прямими або непрямими адресами внутрішніх описувачів об'єктів на зовнішній пам'яті для постійних об'єктів або в оперативній пам'яті для тимчасових об'єктів.
Можна виділити наступні групи операцій:
операції сканування відносин і списків;
операції створення і знищення постійних і тимчасових об'єктів бази даних;
операції модифікації відносин і списків;
операція доповнення поля до відношення;
операції управління проходженням транзакції;
операція явної синхронізації.
Операції групи сканування дозволяють послідовно в порядку, що визначається типом сканування, прочитати кортежі відношення або списку, що задовольняють необхідним умовам. Група включає операції OPEN, NEXT і CLOSE, що означають, відповідно, почало сканування, вимога наступного кортежу, що задовольняє умовам, і кінець сканування.
Для відносин можливі два режими сканування: по відношенню і по індексу. При скануванні по відношенню єдиним параметром операції OPEN є ідентифікатор відношення (що включає, до речі, і ідентифікатор сегмента, в якому це відношення зберігається). Внаслідок того, що в System R допускається розміщення в одній сторінці даних кортежів декількох відносин, сканування по відношенню передбачає послідовний перегляд всіх сторінок сегмента з виділенням в них кортежів, що входять в дане відношення; це дуже дорогий спосіб сканування відношення. При цьому порядок вибірки кортежів визначається їх фізичним розміщенням в сторінках сегмента, тобто приречений системою.
При відкритті сканування відношення по одному з його індексів в число параметрів операції OPEN входить ідентифікатор індексу, визначеного раніше на полях цього відношення. Крім того, можна указати діапазон сканування в термінах значень полів, що складають ключ індексу. При відкритті сканування по індексу проводиться початкова установка покажчика сканування в позицію листа В-дерева індексу, відповідну лівій межі заданого діапазону. Процес сканування складається в послідовному просуванні по листових вершинах індексу до досягнення правої межі діапазону сканування з вибіркою tid'ів і читанням відповідних кортежів. Легко бачити, що якщо сканування проводиться не по кластеризованому індексу, то в гіршому випадку може бути потрібні стільки читання сторінок даних із зовнішньої пам'яті, скільки tid'ів було зустріти, тобто ефективність сканування по індексу визначається "шириною" заданого діапазону сканування. При цьому, звичайно, є та перевага, що порядок сканування відповідає порядку зростання або убування значень ключа індексу.
Нарешті, при скануванні списку, як і при скануванні по відношенню, єдиним параметром операції OPEN є ідентифікатор списку, але, на відміну від сканування по відношенню це сканування максимально ефективне: читаються тільки сторінки, що містять кортежі з даного списку, і порядок сканування співпадає з порядком занесення кортежів в список або порядком списку, якщо він впорядкований.
Внаслідок успішного виконання операції відкриття сканування (якщо немає помилок в параметрах) виробляється і повертається ідентифікатор сканування, який використовується як вхідний параметр інших операцій цієї групи.
Операція NEXT виконує читання наступного кортежу вказаного сканування, що задовольняє умовам даної операції. Умова являє собою диз'юнктивну нормальну форму простих умов, що відносяться до значень вказаних полів відношення. Проста умова - це умова вигляду , де op - операція порівняння =, = або !=. Загальна умова є параметром операції NEXT. Семантика операції NEXT наступна: починаючи з поточної позиції сканування вибираються кортежі відношення в порядку, що визначається типом сканування, доти, поки не зустрінеться кортеж, значення полів якого задовольняють вказаній умові; цей кортеж і є результатом операції; якщо при вибірці наступного кортежу досягається права межа діапазону сканування (права межа значення ключа при скануванні по індексу або останній кортеж відношення або списку при скануванні без індексу), виробляється особлива ознака результату. Після цього єдиною розумною дією є закриття сканування - операція CLOSE.
Операція CLOSE може бути виконана в даній транзакції по відношенню до будь-якого раніше відкритого сканування незалежно від його стану (тобто незалежно від того, чи досягнута при скануванні правий межа діапазону сканування). Параметром операції є ідентифікатор сканування, і її виконання приводить до того, що цей ідентифікатор стає недійсним (і, відповідно, знищуються службові структури пам'яті RSS, що відносяться до даного сканування).
Група операцій створення і знищення постійних і тимчасових об'єктів бази даних включає операції створення таблиць (CREATE TABLE), списків (CREATE LIST), індексів (CREATE IMAGE) і знищення будь-якого з подібних об'єктів (DROP TABLE, DROP LIST і DROP IMAGE). Вхідним параметром операцій створення таблиць і списків є специфікатор структури об'єкта, тобто число полів об'єкта і специфікатори їх типів. Крім того, при специфікації полів відношення вказується допущення або недопущення невизначених значень полів в кортежах цього відношення або списку (невизначені значення кодуються спеціальним образом; будь-яка операція порівняння константи даного типу з невизначеним значенням по визначенню виробляє значення FALSE, крім операції порівняння на збіг зі спеціальною літеральною константою NULL). Внаслідок виконання цих операцій заводиться описувач відносно службовому описувачів відносин або оперативній пам'яті (в залежності від того, чи створюється постійний об'єкт або тимчасовий), і виробляється ідентифікатор об'єкта, який служить вхідним параметром інших операцій, що відносяться до відповідного об'єкта (зокрема, параметром операції OPEN при відкритті сканування об'єкта).
Вхідними параметрами операції CREATE IMAGE є ідентифікатор таблиці, для якої створюється індекс, список номерів полів, значення яких складають ключ індексу, і ознаки упорядкування по зростанню або спаданню для всіх полів, що складають ключ. Крім того, може бути вказаний ознака унікальності індексу, тобто заборони наявності в даному індексі ключів-дублікатів. Якщо операція виконується по відношенню до пустої в цей момент таблиці, то виконання операції таке ж простої, як і для операцій створення таблиць і списків: створюється описувач відносно службовому описувачів індексів і повертається ідентифікатор індексу (який, зокрема, використовується як вхідний параметр операції відкриття сканування відношення по індексу).
Якщо ж до моменту створення індексу відповідна таблиця не пуста (а це допускається), то операція стає істотно більш такою, що дорого коштує, оскільки при її виконанні відбувається реальне створення В-дерева індексу, що вимагає щонайменше одного послідовного перегляду відношення. При цьому, якщо індекс, що створюється має ознаку унікальності, то це контролюється при створенні В-дерева, і якщо унікальність порушується, то операція не виконується (тобто індекс не створюється). З цього слідує, що хоч створення індексів в динаміці не забороняється, більш ефективно створювати всі індекси на даній таблиці до її заповнення. Помітимо, що створення кластеризованого індексу для непустого відношення заборонене, оскільки відповідну кластеризацію відношення без його реструктуризації отримати неможливо.
Операції DROP TABLE, DROP LIST і DROP IMAGE можуть бути виконані в будь-який момент незалежно від стану об'єктів. Виконання операції приводить до знищення відповідного об'єкта і, внаслідок цього, недійсність його ідентифікатора.
Потрібно зазначити, що масові операції над постійними об'єктами (CREATE IMAGE, DROP TABLE і DROP IMAGE) вимагають додаткових накладних витрат в зв'язку з необхідністю забезпечення можливості відкатів транзакції, внаслідок чого потрібне виконання масових зворотних дій. Особливо сильно це торкається операцію знищення непустих таблиць, оскільки вимагає журналізації тих, що всіх містяться в них до моменту знищення кортежів. Тому, хоч знищення непустих таблиць і не заборонено, треба мати на увазі, що це операція, що дуже дорого коштує.
Група операцій модифікації відносин і списків включає операції вставки кортежу у відношення або список (INSERT), видалення кортежу з відношення (DELETE) і модифікації кортежу у відношенні (UPDATE).
Параметрами операції вставки кортежу є ідентифікатор відношення або списку і набір значень полів кортежу. Серед значень полів можуть бути літеральні невизначені значення NULL. Природно, при виконанні операції контролюється допустимість невизначених значень у відповідних полях. При занесенні кортежу в кластеризоване відношення пошук місця в сегменті під кортеж проводиться з використанням кластеризованого індексу: система намагається вставити кортеж в сторінку даних, що вже містить кортежі з тими ж або близькими значеннями полів кластеризації. При занесенні кортежу в некластеризоване відношення місце під кортеж виділяється в першій відповідній сторінці даних. Нарешті, при вставці кортежу в список він вміщується в кінець списку.
При занесенні кортежу в постійне відношення проводиться корекція всіх індексів, визначених на цьому відношенні. Реально це виражається у вставці нового запису у всі В-дерева індексів. При цьому можуть статися переповнення однієї або декількох сторінок індексу, що спричинить переливання частини записів в сусідні сторінки або розщеплення сторінок. Якщо індекс визначений з атрибутом унікальності, то перевіряється дотримання цієї умови, і якщо воно порушене, операція вставки вважається невиконаною. З цього видно, що операція вставки кортежу тим більше складна, чим більше індексів визначено для даної таблиці (це відноситься і до операцій видалення і модифікації кортежів).
Внаслідок успішного виконання операції вставки кортежу у відношення виробляється tid нового кортежу, який повідомляється як параметр у відповідь і може бути надалі використаний як прямий параметр операцій видалення і модифікації кортежів відношення. При занесенні кортежу в список значення tid'у не виробляється (списки допускають тільки послідовне сканування і додання нових кортежів в кінець, над ними не можна визначити індексів, тому непряма адресація кортежів списків через tid'и не потрібно).
Операції видалення і модифікації кортежів допускаються тільки для кортежів постійних таблиць. Природно, що для виконання цих операцій необхідно ідентифікувати відповідний кортеж. Інтерфейс RSS допускає два способи такої ідентифікації: за допомогою tid'а кортежу (явна адресація) і з використанням ідентифікатора відкритого до цього часу сканування. Перший варіант можливий, оскільки tid кортежу повідомляється як параметр у відповідь операції занесення кортежу в постійну таблицю. При ідентифікації кортежу за допомогою ідентифікатора сканування мається на увазі кортеж, прочитаний за допомогою останньої операції NEXT. Якщо при такій ідентифікації виконана операція DELETE або UPDATE, що зачіпає порядок сканування (тобто сканування ведеться по індексу і операція модифікації міняє поле кортежу, що входить до складу ключа цього індексу), те поточний кортеж скану втрачається, і його ідентифікатор не можна використати для ідентифікації кортежу до виконання наступної операції NEXT.
Єдиним параметром операції DELETE є ідентифікатор кортежу (tid або ідентифікатор сканування). Параметри операції UPDATE включають, крім цього ідентифікатора, специфікацію змінних полів кортежу (список номерів полів і їх нових значень). Серед значень можуть знаходитися літеральні зображення невизначених значень, якщо відповідні поля відношення допускають зберігання невизначених значень.
При виконанні операції DELETE проводиться корекція всіх індексів, визначених на даному відношенні. Операція UPDATE також може спричинити корекцію індексів, якщо торкається поля, що входять до складу їх ключів.
Крім описаних "атомарних" операцій сканування і модифікації таблиць і списків, інтерфейс RSS включає одну "макрооперацію", що дозволяє за одне звертання до RSS побудувати відсортований по значенням заданих полів список. Ця операція - BUILDLIST - включає сканування заданого відношення або списку, створення нового списку, в який включаються вказані поля вибираних кортежів, і сортування побудованого списку у відповідності зі значеннями вказаних полів. Ідентифікатор наново побудованого відсортованого списку є параметр у відповідь операції.
Відповідно, параметрами операції BUILDLIST є набір параметрів для відкриття сканування (допускається будь-який спосіб сканування), список номерів полів, що складають кортежі нового списку, і список номерів полів, по яких треба проводити сортування (як і у разі створення нового індексу, можна окремо для кожного з цих полів указати вимогу до сортування по зростанню або спаданню значень даного поля). Окремим параметром операції BUILDLIST є ознака, у відповідності зі значенням якого допускаються або не допускаються кортежі-дублікати в новому списку. Забігаючи уперед, помітимо, що допущення або недопущення дублікатів у відсортованому списку залежить від того, для яких цілей він будується. Наприклад, якщо список будується для виконання операції з'єднання, то дублікатів в ньому бути не повинне. Якщо ж список будується для обчислення агрегатних функцій (COUNT, AVG і т.д.), те дублікати з нього прибирати не можна. Більш детально ми розглянемо цей і близькі питання в зв'язку з проблемами оптимізації запитів в System R.
Операція RSS доповнення поля до існуючого відношення дозволяє в динаміці змінювати схему таблиці. Параметрами операції CHANGE є ідентифікатор існуючої таблиці і специфікація нового поля (його тип). При виконанні операції змінюється тільки описувач даного відношення відносно службовому описувачів відносин. Як ми вже відмічали в попередньому підрозділі, до виконання першої операції UPDATE, що торкається нове поле таблиці, реально ні в одному кортежі таблиці пам'ять під нове поле виділятися не буде. За умовчанням значення нового поля у всіх кортежах таблиці, в які ще не проводилося явне занесення значення, вважаються невизначеними. Тим самим, ні для одного поля, динамічно доданого до існуючої таблиці, не може бути заборонено зберігання невизначених значень.
Кожна операція RSS виконується в межах деякої транзакції. Інтерфейс RSS включає набір операцій управління проходженням транзакції: почати транзакцію (BEGIN TRANSACTION), закінчити транзакцію (END TRANSACTION), встановити точку збереження (SAVE) і виконати відкат до вказаної точки збереження або до початку транзакції (RESTORE).
Ми не відмічали цього раніше, але насправді при зверненні до будь-якої функції RSS, крім BEGIN TRANSACTION, повинен вказуватися ще один параметр - ідентифікатор транзакції. Цей ідентифікатор і виробляється при виконанні операції BEGIN TRANSACTION, яка сама вхідних параметрів не вимагає.
У будь-якій точці транзакції до виконання операції END TRANSACTION може бути виконаний відкат даної транзакції, тобто зворотне виконання всіх змін, вироблених в даній транзакції, і відновлення стану сканів. Відкат може бути зроблений до початку транзакції (в цьому випадку про відновлення стану сканів говорити безглуздо) або до встановленої раніше в транзакції точці збереження.
Точка збереження встановлюється за допомогою операції SAVE. При виконанні цієї операції запам'ятовується стан сканів даної транзакції, відкритих до моменту виконання SAVE, і координати останнього запису про зміни в базі даних в журналі, зробленій від імені даній транзакції. Параметр у відповідь операції SAVE (а прямих параметрів, крім ідентифікатора транзакції, вона не вимагає) є ідентифікатор точки збереження. Цей ідентифікатор надалі може бути використаний як прямий параметр операції RESTORE, при виконанні якої проводиться відновлення бази даних по журналу, з використанням записів про її зміни від даної транзакції до того стану, в якому знаходилася база даних до моменту встановлення вказаної точки збереження. Крім того, по локальній інформації в оперативній пам'яті, прив'язаній до транзакції, відновлюється стан її сканів. Відкат на початок транзакції ініціюється також зверненням до операції RESTORE, але з вказівкою деякого приреченого ідентифікатора точки збереження.
При виконанні своїх транзакцій користувачі System R ізольовані один від іншого, тобто не відчувають того, що система функціонує в багатокористувацькому режимі. Це досягається за рахунок наявності в RSS механізму неявної синхронізації (більш повно це ми обговоримо в наступному підрозділі). Поки помітимо лише, що до кінця транзакції ніякі зміни бази даних, вироблені в межах цієї транзакції, не можуть бути використані в інших транзакціях (спроба використання таких даних приводить до тимчасових синхрозаційних блокувань цих транзакцій). При виконанні операції END TRANSACTION відбувається "фіксація" змін, вироблених в даній транзакції, тобто вони стають видимими в інших транзакціях. Реально це означає зняття синхронізаційних захоплень з об'єктів бази даних, що змінювалися в транзакції. З цього слідує, що після виконання END TRANSACTION неможливі індивідуальні відкати даної транзакції. RSS просто робить недійсним ідентифікатор даної транзакції, і після виконання операції закінчення транзакції відкидає всі операції з таким ідентифікатором.
Остання операція інтерфейсу RSS - операція явної синхронізації LOCK. Ця операція дозволяє встановити явне синхрозаційне захоплення на вказане відношення (параметром операції є ідентифікатор таблиці). Виконання операції LOCK гарантує, що ніяка інша транзакція до кінця даної не зможе змінити дане відношення (вставити в нього новий кортеж, видалити або модифікувати існуючий), якщо встановлене захоплення відношення в режимі читання, або навіть прочитати будь-який кортеж цього відношення, якщо встановлене захоплення в режимі зміни.
З всього, що говорилося раніше з приводу підходу до синхронізації в System R і відповідного розбиття системи на рівні, слідує нелогічність наявності цієї операції в інтерфейсі RSS. Насправді, логічно ця операція надмірна, тобто якби її не було, можна цілком реалізувати SQL на частині операцій, що залишилася. До викладу матеріалу наступного підрозділу про це важко говорити, але заздалегідь помітимо, що операція LOCK введена в інтерфейс RSS для можливості оптимізації виконання запитів. Справа в тому, що, як видно з опису інтерфейсу, він покортежний. Отже, і інформація для синхронізації носить досить вузький характер. У той же час на рівні SQL є більш повна інформація. Наприклад, якщо обробляється пропозиція SQL DELETE FROM EMP, то відомо, що будуть видалені всі кортежі вказаної таблиці. Зрозуміло, що як би не реалізовувався механізм синхронізації в RSS, в цьому випадку вигідніше повідомити відразу, що зміни торкаються всього відношення. Але знов забігаючи уперед, помітимо, що ситуації в компіляторі SQL, коли очевидна вигода від використання явної синхронізації, досить рідкі. Користуватися цим засобом можна тільки дуже обачно, тому що невиправдані захоплення таких великих об'єктів можуть різко обмежити міру асинхронності виконання транзакцій.
7.5. Синхронізація в System R
System R з самого початку задумувалася як багатокористувацька система, що забезпечує режим мультидоступу до баз даних. Тому питанням синхронізації доступу завжди приділялася дуже велика увага. Розробники System R сформулювали і частково вирішили багато проблем синхронізації, відповідні публікації давно стали класикою, і на них посилаються практично у всіх роботах, пов'язаних з синхронізацією в системах управління базами даних. Ми постараємося привести історичну ретроспектива рішень в області синхронізації в System R. Заздалегідь помітимо, що питання синхронізації знаходяться в тісному зв'язку з питаннями журналізації змін і відновлення стану бази даних.
Почнемо з розгляду цілей, якими керувалися розробники System R при виробленні свого підходу до синхронізації. Справа в тому, що початковою метою синхронізації операцій було не забезпечення ізольованості користувачів, а підтримка засобів забезпечення логічної цілісності баз даних. Як ми відмічали у введенні, логічна цілісність баз даних System R підтримується на основі наявності раніше сформульованих і записаних в каталогах бази даних обмежень цілісності. У кінці кожної транзакції або при виконанні явної пропозиції SQL перевіряється непорушення обмежень цілісності змінами, виробленими в даній транзакції. Якщо виявляється порушення обмежень цілісності, то за допомогою операції RSS RESTORE проводиться відкат транзакції, що порушила обмеження.
Для того, щоб можна було коректно виконати такий відкат, необхідно, щоб до кінця транзакції об'єкти бази даних, що змінювалися транзакцією, не могли змінюватися іншими транзакціями. У іншому випадку виникає так звана проблема втрачених змін. Дійсно, нехай транзакція 1 змінює деякий об'єкт бази даних A. Далі інша транзакція 2 також змінює об'єкт А, після чого проводиться відкат транзакції 1 (по причині, наприклад, порушення їй обмежень цілісності). Тоді при наступному читанні об'єкта А транзакція 2 побачить його стан, відмінний від того, в яке він перейшов внаслідок його зміни транзакцією 2.
Початковим постулатом System R було те, що втрачені зміни допускати не можна, і забезпечення цього було мінімальною вимогою до системи синхронізації. Відповідний режим виконання транзакцій називається в System R першим рівнем сумісності транзакцій. Це найбільш низький рівень синхронізації, що викликає мінімальні накладні витрати в системі. Технічно синхронізація на першому рівні сумісності передбачає довготривалі (до кінця транзакції) синхрозаційні захоплення змінних об'єктів бази даних і відсутність яких-небудь захоплень для об'єктів, що читаються.
З точки зору забезпечення логічної цілісності баз даних перший рівень сумісності цілком задовільний, але викликає деякі проблеми всередині транзакцій. Основна проблема - можливість читання брудних даних. Дійсно, читаюча транзакція абсолютно не синхронізується із змінюючими транзакціями, і тому в ній може бути прочитане деяке проміжне з логічної точки зору стан об'єкта (ми підкреслюємо, що "брудним" об'єкт може бути тільки на логічному рівні; фізичну узгодженість в базі даних підтримує інший, "фізичний" рівень синхронізації RSS, на якому ми зупинимося пізніше). Наступний, другий рівень сумісності транзакцій System R забезпечує відсутність брудних даних. Технічно синхронізація на другому рівні сумісності передбачає довготривалі синхрозаційні захоплення (до кінця транзакції) змінних об'єктів і короткочасні (на час виконання операції) захоплення об'єктів, що читаються.
Другий рівень сумісності транзакцій System R гарантує відсутність брудних даних, але не вільний від ще однієї проблеми – читання, що неповторюються. Якщо транзакція два рази (підряд або з деяким тимчасовим проміжком) читає один і той же об'єкт бази даних, то стан цього об'єкта може бути різним при різному читанні, оскільки в проміжку між ними (а він може виникнути, навіть якщо читання йде в транзакції підряд) інша транзакція може модифікувати об'єкт. Цю проблему вирішує третій рівень сумісності транзакцій System R, що є тим самим рівнем максимальної ізольованості користувачів, про який ми говорили раніше. Технічно синхронізація на третьому рівні сумісності передбачає довготривалі (до кінця транзакції) синхрозаційні захоплення всіх об'єктів, що читаються і змінних в даній транзакції.
У початкових версіях System R забезпечувалися всі перераховані рівні сумісності транзакцій. Відповідно, існували параметри операції RSS BEGIN TRANSACTION, що визначали рівень сумісності даної транзакції. Однак, вже перший досвід використання System R показав, що найбільш застосовним є третій рівень сумісності. При цьому існували додатки, які влаштовував перший рівень (в основному, додатки, пов'язані зі статистичною обробкою, в яких помилки "брудних" даних виправлялися за рахунок великого числа читання). Другий рівень сумісності виявився практично непридатним. У результаті в останніх версіях розробники залишили тільки третій рівень сумісності, і далі ми будемо мати на увазі тільки його.
Оскільки інтерфейс RSS - покортежний, то логічно проводити синхронізацію в RSS саме на рівні кортежів або, вірніше, їх унікальних ідентифікаторів - tid'ів. Помітимо, однак, що якщо дві або більше за транзакції читають один кортеж, то з точки зору синхронізації це цілком допустиме, а якщо хоч би одна транзакція змінює кортеж, то вона повинна блокувати всі інші транзакції, що виконують операції читання або зміни даного кортежу. З цього слідує потреба в двох різних режимах захоплень кортежів - спільному режимі (для читання) і монопольному (для змін). Слідуючи термінології System R, далі ми будемо називати ці режими режимом S (спільним) і режимом X (монопольним). Природно формулюються правила сумісності захоплень одного об'єкта в режимах S і X: захоплення режиму S сумістимо із захопленням режиму S і несумісний із захопленням режиму X; захоплення режиму X несумісне із захопленням будь-якого режиму.
Відповідно, при читанні кортежу RSS передусім встановлює захоплення цього кортежу в режимі S; при вставці, видаленні або модифікації кортежу - в режимі X. Якщо до цього моменту кортеж захоплений від імені іншої транзакції в режимі, несумісному з необхідним, транзакція, що звернулася до RSS, блокується, і вимога захоплення кортежу ставиться в чергу доти, поки не виникнуть умови задоволення необхідного захоплення, тобто не будуть зняті конфліктуючі захоплення з кортежу.
У принципі режим покортежних захоплень достатній для задоволення вимог, раніше сформульованих в цьому підрозділі. Потрібно зазначити, що більшість реляційних систем баз даних і обмежуються покортежними (або навіть більш грубими посторінковими) захопленнями. Проте в контексті System R синхронізація такого типу недостатня.
Основною проблемою є можливість появи кортежів-фантом при повторних скануваннях відносин в одній транзакції (навіть на третьому рівні сумісності). Дійсно, після першого сканування всі прочитані кортежі будуть захоплені в режимі S, через що ніяка інша транзакція не зможе видалити або модифікувати такі кортежі. Але ніщо не заважає вставити в іншій транзакції в те ж відношення новий кортеж, значення полів якого задовольняють умовам сканування першої транзакції. Тоді при повторному скануванні тих же відносин з тими ж умовами сканування буде прочитаний кортеж, якого не було при першому скануванні, тобто з'явиться кортежем-фантом.
Був запропонований підхід до розв'язання проблеми фантом на основі так званих предикатних захоплень. Ідея підходу полягає в тому, що при скануванні потрібно насправді захоплювати не індивідуальні прочитані кортежі, а вся віртуальна безліч кортежів, які могли б бути прочитані при даному скануванні. Для цього досить "захопити" умову (предикат), якій повинні задовольняти всі кортежі при даному скануванні. Наприклад, якщо повинні бути прочитані кортежі відношення зі значенням поля а > 5, то захоплюється предикат а > 5. Якщо деяка інша транзакція виконує операцію, наприклад, вставки в те ж відношення кортежу зі значенням поля а > 5, то предикатне захоплення, попереднє реальному виконанню цієї операції, повинне конфліктувати із захопленням першої транзакції і т.д.
Природно, що чим більш точно формулюється предикат, тим більше реальна паралельність виконання транзакцій в системі з предикатними захопленнями. З цієї точки зору найбільшого рівня асинхронності можна було б досягнути, якщо допустити використання як синхронізаційних предикати умов вибірки, видалення або модифікацій мови SQL (або іншої мови запитів високого рівня). Але з іншого боку, чим більш загальний вигляд предикатів допускається, тим складніше стає проблема виявлення сумісності відповідних захоплень. Досить легко реалізовується система предикатних захоплень, в якій предикати являють собою логічні вирази, що складаються з простих предикатів порівняння полів відносин з константними значеннями. Розробники System R не пішли і на таку систему, але деякі ідеї предикатних захоплень використали.
При наявності тільки покортежних захоплень неясним залишається питання синхронізації в RSS покортежних операцій і операцій створення і знищення відносин і індексів, і доповнення полів до існуючого відношення. Незрозуміло, як поєднувати покортежні захоплення з можливість явного захоплення відношення і т.д. Очевидно, що загальна система предикатних захоплень такі проблеми знімає, але як ми вже відмічали, розробники System R не пішли на її реалізацію. Замість цього був розроблений протокол ієрархічних гранульованих захоплень (з деякими елементами предикатних захоплень).
Основна ідея полягає в тому, що є деяка ієрархія пам'яті зберігання кортежів: сегмент-відношення-кортеж. Об'єкти кожного рівня ієрархії можуть бути захоплені. Крім того, можна захоплювати вказаний діапазон значень будь-якого індексу. Набір можливих режимів захоплень розширяється так званими цільовими (intented) захопленнями. Семантично цільове захоплення "складного" об'єкта (сегмента або відношення) означає намір даної транзакції встановлювати цільові або звичайні захоплення на більш низькому рівні ієрархії. Введені наступні типи цільових захоплень: IX (intented to X), IS (intented to S) і SIX (shared, intented to X).
Захоплення об'єкта в режимі IX відповідає наміру транзакції виробляти захоплення об'єктів нижче по ієрархії в режимах IX або X. Захват об'єкта в режимі IS відповідає наміру транзакції виробляти захоплення об'єктів нижче по ієрархії в режимах IS або S. На кінець, захоплення об'єкта в режимі SIX відповідає захопленню об'єкта в режимі S і наміру транзакції захоплювати об'єкти нижче по ієрархії в режимі X. Із цього слідують наступні правила сумісності захоплень різних режимів: |
X | S | IX | IS | SIX
X | ні | ні | ні | ні | ні
S | ні | так | ні | так | ні
IX | ні | ні | так | так | ні
IS | ні | так | так | так | так
SIX | ні | ні | ні | так | ні
Протокол синхронізації з використанням перерахованих режимів захоплень наступний: щоб захопити об'єкт (наприклад, кортеж відношення) в режимі S (X), треба заздалегідь встановити захоплення в режимі IS (IX) відповідних об'єктів вище по ієрархії (у разі захоплення кортежу - сегмента і відношення); при цьому захоплення повинні встановлюватися, починаючи від кореня ієрархії (в нашому випадку - спочатку для сегмента, потім для відношення і тільки потім для кортежу).
Очевидно, що протокол ієрархічних захоплень вирішує проблему сумісності глобальних захоплень складного об'єкта (наприклад, захоплень відношення в режимі S) із захопленнями підоб'єктів цього об'єкта (кортежів). Але також очевидно, що протокол, взагалі кажучи, не вирішує проблему фантом. Якщо відношення сканується без використання індексу, то відсутність фантом можна гарантувати, якщо заздалегідь захопити все відношення в режимі S. Тоді, відповідно до ієрархічного протоколу, ніяка інша транзакція не зможе занести в це відношення новий кортеж, тому що вона буде блокована при спробі захопити відношення в режимі IX (захоплення відношення в режимах S і IX несумісні). Можна, звичайно, захоплювати все відношення і при скануванні з використанням індексу. Таким чином можна вирішити проблему фантом, але це дуже неефективне рішення, тому що воно різко обмежує можливості паралельного виконання транзакцій. Будь-яка тільки читаюча відношення транзакція конфліктує з будь-ким транзакцій, що змінює це відношення. З іншого боку, в RSS при скануванні відношення по індексу є додаткова інформація (діапазон сканування), яка обмежує безліч кортежів, серед яких не повинен виникати фантом.
Виходячи з цих міркувань, було запропоновано ввести в систему синхронізації елементи предикатних захоплень. Помітимо спочатку, що технічно захоплення сегментів, відносин і кортежів трактуються одноманітно, як захоплення tid'ів. При захопленні кортежу насправді захоплюється його tid. При захопленні сегмента або відношення насправді захоплюється tid описувача відповідного об'єкта у внутрішніх відносинах описувачів таких об'єктів (сегментів і відносин). Пропонувалося розширити систему синхронізації, дозволивши застосовувати захоплення до пари ідентифікатор індексу - інтервал значень ключа цього індексу. До такої пари дозволено застосовувати захоплення в будь-кому з допустимих режимів, причому два захоплення сумісні в тому і тільки в тому випадку, якщо вони сумісні відповідно до приведеної вище таблиці, або вказані діапазони значень ключів не перетинаються.
При наявності такої можливості, якщо відкривається сканування відношення по індексу, відношення захоплюється в режимі IS, і в цьому ж режимі захоплюється пара ідентифікатор індексу - діапазон сканування. При занесенні (видаленні) кортежу відношення захоплюється в режимі IX, і в цьому ж режимі для кожного індексу, визначеного на даному відношенні, захоплюється пара ідентифікатор індексу - значення ключа з кортежу, що порушується операцією. Тоді читаючі транзакції реально конфліктують тільки з тими змінюючими транзакціями, які торкаються діапазон сканування. При цьому вирішується проблема фантом, і асинхронність транзакцій обмежується "по суті", тобто тільки тоді, коли їх паралельне виконання створює проблеми.
Помітимо відразу, що описане розв'язання проблем синхронізації далеке від ідеального. По-перше, як і раніше при скануванні відношення без використання індексів відсутність фантом можна гарантувати тільки при повному захопленні всього відношення в режимі S. По-друге, навіть при скануванні по індексу умова реальної вибірки кортежу часто може бути суворіше простої вказівки діапазону сканування, а це означає, що необхідне захоплення дуже сильне, тобто охоплює більш широку безліч кортежів, чим те, яке буде реальним результатом сканування.
Видимо, по цих причинах, а також по причинах необхідного ускладнення системи синхронізації, описані засоби боротьби з фантом не були реалізовані в System R (принаймні, це виходить із заключних публікацій). Більш того внаслідок половинчатості цього рішення і дуже великого обмеження міри асинхронності розробники відмовилися і від неявних захоплень відношення в режимі S при скануванні без використання індексів. (Нагадаємо, що можливість явного захоплення цілком відносини залишилася). Тим самим, System R не гарантує відсутність фантом при повторному скануванні відношення.
Досвід System R в області синхронізації вплинув дуже великий чином на розробників реляційної СУБД у всьому світі. Особливо це торкається пропозицій по частині предикатних захоплень. У ряді існуючій або СУБД, що проектується предикатні захоплення складають основу системи синхронізації, яка, звичайно, при цьому стає істотно більш складної, ніж в System R.
На закінчення даного підрозділу стисло згадаємо про ще один рівень синхронізації, присутньому в RSS, - рівні фізичної синхронізації. Ми вже зазначали, що після виконання будь-якої операції RSS залишає базу даних в фізично узгодженому вигляді. Це означає, зокрема, коректність всіх міжсторінкових посилань. Прикладами таких посилань можуть бути посилання між станицями В-дерев індексів і т.д. Під час виконання операцій зміни (занесення, модифікації або видалення кортежу) може виникати тимчасова некоректність стану сторінок даних. Для того, щоб кожна операція при початку свого виконання мала коректну інформацію, необхідна додаткова короткочасна синхронізація на рівні сторінок. На час виконання операції всі необхідні сторінки захоплюються в режимі читання або зміни. Захоплення знімаються при закінченні виконання операції.
І останнє зауваження. При синхронізації транзакцій можуть виникнути тупикові ситуації, коли дві або більше за транзакцію не можуть продовжувати своє виконання внаслідок взаємного блокування. RSS не робить яких-небудь дій по запобіганню тупикам. Замість цього періодично перевіряється стан системи захоплень на предмет виявлення тупика, і якщо тупик виявляється, вибираються одна або декілька транзакцій - жертв, для яких ініціюється відкат до початку або до найближчої точки збереження транзакції, що гарантує руйнування тупика (при відкаті транзакції її сінхрозахвати знімаються). Вибір жертви виготовляється у відповідності з критеріями мінімальної вартості проробленою транзакцією роботи, яку доведеться повторити після відкату. Ми не будемо більш детально розглядати схеми виявлення і руйнування тупиків. Помітимо лише, що при виявленні тупика застосовується широко поширена техніка редукції графа очікування з метою виявлення в ньому циклів, наявність яких і свідчить про наявність тупика.
7.6. Журналізація і відновлення в System R
Одна з основних вимог до будь-якої системи управління базами даних полягає в тому, що СУБД повинна надійно зберігати бази даних. Це означає, що СУБД повинна підтримувати засоби відновлення стану баз даних після будь-яких можливих збоїв. До таких збоїв відносяться індивідуальні збої транзакцій (наприклад, розподіл на нуль в прикладній програмі, що ініціювала виконання транзакції); збій процесора при роботі СУБД (так звані м'які збої) і збої (поломки) зовнішніх носіїв, на яких розташовані бази даних (жорсткі збої).
Ситуації, виникаючі при збоях кожного з відмічених класів, різні і, взагалі кажучи, вимагають різних підходів до організації відновлення баз даних. Індивідуальні збої транзакцій означають, що всі зміни, вироблені в базі даних деякою транзакцією, незаконні, і їх необхідно усунути. Для цього необхідно виконати індивідуальний відкат транзакції такого ж типу, як при виконанні RSS явної операції RESTORE.
При виникненні м'якого збою системи втрачається вміст оперативної пам'яті. Відновлення стану бази даних полягає в тому, що після його завершення база даних повинна містити всі зміни, вироблені транзакціями, що закінчилися до моменту збою, і не повинна містити жодної зміни, виробленої транзакціями, які до моменту збою не закінчилися. Істотним аспектом ситуації є те, що стан бази даних на зовнішній пам'яті не зруйнований, що дозволяє зробити процес відновлення не дуже тривалим.
Жорсткі збої приводять до повної або часткової втрати вмісту баз даних на зовнішній пам'яті. Проте мета процесу відновлення та ж, що і у разі м'якого збою: після завершення цього процесу база даних повинна містити всі зміни, вироблені транзакціями, що закінчилися до моменту збою, і не повинна містити жодної зміни, виробленої транзакціями, що не закінчилися до моменту збою. У разі жорсткого збою єдино можливий підхід до відновлення стану бази даних може бути заснований на використанні раніше зробленої копії бази даних. У загальному випадку процес відновлення після жорсткого збою істотно більш накладений, ніж після м'якого збою.
Алгоритми відновлення System R засновані на двох базових засобах - веденні журналу і підтримці тіньових станів сегментів. Розглянемо спочатку механізм журналізації. Ми вже згадували про наявність журналу в попередніх підрозділах. Журнал - це окремий файл зовнішньої пам'яті, для якого для надійності звичайно підтримуються дві копії, і в який вміщується інформація про всі операції зміни стану бази даних. У попередньому підрозділі ми згадували про використання журналу для відкату транзакції по явній операції RESTORE або при неявних відкатах при руйнуванні тупиків. Та ж схема вживається і при відкатах індивідуальних транзакцій при збоях.
Механізм індивідуального відкату заснований на зворотному виконанні всіх змін, зроблених даною транзакцією (undo). При цьому з журналу в зворотному хронологічному порядку вибираються всі записи про зміну бази даних, зроблені від імені даної транзакції. Для цього необхідна ідентифікація всіх записів в журналі. У System R всі записи однієї транзакції зв'язуються в один список в порядку, зворотному хронологічному. Посилання в списку являє собою адресу запису в файлі-журналі. Оскільки схема індивідуального відкату єдина для всіх ситуацій індивідуальних збоїв, зокрема для ситуації руйнування тупиків, то зворотне виконання операцій супроводиться зняттям встановлених при прямій роботі транзакції синхронізаційних захоплень з об'єктів бази даних. Отже, після виконання індивідуального відкату транзакції ситуація в системі така, як якби транзакція ніколи і не починалася.
Специфіка м'якого збою системи складається у втраті стану оперативної пам'яті. У оперативній пам'яті знаходяться буфера бази даних. Підтримуються буфера двох сортів: буфера журналу і буфера власне бази даних. Буфера журналу містять останні записи в журнал. Є два буфери журналу. Як тільки один буфер повністю заповнюється, проводиться його запис в файл-журнал і продовжується заповнення другого буфера. Таким чином, при звичайній роботі системи обміни з файлом журналу не приводять до припинення роботи. Буфера бази даних містять копії сторінок бази даних, які використовувалися останнім часом. Внаслідок звичайних в програмуванні принципів локалізації посилань досить ймовірно, що після приміщення копії сторінки бази даних в буфер ця сторінка зажадається в найближчому майбутньому. Тому наявність копії сторінки в буфері дозволить уникнути обміну з пристроєм зовнішньої пам'яті, коли ця сторінка знадобиться в наступний раз.
Помітимо, що розмір буферного пулу СУБД багато в чому визначає її продуктивність. Звичайна реляційна СУБД, така, як System R, при наявності достатнього розміру буферного пулу цілком конкурентноздатна по відношенню до систем, заснованих на спеціалізованій апаратурі машин баз даних.
Задача System R по забезпеченню надійного завершення транзакцій, тобто гарантованій наявності вироблених ними змін в базі даних, вимагає наявності у зовнішній пам'яті інформації про ці зміни. Для цього при закінченні будь-якої транзакції підтримується гарантована присутність в файлі-журналі всіх записів про зміни, зроблені цією транзакцією. При використанні буферизації для запису в журнал для цього досить насильно виштовхнути у зовнішню пам'ять недозаповнений буфер журналу. Під насильним виштовхуванням розуміється запис буфера у зовнішню пам'ять відповідно не до логіки ведення журналу, а з логікою закінчення транзакції. Тільки після здійснення такого насильного виштовхування буфера журналу транзакція вважається такою, що закінчилася. Помітимо, що останнім записом в журналі від будь-якої транзакції, що змінює базу даних є запис про кінець транзакції. Ці записи використовуються при відновленні. Розглянемо тепер (поки не зовсім точно) як здійснюється в System R відновлення бази даних після м'якого збою.
Основою алгоритму відновлення є те, що система дотримується правила попереджуючого запису в журнал (WAL - Write Ahead Log). Це правило означає, що при виштовхуванні будь-якої сторінки з буфера сторінок спочатку гарантується наявність в файлі журналу запису, що відноситься до змін цієї сторінки після моменту її виштовхування в буфер. Оскільки записи в журнал блокуються, то для дотримання правила WAL перед виштовхуванням сторінки даних необхідно виштовхнути недозаповнений буфер журналу, якщо він містить запис, що відноситься до зміни сторінки. Застосування правила WAL гарантує, що якщо у зовнішній пам'яті знаходиться сторінка бази даних, то в файлі журналу знаходяться всі записи про операції, що спричинили зміну цієї сторінки. Зворотне невірне: в файлі журналу можуть міститися записи про зміну деяких сторінок бази даних, а самі ці зміни можуть бути не відображені в станах сторінок у зовнішній пам'яті.
При закінченні будь-якої транзакції (тобто виконанні операції RSS END TRANSACTION) проводиться виштовхування недозаповненого буфера журналу і тим самим гарантується наявність в журналі повної інформації про всі зміни, зроблені даною транзакцією. Насильне виштовхування сторінок буфера бази даних не проводиться (дуже накладно було б виробляти такі виштовхування при закінченні будь-якої транзакції). Тим самим після м'якого збою стан бази даних у зовнішній пам'яті може не відповідати тому, яке повинне було б бути після закінчення транзакцій. Отже, після м'якого збою деякі сторінки у зовнішній пам'яті можуть не містити інформації, вміщеної в них транзакціями, що вже закінчилися, а інші сторінки можуть містити інформацію, вміщену транзакціями, які до моменту збою не закінчилися. При відновленні необхідно додати інформацію в сторінках першого типу і видалити інформацію в сторінках другого типу.
System R періодично встановлює системні контрольні точки. Більш детально ми зупинимося на цьому нижче. Поки помітимо лише, що при встановленні такої контрольної точки проводиться насильне виштовхування у зовнішню пам'ять буфера журналу і всіх буферів сторінок. Це операція, що дорого коштує, і виконується вона досить рідко. При кожній системній контрольній точці в журнал вміщується спеціальний запис.
Передбачимо, що остання системна контрольна точка встановлювалася в момент часу tc, а м'який збій стався в деякий більш пізній момент часу tf. Тоді всі транзакції системи можна розбити на п'ять категорій.
Транзакції категорії Т1 почалися і кінчилися до моменту tc. Отже, всі вироблені ними зміни бази даних надійно знаходяться у зовнішній пам'яті, і по відношенню до них ніяких дій при відновленні проводити не треба. Транзакції категорії Т2 почалися до моменту tc, але встигли кінчитися до моменту м'якого збою tf. Зміни, вироблені такими транзакціями після моменту tc, могли не попасти у зовнішню пам'ять, і при відновленні повинні бути повторно зроблені. Транзакції категорії Т3 почалися до моменту tc, але не кінчилися до моменту збою. Всі їх зміни, зроблені до моменту tc, і, можливо, деякі зміни, зроблені після моменту tc, містяться у зовнішній пам'яті. При відновленні їх необхідно видалити. Транзакції категорії Т4 почалися після моменту установки системної контрольної точки і встигли закінчитися до моменту збою. Їх зміни могли не відобразитися у зовнішню пам'ять; при відновленні їх необхідно виконати повторно. Нарешті, транзакції категорії Т5 почалися після моменту tc і не закінчилися до моменту збою. Їх зміни повинні бути видалені з сторінок у зовнішній пам'яті.
У принципі можна було б виконати всі необхідні відновні дії після м'якого збою, засновуючись тільки на інформації з журналу. Однак в System R ситуація дещо спрощується за рахунок застосування техніки тіньових сторінок. Принцип тіньових сторінок давно використовувався в файлових системах, підтримуючих файли зі сторінковою організацією. Відповідно до цього принципу після відкриття файла на зміну модифіковані сторінки записуються на нове місце зовнішньої пам'яті (тобто під них виділяються вільні блоки зовнішньої пам'яті). При цьому у зовнішній пам'яті зберігається стара (тіньова) таблиця відображення сторінок файла у зовнішню пам'ять, а в оперативній пам'яті по ходу зміни файла формується нова таблиця. При закритті файла наново сформована таблиця записується у зовнішню пам'ять, утворюючи нову тіньову таблицю, а блоки зовнішньої пам'яті, утримуючі попередні образи сторінок файла, звільняються. При збої процесора тим самим автоматично зберігається стан файла, в якому він знаходився перед останнім відкриттям (звичайно, з можливою втратою деяких блоків зовнішньої пам'яті, які потім збираються за допомогою спеціальної утиліти). Допускаються операції явної фіксації поточного стану файла і явного відкату стану файла до точки останньої фіксації.
У System R застосовується розвиток ідей тіньового механізму в контексті мультидоступних баз даних. Як ми вже відмічали, сегменти баз даних System R являють собою файли зі сторінковою організацією. Відповідно, існують і таблиці приписки цих файлів в блоки зовнішньої пам'яті. При виконанні операції установки системної контрольної точки після виштовхування буферів сторінок у зовнішню пам'ять таблиці відображення всіх сегментів також фіксуються у зовнішній пам'яті, тобто стають тіньовими. Далі до наступної контрольної точки доступ до сторінок сегментів проводиться через таблиці відображення, що розташовуються в оперативній пам'яті, і кожна змінна сторінка будь-якого сегмента записується на нове місце зовнішньої пам'яті з корекцією відповідної поточної таблиці відображення.
Тоді, якщо відбувається м'який збій, всі сегменти автоматично переходять в стан, відповідний останній системній контрольній точці, тобто зміни, зроблені пізніше за момент встановлення цієї контрольної точки, в них просто не містяться.
Це досить сильно спрощує процедуру відновлення після м'якого збою. Система взагалі не повинна робити ніяких дій по відношенню до змін транзакцій типу Т5: цих змін ні у зовнішній пам'яті. При відновленні досить виконати зворотні зміни транзакцій типу Т3 (undo в термінології System R), повторно виконати зміни транзакцій типу Т2 (redo в термінології System R; помітимо, до речі, що ці зміни можна тепер виконувати безумовно, не піклуючись про те, що вони, можливо, і так містяться у зовнішній пам'яті). Крім того, треба просто повторити зміни транзакцій типу Т4. Природно, що починати дії по журналу слідує із запису про останню контрольну точку.
Справедливість ради зазначимо, що насправді тіньовий механізм використовується в System R головним чином не для спрощення процедури відновлення після м'якого збою. Як ми вже відмічали, без цього можна обійтися. Головна причина в іншому, а саме, в тому, що відновлення бази даних можна починати тільки від її фізично узгодженого стану. Справа в тому, що в журнал вміщується інформація про зміну об'єктів бази даних, а не сторінок. Наприклад, в журналі може знаходитися інформація про модифікацію кортежу у вигляді триплету . Реально ж при виконанні операції модифікації змінюються декілька сторінок: початкова сторінка; можливо, сторінка заміни, якщо кортеж не вмістився в початкову сторінку; сторінки індексів. І так відбувається при виконанні будь-якої операції зміни бази даних. Оскільки буфера сторінок виштовхуються у зовнішню пам'ять по окремості, то до моменту м'якого збою у зовнішній пам'яті може виникнути набір фізично розузгоджених сторінок, не відповідний ніякій журналізуємої операції. При такому стані зовнішньої пам'яті відновлення по журналу неможливе.
Коли виконується операція установки системної контрольної точки, то до насильного виштовхування буферів сторінок система дожидається завершення всіх операцій всіх транзакції і до закінчення виштовхування не допускає виконання нових операцій. Тому тіньовий стан всіх сегментів бази даних фізично узгоджений і може служити основою відновлення по журналу.
При жорстких збоях втрачається вміст всіх або частини сегментів бази даних. Для відновлення бази даних використовуються журнал і раніше зроблена копія бази даних. У System R допускається посегментне відновлення. Для цього копія сегмента переписується з архівного носія на наново виділений робочий носій, а потім по журналу повторюються всі зміни, що виготовлялися в об'єктах цього сегмента після моменту копіювання. Оскільки в момент жорсткого збою вміст оперативної пам'яті не втрачається, то можливе продовження виконання транзакцій після завершення відновлення. Більш того якщо аварія торкнулася тільки частини сегментів бази даних, то транзакції на фоні процесу відновлення можуть продовжувати роботу з об'єктами бази даних, розташованими в непошкоджених сегментах.
Єдиною вимогою до архівної копії сегмента є те, що вона повинна знаходитися в узгодженому стані (оскільки відновлення ведеться в термінах записів журналу). Тому для створення архівної копії сегмента досить лише дочекатися кінця виконання операцій над об'єктами даного сегмента і заборонити початок нових операцій до кінця копіювання. Тим самим, виконання архівної копії не вимагає перекладу системи в який-небудь особливий режим роботи і тільки трохи гальмує нормальну роботу транзакцій.
На закінчення даного підрозділу помітимо, що в перших версіях System R як архівний носій використовувалися магнітні стрічки. Однак згодом стало ясно, що по-перше, надійність магнітних стрічок істотно менше надійності магнітних дисків, а по-друге, вони стали поступатися і в ємності. Тому в останніх версіях системи використовувалася тільки дискова пам'ять.
І останнє зауваження. Журнал System R розташовується в файлі великого, але постійного розміру. Він використовується в циклічному режимі. Коли записи журналу досягають кінця файла, вони починають вміщуватися в його початок. Оскільки перехід на початок файла можна вважати втратою попереднього журналу, цей перехід супроводиться копіюванням сегментів бази даних. У деяких інших системах використовується архівування самого журналу.

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать