Согласованные в конечном счете (Eventually Consistent)

перевод
Shedar 4 августа 2010 в 10:08 13,1k
Оригинал: Werner Vogels, Amazo…
В последнее время на хабре чаще стали встречаться обсуждения масштабируемых систем и NoSQL решений. Эта статья, написанная техническим директором Amazon — одна из лучших вводных, на мой взгляд, показывающая, какие проблемы возникают при построении масштабируемых систем, что нужно учесть при выборе инструментария, что имеют ввиду авторы кассандры, говоря про обеспечение AP в кассандре и CP в HBase и многое другое.

Введение


В основе облачных вычислений Amazon лежат инфраструктурные сервисы. Такие, как Amazon S3, SimpleDB и EC2. Они позволяют строить масштабируемые вычислительные платформы и приложения. Требования к этим сервисам весьма жесткие. Они должны обеспечивать отличную безопасность, масштабируемость, доступность, производительность и эффективное использование ресурсов. И всё это – во время обслуживания миллионов клиентов со всего мира.
Внутри эти сервисы представляют собой огромные распределенные системы, работающие в мировом масштабе. Что создаёт дополнительные сложности, поскольку при обработке триллионов и триллионов запросов, события, которые обычно случаются с весьма низкой вероятностью, теперь гарантированно случаются. И это нужно учитывать при проектировании и разработке системы. В мировых масштабах мы используем репликацию повсеместно, чтобы обеспечить требуемую производительность и высокую доступность. Хотя репликация и приближает нас к нашим цели, она всё же не позволяет нам прозрачно достичь их. Существует ряд нюансов, с которыми столкнутся пользователи сервисов, использующих репликацию.
Один из таких нюансов – тип согласованности данных, обеспечиваемый системой. В частности, многие распространенные распределенные системы используют модель «согласованность в конечном счете» (eventual consistency) в контексте репликации данных. При разработке больших масштабируемых систем в Amazon мы использовали набор правил и абстракций, связанных с репликацией данных в больших масштабируемых системах. Мы сфокусировались на поиске компромисса между высокой доступностью (high availability) и согласованностью данных. В этой статье я рассмотрю часть информации, сформировавшей наш подход к построению надежных распределенных систем, работающих в мировом масштабе.

Историческая перспектива


В идеальном мире существовала бы только одна модель согласованности: после выполнения обновления данных, все наблюдатели увидят обновления. Первые трудности с достижением этого возникли в СУБД в конце 70х. Лучшая работа на эту тему – «Notes on Distributed Databases» Брюса Линдсей. Он излагает основные принципы репликации баз данных и обсуждает ряд техник, связанных с достижением согласованности. Множество из этих техник пытается достичь прозрачности распределения – чтобы с точки зрения пользователя это выглядело как единая система, а не как множество связанных систем. Многие системы того времени следовали подходу, что лучше сбой всей системы, чем нарушение прозрачности.
В средине 90х, с ростом систем в интернете, эта практика была пересмотрена. В это время люди начали склоняться к мнению, что доступность – наиболее важное свойство, но они не могли решить, чем пожертвовать в качестве компромисса. Эрик Брюэр (Eric Brewer), профессор Беркли, который в то время был главой Inktomi (компания, выпустившая успешный поисковик, которая потом была поглощена Yahoo – прим. пер.), собрал все компромиссы воедино в докладе на конференции PODC в 2000 году. Он представил теорему CAP, которая утверждает, что из трех свойств систем с распределенными данными – согласованность данных (consistency), доступность системы при сбое одного из узлов (system availability) и устойчивость к потере связи между сегментами сети (partition tolerance) (здесь и далее под сегментированием сети подразумевается потеря связи между частями распределенной системы, когда каждая часть отдельно работоспособна, но они «не видят» друг друга – прим. пер.) – одновременно можно достичь только два. Более формализованное подтверждение опубликовано в статье Сета Гилберта и Ненси Линча в 2002.
Система, не обеспечивающая устойчивости к потере связи между сегментами сети, может достичь согласованности данных и доступности, что зачастую достигается использованием протокола транзакций. При этом, определенные ситуации обрабатываются как сбой системы. Например, если клиент не видит часть узлов. Стоит отметить, что в больших масштабируемых системах зачастую присутствует сегментирование, потому согласованность данных и доступность не достижимы одновременно. Это значит, что у нас есть два выбора: ослабить согласованность, что позволит создать систему с высокой доступностью в условиях сегментирования сети, или же акцентироваться на согласованности, что приведет к недоступности системы в определенных ситуациях.
Оба варианта требуют внимания разработчика клиентской части к возможностям системы. Если система акцентируется на целостности, то разработчик должен иметь ввиду, что система может оказаться недоступной, например, для записи и соответственно обрабатывать эту ситуацию, чтобы не потерять данные. Если же система акцентирует внимание на доступности, то она может всегда обеспечивать запись, но чтение данных в некоторых случаях не будет отражать результат недавно осуществленной записи. Разработчику приходится решать, действительно ли клиенту необходимы самые-самые последние изменения. Во многих случаях допустимо использовать слегка устаревшие данные.
В принципе, согласованность в транзакционных системах, соответствующих ACID, – это несколько другой вид обеспечения согласованности. В ACID под согласованностью подразумевается гарантия, что по завершению транзакции база данных находится в согласованном состоянии. Например, при переводе денег между счетами, сумма денег на счетах не должна измениться. В системах, соответствующих ACID, этот вид согласованности, как правило, обеспечивается использованием транзакций и средств базы по обеспечению целостности данных.

Согласованность – клиент и сервер


Существует два взгляда на согласованность. Один с точки зрения разработчика/клиента: как они видят обновления данных. Второй – со стороны сервера: как проходят обновления в системе и что система может гарантировать относительно апдейтов.

Согласованность с точки зрения клиента

С точки зрения клиента у нас есть следующие компоненты:
Система хранения. На данный момент мы рассматриваем её как черный ящик. Но учитываем, что внутри нечто в высокой степени масштабируемое и распределенное, построенное для обеспечения устойчивости и доступности.
Процесс А. Процесс, который пишет в систему хранения и читает из неё.
Процессы В и С. Два процесса, не зависящие от процесса А, которые также пишут систему хранения и читают из неё. Не важно, являются ли они процессами или потоками одного процесса. Важно лишь то, что они независимы и должны взаимодействовать для обмена информацией.
Клиентская (client-side) согласованность определяет, как и когда наблюдатели (в нашем случае процессы А, В и С) видят изменения объекта данный в системе хранения. В следующих примерах, иллюстрирующих различные типы согласованности, процесс А выполнил обновление (update) данных.
Сильная согласованность (Strong consistency). После завершения обновления, любой последующий доступ к данным (Процессом А, В или С) вернет обновленное значение.
Слабая согласованность (Weak consistency). Система не гарантирует, что последующие обращения к данным вернут обновленное значение. Перед тем, как будет возвращено обновленное значение, должен выполниться ряд условий. Период между обновлением и моментом, когда каждый наблюдатель всегда гарантированно увидит обновленное значение, называется окном несогласованности (inconsistency window).
Согласованность в конечном счете (Eventual consistency). Частный случай слабой согласованности. Система гарантирует, что, при отсутствии новых обновлений данных, в конечном счете, все запросы будут возвращать последнее обновленное значение. При отсутствии сбоев, максимальный размер окна несогласованности может быть определен на основании таких факторов, как задержка связи, загруженность системы и количество реплик в соответствии со схемой репликации. Самая популярная система, реализующая «согласованность в конечном счете» – DNS. Обновленная запись распространяется в соответствии с параметрами конфигурации и настройками интервалов кэшированя. В конечном счете, все клиенты увидят обновление.
Согласованность в конечном счете (Eventual consistency) имеет множество вариаций, которые важно учитывать:
Причинная согласованность (Causal consistency). Если процесс А сообщил процессу В, что обновил данные, то последующие обращения процесса В к этим данным будут возвращать обновленные значения и запись гарантированно замещает более раннюю. Доступ процесса С, который не находится в причинной связи с процессом А, подчиняется обычным правилам eventual consistency.
Модель согласованности «Читай то, что записал» (Read-your-writes consistency). Это важная модель, в которой процесс А после обновления данных всегда при обращении получает обновленное значение и никогда не видит более старого. Это частный случай причинной согласованности (causal consistency).
Сессионная согласованность (Session consistency). Это практическая версия предыдущей модели, когда процесс получает доступ к хранилищу в контексте сессии. Пока сессия существует, система гарантирует Read-your-writes согласованность. Если же сессия завершается по причине какого-либо сбоя, то должна создаваться новая сессия, гарантированно не перекрывающаяся с другими.
Модель согласованности «однообразное чтение» (Monotonic read consistency). Если процесс увидел определенное значение, то, при последующих обращениях к этим данным, он никогда не получит более старое значение.
Модель согласованности «однообразная запись» (Monotonic write consistency). В этом варианте система гарантирует упорядоченность записи одного процесса. Системы, не обеспечивающие этот уровень согласованности, сложны в использовании.
Некоторые из этих вариаций могут быть скомбинированы. Например, можно объединить monotonic reads и сессионную согласованность. С практической точки зрения, monotonic reads и read-your-writes наиболее желанны в системах, реализующих «согласованность в конечном счете», но не всегда необходимы. Такая комбинация облегчает разработку приложений, позволяя при этом системе хранения ослабить согласованность и обеспечить высокую доступность.
«Согласованность в конечном счете» (Eventual consistency) не является какой-то эзотерической поэзией экстремальных распределенных систем. Многие современные реляционные СУБД, обеспечивающие надежность дублированием на резервный сервер (primary-backup reliability), реализуют работу механизма репликации в двух режимах: синхронном и асинхронном. В синхронном режиме обновление реплики является частью транзакции. В асинхронном режиме обновление доставляется как бекап, с некоторой задержкой, зачастую через доставку логов. В последнем случае, если основной сервер откажет до того, как лог был доставлен, то чтение с резервного сервера, поднятого вместо основного, вернет нам устаревшие данные. Также, для обеспечения лучшей масштабируемости чтения, реляционные СУБД начали предоставлять возможность чтения с резервного сервера, что является классическим случаем гарантий «согласованности в конечном счете», в котором размер окна несогласованности зависит от периодичности отправки лога.

Согласованность на стороне сервера

На стороне сервера нам нужно глубже разобраться, как распространяются обновления в системе, чтобы понять, что тот или иной способ даёт разработчику. Давайте для начала согласуем несколько определений:
N = количество узлов, хранящих копии (реплики) данных;
W = количество реплик, которые должны подтвердить получение обновления, прежде чем обновление считается завершенным;
R = количество реплик, с которыми устанавливается связь при обработке запроса на чтение данных.
Если W+R > N, то множества реплик, участвующих в записи и участвующих в чтении всегда пересекаются, что может гарантировать сильную согласованность (strong consistency). В механизме синхронной репликации на резервный сервер реляционных СУБД – N=2, W=2 и R=1. Не важно, с какой реплики происходит чтение, всегда будут прочитаны актуальные данные. При асинхронной репликации и включенном чтении с резервного сервера, N=2, W=1 и R=1. В этом случае R+W=N и согласованность данных не может быть гарантирована.
Проблема таких конфигураций в том, что при невозможности записи на W узлов из-за сбоя, операция записи должна возвращать ошибку, отмечая недоступность системы. Например, при N=3, W=3 и двух доступных узлах, система должна сгенерировать ошибку при записи.
В распределенных хранилищах, которые должны обеспечивать высокую производительность и доступность, число реплик в общем случае больше двух. Система, которая ориентируется только на устойчивость к сбоям, зачастую использует N=3 (при W=2 и R=2). Системы, которые должны обслуживать очень высокую нагрузку по чтению зачастую используют больше реплик, чем необходимо для обеспечения устойчивости к сбоям. Значение N может быть несколько десятков, или даже сотен узлов, с R=1, так, что запрос к одному узлу вернет результат. Системы, сконцентрированные на согласованности данных, устанавливают W=N для обновлений, что может уменьшить вероятность успешного завершения записи. Частая конфигурация для систем, требующих устойчивости к сбоям, но не требующих сильной согласованности – работать с W=1, чтобы получить минимальную длительность обновления и затем обновлять остальные реплики используя ленивую (lazy, epidemic) технику.
Как настроить N,W и R зависит от вариантов использования и от требований производительности к различным нагрузкам. При R=1, N=W мы оптимизируем скорость чтения, а при W=1, R=N – мы оптимизируем систему на очень быструю запись. Конечно, в последнем случае, выживание системы при сбоях не гарантируется, и при W<(N+1)/2 существует возможность возникновения конфликтующих записей, когда множества узлов при различных операциях записи не пересекаются.
Слабая (weak/eventual) согласованность возникает в случае, когда W+R <=N. Т.е. существует возможность, что множества узлов при записи и при чтении не пересекутся. Если это осознанный шаг и не из-за требований к устойчивости к сбоям, то установка R во что-то кроме 1 практически не имеет смысла. Слабая согласованность возникает в двух основных случаях: первый – репликация на множество узлов для обеспечения масштабирования по чтению, как уже отмечалось выше, второй вариант – при более сложном доступе к данным. В простых системах ключ-значение довольно просто сравнить версии, чтобы определить, какое значение было записано последним. Но в системах, которые возвращают множества объектов, сложнее определить какое из множеств считать последним актуальным. Большинство систем, в которых W<N, содержат механизм, который обновляет данные на нужных узлах (не вошедших в множество W) в фоновом режиме. Период до обновления всех узлов является окном несогласованности, которое обсуждалось ранее. Если W+R<=N, то система может прочитать данные с узлов, которые еще не получили обновление.
Возможность реализации моделей согласованности read-your-writes, session, monotonic зависит в общем случае от привязки клиента к определенному серверу, который обеспечивает работу со всей распределенной системой. Когда клиент обращается каждый раз к одному и тому же серверу, реализация read-your-writes и monotonic reads довольно простая. При этом несколько сложнее реализовать балансировку нагрузки и устойчивость к сбоям, но это простое решение. Using sessions, which are sticky, makes this explicit and provides an exposure level that clients can reason about (варианты перевода приветствуются).
Иногда read-your-writes и monotonic reads реализуется средствами клиента. Добавляя версии к записям, клиент отбрасывает значение с версиями меньше последней встречавшейся.
Сегментирование возникает, когда некоторые узлы системы не могут соединиться с другими узлами, но оба множества узлов доступны для клиентов. При использовании классического механизма кворума, сегмент имеющий W узлов может продолжать функционировать и принимать апдейты, в то время, как другой сегмент становится недоступным. Аналогичные рассуждения применимы и при чтении. Поскольку множества узлов при чтении и при записи пересекаются по определению, то меньшее множество узлов становится недоступным. Сегментирование случается нечасто, но может возникать как между датацентарми так и внутри датацентров.
В некоторых приложениях недоступность части узлов недопустима, и важно, чтобы клиент, который взаимодействует с любым сегментом, мог нормально работать. В этом случае, оба сегмента определяют новое множество узлов для хранения данных, и выполняется операция слияния (merge) при восстановлении связи между сегментами.

Amazon’s dynamo


Amazon’s dynamo – система, которая позволила настраивать все рассмотренные выше параметры в соответствии с архитектурой приложения. Это система хранения ключ-значение, которая используется во многих сервисах платформы e-commerce и веб-сервисах Amazon. Одна из целей разработки Dynamo – позволить владельцам сервисов, использующих экземпляры системы хранения Dynamo, зачастую распределенных на несколько датацентров, определять компромис между согласованностью, устойчивостью, доступностью, производительностью системы.

Резюмируя выше сказанное


Несогласованность данных в сильно-масштабируемых надежных распределенных системах должна быть допустима по двум причинам: повышение производительности чтения и записи, при наличии множества конкурентных запросов; обработка сегментирования, когда в противном случае нужно заявлять о недоступности части системы, даже если все узлы работают.
Приемлема ли несогласованность – зависит от клиентского приложения. В любом случае, разработчик должен не забывать, какой вид согласованности обеспечивается системой хранения и учитывать это при разработке приложений. Существует ряд практических улучшений модели «согласованность в конечном счете» (eventual consistency), таких, как «сессионная согласованность» и «однообразное чтение», которые облегчают жизнь разработчикам. Зачастую, приложение может использовать eventual consistency без каких-либо проблем. Частный широко распространенный случай – веб сайт, на котором у нас есть понятие согласованности с точки зрения пользователя. В этом случае, окно несогласованности должно быть меньше, чем ожидаемое время перехода пользователя к следующей странице. Это позволяет распространить обновление в системе до следующего запроса на чтение.
Цель этой статьи – повысить информированность о сложности систем, которые должны работать в мировом масштабе и требуют аккуратной настройки, чтобы убедиться, что они могут обеспечивать требуемую приложению производительность, доступность и устойчивость. Одна из вещей, с которыми приходится работать проектировщиков распределенных систем – размер окна несогласованности, во время которого клиенты системы могут ощутить реалии разработки сильно-масштабируемых систем.

Замечания и предложения по улучшению перевода приветствуются.
Проголосовать:
+41
Сохранить: