Почему одни системы всегда показывают актуальные данные, а другие — иногда отдают устаревшее, но зато хорошо масштабируются и показывают хорошие показатели по производительности?
В новом переводе от команды Spring АйО разберем, что такое модель согласованности как контракт между процессом и системой, какие бывают сильные и слабые гарантии и как они связаны с производительностью и доступностью.
Введение
В этом учебном материале мы рассмотрим концепции модели согласованности в компьютерных науках. Это поможет понять, почему она важна для конкурентных и распределённых систем. Именно на этой основе разные системы, работающие с данными, предоставляют гарантии, связанные с тем, как ведут себя их данные.
Зачем нужна модель согласованности?
Итак, что такое модель согласованности? Модель согласованности устанавливает контракт между процессом и системой.
Комментарий от Михаила Поливаха
Друзья, есть очень хороший ресурс от researcher-ов distributed систем (откуда кстати автор и взял картинку для статьи, увидите всё ниже). Я крайне рекомендую ознакомиться перед прочтением статьи, если есть время.
https://jepsen.io/consistency/models
Там подробно описаны определения примитивов моделей консистентности.
Когда вы оперируете понятиями "процесс", "атомарно", "конкурентно" и т.д. очень важно понимать, что имеется в виду именно с точки зрения компьютерных наук. Определение в CS теории и в реальности может отличаться.
Например mutex, если прямо из голой теории – это объект, у которого может быть 2 состояния: locked и unclocked. На практике в ядре линукса mutex это гораздо более сложная абстракция, которая не просто умеет lock / unlock.
Поэтому очень важно понимать, что определения терминов в прикладной разработке и в теории могут отличаться.
В рамках этого контракта система гарантирует, что если процесс соблюдает правила операций с памятью, результат таких операций будет предсказуемым.
Эта гарант��я необходима, потому что мы часто работаем с данными, общими для конкурирующих процессов и потоков. Им приходится одновременно выполнять разные операции над одними и теми же данными и при этом нужно, чтобы данные изменялись только допустимыми способами; иными словами, оставались согласованными.
Кроме того, ситуация усложняется, когда мы распределяем эти данные по нескольким узлам, логически или физически разделённым. Поэтому конкурентный доступ к данным, управляемым распределённой системой, требует явных гарантий согласованности данных, на которые мы можем рассчитывать:
Например, в приведённом выше примере несколько процессов работают со своей локальной копией данных. Однако эти локальные копии являются частью распределённого хранилища данных. Возникает вопрос: если процесс изменяет свою локальную копию, могут ли другие процессы ожидать увидеть это изменение в своих локальных копиях?
Этого ожидания придерживаются и прикладные процессы, и реализация памяти в системе распределённого хранилища данных. Чтобы решить проблему, хранилищу необходимо реализовать модель согласованности и наложить определённые правила использования для процессов, работающих с данными.
Хотя обсуждение моделей согласованности обычно сосредоточено вокруг распределённых систем, для однозвенной конкурентной системы это не менее важно. Большинство фундаментальных концепций были сформулированы именно для однозвенных конкурентных систем.
Некоторые фундаментальные понятия
К этому моменту мы уже встретили несколько терминов, которые нужно корректно определить, обсуждая модели согласованности. Во-первых, мы говорили о процессах, выполняющих операции. Здесь процесс — это экземпляр компьютерной программы, который может включать один или несколько потоков исполнения.
Комментарий от Михаила Поливаха
С точки зрения CS и моделей консистентности, процесс всегда "синхронен" сам с собой. Это значит, что процесс по определению должен всегда наблюдать результат своих действий. Например:
x = 0
x = x + 1
x = x * 2
Если эти операции делает один процесс, то не может быть ситуации, что процесс начнет делать шаг 3, при этом не наблюдая сайд эффектов (изменения значения х) от шага 2.
Это понятно, что есть процессы в ОС, и что они делятся на pthreads в Linux и что может быть многопоточность внутри процесса и т.д. Тем не менее, как я писал выше, сейчас уходим в теорию от конкретных ОС.
Подробнее на Jepsen Research: https://jepsen.io/consistency/models#processes
Далее, у систем есть логическое состояние, которое со временем изменяется. Следовательно, операция представляет собой переход из одного состояния в другое. Каждому переходу также можно присвоить уникальное имя. Например, у счётчика могут быть операции инкремента, декремента и чтения.
В общем случае выполнение операций занимает некоторое конечное время. Чтобы точнее это моделировать, считается, что у операции есть момент вызова и строго более поздний момент зав��ршения — если операция действительно завершается. Эти моменты задаются воображаемыми, идеально синхронизированными и глобально доступными часами:
Комментарий от Михаила Поливаха
В Computer Science Reserach-ах посвященным дистрибьютед системам их часто называют Wall Clock (типа "настенные часы") или "Real Time".
Называют их так потому что настенные часы (просто из обыденной жизни) показывают одно и то же время тебе, мне, твоему другу и другим. Это создаёт иллюзию общего времени.
Опять же, понятное дело что есть специальная теория относительности (СТО), никакого общего времени нет. Тем не менее, большое кол-во моделей консистентности основаны на "Wall Clock" просто потому, что:
В реальности, СТО для большей части компьютерных систем значения мало имеет (хотя есть кейсы где имеет, например для кода, исполняемого на спутниках).
Без Wall Clock строить модели, простые для понимания просто невероятно сложно. Почти нереально.
Поскольку выполнение операций занимает время, несколько операций, выполняемых разными процессами, могут перекрываться. Это приводит к появлению конкурентных операций. Например, две операции считаются конкурентными, если существует некоторый промежуток времени, в течение которого обе они выполняются.
Совокупность операций, включая их конкурентную структуру, называется историей (history). Следовательно, модель согласованности — это множество историй. Эти модели используются, чтобы о��ределить, какие истории допустимы в системе. Для этого они задают правила для воспринимаемого порядка истории и видимости операций.
Обычно более компактную, более ограничительную модель согласованности называют «более сильной», а более широкую, более допускающую модель — «более слабой». То, насколько сильную модель согласованности поддерживает система, влияет на многие её характеристики, такие как доступность и производительность.
Категоризация моделей согласованности
Модели согласованности уже много десятилетий остаются активной областью исследований. Поэтому неудивительно, что терминология согласованности часто пересекается и сбивает с толку. Тем не менее, докторская диссертация Атула Адьи, представленная в 1999 году, пытается создать разумную объединённую таксономию семантики согласованности.
Кроме того, в академической литературе термины «согласованность» (consistency) и «изоляция» (isolation) нередко используются как взаимозаменяемые. Однако изоляцию часто описывают применительно к транзакции с одной или несколькими операциями чтения и записи. Напротив, согласованность в большей степени относится к атомарным операциям чтения и записи.
Разные модели согласованности пытаются отвечать на разные потребности приложений, которые нередко конфликтуют между собой. Например, устойчивость приложения к чтению устаревших значений данных — в сравнении с его способностью обеспечивать более высокий пропускной поток обработки данных.
Как мы увидим позже при обсуждении отдельных моделей согласованности, они часто имеют иерархическую структуру. Здесь более сильная модель согласованности накладывает больше ограничений, при этом соблюдая ограничения, заданные более слабой моделью. Отношения между такими моделями обычно образуют граф:
Jepsen — организация, занимающаяся исследованиями безопасности распределённых систем, — составила приведённую выше карту моделей согласованности. Цвет каждой модели показывает, насколько доступной является та или иная модель для распределённой системы в асинхронной сети.
Комментарий от Михаила Поливаха
В дистрибьютед системах "ассинхронная сеть" не имеет ничего общего с понятием ассинхронности в ЯП (например наш любимый CompletableFuture, Kotlin корутины и т.д.)
Ассинхронная сеть это такая сеть, где:
Могут быть задержки сети, продолжающиеся конечное время
Сеть может падать
Сообщения по такой сети в итоге будут доставлены за конечное время, но непонятно за какое
Эта карта не охватывает все существующие модели согласованности. Например, большинство современных распределённых систем поддерживают довольно слабую модель согласованности, называемую итоговой (eventual) согласованностью. Тем не менее, в этом учебном материале мы рассмотрим лишь некоторые базовые модели согласованности и установим связи между ними.
Более сильные модели согласованности
Модели согласованности определяются и классифицируются двумя типами методов: методом выдачи (issue) и методом представления (view). Метод выдачи описывает ограничения, определяющие, как процесс может выдавать операции. Метод представления задаёт порядок операций, видимый процессам. При этом разные модели согласованности обеспечивают разные условия.
В этом разделе мы рассмотрим некоторые из более сильных моделей согласованности.
Линеаризуемость
Линеаризуемость — это модель согласованности для одного объекта и одной операции. Она требует, чтобы каждая операция выглядела так, будто выполняется атомарно. Кроме того, эти операции должны казаться упорядоченными в соответствии с реальным временем выполнения.
Здесь «реальное время» означает время в физическом мире, измеряемое настенными часами. Например, если одна операция завершается до того, как начинается другая, то вторая операция должна логически вступать в силу после первой:
При линеаризуемости операции записи должны выглядеть мгновенными. Иными словами, как только операция записи завершается, все последующие операции чтения должны возвращать значение этой записи либо значение более поздней записи. Здесь «последующие» определяется временем начала по настенным часам.
Интересно, что если операции над каждым объектом в системе линеаризуемы, то линеаризуемы и все операции в системе. Линеаризуемость была введена Херлихи и Уингом в их статье 1990 года «Linearizability: A Correctness Condition for Concurrent Objects».
Сериализуемость
Сериализуемость — это модель для нескольких объектов и нескольких операций. Это транзакционная модель, где под транзакцией понимается группа из одной или нескольких операций над одним или несколькими объектами. Здесь транзакции выполняются атомарно и выглядят так, будто произошли в некотором полном порядке.
Комментарий от Михаила Поливаха
Полный порядок, он же "total order" в литературе, значит, что любые два элемента из множества можно сравнить, используя какое-то бинарное отношение (для простоты - какую-то операцию сравнения, например < или >).
Например, набор целых чисел от 1 до 5 с операцией > образует полный порядок, т.к. возьмите любые два числа, и вы всегда сможете сказать, какое из них больше.
Есть также понятие "partial order", он же частичный порядок (кстати, отношение "happens before" в JMM как раз образует частичный порядок). Это ситуация, когда часть элементов можно сравнить, а часть элементов - incomparable, т.е. их сравнить нельзя.
Например, возьмите множество всех сотрудников вашей компании и постройте иерархию. И дальше сравните всех по отношению кто у кого в подчинении. Про Вас и Вашего руководителя можно сказать, что вы в подчинении, а вот про Вас и Вашего коллегу? Ни Вы у коллеги, ни коллега у Вас ни в подчинении, т.е. вас сравнить нельзя. Часть людей сравнить с Вами можно, а часть - нет.
Ключевой особенностью сериализуемости является отсутствие ограничений по реальному времени. Например, если процесс A завершает операцию записи и затем процесс B начинает операцию чтения, процесс B не гарантированно наблюдает эффект более ранней операции записи:
Кроме того, сериализуемость также не накладывает требований к порядку транзакций в рамках одного процесса. Поэтому процесс может наблюдать запись, а затем в последующей транзакции не наблюдать ту же самую запись — даже если эту запись выполнил он сам.
Однако при этом сериализуемость накладывает жёсткое ограничение на полный порядок транзакций. Формально сериализуемое выполнение — это выполнение операций конкурентно исполняющихся транзакций, которое даёт тот же эффект, что и некоторое последовательное выполнение этих же транзакций.
Комментарий от Михаила Поливаха
Вот собственно откуда на собеседованиях часто это люди и говорят, без понимания, откуда и что это значит на самом деле.
Причем, обратите внимание, в теории, порядок может быть по сути любой, по диаграмме выше Serializable не гарантирует включение в себя Casual Consistency.
Не пугайтесь, это pure теория, на практике Serializable часто включает в себя Casual Consistency :)
Строгая согласованность
Строгая согласованность — самая сильная модель согласованности. В рамках этой модели операция записи, выполненная любым процессом, должна мгновенно становиться видимой всем процессам. Следовательно, операции должны выглядеть происходящими в некотором порядке, согласованном с их порядком в реальном времени.
Эта модель подразумевает, что если операция A завершается до того, как начинается операция B, то A должна выглядеть предшествующей B в порядке сериализации. Поэтому строгую согласованность можно также понимать как сериализуемую систему, совместимую с порядком реального времени:
Хотя строгая согласованность детерминирована, её ограничения весьма жёсткие. Она требует мгновенного обмена сообщениями, что непрактично, особенно для распределённых систем. Поэтому она актуальна лишь для мысленных экспериментов и формализации.
Строгая согласованность по своей сути подразумевает и сериализуемость, и линеаризуемость. Следовательно, строгую согласованность можно рассматривать как полный порядок транзакционных многообъектных операций из сериализуемости плюс ограничения реального времени из линеаризуемости. Это вытекает из того, что мы обсуждали в предыдущих подразделах.
Более слабые модели согласованности
Сильные модели согласованности часто оказываются слишком ограничительными для практических приложений. Поэтому было предложено несколько более слабых моделей согласованности ради лучшей производительности и масштабируемости. Обычно это достигается ослаблением ограничений более сильных моделей, таких как сериализуемость и линеаризуемость. Рассмотрим некоторые из более слабых моделей согласованности.
Последовательная согласованность
Последовательная согласованность — более слабая модель по сравнению с линеаризуемостью, поскольку в ней отсутствуют ограничения по реальному времени. Она требует, чтобы операции выглядели происходящими в некотором полном порядке, согласованном с порядком операций внутри каждого процесса.
В системе с последовательной согласованностью процесс B может читать сколь угодно устаревшее состояние. Однако, как только процесс B наблюдает некоторую операцию процесса A, он уже никогда не может наблюдать состояние, предшествующее этой операции. Следовательно, процесс в такой системе может значительно опережать другие процессы или, наоборот, отставать от них:
Как мы видим, последовательная согласованность не накладывает ограничений реального времени, но сохраняет свойство полного упорядочивания. Следовательно, операции записи, выполняемые разными процессами, должны наблюдаться всеми процессами в одном и том же порядке. Последовательную согласованность предложил Лесли Лэмпорт в своей статье 1979 года.
Комментарий от редакции
А вот как раз наш перевод на эту тему: https://habr.com/ru/companies/spring_aio/articles/1005934/
Он определяет эту модель так, что результат любого выполнения должен быть тем же, как если бы операции всех процессов выполнялись в некотором последовательном порядке. Кроме того, операции каждого процесса появляются в этой последовательности в порядке, заданном его программой.
Причинная согласованность
Причинная согласованность ещё больше ослабляет ограничения последовательной согласованности. Она требует лишь того, чтобы причинно связанные операции выглядели упорядоченными одинаково для всех процессов. При этом процессы могут наблюдать разный порядок для причинно независимых операций.
Следовательно, только операции записи, причинно связанные между собой, должны наблюдаться всеми процессами в одном и том же порядке. Например, две операции записи могут стать причинно связанными, если одна запись переменной зависит от предыдущей записи любой переменной, когда процесс, выполняющий вторую запись, непосредственно перед этим прочитал первую запись:
Интересно, что порядок наблюдаемых переменных важнее, чем конкретное значение, наблюдаемое при чтении. Поэтому, если операция «b» вступает в силу вследствие более ранней операции «a», причинная согласованность гарантирует, что все процессы увидят операцию «b» после операции «a».
Здесь причинная память восходит к определению отношения happens-before, предложенному Лэмпортом. Оно фиксирует понятие потенциальной причинности, связывая операцию с предыдущими операциями того же процесса и с операциями других процессов, эффекты которых могли быть видимы.
Конвейерная память со случайным доступом (PRAM)
В модели согласованности PRAM все процессы наблюдают операции одного процесса в одном и том же порядке, в котором этот процесс их выдаёт. Однако операции, выданные разными процессами, могут восприниматься по-разному разными процессами.
Например, пара операций записи, выполненных одним процессом, наблюдается всеми процессами в том порядке, в котором этот процесс их выполнил. Но записи от разных процессов могут наблюдаться разными процессами в разном порядке:
Комментарий от Михаила Поливаха
Иными словами, если процесс А выполнил:
write X
write Y
То все процессы увидят систему в таком состоянии, как будто write X произошел действительно до write Y (где "до" определяется Program Order).
Тем не менее, если после ("где после" определяется Program Order) write Y, процесс B произвёл write Z, то даже если есть casual relationship между двумя write Y и write Z, процесс B имеет право не наблюдать изменения, связанные с write Y.
Липтон и Сандберг представили PRAM в своей статье 1988 года. PRAM — более слабая модель, чем согласованность процессора (processor consistency), поскольку она ослабляет требование поддерживать когерентность одного и того же местоположения для всех процессов. Благодаря этому достигается более высокий уровень конкурентности и, как следствие, производительности.
Здесь операции чтения любой переменной могут выполняться в процессе до операций записи. Однако порядок чтение перед записью, чтение после чтения и запись перед записью всё же сохраняется. Следовательно, она эквивалентна моделям согласованности Read Your Writes, Monotonic Writes и Monotonic Reads.
Повторяемое чтение
Повторяемое чтение — это модель согласованности, которая входит в состав требований сериализуемости. Она довольно близка к сериализуемости, за исключением того, что допускает фантомы. Фантомное чтение возникает, когда две идентичные операции чтения наблюдают два разных набора результатов.
Зд��сь, пока транзакция T1 читает набор объектов по предикату, транзакция T2 может изменять любые из объектов, прочитанных транзакцией T1. Однако при повторных чтениях транзакция T1 всё равно будет читать те же значения, хотя может наблюдать фантомные значения для исходного предиката:
Однако повторяемое чтение гарантирует предотвращение «грязных» чтений и неповторяемых чтений. «Грязное» чтение происходит, когда читаются данные, изменённые транзакцией, но ещё не зафиксированные (не закоммиченные).
Комментарий от Михаила Поливаха
Если упороться в Computer Science, то грязное чтение по сути возможно только тогда, когда операции не представляются читателям как атомарные. Любая (ещё раз, ЛЮБАЯ) модель консистентности, которая гарантирует ридерам perception атомарности операций не может допускать грязного чтения.
Но это теория :)
Неповторяемое чтение может возникнуть, когда перед выполнением операции чтения не захватываются блокировки на чтение.
Повторяемое чтение — более сильная модель согласованности, чем cursor stability. При cursor stability транзакции читают объект с помощью курсора, который гарантирует, что «потерянные обновления» не происходят. Усиливая это требование, модель повторяемого чтения обеспечивает стабильность каждой прочитанной записи, а не только курсоров.
Snapshot isolation
Snapshot isolation — ещё одна транзакционная модель, входящая в набор требований сериализуемости. Здесь каждая транзакция выглядит так, будто работает с независимым, согласованным снимком базы данных. Изменения остаются видимыми только внутри транзакции, пока она не будет зафиксирована.
Например, транзакция T1 начинает работу со своим снимком и изменяет объект. Теперь, если транзакция T2 фиксирует запись в тот же объект после того, как снимок транзакции T1 был создан, но до того, как T1 успела зафиксироваться, это требует, чтобы транзакция T1 была отменена:
В то время как сериализуемость обеспечивает полный порядок транзакций, snapshot isolation навязывает лишь частичный порядок. Здесь операции одной транзакции могут чередоваться с операциями других транзакций. Более того, как и повторяемое чтение, snapshot isolation также подразумевает уровень read committed.
Различные системы управления базами данных, такие как Oracle, MySQL, PostgreSQL и Microsoft SQL Server, широко внедрили уровни snapshot isolation. Прежде всего потому, что они обеспечивают более высокую производительность по сравнению с сериализуемостью, одновременно избегая большинства аномалий конкурентного доступа.
Монотонное атомарное представление (MAV)
В модели MAV, как только другая транзакция наблюдает часть эффектов некоторой транзакции, она наблюдает и все эффекты этой транзакции. Таким образом, MAV выражает атомарное ограничение из ACID: все эффекты транзакции должны проявиться целиком (или не проявиться вовсе).
Следовательно, MAV — более сильная модель согласованности, чем read committed. Здесь, например, если транзакция T2 наблюдает операцию записи из транзакции T1, то все ос��альные операции записи транзакции T1 также должны быть видимы транзакции T2:
Термин MAV был введён Бэйлисом, Дэвидсоном и Фекете и др. в их статье 2013 года. Хотя в литературе он обсуждается не слишком широко, он особенно полезен для обеспечения ограничений внешних ключей и для того, чтобы индексы и материализованные представления отражали свои базовые объекты.
И повторяемое чтение, и snapshot isolation дают более сильные гарантии, чем MAV. Однако система, поддерживающая MAV, может быть полностью доступной. Это означает, что даже при наличии сетевых разделений каждый узел системы может продолжать работу.
Модель согласованности на практике
Как мы видели ранее, модели согласованности накладывают на систему всё больше ограничений по мере перехода от более слабых к более сильным. Поэтому более сильные модели способны предотвратить больше сценариев несогласованности данных. Однако они плохо масштабируются и потому обеспечивают низкую производительность.
Большинство традиционных реляционных баз данных поддерживают несколько моделей согласованности с вариантом по умолчанию. При этом они могут использовать непоследовательную терминологию. Например, Oracle Database предлагает уровни изоляции read committed и serializable, причём read committed используется по умолчанию.
Однако таким SQL-базам данных требуется дорогостоящее вертикальное масштабирование, и их трудно масштабировать горизонтально. Поэтому, обеспечивая значительно более сильную согласованность данных, они не справляются с растущими скоростью, объёмом и разнообразием данных. Это привело к появлению баз данных NoSQL. NoSQL-базы обеспечивают отличную горизонтальную масштабируемость, поддерживая более слабые модели согласованности, такие как итоговая (eventual) согласованность. Например, Cassandra поддерживает настраиваемую (tunable) модель согласованности — от сильной до итоговой, причём итоговая используется по умолчанию.
Таким образом, большинство современных хранилищ данных предлагают несколько вариантов моделей согласованности. Выбор зависит от требований приложения. Например, некоторым приложениям может не требоваться согласованность между несколькими записями; тогда может быть достаточно более слабой модели, которая при этом обеспечит более высокую производительность!
Заключение
В этом учебном материале мы рассмотрели некоторые базовые понятия, связанные с изучением моделей согласованности в комьютерных науках. Здесь мы также разобрали ряд более сильных моделей согласованности и некоторые более слабые.
Присоединяйтесь к русскоязычному сообществу разработчиков на Spring Boot в телеграм — Spring АйО, чтобы быть в курсе последних новостей из мира разработки на Spring Boot и всего, что с ним связано.
