database - 分布式互斥：小圈子形成

Question

我一直在研究基于 Quorums 概念的分布式互斥算法。

引用：一个 Coterie C 被定义为一组集合，其中每个集合 g ∈ C 称为一个 quorum。

以下属性适用于小圈子中的仲裁：

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'个共同的节点？”

Answer 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 相同。