一种基于新的选举策略的分布式共识协议

一种基于新的选举策略的分布式共识协议 Consensus Algorithm Based on a New Strategy for Leader Election first-author 肖茜文，女，硕士生，现从事软件工程方面的研究. Email: xiaoqw@whu.edu.cn 肖茜文，女，硕士生，现从事软件工程方面的研究. Email: xiaoqw@whu.edu.cn xiaoqw@whu.edu.cn corresp 陈刚, E-mail:chenzuolin@whu.edu.cn 陈刚, E-mail:chenzuolin@whu.edu.cn chenzuolin@whu.edu.cn 武汉大学 国家网络安全学院, 湖北 武汉 430072 武汉大学 国家网络安全学院, 湖北 武汉 430072 School of Cyber Science and Engineering, Wuhan University, Wuhan 430072, Hubei, China School of Cyber Science and Engineering, Wuhan University, Wuhan 430072, Hubei, China 针对在网络和节点故障率较高环境下的副本状态机一致性问题，提出一种改进的分布式共识协议xm-Paxos.通过选举确定性较高的副本节点作为集群的领导者，加快集群节点对决议结果的确认；同时简化共识协议的重确认过程，减少重确认的消息传递.实验结果表明，在节点故障率较高、网络状况复杂的运行环境下，与使用Paxos算法进行选举的Multi-Paxos协议相比，xm-Paxos协议提高了集群节点的可用性和容错性，并降低了通信负载. Targeting at keeping replicated state machines consistent under the circumstances that failures of network and servers happen frequently, an improved consensus algorithm named xm-Paxos was proposed. The xm-Paxos adopted a different method for leader election, which elected a server with more confirmed replicated logs as the new leader of the cluster, to accelerate the process of logs' confirmation. Meanwhile, xm-Paxos simplified the algorithm when logs need to be re-proposed after leader takeover. The experimental results demonstrate that, compared with Multi-Paxos using Paxos for leader election, xm-Paxos can improve availability and fault-tolerance of the cluster when failures of network and servers occur frequently, and it can also generate fewer messages. 分布式系统 共识算法 xm-Paxos协议 副本状态机 distributed system consensus algorithm xm-Paxos protocol replicated state machine 引言 1 在分布式多副本系统中，网络通信和节点运行状况的不可控性是实现副本一致性面临的主要障碍.随着分布式副本一致在实际中的应用越来越广泛，集群所处的网络状况和节点运行状况的复杂度急剧上升，分布式一致性问题变得日益重要.如何在网络状况复杂、节点故障率较高的运行环境下，为分布式多副本一致提供高容错、低通信负载的解决方案，是一个值得探讨的课题. 分布式系统通常采用共识算法(consensus algorithm)来解决副本一致性的问题.Paxos算法 [ 1 1 ] 作为经典的共识算法，能够在 n 节点集群中容忍⌈ n /2⌉-1个节点失误，并通过消息传递实现分布式系统的一致性.为了将Paxos算法应用于副本状态机一致的应用场景，Multi-Paxos算法 [ 2 2 ] 指出：使用选举机制能够减少集群节点在共识过程中的消息传递.但Multi-Paxos并未指定实现选举的具体方式，使得部分系统在实现过程中需要引入额外的协调者，例如Spinnaker [ 3 3 ] 使用了Zookeeper提供的服务来实现集群领导者的选举.Raft算法 [ 4 4 , 5 5 ] 在选举方式上采取了Paxos的理念，保证了系统的容错性与可用性，但同时Raft要求多决议的状态必须连续.OceanBase [ 6 6 ] 在选举协议中将Paxos由“异步模式”改进为“同步模式”，能够保证集群在最长约2个选举周期内选出新的领导者，但这种选举方式依赖于节点间的时钟同步，服务器之间的时钟偏差不能过大. 近几年，研究者们倾向于将Paxos算法的实现建立在特定的网络通信架构之上，例如使用有序网络通信的Speculative Paxos [ 7 7 ] 和NOPaxos [ 8 8 ] 、应用于广泛地理分布的Multi-Ring Paxos [ 9 9 ] 、应用于网络设备的NetPaxos [ 10 10 , 11 11 ] 等，较少关注故障率较高的运行环境.而本文认为，在网络通信较差、节点故障较多的环境中，采用特定的选举策略能够提高多副本系统的可用性和容错性.本文延续了多副本状态机一致的思想，设计并实现了一种共识协议xm-Paxos，通过实现一种新的选举策略，保证多副本系统在网络和节点故障率较高环境下的高可用性、高容错性和低通信负载. 多决议及其确定性 1 副本状态机与多决议 2 一组服务器能够在各自独立的状态机上维持相同的状态，则称这组服务器状态机为副本状态机(replicated state machine).副本状态机通常是基于副本日志实现的.假设集群中的每一个服务器状态机具有相同的初识状态，并且存储了相同的副本日志，日志内包含的指令以及指令的顺序都相同，那么状态机在根据副本日志执行相同的指令序列之后能够产生相同的状态 [ 5 5 , 12 12 ] . Paxos能够对单一决议达成一致.为了使集群节点能够对一系列日志项达成一致，从而构成相同的副本日志，需要组合多个Paxos协议的实例来促成一系列决议的达成.这种需要对一系列决议达成一致的问题，称为多决议的一致性问题.相对于单一决议一致而言，Paxos在应用于多决议一致性问题时需要面临更多复杂的状况. 多决议的状态 2 当Paxos应用于多副本状态机一致的问题时，为了实现副本日志的一致性，集群节点不仅需要参与决议达成共识的过程，还需要获知决议达成共识的结果. 对每个单条日志项而言，若一个集群节点已经获知该日志项在多数节点上达成一致的决议值，称该日志项所对应的决议在该节点上达到了已确定的状态；相反，若未获知达成一致的共识结果，则称该日志项所对应的决议在该节点上处于未确定的状态. 设 a x 代表集群节点上序号为 x 的日志所对应的决议项， x ∈[0, +∞), 已知集群节点按照单调递增的顺序对日志发起决议.如 图 1 图 1 所示，{ a x | x ∈[0, +∞)}为集群中的一台服务器需要达成一致的决议集合，且集群已对{ a x | x ∈[0, n ]内的决议尝试达成共识.使用T标示服务器上已确定的日志决议，F标示未确定的日志决议，则 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4257357&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4257357&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4257357&type=middle 为此服务器上未确定的决议项的集合，集合内的决议项由于各种原因(例如消息丢失、节点故障或集群未发起决议)未获知在集群中达成一致的共识结果. 对于副本状态机而言，在未确定决议之后的日志所记录的操作是不可执行的，即在未确定决议之后的日志所生成的状态是不可达的.以 图 1 图 1 所示的集群节点为例，它所持有的副本状态机只能到达由{ a x | x ∈[0, 1]}集合内决议的日志构成的状态.为了保证副本状态机的可用性，集群节点需要及时获知已完成的日志决议的共识结果、持有更多的已确定决议. 多决议的确定性 2 在多决议一致的问题中，节点的确定性是指节点持有决议的确定程度.设某节点的确定性为 S ，则有 S = c / p ，其中 c 为该节点持有的已确定决议数， p 为集群发起的决议数.从 S = c / p 可以推断，在 p 值相等时，节点持有的已确定决议数 c 越大，节点在多决议一致性问题中的确定性 S 也将越高. 节点的确定性与节点的可用性之间存在着密切的关系.设某节点的可用性为 U ，则有 U = l / p ，其中 l 为该节点持有的连续确定的最末决议序号， p 为集群发起的决议数.一般情况下，在 p 值相等时，节点的已确定决议数 c 越大，节点的 l 值也可能越大.由此可以推断，在多决议一致的问题中，节点的确定性 S 越高时，节点的可用性 U 也可能越高. 新的共识协议：xm-Paxos 1 在网络通信不能得到保障或集群节点上下线变动活跃的场景下，集群节点可能由于消息的缺失而持有较少的已确定决议，节点在多决议问题中的确定性较低, 相应地，节点的可用性也将不能得到保证.xm-Paxos协议采用新的选举策略，尝试为多副本一致系统提供新的高容错、低通信负载的解决方案，保证集群节点在网络和节点故障率较高的运行环境中仍能保持高可用性. 基本算法 2 xm-Paxos以Multi-Paxos为基石，并在消息传递中使用最小未确定序号 φ 通知集群节点已完成决议的共识结果 [ 13 13 ] ，其中 φ =Min({ x | a x 为集群节点的未确定决议}).协议中负责发起提议的提议者 P 由集群选举出来的领导者 L 担任.每条决议有对应的决议序号，且集群节点按照决议序号单调递增的顺序发起决议的共识过程.假使在 n 个节点的集群中， L 为集群的领导者， A k (其中 k ∈[0, n -1])为集群的决议者.当发起一项新的决议时，决议流程的具体描述如下： 1) 领导者 L 向所有集群决议者 A k 发送ACCEPT消息，消息中携带 L 的提案号 p L 、最小未确定序号 φ L 以及决议的序号和内容. 2) 决议者 A k 接收到ACCEPT消息，将消息中携带的 p L 与自身记录的决议提案号 p k 进行对比.如果 p L ＜ p k ，则忽略该ACCEPT消息.如果 p L ≥ p k ，则记录该ACCEPT消息中的决议内容，并依据消息中的 φ L 更新自身持有决议的确定状态，最后向 L 发送ACCEPT_RES消息. 3) 领导者 L 收到超过半数的决议者发送的ACCEPT_RES消息，则更新持有决议的确定状态，将此决议标识为已确定的决议.如果该决议的序号与 φ L 相等，则更新 φ L = φ L +1. 领导者 L 需定时向集群节点发送HEARTBEAT消息以表明自身仍处于正常工作的状态.若集群节点在规定的时间内未收到来自 L 的HEARTBEAT消息，则认为该领导者节点 L 可能已由于故障而不可达.为了保障多副本集群的正常决议，集群节点将尝试选举新的集群领导者. 选举策略 2 领导者 L 作为任期间集群惟一的提议者 P ，其所持决议的确定性决定了整个多副本系统的可用性.xm-Paxos的选举算法在高容错的基础上，启发式地选择集群中确定性高于多数节点的副本节点作为领导者 L .这种策略能够减少 L 为未确定的决议重新发起共识的次数，从而加快集群节点对决议结果的确认. 根据2.1节中描述的使用最小未确定序号 φ 通知集群节点共识结果的过程来看，在 n 个节点构成的分布式集群中，决议者 A k (使用 k 区分不同的决议者，其中 k ∈[0, n -1])更新持有决议的确定状态时满足下述原则： 1) A k 的最小未确定序号 φ k 越大时， A k 越可能确定更多的决议项，持有的已确定决议数 c k 可能越大. 2) A k 更新决议状态的惟一参照值为领导者 L 的最小未确定序号 φ L . φ L 的载体为L发出的ACCEPT消息，且集群按照决议序号单调递增的顺序发起决议.因此， A k 参与决议的最末决议序号 ω k 越大时， A k 所参照的 φ L 越新，持有的已确定决议数 c k 可能越大. ω k =Max({ x | a x 为集群节点 A k 已参与的决议}). 根据上述两点可以得出，副本节点的最小未确定序号 φ 和最末决议序号 ω 越大时，节点持有的已确定决议数 c 可能越大，节点的确定性 S 也将越大.在启发式推断下，值 φ 和 ω 可用于比较节点之间的确定性大小.如果节点 i 和节点 j 满足关系 φ i ＞ φ j ， ω i ＞ ω j ，则可推断两节点之间的确定性大小为 S i ＞ S j . xm-Paxos在选举过程中使用最小未确定序号 φ 和最末决议序号 ω 比较副本节点之间的确定性.xm-Paxos的选举算法遵循下述流程： 1) 假设节点 i 为集群中某个尝试发起新一轮选举的副本节点， p i , ω i , φ i 分别代表节点 i 持有的提案号、最末决议序号和最小未确定序号, 且节点 i 在尝试发起选举前认定的集群领导者为 L ， L 的提案号为 p L .若节点 i 在规定的时间内未收到来自 L 的HEARTBEAT消息，则执行: 1:转换角色，isCandidate = True 2:选择一个提案号 p i ，使得 p i ＞ p L 3:向全部的集群节点发送Vote〈 p i ， ω i , φ i 〉消息 4: //等待各集群节点的VoteResponse〈 p i 〉回执 5: if收到超过半数的VoteResponse〈 p i 〉消息then 6:    转换角色，isCandidate = False 7:     new_leader( i ， p i )，开始执行领导者的职能：包括发起决议、执行重确认过程、向集群节点定时发送HEARTBEAT消息等. 8: else规定时间内未收到超过半数的VoteResponse〈 p i 〉消息，则尝试发起新一轮的选举. 2) 假设 m 为集群中任一正常工作的副本节点， p m , ω m , φ m 分别代表节点 m 持有的提案号、最末决议序号和最小未确定序号.若节点 m 接收到来自节点 i 的Vote〈 p i ， ω i , φ i 〉消息，则执行： 9: if p i ＞ p m then 10:    if ω i ＜ ω m then ignore 11:    else if ω i == ω m then 12:    if φ i ≥ φ m then发送投票回执VoteResponse〈 p i 〉给节点 i 13:    else ignore 14:    end if 15:  else发送投票回执VoteResponse〈 p i 〉给节点 i 16:  end if 17: else ignore 18: end if 集群节点可能处于三种角色之一：follower、candidate和leader.follower持有一个认定的领导者，candidate正在参选，leader已被认定为领导者. 集群中的一个follower在认为领导者不可达时，将升格成为candidate，并尝试选举本节点成为集群新的领导者.如果candidate在该轮选举中获得了超过半数的投票，则升格成为leader，并开始执行作为领导者的职能.而若candidate在规定时间内未获得超过半数的投票，则继续作为candidate发起新一轮的选举.集群中的任何一个节点在接收到某节点的HEARTBEAT消息且消息中携带的提案号大于本节点持有的提案号时，将认为集群中出现了新的领导者.节点的角色将降至follower，并认定消息发送节点为新领导者. xm-Paxos的选举算法并不保证选举出集群中确定性最高的节点.它应用于网络异常和节点故障复杂的运行环境，选举过程需容忍 n 节点集群中的⌈ n /2⌉-1个节点不可达，因此选举节点的确定性只需高于半数副本节点.同时，选举算法使用最小未确定序号 φ 和最末决议序号 ω 比较不同节点之间的确定性大小，能够避免对已确定决议数进行精确的统计，从而降低协议实现过程的复杂性. 重确认过程 2 为了确保分布式副本的一致性，集群选举出的新领导者节点需要在上任之后对以往决议的结果进行一次重确认.假设新领导者 L 上任时的最小未确定序号为 φ L ，且最末决议序号为 ω L ，则 L 需要确保序号在 φ L 与 ω L 之间的每一项决议均能够通过Paxos算法并再次在集群中达成共识 [ 3 3 ] .在多副本系统里，重确认过程能够提升集群节点的确定性，是除了使用 φ 以外的另一种提升副本可用性的措施. 在以往的分布式共识协议中，重确认过程通常需要对每一项决议重新发起一轮完整的Paxos算法.考虑到各项决议可能处于不同状态，xm-Paxos对重确认过程进行不同程度的简化.对序号在 φ L 与 ω L 之间的决议，新领导者 L 若持有该决议的已确定值，则可不发起该决议的重确认；若通过Paxos算法的prepare阶段可得知该决议的已确定值，则可不发起Paxos算法的accept阶段；若非上述两种情况，则需要对该决议发起完整的Paxos算法以完成重确认过程. xm-Paxos协议通过简化重确认过程来减少集群节点间的一部分消息传递.根据简化后的重确认过程可知，如果集群选举的新领导者 L 持有更多的已确定决议、具有更高的确定性， L 所需完成的重确认过程将越简单，重确认过程造成的通信代价也将越小. 实验结果与分析 1 实验以TCP作为网络传输协议，在处于同一网段的服务器集群上进行.集群节点的数量可变，为了体现实验的一般性，本文分别使用了由5台、7台、11台服务器构成的节点集群.除了xm-Paxos协议以外，本文还实现了使用Paxos算法进行选举的Multi-Paxos协议，并对两者进行了比较.Multi-Paxos是目前应用广泛的共识算法.使用Paxos算法进行选举的Multi-Paxos协议不需要外部协调者，保证了系统的容错性和节点的对等；同时，在Multi-Paxos协议中使用最小未确定序号 φ 确定决议结果，为共识过程减少消息传递. 实验通过控制节点决议的不可达率 γ ，对比两种协议在不同故障率下各方面的性能表现.不可达率的计算公式为： γ = http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4257370&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4257370&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4257370&type=middle ×100%( n =5, 7, 11).其中: m i 表示节点 i 未参与的决议数， p 为集群发起的决议总数, n 为集群节点个数.不可达率 γ 越大，说明集群的网络和节点故障率越高.实验通过控制集群节点服务的启动与闭合达到调节 γ 值大小的目的.调节过程中避免了超过⌈ n /2⌉-1个节点停止服务，降低了实验的复杂度. 实验的集群节点配置如 表 1 表 1 所示.为了避免集群在选举过程结束之后暂时的不可用，集群节点的重确认过程作为后台进程运行. 配置项目 配置描述 CPU Pentium Dual-Core E6300 2.8 GHz 内存 4 GB 操作系统 CentOS 7.0 集群节点的平均可用性 2 在多副本状态机一致的系统里，节点的可用性由该节点状态机的最末可达状态决定.使用 U ′代表集群节点的平均可用性，则 U ′= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4257376&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4257376&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4257376&type=middle ×100%( n =5, 7, 11).其中: l i 表示节点 i 持有的连续确定的最末决议序号， p 为集群发起的决议总数, n 为集群节点个数. 实验设置 γ ≈ 10%, 20%, 30%，并分别在5、7、11个节点构成的集群上测试两种协议.集群领导者负责发起新的提议，与此同时集群的全部节点则负责得出决议结果.在集群进行近10 000次决议时结束运行，并计算集群节点的平均可用性 U ′.实验结果如 表 2 表 2 所示.    xm-P代称xm-Paxos，Multi-P代称Multi-Paxos 9 % 2 γ ≈ 2 5个节点 2 7个节点 2 11个节点 xm-P Multi-P xm-P Multi-P xm-P Multi-P 10 97.48 90.63 97.70 91.89 99.53 99.25 20 92.78 62.76 96.52 56.67 97.23 81.58 30 84.64 48.25 90.29 51.82 96.0 5 69.89 总体看来，在对比实验中，xm-Paxos的节点平均可用性均优于Multi-Paxos.当集群节点 γ ≈10%时，两种协议的差距较小，而随着 γ 的增大，xm-Paxos的节点平均可用性明显强于Multi-Paxos.在不可达率较高的情况下，xm-Paxos的节点平均可用性更优，这是由于当不可达率 γ 较高时，集群领导者发生更替的可能性也更高；xm-Paxos相较于Multi-Paxos，在选举过程中更倾向于选举持有已确定决议更多的节点，从而提高了整个集群全部节点的可用性. 集群节点的平均确定性 2 节点在多决议一致问题中的确定性是衡量集群容错性的一个关键因素.在 γ 相同的情况下，集群节点的确定性越高，说明集群的容错性越好.使用 S ′代表集群节点的平均确定性，则 S ′= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4257381&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4257381&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4257381&type=middle ×100%( n =5, 7, 11)，其中 c i 表示节点 i 持有的已确定决议总数， p 为集群发起的决议总数, n 为集群节点个数. 仍使用3.1节的实验，在集群结束运行后计算集群节点的平均确定性 S ′.实验结果如 表 3 表 3 所示.    xm-P代称xm-Paxos，Multi-P代称Multi-Paxos 9 % 2 γ ≈ 2 5个节点 2 7个节点 2 11个节点 xm-P Multi-P xm-P Multi-P xm-P Multi-P 10 98.52 92.35 98.16 93.71 99.80 99.78 20 98.23 63.97 98.98 56.93 98.85 82.42 30 86.02 49.83 92.38 54.46 98.31 72.94 相较于Multi-Paxos，xm-Paxos的确定性优势随着不可达率 γ 的增大逐渐加强.当集群节点不可达率 γ ≈10%时，xm-Paxos和Multi-Paxos的节点平均确定性皆超过90%；而当 γ ≈30%时，xm-Paxos和Multi-Paxos的节点平均确定性则有了明显的差距.说明在 γ 不可达率逐渐增大的情况下，xm-Paxos仍能保证集群节点达成对决议的确定，而Multi-Paxos则受到 γ 的影响，延缓了集群节点对共识结果的获知. 通信代价 2 在多决议的一致性问题中，通常使用达成每个决议的平均消息损耗衡量通信代价.使用 M 表示通信代价，则 M = http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4257386&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4257386&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4257386&type=middle ( n =5, 7, 11)，其中 t i 表示节点 i 在共识协议中处理的消息总数(包括接收到的消息和发出的消息)， p 为集群发起的决议总数, n 为集群节点个数.仍使用3.1节的实验，比较当不可达率 γ ≈20%时两种协议分别在5、7、11节点集群上的通信代价 M .实验结果如 图 2 图 2 所示. 对于xm-Paxos和Multi-Paxos，在节点数目不同的集群中，数值相对稳定, xm-Paxos的通信代价略低于Multi-Paxos，两者之间的差距在1~2个消息之间.这是由于xm-Paxos对重确认过程进行了简化，并在选举时倾向选择持有决议确定性更高的节点，减少了重确认时的消息传递. 结论 1 本文提出一种改进的分布式共识协议xm-Paxos.xm-Paxos对重确认过程进行简化，并引入新的选举策略，选举确定性较高的副本节点成为集群的新领导者.实验结果表明，在节点变动活跃、网络状况复杂的运行环境下，与现有广泛采用的算法相比(例如Multi-Paxos)，xm-Paxos体现了更好的可用性、更好的容错性和更低的通信负载.下一步将研究如何将xm-Paxos与集群重配置结合，使共识协议更好地应用于节点变动灵活的集群. 参考文献 LAMPORT L. Paxos made simple[J]. ACM SIGACT News , 2001, 32 (4): 18-25. CHANDRA T, GRIESEMER R, REDSTONE J. Paxos made live: An engineering perspective[C]// Proceedings of PODC' 07. New York: ACM, 2007: 398-407. https://www.researchgate.net/publication/221343371_Paxos_made_live_An_engineering_perspective RAO J, SHEKITA E J, TATA S. Using Paxos to build a scalable, consistent, and highly available datastore[J]. Proceedings of the VLDB Endowment, 2011, 4 (4): 243-254. DOI: 10.14778/1938545.1938549. ONGARO D, OUSTERHOUT J. In search of an understandable consensus algorithm[C]// Proceedings of USENIX ATC ' 14. Berkeley: USENIX Association, 2014: 305-319. https://www.usenix.org/conference/atc14/technical-sessions/presentation/ongaro WOOS D, WILCOX J R, ANTON S, et al . Planning for change in a formal verification of the Raft consensus protocol[C]// Proceedings of CPP 2016. New York: ACM, 2016: 154-165. https://www.researchgate.net/publication/302574495_Planning_for_Change_in_a_Formal_Verification_of_the_Raft_Consensus_Protocol 杨传辉. OceanBase高可用方案[J].华东师范大学学报(自然科学版), 2014(5): 173-179. DOI: 10.3969/j.issn.1000-5641.2014.05.015. YANG C H. High availability solution of OceanBase[J]. Journal of East China Normal University (Natural Science) , 2014(5): 173-179. DOI: 10.3969/j.issn.1000-5641.2014.05.015(Ch). PORTS D R K, LI J, LIU V, et al . Designing distributed systems using approximate synchrony in data center networks[C]// Proceedings of NSDI' 15. Berkeley: USENIX Association, 2015: 43-57. https://www.usenix.org/conference/nsdi15/technical-sessions/presentation/ports LI J, MICHAEL E, SHARMA N K, et al . Just say NO to Paxos overhead: Replacing consensus with network ordering[C]// Proceedings of OSDI' 16. Berkeley: USENIX Association, 2016: 467-483. https://blog.acolyer.org/2016/12/08/just-say-no-to-paxos-overhead-replacing-consensus-with-network-ordering/ BENZ S, SOUSA L P, PEDONE F. Stretching Multi-Ring Paxos[C]// Proceedings of SAC' 16. New York: ACM, 2016: 492-499. http://xueshu.baidu.com/usercenter/paper/show?paperid=b6d0ecbfc7ce9655e7390731a85cfe8d&site=xueshu_se DANG H T, SCIASCIA D, CANINI M, et al . Net-Paxos: Consensus at network speed[C]// Proceedings of SOSR' 15. New York: ACM, 2015: 1-7. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.717.2469 DANG H T, CANINI M, PEDONE F, et al . Paxos made switch-y[J]. ACM SIGCOMM Computer Communication Review , 2016, 46 (2): 18-24. DOI: 10.1145/2935634.2935638. RENESSE R V, ALTINBUKEN D. Paxos made moderately complex[J]. ACM Computing Surveys(CSUR), 2015, 47 (3): 42:1-42:36. DOI: 10.1145/2673577. OUSTERHOUT J, ONGARO D. Implementing Replicated Logs with Paxos[EB/OL]. [2013-03-01] . https://ramcloud.stanford.edu/~ongaro/userstudy/paxos.pdf https://ramcloud.stanford.edu/~ongaro/userstudy/paxos.pdf . 10.14188/j.1671-8836.2018.06.004 TP302 whdxxblxb-64-6-501 国家自然科学基金(U1531122) 2018-03-08 2018-12-24 2020-11-30 版权所有© 2018 《武汉大学学报(理学版)》编辑部 Copyright © 2018 Journal of Wuhan University(Natural Science Edition). All rights reserved. 2018 武汉大学学报(理学版) 6 64