Рассмотрение метода репликации в подготовке к интервью по проектированию системы: репликация без лидера

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

• Amazon Dynamo DB

• Riak

• Voldemort

• Cassandra&

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

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

Пример

Рассмотрим конкретный пример системы с тремя репликами, обозначенными A, B и C, как показано ниже:

Далее, предположим, что клиент хочет обновить пару ключ/значение (x, 5), которая уже хранится в системе. В приведенной выше схеме клиент будет производить запись на кворум узлов или чтение из него. Кворум - это половина узлов системы, то есть 2. Изменение сначала получает узел A. Затем оно передается узлу B для репликации, как показано ниже. 

Узлы A и B записывают новое изменение и удовлетворяют требованию кворума. Клиенту/пользователю отправляется подтверждение, даже если узел C еще не реплицировал изменение. 

Пользователю посылается подтверждение после того, как два из трех узлов зафиксируют изменение

В общем случае кворум равен n/2, округленному в большую сторону, при нечетном числе узлов в системе, и 1+(n/2) при четном числе узлов.

Записи и чтения

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

1. Пользователь пытается обновить пару ключ-значение

2. Пользователь получает подтверждение от одного из узлов.

3. Узел, зафиксировавший изменение, выходит из строя.

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

5. Пользователь получает устаревшее значение от одного из узлов, который не получил последнее обновление.

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

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

2. Узлы A и C работают: В этом случае оба узла возвращают последнее значение ключа.

3. Узлы A и B работают: Узел A отвечает последним значением, а узел B - устаревшим. Клиент получает оба значения и выбирает из них последнее. Далее мы рассмотрим, как клиент определяет, какое из двух полученных значений является последним. Кроме того, в данном случае мы предполагаем, что последнее значение еще не реплицировалось на узел B.

4. Узлы C и B работают: Клиент выбирает последнее значение, полученное от узла C, и игнорирует значение, полученное от узла B.

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

6. Все узлы работают: В этом случае, если последнее значение еще не было реплицировано на узел B, клиент получит последнее значение с узлов A и C и устаревшее значение с узла B. Клиент выбирает последнее значение и игнорирует значение с узла B.

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

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