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

Система большинств имеет нагрузку <math>\lceil \frac{n + 1}{2n} \rceil \approx \frac{1}{2}</math>. Она устойчива к <math>\lfloor \frac{n - 1}{2} \rfloor</math> отказам, а ее вероятность отказа равна <math>e^{- \Omega(n)}</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>, то эта вероятность доказуемо лучше, чем у любой (не вероятностной) системы кворумов.