4817
правок
Кворумы: различия между версиями
Перейти к навигации
Перейти к поиску
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 42: | Строка 42: | ||
Рисунок 1. Система кворумов типа «решетка» размером 6 x 6, один кворум заштрихован | Рисунок 1. Система кворумов типа «решетка» размером 6 x 6, один кворум заштрихован | ||
Маэкава в работе [6] предлагает систему кворумов, обладающую несколькими желательными свойствами симметрии, в частности тем, что каждая пара кворумов пересекается ровно в одном элементе: | Маэкава в работе [6] предлагает систему кворумов, обладающую несколькими желательными свойствами симметрии, в частности тем, что каждая пара кворумов пересекается ровно в одном элементе: | ||
'''FPP''' (мажоритарная избирательная система): Предположим, что совокупность серверов имеет размер n = | '''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] называют такие хорошо оформленные системы комитетами (coteries), определяя их следующим образом: | Поскольку в общем случае было бы бессмысленно обращаться к большому кворуму, если его подмножество является кворумом, хорошее определение поможет избежать таких аномалий. Гарсия-Молина и Барбара [2] называют такие хорошо оформленные системы ''комитетами'' (coteries), определяя их следующим образом: | ||
'''Комитет''': комитет Q | '''Комитет''': комитет <math>\mathcal{Q} \subseteq 2^U</math> является системой кворумов, такой, что для любых <math>Q, Q' \in \mathcal{Q}</math> верно <math>Q \nsubseteq Q'</math>. | ||
| Строка 60: | Строка 61: | ||
'''Доминирование''': предположим, что Q, | '''Доминирование''': предположим, что <math>\mathcal{Q}, \mathcal{Q'}</math> – два комитета, <math>\mathcal{Q} \ne \mathcal{Q'}</math>, такие, что для каждого <math>Q' \in \mathcal{Q'}</math> существует <math>Q \in \mathcal{Q}</math>, такое, что <math>Q \subseteq Q'</math>. Тогда <math>\mathcal{Q}</math> ''доминирует'' над <math>\mathcal{Q'}</math>. <math>\mathcal{Q'}</math> ''является доминируемым'', если существует комитет <math>\mathcal{Q}</math>, который доминирует над ним, и ''не является доминируемым'', если такого комитета не существует. | ||
Голосование было упомянуто выше как интуитивный способ осмысления техники кворумов. Оказывается, назначения голосов и кворумы не эквивалентны. Гарсия-Молина и Барбара [ ] | Голосование было упомянуто выше как интуитивный способ осмысления техники кворумов. Оказывается, назначения голосов и кворумы не эквивалентны. Гарсия-Молина и Барбара [2] показали, что системы кворумов являются строго более общими, чем голосования, то есть каждое назначение голосов имеет некоторую соответствующую систему кворумов, но не наоборот. На самом деле, для системы с <math>n</math> серверами существует двойное экспоненциальное <math>(2^{2^{cn}})</math> число недоминируемых комитетов и только <math>O(2^{n^2})</math> различных назначений голосов, хотя для <math>n \le 5</math> голосование и недоминируемые комитеты идентичны. | ||
'''Меры''' | '''Меры''' | ||
Для решения вопроса о том, какая система кворумов лучше всего подходит для заданного набора серверов, было определено несколько мер качества; здесь подробно рассматриваются такие меры, как нагрузка и доступность. | Для решения вопроса о том, какая система кворумов лучше всего подходит для заданного набора серверов, было определено несколько мер качества; здесь подробно рассматриваются такие меры, как ''нагрузка'' и ''доступность''. | ||
Нагрузка. Мерой производительности, присущей системе кворумов, является ее нагрузка. Наор и Вул в работе [10] определяют нагрузку системы кворумов как вероятность доступа к самому загруженному серверу в наилучшем случае. Более точно, при наличии системы кворумов Q стратегия доступа w представляет собой распределение вероятностей на элементах Q; т. е. | '''Нагрузка'''. Мерой производительности, присущей системе кворумов, является ее ''нагрузка''. Наор и Вул в работе [10] определяют нагрузку системы кворумов как вероятность доступа к самому загруженному серверу в ''наилучшем'' случае. Более точно, при наличии системы кворумов <math>\mathcal{Q}</math> ''стратегия доступа'' <math>w</math> представляет собой распределение вероятностей на элементах <math>\mathcal{Q}</math>; т. е. <math>\sum_{Q \in \mathcal{Q}} w(Q) = 1</math>. <math>w(Q)</math> – это вероятность того, что при обращении к сервису будет выбран кворум <math>Q</math>. Нагрузка определяется следующим образом. | ||
| Строка 103: | Строка 104: | ||
Пелег и Вул изучили доступность систем кворумов в работе [11]. Хорошая вероятность отказа Fp(Q) для системы кворумов Q имеет limn!1 Fp(Q) = 0, когда p < j- Заметим, что вероятность отказа любой системы кворумов, чья отказоустойчивость равна f, не ниже е~^^\. Большинство имеет наилучшую доступность, когда p < j\ для p = j, существуют кворумные построения с Fp(Q) = 21; для p > 21 синглтон имеет наилучшую вероятность отказа Fp(Q) = p, но для большинства систем кворумов Fp(Q) стремится к 1. | Пелег и Вул изучили доступность систем кворумов в работе [11]. Хорошая вероятность отказа Fp(Q) для системы кворумов Q имеет limn!1 Fp(Q) = 0, когда p < j- Заметим, что вероятность отказа любой системы кворумов, чья отказоустойчивость равна f, не ниже е~^^\. Большинство имеет наилучшую доступность, когда p < j\ для p = j, существуют кворумные построения с Fp(Q) = 21; для p > 21 синглтон имеет наилучшую вероятность отказа Fp(Q) = p, но для большинства систем кворумов Fp(Q) стремится к 1. | ||
== Нагрузка и доступность систем кворумов == | == Нагрузка и доступность систем кворумов == | ||