LSM-дерево — Вікіпедія
В інформатиці журнально-структуровано дерево зі злиттям (також відоме як LSM-дерево або LSMT[1] ) — це структура даних, яка надає швидкий доступ по індексу в умовах частих запитів на запис (наприклад при роботі з журналами транзакцій). LSM-дерева, як і інші дерева пошуку, підтримують пари «ключ-значення». LSM-дерева зберігають дані у двох або більше окремих структурах, кожна з яких оптимізована для роботи з носієм даних на якому вона буде зберігатись; Синхронізація даних між цими двома структурами проходить ефективно, в пакетах.
Проста версія LSM-дерева – дворівневе дерево – складається з двох деревоподібних структур C0 та C1. C0 менше за розміром і зберігається повністю в оперативній пам'яті, а C1 знаходиться в незалежній пам'яті. Нові записи вставляються у C0. Якщо після вставки розмір C0 перевищує певне задане граничне значення, безперервний сегмент видаляється з C0 і зливається з C1 на пристрої постійного зберігання. Хороша продуктивність досягається за рахунок того, що дерева оптимізовані під своє сховище, а злиття здійснюється ефективно і групами по кілька записів, використовуючи алгоритм, що нагадує сортування злиттям.
Тип | Гібридне | |
---|---|---|
Винайдено | [1]Патрік О'Ніл, Едвард Ченг, Елізабет О'Ніл | |
Часова складність | ||
Операція | Середнє | Найгірший випадок |
Вставка | ||
Пошук | ||
Видалення |
Проста версія LSM-дерева – дворівневе дерево – складається з двох деревоподібних структур C0 та C1. C0 менше за розміром і зберігається повністю в оперативній пам'яті, а C1 знаходиться в незалежній пам'яті. Нові записи вставляються у C0. Якщо після вставки розмір C0 перевищує певне задане граничне значення, безперервний сегмент видаляється з C0 і зливається з C1 на пристрої постійного зберігання. Хороша продуктивність досягається за рахунок того, що дерева оптимізовані під своє сховище, а злиття здійснюється ефективно і групами по кілька записів, використовуючи алгоритм, що нагадує сортування злиттям.
![Diagram illustrating compaction of data in a log-structured merge tree](http://upload.wikimedia.org/wikipedia/commons/thumb/f/f2/LSM_Tree.png/220px-LSM_Tree.png)
Більшість LSM-дерев, що використовуються на практиці, складаються з багатьох компонентів. Рівень C0 (назвемо його MemTable) зберігається в оперативній пам'яті і є мутабельним. Зазвичай він представлений у вигляді дерева і виступає як буфер записів. А рівень C1 представлений у вигляді не одної, а декількох таблиць, що збережені у незалежній пам'яті. Коли MemTable досягає певного розміру, вона повністю записується на диск і формує нову таблицю. А вміст поточної MemTable обнуляється. Оскільки з часом кількість таблиць на диску буде рости, щоб уникнути періодично таблиці на диску об'єднуються (або ущільнюються).
Оскільки дані на диску не перезаписуються, то вони можуть бути організовані в структуру, яка буде максимально оптимізована для запитів на читання. Зазвичай дані організовують у Таблицю Сортованих Строк (Sorted String Table чи SSTable). Цей формат передбачає, що всі ключі будуть сортовані, та існуватиме тільки одна пара «ключ-значення» в межах одної таблиці/файлу. Таким чином можна досягти наступних переваг:
- Таблиці можна легко об'єднувати, використовуючь принцип сортування злиттям. Що дає об'єднану таблицю, яка відповідає вимогам SSTable.
- Пошук легко організувати за допомогою алгоритму бінарного пошуку, або ж створити індекс з позиціями для певних ключів проводити послідовне сканування. (Наприклад: Знаючи позиції ключів гараж і гарувати, можна провести послідовний пошук ключа гарний)
Пошук значення по ключу проводиться в першу чергу в MemTable, оскільки там знаходяться найактуальніші дані. Якщо ж в MemTable ключ не знайдений, то пошук має бути проведений в усіх таблицях на диску. Певний ключ може з’являтися серед декількох таблиць, і яке значення з наявних варто повернути як результат, залежить від програми. Деяким програмам просто потрібна найновіша пара «ключ-значення» з заданим ключем. Деякі програми повинні певним чином об'єднувати значення, щоб отримати сукупне значення. Наприклад, в Apache Cassandra кожне значення представляє рядок у базі даних, а різні версії рядка можуть мати різні набори стовпців. [1]
Щоб знизити час виконання запитів, система повинна уникати ситуацій, коли виконується занадто багато підзапитів до кожної таблиці SSTable.
Оскільки пошук в LSM-дереві може бути повільним, у випадку якщо ключ відсутній в базі даних (тому що пошук має бути проведений в MemTable, а також усіх SSTable), зазвичай попередньо робиться перевірка на наявність ключа за допомогою Фільтра Блума. Це дозволяє суттєво зменшити навантаження на базу даних.
В LSM-деревах вставка, оновлення і видалення даних це операції, які не потребують пошуку наявного в сховищі значення. Натомість вставка і оновлення просто додають нове значення по ключу, а під час виконання запиту на читання як результат повертається тільки найновіша пара «ключ-значення».
Оскільки таблиці на диску не можуть бути змінені (окрім операції ущільнення), операція видалення є особливим випадком операції вставки. Для того щоб значення по ключу вважалося видаленим, проводиться операція вставки спеціального «запису видалення» (також відомий як tombstone). В такому випадку, під час виконання запиту на читання, система відкидає всі значення які "старші" за «запис видалення».
- ↑ а б Leveled Compaction in Apache Cassandra : DataStax. 13 лютого 2014. Архів оригіналу за 13 лютого 2014.
- 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.