Линеаризуемость относится к операциям объекта и порядку завершённых вызовов. Сериализуемость относится к общему результату транзакций. Несколько линеаризуемых вызовов нельзя без дополнительного механизма объявить одной транзакцией.
Практический смысл
Почему это важно
После подтверждённой записи следующий клиент не должен получить прежнее значение через другой путь чтения. Это существенно для счётчика, признака занятости или состояния заказа. При выборе реплики и кэша нужно проверить всю операцию чтения; само число копий и одинаковые часы узлов такой гарантии не дают.
Доказательная часть
Что подтверждено
Каждой линеаризуемой операции можно назначить один логический момент между вызовом и ответом так, чтобы общая история соответствовала последовательным правилам объекта. Реальное выполнение не обязано занимать нулевое время.
Граница применимости: Модель параллельных объектов Херлихи и Уинг; соблюдение последовательной спецификации входит в определение.
Если одна операция завершилась до вызова другой, допустимый линеаризованный порядок обязан поставить первую раньше второй. Это правило действует и для разных клиентов одного объекта.
Граница применимости: Линеаризуемые истории; предшествование задано завершением и последующим вызовом, а не только метками часов серверов.
У объекта остатка было значение 1. Запись 0 завершилась успешно, затем другой клиент начал чтение. Если иных записей нет, линеаризуемое чтение обязано вернуть 0. Ответ 1 от отстающей копии нарушает гарантию независимо от того, какой клиент выполнил запись.
Граница применимости: Учебный пример одного объекта с операциями записи значения и чтения; чтение начато после ответа об успешной записи, между ними нет другой записи.
Если чтение перекрывается по времени с записью нового значения, один реальный порядок вызовов ещё не определяет результат. При отсутствии других операций чтение может быть помещено до записи или после неё и вернуть соответственно старое или новое значение.
Граница применимости: Один объект чтения/записи, одна перекрывающаяся запись и одно чтение; обе операции завершаются, остальные ограничения истории отсутствуют.
Линеаризуемость отдельных объектов не делает несколько вызовов одной атомарной транзакцией. Между уменьшением одного счётчика и увеличением другого может пройти чужая операция, даже если каждый отдельный вызов линеаризуем. Границу общей операции нужно обеспечить отдельно.
Граница применимости: Сравнение последовательных операций двух объектов и транзакционной группировки; линеаризуемость не названа более высоким уровнем изоляции SQL.
Совпадающие настройки часов узлов не доказывают линеаризуемость. Проверять нужно результаты операций и возможность построить допустимый порядок с учётом их вызовов и ответов. Часы помогают наблюдать выполнение, но не заменяют правило доступа к объекту.
Граница применимости: Применение определения Херлихи и Уинг к проверке истории; отдельный алгоритм проверки и его полнота здесь не заявлены.
Граница терминов
Не путать
Линеаризуемость задаёт требуемый порядок операций. Теорема CAP показывает, почему в своей модели при разделении сети нельзя совместить этот порядок с успешным обслуживанием каждого запроса к исправному узлу.
Перед спецификацией
Что проверить
- Назовите объект и его операции: например, чтение и замена одного значения остатка.
- Проверьте чтение другим клиентом после успешного завершения записи.
- Испытайте каждый реальный путь чтения, включая реплики и кэш.
- Разделите неперекрывающиеся вызовы и операции, выполнявшиеся одновременно.
- Сопоставьте ответы с допустимой последовательной историей, а не только с серверными метками времени.
- Для группы изменений нескольких объектов отдельно определите транзакционную границу.
- При разделении сети проверьте, какие операции продолжаются и какую гарантию сохраняют их ответы.
Открытые основания
Первоисточники
Linearizability: A Correctness Condition for Concurrent Objects
Carnegie Mellon University / ACM · Herlihy and Wing, ACM TOPLAS 12(3), July 1990
Даёт формальное real-time correctness condition для concurrent operations.
Открыть первоисточникPostgreSQL 18 Documentation: Transaction Isolation
PostgreSQL Global Development Group · PostgreSQL 18, Chapter 13.2
Определяет isolation phenomena и фактическое поведение PostgreSQL levels, включая Serializable.
Открыть первоисточникBrewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services
MIT Laboratory for Computer Science · Gilbert and Lynch, SIGACT News 33(2), 2002
Формализует CAP impossibility для atomic consistency и availability в asynchronous network model.
Открыть первоисточник