Ця стаття була написана на основі презентації Мохаммада Рези Каргара.

Сучасні бази даних базуються на двох основних компонентах: двигуни зберігання та стратегії індексування, які відіграють вирішальну роль у визначенні продуктивності даних, ефективності вибірки та масштабованості. У цій статті порівнюються дві відомі структури індексів: дерева злитих журналів (LSM-дерева) та B-дерева, зокрема їхні особливості, переваги та компроміси.

LSM-дерева, завдяки своїй структурі «тільки для додавання», відмінно підходять для робочих навантажень, орієнтованих на запис, і добре підходять для NoSQL баз даних. У свою чергу, B-дерева дуже ефективні для операцій, що базуються на читанні, і часто використовуються в реляційних базах даних. Розуміння цих компромісів є важливим для вибору стратегії індексування, яка відповідатиме конкретним вимогам до робочого навантаження та продуктивності. Це дослідження, натхненне презентацією Мохаммада Рези Каргара, підкреслює важливість налаштування систем баз даних для оптимізації їхніх основних структур.

https://www.linkedin.com/posts/alexxubytesystemdesign-coding-interviewtips-activity-6988884641034158080-CSq/

https://bigdatarepublic.nl/articles/storage-engines-how-data-is-stored/#:~:text=In%20general%20these%20types%20of,referred%20to%20as%20log%2Dstructured.

https://medium.com/@shenli3514/distributed-sql-database-internals-3-distributed-storage-engine-bdc49c26242e#:~:text=The%20storage%20engine%20is%20responsible,or%20other%20permanent%20storage%20media.

Дані лише для додавання

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

Дані лише для додавання

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

Основні характеристики:

• Послідовні записи: Нові дані завжди додаються в кінець, що забезпечує ефективні операції запису.
• Незмінність: Після запису існуючі дані не можуть бути змінені безпосередньо у файлі.
• Спрощений контроль за одночасним доступом: Природа "тільки для додавання" мінімізує конфлікти та спрощує механізми контролю за одночасним доступом, оскільки кілька процесів можуть безпечно записувати в кінець файлу одночасно.
• Історія даних: Оскільки дані ніколи не переписуються, це надає повну історію змін, що може бути корисно для аудиту, налагодження та відновлення даних.

Приклади:

• Лог-файли: Класичний приклад, використовується для запису системних подій, історії транзакцій та активності додатків.
• Системи контролю версій (як-от Git): Зміни записуються як нові коміти, створюючи хронологічну історію коду.
• Технології блокчейн: Транзакції додаються до ланцюга блоків, формуючи незмінний і захищений запис.

Переваги:

• Покращена швидкість запису: Послідовні записи зазвичай швидші за випадкові записи.
• Покращена цілісність даних: Незмінність зменшує ризик випадкового пошкодження даних.
• Спрощений контроль за одночасним доступом: Мінімізує необхідність у складних механізмах блокування.

Врахування:

• Споживання простору: Постійне зростання файлу може призвести до проблем з простором.
• Швидкість читання: Для отримання конкретних даних може знадобитися сканування всього файлу, що може бути неефективно для великих наборів даних.

Логічно структуроване дерево злиття (LSM-дерево):

Цей популярний підхід до індексування базується на принципі тільки для додавання. Він використовує відсортовані рядкові таблиці (SSTables) і процес поетапного злиття для ефективного зберігання та вибірки даних.

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

Основні поняття:

• Принцип тільки для додавання: Нові дані завжди додаються в кінець структури, мінімізуючи випадкові записи і покращуючи швидкість запису.
• Відсортовані рядкові таблиці (SSTables): Дані організуються в незмінні, відсортовані файли, звані SSTables. Ці файли ефективно читаються послідовно.
• Поетапна структура: LSM-дерева зазвичай мають кілька рівнів:
  • Memtable: Вбудована структура даних (наприклад, збалансоване дерево), що містить недавно додані дані.
  • Рівні SSTable: Дані з memtable періодично скидаються на диск як SSTables. Ці SSTables організовуються в рівні, причому кожен рівень зазвичай містить більші та більш відсортовані дані.

Як це працює:

1. Записи: Нові дані спочатку додаються до memtable.
2. Скидання: Коли memtable досягає певного порогу розміру, вона скидається на диск як новий SSTable.
3. Злиття: Періодично менші SSTables зливаються в більші, більш відсортовані SSTables. Цей процес зменшує кількість файлів і покращує швидкість читання.
4. Читання: Для пошуку конкретного ключа LSM-дерево спочатку шукає в memtable.
   Якщо не знайдено, система шукає в SSTables на кожному рівні, починаючи з найменших (найновіших) і переходячи до найбільших.

Основні переваги:

• Висока пропускна здатність запису: Додавання до файлів і використання структур в пам'яті значно покращують продуктивність запису.
• Ефективна продуктивність читання: Злиття та сортування покращують локальність даних, що призводить до швидшого читання.
• Ефективність використання простору: Дані стискаються в SSTables, а злиття зменшує надлишковість.

Основні фактори, які слід враховувати:

• Читання з множинними копіями: Під час злиття може знадобитися кілька операцій читання та запису, що може вплинути на продуктивність читання.
• Збільшення простору: До злиття можуть виникати тимчасові витрати пам'яті через кілька копій одних і тих самих даних.

Використання:

• NoSQL бази даних: Широко використовуються в базах даних, таких як Cassandra і LevelDB.
• Бази даних часових рядів: Ефективно обробляють великі обсяги даних з часовими мітками.
• Сховища ключ-значення: Ідеально підходять для додатків з частими записами і рідкими читаннями.

B-дерева

Класична структура індексації на основі дерев, зазвичай використовувана в реляційних базах даних. B-дерева забезпечують відсортоване зберігання ключів і значень і сприяють ефективному пошуку, діапазонним запитам і оновленням.

B-дерево є основною структурою даних у комп'ютерних науках, особливо підходить для індексації в базах даних. Це збалансовані деревоподібні структури, що ефективно зберігають і отримують відсортовані дані.

• Збалансована структура: B-дерева підтримують збалансовану форму дерева, що забезпечує низьку висоту дерева. Це важливо для ефективних операцій пошуку.
• Багато ключів на вузол: На відміну від бінарних дерев пошуку, вузли B-дерева можуть містити кілька ключів і вказівників на дочірні вузли. Це зменшує загальну висоту дерева, мінімізуючи кількість доступів до диска для операцій пошуку.
• Відсортований порядок: Ключі в кожному вузлі та по всьому дереву зберігаються в відсортованому порядку.
• Ефективний пошук: B-дерева дозволяють швидко шукати, вставляти і видаляти елементи. Час пошуку зазвичай є логарифмічним щодо кількості ключів.

Як це працює:

• Пошук: Для знаходження конкретного ключа алгоритм B-дерева починає з кореневого вузла і проходить по дереву, порівнюючи пошуковий ключ з ключами в кожному вузлі.
• Вставка: Нові ключі вставляються в відповідні позиції в дереві. Якщо вузол заповнюється, він ділиться на два вузли, підтримуючи збалансовану структуру.
• Видалення: Видалення ключа передбачає його видалення з вузла і потенційне ребалансування дерева для збереження структури.

Використання:

• Індексація в базах даних: B-дерева широко використовуються як основні або вторинні індекси в реляційних базах даних.
  Вони ефективно підтримують пошук рівності, діапазонні запити та впорядковані обходи.
• Файлові системи: Використовуються в файлових системах для організації та пошуку файлів на диску.
• Бази даних: Використовуються в різних типах баз даних, включаючи реляційні, NoSQL та бази даних часових рядів.

Переваги:

• Ефективний пошук: Логарифмічна складність часу пошуку.
• Добре підходять для діапазонних запитів: Забезпечують ефективне отримання даних в межах конкретного діапазону.
• Збалансована структура: Підтримують хорошу продуктивність навіть для великих наборів даних.

Обмеження:

• Витрати пам'яті: Потрібно додаткове місце для зберігання структури дерева.

Сутність B-дерев: B-дерева є потужною та універсальною структурою даних, що відіграє важливу роль в ефективному зберіганні та отриманні даних у багатьох системах баз даних.

PostgreSQL в основному використовує індекси B-дерев для більшості типів даних.

• Тип індексу за замовчуванням: B-дерево є типом індексу за замовчуванням у PostgreSQL.
• Типи даних: Підтримує широкий спектр типів даних, які можна сортувати, включаючи цілі числа, числа з плаваючою комою, рядки, дати тощо.
• Функціональність: Індекси B-дерев добре підходять для:
  • Запитів рівності: Пошук рядків, де конкретний стовпець відповідає заданому значенню.
  • Діапазонних запитів: Пошук рядків, де значення стовпця потрапляє в певний діапазон.
  • Впорядкованого отримання: Ефективне отримання даних у відсортованому порядку.

Основні моменти:

• Ефективність: Індекси B-дерев забезпечують ефективні операції пошуку, вставки та видалення, що робить їх популярним вибором для багатьох баз даних.
• Універсальність: Їх здатність обробляти різні типи даних та підтримувати різні типи запитів робить їх дуже універсальними.

PostgreSQL пропонує кілька типів індексів, кожен з яких має свої сильні сторони та підходить для різних типів даних і шаблонів запитів:

B-дерево:

• Тип індексу за замовчуванням і найширше використовуваний.
• Відмінно підходить для пошуку рівності, діапазонних запитів та впорядкованих пошуків.
• Підтримує широкий спектр типів даних.

Хеш:

• Оптимізований для запитів рівності.
• Дуже швидкий для точних співпадінь, але не підходить для діапазонних запитів чи впорядкованого отримання.

GiST (Загальний індекс пошуку):

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

SP-GiST (Просторово-розділений GiST):

• Розширення GiST спеціально для просторових даних.
• Покращує продуктивність для певних просторових операцій.

GIN (GINdex):

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

BRIN (Блоковий діапазонний індекс):

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

Вибір правильного індексного двигуна:

Вибір індексного двигуна сильно залежить від таких факторів, як:

• Тип даних: Тип даних, що індексується (наприклад, цілі числа, рядки, геометрії, масиви).
• Шаблони запитів: Типи запитів, які виконуватимуться на даних (наприклад, запити рівності, діапазонні запити, повнотекстові запити).

Яка проблема у наївному підході до індексації бази даних, як використання простого хеш-микроса?

Хоча хеш-мікрос може використовуватися для індексації, він має кілька проблем у контексті баз даних:

• Масштабованість: Хеш-мікрос, що містить увесь індекс в пам'яті, може стати занадто великим для управління, коли база даних розростається.
• Місце на диску: Зберігання всього індексу на диску може призвести до надмірного споживання місця на диску, особливо з великими базами даних.
• Відновлення після збою: Якщо система зазнає збою, відновлення хеш-мікроса з диска може бути трудомістким.

Що таке відсортовані рядкові таблиці (SSTables) і як вони вирішують обмеження простих хеш-микросів?

SSTables — це формат зберігання ключ-значення, який вирішує проблеми наївної індексації, зберігаючи відсортовані пари ключ-значення в сегментах на диску:

• Відсортовані ключі: Відсортування ключів у сегментах забезпечує ефективний пошук за допомогою бінарного пошуку або інших технік.
• Сегментація диска: Розподіл даних на сегменти дозволяє легше зливати і компактити їх, покращуючи продуктивність запису та використання місця на диску.
• Злиття та компактація: Фонові процеси зливають та компактують сегменти для видалення дубльованих ключів і підтримки відсортованої, ефективної структури.

Що таке дерева, побудовані на основі журналу (LSM-дерева), і як вони базуються на концепції SSTables?

LSM-дерева — це структура даних, яка використовує SSTables для забезпечення ефективної продуктивності при читанні та записі:

• Memtable: Вхідні записи спочатку буферизуються в пам'яті у відсортованій структурі, званій Memtable.
• Запис на диск: Коли Memtable досягає порогового розміру, він вивантажується на диск як сегмент SSTable.
• Мульти-рівнева компактація: Сегменти на різних рівнях періодично зливаються і компактуються, оптимізуючи зберігання та продуктивність читання.

Що таке B-дерева і як вони відрізняються від LSM-дерев?

B-дерева — це ще одна структура даних на основі дерева, що використовується для індексації, пропонуючи інший підхід порівняно з LSM-деревами:

• Блокове зберігання: Дані зберігаються в фіксованих розмірах блоках на диску, що відповідає характеристикам вводу-виводу диска для ефективності.
• Збалансована структура дерева: Дерево підтримується збалансованим, що забезпечує логарифмічну складність часу для операцій пошуку, вставки та видалення.
• Оновлення на місці: Оновлення виконуються безпосередньо в дереві, мінімізуючи підсилення запису в порівнянні з LSM-деревами.

Які компроміси між LSM-деревами та B-деревами для індексації баз даних?

Вибір між LSM-деревами та B-деревами залежить від конкретних шаблонів навантаження та вимог до продуктивності:

• Записи: LSM-дерева зазвичай добре справляються з записами, орієнтованими на велике навантаження завдяки своїй природі додавання лише до кінця і ефективним послідовним записам.
• Читання: B-дерева часто демонструють кращу продуктивність при читанні, особливо для випадкових запитів, завдяки оновленням на місці та збалансованій структурі.
• Підсилення простору: LSM-дерева можуть мати більше підсилення простору через процес злиття та компактації.
• Конкуренція: B-дерева зазвичай обробляють конкуренцію більш ефективно завдяки своїй блоковій структурі та механізмам блокування.

Що таке підсилення запису і чому це важливо при індексації бази даних?

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

• Вплив: Велике підсилення запису може негативно вплинути на продуктивність запису, особливо в додатках, орієнтованих на великі записи.
• LSM-дерева проти
  B-дерева:** LSM-дерева, як правило, мають більше підсилення запису через їх процес злиття та компактації, тоді як B-дерева мінімізують це за допомогою оновлень на місці.

Які є недоліки у LSM-дерев?

Незважаючи на свої переваги, LSM-дерева мають деякі недоліки, які слід враховувати:

• Вплив компактації: Процеси компактації можуть спричиняти варіативність продуктивності, що може призвести до збільшення латентності в деяких випадках.
• Просторові витрати: Компактація та злиття можуть призвести до тимчасових витрат на зберігання.
• Складність: Реалізація та управління LSM-деревами може бути більш складним порівняно з більш простими структурами індексів.

Як обрати правильну структуру індексації для мого додатка бази даних?

Оптимальна структура індексації залежить від таких факторів:

• Навантаження: Визначте, чи ваш додаток має високе навантаження на читання, записи або їх поєднання.
• Цілі продуктивності: Визначте відносну важливість латентності читання, пропускної здатності запису та ефективності простору.
• Характеристики даних: Розгляньте розмір, розподіл та шаблони оновлень ваших даних.
• Система бази даних: Досліджуйте можливості та обмеження системи бази даних, яку ви використовуєте.

Розуміння структур індексів бази даних

Короткий квіз

1. Яка основна мотивація для використання індексів бази даних?
2. Поясніть концепцію "append-only" журналів в контексті механізмів зберігання даних бази даних.
3. Опишіть основний компроміс між продуктивністю читання та запису при порівнянні B-дерев і LSM-дерев.
4. Що таке "підсилення запису" і чому це є проблемою, особливо в додатках бази даних з високими вимогами до запису?
5. Коротко опишіть процес вставки нової пари ключ-значення в структуру індексації B-дерева.
6. Яка роль "memtable" у реалізації LSM-дерева?
7. Поясніть, як відсортовані рядкові таблиці (SSTables) покращують простий підхід з хеш-мапою для індексації.
8. Яке значення має "компактація" в контексті LSM-дерев?
9. Чому процес компактації в LSM-деревах може призводити до піків продуктивності? Як ці піки можуть впливати на додаток?
10. Коротко обговоріть концепцію "фактору розгалуження" в B-деревах та її вплив на продуктивність.

Ключ до відповідей

1. Індекси бази даних використовуються для прискорення операцій отримання даних. Вони забезпечують механізм швидкого пошуку, який уникає необхідності сканувати весь набір даних.
2. Append-only журнали — це механізм зберігання, при якому нові дані завжди додаються в кінець журналу. Цей підхід спрощує запис даних і відновлення, але потребує додаткових механізмів для індексації та запитів.
3. B-дерева зазвичай забезпечують більш швидку продуктивність при читанні завдяки своїй структурі, що дозволяє ефективно виконувати операції пошуку. LSM-дерева, які віддають перевагу швидкості запису за рахунок додавання нових даних в кінець, можуть мати повільніше читання через необхідність зливати і компактувати сегменти.
4. Підсилення запису — це явище, коли одна логічна операція запису призводить до кількох фізичних записів на носії даних. Це може суттєво вплинути на продуктивність, особливо в додатках з високими вимогами до запису, збільшуючи диск I/O і знижуючи пропускну здатність.
5. Вставка пари ключ-значення в B-дерево включає пошук відповідного листового вузла за ключем. Якщо в листі є місце, пара вставляється. Якщо ні, вузол розділяється, і структура дерева балансуватиметься.
6. Memtable є буфером в пам'яті в LSM-дереві, який утримує нещодавно записані дані в відсортованому порядку. Коли він досягає певного розміру, його вміст вивантажується на диск як SSTable.
7. SSTables покращують хеш-мапи, зберігаючи пари ключ-значення в відсортованому порядку в кожному сегменті. Це сортування дозволяє ефективно виконувати запити за діапазоном та бінарний пошук всередині сегментів.
8. Компактація в LSM-дереві зливає та переписує SSTables для видалення дубльованих ключів, відновлення місця, що було витрачено на видалені дані, і покращення продуктивності читання, зменшуючи кількість сегментів для сканування.
   9.
   Процес компактації, хоча і є корисним в довгостроковій перспективі, може призвести до тимчасових піків продуктивності, оскільки він включає значні операції з вводу/виводу. Ці піки можуть вплинути на додаток, спричиняючи збільшення латентності та змінність часу відповіді.
9. Фактор розгалуження в B-дереві відноситься до кількості дочірніх вузлів, які можуть бути у вузла. Вищий фактор розгалуження призводить до менш глибокого дерева, зменшуючи кількість рівнів, які потрібно пройти під час операцій пошуку, і загалом покращує продуктивність.

Есе запитання

1. Порівняйте переваги та недоліки використання структур індексації B-дерев і LSM-дерев у різних додатках бази даних. Врахуйте такі фактори, як навантаження на читання/запис, розмір даних та вимоги до продуктивності.
2. Докладно обговоріть концепцію підсилення запису. Поясніть, як це виникає в різних структурах індексації, і окресліть стратегії для мінімізації його впливу.
3. Поясніть роль компактації в LSM-деревах. Опишіть різні рівні компактації та обговоріть компроміси, пов'язані з вибором стратегії компактації.
4. Проаналізуйте проблеми контролю конкурентності в структурах індексації. Обговоріть різні механізми блокування і те, як вони вирішують проблеми, пов'язані з одночасними операціями читання та запису.
5. Поясніть, як вибір відповідної структури індексації може бути обумовлений специфічними характеристиками набору даних і очікуваними шаблонами запитів. Наведіть приклади для ілюстрації своїх тверджень.

Глосарій ключових термінів

Append-only Log: Механізм зберігання, при якому нові дані завжди додаються в кінець журналу. B-tree: Самобалансуюча деревоподібна структура даних, яка зазвичай використовується для індексації в базах даних, що забезпечує ефективні операції пошуку, вставки та видалення. Branching Factor: Кількість дочірніх вузлів, які може мати вузол у B-дереві. Compaction: Процес в LSM-деревах, що зливає і переписує SSTables для видалення дублікованих ключів, відновлення місця та покращення продуктивності читання. Hash Map: Структура даних, яка використовує хеш-функцію для відображення ключів на відповідні значення, забезпечуючи швидку продуктивність пошуку в середньому випадку. Index: Структура даних, яка прискорює операції отримання даних у базі даних, надаючи механізм швидкого пошуку на основі конкретних ключів. LSM-tree (Log-Structured Merge-Tree): Механізм зберігання, що надає пріоритет продуктивності запису, додаючи нові дані в append-only журнал і використовуючи фонові злиття для оптимізації продуктивності читання. Memtable: Буфер в пам'яті в LSM-дереві, який утримує нещодавно записані дані в відсортованому порядку. SSTable (Sorted String Table): Формат файлу, що використовується в LSM-деревах для зберігання пар ключ-значення в відсортованому порядку в кожному сегменті. Write Amplification: Явища, при якому одна логічна операція запису призводить до кількох фізичних записів на носії даних.

Висновок

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

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

Перекладено з: Database Deep Dive: Exploring Storage Engines and Indexing Strategies,LSM-Trees vs. B-Trees