Flat DB — чтение состояния за один прыжок

Чтобы прочитать один баланс, нужно пройти весь trie

Очевидный способ хранить trie: каждый узел — в таблице «ключ-значение», где ключ — его хеш. Чтобы прочитать баланс Алисы, вы начинаете с stateRoot, получаете этот узел, находите хеш дочернего узла по первому ниблу её ключа, запрашиваете его — и так далее: 4–6 отдельных запросов, каждый из которых может обернуться чтением с диска, лишь чтобы добраться до одного листа. А поскольку ключи — это хеши, соседние аккаунты разбросаны случайно по всему диску: нет никакой локальности, которую можно было бы использовать. К тому же узлы trie громоздки — ветвь хранит шестнадцать дочерних хешей — и вы перекачиваете в десятки раз больше байт, чем само значение.

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

→ Шаг 2: ключевать узлы по месту в дереве, а не по хешу.

Ключевать узлы по пути, чтобы соседи лежали рядом

Это был предыдущий дизайн Nethermind — HalfPath, чистый полушаг к Flat DB. Trie остаётся прежним, но меняется ключ каждого узла в базе данных: вместо хеша в начало ключа добавляется путь в trie до этого узла. Теперь ключ узла кодирует его положение в дереве, и RocksDB — хранящий записи, отсортированные по ключу — физически размещает родителя и ребёнка рядом. Обход пути превращается из россыпи случайных seek’ов в короткое последовательное сканирование.

Одно это изменение раскладки даёт большой выигрыш: обработка блоков примерно на 40–50% быстрее, а база данных примерно на 25% меньше, поскольку данные, упорядоченные по пути, гораздо лучше сжимаются (в одном 12-дневном тесте несжатая БД выросла на 1,28% вместо обычных 14,62%). «Half» в названии — честная оговорка: это гибрид, он реорганизует ключи, но сохраняет всю остальную машинерию trie — промежуточный вариант между старым хеш-хранилищем и чисто путь-ориентированным.

→ Шаг 3: читать значение напрямую, вынести trie с горячего пути.

Хранить значения плоско; держать trie только для корня

Вот в чём идея. Разделим две задачи, которые решал trie. Доказательство состояния — пересчёт stateRoot — действительно требует дерева. Чтение значения — нет. Поэтому заведём отдельную плоскую колонку address → account и ещё одну (address, slot) → value, и будем отвечать на каждое чтение из них одним прямым запросом. Trie по-прежнему поддерживается, но в стороне: к нему обращаются только тогда, когда нужно пересчитать корень в конце блока. Это и есть Flat DB: данные аккаунтов, данные хранилища и узлы trie разложены по отдельным колонкам RocksDB, а плоские колонки — не trie — служат основным путём чтения.

Чтение сокращается с 4–6 зависимых запросов до одного. По тестам Nethermind это даёт примерно на 20% более высокую пропускную способность выполнения по сравнению с HalfPath, и около 40% на блоках с большим объёмом чтения, где доступ к состоянию доминирует. Данных перекачивается меньше: плоская запись аккаунта намного компактнее, чем узлы trie, через которые пришлось бы пройти.

→ Шаг 4: дать плоскому хранилищу память.

Главное: слой — это дифф, а не копия

Здесь все обычно спотыкаются, поэтому зафиксируем это до всего остального. Слой — это не полная Flat DB для данного блока. Это дифф — только те несколько аккаунтов и слотов хранилища, которые изменил именно этот блок, сопоставленные с новыми значениями. В самом низу лежит базовая Flat DB — полное состояние на какой-то более ранний момент; каждый слой выше — тонкая заплата. Чтобы прочитать ключ, проверяем самый свежий слой, затем следующий, падаем вниз до первого совпадения — побеждает первое (наиболее свежее) значение — и если ни один слой не упоминает ключ, читаем из полной базы.

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

Слияние двух слоёв = оставить новейшее значение для каждого ключа

Объединить дифф блока 5 с диффом блока 6 — ровно то, что кажется интуитивным: берём объединение их ключей, и там, где оба изменили один ключ, оставляем новое значение и отбрасываем старое. Это ответ на вопрос почему становится меньше — ключ, перезаписанный внутри диапазона, сворачивается с нескольких записей до одной. Горячие ключи (хранилище активного контракта, баланс биржи) меняются почти каждый блок, поэтому перекрытий — и экономии — много.

И это также отвечает на вопрос «как отличить скомпакченные блоки внутри слоя» — никак, и это не нужно. Слой «блоки 5–8» хранит для каждого ключа только итоговое значение на блоке 8; промежуточное значение блока 6 утеряно навсегда. Вместе с этим теряется возможность прочитать состояние внутри диапазона. Это безопасно по одной точной причине: однобло­чные слои хранятся только для недавних, ещё не финализированных блоков — тех, которые возможно придётся откатить. Более старые блоки устоялись, так что никто никогда не попросит состояние «на блоке 6» конкретно, и потеря промежуточных значений ничего вам не стоит.

Какие цепочки сливать: степени двойки

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

Точное правило: «охват нового слитого слоя — наибольшая степень двойки, делящая номер блока». Развернём по шагам — появляется закономерность: блоки 1 и 2 сливаются в двухслойный; блок 3 ждёт, пока блок 4 не соберёт всё в четырёхслойный; и так далее. Набор хранимых слоёв — это в точности двоичные разряды текущего номера блока. После блока 13 — двоичное 1101 — хранятся восьмислойный, четырёхслойный и однослойный: всего три слоя, покрывающих тринадцать блоков.

→ Шаг 5: найти чтение, о котором забыли.

Вы всё равно трогаете trie — при коммите

Плоские чтения быстрые, но блок — это не только чтения. В конце каждого блока клиент обязан пересчитать новый stateRoot, а это по-прежнему означает чтение и перехеширование узлов trie вдоль каждого изменённого пути. Ашраф говорит об этом прямо: «Без этих оптимизаций Flat DB ненамного быстрее HalfPath». Плоский путь чтения устранил одно узкое место и обнажил следующее.

Исправление — две части плумбинга вокруг доступа к trie при коммите. TrieNodeCache — сегментированная хеш-таблица, индексированная по пути и хешу — держит горячие узлы trie в памяти. А TrieNodeWarmer предварительно выгружает узлы trie, которые вот-вот понадобятся блоку, чтобы они уже были в памяти к моменту вычисления корня, скрывая задержку диска. Только с ними на месте выигрыш от плоского чтения реально проявляется сквозным образом.