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

Кворумные построения можно сравнивать, проанализировав их поведение в соответствии с приведенными выше показателями. Синглтон имеет нагрузку 1, устойчивость 0 и вероятность отказа Fp = p. Эта система имеет наилучшую вероятность отказа, когда p > j, но в остальном демонстрирует низкие показатели как по доступности, так и по нагрузке.

Система большинств имеет нагрузку dn2+1 ^ j. Она устойчива к |_-^=-1c отказам, а ее вероятность отказа равна e-£2(n)^ Эта система имеет максимально возможную устойчивость и асимптотически оптимальную вероятность отказа, но плохую нагрузку.

Нагрузка решетки равна O(p1), отличаясь от оптимальной не более чем на постоянный коэффициент V". Однако ее устойчивость составляет только pn - 1, и она имеет плохую вероятность отказа, которая стремится к 1 по мере роста n. Устойчивость системы кворумов FPP равна q & pn. Нагрузка FPP была проанализирована в [ ], где было показано, что L(FPP) = q+1 fa 1/ pn, что является оптимальным. Однако с ростом n вероятность отказа стремится к 1.

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

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

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

'''Теорема 2. Пусть Q – b-маскирующая система кворумов.   Тогда L(Q) > max{|fey, ^p}, и, следовательно, UQ) > у/Щ±.'''

В работе [ ] Малхи и Райтер исследуют две вариации маскирующих систем кворумов. Первая, называемая системами кворума распространения, подходит для сервисов, которые получают и распределяют самопроверяющуюся информацию от корректных клиентов (например, значения с цифровой подписью), которую неисправные серверы, возможно, не могут перераспределить, но не могут необнаружимым образом изменить. Вторая разновидность, называемая непрозрачными маскирующими кворумами, похожа на обычные маскирующие кворумы тем, что не предполагает самопроверки данных, и отличается от них тем, что клиентам не требуется знать сценарии отказов, для которых был разработан сервис. Это несколько упрощает клиентский протокол и в случае, если сбои вызваны злоумышленным поведением, раскрывает клиентам меньше информации, которая могла бы послужить руководством для атаки, пытающейся скомпрометировать систему. В [ ] также показано, как справиться не только с неисправными серверами, но и с неисправными клиентами.

Устойчивость любой системы кворумов ограничена половиной общего количества серверов. Более того, как уже говорилось выше, существует неотъемлемый компромисс между низкой нагрузкой и высокой устойчивостью, так что фактически невозможно одновременно достичь и того, и другого оптимальным образом. В частности, системы кворумов на n серверах, которые достигают оптимальной нагрузки p1, могут выдержать не более pn сбоев.

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

W(n,l) Пусть U – совокупность размера n. W(n,l), I > 1, – система hQ; wi, где Q – система множеств <Э = fQ С U: |Q| = l-s/n}; w – стратегия доступа w, определяемая 8Q 2 Q;w(Q) = I^I.