Кворумы
Ключевые слова и синонимы Системы кворумов (Quorum systems); системы голосования (Voting systems); комитеты (Coteries)
Постановка задачи
Системы кворумов представляют собой инструменты повышения доступности и эффективности тиражируемых сервисов. Системой кворумов для совокупности серверов является набор подмножеств серверов, каждая пара которых имеет пересечение. Интуитивно понятно, что каждый кворум может работать от имени системы, тем самым повышая ее доступность и производительность, а свойство пересечения гарантирует, что операции, выполняемые на разных кворумах, сохраняют согласованность.
Мотивация создания систем кворумов обусловлена необходимостью обеспечить надежность выполнения машинами критически важных задач. Единственным способом повышения надежности сервиса, помимо использования более надежного оборудования, является тиражирование, или репликация. Чтобы сделать сервис надежным, его можно установить на несколько одинаковых серверов, каждый из которых хранит копию состояния сервиса и выполняет на нем операции чтения/записи. Это позволяет системе предоставлять информацию и выполнять операции даже в том случае, если некоторые машины выйдут из строя или оборвутся каналы связи. К сожалению, репликация влечет расходы, связанные с необходимостью поддерживать согласованность серверов. Чтобы повысить доступность и производительность тиражируемого сервиса, Гиффорд и Томас [3, 14] в 1979 году ввели использование голосов, назначаемых каждому серверу, так, чтобы для выполнения операций было достаточно большинства от суммы голосов. В более общем виде системы кворумов формально определяются следующим образом.
Система кворумов: предположим, что существует совокупность [math]\displaystyle{ U }[/math] серверов, [math]\displaystyle{ |U| = n }[/math], и произвольное число клиентов. Системой кворумов [math]\displaystyle{ \mathcal{Q} \subseteq 2^U }[/math] является множество подмножеств [math]\displaystyle{ U }[/math], каждая пара которых имеет пересечение. Каждое [math]\displaystyle{ Q \in \mathcal{Q} }[/math] называется кворумом.
Протокол доступа
Чтобы продемонстрировать удобство использования систем кворумов при построении тиражируемых сервисов, покажем, как кворумы используются для реализации совместно используемой мультирайтерной и мультиридерной атомарной переменной. Кворумы также используются в различных протоколах взаимного исключения, для достижения консенсуса и в протоколах фиксации.
В данном приложении клиенты выполняют операции чтения и записи над переменной [math]\displaystyle{ x }[/math], которая реплицируется на каждом сервере в совокупности [math]\displaystyle{ U }[/math]. Копия переменной [math]\displaystyle{ x }[/math] хранится на каждом сервере вместе со значением временной метки [math]\displaystyle{ t }[/math]. Временные метки назначаются клиентом каждой реплике переменной, когда клиент записывает реплику. Разные клиенты выбирают разные временные метки, например, целые числа, дополненные именем [math]\displaystyle{ c }[/math] в младших разрядах. Операции чтения и записи реализованы следующим образом.
Запись: чтобы клиент [math]\displaystyle{ c }[/math] записал значение [math]\displaystyle{ v }[/math], он запрашивает каждый сервер в некотором кворуме [math]\displaystyle{ Q }[/math], чтобы получить набор пар значение/временная метка [math]\displaystyle{ A = \{ \langle v_u, t_u \rangle \}_{u \in Q} }[/math]; выбирает временную метку [math]\displaystyle{ t \in T_c }[/math], большую, чем наибольшее значение временной метки в [math]\displaystyle{ A }[/math]; обновляет [math]\displaystyle{ x }[/math] и соответствующую временную метку на каждом сервере в [math]\displaystyle{ Q }[/math] до [math]\displaystyle{ v }[/math] и [math]\displaystyle{ t }[/math], соответственно.
Чтение: чтобы клиент прочитал [math]\displaystyle{ x }[/math], он запрашивает каждый сервер в некотором кворуме [math]\displaystyle{ Q }[/math], чтобы получить набор пар значение/временная метка [math]\displaystyle{ A = \{ \langle v_u, t_u \rangle \}_{u \in Q} }[/math]. Затем клиент выбирает пару [math]\displaystyle{ \langle v, t \rangle }[/math] с наибольшей временной меткой в [math]\displaystyle{ A }[/math], чтобы получить результат операции чтения. После этого он записывает [math]\displaystyle{ \langle v, t \rangle }[/math] на каждый сервер в некотором кворуме [math]\displaystyle{ Q' }[/math].
И при операциях чтения, и при операциях записи каждый сервер обновляет свою локальную переменную и временную метку до полученных значений [math]\displaystyle{ \langle v, t \rangle }[/math] только в случае, если [math]\displaystyle{ t }[/math] больше, чем временная метка, связанная с переменной в данный момент. Приведенный выше протокол корректно реализует семантику мультиридерной мультирайтерной атомарной переменной (см. Линеаризуемость).
Основные результаты
Пожалуй, двумя самыми очевидными системами кворумов являются синглтон и множество большинств или, в более общем случае, взвешенных большинств, предложенных Гиффордом [3].
Синглтон: система множеств [math]\displaystyle{ \mathcal{Q} = \{ \{ u \} \} }[/math] для некоторого [math]\displaystyle{ u \in U }[/math] является синглтонной системой кворума.
Взвешенное большинство: предположим, что каждому серверу [math]\displaystyle{ s }[/math] в совокупности [math]\displaystyle{ U }[/math] присвоено количество голосов [math]\displaystyle{ w_s }[/math]. Тогда система множеств [math]\displaystyle{ \mathcal{Q} = \{ Q \subseteq U: \sum_{q \in Q} w_q \gt \big( \sum_{q \in U} w_q \big) / 2 \} }[/math] является системой кворумов, называемой взвешенным большинством. Когда все веса одинаковы, такую систему называют просто системой большинств.
Примером системы кворумов, которая не может быть определена голосованием, является следующая конструкция решетки:
Решетка: предположим, что совокупность серверов имеет размер [math]\displaystyle{ n = k^2 }[/math] для некоторого целого числа [math]\displaystyle{ k }[/math]. Разложим совокупность в решетку [math]\displaystyle{ \sqrt{n} \times \sqrt{n} }[/math], как показано на рис. 1. Кворум представляет собой объединение полного ряда и одного элемента из каждого ряда ниже полного ряда. Таким образом, получается система кворумов типа «решетка», размер кворумов которой составляет [math]\displaystyle{ O(\sqrt{n}) }[/math].
Рисунок 1. Система кворумов типа «решетка» размером 6 x 6, один кворум заштрихован
Маэкава в работе [6] предлагает систему кворумов, обладающую несколькими желательными свойствами симметрии, в частности тем, что каждая пара кворумов пересекается ровно в одном элементе:
FPP (мажоритарная избирательная система): Предположим, что совокупность серверов имеет размер [math]\displaystyle{ n = q^2 + q + 1 }[/math], где [math]\displaystyle{ q = p^r }[/math] для простого [math]\displaystyle{ p }[/math]. Известно, что для [math]\displaystyle{ n }[/math] существует конечная проективная плоскость с [math]\displaystyle{ q + 1 }[/math] попарно пересекающимися подмножествами, каждое подмножество имеет размер [math]\displaystyle{ q + 1 }[/math], где каждый элемент содержится в [math]\displaystyle{ q + 1 }[/math] подмножествах. Тогда множество подмножеств конечной проективной плоскости образует систему кворумов.
Голосование и связанные с ним понятия
Поскольку в общем случае было бы бессмысленно обращаться к большому кворуму, если его подмножество является кворумом, хорошее определение поможет избежать таких аномалий. Гарсия-Молина и Барбара [2] называют такие хорошо оформленные системы комитетами (coteries), определяя их следующим образом:
Комитет: комитет [math]\displaystyle{ \mathcal{Q} \subseteq 2^U }[/math] является системой кворумов, такой, что для любых [math]\displaystyle{ Q, Q' \in \mathcal{Q} }[/math] верно [math]\displaystyle{ Q \nsubseteq Q' }[/math].
Особый интерес представляют системы кворумов, которые не могут быть уменьшены в размерах (т. е. ни один кворум в системе не может быть уменьшен в размерах). Гарсия-Молина и Барбара [2] используют термин «доминирует» для обозначения того, что одна система кворума всегда превосходит другую, следующим образом:
Доминирование: предположим, что [math]\displaystyle{ \mathcal{Q}, \mathcal{Q'} }[/math] – два комитета, [math]\displaystyle{ \mathcal{Q} \ne \mathcal{Q'} }[/math], такие, что для каждого [math]\displaystyle{ Q' \in \mathcal{Q'} }[/math] существует [math]\displaystyle{ Q \in \mathcal{Q} }[/math], такое, что [math]\displaystyle{ Q \subseteq Q' }[/math]. Тогда [math]\displaystyle{ \mathcal{Q} }[/math] доминирует над [math]\displaystyle{ \mathcal{Q'} }[/math]. [math]\displaystyle{ \mathcal{Q'} }[/math] является доминируемым, если существует комитет [math]\displaystyle{ \mathcal{Q} }[/math], который доминирует над ним, и не является доминируемым, если такого комитета не существует.
Голосование было упомянуто выше как интуитивный способ осмысления техники кворумов. Оказывается, назначения голосов и кворумы не эквивалентны. Гарсия-Молина и Барбара [2] показали, что системы кворумов являются строго более общими, чем голосования, то есть каждое назначение голосов имеет некоторую соответствующую систему кворумов, но не наоборот. На самом деле, для системы с [math]\displaystyle{ n }[/math] серверами существует дважды экспоненциальное [math]\displaystyle{ (2^{2^{cn}}) }[/math] число недоминируемых комитетов и только [math]\displaystyle{ O(2^{n^2}) }[/math] различных назначений голосов, хотя для [math]\displaystyle{ n \le 5 }[/math] голосование и недоминируемые комитеты идентичны.
Меры
Для решения вопроса о том, какая система кворумов лучше всего подходит для заданного набора серверов, было определено несколько мер качества; здесь подробно рассматриваются такие меры, как нагрузка и доступность.
Нагрузка. Мерой производительности, присущей системе кворумов, является ее нагрузка. Наор и Вул в работе [10] определяют нагрузку системы кворумов как вероятность доступа к самому загруженному серверу в наилучшем случае. Более точно, при наличии системы кворумов [math]\displaystyle{ \mathcal{Q} }[/math] стратегия доступа [math]\displaystyle{ w }[/math] представляет собой распределение вероятностей на элементах [math]\displaystyle{ \mathcal{Q} }[/math]; т. е. [math]\displaystyle{ \sum_{Q \in \mathcal{Q}} w(Q) = 1 }[/math]. [math]\displaystyle{ w(Q) }[/math] – это вероятность того, что при обращении к сервису будет выбран кворум [math]\displaystyle{ Q }[/math]. Нагрузка определяется следующим образом.
Нагрузка: пусть задана стратегия [math]\displaystyle{ w }[/math] для системы кворумов [math]\displaystyle{ \mathcal{Q} = \{ Q_1, ..., Q_m \} }[/math] над совокупностью U. Для элемента [math]\displaystyle{ u \in U }[/math] нагрузка, порождаемая [math]\displaystyle{ w }[/math] на [math]\displaystyle{ u }[/math], равна [math]\displaystyle{ l_w(u) = \sum_{Q_i \ni u} w(Q_i) }[/math]. Нагрузка, порождаемая стратегией [math]\displaystyle{ w }[/math] на системе кворумов [math]\displaystyle{ \mathcal{Q} }[/math], равна [math]\displaystyle{ L_w(\mathcal{Q}) = max_{u \in U} \{ l_w(u) \} }[/math].
Системная нагрузка (или просто нагрузка) на систему кворумов [math]\displaystyle{ \mathcal{Q} }[/math] равна [math]\displaystyle{ L(\mathcal{Q}) = min_w \{ L_w(\mathcal{Q}) \} }[/math], где минимум берется по всем стратегиям.
Нагрузка является определением наилучшего случая и будет достигнута только при использовании оптимальной стратегии доступа и только в случае отсутствия сбоев. Сильной стороной этого определения является то, что нагрузка – это свойство самой системы кворумов, а не использующего ее протокола.
Следующая теорема была доказана в работе [10] для всех систем кворумов.
Теорема 1. Пусть [math]\displaystyle{ \mathcal{Q} }[/math] – система кворумов над совокупностью из [math]\displaystyle{ n }[/math] элементов. Обозначим за [math]\displaystyle{ c(\mathcal{Q}) }[/math] размер наименьшего кворума [math]\displaystyle{ \mathcal{Q} }[/math]. Тогда [math]\displaystyle{ L(\mathcal{Q}) \ge max \{ \frac{1}{c(\mathcal{Q})}, \frac{c(\mathcal{Q})}{n} \} }[/math]. Следовательно, [math]\displaystyle{ L(\mathcal{Q}) \ge \frac{1}{\sqrt{n}} }[/math].
Доступность. Устойчивость [math]\displaystyle{ f }[/math] системы кворумов представляет собой меру того, сколько аварийных отказов система гарантированно переживет.
Устойчивость: устойчивость [math]\displaystyle{ f }[/math] системы кворумов [math]\displaystyle{ \mathcal{Q} }[/math] – это наибольшее [math]\displaystyle{ k }[/math], такое, что для каждого множества [math]\displaystyle{ K \subseteq U, |K| = k }[/math], существует [math]\displaystyle{ Q \in \mathcal{Q} }[/math], такое, что [math]\displaystyle{ K \cap Q = \empty }[/math].
Заметим, что устойчивость [math]\displaystyle{ f }[/math] составляет не более [math]\displaystyle{ c(\mathcal{Q}) - 1 }[/math], так как при отключении членов наименьшего кворума все кворумы будут повреждены. Однако возможно, что [math]\displaystyle{ f }[/math]-устойчивая система кворумов, несмотря на уязвимость к нескольким конфигурациям [math]\displaystyle{ f + 1 }[/math] отказов, может пережить множество конфигураций более чем [math]\displaystyle{ f }[/math] отказов. Один из способов измерить это свойство системы кворумов – это предположить, что каждый сервер выходит из строя независимо с вероятностью [math]\displaystyle{ p }[/math], а затем определить вероятность [math]\displaystyle{ F_p }[/math] того, что ни один кворум не останется полностью живым. Она называется вероятностью отказа и формально определяется следующим образом:
Вероятность отказа: предположим, что каждый сервер в системе претерпевает сбой независимо с вероятностью [math]\displaystyle{ p }[/math]. Для каждого кворума [math]\displaystyle{ Q \in \mathcal{Q} }[/math] обозначим за [math]\displaystyle{ \mathcal{E}_{\mathcal{Q}} }[/math] событие, когда [math]\displaystyle{ Q }[/math] поврежден, т. е. по крайней мере один элемент [math]\displaystyle{ i \in Q }[/math] претерпел сбой. Пусть [math]\displaystyle{ crash(\mathcal{Q}) }[/math] – событие, когда все кворумы [math]\displaystyle{ Q \in \mathcal{Q} }[/math] были повреждены, т. е. [math]\displaystyle{ crash(\mathcal{Q}) = \bigwedge_{Q \in \mathcal{Q}} \mathcal{E}_{\mathcal{Q}} }[/math]. Тогда вероятность отказа системы равна [math]\displaystyle{ F_p(\mathcal{Q}) = Pr(crash(\mathcal{Q})) }[/math].
Пелег и Вул изучили доступность систем кворумов в работе [11]. Хорошая вероятность отказа [math]\displaystyle{ F_p(\mathcal{Q}) }[/math] для системы кворумов [math]\displaystyle{ \mathcal{Q} }[/math] имеет пределом [math]\displaystyle{ lim_{n \to \infty} F_p(\mathcal{Q}) = 0 }[/math], когда [math]\displaystyle{ p \lt 1/2 }[/math]. Заметим, что вероятность отказа любой системы кворумов, чья отказоустойчивость равна [math]\displaystyle{ f }[/math], не ниже [math]\displaystyle{ e^{- \Omega(f)} }[/math]. Большинство имеет наилучшую доступность, когда [math]\displaystyle{ p \lt 1/2 }[/math]; для [math]\displaystyle{ p = 1/2 }[/math] существуют кворумные построения с [math]\displaystyle{ F_p(\mathcal{Q}) = 1/2 }[/math]; для [math]\displaystyle{ p \gt 1/2 }[/math] синглтон имеет наилучшую вероятность отказа [math]\displaystyle{ F_p(\mathcal{Q}) = p }[/math], но для большинства систем кворумов [math]\displaystyle{ F_p(\mathcal{Q}) }[/math] стремится к 1.
Нагрузка и доступность систем кворумов
Кворумные построения можно сравнивать, анализируя их поведение в соответствии с приведенными выше мерами. Синглтон имеет нагрузку 1, устойчивость 0 и вероятность отказа [math]\displaystyle{ F_p = p }[/math]. Эта система имеет наилучшую вероятность отказа, когда [math]\displaystyle{ p \gt 1/2 }[/math], но в остальном демонстрирует низкие показатели как по доступности, так и по нагрузке.
Система большинств имеет нагрузку [math]\displaystyle{ \lceil \frac{n + 1}{2n} \rceil \approx \frac{1}{2} }[/math]. Она устойчива к [math]\displaystyle{ \lfloor \frac{n - 1}{2} \rfloor }[/math] отказам, а ее вероятность отказа равна [math]\displaystyle{ e^{- \Omega(n)} }[/math]. Эта система имеет максимально возможную устойчивость и асимптотически оптимальную вероятность отказа, но низкую нагрузку.
Нагрузка решетки равна [math]\displaystyle{ O(\frac{1}{\sqrt{n}}) }[/math], отличаясь от оптимальной не более чем на постоянный коэффициент. Однако ее устойчивость составляет только [math]\displaystyle{ \sqrt{n} - 1 }[/math], и она имеет высокую вероятность отказа, которая стремится к 1 по мере роста [math]\displaystyle{ n }[/math].
Устойчивость системы кворумов FPP равна [math]\displaystyle{ q \approx \sqrt{n} }[/math]. Нагрузка FPP была проанализирована в [10], где было показано, что [math]\displaystyle{ L(FPP) = \frac{q + 1}{n} \approx \frac{1}{\sqrt{n}} }[/math], что является оптимальным. Однако с ростом [math]\displaystyle{ n }[/math] вероятность отказа стремится к 1.
Как показали эти системы, существует компромисс между нагрузкой и отказоустойчивостью в системах кворумов, где устойчивость [math]\displaystyle{ f }[/math] системы кворумов [math]\displaystyle{ \mathcal{Q} }[/math] удовлетворяет соотношению [math]\displaystyle{ f \le nL(\mathcal{Q}) }[/math]. Таким образом, улучшение одного из них должно происходить за счет другого, и фактически невозможно одновременно достичь оптимального результата по обоим показателям. Можно сделать вывод, что высокая нагрузка конфликтует с низкой вероятностью отказа, но это не обязательно так. На самом деле существуют системы кворумов, такие как система путей (Paths) Наора и Вула [10] и треугольная решетка Баззи [1], которые достигают асимптотически оптимальной нагрузки [math]\displaystyle{ O(1/\sqrt{n}) }[/math] и имеют близкую к оптимальной вероятность отказа для своих размеров кворумов. Другое построение – система CWlog Пелега и Вула [12], которая имеет необычно малый размер кворума log n – log log n, и для систем с кворумами такого размера имеет оптимальную нагрузку, [math]\displaystyle{ L(CWlog) = O(1/log n) }[/math], и оптимальную вероятность отказа.
Византийские системы кворумов
По большей части системы кворумов изучались в средах, где сбои могут просто приводить к недоступности серверов (доброкачественные сбои). Но что, если сервер может проявить произвольное, возможно, злонамеренное поведение? Малхи и Райтер [7] провели исследование систем кворумов в средах, склонных к произвольному (византийскому) поведению серверов. Интуитивно, система кворумов, устойчивая к византийским ошибкам, представляет собой набор подмножеств серверов, каждая пара которых пересекается по множеству, содержащему достаточное количество исправных серверов, чтобы замаскировать поведение неисправных серверов. Более точно византийские системы кворумов определяются следующим образом:
Маскирующая система кворумов: система кворумов [math]\displaystyle{ \mathcal{Q} }[/math] является b-маскирующей, если она имеет устойчивость [math]\displaystyle{ f \ge b }[/math], и каждая пара кворумов пересекается по крайней мере в [math]\displaystyle{ 2b + 1 }[/math] элементах.
Требования маскирующей системы кворумов позволяют клиенту получить от сервиса правильный ответ, несмотря на до [math]\displaystyle{ b }[/math] византийских ошибок сервера. Более точно говоря, операция записи остается прежней; чтобы получить правильное значение [math]\displaystyle{ x }[/math] в результате операции чтения, клиент считывает набор пар значение/временная метка из кворума [math]\displaystyle{ Q }[/math] и сортирует их на кластеры идентичных пар. Затем он выбирает пару значение/временная метка, которую возвращают по меньшей мере [math]\displaystyle{ b + 1 }[/math] серверов, а значит, ее должен содержать хотя бы один правильный сервер. Свойства маскирующих систем кворумов гарантируют, что хотя бы один такой кластер существует. Если таких кластеров несколько, клиент выбирает тот, у которого наибольшая временная метка. Легко увидеть, что любое полученное таким образом значение было записано ранее, и более того, что было получено самое последнее записанное значение. Таким образом, получена семантика безопасной мультиридерной мультирайтерной переменной (см. Линеаризуемость) в византийской среде.
Для b-маскирующей системы кворумов справедлива следующая нижняя граница нагрузки:
Теорема 2. Пусть [math]\displaystyle{ \mathcal{Q} }[/math] – b-маскирующая система кворумов. Тогда [math]\displaystyle{ L(\mathcal{Q}) \ge max \{ \frac{2b + 1}{c(\mathcal{Q})}, \frac{c(\mathcal{Q})}{n} \} }[/math] и, следовательно, [math]\displaystyle{ L(\mathcal{Q}) \ge \sqrt{\frac{2b + 1}{n}} }[/math].
Это строгая граница, и были представлены удовлетворяющие ей построения маскирующих систем кворумов.
В работе [7] Малхи и Райтер исследуют две вариации маскирующих систем кворумов. Первая, называемая диссеминирующими системами кворумов, подходит для сервисов, которые получают и распространяют самопроверяемую информацию от корректных клиентов (например, значения с цифровой подписью), которую неисправные серверы, возможно, не могут перераспределить, но не могут необнаружимым образом изменить. Вторая разновидность, называемая непрозрачными маскирующими системами кворумов, похожа на обычные маскирующие кворумы тем, что не предполагает самопроверки данных, и отличается от них тем, что клиентам не требуется знать сценарии отказов, для которых был разработан сервис. Это несколько упрощает клиентский протокол и в случае, если сбои вызваны злоумышленным поведением, раскрывает клиентам меньше информации, которая могла бы послужить руководством для атаки, пытающейся скомпрометировать систему. В [7] также показано, как справиться не только с неисправными серверами, но и с неисправными клиентами.
Вероятностные системы кворумов
Устойчивость любой системы кворумов ограничена половиной общего количества серверов. Более того, как уже говорилось выше, существует неотъемлемый компромисс между низкой нагрузкой и высокой устойчивостью, так что фактически невозможно одновременно достичь и того, и другого оптимальным образом. В частности, системы кворумов на [math]\displaystyle{ n }[/math] серверах, которые достигают оптимальной нагрузки [math]\displaystyle{ \frac{1}{\sqrt{n}} }[/math], могут выдержать не более [math]\displaystyle{ \sqrt{n} }[/math] сбоев.
Чтобы снять эти ограничения, Малхи и др. в работе [8] предлагают ослабить свойство пересечения систем кворумов таким образом, чтобы «кворумы», выбранные в соответствии с определенной стратегией, пересекались только с очень высокой вероятностью. Соответственно, они называют эти системы вероятностными системами кворумов. Такие системы допускают возможность, хотя и небольшую, что две операции будут выполняться в непересекающихся кворумах, и в этом случае согласованность системы может пострадать. Однако даже небольшое ослабление согласованности может привести к значительному повышению устойчивости и снижению вероятности отказа системы, при этом нагрузка остается практически неизменной. Таким образом, вероятностные системы кворумов наиболее подходят для использования в тех случаях, когда доступность операций, несмотря на наличие сбоев, важнее, чем определенная степень согласованности. Примером может быть случай, когда стоимость несогласованных операций высока, но не безвозвратна, или когда получение самой свежей информации желательно, но не критично, в то время как отсутствие информации может повлечь за собой более серьезные штрафы.
Семейство построений, предложенных в [8], выглядит следующим образом:
W(n, [math]\displaystyle{ \ell }[/math]): Пусть [math]\displaystyle{ U }[/math] – совокупность размера [math]\displaystyle{ n }[/math]. [math]\displaystyle{ W(n, \ell), \ell \ge 1 }[/math] – система [math]\displaystyle{ \langle \mathcal{Q}, w \rangle }[/math], где [math]\displaystyle{ \mathcal{Q} }[/math] – система множеств [math]\displaystyle{ \mathcal{Q} = \{ Q \subseteq U: |Q| = \ell \sqrt{n} \} }[/math], а [math]\displaystyle{ w }[/math] – стратегия доступа, определяемая следующим образом: [math]\displaystyle{ \forall Q \in \mathcal{Q}, w(Q) = \frac{1}{|Q|} }[/math].
Вероятность выбора в соответствии с [math]\displaystyle{ w }[/math] двух непересекающихся кворумов меньше [math]\displaystyle{ e^{- \ell^2} }[/math] и может быть сделана достаточно малой при соответствующем выборе [math]\displaystyle{ \ell }[/math]. Поскольку каждый элемент находится в [math]\displaystyle{ \big( \ell \sqrt[n - 1]{n} - 1 \big) }[/math] кворумах, нагрузка [math]\displaystyle{ L(W(n, \ell)) }[/math] равна [math]\displaystyle{ \frac{\ell}{\sqrt{n}} = O \big( \frac{1}{\sqrt{n}} \big) }[/math]. Поскольку для того, чтобы некоторый кворум был доступен, необходимо иметь в наличии только [math]\displaystyle{ \ell \sqrt{n} }[/math] серверов, [math]\displaystyle{ W(n, \ell) }[/math] устойчива к [math]\displaystyle{ n - \ell \sqrt{n} }[/math] сбоям. Вероятность отказа [math]\displaystyle{ W(n, \ell) }[/math] меньше [math]\displaystyle{ e^{-\Omega(n)} }[/math] для всех [math]\displaystyle{ p \le 1 - \frac{\ell}{\sqrt{n}} }[/math], что является асимптотически оптимальным. Более того, если [math]\displaystyle{ \frac{1}{2} \le p \le 1 - \frac{\ell}{\sqrt{N}} }[/math], то эта вероятность доказуемо лучше, чем у любой (не вероятностной) системы кворумов.
Ослабление согласованности также может дать значительные улучшения в средах, в которых возможны византийские ошибки. Более детальное изложение можно найти в работе [8].
Применение
Практически любой отказоустойчивый распределенный протокол, такой как Paxos [5] или консенсус [1], неявно опирается на кворумы, как правило, в форме большинств. Были построены масштабируемые хранилища данных, такие как Fleet [9], Rambo [4] и Rosebud [13].
См. также
Литература
1. Dwork, C., Lynch, N., Stockmeyer, L.: Consensus in the presence of partial synchrony. J. Assoc. Comput. Mach. 35,288-323 (1988)
2. Garcia-Molina, H., Barbara, D.: How to assign votes in a distributed system. J. ACM 32,841-860 (1985)
3. Gifford, D.K.: Weighted voting for replicated data. In: Proceedings of the 7th ACM Symposium on Operating Systems Principles, 1979, pp. 150-162
4. Gilbert, S.: Lynch, N., Shvartsman, A., Rambo ii: Rapidly reconfigurable atomic memory for dynamic networks. pp. 259-268. In: Proceedings if the IEEE 2003 International Conference on Dependable Systems and Networks (DNS). San Francisco, USA (2003)
5. Lamport, L.: The part-time parliament. ACM Trans. Comput. Syst. 16,133-169(1998)
6. Maekawa, M.: A pn algorithm for mutual exclusion in decentralized systems. ACM Trans. Comput. Syst. 3(2), 145-159 (1985)
7. Malkhi, D., Reiter, M.: Byzantine quorum systems. Distrib. Comput. 11, 203-213 (1998)
8. Malkhi, D., Reiter, M., Wool, A., Wright, R.: Probabilistic quorum systems. Inf. Com put. J. 170,184-206 (2001)
9. Malkhi, D., Reiter, M.K.: An architecture for survivable coordination in large-scale systems. IEEE Trans. Knowl. Data Engineer. 12,187-202(2000)
10. Naor, M., Wool, A.: The load, capacity and availability of quorum systems. SIAM J. Comput. 27,423^47 (1998)
11. Peleg, D., Wool, A.: The availability of quorum systems. Inf. Comput. 123, 210-223 (1995)
12. Peleg, D., Wool, A.: Crumbling walls: A class of practical and efficient quorum systems. Distrib. Comput. 10,87-98 (1997)
13. Rodrigues, R., Liskov, B.: Rosebud: A scalable byzantine-fault tolerant storage architecture. In: Proceedings of the 18th ACM Symposium on Operating System Principles, San Francisco, USA (2003)
14. Thomas, R.H.: A majority consensus approach to concurrency control for multiple copy databases. ACM Trans. Database Syst. 4,180-209(1979)