Paxos原理与实现(二)实现与实践篇

上一部分描述了Paxos算法的原理,这部分根据 MIT 6.824 lab3 的内容,展开来讨论一下Paxos算法实现的过程中遇到的问题,以及如何将它运用到一个实际的K-V系统中.
我把这部分代码放在了github上.
这个实验包括两部分,第一部分是实现一个Paxos算法库,第二部分是基于这个Paxos库实现一个KV存储系统.
先来说实现.
一个实际的系统中,同时可能存在多个需要处理的一致性问题,那么就需要处理以下几个问题:
  • 如何区分这些不同的问题?
  • 如何存储这些不同的问题?
  • 如何同步处理这些问题?
要解决这些问题,需要针对每个问题分配一个序列号,每个序列号对应该问题相关的数据存储,最后每个问题的解决过程对应一个线程来处理.
在代码中,使用一个数据结构来存储每次一致性问题的相关数据:
type instance struct {
state Fate        // instance state
n_p   string      // propose num
n_a   string      // accept num
v_a   interface{} // accept value
}
使用一个map来存储提议的数据:
instances map[int]*instance
其次需要注意的是,每个一致性事件对应的序列号,与每次一个提议值提交提案时的提议编号,不是一码事.一致性事件的序列号,虽然也是递增的,新的提议会比旧的提议序列号大,但是却不会发生改变,而提议编号,根据前面算法原理部分的描述,是由提议者自己决定的一个递增的值,一旦这次提议失败,将根据学习到的提议值,重新使用一个更新的提议编号来提交提议.简单的说就是以下几个区别:
  • 提议序列号对所有提议者而言都是唯一固定的,新的提议其序列号更高,但是一旦决定将不会发生改变.
  • 每个提议者提交自己提议时的提议编号,由提议者自己决定,但需要保证在同一次提议中,同一个提议者先后的提议其提议编号是递增的.
对应到前面的代码中,提议序列号就是map的key,而提议编号就是instance数据结构中的n_p,n_v.
那么紧跟着又需要面对的问题是,一个提议者实际中可能同时会提交不同的多个提议,也会存储这些提议的结果,另外不仅是存储自己系统上的提议结果,还需要知道其他提议者的提议结果,如果没有什么措施告诉它何时可以清除之前的数据,累计下来的数据就会越来越多,因此每个提议者还需要提供另外几个接口:
  • Max:返回当前的最高提议序列号
  • Min: 返回当前所有提议者通过决议的最小提议序列号,同时释放比这个序列号小的提议数据.
  • Done:  客户端通过调用这个接口,将通知提议者,客户端已经拿到了这个提议的数据,换言之在该序列号前面的数据已经同步了,提议者可以释放这部分空间.

为了做到这些,每个提议者还需要维护一个数据,用来存储其他提议者当前通过提议的最大序列号,这就是代码里面的dones数组的作用,其索引是每个提议者对应的编号,值为每个提议者当前通过的最大提议序列号.

另外还有一个问题需要交代一下.

活锁(livelock)问题,在Paxos算法中,prepare阶段,假如提议者A提交prepare请求之后,发现该提案不通过,于是选择一个更高的提议编号来提交下一次提议,B提议者也是如此,但是不凑巧的是每次相互之间的提议编号正好都是成覆盖关系,最后两者你不服我,我也不服你,无休止的循环下去,这就变成了活锁问题.这里的代码中并没有处理这个问题,因为出现这种问题的概率较低,而且即使出现,大不了就是多几次prepare处理,不会那么倒霉一直活锁下去.

这样就大概完成了Paxos算法的实现,这里更多谈到除了基础的原理之外还需要注意的部分,所以读者需要结合原理,代码和这个实验的文档一起来看才能真的了解它.

接下来谈如何使用这个算法应用到一个KV系统中,这就是代码中kvpaxos目录中的代码.
先简单介绍一下这个KV系统.它由一组服务器构成,对外提供Get/Put/Append三个简单的接口,是一个去中心化的平行设计,也就是说,客户端对其中的任意一个服务器做一个操作,其结果都应该是一致的.这些服务器之间并不互相通信,是通过前面实现Paxos库进行的通信,所有一致性的操作都封装在这里,KV系统本身之间并不进行通信进行同步数据,完全依赖于Paxos库的结果来做操作.
我们来看要在一个KV服务集群中做到同步需要面对的问题.很容易想到的是所有修改类的操作,通过日志同步的方式来做到一致性.就是说,如果针对这个系统,客户端先后进行了A,B,C三次修改操作(因为读操作不涉及数据的改动,所以不在这里提及,下同),那么这个操作顺序表现在使用日志来同步操作这一点上,所有这个集群的服务器都应该是一样的.
结合前面的分析,每个Paxos提议都对应一个序列号,所以这里可以给每个操作都有一个操作日志,每次操作都分配一个序列号,这个序列号是递增的(如何保证不同的客户端提交的修改操作不重复,递增不在这里讨论,这里假设客户端满足这个条件了,不会出现同时多个客户端提交同一个修改序列号的操作),而服务器自己也会保存一个自己最后执行的序列号.当服务器收到一个客户端修改请求时,服务器首先根据服务器上保存的上一次操作的序列号,依次来做数据的同步,因为这个服务器可能是后面才启动的,而服务器集群已经到了更高序列号的操作,此时首先就是不断的根据最后序列号来同步数据,同步完毕之后才使用客户端的修改操作来使用Paxos算法发起另一次新的修改请求.每同步完成一次数据,服务器可以调用前面的Done接口,告诉Paxos系统自己已经同步到了这部分数据,前面的提议数据可以丢弃了.
这样,就完成了这个基于Paxos算法的KV系统的概述.最后,要想真正明白的,还是希望能亲手做一下这个实验,我花了好几天的时间,半抄半写完成的实验,有些东西这里写的很简单,但是只有自己做一遍才能体会的更深刻些,虽然这个实验是这个教程的第三个实验,可是就我的感觉并不需要做前面的实验就可以开始动手做,前提是对Paxos算法有一定的了解了.我做的这部分还是2015年的课程,最新的2016年的课程,相同的部分好像使用Raft协议来做了,回头做完了再做一次总结.

Leave a Reply