Akumuli: запись и хранение данных

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

Как известно, данные на диске можно хранить в различных B-деревьях, это такая структура данных, которая позволяет искать по ключу за логарифмическое время, но в тоже время - читая минимальное количество страниц памяти с диска. Для хранения time series данных, умные люди очень давно придумали TSB tree и некоторые другие структуры данных на основе B-tree.

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

Я ввел одно ограничение, которое в принципе можно обойти, но которое очень упрощает жизнь - ограничил late writes. Это означает, что библиотека не позволяет записывать сильно устаревшие данные, размер окна записи задается в конфигурации, а также, может меняться динамически. В случае, если нагрузка слишком большая, окно записи может уменьшаться, снижая нагрузку. Это ограничение позволило мне использовать более простую структуру для хранения данных.

Persistent storage

Итак, данные в akumuli хранятся в томах, размер каждого тома - 4Гб. Все тома создаются заранее, при создании хранилища, и образуют циклический список. В любой момент времени мы можем писать только в один том. При этом, метки времени в соседних томах могут пересекаться. На высоком уровне, алгоритм записи выглядит очень просто - мы пишем в открытый том до тех пор, пока он не заполнится, затем, открываем следующий и пишем в него. Если в следующем томе есть данные - они теряются. Вы уже наверное поняли, что глубина хранения данных определяется размером хранилища, новые данные просто перезатирают самые старые, также как в rrd-tool. Это осмысленное решение а не недостаток дизайна, оно не позволяет задавать глубину хранения для каждого параметра в отдельности, но зато, позволяет писать софт, который работает предсказуемо, не падая от нехватки места на диске. 

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

Данные записываются начиная с конца тома, в обратном направлении. На изображении, смещения увеличиваются слева направо, при этом элемент данных "А" был добавлен первым, "В" - вторым, а "С" - третьим. В массив смещений записываются смещения элементов данных (как неожиданно!). Причем смещения, как раз записываются в прямом порядке.
На изображении, элемент массива с индексом 0 содержит смещение элемента "А" и был добавлен первым. Запись в том заканчивается тогда, когда массив смещений и данные встречаются, т.е. между последним добавленным элементом массива данных и последним смещением не достаточно места для добавления следующего элемента данных.

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

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

In-memory cache

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

Кэш в памяти у меня построен на основе B-tree (реализация гугла), в качестве ключа используется кортеж из метки времени и ид-ра параметра, значение - смещение элемента в томе. Б-деревья выбраны не случайно, time-series данные имеют одну особенность, метка времени как правило возрастает, это значит, что данные в B-tree добавляются почти всегда в порядке возрастания, а это sweet spot для B-tree. Режим, в котором вставка в B-tree выполняется очень быстро.

Кэш организован следующим образом, данные хранятся в bucket-ах (штука, которая содержит внутри себя дерево и кое какую метаинформацию). Каждый такой bucket отвечает за небольшой интервал времени, кратный глубине окна записи, эти интервалы не пересекаются. Bucket-ы объединены в список, в хронологическом порядке. Устаревшие bucket-ы, запись в которые уже запрещена (они вышли за границу окна записи), извлекаются из конца списка по очереди, их содержимое перебирается в порядке возрастания и получившаяся последовательность смещений записывается в соответствующий сектор массива смещений тома. Future write приводит к созданию нового bucket-а (на самом деле не созданию, а извлечению готового из пула, zero allocation).

Concurrency

В кэш можно писать параллельно из нескольких потоков, чем больше потоков пишут в один bucket, тем больше lock contention и тем все медленнее. Чтобы решить эту проблему, bucket содержит не одно дерево, а несколько, по количеству процессоров/ядер. Каждый поток сначала выбирает свой экземпляр B-tree из bucket-а, лочит его, а затем - пишет в него. Это уменьшает contention и улучшает cache locality, в общем, все работает лучше. При сохранении последовательности смещений на диск, последовательности, полученные от отдельных деревьев сливаются в одну, а уже потом - записываются в том.

Comming soon

В следующей статье я постараюсь описать то, как выполняется поиск.