Почему Кассандра не линеаризуема при использовании чтения и записи на основе кворума

Question

Не могли бы вы объяснить, почему Cassandra не линеаризуется, даже если используются чтение и запись на основе кворума?

Линеаризуемость определяется как

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

Answer 1

РЕДАКТИРОВАТЬ : Оглядываясь назад, это не лучшее объяснение.Я рекомендую прочитать ответ Анурага ниже, который является гораздо более кратким.

Поскольку обычные операции Кассандры не обнаруживают существующее состояние, которое оно меняет, только согласованность кворума не считается «линеаризуемой».

ДляНапример, если вам нужно отрегулировать баланс банковского счета, вам необходимо знать текущий баланс для его корректировки.Рассмотрим клиента, который выполняет следующие операции:

A. SELECT balance FROM account WHERE id='x' (assume this returns 5.12)
B. UPDATE account SET balance=4.12 WHERE id='x' (subtract 1$ from balance)

Проблема заключается в том, что с точки зрения Кассандры операция B неэффективно "видит" A, поскольку она не учитывает существующее состояние.данных или любых других операций, которые могут происходить по этому вопросу.Другой клиент может обновлять баланс для той же учетной записи во время отправки B.

Облегченные транзакции в Cassandra 2.0 описывает, как облегченные транзакции обеспечивают «линеаризуемую согласованность», предоставляя конструкции, гарантирующие, чтоОперации выполняются последовательно для данного раздела и не прерываются другими.Таким образом, вместо моего предыдущего примера, вы можете выполнить:

A. SELECT balance FROM account WHERE id='x' (assume this returns 5.12)
B. UPDATE account SET balance=4.12 WHERE id='x' IF balance=5.12

Использование IF balance=5.12 инструктирует Кассандру начать легкую транзакцию, которая использует протокол paxos consesus для выборов руководства.и гарантировать, что операции применяются последовательно.Если состояние баланса не соответствует условию, обновление не будет применено (указано в успешном ответе с логическим столбцом was_applied).Если C * не сможет достичь этого в течение некоторого времени ожидания (из-за конфликта или некоторых других факторов), операция не будет выполнена, не будет применена, и у клиента появится тайм-аут.

Answer 2

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

Также для пояснения определения линеаризуемости, добавляемого к определению жирным шрифтом

Если операция B началась после успешного завершения операции A, то операция B должна видеть систему в том же состоянии, в котором она была завершение операции A или более новое состояние (но никогда больше не старое состояние) .

Копирование из книги Мартина Клепмана по интенсивным приложениям

Линеаризуемость и кворумы Интуитивно кажется, что строгое чтение и запись кворума должны быть линеаризуемыми в модели стиля Динамо. Однако, когда у нас есть переменные сетевые задержки, возможно иметь гоночные условия, как показано на рисунке 9-6.

На рисунке 9-6 начальное значение x равно 0, и клиент модуля записи обновляет x до 1, отправляя запись во все три реплики (n = 3, w = 3). Одновременно клиент A читает из кворума двух узлов (r = 2) и видит новое значение 1 на одном из узлов. Также одновременно с записью клиент B читает из другого кворума из двух узлов и возвращает старое значение 0 из обоих.

Условие кворума выполнено (w + r> n), но это выполнение тем не менее не линеаризуемо: запрос B начинается после того, как запрос A завершается, но B возвращает старое значение, в то время как A возвращает новое значение. (Это снова ситуация с Алисой и Бобом из рисунка 9-1.)

Интересно, что можно сделать линеаризуемыми кворумы в стиле «Динамо» за счет снижения производительности: считыватель должен выполнить восстановление чтения (см. «Восстановление чтения и антиэнтропия» на стр. 178) синхронно, прежде чем возвращать результаты в приложение [23 ], и писатель должен прочитать последнее состояние кворума узлов перед отправкой своих записей [24, 25]. Однако Riak не выполняет синхронное восстановление чтения из-за снижения производительности [26]. Cassandra действительно ожидает завершения восстановления чтения при чтении кворума [27], но теряет линеаризуемость при наличии нескольких одновременных записей в один и тот же ключ из-за использования разрешения конфликтов последней записи-выигрышей.

Кроме того, таким способом могут быть реализованы только линеаризуемые операции чтения и записи; линеаризуемая операция сравнения и задания не может быть выполнена, поскольку она требует согласованного алгоритма [28].

Таким образом, наиболее безопасно предположить, что система без лидера с репликацией в стиле Dynamo не обеспечивает линеаризуемость.

И еще немного объяснений о Linearizability vs Serializability:

Answer 3

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

старые документы по последовательной согласованности

Однако кажется, что безусловноеОбновления - это то, что «ломает» линеаризуемость, и их необходимо отключить на уровне драйвера, чтобы кассандра была помечена как «линеаризуемая».

Таким образом, можно добиться линеаризации с помощью Cassandra.Но кассандра сама по себе не обеспечит линеаризуемость.