Говоря о хранении и извлечении из LevelDB

Введение

LevelDB разработан Google, очень быстрое постоянное хранилище KeyValue, ключ и значение могут быть любым массивом байтов, и это отношение сопоставления сортируется по ключу.

Типичные сценарии приложений

Функция счетчика, очень часто обновляемая, и данные не могут быть потеряны

характеристика

• ключ и значение могут быть произвольными массивами байтов
• Данные сортируются по ключу
• Пользователь может настроить правила сортировки
• Основные методы работы поставлены (ключ, значение), Get (Key), удалить (ключ).
• Несколько изменений могут действовать как одна атомарная операция
• Пользователи могут создать временный снимок, чтобы получить единообразное представление данных.
• Данные поддерживают прямую и обратную итерации.
• Данные автоматически сохраняются в сжатом виде с использованием библиотеки сжатия Snappy.
• Внешние действия (операции с файловой системой и т. д.) проходят через виртуальный интерфейс, чтобы пользователь мог настроить взаимодействие с ОС.

ограничение

• LevelDB не является реляционной базой данных и не поддерживает реляционные модели данных, SQL-запросы и индексы.
• Только один процесс (возможно, многопоточный) может одновременно обращаться к конкретной базе данных.
• В библиотеке нет встроенных клиентских и серверных функций, и приложения, которым требуются эти функции, должны инкапсулировать их сами.

представление

В тестовой библиотеке всего 100 строк записей, каждая запись имеет 16-байтовый ключ, 100-байтовое значение, а сжатое значение составляет около 50 байт.

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

• Последовательная запись: среднее время каждой операции составляет 1,765 микросекунды, то есть поддерживается около 55 Вт последовательных операций записи в секунду.
• Последовательная запись + сброс каждый раз: среднее время выполнения каждой операции составляет 268,409 микросекунд, то есть поддерживается около 3700 операций записи на сброс в секунду.
• Случайная запись: среднее время на операцию составляет 2,460 микросекунд, то есть поддерживается около 40 Вт операций произвольной записи в секунду.
• Обновление записи: среднее время на операцию составляет 2,380 микросекунд, а производительность аналогична случайной записи.

производительность чтения

• Случайное чтение: в среднем каждая операция занимает 16,677 микросекунд, то есть поддерживается около 6 Вт операций произвольного чтения в секунду.
• Последовательное чтение: среднее время на операцию составляет 0,476 микросекунды, то есть поддерживается около 210 Вт операций последовательного чтения в секунду.
• Чтение в обратном порядке: среднее время на операцию составляет 0,724 микросекунды, то есть поддерживается около 130 Вт операций чтения в обратном порядке в секунду.

Вышеуказанная производительность является результатом без включенной функции "сжатие". Если опция "сжатие" включена, производительность будет улучшена. Например, производительность случайного чтения будет улучшена до 11,602 микросекунд, то есть 8,5 Вт раз в секунду.

RocksDB

leveldb от Google — очень хороший движок для хранения, но все еще есть некоторые неудовлетворительные места, такие как leveldb не поддерживает многопоточное слияние, поддержка поиска по диапазону ключей все еще очень проста, никаких мер по оптимизации не предпринималось и так далее.

RocksDB от Facebook — более мощный движок, который на самом деле является улучшением LevelDB и очень похож на LevelDB в использовании.

На современном рынке с открытым исходным кодом существует множество баз данных, которые используют RocksDB в качестве базового механизма хранения, например TiDB.

хранение и поиск

Говоря о реализации LevelDB, я хочу начать с хранения и извлечения данных, а также обсудить эволюцию и различие методов хранения различных структур.

На самом базовом уровне база данных должна уметь делать две вещи:

1. Дайте базе данных некоторые данные, и она должна иметь возможность хранить эти данные.
2. Найдите базу данных, чтобы вернуть эти данные, она должна предоставить вам эти данные.

SimpleDB

Мы пытаемся реализовать простейшую постоянную базу данных KeyValue, которая поддерживает следующие функции:

• Упорство
• set(String key, String value)
• get(String key)

Новый проектSimpleDB, создайте сервер, поддерживающий

• Интерфейс set добавляет полученный ключ и значение в строку JSON структуры KeyValue и добавляет ее в указанный постоянный файл.
• Интерфейс получения сопоставляет соответствующее значение в постоянном файле в соответствии со значением параметра Key.

Set

    @GetMapping(path = "set")
    public String set(@RequestParam("key") String key, @RequestParam("value") String value) {
        if (StringUtils.isEmpty(key) || StringUtils.isEmpty(value)) return "FALSE";
        String recordLine = buildRecordLine(key, value);
        FileUtil.writeString(recordLine, PATH, UTF_8, true);
        return "OK";
    }

Get

    @GetMapping(path = "get")
    public String get(String key) {
        List<String> recordLines = FileUtil.readLines(PATH);
        List<Record> targetRecords = recordLines.stream()
                .map(line -> JsonUtil.decodeJson(line, Record.class))
                .filter(record -> key.equals(record.getKey()))
                .collect(Collectors.toList());
        return CollectionUtils.isEmpty(targetRecords) ? null : targetRecords.get(targetRecords.size() - 1).getValue();
    }

использовать

Выполните следующий запрос набора

http://localhost:8080/set?key=name&value=yuming
http://localhost:8080/set?key=age&value=24
http://localhost:8080/set?key=name&value=yuming2

Сохранять содержимое файла

{"key":"name","value":"yuming"}
{"key":"age","value":"24"}
{"key":"name","value":"yuming2"}

Выполните следующий запрос на получение

http://localhost:8080/get?key=name
http://localhost:8080/get?key=age

Ответ

yuming2
24

Анализировать операции записи

Операция set очень проста, запрос добавляется в постоянный файл, так как он записывается последовательно, эффективность будет очень высокой.

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

одновременная запись

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

    private static ExecutorService executorService = Executors.newSingleThreadExecutor();


    /**
     * set接口将收到的Key和Value拼接成KeyValue结构的JSON字符串追加到指定持久化文件中
     *
     * @param key
     * @param value
     * @return
     */
    @GetMapping(path = "set")
    public String set(@RequestParam("key") String key, @RequestParam("value") String value) {
        if (StringUtils.isEmpty(key) || StringUtils.isEmpty(value)) return "FALSE";
        String recordLine = buildRecordLine(key, value);
        Future<?> future = executorService.submit(() -> FileUtil.writeString(recordLine, PATH, UTF_8, true));
        try {
            future.get();
            return "OK";
        } catch (Exception e) {
            LOGGER.error("writeString error", e);
            return "FALSE";
        }
    }

Анализ операций чтения

Давайте еще раз посмотрим на операцию Get. Поскольку каждый запрос должен пройти через весь файл журнала (O(n)), когда файл журнала становится все больше и больше, производительность операции Get не оптимистична.

Можно ли оптимизировать

Первая идея - добавить ли кеш, но по мере увеличения объема данных памяти явно не хватает.

Если горячих данных много, то большая часть ключей будет перезаписана быстро, и даже мы обеспечим метод удаления (добавление строки с нулевым значением, а затем сжатие потока для последующей обработки). пар KeyValue не так уж и много, можно ли использовать кеш?Сукно?

В этом случае первым делом нужно решить проблему согласованности данных в кеше и содержимом файла.

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

Redis

Redis хранит данные непосредственно в памяти и добавляет данные в файлы журналов для сохранения.Файлы журналов используются только для восстановления данных при запуске (последовательное чтение и выполнение только один раз).

Таким образом, мы можем гарантировать Redis:

• Операции записи, сначала запись в память, а затем последовательная запись на диск, быстрая
• Операция чтения, поиск прямо в памяти, быстро

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

• Сложные и эффективные структуры данных на основе памяти
• Единый поток обработки для сериализации

Как сжать лог-файлы

1. Прочитайте исходный файл журнала и сожмите его, чтобы создать новый файл.
2. Новый файл журнала создается непосредственно в памяти данных

показатель

Не все сценарии могут хранить все данные в памяти, поэтому нам все еще нужно изучить, есть ли другие решения.

Чтобы эффективно искать значение определенного ключа в базе данных, нам нужна структура данных: индекс.

Общая идея индексации состоит в том, чтобы сохранить некоторые дополнительные метаданные в качестве путевых точек, чтобы помочь вам найти нужные данные. Если вы хотите искать одни и те же данные несколькими разными способами, вам могут понадобиться разные индексы, построенные на разных частях данных.

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

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

Это важный компромисс в системах хранения: правильно подобранные индексы ускоряют запросы на чтение, но каждый индекс замедляет запись. По этой причине база данных не индексирует все по умолчанию и требует, чтобы вы вручную выбрали индекс, исходя из ваших знаний о шаблонах запросов приложения. Вы можете выбрать тот индекс, который обеспечивает наибольшую пользу для вашего приложения, не увеличивая накладные расходы, чем это необходимо.

хэш-индекс

Мы продолжаем оптимизировать нашу SimpleDB, мы обсуждали кэширование операций чтения ранее и упоминали, что кэширование памяти для всех данных недоступно.

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

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

Поскольку мы не можем частично кэшировать, можем ли мы сжать наш кеш.

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

Такая структура, которую мы строим, на самом деле является хеш-индексом.

Такой механизм хранения идеально подходит для ситуаций, когда значение каждого ключа часто обновляется. Например, ключ может быть URL-адресом видео, а значением может быть количество раз, когда оно было воспроизведено (увеличивается каждый раз, когда кто-то нажимает кнопку воспроизведения).

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

компрессия

До сих пор мы писали только добавления к файлу — так как же нам избежать в конечном итоге нехватки места на диске? Хорошее решение — разделить журнал на сегменты определенного размера, закрыть текущий файл сегмента, когда журнал вырастет до определенного размера, и начать запись в новый файл сегмента.

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

Кроме того, поскольку сжатие часто делает сегменты очень маленькими (при условии, что ключи в среднем перезаписываются в сегменте несколько раз), мы также можем объединить несколько сегментов во время сжатия, как показано на рисунке ниже. Сегменты никогда не изменяются после записи, поэтому объединенные сегменты записываются в новый файл.

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

Зачем использовать журнал добавления вместо перезаписи старого значения

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

ограничение

• Хеш-таблица должна помещаться в памяти, и, в принципе, можно хранить хеш-карту на диске, но, к сожалению, хэш-карты на диске плохо работают. Он требует большого количества операций ввода-вывода с произвольным доступом, его рост обходится дорого, когда он заполняется, а коллизии хэшей требуют много логики.
• Запросы диапазона неэффективны. Например, все ключи между kitty00000 и kitty99999 не могут быть легко отсканированы — вам нужно искать каждый ключ отдельно в хэш-карте.

SSTable

Использование хэш-индекса Когда данных много, мы не можем поместить все данные индекса в память, поэтому можем ли мы хранить только часть индекса? Судя по предыдущей файловой структуре явно не поддерживается. Если содержимое нашего файла упорядочено, можем ли мы сохранить только часть индекса?

Мы можем внести простое изменение в формат файла сегмента: мы требуем, чтобы последовательность пар ключ-значение была отсортирована по ключу. На первый взгляд кажется, что это требование лишает нас возможности использовать последовательную запись.

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

1. Объединение сегментов выполняется просто и эффективно, даже если размер файла превышает объем доступной памяти. Этот подход подобен тому, который используется в алгоритме сортировки слиянием, как показано на следующей диаграмме: вы начинаете читать входные файлы рядом, просматривая первый ключ в каждом файле, копируя младший ключ (в соответствии с порядком сортировки). в выходной файл и повторите. Это создает новый объединенный файл сегмента, также отсортированный по ключу.

Что делать, если один и тот же ключ появляется в нескольких входных сегментах? Помните, что каждый сегмент содержит все значения, записанные в базу данных за определенный период времени. Это означает, что все значения в одном входном сегменте должны быть новее, чем все значения в другом сегменте (при условии, что мы всегда объединяем соседние сегменты).

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

Тем не менее, вы знаете разницу между сумочкой и красивым, и из-за функции заказа вы знаете, что между ними должна быть ручная работа. Это означает, что вы можете перейти к смещению сумки и сканировать оттуда, пока не найдете ручную работу (или нет).

Вам по-прежнему нужен индекс в памяти, чтобы указать смещение некоторых ключей, но он может быть разреженным: достаточно одного ключа на каждые несколько килобайт файла сегмента, так как несколько килобайт можно просканировать очень быстро. 3. Поскольку запрос на чтение в любом случае должен сканировать несколько пар ключ-значение в запрошенном диапазоне, эти записи могут быть сгруппированы в блоки и сжаты (заштрихованы на изображении выше) перед записью на диск (показана область).

Каждая запись индекса в разреженной памяти указывает на начало сжатого блока. Помимо экономии места на диске, сжатие также может снизить использование полосы пропускания ввода-вывода.

Создавайте и обслуживайте SSTables

написать

Пока что, но как сначала отсортировать данные по ключу? Наши входящие записи могут происходить в любом порядке.Можно поддерживать упорядоченные структуры на диске (см. «B-деревья»), но гораздо проще хранить их в памяти. Можно использовать множество хорошо известных древовидных структур данных, таких как красно-черные деревья или деревья AVL. Используя эти структуры данных, вы можете вставлять ключи в любом порядке и читать их в отсортированном порядке.

Теперь мы можем сделать наш механизм хранения двигателем следующим образом:

При записи он сначала добавляется в хранящуюся в памяти сбалансированную древовидную структуру данных (например, красно-черное дерево). Это дерево памяти иногда называют memtable.

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

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

Процессы слияния и уплотнения выполняются в фоновом режиме для объединения файлов сегментов и удаления перезаписанных или удаленных значений.

Эта схема работает хорошо. Он страдает только одной проблемой: в случае сбоя базы данных самые последние записи (в таблицах памяти, но еще не записанные на диск) будут потеряны. Чтобы избежать этой проблемы, мы можем вести отдельный журнал на диске, где каждая запись немедленно добавляется на диск.

Журнал не отсортирован, но это не имеет значения, потому что его единственная цель — восстановить memtable после сбоя. Всякий раз, когда memtable записывается в SSTable, соответствующий журнал может быть удален.

читать

Чтение данных из LevelDB на самом деле не сложно.Memtable и imm больше похожи на двухуровневые кэши.Они обеспечивают более быструю скорость доступа в память.Если значение ответа можно получить непосредственно из этих двух мест в памяти,то они должны быть самыми последними данными .

LevelDB всегда сначала записывает новые пары ключ-значение и удаляет исторические данные при сжатии данных.

Данные читаются в порядке MemTable, Immutable MemTable и SSTables разных уровней.Первые две находятся в памяти, а SSTables разных уровней постоянно хранятся на диске в виде файлов *.ldb.Именно потому, что являются различными уровнями SSTables, которые наша база данных называется LevelDB.

Когда LevelDB не находит соответствующие данные в памяти, он будет искать в SSTables нескольких уровней на диске.Этот процесс немного сложнее.LevelDB будет искать на нескольких уровнях уровень за уровнем, и ни один из этих уровней не будет пропустить.

В процессе поиска задействована очень важная структура данных FileMetaData:

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

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

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

Затем определите, содержит ли текущий SSTable ключ запроса.Если он не существует, продолжайте поиск следующего уровня, пока не будет запрошен последний уровень kNumLevels (по умолчанию уровень 7) или соответствующее значение.

Дерево LSM (дерево слияния с логарифмической структурой)

Алгоритмы, описанные здесь, по сути являются библиотеками механизма хранения ключей и значений, используемыми в LevelDB и RocksDB, предназначенными для встраивания в другие приложения. Кроме того, LevelDB можно использовать в Riak как замену Bitcask. Подобные механизмы хранения используются в Cassandra и HBase, оба вдохновлены документацией Google Bigtable (которая представила SSTable и memtable).

Эта структура индекса была первоначально описана Патриком О'Нилом и соавт. Файловая система с лог-структурой, созданная на основе предыдущей работы, основанная на лог-структурированном дереве слияния (или LSM-дереве). Механизмы хранения, основанные на этом принципе объединения и сжатия отсортированных файлов, часто называют механизмами хранения LSM.

Lucene, система индексирования для полнотекстового поиска, используемая Elasticsearch и Solr, использует аналогичный подход для хранения своих словарей. Полнотекстовое индексирование намного сложнее, чем индексирование по ключу-значению, но основано на аналогичной идее: по заданному слову в поисковом запросе найти все документы (веб-страницы, описания продуктов и т. д.), в которых это слово упоминается. Это достигается с помощью структуры «ключ-значение», где ключом является слово (термин), а значением — список идентификаторов всех документов, содержащих это слово (список статей). В Lucene это сопоставление терминов со списками публикаций хранится в упорядоченных файлах класса SSTable, объединяемых в фоновом режиме по мере необходимости.

оптимизация производительности

Как всегда, большое количество деталей заставляет механизм хранения хорошо работать на практике. Например, при поиске ключей, которых нет в базе данных, алгоритм LSM-дерева может быть медленным: вам нужно проверить memtable, а затем взять все сегменты обратно к самому старому (вероятно, придется читать каждый из них из диск), прежде чем вы сможете определить, что ключ не существует.

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

Существуют также различные стратегии для определения порядка и времени сжатия и объединения SSTables. Самый распространенный вариант – размерное послойное уплотнение. LevelDB и RocksDB используют плоское сжатие (отсюда и название LevelDB), HBase использует многоуровневое сжатие, а Cassandra поддерживает и то, и другое.

При корректировке на уровне масштаба новые и меньшие таблицы SST последовательно объединяются в более старые и большие таблицы SST. При горизонтальном сжатии критические диапазоны разбиваются на более мелкие SSTables, а более старые данные перемещаются на отдельные «уровни», что позволяет выполнять сжатие более поэтапно и использовать меньше места на диске.

Несмотря на множество тонкостей, основная идея LSM-дерева — сохранение серии SSTables, объединенных в фоновом режиме, — проста и эффективна. Он продолжает нормально работать, даже если набор данных намного больше доступной памяти.

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

B-дерево

Только что рассмотренные лог-структурированные индексы постепенно получают признание, но они не являются наиболее распространенными типами индексов. Наиболее широко используемая индексная структура была введена в 1970 году и стала «повсеместной» менее чем через 10 лет. B-деревья выдержали испытание временем. Они являются стандартной реализацией индексов почти во всех реляционных базах данных.

Как и SSTables, B-деревья поддерживают пары ключ-значение, отсортированные по ключу, что позволяет эффективно выполнять поиск ключ-значение и запросы диапазона. Но на этом сходство заканчивается: B-деревья имеют очень разную философию проектирования.

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

Напротив, B-дерево разбивает базу данных на блоки или страницы фиксированного размера, традиционно размером 4 КБ (иногда больше), и может читать или записывать только одну страницу за раз. Этот дизайн ближе к базовому оборудованию, поскольку диски также организованы в виде блоков фиксированного размера.

найти

Каждая страница может быть идентифицирована с помощью адреса или местоположения, что позволяет странице ссылаться на другую страницу — аналогично указателю, но на диске, а не в памяти. Мы можем использовать эти ссылки на страницы для построения дерева страниц, как показано.

Вставить и изменить

Если необходимо обновить значение существующего ключа в B-дереве, выполняется поиск страницы, содержащей ключ, значение на этой странице изменяется, и страница записывается обратно на диск (любые ссылки на страницу остаются действительными). .

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

Алгоритм гарантирует, что дерево останется сбалансированным: B-дерево с n ключами всегда имеет глубину O(log n). Большинство баз данных можно разместить в трех- или четырехуровневом B-дереве, поэтому вам не нужно следовать нескольким ссылкам на страницы, чтобы найти нужную страницу. (Четырехуровневое дерево страниц размером 4 КБ с коэффициентом ветвления 500 может хранить до 256 ТБ.)

Гарантия надежности

Основная базовая операция записи B-дерева заключается в перезаписывании страницы на диске новыми данными. Предполагается, что оверлей не изменяет положение страницы, то есть при перезаписи страницы все ссылки на страницу остаются нетронутыми. Это резко контрастирует с лог-структурированными индексами, такими как LSM-деревья, которые только добавляют файлы (и в конечном итоге удаляют устаревшие файлы), но никогда не изменяют файлы.

redo log

Чтобы сделать базу данных более надежной, B-дерево обычно реализуется с дополнительной структурой данных на диске: предпрограммным журналом (Wal, WRITE-AHEAD-LOG) (также известным как журнал повторов). Это дополнительный файл, который можно применить к странице самого дерева. Этот журнал используется для восстановления дерева B до согласованного состояния, когда база данных восстанавливается после сбоя.

управление параллелизмом

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

Сравнение B-деревьев и LSM-деревьев

Хотя реализации B-деревьев, как правило, более зрелые, чем реализации LSM-деревьев, LSM-деревья также очень интересны благодаря своим характеристикам производительности. Как правило, LSM-деревья быстрее записываются, а B-деревья быстрее читаются. Чтение LSM-деревьев обычно происходит медленнее, потому что им приходится проверять несколько различных структур данных и таблиц SST на разных этапах сжатия.

Преимущества LSM-деревьев

пиши быстро

Индекс B-дерева должен записывать каждую часть данных по крайней мере дважды: один раз в журнал упреждающей записи и один раз в саму страницу дерева (возможно, снова выгружая страницы). Даже если на этой странице было изменено всего несколько байтов, накладные расходы на запись всей страницы сразу. Некоторые механизмы хранения даже перезаписывают одну и ту же страницу дважды, чтобы избежать частичного обновления страницы в случае сбоя питания.

меньше мусора

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

Недостатки LSM-деревьев

компрессионная блокировка

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

степень сжатия

Другая проблема с уплотнением возникает из-за высокой пропускной способности записи: ограниченная пропускная способность диска при записи должна быть разделена между начальной записью (регистрация и сброс memtable на диск) и потоком уплотнения, работающим в фоновом режиме. При записи в пустую базу данных для начальной записи можно использовать всю пропускную способность диска, но чем больше база данных, тем больше пропускная способность диска требуется для сжатия.

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

дела

Одним из преимуществ B-деревьев является то, что каждый ключ существует только в одном месте в индексе, тогда как механизмы хранения с логической структурой могут иметь несколько копий одного и того же ключа в разных сегментах.

Этот аспект делает B-деревья привлекательными в базах данных, которые хотят обеспечить надежную семантику транзакций: во многих реляционных базах данных изоляция транзакций достигается за счет использования блокировок на диапазонах ключей, а в индексах B-деревьев эти блокировки могут подключаться непосредственно к дереву. .

в заключении

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

Среди новых хранилищ данных все более популярными становятся лог-структурированные индексы. Не существует быстрых и простых правил для определения того, какой тип механизма хранения лучше подходит для вашего сценария, поэтому стоит провести некоторые эмпирические испытания.

Ссылаться на

• Страница проекта LevelDB на GitHub
• Результаты исследования RocksDB, «модернизированного» механизма хранения LevelDB
• Когда родился Redis, почему родился LevelDB?
• Designing Data-Intensive Application
• Анализ реализации Bigtable и LevelDB