В этой статье мы подробно рассмотрим, как сделано B+ дерево в распределенной БД Apache Ignite.

На Хабре уже есть пара статей о B-деревьях (раз, два), но они скорее теоретические и даже если и содержат реализацию, то не production ready. От того и возникает интерес поглядеть на реализацию, которую используют в жизни.

Прежде чем читать статью дальше, советую посмотреть лекцию Максима Бабенко, если вы ещё не знаете, что такое B-дерево в теории. А вот глубоко знать Java или проект Apache Ignite не нужно — детали я либо напишу явно, либо спрячу под спойлерами.

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

Учтите, что я не являюсь ведущим разработчиком Apache Ignite и что-то мог неверно понять из кода. Так что за скобки я выношу фразу "на сколько я понял", которую следует мысленно добавить перед каждым утвердительным предложением.

Зачем B+ дерево в Apache Ignite

Apache Ignite это in memory БД, однако с версии 2.1 у неё появился persistent data store — функционал сохранения данных на диск (не имеет ничего общего с persistent data structure). Поэтому понятно зачем нужна структура для внешней памяти, осталось разобраться, почему не выбрали другую.

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

B* и B+* — плотнее лежат на диске, но у них хуже производительность, а т.к. мы храним данные из оперативной памяти, нам важнее производительность.

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

Есть ещё диковинные фрактальные деревья, однако они, по всей видимости, запатентованы и реализованы только в TokuDB.

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

Реализация в крупную клетку

Изначально компания GridGain разработала Apache Ignite, но до ухода в open-source он носил имя компании, поэтому имена некоторых компонентов начинаются с Grid, а других с Ignite. Поэтому GridCursor, но IgniteTree. Иной логики здесь нет.

Код Apache Ignite написан по лекалам Java best practices и каждый класс наследует интерфейс, а то и не один. От интерфейса IgniteTree и начнём пляску. Привожу код без javadoc, для краткости.

public interface IgniteTree<L, T> {
    public T put(T val) throws IgniteCheckedException;

    public void invoke(L key, Object x, InvokeClosure<T> c) throws IgniteCheckedException;

    public T findOne(L key) throws IgniteCheckedException;

    public GridCursor<T> find(L lower, L upper) throws IgniteCheckedException;

    public GridCursor<T> find(L lower, L upper, Object x) throws IgniteCheckedException;

    public T findFirst() throws IgniteCheckedException;

    public T findLast() throws IgniteCheckedException;

    public T remove(L key) throws IgniteCheckedException;

    public long size() throws IgniteCheckedException;

    interface InvokeClosure<T> {
        void call(@Nullable T row) throws IgniteCheckedException;

        T newRow();

        OperationType operationType();
    }

    enum OperationType {
        NOOP,
        REMOVE,
        PUT
    }
}

Интерфейс IgniteTree описывает стандартный набор операций. Обратите внимание, что наличие поиска по диапазону требует провязать листья в список. Бонусом поддерживается произвольная операция над записью — invoke.

Операция put принимает лишь один аргумент типа T без ключа. Вы не найдете объяснения этому в IgniteTree, однако ответ скрывается в заголовке BPlusTree.

public abstract class BPlusTree<L, T extends L> extends DataStructure implements IgniteTree<L, T>

Как видите, значение наследует ключ, поэтому в операции put ключ вычисляют из значения. Это не ограничивает функционал дерева. Мое предположение, что так компактнее хранить set-ы.

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

Теперь посмотрим на код поиска элемента.

/**
 * @param g Get.
 * @throws IgniteCheckedException If failed.
 */
private void doFind(Get g) throws IgniteCheckedException {
    for (;;) { // Go down with retries.
        g.init();

        switch (findDown(g, g.rootId, 0L, g.rootLvl)) {
            case RETRY:
            case RETRY_ROOT:
                checkInterrupted();

                continue;

            default:
                return;
        }
    }
}
/**
 * @param g Get.
 * @param pageId Page ID.
 * @param fwdId Expected forward page ID.
 * @param lvl Level.
 * @return Result code.
 * @throws IgniteCheckedException If failed.
 */
private Result findDown(final Get g, final long pageId, final long fwdId, final int lvl)
    throws IgniteCheckedException {
    long page = acquirePage(pageId);

    try {
        for (;;) {
            // Init args.
            g.pageId = pageId;
            g.fwdId = fwdId;

            Result res = read(pageId, page, search, g, lvl, RETRY);

            switch (res) {
                case GO_DOWN:
                case GO_DOWN_X:
                    assert g.pageId != pageId;
                    assert g.fwdId != fwdId || fwdId == 0;

                    // Go down recursively.
                    res = findDown(g, g.pageId, g.fwdId, lvl - 1);

                    switch (res) {
                        case RETRY:
                            checkInterrupted();

                            continue; // The child page got split, need to reread our page.

                        default:
                            return res;
                    }

                case NOT_FOUND:
                    assert lvl == 0 : lvl;

                    g.row = null; // Mark not found result.

                    return res;

                default:
                    return res;
            }
        }
    }
    finally {
        if (g.canRelease(pageId, lvl))
            releasePage(pageId, page);
    }
}

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

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

В Apache Ignite любят concurrency. Поэтому дерево поддерживает конкурентную модификацию. На момент операции одна страница блокируется, однако другой поток может модифицировать остальную часть дерева так, что потребуется повторное чтение. Причем так процедура может дойти до корня.

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

Теперь посмотрим код добавления элемента.

private T doPut(T row, boolean needOld) throws IgniteCheckedException {
    checkDestroyed();

    Put p = new Put(row, needOld);

    try {
        for (;;) { // Go down with retries.
            p.init();

            Result res = putDown(p, p.rootId, 0L, p.rootLvl);

            switch (res) {
                case RETRY:
                case RETRY_ROOT:
                    checkInterrupted();

                    continue;

                case FOUND:
                    // We may need to insert split key into upper level here.
                    if (!p.isFinished()) {
                        // It must be impossible to have an insert higher than the current root,
                        // because we are making decision about creating new root while keeping
                        // write lock on current root, so it can't concurrently change.
                        assert p.btmLvl <= getRootLevel();

                        checkInterrupted();

                        continue;
                    }

                    return p.oldRow;

                default:
                    throw new IllegalStateException("Result: " + res);
            }
        }
    }
    catch (IgniteCheckedException e) {
        throw new IgniteCheckedException("Runtime failure on row: " + row, e);
    }
    catch (RuntimeException e) {
        throw new IgniteException("Runtime failure on row: " + row, e);
    }
    catch (AssertionError e) {
        throw new AssertionError("Assertion error on row: " + row, e);
    }
    finally {
        checkDestroyed();
    }
}

/**
 * @param p Put.
 * @param pageId Page ID.
 * @param fwdId Expected forward page ID.
 * @param lvl Level.
 * @return Result code.
 * @throws IgniteCheckedException If failed.
 */
private Result putDown(final Put p, final long pageId, final long fwdId, final int lvl)
    throws IgniteCheckedException {
    assert lvl >= 0 : lvl;

    final long page = acquirePage(pageId);

    try {
        for (;;) {
            // Init args.
            p.pageId = pageId;
            p.fwdId = fwdId;

            Result res = read(pageId, page, search, p, lvl, RETRY);

            switch (res) {
                case GO_DOWN:
                case GO_DOWN_X:
                    assert lvl > 0 : lvl;
                    assert p.pageId != pageId;
                    assert p.fwdId != fwdId || fwdId == 0;

                    res = p.tryReplaceInner(pageId, page, fwdId, lvl);

                    if (res != RETRY) // Go down recursively.
                        res = putDown(p, p.pageId, p.fwdId, lvl - 1);

                    if (res == RETRY_ROOT || p.isFinished())
                        return res;

                    if (res == RETRY)
                        checkInterrupted();

                    continue; // We have to insert split row to this level or it is a retry.

                case FOUND: // Do replace.
                    assert lvl == 0 : "This replace can happen only at the bottom level.";

                    return p.tryReplace(pageId, page, fwdId, lvl);

                case NOT_FOUND: // Do insert.
                    assert lvl == p.btmLvl : "must insert at the bottom level";
                    assert p.needReplaceInner == FALSE : p.needReplaceInner + " " + lvl;

                    return p.tryInsert(pageId, page, fwdId, lvl);

                default:
                    return res;
            }
        }
    }
    finally {
        if (p.canRelease(pageId, lvl))
            releasePage(pageId, page);
    }
}

Разница только в том, что после обнаружения позиции код разветвляется на replace и insert. Код remove можно уже не смотреть. Базовый механизм заключается в том, чтобы с повторными попытками пройтись рекурсивно по дереву вместе со специальным объектом в зависимости от операции: Get, Put или Remove.

Invoke работает таким же образом, только операция происходит с копией записи, потом определяется её тип: NOOP — для чтения, REMOVE — для удаления и PUT для обновления или добавления, и затем генерируется соответствующий объект Put или Remove, который применяется к записи в дереве.

Использование

Ниже я подробно рассмотрю два наследника BPlusTree: CacheDataTree и PendingEntriesTree. За бортом остается реализация индексов — это тема для отдельной дискуссии, к которой я пока не готов.

Прежде чем идти дальше, уточню, что местный распределенный map имеет функционал вытеснения и называется IgniteCache — далее просто кеш.

CacheDataTree

CacheDataTree — это отображение нескольких IgniteCache на диск. Сортировка многоуровневая: сперва сортируют по id кеша, чтобы сгруппировать ключи в одном кеше, а потом по хешам.

CacheDataTree не итерируют по диапазону, так как индексы реализованы в наследниках H2Tree extends BPlusTree, поэтому конкретный вид сортировки не важен: для операций put и get хватит любой. Сравнивать же хеши быстрее, чем объекты. Но куда важнее то, что равномерный хеш плотнее заполнит дерево.

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

Использование хешей в дереве поиска не такая странная идея как кажется, её логическое развитие приведет к Hash array mapped trie.

PendingEntriesTree

PendingEntriesTree хранит ключи для данных со временем жизни и используется как set. Сортировка многоуровневая: сперва сортируют по id кеша, чтобы сгруппировать ключи в одном кеше, а затем по времени жизни. Далее идет ещё один раунд сравнения — судя по всему, чисто технический, чтобы различать элементы. По сортировке легко догадаться, что используется этот класс для поиска диапазонов. Это дерево дублирует ключи записей в кеше для вытеснения.

Понять, как это работает отдельное приключение.

@Override public boolean expire(
    GridCacheContext cctx,
    IgniteInClosure2X<GridCacheEntryEx, GridCacheVersion> c,
    int amount
)

private final IgniteInClosure2X<GridCacheEntryEx, GridCacheVersion> expireC =
    new IgniteInClosure2X<GridCacheEntryEx, GridCacheVersion>() {
        @Override public void applyx(GridCacheEntryEx entry, GridCacheVersion obsoleteVer) {
            boolean touch = !entry.isNear();

            while (true) {
                try {
                    if (log.isTraceEnabled())
                        log.trace("Trying to remove expired entry from cache: " + entry);

                    if (entry.onTtlExpired(obsoleteVer))
                        touch = false;

                    break;
                }
                catch (GridCacheEntryRemovedException ignore) {
                    entry = entry.context().cache().entryEx(entry.key());

                    touch = true;
                }
            }

            if (touch)
                entry.context().evicts().touch(entry, null);
        }
    };

cctx.cache().removeEntry(this);

Детали реализации

Работа со страницами в Offheap

Offheap — техника оптимизации ручного управления памятью в языке со сборщиком мусора.

Это миф, что из-за сборщика мусора все тормозит, обычно коллекторы стоят жалкие проценты производительности. Даже большие кучи сами по себе не проблема, т.к. коллекторы работают конкурентно (например CMS и G1 в Java), а у серверов десятки ядер. Конечно, сборщик добавляет непредсказуемых пауз в работу приложения, что важно для игр, но терпимо для базы данных.

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

И тут такое дело, что до появления PDS Apache Ignite позиционировался главным образом как кэш между сервисами и дисковой БД (например Hadoop). Потому мапы в Ignite называются IgniteCache и имеют соответствующий функционал вытеснения. А кеши как раз нарушают гипотезу о поколениях — в них вероятность удаления объекта растет со временем жизни. Потому-то в этом случае Offheap для хранения пользовательских данных улучшает производительность.

Ещё бонусы:

• В offheap проще реализовать структуры вмещающие больше чем Integer.MAX_VALUE элементов.
• Если держать кучу меньше 32ГБ, то ссылки будут весить 4 байта, что экономит несколько гигабайт.
• Так как коллектор строит граф объектов он потребляет память пропорционально их числу. А число объектов пропорционально кучи. Так же коллектор потребляет CPU, которое лучше потратить на сжатие данных например.
• На очень больших кучах, даже если гипотеза о поколениях не нарушается в целом, все равно найдется достаточно много по абсолютной величине старых объектов, которые будут её нарушать.

Поскольку данные потом отправятся на диск, то объекты сериализуют в память напрямую через unsafe, а затем эту область памяти используют под буфер ввода-вывода.

Write Ahead Log

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

Обход узла

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

private int findInsertionPoint(int lvl, BPlusIO<L> io, long buf, int low, int cnt, L row, int shift)
    throws IgniteCheckedException {
    assert row != null;

    int high = cnt - 1;

    while (low <= high) {
        int mid = (low + high) >>> 1;

        int cmp = compare(lvl, io, buf, mid, row);

        if (cmp == 0)
            cmp = -shift; // We need to fix the case when search row matches multiple data rows.

        //noinspection Duplicates
        if (cmp < 0)
            low = mid + 1;
        else if (cmp > 0)
            high = mid - 1;
        else
            return mid; // Found.
    }

    return -(low + 1);  // Not found.
}

if (cmp == 0)
     cmp = -shift;

Список листов

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

Заключение

Поскольку B+ дерева в Apache Ignite молодое по сравнению с другими реляционными БД, получаем необходимый набор для production ready B+ дерева:

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

Автор: SharplEr

Источник