Loser story

Вообще мы тут сделали end-to-end search/analytics benchmarks на 1e9 otel logs
Планируем туда добавить больше систем (там на самом деле большой список), да и можно размер датасета можно поднять до 50e9, основной неприятный момент это долгая индексация для некоторых систем
Цели у этого на самом деле простые, понять что где лучше и сделать также или лучше уже у нас
В целом выглядит достаточно неплохо, больше всего лично меня когда померяли удивило что у нас индексация работает весьма шустрее чем у остальных. Почему удивило? Ну я коллеге постоянно ныл про то какая же индексация медленная и что надо сделать быстрее, а оно вроде итак неплохо оказывается, но зато коллега делает бранчу и там на 30-50% быстрее :)
Да кстати системы настроены не идеально (например opensearch конфиг индексирует лишнее), кое что мы планируем к концу недели поправить и сделать лучше, но если что делайте пр-ы: github.com/serenedb/searchbench

Вообще будем делать серию блог постов про бенчмарк, вот первый, так сказать с исторической перспективой: https://blog.serenedb.com/searchbench-arangodb
Если у вас какие-то вопросы, пишите, про все что знаю расскажу)
Ну и да, ставьте звездочку https://github.com/serenedb/serenedb

Последние пару месяцев смотрел и правил перф серчевого движка и в общем у нас наконец-то есть неплохие промежуточные результаты, иначе говоря мы быстрее во всех query/collection types :)

https://serenedb.com/search-benchmark-game
TLDR:
Взяли бенчмарк фреймворк, который сделали Tantivy, по результатам которого последние версии Lucene (powers Elasticsearch/etc) стали сильно бодрее, и добавили туда IResearch (библиотеку которую мы написали и используем в SereneDB), в отличие от некоторых других, все настройки честные, в плане многопоточности/кешей и тд (это возможно во всех Lucene-like engines, но делает бенчмарк бессмысленным).
Больше про детали бенчмарка можно почитать тут https://blog.serenedb.com/search-benchmark-game-overview

А ещё мы начали серию статьей, две части уже доступны, про то засчет чего получилось быстрее чем у Lucene и Tantivy:
1. https://blog.serenedb.com/search-optimization-1
2. https://blog.serenedb.com/search-optimization-2
3. Coming soon...

В общем все как обычно, если можете поддержать, ставьте звёздочку на репу https://github.com/serenedb/serenedb/tree/main/libs/iresearch :)

Мы тут написали небольшой пост про свой iobuf который юзаем для реализации postgres протокола:
https://www.serenedb.com/blog/io-buffer

tldr: как мне кажется ключевых моментов три
1) он chunked => отсутствуют большие аллокации/копии данных
2) он простое wait-free
3) в него можно записать что-то потом (uncommitted, в блоге написано подробнее), это важно чтобы сначала сериализовать что-то и только потом записать размер этого в префиксе.


Вообще изначально думали заюзать folly iobuf или absl cord, но коллега очень не хотел мьютекс в таком простом кейсе добавлять :)

Собственно код самого буфера и проекта по ссылке
https://github.com/serenedb/serenedb
Буду рад всем кто поддержит нас с помощью PR/issue/звёздочек!

Привет, мы частично заопенсорсили текущий код нашего проекта -- SereneDB. Это оказалось тяжелее чем хотелось бы :) https://github.com/serenedb/serenedb

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

Пара интересных моментов, которые можно посмотреть уже сейчас, связаны с архитектурой:

=> pg wire protocol (postgres drivers and tools like psql)
=> libpq_query parser (postgres query syntax)
=> axiom query frontend (runner + optimizer)
=> velox query execution
=> rocksdb | search

На мой взгляд, наиболее любопытны два аспекта:

axiom -- библиотека оптимизатора для velox, которую недавно начала делать meta. Мы активно подключились к разработке, примерно половина коммитов за последние 3 месяца наши. Кстати в нашем форке есть пока отсутствующие у них "фичи": window функции, cross джоины, etc. Да, проект пока ещё совсем сырой, но мне кажется библиотека оптимайзера это классная идея, так как если с execution оно более менее устоялось, с оптимайзерами все не так однозначно

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

Кстати если вы не особо разработчик баз данных, у нас есть разные прикольных чисто инженерные моментов:
1) build from source (кроме libc, там пока не густо), как следствие например мы можем легко пропатчить libc++ и используем memory sanitizer
2) А ещё именно это позволяет легко получать static binary
3) И да у нас C++26, clang, llvm стек в общем
4) А для concurency юзаем YACLib
5) Да и в целом есть много прикольных решений про которые расскажем немного позже, например, сериализации структур с помощью boost pfr или кастомные локфри iobuf-ы

В любом случае буду рад всем кто поддержит наш пока небольшой проект с помощью PR/issue/звёздочек!

Вообще вот странная штука, больших проектов на C++, C, Rust которые делают базы данных или около довольно много (например стартапы, да и в bigtech).
Но при этом тех которые делают хотя бы следующие вещи:
1. Запускают свои тесты с 4 санитайзерами
2. Имеют coverage репорт
3. Имеют perf тесты и репорт

Как будто единицы, почему так?
(ну достаточно часто есть какой-то минимальный, криво сделанный сабсет описанного)

Это же что-то в целом довольно базовое, в целом для любого проекта.
Базы данных это вроде бы что-то довольно низкоуровневое, где цена багов/регресии может быть высока.
Да и делается не так сложно.
Я бы еще понял если бы сейчас был какой-нибудь 2015, но сейчас 2025.
В общем где эта, "культура разработки"?

Решил почитать перед сном коммиты в llvm libc++, а то там llvm 21 вышел, думаю может обновиться. И нашел коммит, который фиксит любопытное issue.

Вот здесь хорошая выжимка, но если совсем кратко:
1) в llvm 20 сделали abi break на кучу стандартных контейнеров, заметили спустя полгода, что делать с llvm 20 пока не решили) А ещё с gcc фикс не работает так как баг в gcc.
2) [[no_unique_address]] для одинаковых типов, но разных филдов работает весьма неочевидным образом, если вы тот самый любитель поликонваться динамически будьте аккуратны хотя почему вы при этом используете llvm libc++ для меня загадка


Ну и раз уж что-то пишу, по-моему стоят упоминания
1) в abseil поменяли load factor с 7/8 на 27/32
2) в той же самой llvm libc++, multimap/set::find оптимизировали и он перестал возвращать тоже самое что lower_bound
3) ещё из забавных оптимизаций: в abseil и в llvm libc++ перестали считать хеш для вставки в пустую хештаблицу

https://aws.amazon.com/blogs/aws/introducing-amazon-s3-vectors-first-cloud-storage-with-native-vector-support-at-scale

Звучит конечно прикольно, более дешёвый стор большого количества векторов по которому работает ann поиск.

А есть уже какие-то известные детали реализации/etc?

Я попытался побыстрому найти инфу об интеграции с opensearch в их репе или их knn репе, но безуспешно

Наиболее близкое issue, которое я нашёл, это:
https://github.com/opensearch-project/k-NN/issues/2391

Однако, насколько я понимаю, там речь идёт о внешнем билде индекса, а не о внешнем кверинге

https://github.com/orgs/community/discussions/163932
гитхаб наконец-то обновил UI для ПР-ов, по ощущениям правда бодрее стало. Особенно левая панель с file tree.
правда только 300 файлов пока...

Три месяца назад я ушел из 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 заопенсурсим в скором времени

Бтв с учетом новостей чет вспомнилось

JeMalloc has long history and it is well maintained and constantly improved.

https://github.com/ClickHouse/ClickHouse/issues/34157

Я не верю, но возможно сюда что-то накоммитят: https://github.com/facebook/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 байт из того же места — можно не ждать завершения записи.
Неудивительно, что, как и многие другие оптимизации процессора, она работает не всегда. Например, чтение меньшего числа байт (по крайне мере с ненулевого оффсета) обычно работает медленнее.

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

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

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

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

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 под это

В 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

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

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

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://t.me/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://github.com/abseil/abseil-cpp/commit/cbfe51b2c01da330ff292b145de91346a5950163


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


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