В Tarantool 1.7 появился новый движок хранения для флэш и жёстких дисков:
Винил. В Виниле реализован алгоритм LSM-деревьев, так же как в таких
СУБД как Cassandra и RocksDB.

Доклад посвящён LSM деревьям и проблемам их эффективной реализации.

Я начну с объяснения таких терминов как read, write, и space amplification, и расскажу
почему они являются главными критериями при оценке производительности
LSM деревьев.

Затем мы обсудим менее известную метрику для оценки качественной СУБД -
предсказуемое, низкое время ответа. Предсказуемого времени ответа
особенно сложно добиться при реализации LSM дерева, т.к. в этой структуре
данных очень много "пакетных" операций, таких как сортировка и
слияние больших файлов.

Я расскажу о том, как мы решали эти проблемы в Виниле, и почему
подход RocksDB не всегда оптимален.

Tarantool реализован на основе модели акторов, работающих в фиксированном
числе тредов. "Внутренности" базы данных не используют блокировок, как
физических (мутексы), так и логических. Эти принципы сами по себе представляют
как барьер для внедрения RocksDB так и потенциальный буст для альтернативной
технологии.

Гибридный подход к хранению данных в оперативной памяти, использующий
B-деревья для оперативной памяти и LSM деревья для хранения
на диске также снижает требования к оперативной памяти и повышает
производительность.

В настоящее время Винил доступен в релизе Tarantool 1.7.4 и используется
в нескольких проектах Mail.Ru. Доклад может быть интересен как программистам,
интересующимся современными алгоритмами и структурами данных, так и
пользователям Tarantool, рассматривающим его в качестве замены таким
СУБД как MongoDB или Cassandra.