Информатика · объяснение и практика
CAP начинается с точных определений ответа и согласованности при разрыве связи
Разобрать невозможность одновременно гарантировать линеаризуемый регистр и доступность на обеих сторонах сетевого разделения в асинхронной модели.

В теме Компьютерные сети и веб · Учебная карта
Главная мысль
В формальной постановке CAP согласованность означает атомарное, линеаризуемое поведение, а доступность — завершение каждого запроса к неотказавшему узлу. Во время разделения сети эти требования несовместимы для нуждающегося в обмене реплицированного регистра.
Метод и постановка
Начните с конкретного объекта, а не с выбора двух букв. Пусть две реплики хранят регистр, первоначально равный нулю, и перестали получать сообщения друг от друга. На первой стороне клиент записывает единицу и получает успешный ответ. После этого на второй стороне вызывается чтение. Реальный порядок требует, чтобы завершённая запись предшествовала этому чтению.
Вторая реплика не отличает ситуацию с новой записью от ситуации, где никакой записи не было, потому что сообщения через разделение не проходят. Если она обязана закончить чтение, один и тот же доступный ей локальный опыт должен привести к ответу. Но линеаризуемая спецификация требует разных значений в этих двух историях. Если вместо ответа ожидать подтверждения другой стороны, нарушается указанная гарантия доступности.
Проверка и границы вывода
Доказательство использует точные определения. Ошибка ответа не считается успешным выполнением обычного чтения регистра только потому, что сервер вернул пакет. Также ограниченная эксплуатационная доля успешных запросов не тождественна квантору «каждый запрос завершится» в теореме. При обсуждении реальной системы эти метрики нужно назвать отдельно.
CAP не утверждает, что без разделения всегда надо отказаться от одной из гарантий, и не сводит все варианты согласованности к одному слову. Более слабые модели, ожидание восстановления связи и выбор стороны, которой разрешены записи, меняют поведение и договор с клиентом. Частичная потеря доступности может быть сознательным способом сохранить согласованность. В отчёте укажите, какие узлы не отказали, какие сообщения задержаны и какие операции обязаны завершаться; только после этого формальный конфликт становится проверяемым.
Пример
Реплики L и R изолированы. На L завершилась запись 7, после её ответа началось чтение на R. В истории без записи R видит те же локальные сообщения, но правильное начальное значение равно нулю.
Ответ 0 нарушает линеаризуемость истории с записью 7. Ответ 7 без информации нарушил бы историю без записи. Бесконечное ожидание сохраняет возможность правильного ответа позже, но не выполняет доступность во время разделения.
От чтения к действию
А теперь — вы
Частые вопросы
CAP означает всегда выбрать любые две буквы?
Такая фраза скрывает условия; конфликт проявляется при сетевом разделении в указанной модели.
Линеаризуемость и eventual consistency одинаковы?
Нет. Они допускают разные истории чтений и записей, поэтому теорему нельзя переносить без определения гарантий.
Углублённый разбор
Причинный порядок зависимых записей при разделе
Причинная согласованность запрещает показывать следствие раньше его зависимостей, но допускает старые данные при отсутствии связи. Для реализации такого порядка полезно отделять физическое получение сообщения от разрешения сделать его видимым.
Перед началом: Причинное предшествование; Векторные счётчики событий.
Зависимость возникает из порядка действий и прочитанного результата
Если процесс сначала видит обновление конфигурации, затем создаёт задание, опирающееся на него, запись задания причинно зависит от конфигурации. Другая реплика не должна показывать это задание в представлении, где необходимая версия конфигурации ещё отсутствует. Независимое обновление аудита может оставаться конкурентным и не обязано занимать одно глобально согласованное место относительно обеих записей.
Причинный порядок является частичным. Он сохраняет локальную последовательность и передачу знания через сообщения или чтения, а также их транзитивные следствия. Само сравнение настенных часов недостаточно: более поздняя отметка не доказывает зависимость, а рассинхронизация часов может поменять численный порядок реально связанных действий.
Вектор позволяет проверить готовность сообщения
В учебной модели каждому из трёх источников выделена координата. Получатель хранит v — сколько событий каждого источника уже опубликовано. Сообщение источника j с меткой t можно опубликовать, если tⱼ=vⱼ+1 и tᵢ≤vᵢ для остальных i. Первое условие сохраняет порядок самого источника, остальные требуют наличия всех объявленных зависимостей.
Сообщение, не прошедшее проверку, сохраняется в буфере. После каждой публикации условия буферных сообщений проверяются снова. Это отделяет приход пакета от наблюдаемого изменения состояния. Модель предполагает последовательные номера источника и корректное включение причинного контекста в метку; произвольный недостоверный вектор не даёт нужной гарантии.
Разделение связи не добавляет недостающие зависимости
При разрыве связи реплика может продолжать показывать старое причинно замкнутое состояние и принимать независимые локальные действия. Но клиент, перешедший с контекстом недоступной зависимости, может потребовать ожидания или другого явно оговорённого поведения. Нельзя одновременно обещать ему немедленную видимость всех зависимостей и считать, что отсутствующие данные уже доступны.
Причинная согласованность также не решает автоматически конфликт конкурентных записей одного ключа и не сохраняет произвольный бизнес-инвариант. Для этого нужны дополнительные правила разрешения конфликтов или координации. В тесте проверяйте замкнутость множества видимых событий: если видно следствие, каждая его зависимость уже должна быть опубликована. Простого совпадения конечного состояния после восстановления связи недостаточно.
Следствие приходит первым
Условие. Получатель начинает с v=(0,0,0). Конфигурация X имеет метку (1,0,0), зависимое задание Y от второго источника — (1,1,0), независимый аудит Z — (0,0,1). Пакеты приходят в порядке Y,Z,X.
- Y пока нельзя опубликовать: его первая координата требует уже известное событие X, но v₁=0. Сообщение остаётся в буфере.
- Z проходит проверку третьего источника: его номер равен одному, остальные зависимости нулевые. После публикации v=(0,0,1).
- X также готово и меняет v на (1,0,1). Теперь недостающая зависимость Y появилась.
- Повторная проверка буфера разрешает Y: во второй координате следующий номер один, а первая и третья зависимости удовлетворены. Итоговый вектор (1,1,1), порядок видимости Z,X,Y.
Ответ. Y буферизуется до X; независимое Z публикуется сразу.
Проверка. Точный симулятор предиката готовности перебирает все шесть порядков прихода: в каждом опубликованное Y следует после X, а все три события в итоге доступны.
Где легко ошибиться. Порядок получения пакетов не является причинным порядком видимости. Буфер и повторная проверка зависимостей — необходимые части описанной модели.
Проверьте понимание
Вопросы к этой главе
Почему Z можно показать раньше X?
Между ними нет причинной зависимости в заданной истории. Причинная модель не требует общего порядка всех независимых обновлений на всех репликах.
Вектор доказывает актуальность данных?
Он подтверждает выполнение объявленных зависимостей относительно опубликованного префикса. Он не обещает получение всех последних удалённых записей во время разделения связи.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Lloyd et al.: COPS, causal+ consistency
Прочитаны причинные зависимости и проверка наличия зависимостей перед публикацией записи. Собственная трёхисточниковая модель доставки использует векторные счётчики как учебный механизм; она не выдаётся за точную структуру метаданных COPS.
Полурешётка слияния состояния CRDT
Слияние состояния CRDT можно обосновать порядком информации: локальные изменения только добавляют знание, а merge вычисляет точную верхнюю грань. Видимое множество при этом способно уменьшаться, если удаление хранится как новая монотонная информация.
Перед началом: Частичный порядок; Объединение множеств.
Состояние и результат запроса имеют разные порядки
В двухфазном множестве хранят пару (P,N): P содержит когда-либо добавленные элементы, N — отмеченные удаления. Запрос возвращает P∖N. Порядок состояний покомпонентный по включению, а слияние равно (P₁∪P₂,N₁∪N₂). Это наименьшая верхняя грань: она содержит обе пары и входит в любую другую общую верхнюю границу.
Добавление увеличивает P, удаление увеличивает N; удалять можно уже наблюдённый элемент. Оба изменения монотонны в порядке полного состояния. Видимый результат запроса не обязан расти: добавление tombstone убирает элемент из P∖N, хотя общий объём знания увеличился. Поэтому монотонность CRDT нельзя проверять только по количеству элементов на экране.
Алгебра слияния устраняет зависимость от доставки
Объединение множеств коммутативно, ассоциативно и идемпотентно. Следовательно, порядок получения состояний, группировка слияний и повторная доставка одного состояния не меняют итоговую пару. При доставке всех обновлений реплики сходятся к одной верхней грани. Условие доставки остаётся существенным: навсегда потерянное обновление не появляется из одних алгебраических законов.
Эти свойства относятся к состояниям, а не к произвольной последовательности команд add/remove. Повторно применить присланное полное состояние безопасно; повторная команда с новой семантикой может быть другой операцией. Также общая сходимость не означает линеаризуемость: во время разделения разные реплики могут отвечать по разным причинно допустимым состояниям.
Tombstone меняет допустимую семантику повторного добавления
Если элемент попал в N, простое последующее добавление того же имени в P не вернёт его в результат. Двухфазное множество разрешает добавить элемент, затем удалить, но не воскресить тот же элемент. Для повторного логического добавления нужны новые идентичности или другой тип множества, например с тегами наблюдённых добавлений. Нельзя незаметно очистить N ради удобства интерфейса.
Очистка tombstone требует отдельного протокола, доказывающего, что старые состояния больше не смогут вернуть удалённый элемент. Иначе поздняя реплика создаст расхождение. В независимой проверке полезно перебрать все перестановки нескольких состояний, повторить одно из них и отдельно проверить, что merge действительно является наименьшей, а не просто некоторой верхней границей в выбранном порядке.
Удаления переживают повторную доставку
Условие. Три реплики имеют состояния A=({p,q},{p}), B=({p,q,r},{q}), C=({q,s},∅). Найдите общий merge, видимый результат и эффект повторного добавления q после слияния.
- Объединение положительных множеств равно {p,q,r,s}. Объединение tombstones равно {p,q}, поскольку удаление любого участника сохраняется.
- Общее состояние равно ({p,q,r,s},{p,q}), поэтому запрос возвращает {r,s}. Порядок слияний A,B,C не влияет на эту пару.
- Повторная доставка B ничего не меняет: оба его компонента уже содержатся в общем состоянии. Это идемпотентность по полному состоянию.
- Повторное добавление q лишь оставляет q в P, где оно уже есть. Поскольку q сохраняется в N, видимый результат остаётся {r,s}; воскресить q данной операцией нельзя.
Ответ. Merge=({p,q,r,s},{p,q}), запрос {r,s}; повторное add(q) не восстанавливает q.
Проверка. Перебор всех шести порядков и повторов даёт одну пару; перебор верхних граней на конечном универсуме подтверждает её наименьшесть.
Где легко ошибиться. Не удаляйте tombstones без доказанного протокола очистки. Видимое множество и монотонное состояние — разные объекты, а двухфазное множество запрещает обычное повторное добавление удалённого имени.
Проверьте понимание
Вопросы к этой главе
Почему это не просто объединение видимых множеств?
Видимые множества A и B не сохраняют все сведения об удалениях. Их простое объединение могло бы вернуть p или q, тогда как слияние полного состояния сохраняет tombstones.
Сходимость защищает любой инвариант приложения?
Нет. Алгебра гарантирует одинаковый результат после получения одинаковых обновлений. Бюджетные ограничения и взаимные исключения могут потребовать отдельной координации или иной структуры данных.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Shapiro et al.: Convergent and Commutative Replicated Data Types
Прочитаны §2.2 достаточные условия монотонной полурешётки и §3.2.1 state-based 2P-Set с tombstones. Собственные три состояния и все порядки их слияния проверены отдельно. HAL-документ был закрыт Anubis; прочитан авторский PDF LIP6.
Номер эпохи запрещает запись просроченному владельцу аренды
Истёкшая аренда не останавливает клиентский процесс и уже отправленные пакеты. Безопасность записи можно перенести на сам ресурс: каждая новая эпоха получает больший номер, а хранилище атомарно отклоняет запросы ниже уже установленного барьера. Это правило отделено от дедупликации повторных команд.
Перед началом: Аренда ресурса; Атомарное обновление.
Проверка клиентских часов не отзывает отложенный пакет
Клиент может получить аренду, проверить её срок, затем остановиться на неопределённое время перед записью. Другой клиент успеет получить следующую аренду и изменить ресурс. Возобновившийся первый клиент продолжит старый код или его пакет лишь теперь придёт в хранилище. Повторная локальная проверка тоже не закрывает промежуток между проверкой и фактическим изменением удалённых данных.
Сервис выдаёт строго возрастающий token при каждой новой эпохе владения. Ресурс хранит high-water mark M. Запрос с t<M отклоняется; запрос с t≥M может выполнить свою команду и установить M=max(M,t). Проверка, изменение данных и сохранение M должны составлять одну атомарную операцию. Иначе два обработчика могут оба пройти старую проверку, после чего запоздалый обработчик испортит уже новое состояние.
Барьер установлен на ресурсе, а не в воображении клиента
После принятия token42 никакой запрос с token41 уже не изменит ресурс. Это инвариант монотонности M; он сохраняется индукцией по принятым операциям. Однако до первого принятого запроса новой эпохи хранилище может ещё не знать о её существовании. Одно истечение срока аренды или выдача token42 на другом сервере не делает локальный M автоматически равным 42.
Если требуется запретить старую эпоху до начала любых новых действий, новая эпоха сначала устанавливает барьер на самом ресурсе и получает подтверждение. Сохранённый M нельзя терять при перезапуске, а номера нельзя повторно выдавать после сбоя сервиса аренды. Для нескольких независимых ресурсов проверка каждого token не создаёт общей транзакции между ними: это дополнительная задача протокола.
Равный token не означает повтор той же операции
Один владелец может выполнить несколько различных записей в своей эпохе, поэтому правило допускает равный M номер. Повтор пакета с тем же token тоже пройдёт этот фильтр. Для команды «увеличить счётчик» это может дать два увеличения. Отдельный идентификатор команды и устойчивый результат нужны для дедупликации; fencing отвечает на другой вопрос — имеет ли запрос достаточно новую эпоху. Случайный уникальный идентификатор без порядка не заменяет сравнение поколений.
Четыре запроса к одному барьеру
Условие. Изначально M=40, значение 0. Последовательно приходят команды (token42,set7), (token41,set99), (token42,set8), (token43,set9). Используется атомарное правило t≥M. Найдите принятие каждой команды и итог.
- Первая команда имеет 42≥40: значение становится 7, барьер 42. Это первый подтверждённый ресурсом шаг новой эпохи.
- Вторая команда имеет 41<42 и отвергается без изменения данных. Старый клиент не может заменить 7 на99.
- Третья команда имеет равный token42 и допускается: значение 8, M остаётся 42. Правило не считает её дубликатом первой команды.
- Четвёртая команда 43 повышает барьер и записывает 9. Итог M=43, значение 9; все последующие запросы ниже 43 будут отвергнуты.
Ответ. Приняты первая, третья и четвёртая команды; вторая отклонена. Итоговое значение 9, барьер 43.
Проверка. Прямое проигрывание автомата ресурса даёт пары (M,value): (40,0),(42,7),(42,7),(42,8),(43,9). Во всех переходах M не убывает. Если поменять первые два пакета местами,41 успеет пройти до установки 42 — это точная граница гарантии.
Где легко ошибиться. Не выдавайте token только клиенту, оставляя ресурс обычным слепым хранилищем. Защиту создаёт проверка перед каждым изменением, причём с устойчивым и атомарно обновляемым барьером.
Проверьте понимание
Вопросы к этой главе
Должен ли token совпадать со временем?
Нет. Нужен надёжный порядок эпох, а не число миллисекунд. Счётчик поколений может быть логическим. Его строгая монотонность и сохранность после сбоев важнее сходства с настенными часами.
Достаточно ли token для единственного применения платежа?
Нет. Две доставки одной команды в разрешённой эпохе имеют одинаковый допустимый token. Нужен отдельный механизм идентичности операции и атомарного сохранения результата вместе с эффектом.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Martin Kleppmann: How to do distributed locking, Making the lock safe with fencing
Прочитан раздел о проверке монотонного fencing token самим хранилищем и задержанных запросах. Собственная трасса различает повышение барьера, повтор одной эпохи и отдельную дедупликацию. Более сильная гарантия отклонять всё сразу после истечения времени аренды не приписывается этому правилу.
Детерминированный автомат требует общего порядка команд
Одинаковый набор доставленных команд ещё не даёт одинакового состояния реплик. Для некоммутирующих операций нужен согласованный порядок применения. Уже согласованный журнал позволяет доказать совпадение индукцией по префиксу, а индекс применения отделяет повтор доставки от новой команды.
Перед началом: Детерминированная функция состояния; Порядок сообщений.
Набор команд слабее последовательности
Пусть состояние x числовое, команды A прибавляет 3, B умножает 4. При x=2 порядок A,B даёт 20, а B,A даёт 11. Обе реплики получили одинаковые команды по одному разу, но разошлись. Следовательно надёжная доставка и удаление дублей сами по себе не решают согласование порядка. Причинный частичный порядок тоже может оставить эти конкурентные команды несравнимыми.
Для детерминированной машины задаётся общая неизменная последовательность команд. Реплики начинают в одном состоянии и применяют одинаковый префикс в одинаковом порядке. Тогда равенство после k команд и одна и та же функция следующей команды влекут равенство после k+1. Это простая индукция по индексу журнала. Она предполагает, что сам журнал уже согласован; алгоритм его достижения и прогресс при разделении связи являются отдельными обязательствами.
Дырка в индексе запрещает преждевременное применение
Реплика хранит lastApplied и буфер принятых записей. Следующая допустимая запись имеет индекс lastApplied+1. Если пришёл индекс 2 раньше 1, его сохраняют, но пока не применяют. После появления 1 можно последовательно продвинуться через весь имеющийся непрерывный префикс. Дубликат уже применённого индекса не меняет состояние ещё раз.
В модели один индекс всегда имеет одну и ту же согласованную команду; разные содержимые под тем же индексом означали бы нарушение предпосылки, которое нельзя молча разрешать локальной догадкой. Состояние машины и lastApplied должны восстанавливаться согласованно после сбоя. Иначе потеря индекса при сохранённом эффекте позволит повторить команду. Чисто оперативный счётчик не даёт обещания устойчивого однократного применения.
Коммутативность ослабляет порядок только при проверенном наблюдении
Два прибавления коммутируют по конечному числовому состоянию, но прибавление и умножение обычно нет. Это можно проверить равенством f(g(x))=g(f(x)) для всех допустимых x, а не лишь для одного удачного начального значения. Если команды ещё возвращают прежний баланс, одинаковый конечный x сам по себе не гарантирует одинаковые клиентские ответы; наблюдаемые результаты тоже входят в спецификацию.
Повтор одного индекса отличается от повторного пользовательского намерения в новом индексе. Журнал применит оба разных индекса, если протокол допустил их туда. Защита от повторного запроса по идентификатору намерения решается отдельно. Также чтение локальной отстающей реплики не становится линеаризуемым лишь благодаря совпадению общего префикса: для такой гарантии нужны правила свежести чтений и отношения к завершённым операциям клиентов.
Запись 2 пришла раньше записи 1
Условие. Начальное x=2,lastApplied=0. Уже согласованный журнал:1:add3,2:multiply4,3:add−2. Реплика получает индексы в порядке 2,1,2,3. Применяйте только непрерывный префикс и игнорируйте повтор уже применённого индекса.
- Первый пакет 2 сохраняется в буфере. Индекса 1 ещё нет, поэтому x остаётся 2,lastApplied=0.
- После пакета 1 применяется add3: x=5,lastApplied=1. Теперь доступен сохранённый 2, и multiply4 даёт x=20,lastApplied=2.
- Повтор пакета 2 не выполняет умножение заново, потому что его индекс уже применён. Значения x=20 и lastApplied=2 сохраняются.
- Пакет 3 прибавляет−2: x=18,lastApplied=3. Прямое последовательное проигрывание согласованного журнала даёт тот же результат 18.
Ответ. Итог x=18,lastApplied=3; приход 2 перед 1 меняет ожидание, но не порядок применения.
Проверка. Перебор всех порядков доставки записей 1,2,3 с дополнительной копией 2 даёт одинаковый итог 18 и единственную трассу применённых индексов 1,2,3. Контрольное применение сразу при приходе 2,1,3 дало бы9 и нарушило бы заданный порядок.
Где легко ошибиться. Не подменяйте общий порядок одинаковым множеством пакетов и не считайте индекс журнала универсальной дедупликацией пользовательских действий в разных позициях.
Проверьте понимание
Вопросы к этой главе
Нужно ли ждать одинаковой скорости всех реплик?
Нет. Реплики могут применять разные по длине префиксы и временно отставать. Доказательство обещает одинаковое состояние при одинаковом применённом префиксе, а не одновременное завершение каждой доставки.
Как поступить с временем или случайностью внутри команды?
Если они влияют на результат, их нужно согласовать как часть входа либо использовать другой доказанный способ детерминизации. Независимый вызов часов или генератора на каждой реплике нарушает предпосылку одинаковой функции перехода.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Fred B. Schneider: Replication Management using the State Machine Approach, §2/§4
Прочитаны детерминированная машина и Replica Coordination: Agreement/Order, а также оговорки о коммутирующих командах. Собственный индексированный apply-автомат дан при уже согласованном неизменном журнале. Скан 86-800.pdf открылся с нечитаемой кодировкой и не использован вместо этой читаемой авторской версии.
Маркеры Чанди — Лэмпорта сохраняют согласованный глобальный срез
Снимок распределённой системы состоит не только из состояний процессов: часть данных может находиться в сообщениях между ними. Маркеры отделяют сообщения до локального снимка от последующих. Разберём согласованный срез без общих часов и проверим сохранение числа жетонов при двух сообщениях в пути.
Перед началом: Порядок отправки и приёма сообщения; Направленные FIFO-каналы и локальное состояние процесса.
Согласованность важнее общего момента часов
Глобальный срез выбирает префикс событий каждого процесса. Он согласован, если включённый приём сообщения имеет включённую отправку. Обратная ситуация допустима: отправка уже входит в срез, а приём ещё нет, и тогда сообщение должно находиться в записанном состоянии канала. Одни локальные числовые остатки не позволяют отличить такое сообщение от потерянного.
В классической модели каналы направленные, надёжные и сохраняют порядок FIFO. Процесс записывает своё состояние и до отправки новых прикладных сообщений посылает маркер по каждому исходящему каналу. Предполагается возможность отличить маркер от прикладных данных и связать его с нужным запуском снимка. Общая одновременная остановка процессов для этого не требуется.
Как первый маркер отличается от остальных
Если процесс впервые узнаёт о снимке по входящему маркеру, он записывает локальное состояние и считает этот входящий канал пустым: из-за FIFO все предыдущие сообщения по нему уже приняты. Затем он рассылает собственные маркеры. По другим входящим каналам начинается запись прикладных сообщений до получения их маркеров. Если локальный снимок уже сделан, очередной маркер лишь закрывает запись соответствующего канала.
FIFO обеспечивает разделение: сообщение, отправленное после снимка отправителя и после его маркера, не может обогнать этот маркер и попасть в записанное состояние канала. Сообщение, отправленное до снимка, может ещё идти к уже записавшемуся получателю; именно такие сообщения и сохраняются. Записанные локальные состояния не обязаны совпадать с набором показаний, наблюдавшимся одновременно на физических часах.
Проверка жетонов и условие завершения
Пусть P, Q, R начинали с 10 жетонами каждый, а каналы P↔Q и P↔R пусты. До записи P процесс Q отправил ему 4 жетона, R отправил 3; оба сообщения задержаны. Поэтому Q хранит 6, R хранит 7, а P пока 10. P начинает снимок и посылает маркеры. Q и R записываются при получении первых маркеров и отправляют ответные вслед за уже отправленными прикладными сообщениями.
P до ответных маркеров получает 4 и 3, записывая их в разные входящие каналы. Сумма снимка равна 10+6+7+4+3=30. Текущий остаток P уже может быть 17, но подменять им сохранённые 10 нельзя: сообщения были бы учтены дважды. Завершение требует достижимости участников и конечной доставки маркеров; при недоставке из-за разделения сети безопасность записанного фрагмента не превращается в гарантию готового полного снимка.
Семь жетонов находятся не в процессах, а в каналах
Условие. Используйте описанный порядок: Q и R уже отправили P соответственно 4 и 3 жетона, но P ещё не принял их и записывает свои 10. Q, R получают маркеры от P раньше ответных маркеров на P. Восстановите полный снимок.
- Записанные состояния процессов: P=10, Q=6, R=7; исходящие из P прикладные каналы до маркеров пусты.
- Q, R впервые записываются по маркерам P, поэтому состояния каналов P→Q и P→R пусты.
- Сообщения 4 и 3 приходят P после его записи, но до маркеров Q, R. Сохраняем Q→P=[4], R→P=[3].
- Общий итог 10+6+7+4+3=30. Без каналов получилось бы 23; с текущим P=17 и сохранёнными сообщениями получилось бы 37.
Ответ. Снимок содержит состояния(10,6,7) и два сообщения в пути общей величиной 7. Всего сохранено 30 жетонов.
Проверка. Каждая отправка уменьшила локальный остаток отправителя ровно на содержимое соответствующего канала. При последующем приёме сообщение исчезает из канала и увеличивает остаток P, сохраняя общий итог.
Где легко ошибиться. Не смешивайте сохранённое состояние процесса с его более поздним текущим значением и не забывайте сообщения в полёте.
Проверьте понимание
Вопросы к этой главе
Можно ли записать все каналы пустыми?
Только если это следует из порядка событий. В примере отправки уже включены в срез, а приёмы ещё нет, поэтому без записей каналов нарушился бы учёт жетонов.
Гарантируют ли маркеры завершение при разрыве связи?
Нет. Для полного завершения они должны дойти до нужных участников и по всем проверяемым каналам. Надёжная конечная доставка является условием модели.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Chandy–Lamport1985: Distributed Snapshots, §3.2–4
Правила отправки и приёма маркеров и согласованность среза в FIFO-модели. Пример трёх процессов с двумя переносами жетонов построен отдельно.
Escrow-права сохраняют глобальный лимит при разделённой сети
Два изолированных узла не могут каждый расходовать весь общий остаток. Но они могут заранее разделить право на расход. На примере запаса из десяти единиц докажем инвариант, проведём передачу одного права с повторной доставкой и увидим, почему свободный ресурс в другой части сети ещё не разрешает локальную операцию.
Перед началом: Инвариант суммы; Разделение сети и локальное состояние.
Разделяется разрешение, а не только показание счётчика
Фиксированный целочисленный запас, честные узлы, локально атомарное списание прав и надёжное сохранение журнала. Передача прав имеет уникальный идентификатор и не зачисляется повторно.
Пусть общий начальный запас N, свободные права узлов rᵢ≥0 и число окончательно использованных единиц s≥0. Пока передач в пути нет, поддерживается Σrᵢ+s=N. Локальная операция расхода k разрешается только при rᵢ≥k и атомарно меняет rᵢ←rᵢ−k,sᵢ←sᵢ+k. Остальным узлам не нужно немедленно видеть эту операцию, чтобы собственные права оставались безопасными.
Сумма глобального расхода не превосходит N по неотрицательности всех прав. Важна локальная атомарность: два параллельных запроса одного узла не должны оба пройти по одному прежнему остатку. Простое чтение общего приблизительного счётчика с последующей независимой записью не реализует данное правило.
Пересылка не должна создавать вторую копию разрешения
Для передачи k прав отправитель сначала безвозвратно для данной попытки списывает k из своего доступного остатка и создаёт устойчивую запись с уникальным номером. Пока получатель не зачислил её, k считается находящимся в пути. После первого корректного зачисления эта величина переходит в права получателя. Повтор того же номера подтверждается, но ещё k не добавляет.
Инвариант принимает вид свободные права + права в пути + израсходовано = N. Для систем с отказами нужны устойчивый журнал, дедупликация и доказанная процедура восстановления. Нельзя по тайм-ауту вернуть права отправителю, если задержанный получатель ещё может их зачислить. Потерянное подтверждение и потерянное право — разные наблюдения. Здесь проверяется механизм сохранения разрешений, а не полный отказоустойчивый продукт.
Граница локальной доступности остаётся видимой
Если у A осталась одна единица прав, запрос на две не выполняется, даже когда B хранит свободные права. Во время разделения A не может безопасно присвоить разрешение B, продолжая обещать, что B тоже вправе его расходовать. Требуется передача после восстановления связи, отказ или явно оговорённое ожидание.
Это не опровержение CAP: объект и его условия ответа отличаются от линеаризуемого регистра. Метод сохраняет конкретный числовой инвариант при некоторых локальных операциях, но не гарантирует успешность любого глобально выполнимого запроса на любом узле. Он особенно полезен, когда заранее распределённого бюджета хватает большей части обычных действий.
Девять расходованных единиц и одно передаваемое право
Условие. Начальные права A=6,B=4, запас N=10. При разрыве связи A расходует 5, B расходует 4. Затем A пытается расходовать ещё 2. После восстановления связи A передаёт последнее право B; сообщение приходит дважды. Проследите остатки.
- После двух независимых расходов A=1,B=0,s=9. Сумма равна 10, а запрос A на 2 не проходит условие 1≥2.
- Передача права с номером t списывает у A последнюю единицу: A=0,B=0,inflight=1,s=9. Во время пересылки суммарный доступный остаток меньше физически ещё не использованного запаса.
- Первая доставка t зачисляет B=1 и закрывает inflight. Повторная доставка t не меняет B: номер уже применён. Сумма по-прежнему 10.
- B может расходовать эту единицу, после чего s=10 и оба остатка нулевые. Если бы повтор t добавил ещё одно право, последующий расход мог бы дать s=11 — прямое нарушение исходного предела.
Ответ. Дополнительный расход A на 2 отклоняется. Передача создаёт у B ровно одно право, независимо от повторной доставки, и допускает общий расход не больше 10.
Проверка. Для каждого шага отдельно пересчитывается сумма A+B+inflight+s. Она равна 10 до отправки, во время передачи, после обеих доставок и после финального расхода.
Где легко ошибиться. Не зачисляйте повторную передачу как новое право и не возвращайте отправителю неопределённую передачу только по истечении времени.
Проверьте понимание
Вопросы к этой главе
Сходимость обычного счётчика сама сохраняет предел?
Нет. Итоговое правильное сложение двух расходов может уже показать превышение. Право на каждый расход должно быть ограничено до подтверждения операции.
Почему передача временно уменьшает доступность?
Чтобы один жетон не расходовался одновременно у обоих участников. После списания у отправителя и до подтверждённого зачисления получателю он относится к учтённым правам в пути.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Balegas et al.: bounded counter и escrow
Прочитаны разделII.D о разделении прав и схема bounded counter в разделеIII. Собственный журнал передачи с inflight и дедупликацией не выдаётся за буквальную матричную реализацию статьи.
OR-set различает удалённое наблюдённое добавление и конкурентное новое
В двухфазном множестве однажды удалённое имя уже не возвращается. Для обычного пользовательского списка это часто неудобно. Наблюдаемое удаление связывает команду с конкретными известными добавлениями: конкурентная новая запись и последующее повторное добавление получают собственные теги и сохраняют смысл.
Перед началом: Объединение состояния CRDT; Причинная видимость обновлений.
Одинаковое имя не означает одинаковое событие
State-based множество с глобально уникальным тегом каждого add. Учебное полное состояние хранит все добавленные пары и удалённые теги; доставка состояний может повторяться.
Пусть A — множество пар (элемент,тег), а R — множество удалённых тегов. Запрос показывает элемент x, если найдётся пара (x,t)∈A с t∉R. Добавление x создаёт новый уникальный t и добавляет пару. Повторная доставка старого состояния не создаёт новый тег; новый вызов add создаёт.
Команда remove(x) собирает только те теги x, которые сейчас видны на её реплике, и добавляет их в R. Она не может удалить ещё не наблюдавшееся конкурентное событие по его неизвестному тегу. Новое добавление того же имени после удаления снова получает свежую идентичность и поэтому способно вернуть элемент в видимый список.
Слияние сохраняет историю, запрос вычисляет её результат
В нашем намеренно простом полном представлении merge равен (A₁∪A₂,R₁∪R₂). Оба компонента только растут, а объединение коммутативно, ассоциативно и идемпотентно. Все получившие одни обновления реплики вычисляют один результат. Это утверждение требует доставки: навсегда недоступная новая пара не возникает из одного закона объединения.
Некоторые реализации хранят лишь живые пары и отдельные надгробия либо сжимают причинный контекст в векторы. Их формулы слияния отличаются от простого объединения живых списков. Мы сохраняем все исторические пары, чтобы доказательство было прозрачным. Видимое множество и полное состояние снова различаются: первое может уменьшаться при монотонном росте второго.
Удаление выигрывает у прошлого, конкурентное добавление выживает
Во время разделения реплика L добавляет x с тегом l₁, а R независимо добавляет x с тегом r₁. L затем удаляет x, наблюдая только l₁. После слияния l₁ погашен, но r₁ остаётся живым. Это называют add-wins для конкурирующих add/remove, а не правилом «любое добавление сильнее любого удаления».
После наблюдения обоих тегов новая команда remove(x) может погасить оба, и x исчезнет. Затем add(x,l₂) вернёт его. Очищать старые метки удаления без причинного сертификата нельзя: поздняя реплика всё ещё может прислать историческую пару l₁. Если забыть её удаление, произойдёт ложное воскрешение именно старого события.
Три добавления и две разные команды удаления
Условие. L создаёт (x,l₁), R независимо создаёт (x,r₁). До обмена L удаляет x. Затем реплики сливаются, выполняется удаление уже после наблюдения обоих добавлений и новое добавление (x,l₂). Найдите состояния запроса.
- Перед первым merge состояние L: A={(x,l₁)},R={l₁}; состояние R: A={(x,r₁)},R=∅. Локально x уже отсутствует на L, но присутствует на R.
- Первое слияние даёт A={(x,l₁),(x,r₁)},R={l₁}. Запрос находит живой r₁, поэтому x присутствует. L не удаляла событие, о котором ещё не знала.
- Удаление после обмена добавляет в R также r₁. Теперь оба известных добавления погашены и запрос пуст. Последовательность видимости не противоречит сходимости полного состояния.
- Новое событие (x,l₂) имеет свежий тег, отсутствующий в R. Запрос снова показывает x. Повторная доставка любого предыдущего состояния этот новый тег не удаляет.
Ответ. После первого merge x есть благодаря r₁; после полного наблюдаемого удаления x нет; после свежего l₂ x снова есть.
Проверка. Все порядки объединения первых трёх состояний дают одну пару множеств и живой r₁. Контроль с удалённым tombstone l₁ и поздней старой парой демонстрирует ошибочное воскрешение при неправильной очистке.
Где легко ошибиться. Не передавайте remove только как имя x, если требуется наблюдаемая семантика. Оно должно нести или эквивалентно кодировать именно наблюдённые идентичности добавлений.
Проверьте понимание
Вопросы к этой главе
Нужно ли выбирать победителя по настенным часам?
Нет. Здесь результат определяется тегами и причинным наблюдением. Рассинхронизация часов не меняет того, какие добавления были известны в момент удаления.
Почему недостаточно хранить только видимый список?
По пустому списку нельзя понять, элемент ещё никогда не добавляли или его известный тег уже удалён. Эти истории должны по-разному взаимодействовать с поздним старым состоянием.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Bieniusa et al.: Observed Remove Set
Прочитаны раздел4.1, уникальные теги и примерная схема Figure2; оптимизация4.2 не реализуется. Полное историческое представление, собственные l₁/r₁/l₂ и проверка поздней пары описаны отдельно.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
FLP ограничивает гарантированное завершение консенсуса, а не запрещает все решения
Правильно сформулировать невозможность детерминированного асинхронного консенсуса при одном возможном crash-отказе и отделить безопасность от живости.
Открыть темуСогласованный снимок не защищает ограничение между разными строками
Построить аномалию write skew при изоляции снимка и показать, почему отсутствие одновременной записи одной строки не обеспечивает сериализуемость.
Открыть темуКонфликтный граф транзакций: цикл запрещает перестановку в последовательное расписание
Построить граф предшествования операций транзакций и проверить конфликтную сериализуемость по наличию цикла, отделяя её от более общих критериев эквивалентности.
Открыть тему