Обновление состояния шарда

Хранилище ячеек хранит дедуплицированные ячейки, из которых складываются деревья многих сохранённых состояний, и умеет отдать нужное дерево по root hash. Но само по себе оно не решает, каким должно быть следующее состояние. Меркл-обновление — часть каждого блока, которая описывает переход от состояния предыдущего блока к состоянию текущего. Именно оно несёт эту связь между состояниями соседних блоков.

Меркл-обновление

Меркл-обновление блока (old_hash, new_hash, old_depth, new_depth, old, new) несёт в поле new частично обрезанное дерево нового состояния: в нём есть все изменившиеся ячейки, а неизменившиеся поддеревья заменены обрезанными ветвями с хешами оригиналов. Поле old в тракте хранения состояний не используется — хранилищу нужно только new.

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

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

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

Прямое и виртуальное сохранение

Не каждое состояние шарда попадает в базу ячеек. Для мастерчейна прямым сохраняется каждое состояние, для рабочей цепочки — лишь одно из заданного числа подряд идущих (шаг конфигурируется, см. таблицу конфигурации), а промежуточные состояния остаются виртуальными: узел строит их в памяти и хранит про них в дескрипторе блока только флаг, что состояние вычислимо. Так узел не платит записью в RocksDB за состояние, которое почти всегда тут же уступит место следующему.

Сохранение делается прямым, если верно хотя бы одно из трёх условий:

• seqno блока кратен шагу прямых сохранений;
• число новых ячеек шарда, накопленное с прошлого прямого сохранения, достигло порога (значение конфигурируется, см. таблицу конфигурации);
• вызывающий явно пометил блок как верхний блок шарда — тогда сохранение прямое принудительно, вне зависимости от двух других условий.

Накопитель новых ячеек живёт при кэше состояний шарда и обнуляется при каждом прямом сохранении.

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

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

Виртуальное состояние

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

Полученное состояние остаётся только в памяти, в кэше состояний шарда. Флаг HAS_VIRTUAL_STATE означает не «состояние можно прочитать из базы», а «для этого блока известно меркл-обновление, и состояние вычислимо». Загрузка такого состояния при обращении извне — это как раз поиск ближайшего опорного состояния и применение к нему цепочки обновлений, о чём дальше.

Прямое состояние

Прямое сохранение устроено сложнее виртуального: помимо построения состояния в памяти оно ещё и фиксирует его на диске одним батчем RocksDB.

1. Вычисляется root hash. Если состояние уже пришло готовым от коллатора, это хеш его корня как есть, и предыдущее состояние в этом случае даже не нужно. Если нет, root hash берётся из ещё не применённого, частично обрезанного дерева меркл-обновления — то есть вычисляется до применения обновления.
2. Перед дорогой работой узел на всякий случай перепроверяет, не появился ли уже флаг наличия прямого состояния у этого блока. Первая из трёх таких проверок стоит сразу после вычисления root hash, ещё до применения обновления. Вторая стоит там, где корень уже получен: для случая с меркл-обновлением это происходит после того, как оно применено и дерево пересобрано, а для уже готового состояния, где применять нечего, вторая проверка идёт сразу следом за первой. Третья проверка выполняется ещё раз позже, после того как взята блокировка на следующем шаге. Если хотя бы одна из этих проверок обнаружит флаг, дальнейшая работа обрывается, и состояние просто перечитывается из хранилища.
3. Берётся общая для всего хранилища состояний блокировка — та же, что использует сборка мусора состояний, потоковая загрузка сырого состояния (см. ниже) и сохранение устойчивого состояния: пока идёт прямое сохранение, они ждут.
4. Заводится пакет записи RocksDB с преаллокацией под оценённое число новых ячеек.
5. Для шардового блока считаются точки разбиения аккаунтов (следующий раздел), а для мастерчейна их нет.
6. Дерево ячеек нового состояния обходится и записывается в пакет хранилищем ячеек — с тем же раундом, которым помечаются новые ячейки: seqno мастер-блока, покрывающего сохраняемый блок.
7. В тот же пакет добавляется запись корня в таблицу сохранённых состояний.
8. Пакет пишется в базу ячеек одним вызовом. Сбой этой записи фатален: узел падает.
9. В дескрипторе блока выставляется флаг HAS_STATE.
10. Если журнал зоны молодых ячеек к этому моменту перерос порог, пишется его чекпоинт.
11. Дерево только что сохранённого состояния и связанный с предыдущим состоянием счётчик-держатель референсного мастер-состояния отправляются в фоновую очередь освобождения памяти вместо немедленного уничтожения, и лишь после этого блокировка с шага 3 отпускается.
12. Наконец, состояние перечитывается из хранилища заново: в кэш состояний шарда должно попасть дерево, собранное из ячеек хранилища, а не то, что построил применитель меркл-обновлений в памяти. Вместе с ним заводится новый применитель меркл-обновлений, привязанный к только что сохранённому состоянию как к опорному: от него будет отталкиваться цепочка следующих виртуальных состояний.

Разбиение аккаунтов

Среди ссылок корня состояния шарда — processed_upto (ссылка №0) и словарь аккаунтов, accounts (ссылка №1). Обходить и записывать корень состояния одним потоком на шестом шаге прямого сохранения расточительно, когда состояние большое, поэтому перед прямым сохранением шардового блока узел выполняет разбиение аккаунтов: разбивает этот словарь по первым нескольким битам адреса аккаунта на поддеревья. Глубина разбиения в битах адреса конфигурируется (см. таблицу конфигурации) и определяет корни, по которым обход дерева в хранилище ячеек расходится на параллельные задачи. Для мастерчейна разбиения нет вовсе: его состояние обходится одним потоком.

Сборка мусора состояний при удалении устаревшего состояния тоже заново считает тот же набор точек разбиения. Устройство самой сборки мусора здесь не раскрывается — ей будет посвящена отдельная статья.

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

Загрузка состояния

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

На каждом шаге назад узел сначала проверяет кэш состояний шарда:

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

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

Собранная цепочка обновлений применяется по порядку от опорного состояния к целевому — одним и тем же применителем меркл-обновлений, тем же способом, что описан в разделе про меркл-обновление.

Потоковая загрузка сырого состояния

Кроме двух способов получить следующее состояние от блока к блоку, у хранилища есть отдельный тракт для случая, когда узлу передают уже готовое, сериализованное целиком сырое состояние: так узел при холодном старте принимает и нулевые состояния, и скачанное устойчивое состояние. В отличие от прямого и виртуального сохранения, здесь нет ни предыдущего состояния, ни меркл-обновления — на вход приходят идентификатор блока, файл или байты в формате BOC и ожидаемый root hash.

Такое состояние узел не разбирает в дерево в памяти целиком, а обрабатывает в два прохода через временный файл. Так он может принять состояние произвольного размера при ограниченной памяти. Первый проход читает BOC потоково и переписывает ячейки одну за другой во временный файл. Через каждые 10 000 ячеек он добавляет суммарный размер чанка. По этим отметкам второй проход будет читать файл с конца.

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

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

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

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

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