Сегодня расскажу что-то полезное.
Это wait-free "алгоритм" для некоторого подобия взаимного исключения и очереди. Звучит конечно круто, но на практике это простейший код, как и почти все действительно полезные wait/lock-free алгоритмы.

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

Наверно нихуя не понятно, я не умею нормально объяснить, приведу пример.

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

Оптимально будет сделать так:

void forceAsyncRequest() {
some_thread.push([this] {
counter_.store(1);
...do it...
// если за это время пришел новый asyncRequest мы перезапустим сами себя в конце
if (counter_.fetch_sub(1) > 1) {
forceAsyncRequest();
}
}
}

void asyncRequest() {
if (counter_.fetch_add(1) == 0) {
forceAsyncRequest();
}
}

Я написал такой код ещё в транзасе, там было обновление кеша прореживания объектов по таймауту, а также некоторым действиям пользователя.
Там также нашлось несколько других мест где этот паттерн был полезен.

И недавно мне понадобился этот "алгоритм" в ArangoDB, решил с вами поделиться)

Кстати в yaclib (star plz https://github.com/YACLib/YACLib) я все планирую написать специальный тип таски на такой паттерн (там ещё в push аллокации не будет), да все руки не доходят (issue есть: https://github.com/YACLib/YACLib/issues/10)

Кстати сегодня впервые задумался, а какая libc на macOS?
https://github.com/apple-open-source-mirror/Libc какая-то имплементация есть, но интересно с кого она спизжена, с bsd libc, glibc или прям совсем своя?

На linux из адекватного кажется есть две альтернативы:
glibc (если используете в виде .so, то велики шансы, что у вас проблемы с поддержкой разных дистрибутиво, а использовать не .so по сути нельзя)

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

Возможно когда-нибудь у нас будет llvm libc, ждём

На windows это видимо msvc рантайм какой-то, иногда видимо mingw рантайм, хз

Вообще я тут недавно участвовал в дискуссии, что было бы лучше, если у нас была не libc, а memory_libc.a, string_libc.a, alloc_libc.a, io_libc.a, etc
В общем набор маленьких библиотек, со статической линковкой в одну большую .so или в ваш проект, вероятно тогда у нас было бы больше альтернатив и конкуренции, сейчас же, даже если ты знаешь как написать самый быстрый strstr (twoway топ), то тебе либо надо мучаться с попытками затащить это в glibc, либо писать свою/тащить в другую маргинальную libc. Оба варианта сложные, иногда сложнее самой задачи, как мне кажется это весьма печально.

Собственно подъехали отзывы о докладе. Из приятного если время считается правильно, то большинство посмотрели целиком.

По лично моему впечатлению получилось несколько проблем:
1) Действительно кароче чем можно было, вроде минут 35.
Но с другой стороны, говорить больше сторонней информации, по типу введения не хотелось (у меня были такие слайды, выпилил), также не хотелось добавлять ещё больше кода на слайды так как по-моему в докладе достаточно сложности
2) По поводу презентации, мне казалось она офигенно выглядит, видимо не так, попробую сменить размер текста и тему
3) Ну и я вероятно действительно рассказал все несколько быстрее и монотоннее чем нужно, основная проблема лично для меня была, что в процессе доклада ты по сути говоришь все самому себе и не видно никакой реакции -- понятно/не понятно.
Возможно стоило предложить задавать вопросы в процессе доклада (узнал о такой возможности только когда смотрел другой доклад)

Презентация в комментах
Запись видимо будет когда-то весной, я скину)

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

Пока еду в такси, захотелось что-то написать (тем более все пишут)
В 2021 я кажется (хотя наверно ещё рано судить, но все-таки) нашел классную команду и работу
Бросил уник
Сдавал классные и не очень домашки
Организовал и писал опенсурс проект (и надеюсь заюзать его полноценно в следующем году)
Выступил на конференции по плюсам
Завел кота
Ещё не совсем одичал и всё ещё общаюсь с людьми
Стал лучше в английском (всё ещё ужасен)
Прочитал несколько классных книжек
Написал каркас и альфу для большого проекта с нуля

Хотелось бы в следующем году:
Стать лучше в английском
Сделать много классных тасок
Быть ответственнее по отношению к коту
Больше читать полезного
Попробовать себя в роли преподавателя, хотелось бы прочитать такой курс в ксц https://gist.github.com/MBkkt/296baa71181de5d95110048f358e564e, но не знаю как сложится пока (кст пишите критику)
Заюзать yaclib в arangodb
Меньше забивать на свое здоровье

Больше отдыхать, больше успевать.
В общем если получится половина будет неплохо)

Всех с наступающим новым годом)

Опять давно не писал...

В плюсах есть built-in T* operator+(T*), он как и некоторые другие built-in операторы нужен в основном для разрешения перегрузок, нам же интересно другое его немного нестандартное применение:

auto lambda = [] {};
auto func = +[] {};
using ptr = void(*)();
static_assert(std::is_same_v<ptr, decltype(func)> && !std::is_same_v<decltype(func), decltype(lambda)>);

Это работает, потому что лямбда с пустым захватом умеет неявно каститься в указатель на функцию, в итоге мы вызываем этот каст с помощью operator+.
Мне недавно это пригодилось, чтобы написать код аккуратнее код, который работает с несколькими разными лямбдами без захвата, как с переменными одного типа.


А теперь резкий переход, cегодня вспоминал io_uring [1], по работе, и понял, что ни разу не писал в канал про эту абстракцию, которая мне очень нравится.
Ниже речь пойдет только про Linux.

В Linux до относитель недавнего времени (5.1) существовало по сути два способа взаимодействия с файловой системой:

Способные блокировать поток, сисколы (read, write, etc), простое, но неэффективное API прямиком из 70ых (в golang есть интересный хак, когда вы делаете блокирующий сисколл [2], поток тредпула (m), исполняющий горутину, отдает свою очередь горутин (p) шедулеру, и соотвественно другие потоки без очереди могут ее захватить). В плюсах же чаще для файлового IO просто делают отдельный тредпул. Главная проблема этого подхода он не масштабируется, так как мы добавляем порядок, синхронизацию, там где оно не нужно.

Aсинхронное API (aio_*), оно крайне кривое (почему, отдельный разговор), и работает только с не буферизованными файлами. Так что, если вы хотели его использовать, вам нужно было реализовывать собственный кеш для файлов, как итог им пользуются только некоторые базы данных, насколько мне известно.
Также на мой личный взгляд, если вы не считаете, что ваш процесс единственный нагруженный в юзерспейсе ОС, использовать его сомнительно.

В ядре 5.1 появилось новое API — io_uring.

Некоторая предыстория моего знакомства с этим API:

Года так 3 назад, я задавался вопросом, а можно ли как-то сделать асинхронный fsync append-only файла. Задача была в том, чтобы по событию синхронизировать файл в который писались данные, при этом отсутствовал внешний наблюдатель (то есть смысла ожидать fsync не было, хотелось как бы попросить OS: пожалуйста, если можешь синкани состояние этого файла как можно скорее).

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

1) Пишем write в буфер фиксированного размера
2.1) Периодически флашим его, то есть асинхронно отправляем write c буффером через io_uring интерфейс (тут также понадобится некоторый кеш блоков, так как мы отдаем владение блоком ядру, но это просто список, стек)
2.2) Тут возможна оптимизация, есть два варианта как пользоваться io_uring сабмитить данные самому через сискол, или завести специальный поток на стороне ядра который будет поллить очередь [3].
3) Когда же попросили сделать fsync, мы просто флашим буфер, и хочется сказать "отправляем fsync через io_uring", но нет, ведь ядро, может исполнять запросы в очереди в произвольном порядке, что и делает io_uring действительно быстрым (забавно кстати, что есть некоторые параллели с тем как vulkan отличается от opengl). То есть, если мы просто будем отправлять fsync, то ядро сначала может исполнить его, а затем уже write-ы которые в очереди.
3) Что же тогда делать? Ну можно было бы дождаться завершения всех вызовов в очереди, то есть самим по-poll-ить completion queue, но есть решения лучше, давайте просто запушим nop операцию которая будет с DRAIN флагом, такая операция и будет барьером, который не позволит ядру запустить fsync раньше чем исполнить все write, при этом мы не будем ждать (!)

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

Ну и как вишенка на торте, то что помимо правильного API мы получаем самое производительное решение: есть разные бенчмарки, вот например [5]

Пожалуй единственный печальный момент, что даже 5.1 кернел еще далеко не у всех юзеров, как я понимаю enterprise на данный момент это в основном 3-4 кернелы (что конечно пиздец, но спасибо хоть не 2)

Что же с аналогами не из мира linux?

Ну на Windows, довольно быстро сообразили, что тут сделали офигенную штуку и сделали аналог [6], судя по тому, что я видел, разница около косметическая, что если WIndows это уже давно, просто лишняя абстракция над Linux кернелом? Работает же WSL как-то, ощущения что буквально взяли почти как есть io_uring.
Из особенностей, помимо мелких отличий, оно более свежее, так что мануалов, багов и тд, наверно больше. А еще, помоему, нет некоторых фичей, но задел под флаги есть [7], так что думаю это только вопрос времени.

В FreeBSD, macOS, ... ну вы поняли, насколько я знаю аналога нет :(
Ну пожалуй стоит заметить, что kqueue изначально сделан более прямо чем epoll и умеет в fd в отличии от него (epoll всегда возвращает что готов)
Как следствие проблема именно файлового IO там вероятно чуть менее остра? Ну а сокращение количества вызовов сисколов (только сейчас задумался как же странно это звучит), и возможность делать асинхронными не только read/write видимо менее критична на их взгляд. Не знаю, вообще macOS закрытая, а FreeBSD полутруп?

Но говоря про последнее, меня очень привлекает в io_uring именно возможность удешевления сисколов до почти обычных вызовов [8].
Может кто знает, я не интересовался такими маргинальными знаниями раньше: похоже ли io_uring на то, как обычно делают взаимодействие между компонентами в микроядерных ОС?
Но ладно, это неважно, важно, как мне кажется, то что по мере добавления поддержки новых сисколов в io_uring, возможно из Linux-а вынесут к черту большую часть кернел имплемнатции дров? И будет в кернеле не 20+ млн строк, а хотя бы какая-нибудь парочка)

Ладно оставим эти влажные фантазии, надеюсь на какую-то активность в комментах, я старался, а io_uring классный

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

Ссылочки, для тех кому TLDR

[1] Efficient IO with io_uring собственно описание
[2] Функция, которая вызывается в golang для сисколов
[3] Пример с обьяснениями поллинга submission queue
Также это в целом отличный сайт с крутым названием, о том как использовать io_uring и liburing, кстати у автора сайта в блоге есть серия статей c примерами.
[4] IOSQE_IO_DRAIN
[5] Опыт и бенчмарки ScyllaDB
[6] Windows I/O Rings описание в прикольном блоге, там же есть пост в котором автор пишет о тех различиях, на которые он обратил внимание
[7] Windows I/O Rings дока, как видим пока флажков нет
[8] Доклад про микроядерную ОС: managarm, в общем выглядит красиво

Мда это фейл

https://telegra.ph/Bla-bla-bla-pro-io-uring-02-03 одной ссылкой про io_uring

Еще и спалился что не пишу большие тексты в телеге

Бля, почему слинковаться с libc++ так сложно?

Например такое пишут в simdjson:
https://github.com/simdjson/simdjson/blob/master/cmake/developer-options.cmake#L162
> # The next line is needed empirically.

Я в итоге сделал
add_link_options(-stdlib=libc++ -lc++abi)
add_compile_options(-stdlib=libc++)

Причем пришлось глобально в cmake сетитить чтобы пробросить в gtest

Но это пиздец. ненавижу cmake, писателей опций компиляторов и их документацию и тд. Почему блин не сделать все хотя бы внутри cmake просто добавили бы что-то вроде;
set(CMAKE_CXX_STDLIB ...)

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

Так что вот: https://github.com/YACLib/Bench
мы сделали сравнение YACLib, Folly, Boost::Thread фьюч, в бенчмарках практически полностью аналогичных бенчмаркам Folly.
Если вам любопытно, или не сложно, запустите пожалуйста их у себя и сделайте PR c результатами, мы будем очень признательны!
В readme есть how to guide, но если возникнут какие-то вопросы, или что-то не будет получаться, то можно написать issue, либо спросить здесь в комментариях.

P.S. Картинок пока к сожалению нет, но в ближайшем будущем добавим скрипт, который их рисует + применим его к тем результатам что уже в репе.
А еще наверно будет пост на reddit и habr, с разбором результатов бенчмарков

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

Проще говоря если я повторяю команду нужно удалить прошлый ее вызов из истории

Наконец-то получил загран!

Кстати разбираю сейчас EPaxos, статью и алгоритм в целом, думаю напишу подробнее об этом, было бы круто если кто нибудь тоже прочитает и готов обсудить (в комментах)

// godbolt умеет в много файлов и cmake
https://twitter.com/CompileExplore/status/1431022441917210625
Я единственный слоупок который не знал об этой фиче?
В общем это прям классно, единственный минус, нельзя ничего качать в cmake :(
Есть issue, но там пишут что по secure причинам не хотят разрешать.
Есть мысль что можно предложить local storage из которого будут пытаться по alias-у забрать

Но в целом это не супер важно, пример работы фичи с яклибом:
https://godbolt.org/z/e6WP4Wb6o

// Как вы блокируете > 1 мьютекса?
Наверно у вас есть на них какой-то порядок, либо вы используете std::lock (иначе possible deadlock).
std::lock использует алгоритм наподобии (только обобщенный до n мьютексов):

while (true) {
  std::unique_lock l0(m0);
  if (m1.try_lock()) {
    l0.release();
    break;
  }
  l0.unlock();
  std::this_thread::yield();
  std::unique_lock l1(m1);
  if (m0.try_lock()) {
    l1.release();
    break;
  }
  l1.unlock();
  std::this_thread::yield();
}

И мне всегда казалось неочевидным, что это лучше, чем упорядочить по адресам (адрес обьекта мьютекса не может измениться, что кстати должно быть неправдой в rust?).
Недавно в коде folly обнаружил ссылку на любопытную статью с бенчмарками
http://howardhinnant.github.io/dining_philosophers.html

В общем если у вас не естественный порядок (например у вас всего два мьютекса и вы всегда держите блокировку на первом дольше чем на втором) std::lock покажет себя лучше чем упорядочивание по адресам.
Условный пример, когда std::lock лучше:
У вас есть счета юзеров, каждый из них обладает мьютексом.
Чтобы совершить перевод с одного счета на другой вы блокируете мьютекс отправителя и мьютекс получателя

В итоге Epaxos оказался сложной и интересной темой, и я решил написать несколько постов о leaderless replicated state machine.
А потом оказалось что у меня куча дел и в итоге вы читаете первый пост только сейчас.

Наверно многие из вас в какой-то степени знают Raft/Paxos/MultiPaxos.
Исторически сложилось так, что Raft стал самым популярным алгоритмом для RSM.
Какие оптимизации (относительно запуска single decree Paxos в каждой ячейке реплицируемого лога, что очевидно проще) используются в нем?
1) То что у нас есть лидер, причем строгий, то есть никогда не может существовать несколько лидеров одновременно (это ключевое отличие от MultiPaxos, где тоже обычно есть лидер, но не строгий, выбираемый по иным правилам. А ещё это переносит livelock в Raft с фаз Prepare/Accept на выбор лидера, по сути остался только выбор лидера и Accept). Главное, эта оптимизация позволяет лидеру практически не сталкиваться с конкуренцией.
2) То что после фазы Prepare/выбора лидера мы отправляем Accept-ы батчами, это позволяет нам делать 1 rtt вместо 2 (без учёта клиента, которого редиректят на лидера, и собственно самого выбора лидера/первого Prepare для MultiPaxos)

К сожалению эти оптимизации не лишены недостатков:
1) Страдает доступность, ведь в случае каких-то проблем с лидером: падает, тормозит, сеть медленная, етс. У нас возникают проблемы в целом, от долгих перевыборов до чего то посложнее (пример решения части из них https://decentralizedthoughts.github.io/2020-12-12-raft-liveness-full-omission)
2) В случае WAN происходит 2 WAN коммуникации (клиент лидер, лидер фоловеры)
3) В целом так или иначе, но лидер это бутылочное горлышко

Поэтому мне кажется мысль, которая возникает у многих, особенно в случае WAN, а нельзя ли как-то оставить алгоритм leaderless, и при этом получить хороший throughput и низкую latency.

Собственно о статьях про такие алгоритмы я и хочу рассказать.

#leaderless_0

В процессе изучения темы, я столкнулся с тем что leaderless алгоритмы: EPaxos, FPaxos, Atlas, etc довольно сложны, при том что сам по себе Paxos довольно прост.

Так что начну я с обзора одной несложной статьи, автор которой опирается на собственные исследования в рамках CASPaxos (https://arxiv.org/abs/1802.07000)

Идея CASPaxos крайне проста: если state RSM меньше чем команда лога, компактный, то можно реплицировать его вместо лога. И выиграть как с точки зрения упрощения алгоритма, так и с точки зрения перфоменса, то есть в батчинге (можно отправлять/записывать результат не каждой отдельной команды батча, а его финальное состояние)

http://rystsov.info/2020/06/27/pacified-consensus.html:
Собственно идея самого алгоритма который позволит реплицировать leaderless и быстро произвольный RSM (а не только регистр) очень прикольна. Давайте возьмём условный MultiPaxos, и вместо того чтобы выбирать лидера, уменьшим конфликты засчет порядка на запросах клиентов, то есть сделаем батчинг, и определим позицию в логе заранее (сделаем это с помощью CASPaxos, так как реплицируемый стейт это просто набор запросов), а ещё этот CASPaxos можно не fsync-ать, так как даже если что-то разломается, сам наш алгоритм -- примитивный Paxos, и продолжит работать, пусть и медленее.

#leaderless_1

В общем можно посмотреть мой доклад по фьючам в яклибе:
https://youtu.be/VbWEJibHlg8

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

Кек, со мной такое в первый раз, я ещё думаю какого фига не открывается