4817
правок
Кворумы: различия между версиями
Перейти к навигации
Перейти к поиску
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 75: | Строка 75: | ||
'''Нагрузка''': пусть задана стратегия w для системы кворумов Q = | '''Нагрузка''': пусть задана стратегия <math>w</math> для системы кворумов <math>\mathcal{Q} = \{ Q_1, ..., Q_m \}</math> над совокупностью U. Для элемента <math>u \in U</math> нагрузка, порождаемая <math>w</math> на <math>u</math>, равна <math>l_w(u) = \sum_{Q_i \ni u} w(Q_i)</math>. Нагрузка, порождаемая стратегией <math>w</math> на системе кворумов <math>\mathcal{Q}</math>, равна <math>L_w(\mathcal{Q}) = max_{u \in U} \{ l_w(u) \}</math>. | ||
Системная нагрузка (или просто нагрузка) на систему кворумов Q равна | ''Системная нагрузка'' (или просто ''нагрузка'') на систему кворумов <math>\mathcal{Q}</math> равна <math>L(\mathcal{Q}) = min_w \{ L_w(\mathcal{Q}) \}</math>, где минимум берется по всем стратегиям. | ||
где минимум берется по всем стратегиям. | |||
| Строка 88: | Строка 86: | ||
Следующая теорема была доказана в работе [ ] для всех систем кворумов. | Следующая теорема была доказана в работе [ ] для всех систем кворумов. | ||
'''Теорема 1. Пусть Q – система кворумов над совокупностью из n элементов. Обозначим за c(Q) размер наименьшего кворума Q. Тогда L(Q) | '''Теорема 1. Пусть <math>\mathcal{Q}</math> – система кворумов над совокупностью из <math>n</math> элементов. Обозначим за <math>c(\mathcal{Q})</math> размер наименьшего кворума <math>\mathcal{Q}</math>. Тогда <math>L(\mathcal{Q}) \ge max \{ \frac{1}{c(\mathcal{Q})}, \frac{c(\mathcal{Q})}{n} \}</math>. Следовательно, <math>L(\mathcal{Q}) \ge \frac{1}{\sqrt{n}}</math>.''' | ||
Доступность. Устойчивость f системы кворумов представляет собой меру того, сколько аварийных отказов система гарантированно переживет. | '''Доступность'''. Устойчивость <math>f</math> системы кворумов представляет собой меру того, сколько аварийных отказов система ''гарантированно'' переживет. | ||
'''Устойчивость''': устойчивость f системы кворумов Q – это наибольшее k, такое, что для каждого множества K | '''Устойчивость''': ''устойчивость'' <math>f</math> системы кворумов <math>\mathcal{Q}</math> – это наибольшее <math>k</math>, такое, что для каждого множества <math>K \subseteq U, |K| = k</math>, существует <math>Q \in \mathcal{Q}</math>, такое, что <math>K \cap Q = \empty</math>. | ||
Заметим, что устойчивость f составляет не более c(Q) - 1, так как при отключении членов наименьшего кворума все кворумы будут поражены. Однако возможно, что f-устойчивая система кворумов, несмотря на уязвимость к нескольким конфигурациям f + 1 отказов, может пережить множество конфигураций более чем f отказов. Один из способов измерить это свойство системы кворумов – это предположить, что каждый сервер выходит из строя независимо с вероятностью p, а затем определить вероятность | Заметим, что устойчивость <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> того, что ни один кворум не останется полностью живым. Она называется ''вероятностью отказа'' и формально определяется следующим образом: | ||
'''Вероятность отказа''': предположим, что каждый сервер в системе претерпевает сбой независимо с вероятностью p. Для каждого кворума Q | '''Вероятность отказа''': предположим, что каждый сервер в системе претерпевает сбой независимо с вероятностью <math>p</math>. Для каждого кворума <math>Q \in \mathcal{Q}</math> обозначим за <math>\mathcal{E}_{\mathcal{Q}}</math> событие, когда <math>Q</math> ''поврежден'', т. е. по крайней мере один элемент <math>i \in Q</math> претерпел сбой. Пусть <math>crash(\mathcal{Q})</math> – событие, когда все кворумы <math>Q \in \mathcal{Q}</math> были повреждены, т. е. crash(Q) = VQ2 QEQ. Тогда вероятность отказа системы равна Fp(Q) = Pr(crash(Q)). | ||