Как именно memtable сбрасывается в SSTable на диске в LSM-деревьях?
С точки зрения реализации, как именно memtable (в Cassandra, RocksDB, LevelDB или любом LSM-дереве) сбрасывается в SSTable?
Я понимаю, что memtable представляет собой отсортированные данные, структурированные, как красно-черное дерево, но как нам превратить это в файл отсортированных пар ключ/значение? Проходим ли мы по дереву от наименьшего ключа к наибольшему дереву в цикле for и вставляем данные один за другим в буфер памяти (в формате SSTable), а затем записываем это на диск? Используем ли мы какой-то метод сериализации дерева (если да, то как это все еще в формате SSTable)? Можем ли мы просто использовать min-heap для memtable и при очистке продолжать получать элемент min и добавлять его в наш массив для очистки?
Я пытаюсь понять супер конкретные детали. Я смотрел на этот файл, но мне было трудно его понять: https://github.com/facebook/rocksdb/blob/fbfcf5cbcd3b09b6de0924d3c52a744a626135c0/db/flush_job.cc
2 ответа
Ты прав.
Memtable перебирается от наименьшего к наибольшему и записывается в файл.
На практике в файл записываются и другие вещи, но основой файла является раздел, содержащий все ключи, которые ранее были в memtable. Такие как фильтры Блума, поиск разреженных индексов и другие метаданные, такие как количество, максимальный ключ, минимальный ключ.
Вам не нужна минная куча. Поскольку данные уже отсортированы в списке пропусков
Таблица памяти RocksDB по умолчанию реализована с использованием списка пропусков, который представляет собой связанный список с возможностью двоичного поиска, аналогичный дереву B+. При записи в таблицу SST он перебирает все ключи в отсортированном порядке.