#30: LSM Tree: структура данных взрывает мозг

[00:20] Здарова! Меня зовут Саша Пахомов, и я инженер, который любит своё дело. Вы слушаете подкаст, в котором разработчик современной базы данных изучает то, как они работают, и делится знаниями со слушателями. Тема сегодняшнего выпуска — LSM-дерево, или Log-Structured Merge Tree. Это структура данных, которая взрывает мозг. Всё больше современных баз данных начинают использовать LSM-деревья в качестве основного низкоуровневого хранилища ключ-значение. По сути, это единственная реальная альтернатива всем известным B+-деревьям. Это юбилейный, тридцатый выпуск подкаста «Тысяча фичей». Мы начинаем изучать LSM-деревья. Поехали!

[01:10] Прежде чем погрузиться в кишочки и начать разбираться, как работают LSM-деревья, давайте сначала поговорим о том, а зачем нам вообще нужна какая-то другая структура данных — LSM-дерево, — если у нас уже есть B+-деревья и всё им подобное. Есть copy-on-write B+, есть разные другие модификации, про которые мы с вами разговаривали: сначала в 24-м выпуске, где ознакомились со структурой данных B+-дерево, а потом в 26-м выпуске мы уже рассматривали конкретные реализации B+-деревьев, которые работают в современных системах. Так почему нам их недостаточно? Зачем вообще что-то ещё изобретать и использовать?

[01:48] Для начала давайте рассмотрим классический трейд-офф, который всегда стоит перед нами, когда мы выбираем структуру данных. Мы хотим оптимизировать чтение, хотим оптимизировать запись — и при этом не хотим раздувать занимаемое место, а мы этого, как правило, не хотим.

[02:26] Кстати, эта гипотеза называется RUM — read-update-memory. Она гласит, что если представить чтение (read), запись (update) и место (memory) как три вершины треугольника, то мы можем оптимизировать только две из них. Либо оптимизируем read и space, либо update и space, либо read и update — но тогда у нас вырастает space. То есть гипотеза звучит так: мы не можем одновременно оптимизировать все три параметра. Что-то очень похоже на CAP-теорему, на самом деле.

[02:53] Так вот, B+-деревья — это как раз те самые структуры, что оптимизированы на чтение, немножко на запись и плюс-минус адекватно используют место. Но у B+-деревьев есть несколько проблем, которые не позволяют им оптимизироваться под высокую запись. То есть если мы хотим писать в B+-дерево очень-очень много и очень-очень часто, то возникают проблемы.

[03:14] Например, какие проблемы? Внесение данных — то, что я называю update, — это и add, и delete: любая модификация, я её в дальнейшем буду называть update (insert или update, как многие называют). Так вот, эти модифицирующие операции, которые меняют структуру данных, могут привести к тому, что узлы B+-дерева начнут процесс либо слияния (если мы делали удаление и преодолели какой-то трешхолд, на котором нужно сливать два узла, две страницы или более), либо разделения — наоборот, когда мы заполнили узел на максимум, места больше нет и узел нужно разделить. Это процесс слияния-разделения.

[03:51] Кстати, если вам сложновато представить B+-деревья — вдруг вы не слушали 24-й или 26-й выпуск либо подзабыли, — у меня осталась пасхалка в Telegram-канале для подписчиков «Тысячи фичей» (кстати, вступайте). Я там нарисовал от руки, когда сам разбирался, B+-дерево — просто так, как я его себе представляю. Открывайте картинку, PNG-шку, и можете прямо вместе с моим рассказом её просматривать. А мы идём дальше.

[04:19] Помимо разделения и слияния, у B+-дерева есть и другие проблемы. Например, одна из них — то, что мы резервируем в узлах, то есть в страницах, места больше, чем там реально лежит данных. Как правило, узел должен быть заполнен процентов на семьдесят, а остальные тридцать оставлены как бы на будущее. Но прикол в том, что мы храним страницы на диске как есть, поэтому примерно 30% дискового пространства в общей сложности будет пустым. Мы расходуем место практически впустую, хотя могли бы этого не делать.

[04:51] И ещё одна проблема B+-дерева — это то, что изменение одной ячейки внутри страницы… Ну, мы просто одну строчку обновили. Чтобы записать эту страницу на диск, нам нужно записать всю страницу целиком, потому что у нас постраничное хранение: мы храним страницы по 4 килобайта и представляем их в памяти так же. Таким образом, если мы обновляем ячейку размером в несколько байт, записать всё равно нужно 4 килобайта — если хотим, чтобы запись была долговечной. Это тоже одна из проблем B+-дерева.

[05:19] Если посмотреть на B+-дерево с позиции трейд-оффа «чтение — запись», то это, конечно, структура данных, оптимизированная под чтение. Давайте представим, что обращение к диску очень долгое — мы это знаем. IO-операции на диск кратно дольше, чем операции в памяти, поэтому операции в памяти мы не считаем за что-то тяжёлое и говорим сейчас только про обращение к диску. Так вот, когда мы читаем из B+-дерева, нелистовые страницы — те, что идут от root вниз, — скорее всего, будут закэшированы в буферном пуле. Поэтому, чтобы найти нужную страницу, диск мы почти не трогаем. Но потом эту страницу нужно считать.

[05:58] Допустим, мы ищем в B+-дереве значение по ключу 3 и прошли до узла, до страницы, в которой оно лежит (или не лежит — но, допустим, лежит). Чтобы модифицировать это значение, нам нужно сначала считать страницу в память, проапдейтить в ней значение, а потом записать страницу обратно на диск. То есть мы делаем два IO — две операции на одну запись в B+-дереве. При этом на чтение мы просто нашли нужную страницу, прочитали, вернули пользователю; а на запись — нашли, модифицировали, записали. Таким образом, запись, по сути, вдвое дороже чтения.

[06:37] И это в целом нормально, если нагрузка на базу более-менее сбалансированная — какой-нибудь online transaction processing, обычные пользователи, записи, аккаунты, когда данные читают раза в два-три чаще, чем обновляют. Нормальная среднестатистическая нагрузка — нас это устраивает. Но представьте, что нагрузка — это в основном только запись. Вот мы пишем, пишем, пишем.

[07:00] Например, мы занимаемся каким-то трейдингом и постоянно обновляем позиции. Или у нас транзакции, которые пользователи делают карточками: есть база данных transactions, а в ней таблица transactions, и её задача — очень быстро и надёжно писать. Потому что записать транзакцию — самое важное, чтобы зафиксировать, что она произошла, и записать её на диск. А как мы её потом будем считывать — отдельный вопрос: можно реплицировать эту таблицу в другую, более оптимальную для чтения, или использовать под чтение структуру данных вроде B+-дерева. А сама таблица transactions из чего должна состоять, какая структура данных под ней должна лежать, если требование к таблице — быстрая запись?

[07:44] Конечно, у меня есть ответ на этот вопрос, иначе я бы не записывал этот выпуск. Структура данных, которая называется Log-Structured Merge Tree, создана как раз для этого — она оптимизирована под update. Каким образом ей удаётся быть быстрее на запись, чем B+-дереву? Сейчас объясню.

[07:59] Чтобы достичь хороших результатов на записи, нужно ввести ряд ограничений и даже немножко поменять парадигму, поменять мышление о том, как мы представляем себе стандартную структуру данных. Так вот, первый инвариант, первое условие, которое накладывается на все данные внутри LSM-дерева, — это то, что они строго неизменяемы. Иммутабельны.

[08:20] Неизменяемость внутреннего представления данных не означает, что мы как storage, использующий под собой LSM, снаружи не поддерживаем апдейты. Нет, конечно же, поддерживаем: мы можем внести в таблицу transactions апдейт и поменять запись. Но это интерфейс. Снаружи он апдейты поддерживает, а внутренняя реализация никакие записи in place по факту менять не будет. А что она сделает? Просто создастся новая запись, которая говорит, что та прошлая была изменена. Таким образом, сама структура данных — append-only, то есть доступная только для добавления. И изменение данных, и удаление реализованы добавлением новой записи.

[09:01] Если это обновление — мы говорим: вот новая версия записи, тут всё понятно. А если удаление — мы вставляем специальный маркер, tombstone, который говорит, что та запись была удалена. Сам факт неизменяемости позволяет нам реализовать некоторые вещи и, наоборот, о некоторых не думать. Например, можно не думать о блокировках. Почему? Потому что записи больше не могут обновляться in place. Если мы что-то читаем, работаем с какой-то страницей — точнее, с записью, — мы знаем, что она неизменяема. А раз неизменяема, значит, никто параллельно с нами её изменить не может.

[09:38] Соответственно, никаких блокировок: не нужно брать ни write-, ни read-блокировку, потому что нет такого прецедента, что запись может измениться. Если что-то меняется — оно добавляется в конец: где-то появляется новая запись о том, что это поменялось, но в конкурентной среде никаких проблем нет. Это те блокировки, которые на самом деле называются защёлками, latch’ами. Так вот, latch’ей в структуре данных на низком уровне нет, что круто.

[10:01] Также неизменяемость файлов может экономить нам место. Почему? Потому что нам больше не нужно, как в B+-дереве, хранить плюс 30% под будущие записи. Там страница фиксирована по 4 килобайта, и мы либо аллоцируем её, либо нет; а если аллоцируем — хотим, чтобы она была заполнена больше, чем наполовину. А когда всё неизменяемо, нет смысла аллоцировать полупустую страницу — она ведь неизменяемая. Мы просто добавляем записи в конец, причём плюс ещё и в том, что не нужно выравниваться по памяти, не нужно добавлять лишние килобайты ради этой страницы. Потому что мы можем, например, буферизировать апдейты — но об этом чуть позже.

[10:41] Итак, плюшки неизменяемости — это то, что у нас нет latch’ей, нет низкоуровневых блокировок, и мы начинаем экономить место. А минус подхода в том, что все эти аппенды в конец так или иначе требуют чуть большего места и чуть большего набора файлов — файлов становится много. Но это всё внешние наблюдения, очевидные плюсы и минусы. Мы так и не разобрались, как Log-Structured Merge Tree устроена внутри. Сейчас разберёмся.

[11:09] Для начала, ребят, я помимо рисунка с B+-деревом сразу же публикую в Telegram-канале и рисунок LSM. Поэтому заходите в Telegram, канал «Тысяча фичей», — там есть такие приятные плюшки. Вы можете слушать подкаст и одновременно смотреть на картинку, на которую, кстати, я сейчас тоже смотрю. Итак, когда мы говорим про LSM, мы можем говорить про двухкомпонентный LSM и про многокомпонентный. В Telegram-канале у меня нарисован многокомпонентный, но прежде чем про него рассказать, давайте я чуть-чуть коснусь двухкомпонентного.

[11:41] Итак, в чём его суть? Двухкомпонентный LSM, как говорится в его названии, состоит из двух компонентов. Первый компонент — это структура данных, расположенная исключительно в оперативной памяти. В оперативной памяти у нас хранится представление данных: по сути, это просто какое-то красно-чёрное дерево или условно бинарное дерево, которое нормально проявляет себя в памяти. На диске, если мы его начинаем сохранять, оно работает плохо, потому что не оперирует страницами — там просто узлы. А вот в оперативной памяти это ок. Поэтому первый компонент — это дерево в памяти.

[12:18] Из него наши клиенты и читают, и пишут — до тех пор, пока оно не начнёт заполняться или пока не запросят запись, которой в этом дереве нет. Тут нам помогает второй компонент: когда нужно что-то найти, но мы же не можем всю структуру данных хранить в памяти (иначе было бы слишком просто), — часть данных лежит на диске. Как раз за неё отвечает второй компонент, уже дисковая структура данных. Это вполне может быть B-дерево. Просто так как файл у нас неизменяемый и есть глобальный инвариант, что мы не меняемся, мы можем, например, оптимизировать место: B-дерево будет хранить все записи, то есть будет заполнено на сто процентов.

[12:57] Итак, представляем: один компонент в памяти, один на диске. Компонент в памяти — структура данных, оптимизированная под оперативную память, а тот, что на диске, — дисковая. Все записи идут сначала в первый компонент, тот, что в оперативной памяти: любая запись сразу туда залетает, что очень быстро. Чтобы её не потерять, рядом с первым компонентом лежит write-ahead log — или что-то подобное, можно просто называть это log. В этот log добавляются записи о том, что мы записали в такой-то узел такое-то значение по такому-то ключу.

[13:36] То есть это просто журнал — про журнал мы поговорим дальше, в следующем выпуске, когда будем рассматривать, что такое recovery и как оно делается. Но суть в том, что он очень быстро пишет, потому что мы делаем append: указатель, головка на диске — если он магнитный, ну а если не магнитный, просто SSD, — постоянно записывает в конец, добавляет новые страницы, но ничего оттуда не удаляет. Поэтому это очень быстрая запись.

[13:59] И смотрите, как получается. Когда к нам приходит запрос на запись, на update, на upsert, мы сначала пишем в log и одновременно обновляем структуру данных в дереве — и считаем, что запись исполнена. Таким образом, если у нас отключат электричество и дерево в памяти, его конечное представление, конечно же, пропадёт, то потом при восстановлении мы прочитаем этот log и восстановим дерево из него. Оно будет точно таким же, каким было до. Это называется процесс recovery.

[14:27] Так вот, это про структуру данных в памяти. Когда дерево заполняется довольно сильно и в оперативную память больше не влезает, мы начинаем по частям, по веточкам подмёрживать его в дерево, которое лежит на диске. То есть берём одну ветку, подмёрживаем её в дисковое дерево; берём другую, подмёрживаем — и из памяти, соответственно, удаляем. Таким образом структура данных из памяти плавно мигрирует на диск и вливается в дисковую структуру. Вот так работает двухкомпонентное LSM-дерево.

[14:57] Но что более интересно: как пишет автор книги — например, «Database Internals», — ему неизвестны двухкомпонентные LSM-деревья, которые используются в реальных системах. Некоторые системы используют просто merge tree — как бы похожую структуру, — но там нет лога, поэтому про это сейчас говорить не будем. Сразу перейдём на многокомпонентную структуру данных, на многокомпонентный LSM, потому что он используется повсеместно, в огромном количестве баз данных, и он интереснее двухкомпонентного. И как раз он нарисован на картинке, выложенной в Telegram-канале.

[15:34] Итак, слово «многокомпонентный» говорит, что у нас много компонентов. Единственное, что отличает его от двухкомпонентного дерева, — то, что на диске лежит не одно дерево, а много. То есть их много-много на диске. А в памяти всё точно так же — одно дерево: бинарное дерево поиска плюс лог, который лежит на диске и помогает обеспечить долговечность. Это как бы наш компонент номер один. А все остальные компоненты — это просто деревья на диске: какие-нибудь B-деревья или SSTable, это уже зависит от реализации. Главное, что это дисковая структура данных.

[16:06] Первый компонент — это компонент номер один, второй — номер два, а дальше третий, четвёртый и так далее делятся по уровням сверху вниз. И чем дальше уровень, тем больше этот компонент. То есть вначале у нас дерево в памяти, которое мы специальным процессом потом дампим на диск, — оно обладает неким размером «единица». В таком же размере оно дампится на диск в новую таблицу. Отличие этого мердж-процесса от двухкомпонентного в том, что тут таблица целиком записывается на диск: нет поветочного подмёрживания, мы просто берём её целиком и целиком фигачим на диск. Это первый шаг жизненного цикла структуры данных.

[16:46] Второй шаг — это то, что структура данных на диске начинает потом подмёрживаться в другие, более крупные деревья. Сначала было маленькое дерево на диске, один в один как в памяти. Потом оно плавно перетекает — ну, не плавно, а специальным процессом, который называется compaction, — в более крупные деревья на следующем уровне. И так постепенно: по чуть-чуть части этого дерева подмёрживаются в большие, потом в ещё более большие, и в конце у нас лежит одно самое большое мердж-дерево — последний уровень.

[17:21] То есть это такая многоуровневая система, её можно представить как пирамидку: на вершине — деревце в памяти, и потом данные из него плавно перетекают на нижние уровни, вниз пирамидки. Этот процесс перетекания и называется compaction, и делается он в бэкграунде.

[17:38] Смотрите, как выглядит запись, которая очень быстрая. Когда к нам прилетает запрос на запись, мы мгновенно пишем в структуру данных в оперативной памяти (что очень быстро) и быстро дописываем запись в append-only-лог — и говорим: всё, запись произошла. Потом по тому же ключу можем сделать, например, удаление, создав в этом логе новую запись о том, что строчка по этому ключу удалена. И уже потом, в процессе мерджа на диск, это удаление пройдёт по факту.

[18:01] То есть в итоге, в одном из процессов compaction, когда дойдёт до последнего дерева, запись физически удалится. Потому что во время мерджа мы прочитаем этот маркер, так называемый tombstone, увидим, что запись нужно удалить, — и при последнем мердже, при создании с нуля последнего неизменяемого файла, этой записи там просто не окажется. До тех пор, пока мы не дошли до конца, до последнего уровня, удалять её, конечно, нельзя — иначе это может привести к воскрешению записи. Не буду объяснять, как она может воскреснуть: для подкаста довольно сложно. Есть такой нюанс.

[18:39] Жизненный цикл LSM я тоже нарисовал на картинке в Telegram-канале, там всё описано. Жёлтеньким цветом нарисовано то, что находится в оперативной памяти, а сереньким — то, что на диске. Если интересно — откройте, посмотрите; мне кажется, по рисунку довольно понятно. Я сейчас просто проговорю словами. У нас есть структура данных в памяти — мы из неё читаем и в неё пишем, она самая горячая, самая активная. Потом она переходит в статус «сохраняем». Потом сохраняется на диск. После сохранения она начинает подмёрживаться к другим неизменяемым структурам, которые сливаются в новую неизменяемую структуру. Потом это созданное сливается со следующими — и с каждым разом структуры всё больше, больше, больше, пока не дойдёт до самого максимального размера.

[19:25] Я читал пейперы, и там объясняется, почему таблица с каждым разом становится всё больше и больше. Учёные сделали эксперименты, математические выкладки и математически доказали, что если увеличивать размер дерева геометрически, то процесс мерджа будет наименее затратным для диска. То есть такое соотношение размеров таблиц производит наименьшее количество дисковых операций. Доказывать я вам это теоремой не буду; если интересно, могу поделиться ссылкой на статью. Но, в общем, так все и делают: на первых уровнях маленькие деревья, а потом всё больше и больше с геометрической прогрессией, и в конце — одно большое. Вот так по жизненному циклу.

[20:12] Из ещё каких-то интересных вещей, которые поражают — и почему я в начале назвал эту структуру данных взрывающей мозг, — там совсем нет блокировок. Смотрите, как элегантно всё происходит. У нас в памяти есть структура данных, мы в неё фигачим — пишем, читаем, — и нам нужно начать сохранять её на диск. Но мы же не можем просто начать обходить дерево и записывать его на диск: в этот момент в него может прийти запись, модификация, и оно изменится. Налицо гонка.

[20:42] Решается это очень просто: мы делаем новую пустую структуру данных, сохраняем на неё ссылку из корня — по сути, делаем своп, — и все новые записи идут в неё. То есть мы как бы сделали форк. А текущую структуру, которую сохраняем, мы блокируем на запись — запрещаем в неё писать. Таким образом, с момента начала сохранения на диск в неё уже никто не пишет, а все пишут в новое дерево. Для внешнего клиента, для того, кто всё это использует, совершенно ничего не поменялось: он как фигачил запись, так и фигачит. То есть никаких блокировок нет. Это очень хорошее преимущество.

[21:18] Понятно, что запись очень эффективная, быстрая; мы разобрались, как она происходит, по крайней мере на начальных этапах. А что про чтение? Хорошо писать-писать, но мы же пишем, чтобы потом когда-то читать. К тому же в начале я сказал, что читать данные мы всё-таки хотим, и интерфейс, который предоставляет storage, содержит и чтение, и запись. Просто чтение будет немножко подольше. Насколько дольше — хороший вопрос; зависит от того, как часто и сильно мы обновляем одни и те же записи. Но оно будет медленнее, это явно.

[21:51] Почему медленнее? Смотрите: так как мы всё время добавляем новые версии данных, нам нужно прочитать всю цепочку версий, которые сейчас хранятся в структуре для одной записи. Что я имею в виду? Вот нам нужно считать ключ по значению 3. И этот ключ перед этим мы сначала обновляли 230 раз, а потом в конце удалили — и все эти 230 обновлений и удаление произошли, скажем, за минуту. Понятное дело, что за эту минуту запись до самого нижнего дерева, в котором её бы просто не было, дойти не успела. И если бы мы прочитали её просто из этого нижнего дерева, мы бы её там не нашли и сказали, что её нет.

[22:29] А допустим, она сейчас в процессе миграции. В последнем дереве у нас, может быть, её 135-е обновление, 135-е состояние. А маркер об удалении где-то ещё — может, вообще в памяти, где-то на верхних уровнях. Чтобы во всём этом разобраться, нам нужно считать все деревья, в которых этот ключ есть. То есть мы открываем итераторы на каждом дереве — на последнем, предпоследнем, пред-предпоследнем, — если знаем, что там такой ключ может оказаться. Мы их вычитываем и при чтении видим все версии этого ключа.

[23:02] И так как у нас есть маркеры с timestamp, мы понимаем, какая запись последняя, какое актуальное состояние у этого ключа. В нашем случае — удалённое, и мы возвращаем пользователю: ну, сорян, такой записи нет. А если бы удаления в конце не было, вернули бы самое актуальное состояние. То есть мы начинаем платить за быструю запись тем, что во время чтения приходится читать много версий данных и потом их объединять.

[23:30] Смотрите. В B+-дереве или в какой-нибудь древовидной структуре, чтобы считать, достаточно просто пройтись от верхнего узла, от рута, до нижних узлов, выполнить несколько операций сравнения — как правило, до десяти — и получить искомый ключ или сказать, что его нет. Там чтение сильно быстрее, вся задача — найти одну запись. А здесь нам нужно найти не одну запись, а все версии этой записи и потом понять, какая актуальная. Мы начинаем читать медленнее. Конечно, это огромный недостаток этой структуры данных.

[24:02] Но нужно понимать, что дизайн у неё такой, что первоначальная операция, под которую она заточена, — это, естественно, запись. Мы делаем всё, чтобы её оптимизировать, и запись действительно быстрая: мы просто фигачим в лог-файл на дисковой системе запись о том, что что-то произошло, и меняем структуру данных в памяти. Понимаете, это очень быстро. Да, во время чтения приходится платить. Но если это, как я уже говорил, таблица типа транзакций, которых нужно очень-очень много и которые нужно очень много писать, — то это вполне себе хорошее решение.

[24:37] Внутри LSM, внутри этой структуры данных, есть ещё очень много других структур. Например, как я уже говорил, B-дерево — B+ со стопроцентной заполненностью, иммутабельное — вполне может быть реализацией одного такого файла на одном уровне. Также реализацией файла может быть SSTable, что расшифровывается как Sorted String Table: там лежат отсортированные строковые ключи, тоже иммутабельное хранилище.

[25:03] Помимо таких больших структур, как B-дерево, внутри могут использоваться маленькие подструктуры. Чаще всего это какие-то фильтры. Один очень известный такой фильтр — Bloom-фильтр. Про то, как он работает, я, может быть, расскажу в каком-то другом выпуске про интересные структуры данных, потому что это реально интересно. А для чего он используется внутри — расскажу сейчас. Вот у нас много уровней, много так называемых таблиц в терминах LSM, и много файлов. Нам нужно понять: когда мы начинаем открывать итератор и читать нужный ключ из таблицы — а нужно ли нам её вообще открывать? Может быть, там его просто нет, и мы можем легко на это ответить.

[25:44] И Bloom-фильтр — как раз та структура, которая отвечает нам на этот вопрос. Если мы ищем ключ 111, то можем спросить у тысячи таблиц, что у нас лежат: где точно этого ключа нет? И таблицы очень быстро ответят: «у меня такого ключа нет стопроцентно» — и тогда мы их даже читать не будем. Либо ответят: «есть или нет — не знаю, надо смотреть» — и вот тогда мы откроем и посмотрим.

[26:04] Также мы можем делать, например, проверку границ. Таблица может хранить метаинформацию: мол, во мне лежат ключи, минимальный — 3, максимальный — 100. И когда нас просят прочитать ключ 101, мы просто смотрим на эти два значения и понимаем, что в этой таблице физически не может быть такого ключа, — поэтому её тоже не читаем. Это проверка границ. Также там используется интересная структура данных — skip list. Кстати, не знаю, многие ли слушатели представляют, как работает skip list, но это, думаю, тоже оставим на другой выпуск.

[26:36] В общем, сама по себе эта LSM — вот в чём моя идея, что я хочу сказать, — состоит из других структур данных. То есть это уже сложная структура: у неё есть процессы уплотнения, какие-то асинхронные вещи, куча-куча всего используется — прям сложная инженерная штука, особенно если смотреть на современные реализации. Но для подкаста такие сложные вещи объяснять довольно проблематично, я думаю, вы это понимаете. Я не буду углубляться в дебри, в детали. Если интересно, вы сами можете найти материалы или написать в Telegram-канал — я пошарю вам пейперы, расскажу, что почитать, какие книжки, потому что перед глазами всё-таки что-то иметь нужно, когда изучаешь такие сложные штуки.

[27:17] Нам лишь нужно понимать и развивать высокоуровневую техническую эрудицию — чтобы потом, когда мы будем читать описание новой современной базы данных, сразу могли понять, чего от неё ожидать, а чего не ожидать. То есть если база данных говорит, что у неё есть реализация storage engine поверх LSM — например, поверх RocksDB, который внутри себя содержит LSM, — мы сразу понимаем: если мы будем его использовать, то записывать сможем очень-очень эффективно и быстро. Но в то же время чтение будет ограничено, и если у нас профиль нагрузки — чтение, и мы очень много читаем, то выбирать LSM для этого точно не нужно.

[28:02] Помимо таких простых житейских советов, какой-то житейской, инженерной мудрости, я ещё в процессе подготовки к этому подкасту, в процессе изучения материалов и чтения, намайнил для себя, как я говорю, инсайдов. Произошли такие небольшие микроозарения, появились мысли, которых я раньше не думал. Сейчас с вами ими поделюсь. Например, первая мысль — это то, что сама структура данных LSM была придумана где-то тоже в 80-х годах, чуть после B+-дерева, в общем, довольно давно. Но штука в том, что сейчас много баз данных начинают повсеместно использовать LSM в качестве основного хранилища.

[28:43] Вопрос: а почему в Postgres нет LSM, если оно такое хорошее и все его сейчас используют? Это вопрос, который я сам себе задаю, и ответ я для себя нашёл такой (и из книжек тоже прочитал, вроде бы он и является правдой). То, что вот это log-structured, то есть журналированное устройство, — когда журналирование значит, что мы добавляем в конец неизменяемой структуры данных какую-то запись, — оно очень хорошо мэтчится, очень хорошо соотносится с современными дисками.

[29:15] В том самом выпуске, который я делал про диски, я говорил, что они влияют на то, какие структуры данных мы используем, на то, как сейчас работают базы данных, — диски влияют очень сильно. И это была правда. И вот популярность LSM, популярность этого решения, растёт вместе с популярностью SSD-дисков. Почему? Потому что log-structured merge означает, что у нас есть лог, и мы только записываем. А вспоминаем, как работает твердотельный накопитель: он записывает и удаляет блоками, много записывает, а читает страницами.

[29:44] То есть, смотрите: мы не можем записать одну страницу, не можем модифицировать страницу. Чтобы модифицировать страницу, нам нужно очистить блок и записать новый. Работа с очисткой больших данных, с записью новых данных, с иммутабельностью и с невозможностью поменять страницу in place — сделать такой точечный апдейт на месте — это ровно то, как устроен log-structured merge. И это же то, как устроены высокоуровневые твердотельные накопители. И получается, что для таких дисков это естественно: паттерн их использования для них более естественный, чем если бы поверх SSD лежало классическое B+-дерево.

[30:24] Оно работало бы не так эффективно с точки зрения утилизации ресурсов, потому что B+-дерево оперирует страницами, а в SSD мы записываем блоки. А вот эти таблицы, которые располагаются в LSM-дереве, могут собой представлять целые блоки, что очень-очень круто. Поэтому популярность этой структуры данных обязана тому, как работают твердотельные накопители.

[30:48] Помимо того, что идея журналирования используется внутри log-structured merge, она используется также, например, внутри файловой системы. Файловая система тоже не сразу идёт на диск что-то обновлять, не сразу просит драйвер диска или само устройство, — она сначала у себя тоже ведёт некоторый журнал. Помимо этого, сам твердотельный накопитель, сам hardware — точнее, софт, который там работает, — тоже использует журнал. Таким образом, у нас получается журнал, который журналируется в журнал, который журналируется в журнал.

[31:22] Это может быть не сильно эффективно с точки зрения такого инженерного перфекционизма, и поэтому есть некоторые подходы, некоторые API, которые говорят: давайте пропустим эти сквозные журналы и будем использовать напрямую то журналирование, которое устроено менеджером в диске. То есть мы делаем такой линк, такой коннект, который говорит, что верхнеуровневый софт — реализация LSM на C++, например, — когда хочет сделать запись в лог, действительно хочет сделать запись в лог, а не записать какую-то страницу на диск. Поэтому граница вот этого API начинает стираться между диском и структурой данных.

[32:02] Для поклонников чистой архитектуры это, конечно, ужасно, но для реальных инженеров, которые пишут базы данных, пишут storage engine, это огромная оптимизация, про которую забывать не стоит. Подобные вещи — когда мы начинаем совмещать то, как работает hardware, и то, как его использует верхнеуровневый софт, — реализуемы, если мы работаем с дисками, с SSD. Такой подход называется open-channel SSD: он позволяет расширить верхнеуровневый API (условно read-write) и высветить наружу немного своих внутренностей.

[32:38] То, как у него работает стадия compaction, сборки мусора, стирания блоков, программирования и так далее, — все эти абстракции он начинает высвечивать наружу, чтобы те, кто понимает, начали использовать их более эффективно. Но, честно говоря, не все так делают: некоторые просто используют обычные API файловой системы, и в целом это тоже неплохо работает.

[33:00] Итак, сегодня мы познакомились с реальным конкурентом B+-деревьям, разобрались, как устроены LSM-деревья, и теперь с лёгкостью можем ориентироваться в базах данных. Ведь если наш профиль нагрузки — это много чтения, мало записей, то хранилища, построенные на B-деревьях, — это то, что нам нужно. А вот если мы очень много пишем и читаем относительно редко, то, скорее всего, нам лучше подойдут LSM-подобные структуры данных. Надеюсь, этот выпуск был полезен и привнёс частичку новых знаний — ну или освежил и структурировал уже существующие. Не забывайте делиться подкастом с друзьями и коллегами — давайте прокачивать себя и людей вокруг. Ну а на этом всё. Услышимся!