Получить доступ

Почему условие R + W > N само по себе не даёт линеаризуемости?

SeniorCAP и согласованность
Ещё спрашивают так:
  • Почему кворум не даёт строгой согласованности?
Коротко

Кворум гарантирует свежесть, но не порядок: прерванные и конкурентные записи, а также нестрогий кворум ломают линеаризуемость.

  • Прерванная запись попала на часть реплик — читатели то видят её, то нет
  • Конкурентные записи без согласования — разные читатели видят разный итог
  • Sloppy quorum и hinted handoff пишут не на «свои» реплики

А ещё Линеаризуемость требует консенсуса (Raft, Paxos) или чтения с repair и проверкой

Так подсказку видит пользователь sotto на живом собеседовании — за пару секунд, пока вы думаете вслух.

Подробно

Условие пересечения означает лишь, что множества реплик, отвечающих на чтение и на запись, обязаны иметь общий узел, а значит читатель увидит хотя бы одну копию последней успешно подтверждённой записи. Этого недостаточно по нескольким причинам. Запись, прерванная на середине, могла попасть на часть реплик и не быть подтверждённой — последующие чтения могут её то видеть, то нет. Две конкурентные записи без согласования порядка приводят к тому, что разные читатели видят разный итог. Нестрогий кворум, когда во время разделения подтверждения принимают от произвольных доступных узлов, вообще снимает гарантию пересечения. Наконец, восстановление при чтении и антиэнтропия работают асинхронно, поэтому окно расхождения существует. Линеаризуемость требует согласованного порядка операций — то есть консенсуса вроде Raft или Paxos либо синхронной репликации через лидера, — а не арифметического условия на числа реплик.

Что хотят услышать

  • Что именно гарантирует пересечение кворумов.
  • Сценарии, ломающие линеаризуемость.
  • Консенсус как способ её получить.

Частые ошибки

  • Считать неравенство R + W > N достаточным условием строгой согласованности.
  • Не различать свежесть значения и порядок операций.

Проверьте себя

Один верный вариант. Подумайте, потом откройте ответ.

Показать варианты и ответ
  • ✓Пересечение кворумов гарантирует, что чтение увидит хотя бы одну реплику с последней подтверждённой записью, но не задаёт порядок операций: прерванные и конкурентные записи, а также нестрогий кворум при разделении дают аномалии — для линеаризуемости нужен консенсус
  • ✗Потому что R и W измеряются в разных единицах и их нельзя складывать
  • ✗Потому что неравенство работает только при нечётном N
  • ✗Потому что кворум применим только к чтению, а записи всегда идут на лидера

Что спросят дальше

  • Что такое нестрогий кворум и чем он опасен?
  • Как read repair и антиэнтропия приводят реплики к сходимости?

Разбор темы

Связанные вопросы

Закрытая бета

Подсказки на собеседовании — в реальном времени

sotto слышит вопрос интервьюера и показывает короткий ответ и план, как в блоке «Коротко». Оставьте контакт — пришлём доступ и промокод.

  • Промокод на 2 часа — сверх пробных 30 минут
  • Программа для Windows — скачать сразу, войти — через Яндекс ID или VK ID
  • Прямая связь с разработчиком: что улучшить — сделаем