GoProg

 
Топ хэштегов


Архив

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;
  • Все внешние операции на уровне операционной системы, такие как работа с файлами, производится через виртуальный программный интерфейс, который позволяет пользователю изменить поведение библиотеки при взаимодействии с операционной системой.

Библиотека достаточно хорошо оптимизирована и демонстрирует высокую производительность при различных видах использования. Разработчики 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-, осуществляется через итератор:

prefix := []byte("foo-")

iter := db.NewIterator(util.BytesPrefix(prefix), nil) 
for iter.Next() { 
  key := iter.Key() 
  value := iter.Value() 
  // операции 
} 
iter.Release() 
err = iter.Error() 

Пройти по всем ключам в диапазоне можно так:

from := []byte{"begin"}
to := []byte{"end"}


iter := base.base.NewIterator(&util.Range{Start: from, Limit: to}, nil)
defer iter.Release()

for iter.Next() {
  key := iter.Key() 
  value := iter.Value() 
  // операции 
}

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

#databases #Go #golang #IT #leveldb #lsmдеревья #базыданных



Новый комментарий: