SDCast #44: в гостях Евгений Лазин, программмист, автор проекта akumuli

sd-podcast-logo Рад представить вам 44-й выпуск SDCast’а! У меня в гостях Евгений Лазин, программист, автор проекта Akumuli. Основной темой этого выпуска являются БД для хранения временных рядов (Time-series DB, TSDB).

В начале мы обсудили общие вопросы, такие как: зачем нужны tsdb, чем они отличаются от привычных всем реляционных баз данных, какие у них особенности и основные области применения.

Базы данных типа TSDB широко применяются в мониторинге для хранения разного рода метрик, привязанных ко времени. Поэтому мы пообщались так же на тему мониторинга: что такое мониторинг, что является единицей мониторинга, зачем нужна связь со временем, какие есть инструменты мониторинга, зачем нужен time series db, и чем не подходят привычные способы хранения данных.

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

Обсудили и общие вопросы open source проекта: внешнее API, документация, тестирование и покрытие кода, есть ли интерес у сообщества.

Ссылки на ресурсы по темам выпуска:

Скачать (mp3, 30 MB) Скачать (ogg, 35 MB)
  • Денис Иванов

    Оч круто. Сдержано, с техническими деталями, без категоричности.
    Спасибо обоим ! :)

  • Antony

    Качественный материал.

  • Vadim

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

    Я 3 раза прослушал, и… все равно единой картины не получилось построить :)))))
    Пожалуйста, скажите что не так я понял, получается что

    Прихоодят на сервер некие данные в виде “метрика,пользователь,значение,время”. Эти данные собираются, по истечению некого времени или по достижению лимита, сжимаются методом статического дерефа Хаффмана, делятся на 4 Кб и сбрасываются в 4 Гб файл путем отображения файла в памяти (понятно, что не всего 4 Гб, но за счет некого скользящего окна). Эти буферы записываются в конец файла (т.е. APPEND) в структуру листа дерева B+ tree, которое реализовано в виде массива (а не связанного списка). При этом некая метаинформация записывается в начало файла. На ветках этого дерева располагаются значения метрик (min/max) для ускорения поиска нужных данных.

    Если для 1 метрики может быть много файлов, то получается чтобы на графике показать ее значения, нужно открыть все 4 Гб файлы ?
    Если буфер сжимается, разбивается на несколько chunk-ов, то как можно из них получить значения метрик, декодировать ? Получается что нужно будет заново собрать воедино их в 1ый буфер.
    Что есть метаинформация, которая берется из буфера/chunk-а и записывается в начало файла ? И как может записываться в начало, ведь там, видимо, будет корень.
    Правильно ли я понял, место, где используется алгоритм Хаффмана ? И где хранится таблица ассоциаций между символом и кодом ?

    • Евгений Лазин

      Должно быть так получилось из-за того, что я рассказывал о двух версиях – текущей и перспективной.

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

      Изначально, данные в скользящем окне сортируются по метке времени и затем по идентификатору серии (чтобы можно было выбрать N-секунд самых старых данных и сбросить их на диск). Перед сжатием они сортируются наоборот, сначала по идентификатору а затем по метке времени и затем сжимаются (это нужно для того чтобы лучше сжать данные и чтобы можно было более эффективно читать данные одного временного ряда). Естественно, эти блоки получаются разного размера, размер блока зависит от того, сколько данные пришло за заданный интервал времени. Смещение каждого записанного блока сохраняется в начале файла как описано тут – http://akumuli.org/akumuli/2015/02/01/storage_pt1/. Это нужно для того, чтобы к ним можно было обращаться по индексу.

      Тут появляются следующие недостатки: зависимость от mmap (все тома отображаются в память одновременно, поэтому akumuli работает только на х86_64, иначе адресного пространства не хватит), общее скользящее окно для записи (отдельный временной ряд не может запаздывать относительно остальных, иначе не будет записан), низкая скорость чтения временных рядов по одному, если временных рядов очень много или они короткоживущие. Еще эта схема плохо масштабируется по потокам. Также плохо обстоят дела с вычисление агрегатов, я сначала хотел сделать как в graphite, но это очень негибко и работает лишь в простейших случаях, в общем – лишено всякого смысла. Поэтому я начал двигаться в сторону нового движка хранения – на основе B+tree.

      Это Б+ дерево как раз пишет на диск блоки по 4КБ и хранит на ветках всякие агрегаты (min/max/sum/count). От обычного Б+ дерева эта реализация отличается еще тем, что не переписывает ничего на диске, данные только добавляются в конец (это упрощает concurrency control, по сути это MVCC) и данные из дерева не удаляются обычным образом, вместо этого старые тома просто удаляются целиком, при этом Б+ дерево может понять что какие-то ссылки ведут в этот удаленный том и по ним не нужно переходить при обходе дерева/поиске и прочих операциях. Тут уже не используется mmap, каждый временной ряд это отдельное дерево (в одном хранилище их может быть очень много), поэтому доступ к отдельному временному ряду всегда выполняется быстро. Данные в разные временные ряды можно записывать независимо и параллельно, из разных потоков.

      Алгоритм Хаффмана не используется, это было один из рассматриваемых вариантов, но в итоге я остановился на DeltaRLE + LEB128 для меток времени и алгоритме на основе FCM предиктора для float-ов. Недавно протестировал алгоритмы сжатия с помощью american fuzzy lop.

      • Vadim

        Спасибо большое, что ответили.
        Правильно ли я понял, что для случая B+tree 4Гб файл содержит блоки по 4Кб, которые состоят из узлов. Узлы могут быть как ветвями (агрегаты + ссылки на след. узлы), так и листьями (содержат значения метрик). Узлы в 1 блоке могут относиться к разным временным рядам (например, в пределах 1сек, 500 мс и т.д.), причем, если данных пришло много, и у нас осталось свободного места в размере 4Кб, то возможна такая ситуация, что узлы из одного и того же временного ряда будут находиться в разных блоках разных файлов.

        P.S. тема очень крутая, удачи вам !

        • Евгений Лазин

          >> Правильно ли я понял, что для случая B+tree 4Гб файл содержит блоки по 4Кб, которые состоят из узлов

          Не совсем. Каждый 4Гб файл содержит блоки по 4КБ, но эти блоки могут принадлежать множеству разных B+tree. При этом B+tree может хранить свои данные в множестве таких 4х гигабайтных файлов. И блоки не состоят из узлов, каждому узлу дерева соответствует ровно один блок, либо лист, либо внутренний узел. В лист помещается переменное количество измерений, а во внутренний узел – 32 ссылки на нижележащие узлы или листья. Как-то так. Я этот формат когда-нибудь задокументирую, когда он стабилизируется.

  • IvanKorjavin

    С большим опозданием прослушал последние несколько эпизодов.

    Отличные дискуссии, хоть переслушивай.

    Спасибо вам.

  • Roman Rusakov

    Спасибо, очень круто и полезно было послушать. Удачи проекту!