https://github.com/abseil/abseil-cpp/commit/535f22b4a08a11166c91fabc22fe130933c745a7#diff-63e37c19fd975193f3b7ebfc5bf0a0d0b47761463d5c683df93e2823999be1faR256
Прикольно

В общем я не специалист по написанию sql/etc запросов, хоть и пишу бд.

Сейчас узнал (из issue) про забавный хак: ORDER BY RAND() LIMIT N. Собственно идея в том чтобы получить N случайных записей из таблицы (зачем нужно уже это без понятия, но прикольно).

https://youtu.be/ugw0lQoATB4
Мне тут ютуб порекомендовал любопытный доклад про различные заброшенные опенсурс субд.
Кстати про несколько систем из списка слышал, но вообще довольно грустно

В целом как-то не было особо времени/желания писать посты, на работе как то загружено, а остальное время занимался яклибом.
Между прочим я уже скоро два месяца как в Кельне, и в общем мне тут нравится.
Мои опасения по поводу отсутствия разнообразия в местной кухне не оправдались, а работать из офиса намного лучше ;)

Вы наверно знаете, что такое конечные автоматы.
Но возможно, как и я до недавнего времени, не слышали об FST.

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

Еще эта структура данных примечательна тем, что имеет полезные применения:
- Используется для хранения словаря термов (и не только) в lucene и других поисковых движках. Кстати в качестве полукольца веса может быть и строка
- В распознавании речи в kaldi, статья довольно подробно описывает зачем, только учитывайте, что за исключением части раздела 2 и раздела 4 это по большей части повторение первой статьи.

Как я думаю следствием этого является наличие вменяемых имплементаций.
Например гугловая библиотека C++ OpenFST, ее используют kaldi и например мы в ArangoDB.

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

Но зачем вообще в ArangoDB OpenFST? Мы используем ее в https://github.com/iresearch-toolkit/iresearch (аналог lucene), правда с некоторыми патчами.
Поставьте нам в iresearch звездочку кстати!

К сожалению OpenFST не без недостатков, что неудивительно учитывая что либа была написана еще в 2000-ых:
- bazel/make как система сборки, это типичный недостаток гугловых/старых либ, но это не большая проблема, можно написать свой простенький cmake для нужного вам (есть в iresearch)
2. То что это все живет не на условном github/gitlab/etc, хз принимают ли они патчи например, ну и в целом мне кажется это сказывается на активности разработки.
3. В либе много довольно странного API, который стоило бы задеприкейтить.
В целом ощущение что оно почти не развивается

Если же говорить про другие библиотеки fst, я видел несколько любопытных на rust:
- Попытка переписать openfst
- Реализация fst на rust, которая используется в tantivy
Собственно имплементация в lucene
Вроде бы еще что-то есть на java но я не интересовался

Еще постараюсь до нг написать про fault-injection немного и геометрию

Всех с наступающим/наступившим новым годом!
В общем надеюсь что новый год будет лучше чем этот для всех нас.

Кстати YACLib добавили в conan!
https://github.com/conan-io/conan-center-index/pull/14006

https://quick-lint-js.com/blog/cpp-vs-rust-build-times/
Оно конечно немного стрёмно, в духе сравнения apple clang 14 (что примерно соответствует 12-13 llvm clang) и llvm clang 15
Но любопытно и впечатляет насколько много бесполезного было сделано

Давно не писал, чем я вообще занимаюсь

Читаю книжки:
1. https://nlp.stanford.edu/IR-book/information-retrieval-book.html — про идеи и алгоритмы, которые стоят за поиском.
В целом, я многое уже знал по работе, но мне нравится, то что структурирует мои знания и в целом более теоретический взгляд.
Ещё в очередной раз убедился насколько книжки с упражнениями лучше, чем книжки без них, единственный минус, в отличии от perfbook, здесь нет ответов, чтобы проверить себя (остается, либо доказывать, либо гуглить, если не уверен).

2. https://ciir.cs.umass.edu/irbook
По сути тоже самое, но якобы более практическое (из прикольного к книжке есть жаба код учебного поискового движка http://www.search-engines-book.com), по факту мне показалась более поверхностной и менее интересной.

Вообще на работе сейчас занимаюсь ускорением geo поиска, так как он работает у нас на s2, у меня периодически горит с них жопа.
Например, сделал оптимизацию для случая, когда кверить будут только точки и заодно улучшил интерфейс, чтобы не нужно было делать аллокацию на каждый вызов, PR до сих пор висит https://github.com/google/s2geometry/pull/303, потому что гугловый чел не оценил моего расширения интерфейса. Надеюсь его не сократят, а то не знаю сколько ещё ждать ответа.

В целом мне кажется историю, которая у нас сейчас: храним термы для кверинга в инвертед индексе, а потом вычисляем точную операцию, можно делать принципиально лучше, проблема в том что s2 почти не развивается, а нужно, чтобы их индекс умел в выдачу конкретных фигур в intersects/contains не только для поиска точек, но и полилиний и полигонов, вроде как они планируют это сделать, но когда — хрен его знает :(

Вообще как бы вы решали задачу k-way merge (есть k отсортированных input, нужно получить 1 отсортированный output)?

Я бы встретив такое на собесе решил бы через кучу, и с асимптотической точки зрения лучше нельзя.

Но с практической можно делать меньшее (в константу раз) число сравнений.
Вчера я вспомнил, что хотел померить это в arangosearch.

Ну и в общем в чем же идея?
Давайте сначала вспомним, что будет происходить в случае кучи:
Каждый раз доставая элемент нужно сделать sift down обновленной вершины:
Это в свою очередь спуск вниз на глубину log(k), к сожалению на каждом спуске нам ещё нужно проверять спускаться в левое или в правое под дерево, то есть в итоге мы получим не больше 2 * log(k)
(в плюсах и многих других языках из коробки ещё хуже, так как decrease key отсутствует, нужно сделать pop + push, что уже до 3 логарифмов, +1 потому что push это sift up, который требует не более логарифма сравнений)

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

Поэтому вместо этого можно поддержать дерево явно, по сути сделав дерево отрезков минимумов, такой подход называют tournament tree, и он даст ровно log сравнений

Cегодня я набросал код и вероятно завтра напишу микробенчмарки, потом еще посмотрю на перф в аранге:
https://github.com/iresearch-toolkit/iresearch/pull/476

В целом весьма очевидно что мы выигрываем, есть ли минусы? В сравнение с pop + push подходом нет, в сравнении с sift_down к сожалению да.

Главная проблема что в случае дерева нам нужно поднимать новое значение снизу, то есть логарифм сравнений мы делаем всегда.
В случае же с кучей мы опускаем значение среди других значений и если нам повезло и input-ы не пересекаются мы на каждый push в output будем делать только 2 сравнения (кроме тех где input закончился).

Резюмируя для [0;4-8] инпутов tournament tree однозначно лучший подход, относительно числа сравнений.

А дальше это зависит от данных. Если данные рандомные то все еще лучший. А вот если по какой-то причине у вас очень мало переключений инпутов или вообще disjoint диапазоны, то вероятно ручной sift down покажет себя оптимальнее :(

Можно ли что-то с этим сделать?
Наверно нет, только страдать, впрочем еще мне нравится подход с деревом тем, что это всегда фиксированное число сравнений, их число не зависит от того как именно output данные расположены в input-ах

Не конструктивный пост, для меня C++ лучший выбор для разработки чем Rust, да у него есть очевидные преимущества над C++, впрочем верно и обратное.

Сейчас я не буду перечислять все, а расскажу об одном из наиболее важных для меня недостатков, который декларируется как преимущество, это cargo и система пакетов.
В вакууме она безусловно лучше того, что предоставляет C++ (кривые поделия, отсутствие стандарта => большинство зависимостей собирается из сорцов).

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

Качество кода и глубина зависимостей становятся куда менее однородными, чем при подходе сборки из сорцов.
Есть статья которая в целом отражает мое отношение к зависимостям:
https://research.swtch.com/deps

Безусловно я не считаю что все нужно писать с нуля, буквально первое, что я делаю с идеей, это ищу код который её реализует.
К сожалению часто даже найдя такой код, использовать его не является разумным.
В случае же с пакетными менеджерами, люди редко смотрят на что-то кроме наличие нужного API и количества установок.

Впрочем в си на мой взгляд есть противоположная проблема, когда библиотеки практически не используются (кроме domain specific: сжатие, криптография, етс), а в стандартной библиотеке отсутствуют контейнеры, как следствие все реализуется по 10 раз, а дефолтная структура данных для си это список (из-за своей простоты).

Резюмируя, у каждого из подходов есть свои недостатки, но контролировать, что в твоём проекте нет лишних велосипедов, сильно легче на мой взгляд, чем контролировать что все зависимости не зависят от чего то зря (да и что делать в таком случае не очень ясно).

Прочитал интересный пост на ночь: https://eklitzke.org/efficient-file-copying-on-linux
TLDR: если читаете файл на линухе, есть вероятность что стоит делать это блоками по 128 Кб, так как readahead настроен обычно на такое число

В общем недавно появилось время и я доделал дерево вместо кучи,
померял и даже на простом компараторе получил ускорение на 15%.

Ещё недавно пофиксил оптимизировал довольно забавный кейс:
Дана сортированная по возрастанию последовательность уникальных чисел.
Затем по ней много ищут.
Есть две особенности:
1. В последовательности множество dense подотрезков, как правило с длиной больше 1.
2. Если все искомые числа выписать в одну последовательность, то это будет последовательность сортированных подотрезков, как правило с длиной больше 1.

Понятно что baseline здесь это обычный бинпоиск.
Но мы могли бы сохранить найденную позицию в массив.
Тогда при следующем поиске, нужно вычислить разницу между значением, которое было на этой позиции и искомым числом.
После прибавить эту разницу к прошлой позиции.
Затем проверить, что мы не вышли за пределы массива и это действительно искомый элемент.
В случае если между текущим искомым числом и прошлым был dense диапазон, мы нашли новое число.
А если не получилось все ещё можно использовать обычный бинпоиск.

Я не особо усердно бенчмаркал, так как это очевидно лучше, но даже на достаточно маленьких массивах (1e5) вышло в 2-4 раза быстрее.

Я думаю многие знакомы с pmr, который формально был добавлен в C++17, а на практике в libc++ нет поддержки до сих пор.
Если не считать этого фатального недостатка, то в целом pmr может быть иногда довольно полезен.

monotonic_buffer_resource же при этом абсолютно бесполезен на уровне дизайна.
Идейно кажется довольно удобной абстракцией -- непрерывная память, которая запинена.
Реализация представляет из себя связный список блоков, размер блоков растет экспоненциально.

Но может ли кто-то объяснить почему у нее нет методов:
1) clear -- отпустить все блоки кроме последнего, для последнего считать, что он пустой
2) current_block_size/next_block_size/size, хотя бы что-то

Необходимость первого метода довольно очевидна, так же как наличие такого метода для вектора.
Необходимость же второго обусловлена тем, что иногда хочется освободить всю память (в отличие от clear), но при этом при следующем использовании начать сразу с нужного размера. И это как раз возможно, конструктор от размера есть у этого ресурса, а вот его размер нужно трекать снаружи почему то :(

Пример для clear:
... our_resource;
vector<T1> v1({our_resource});
use(v1);
v1 = {};
our_resource.clear()
vector<T2> v2({our_resource});
use(v2);

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

Прочитал любопытный пейпер 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 ртт в лучшем случае (остальное зависит от реализации редиректа на лидера).

Вообще я не очень люблю рафт, мне как-то всегда больше нравились алгоритмы консенсуса, которые ближе к оригинальному 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 секунд.

Есть ли какие-то реальные преимущества у рафта перед например 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

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