В information retrieval => search engines есть такое понятие как релевантность документа aka document rank (score).

Допустим у вас есть набор текстовых документов, вы ищите документы удовлетворяющие булевому запросу слов (одно слово будем называть term, ещё иногда используют token).
Например, foo or bar => вернет все документы, которые содержат слова foo или bar.

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

Такой порядок устанавливается на практике с помощью функции, которая возвращает вещественное число, а принимает большое число параметров, называют ranking (score) function.

Есть довольно много разных ranking model, но переменные везде примерно одинаковые:
1) document term frequency, tf – обычно имеется в виду сколько раз конкретный терм запроса встречается в конкретном документе.
2) document length, dl, |D|, norm – сколько всего термов в конкретном документе
3) average document length, думаю итак ясно.
4) inverse document frequency, IDF, это составной компонент, который вычисляется для вашего запроса и всего множества документов, а не конкретного документа, он может иметь разную форму (*), например, log(N / n_t).
4.1) N – количество документов всего
4.2) n_t – в скольких документах содержится такой терм

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

Одна из самых простых и при этом популярных функций это tf-IDF – tf * IDF, тут важно упомянуть что как и с IDF, под tf здесь может подразумевается некоторая модификация и log(1 + tf), и sqrt(tf) / sqrt(dl) (это в lucene) и тд.

BM25 (https://en.wikipedia.org/wiki/Okapi_BM25) другая известная и пожалуй самая популярная функция на сегодняшний день. Как правило ее параметризуют двумя константами k1 и b.
Собственно к чему я это все, в какой-то момент мне стало любопытно “А почему k1? Есть другие k2, k3, …?”
Собственно погуглив, я обнаружил странное, для k2 и k3 находится один и тот же дополнительный коэффициент вида BM25(k1, b) * (tf_q + k3 * tf_q) / (tf_q + k3)
tf_q – как много раз терм встречается в запросе.
По сути мы пытаемся увеличить значение скора, если мы нашли документ по терму который запросили несколько раз.
Оказалось, что такая добавка мало что дает в плане качества, поэтому не используется на практике. К тому же в lucene-like системах обычно есть альтернативный вариант сказать, что какая-то часть подзапроса более/менее важна чем другие (boosting).

Но как же быть с тем, что и k2 и k3 называют в разных пейперах одно и тоже?
В итоге благодаря этому https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/okapi_trec3.pdf я похоже нашел разгадку.
Изначально в ходе экспериментов k3 действительно был таким (он кстати встречается чаще чем k2), а вот k2 другим. При этом k2 оказался еще более бесполезным чем k3. В итоге k3 стал более известен, но k1, k3 выглядит весьма странно, поэтому кто-то поменял k3 на k2, ну а дальше кто-то это скопировал :)

Не знаю зачем я это написал, но по-моему прикольная история.

(*) Версия IDF в BM25 лучше исключает влияние на score часто встречающихся термов, а в lucene модифицировали эту версию, чтобы избежать отрицательных значений результата функции (это полезно для алгоритма, который используется для оптимизации top k запросов, wand)

Недавно листал коммиты в одном интересном мне проекте и заметил любопытную идею, которая мне раньше не приходила в голову

https://github.com/quickwit-oss/tantivy/commit/b525f653c09726c9f97d35ee15aea1d557bce4f2

В общем все просто, давайте для онлайн partial_sort-а большой последовательности (набора top k лучших из онлайн последовательности), вместо бинарной кучи (топ -- последний) использовать такой подход:

1. Достанем k * 2 элементов
2. Выкинем k последних с помощью nth_element
3. Достанем ещё k
Повторим начиная с шага 2
В конце посортируем то что осталось

Ещё часто помимо limit есть offset, в таких случаях k = offset + limit.
В конце же можно оптимизировать (что важно для большого offset) и использовать не
1. nth_element(offset + limit)
2. erase_tail
3. sort
4. erase_tail
а
1. nth_element(offset + limit)
2. erase_tail
3. nth_element(limit, opposite_cmp)
4. erase_tail
5. sort

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

Этот пост я давно откладывал. Расскажу как писал SharedMutex в yaclib (RWLock, RWMutex) для С++20 coroutines.

Что это вообще такое?
mutex, который позволяет параллельные чтения и эксклюзивные записи.
А так же может
* требовать приоритета reader над writer, наоборот, или "равенства" ("честности")
* позволять рекурсивный mutex lock
* upgrade lock, про это подробнее в комментах

Мне хотелось в первую очередь универсальное решение, так что в первом пункте я выбрал “честность”.
Рекурсивность может быть достигнута внешним кодом, а необходимость в ней на мой взгляд признак плохого дизайна.
upgrade lock – специфичная опция требующая дополнительных усилий, в которой я не заинтересован.
А еще меня устраивало ограничение в не более чем 2^32 одновременных вызовов reader/writer lock

Как добиться “честности”?
Первое, что приходит в голову, общая очередь всех lock-ов ожидающих захвата (к слову в rust tokio примерно так и реализован rwlock).
Собственно такую же идею реализовали в arangodb, что и сподвигло меня написать это нормально.

Есть ли существенные недостатки в такой имплементации? К сожалению, да.
Когда мы вызываем writer unlock и следующий, кто залочит, reader, мы хотим разбудить всех reader-ов в очереди, для этого придется пробежаться по всей очереди, что может быть медленно.
Поэтому в том же tokio будят только reader-ов из начала очереди, поэтому не параллельных критических секций может становится значительно больше чем потенциально могло быть.
Представьте очередь вида w r w r … w, то есть, в худшем случае суммарное время исполнения всех критических секций может вырасти в n раз при такой имплементации.
На практике все не так плохо, так как худшие случаи редки, а чтения обычно достаточно быстрые.

Будет неправильным не заметить, что у такой имплементации может быть очень полезное свойство, ее можно сделать аналогично mpsc vyukov queue (примерно также как в mcs spinlock, что впрочем и является в некотором виде первоисточником), то есть получить практически wait-free с полным отсутствие contention.
К сожалению я не встречал таких вменяемых реализаций, только экспериментальные rw spinlock-и на си.

То есть чтобы достичь "честности", нам понадобится две "очереди".
В одну будем класть reader-ов, в другую writer-ов.
Тогда reader unlock всегда будит 0-1 writer, а writer unlock будит либо всех reader-ов, либо 0-1 writer.

Собственно именно такая идея является основой для большинства остальных реализации: golang RWMutex, userver SharedMutex ...

"честность" контролируется тем, что мы используем в качестве reader/writer очередей (fifo/batched lifo) и кого будим в unlock-ах.

Как только это заработало, следующее о чем я подумал это fast-path, в случае отсутствия конкуренции.
Начал я с банального, добавил atomic_uint64_t счётчик – сколько сейчас writer/reader, и соответственно fast-path это cas-loop в котором я пытался его изменить:

0 w 0 r -> 1 w 0 r // writer lock
1 w 0 r -> 0 w 0 r // writer unlock
0 w n r -> 0 w n+1 r // reader lock
m w n r -> m w n-1 r // not last reader unlock
0 w 1 r -> 0 w 0 r // last reader unlock

В целом это уже неплохо, но хотелось чтобы множество reader-ов не конфликтовали в cas-loop, то есть хотелось для reader-ов делать fetch_add/sub

Я много пытался, но оно не работало правильно :)
В итоге я подсмотрел идею в golang RWMutex.
Можно завести дополнительный атомарный счетчик (reader(s) wait), который будет использоваться для синхронизации последнего reader unlock и первого writer lock.
Вообще можно подумать, а почему просто не переписать решение с golang?
Основной нюанс, то что решение в golang может за lock засыпать несколько раз, что невозможно с C++20 stackless coroutines.
Ну и как следствие моя реализация оказалась в некоторых местах более оптимальной, нет slow-path в reader unlock, а fast-path для writer lock всего лишь один cas. В golang это не так потому что реализация сделана из других примитивов (userspace аналога futex и полноценного golang Mutex).

Можно ли сделать лучше?
В теории да, slow-path в reader/writer lock – wait-free, а в writer unlock – lock-free, вместо маленькой критической секции защищенной mutex/spinlock, нужны соответствующие очереди и логика.
Будет ли это действительно быстрее? Вряд ли, потому что до кода в slow-path мы уже сделали fetch_add/sub в fast-path с contention (условно в 10 раз медленнее cas-loop без contention).

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

В общем я слежу за разными open-source проектами, и иногда мне попадаются коммиты с интересными идеями.
Я подумал было бы неплохо писать о таком сюда, в этот раз из свежего abseil:

* https://github.com/abseil/abseil-cpp/commit/f4106724bf9cc54ed055e8d6364ae91e0d7c1547
В очередной раз убедился что tail-call оптимизация прекрасно работает не только в случае рекурсии, но и в случае fast-path

* https://github.com/abseil/abseil-cpp/commit/794352a92f09425714b9116974b29e58ce8f9ba9
прикольная оптимизация для ascii to lower/upper. Что интересно, аналогичного для сравнения без учёта case не сделано. Возможно, потому что в случае когда строки итак в одинаковом кейсе, это будет медленнее чем текущий вариант

* https://github.com/abseil/abseil-cpp/commit/d5a2cec006d14c6801ddeb768bf2574a1cf4fa7f
Ещё в последнее время они активно оптимизируют StrCat/etc, это последний коммит на тему.
Как по мне ценный урок отсюда, не пишите велосипеды для такого, гугл напишет за вас

И хочу попробовать воспользоваться каналом с корыстными целями, ищу новую работу, на текущий момент в Германии, моё резюме:
https://www.linkedin.com/in/valery-mironov

Можно писать в телеграмм (@Mkkt_Bkkt) или линкедин

Что ещё можно сделать, если у вас есть алгоритм, который требует SharedMutex, но скорость стандартного подхода вас не устраивает.

В первую очередь можно посмотреть на SharedMutex, который сделан с приоритетом на перформанс читателей.
Идея везде примерно одинаковая, давайте пошардируем читателей и как следствие избавимся от контеншена, примеры:
1) https://arxiv.org/pdf/1810.01553.pdf красивая идея, как любой лок сделать reader biased
2) https://github.com/facebook/folly/blob/main/folly/SharedMutex.h#L43 довольно сложная имплементации SharedMutex, которая пытается избегать контеншена с помощью thread local слотов
https://blog.the-pans.com/shared-mutex

Если SharedMutex нужен для чего-то похожего на структуру данных, есть два варианта:

Очевидный с RCU, плюсы, читателям в kernel-space не нужна синхронизация, в user-space нужна довольно тривиальная (в виде счётчика, может быть шардированным).
Минусы, сложность реализации, может быть много версий структуры данных.

И менее известный вариант, left-right, тут есть необходимые ссылки: https://concurrencyfreaks.blogspot.com/2013/12/left-right-classical-algorithm.html
В целом же идея очень простая, давайте поддерживать две копии структуры данных.
Наличие/отсутствие контеншена зависит от имплементации read indicator -- счётчика читателей для соответствующей версии структуры данных (может быть шардированный), по сути аналогично RCU.
Основное преимущество перед scalable SharedMutex то, что наличие писателей никак не влияет на читателей.
Ну и простейшая реализация, в отличие от RCU.
Главный минус в сравнении с RCU, что две копии нужны всегда, и что писатель должен делать работу "дважды".

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

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.tgoop.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.tgoop.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