Экосистема NoSQL

Глава 13 из книги "Архитектура приложений с открытым исходным кодом", том 1.

Оригинал: The NoSQL Ecosystem
Автор: Adam Marcus
Перевод: А.Панин

13.5. Согласованность данных

После обсуждения достоинств техник копирования данных на множество машин для повышения долговечности их хранения и распределения нагрузки, пришло время открыть вам секрет: хранение копий ваших данных на множестве машин при условии их идентичности является сложной задачей. На практике копии повреждаются и не соответствуют друг другу, теряются без возможности последующего восстановления, сети не позволяют синхронизировать наборы копий, а также передаваемые между машинами сообщения доставляются с задержкой или теряются. Существует два основных подхода к обеспечению согласованности данных в экосистеме NoSQL. Первый подход подразумевает строгую согласованность (strong consistency) данных, при которой все копии остаются синхронизированными. Второй подход подразумевает конечную согласованность (eventual consistency), при которой копии могут быть не идентичными, но в конечном счете все же стать таковыми. Для начала давайте разберемся с тем, почему второй вариант является допустимым решением, рассмотрев фундаментальное понятие систем распределенных вычислений. После этого мы перейдем к подробному рассмотрению каждого из подходов.

13.5.1. Немного о CAP

Теорема говорит о том, что система хранения данных, которая функционирует на множестве компьютеров может обладать только двумя из этих параметров в ущерб третьему. Также нам приходится реализовывать системы с возможностью разделения. При работе с современным оборудованием сетей с использованием современных протоколов сообщений пакеты могут теряться, свитчи могут выходить из строя и не существует способа для получения информации о неработоспособности сети или сервера. Все системы NoSQL должны обладать возможностью разделения. Остается выбор между согласованностью и доступностью. Ни одна система NoSQL не может обладать двумя этими параметрами одновременно.

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

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

Положения теоремы CAP ведут к появлению подходов строгой согласованности и конечной согласованности при разработке хранилищ данных NoSQL. Существуют и такие подходы, как облегченная согласованность и облегченная доступность, представленные в системе PNUTS [CRS+08] компании Yahoo!. Ни в одной из обсуждаемых нами систем NoSQL с открытым исходным кодом эта техника пока не реализована, поэтому мы не будем рассматривать ее более подробно.

13.5.2. Строгая согласованность данных

Системы, предусматривающие строгую согласованность данных, следят за тем, чтобы копии данных были идентичны и позволяли получить одно и то же значение ключа. Некоторые копии могут быть не синхронизированы с другими, но в момент, когда пользователь запрашивает значение для ключа employee30:salary, машины имеют возможность согласования значения, передаваемого пользователю. Принцип работы этого механизма лучше всего описывается с помощью чисел.

Например, мы копируем ключ на N машин. Какая-либо машина, возможно, одна из множества N, выступает в качестве координатора для каждого запроса. Координатор устанавливает факт того, что определенное количество машин из множества N приняло и подтвердило каждый из запросов. В момент, когда происходит запись обновленных данных для ключа, координатор не отправляет подтверждение завершения обновления пользователю до того момента, как как будет принято подтверждение получения обновлений группой из W копий. Когда пользователь хочет прочитать значение, соответствующее какому-либо ключу, координатор отправляет ответ, когда как минимум из R копий прочитано одно и то же значение. Мы говорим, что система использует строгую согласованность данных, если R+W>N.

Таким образом, для достижения строгой согласованности данных в этом случае нам потребовалось установить значение R=2, следовательно, R+W=4.

Что же случится, если W копий не будут обновлены в ходе выполнения запроса записи данных или R копий не будут прочитаны в ходе выполнения запроса чтения данных в случае необходимости использования строго согласованного ответа? Координатор может приостановить обработку запроса до истечения времени ожидания и в конечном счете отправить пользователю сообщение об ошибке или ожидать того, что ситуация разрешится сама собой. В любом случае, система окажется не в состоянии выполнить этот запрос, по крайней мере в течение некоторого промежутка времени.

Ваш выбор значений R и W влияет на то, как много машин смогут вести себя странно до того момента, как ваша система заблокирует возможность совершения различных действий с ключом. Если вы установите необходимость подтверждения записи данных для всех ваших копий, например, то будет справедливо равенство W=N и операции записи будут приостанавливаться или аварийно завершаться в случае невозможности работы с любой копией. Стандартным выбором является равенство R+W=N+1, соответствующее минимальным требованиями строгой согласованности данных, при этом позволяющее временные несоответствия между копиями. Многие системы, реализующие подход строгой согласованности данных, выбирают равенства W=N и R=1, так как в этом случае не придется рассчитывать на рассинхронизацию узлов.

Система HBase использует для хранения и копирования данных HDFS, распределенную прослойку для хранения данных. HDFS предоставляет гарантии строгой согласованности данных. В HDFS запись не может завершиться успешно до тех пор, пока данные не будут скопированы во все N (обычно 2 или 3) копий, поэтому справедливо равенство W=N. Чтение завершится успешно в случае доступности хотя бы одной копии, поэтому справедливо равенство R=1. Для предотвращения снижения производительности из-за интенсивных нагрузок записи, данные передаются от пользователя узлам с копиями асинхронно в параллельном режиме. Как только получено подтверждение о том, что все копии данных доставлены, финальный шаг добавления новых данных в систему выполняется атомарно и согласованно всеми узлами с копиями данных.

13.5.3. Конечная согласованность данных

Такие системы на основе Dynamo, как Voldemort, Cassandra и Riak позволяют пользователю задать необходимые значения N, R и W, даже при условии R+W<=N. Это значит, что пользователь может достичь и строгой и конечной согласованности данных. Если пользователь выбирает конечную согласованность данных, даже в том случае, когда разработчик стремится реализовать модель строгой согласованности данных, но значение W меньше N, существуют периоды, в течение которых копии могут быть не синхронизированы. Для реализации модели конечной согласованности данных копий эти системы применяют специальные инструменты для быстрого выявления устаревших копий. Для начала давайте рассмотрим вопрос о том, как различные системы определяют рассинхронизацию копий данных, после чего обсудим их механизмы синхронизации копий данных и наконец проясним некоторые методы для ускорения процесса синхронизации, реализованные на основе методов системы Dynamo.

Так как две копии могут содержать две различных версии значения для какого-либо ключа, механизмы контроля версий данных и поиска конфликтов очень важны. Системы на основе Dynamo используют механизм контроля версий под названием "вектор времени" (vetctor clocks). Вектор времени является вектором, поставленным в соответствие каждому ключу и содержащим счетчик для каждой копии. Например, если серверы A, B и C хранят три копии какого-либо ключа, вектор времени будет состоять из трех элементов (N_A, N_B, N_C) и инициализироваться с помощью значений (0, 0, 0).

Каждый раз, когда соответствующая ключу копия данных обновляется, счетчик вектора увеличивает значение. Если сервер B модифицирует ключ, который до этого имел версию (39, 1, 5) он изменит вектор времени до (39, 2, 5). Когда данные другой копии, скажем на сервере C, обновляются с использованием сервера B, происходит сравнение вектора времени сервера B с локальным вектором времени. В случаях, если счетчики локального вектора времени имеют меньшие значения, чем счетчики, полученные с сервера B, на локальном сервере хранится устаревшая копия данных, которая может быть перезаписана с использованием копии с сервера B. Если серверы B и C имеют счетчики, значения в каждом из которых больше других, скажем (39, 2, 5) и (39, 1, 6), серверы считают, что они получили различные, возможно не взаимозаменяемые обновления и констатируют наличие конфликта.

Механизмы разрешения конфликтов отличаются в различных системах. Документация системы Dynamo возлагает задачу разрешения конфликтов на использующее систему хранения данных приложение. Две версии списка покупок могут быть объединены в одну без значительной потери данных, но две версии совместно редактируемого документа могут потребовать вмешательства человека для обзора и разрешения конфликта. Система Voldemort реализует эту модель, возвращая несколько копий данных ключа отправившему запрос клиентскому приложению в случае конфликта.

Система Cassandra, которая хранит метку времени для каждого ключа, использует наиболее позднюю версию данных ключа в случае конфликта двух версий. Эта возможность исключает необходимость дополнительного взаимодействия с клиентом и упрощает API. Также данное архитектурное решение затрудняет работу в ситуациях, когда конфликтующие данные могут быть объединены специальным образом, как в нашем примере со списком покупок или при реализации распределенных счетчиков. Система Riak позволяет использовать оба подхода, предоставляемых системами Voldemort и Cassandra. Система CouchDB предлагает гибридную модель: она определяет наличие конфликта и позволяет пользователям запрашивать соответствующие ключу конфликтующие данные для ручного исправления, но самостоятельно выбирает версию для возвращения данных пользователям до разрешения конфликтов.

Если R копий при чтении координатором содержат не конфликтующие между собой данные, координатор может безопасно возвращать данные приложению. Координатор также может отметить факт рассинхронизации нескольких копий. Документация системы Dynamo рекомендует, а системы Cassandra, Riak и Voldemort реализуют технику с названием "исправление при чтении" (read repair) для разрешения таких ситуаций. В момент, когда координатор устанавливает наличие конфликта при чтении, даже если непротиворечивое значение отправлено пользователю, координатор начинает использовать протоколы разрешения конфликтов по отношению к конфликтующим копиям. Данное действие позволяет осуществить профилактическое разрешение конфликта с помощью небольшой дополнительной работы. Версии данных копий уже отосланы координатору, поэтому быстрейшее разрешение конфликта позволит снизить количество несоответствий в данных системы.

Системы Cassandra, Riak и Voldemort используют технику под названием "передача данных с использованием подсказок" (hinted handoff) для повышения производительности операций записи в ситуациях, когда узел становится временно недоступным. Если одна из копий соответствующих ключу данных не может быть обновлена в из - за отсутствия ответа сервера на запрос записи, выбирается другой узел для временного переноса операций записи на его мощности. Записанные данные, предназначавшиеся для недоступного узла, хранятся отдельно и в тот момент, когда сервер резервных копий определяет, что до этого недоступный узел снова доступен, он передает все данные доступному серверу. Документация системы Dynamo использует подход "неполного кворума" (sloppy quorum) и добавляет количество записей с использованием подсказок к значению W, отражающему требуемое количество подтверждений операций записи. Системы Cassandra и Voldemort не добавляют количество записей с использованием подсказок к значению W и считают запись неудачной в случае недостаточного количества подтверждений операций записи W на заданные изначально серверы. Техника передачи данных с использованием подсказок также полезна и для этих систем, так как она ускоряет процесс восстановления данных во время перехода недоступного узла в работоспособное состояние.

Когда сервер с копией данных недоступен в течение длительного промежутка времени или машина, хранящая скопированные с помощью подсказки данные для недоступного сервера также становится недоступной, копии должны синхронизироваться друг с другом. В этом случае системы Cassandra и Riak реализуют процесс, аналогичный процессу в системе Dynamo и называемый "противодействием энтропии" (anti-entropy). В ходе этого процесса серверы обмениваются деревьями Меркле (Merkle Trees) для идентификации их участков диапазонов ключей, которые являются рассинхронизированными. Дерево Меркле является иерархической структурой для проверки данных на основе хэшей: если хэш всего пространства ключей не одинаков для двух копий, серверы будут обмениваться хэшами все меньших и меньших участков скопированных данных пространства ключей до того момента, как рассинхронизированные ключи будут идентифицированы. Этот подход снижает объем ненужных и в большей степени идентичных данных, передаваемых между серверами.

Наконец, с ростом распределенных систем становится все сложнее узнать то, как функционирует каждый их узлов системы. Три системы, построенные на основе Dynamo, используют для отслеживания состояния узлов старую простую технику, известную под названием "gossip". Периодически (каждую секунду или с подобной периодичностью) узел должен выбирать другой случайный узел, с которым он уже взаимодействовал для обмена данными о состоянии других узлов системы. С помощью этого обмена данными узлы узнают о том, какие из узлов находятся в неработоспособном состоянии, а также о том, куда перенаправить клиентов, ищущих ключ.

Продолжение статьи: 13.6. Заключительное слово.