LevelDB

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 15:43, 21 января 2019.
LevelDB
Leveldb-logo.png
Разработчики: Jeffrey Dean, Sanjay Ghemawat
Выпущена: 2004 (2004)
Постоянный выпуск: 1.20 / 2 марта 2017
Написана на: C++
Операционная система: Кроссплатформенная
Тип ПО: Database library
Лицензия: New BSD License
Веб-сайт github.com/google/leveldb

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

История

LevelDB основана на концепции от компании Google с BigTable система баз данных. Реализация таблицы для системы Bigtable была разработана примерно в 2004 году и основана на другой внутренней базе кода Google, чем код LevelDB. Эта кодовая база опирается на ряд библиотек кода Google, которые сами по себе не являются открытыми, поэтому непосредственно открыть источник, что код было бы трудно. Джефф Дин и Санджай Гемават хотел создать систему, напоминающую систему BigTable таблетки стека, которая была минимальной зависимости и будут пригодны для открытых источников, а также быть пригодным для использования в Chrome для индексированные базы данных реализация.

Особенности

LevelDB хранит ключи и значения в произвольных массивах байтов, а данные сортируются по ключу. Он поддерживает пакетную пишет, прямой и обратной итерации, и сжатие данных с помощью Google's Snappy сжатия библиотеки.

Применение

LevelDB используется в качестве серверной базы данных для Google Chrome's IndexedDB и является одним из поддерживаемых движков для Riak. Кроме того, Биткоин ядро хранит блокчейн метаданные с помощью базы данных LevelDB. В Minecraft: карманное издание использует модифицированную версию для чанка и организация хранения данных. Система автоматизированного проектирования AutoCAD 2016 также используется LevelDB.

Производительность

Корпорация Google предоставила критерии сравнения LevelDB производительность для базы данных SQLite и Kyoto Cabinet в различных сценариях. LevelDB превосходит обоих SQLite и Киотского кабинета в операции записи и последовательного порядка операций чтения. LevelDB также превосходит при пакетной записи, но медленнее, чем SQLite при работе с большими значениями

Алгоритм и свойства LevelDB

Ошибки и надежность

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

Алгоритм хранения данных

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

Вставка

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

Некоторые свойства LevelDB

  • хранилище типа ключ-значение;
  • ключ и значение это произвольный массив байт;
  • данные хранятся упорядоченно, порядок можно задавать;
  • прямой и обратный итератор для обхода данных;
  • множественное атомарное обновление;
  • поддержка снимков;
  • сжатие данных через Snappy.

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

  • в качестве ключей и привязанных к ним значений может использоваться произвольный байтовый массив;
  • данные хранятся отсортированными по связанному с ними ключу;
  • пользователь может переопределить метод сортировки, указав собственную функцию сравнения;
  • управление данными производится через базовые операторы Put(key,value), Get(key) и Delete(key);
  • в рамках одной атомарной операции в базу может быть внесено сразу несколько изменений;
  • поддерживается создание снапшотов, представляющих собой неизменный срез состояния БД на текущий момент времени. Со снапшотом можно работать в штатном режиме, но в нём не будут отражаться изменения базы, производимые после его создания;
  • над данными можно использовать прямые и обратные итерации (переходить к следующему или предыдущему элементу отсортированного списка);
  • данные хранятся в сжатом виде, для сжатия используется библиотека Snappy.[Источник 2]

Библиотека LevelDB

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

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

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

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

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

Библиотека может быть ипользована с большинством популярных языков программирования.

API LevelDB

Открытие и закрытие

Открытие

  #include <assert>
  #include "leveldb/db.h"

  leveldb::DB* db;
  leveldb::Options options;
  options.create_if_missing = true;
  leveldb::Status status = leveldb::DB::Open(options, "/tmp/testdb", &db);
  assert(status.ok());

Закрытие

   delete db;

Опции

Параметры данных
Имя Описание Значение по умолчанию
comparator компаратор задающий порядок ключей BytewiseComparator, использует внутри себя memcmp
create_if_missing создать базу, если отсутствует false
error_if_exists выкинуть ошибку, если база существует false
paranoid_checks агрессивная проверка целостности базы false
env окружение через которое будет производится операции ввода/вывода Env::Default()
write_buffer_size размер буфера на запись 4MB
max_open_files количество открытых файлов 1000
block_cache использовать специальный кеш для блоков NULL, создает и использует внутренний кеш объемом 8MB
block_size приблизительный объем пользовательских данных в блоке 4K
compression сжатие блока kSnappyCompression
filter_policy фильтр(Блума) для уменьшения операций чтения с диска. NULL

Slice

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

  leveldb::Slice slice;
  if (...) {
    std::string str = ...;
    slice = str;
  }
  Use(slice);

leveldb::Slice имеет ряд конструкторов для удобства использования:

  Slice(const char* d, size_t n) : data_(d), size_(n) { }
  Slice(const std::string& s) : data_(s.data()), size_(s.size()) { }
  Slice(const char* s) : data_(s), size_(strlen(s)) { }

И методы для получения данных

  const char* leveldb::Slice::data() const;
  char leveldb::Slice::operator[](size_t n) const;
  std::string leveldb::Slice::ToString() const;

Статус

Для информирования о возможных ошибках большинство функций в LevelDB возвращают статус. По статусу можно проверить выполнилась функция успешно и получить текстовое описание ошибки.

  leveldb::Status s = ...;
  if (!s.ok()) cerr << s.ToString() << endl;

Чтение, запись, удаление

Сигнатуры Put, Get, Delete

  Status leveldb::DB::Put(const WriteOptions& options, const Slice& key, const Slice& value);
  Status leveldb::DB::Get(const ReadOptions& options, const Slice& key, std::string* value);
  Status leveldb::DB::Delete(const WriteOptions& options, const Slice& key);

Пример использования:

  std::string value;
  leveldb::Status s = db->Get(leveldb::ReadOptions(), key1, &value);
  if (s.ok()) s = db->Put(leveldb::WriteOptions(), key2, value);
  if (s.ok()) s = db->Delete(leveldb::WriteOptions(), key1);

Итератор

Итератор представлен классом leveldb::Iterator и имеет следующий интерфейс:

  bool leveldb::Iterator::Valid() const;
  void leveldb::Iterator::SeekToFirst();
  void leveldb::Iterator::SeekToLast();
  void leveldb::Iterator::Seek(const Slice& target);
  void leveldb::Iterator::Next();
  void leveldb::Iterator::Prev();
  Slice leveldb::Iterator::key() const;
  Slice leveldb::Iterator::value() const;
  Status leveldb::Iterator::status() const;

Интерфейс итератора предоставляет методы для последовательного и произвольного доступа. Последовательный доступ может осуществлятся как в прямом, так и в обратном направлении.

  leveldb::Iterator* it = db->NewIterator(leveldb::ReadOptions());
  for (it->SeekToFirst(); it->Valid(); it->Next()) {
  cout << it->key().ToString() << ": "  << it->value().ToString() << endl;
  }
  assert(it->status().ok());  // Check for any errors found during the scan
  delete it;

  for (it->Seek(start);
     it->Valid() && it->key().ToString() < limit;
     it->Next()) {
    ...
  } 

  for (it->SeekToLast(); it->Valid(); it->Prev()) {
  ...
  }

Схема данных

Для хранение метрик в хранилище типа ключ-значение используют следующую схему: ключ=метрика+временная метка+теги(теги опцианальны). Подобным образом устроена OpenTSDB, работающая поверх HBase. Внутри OpenTSDB есть схема uid'ов метрик и схема данных. Такой же принцып будет задействован и здесь.

Одна база будет использоваться для хранения идентификаторов метрик. Ключем тут будет число в size_t, значением строка в стиле Си.

Втроая база будет исопльзоваться под данные, ключем тут будет структура вида:

struct Key
{
    size_t muid;
    time_t timestamp;
};

значение будет хранится в виде double. Тут на полную катушку используется тот факт, что ключ и значение в LevelDB массив байт, а значит можем использвать простые структуры данных без всякой сериализации.

Интерфейс хранилища

#pragma once

#include <ctime>
#include <cstdint>

#include <memory>
#include <unordered_map>

namespace leveldb
{
    class DB;
    class Iterator;
    class Slice;
    class Comparator;
    class Cache;
}

/*!
 * Хранилище метрик
 */
class Storage
{
public:
    class Iterator;
    typedef size_t MetricUid;

    /*!
     * Представление ключа
     */
    struct Key
    {
        MetricUid muid;   //!< uid метрики
        time_t timestamp; //!< время
    };

    /*!
     * Конструктор
     * @param dir каталог для размещения базы данных и базы метрик
     * @param cacheSizeMb размер блока кеша
     */
    Storage(const std::string& dir, size_t cacheSizeMb = 16);

    /*!
     * @brief Добавление метрики.
     * @param name имя метрики
     * @return уникальный идентификатор метрики
     *
     * Добавляет метрику в базу UID'ов и возвращает UID метрики.
     * Если метрика уже была добавлена, то возращает UID метрики
     */
    MetricUid addMetric(const std::string& name);

    /*!
     * Записать значение
     * @param muid идентификатор метрики
     * @param timestamp временная точка
     * @param value значение
     * @return true если нет ошибок
     */
    bool put(MetricUid muid, time_t timestamp, double value);

    /*!
     * Получить итератор для интервала значений метрики
     * @param muid идентификатор метрики
     * @param from начало интервала
     * @param to конец интервала
     * @return итератор
     */
    Iterator get(MetricUid muid, time_t from, time_t to);

    Storage(const Storage&) = delete;
    Storage& operator=(const Storage&) = delete;

private:

    /*!
     * Инициализация базы uid метрик
     */
    void initUID();

    /*!
     * Инициализация данных
     */
    void initData();

private:

    /*!
     * Текущий индекс для UID
     */
    MetricUid m_currentIndx;

    /*!
     * Базовый каталог
     */
    std::string m_dir;

    /*!
     * Размер блока кеша
     */
    size_t m_cacheSizeMb;

    /*!
     * Кеш для данных
     */
    std::shared_ptr<leveldb::Cache> m_dataCache;

    /*!
     * База UID'ов
     */
    std::shared_ptr<leveldb::DB> m_uid;

    /*!
     * База измерений
     */
    std::shared_ptr<leveldb::DB> m_data;

    /*!
     * Мэп метрика -> uid
     */
    std::unordered_map<std::string, MetricUid> m_metric2uid;
};

/*!
 * Итератор для обхода последовательности данных
 */
class Storage::Iterator
{
public:
    typedef std::tuple<time_t, double> Value;
    typedef std::shared_ptr<leveldb::Iterator> IteratorPrivate;

    Iterator();

    Iterator(const IteratorPrivate& iter, const Key& limit);

    /*!
     * Проверка итератора на валидность
     * @return true если итератор валиден
     */
    bool valid() const;

    /*!
     * Получить значение
     * @return кортеж <время, значение>
     */
    Value value() const;

    /*!
     * Переход к следующему элементу
     */
    void next();

private:

    IteratorPrivate m_iter; //!< итератор LevelDB
    Key m_limit; //!< ключ для ограничения последовательности справа
};

Конструктор Storage принимает путь к каталогу, где будут размещатся база с uid и база с данными, размер блока кеша.

Реализация

Начинется с компаратора, т.к. memcmp не подходит для сравнения чисел. Благодаря использования структуры в качестве ключа, код прост и читаеется:

namespace
{
    class TimeMeasurementComporator: public leveldb::Comparator
    {
    public:
        int Compare(const leveldb::Slice& a, const leveldb::Slice& b) const
        {
            const char* dataA = a.data();
            const char* dataB = b.data();
            const Storage::Key* keyA =
                    reinterpret_cast<const Storage::Key*>(dataA);
            const Storage::Key* keyB =
                    reinterpret_cast<const Storage::Key*>(dataB);
            if (keyA->muid < keyB->muid)
            {
                return -1;
            }
            else if (keyA->muid > keyB->muid)
            {
                return 1;
            }

            if (keyA->timestamp < keyB->timestamp)
            {
                return -1;
            }
            else if (keyA->timestamp > keyB->timestamp)
            {
                return 1;
            }

            return 0;
        }

        // Ignore the following methods for now:
        const char* Name() const
        {
            return "TimeMeasurementComporator";
        }
        void FindShortestSeparator(std::string*, const leveldb::Slice&) const
        {
        }
        void FindShortSuccessor(std::string*) const
        {
        }
    };
    TimeMeasurementComporator GLOBAL_COMPORATOR;
}

Дальше инициализация/создание базы под данные:

void Storage::initUID()
{
    Options options;
    options.create_if_missing = true;
    options.compression = kNoCompression;

    DB* cfg;
    Status status = DB::Open(options, m_dir + "/conf", &cfg);
    if (!status.ok())
    {
        LOG(ERROR)<<"Error opening database "<<status.ToString();
        exit(1);
    }
    m_uid.reset(cfg);

    std::unique_ptr<leveldb::Iterator> it(
            m_uid->NewIterator(leveldb::ReadOptions()));

    for (it->SeekToFirst(); it->Valid(); it->Next())
    {
        const size_t* index = reinterpret_cast<const size_t*>(it->key().data());
        m_metric2uid[it->value().ToString()] = *index;
        m_currentIndx = *index;
    }
}

Тут происходит инициализация базы и заполнения отображения метрики в UID. Добавление данных довольно простое:

Storage::MetricUid Storage::addMetric(const std::string& name)
{
    auto result = m_metric2uid.find(name);
    if (result != m_metric2uid.end())
    {
        return result->second;
    }
    ++m_currentIndx;
    m_metric2uid[name] = m_currentIndx;
    const auto s = m_uid->Put(WriteOptions(),
            Slice(reinterpret_cast<const char*>(&m_currentIndx), sizeof(m_currentIndx)),
            name);

    if (!s.ok())
    {
        LOG(ERROR)<<"Error put "<<s.ToString();
    }

    return m_currentIndx;
}

bool Storage::put(MetricUid muid, time_t timestamp, double value)
{
    const Key key = {muid, timestamp};

    const auto s = m_data->Put(WriteOptions(),
            Slice(reinterpret_cast<const char*>(&key), sizeof(key)),
            Slice(reinterpret_cast<char*>(&value), sizeof(value)));

    if (!s.ok())
    {
        LOG(ERROR)<<"Error put "<<s.ToString();
    }

    return s.ok();
}

Получение данных реализовано посредством создание обертки над итератором LevelDB:

Storage::Iterator Storage::get(MetricUid muid, time_t from, time_t to)
{
    const Key begin = {muid, from};
    const Key end = { muid, to };

    Storage::Iterator::IteratorPrivate iter(m_data->NewIterator(ReadOptions()));
    iter->Seek(Slice(reinterpret_cast<const char*>(&begin),
                     sizeof(begin)));
    return Storage::Iterator(iter, end);
}

Storage::Iterator::Iterator():
        m_iter(nullptr)
{
    memset(&m_limit, 0, sizeof(m_limit));
}


Storage::Iterator::Iterator(const IteratorPrivate& iter, const Key& limit) :
        m_iter(iter),
        m_limit(limit)
{
}

bool Storage::Iterator::valid() const
{
    if(!m_iter)
    {
        return false;
    }

    const Slice right(reinterpret_cast<const char*>(&m_limit),
                      sizeof(m_limit));

    return m_iter->Valid() &&
           (GLOBAL_COMPORATOR.Compare(m_iter->key(),right) < 0);
}

Storage::Iterator::Value Storage::Iterator::value() const
{
    if(!m_iter)
    {
        return Value(0,0);
    }

    const Key* data =reinterpret_cast<const Key*>(m_iter->key().data());
    double val = *reinterpret_cast<const double*>(m_iter->value().data());
    return Value(data->timestamp, val);
}

void Storage::Iterator::next()
{
    if(m_iter && m_iter->Valid())
    {
        m_iter->Next();
    }
}

Источники

  1. BSD licenses // Wikipedia. [2018-2018]. Дата обновления: 24.12.2018. URL: https://en.wikipedia.org/wiki/BSD_licenses#3-clause_license_.28.22Revised_BSD_License.22.2C_.22New_BSD_License.22.2C_or_.22Modified_BSD_License.22.29 (дата обращения: 20.10.2018)
  2. morphs // Блог [2016-2019]. Дата обновления: 05.09.2016. URL: http://morphs.ru/posts/15 (дата обращения: 21.01.2019)
  3. Использование LуvelDB // Habrahabr [2006 - 2019]. Дата обновления: 14.07.2015. URL: https://habrahabr.ru/post/256207/#1 (дата обращения: 21.01.2019)