标签: paxos

以下问题旨在认真而不是轻浮.我缺乏分布式系统的经验,但我确实理解Basic Paxos如何工作以及为什么领导者选择是有用的.不幸的是,我的理解还不够深入,无法理解下面的问题.

在关于交易提交的共识,第8页(链接PDF的第11页)中,我们有以下声明.

选择独特的领导者等同于解决共识问题.

如果这个陈述是真的,并且Paxos的目的是达成共识,为什么Paxos本身并不常用于领导者选举？

此外,同一篇论文赞同领导者选举算法描述的稳定领袖选举论文.

如果这两个问题是等价的,并且同一篇论文支持不同的领导者选举算法,为什么不使用其他算法来解决一般共识问题而不是Paxos？

使用2F + 1处理器时,Paxos算法可以容忍高达F的故障.据我所知,此算法仅适用于固定数量的处理器.是否可以在动态环境中使用此算法,其中可以动态添加和删除节点？

在raft中,当节点重新启动时,它会尝试重做所有日志条目以赶上状态.但是如果节点在恢复阶段再次出现故障,节点会做两次操作.如果ops不是幂等的,那么这两次重做操作将违反状态机.

根据上面的描述,我的问题是,在实践中使用筏子的系统中使ops成为幂等的必要吗？

基本上,我想实现以下算法并分析使用这些算法构建的系统在不同条件下的行为.

• 八卦协议
• 多个paxos
• 一致的散列

我的兴趣在于这些算法.我基本上正在寻找一种编程语言,可以让我快速编写这些算法并深入理解这些算法.

我应该选择哪种语言？Java,Scala,Erlang或其他任何东西.

目前,我了解Java和C++.

我读了一篇名为"Paxos简单"的论文,但仍有一些混淆:

1. "paxos算法的实例"是指什么？每个实例都表明外部客户端有输入/命令吗？并且每个实例的paxos算法将并行执行???

2. 如果只有一个能够发出提案的"杰出"提议者,那么paxos算法与2阶段提交算法的区别是什么？

3. 我们在哪里可以在实际项目中应用paxos算法？

这篇论文似乎给出了更清晰的描述:http: //research.microsoft.com/pubs/64634/web-dsn-submission.pdf

还有什么想法？

我是分布式系统的新手,我正在读"简单的Paxos".它创造了很多喋喋不休,我正在考虑性能影响.

假设您正在构建一个全球分布式数据库,其中有几个小型集群位于不同的位置.最小化跨站点通信量似乎很重要.

1. 你肯定需要做出哪些决定才能达成共识？我唯一想到的就是决定是从网络添加还是删除一个节点(或一组节点？).这似乎是矢量时钟工作所必需的.另一个我不太确定是在决定写入同一位置的命令,但是这应该由一位通过Paxos选出的领导者完成吗？

2. 避免让系统中的所有节点一起做出决定会很好.每个本地群集中的一些节点是否可以参与跨群集决策,并且所有本地节点都使用本地Paxos进行通信以确定跨站点问题的本地答案？假设网络未饱和,延迟将是相同的,但跨站点网络流量将更轻.

3. 假设您可以沿着行拆分数据库的表,并将每个行子集分配给节点的子集.在系统中的所有机器上使用Paxos选择一组节点来包含数据的每个子集是不正常的,然后只针对处理该数据子集的所有操作在这些节点之间运行Paxos？

一个包罗万象:是否还有其他任何与设计相关或算法优化的人来解决这个问题？

Backgound:

在第3节,名为实施状态机,Lamport的论文Paxos Made Simple,Multi-Paxos被描述.Multi Paxos用于Google Paxos Made Live.(Multi-Paxos用于Apache ZooKeeper).在Multi-Paxos中,可能会出现差距:

通常,假设领导者可以?提前获得命令 - 也就是说,它可以在选择命令1到之后i + 1通过i + ?命令提出命令i.? - 1然后可能出现高达命令的差距.

现在考虑以下场景:

整个系统使用主从架构.只有主服务器提供客户端命令.Master和Slaves通过Multi-Paxos就命令序列达成共识.Master是Multi-Paxos实例的领导者.现在假设主服务器及其两个从服务器具有下图所示的状态(已选择命令):

.

请注意,主状态中存在多个间隙.由于不同步,这两个奴隶落后了.这时,主人失败了.

问题:

1. 在检测到主设备故障后,从设备应该做什么(例如,通过心跳机制)？

2. 特别是,如何处理与旧主人的差距和缺失的命令？

关于Zab的更新:

正如@sbridges指出的那样,ZooKeeper使用Zab而不是Paxos.报价,

Zab主要用于主备份(即主从)系统,如ZooKeeper,而不是用于状态机复制.

似乎Zab与我上面列出的问题密切相关.根据Zab的简短概述文件,Zab协议包括两种模式:恢复和广播.在恢复模式下,会做出两个特定的保证:永远不会忘记已提交的消息并放弃跳过的消息.我对Zab的困惑是:

3. 在恢复模式下Zab是否也存在缺口问题？如果是这样,扎布做什么？

我将使用多个Paxos实现一个键值存储.我会有几个节点,其中一个是主节点.此主节点接收更新请求并将值复制到从属节点.

我的问题是如何选择主节点(或领导者)？我还可以使用Paxos算法吗？如果是这样,您是否认为有必要将paxos实现抽象为一个单元,该单元不仅可以由复制单元使用,还可以由领导选举单元使用？

如果我使用id最小的节点作为领导者？我该如何实施主租约？

谢谢你的回答.

为什么多paxos被称为多paxos？我看不出它是多么"多".

我正在学习Paxos算法(http://research.microsoft.com/en-us/um/people/lamport/pubs/paxos-simple.pdf),有一点我不明白.

我们知道事件遵循及时的顺序,并且当事件1-5和10被确定时发生,但此后6-9和11还没有.在上面的论文中,它说我们只需用无操作值填写6-9之间的差距,然后简单地记录11和11之间的新事件.

因此,在这种情况下,由于已经记录了事件10,我们知道某些事件必须在5到10之间发生,但由于某些故障而未被Paxos记录.如果我们只是填写无操作值,这些事件将在我们的录音中丢失.

更糟糕的是,如果我在上面链接的论文中说,事件实际上是来自客户端的命令,那么在中间丢失一些命令可能会使整个操作集合非法(如果没有任何命令可以跳过或命令他们很重要).

那么,为什么Paxos为事件之间的差距填补无操作价值仍然是合法的呢？(如果由于上面关注的无操作值,整个记录集可能无效.)此外,是否有更好的方法从这些间隙中恢复而不是使用no-op？