Назовём «хранилкой» такую штуку: некий демон, слушающий порт, принимающий команды SET/GET и т.п., строящий в памяти некую структуру данных, хранящий её также каким-то образом на диске и способный подняться после вырубания питания. Примеры «хранилок»: InnoDB, Redis, PostgreSQL и др.
Примитивная схема работы «хранилки»: есть структура данных в памяти - «дерево» (или что-то ещё: хештаблица, список, массив и т.п.) и есть журнал. Журнал - бесконечно растущий файл. Все пишущие операции сначала пишем в журнал, потом исполняем на «дереве». В случае падения, просто исполняем весь журнал с начала до конца и получаем в памяти «дерево» на момент падения. Или не критично отличающуюся (например декартово дерево, где есть рандомчик). Минус: журнал только растёт и на высоконагруженной системе через 2 года журнал будет читаться и исполняться целых две недели при поднятии после падения.
Схема получше: кроме журнала есть «дамп» - файл, новая версия которого каждые сутки пишется на диск, а внутри наше сериализованное «дерево» + позиция в журнале на момент записи «дампа». При поднятии нужно только построить «дерево» по дампу и дальше «догнаться» по журналу до его конца, начиная с позиции, являвшейся концом журнала на момент записи «дампа».
Второй принцип используется много где.
Когда в память всё не влезало и умные люди занимались вопросами поиска во внешней памяти, то придумали и полюбили B+-Tree за то, что основание логарифма в оценке средней стоимости доступа к ключу у такого дерева конское со всеми вытекающими - т.е. примерно 2-3 рандомных доступа к диску на поиск любого ключа в базе примерно любого адового объёма. Да и вообще конское основание логарифма - хорошо, когда операция обращения вычислителя к своей памяти передаёт не байты, а блоки байтов, что верно уже чуть более чем для всего, где память иерархична: проц, кеш L1, L2, L3, оператива, диск — в этой иерархии размер блока растёт с удалением по иерархии от вычислителя. Чем дальше надо идти, тем выгоднее взять сразу много. А раз приехало много, то лучше чтобы всё приехавшее было полезно: вот так и родилось B+-Tree. Чем плох бинарный поиск в mmap-леном файле? Тем, что операции все в блоках (секторах диска по 4096), а из блока нужен только один ключ для принятия решения о том, вправо шагать или влево. То есть из всего приехавшего нам блока размером 4096 мы используем процента 2, остальное в помойку. Для сокращения пространства поиска всего в 2 раза мы гоняем целый блок с кучей ключей. Пропускная способность линии обмена с внешней памяти тратится бездарно. В B+-Tree всё не так - каждый приехавший блок полезен на 100% и сокращает пространство поиска сразу в B раз, где B - fanout дерева, который конечно может быть переменный из-за разницы в длинах ключей, но уже неважно, профит и так громадный.
Хотя конечно у самых умных чуваков на диск пишется и читается минимум мегабайт по 64, чтобы оправдать цену seek головы (что для ssd тоже имеет цену) - поэтому размер SSTable в гугловом BigTable примерно такой. Короче это тема LSM структур, но вопрос про B+-Tree.
Изначальный вопрос про хранилки на B+-Tree. Во внешней памяти лежит куча блоков B+-Tree и обмен с внешней памятью идёт поблочно. Иногда мы меняем блоки, тогда в памяти повисают «грязные» блоки, которые надо потом скинуть обратно в файл. Понятно, что попутно мы всё пишем в точно такой же журнал, как описано в начале. Вот тут наступает хрень - нельзя просто так взять и записать все блоки на те места, где они были. Мы же умные чуваки и не хотим гонять с диска мелочь, поэтому наши блоки больше размера сектора - ну например 16 кб или даже 4 мб. Посередине записи такого блока может пропасть питалово и тогда у нас не останется даже предыдущей копии такого блока, ведь мы записывали сразу поверх старого. Накатить из журнала мы тоже ничего не можем - там нет целых блоков, а только отдельные операции SET. Эти операции SET поднимали блок с диска, меняли и делали «грязным». Но с диска мы уже ничего не поднимем, там на месте блока уже мусор.
Поэтому умные чуваки из InnoDB догадались сделать double write buffer. Типа, все блоки, которые надо записать, сначала запишем в специальное место файла, потом вызовем fsync(), а потом уже начнём их записывать поверх старых версий тех же блоков. Тогда всё ништяк - питалово может пропадать в любом месте: мы либо в double write buffer их ещё не дописали и тогда «оригинальные» невредимы, либо если зафакапили оригинальные у нас есть «микрожурнал» в виде double write buffer откуда мы можем блоки поднять.
Чуваки в Postgres сделали по-моему чуть проще и в чём-то надёжнее (из-за простоты) - пишут блок целиком в ЖУРНАЛ, а потом уже на место назначения. Там у них есть такое понятие как checkpoint process - это такой длительный размазанный по времени процесс, чтобы не мешать обычной работе СУБД, чтобы не юзать диск сразу в полку, а скинуть все грязные страницы помедленнее. Он выглядит примерно так:
1. Атомарно собрать список всех грязных блоков в памяти, которые хотим синхронизировать - просто массив их ID. Ну, или указателей, чё там в реализации творится не знаю.
2. Новые грязные после взятия этого списка могут плодиться как хотят, но в данный checkpoint process они не попадают.
3. Записать в журнал метку «checkpoint» (эта метка называется checkpoint, а есть ещё в англоязычной литературе «checkpointing process» - это сам процесс вот этого всего).
4. Читать начиная с этой метки мы можем только при условии, что checkpoint process дойдёт до конца без падения.
5. Лениво начать такое: любой блок из множества выбранных пишется в журнал, потом в своё законное место. Если вдруг в ходе этого процесса на блок прилетает меняющая его команда, а в журнал этот блок ещё не попал, то прилетевшая отдельная команда в журнал не пишется, а сразу накатывается на уже грязный блок и уже блок целиком пишется в журнал. Далее блок становится «полугрязный» и все меняющие операции с этим блоком пишутся в журнал как обычно, отдельными мелкими записями, а не в виде новых изменённых версий блока - блок у журнал после начала данного checkpoint process достаточно записать только 1 раз. Короче надо записать все выбранные в начале блоки в журнал и максимум 1 раз, но меняющие эти блоки входящие команды не должны оказаться в журнале ДО самого этого блока.
5. После записи блока в журнал можно перезаписывать его в «дампе» (он же «файл таблицы»). Короче, журнал тут послужил double write buffer - от этого деться нельзя, если только не специальная аппаратура - куда-то надо записать блок до того, как перезаписывать его старую версию новой. Тут два варианта - сначала записать все выбранные в журнал, а потом начать их писать в файл таблицы, либо можно по одному «в журнал и сразу в файл таблицы». Тут вопрос в обработке ситуации падения прямо в этот момент: если выбрать второй способ, то мы будем видеть в файле таблицы блоки свежее, чем им следовало бы быть согласно той позиции журнала, с которой мы начнём читать журнал после падения — а нечнём мы читать журнал не с нашей новой только что записанной метки «checkpoint», а с предыдущей у которой «checkpointing process» дошёл до конца. А на момент той метки наши блоки были более древними, чем оказались перезаписанными в ходе нового «checkpointing process». Короче, кажется эта ситуация теоретически может быть обработана: нужно будет уметь для таких чрезмерно новых блоков пропускать все команды в журнале более старые, чем сам блок. Для простоты можно думать, что сделано первым способом - «сначала все блоки скинуть в журнал, потом начать скидывать в файл таблицы».
6. Предположим, процесс сдох тут где-то посередине. Просто читаем журнал с прошлого «checkpoint», встречаем постепенно нашу новую метку «checkpoint» и доводим этот новый checkpoint process до конца, дописывае блоки которые ещё не дописались куда нужно - мы их спокойно поднимем из файла таблицы: там спокойно лежат старые блоки, которые не начали перезаписываться новыми версиями, ведь эти новые версии ещё не дозаписались в журнал. Ну или дозаписались и начали перезаписываться в файле таблицы, тогда можно просто сравнивать байтики блоков - если в файле таблицы блок лежит не такой, как записался в журнал, значит тупо перезаписать его тем, что записался в журнал. Ну CRC32 ещё или MD5 там везде понакрутить конечно.
Фактически у нас тут тот же double write buffer, только им служит журнал. Чем мне такое нравится - журнал можно тупо зареплицировать на бесконечное число других хостов и поднять там реплики. Я PostgreSQL не админил, возможно там такое почему-то сделать нельзя, но точно не по идеологическим причинам, а из-за каких-то тактических архитектурных фекапов. А вот в случае MySQL там какая-то жесть: нельзя просто так взять и зареплицировать некий журнал, он там какой-то непростой. Это всё холивар и содомия, я вообще не шарю.
Вот хочется почитать как именно устроена работа по синхронизации блоков B+-Tree с диском в MySQL.
Про Postgres я тут изложил упрощённо, реально есть нюансы, но общая идея в том, что давайте просто запишем блок в журнал целиком и это будет нашим двойным буфером. Заодно такой журнал просто зареплицировать как поток команд и это PROFIT.
В случае с MySQL есть загадки. Во-первых меня смутило упоминание в литературе того, что их этот double write buffer ограничен (естественно, под него же выделено место в файле таблицы) где-то 128 блоками (настраивается). А что если грязных блоков больше? Или они делают checkpoint когда грязных блоков НЕ БОЛЕЕ 128 всегда? Но вроде нет, что-то читал про умение делать это группами блоков.
Как-бэ загадка вот в чём: например журнал начался на позиции 500. Мы с него поднялись. У нас народилось 200 грязных блоков. Мы херак записали 128 из них сначала в DWB, потом в файл таблицы. Всё чинно и благородно, никакие байтики не помялись. Тут херак упали.
Поднимаемся с позиции журнала 500. Начинаем накатывать какие-то команды. Команды требуют поднятия с диска блоков и их изменения. Мы идём в файл таблицы, а там херак 128 из этих блоков новее чем другие. Возможно это обрабатывается так же, как я предположил для postgres - на блоке просто стоит число, мол «я актуален для позиции журнала 700», поэтому мы херак и пропускаем все команды для него до позиции 700. Возможно это бред и всё не так.
Плюс там есть ещё какой-то fuzzy checkpointing.
