⭐️ Гарантии упорядоченности

➡️ Причинно-следственная согласованность

Это гарантия расположения событий в причинно-следственном порядке: один узел читает данные, а затем вносит изменения, другой узел читает эти изменения и в свою очередь что-то пишет и т. д.

Например, история Git похожа на график причинно-следственных зависимостей.

➡️ Упорядоченность по порядковым номерам

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

Для упорядочения событий можно использовать порядковые номера, генерируемые счетчиками. Каждая операция имеет уникальный порядковый номер. Всегда может определить, какой номер больше и, следовательно, какая операция произошла позже.

В случае репликации с одним лидером мы спокойно присваиваем номера операциям на лидере и передаем их на реплики.

Как упорядочить записи, если единого ведущего узла нет?

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

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

Например, у нас всего 2 узла. Счетчик одного генерит четные номера, другого — нечетные. Они не смешаются и не создадут проблем. Но можем ли мы сказать, что операция 115 была позже операции 100? Не всегда, ведь нечетный узел может обрабатывать запросы быстрее (в силу своей мощности или легкости запросов). В итоге 115-я операция с нечетного узла могла произойти раньше 100-й операции с четного узла.

💡Для решения проблемы упорядоченности есть метод временных меток Лампорта:

👉 Каждый узел имеет уникальный идентификатор и счетчик количества обработанных им операций. Временная метка Лампорта — это пара «счетчик, ID узла».
👉 Каждый узел и каждый клиент отслеживают максимальное значение счетчика, встречавшееся им до сих пор, и включают это значение максимума в каждый запрос.
👉 Когда узел получает запрос со значением счетчика, бóльшим, чем его собственное, он сразу увеличивает свой счетчик до этого максимума.

➡️ Рассылка общей последовательности

Рассылка общей последовательности — это протокол обмена сообщениями между узлами. Он требует выполнения двух пунктов:
‰
‰✅ Надежная доставка. Ни одно сообщение не должно быть потеряно. Если сообщение доставляется одному узлу, то оно доставляется всем узлам.
‰
‰✅ Полностью упорядоченная доставка. Сообщения доставляются во все узлы в одном и том же порядке.

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

Где используется рассылка общей последовательности:

🟡для репликации БД

🟡в сервисах консенсуса (ZooKeeper и др.)

🟡для реализации сервиса блокировки, которая предоставляет ограждающие маркеры

Применение ограждающих маркеров рассматривалось в главе 8.
Каждый запрос на получение блокировки заносится в журнал и последовательно нумеруется. Порядковые номера могут служить маркерами-ограничителями, поскольку монотонно возрастают. В ZooKeeper такие порядковые номера называются zxid.

#кабанчик #сисдиз