SSTable

Многие NoSQL хранилища, в качестве формата для хранения данных на диске используют SSTable. К таким базам можно отнести, например, Cassandra, HBase и LevelDB. Давайте попробуем разобраться чем это вызвано.

SSTable (Sorted String Table) – достаточно простой формат, позволяющий эффективно храненить большое число пар “ключ-значение”, оптимизированный для обеспечения высокой пропускной способности при выполнении операций последовательного чтения и записи данных. В связи с этим данный формат позволяет легко обрабатывать большие объемы информации, амортизируя нагрузку на диск. Формат не предъявляет никаких требований к размеру “ключей” и “значений”, но предполагает, что все ключи отсортированы. Таким образом, осуществляя последовательное чтение, можно получить отсортированный индекс, который будет содержать смещения до соответствующих “значений”, что обеспечит быстрый доступ к данным по ключу. Можно сказать, что SSTable – одновременно очень простой и очень удобный способ для работы с большими отсортированными сегментами данных.

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

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

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

Если присмотреться, то есть все необходимые части для решения этой проблемы: случайная запись осуществляется быстро, если SSTable находится в памяти (назовем ее MemTable); чтение осуществляется также быстро, если SSTable не изменяется и находится на диске. Таким образом, если принять следующие соглашения, то можно решить обозначенную проблему:

  • Индексы SSTable с диска загружаются в оперативную память
  • Данные записываются непосредственно в индекс MemTable
  • При чтении сначала проверяется MemTable, затем SSTable
  • Периодически MemTable сбрасывается на диск в виде SSTable
  • Периодически SSTable на диске объединяются в один файл

В итоге мы имеем следующее. Запись всегда осуществляется в память, следовательно, всегда производится быстро. Как только MemTable достигает определенного размера, она сбрасывается на диск в виде неизменного SSTable. Так как все индексы SSTable находятся в памяти, при любом чтении в первую очередь проверяется MemTable, и только потом осуществляется обращение к SSTable, если данные не были найдены в MemTable.

Таким образом, мы только что заново открыли подход, который Patrick O’Neil описал в своей статье “The Log-Structured Merge-Tree” (LSM Tree)” еще в 1996 году. 

 

Тэги: databases leveldb sstable базы данных


 


 
архив

подписка