SS-таблицы и LSM-деревья

В случае хэш-индекса пары ключ-значения лежат в файлах в порядке появления. Если мы будем хранить их с сортировкой по ключу, то мы получим SS-таблицу (sorted string table, SSTable).

Работа с индексом, основанным на SS-таблице, может быть организована следующим образом:

В оперативной памяти располагается сбалансированная структура данных, например, красно-чёрное дерево. Такое дерево само поддерживает хранение ключей в отсортированном виде. Поскольку оно расположено в памяти, то называется MemTable. При поступлении записи добавляем ее в MemTable.

Когда размер MemTable превышает определенное пороговое значение (обычно несколько мегабайт), записываем его на диск в виде файла SS-таблицы.

Для обслуживания запроса на чтение сначала пробуем найти ключ в MemTable, затем в последнем по времени сегменте на диске, затем в предпоследнем и т. д.

Время от времени запускаем в фоне процесс слияния и уплотнения, чтобы объединить файлы сегментов и отбросить перезаписанные или удаленные значения.

SS-таблица имеет три преимущества перед хэш-индексами:
1) Объединение сегментов выполняется просто и эффективно с помощью сортировки слиянием.

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

Пример на схеме к посту.

3) Поскольку для выполнения запроса на чтение необходимо просмотреть несколько пар «ключ — значение», можно сгруппировать эти записи в блок и сжать его. Каждая запись разреженного индекса в оперативной памяти будет указывать на начало сжатого блока.

Изначально эта индексная структура была описана под названием Log-Structured Merge-Tree. Важный момент, что в LSM допускается только дописывание данных в файлы и удаление устаревших файлов, а не обновление записанного файла.

Такой подход используется в key-value БД LevelDB, RocksDB, а также в Cassandra и HBase.

#кабанчик #сисдиз