LSM-дерево

В інформатиці журнально-структуровано дерево зі злиттям (також відоме як LSM-дерево або LSMT ) — це структура даних, яка надає швидкий доступ по індексу в умовах частих запитів на запис (наприклад при роботі з журналами транзакцій). LSM-дерева, як і інші дерева пошуку, підтримують пари «ключ-значення». LSM-дерева зберігають дані у двох або більше окремих структурах, кожна з яких оптимізована для роботи з носієм даних на якому вона буде зберігатись; Синхронізація даних між цими двома структурами проходить ефективно, в пакетах.

Проста версія LSM-дерева – дворівневе дерево – складається з двох деревоподібних структур C₀ та C₁. C₀ менше за розміром і зберігається повністю в оперативній пам'яті, а C₁ знаходиться в незалежній пам'яті. Нові записи вставляються у C₀. Якщо після вставки розмір C₀ перевищує певне задане граничне значення, безперервний сегмент видаляється з C₀ і зливається з C₁ на пристрої постійного зберігання. Хороша продуктивність досягається за рахунок того, що дерева оптимізовані під своє сховище, а злиття здійснюється ефективно і групами по кілька записів, використовуючи алгоритм, що нагадує сортування злиттям.

LSM-дерево

Тип	Гібридне
Винайдено	[1]Патрік О'Ніл, Едвард Ченг, Елізабет О'Ніл
Часова складність
Операція	Середнє	Найгірший випадок
Вставка	$\Theta (1)$	$\Theta (1)$
Пошук	$O(n)$	$O(n)$
Видалення	$O(n)$	$O(n)$

Проста версія LSM-дерева – дворівневе дерево – складається з двох деревоподібних структур C₀ та C₁. C₀ менше за розміром і зберігається повністю в оперативній пам'яті, а C₁ знаходиться в незалежній пам'яті. Нові записи вставляються у C₀. Якщо після вставки розмір C₀ перевищує певне задане граничне значення, безперервний сегмент видаляється з C₀ і зливається з C₁ на пристрої постійного зберігання. Хороша продуктивність досягається за рахунок того, що дерева оптимізовані під своє сховище, а злиття здійснюється ефективно і групами по кілька записів, використовуючи алгоритм, що нагадує сортування злиттям.

Діаграма, що ілюструє ущільнення даних у LSM-дереві.

Більшість LSM-дерев, що використовуються на практиці, складаються з багатьох компонентів. Рівень C₀ (назвемо його MemTable) зберігається в оперативній пам'яті і є мутабельним. Зазвичай він представлений у вигляді дерева і виступає у якості буфера записів. А рівень C₁ представлений у вигляді не одної, а декількох таблиць, що збережені у незалежній пам'яті. Коли MemTable досягає певного розміру, вона повністю записується на диск і формує нову таблицю. А вміст поточної MemTable обнуляється. Оскільки з часом кількість таблиць на диску буде рости, щоб уникнути періодично таблиці на диску об'єднуються (або ущільнюються).

Організація даних на диску

Оскільки дані на диску не перезаписуються, то вони можуть бути організовані в структуру, яка буде максимально оптимізована для запитів на читання. Зазвичай дані організовують у Таблицю Сортованих Строк (Sorted String Table чи SSTable). Цей формат передбачає, що всі ключі будуть сортовані, та існуватиме тільки одна пара «ключ-значення» в межах одної таблиці/файлу. Таким чином можна досягти наступних переваг:

• Таблиці можна легко об'єднувати, використовуючь принцип сортування злиттям. Що дає об'єднану таблицю, яка відповідає вимогам SSTable.
• Пошук легко організувати за допомогою алгоритму бінарного пошуку, або ж створити індекс з позиціями для певних ключів проводити послідовне сканування. (Наприклад: Знаючи позиції ключів гараж і гарувати, можна провести послідовний пошук ключа гарний)

Пошук даних

Пошук значення по ключу проводиться в першу чергу в MemTable, оскільки там знаходяться найактуальніші дані. Якщо ж в MemTable ключ не знайдений, то пошук має бути проведений в усіх таблицях на диску. Певний ключ може з’являтися серед декількох таблиць, і яке значення з наявних варто повернути як результат, залежить від програми. Деяким програмам просто потрібна найновіша пара «ключ-значення» з заданим ключем. Деякі програми повинні певним чином об'єднувати значення, щоб отримати сукупне значення. Наприклад, в Apache Cassandra кожне значення представляє рядок у базі даних, а різні версії рядка можуть мати різні набори стовпців.

Щоб знизити час виконання запитів, система повинна уникати ситуацій, коли виконується занадто багато підзапитів до кожної таблиці SSTable.

Оскільки пошук в LSM-дереві може бути повільним, у випадку якщо ключ відсутній в базі даних (тому що пошук має бути проведений в MemTable, а також усіх SSTable), зазвичай попередньо робиться перевірка на наявність ключа за допомогою Фільтра Блума. Це дозволяє суттєво зменшити навантаження на базу даних.

Оновлення і видалення даних

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

Оскільки таблиці на диску не можуть бути змінені (окрім операції ущільнення), операція видалення є особливим випадком операції вставки. Для того щоб значення по ключу вважалося видаленим, проводиться операція вставки спеціального «запису видалення» (також відомий як tombstone). В такому випадку, під час виконання запиту на читання, система відкидає всі значення які "старші" за «запис видалення».

Джерела

• O'Neil, Patrick E.; Cheng, Edward; Gawlick, Dieter; O'Neil, Elizabeth (June 1996). The log-structured merge-tree (LSM-tree). Acta Informatica. 33 (4): 351—385. doi:10.1007/s002360050048.
• Li, Yinan; He, Bingsheng; Luo, Qiong; Yi, Ke (2009). Tree Indexing on Flash Disks. 2009 IEEE 25th International Conference on Data Engineering. с. 1303—6. doi:10.1109/ICDE.2009.226. ISBN 978-1-4244-3422-0.
• Luo, Chen; Carey, Michael J. (July 2019). LSM-based storage techniques: a survey. The VLDB Journal. arXiv:1812.07527. doi:10.1007/s00778-019-00555-y.