Встраиваемые хранилища: LevelDB

LevelDB - это высокопроизводительная NoSQL система для хранения данных в формате ключ/значение, разработанная компанией Google. Хранилище LevelDB написано на языке С++ и подключается к приложениям в виде разделяемой библиотеки (как SQLite и BerkeleyDB), обеспечивая возможность хранения упорядоченных наборов данных, в которых строковые ключи сопоставлены со строковыми значениями. Код LevelDB открыт под лицензией BSD. 

Алгоритм хранения данных следующий — данные хранятся в SS-таблицах (Sorted String Table) в качестве пар ключ/значение. Множество SS-таблиц образует LSM-дерево. LSM-деревья (Log-structured merge-tree) состоят из нескольких уровней хранения. Первый (нулевой, он же MemTable) находится в памяти, а остальные лежат на диске. Каждый уровень представляет собой дерево или список деревьев, и у каждого уровня есть лимит роста размера (обычно 10-кратный на уровень).

Вставка производится сначала в нулевой уровень, при переполнении он сбрасывается в первый, при переполнении первого — попадает во второй и т.д. Вставки получаются быстрые, так как не нужно мучиться с перезаписью отдельных мелких блоков данных. Но возникают проблемы: во-первых, имеем неслабый write amplification, а во-вторых — при поиске значений должны просматривать все деревья. С первым ничего не поделаешь, а со вторым борятся поддержанием в памяти bloom-фильтров — неких хеш-таблиц, посмотрев в которые, можно сказать, в каких деревьях данных точно нет, а в каких они могут быть.  Параллельно пишется Write Ahead Log, на случай экстренного отказа (пропало питание или что-то еще) 

Библиотеку LevelDB можно использовать для разных целей. Например, веб-браузер может обрабатывать с помощью LevelDB кэш недавно посещённых страниц. Операционная система — список установленных пакетов и зависимостей между ними, а любое приложение может использовать LevelDB для хранения пользовательских настроек.  

Более того, LevelDB уже поддерживается в качестве низкоуровневого хранилища в таких проектах Google, как BigTable (в формате LevelDB хранятся конечные записи) и распределенной БД Riak (LevelDB может использоваться как хранилище для конечных узлов). 

Положительной чертой LevelDB является минимальное число зависимостей, что позволяет легко портировать библиотеку для разнообразных систем. В настоящий момент LevelDB уже работает в Unix-подобных ОС, Mac OS X, Windows и Android. Отдельно отмечается, что LevelDB является достаточно специализированным решением, например, LevelDB не поддерживает выполнение SQL-запросов и подключение индексов; не поддерживается одновременный доступ к БД нескольких процессов - в заданный момент времени только один процесс может работать с файлом базы (возможна работа в многопоточных программах); отсутствует встроенное решение для организации клиент-серверного доступа, работа сервера может быть организована в виде расширений 

Основные возможности LevelDB: 

• В качестве ключей и привязанных к ним значений может использоваться произвольный байтовый массив; 

• Данные хранятся отсортированными по связанному с ними ключу; 

• Пользователь может переопределить метод сортировки, указав собственную функцию сравнения; 

• Управление данными производится через базовые операторы Put(key,value), Get(key) и Delete(key); 

• В рамках одной атомарной операции в базу может быть внесено сразу несколько изменений; 

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

• Над данными можно использовать прямые и обратные итерации (переходить к следующему или предыдущему элементу отсортированного списка); 

• Данные хранятся в сжатом виде, для сжатия используется библиотека Snappy; 

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

Библиотека достаточно хорошо оптимизирована и демонстрирует высокую производительность при различных видах использования. Разработчики Google провели сравнение производительности LevelDB c такими системами, как SQLite, Kyoto Cabinet и InnoDB. В результате тестирования было выявлено, что существенное преимущество LevelDB наблюдается при пакетном обновлении данных (изменение сразу порции записей), затрагивающем большое число ключей, распределенных по всему хранилищу. 

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

go get github.com/syndtr/goleveldb/leveldb 

После чего для открытия или создания новой базы данных достаточно выполнить следующий код на Go: 

db, err := leveldb.OpenFile("path/to/db", nil)    
defer db.Close()
...  

Чтение и модификация данных осуществляется через методы Put, Get, Delete: 

data, err := db.Get([]byte("key"), nil)  
err = db.Put([]byte("key"), []byte("value"), nil)  
err = db.Delete([]byte("key"), nil) 

Пакетная модификация данных выполняется следующим образом: 

batch := new(leveldb.Batch) 
batch.Put([]byte("foo"), []byte("value")) 
batch.Put([]byte("bar"), []byte("another value")) 
batch.Delete([]byte("baz")) 
err = db.Write(batch, nil) 

Итерации по всем ключам, начинающимся со строк foo-, осуществляется через итератор: 

iter := db.NewIterator(util.BytesPrefix([]byte("foo-")), nil) 
for iter.Next() { 
    key := iter.Key() 
    value := iter.Value() 
    ... 
} 
iter.Release() 
err = iter.Error() 

Больше информации можно найти на сайте проекта.

05.09.2016