Вопрос с собеседования · System design

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

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

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

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

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

Подробно

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

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

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

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

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

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

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

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

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

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

Разбор темы

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

Партнёр платформы

Разбор собеседования с sotto

После собеседования sotto разбирает разговор: оценка, каждый вопрос — хорошо, частично или слабо, чего не хватило в ответе и над чем поработать к следующему разу. Первые 30 минут бесплатно.

Разбор собеседования