Хранилище ячеек

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

Ячейка — мелкое значение (медианный размер около 128–191 байт) с произвольным доступом по хешу и постоянно меняющимся счётчиком ссылок. Это прямая противоположность тому, что хранят тела блоков и архивы: крупные неизменяемые блобы, для которых узел использует Cassadilia, чьё устройство описано в отдельной статье. Для ячеек выбор другой: они лежат в обычной LSM-базе RocksDB, в отдельном инстансе под названием база ячеек.

База ячеек

База ячеек (weedb-обёртка над RocksDB) — отдельный инстанс, который узел открывает в собственном подкаталоге каталога хранилища: рядом с базой core, где живут дескрипторы, связи и индексы блоков, но независимо от неё. Настройки инстанса рассчитаны на нагрузку «много мелких значений, один писатель»: чтения и запись идут в обход page cache, потому что узел держит собственный кэш ячеек и не хочет второго кэширования на уровне ОС. К этому узел добавляет несколько параллельных фоновых потоков компакции и авто-подстраиваемый ограничитель скорости записи.

База ячеек делится на четыре колонки:

Устройство temp_cells и то, как в него попадают данные, — тема отдельной статьи о потоковой загрузке сырого состояния. Здесь эта колонка упомянута только как часть состава базы.

Корень сохранённого состояния

Само дерево ячеек в состоянии не хранится единой записью: там лежит только точка входа в него. Каждое сохранённое состояние шарда фиксируется одной строкой колонки shard_states, где ключом служит идентификатор блока, 80 байт (рабочая цепочка, префикс шарда, seqno, root hash и file hash), а значением — 32-байтовый хеш корневой ячейки состояния.

Запись корня попадает в тот же пакет RocksDB, что и новые строки ячеек этого состояния: сначала в пакет добавляются ячейки, затем запись корня, и весь пакет пишется одним вызовом. Поэтому состояние либо сохранено целиком, либо не сохранено вовсе: расщепить эти две части невозможно. Сборка мусора состояний идёт обратным путём и удаляет запись корня тем же пакетом, которым удаляет ячейки. Устройство самой сборки мусора здесь не раскрывается — она описана в отдельной статье.

Та же таблица заодно служит и индексом «seqno мастер-блока → идентификатор блока», потому что идентификаторы в её ключе отсортированы по рабочей цепочке, префиксу шарда и seqno.

Строка ячейки

Строка колонки cells устроена просто: ключом служит repr-хеш ячейки, те же 32 байта, а значением — восьмибайтовый префикс idx, за которым следуют сами байты ячейки в её собственной сериализованной форме.

idx — не порядковый номер ячейки в дереве, а её идентификатор в структуре счётчиков ссылок, о которой пойдёт речь ниже. Сам счётчик ссылок в строке не хранится вовсе, а repr-хеш в значении не дублируется, потому что он и так является ключом строки.

Ячейка хранилища в памяти

Хранилище ячеек отдаёт наружу не сырые байты, а ячейку хранилища (StorageCell) — представление ячейки в памяти узла поверх строки базы ячеек: она держит дескриптор ячейки, её данные и хеши уровней сразу, а детей материализует лениво, по требованию.

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

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

Хранилище ячеек как точка входа

CellStorage — единственная точка, через которую узел работает с ячейками. Основные методы:

Асимметрия первых двух методов намеренная: store_cell_mt получает пакет снаружи, потому что вызывающий сам добавляет в него запись корня состояния, а remove_cell_mt создаёт пакет сам, и вызывающему остаётся лишь дописать в него удаление корня.

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

Загрузка ячейки

load_cell ищет ячейку в четыре шага по порядку: кэш материализованных ячеек, зона молодых ячеек, кэш сырых байтов, колонка cells. Если ячейка не нашлась ни на одном шаге, метод возвращает ошибку «ячейка не найдена».

Кэш материализованных ячеек хранит отображение «хеш → (эпоха, слабая ссылка)», и попадание засчитывается только тогда, когда запись не устарела и слабую ссылку ещё можно поднять до сильной. Эпоха — это seqno мастер-блока, которым покрыто загружаемое состояние, а параметр drop_interval задаёт, насколько старую материализацию ещё можно переиспользовать (см. таблицу конфигурации). Сборка мусора состояний намеренно грузит корень удаляемого состояния с нулевой эпохой, чтобы его ячейки не попали в переиспользование более свежими загрузками.

Счётчик ссылок

Дедупликация ячеек держится на счётчике ссылок: одна и та же ячейка, встретившаяся в нескольких состояниях, хранится один раз, а переиспользование учитывается счётчиком. Сам счётчик, однако, не лежит в строке RocksDB: там остаётся только индекс ячейки (см. выше). Отдельная структура в оперативной памяти узла хранит отображение «индекс ячейки → счётчик ссылок»: выделение нового индекса, чтение значения и пакетное применение изменений идут в ней целиком в памяти, без обращения к диску. Значения индекса выдаются монотонно и никогда не переиспользуются.

Раз счётчики живут в памяти, их нужно фиксировать на диске отдельно от строк ячеек, и при сохранении и удалении состояния (store_cell_mt, remove_cell_mt) хранилище делает это на каждой такой транзакции: вся структура счётчиков целиком сериализуется и кладётся снапшотом счётчиков в тот же пакет RocksDB, что и изменения строк колонки cells. Инкрементальной записи счётчиков нет — только полный снапшот на транзакцию. Из-за этого именно в store_cell_mt и remove_cell_mt счётчики и строки ячеек фиксируются на диске атомарно: узел не может оказаться в состоянии, где строки ячеек уже записаны, а счётчики ещё описывают предыдущий момент. Это не свойство любой записи в базу ячеек: apply_temp_cell и миграция версий пишут строки промежуточными батчами, а снапшот пишется отдельным финальным батчем, а prepare_persistent_state_save пишет строки колонки cells вообще без снапшота счётчиков.

Зона молодых ячеек

Не всякая новая ячейка стоит того, чтобы сразу писать её в RocksDB: многие ячейки живут всего несколько блоков и тут же удаляются вслед за состоянием, в которое входили. Чтобы не платить записью в LSM за такие ячейки, хранилище сначала кладёт новую ячейку не в колонку cells, а в оперативную буферную зону молодых ячеек со своим журналом (устройство журнала — в следующем разделе). Ячейка попадает туда с раундом рождения: номером раунда, в качестве которого используется seqno мастер-блока, покрывающего сохраняемое состояние.

Ячейка переезжает в базу ячеек, только когда её раунд рождения отстал от текущего раунда не меньше чем на 100 раундов: это и называется промоушеном. Если счётчик ссылок ячейки обнулился раньше, чем она дожила до промоушена, ячейка удаляется прямо из зоны и в RocksDB не попадает вовсе. Отдельного фонового процесса промоушена нет: промоушен выполняется внутри той же транзакции, что сохраняет очередное состояние. При её завершении из зоны изымаются все ячейки, чей раунд рождения достаточно устарел, и переносятся в тот же пакет, которым фиксируется само сохранение. Чтобы промоутированные ячейки не задублировались следующим же сохранением, их хеши сразу добавляются в фильтр сохранённых ячеек — раньше, чем пакет пишется в RocksDB. Пока узел не сохраняет новых состояний, зона молодых ячеек поэтому не разгружается: раунд, по которому считается возраст ячейки, двигается только вместе с новыми блоками.

Ячейки зоны видны на чтение наравне с уже записанными: загрузка ячейки заглядывает в зону молодых ячеек раньше, чем в саму базу (см. выше), а сохранение нового состояния при поиске уже существующей ячейки тоже сначала проверяет зону. Механизм рассчитан на то, что устаревшие состояния будут вычищаться быстрее, чем растёт зона: сборка мусора состояний по умолчанию устроена соответствующим образом, а как именно — предмет отдельной статьи о самой сборке мусора.

Долговечность зоны молодых ячеек

Зона живёт в оперативной памяти, поэтому сама по себе не переживает перезапуск узла. Собственный журнал даёт ей долговечность: каждое изменение зоны сначала дописывается в файл журнала, и только потом пакет RocksDB с этим же изменением фиксируется в базе. Номер только что дописанной записи журнала публикуется тем же пакетом, что и остальные изменения транзакции. Журнал ведётся простой дозаписью, без принудительной синхронизации с диском: протокол переживает падение процесса, но не рассчитан на произвольную потерю питания.

Журнал не растёт бесконечно: как только его размер превышает пороговое значение (см. таблицу конфигурации), узел пишет файл чекпоинта (полный снимок всего содержимого зоны на этот момент) и обнуляет журнал. Публикация чекпоинта атомарна: файл сначала записывается во временное имя, а затем переименовывается, и лишь после этого в базе фиксируются его номер и хеш. Чекпоинт проверяется после каждой успешной записи пакета, будь то сохранение состояния или его удаление сборкой мусора.

При старте узел восстанавливает зону. Сначала применяется файл последнего чекпоинта, если он есть, а затем поверх него переигрываются записи журнала, ещё не попавшие в чекпоинт. Всё, что в журнале лежит дальше последней зафиксированной записи, отбрасывается как хвост незавершённой транзакции. Незавершённое переигрывание до нужной границы — фатальная ошибка открытия хранилища: она означает, что журнал повреждён сильнее, чем рассчитан протокол.

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

Удаление ячейки

Ячейка физически удаляется, только когда её счётчик ссылок доходит до нуля: обход вглубь по детям не идёт, пока у ячейки остаются другие владельцы, а спускается в поддерево лишь тогда, когда снимаемая ссылка была последней. Способ удаления зависит от того, где ячейка на момент удаления лежала: запись зоны молодых ячеек просто убирается из зоны и в RocksDB так никогда и не попадает, а строка базы ячеек удаляется из колонки cells вместе с записью в кэше сырых байтов и в фильтре сохранённых ячеек. Если после снятия ссылки счётчик остаётся равным единице, строка остаётся на месте — только исчезает отдельная запись об этой ячейке в структуре счётчиков ссылок.

Конфигурация