Посмотрел "доклад", смотреть не рекомендую, потому что по сути пара тезисов, но достаточно интересных.

firebolt -- стартап, аналог этих ваших snowflake, google bigquery, amazon redshift, etc.

Сделано изначально полностью из сторонних компонентов (на докладе был вопрос, который позиционировал это как минус, как по мне скорее наоборот):
file storage: s3
disk/in memory indexes/cache/query single node runtime: ClickHouse
query parser and planner: Hyrise
metadata storage: FoundationDB
provision и orchestration: Terraform и Kubernetes
Утверждается, что постепенно дописывают под свои нужды.

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

Кстати возможно, если бы делали сейчас вместо ClickHouse + Hyrise, взяли бы DuckDB
Из того что я видел query engine DuckDB показался мне более продуманным + оно postgres совместимое (что кстати тоже тренд, и одна из причин почему они утверждают, что отказались от query engine ClickHouse).

Ещё интересный момент это FoundationDB, не первый раз встречаю ее как сторадж метаданных. В общем вклад в тестирование (там изначально делали со встроенным fault injection фреймворком) приносит свои плоды.

А ещё упомянули две классные статьи
https://github.com/cwida/fsst -- про сжатие строк, вот тут можно почитать https://www.group-telegram.com/experimentalchill/128

https://github.com/google/cuckoo-index прикольное развитие идеи cuckoo фильтров.
Любопытно что авторы утверждают что с xor фильтр https://arxiv.org/pdf/1912.08258.pdf не взлетит.
Вообще как по мне основная проблема то что per stripe (кусок данных, file в lsm tree например, обычно конечно он внутри тоже поделен) тупо лучше в случае high cardinality.
И не очень понятно как принимать такие решения автоматически? Можно наверное строить всегда CI, а если видно что в какой-то stripe будет dense делать xor filter, и выкидывать ее из общего CI?
delete поддерживаются довольно тривиально, а само действие можно делать на compaction

Прочитал статью, первый раз столкнулся с таким явным вариантом рекурсивного сжатия https://15721.courses.cs.cmu.edu/spring2024/papers/03-data2/kuschewski-sigmod23.pdf

Как по мне идея прикольная и достаточно простая:
1) Возьмём несколько простых и хороших алгоритмов сжатия, применим лучший из них
2) Затем сделаем тоже самое к получившимся данным
3) Делаем так пока это имеет смысл

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

Собственно в пейпере предлагается применять только к 1% данных от 64k энтрей в колонке, утверждается что получается при этом весьма хорошо.

Вообще если вы не очень знакомы с открытыми форматами колоночного хранения данных, мне кажется тут довольно хорошо расписано верхнеуровнево
https://15721.courses.cs.cmu.edu/spring2024/papers/02-data1/p3044-liu.pdf

Ещё из интересного нигде выше нет varint-ов, вероятно потому что их коэффициент сжатия обычно весьма плох, хотя скорость расжатия может быть даже лучше чем у bitpacking (смотри streamvbyte)

Если вдруг не знакомы с bitpacking/bitmap методами, советую эту статью
https://dbucsd.github.io/paperpdfs/2017_2.pdf
TLDR:
* roaring bitmap, лучший выбор из битмап
* pfor/simd bitpacking, block size 128/256, optional delta -- лучшие методы из bitpacking
* bitpacking обычно лучше bitmap, для всего кроме интерсекшена / dense листов (имхо с интерсекшеном разница меньше чем утверждается в статье, так как "skip pointers" в ней достаточно плохо рассматривается)
* имхо random access у roaring поприятнее

Так вот по поводу varint, много где еще используется стандартный алгоритм:
https://en.wikipedia.org/wiki/LEB128

Это очень печально, так как не смотря на простоту, такой алгоритм работает сильно хуже с branch предиктором, чем например utf-8 подход

Есть несколько разных попыток это исправить, например
https://github.com/ledbit/varint
https://www.sqlite.org/src4/doc/trunk/www/varint.wiki

Так что если вдруг у вас есть возможность сделать что-то новое/сломать обратную совместимость, и по какой-то причине вы используете отдельные varint-ы обратите внимание хотя бы на prefix варианты, которые работают значительно быстрее

Если же у вас массив varint-ов, смотрите в сторону https://github.com/lemire/streamvbyte и аналогов (есть даже с LEB128 совместимые)

Недавно читал про разные olap query execution engines: velox, photon, etc.
Есть интересный момент, о котором я думал раньше, но не встречал на практике.

Предлагается для строковых функций (lower, upper, reverse, etc) делать предположение об инпуте, ASCII он или нет.

Утверждается, что в среднем это сильно ускоряет их, впрочем, если у вас только китайский текст, то вам такое не поможет, но вероятно и ничего не испортит.

velox использует такой подход: Сделаем проверку на ASCII для инпута, если мы о нём ничего не знаем.
Как правило эту проверку нужно сделать только один раз для инпут данных, так как большинство строковых функций принимая ASCII вернут так же ASCII.
плюсы:
* не требует ничего от стораджа
минусы:
* определяет ASCII или нет каждый раз
* значительная часть времени для ASCII строк уходит на проверку, если бы мы знали заранее, что у нас только ASCII, было бы быстрее
* незначительно медленнее utf-8


photon менее понятно, так как кода нет, но можно сказать что они так же имеют специализированные варианты функций.
И возможно сохраняют некоторую мета информацию о колонке, насколько много в ней ASCII строк и нужно ли делать дополнительные проверки.
плюсы:
* читай минусы velox
минусы:
* дополнительные вычисления на вставке/компактизации данных


В заключение скажу что мне стало куда более очевидно, что для любой обработки строк стоит хотя бы сделать ASCII специализацию, и проброс ASCII or UTF-8, чтобы не считать это каждый раз.
Например в lucene, да и у нас в поисковом движке, этого нет (при вставке текста, он проходит через множество функций токенизации), а сейчас я уверен, что это стоило бы попробовать сделать.

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


https://vldb.org/pvldb/vol15/p3372-pedreira.pdf
https://people.eecs.berkeley.edu/~matei/papers/2022/sigmod_photon.pdf

В комментариях упомянули интересный момент, в некоторых JVM, есть runtime флаг, для того чтоб знать в какой кодировке записана строка (utf-16 или latin1), гуглиться по "jvm CompactStrings".

Могу прокомментировать это только с той точки зрения, что там это похоже делалось только для экономии памяти.
Так как оптимизировать строковые функции для latin1 сложнее и менее эффективно (UTF-8 => ASCII vs UTF-16 => Latin1)

Недавно в userver добавили реализацию счётчика на основе rseq -- restartable sequence.

Идея не новая и встречалась как один из юзкейсов, когда это все добавлялось в ядро (4.18).
Но в опенсурсе таких реализаций не встречал.

Основное преимущество перед per thread счётчиком, то что thread-ов обычно больше cpu-cores, и как следствие чтения получаются быстрее, а записи аналогичны.

Вообще впервые я встретил применение rseq в google tcmalloc, как замену per thread спискам блоков.
И на мой взгляд это одна из лучших идей, которые я видел в современных аллокаторах. Потому что для очень большого числа программ, это сильно улучшает использование памяти.

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

Ещё из интересного в glibc 2.35 затащили инициализацию rseq и в целом начали использовать для sched_getcpu.
Вроде бы это произошло потому что пришли люди из mysql в redhat и сказали, а у нас медленно с вашим sched_getcpu, если сделать с rseq будет быстрее.
Юзкейс аналогичный, шардированный счётчик.

Я конечно все понимаю, не очень популярный инвалидский дистрибутив и все дела.
Но у всех зависает wildcard search по контенту пакетов в alpine?
https://pkgs.alpinelinux.org/contents и попробовать поискать что-то в духе *symbolizer*

После такого бессмысленного поста как будто обязан написать что-то любопытное.
В протобуфе относительно недавно обновили то как считают сколько байтов нужно чтобы заенкодить varint
https://github.com/protocolbuffers/protobuf/commit/7315f6d398d2d18443b26c513cbdcdbffaeebaa3
Разница на самом деле довольно минимальна, и основной профит на арме

Нашел я это читая новые коммиты в s2.
Забавно что там версия стилистически другая, могли бы в целом в абсеил затащить varint.

Забавная штука https://disc.bu.edu/papers/vldb23-mun

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

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

А вот как оптимизации для row oriented формата выглядит действительно прикольно, жаль мало применимо.

Мне вмержили коммит в абсеил, удивительное событие
https://github.com/abseil/abseil-cpp/commit/cbfe51b2c01da330ff292b145de91346a5950163


А вообще хотел написать, что я недавно закончил работать в ArangoDB.
Главное, я понял как можно делать поиск и как не стоит делать базы данных ;)


Сейчас устроился в YDB в СПб офис, так что если есть кто-то кто не против познакомиться лично, я был бы рад.

Выложили в публичный доступ курс по БД в ШАДе:
https://www.group-telegram.com/databaseinternalschat/666

https://gitlab.com/savrus/shad-db старые домашки можно посмотреть тут

А еще прикольные лекции выходят тут https://shad.yandex.ru/sreweek


Ну и чтобы было более интересным постом, расскажу про забавную штуку которую нашел в folly.
Если вы когда-то использовали std::exception_ptr, то возможно вы задумывались над тем что это довольно удобный способ сохранить ошибку:
1) std::make_exception_ptr, принимает любой тип (с недавнего времени работает быстро)
2) std::expection_ptr размером 1-2 указателя, и при этом может проверяться на null (дешёвая проверка отсутствия ошибки)
3) default constructible

К сожалению все портит, то что доставать ошибку неудобно и медленно: нужно делать rethrow + catch

В folly есть хак для большинства стандартных библиотек, чтобы достать из std::exception_ptr указатель на запрашиваемый тип или вернуть null

https://github.com/facebook/folly/blob/main/folly/lang/Exception.cpp

В последнее время я занимаюсь векторным поиском, поэтому захотелось написать про одну интересную и новую статью об этом.

https://research.google/blog/soar-new-algorithms-for-even-faster-vector-search-with-scann

Статья хорошо написана, но наверное будет сложно понять если не знать некоторых деталей:

Проблема:
Хочется быстро выдавать из n векторов top k ближайших по некоторой функции расстояния (max inner product, cosine, l2 distance, etc) к вектору q, dimensions которого d

Решения:
1. Последовательный перебор, работает за O(n * k * d), это ускоряется с помощью simd и thread параллелизма или даже gpu, но работает все равно не быстро (банально много нужно прочитать с диска).

2. Можно строить структуры данных подобные kd-tree/r-tree (разница в том, что первое про разбиение пространства, а второе про создание баундов).
К сожалению они плохо работают на больших размерностях (> 3):
2.1 kd потому что разбиение на каждом уровне происходит по одному из dimensions, а это мало что говорит о расстоянии для больших dimensions
2.2 r потому что баунд боксы почти всегда оверлапятся

В итоге используются разные приблизительные методы, которые будут работать с recall < 1
recall = (count of approximate top k in exact top k) / k

Тут можно разделить на три подхода: quantization (уменьшение размера или размерности исходных данных), структуры данных для исходных данных, и комбинация этих двух подходов.

1. Как уменьшить объем исходных данных:
1.1. scalar quantization -- обычно исходные вектора имеют координаты float32 => можно их преобразовать в int8, или даже более маленькие множества, это может дать ускорение в несколько раз (< 32).
1.2 product quantization -- разобьём исходный вектор размера d на m частей, для каждой части сделаем k(256) кластеров (например с помощью kmeans). Затем для каждого вектора из датасета каждый из m кусочков заменим на индекс соответствующего ему кластера.
В итоге вместо вектора из d float32, получим вектор из m uint8 (типичные значения m d/(4 ~ 16), соответственно типичное сжатие в 16-64 раза, с довольно хорошим качеством)

2.1 Какие структура данных используются?
1.1 hnsw, не буду описывать подробно, просто это вариант когда мы поверх исходного датасета строим примерный граф. Он наиболее популярный, так как имплементации достаточно простые (in memory как правило) и работают быстро на поиске. Из недостатков требует много памяти и медленный на построении. Есть интересные версии, DiskANN, с некоторыми заимствованиями из других подходов.
1.2 ivf -- разобьём исходные датасет на кластера каким то способом (например kmeans (scann -- google alloydb) или 2-means + randomize (annoy -- spotify)) и запишем к каждому из них список id исходных векторов
1.3 Предыдущий подход в чистом виде редко используется, ivf (kmeans) tree, аналогичен, только вместо того чтобы иметь огромные кластера, строится дерево из кластеров.

Ну и собственно интересный момент, в случае ivf подобных методов, чтобы вектора были более похожими (для более точной компрессии с помощью PQ), можно вместо исходных векторов компрессить cluster vector - cluster center, обозначим за r.

А теперь подходим к статье:

Когда вы используете ivf-like метод основное засчет чего вы теряете либо recall, либо rps это те вектора которые близки к границам кластеров.

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

На практике это даст незначительное улучшение.

В статье же рассказывается, что для inner product подобных расстояний, можно при выборе второго кластер хотеть чтобы r_1 и r_2 были почти ортогональны (если точнее, то угол влияет на выбор).

Это даёт качественное улучшение recall.


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

Почти все хорошее в этой области от пары рисерчей и google, ms, fb (и немного от нормальных баз данных, timescale pgvector например)

https://news.ycombinator.com/item?id=41005355 статья от YDB как искали баги с помощью jepsen фреймворка, с ссылками на пр-ы

В ydb используется google tcmalloc, well, он примерно двухлетней давности.
Недавно один коллега обратил на это внимание, попробовал обновить и посмотреть на разных бенчмарках, что получится.
Memory usage упал в tcp-c аж на 15%, но латенси стало похуже.

Меня заинтересовало, что метрика того сколько занимают tcmalloc кеши изменилась довольно значительно, не только по размеру (как раз те 15%) но и по форме (став меняться динамически).

Я довольно давно не следил за tcmalloc репой (примерно с тех времён как они рассказывали как сделали большие аллокации huge page aware, 21~ год).
Ну и думал придется покопаться в их коммитах, чтобы найти что такого в кешах они поменяли.

Но в процессе поиска наткнулся на то что недавно, они написали статью как меняли tcmalloc на скейле гугла последние два года.

https://zzhou612.com/publication/2024-asplos-malloc/2024-asplos-malloc.pdf

Статья прям приятно читается, хотя как следствие и не содержит каких-то подробных технических деталей.

Но если приводить TLDR, то
1) Взяли больших потребителей внутри гугла (spanner, f1, bigtable, etc) и пару внешних отличающихся workload-ов (redis, tensor flow, etc)
2) Начали все это активно и по разному мерять (a/b тесты, continues profiling, etc)
3) На каждом уровне кеширования нашли определеные проблемы
4) Получили средний профит для своих ворклоадов на уровне: 3.5% по памяти, 1.5% по пропускной способности
5) Интересно, что как и с большинством идей из tcmalloc многие из этих можно переиспользовать в других аллокаторах

Ещё наверное интересно, что это показывает в какой-то степени насколько general-purpose аллокаторы (jemalloc, tcmalloc-и, может быть mimalloc) сложно сделать лучше чем сейчас даже на проценты.
Не потому что нельзя под конкретный ворклоад написать аллокатор быстрее в 2 раза, а потому что это замедлит другие юзкейсы.

Резюмируя кажется то что я искал, они называют "Heterogeneous per-CPU cache"
собственно включение которого у нас нет https://github.com/google/tcmalloc/commit/2407bb02b75ba00fd066bd5730a42cd319c303b0
сам код
https://github.com/google/tcmalloc/commit/691f9f62affb27764db8ca26f27159172c439001

1. Давно хотел померять std::function альтернативы, так как бенчмарки которые видел были очень outdated.
Взял микробенчмарк из abseil и адаптировал.
Не ноутная amd железка, clang 19, libc++ 19 (abi v2!), около транк для остальных либ

Benchmark                                   Time             CPU   Iterations
-----------------------------------------------------------------------------
BM_TrivialStdFunction                    1.11 ns         1.11 ns    622220945
BM_TrivialAbslFunctionRef                1.10 ns         1.10 ns    637419510
BM_TrivialAbslAnyInvocable               1.85 ns         1.85 ns    377698611
BM_TrivialFollyFunctionRef               1.10 ns         1.10 ns    635925877
BM_TrivialFollyFunction                  2.03 ns         2.03 ns    345277532
BM_TrivialBoostFunction                  1.31 ns         1.31 ns    535099651
BM_TrivialFu2Function                    5.27 ns         5.27 ns    133167133
BM_TrivialFu2UniqueFunction              5.07 ns         5.07 ns    137751417

BM_LargeStdFunction                      11.0 ns         11.0 ns     63490131
BM_LargeAbslFunctionRef                  1.10 ns         1.10 ns    635590925
BM_LargeAbslAnyInvocable                 9.20 ns         9.20 ns     76082731
BM_LargeFollyFunctionRef                 1.10 ns         1.10 ns    635390697
BM_LargeFollyFunction                    11.1 ns         11.1 ns     62981528
BM_LargeBoostFunction                    11.9 ns         11.9 ns     58833683
BM_LargeFu2Function                      10.5 ns         10.5 ns     66229864
BM_LargeFu2UniqueFunction                10.7 ns         10.7 ns     65711158

BM_FunPtrStdFunction                     1.42 ns         1.42 ns    472854986
BM_FunPtrAbslFunctionRef                 1.28 ns         1.28 ns    545957263
BM_FunPtrAbslAnyInvocable                3.77 ns         3.77 ns    185835648
BM_FunPtrFollyFunctionRef                1.28 ns         1.28 ns    545872297
BM_FunPtrFollyFunction                   2.03 ns         2.03 ns    345335520
BM_FunPtrBoostFunction                   1.49 ns         1.49 ns    470280007
BM_FunPtrFu2Function                     5.98 ns         5.98 ns    117100264
BM_FunPtrFu2FunctionView                 1.29 ns         1.29 ns    541223933
BM_FunPtrFu2UniqueFunction               6.35 ns         6.35 ns    110392385

BM_TrivialArgsStdFunction               0.930 ns        0.930 ns    752811771
BM_TrivialArgsAbslFunctionRef           0.934 ns        0.934 ns    752592908
BM_TrivialArgsAbslAnyInvocable           1.11 ns         1.11 ns    630181056
BM_TrivialArgsFollyFunctionRef          0.952 ns        0.952 ns    743261325
BM_TrivialArgsFollyFunction             0.938 ns        0.938 ns    753110708
BM_TrivialArgsBoostFunction              1.12 ns         1.12 ns    627254290
BM_TrivialArgsFu2Function                2.24 ns         2.24 ns    312131551
BM_TrivialArgsFu2UniqueFunction          2.24 ns         2.24 ns    312115556

BM_NonTrivialArgsStdFunction             4.30 ns         4.30 ns    162679265
BM_NonTrivialArgsAbslFunctionRef         4.65 ns         4.65 ns    150336051
BM_NonTrivialArgsAbslAnyInvocable        4.29 ns         4.29 ns    162800037
BM_NonTrivialArgsFollyFunctionRef        4.65 ns         4.65 ns    150487034
BM_NonTrivialArgsFollyFunction           4.29 ns         4.29 ns    163183216
BM_NonTrivialArgsBoostFunction           7.48 ns         7.48 ns     93603218
BM_NonTrivialArgsFu2Function             5.94 ns         5.94 ns    117998045
BM_NonTrivialArgsFu2UniqueFunction       6.12 ns         6.12 ns    118745273

Чтобы понимать погрешность можно смотреть на absl vs folly FunctionRef, там по сути одинаковый код
Удивило что
1. std::function весьма хорош (в минусы запишем то что не умеет в move only lambda, и const/noexcept в сигнатуре)
В случае abi v1, оно все еще неплохо, но уже похуже abseil/folly
2. fu2 такой фу фу (зато умеет в overload-ы, fu2::function_view работает только для function pointer?)
3. absl::AnyInvocable в случае function pointer, хотя вроде бы в их коде есть special case под это

2. Тут в асио был фикс https://github.com/chriskohlhoff/asio/commit/b6110cffea56fee4d0eb1b674d5a5a63f4523413
Чисто случайно узнал, что он пофиксил ишью, которое я создавал давно и даже предлагал фикс https://github.com/chriskohlhoff/asio/issues/1521)
Почему так сложно написать: "привет, я пофиксил <commit-hash>"?
Вообще нужно конечно не пользоваться asio, тут скорее моя вина что какой-то фикс решил в апстрим занести

https://github.com/jemalloc/jemalloc а кто-нибудь знает, почему jemalloc улетел в архив?

При том насколько я понял, овнер убирает архив, делает коммит, и опять ставит архив

Наткнулся на забавную штуку.

Есть большой класс — кусок query execution, в некотором смысле state machine. Соответственно, в нём есть мембер переменная enum State : int, по которой делают switch и в которую делают store в этом же switch.

А ещё код был примерно такой, и я заметил, что _unused не используется — и удалил:

void* ...;  
int _unused = 0;  
State _state = 0;  
void* ...;  

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

И тут, собственно, причина, почему я пишу: я заметил, что тесты стали проходить медленнее — процентов на 5-10 от обычного времени (42 vs 46 минут). Ну, подумал, может, совпадение, но решил запустить ещё раз с/без патча. Результаты повторились (к сожалению, это было не единственное изменение в PR).

Пошёл смотреть, какие именно тесты стали медленнее, и заметил, что в половине из них разница в пределах погрешности, но многие тесты кверинга стали заметно медленее.
В общем, методом пристального взгляда я нашёл это место и позапускал с _unused и без. И действительно оказалось, что на ryzen 4 (по крайней мере, 7950X) код с чтением и записью 4 байт по адресу с alignment 4 работает лучше, чем с alignment 8.

Есть у кого идеи, почему?
Возможно, это какой-то затуп store-to-load forwarding-a, но как-то неочевидно, почему это происходит именно в таком сетапе.

Если что, store-to-load forwarding — это оптимизация в процессорах, когда ты пишешь в память x (<= 16?) байт, а потом читаешь <= x байт из того же места — можно не ждать завершения записи.
Неудивительно, что, как и многие другие оптимизации процессора, она работает не всегда. Например, чтение меньшего числа байт (по крайне мере с ненулевого оффсета) обычно работает медленнее.

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

Три месяца назад я ушел из YDB, чтобы вместе с коллегами по ArangoSearch создать новую базу данных — SereneDB.

Если описывать очень кратко, то SereneDB, это база данных которая хочет совместить:
1. Продвинутый search-engine, аналог Lucene, только эффективнее и быстрее
2. Сolumnar storage и query execution, сделанные с учетом опыта modern OLAP систем
3. Удобное ACID хранение в RocksDB. На текущий момент аналитический движок это отстающий во времени snapshot транзакционного хранилища.
4. И дать к этому всему доступ из Postgres экосистемы: postgres sql grammar, functions, types, psql, драйвера, pgadmin, и тд.

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

P.S. single-node заопенсурсим в скором времени