← вся теориятеория к собесу · Распределённые системы

Распределённые системы: внутренности хранилищ

Движки хранения: LSM против B-tree

Под каждой БД лежит движок хранения, и их два семейства - B-tree и LSM-tree. Собес проверяет, можешь ли ты по движку предсказать поведение под нагрузкой: кто король чтения, кто записи, и почему.

Стержень: B-tree пишет на место и силён в точечных чтениях, LSM пишет последовательно и силён в потоке записи ценой чтения через уровни.

// Формулировки: «чем LSM отличается от B-tree?», «зачем bloom-фильтры?», «что такое write amplification?».

Два семейства

B-tree: страницы фиксированного размера, чтение за O(log N) страниц, записи на место (update-in-place) плюс WAL. Король точечных чтений, стабилен, но деградирует на случайной записи из-за расщепления страниц.

LSM-tree (log-structured merge): запись сначала в memtable в памяти и в WAL, затем флаш в иммутабельный отсортированный файл (SSTable), а фоновая компакция сливает уровни. Запись последовательна и дёшева, зато чтение может пройти несколько уровней.

// Отсюда выбор по workload: поток событий с тяжёлой записью - LSM (Cassandra, RocksDB, семейство ClickHouse); транзакционное чтение-запись - B-tree (Postgres, MySQL).

LSM-tree: memtable → SSTable-уровни с фоновой компакцией
B-tree: страницы, update-in-place; король точечных чтений

Амплификация и bloom-фильтры

У LSM три силы в треугольнике: read, write и space amplification. Компакция снижает read-amp (меньше уровней для чтения) ценой write-amp (данные переписываются при слияниях); стиль компакции (leveled против tiered) двигает баланс.

Bloom-фильтры спасают чтение LSM: вероятностная структура отвечает «этого ключа в данном SSTable точно нет» без похода на диск. Проверка отсутствия становится почти бесплатной, и чтение не лезет в файлы, где ключа гарантированно нет.

// Но холодных случайных чтений от LSM ждать не стоит: если ключ есть, путь может пройти через несколько уровней. Это плата за дешёвую запись.

write amplification: во сколько раз данные переписываются сверх исходного
bloom filter: вероятностная проверка «ключа точно нет»

WAL, индексы, тюнинг

WAL (write-ahead log) - фундамент durability обоих семейств: сначала пишем лог, потом применяем к структуре данных. Политика fsync - честный трейдоф скорости и потери последних записей при сбое.

Вторичный индекс это ещё одна структура, обновляемая на каждую запись: ускоряет чтение, замедляет запись. В write-heavy системе индексы «на всё» означают, что каждая запись платит за каждый индекс.

// Главное практическое следствие: тюнить БД, не зная её движка, вредно - советы для B-tree (например, про случайные обновления) прямо противопоказаны LSM, и наоборот.

WAL: write-ahead log: durability до применения к структуре
fsync-политика: когда сбрасывать лог на диск: скорость против потери

Как отвечать: «Чем LSM-дерево отличается от B-tree и когда что?»

Разница в том, как они пишут. B-tree обновляет данные на месте: находит страницу и правит её, плюс пишет WAL. Это даёт быстрые и предсказуемые точечные чтения за логарифм, но случайная запись дёргает страницы и вызывает их расщепление. LSM пишет иначе: новое сначала попадает в memtable в памяти и в WAL, потом флашится в иммутабельный отсортированный файл, а фоновая компакция сливает файлы по уровням. Запись получается последовательной и очень дешёвой, зато чтение может пройти несколько уровней, и его спасают bloom-фильтры, отсекающие файлы без нужного ключа. Отсюда выбор: тяжёлый поток записи, события, логи, временные ряды - беру LSM, это Cassandra, RocksDB, ClickHouse-семейство. Транзакционная нагрузка с частыми точечными чтениями - B-tree, Postgres или MySQL. И тюнинг у них противоположный, поэтому движок надо знать.

Почему это сильный ответ: различие выведено из способа записи (in-place против log-structured), названы следствия для чтения (bloom-фильтры), конкретные СУБД (система управления базами данных) каждого лагеря и предупреждение о противоположном тюнинге.

На чём валят

−Ждать от LSM-хранилища дешёвых случайных чтений холодных ключей - путь через уровни.
−Отключить или отложить fsync WAL ради скорости и «потерять последние секунды» при сбое - осознанно ли?
−Игнорировать компакцию в capacity-планировании - она ест диск и I/O кластера.
−Вторичные индексы «на всё» в write-heavy системе - каждая запись платит за каждый.
−Тюнить БД, не зная её движка: советы для B-tree вредны для LSM и наоборот.

Проверьте себя

Пять вопросов из банка по этой подтеме. Всего их 10, остальные разбираются в тренажёре.

#storage_internals1 / 5
Почему хранилища с LSM-деревом (Cassandra, RocksDB, ClickHouse) быстры на запись?
A)Потому что LSM-дерево обновляет каждую строку прямо на её месте на диске без дополнительных файлов
B)Потому что LSM держит базу данных в оперативной памяти и на диск почти не пишет
C)Пишут последовательно в память + append-лог, а на диск сбрасывают отсортированными пачками; слияние идёт фоном
D)Потому что LSM отказывается от журналирования (WAL), экономя на записи
показать ответ и разбор
+C)Пишут последовательно в память + append-лог, а на диск сбрасывают отсортированными пачками; слияние идёт фоном
// разбор: LSM-tree копит записи в памяти (memtable) и последовательно в WAL, а затем сбрасывает на диск целыми отсортированными файлами (SSTable), которые не меняются на месте. Вместо дорогих случайных обновлений страниц (как в B-tree) — дешёвая последовательная запись, отсюда высокий write-throughput. Плата: чтение может заглянуть в несколько SSTable (смягчается bloom-фильтрами и индексами), а фоновая компакция сливает файлы и убирает устаревшее, потребляя I/O. Классический размен write-amplification против read-amplification.
#storage_internals2 / 5
Что даёт MVCC (multiversion concurrency control) в базах вроде PostgreSQL?
A)MVCC блокирует таблицу на чтение при каждой записи, обеспечивая согласованность через строгие локи
B)MVCC хранит ровно одну текущую версию каждой строки, мгновенно затирая предыдущую при апдейте
C)MVCC устраняет необходимость в очистке и обслуживании таблиц
D)Читатели видят согласованный снимок и не блокируют писателей: хранятся версии строк, каждая транзакция видит свою
показать ответ и разбор
+D)Читатели видят согласованный снимок и не блокируют писателей: хранятся версии строк, каждая транзакция видит свою
// разбор: MVCC хранит несколько версий строки: изменение создаёт новую версию, не затирая старую сразу. Каждая транзакция видит снимок, актуальный на её начало, поэтому читатели не блокируют писателей и наоборот — резко выше конкурентность, чем при блокировочном чтении. Плата: старые версии копятся и их надо чистить (VACUUM в Postgres), иначе таблица распухает (bloat); длинные транзакции удерживают старые версии и мешают очистке. MVCC — почему в Postgres «читатели не мешают писателям», но нужен уход за bloat.
#storage_internals3 / 5
Зачем в распределённых хранилищах применяют bloom-фильтр?
A)Быстро и компактно отсеять точно отсутствующие ключи, не читая диск: «возможно есть» или «точно нет»
B)Bloom-фильтр хранит список ключей и даёт точный ответ о наличии
C)Он может ошибочно сказать «ключа нет», когда на самом деле ключ в хранилище присутствует
D)Bloom-фильтр применяется для сжатия данных на диске, а не для поиска ключей
показать ответ и разбор
+A)Быстро и компактно отсеять точно отсутствующие ключи, не читая диск: «возможно есть» или «точно нет»
// разбор: Bloom-фильтр — компактная вероятностная структура, отвечающая на «есть ли ключ» без хранения самих ключей: «точно нет» (можно не лезть на диск/в SSTable) или «возможно есть» (тогда проверяют). Ложноотрицательных нет, ложноположительные редки. В LSM-хранилищах он экономит массу дисковых чтений: перед обращением к SSTable фильтр отсекает файлы, где ключа точно нет. Цена — немного памяти и настраиваемая доля ложных срабатываний. Широко используется в Cassandra, HBase, RocksDB, ClickHouse.
#storage_internals4 / 5
Чем B-tree индекс (Postgres) отличается по профилю нагрузки от LSM-дерева (Cassandra)?
A)B-tree выигрывает на чтении/точечном поиске, LSM — на интенсивной записи
B)B-tree и LSM идентичны по профилю нагрузки, отличаясь лишь названием и вендором СУБД
C)LSM быстрее B-tree и на чтении, и на записи, поэтому B-tree устарел
D)B-tree применим в памяти, а LSM — на диске, отсюда разница между ними
показать ответ и разбор
+A)B-tree выигрывает на чтении/точечном поиске, LSM — на интенсивной записи
// разбор: B-tree обновляет страницы на месте: чтение и точечный поиск дёшевы (один спуск по дереву), но случайная запись дороже (обновление страниц, возможные разбиения). LSM пишет последовательно пачками (memtable → SSTable) без обновления на месте: запись очень дешева, но чтение может проверять несколько SSTable (смягчается bloom-фильтрами). Отсюда выбор: read-heavy и точечные lookup'ы — B-tree (OLTP, Postgres); write-heavy потоки событий/тайм-серии — LSM (Cassandra, ClickHouse). Это про размен read- и write-amplification.
#storage_internals5 / 5
Что такое compaction в LSM-хранилище и зачем она нужна?
A)Compaction сжимает отдельные файлы архиватором, не затрагивая число файлов и старые версии
B)Это операция записи новых данных, заменяющая обычную вставку в memtable
C)Compaction отключает bloom-фильтры хранилища, ускоряя запись ценой чтения
D)Фоновое слияние SSTable: убирает устаревшие версии и tombstone, ограничивает число файлов для чтения
показать ответ и разбор
+D)Фоновое слияние SSTable: убирает устаревшие версии и tombstone, ограничивает число файлов для чтения
// разбор: LSM пишет данные новыми иммутабельными файлами (SSTable), поэтому одна строка со временем оказывается в нескольких файлах (новые версии, удаления-tombstone). Без обслуживания чтение вынуждено проверять всё больше файлов (растёт read-amplification), а место занимают устаревшие версии. Compaction фоном сливает SSTable, оставляя актуальную версию каждой строки и физически удаляя tombstone, — так число файлов и объём под контролем. Плата — она ест диск I/O и CPU, конкурируя с рабочей нагрузкой.

дальше

Теорию прочитали. Навык ставится повторением

В Сеньорчике эта подтема идёт в ежедневных сессиях: движок возвращает её, пока ответы не станут уверенными, и ведёт прогресс отдельно по каждой подтеме. Теория внутри тоже бесплатна, лимит только на количество вопросов в день.

Открыть тренажёр Вся тема: Распределённые системы