# Calculate bloom filter and page size automatically
Tarantool, Вильданов Эмир, лето-осень 2022
[Link to GSoC project](https://github.com/tarantool/tarantool/wiki/Tarantool-Summer-of-Code-2022-ideas#calculate-bloom-filter-and-page-size-automatically)
## Связанные issues
Bloom filter:
* [Set bloom_fpr automatically #3969](https://github.com/tarantool/tarantool/issues/3969)
Page size **(пока что работа над page size отложена)**:
* [Introduce vinyl_primary_key_page_size #3366](https://github.com/tarantool/tarantool/issues/3366)
* [vinyl: automatic page size based on page cache size #2158](https://github.com/tarantool/tarantool/issues/2158)
* [vinyl: dynamic page size #2128](https://github.com/tarantool/tarantool/issues/2128)
## Описание проблемы
Фильтр Блума -- это вспомогательная вероятностная структура данных, позволяющая уменьшить количество чтений с диска (
особенно несуществующих значений). С принципом работы стандартного и усовершенствованного фильтра (используемого в
Tarantool'e) можно ознакомиться
в [статье](http://algo2.iti.kit.edu/singler/publications/cacheefficientbloomfilters-wea2007.pdf).
Цитата из документации (
раздел "[Хранение данных с помощью vinyl](https://www.tarantool.io/ru/doc/latest/book/box/engines/vinyl/#bloom-filters)"):
> Единственный параметр, который можно менять независимо для каждого индекса, называется vinyl_bloom_fpr (FPR в данном случае означает сокращение от «false positive ratio» – коэффициент ложноположительного срабатывания), который по умолчанию равен 0,05, или 5%. На основе этого параметра Tarantool автоматически строит фильтры Блума оптимального размера для поиска как по полному ключу, так и по компонентам ключа. Сами фильтры Блума хранятся вместе с постраничным индексом в файле .index и кэшируются в оперативной памяти.
Сопоставляется фильтр каждому хранящемуся на диске run'у. В момент восстановления space'а (после перезагрузки
Tarantool'a) или при создании индекса метаинформация (в том числе и фильтры) о run'ах загружается в память.
В данный момент на каждом уровне LSM-дерева всем run'ам сопоставляются bloom-фильтры с одинаковыми fpr. Предполагается,
что данная реализация является не самой эффективной.
## Предложение
Предложение по оптимизации строится на результатах, приведённых
в [статье](https://dl.acm.org/doi/pdf/10.1145/3035918.3064054). Её авторы утверждают, что более оптимальная с точки
зрения уменьшения объёма занимаемой памяти и уменьшения затрат на "паразитное" чтение стратегия заключается в
присваивании разных fpr на разных уровнях. А именно предлагается присваивать fpr прямо пропорционально размеру run'ов на
уровнях LSM-дерева: run'ам на более глубоких уровнях предлагается сопоставлять фильтры с более высоким fpr:
> the optimal FPRs are proportional to the number of entries in each level
Логика такая: на последних уровнях блум-фильтры занимают много места, поскольку размер блум фильтра растёт прямо
пропорционально количеству записей в ран файле. Мы увеличим fpr на нижних уровнях, но уменьшим его на более высоких
уровнях. Мы незначительно проиграем по количеству паразитных чтений с диска на нижних уровнях (незначительно, потому что
при чтении с диска мы пользуемся указателями на конкретную страницу), при этом уменьшим количество ложноположительных
срабатываний фильтра на более высоких уровнях, содержащих самую "свежую" информацию.
## Алгоритм вычисления новых fpr
### Алгоритм из статьи:
Предлагаемый алгоритм основывается на выбранном пользователем параметре R (условные затраты на выполнение операции READ)
, который лежит в диапазоне от 0 до L * (T - 1), где L -- это количество уровней в LSM-дереве, а T -- это параметр
соотношения размеров файлов на каждом уровне
(`vinyl_run_count_per_level` + 1 в Tarantool).
На изображении выше приведены формулы для вычисления оптимальных fpr для соответствующих уровней. Здесь L_filtered и
L_unfiltered -- это число уровней с фильтрами и без соответственно. Значения R = 0 и R = L * (T - 1) соответствуют
случаям, когда фильтрами покрыты все уровни LSM-дерева и когда фильтрами не покрыты никакие уровни.
### Алгоритм, адаптированный под размеры ран файлов:
**NOTE:** [main formula explanation](https://www.khanacademy.org/math/multivariable-calculus/applications-of-multivariable-derivatives/constrained-optimization/a/lagrange-multipliers-examples)
В формуле подразумевается, что последний ран файл имеет наибольший размер. На самом деле, это не всегда так: например, при увеличении значения `vinyl_memory` размер ран файла, образовавшегося после дампа может сильно превысить размеры всех существующих ран файлов.
Однако, если посмотреть, на реализацию функции `vy_range_update_compaction_priority`, можно понять, что в таком случае будет вызван так называемый *major compaction*, то есть все ран файлы объединятся в один:
1. `target_run_size` приравнивается размеру нового ран файла, поскольку`size < first_slice.bytes`;
2. Дойдя до последнего ран файла цикл `while (size > target_run_size)` не совершает итерацию и на последнем уровне оказывается больше одного ран файла.
При обнаружении такого случая на момент вычисления оптимального `bloom_fpr`, достаточно присвоить ран файлу стандартное значение.
Ситуация, когда происходит дамп, а за ним не следует *major compaction* неосуществима при условии, что размер `vinyl_memory` достаточно велик.
## Реализация
Для реализации оптимизации было рассмотрено несколько вариантов, ниже будет приведён конечный вариант. Два варианта
изменений, которые были отмечены как более трудоёмкие и нерациональные будут приведены в конце документа под
заголовком **Первоначальная реализация**.
```c
double
vy_task_find_range_bloom_fpr(
struct vy_lsm *lsm,
struct vy_range *range,
uint64_t new_run_stmts_count,
int W,
uint64_t total_stmts_count,
int skip_n)
{
double R = W * lsm->opts.lookup_cost_coeff;
if (new_run_stmts_count == total_stmts_count) {
/** By definition of R. May also look at formulas ahead.
* R <= 1 in this case as soon as W = 1.
* It also means that skip_n == range->slice_count.
*/
return R;
}
struct vy_slice *last_slice =
rlist_last_entry(&range->slices, struct vy_slice, in_range);
uint64_t last_slice_stmts_count = last_slice->count.rows;
if (new_run_stmts_count > last_slice_stmts_count) {
/** The only case is when the size of dumped run
* is bigger than the size of the last run.
* Returning default bloom_fpr value,
* cause otherwise formula breaks.
* update_compaction_priority will understand that
* major compaction must be called and compaciton will create
* new run with optimal bloom_fpr
*/
return lsm->opts.bloom_fpr;
}
uint64_t scnd_last_slice_stmts_count = 0;
if (skip_n == range->slice_count - 1) {
/** In both dump and compaction cases it means
* we only have the new run except the last run.
*/
scnd_last_slice_stmts_count = new_run_stmts_count;
} else {
struct vy_slice *scnd_last_slice = rlist_prev_entry(
last_slice, in_range);
scnd_last_slice_stmts_count = scnd_last_slice->count.rows;
}
int W_u = 0;
int W_f = 0;
double t_r = 0;
if (R <= (total_stmts_count / last_slice_stmts_count)) {
W_u = 0;
} else {
t_r = (double)scnd_last_slice_stmts_count /
last_slice_stmts_count;
W_u = MAX(0, floor((R - t_r * W) / (1 - t_r)));
}
if (W_u == W) {
/** As soon as all runs should be unfiltered. */
return 1;
}
W_f = W - W_u;
int slice_number = 0;
uint64_t filtered_stmts_count_sum = new_run_stmts_count;
struct vy_slice *slice;
rlist_foreach_entry(slice, &range->slices, in_range) {
if (slice_number++ < skip_n) {
continue;
}
filtered_stmts_count_sum += slice->count.rows;
if (slice_number == W_f) {
break;
}
}
double bloom_fpr = (R - W_u) * new_run_stmts_count /
filtered_stmts_count_sum;
return bloom_fpr;
}
/*
* Logic:
* Let's consider our dump is divided evenly into all lsm ranges.
* So everything we have to do is to find optimized bloom_fpr
* for small dump part in one of lsm ranges.
*
* @param lsm
* @param new_run_stmts_count statements count in the newly created after
* dump run
* @return optimally calculated bloom_fpr for dump
*/
double
vy_task_find_lsm_bloom_fpr(
struct vy_lsm *lsm,
uint64_t new_run_stmts_count)
{
struct vy_range *range = vy_range_tree_first(&lsm->range_tree);
uint64_t part_run_stmts_count = new_run_stmts_count / lsm->range_count;
int W = range->slice_count + 1;
int total_stmts_count = range->count.rows + part_run_stmts_count;
return vy_task_find_range_bloom_fpr(
lsm, range, part_run_stmts_count,
W, total_stmts_count, 0);
}
```
Параметр `new_run_stmts_count` вычисляется в процессе создания нового ран файла и наполнения `vy_stmt_stream` при дампе и слиянии.
### bloom_fpr как пользовательский параметр
Нынешний вариант реализации фильтров Блума позволяет пользователям самим выбрать параметр `bloom_fpr`, который будет
применён при создании фильтров на всех уровнях.
Было принято решение оставить возможность задания данного параметра для одного* конкретного случая: в
функции `vy_lsm_recover_run` при восстановлении LSM-дерева из логов также создаётся новый run, для которого впоследствии
в функции `vy_run_rebuild_index` нужно построить фильтр.
Сейчас параметр `bloom_fpr` в ней берётся из структуры `index_opts`.
В документации необходимо отразить тот факт, что теперь это поле применяется только для одного случая.
Код С:
```c
/** Index options */
struct index_opts {
...
/* Bloom filter false positive rate.
* Used only as default parameter when rebuilding index
* See vy_run_rebuild_index()
*/
double bloom_fpr;
...
}
```
### R как пользовательский параметр
Вместо выбора пользовательского параметра `bloom_fpr` пользователю теперь доступен параметр `lookup_cost_coeff`, который
так же варьируется от 0 до 1.
Код Lua:
* Добавить параметр в `index_options` файла schems.lua;
* Изменить `default_cfg` файла load_cfg.lua;
* Добавить в тесты lua проверку на ограничения по новому параметру.
Код C:
* Добавить проверку в `index_opts_decode` alter.cc;
* Добавить проверку в `box_check_vinyl_options` box.cc;
* Добавить параметр в index_def.c и index_def.h.
### Создание фильтров с fpr, зависящем от уровня
Поскольку главной идей оптимизации является вычисление оптимального параметра fpr для каждого уровня LSM-дерева остаётся
передать новый вычисленный параметр fpr в функцию `tuple_bloom_new`.
### Benchmark
Для проверки работоспособности внесённых изменений потребовалось написать бенчмарк, который проверит:
* Изменилась ли производительность CRUD операций (не должна измениться)
* Изменилось ли потребление оперативной памяти (должно уменьшиться)
Изначально была предпринята попытка переписать [бечмарк](https://github.com/tarantool/tarantool/pull/7083/files)
на чистом C++ от @CuriousGeorgiy. Однако на момент запуска в серии вызовов функций `vy_run_reader_f`, `cpipe_create`
, `cbus_find_endpoint_locked` возникала runtime-ошибка. Есть предположение, что на момент инициализации окружения для
движка vinyl не были вызваны необходимые функции.
В итоге было принято решение
видоизменить [бенчмарк](https://github.com/Korablev77/tarantool/commit/2c3b217b28edf07585161e8e456caf6000e6ea7a) от
@Korablev77, написанный на Lua + C: на Lua проще провести инициализацию окружения, а на C++ провести замеры по времени.
## Зафиксированные трудности
* Размер L0 не фиксирован, даже при дампе L0 с одинаковым параметром vinyl_memory размер получившегося рана может
меняться.
* Размер vinyl_memory должен быть больше чем 100 Mb:
* [code comment](https://github.com/tarantool/tarantool/blob/7ec71b4f6b0a15997553529c8e15c2dd415df44f/src/box/vy_regulator.c#L97-L106)
* > @curiousgeorgiy: у тебя скорость записи в память превышает скорость записи на диск, и в итоге у тебя винил, не успев задампить, начинает триггерить ещё один дамп
## Вопросы и замечания
* **В `dump_new` нет range**
* На самом деле в LSM-дереве несколько ranges. При дампе ран файл попадает во все ranges, которые покрывают его. То
есть для каждого range необходимо добавить ран файл со своим фильтром?
* При coalesce и split вызывается перерасчёт compaction_priority.
* Использование функции MAX можно найти в vy_run.c : "run->info.max_lsn = MAX(run->info.max_lsn, lsn);"
* Использование функции log() можно найти в bloom.c : "ceil(log(false_positive_rate) / log(0.5));"
* Есть ли статистика по тому, насколько высокими могут получаться деревья?
* Вопрос связан с тем, что на примере big_insert получалось так, что до создания уровня L3 не доходило, потому что
дерево делилось на несколько ranges.
* Изучить процесс `vy_run_recover` и `vy_run_info_decode`, чтобы понять, какому range он сопоставляется.
* Бесполезные подсказки:
* > error: 'builtin/box/schema.lua:1821: Use space:select(...) instead of space.select(...)'
* > error: 'builtin/box/schema.lua:1821: Use space:update(...) instead of space.update(...)'
* Иногда логи выводятся в интерактивную строку (после tarantool>)
* Маленькая наблюдаемая скорость дампа:
* > dumping 88667998 bytes, expected rate 200.0 MB/s, ETA 0.4 s, write rate (avg/max) 2.3/24.4 MB/s
## Первоначальная реализация
### Варианты вычисления уровня ран файла и количества уровней в LSM-дереве
Уровни в LSM-дереве, представленные в виде пирамиды -- это лишь абстракция для удобного восприятия этой структуры: по
факту каждый range хранит slice'ы, ссылающиеся на соответствующе run'ы в порядке убывания их lsn в виде массива.
В коде единственное место, где происходит выявление уровня run'а -- это функция `vy_range_update_compaction_priority`:
```c
...
while (size > target_run_size) {
/*
* The run size exceeds the threshold
* set for the current level. Move this
* run down to a lower level. Switch the
* current level and reset the level run
* count.
*/
level_run_count = 1;
...
```
На данный момент предложено два варианта по определению уровня конкретного ран файла и количеству уровней в дереве:
1. Скопировать логику определения уровня из функции выше в место, где происходит создание нового ран файла:
1. Поскольку размер дампов L0 не равен размеру `vinyl_memory` (из-за затрат на вспомогательные структуры данных) и
не зафиксирован (из-за того, что от запуска к запуску пользователь может изменять параметр `vinyl_memory`),
необходимо высчитывать его с помощью скользящего среднего и сохранять в логах информацию о размере L0.
2. С помощью вычисленных из алгоритма значений `target_run_size` и `last_run_size` (можно получить напрямую из
slice'a) найти значения `run_level_number` и `tree_levels_number` по формулам:
1. `run_level_number = ceil(log(target_run_size / L0_size, run_size_ratio))`
2. `tree_levels_number = ceil(log(last_run_size / L0_size, run_size_ratio))`
2. Воспользоваться полем `dump_count` у класса `vy_run`:
1. Поскольку это поле фиксирует количество дампов, которое необходимо совершить для получения конкретного ран файла,
можно получать значение `run_level_number` по
формуле `run_level_number = ceil(log(run->dump_count, run_size_ratio))`.
2. Аналогично значение `tree_levels_number` можно получить по
формуле `run_level_number = ceil(log(last_run->dump_count, run_size_ratio))`.
У обоих вариантов есть свои недостатки:
| Вычисление с помощью `target_run_size` | Вычисление с помощью `dump_count` |
|-----------------------------------------------------------------------------------------------------------------------------------|----------------------------------------------------------------------------------------|
| Погрешность вычисления `target_run_size` и `L0_size` | Зависимость* от погрешности вычислений в функции `vy_range_update_compaction_priority` |
| Необходимость добавления в классы, связанные с LSM-деревьями, новых полей для работы с параметрами `L0_size` и `tree_levels_number` | Особый** алгоритм вычисления `dump_count` последнего уровня дерева |
| Необходимость сохранения в .xlog файлы информации о новых полях для обеспечения персистентности | |
*Поле `dump_count` обновляется в функции `vy_task_compaction_new` на основании вычисленного в
функции `vy_range_update_compaction_priority` показателя `compaction_priority`.
**Из документации:
```c
* If the run was produced by a major compaction, it
* is is the sum of dump counts of compacted runs
* minus the dump count of the last (greatest) run.
```
Поскольку на последнем уровне всегда хранится только один ран файл и поскольку при слиянии вычитается
показатель `dump_count` последнего ран файла может возникнуть следующая ситуация:
Можно заметить, что при применении формулы вычисления уровня для последнего ран файла получится значение 2, что не
соответствует действительности.
### Присвоение run'ам уровня
В ходе работы движка vinyl новый для записи ран файл создаётся в следующих местах:
1. при осуществлении dump'а через вызов функции `vy_task_dump_new`;
2. при слиянии нескольких run'ов через вызов функции `vy_task_compaction_new`;
[//]: # (3. при восстановлении run'а в функции `vy_lsm_recover_run`;)
[//]: # (4. при вызове функции `vy_run_prepare` через ``)
[//]: # (5. при тестировании в функции `test_basic`)
В обоих случаях логика исполнения задач (task'ов) разделяется на несколько этапов:
1. Подготовительный, где task инициализируется необходимой информацией;
2. `.execute`, где происходит процесс создания нового run путём вызова функции
`vy_task_write_run`;
3. `.complete`, где, например, происходит работа с логами.
Функция по вычислению оптимального fpr:
```c
double
vy_task_calculate_optimal_bloom_fpr(struct vy_lsm *lsm,
/* Подход 1. */
uint64_t target_run_size
/* Подход 2. */
uint32_t run_dump_count,
uint32_t levels_number) {
/* Подход 1. */
uint32_t levels_number = lsm->levels_number;
uint64_t run_level = log_a_to_base_b(target_run_size / lsm->L0_size, lsm->opts.run_size_ratio);
/* Подход 2. */
uint64_t run_level = log_a_to_base_b(run_dump_count, lsm->opts.run_size_ration);
double R = (levels_number * lsm->opts.run_count_per_level) / 2;
uint32_t L_filtered = levels_number - max(0, (int)((R - 1) / lsm->opts.run_count_per_level));
if (run_level > L_filtered) {
return 1;
}
uint32_t L_unfiltered = levels_number - L_filtered;
return (R - L_unfiltered * lsm->opts.run_count_per_level) / (pow(lsm->opts.run_count_per_level, L_filtered + 1 - run_level));
}
```
Предложенные варианты изменений:
#### С помощью `target_run_size`:
1. Создать в структурах `vy_lsm_recovery_info`, `vy_log_record` и `vy_lsm` новые поля:
```c
/** Size of L0 dump. */
uint64_t L0_size;
/** Number of levels in LSM-tree. */
uint32_t levels_number;
```
**ЗАМЕЧАНИЕ:** Нужно персистить уровень не LSM-дерева, а каждого его range'a, поскольку именно они представляют собой
отдельные деревья. Выглядит так, будто это дороговато.
2. Добавить в файл *vy_lsm.c* функцию `vy_lsm_update_L0_size` по пересчёту `L0_size` с помощью скользящего среднего.
3. Поддержать сохранение информации об `L0_size` и `levels_number` в записи `VY_LOG_DUMP_LSM` и её последующее
восстановление:
```c
enum vy_log_key {
VY_LOG_KEY_L0_SIZE = 17,
VY_LOG_KEY_LEVELS_NUMBER = 18,
};
vy_log_record_decode(struct vy_log_record *record,
struct xrow_header *row)
{
case VY_LOG_KEY_L0_SIZE:
record->L0_size = mp_decode_uint(&pos);
break;
case VY_LOG_KEY_LEVELS_NUMBER:
record->levels_number = mp_decode_uint(&pos);
break;
}
vy_recovery_dump_lsm(struct vy_recovery *recovery,
int64_t L0_size, int32_t levels_number)
{
...
lsm->L0_size = L0_size;
lsm->levels_number = levels_number;
}
case VY_LOG_DUMP_LSM:
rc = vy_recovery_dump_lsm(recovery, record->lsm_id,
record->L0_size, record->levels_number);
struct vy_log_record {
...
/** Size of L0 dump. */
uint64_t L0_size;
/** Number of levels in LSM-tree. */
uint32_t levels_number;
};
struct vy_lsm_recovery_info {
...
/** Size of L0 dump. */
uint64_t L0_size;
/** Number of levels in LSM-tree. */
uint32_t levels_number;
};
vy_log_dump_lsm(int64_t id, int64_t dump_lsn,
int64_t L0_size, int32_t levels_number) {
record.L0_size = L0_size;
record.levels_number = levels_number;
}
```
4. Для каждого случая создания ран файла посчитать два параметра `run_level_number` и `tree_levels_number`:
- В случае дампа:
```c
vy_lsm_update_L0_size(lsm, new_run_size);
if (lsm->levels_number == 0) {
lsm->levels_number = 1;
}
uint64_t target_run_size = lsm->L0_size * lsm->opts.run_size_ratio;
task->bloom_fpr = vy_task_calculate_optimal_bloom_fpr(lsm, target_run_size);
```
Где `new_run_size` вычисляется из размера участков памяти, с которых и будет происходить дамп:
```c
uint64_t new_run_size = 0;
rlist_foreach_entry(mem, &lsm->sealed, in_sealed) {
...
new_run_size += mem->count.bytes;
}
```
- В случае слияния:
```c
uint64_t target_run_size;
uint64_t size;
struct vy_slice *last_slice;
struct vy_slice *first_slice;
last_slice = rlist_last_entry(&range->slices, struct vy_slice, in_range);
size = MAX(last_slice->count.bytes, 1);
first_slice = rlist_first_entry(&range->slices, struct vy_slice, in_range);
do {
target_run_size = size;
size = DIV_ROUND_UP(target_run_size, lsm->opts.run_size_ratio);
} while (size > (uint64_t)MAX(first_slice->count.bytes, 1));
...
lsm->levels_number = log_a_to_base_b(last_slice->count.bytes / lsm->L0_size, lsm->opts.run_size_ratio);
task->bloom_fpr = vy_task_calculate_optimal_bloom_fpr(lsm, target_run_size);
```
#### С помощью `dump_count`:
И в случае дампа, и в случае слияния передать в функцию значения `dump_count` и `levels_number`:
```c
...
struct vy_slice *last_slice = rlist_last_entry(&range->slices, struct vy_slice, in_range);
uint32_t levels_number = log_a_to_base_b(last_slice->run->dump_count, lsm->opts.run_size_ratio);
task->bloom_fpr = vy_task_calculate_optimal_bloom_fpr(lsm, new_run->dump_count, levels_number);
...
```
**ЗАМЕЧАНИЕ**: в функции `vy_task_dump_new` мы не работаем с конкретным `range`. Нужно назначать ран файлу дефолтное
значение fpr, которое поменяется на этапе слияния.
Sign in with Wallet
Connect another wallet