LINUX.ORG.RU

InnoDB - как физически сохраняет блоки B+-Tree на диск?

 


0

1

Назовём «хранилкой» такую штуку: некий демон, слушающий порт, принимающий команды 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.

Double Write Buffer вообще не предназначен для решения вопросов принятия-отката транзакций - это делают так называемые Undo space и Rollback segments. Double Write Buffer нужен лишь для устранения повреждений страницы файла базы после проишествия, и то он нужен только если сама файловая система такого не умеет. Дело в том, что мускулю для автоматического восстановления базы нужны целостные страницы, не важно с новыми или старыми данными в них. Вот здесь показан пример отката большого числа транзакций, я приведу отрывок:
https://dev.mysql.com/doc/refman/5.5/en/innodb-recovery.html
«InnoDB: Restoring possible half-written data pages from the doublewrite
InnoDB: buffer...
InnoDB: Doing recovery: scanned up to log sequence number 457028695
InnoDB: 1 transaction(s) which must be rolled back or cleaned up
InnoDB: in total 990682 row operations to undo
...»
Как видишь, 990682 операций отменяется.

Чем мне такое нравится - журнал можно тупо зареплицировать на бесконечное число других хостов и поднять там реплики. Я PostgreSQL не админил, возможно там такое почему-то сделать нельзя, но точно не по идеологическим причинам, а из-за каких-то тактических архитектурных фекапов. А вот в случае MySQL там какая-то жесть: нельзя просто так взять и зареплицировать некий журнал, он там какой-то непростой.

Это проблема, от которой MySQL будет харкать до самой смерти - репликацию в нем сделали быстро и плохо, на единственном логическом уровне, независимом от движка. Теперь уже не скажешь «мы пошутили, давайте переделаем всю архитектуру заново». Журнал просто так реплицировать не получится, хотя бы потому, что их теперь несколько.

byko3y ()