Amazon DynamoDB

DynamoDB таблиця включає записи (item), які мають атрибути, деякі з яких утворюють первинний ключ[10]. Якщо в реляційних системах запис містить кожен атрибут таблиці (або оперує значеннями «null» чи «unknown» за їх відсутності), то записи в DynamoDB не мають схеми. Єдиний виняток: при створенні таблиці розробник вказує первинний ключ, а таблиця вимагає цього ключа для кожного запису. Первинні ключі повинні бути скалярними (рядки, числа чи двійкові) і можуть мати одну з двох наступних форм. Первинний ключ з одним атрибутом відомий як «ключ секції» (partition key) таблиці. Ключ секції визначає секцію по хешу запису, бо ідеальний ключ секції повинен мати рівномірний розподіл діапазону. Первинний ключ також може мати другий атрибут, який DynamoDB називає табличним «ключем сортування». У цьому випадку ключі секцій не повинні бути унікальними; вони поєднуються з ключами сортування для утворення унікального ідентифікатора для кожного запису. Ключ секції все ще використовується для визначення того, в якій секції зберігається запис, але в кожній секції записи сортуються за ключем сортування.

У реляційній моделі індекси, як правило, служать «допоміжною» структурою даних для доповнення таблиці. Вони дозволяють СУБД оптимізувати запити з використанням методів прихованих від користувача, і вони не покращують функціональність запитів. У DynamoDB немає оптимізатора запитів, а індекс — це просто інша таблиця з іншим ключем (або двома), що зберігається разом з оригіналом.[10] Коли розробник створює індекс, то створюється копія даних, але копіюються лише ті поля, які вказані (як мінімум поля, які індексуються та первинний ключ базової таблиці).

Запити записів користувачів DynamoDB адресується безпосередньо до власних індексів. Доступні два типи індексів. Глобальний вторинний індекс (global secondary index, GSI) містить ключ розділу (і необов'язковий ключ сортування), який відрізняється від ключа розділу оригінальної таблиці. Локальний вторинний індекс (local secondary index, LSI) містить той самий ключ розділу, що і початкова таблиця, але інший ключ сортування. Обидва індекси вводять абсолютно нову функціональність запитів у базу даних DynamoDB, дозволяючи виконувати запити на нових ключах.

Ця система індексації є надмірністю даних, чистою та простою, чого не дозволяється в реляційних БД. Індекси — це яскравий приклад того, як DynamoDB надає пріоритет швидкості над ефективністю використання простору. Як і у реляційних системах, DynamoDB оновлює індекси автоматично при додаванні/оновленні/видаленні записів, тому варто бути обережними при створенні індексів, бо інакше є ризик сповільнення важкої на запис бази даних через гальмування оновлення індексу.

DynamoDB використовує JSON для свого синтаксису через його популярність у розробників. Створення таблиці вимагає лише трьох аргументів: TableName, KeySchema — список, що містить ключ секції та необов'язковий ключ сортування — та AttributeDefinitions — список атрибутів записів, серед яких повинні бути атрибути, що використовуються як ключі секції та сортування. Тоді як реляційні бази даних пропонують надійні мови запитів, DynamoDB пропонує лише операції Put, Get, Update та Delete. Запити додавання запитів (Put) містять атрибут TableName та атрибут Item, який складається з усіх атрибутів та значень, які має запис. Запит на оновлення Update відповідає тому ж синтаксису. Аналогічно, щоб отримати записи (Get) або видалити (Delete) запис, просто вказують TableName та Key.

DynamoDB використовує як хешування, так і B-дерева для управління даними. Після введення дані спочатку поширюються на різні секції шляхом гешування ключа секції. Кожна секція може зберігати до 10 ГБ даних та обробляти за замовчуванням 1000 одиниць ємності запису (Write Capacity Units, WCU) та 3000 одиниць ємності зчитування (Read Capacity Units, RCU)[11]. Один RCU являє собою одне узгоджене зчитування в секунду або два не узгоджених читання в секунду для записів розміром до 4 КБ[10]. Один WCU являє собою один запис в секунду для запису розміром до 1 КБ.

Щоб запобігти втраті даних, DynamoDB оснащено дворівневою системою резервної реплікації та довготривалого зберігання[12]. Кожна секція містить три вузли, кожен з яких містить копію даних цієї секції. Кожен вузол містить також дві структури даних: B-дерево, яке використовується для пошуку елементів, і журнал реплікації, який зазначає всі зміни, внесені до вузла. DynamoDB періодично робить знімки цих двох структур даних і зберігає їх протягом місяця в S3, щоб інженери могли виконати своєчасне відновлення баз даних у разі потреби.

У кожній секції один з трьох вузлів позначається «лідером» (leader node). Усі операції запису проходять спочатку через цей лідер-вузол перед поширенням на інші вузли, що робить записи узгодженими в DynamoDB. Для підтримки свого статусу лідер-вузол кожні 1,5 секунди надсилає кожному вузлу «пульс» (heartbeat). Якщо інший вузол перестане приймати пульс, він може ініціювати нові вибори лідера. DynamoDB використовує алгоритм Паксос для обрання лідерів.

Інженери Amazon спочатку уникали використання Dynamo через додаткові інженерні витрати, такі як забезпечення ресурсів, керування секціями та вузлами[7]. Тому команда DynamoDB створила сервіс AutoAdmin для управління базою даних[12]. AutoAdmin замінює вузол, коли він перестає реагувати, для цього дані копіюються з іншого вузла. Коли секція перевищує будь-яке із трьох порогових значень параметрів на читання чи запис (RCU, WCU) або розмір даних перевищує 10 Гб, AutoAdmin автоматично додає нові секції для подальшої сегментації даних[11].

Подібно до систем індексації в реляційній моделі, DynamoDB вимагає, щоб будь-які оновлення таблиці відображалися в кожному з індексів таблиці. DynamoDB робить це за допомогою служби, яка називається «розповсюджувач журналів» (log propagator), та підписана на журнали реплікації кожного вузла і надсилає додаткові запити Put, Update та Delete в індекси за необхідності[12]. Оскільки використання індексів призводить до суттєвого впливу на продуктивність запитів, які виконують запис, то DynamoDB дозволяє користувачеві робити не більше п'яти запитів до будь-якої таблиці.

Припустимо, що користувач DynamoDB виконує операцію запису (Put, Update або Delete). У той час як типова реляційна система перетворює SQL-запит у формулу реляційної алгебри і запускає алгоритми оптимізації, DynamoDB пропускає ці обидва процеси і отримує дозвіл на виконання[12]. Запит надходить на маршрутизатор запитів DynamoDB, який підтверджує автентифікацію — «Чи надходить запит звідти та від того, кім він себе оголосив?» Припускаючи, що ці перевірки виконуються успішно, система гешує ключ секції для відправки у відповідну секцію. Всередині є три вузли, кожен з яких має копію даних секції. Система спочатку виконує запис у лідер-вузол, потім записує на другий вузол, потім надсилає повідомлення про успішне виконання операції і, нарешті, поширюється на третій вузол. Записи є узгодженими, бо вони завжди спочатку надходять через лідер-вузол.

Нарешті, служба «розповсюджувач журналів» поширює зміни на всі індекси. Для кожного індексу він бере значення цього індексу первинного ключа з запису, а потім виконує те саме записування цього індексу без поширення логування. Якщо операція є оновленням до вже існуючого елемента, оновлений атрибут може слугувати первинним ключем для індексу, і, таким чином, B-дерево для цього індексу також має оновлюватись. B-дерева обробляють лише операції вставлення, видалення та читання, тому на практиці, коли розповсюджувач журналу отримує операцію «Update», він видає операцію «Delete» та «Put» всім індексам.

Тепер припустимо, що користувач DynamoDB виконує операцію Get. Маршрутизатор запитів проходить, як і раніше, аутентифікацію та авторизацію. Далі, як зазначено вище, ми гешуємо наш ключ секції, щоб потрапити у відповідний геш. Тепер ми стикаємося з проблемою: як можна вирішити, що слід досліджувати, з трьома вузлами в можливій відповідності один одному. DynamoDB надає користувачеві два варіанти при видачі читання: узгоджене та зрештою узгоджене. При узгодженому читанні відвідується лідер-вузол. Але, тут знов виникає компроміс щодо узгодженості та доступності: у системах важких для читання завжди читання від лідера може перевантажити окремий вузол і зменшити доступність.

В другому варіанті, зрештою узгоджене читання, вибирає випадковий вузол. На практиці саме тут DynamoDB поступається узгодженістю відносно доступності. Якщо ми оберемо цей маршрут, які шанси на неузгодженість? Нам знадобиться операція запису, щоб повернути «успіх» і розпочати поширення на третій вузол, але не закінчити. Нам також знадобиться наш Get, щоб націлитись на третій вузол. Це означає, що ймовірність виникнення неузгодженості 1 до 3 у часовому вікні розповсюдження запису. Якого розміру це часове вікно? Так можливі численні катастрофи, які можуть спричинити відставання вузла, але в переважній більшості випадків третій вузол оновлюється протягом мілісекунд після лідера.