4817
правок
Кворумы: различия между версиями
Перейти к навигации
Перейти к поиску
м
→Постановка задачи
Irina (обсуждение | вклад) м (→Применение) |
Irina (обсуждение | вклад) |
||
| Строка 6: | Строка 6: | ||
Мотивация создания систем кворумов обусловлена необходимостью обеспечить надежность выполнения машинами критически важных задач. Единственным способом повышения надежности сервиса, помимо использования более надежного оборудования, является тиражирование, или репликация. Чтобы сделать сервис надежным, его можно установить на несколько одинаковых серверов, каждый из которых хранит копию состояния сервиса и выполняет | Мотивация создания систем кворумов обусловлена необходимостью обеспечить надежность выполнения машинами критически важных задач. Единственным способом повышения надежности сервиса, помимо использования более надежного оборудования, является тиражирование, или репликация. Чтобы сделать сервис надежным, его можно установить на несколько одинаковых серверов, каждый из которых хранит копию состояния сервиса и выполняет на нем операции чтения/записи. Это позволяет системе предоставлять информацию и выполнять операции даже в том случае, если некоторые машины выйдут из строя или оборвутся каналы связи. К сожалению, репликация влечет расходы, связанные с необходимостью поддерживать согласованность серверов. Чтобы повысить доступность и производительность тиражируемого сервиса, Гиффорд и Томас [3, 14] в 1979 году ввели использование ''голосов'', назначаемых каждому серверу, так, чтобы для выполнения операций было достаточно большинства от суммы голосов. В более общем виде системы кворумов формально определяются следующим образом. | ||
| Строка 14: | Строка 14: | ||
'''Протокол доступа''' | '''Протокол доступа''' | ||
Чтобы продемонстрировать удобство использования систем кворумов при построении тиражируемых сервисов, кворумы используются для реализации совместно используемой мультирайтерной и мультиридерной атомарной переменной. Кворумы также используются в различных протоколах ''взаимного исключения'', для достижения консенсуса и в протоколах фиксации. | Чтобы продемонстрировать удобство использования систем кворумов при построении тиражируемых сервисов, покажем, как кворумы используются для реализации совместно используемой мультирайтерной и мультиридерной атомарной переменной. Кворумы также используются в различных протоколах ''взаимного исключения'', для достижения консенсуса и в протоколах фиксации. | ||
В приложении клиенты выполняют операции чтения и записи переменной <math>x</math>, которая реплицируется на каждом сервере в совокупности <math>U</math>. Копия переменной <math>x</math> хранится на каждом сервере вместе со значением временной метки <math>t</math>. Временные метки назначаются клиентом каждой реплике переменной, когда клиент записывает реплику. Разные клиенты выбирают разные временные метки, например, целые числа, дополненные именем c в младших разрядах. Операции чтения и записи реализованы следующим образом. | В данном приложении клиенты выполняют операции чтения и записи над переменной <math>x</math>, которая реплицируется на каждом сервере в совокупности <math>U</math>. Копия переменной <math>x</math> хранится на каждом сервере вместе со значением временной метки <math>t</math>. Временные метки назначаются клиентом каждой реплике переменной, когда клиент записывает реплику. Разные клиенты выбирают разные временные метки, например, целые числа, дополненные именем <math>c</math> в младших разрядах. Операции чтения и записи реализованы следующим образом. | ||
'''Запись''': чтобы клиент <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>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>, соответственно. | ||