# Replication algorhitms

- CURP - https://blog.acolyer.org/2019/03/15/exploiting-commutativity-for-practical-fast-replication/
- harpoon consensus
- raft consensus

https://en.wikipedia.org/wiki/Optimistic_replication

https://en.wikipedia.org/wiki/Master/slave_(technology)

https://stackoverflow.com/questions/413086/client-server-synchronization-pattern-algorithm

https://en.wikipedia.org/wiki/Operational_transformation

https://github.com/mitsuhiko/similar
https://github.com/dtolnay/dissimilar


https://en.wikipedia.org/wiki/Conflict-free_replicated_data_type

https://engineering.fb.com/2019/03/01/security/homomorphic-hashing/

## Варианты синхронизации

1. хранить время последнего изменения для диапазона записей и синхронизировать только эти диапазоны
2. проверять контрольную сумму для диапазонов записей, и синхронизировать несовпадающие
3. ?

**Вариант 1**. Например БД записывает время последнего изменения для каждых 100 ключей. Тогда нужно синхронизировать все диапазоны.
Например диапазон 0-100 был обновлен в 16:00, а на реплке в 15:00, значит есть обновления.

**Вариант 2** БД создает контрольную сумму для диапазонов.
Например диапазон 0-100 имеет контрольную сумму 5287, а на реплике 4432. Значит есть обновления.

В обеих вариантах можно постепенно сужаться до меньших диапазонов.

- Начиная от половины коллекции, потом делить на 2?
- Либо какие то постоянные, например 10, 100, 1000?
- Либо  256, 65536...?

То есть если у нас 1_000_000 записей, мы смотрим:
500_000, потом 250_000, 125к,  - в общем O(log), притом нужно по 2 раза искать контрольные суммы. Но получается при каждой итерации обходятся все пары ключ-значение!

Или при 1м записей: найти для 10 диапазонов по 100к, потом для 10 диапазонов по 10к, потом по 1к, 100, 10.
Так же происходит итерация по каждой паре ключ-значение.

Или наоборот, хэшировать все значения один раз?

**С новым алгоритмом:**
Мы можем вычислить хеш от всей бд, вычисляя хеш последовательно для чанков, вычислили хеш для 0-100 записей, для 100-200, и суммировали хеш. Отправили суммарный хеш, если он не совпадает то что?
Преимущество будет в возможности вычислить хеш параллельно, потом просто просуммировав хеши.

Нужно брать диапазоны по range, а не с chunk, так как значения могут удаляться, и вся коллекция будет с другими хешами.

Хранить ли хеши персистентно или генерировать каждый раз? Но как понять что хеш изменился? При обновлении данных удалять хеш?
Лучше всего, конечно, хранить персистентно, и обновлять некую атомарную переменную для пометки устаревшего хеша.
Плюс этого метода еще в том, что можно распараллелить вычисление хеша.
Можно так же вместе с хешом хранить время последнего изменения. При обновлении данных обновлять время последнего изменения и помечать хеш как устаревший. Зачем время последнего изменения?

Потом при синхронизации сравнивать хеш, если хеш устарел, то вычислять новый хеш и сравнивать с хешем на реплике. Если хеш не устарел, то просто сравнивать хеши.

Нужно делать неперекрывающиеся окна (chunks), что-то похожее на partition, с индексом. Передаем в функцию текущий индекс, функция возвращает окно (range?).

Окна удобно делать размером по степени 2. Например окна размером 1024 будет 10 бит.

**2^8 = 256**
512
1024
2048
4 096
8 192
16 384
32 768
**2^16 = 65536**
131 072
262 144
524 288
1 048 576
2 097 152
4 194 304
8 388 608
**2^24 = 16 777 216**
33 554 432
67 108 864
134 217 728
268 435 456
536 870 912
1 073 741 824
2 147 483 648
**2^32 = 4_294_967_296**

Минимальный bucket, batch, group, range будет 256? Но не обязательно 256?
Для миллиона записей будет 4000 бакетов.
Следующий уровень может быть 65536 записей, или 256 бакетов первого уровня.
Для 100 млн записей будет 150 бакетов 2 уровня.
То есть мы храним в памяти сортированную карту bucket_id->hash. В самом начале при синхронизации мы берем Tree, смотрим seq_id, делим его на количество тредов (например seq_id=1000_000, тредов 8), даем range каждому треду (thread1=0...125000, thread2=125000=250000 etc...). Вычисляем hash для каждого бакета. Отправляем хеши бакетов в другую сторону. Другая сторона делает тоже самое, вычисляет какие бакеты не совпадают, отправляет отличающиеся данные. Снова сверка и профит.
При обновлении записей мы пишем дату изменения и отметку, что бакет изменился.

Какой вид будет у bucket_id? Числовой или массив байт?

**id prefix**
0 54 => 0,0 = u8+u32
1 55 => 1,0
0 300 => 0,1
2 301 => 2,1

**StaticFormBodyId**: `form_id, status, id` = 654 1 4 => 2,1,0
Последний id и status можно опустить, будет form_id = 654 => 2 = u32 (form_id prefix)

**InviteId**: `space_id, id` = 0 1234 654 => 0,3,2 = u8+u32+u32
space_id prefix = u32

**AccessId**: `user_id, space_id, node_id` = 654 0 1234 1 654 => 2,0,3,1,2 = u32+u8+u32+u8+u32
Для каждого пользователя, пространства и для каждой заметки/группы тут будет запись.
Логично тогда делить на user_id prefix + space_id prefix + node_id prefix. Возможно стоит брать по 16 бит, а не 8.
Либо просто по user_id?

**VoteId**: `form_id, form_session_id, form_body_version, status, id, version` = `1234, 4, 4, 0, 300, 4` = `3,1,1,0,1,0` = `u32+u32+u32+u8+u32+u32`
form_id prefix + id prefix?
or just form_id prefix?

**BranchWithSpace**: `space_id, branch` = `0 1234 [12, 301, 1234]` => `0,3,[0,1,3...]` - where array max 8 items?
space_id prefix?

То есть бакет id у нас тоже будет составной, из чисел? Пока решили делать u32.

## Репликация

Сначала базы данных синхронизируются при соединении. Реплика отправляет хеш, если хеш не совпадает, оригинал отправляет хеши чанков реплике, та отвечает массивом несовпадающих хешей. Оригинал отправляет несовпадающие чанки, реплика их записывает, снова проверяет, если хеш совпадает, то синхронизация завершена. Далее идет стриминг новых данных.

Нужно реализовать конечный автомат.

1. при подключении master отправляет ReplicationInitReq (entity_id, instance_id, version, checksum)
2.
