Fair raft join

This patch already has 51 commit squashed. It itcludes changes related to raft join, but also has lots of refactoring.

Close #32 (closed)

docs/clustering.md

-# Создание кластера. Алгоритм и детали реализации.
+# Инициализация кластера. Высокоуровнево.
 
-## fn main()
+Админ запускает пачку инстансов:
 
+```sh
+picodata run --instance-id i1 --listen i1 --peer i1,i2
+picodata run --instance-id i2 --listen i2 --peer i1,i2
+picodata run --instance-id i3 --listen i3 --peer i1,i2
+# ...
+picodata run --instance-id iN --listen iN --peer i1,i2
 ```
-// Каждый инстанс обладает на старте следующей информацией:
-// --advertise-uri (по-дефолту <hostname>:<listen_port>)
-// --replicaset-id (опционально)
-// --instance-id (опционально)
-// --peers
-```
 
-1. Если у инстанса уже есть снапшоты, можно сразу вызывать box.cfg() и стартовать рафт ноду.
-1. Инстанс идёт собирать транзитивное замыкание в дочернем процессе.
-1. Дочерний процесс поднимает listen порт и высовывает хранимку raft_discover.
-1. Дочерний процесс пробегается по всем --peer, обменивается с ними этими списками, а заодно получает айдишники (instance_id, replicaset_id) и advertise_address.
-1. Возможно ответом будет "нечего тут собирать, у нас уже есть лидер такой-то", тогда можно пойти сразу на него и goto *join*.
-1. Как только ото всех пиров (известных изначально, и обнаруженных в процессе) получен утвердительный ответ, транзитивное замыкание считается собраным.
-1. Транзитивное замыкание гарантирует нам одинаковость собранной информации на всех инстансах, в этом сборе участвовавших.
-1. Теперь выбираем кто будет главным. Для этого сравниваются лексикографически все instance_id. Этот инстанс присваивает себе raft_id = 1, генерит снапшот рафт ноды с одним собой любимым, персистит его, и начинает тикать нодой. Бутстрап первого инстанса закончен.
-1. Остальные инстансы goto *join*
-
-### join
-
-1. Если нас послали делать джойн, значит адрес лидера уже известен. Либо нам его сказали в ответе на raft_discover, либо мы его сами вычислили из транзитивного замыкания.
-1. Инстанс идет на лидера и говорит: "приджойнь меня в кластер, пожалуйста". Попутно сообщает свои айдишники и адвертайз урл.
-1. И лидер приджойнивает. И любезно сообщает в ответ raft_id нашей ноды. А ещё правильный instance_id и replicaset_id, и урлы братьев по репликации.
-1. Обладая этой информацией, инстанс стартует box.cfg с параметрами репликации.
-1. Потом создает сервисные рафтовые спейсы и стратует рафт ноду.
-1. И вот теперь то бутстрап окончен.
-
-## fn raft_discover()
-
-Если транзитивное замыкание еще не собрано, сервер на запрос raft_join присылает свой адвертайз, айдишники, и все пиры.
-
-Если нода давно забутстраплена, сервер отвечает "у нас уже есть лидер", достает его raft_id из статуса рафта, а по raft_id - его адвертайз из спейса с рафт топологией.
-
-На запрос raft_discover есть и третий вариант ответа, когда транзитивное замыкание уже собрано, но сама рафт нода еще не проинициализирована. В этом случае серверу правильнее отдавать значение advertise_uri первого инстанса, вычисленное из транзитивного замыкания. Именно оно прилетит из рафт снапшота как только нода поднимется.
-
-## fn raft_join()
-
-1. Во-первых, если это на самом деле не лидер, надо вернуть ошибку.
-1. Из аргументов известны айдишники и адвертайз адрес клиента.
-1. В ответ надо дать raft_id.
-1. Ещё в ответе должны быть replicaset_uuid (правильно сгенеренный, либо выбранный среди существующих), instance_uuid (ну так, за компанию), урлы других инстансов из его репликасета, чтобы он сразу мог забутстрапить репликацию. Всё это раздаётся из таблички с топологией, но сначала её надо туда положить, причем класть надо средствами рафта.
-1. Будущий raft_id выбирается как box.space.raft_topology:max() + 1
-1. Алгоритм выбора replciaset_uuid и instance_uuid мы пока не обсуждаем, пусть пока это будет чистый рандом.
-1. Коммитить в рафт изменение топологии надо пачкой - в propose_conf_change надо упихать всю инфу об инстансе, иначе инфа может разъехаться.
-1. Есть и ещё одна проблема. Тк комит в рафт - штука не быстрая, другие конкурентные запросы (от других инстансов) всё это время будут получать отлуп типа "conf change already in progress". Это может сильно замедлить сборку больших кластеров.
-1. Чтобы ускорить процесс джойна, запросы на джойн должны вставать в очередь, и обрабатываться траншами.
-1. Ни один клиент не уйдёт обиженным, получит свой raft_id, и сможет запуститься
+Сколько бы инстансов ни было, в опции `--peer` у каждого следует указать один и тот же набор из нескольких "первых". На них возлагается особая миссия по инициализации кластера (дискавери).
+
+Подробный алгоритм дискавери в этой истории роли не играет, но описан в соседнем файле `discovery.md`. Пока об алгоритме дискавери достаточно знать лишь то, что, следуя этому алгоритму, один и только один из этих пиров возьмет на себя смелость создать рафт группу. Иначе рафт групп получилось бы неколько.
+
+Всё управление топологией рафт группы по сути возлагается на сам алгоритм рафт. И на его конкретную имплементацию - крейт `raft-rs`.
+
+# Инициализация кластера. Подробнее.
+
+[https://yuml.me/edit/15c7c2d0]
+
+![main.rs](main_run.svg "main.rs control flow")
+
+Эта устрашающая схема максимально точно изображает логику кода в `main.rs`. Ниже объясняется подробнее, что происходит на каждом этапе.
+
+### fn main()
+
+Сначала процесс пикодаты форкается. Родитель (supervisor) ждет по механизму IPC сообщения от дочернего процесса и при необходимости рестартит его. Опционально дочерний процесс может попросить родителя дропнуть все файлы БД. Это будет нужно для т.н. ребутстрапа.
+
+### fn start_discover()
+
+Дочерний процесс начинает своё существование с вызова `box.cfg()` и вызова функции `start_discover`.
+Если вдруг из спейсов обнаруживается, что нода уже была забутстрапленна, то никакой алгоритм дискавери делаь и не надо, и инстанс сразу переходит на этап `postjoin()`. В противном случае, если это первый запуск, из алгоритма дискавери мы получаем флаг `its_me` и адрес лидера. Сам лидер (единственный `its_me == true`) выполняет `start_boot`, после чего выполняет `postjoin()`. Остальные инстансы (не только проигравшие пиры, но и все будущие) ребутстрапятся и идут делать `start_join`.
+
+
+### fn start_boot()
+
+В функции `start_boot` происходит инициализация рафт группы - лидер генерирует и персистит первую запись в журнале. В этой записи будет лежать операция добавления ноды, что позволит всем остальным инстансам инициализироваться с пустой рафт группой.
+
+Саму рафт ноду инстанс на этом этапе не создаёт. Это произойдет позже, на стадии `postjoin()`.
+
+### fn start_join()
+
+Вызову `start_join` всегда предшествует ребутстрап (удаление БД и рестарт процесса), поэтому ни бокса, ни спейсов на этом этапе снова нет. Сама функция достаточно примитивная.
+
+Инстанс отправляет запрос `join` на лидера (лидер известен после дискавери). Лидер шушукается с группой, и если всё хорошо, в ответ присылает необходимую информацию:
+- `raft_id` и `raft_group` - для инициализации рафт ноды;
+- `insance_uuid`, `replicaset_uuid`, `replication`, `read_only` - для `box.cfg`.
+
+Получив все настройки, инстанс засовывает их в `box.cfg()`, и после этого персистит `raft_group` с актуальными адресами других инстансов. Без этого инстанс не сможет отвечать на рафт сообщения. А чтобы записи в `raft_group` не были потёрты менее актуальными из рафт лога, каждая маркируется значением `commit_index`.
+
+После всех этих манипуляций, также идёт `postjoin()`.
+
+### fn postjoin()
+
+Логика `postjoin()` для всех инстансов одинакова. К этому моменту на инстансе уже инициализированы правильные спейсы и возможно даже существует предыстория рафт журнала. Инстанс инициализирует рафт ноду и получает read barrier (это позволяет убедиться, что рафт лог актуален). Из рафт лога становятся известны параметры репликации, и инстанс синхронизируется с репликами.
+
+Остаётся один маленький штришок - проверить свой статус voter / learner, при необходимости кинуть запрос на промоут до воутера (всё тот же `join`, лидер известен после получения read barrier), и дождаться его применения.
+
+Всё, нода готова к использованию.
+
+# Обработка запросов
+
+### extern "C" fn join()
+
+Львиная доля всей логики по управлению топологией кроется в хранимке `join`. Её назначение достаточно простое - закоммитить ConfChange, но за этими словами кроется несколько нюансов.
+
+Во-первых, если этот `instance_id` уже есть в группе (закоммиченый) и никакая информация не обновилась (например флаг voter / learner), то можно сразу отвечать клиенту не задействуя рафт.
+
+Если это первое появление инстанса в группе, то он всегда добавляется в роли learner. В роли voter его добавлять нельзя, иначе появится проблема курицы и яйца. Чтобы ConfChange с воутером закоммитился, этот voter должен участвовать в кворуме. А он не может - он ещё ждёт ответа на запрос `join`.
+
+Во-вторых, рафт не позволяет делать ConfChange, если предыдущий ConfChange не был закоммичен. Поэтому запросы `join` на лидере придётся обрабатывать батчами в отдельном файбере. Пачку запросов накопили - обработали - каждому послали индивидуальный ответ.
+
+В-третьих, прежде чем отвечать клиенту, надо дождаться, пока ConfChange закоммитится. Или, более формально, пока лидер не выйдет из т.н. joint state (см. рафт диссер §4.3). После этого можно отвечать клиенту `raft_id`, `raft_group`, `insance_uuid`, `replicaset__uuid`, `replication`, `read_only`. В будущем состав ответа может дополняться новыми параметрами по мере необходимости.
+
+- `raft_id` генерит лидер, и делает это строго последовательно и атомарно на весь батч.
+- `raft_group` представляет собой дамп всего спейса с топологией кластера. Он понадобится новому инстансу чтобы знать адреса соседей и нормально с ними общаться.
+
+И, наконец, где-то здесь же надо будет убедиться, что нода является лидером, когда генерит `raft_id`. У остальных нет на это права.
+
+# TODO
+
+Q: провести эксперимент, может ли ConfChange пролезть в MsgPropose?
+A: Может
+
+Q: провести эксперимент, можно ли параллельно отравлять simple_conf_change, или это только v2 касается?
+A: Пофиг, simple у нас только один в логе - самый первый.
+
+Q: правда ли, что пропоуз сразу после коммита не потеряется, и не задублируется?
+A: нет, коммит на фоловерах может прийти, а пропоуз потеряется. тогда у нового лидера не будет подходящего момента, чтобы восполнить эту утрату.  Именно поэтому за промоутом до воутера следит сам фоловер.
+
+Q: может ли фоловер (не лернер) слать другому фоловеру MgsAppend закомиченных энтрей?
+A: ???