2

我正在尝试使用 Paxos 在大小约为 50MB 的文件上保持节点之间的共识，并在各个节点上不断进行修改。我遇到了实用性问题。要求：

  1. 跨数百个节点同步一个 50MB 以上的文件
  2. 对此文件进行更改，可以从任何节点进行，并且不太可能直接相互竞争，最多在几秒钟内通过网络传播
  3. 加入网络的新节点可以在几分钟（<1 小时）内按照 Paxos 消息构建整个文件

我面临的问题是似乎没有办法同时实现目标 2 和 3。

以下是我目前考虑过的选项：

  • 每轮同步整个文件——完全不切实际，Paxos 轮次需要几分钟
  • 仅同步对文件的更改——对于目标 1 和 2 来说是合理的，但会破坏目标 3，因为新节点只能在每个状态单元更改后才能同步整个文件
  • 每轮同步更改和文件的随机部分——我不确定 Paxos 是否允许这样做。节点将能够根据自己的更改验证更改（允许新更改），并且能够根据其版本的所述部分验证文件的随机部分，但这实用吗？

我认为第三种选择是最好的，但我不确定 Paxos 是否允许这样做。想法是将每轮交换的数据限制为 1500 字节，并主要用对文件的更改来填充这 1500 字节。大多数轮次，文件将保持不变，而发生变化的轮次很可能少于 100 字节的更改状态，因此其他 1400 字节可以用文件的某些部分填充，这将允许构建新节点随着时间的推移整理整个文件。这实用吗？这个问题已经解决了吗？

4

2 回答 2

1

正如彼得在评论中提到的那样，最终一致的可能更合适。这是一种基于gossip 协议的算法。

每个节点都有文件的某个版本。每 N 秒，每个节点连接到另一个节点并交换版本号。如果一个节点落后于另一个节点，它会从对等节点下载文件。

这收敛得非常快，我认为在 1000 个节点的 10-20 轮八卦内。

更新

（在混合中引入 raft 或消息队列。）

筏

从您的评论看来，您手头上有一个键值存储。您可以将其视为分布式状态机，在其中您将每个键的更新视为其自己的命令。这对于像 paxos 或 raft 这样的共识协议来说非常有用（我现在更喜欢raft来考虑开源实现的数量）。更重要的是，这些通常被实现为也像原子广播系统一样。简而言之，少数节点充当核心决策者，其余节点听取结果。

（当然，我不知道您的文件是如何更新的；即，它是否只在主节点上更新，其余的都是从节点。）

一个主要问题是扇出到 1000 个节点。为此，您可能需要分层扇出。有各种计划可以帮助解决这个问题；这里有一些想法。A）让每个节点连接到两个随机对等点；并从具有最短路径的对等点流到主节点（这称为二选一）；或 B) 以某个概率p选择具有最短路径的对等点。C）让每个节点连接到一个随机对等点，并以一定的概率p从该节点流式传输，否则连接到其上游节点。这些概率是为了形成一棵 n 叉树，这在连接到主节点的每个节点和链表中的每个节点之间取得了很好的平衡。

消息队列

现在，paxos 和 raft 提供了一些非常强大的保证。特别是在这种情况下，每次更新都将按顺序处理——跨所有键。如果您不需要这种保证，那么您可以构建一个更简单的系统。

每个密钥更新都可以广播到分布式消息队列（如 SQS、RabbitMQ 等）。对每个密钥更新进行版本化，并且仅在其大于您拥有的版本时应用更新。这为您提供了一个美观且快速且最终一致的系统。

如果系统允许，我会使用 raft/paxos 使用上面的这种方法。

于 2015-08-31T04:15:13.567 回答
0

我们可以使用 paxos 将写入的事务日志复制到文件中，如此处所述。当具有空文件的新服务器加入集群时，它可以从最新节点请求快照。同时新节点也可以监听和缓冲当前的更新。一旦它加载了快照，然后应用了以后的更新，它就完全是最新的了。

快照可以是文件的完整副本。拍摄完整快照意味着阻止写入而不是读取。对于被袭击的 SSD 磁盘上的 50M 文件来说，这可能不会造成太大的性能开销。一种更有效的方法是将文件建模为具有写时复制语义的不可变（纯函数）数据结构。我们可以将其建模为文件块的持久数据结构，而不是平面文件。一个例子是一个不可变的排序映射其中键是文件块号，值是文件块。写入文件意味着将一个或多个更新的块插入到映射中。有了这样的数据结构，所有的写操作都会返回一个新的不可变映射。新地图与以前版本的地图共享未修改的文件块。文件的快照就是地图在特定时间点的不可变版本。使用不可变映射不需要锁定来访问映射中的所有块以将文件状态的完整快照传输到任何新服务器。日志结构化存储使用了这种技术。

于 2015-12-08T23:35:12.510 回答