Кворумы: различия между версиями

Мотивация создания систем кворумов обусловлена необходимостью обеспечить надежность выполнения машинами критически важных задач. Единственным способом повышения надежности сервиса, помимо использования более надежного оборудования, является тиражирование, или репликация. Чтобы сделать сервис надежным, его можно установить на несколько одинаковых серверов, каждый из которых хранит копию состояния сервиса и выполняет операции на нем чтения/записи. Это позволяет системе предоставлять информацию и выполнять операции даже в том случае, если некоторые машины выйдут из строя или оборвутся каналы связи. К сожалению, репликация влечет расходы, связанные с необходимостью поддерживать согласованность серверов. Чтобы повысить доступность и производительность тиражируемого сервиса, Гиффорд и Томас [3, 14] в 1979 году ввели использование ''голосов'', назначаемых каждому серверу, так, чтобы для выполнения операций было достаточно большинства от суммы голосов. В более общем виде системы кворумов формально определяются следующим образом.

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

В приложении клиенты выполняют операции чтения и записи переменной <math>x</math>, которая реплицируется на каждом сервере в совокупности <math>U</math>. Копия переменной <math>x</math> хранится на каждом сервере вместе со значением временной метки <math>t</math>. Временные метки назначаются клиентом каждой реплике переменной, когда клиент записывает реплику. Разные клиенты выбирают разные временные метки, например, целые числа, дополненные именем c в младших разрядах. Операции чтения и записи реализованы следующим образом.

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

'''Решетка''': предположим, что совокупность серверов имеет размер <math>n = k^2</math> для некоторого целого числа <math>k</math>. Разложим совокупность в решетку <math>\sqrt{n} \times \sqrt{n}</math>, как показано на рис. 1. Кворум – это объединение полного ряда и одного элемента из каждого ряда ниже полного ряда. Таким образом, получается система кворумов типа «решетка», размер кворумов которой составляет <math>O(\sqrt{n})</math>.

'''FPP''' (мажоритарная избирательная система): Предположим, что совокупность серверов имеет размер <math>n = q^2 + q + 1</math>, где <math>q = p^r</math> для простого <math>p</math>. Известно, что для <math>n</math> существует конечная проективная плоскость с <math>q + 1</math> попарно пересекающимися подмножествами, каждое подмножество имеет размер <math>q + 1</math>, и где каждый элемент содержится в <math>q + 1</math> подмножествах. Тогда множество подмножеств конечной проективной плоскости образует систему кворумов.

Голосование было упомянуто выше как интуитивный способ осмысления техники кворумов. Оказывается, назначения голосов и кворумы не эквивалентны. Гарсия-Молина и Барбара [2] показали, что системы кворумов являются строго более общими, чем голосования, то есть каждое назначение голосов имеет некоторую соответствующую систему кворумов, но не наоборот. На самом деле, для системы с <math>n</math> серверами существует двойное экспоненциальное <math>(2^{2^{cn}})</math> число недоминируемых комитетов и только <math>O(2^{n^2})</math> различных назначений голосов, хотя для <math>n \le 5</math> голосование и недоминируемые комитеты идентичны.

Следующая теорема была доказана в работе [ ] для всех систем кворумов.

Заметим, что устойчивость <math>f</math> составляет не более <math>c(\mathcal{Q}) - 1</math>, так как при отключении членов наименьшего кворума все кворумы будут поражены. Однако возможно, что <math>f</math>-устойчивая система кворумов, несмотря на уязвимость к нескольким конфигурациям <math>f + 1</math> отказов, может пережить множество конфигураций более чем <math>f</math> отказов. Один из способов измерить это свойство системы кворумов – это предположить, что каждый сервер выходит из строя независимо с вероятностью <math>p</math>, а затем определить вероятность <math>F_p</math> того, что ни один кворум не останется полностью живым. Она называется ''вероятностью отказа'' и формально определяется следующим образом:

Пелег и Вул изучили доступность систем кворумов в работе [11]. Хорошая вероятность отказа <math>F_p(\mathcal{Q})</math> для системы кворумов <math>\mathcal{Q}</math> имеет <math>lim_{n \to \infty} F_p(\mathcal{Q}) = 0</math>, когда <math>p < \frac{1}{2}</math>. Заметим, что вероятность отказа любой системы кворумов, чья отказоустойчивость равна <math>f</math>, не ниже <math>e^{- \Omega(f)}</math>. Большинство имеет наилучшую доступность, когда <math>p < \frac{1}{2}</math>; для <math>p = \frac{1}{2}</math> существуют кворумные построения с <math>F_p(\mathcal{Q}) = \frac{1}{2}</math>; для <math>p > \frac{1}{2}</math> синглтон имеет наилучшую вероятность отказа <math>F_p(\mathcal{Q}) = p</math>, но для большинства систем кворумов <math>F_p(\mathcal{Q})</math> стремится к 1.

Кворумные построения можно сравнивать, проанализировав их поведение в соответствии с приведенными выше показателями. Синглтон имеет нагрузку 1, устойчивость 0 и вероятность отказа <math>F_p = p</math>. Эта система имеет наилучшую вероятность отказа, когда <math>p > \frac{1}{2}</math>, но в остальном демонстрирует низкие показатели как по доступности, так и по нагрузке.

Нагрузка решетки равна <math>O(\frac{1}{\sqrt{n}})</math>, отличаясь от оптимальной не более чем на постоянный коэффициент. Однако ее устойчивость составляет только <math>\sqrt{n} - 1</math>, и она имеет плохую вероятность отказа, которая стремится к 1 по мере роста <math>n</math>.

Как показали эти системы, существует компромисс между нагрузкой и отказоустойчивостью в системах кворумов, где устойчивость <math>f</math> системы кворумов <math>\mathcal{Q}</math> удовлетворяет соотношению <math> f \le nL(\mathcal{Q})</math>. Таким образом, улучшение одного из них должно происходить за счет другого, и фактически невозможно одновременно достичь оптимального результата по обоим показателям. Можно сделать вывод, что хорошая загрузка конфликтует с низкой вероятностью отказа, но это не обязательно так. На самом деле существуют системы кворумов, такие как система путей (Paths) Наора и Вула [10] и треугольная решетка Баззи [1], которые достигают асимптотически оптимальной нагрузки <math>O(1/\sqrt{n})</math> и имеют близкую к оптимальной вероятность отказа для своих размеров кворумов. Другое построение – система CWlog Пелега и Вула [12], которая имеет необычно малый размер кворума log n – log log n, и для систем с кворумами такого размера имеет оптимальную нагрузку, <math>L(CWlog) = O(1/log n)</math>, и оптимальную вероятность отказа.

По большей части системы кворумов изучались в средах, где сбои могут просто приводить к недоступности серверов (доброкачественные сбои). Но что, если сервер может проявить произвольное, возможно, злонамеренное поведение? Малхи и Райтер [7] провели исследование систем кворумов в средах, склонных к произвольному (византийскому) поведению серверов. Интуитивно, система кворумов, устойчивая к византийским ошибкам, представляет собой набор подмножеств серверов, каждая пара которых пересекается во множестве, содержащем достаточное количество корректно работающих серверов, чтобы замаскировать поведение неисправных серверов. Более точно византийские системы кворумов определяются следующим образом:

'''Маскирующая система кворумов''': система кворумов <math>\mathcal{Q}</math> является ''b-маскирующей'', если она имеет упругость <math>f \ge b</math>, и каждая пара кворумов пересекается по крайней мере в <math>2b + 1</math> элементах.

Требования маскирующей системы кворумов позволяют клиенту получить от сервиса правильный ответ, несмотря на до <math>b</math> византийских ошибок сервера. Более точно говоря, операция записи остается прежней; чтобы получить правильное значение <math>x</math> в результате операции чтения, клиент считывает набор пар значение/временная метка из кворума <math>Q</math> и сортирует их на кластеры идентичных пар. Затем он выбирает пару значение/временная метка, которую возвращают по меньшей мере <math>b + 1</math> серверов, а значит, ее должен содержать хотя бы один правильный сервер. Свойства маскирующих систем кворумов гарантируют, что хотя бы один такой кластер существует. Если таких кластеров несколько, клиент выбирает тот, у которого наибольшая временная метка. Легко увидеть, что любое полученное таким образом значение было записано раньше, и более того, что было получено самое последнее записанное значение. Таким образом, получена семантика безопасной мультиридерной мультирайтерной переменной (см. [[Линеаризуемость]]) в византийской среде.

'''Теорема 2. Пусть <math>\mathcal{Q}</math> – b-маскирующая система кворумов. Тогда <math>L(\mathcal{Q}) \ge max \{ \frac{2b + 1}{c(\mathcal{Q})}, \frac{c(\mathcal{Q})}{n} \}</math>, и, следовательно, <math>L(\mathcal{Q}) \ge \sqrt{\frac{2b + 1}{n}}</math>.'''

Устойчивость любой системы кворумов ограничена половиной общего количества серверов. Более того, как уже говорилось выше, существует неотъемлемый компромисс между низкой нагрузкой и высокой устойчивостью, так что фактически невозможно одновременно достичь и того, и другого оптимальным образом. В частности, системы кворумов на n серверах, которые достигают оптимальной нагрузки <math>\frac{1}{\sqrt{n}}</math>, могут выдержать не более <math>\sqrt{n}</math> сбоев.

Чтобы снять эти ограничения, Малхи и др. в работе [8] предлагают ослабить свойство пересечения систем кворумов таким образом, чтобы «кворумы», выбранные в соответствии с определенной стратегией, пересекались только с очень высокой вероятностью. Соответственно, они называют эти системы ''вероятностными системами кворумов''. Такие системы допускают возможность, хотя и небольшую, что две операции будут выполняться в непересекающихся кворумах, и в этом случае согласованность системы может пострадать. Однако даже небольшое ослабление согласованности может привести к значительному повышению устойчивости и снижению вероятности отказа системы, при этом нагрузка остается практически неизменной. Таким образом, вероятностные системы кворумов наиболее подходят для использования в тех случаях, когда доступность операций, несмотря на наличие сбоев, важнее, чем определенная степень согласованности. Это может быть в том случае, если стоимость несогласованных операций высока, но не безвозвратна, или если получение самой свежей информации желательно, но не критично, в то время как отсутствие информации может повлечь за собой более серьезные штрафы.

'''W(n, <math>\ell</math>)''': Пусть <math>U</math> – совокупность размера <math>n</math>. <math>W(n, \ell), \ell \ge 1</math> – система <math> \langle \mathcal{Q}, w \rangle</math>, где <math>\mathcal{Q}</math> – система множеств <math>\mathcal{Q} = \{ Q \subseteq U: |Q| = \ell \sqrt{n} \}</math>; <math>w</math> – стратегия доступа, определяемая следующим образом: <math>\forall Q \in \mathcal{Q}, w(Q) = \frac{1}{|Q|}</math>.

Вероятность выбора в соответствии с <math>w</math> двух непересекающихся кворумов меньше <math>e^{- \ell^2}</math> и может быть сделана достаточно малой при соответствующем выборе <math>\ell</math>. Поскольку каждый элемент находится в <math>\big( \ell \sqrt[n - 1]{n} - 1 \big)</math> кворумах, нагрузка <math>L(W(n, \ell))</math> равна <math>\frac{\ell}{\sqrt{N}} = O \big( \frac{1}{\sqrt{N}} \big)</math>. Поскольку для того, чтобы некоторый кворум был доступен, необходимо иметь в наличии только <math>\ell \sqrt{N}</math> серверов, <math>W(n, \ell)</math> устойчива к <math>n - \ell \sqrt{N}</math> сбоям. Вероятность отказа <math>W(n, \ell)</math> меньше <math>e^{-\Omega{n}}</math> для всех <math>p \le 1 - \frac{\ell}{\sqrt{N}}</math>, что является асимптотически оптимальным. Более того, если <math>\frac{1}{2} \le p \le 1 - \frac{\ell}{\sqrt{N}}</math>, то эта вероятность доказуемо лучше, чем у любой (не вероятностной) системы кворумов.