Багатоверсійність даних і управління паралельними транзакціями

1. Розглянемо основні алгоритми управління паралельними транзакціями, засновані на концепції версійності....
2. Багатоверсійності варіант двофазного протоколу синхронізації
3. Багатоверсійності протокол для транзакцій, що не змінюють дані
4. MVSG-планувальники
5. Проблеми реалізації версійність алгоритмів
6. ***
7. література

Розглянемо основні алгоритми управління паралельними транзакціями, засновані на концепції версійності.

Перші роботи, присвячені управлінню паралельними транзакціями на основі багатоверсійності (multiversion concurrency control, MVCC), з'явилися ще в кінці 70-х - початку 80-х років. Вихідні статті були написані Рідом і колективом авторів на чолі з Байєром [ 1-3 ], Ідеї яких були розвинені в роботах Стернса і Розенкранца [10], а також Бернштейна і Гудмена [6]. Основна ідея MVCC полягає в тому, що в базі даних допускається існування декількох «версій» одного і того ж елемента даних, що дозволяє поліпшити ряд характеристик СУБД, найбільш важливих для наступних категорій додатків.

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

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

Додатки реального часу, для яких потрібно швидкий відгук і висока ступінь паралельності. Як приклад такого додатка можна привести систему резервування авіаквитків, в якій число паралельно виконуваних транзакцій може бути дуже велике. Типова транзакція для такої системи перевіряє наявність вільних місць на деякий рейс. Конфлікт двох транзакцій (в одній з яких змінюється кількість вільних місць, а в другій з'ясовується, чи є ще вільні місця на рейс) не обов'язково є серйозним. Замість блокування даних про рейс, яка може привести до тривалого очікування з боку оператора, можна дозволити другий транзакції прочитати стару версію даних. Це не викличе помилки, якщо тільки перша транзакція не обнуляє число вільних місць.

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

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

Застосування концепції версійності не обмежується СУБД. Управління версіями є однією з основоположних завдань в області систем управління конфігурацією програмного забезпечення. Зараз також ведеться цікава робота щодо застосування версій в системах спільної роботи над мультимедіа-проектами [8]. Інша робота присвячена використанню версій в розподілених мобільних базах даних [9]. У контексті таких систем доводиться вирішувати проблеми, пов'язані головним чином з повільними і нестабільними каналами зв'язку. Тому алгоритми роботи подібних систем дещо складніше розглянутих в цій статті.

Наведемо далі огляд основних багатоверсійних алгоритмів управління паралельними транзакціями, різні варіанти і комбінації яких були реалізовані в Oracle, Postgres і MySQL. На завершення огляду порівняємо алгоритми і обговоримо труднощі, з якими доводиться стикатися при їх застосуванні. Будемо говорити про алгоритми роботи багатоверсійного планувальника, оскільки саме цей компонент СУБД відповідає за зіставлення конкретних даних логічних операцій над ними. Будемо також розглядати тільки такі планувальники, які імітують поведінку відокремлених транзакцій.

тимчасові місця

В [6] Бернштейн і Гудмен пишуть, що найбільш ранній відомий їм алгоритм роботи планувальника для версійність СУБД заснований на тимчасових мітках (multiversion timestamp ordering, MVTO). Цей планувальник обробляє операції таким чином, щоб сумарний результат виконання операцій був еквівалентний послідовному виконанню транзакцій. Порядок сериализации задається порядком тимчасових міток, які отримують транзакції під час старту. Тимчасові місця також використовуються для ідентифікації версій даних при читанні і модифікації - кожна версія отримує тимчасову мітку тієї транзакції, яка її записала. Планувальник не тільки стежить за порядком виконання дій транзакцій, але також відповідає за трансформацію операцій над даними в операції над версіями - кожна операція виду «прочитати елемент даних x», ​​повинна бути перетворена планувальником в операцію: «прочитати версію y елемента даних x».

Мітку часу, отриману транзакцією ti на початку її роботи, будемо позначати як ts (ti), операцію читання транзакцією ti елемента даних x як ri (x). Для позначення того, що транзакція ti читає версію елемента даних x, створену транзакцією tk, будемо писати ri (xk), для позначення того, що транзакція ti записує версію елемента даних x, будемо використовувати запис wi (x). Опишемо алгоритм роботи планувальника MVTO.

Планувальник перетворює операцію ri (x) в операцію ri (xk), де xk - це версія елемента x, позначена найбільшою часовою міткою ts (tk), такий що ts (tk)

1) Операція wi (x) обробляється планувальником наступним чином:

a) якщо планувальник вже обробив дію виду rj (xk), таке що ts (tk)

b) в іншому випадку wi (x) перетворюється в wi (xi).

3) Завершення транзакції ti (commit) відкладається до того моменту, коли завершаться всі транзакції, що записали версії даних, прочитані ti.

Останній крок потрібен тільки в тому випадку, коли хочуть запобігти «брудне» читання.

На рис. 1 наведено приклад роботи планувальника MVTO. Взаємодія транзакцій t1 і t2 відмінним чином ілюструє плюси використання версій. У разі подібного плану виконання транзакцій при відсутності версійності вийшов би класичний випадок читання неузгоджених даних. Однак в нашому прикладі ця ситуація цілком прийнятна через те, що перша транзакція читає «стару» версію елемента даних y. Транзакція t3 очікує закінчення роботи t2 перед власним завершенням (пунктирна лінія на рис. 1). Це відбувається тому, що t3 прочитала незавершену версію x2.

Транзакція t4 є прикладом «пізньої» транзакції зміни. Вона створює версію y4, в той час як транзакція t5 (яка стартувала пізніше) вже прочитала більш ранню версію y2. Тобто транзакція t5 «не бачить» деяких змін, внесених t4. Таким чином, сериализация транзакцій в порядку отримання ними тимчасових міток неможлива - необхідний відкат (пункт 2a алгоритму).

Багатоверсійності варіант двофазного протоколу синхронізації

Розглянемо варіант широко відомого двухфазного протоколу синхронізації транзакцій (multiversion two-phase locking protocol, MV2PL), адаптованого для застосування в версійність базі даних. Будемо розрізняти три типи версії елемента даних:

• завершення (commited) - версії, створені транзакціями, які вже успішно закінчили свою роботу;
• поточна версія (current) - остання із завершених версій;
• незавершені (uncommited) - версії, створені транзакціями, які ще знаходяться в роботі.

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

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

1. якщо операція не є фінальною, то: a) операція r (x) виконується негайно; їй зіставляється остання із завершених до даного моменту версій x (або остання з незавершених версій x в другому варіанті алгоритму); b) операція w (x) виконується тільки після завершення транзакції, яка записала останню версію x.
2. якщо операція є фінальною для транзакції ti, то вона відкладається до тих пір, поки не завершаться: a) всі транзакції tj, що прочитали поточну версію даних, яку повинна замінити версія, записана ti (тим самим усувається можливість неповторюваного читання); b) всі транзакції tj, які записали версії, прочитані ti (це потрібно тільки в другому варіанті алгоритму).

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

Ймовірно, саме через цих проблем на практиці найчастіше використовується протокол 2V2PL, запропонований вперше в [3]. У цьому протоколі можливе одночасне існування двох версій елемента даних: однієї поточної версії даних і не більше однієї незавершеної. Така організація версій вигідна перш за все для транзакцій, що виконують операцію читання.

У 2V2PL використовуються три типи блокувань, присівши кожна блокування утримується до кінця транзакції:

• блокування rl (read lock) встановлюється на поточну версію елемента даних x безпосередньо перед її прочитанням;
• блокування wl (write lock) встановлюється перед тим, як створити нову (незавершену) версію елемента x;
• блокування cl (commit lock) встановлюється перед виконанням останньої операції транзакції (зазвичай перед операцією завершення) по відношенню до кожного елементу даних, який вона записала. Це блокування грає роль монопольної блокування для звичайного протоколу 2PL. Вона необхідна для коректної зміни версій.

Блокування rl сумісні між собою, а також з блокуваннями wl. Тому використання блокувань rl і wl забезпечує виконання правил (1a) і (1b) алгоритму MV2PL (з урахуванням того, що одночасно дозволяється підтримувати не більше однієї незавершеної версії). Блокування cl, в свою чергу, забезпечує виконання правил (2a) та (2b).

Багатоверсійності протокол для транзакцій, що не змінюють дані

У роботі багатьох додатків переважають транзакції, що не змінюють дані (read-only). Такі додатки зчитують і аналізують великі обсяги даних. У разі наявності хоча б невеликого числа паралельно виконуваних транзакцій, які виробляють зміни, компонент, який відповідає за управління паралельними транзакціями, повинен забезпечити узгодженість прочитаних даних. У разі використання алгоритмів планування без підтримки версій такі довготривалі транзакції можуть призвести до надзвичайного падіння продуктивності. Наприклад, при використанні 2PL вкрай велика ймовірність блокування транзакцій, які виробляють поновлення даних. В результаті у цих транзакцій буде дуже великий час відгуку.

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

Протокол ROMV (Multiversion Protocol for Read-Only Transactions, ROMV) - гібридний, він заснований на MVTO і 2PL. Він орієнтований на додатки, для яких найбільш важлива швидкість виконання транзакцій, які не виробляють змін даних. (В літературі відсутня згода з приводу назв алгоритмів. Так, Пол боббер і Майкл Кері в [7] називають обговорюваний протокол ROMV як MV2PL, ми ж дотримуємося термінології, прийнятої в [4]).

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

Транзакції, що модифікують дані, виконуються відповідно до протоколу S2PL - варіанті 2PL. У ньому все монопольні блокування відпускаються лише в кінці транзакції. Кожна операція, яка зраджує елемент даних, створює нову версію цього елемента. По завершенні транзакції кожна така версія позначається тимчасової міткою, що відповідає часу завершення транзакції.

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

Незважаючи на ідейну простоту, цей підхід викликає деякі складнощі при реалізації. Наприклад, він вимагає створення спеціального збирача сміття. Цей компонент СУБД повинен видаляти непотрібні версії даних. Найпростіший збирач сміття видаляє всі версії (крім поточних), значення тимчасових міток яких менше часу початку найстарішої з активних читають транзакцій.

MVSG-планувальники

Останній розглянутий клас багатоверсійних алгоритмів планування узагальнює широко відому моноверсіонную техніку Serialization Graph Testing (SGT). Засновані на SGT планувальники підтримують граф конфліктів, в якому вершини і дуги додаються динамічно в залежності від операцій, які отримує на вхід планувальник. При цьому конфліктуючими називаються будь-які дві операції над одним і тим же елементом даних, якщо хоча б одна з них є операцією модифікації. Іншими словами, для конфліктуючих операцій важливий порядок їх виконання. Таким чином, планування конфліктуючих операцій накладає обмеження на порядок серіалізації транзакцій. Ці обмеження і висловлює граф конфліктів. Розглянемо, як відбувається планування чергової операції pi (x) за допомогою SGT-планувальника.

1. Якщо це перша операція транзакції ti, що надійшла планувальником, то створюється новий вузол в графі сериализации.
2. У граф додаються дуги виду (tj, ti) для кожної запланованої раніше операції qj (x) (i _ j), яка конфліктує з pi (x). Можливі два варіанти: a) результуючий граф містить цикли - транзакція ti відкочується; b) отриманий граф аціклічен - дія додається до списку запланованих.

Що означає, що в графі з'явився цикл? Отримане розклад більше не буде серіалізуемим. Це твердження стає очевидним, якщо зауважити, що дуга з ti в tj фіксує порядок проходження транзакцій в еквівалентному послідовному розкладі. Результат нашого розкладу повинен бути таким же, як і послідовне виконання спочатку всіх дій транзакції ti, а потім tj. Оскільки транзакція не може слідувати раніше самої себе, граф з циклами не матиме відповідного послідовного розкладу.

Тепер ми можемо перейти до більш загального багатоверсійності нагоди і будемо розглядати багатоверсійності граф конфліктів MVSG. Покажемо, що обмеження, які ми накладали на граф сериализации в моноверсіоннім випадку, недостатні. Розглянемо наступний приклад:

S = w1 [x1] w1 [y1] r2 [y1] r3 [x1] w2 [z2] r3 [z2] w2 [x2]

Граф (рис. 2), складений за правилами алгоритму SGT, буде містити дуги (t1, t2), (t1, t3), (t2, t3).

Цей граф аціклічен. Однако для S НЕ існує еквівалентного моноверсіонного послідовного розклад. Дійсно, оскільки t3 читає версію x, записану t1 (r3 [x1]), то t2, яка теж пише елемент x (w2 [x2]), повинна слідувати в моноверсіонном послідовному розкладі або після t3, або перед t1. Але перший варіант неможливий через кроку r3 [z2], а другий - через r2 [y1]. Таким чином, багатоверсійності планувальник повинен також спеціальним способом перевіряти узгодженість кроків, що створюють нові версії. Для цього в граф додаються додаткові дуги, які фіксують «позиції записи» у відповідному послідовному розкладі.

Опишемо загальну схему роботи MVSG-планувальника. Коли черговий крок pi (x) надходить планувальником, він робить такі дії.

1. Якщо це перша дія транзакції ti, яке надійшло планувальником, то відповідний вузол додається до графу конфліктів.
2. Якщо це крок ri (x), то вибирається підходяща версія xj, і в граф додається дуга (tj, ti) (оскільки, згідно наших позначень, версію xj записала транзакція tj). Для всіх інших k, таких що wk (xk) є кроком tk, в граф додається або дуга (tk, tj), або дуга (ti, tk). В цьому і полягає вибір «позиції записи».
3. Якщо це крок wi (xi), то для кожної транзакції tk, яка прочитала, скажімо, версію xj, потрібно додати або дугу (ti, tj), або дугу (tk, ti). Тобто ti повинна слідувати або до tj, або після tk у відповідному послідовному розкладі.
4. Якщо граф залишається ациклічним, то зміни в графі фіксуються, а дія додається до списку запланованих. Інакше транзакція відкочується.

Слід звернути увагу на виборі правильного видання для читання. Версія xj не є підходящою в двох випадках: по-перше, якщо існує шлях з ti в tj (tj слід після ti по порядку сериализации); по-друге, якщо існує шлях (tj, tk, ti), де tk пише x - wk (xk). У цих випадках відсутній спосіб вибору місця для wk (xk) в еквівалентному моноверсіонном послідовному розкладі.

Як уже зазначалося, вибір для додавання в граф дуги - «(ti, tj) або (tk, ti)», по суті, є вибором «позиції записи». Вибирається порядок проходження інших транзакцій, які пишуть x. У деяких випадках буде матися кілька альтернативних шляхів, а в деяких вже існуючі дуги не залишать можливості вибору.

У розглянутому прикладі в графі утворюється цикл на останньому кроці - w2 [x2]. Виконуючи цей крок, ми повинні будемо, згідно з правилом 3 алгоритму, додати одну з дуг - (t2, t1) або (t3, t2). Обидві ведуть до утворення циклу.

Це сімейство алгоритмів описано в [11], [12] і в [4] під назвою MVSGT.

Проблеми реалізації версійність алгоритмів

Далеко не всі розглянуті алгоритми активно застосовуються на практиці - при їх реалізації виникають проблеми двох типів. По-перше, потрібно так влаштувати фізичну організацію даних, щоб можна було забезпечити ефективне управління версіями. Тут слід врахувати і розростання обсягу бази даних при додаванні версій. Тобто в ідеалі при організації даних повинні враховуватися можливі обмеження на кількість версій. Зауважимо, що на практиці обмеження на число версій часто відсутня - замість цього система просто видаляє непотрібні версії у міру завершення відповідних транзакцій. Подібна ситуація спостерігається в СУБД MySQL (в конфігурації, при якій низкоуровневая робота з таблицями покладається на підсистему InnoDB). У InnoDB використовується один з різновидів протоколу ROMV. Оскільки в цьому протоколі всі транзакції, що вносять зміни в базу даних, створюють нові версії даних, то проблема обмеження числа версій стоїть так само гостро, як і в більшості інших версійність алгоритмів. У InnoDB видалення версій відбувається в той момент, коли вони виявляються не потрібними жодної з активних транзакцій. Таким чином, відповідальність за підтримання помірної кількості версій лягає на користувачів СУБД, які повинні стежити за тим, щоб в системі не з'являлися «довгі транзакції». В іншому випадку версії залишатимуться в базі даних, що призведе до нефункціональні збільшення її обсягу.

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

Ще одна підсистема СУБД, яка істотно змінюється при додаванні версій, - це підсистема управління пам'яттю. Оскільки багато версій одного і того ж елемента даних можуть використовуватися паралельно, необхідно ефективне розміщення версій в основний пам'яті. Якщо заздалегідь невідомо максимальне число версій, допустимих для одного елемента даних, то ця вимога важко виконати.

Перераховані труднощі проявляються по-різному, в залежності від вибору алгоритму, що пояснюється тим, що алгоритми фіксують порядок створення і підтримки версій. Тому вони впливають як на фізичну сторону організації багатоверсійності СУБД, так і на логічну. На практиці найбільш часто використовуються протоколи ROMV і 2V2PL. З одного боку, ці протоколи досить прості в реалізації, а з іншого - надають користувачеві більшу частину вигод версійність СУБД. У разі протоколу 2V2PL істотну роль також відіграє його схожість із звичайним 2PL. Крім цього, в 2V2PL вирішується проблема обмеження числа версій. Складність вирішення цієї проблеми в разі протоколу MVTO, мабуть, є однією з причин його малої поширеності. Можна припустити, що та ж причина пояснює невелику кількість реалізацій, що використовують MV2PL. Автору також не відомо про реалізаціях, які застосовують MVSG-планувальники.

***

У статті зроблено огляд найбільш відомих версійність алгоритмів, застосовуваних для організації управління паралельними завданнями. Також розглянуті основні проблеми, що виникають при їх реалізації. Огляд підготовлений в процесі пошуку можливого шляху організації версій в XML СУБД Sedna, що розробляється в ІСП РАН групою MODIS.

література

1. D. Reed, Naming and Synchronization in a Decentralized Computer System, Ph.D. Thesis, MIT, September тисяча дев'ятсот сімдесят вісім.
2. D. Reed, Implementing atomic actions on decentralized data. ACM Trans. Comp. Syst. 1, 1, Feb. 1 983.
3. R. Bayer, H. Heller, A. Reiser, Parallelism and recovery in database systems. ACM Trans. Database Syst. 5, 2, June 1980.
4. G. Weikum, G. Vossen, Transactional information systems. Morgan Kaufmann, 2002.
5. R. Unland, Optimistic Concurrency Control Revisited. Arbeitsberichte des Instituts fr Wirtschaftsinformatik, 1994.
6. P. Bernstein, N. Goodman, Multiversion concurrency control - theory and algorithms. ACM Transactions on Database Systems, Vol. 8, No. 4, December +1983.
7. P. Bober, M. Carey, Multiversion Query Locking. Proceedings of the 18th VLDB Conference Vancouver, British Columbia, Canada, 1992.
8. O. Proskurnin, Concurrent Video: Versioning Concepts. Proceedings of the Spring Young Researcher? S Colloquium on Database and Information Systems SYRCoDIS, St.-Petersburg, Russia, 2004.
9. A. Yakovlev, A Multi-Version Concurrency Control Model for Distributed Mobile Databases. Proceedings of the Spring Young Researcher? S Colloquium on Database and Information Systems SYRCoDIS, St.-Petersburg, Russia, 2004.
10. R. Stearns, D. Rosenkrantz, Distributed database concurrency control using before-values. In Proc. 1981 ACM SIGMOD Conf. Management of Data, ACM, New York, 1981.
11. C. Papadimitriou, The theory of database concurrency control. Computer Science Press, 1986.
12. T. Hadzliacos, Serialization graph algorithms for multiversion concurrency control. Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, 1988.

Петро Чардін ( [email protected] ) - студент ВМиК МГУ. Автор вдячний Готфрід Воссену за надані матеріали і Сергію Кузнецову за численні поради і зауваження.