4817
правок
Кворумы: различия между версиями
Перейти к навигации
Перейти к поиску
→Постановка задачи
Irina (обсуждение | вклад) (Новая страница: «Ключевые слова и синонимы Системы кворумов (''Quorum systems''); системы голосования (''Voting systems''); комитеты (''Coteries'') == Постановка задачи == Системы кворумов представляют собой инструменты повышения доступности и эффективности тиражируемых сервисов. Системой кв...») |
Irina (обсуждение | вклад) |
||
| Строка 3: | Строка 3: | ||
== Постановка задачи == | == Постановка задачи == | ||
Системы кворумов представляют собой инструменты повышения доступности и эффективности тиражируемых сервисов. Системой кворумов для совокупности серверов является набор подмножеств серверов, каждая пара которых имеет пересечение. Интуитивно понятно, что каждый кворум может работать от имени системы, тем самым повышая ее доступность и производительность, а свойство пересечения гарантирует, что операции, выполняемые на разных кворумах, сохраняют согласованность. | Системы кворумов представляют собой инструменты повышения доступности и эффективности тиражируемых сервисов. ''Системой кворумов'' для совокупности серверов является набор подмножеств серверов, каждая пара которых имеет пересечение. Интуитивно понятно, что каждый кворум может работать от имени системы, тем самым повышая ее доступность и производительность, а свойство пересечения гарантирует, что операции, выполняемые на разных кворумах, сохраняют согласованность. | ||
Мотивация создания систем кворумов обусловлена необходимостью обеспечить надежность выполнения машинами критически важных задач. Единственным способом повышения надежности сервиса, помимо использования более надежного оборудования, является тиражирование, или репликация. Чтобы сделать сервис надежным, его можно установить на несколько одинаковых серверов, каждый из которых хранит копию состояния сервиса и выполняет операции на нем чтения/записи. Это позволяет системе предоставлять информацию и выполнять операции даже в том случае, если некоторые машины выйдут из строя или оборвутся каналы связи. К сожалению, репликация влечет расходы, связанные с необходимостью поддерживать согласованность серверов. Чтобы повысить доступность и производительность тиражируемого сервиса, Гиффорд и Томас [3, 14] в 1979 году ввели использование голосов, назначаемых каждому серверу, так, чтобы для выполнения операций было достаточно большинства от суммы голосов. В более общем виде системы кворумов формально определяются следующим образом. | Мотивация создания систем кворумов обусловлена необходимостью обеспечить надежность выполнения машинами критически важных задач. Единственным способом повышения надежности сервиса, помимо использования более надежного оборудования, является тиражирование, или репликация. Чтобы сделать сервис надежным, его можно установить на несколько одинаковых серверов, каждый из которых хранит копию состояния сервиса и выполняет операции на нем чтения/записи. Это позволяет системе предоставлять информацию и выполнять операции даже в том случае, если некоторые машины выйдут из строя или оборвутся каналы связи. К сожалению, репликация влечет расходы, связанные с необходимостью поддерживать согласованность серверов. Чтобы повысить доступность и производительность тиражируемого сервиса, Гиффорд и Томас [3, 14] в 1979 году ввели использование ''голосов'', назначаемых каждому серверу, так, чтобы для выполнения операций было достаточно большинства от суммы голосов. В более общем виде системы кворумов формально определяются следующим образом. | ||
Система кворумов: предположим, что существует совокупность U серверов, |U| = n, и произвольное число клиентов. Системой кворумов Q | '''Система кворумов''': предположим, что существует ''совокупность'' <math>U</math> серверов, <math>|U| = n</math>, и произвольное число клиентов. ''Системой кворумов'' <math>\mathcal{Q} \subseteq 2^U</math> является множество подмножеств <math>U</math>, каждая пара которых имеет пересечение. Каждое <math>Q \in \mathcal{Q}</math> называется ''кворумом''. | ||
'''Протокол доступа''' | '''Протокол доступа''' | ||
Чтобы продемонстрировать удобство использования систем кворумов при построении тиражируемых сервисов, кворумы используются для реализации совместно используемой мультирайтерной и мультиридерной атомарной переменной. Кворумы также используются в различных протоколах взаимного исключения, для достижения консенсуса и в протоколах фиксации | Чтобы продемонстрировать удобство использования систем кворумов при построении тиражируемых сервисов, кворумы используются для реализации совместно используемой мультирайтерной и мультиридерной атомарной переменной. Кворумы также используются в различных протоколах ''взаимного исключения'', для достижения консенсуса и в протоколах фиксации. | ||
В приложении клиенты выполняют операции чтения и записи переменной <math>x</math>, которая реплицируется на каждом сервере в совокупности <math>U</math>. Копия переменной <math>x</math> хранится на каждом сервере вместе со значением временной метки <math>t</math>. Временные метки назначаются клиентом каждой реплике переменной, когда клиент записывает реплику. Разные клиенты выбирают разные временные метки, например, целые числа, дополненные именем c в младших разрядах. Операции чтения и записи реализованы следующим образом. | |||
'''Запись''': чтобы клиент <math>c</math> записал значение <math>v</math>, он запрашивает каждый сервер в некотором кворуме <math>Q</math>, чтобы получить набор пар значение/временная метка <math>A = \{ \langle v_u, t_u \rangle \}_{u \in Q}</math>; выбирает временную метку <math>t \in T_c</math>, большую, чем наибольшее значение временной метки в <math>A</math>; обновляет <math>x</math> и соответствующую временную метку на каждом сервере в <math>Q</math> до <math>v</math> и <math>t</math>, соответственно. | |||
И при операциях чтения, и при операциях записи каждый сервер обновляет свою локальную переменную и временную метку до полученных значений | '''Чтение''': чтобы клиент прочитал <math>x</math>, он запрашивает каждый сервер в некотором кворуме <math>Q</math>, чтобы получить набор пар значение/временная метка <math>A = \{ \langle v_u, t_u \rangle \}_{u \in Q}</math>. Затем клиент выбирает пару <math> \langle v, t \rangle</math> с наибольшей временной меткой в <math>A</math>, чтобы получить результат операции чтения. После этого он записывает <math> \langle v, t \rangle</math> на каждый сервер в некотором кворуме <math>Q'</math>. | ||
И при операциях чтения, и при операциях записи каждый сервер обновляет свою локальную переменную и временную метку до полученных значений <math> \langle v, t \rangle</math> только в случае, если <math>t</math> больше, чем временная метка, связанная с переменной в данный момент. Приведенный выше протокол корректно реализует семантику мультиридерной мультирайтерной атомарной переменной (см. [[Линеаризуемость]]). | |||
== Основные результаты == | == Основные результаты == | ||