Как устроен путь записи в LSM-дереве, лежащем в основе Cassandra и подобных хранилищ?

Ключевая идея в том, что диск получает только последовательные записи: ничего не обновляется по месту, что радикально быстрее случайных обновлений B-tree. Плата возникает при чтении — искомый ключ может лежать в памяти или в любом из накопившихся файлов, поэтому обращений становится несколько; смягчают это фильтры Блума, отсеивающие файлы без нужного ключа, и разреженные индексы. Вторая часть цены — компакция: она потребляет диск и процессор в фоне и способна повлиять на задержки, а до её выполнения удалённые данные физически остаются на диске в виде надгробий. Отсюда практическое правило: такие хранилища выбирают под нагрузку с преобладанием записи и доступом по известному ключу.