本文选自《交易技术前沿》第二十四期 (2016年9月)。
佘鹏飞
上交所技术有限责任公司 上海 200120
Email :pfshe@sse.com.cn
摘要:本文主要介绍了一种基于虚同步的全序复制算法,根据该复制算法设计了内存复制协议,并论证了该内存复制算法的正确性,最后在该复制协议的基础上进行了适合证券交易系统撮合集群间内存数据异步复制框架的设计。通过该内存数据异步复制框架可以解决当前交易撮合集群间数据同步复制的问题,从而提高交易撮合系统的性能降低系统业务处理的延迟。
关键词:虚同步,全序算法,异步复制
证券交易所的交易系统是公认的关键业务实时处理系统。通常为了使得交易系统有较低的延时和较高的吞吐性能,一般会采用主机内存来存储数据。为了保证交易系统的高可用性,目前世界上主流交易所的交易系统会采用一个甚至多各数据副本进行冗余备份。如此,当前通用的交易系统都存在着内存数据在集群中各数据副本间的复制问题,这个问题也是提高交易系统的可用性必须面对的主要问题。要保证所有数据副本的状态是一致的,就必须要求所有的数据副本按照相同的顺序处理所有来自不同客户端的请求。因此,设计一个内存数据复制协议就演变成了设计一个全序协议。
为了满足交易系统对可靠性和延时性能的极高要求,提高交易系统的容错能力,我们提出了一个新的基于虚同步机制的全序算法,然后在该算法的基础上形成了一个全序复制协议,最后我们给出了一种满足交易系统低延时性和高可靠性要求的内存数据的异步复制.
设计一个基于领导者的全序算法的关键要点在于,当领导者失效时,如何选择一个唯一的新领导者,以及如何保持领导者和跟随者间的所有数据副本的状态是一致的。为了能够满足前面的两个条件,我们将组通信中的虚同步机制引入到全序算法中。
虚同步机制与组成员关系变化是密切相关的。为了表示上的方便,我们引入了组视图的概念,组视图时对组成员关系的一种抽象描述。
假设一个通信组G,通信组G的一个视图是指由通信组G中处于正确的运行状态且彼此之间可以进行相互通信的成员进程组成的进程子集,而且该子集被其中的所有成员进程都认同。我们用view(G)来表示通信组G的一个视图,每一个视图都有唯一的标识。
在一个通信组中,通信组成员之间的组播通信随时受组视图变化的影响,对于一个通信组成员来说,不仅要处理组成员之间的组播消息,而且还要处理视图变化的通知消息,并且这两类消息相互交织穿插在组成员所处理的消息流中。虚同步机制就是对这两类消息进行协调管理,在组视图发生变化的情况下,保证正确的组成员之间对这两类消息的同步处理。
假设通信组G,视图view1(G)和view2(G),且view2(G)是view1(G)的直接后继,我们称通信组G中的通信是虚同步的,当且仅当如果存在一个进程p∈view1(G),在视图view1(G)中已经处理了消息M,且已更新了下一个视图view2(G),则所有已经更新下一个视图view2(G)的进程在更新view2(G)之前已经处理了消息M。
为了在通信组成员之间实现虚同步通信,我们设计一个虚同步算法。当通信组的视图发生变化时,当前视图中所有正确的成员就启动该算法,以便能够让所有的正确成员在下一个视图和当前视图中所有传递的消息集合达成一致。
每个成员p计算下一个视图的估计值E_viewp及计算在当前视图中所传递的消息集合Setp(M),并将这两个视图的估计值构造成一个新的视图估计值N_E_viewp;
成员p通过可靠组播协议将新的视图估计值N_E_viewp发送给所有的正确成员,然后使这些成员在新的视图和当前视图中所传递的消息集合上达成一致,向领导者发送提议消息;
领导者进程根据所有的正确成员回复的提议消息来计算新的视图估计值N_E_viewL,这个视图估计值是所有属于当前估计视图中成员的最新视图的交集,这样就可以保证下一个视图中不包含所有被怀疑的成员。领导者的待传递的消息集合SetL(M)是所有属于当前估计视图中成员的待传递的消息集合SetF(M)的并集,这样就可以保证属于下一个估计视图中的每一个成员不遗漏一条在当前视图中被其它成员传递的消息。
这个虚同步算法的优点在于,在参与同步的成员的失效个数不超过一半的情况下,该算法可以保证当前视图中所有正确的成员在下一个视图和在当前视图中所传递的消息集合达成一致,并且满足终止性,一致性及有效性等特性。
在虚同步机制研究的基础上,我们以虚同步算法为基础,提出了一个新的全序协议算法,通过这个全序协议算法设计了一个动态的内存数据复制协议。这个复制协议由客户端复制协议和组成员副本复制协议两部分组成。其中,客户端协议的主要功能是,通过可靠的组播通信将请求发送给通信组的各个副本,并等待领导者副本的应答消息,最后将结果返回给客户。组成员副本复制协议主要由全序协议算法构成,通过组成员副本复制协议可以动态复制领导者的定序的结果给各个组成员副本,并接收处理来自组成员关系的通知消息,更新维护当前的组视图。
组成员副本复制协议是动态复制协议最重要的核心部分,所以我们将对组成员副本复制协议进行详细的描述。具体描述如下所示:
协议的正确性主要有两个方面分别是保证提交的全序性和保证所有的消息最终都会被提交。
在算法中,当前的领导者进程L唯一地指定,这样经由领导者进程进行定序后的全序消息序列是唯一的。所有的组成员副本成员是严格按照这个全序消息序列向应用处理提交消息的,所以无论是领导者进程还是跟随者进程都是根据唯一的全序消息序列向应用处理提交消息的。
客户端向通信组发送消息时是采用了可靠组播的方式,同一个客户端发出的消息是能够保证每个组成员都收到的,所以领导者和跟随者进程都能够接收到客户端的消息。在领导者进程正常工作时,所有的消息都会被定序后提交处理。在新领导者进程选举期间,客户端发送的消息都被缓存下来,当新领导者进程和所有组成员副本成员在新的组视图下就提交消息的全序列达成一致稳定后,缓存的客户端消息会被新领导者进程进行定序后提交给应用处理。所以不论是领导者正常工作的情况下还是新领导者选举期间的客户端消息都能够最终被提交处理。
对于这个基于虚同步机制的全序算法内存数据复制协议,其的容错性主依赖于虚同步的组通信机制。上述协议算法的容错性主要体现在对组视图变化的处理,当一个进程发生故障导致组视图变化时,虚同步的通信机制会保证所有正确的成员进程收到的消息数据集合是一致的。在按照领导者跟随者模式的全序复制协议向应用提交了相同序列的消息数据后,消息数据集合中未提交的数据也是相同的。所以在上述协议正确性的保证下,新选举出的领导者提交的消息数据序列和原来领导者的消息数据序列应该是一致的。对于原来领导者在消息数据集合中未被虚同步的组通信发布过的定序消息数据,对于整个虚同步通信组来说都可以认为这些消息数据未被定序过需要重新由新选举出的领导者来进行定序。
证券交易系统对系统的可靠性和容错性要求还是非常高的,为此我们在设计系统的异步复制框架时引入了基于虚同步机制的全序算法复制协议。通过这个全序算法复制协议,这个异步复制框架作为证券交易系统的底层容错通信框架主要提供了可靠有序组播服务,主备节点间消息数据同步服务和基于心跳超时的失败检测服务以及基于选举算法的主备切换等服务。具体服务和结构如图1所示, 上述服务可以分为三个独立的模块:集群管理与切换控制模块、数据定序与同步控制模块和可靠有序组播消息总线模块。集群管理和切换控制模块主要负责动态视图的检测和维护以及在发生切换时触发选举;数据定序与同步服务模块主要负责数据的虚拟同步和定序消息的异步复制以及在发生状态切换时的数据回补服务;可靠有序组播消息总线模块主要负责对组播消息数据进行缓存和可靠传输并对前面两个模块提供数据传输服务。
现有证券交易系统的内存数据的同步事务复制满足了系统的可靠性和容错性的要求,但是同步复制带来的时间消耗也严重影响了系统的性能和低延时的要求。针对这个问题,我们提出了基于虚同步的内存数据异步复制框架,该框架在满足交易系统的可靠性和容错性的要求的前提,通过异步复制和数据弱一致性乃至最终一致性保证,避免了内存数据复制的时间消耗对系统性能和延时的影响。
本文在写作过程中得到了上海证券交易所和中国金融期货交易所的多位交易系统架构专家的指导和帮助,在此深表谢意。
[1] Andrew S.Tanenbaum等著,辛春生,陈宗斌等译. 分布式系统原理与范型(第2版). 清华大学出版社,2008年6月
[2] George Coulouris,Jean Dollimore 著,金蓓弘, 马应龙等译. 分布式系统:概念与设计(第5版) .机械工业出版社,2013年1月
[3] 朱华勇 著,分布式系统实时发布、订阅数据分发技术. 国防工业出版社,2013年8月
[4] 史殿习,吴泉源,王怀民等. 组通信中虚同步协议的研究与设计. 计算机研究与发展,2000,37(10)
佘鹏飞,男,硕士,上交所技术有限责任公司技术开发部架构师,主要从事核心交易系统的架构设计工作,对分布式容错系统设计和低延迟技术有研究兴趣。
文章转自微信公众号:上交所技术服务
文章内容仅供参考!
如果觉得我的文章对您有用,请点赞。您的支持将鼓励我继续创作!
赞1
添加新评论0 条评论