http://pmg.csail.mit.edu/papers/vr-revisited.pdf
Граф состояний репликаций требует, чтобы репликации запускались в одинаковом начальном состоянии, и чтобы операции были детерминированы. С этими допущениями, легко увидеть, что реплики в конечном итоге будут в одинаковом состоянии, если они выполнили одинаковую последовательность операций. Проблема для протокола репликаций в гарантии того, что операции выполняются в одинаковом порядке на всех репликах несмотря на одновременный запросы от клиентов и несмотря на отказы в работе.
VR использует первичную реплику (лидера) для упорядочения запросов от клиентов; другие реплики - это резервные копии (англ. backups), которые просто принимают порядок, выбранный лидером. Использование лидера предоставляет простое решение для требования порядка запросов, но это добавляет проблему: что случится, если лидер откажет? VR имеет решает эту проблему, разрешая различным репликам брать на себя роль лидера с течением времени. Система проходит через последовательность представлений (англ. view). В каждой картине одна из реплик выбрана в качестве лидера. Резервные копии проверяют лидера, и если он, по-видимому, неисправен, они выполняют протокол смены представления (англ. view change) для выбора нового лидера.
Для корректной работы по изменению вида в течение смены представления состояние системы в следующем представлении должно отражать все клиентские операции, которые были выполнены в предыдущих представлениях в предыдущем выбранном порядке. Мы поддерживаем это требование, имея ожидание лидера до тех пор, пока по крайней мере f + 1 реплика (включая самого лидера) не будут знать о запросе клиента до его выполнения, и инициализируя состояние нового представления через опрашивание f + 1 реплики. Таким образом, каждый запрос, известен как, кворум (англ. quorum), и новое представление начинается с кворума.
VR также предоставляет путь для узлов, которые не удалось восстановить, а затем продолжить обработку. Это важно, поскольку в противном случае количество отказов узлов могло бы в конечном счете превысить порог. Корректное восстановление требует, чтобы восстанавливаемая реплика присоединялась к протоколу только после того, как он знает состояние по крайней мере не старее того, когда реплика отказала. Тогда он может правильно реагировать, если это необходимо для кворума. Очевидно, это требование могло бы быть удовлетворено, если у нас каждая реплика записывала, что она знает на диск перед каждым сообщением. Но мы не требуем использование диск для этой цели.
Итак, VR использует 3 суб-протокола, которые работает вместе и гарантируют корректность:
- Обычный случай, обрабатывающий пользовательские сообщения.
- Изменение представлений для выбора нового лидера.
- Восстановление отказавшей реплики, чтобы она могла заново присоединиться к группе.
Эти суб-протоколы детально описаны в следующем разделе.
Этот раздел описывает как VR работает при допущении, что группа из реплик фиксирована. Мы опишем несколько путей для улучшения производительности протоколов в разделе 5 и оптимизаций в разделе 6. Реконфигурации протокола, который позволяет группе реплик изменяться описана в разделе 7.
Фигура 2 показывает состояние VR слоя реплики. Подлинность лидера не записана в состоянии, но скорее вычисляется из номера представления (англ. view-number) и конфигурации (англ. configuration). Реплики нумеруются на основе их IP-адресов: реплика с наименьшим IP-адресом - реплика под номером 1. Лидер выбирается циклически, начиная с реплики 1, когда система переходит в новые представления. Статус (англ. status) показывает каком суб-протоколом занимается реплика.
Клиентская сторона также имеет состояние. Оно записывает конфигурацию и текущий номер представления, по его мнению, что позволяет знать какая реплика является в данный момент первичной. Каждое сообщение, посланное клиенту, сообщение ему о текущей номере представления, это позволяет клиенту следить за лидером.
Кроме того клиент записывает собственный номер (англ. client-id) и текущий номер запроса (англ. request-number). Клиенту позволено иметь только один outstanding запрос за раз. Каждому запросу дан номер клиентом и последующие запросы должны иметь больший номер, чем предыдущие; мы опишем как клиенты гарантируют это, если они отказывают и восстанавливаются в разделе 4.5. Номер запроса используется репликами для избежания выполнения запроса больше 1 раза; он также используется клиентом для отбрасывания дублирующихся ответов на его запросы.
Этот раздел описывает, как VR работает, когда лидер не отказал. Реплики принимают участие в обработке клиентский запросов только когда их статус нормальный. Это ограничение критично для корректности, описанной в разделе 8.
Описание протокола допускает, что все участвующие реплики имеют одинаковое представление. Каждое сообщение, посланное от одной реплики до другой, содержит текущий номер представления отправителя. Реплики обрабатывают только сообщение нормального протокола, содержащие номер представления, который совпадает с номером представления, который они знают. Если отправитель впереди, то реплика выполняет перенос состояние (англ. state transfer): она запрашивает информацию, которой ей не хватает из других реплик и использует эту информацию для приведения себя до актуального состояния перед обработкой сообщения. Перенос состояния описана дальше в разделе 5.2.
Протокол обработки запросов работает следующим образом. Описание игнорирует ряд мелких деталей таких, как переотправка сообщений протокола, которые не получили ответов.
Фигура 2: VR состояние реплики
- configuration. Это сортированный массив, содержащий IP-адреса каждой из 2f + 1 реплики.
- replica number. Это индекс в конфигурации, где хранится IP-адрес текущей реплики.
- Текущий view-number. Изначально, 0.
- Текущий status. Либо нормальный, либо изменение представления, либо восстановление.
- op-number назначенный самому недавнему полученному запросу. Изначально, 0.
- log. Это массив, содержащий записи номеров операций. Записи содержат запросы, которые были получены до сих пор в их указанном порядке.
- commit-number. Это op-number последней зафиксированной операции.
- Таблица клиентов. Сюда записывается для каждого клиента ряд самых недавних запросов, а также если запрос был выполнен, результат, отправленный в ответ на запрос.
- Клиент посылает сообщение [REQUEST op, c, s] лидеру, где op - операция (с аргументами), которую клиент хочет выполнить, с - client-id, s - request-number, привязанный к запросу.
- Когда лидер получает запрос, он сравнивает request-number в запросе с информацией в client-table. Если request-number s не больше, чем информация в таблице, он сбрасывает запрос. Но перешлет его, если запрос последний от клиента и уже был выполнен.
- Лидер повышает op-number, добавляет запрос в конец log и обновляет информацию для этого клиента в client-table, чтобы она содержала новый номер запроса s. Затем лидер шлет сообщение [PREPARE v, m, n, k] другим репликам, где v - текущий view-number, m - сообщение, полученное от клиента, n - op-number, привязанный к запросу, k - commit-number.
- Резервные копии обрабатывают сообщение PREPARE в порядке: резервная копии не примет запрос с op-number n пока имеет записи для всех предыдущих запросов в log. Когда резервная копия i получит PREPARE сообщение, она ждет до тех пор, пока имеет сообщение в своем логе о всех предыдущих запросах (делая перенос состояния, если необходимо получить отсутствующую информацию). Затем она увеличивает свой op-number на 1, добавляет запрос в конец своего log, обновляет клиентскую информацию в client-table и отправляет сообщение [PREPAREOK v, n, i] лидеру для обозначения, что эта операция и все предыдущие готовы локально.
- Лидер ожидает для f PREPAREOK сообщение из различных резервных копий; на этой стадии он рассматривает операцию (и все ранние) как зафиксированные. Затем, после выполнения всех ранних операций (которые имеют меньшие op-numbers), лидер выполняет операцию, делая вызов сервисного кода и увеличивает commit-number на 1. Затем он шлет сообщение [REPLY v, s, x] клиенту, где v - view-number, s - номер, предоставленный клиентом, в запросе, x - результат вызова сервисного кода. Лидер также обновляет клиентскую запись в client-table, содержащую результат.
- Обычно лидер информирует резервные копии о фиксации, когда он посылает следующее PREPARE сообщение; это цель commit-number в PREPARE сообщении. Однако, если лидер не получает новых клиентских запросов своевременно, он вместо этого информирует резервные копии о последнем коммите, отправляя им сообщение [COMMIT v,k], где k - commit-number (отметим, что в этом случае commit-number = op-number).
- Когда резервная копия узнает о коммите, она ждет, пока запрос находится в её логе (который может требовать переноса состояния) и пока она выполняет все предыдущие операции. Затем она выполняет операцию через вызов сервисного кода, увеличивая свой commit-number на 1, обновляет клиентскую запись в client-table, но не отправляет ответ клиенту.
Фигура 3 показывает фазы обычного протокола обработки.
Если клиент не получается своевременно ответы на запросы, он заново отсылает запрос всем репликам. Таким образом если группа перешла в более позднее представление, его сообщения достигнут нового лидера. Резервные копии игнорируют клиентские запросы, только лидер обработает их.
Описание протоколов, представленное в предыдущем разделе игнорировал ряд важных вопросов, которые должны быть решены на практике. В этом разделе мы опишем как обеспечить хорошую производительность при восстановлении узла, переноса состояния и изменения представления. Во всех этих случаях ключом для решения проблемы является эффективное управление журналом логирования.