LSM Tree: Як Cassandra, RocksDB і LevelDB Пишуть Швидко

Мемберізова база даних: Записи ніколи не торкаються до диска першим

Коли LSM-дерево отримує запис, воно не шукає правильного місця на диску для його розміщення. Замість цього запис вставляється в мемберізовану базу даних, структуру пам'яті, яка зберігає найновіші записи. Це зазвичай перекісноліс або збалансоване дерево, які зберігають найновіші записи. Оскільки мемберізована база даних знаходиться в оперативній пам’яті, вставлення в неї надзвичайно швидке, і завдяки тому, що вона підтримується в порядку за ключами, пізніші операції, такі як сканування діапазонів або очищення, можуть проходити по ній без додаткових зусиль. Кожен запис також додається до журналу попереднього запису на диску перед або поряд із вставкою мемберізованої бази даних. Цей журнал є запобіжним заходом: якщо процес аварійно завершується до того, як мемберізована база даних буде очищена, журнал можна відтворити, щоб відбудувати вміст мемберізованої бази даних. Сам журнал записується послідовно, тому він дешевий навіть незважаючи на те, що він торкається диску при кожному записі. Мемберізована база даних має фіксовану ємність, часто вимірювану десятками мегабайт. Як тільки вона заповнюється, двигун зберігання зупиняє її, починає нову порожню мемберізовану базу даних для поглинання нових записів і планує заморожену базу даних до очищення на диск. Це передача, яка дозволяє записам продовжувати текти без будь-якого блокування введенням-виведенням на диску у типовому випадку. Оновлення та видалення обробляються так само, як нові записи: оновлення — це просто нове значення, записане під існуючим ключем, а видалення — спеціальний маркер, який називається надгробником. Жодна з цих операцій не шукає або не змінює стару копію ключа. Стара копія просто сидить, застаріла, десь на диску, поки стиснення не помітить і не видалить її. Це основна спрощення, яке робить записи LSM швидкими: додавайте зараз, очищайте пізніше. Оскільки читання потребує побачити найновіші дані, мемберізовану базу даних завжди перевіряють першу, перш ніж консультуватися з чимось на диску, оскільки вона містить найновіший стан будь-якого ключа, який нещодавно було записано.

Непостійні таблиці SST: Незмінні, Відсортовані, Видалені послідовно

При злиті мемтаблиці її відсортоване вміст записується на диск у вигляді таблиці SST (sorted string table), як незмінний об'єкт. Ключовою особливістю таблиці SST є те, що вона не змінюється: після запису її дані ніколи не змінюються. Це рішення усуває цілий клас проблем, які виникають при використанні зберігання даних «в місцях». Не потрібні блокування для захисту файлу під час запису, немає ризику аварії, яка залишила б сторінку частково оновленою, і кешування стає простим, оскільки кешований блок ніколи не може застаріти.Оскільки мемтаблиця вже була відсортована, запис її як таблицю SST є одним лінійним проходом: двигун стімолює пари ключ-значення до диска у порядку зростання ключа, в один довгий послідовний запис. Послідовні записи значно швидші за випадкові записи на обертових дисках, оскільки немає часу на пошук між операціями, і вони також більш дружні до флеш-пам’яті, яка страждає від зносу та збільшення кількості записів через невеликі випадкові оновлення.Кожна таблиця SST зазвичай зберігає не лише вихідні дані. Зазвичай вона містить розрідний індекс, який відображає ключі на зміщення байтів, щоб пошук не потребував сканування всього файлу, і часто невеличкий підпис, що узагальнює діапазон ключів, охоплений файлом. Деякі двигуни також зберігають контрольні суми для кожного блоку для виявлення пошкоджень.З плином життя бази даних на диску накопичується багато таблиць SST, одна для кожного злиття мемтаблиці плюс вихідні дані з кожної операції компресії. Один і той же ключ теоретично може існувати в кількох таблицях SST одночасно, якщо його було записано, а потім оновлено. Зараз лише копія в найновішій таблиці SST або в мемтаблиці, якщо вона ще не була злита, є поточним значенням; решта застарілі, але все ще фізично присутні доти, поки компресія не видалить їх.

Чому це важливо

Цей ефект пояснює, чому LSM-дерева (Log Structured Maimon) виконують запити швидше, ніж B-Tree, особливо коли часто відбуваються записи. Щоб знайти значення за певним ключем, LSM-дерево не може просто переглянути один об'єкт; воно потенційно повинно перевірити мемтебл (memtable) і всі SSTable (Sorted String Tables) на диску. Воно завжди починає з мемтебла, оскільки він містить найсвіжіші, невивантажені записи. Якщо ключ знайдено там, пошук негайно припиняється. Якщо ключа немає в мемтеблі, двигун переходить до SSTable, перевіряючи їх у порядку від найновшого до найстарішого. Цей порядок має значення, оскільки ключ може бути записаний кілька разів у різних SSTable, і лише останній версія є правильною. Як тільки знайдено відповідний ключ в SSTable, пошук припиняється, оскільки будь-яка раніша версія цього ключа вже застаріла. Якщо знайдено запис типу

tombstone

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

)%>% read amplification

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

Квіткові фільтри: Пропуск файлів, які не містять ключ

Перевірка кожного SSTable на кожне прочитання зробило б пошуки нестерпно повільними, коли накопичується десятки файлів. Стандартним рішенням є bloom filter – невелика, дешева ймовірнісна структура даних, побудована разом із кожною SSTable під час запису. Bloom filter може швидко і майже без пам’яті відповісти на одне питання: чи можливо, що цей ключ існує в цьому файлі?Bloom filter працює шляхом хешування ключа кількома незалежними хеш-функціями та встановлення відповідних біт у бітовому масиві рівно одним. Щоб перевірити, чи може бути присутнім ключ, використовуються ті ж самі хеш-функції, і двигун перевіряє, чи встановлені всі відповідні біти. Якщо навіть один біт не встановлений, ключ напевно відсутній у файлі, і SSTable можна повністю пропустити без залучення диска. Якщо всі біти випадково встановлені, ключ може бути присутнім, тому двигун повинен прочитати файл індексу, щоб підтвердити це, що іноді призводить до марного пошуку, який називається хибним позитивним результатом. Ключовим є те, що bloom filter ніколи не виробляє хибно негативного результату: він ніколи не стверджує, що ключ відсутній, коли він насправді є.Оскільки bloom filter компактні, часто лише кілька біт на ключ, їх можна зберігати в пам’яті навіть тоді, коли основні SSTable занадто великі для кешування. Це дозволяє базі даних пропускати переважну більшість нерелевантних файлів на диску одним швидким перевіркою в пам'яті, значно зменшуючи розмноження читання, описане раніше, без втрати будь-яких переваг LSM з боку запису.Хибний позитивний відсоток можна регулювати: виділення більше біт на ключ дає менше марних пошуків за рахунок більшого використання пам’яті, тому оператори можуть обмінюватися пам'яттю та затримкою читання залежно від своєї роботи.

Компресія: Узгодження SSTables та компроміс із деревом B

Компресія — це фоновий процес, який підтримує здоров’я LSM-дерева з часом. Він періодично вибирає набір SSTables, об'єднує їх у нові, більші SSTables, і видаляє оригінали. Під час об'єднання, коли один і той же ключ зустрічається в кількох вхідних файлах, зберігається лише найновіша версія, а меморіальні таблички можуть бути остаточно видалені, коли двигун переконався, що раніше SSTable більше не містить ті дані, які вона мала затінити. Це звільняє місце на диску та зменшує кількість файлів, які потрібно просканувати під час майбутнього читання, безпосередньо зменшуючи посилення читання. Компресія не є безкоштовною. Вона споживає введення-виведення даних та обчислювальні ресурси для переписування даних, які вже були написані один раз, що є витратою вартістю, відомою як збільшення запису: окремий логічний запис може з часом бути записаний кілька разів, оскільки він мігрує через послідовність раундів компресії. Різні двигуни розраховують графік компресії по-різному, наприклад стратегії, засновані на розмірах, які об'єднують схожі за розміром файли разом, або рівневі стратегії, які організовують SSTables у рівні збільшувального розміру, але всі вони керують одним і тим самим фундаментальним балансом між кількістю накопичених файлів та кількістю переписування, щоб підтримувати цей баланс. Це місце, де порівняння з деревом B стає конкретним. Дерево B оновлює дані на місці: запис означає знаходження правильної сторінки листя та безпосередньо її модифікацію, що забезпечує передбачуваність і низьку вартість читання, зазвичай один перегляд до одного актуального розташування, але дорогий випадковий запис, оскільки кожен може торкатися різних, випадково розташованих сторінок на диску. LSM-дерево повністю змінює це: записи послідовні та дешеві, будь-яке місце добре, оскільки нічого не шукається в місці; читання може потребувати перевірки кількох місць і покладатися на фонову компресію для підтримки цього числа. Жодна з цих конструкцій не є строго кращою: робоче навантаження, яке багато записує, наприклад, вхід даних журналу або часові ряди, зазвичай віддає перевагу LSM-деревам, тоді як робоче навантаження, яке багато читає з невеликою кількістю записів, часто віддає перевагу дереву B, і вибір движка зберігання насправді є вибором того, яку вартість — збільшення запису та витрати на компресію або вартість випадкового запису — може дозволити робоче навантаження сплатити.

Часті запитання

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте LSM Tree: How Cassandra, RocksDB, and LevelDB Write Fast і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.