У вас используется consistent hashing. Значит ли это, что нет необходимости в командах типа
list(prefix)? Еще интересно , а связка пользователя и его мэйлов в чем у вас хранится

А у вас же используется Version Vector а не Vector Clock? вот я часто путаю эти понятия. Пока для меня так, что если мы храним вектор для каждого значения K/V, то значит в системе Version Vector  https://martinfowler.com/articles/patterns-of-distributed-systems/version-vector.html

> У вас используется consistent hashing.

Да, у нас используется вариация на тему консистентного хеширования. Одно из существенных отличий - у нас ключи уже являются хешами, полученными с помощью криптографических функций, поэтому мы дополнительно для равномерного распределения по кольцу ключи уже не хешируем (а эта операция прибита гвоздями во многих библиотеках консистентного хеширования). У нас всё пространство ключей разбито на диапазоны, и за каждый диапазон отвечают RF каких-то физических нод. Для распределения диапазонов между нодами используется multi-probe consistent hashing.

> Значит ли это, что нет необходимости в командах типа list(prefix)?

Если имеется в виду получение списка всех ключей, начинающихся с префикса, то потребности именно в такой операции действительно нет. Но активно используется итерация по диапазону [prefix1, prefix2] - в сборщике мусора, в системе сбора статистики...

> Еще интересно, а связка пользователя и его мэйлов в чем у вас хранится

Это в документоориентированной базе, снаружи от объектного хранилища.

Я должен признаться, что сам не на 100% понимаю разницу между этими понятиями. Если посмотреть вот эту статью (https://haslab.wordpress.com/2011/07/08/version-vectors-are-not-vector-clocks/), то выходит так, что Vector Clock - это всегда счётчик с интами, а Version Vector может вместо интов использовать limited set of symbols, то есть более экономичен по памяти? И поскольку у нас всё на интах, это значит, что у нас Vector Clock. С другой стороны, если опираться на определения из статьи Фаулера, то получается, что у нас вполне классический Version Vector. Кажется, что различие между эти терминами очень тонкое, скорее всего, одно даже является обобщением другого.

И мы не одиноки в этих вопросах: https://github.com/gabrielgiussi/cappio/issues/105

Спасибо за ответ!

В книге distributed systems for practitioners
Вот прочел такое

Version vectors maintain state identical to that in a vector clock, containing
one integer entry per node in the system. The update rules are slightly
different: nodes can experience both local updates (e.g. a write applied at a
server) or can synchronize with another node (e.g. when recovering from a
network partition)

У меня  вопроса
1)
Вот тут интересно.  Если у нас есть координатор, который подготовил write request
и разослал его другим нодам. другие ноды могут иметь свое версию(они увеличат свои каунтеры)
или они все будут ту, которую подготовил координатор?

2) Интересно, вот есть момент, который не совсем понятем мне. Может кто знает?

Размерность векторных часов если равна количеству нод в кластере, а не количеству
клиентов, то какой traid-off мы делаем? Интересно было бы найти пример для осознания
этого компромисcа

О, что это за книга такая интересная?

В целом она про тоже , что и кабанчик. Но у Клепмана про многое написано очень широко и нужно по многим пунктам копать в других источниках, а вот эта мне понравилась тем, что тут локальнее что ли все ). Например про проблематику распределенных транзакций и недостатки 2PC, 3PC в этой мне больше понравилось https://leanpub.com/distributed-systems-for-practitioners#:~:text=Learn%20the%20basic%20principles%20that,the%20space%20of%20distributed%20systems.

ох спасибо

Еще вопрос такой есть. может кому интересно обсудить. Вот есть у нас условный пейпер Dynamo. там написанно, как они  используются vector clock и возможность настройки кворума. т.е мы можем настраивать W,R. Можно ли этими настройками добиться строгой консистентности? Как по мне так не можем, если даже мы установим W+R >N т.к у нас допускается сохранение конкурентных значений для ключа. Как я понимаю это происходит из-за того, что вот нет идеи в Динамо резолвить конфликты на записи. А строгая консистентность подразумевает, что значение всегда одно у ключа. Т.е ведь даже в leader less репликации мы можем иметь строгую консистентность, если будет отлеживать конфликты и резолвить их в момент записи.Динамо умеет отслеживать их, но не умеет резолвить при записи, а предлагает резолвить при чтении. Что скажете?

Вот например у нас есть 4 ноды в динамо. A,B,C,D.
Мы сказали, что фактор репликации 2.
Вот 2е пишут одновременно в кластер по ключу k1.
Preference list для этого ключа k1 = это ноды B,C.
Один законектился на ноду A и пишет пару k1/v1, а другой на ноду D и пишет пару k1/v2.
Эти ноды стали координаторами для запросов.
и соответственно послали (k1,v1) ,(k1,v2) на ноды B,C.
Так получилось , что (k1,v1) пришел сначала на B, а потом на C.
а от D пришло наоборот сначала на C, когда там еще ничего не было , а потом на B,.
В итоге мы получим для k1
на B
({B:1},v1)
({B:1},v2)
на C
({C:1},v2)
({C:1},v1)

Если теперь любой клиент сделает запрос по ключу
k1, то ему вернутся 2 значения этого ключа. Вроде
все клиенты видят одно и тоже, но ведь это не строгая
консистентность? так я понимаю что при строгой консистентности(Linearizability) такого быть не должно.

Да, мне кажется вы абсолютно здраво мыслите

в контексте того что fsync в nvme не консистентен (там гарантия достигается в серверных моделях путем установки конденсатора. который должен помочь правильно все записать) мы и в Postgres то локальном добиться консистентности не можем =)

вообще с консистентностью сейчас большинство распределенных opensource систем скатываются в eventually consistency
то есть если не вносить новых данных и все ноды активны, то "все станет консистентно, через какое то время"

в качестве примера EC почему-то вспоминается всегда DNS

А как интересно в биткоине добиваются строгой консистентности? там же наверное леадер лесс репликация

имхо, она там формально не строгая, просто ставка на то, что среди всего гигантского количества пиров-держателей блока ошибок будет меньше 50% по любым причинам

Спасибо за пояснение, ну да - теперь становится более-менее понятна разница.

Тогда у нас точно version vector, так как у нас поддерживаются оба варианта обновления часов. Локальный счётчик  в version vector ноды-обработчика запроса /координатора инкрементируется при запросах на запись.

Этот апдейт синхронно (по протоколу репликации) от ноды-обработчика получают несколько других нод, вовлеченных в обработку этого запроса (реплики индекса). Они видят запрос на запись и видят присовокупленное к нему значение version vector. Берут поступивший от координатора экземпляр и мержат в собственный экземпляр version vector. При этом, естественно, у них изменяется не локальный счётчик, а счётчик, соответствующий координатору.

Далее version vector уже асинхронно распространяется по всем остальным членам кластера с помощью gossip протокола

Честно скажу, что не очень понимаю, как в реальной жизни должен выглядеть вариант с client_id вместо node_id внутри векторных часов.

Вот представим себе инфраструктуру Google, Yandex, Facebook. Во всех подобных компаниях, согласно учебнику Бунина по хайлоаду, обязательно есть шина данных, которая внутри очень сложная, а снаружи очень простая, и всем прикладным разработчикам удобно ей пользоваться. Учитывая масштабы этих компаний, количество инстансов клиентских сервисов может исчисляться десятками тысяч, они stateless и довольно волатильны, могут пачками создаваться и удаляться. Как для них поддерживать консистентое видение client_id в рамках кластера? Что произойдёт с данными в хранилище, если пара узлов получат один и тот же client_id? Или это наоброт нормальная ситуация и только так и надо?

Ну и я всё-таки исхожу из того, что количество нод в хранилище на порядок меньше, чем количество его возможных клиентов. Поэтому векторные часы c node_id будут гораздо компактнее, чем с client_id

Поправьте меня плз, если не так понимаю эту концепцию...

В целом согласен, только я не совсем понял, как сделать ресолвинг конфликтов при записи. В данном случае ресолвинг конфликтов == их полное превентивное предотвращение? То есть pessimistic concurrency control?

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

Поскольку в описываемом примере произошли конкурентные апдейты, то linearizability тут не соблюдается

Полюбопытствую, кто-то из присутствующих при эксплуатации СУБД в продакшене вообще включает fsync?