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

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

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

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

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

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

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

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

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

Голосование на основе кворума за контроль реплики

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

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

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

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

Смотрите также

использованная литература

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

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

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

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

[1],