Репликация (replication) это хранение копии одних и тех же данных на нескольких машинах, соединенных сетью. Как обсуждалось во введении ко второй части, есть несколько причин, почему вы можете захотеть реплицировать данные:

• Чтобы держать данные географически близко к вашим пользователям (и таким образом, снизить задержку доступа).
• Чтобы позволить системе продолжать работать даже если некоторые её части выйдут из строя (и таким образом, увеличить доступность).
• Чтобы масштабировать количество машин, способных обрабатывать запросы на чтение (и таким образом, увеличить пропускную способность чтения).

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

Если данные, которые вы реплицируете, не меняются со временем, тогда репликация проста: вам просто нужно единожды скопировать данные на каждый узел и всё готово. Вся сложность репликации заключается в обработке изменений реплицируемых данных и именно об этом пойдёт речь в этой главе. Мы обсудим три популярных алгоритма для репликации изменений между узлами: репликация с одним лидером (single-leader), репликация с несколькими лидерами (multi-leader) и репликация без лидера (leaderless replication). Практически все распределённые базы данных используют один из этих трех подходов. У каждого из них есть свои преимущества и недостатки, которые мы рассмотрим подробно.

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

Репликация баз данных — это старая тема. Основные принципы почти не изменились с тех пор, как они были изучены в 1970-х [1], потому что фундаментальные ограничения сетей остались прежними. Тем не менее, вне исследований многие разработчики долгое время продолжали предполагать, что база данных состоит всего из одного узла. Массовое использование распределённых баз данных появилось относительно недавно. Поскольку многие разработчики приложений являются новичками в этой области, возникло много недоразумений по таким вопросам, как конечная согласованность. В разделе «Проблемы с задержкой репликации» мы будем более определенно говорить о конечной согласованности и обсудим такие вещи как гарантии «чтения своих записей» (read-your-writes) и монотонных чтений (monotonic reads).

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

Каждая запись в базе данных должна быть обработана каждой репликой; в противном случае реплики перестанут содержать одни и те же данные. Самое распространённое решение для этого называется репликация на основе лидера (leader-based replication, также известная как активная/пассивная или репликация «главный–подчинённый» (master-slave) и иллюстрируется на рисунке 5-1. Она работает следующим образом:

1. Одна из реплик назначается лидером (также известным как master — мастер или primary — основной). Когда клиенты хотят записать данные в базу данных, они должны отправить свои запросы лидеру, который сначала записывает новые данные в своё локальное хранилище.
2. Другие реплики известны как последователи (реплики для чтения (read replicas), подчинённые (slaves), вторичные (secondaries) или горячие резервные копии (hot standbys). Каждый раз, когда лидер записывает новые данные в свое локальное хранилище, он также отправляет изменение данных всем своим последователям в виде журнала репликации (replication log) или потока изменений (change stream). Каждая реплика берёт журнал у лидера и обновляет свою локальную копию базы данных соответственно, применяя все записи в том же порядке, в котором они были обработаны на лидере.
3. Когда клиент хочет прочитать данные из базы данных, он может выполнить запрос как к лидеру, так и к любому из последователей. Однако записи принимаются только на лидере (с точки зрения клиента, последователи доступны только для чтения).

Этот режим репликации является встроенной особенностью многих реляционных баз данных, таких как PostgreSQL (начиная с версии 9.0), MySQL, Oracle Data Guard [2] и группы доступности AlwaysOn SQL Server [3]. Он также используется в некоторых нереляционных базах данных, включая MongoDB, RethinkDB и Espresso [4]. Наконец, репликация с лидером не ограничивается только базами данных: распределённые брокеры сообщений, такие как Kafka [5] и очереди с высокой доступностью RabbitMQ [6] также используют её. Некоторые сетевые файловые системы и реплицируемые блочные устройства, такие как DRBD, схожи с ней.

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

Подумайте о том, что происходит на рисунке 5-1, где пользователь веб-сайта обновляет своё изображение профиля. В какой-то момент клиент отправляет запрос на обновление лидеру; вскоре после этого он получает его. В какой-то момент лидер пересылает изменение данных последователям. В конечном итоге лидер уведомляет клиента, что обновление прошло успешно.

На рисунке 5-2 показано взаимодействие различных компонентов системы: клиента пользователя, лидера и двух последователей. Время идёт слева направо. Запрос или ответ отображается толстой стрелкой.

В примере на рисунке 5-2 репликация на последователя 1 синхронна: лидер ждёт, пока последователь 1 подтвердит, что он получил запись, перед тем как сообщить об успехе пользователю и сделать запись видимой для других клиентов. Репликация на последователе 2 асинхронна: лидер отправляет сообщение, но не ждёт ответа от последователя.

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

Преимущество синхронной репликации в том, что у последователя есть гарантированная актуальная копия данных, согласованная с лидером. Если лидер внезапно выходит из строя, мы можем быть уверены, что данные всё ещё доступны у последователя. Недостаток заключается в том, что если синхронный последователь не отвечает (потому что он вышел из строя, есть сбой в сети или по любой другой причине), запись не может быть обработана. Лидер должен заблокировать все записи и ждать, пока синхронная реплика не станет доступной снова.

По этой причине непрактично, чтобы все последователи были синхронными: отказ любого узла приведёт к полной остановке системы. На практике, если вы включаете синхронную репликацию в базу данных, это обычно означает, что один из последователей синхронен, а другие асинхронны. Если синхронный последователь недоступен или работает медленно, одного из асинхронных последователей делают синхронным. Это гарантирует, что у вас есть актуальная копия данных как минимум на двух узлах: лидере и одном синхронном последователе. Эта конфигурация иногда называется полусинхронной.

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

Уменьшение надёжности может показаться плохим компромиссом, но асинхронная репликация тем не менее широко используется, особенно если есть много последователей или они географически распределены. Мы вернёмся к этой проблеме в разделе «Проблемы с задержкой репликации».

Время от времени вам нужно настраивать новых последователей, возможно, для увеличения количества реплик или замены отказавших узлов. Как удостовериться, что у нового последователя есть точная копия данных лидера?

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

Вы можете сделать файлы на диске согласованными, блокируя базу данных (делая её недоступной для записей), но это противоречило бы нашей цели высокой доступности. К счастью, настройку последователя обычно можно выполнить без простоя. Концептуально процесс выглядит следующим образом:

1. Сделайте согласованный снимок базы данных лидера в некоторый момент времени — если возможно, без блокировки всей базы данных. У большинства баз данных есть эта возможность, так как она также необходима для резервных копий. В некоторых случаях требуются сторонние инструменты, такие как innobackupex для MySQL [12].
2. Скопируйте снимок на новый узел последователя.
3. Последователь подключается к лидеру и запрашивает все изменения данных, произошедшие с момента создания снимка. Это требует, чтобы снимок был связан с точной позицией в репликационном журнале лидера. У этой позиции есть разные названия: например, PostgreSQL называет её порядковым номером журнала, а MySQL — координатами binlog.
4. Когда последователь обработал отставание изменений данных с момента снимка, мы говорим, что он его догнал. Теперь он может продолжить обработку изменений данных от лидера по мере их поступления.

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

Любой узел в системе может выйти из строя, возможно, неожиданно из-за сбоя, но также вероятно из-за запланированного технического обслуживания (например, перезагрузка машины для установки патча безопасности ядра). Возможность перезагрузки отдельных узлов без простоя — большое преимущество для операций и обслуживания. Таким образом, наша цель — поддерживать непрерывную работу системы в целом в случае сбоев отдельных узлов и минимизировать последствия отказа узла.

Как достичь высокой доступности с репликацией на основе лидера?

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

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

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

1. Определение отказа лидера. Есть много вещей, которые могут потенциально пойти не так: сбои, отключения питания, сетевые проблемы и многое другое. Нет надёжного способа точно определить, что пошло не так, поэтому в большинстве систем просто используется тайм-аут: узлы часто обмениваются сообщениями друг с другом и если узел не отвечает в течение некоторого времени, скажем, 30 секунд, считается, что он «мёртв». (Если лидер намеренно отключён для планового технического обслуживания, это не применяется).
2. Выбор нового лидера. Это может быть сделано через процесс выборов (где лидер выбирается большинством оставшихся копий) или новый лидер может быть назначен заранее избранным контролирующим узлом. Обычно лучший кандидат на роль лидера — это реплика с самыми свежими изменениями данных от старого лидера (чтобы минимизировать потери данных). Достижение согласия всех узлов по поводу нового лидера — это проблема консенсуса, подробно обсуждаемая в Главе 9.
3. Перенастройка системы для использования нового лидера. Теперь клиентам необходимо отправлять свои запросы на запись новому лидеру (мы обсудим это в Главе 6). Если старый лидер возвращается, он всё ещё может считать себя лидером, не понимая, что другие реплики вынудили его уступить. Система должна проконтролировать, что прежний лидер стал последователем и признал нового лидера.

Отработка отказа сопряжена с рисками:

• Если используется асинхронная репликация, новый лидер может не успеть получить все записи от старого лидера перед его отказом. Если бывший лидер вернётся в кластер после выбора нового лидера, что должно произойти с этими записями? В промежутке времени новый лидер мог получить противоречащие записи. Самое распространённое решение — просто отбрасывать непрореплицированные записи старого лидера, что может нарушить ожидания клиентов о надежности.
• Отбрасывание записей особенно опасно, если другие хранилища данных вне базы данных должны быть согласованы с содержимым базы данных. Например, в одном инциденте на GitHub [13] устаревший последователь MySQL был повышен до лидера. В базе данных использовался счётчик с автоинкрементом для назначения первичных ключей новым строкам, но из-за того, что счётчик нового лидера отставал от счётчика старого лидера, некоторые первичные ключи, ранее назначенные старым лидером, были повторно использованы. Эти первичные ключи также использовались в хранилище Redis, поэтому повторное использование первичных ключей привело к несоответствию между MySQL и Redis, что привело к раскрытию некоторых личных данных неправильным пользователям.
• В некоторых сценариях сбоя (см. Главу 8) может произойти так, что два узла одновременно считают себя лидерами. Это состояние называется «разделённый мозг» и является опасным: если оба лидера принимают записи и нет процесса разрешения конфликтов (см. «Репликация с несколькими лидерами»), вероятно, данные будут утеряны или повреждены. В качестве дополнительной защиты некоторые системы имеют механизм выключения одного узла при обнаружении двух лидеров. Однако, если этот механизм не тщательно разработан, можно получить ситуацию, при которой оба узла будут выключены [14].
• Каков правильный тайм-аут перед объявлением лидера мёртвым? Более длительный тайм-аут означает более долгое время восстановления в случае отказа лидера. Однако, если тайм-аут слишком короткий, могут возникнуть ненужные переключения. Например, временный пик нагрузки может вызвать увеличение времени ответа узла выше тайм-аута или сбой в сети может вызвать задержку пакетов. Если система уже сталкивается с высокой нагрузкой или проблемами с сетью, ненужная отработка отказа, скорее всего, ухудшит ситуацию, а не улучшит.

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

Эти проблемы — отказы узлов; ненадёжные сети и компромиссы между согласованностью, надежностью, доступностью и задержкой реплик — фактически представляют собой фундаментальные проблемы в распределённых системах. В Главах 8 и 9 мы обсудим их более подробно.

Как работает репликация на основе лидера под капотом? На практике используется несколько различных методов репликации, поэтому давайте кратко рассмотрим каждый из них.

В простейшем случае лидер регистрирует каждый запрос на запись (выражение (statement)), который он выполняет и отправляет этот журнал выражений своим последователям. Для реляционной базы данных это означает, что каждый запрос INSERT, UPDATE или DELETE пересылается последователям и каждый последователь анализирует и выполняет этот SQL-запрос, как если бы он был получен от клиента.

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

• Любой запрос, вызывающий недетерминированную функцию, такую как NOW() для получения текущей даты и времени или RAND() для получения случайного числа, вероятно, будет генерировать разное значение на каждой реплике.
• Если запросы используют автоинкрементирующийся столбец или если они зависят от существующих данных в базе данных (например, UPDATE … WHERE <некоторое условие>), они должны выполняться в точно таком же порядке на каждой реплике, иначе они могут иметь разный эффект. Это может быть ограничивающим фактором при одновременном выполнении нескольких транзакций.
• Запросы, имеющие побочные эффекты (например, триггеры, хранимые процедуры, пользовательские функции), могут привести к различным побочным эффектам на каждой реплике, если эти побочные эффекты не являются абсолютно детерминированными.

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

Репликация на основе выражений использовалась в MySQL до версии 5.1. Она всё ещё иногда используется, поскольку она довольно компактна, но по умолчанию MySQL теперь переключается на репликацию на основе строк (обсуждается вкратце), если в инструкции есть какой‐либо недетерминизм. VoltDB использует репликацию на основе выражений и делает её безопасной, требуя, чтобы транзакции были детерминированными [15].

В Главе 3 мы обсудили, как хранилища данных представляют данные на диске, и выяснили, что обычно каждая запись добавляется в журнал:

• В случае хранилища данных, организованного в виде журнала (см. «SSTables and LSM-Trees»), этот журнал является основным местом хранения. Журнальные сегменты компонуется и собираются в фоновом режиме.
• В случае B-tree (см. «B-Trees»), который перезаписывает отдельные блоки на диске, каждое изменение сначала записывается в журнал предварительной записи, так что индекс можно восстановить в согласованное состояние после сбоя.

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

Этот метод репликации используется в PostgreSQL и Oracle [16]. Основной недостаток заключается в том, что журнал описывает данные на очень низком уровне: журнал предварительной записи содержит детали о том, какие байты были изменены в каких блоках диска. Это делает репликацию тесно связанной с движком хранения. Если база данных меняет свой формат хранения с одной версии на другую, обычно невозможно запустить разные версии программного обеспечения базы данных на лидере и последователях.

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

Альтернативой является использование разных форматов журналов для репликации и для движка хранения, что позволяет отделить репликационный журнал от внутренних механизмов системы хранения. Такой репликационный журнал называется логическим, для отличия от (физического) представления данных системой хранения.

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

• Для вставленной строки журнал содержит новые значения всех столбцов.
• Для удалённой строки журнал содержит достаточно информации для уникальной идентификации удалённой строки. Обычно это был бы первичный ключ, но если на таблице нет первичного ключа, необходимо регистрировать старые значения всех столбцов.
• Для обновлённой строки журнал содержит достаточно информации для уникальной идентификации обновленной строки и новые значения всех столбцов (или по крайней мере новые значения всех столбцов, которые изменились).

Транзакция, модифицирующая несколько строк, генерирует несколько таких записей в журнале, за которыми следует запись, указывающая, что транзакция была зафиксирована. MySQL использует этот подход в своем binlog (когда настроена на использование репликации на уровне строки) [17].

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

Логический формат журнала также проще анализировать внешним приложениям. Этот аспект полезен, если вы хотите отправить содержимое базы данных во внешнюю систему, такую как хранилище данных для офлайн-анализа или для создания пользовательских индексов и кэшей [18]. Эта техника называется захват данных об изменениях и мы к ней вернемся в Главе 11.

Подходы к репликации, описанные до сих пор, реализуются системой базы данных, без участия какого-либо прикладного кода. Во многих случаях это то, что вам нужно — но есть обстоятельства, когда требуется больше гибкости. Например, если вам нужно реплицировать только подмножество данных или хотите реплицировать из одного типа базы данных в другую или если вам нужна логика разрешения конфликтов (см. «Обработка конфликтов записи»), то, возможно, потребуется перенести репликацию на уровень приложения.

Некоторые инструменты, такие как Oracle GoldenGate [19], могут предоставить приложению изменения данных, прочитав журнал базы данных. Альтернативой является использование функций, доступных во многих реляционных базах данных: триггеров и хранимых процедур.

Триггер позволяет зарегистрировать пользовательский прикладной код, который автоматически выполняется, когда происходит изменение данных (транзакция записи) в системе базы данных. Триггер имеет возможность регистрировать это изменение в отдельной таблице, из которой его можно прочитать внешним процессом. Затем этот внешний процесс может применить необходимую прикладную логику и реплицировать изменение данных в другую систему. Например, так работают Databus для Oracle [20] и Bucardo для Postgres [21].

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

Возможность переносить отказы узлов — только одна из причин, почему нужна репликация. Как упоминалось во введении к Части II, другие причины — это масштабируемость (обработка большего количества запросов, чем может обработать одна машина) и задержка (размещение реплик географически ближе к пользователям).

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

В этой архитектуре масштабирования чтения (read-scaling architecture) вы можете увеличить способность обслуживать запросы только для чтения, просто добавив больше последователей. Тем не менее, этот подход реально работает только с асинхронной репликацией — если бы вы попытались синхронно реплицировать на все последователи, отказ одного узла или сбой в сети сделали бы всю систему недоступной для записи. И чем больше узлов у вас есть, тем вероятнее, что один из них не будет работать, поэтому полностью синхронная конфигурация была бы очень ненадёжной.

К сожалению, если приложение читает данные с асинхронного последователя, оно может видеть устаревшую информацию, если последователь отстал. Это приводит к видимым несоответствиям в базе данных: если вы запустите один и тот же запрос на лидере и на последователе одновременно, вы можете получить разные результаты, потому что не все записи были отражены в последователе. Это несогласованность — всего лишь временное состояние. Если прекратить запись в базу данных и подождать некоторое время, последователи в конечном итоге догонят и станут согласованными с лидером. По этой причине этот эффект известен как «конечная согласованность» (eventual consistency) [22, 23].

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

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

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

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

В этой ситуации нам нужна согласованность «чтения после записи» (read-after-write), также известная как согласованность «читай свои записи» (read-your-writes) [24]. Это гарантия того, что если пользователь обновит страницу, он всегда увидит любые обновления, которые он отправил сам. Никаких обещаний для других пользователей: обновления других пользователей могут быть невидимыми до какого-то более позднего момента. Однако это заверяет пользователя, что их собственные данные были правильно сохранены.

Как мы можем реализовать согласованность чтения после записи в системе с репликацией на основе лидера? Существует несколько возможных техник. Несколько примеров:

• Когда вы читаете что-то, что пользователь мог бы изменить, читайте это с лидера; в противном случае — читайте с реплики. Это требует наличия у вас был какого-то способа знать, могло ли что-то измениться, фактически не запрашивая этих изменений. Например, информацию о профиле пользователя в социальной сети обычно может редактировать только владелец профиля, а не кто угодно ещё. Таким образом, простое правило: всегда читайте собственный профиль пользователя с лидера, а профили других пользователей — с реплики.
• Если большинство вещей в приложении потенциально могут быть изменены пользователем, этот подход не будет эффективным, так как большинство вещей придётся читать с лидера (что убивает преимущество масштабирования чтения). В этом случае можно использовать другие критерии для решения, читать ли с лидера. Например, вы можете отслеживать время последнего обновления и в течение одной минуты после последнего обновления делать все чтения с лидера. Вы также можете контролировать задержку репликации на последователях и предотвращать запросы на любом последователе, который отстаёт от лидера более чем на одну минуту.
• Клиент может запомнить временную метку своей последней записи — затем система может обеспечить, чтобы реплика, обслуживающая любые чтения для этого пользователя, отражала обновления по крайней мере до этой временной метки. Если реплика не достаточно обновлена, чтение может быть обработано другой репликой или запрос может ждать, пока реплика не догонит. Временная метка может быть логической временной меткой (что-то, указывающее на порядок записей, например, номер последовательности журнала) или фактическим системным временем (в этом случае синхронизация часов становится критической; см. «Ненадёжные часы»).
• Если ваши реплики распределены по нескольким центрам обработки данных (для географической близости к пользователям или для обеспечения доступности), возникают дополнительные сложности. Любой запрос, который должен быть обработан лидером, должен быть направлен в центр обработки данных, содержащий лидера.

Другая сложность возникает, когда один и тот же пользователь обращается к вашему сервису с нескольких устройств, например, из веб-браузера и мобильного приложения. В этом случае вам, возможно, захочется обеспечить согласованность чтения после записи между устройствами: если пользователь вводит какую-то информацию на одном устройстве, а затем просматривает её на другом устройстве, он должен видеть информацию, которую он только что ввёл.

В этом случае возникают дополнительные вопросы:

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

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

Это может произойти, если пользователь делает несколько чтений с разных реплик. Например, на Рис. 5-4 показан пользователь 2345, делающий один и тот же запрос дважды: сначала к последователю с небольшой задержкой, а затем к последователю с большей задержкой. (Этот сценарий довольно вероятен, если пользователь обновляет веб-страницу и каждый запрос направляется к случайному серверу.) Первый запрос возвращает комментарий, который недавно добавил пользователь 1234, но второй запрос ничего не возвращает, потому что запаздывающая реплика ещё не получила это обновление. Фактически, второй запрос наблюдает состояние системы на более раннем этапе, чем первый запрос. Это было бы не так плохо, если бы первый запрос ничего не вернул, потому что пользователь 2345, вероятно, не знал бы, что пользователь 1234 недавно добавил комментарий. Однако для пользователя 2345 это очень запутанно, если сначала он видит комментарий пользователя 1234, а затем видит, что он снова исчез.

Монотонные чтения [23] — это гарантия того, что такая аномалия не происходит. Это слабая гарантия по сравнению с полной согласованностью, но более сильная, чем конечная согласованность. Когда вы читаете данные, вы можете увидеть старое значение; монотонные чтения означают только то, что если один пользователь делает несколько последовательных чтений, он не увидит времени идущего назад — то есть, он не прочитает более старые данные после того, как ранее прочитал более новые данные.

Один из способов обеспечить монотонные чтения — убедиться, что каждый пользователь всегда читает с одной и той же реплики (разные пользователи могут читать с разных реплик). Например, реплика может быть выбрана на основе хэша идентификатора пользователя, а не случайным образом. Однако, если эта реплика выходит из строя, запросы пользователя должны быть перенаправлены на другую реплику.

Третий пример аномалий из-за задержек репликации касается нарушения причинности. Представьте себе следующий короткий диалог между мистером Пунсом и миссис Кейк:

Мистер Пунс
Насколько далеко вы можете заглянуть в будущее, миссис Кейк?

Миссис Кейк
Обычно примерно на десять секунд, мистер Пунс.

Между этими двумя фразами существует причинная зависимость: миссис Кейк услышала вопрос мистера Пунса и ответила на него.
Теперь представьте, что третье лицо слушает этот разговор через последователей. То, что сказала миссис Кейк, проходит через последователя с небольшой задержкой, но то, что сказал мистер Пунс, имеет большую задержку репликации (см. Рис. 5-5). Этот наблюдатель услышит следующее:

Миссис Кейк
Обычно примерно на десять секунд, мистер Пунс.

Мистер Пунс
Насколько далеко вы можете заглянуть в будущее, миссис Кейк?

Для наблюдателя кажется, что миссис Кейк отвечает на вопрос, прежде чем мистер Пунс его задаст. Такие сверхъестественные способности впечатляющи, но очень запутывающи [25].

Предотвращение такой аномалии требует другого типа гарантии: чтения с согласованным префиксом [23]. Эта гарантия означает, что если последовательность записей происходит в определённом порядке, то любой, читающий эти записи, увидит их в том же порядке.

Это особенно проблематично в разделённых (шардированных) базах данных, о которых мы поговорим в Главе 6. Если база данных всегда применяет записи в одном и том же порядке, чтения всегда видят согласованный префикс, так что эта аномалия не может произойти. Однако во многих распределённых базах данных разные разделы работают независимо, поэтому нет глобального упорядочения записей: когда пользователь читает из базы данных, он может видеть некоторые части базы данных в более старом состоянии и некоторые в более новом.

Одно из решений — удостовериться, что любые записи, имеющие причинную связь между собой, записываются в один и тот же раздел — но в некоторых приложениях это невозможно сделать эффективно. Существуют также алгоритмы, которые явно отслеживают причинные зависимости, о чем мы вернемся к обсуждению в «Отношении «произошло перед» и параллелизме» на стр. 78.

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

Как уже обсуждалось ранее, существуют способы, которыми приложение может предоставить более надёжную гарантию, чем база данных в основе — например, выполняя некоторые виды чтения с лидера. Однако работа с этими проблемами в коде приложения сложна и легко ошибиться.

Было бы лучше, если бы разработчикам приложений не приходилось беспокоиться об узких местах репликации и они могли бы просто доверять своим базам данных «делать всё правильно». Вот почему существуют транзакции: они представляют собой способ для базы данных предоставлять более надёжные гарантии, чтобы приложение могло быть более простым.

Одноузловые транзакции существуют уже давно. Однако при переходе к распределённым (реплицированным и разделенным) базам данных многие системы от них отказались, утверждая, что транзакции слишком дорогостоящи с точки зрения производительности и доступности и утверждая, что итоговая согласованность неизбежна в масштабируемой системе. В этом заявлении есть доля истины, но оно чересчур упрощено, и мы разработаем более нюансированное видение в течение оставшейся части этой книги. Мы вернёмся к вопросу о транзакциях в Главах 7 и 9 и обсудим некоторые альтернативные механизмы в Третьей части.

До сих пор в этой главе мы рассматривали архитектуры репликации, использующие одного лидера. Хотя это распространённый подход, существуют интересные альтернативы.

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

Естественным расширением модели репликации с лидером является возможность разрешения записей более чем на одном узле. Репликация всё ещё происходит так же: каждый узел, обрабатывающий запись, должен переслать эти изменённые данные всем другим узлам. Мы называем это конфигурацией с несколькими лидерами (также известной как мастер-мастер или активная/активная репликация). В этой настройке каждый лидер одновременно действует как последователь к другим лидерам.

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

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

В конфигурации с несколькими лидерами вы можете иметь лидера в каждом центре обработки данных. Рисунок 5-6 показывает, как может выглядеть такая архитектура. В каждом центре обработки данных используется обычная репликация лидер-последователь; между центрами обработки данных лидер каждого центра реплицирует свои изменения на лидерах в других центрах.

Давайте сравним, как себя ведут конфигурации с одним лидером и несколькими лидерами в развёртывании с несколькими центрами обработки данных:

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

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

Устойчивость к проблемам с сетью
Трафик между центрами обработки данных обычно идёт через общедоступный интернет, что может быть менее надёжным, чем локальная сеть внутри центра обработки данных. Конфигурация с одним лидером очень чувствительна к проблемам в этой связи между центрами обработки данных, потому что записи делаются синхронно через эту связь. Конфигурация с несколькими лидерами с асинхронной репликацией обычно может лучше переносить проблемы с сетью: временное прерывание сети не мешает обработке записей.

Некоторые базы данных поддерживают конфигурации с несколькими лидерами по умолчанию, но это также часто реализуется с использованием внешних инструментов, таких как Tungsten Replicator для MySQL [26], BDR для PostgreSQL [27] и GoldenGate для Oracle [19].

Несмотря на преимущества репликации с несколькими лидерами, у неё также есть крупный недостаток: те же данные могут быть одновременно изменены в двух разных центрах обработки данных и эти конфликты записей должны быть разрешены (указано как «разрешение конфликтов» на рисунке 5-6). Мы обсудим эту проблему в разделе «Обработка конфликтов записей» на стр. 63.

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

Ещё одна ситуация, когда репликация с несколькими лидерами оправдана — это когда у вас есть приложение, которое должно продолжать работать даже в отсутствие подключения к интернету.

Допустим, у вас есть приложение календаря на мобильном телефоне, ноутбуке и других устройствах. Вам нужно иметь возможность просматривать свои встречи (делать запросы на чтение) и добавлять новые встречи (делать запросы на запись) в любое время, независимо от того, подключено ли ваше устройство к интернету в данный момент. Если вы вносите изменения в офлайн-режиме, они должны синхронизироваться с сервером и вашими другими устройствами, когда устройство снова будет онлайн.

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

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

Есть инструменты, которые стремятся упростить настройку многопоточной конфигурации. Например, CouchDB предназначен для такого рода работы [29].

Приложения для совместного редактирования в режиме реального времени позволяют нескольким людям редактировать документ одновременно. Например, Etherpad [30] и Google Docs [31] позволяют нескольким пользователям одновременно редактировать текстовый документ или электронную таблицу (алгоритм кратко обсуждается в разделе «Автоматическое разрешение конфликтов»).

Мы обычно не рассматриваем совместное редактирование как проблему репликации базы данных, но в этом есть много общего с уже упомянутым редактированием оффлайн. Когда один пользователь редактирует документ, изменения мгновенно применяются к его локальной копии (состоянию документа в его веб-браузере или клиентском приложении), а затем асинхронно реплицируются на сервер и к другим пользователям, редактирующим тот же документ.

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

Тем не менее, для более быстрого совместного редактирования может потребоваться сделать единичное изменение очень маленьким (например, одно нажатие клавиши) и избегать блокировки. Этот подход позволяет нескольким пользователям редактировать одновременно, но он также вносит все сложности многопоточной репликации, включая необходимость разрешения конфликтов [32].

Самая большая проблема с репликацией с несколькими лидерами заключается в том, что могут возникнуть конфликты записи, что требует разрешения конфликта.

Рассмотрим, например, вики-страницу, которую одновременно редактируют два пользователя, как показано на Рисунке 5-7. Пользователь 1 изменяет заголовок страницы с А на B, а пользователь 2 одновременно изменяет заголовок с А на C. Изменение каждого пользователя успешно применяется к их локальному лидеру. Однако, когда изменения реплицируются асинхронно, обнаруживается конфликт [33]. Эта проблема не возникает в базе данных с одним лидером.

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

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

Самая простая стратегия для работы с конфликтами — избегать их: если приложение может гарантировать, что все записи для конкретной блока проходят через одного и того же лидера, то конфликты могут не возникнуть. Поскольку многие реализации репликации с несколькими лидерами довольно плохо справляются с конфликтами, часто рекомендуется избегать конфликтов [34].

Например, в приложении, где пользователь может редактировать свои собственные данные, вы можете обеспечить, чтобы запросы от конкретного пользователя всегда направлялись в один и тот же центр обработки данных и использовали лидера в этом центре для чтения и записи. Разные пользователи могут иметь разные «домашние» центры обработки данных (возможно, выбранные на основе географической близости к пользователю), но с точки зрения любого пользователя конфигурация по сути своей является для одного лидера.

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

База данных с одним лидером применяет записи последовательно: если есть несколько обновлений для одного и того же поля, последняя запись определяет окончательное значение поля.

В конфигурации с несколькими лидерами нет определённого порядка записей, поэтому неясно, каким должно быть конечное значение. На Рисунке 5-7 у лидера 1 заголовок сначала обновляется до B, а затем до C; у лидера 2 сначала обновляется до C, а затем до B. Ни один порядок не «правильнее» другого.

Если бы каждая реплика просто применяла записи в порядке их поступления, база данных оказалась бы в несогласованном состоянии: окончательное значение было бы C у лидера 1 и B у лидера 2. Это неприемлемо — каждая система репликации должна обеспечивать, чтобы данные в конечном итоге были одинаковыми во всех репликах. Таким образом, база данных должна разрешить конфликт конвергентно, что означает, что все реплики должны прийти к одному и тому же окончательному значению, когда все изменения будут реплицированы.

Есть различные способы конвергентного разрешения конфликтов:

• Присвойте каждой записи уникальный идентификатор (например, временную метку, длинный случайный номер, UUID или хеш ключа и значения) и выберите запись с самым высоким идентификатором в качестве победителя, а остальные записи отбросьте. Если используется временная метка, этот метод называется «последний победит» (LWW). Хотя этот подход популярен, он чрезвычайно подвержен потере данных [35]. Мы рассмотрим LWW более подробно в конце этой главы («Обнаружение одновременных записей»).
• Присвойте каждой реплике уникальный идентификатор и позвольте записям, происходящим из реплики с более высоким номером, всегда иметь преимущество перед записями, происходящими из реплики с более низким номером. Этот подход также подразумевает потерю данных.
• Любым способом объедините значения — например, упорядочьте их алфавитно, а затем объедините их (на Рисунке 5-7 объединенный заголовок может быть что-то вроде «B/C»).
• Запишите конфликт в явную структуру данных, которая сохраняет всю информацию и напишите прикладной код, который разрешит конфликт в некоторый более поздний момент времени (возможно, предложив пользователю).

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

При записи
Как только база данных обнаруживает конфликт в журнале реплицируемых изменений, она вызывает обработчик конфликта. Например, Bucardo позволяет вам написать небольшой фрагмент на Perl для этой цели. Этот обработчик обычно не может запросить пользователя — он работает в фоновом режиме и должен быстро выполняться.

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

Обратите внимание, что разрешение конфликтов обычно применяется на уровне отдельной строки или документа, а не для всей транзакции [36]. Таким образом, если у вас есть транзакция, которая атомарно делает несколько разных записей (см. Главу 7), каждая запись по-прежнему рассматривается отдельно для разрешения конфликта.

Некоторые виды конфликтов очевидны. В примере на Рисунке 5-7 две записи одновременно изменили то же поле в одной и той же записи, устанавливая разные значения. Мало сомнений, что это конфликт.

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

Быстрого готового ответа нет, но в следующих главах мы пройдем путь к хорошему пониманию этой проблемы. Мы увидим ещё несколько примеров конфликтов в Главе 7, а в Главе 12 обсудим масштабируемые подходы к обнаружению и разрешению конфликтов в реплицируемой системе.

Топология репликации описывает коммуникационные маршруты, по которым записи распространяются от одного узла к другому. Если у вас есть два лидера, как показано на Рисунке 5-7, существует только одна правдоподобная топология: лидер 1 должен отправлять все свои записи лидеру 2 и наоборот. С более чем двумя лидерами возможны различные топологии. Некоторые примеры показаны на Рисунке 5-8.

Самая общая топология — все-ко-всем (Рисунок 5-8 [c]), в которой каждый лидер отправляет свои записи каждому другому лидеру. Однако также используются более ограниченные топологии. Например, MySQL по умолчанию поддерживает только круговую топологию [34], в которой каждый узел получает записи от одного узла и пересылает эти записи (плюс свои собственные) одному другому узлу. Ещё одна популярная топология имеет форму звезды: один назначенный корневой узел пересылает записи всем остальным узлам. Топологию звезды можно обобщить до дерева.

В круговых и звездных топологиях записи может потребоваться пройти через несколько узлов, прежде чем она дойдёт до всех реплик. Поэтому узлам необходимо пересылать изменения данных, которые они получают от других узлов. Чтобы предотвратить бесконечные петли репликации, каждому узлу присваивается уникальный идентификатор и в журнале репликации каждая запись помечается идентификаторами всех узлов, через которые она прошла [43]. Когда узел получает изменение данных, помеченное собственным идентификатором, это изменение игнорируется, потому что узел знает, что оно уже было обработано.

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

С другой стороны, у топологий все-ко-всем также могут быть проблемы. В частности, некоторые сетевые соединения могут быть быстрее других (например, из-за перегрузки сети), что приводит к тому, что некоторые сообщения о репликации могут «обгонять» другие, как показано на Рисунке 5-9.

На Рисунке 5-9 клиент A вставляет строку в таблицу на лидере 1, а клиент B обновляет эту строку на лидере 3. Тем не менее, лидер 2 может получить записи в другом порядке: он может сначала получить обновление (которое с его точки зрения является обновлением строки, которая не существует в базе данных) и только затем получить соответствующую вставку (которая должна была предшествовать обновлению).

Эта проблема причинности аналогична той, что мы видели в разделе «Чтения с согласованным префиксом»: обновление зависит от предшествующей вставки, поэтому нам нужно убедиться, что все узлы обрабатывают вставку сначала, а затем обновление. Простое прикрепление метки времени к каждой записи недостаточно, потому что нельзя доверять синхронизации часов для правильной упорядоченности этих событий на лидере 2 (см. Главу 8).

Для правильной упорядоченности этих событий можно использовать технику, называемую векторами версий, о которой мы поговорим позже в этой главе (см. «Обнаружение одновременных записей»). Однако техники обнаружения конфликтов плохо реализованы во многих системах репликации с несколькими лидерами. Например, на момент написания этого текста, PostgreSQL BDR не обеспечивает причинного упорядочения записей [27] и Tungsten Replicator для MySQL даже не пытается обнаруживать конфликты [34].

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

Подходы к репликации, которые мы обсудили в этой главе — репликации с одним лидером и репликации с несколькими лидерами — основаны на идее, что клиент отправляет запрос на запись на один узел (лидер), а система базы данных заботится о копировании этой записи на другие реплики. Лидер определяет порядок обработки записей, а подчинённые применяют записи лидера в том же порядке.

Некоторые системы хранения данных идут другим путем, отказываясь от концепции лидера и позволяя любой реплике принимать записи напрямую от клиентов. Некоторые из самых ранних систем репликации данных были без лидера [1, 44], но эта идея в основном была забыта в эпоху доминирования реляционных баз данных. Она снова стала модной архитектурой для баз данных после того, как Amazon использовала её для своей внутренней системы Dynamo [37]. Riak, Cassandra и Voldemort — это хранилища с открытым исходным кодом с моделями репликации без лидера, вдохновленные Dynamo, поэтому такие базы данных также известны как базы данных в стиле Dynamo.

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

Представьте, у вас есть база данных с тремя репликами и одна из реплик в настоящее время недоступна, возможно, она перезагружается для установки обновления системы. В конфигурации с лидером, если вы хотите продолжать обрабатывать записи, вам может потребоваться выполнить отработку отказа (см. «Обработка отказа узлов»).

С другой стороны, в конфигурации без лидера отработки отказа не существует. На Рисунке 5-10 показано, что происходит: клиент (пользователь 1234) отправляет запись на все три реплики параллельно и две доступные реплики принимают запись, но недоступная реплика пропускает её. Допустим, что достаточно, чтобы две из трех реплик подтвердили запись: после того как пользователь 1234 получил два подтверждения ok, мы считаем запись успешной. Клиент просто игнорирует тот факт, что одна из реплик пропустила запись.

Теперь представьте, что недоступный узел снова в сети и клиенты начинают читать с него. Любые записи, которые произошли во время отключения узла, отсутствуют на этом узле. Таким образом, если вы читаете с этого узла, вы можете получить устаревшие значения в качестве ответов.

Для решения этой проблемы, когда клиент читает из базы данных, он не просто отправляет свой запрос одной реплике: запросы на чтение также отправляются нескольким узлам параллельно. Клиент может получить разные ответы от разных узлов, то есть актуальное значение от одного узла и устаревшее значение от другого. Для определения, какое значение новее, используются номера версий (см. «Обнаружение одновременных записей»).

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

В хранилищах данных динамического типа часто используются два механизма:

Чтение с восстановлением (read repair)
Когда клиент делает чтение с нескольких узлов параллельно, он может обнаружить устаревшие ответы. Например, на Рисунке 5-10 пользователь 2345 получает значение версии 6 от реплики 3 и значение версии 7 от реплик 1 и 2. Клиент видит, что у реплики 3 устаревшее значение и записывает более новое значение обратно на эту реплику. Этот подход хорошо работает для значений, которые часто читаются.

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

Не все системы реализуют оба этих механизма; например, у Voldemort в настоящее время нет процесса анти-энтропии. Обратите внимание, что без процесса анти-энтропии значения, которые редко читаются, могут отсутствовать на некоторых репликах и следовательно, иметь сниженную надёжность, потому что ремонт чтения выполняется только при чтении значения приложением.

В примере на Рисунке 5-10 мы считали запись успешной, даже если она была обработана только на двух из трёх реплик. Что если только одна из трёх реплик приняла запись? Как далеко мы можем зайти в этом деле?

Если мы знаем, что каждая успешная запись гарантированно присутствует как минимум на двух из трёх реплик, то это означает, что как минимум одна реплика может быть устаревшей. Таким образом, если мы читаем как минимум с двух реплик, мы можем быть уверены, что как минимум одна из двух актуальна. Если третья реплика недоступна или медленно отвечает, чтение, тем не менее, может продолжать возвращать актуальное значение.

В более общем плане, если имеется n реплик, каждая запись должна быть подтверждена w узлами, чтобы считаться успешной и мы должны запрашивать по крайней мере r узлов для каждого чтения. (В нашем примере n = 3, w = 2, r = 2.) Пока w + r > n, мы ожидаем получить актуальное значение при чтении, потому что как минимум один из r узлов, с которых мы читаем, должен быть актуален. Чтения и записи, которые следуют этим значениям r и w, называются кворумными чтениями и записями. Вы можете думать о r и w как о минимальном количестве голосов, необходимых для того, чтобы чтение или запись были допустимыми.

В базах данных в динамическом стиле параметры n, w и r обычно настраиваются. Общим выбором является сделать n нечётным числом (обычно 3 или 5) и установить w = r = (n + 1) / 2 (округленное в большую сторону). Тем не менее, вы можете изменить эти числа по своему усмотрению. Например, рабочая нагрузка с небольшим количеством записей и множеством чтений может иметь выгоду от установки w = n и r = 1. Это ускоряет чтение, но имеет недостаток: достаточно одного отказавшего узла, чтобы все записи в базе данных потерпели неудачу.

Условие кворума, w + r > n, позволяет системе выдерживать недоступные узлы следующим образом:

• Если w < n, мы всё равно можем обрабатывать записи, если узел недоступен.
• Если r < n, мы всё равно можем обрабатывать чтения, если узел недоступен.
• С n = 3, w = 2, r = 2, мы можем выдержать один недоступный узел.
• С n = 5, w = 3, r = 3, мы можем выдержать два недоступных узла. Этот случай показан на Рисунке 5-11.

Обычно чтения и записи всегда отправляются на все n реплик параллельно. Параметры w и r определяют, сколько узлов мы ждем — то есть, сколько из n узлов должны сообщить о успехе, прежде чем мы будем считать чтение или запись успешными.

Если доступно меньше требуемого количества узлов w или r, записи или операции чтения возвращают ошибку. Узел может быть недоступен по многим причинам: потому что узел выключен (аварийно завершил работу, выключен), из-за ошибки выполнения операции (невозможно записать из-за заполненного диска), из-за сбоя в сети между клиентом и узлом или по любой другой причине. Нас интересует только то, вернул ли узел успешный ответ и нам не нужно различать разные виды сбоев.

Если у вас есть n реплик, и вы выбираете w и r так, что w + r > n, то обычно можно ожидать, что каждое чтение вернёт самое последнее значение, записанное для ключа. Это происходит потому, что набор узлов, на которые вы выполняли запись и набор узлов, с которых вы читали, должны пересекаться. Другими словами, среди узлов, с которых вы читаете, должен быть как минимум один узел с самым последним значением (иллюстрировано на Рисунке 5-11).

Часто r и w выбирают так, чтобы быть большинством (больше n/2) узлов, потому что это обеспечивает w + r > n, позволяя при этом выдержать до n/2 (округлённые вниз) отказов узлов. Но кворумы не обязательно должны быть большинством — важно только то, что наборы узлов, используемых операциями чтения и записи, пересекаются хотя бы в одном узле. Другие варианты назначения кворума также возможны, что позволяет некоторую гибкость в проектировании распределённых алгоритмов.

Также можно установить w и r в меньшие значения, чтобы w + r ≤ n (то есть условие кворума не выполняется). В этом случае чтения и записи всё равно будут отправлены на n узлов, но для успешного завершения операции потребуется меньшее количество успешных ответов.

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

Тем не менее, даже с w + r > n, вероятно, существуют граничные случаи, когда возвращаются устаревшие значения. Эти случаи зависят от реализации, но возможны следующие сценарии:

• Если используется нестрогий кворум (см. «Нестрогие кворумы и направленная передача»), записи w могут попасть на разные узлы, чем чтения r, поэтому уже не существует гарантированного перекрытия между узлами r и w.
• Если две записи происходят одновременно, неясно, какая произошла первой. В этом случае единственным безопасным решением является слияние параллельных записей (см. «Работа с конфликтами записи»). Если победитель выбирается на основе метки времени (последняя запись побеждает), записи могут быть потеряны из-за расхождения часов.
• Если запись происходит параллельно с чтением, запись может быть отражена только на некоторых репликах. В этом случае неопределено, возвращается ли старое или новое значение.
• Если запись успешно произошла на некоторых репликах, но завершилась с ошибкой на других (например, потому что диски на некоторых узлах заполнены) и в целом успешно на меньшем числе, чем w реплик, она не откатывается на репликах, где она была успешной. Это означает, что если запись была отмечена как неудачная, последующие чтения могут возвращать или не возвращать значение из этой записи.
• Если узел с новым значением выходит из строя, и его данные восстанавливаются из реплики с старым значением, количество реплик, хранящих новое значение, может упасть ниже w, нарушив условие кворума.
• Даже если все работает правильно, есть граничные случаи, в которых вы можете не повезти с временем, как мы увидим в Главе 9. Таким образом, несмотря на то что кворумы кажутся гарантией того, что чтение возвращает последнее записанное значение, на практике все не так просто. Базы данных в динамическом стиле обычно оптимизированы для использования в случаях, когда можно терпеть последовательную согласованность. Параметры w и r позволяют вам регулировать вероятность чтения устаревших значений, но мудро не считать их абсолютной гарантией.

В частности, обычно вы не получаете те гарантии, о которых говорится в «Проблемы с задержкой репликации» (чтение ваших записей, монотонные чтения или согласованные префиксные чтения), поэтому вышеупомянутые аномалии могут возникнуть в приложениях. Более надёжные гарантии, как правило, требуют транзакций или консенсуса. Мы вернёмся к этим темам в Главе 7 и Главе 9.

С операционной точки зрения важно отслеживать, возвращают ли ваши базы данных актуальные результаты. Даже если ваше приложение может мириться с неактуальными данными, необходимо следить за состоянием репликации. Если она значительно отстаёт, система должна уведомить вас, чтобы вы могли выявить причину (например, проблема в сети или перегруженный узел).

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

Тем не менее, в системах с репликацией без основного узла нет фиксированного порядка, в котором применяются записи, что усложняет мониторинг. Более того, если база данных использует только чтение для восстановления (без анти-энтропии), нет ограничения на то, насколько старым может быть значение. Если значение читается редко, то значение, возвращённое устаревшей репликой, может быть древним.

Были проведены исследования по измерению устаревания реплик в базах данных с репликацией без основного узла и прогнозированию ожидаемого процента устаревших чтений в зависимости от параметров n, w и r [48]. К сожалению, это пока не является общей практикой, но было бы хорошо включить измерения устаревания в стандартный набор метрик для баз данных. Конечная согласованность является намеренно неопределённой гарантией, но для эксплуатационной способности важно иметь возможность количественной оценки «эвентуальности».

Базы данных с правильно настроенными кворумами могут терпеть отказ отдельных узлов без необходимости переключения на резервный режим. Они также могут терпеть замедление работы отдельных узлов (например, из-за перегрузки), потому что запросы не обязаны ждать ответа от всех n узлов — они могут вернуться, когда w или r узлов ответили. Эти характеристики делают базы данных с репликацией без основного узла привлекательными для случаев использования, требующих высокой доступности и низкой задержки и которые могут терпеть иногда устаревшие чтения.

Тем не менее, кворумы (как описано выше) не настолько устойчивы к отказам, как могли бы быть. Сбой в сети легко может отрезать клиента от большого числа узлов базы данных. Несмотря на то, что эти узлы работают и другие клиенты могут подключиться к ним, для клиента, отрезанного от узлов базы данных, они могут быть равнозначны мертвым. В этой ситуации вероятно, что остается менее чем w или r доступных узлов, поэтому клиент больше не может добраться до кворума.

В большом кластере (с значительно большим числом узлов, чем n) вероятно, что клиент может подключиться к некоторым узлам базы данных во время сбоя в сети, просто не к тем узлам, которые ему нужны для формирования кворума для определённого значения. В этом случае проектировщики баз данных сталкиваются с дилеммой:

• Лучше ли возвращать ошибки для всех запросов, для которых нельзя достичь кворума из w или r узлов?
• Или же стоит ли всё равно принимать записи и записывать их на некоторые узлы, доступные, но не являющиеся среди n узлов, на которых обычно хранится значение?

Последнее известно как нестрогий кворум [37]: для записи и чтения по-прежнему требуются успешные ответы w и r, но среди них могут быть узлы, не входящие в назначенные n «домашние» узлы для значения. В аналогии, если вы заблокировали себя из дома, вы можете постучаться к соседу и попросить разрешения на временное пребывание на их диване.

Как только сетевое прерывание устранено, любые записи, которые один узел временно принял от имени другого узла, отправляются на соответствующие узлы «домой». Это называется направленной передачей (hinted handoff). (Как только вы снова найдёте ключи от своего дома, ваш сосед вежливо попросит вас встать с их дивана и идти домой.)

Нестрогие кворумы особенно полезны для повышения доступности записи: пока доступны любые w узлов, база данных может принимать записи. Тем не менее это означает, что, даже когда w + r > n, вы не можете быть уверены, что прочитаете последнее значение для ключа, потому что последнее значение может быть временно записано на некоторые узлы вне n [47].

Таким образом, нестрогий кворум на самом деле не кворум в традиционном смысле. Это только заверение в надёжности, а именно что данные хранятся на w узлах где-то. Нет гарантии, что чтение с r узлов его увидит, пока подсказка не завершена.

Нестрогие кворумы дополнительные во всех распространённых реализациях Dynamo. В Riak они включены по умолчанию, а в Cassandra и Voldemort они отключены по умолчанию [46, 49, 50].

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

Cassandra и Voldemort реализуют поддержку нескольких центров обработки данных в рамках обычной модели без лидера: количество реплик n включает узлы во всех центрах обработки данных и в конфигурации можно указать, сколько из n реплик вы хотите иметь в каждом центре обработки данных. Каждая запись от клиента отправляется на все реплики, независимо от центра обработки данных, но обычно клиент ожидает подтверждения от кворума узлов в своем локальном центре обработки данных, чтобы не подвергаться задержкам и перебоям на кросс-центровой обработки данных связи. Записи с более высокой задержкой к другим центрам обработки данных часто настраиваются для асинхронной обработки, хотя в конфигурации есть некоторая гибкость [50, 51].

Riak поддерживает всю коммуникацию между клиентами и узлами базы данных в пределах одного центра обработки данных, поэтому n описывает количество реплик в пределах одного центра обработки данных. Межцентровая репликация данных между кластерами баз данных происходит асинхронно в фоновом режиме, в стиле, аналогичном многолидерной репликации [52].

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

Проблема в том, что события могут поступать в разном порядке к разным узлам из-за переменных сетевых задержек и частичных сбоев. Например, на рисунке 5-12 показаны два клиента, A и B, одновременно пишущие в ключ X в хранилище данных из трех узлов:

• Узел 1 получает запись от A, но никогда не получает запись от B из-за временного сбоя.
• Узел 2 сначала получает запись от A, затем запись от B.
• Узел 3 сначала получает запись от B, затем запись от A.

Если каждый узел просто перезаписывал бы значение для ключа каждый раз, когда он получал запрос на запись от клиента, узлы стали бы навсегда несогласованными, как показано в последнем запросе get на рисунке 5-12: узел 2 считает, что окончательное значение X — это B, тогда как другие узлы считают, что значение — это A.

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

Мы кратко коснулись некоторых техник разрешения конфликтов в «Разрешение конфликтов при записи». Прежде чем завершить эту главу, давайте немного подробнее рассмотрим эту проблему.

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

Как указано кавычками вокруг слова «последнее», эта идея может ввести в заблуждение. В примере с рисунка 5-12 ни клиент A, ни клиент B не знали о другом, когда отправили свои запросы на запись на узлы базы данных, поэтому неясно, какой из них произошел первым. Фактически нет смысла говорить, что что-то произошло «первым»: мы говорим, что записи совпадают, поэтому их порядок не определён.

Несмотря на то что у записей нет естественной упорядоченности, мы можем принудить к произвольному упорядочиванию. Например, мы можем прикрепить временную метку к каждой записи, выбрать самую большую временную метку как самую «последнюю» и отбросить все записи с более ранней меткой времени. Этот алгоритм разрешения конфликтов, называемый «последняя запись побеждает» (LWW), является единственным поддерживаемым методом разрешения конфликтов в Cassandra [53] и необязательной функцией в Riak [35].

LWW достигает цели конечной сходимости, но за счет прочности: если существует несколько одновременных записей в один и тот же ключ, даже если все они были зарегистрированы как успешные для клиента (потому что они были записаны в w репликах), только одна из записей будет сохранена, а остальные будут молча отброшены. Более того, LWW может даже отбрасывать записи, которые не являются одновременными, как мы расскажем в разделе «Временные метки для упорядочивания событий».

Существуют ситуации, такие как кэширование, в которых потерянные записи, возможно, допустимы. Если потеря данных недопустима, LWW — плохой выбор для разрешения конфликтов.

Единственным безопасным способом использования базы данных с LWW является обеспечение того, чтобы ключ был записан только один раз и затем рассматривался как неизменный, избегая таким образом любых параллельных обновлений для одного и того же ключа. Например, рекомендуется использовать Cassandra с UUID в качестве ключа, обеспечивая тем самым каждой операции записи уникальный ключ [53].

Как мы определяем, являются ли две операции параллельными или нет? Чтобы развить интуицию, давайте рассмотрим несколько примеров:

• На рисунке 5-9 две записи не являются параллельными: вставка A происходит до инкрементирования B, потому что значение, увеличенное B, является значением, вставленным A. Другими словами, операция B основана на операции A, поэтому операция B должна была произойти позже. Мы также говорим, что B зависит от A.
• С другой стороны, две записи на рисунке 5-12 являются параллельными: когда каждый клиент начинает операцию, он не знает, что другой клиент также выполняет операцию с тем же ключом. Таким образом, между операциями нет причинной зависимости.

Операция A происходит до операции B, если B знает о A, зависит от A или строится на основе A каким-то образом. Вопрос о том, произошла ли одна операция до другой, ключевой для определения того, что означает параллелизм. Фактически, мы можем просто сказать, что две операции являются параллельными, если ни одна из них не произошла до другой (то есть ни одна из них не знает о другой).

Таким образом, когда у вас есть две операции A и B, существует три возможности: либо A произошло до B, либо B произошло до A, либо A и B параллельны. Нам нужен алгоритм, чтобы сказать нам, являются ли две операции параллельными или нет. Если одна операция произошла до другой, позднее операция должна перезаписать более раннюю операцию, но если операции параллельны, у нас есть конфликт, который нужно разрешить.

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

На рисунке 5-13 показаны два клиента, одновременно добавляющих товары в одну и ту же корзину. (Если вам кажется, что этот пример слишком абсурден, представьте себе, что два диспетчера воздушного движения одновременно добавляют воздушные суда в сектор, который они отслеживают). Изначально корзина пуста. Клиенты делают в сумме пять записей в базу данных:

1. Клиент 1 добавляет молоко в корзину. Это первая запись по этому ключу, поэтому сервер успешно её сохраняет и присваивает версию 1. Сервер также возвращает значение клиенту вместе с номером версии.
2. Клиент 2 добавляет яйца в корзину, не зная, что клиент 1 одновременно добавил молоко (клиент 2 думал, что его яйца — единственный товар в корзине). Сервер присваивает версию 2 этой записи и хранит яйца и молоко как два отдельных значения. Затем сервер возвращает оба значения клиенту, вместе с номером версии 2.
3. Клиент 1, не подозревая о записи клиента 2, хочет добавить муку в корзину, поэтому он считает, что текущее содержимое корзины должно быть [молоко, мука]. Он отправляет это значение на сервер вместе с номером версии 1, который сервер дал клиенту 1 ранее. Сервер может сказать по номеру версии, что запись [молоко, мука] заменяет предыдущее значение [молоко], но она является конкурентной с [яйца]. Таким образом, сервер присваивает версию 3 [молоко, мука], перезаписывает значение версии 1 [молоко], но оставляет значение версии 2 [яйца] и возвращает оба оставшихся значения клиенту.
4. Тем временем клиент 2 хочет добавить ветчину в корзину, не зная, что клиент 1 только что добавил муку. Клиент 2 получил два значения [молоко] и [яйца] от сервера в последнем ответе, поэтому клиент теперь объединяет эти значения и добавляет ветчину, формируя новое значение [яйца, молоко, ветчина]. Он отправляет это значение на сервер вместе с предыдущим номером версии 2. Сервер обнаруживает, что версия 2 перезаписывает [яйца], но является конкурентной с [молоко, мука], поэтому оставшиеся два значения — [молоко, мука] с версией 3 и [яйца, молоко, ветчина] с версией 4.
5. Наконец, клиент 1 хочет добавить бекон. Ранее он получил [молоко, мука] и [яйца] от сервера на версии 3, поэтому он объединяет их, добавляет бекон и отправляет окончательное значение [молоко, мука, яйца, бекон] на сервер вместе с номером версии 3. Это перезаписывает [молоко, мука] (обратите внимание, что [яйца] уже были перезаписаны на предыдущем этапе), но она является конкурентной с [яйца, молоко, ветчина], поэтому сервер оставляет эти две конкурирующие записи.

Поток данных между операциями на рисунке 5-13 показан графически на рисунке 5-14. Стрелки показывают, какая операция произошла до какой другой операции, в том смысле, что позднее операция знала о предыдущей или зависела от неё. В этом примере клиенты никогда не полностью уточняют данные на сервере, поскольку всегда идёт другая операция, происходящая параллельно. Но старые версии значения в конечном итоге перезаписываются и ни одна запись не теряется.

Обратите внимание, что сервер может определить, являются ли две операции конкурентными, глядя на номера версий — ему не нужно интерпретировать само значение (поэтому значение может быть любой структурой данных). Алгоритм работает следующим образом:

• Сервер поддерживает номер версии для каждого ключа, увеличивает номер версии при каждой записи в этот ключ и хранит новый номер версии вместе с записанным значением.
• Когда клиент читает ключ, сервер возвращает все значения, которые ещё не были перезаписаны, а также последний номер версии. Клиент должен прочитать ключ перед записью.
• Когда клиент пишет ключ, он должен включить номер версии из предыдущего чтения и ему нужно объединить все значения, которые он получил при предыдущем чтении. (Ответ на запрос на запись может быть похожим на чтение, возвращая все текущие значения, что позволяет нам цеплять несколько записей, как в примере с корзиной покупок).
• Когда сервер получает запись с определённым номером версии, он может перезаписать все значения с этим номером версии и ниже (поскольку он знает, что они были объединены в новое значение), но он должен сохранить все значения с более высоким номером версии (потому что эти значения конкурентны с поступающей записью).

Когда запись включает номер версии из предыдущего чтения, это говорит нам, на каком предыдущем состоянии базируется запись. Если вы делаете запись без включения номера версии, она конкурентна с другими записями, поэтому она ничего не перезапишет — её просто вернут как одно из значений при последующих чтениях.

Этот алгоритм гарантирует, что никакие данные не пропадут незамеченными. К сожалению, это требует дополнительной работы со стороны клиентов: если несколько операций происходят одновременно, клиентам придется провести дополнительную очистку, объединяя параллельно записанные значения. Riak называет эти параллельные значения (братьями и сёстрами?) сиблингами.

Объединение сиблингов в значительной степени сводится к той же проблеме, что и разрешение конфликтов в многопроцессорной репликации с несколькими лидерами, о которой мы ранее говорили. Простым подходом является выбор одного из значений на основе номера версии или временной метки (последняя запись побеждает), но это может привести к потере данных. Так что, возможно, придётся предпринять что-то более умное в коде приложения.

С примером корзины для покупок разумным подходом к объединению сиблингов является просто взять их объединение. На рисунке 5-14 два конечных сиблинга: [молоко, мука, яйца, бекон] и [яйца, молоко, ветчина]; обратите внимание, что молоко и яйца присутствуют в обоих, хотя были записаны только один раз. Объединённое значение может быть что-то вроде [молоко, мука, яйца, бекон, ветчина], без дубликатов.

Однако, если вы хотите позволить людям также удалять вещи из своих корзин, а не только добавлять их, то объединение сиблингов может не дать правильный результат: если вы объедините две сиблинговых корзины и предмет был удалён только в одной из них, то удалённый предмет снова появится в объединении сиблингов [37]. Чтобы избежать этой проблемы, предмет нельзя просто удалить из базы данных при его удалении; вместо этого система должна оставить маркер с соответствующим номером версии, указывающий, что предмет был удалён при объединении сиблингов. Такой маркер удаления известен как надгробие (tombstone). (Мы ранее видели надгробия в контексте компактации журнала).

Поскольку объединение сиблингов в коде приложения сложно и подвержено ошибкам, существуют усилия по разработке структур данных, которые могут выполнять это объединение автоматически, как это обсуждается в разделе «Автоматическое разрешение конфликтов». Например, поддержка типов данных в Riak использует набор структур данных, называемых CRDT [38, 39, 55], которые могут автоматически объединять сиблингов разумным образом, включая сохранение удалений.

Пример на рисунке 5-13 использовал только одну реплику. Как алгоритм меняется, когда есть несколько реплик, но нет лидера? Рисунок 5-13 использует один номер версии для учета зависимостей между операциями, но это недостаточно, когда несколько реплик принимают записи параллельно. Вместо этого нам нужно использовать номер версии для каждой реплики, а также для каждого ключа. Каждая реплика увеличивает свой собственный номер версии при обработке записи и также отслеживает номера версий, которые она видела от каждой из других реплик. Эта информация показывает, какие значения перезаписывать, а какие оставить в качестве сиблингов.

Совокупность номеров версий со всех реплик называется вектором версий (version vector) [56]. Используется несколько вариантов этой идеи, но, возможно, наиболее интересен точечный вектор версий [57], который используется в Riak 2.0 [58, 59]. Мы не будем вдаваться в детали, но способ работы схож с тем, что мы видели в нашем примере с корзиной.

Как и номера версий на рисунке 5-13, векторы версий отправляются от реплик базы данных к клиентам при чтении значений и должны быть отправлены обратно в базу данных при последующей записи значения. (Riak кодирует вектор версий как строку, которую он называет контекстом причинности). Вектор версий позволяет базе данных различать перезаписи и параллельные записи.

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

В этой главе мы рассмотрели проблему репликации. Репликация может служить нескольким целям:

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

Работа в отсутствие соединения
Позволяет приложению продолжать работу при разрыве сетевого соединения.

Задержка
Размещение данных географически близко к пользователям, чтобы они могли взаимодействовать с ними быстрее.

Масштабируемость
Возможность обработки большего объёма чтения, чем одна машина могла бы обработать, выполняя чтения на репликах.

Несмотря на простую цель — хранение копии одних и тех же данных на нескольких машинах, репликация оказывается удивительно сложной проблемой. Это требует тщательного размышления о параллелизме и обо всех вещах, которые могут пойти не так и управления последствиями этих сбоев. Как минимум, нам нужно уметь работать с недоступными узлами и разрывами в сети (и это даже не учитывает более хитрые виды сбоев, такие как тихие ошибки коррупции данных из-за ошибок в программном обеспечении).

Мы обсудили три основных подхода к репликации:

Репликация с одним лидером
Клиенты отправляют все записи на один узел (лидер), который отправляет поток событий изменения данных на другие реплики (последователей). Чтение может выполняться на любой реплике, но чтение с последователей может быть устаревшим.

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

Репликация без лидера
Клиенты отправляют каждую запись на несколько узлов и выполняют чтение с нескольких узлов параллельно для обнаружения и исправления узлов с устаревшими данными.

Каждый подход имеет свои преимущества и недостатки. Репликация с одним лидером популярна, потому что её довольно легко понять, и нет необходимости беспокоиться о разрешении конфликтов. Репликация с несколькими лидерами и репликация без лидера могут быть более надёжными в случае неисправных узлов, разрывов в сети и возникновений задержки — за счёт усложнения понимания и предоставления только очень слабых гарантий согласованности.

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

Мы рассмотрели некоторые странные эффекты, вызванные задержкой репликации, и обсудили несколько моделей согласованности, которые полезны для определения поведения приложения при задержке репликации:

Согласованность чтения после записи
Пользователи всегда должны видеть данные, которые они сами отправили.

Монотонные чтения
После того как пользователи увидели данные в один момент времени, они не должны увидеть данные из более раннего момента времени.

Согласованные префиксные чтения
Пользователи должны видеть данные в состоянии, которое имеет причинный смысл: например, видеть вопрос и его ответ в правильном порядке.

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

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