Неблокуюча база даних з ACID транзакціями



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

Ключові слова: атомарність, узгодженість, ізольованість, довговічність, доступність, стійкість, транзакція, конкурентний доступ.

Кицмен Дмитро Романович

КПІ ім. Ігоря Сікорського

Київ, Україна

dmitrokytsmen@gmail.com

Non-blocking database with ACID transactions

Abstract. In order to achieve non-blocking transaction processing, it is proposed to use such transaction processing algorithms and data structures to further store new data that significantly contributes not only to optimizing and speeding up the database but also ensures the presence of ACID properties.

Keywords: atomicity, consistency, isolation, durability, availability, stability, transaction, concurrent access.

Kytsmen Dmytro

National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"

Ukraine, Kyiv

ВСТУП

На даний момент більшість реляційних СУБД використовують механізм управління паралельним доступом з допомогою багатоверсійності (MVCC — Multi Version Concurrency Control) [1], який полягає в наданні кожному користувачу “зліпку” бази даних, який володіє властивістю, при якій зміни, які вніс один користувач, не є видимими для інших користувачів до моменту фіксації транзакції. Головна проблема полягає в тому, що не існує єдиного стандарту для реалізації MVCC, тому кожен вендор трактує його по своєму і програмні реалізації цього механізму на рівних рівнях абстракції за допомогою різних механізмів призводять до утворення вузьких місць в різних реляційних базах даних. У ситуації, коли система обробляє десятки одночасних транзакцій і має вимоги до несприятливої латентності, системи без блокування є гарним компромісом між складністю розробки та вимогами високого паралелізму[3]. Сервер бази даних для веб-сайту є гарним кандидатом для неблокуючого дизайну. Хоча будь-яка конкретна транзакція може бути заблокована, тим часом для обробки завжди є більше транзакцій, тому процесори ніколи не залишаться без роботи.

МОДЕЛЬ ЗБЕРЕЖЕННЯ ДАНИХ

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

Рис. 1. Схема представлення запису за допомогою дерева

ОБРОБКА ТРАНЗАКЦІЙ

Давайте розглянемо конкурентні зміни об’єкту. Транзакція 1:

UPDATE Person SET age = 23 AND occupation = “Software Engineer”

Транзакція 2:

UPDATE Person SET occupation = “Computer Scientist” and name = “DMYTRO”

Кожна транзакція створює нове дерево, яке містить тільки значення тих змінних, які вона міняє. Після того, як транзакція надходить, вона додається в кінець ланцюга транзакцій. Транзакції записують та зчитують дані в строго вказаному порядку і не можуть перемішуватись у порядку виконання. Це дозволяє нам гарантувати таку властивість як ізоляція [3]. В рис. 1 показано процес отримання об’єкту, при виконанні транзакції зчитування. Надалі приведемо приклад запиту, який зчитує дані.

SELECT name, age, occupation FROM Person

В блокованому (м’ютекс) підході, потік T2 очікує поки T1 завершиться і тільки тоді пише в об’єкт [5]. В цьому випадку кожен з них пише в окрему область пам’яті паралельно і є лише одна невелика синхронізація – атомарна вставка кореня в ланцюг. Потік зчитування може читати стан об’єкту в будь-який момент часу – на початку, після завершення потоку Т1, після завершення потоку Т2. Зчитування складається з наступних етапів:

$1.$ Пошук першої транзакції в ланцюгу згідно з вказаним режимом зчитування.

$2.$ Скопіювати відсутні вказівники на дані, які намагались зчитати в попередньої транзакції.

$3.$ Зчитати значення кожного об’єкту за час

\[O(\log N)\qquad (1)\]

шляхом переходу від кореня транзакції до листа.

Кожне дерево транзакції містить шляхи до елементів, які воно поміняло Ми повинні скопіювати посилання з попередніх транзакцій й під час кроку 2 отримати дані. Як тільки покажчики скопійовані, то ми можемо зчитувати будь-яке значення з кореню транзакцій за час 1. Можна зауважити що, незважаючи на одночасну роботу двох потоків з одним записом і його подальшою модифікацією, база гарантує ізольованість, яка в свою чергу означає неможливість видимості проміжних змін за межами транзакції до її завершення [3].

Рис. 2. Схема виконання транзакцій зміни даних

Рис. 3. Схема виконання транзакції зчитування даних

LOCK-FREE АЛГОРИТМ ЗАСТОСУВАННЯ ТРАНЗАКЦІЙ

Враховуючи наведені вище аргументи, сформуємо алгоритм завершення транзакції:

$1.$ Створити новий корінь транзакції T.

$2. $ Встановити значення стану транзакції ORDERED.

$3.$ Атомарно встановити T як новий корінь ланцюга транзакції (сам ланцюг реалізований з використанням неблокуючого однонаправленого списку) [6].

$4.$ Побудувати шлях розміром для кожного зміненого поля об’єкту.

$5.$ Встановити значення стану транзакції BUILT.

$6.$ Спробувати оновити значення покажчика, який вказує на останню послідовну побудовану транзакцію.

$7.$ Валідувати транзакцію, якщо режим зобов’язання - EAGER:

$a.$ Встановити значення стану VALID і спробувати оновити покажчик, який вказує на останню послідовну провалідовану транзакцію, якщо транзакція успішно провалідована.

$b.$ Встановити стан транзакції в INVALID, якщо вона не завершилась.

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

ОЦІНКА ЕФЕКТИВНОСТІ

Якщо ми маємо ланцюг транзакцій M і об’єкт (рядок) з N полями, тоді, в найгіршому випадку, часова складність доступу є \[O(M*\log N)\] (2) ми повинні пройти через всі M дерев. Часова складність може бути зменшена до \[O(M+\log N)\] (3) шляхом збереження кореню транзакції в фільтрі Блума [4], який дозволить перевірити чи конкретне поле було змінено в певній транзакції. Також необхідно розглянути два випадки:

$1.$ Поля з частим доступом. Нехай K - кількість запитів на зчитування конкретного поля, тоді середня вартість поширення посилання \[O\left( \left( M+logN \right)/K \right)=O\left( M/K+logN/K \right)\] (4) ,де M/K є відношенням запису до зчитування. Для K ~ M така вартість є недостатньою.

$2.$ Поля з не частим доступом. Кожен раз ми повинні проходити по ланцюгу поки транзакція з посиланням на поле буде досягнута. Відповідно, необхідно розробити доволі малий алгоритм для збереження M (кількість останніх послідовних дерев з неопрацьованими посиланнями). В описаному підході збереження/модифікації даних є застереження щодо продуктивності: тільки один потік може додавати транзакцію до ланцюга в один момент часу. Ця проблема може бути вирішена шляхом дозування транзакцій локально кожним потоком:

$1.$ Кожен потік підтримує власний ланцюг транзакцій.

$2.$ Якщо розмір локального ланцюга наближується до порогового значення або час закінчується, потік атомарно додає свій ланцюг до кінця основного ланцюга.

ВИСНОВКИ

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

ЛІТЕРАТУРА

$1.$ Muro S. Multi-version concurrency control scheme for a database system / S. Muro, T. Minoura, T. Kameda. // Journal of Computer and System Sciences. – С. 207–224.

$2.$ Navathe S. Fundamentals of Database Systems / S. Navathe, R. Elmasri., 2010. – 882 с.

$3.$ Date C. SQL and Relational Theory, 2nd Edition / O'-Reilly Media, 2011. – 172 с.

$4.$ Parsian M. Data Algorithms. Recipes for Scaling Up with Hadoop and Spark / O'Reilly Media, 2015. – 693 с.

$5.$ Shavit N. The Art of Multiprocessor Programming / N. Shavit, M. Herlihy., 2012. – 73 с. – (Morgan Kaufmann).

$6.$ Harris T. A Pragmatic Implementation of Non-Blocking Linked-Lists [Електронний ресурс] / Timothy L. Harris // DISC '01 Proceedings of the 15th International Conference on Distributed Computing. – 2001. – Режим доступу до ресур-су: https://www.cl.cam.ac.uk/research/srg/netos/papers/2001\-caslists.pdf.

May 17, 2018