Распределенное взаимное исключение: формирование кружка

Я изучал распределенные алгоритмы взаимного исключения, основанные на концепции кворумов.

Цитата: Группа C определяется как множество множеств, где каждое множество g ∈ C называется кворумом.

Следующие свойства справедливы для кворумов в кружке:

1) Свойство пересечения: для любого кворума g, h ∈ C, g ∩ h= ∅. Например, наборы {1,2,3}, {2,5,7} и {5,7,9} не могут быть кворумами в кружке, поскольку первый и третий наборы не имеют общего элемента.

2) Свойство минимальности: в котерии C не должно быть кворумов g, h таких, что g ⊇ h. Например, наборы {1,2,3} и {1,3} не могут быть кворумами в кружке, поскольку первый набор является надмножеством второго.

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

ОБНОВЛЕНИЕ: Если выразить проблему другими словами: «Учитывая N узлов, как лучше всего сформировать «K» кворумов, чтобы любые два из них имели общее количество узлов «J»?»


database distributed-computing distributed-database mutual-exclusion critical-section
person sg1    schedule 05.03.2014    source источник

Ответы (1)


arrow_upward
0
arrow_downward

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

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

Насколько я знаю, на практике вы связываетесь со случайными узлами и используете в качестве кворума n/2 + 1, но, как видите, вы также можете определить более сложные распределения, которые позволяют вам иметь меньшие кворумы, что опять же повышает производительность.

Обновление:

Примеры таких кворумов с 9 серверами могут быть следующими:

  • 2 кворума: серверы 1–5 — это один кворум, а 5–9 — другой (простое большинство)
  • 3 кворума: серверы 1,2,3,4; 4,5,6,7; а 7,8,9,1 могут быть 3 разными кворумами
  • больше кворумов: серверы 1,2,3; 3,4,5; 5,6,1; 6,7,3; 8,3,1; 9,3,1; может быть 6 различных кворумов. Однако здесь вы можете видеть, что серверы 1 и 3 являются частью 4 кворумов каждый, и по этой причине им потребуется обрабатывать гораздо больше трафика.
  • потенциально вы также можете создавать кворумы, такие как 1,2; 1,3; 1,4; 1,5; 1,6; 1,7; 1,8; 1,9; Но это то же самое, что просто иметь сервер 1.
person peter    schedule 05.03.2014
comment
Я хочу знать, как определить эти сложные дистрибутивы. Спасибо за ваш ответ, но это все еще не решает мою проблему. - person sg1; 05.03.2014
comment
Я добавил несколько примеров для установки с 9 серверами, возможно, проще всего нарисовать их на бумаге, чтобы лучше увидеть кворумы и понять, почему это будет работать. - person peter; 05.03.2014
comment
Спасибо. Я понимаю. Но знаете ли вы какую-либо исследовательскую работу/алгоритм/справку, где я мог бы прочитать о формировании таких кворумов более структурированным образом? Например: учитывая узлы «N», разделите их на наборы «K» так, чтобы любые два набора имели общее количество узлов «J»... (и, возможно, еще некоторые ограничения)... - person sg1; 05.03.2014
comment
Нет, в основном у вас уже есть формула, как вы описали ее в своем вопросе. Я думаю, что определение кворума в большинстве случаев довольно тривиально, и сложность заключается в том, чтобы понять, когда соединения и узлы разорваны, чтобы не блокировать новые операции без необходимости. Вот почему об этом не так много статей. - person peter; 06.03.2014