Кворум (распределенные вычисления)

Кворум — это минимальное количество голосов, которое должна получить распределенная транзакция, чтобы ей было разрешено выполнить операцию в распределенной системе . кворуме . Для обеспечения согласованной работы в распределенной системе реализован метод, основанный на

Методы кворума в системах распределенных баз данных

Голосование на основе кворума может использоваться в качестве метода управления репликами . ^[1] а также метод фиксации для обеспечения транзакций атомарности при наличии разделения сети . ^[1]

Голосование на основе кворума в протоколах фиксации

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

Каждому сайту в системе присваивается голос V _i . Предположим, что общее количество голосов в системе равно V, а кворумы прерывания и фиксации равны V _a и V _c соответственно. Тогда при реализации протокола фиксации необходимо соблюдать следующие правила:

V _a + V _c > V, где 0 < V _c , V _a $\leq$ V.
Прежде чем транзакция будет зафиксирована, она должна получить кворум фиксации V _c .
Всего по крайней мере один сайт, готовый к фиксации, и ноль или более сайтов, ожидающих $\geq$ В _ц . ^[2]
Прежде чем транзакция будет прервана, она должна получить кворум прерывания V _a.
Всего ноль или более сайтов, готовых к прерыванию, или сайтов, ожидающих прерывания. $\geq$ И _.

Первое правило гарантирует, что транзакция не может быть зафиксирована и прервана одновременно. Следующие два правила указывают голоса, которые транзакция должна получить, прежде чем она сможет завершиться тем или иным способом.

Голосование на основе кворума для управления репликами

В реплицируемых базах данных копии объекта данных имеются на нескольких сайтах. Чтобы обеспечить сериализуемость , нельзя разрешать двум транзакциям одновременно читать или записывать элемент данных. В случае реплицируемых баз данных можно использовать протокол управления репликами на основе кворума, чтобы гарантировать, что никакие две копии элемента данных не читаются и не записываются двумя транзакциями одновременно.

Голосование за контроль реплик на основе кворума принадлежит [Gifford, 1979]. ^[3] Каждой копии реплицируемого элемента данных назначается голос. Затем каждая операция должна получить кворум чтения (V _r ) или кворум записи ( V _w ) для чтения или записи элемента данных соответственно. Если данный элемент данных имеет в общей сложности V голосов, кворумы должны подчиняться следующим правилам:

V _r + V _w > V
V _w > V/2

Первое правило гарантирует, что элемент данных не читается и не записывается двумя транзакциями одновременно. Кроме того, это гарантирует, что кворум чтения содержит хотя бы один сайт с новейшей версией элемента данных. Второе правило гарантирует, что две операции записи из двух транзакций не могут выполняться одновременно с одним и тем же элементом данных. Эти два правила гарантируют сохранение сериализуемости одной копии.

См. также

Ссылки

^ Jump up to: ^а ^б Озсу, Тамер М; Вальдурье, Патрик (1991). «12». Принципы распределенных систем баз данных (2-е изд.). Река Аппер-Сэддл, Нью-Джерси: Prentice-Hall, Inc. ISBN 978-0-13-691643-7 .
^ Скин, Дейл. «Протокол фиксации на основе кворума» (PDF) . Библиотека ECommons Корнеллского университета . Проверено 10 февраля 2013 г.
^ Гиффорд, Дэвид К. (1979). Взвешенное голосование за реплицируемые данные . SOSP '79: Материалы седьмого симпозиума ACM по принципам операционных систем. Пасифик Гроув, Калифорния, США: ACM. стр. 150–162. CiteSeerX 10.1.1.12.6256 . дои : 10.1145/800215.806583 .

[ozsu-1] Jump up to: ^а ^б Озсу, Тамер М; Вальдурье, Патрик (1991). «12». Принципы распределенных систем баз данных (2-е изд.). Река Аппер-Сэддл, Нью-Джерси: Prentice-Hall, Inc. ISBN 978-0-13-691643-7 .

[2] Скин, Дейл. «Протокол фиксации на основе кворума» (PDF) . Библиотека ECommons Корнеллского университета . Проверено 10 февраля 2013 г.

[3] Гиффорд, Дэвид К. (1979). Взвешенное голосование за реплицируемые данные . SOSP '79: Материалы седьмого симпозиума ACM по принципам операционных систем. Пасифик Гроув, Калифорния, США: ACM. стр. 150–162. CiteSeerX 10.1.1.12.6256 . дои : 10.1145/800215.806583 .

[1]

[2]

[3]