Loser story

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

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

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

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

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

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

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

Недавно в 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 будет быстрее.
Юзкейс аналогичный, шардированный счётчик.

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

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

Недавно читал про разные 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

Прочитал статью, первый раз столкнулся с таким явным вариантом рекурсивного сжатия 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 совместимые)

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

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://t.me/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

Что ещё можно сделать, если у вас есть алгоритм, который требует 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, что две копии нужны всегда, и что писатель должен делать работу "дважды".

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

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

В общем я слежу за разными 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, это последний коммит на тему.
Как по мне ценный урок отсюда, не пишите велосипеды для такого, гугл напишет за вас

Можно ли сделать лучше?
В теории да, 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).

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

Этот пост я давно откладывал. Расскажу как писал 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).

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

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

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

В 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://youtu.be/_qaKkHuHYE0?si=u0nHEWKgKasWAUyW
Забавный доклад, автор рассказывает про то как не получилось. Кстати спустя какое-то время код совсем удалили: https://github.com/google/tcmalloc/commit/42555acdab2ece45233bcbdade24ad03987a24bb

Что ещё более забавно, после была попытка в не lock-free ring buffer cache, оно какое-то время поюзалось, но в итоге стек всех пережил
https://github.com/google/tcmalloc/commit/26d81c3707283d341966945fba428e1eab287eaa

Есть ли какие-то реальные преимущества у рафта перед например MultiPaxos с теоретической точки зрения?
При стабильном environment-е, и если это не WAN, пропускная способность может быть немного выше (так как выбор лидера есть и там и там) https://www.diva-portal.org/smash/get/diva2:1471222/FULLTEXT01.pdf

Почему же почти все используют рафт?
Есть готовые опенсурс реализации, и даже если писать свою имплементацию, та информация, что есть про рафт куда ближе к спецификации, чем то что есть на тему разных paxos алгоритмов.

В общем ждём когда какая-нибудь жирная компания сделает качественный опенсурс paxos?)

Кстати случайно наткнулся на прикольную статью с некоторой историей алгоритмов семейства paxos, рекомендую
https://vadosware.io/post/paxosmon-gotta-concensus-them-all

Вообще я не очень люблю рафт, мне как-то всегда больше нравились алгоритмы консенсуса, которые ближе к оригинальному single node paxos.

Основная разница между paxos (а конкретнее вариациями MultiPaxos) и raft в том какие кворумы пересекаются и как следствие где происходит livelock:
В MultiPaxos, наличие лидера просто оптимизация, корректность от нее не зависит, пересекаются кворумы phase 1 (propose/promise) и phase 2 (accepted).
В рафте же пересекаются leader election (request vote) и log replication (append entries).

Из этого следует главный, на мой взгляд, недостаток рафта, все упирается в лидера, причем ладно пропускная способность, так ещё и в случае реального падения лидера, система становится недоступной, обычно на весьма продолжительное время, условные 1-20 секунд.

Прочитал любопытный пейпер https://www.usenix.org/system/files/conference/hotcloud17/hotcloud17-paper-arora.pdf

В общем как обрабатывать чтения в рафте?

Ну если достаточно консистентных, то можно из fsm любой ноды читать, если же нужны линеаризуемые

Можно, наивно -- захендлим так же как и записи, реплицуруя их лидером на кворум.
Этот подход может быть улучшен с помощью отсутствия реальных записей на диск для чтений, это как бы дефолт, описан в даже в сокращённой пдфке рафта (забавно что даже в просто чтении ошибались https://github.com/etcd-io/etcd/issues/741)

Другой достаточно популярный сейчас вариант, реализовать PreVote и CheckQuorum leader leases, тогда можно достичь того что в рафте никогда не будет существовать более одной ноды считающей(!) себя лидером => можем читать сразу из fsm лидера (стоит учитывать, что leader lease и election таймауты между участниками рафта должны быть подогнаны динамически под максимальный clock drift).
Почитать можно немного тут, в пейпере это не особо подробно описывается, так как довольно известный подход имеющийся в большинстве промышленных реализаций.

Проблема варианта с кворумом, что он имеет большое латенси, минимум 1 ртт, второго, что ограничен пропускной способностью лидера.
Собственно что же предлагается в пейпере?

1) Берём второй подход, используем его когда с клиента пришли на лидера
2) С некоторой вероятностью, есть формула, (ну и на мой взгляд в fallback случаях, например, таких как множество нод без лидера меньше majority, тайм-аут, етс) делаем редирект на лидера
3) Делаем с фолловеров чтение в виде чтения quorum каких-то фолловеров
4) там есть ещё взаимодействие с лидером для полноценных линеаризуемых чтений кворумом, но это неинтересный чисто технический нюанс, смотрите strong consistent reads

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

Основной нюанс изменение в latency, причём не столько его самого сколько его нестабильность: пришел на лидера, ответили сразу, пришел не на лидера подожди 1 ртт в лучшем случае (остальное зависит от реализации редиректа на лидера).

https://www.vldb.org/pvldb/vol8/p1058-leis.pdf
Забавный пейпер про то как можно сделать window functions всегда за n*log(n), даже когда окно динамически меняется: давайте запихнем все в дерево отрезков