使用Paxos跨节点同步大文件
Using Paxos to synchronize a large file across nodes
我正在尝试使用 Paxos 在大小约为 50MB 的文件上保持节点之间的共识，并在各个节点不断修改。我 运行 关注实用性问题。
要求：
- 跨数百个节点同步 50MB 以上的文件
- 对该文件进行更改，可以从任何节点进行更改，并且不太可能直接相互竞争，最多在几秒钟内传播到整个网络
- 加入网络的新节点可以在几分钟内（<1 小时）通过跟随 Paxos 消息构建整个文件
我面临的问题是似乎没有办法同时实现目标 2 和 3。
以下是我目前考虑过的选项：
- 每一轮同步整个文件——完全不切实际，Paxos 轮次需要几分钟
- 仅同步对文件的更改——对于目标 1 和 2 来说是合理的，但违反了目标 3，因为新节点只能在每个状态单元都发生更改后才能同步整个文件
- 每轮同步更改和随机文件 — 我不确定 Paxos 是否允许这样做。节点将能够根据自己的更改验证更改（允许新更改），并且能够根据其版本的所述部分验证文件的随机部分，但这是否可行？
我认为第三个选项是最好的，但我不确定 Paxos 是否允许这样做。这个想法是将每轮交换的数据限制在 1500 字节以内，并主要用对文件的更改来填充这 1500 字节。大多数回合，文件将保持不变，并且发生更改的回合很可能少于 100 字节的更改状态，因此其他 1400 字节可以用文件的某些部分填充，这将允许构建新节点随着时间的推移整个文件。这实用吗？这个问题已经解决了吗？
正如彼得在评论中提到的，最终一致可能更合适。这是一种基于 gossip protocol.
的算法
每个节点都有文件的某个版本。每 N 秒，每个节点连接到另一个节点，并且它们交换版本号。如果一个节点落后于另一个节点，它会从对等节点下载文件。
这收敛得非常快，我认为在 1000 个节点的 10-20 轮八卦中。
更新
（引入 raft 或消息队列。）
木筏
从您的评论看来，您手上有一个键值存储。您可以将其视为分布式状态机，在其中您将对每个键的更新视为其自己的命令。这对于像 paxos 或 raft 这样的共识协议非常有用（我现在支持 raft 开源实现的数量）。更重要的是，这些通常被实现为也像一个原子广播系统。简而言之，少数节点作为核心决策者，其余节点听取结果。
（当然，我不知道你的文件是如何更新的；即如果它只在一个主节点上更新，其余的都是从节点。）
一个主要问题是扇出到 1000 个节点。为此，您可能需要分层扇出。有多种方案可以帮助解决这个问题；这里有一些想法。 A）让每个节点连接到两个随机对等点；并从具有最短路径的对等节点流向主节点（这称为 power of two choices）；或 B) 以某种概率 p 选择具有最短路线的对等方。 C) 让每个节点连接到一个随机对等节点，并以某种概率 p，来自该节点的流连接到其上游节点。这些概率是为了做一棵n叉树，在连接到主节点的每个节点和链表中的每个节点之间很好地平衡。
消息队列
现在，paxos 和 raft 提供了一些非常强大的保证。特别是对于这种情况，每次更新都将按顺序处理——跨所有键。如果您不需要该保证，那么您可以构建一个更简单的系统。
每个密钥更新都可以广播到分布式消息队列（如 SQS、RabbitMQ 等）。对每个密钥更新进行版本化，并且仅在其大于您拥有的版本时才应用更新。这为您呈现了一个美观快速的最终一致系统。
如果系统允许，我会使用 raft/paxos 使用上述方法。
我们可以使用paxos将写入文件的事务日志复制为described here。当带有空文件的新服务器加入集群时，它可以从最新节点请求快照。同时，新节点还可以监听和缓冲当前更新。一旦它加载了快照，然后应用了以后的更新，它就完全是最新的。
快照可以是文件的完整副本。获取完整快照意味着阻止写入而不是读取。对于 raided SSD 磁盘上的 50M 文件来说，这可能不会带来太大的性能开销。一种更有效的方法可能是将文件建模为不可变（纯函数）数据结构，copy-on-write semantics. Rather than a flat file we can model it as a persistent data structure of file chunks. An example would be a immutable sorted map where the keys are file chunk numbers and the values are the chunks of the file. Writing to the file means then means inserting one or more updated chunks into the map. With such a data structure all write operations return a new immutable map. The new map shares unmodified file chunks with prior versions of the map. A snapshot of the file is then the immutable version of the map at a particular point in time. With an immutable map no locks need to be take to visit all chunks in the map to transmit the full snapshot of the file state to any new server. Log structured storage 使用这种技术。
我正在尝试使用 Paxos 在大小约为 50MB 的文件上保持节点之间的共识，并在各个节点不断修改。我 运行 关注实用性问题。 要求：
- 跨数百个节点同步 50MB 以上的文件
- 对该文件进行更改，可以从任何节点进行更改，并且不太可能直接相互竞争，最多在几秒钟内传播到整个网络
- 加入网络的新节点可以在几分钟内（<1 小时）通过跟随 Paxos 消息构建整个文件
我面临的问题是似乎没有办法同时实现目标 2 和 3。
以下是我目前考虑过的选项：
- 每一轮同步整个文件——完全不切实际，Paxos 轮次需要几分钟
- 仅同步对文件的更改——对于目标 1 和 2 来说是合理的，但违反了目标 3，因为新节点只能在每个状态单元都发生更改后才能同步整个文件
- 每轮同步更改和随机文件 — 我不确定 Paxos 是否允许这样做。节点将能够根据自己的更改验证更改（允许新更改），并且能够根据其版本的所述部分验证文件的随机部分，但这是否可行？
我认为第三个选项是最好的，但我不确定 Paxos 是否允许这样做。这个想法是将每轮交换的数据限制在 1500 字节以内，并主要用对文件的更改来填充这 1500 字节。大多数回合，文件将保持不变，并且发生更改的回合很可能少于 100 字节的更改状态，因此其他 1400 字节可以用文件的某些部分填充，这将允许构建新节点随着时间的推移整个文件。这实用吗？这个问题已经解决了吗？
正如彼得在评论中提到的，最终一致可能更合适。这是一种基于 gossip protocol.
的算法每个节点都有文件的某个版本。每 N 秒，每个节点连接到另一个节点，并且它们交换版本号。如果一个节点落后于另一个节点，它会从对等节点下载文件。
这收敛得非常快，我认为在 1000 个节点的 10-20 轮八卦中。
更新
（引入 raft 或消息队列。）
木筏
从您的评论看来，您手上有一个键值存储。您可以将其视为分布式状态机，在其中您将对每个键的更新视为其自己的命令。这对于像 paxos 或 raft 这样的共识协议非常有用（我现在支持 raft 开源实现的数量）。更重要的是，这些通常被实现为也像一个原子广播系统。简而言之，少数节点作为核心决策者，其余节点听取结果。
（当然，我不知道你的文件是如何更新的；即如果它只在一个主节点上更新，其余的都是从节点。）
一个主要问题是扇出到 1000 个节点。为此，您可能需要分层扇出。有多种方案可以帮助解决这个问题；这里有一些想法。 A）让每个节点连接到两个随机对等点；并从具有最短路径的对等节点流向主节点（这称为 power of two choices）；或 B) 以某种概率 p 选择具有最短路线的对等方。 C) 让每个节点连接到一个随机对等节点，并以某种概率 p，来自该节点的流连接到其上游节点。这些概率是为了做一棵n叉树，在连接到主节点的每个节点和链表中的每个节点之间很好地平衡。
消息队列
现在，paxos 和 raft 提供了一些非常强大的保证。特别是对于这种情况，每次更新都将按顺序处理——跨所有键。如果您不需要该保证，那么您可以构建一个更简单的系统。
每个密钥更新都可以广播到分布式消息队列（如 SQS、RabbitMQ 等）。对每个密钥更新进行版本化，并且仅在其大于您拥有的版本时才应用更新。这为您呈现了一个美观快速的最终一致系统。
如果系统允许，我会使用 raft/paxos 使用上述方法。
我们可以使用paxos将写入文件的事务日志复制为described here。当带有空文件的新服务器加入集群时，它可以从最新节点请求快照。同时，新节点还可以监听和缓冲当前更新。一旦它加载了快照，然后应用了以后的更新，它就完全是最新的。
快照可以是文件的完整副本。获取完整快照意味着阻止写入而不是读取。对于 raided SSD 磁盘上的 50M 文件来说，这可能不会带来太大的性能开销。一种更有效的方法可能是将文件建模为不可变（纯函数）数据结构，copy-on-write semantics. Rather than a flat file we can model it as a persistent data structure of file chunks. An example would be a immutable sorted map where the keys are file chunk numbers and the values are the chunks of the file. Writing to the file means then means inserting one or more updated chunks into the map. With such a data structure all write operations return a new immutable map. The new map shares unmodified file chunks with prior versions of the map. A snapshot of the file is then the immutable version of the map at a particular point in time. With an immutable map no locks need to be take to visit all chunks in the map to transmit the full snapshot of the file state to any new server. Log structured storage 使用这种技术。