Цена дешёвой записи: как RocksDB выполняет чтение?

Как RocksDB читает ключ?

Чтение в RocksDB идёт от самых новых данных к самым старым и останавливается на первой найденной версии ключа. Вот и всё; остальные механизмы лишь ускоряют этот процесс.

Порядок поиска фиксирован и повторяет путь записи из предыдущей статьи в обратном направлении: активная memtable, неизменяемые memtable, SST-файлы на уровне 0, а затем отсортированные SST-файлы от уровня 1 и ниже.

Сначала RocksDB проверяет активную memtable, поскольку она содержит самые свежие записи, находится в памяти и использует skiplist. Поэтому поиск выполняется по отсортированной структуре в памяти и почти не требует операций ввода-вывода. Как только ключ найден, поиск прекращается.

После активной memtable RocksDB проверяет заполненные неизменяемые memtable, которые ещё не были сброшены на диск. Они проверяются от самых новых к самым старым.

Затем проверяется диск. Каждый файл уровня 0 нужно проверять отдельно, от самого нового к самому старому, поскольку диапазоны их ключей пересекаются. Каждый такой файл — снимок данных, которые успела принять соответствующая memtable, поэтому один ключ может одновременно находиться в двух файлах уровня 0.

Каждый файл уровня 0 — отдельное место, где может скрываться ключ. Именно поэтому количество файлов уровня 0 увеличивает стоимость чтения и RocksDB приостанавливает запись, чтобы ограничить их число.

Начиная с уровня 1 SST-файлы внутри каждого уровня отсортированы и не пересекаются, поэтому ключ может находиться не более чем в одном файле на уровень. Нужный файл находят двоичным поиском по метаданным, после чего поиск продолжается внутри него. Индексный блок указывает на нужный блок данных, а тот либо содержит ключ, либо показывает, что на этом уровне ключа нет.

Номера последовательности важны для пути чтения RocksDB, поскольку позволяют остановить поиск на первой найденной версии. Это гарантирует, что она будет новейшей. Например, если при чтении обнаружена tombstone-запись, операция успешно возвращает результат о том, что ключ удалён. Поиск заканчивается на tombstone-записи, а старое значение остаётся на диске.

Какие операции чтения предлагает RocksDB?

RocksDB предоставляет четыре способа чтения, каждый из которых по-своему использует путь чтения: Get, MultiGet, Iterators и Snapshots.

Get

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

MultiGet

MultiGet объединяет точечные поиски в пакет. Операция чтения может передать RocksDB набор ключей, которые система сортирует и группирует по файлам, к которым они могут обратиться.

Это позволяет RocksDB открыть один SST, один раз проверить его индексные блоки и блоки фильтров, а также объединить операции ввода-вывода в пакет. Путь чтения тот же, что и для Get, но постоянные издержки распределяются по всему пакету.

Итераторы

Iterators сканируют диапазоны: переходят к ключу, а затем перемещаются вперёд или назад в порядке сортировки.

По сути, итератор выполняет k-путевое слияние, то есть объединяет k разных отсортированных списков в одну полностью отсортированную последовательность. Каждый активный источник данных — memtable, любая неизменяемая memtable, каждый файл L0 и по одному файлу с каждого более глубокого уровня — предоставляет собственный отсортированный курсор. Куча раз за разом возвращает курсор со следующим наименьшим ключом.

На каждом шаге действует правило приоритета новейшей версии. Если несколько источников предлагают один ключ, побеждает новейшая версия, а остальные отбрасываются.

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

Snapshot

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

Создание snapshot практически ничего не стоит, поскольку расходы возникают позже: пока snapshot активен, версии, которые он видит, нельзя удалить независимо от их возраста.

И Get, и MultiGet точно знают, какой ключ им нужен. Поэтому вместо вопроса «где находится этот ключ?» поиск может задать более дешёвый вопрос: «в каких файлах его точно нет?». У Iterators такой возможности нет. Отвечать на более дешёвый вопрос — единственная задача фильтра Блума.

Что такое фильтр Блума?

Фильтр Блума отвечает на один вопрос о множестве: этого элемента точно нет в нём? Ответ может быть либо «точно нет», либо «возможно», но никогда — уверенное «да». Если ключа в файле точно нет, поиск не открывает этот файл и экономит операции ввода-вывода.

При создании SST каждый ключ проходит через несколько хеш-функций, и каждый хеш устанавливает бит в компактном битовом массиве — блоке фильтра.

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

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

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

При стандартной для RocksDB настройке в десять бит на ключ доля ложноположительных результатов составляет около одного процента. Десять бит дают 99%-ную вероятность пропустить файл, в котором нет ключа. Фильтр для SST с миллионом ключей занимает чуть больше мегабайта, находится в памяти рядом с индексом и проверяется без обращения к защищаемому им диску. Немногие структуры в системной инженерии дают настолько много при столь малых затратах.

Это также объясняет, почему в предыдущей статье этой серии размер блока фильтра оказался равен нулю. Фильтры Блума включаются отдельно и настраиваются через filter_policy с выбранным приложением количеством бит на ключ. По умолчанию фильтры не используются.

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

Одно из ограничений фильтров Блума состоит в том, что они помогают только тогда, когда известен точный ключ. Фильтр Блума может определить, находится ли key:0301 в этом файле, но не может ответить, содержит ли файл что-либо между key:0090 и key:0110, поскольку хеширование уничтожает порядок.

Iterators не знают следующий ключ заранее, поэтому эта структура им не помогает. Фильтры Блума предназначены для точечного поиска. Для нагрузок с большим количеством диапазонных запросов нужны другие решения.

А как насчёт поиска по префиксу в RocksDB?

RocksDB частично решает проблему сканирования, изменяя то, что хешируется. Экстрактор префикса сообщает RocksDB, что ключи имеют значимую структуру — например, первые восемь байт или всё до разделителя. Когда RocksDB знает, что считать префиксом, она может строить фильтры Блума по префиксам вместо полных ключей или наряду с ними. Фильтр, способный определить, есть ли в файле ключ с определённым префиксом, может помочь итератору.

Однако это ускорение работает только с одним префиксом.

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

Поиск по префиксу не делает диапазонное сканирование дешёвым в общем случае.

Он удешевляет один конкретный и чрезвычайно распространённый вид диапазонного сканирования по заданному префиксу.

Что такое кэш блоков RocksDB?

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

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

Есть один нюанс: кэшей два.

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

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

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

Во что обходятся читателям tombstone-записи и цепочки слияния?

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

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

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

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

Треугольник амплификации

Треугольник амплификации описывает компромисс между тремя характеристиками каждого LSM-дерева: амплификацией записи, чтения и пространства. Улучшение любых двух ухудшает третью.

Athanassoulis и соавторы формализовали эти компромиссы в гипотезе RUM (2016). Согласно ей, метод доступа может минимизировать не более двух видов издержек: на чтение, обновление и память или пространство. Третий принимает расходы на себя. B-деревья занимают одну позицию — дешёвое чтение и дорогие обновления, — а LSM-деревья другую — дешёвые обновления и дорогое чтение. Треугольник описывает всё пространство между ними.

Всё, о чём говорилось в этой статье, — защита одного из углов треугольника.

Амплификация записи — это отношение количества байтов, физически записанных на диск, к количеству байтов, логически записанных приложением. Одна операция Put сначала записывается в WAL, затем при сбросе — в L0 и после этого при каждой компакции, которая переносит её на следующий уровень. Таким образом, одна логическая запись за время своего существования может превратиться в десять–тридцать физических записей в многоуровневом LSM с десятком уровней. В предыдущей статье мы радовались, что все эти записи последовательны, а в этой — сетуем на их количество.

Амплификация чтения — это количество мест, которые запрос должен проверить, чтобы найти ответ. В худшем случае точечный поиск проверяет каждую memtable, каждый файл L0 и по одному файлу на каждом более глубоком уровне — именно такой поиск описан в начале статьи. Реальная стоимость определяется тем, что не смогли отсеять фильтры Блума и кэш блоков. Для диапазонного сканирования это k-путевое слияние, которое одновременно держит открытыми все источники. Эта статья в основном посвящена амплификации чтения: фильтрам, кэшам и экстракторам префиксов, которые её сокращают.

Амплификация пространства — это отношение занятого дискового пространства к объёму хранимых логических данных. Старые версии, ожидающие компакции, tombstone-записи и скрытые ими данные, несвёрнутые цепочки слияния и все версии, удерживаемые активными snapshot, занимают диск данными, которые приложение больше не может или не хочет читать. Хорошо настроенная многоуровневая компакция удерживает этот показатель около 1,1x, тогда как другие схемы требуют значительно больше пространства.

Треугольник показывает, что улучшение любых двух углов ухудшает третий. То есть:

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

Настройки «быстро» не существует. Есть лишь позиции внутри треугольника, которые подходят или не подходят конкретной нагрузке.

Пошаговый разбор пути чтения

Ниже повторно используется проект из практического примера предыдущей статьи, но с включённой статистикой.

Замените содержимое src/main.rs следующим кодом:

use rocksdb::{BlockBasedOptions, Options, DB};

fn main() {
	let with_bloom = std::env::args().nth(1).as_deref() == Some("bloom");
	let path = if with_bloom { "/tmp/read-bloom" } else { "/tmp/read-nobloom" };

	let mut opts = Options::default();
	opts.create_if_missing(true);
	opts.enable_statistics();

	if with_bloom {
		let mut bbt = BlockBasedOptions::default();

		bbt.set_bloom_filter(10.0, false);
		opts.set_block_based_table_factory(&bbt);
	}

	let db = DB::open(&opts, path).unwrap();

	// Three L0 SSTs with fully overlapping ranges: file b holds keys where
	// key % 4 == b, all spanning 0..600. Keys where key % 4 == 3 exist nowhere
	for batch in 0..3u64 {
		let mut k = batch;

		while k < 600 {
			let key = format!("key:{:04}", k);
			db.put(key.as_bytes(), b"value").unwrap();
			k += 4;
		}

		db.flush().unwrap();
	}

	// key:0404 lives only in the oldest file, meaning the search must get past
	// the two newer files to reach it
	let hit = db.get(b"key:0404").unwrap();
	println!("get(key:0404) = {:?}", hit.map(|b| String::from_utf8(b).unwrap()));

	// key:0303 is inside every file's range and inside no file
	let miss = db.get(b"key:0303").unwrap();
	println!("get(key:0303) = {:?}", miss);

	if let Some(stats) = db.property_value("rocksdb.options-statistics").unwrap() {
		for line in stats.lines() {
			if line.contains("bloom.filter.useful")
				|| line.contains("bloom.filter.full.positive")
				|| line.contains("block.cache.data") {
				println!("{}", line);
			}
		}
	}
}

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

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

Отсутствующий ключ, то есть key:0303, входит в диапазон каждого файла, но не присутствует ни в одном из них. Такое чтение может ускорить только фильтр Блума.

Сначала запустите код без изменений, а затем с аргументом bloom.

Без фильтров вывод выглядит так:

get(key:0404) = Some("value")
get(key:0303) = None
rocksdb.block.cache.data.miss COUNT : 3
rocksdb.block.cache.data.hit COUNT : 3
rocksdb.bloom.filter.useful COUNT : 0

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

С фильтрами вывод выглядит так:

get(key:0404) = Some("value")
get(key:0303) = None
rocksdb.block.cache.data.miss COUNT : 1
rocksdb.block.cache.data.hit COUNT : 0
rocksdb.bloom.filter.useful COUNT : 5
rocksdb.bloom.filter.full.positive COUNT : 1

Всего выполнено одно обращение к блоку данных. Можно вручную проверить расчёт, по которому useful равен 5:

• При успешном поиске были проверены фильтры самого нового и второго файлов, и оба вернули отрицательный результат. Фильтр самого старого файла вернул единственный full.positive, оказавшийся истинно положительным результатом. Итого два пропуска
• При поиске отсутствующего ключа были проверены все три фильтра и получены три отрицательных результата. Итого три пропуска и ни одного открытого файла

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

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

Как Solana нагружает путь чтения?

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

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

Внутри валидатора чтение из Blockstore выполняется в двух формах: обслуживание запросов на восстановление и воспроизведение или потоковая передача блока.

При обслуживании запросов на восстановление другие валидаторы запрашивают пропущенные шреды. Это точечный поиск по (slot, index). Воспроизведение или потоковая передача данных реестра для целого блока — это диапазонное сканирование заданного слота.

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

Структура ключей из пути записи оптимизирует путь чтения. Та же схема с номером слота в начале ключа, благодаря которой при сбросах создавались почти не пересекающиеся файлы L0, превращает чтение блоков в один непрерывный проход.

Уровень RPC задаёт более сложные вопросы. getTransaction выполняет точечный поиск по подписи в данных о статусах транзакций. Именно для такого случая существуют фильтры Блума: отсутствие подписи в конкретном SST должно определяться одной проверкой в памяти, а не чтением индекса.

getSignaturesForAddress — это сканирование по префиксу, описанное ранее в статье. Индекс «адрес — подпись» начинается с адреса, поэтому вся история одного аккаунта занимает один непрерывный диапазон ключей. Активность по адресу превращается в диапазонное сканирование того вида, с которым структура хорошо справляется.

Однако фактические вопросы приложений опираются на оба механизма. Примитива «дай мне все транзакции для этого адреса» не существует. Такой запрос превращается в сканирование по префиксу для получения подписей, а затем в точечный поиск транзакции по каждой подписи.

По сути, один диапазонный запрос разветвляется на сотни или тысячи операций Get. Именно для такой нагрузки и существует пакетная обработка MultiGet: отсортировать подписи, сгруппировать их по затрагиваемым файлам и один раз проверить индекс и фильтры каждого файла.

Запрос, который снаружи выглядит как один вызов API, на пути чтения последовательно задействует все описанные в статье механизмы: итератор, упорядочивание по префиксу, фильтры Блума, пакетное распределение затрат и кэш блоков.

Мы создали такой вызов API.

Раньше разработчикам приходилось запускать на стороне клиента цикл из getSignaturesForAddress и n вызовов getTransaction, а также добавлять логику повторных попыток, которая всегда требуется шаблонам n+1.

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

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

Архивная система, обслуживающая этот метод, хранит в RocksDB полную историю транзакций Solana — сотни терабайт. Мы перенесли её с ClickHouse на RocksDB, и именно поэтому появилась эта серия статей. Описанный в них движок хранения — тот самый движок, который мы настраивали семейство столбцов за семейством, чтобы всю историю аккаунта можно было получить одним непрерывным сканированием, а поиск подписи требовал одной проверки в памяти. Поэтому наша архивная система — самая производительная во всей Solana.

Заключение

Путь чтения — это график погашения долга LSM-дерева, а эта статья представляет подробный счёт. Поиск идёт от самых новых данных к самым старым через memtable, L0 и все отсортированные уровни, после чего останавливается на первой найденной версии. Все остальные функции и инструменты существуют для того, чтобы свести к минимуму количество обращений при поиске. Фильтры Блума определяют по данным в памяти, что ключа точно нет в файле, и позволяют не открывать его. Кэш блоков удешевляет повторное открытие файлов, к которым всё же приходится обращаться. А структура префиксов превращает единственный доступный вид диапазонного сканирования в тот, который действительно нужен приложениям.

Треугольник амплификации — это реестр, в котором учитывается всё перечисленное: стоимость чтения погашается памятью, а стоимость записи оплачивается раньше последовательными взносами. Стоимость пространства незаметно накапливается в каждой tombstone-записи и каждой скрытой версии, через которые переступает поиск.

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

Если вам нравится проводить день за чтением подробного разбора пути чтения базы данных, присоединяйтесь к нашей команде. Описанный здесь путь чтения мы используем для работы с полной историей Solana, где разница между проверкой фильтра Блума и открытием файла измеряется реальным оборудованием и реальными деньгами. Мы нанимаем специалистов в инженерную команду. Все открытые вакансии доступны на helius.dev/careers