【交易技术前沿】多节点冗余计算机系统的可靠性分析建模和分布式仿真验证 / 张娟，付华伟，左涛


本文选自《交易技术前沿》第十六期 （2014年9月）。

摘 要：计算机系统是应用程序运行的平台，计算机系统的可靠性是IT业务能否正常运行的关键。增加计算机系统可靠性的一种常用方法是配置多节点冗余计算机，即“多机热备”。通常来说，冗余节点数量越多，系统的可靠性越高。但对于要求主备机数据同步的计算机系统来说，冗余节点数量的增加，并不一定能提高系统可靠性，这是由于在数据同步的系统中，主备切换时也会暂时停止对外服务，从而增加了系统不可用性的缘故。本文应用马尔科夫模型对主备数据同步模式下的多节点冗余计算机系统可靠性进行建模，推导出了多机热备系统可靠性的统计计算公式，证明了计算机系统可靠性随着冗余节点数量增加先大幅提高再缓慢下降的结论，为交易所到底选择几个节点实现热备提供了科学的理论依据，各交易所可根据自身的系统架构、IT运维响应时间及服务器可靠性数值进行科学决策。本文还应用了Monte Carlo仿真的方法对多节点冗余计算机系统的运行进行了模拟验证。关键字：可靠性、可用性、双机热备、多机热备、马尔科夫（Markov）模型、Monte Carlo仿真。在进行冗余计算机系统架构设计之前，我们必须先提出一个科学、合理的系统可用性指标。过低的可用性指标会导致系统故障率较高，但过高的可用性指标又会增加系统设计的复杂度。
系统的整体可用性设计成多少比较合理？
通常来说，“5个9”是IT业公认的系统（设备）可用性指标，如：EMC存储、HP3PAR存储和HP的Nonstop设备等都以5个9的高可用性作为产品卖点进行宣传，“5个9”的可用性指标相当于系统每10年发生一次60分钟的计划外停机事件（60分钟/10年=6分钟/年=99.999%的可用性），这一数值远高于我国（甚至世界）证券期货行业的实际水平。
本文假设IT系统的整体可用性指标设计为99.999%。
典型的交易所IT系统一般会由多个关键子系统以串联方式组成，如：前置、排队机、撮合、资金、行情、结算子系统等。任何一个子系统出现故障，都会导致IT系统对外服务出现异常。假设IT系统是由5个关键子系统以串联方式组成的，那么每个子系统的可用性必须达到6个9，才能保证IT系统的整体可用性指标（99.9999%5=99.999%）。
很显然，就单机而言，其可用性指标根本达不到6个9的要求，必须通过多机热备冗余的方式来提高可用性。显而易见，冗余设备数量越多，系统因故障而彻底停止运行的可能性就越低。但是对于要求主备机数据同步的计算机系统来说，可用性并不一定越高，因为主备同步系统要求数据零丢失，即主机与备机之间必须进行数据相互确认与应答之后才能继续工作。如果其中一台设备发生故障，其他设备会反复确认，确定此设备无法正常运行之后才会继续工作或进行主备切换，后文中我们统一将此数据确认的过程称为主备切换过程，在主备切换过程中，系统将暂时停止对外服务。
因此当冗余设备数量增加时，设备发生故障的概率（总次数）也会随之增加，系统发生主备切换的次数也会增加，进而导致系统发生切换（会暂时停止对外提供服务）的时间也累计增加，从而降低了系统的可用性。
如何科学的选择冗余设备的数量，在既满足系统高可用性要求的同时，又能维持较低的系统复杂度，是本文的主要目的。
本文对冗余计算机系统可靠性的计算采用马尔科夫（Markov）模型建模的方法，因为计算机的故障发生时间一般服从指数分布，具有无记忆性，正好满足Markov模型应用的一个重要条件，而且Markov模型具有简单直观、易于理解的优点。本文给出了由Markov模型计算出的多机热备系统的可靠性公式并通过仿真模拟的方法进一步验证了此公式的正确性。
本文的主要结构如下：首先定义了计算机系统的可靠性指标（第二章），然后利用Markov模型对计算机系统的可靠性进行分析,其中包括理论计算和实证分析（第三章），最后通过仿真模拟的方法验证了结论的正确性（第四章）。可靠性是指系统在规定条件下和规定时间内完成规定功能的能力。在本文中，系统的可靠性是指计算机系统能够正常工作的能力。这里介绍几个实际中常用的指标:

2.1平均无故障、修复、主备切换时间

平均无故障时间(MTTF): 对于单个设备来说，平均无故障时间是指单个设备的两次故障间的平均正常工作时间[1]。MTTF通常与设备产品类型有关，如：网络设备、服务器设备、存储设备在产品设计上，MTTF就会有很大差异，存储设备的MTTF是目前公认最长的IT设备。
对于多节点冗余计算机系统来说，平均无故障时间是指系统两次彻底停止运行期间的平均正常工作时间。
平均修复时间（MTTR）：对于单个设备来说，平均修复时间是指单机从发生故障到恢复正常工作所用的平均时间。MTTR在实际工作中包括：故障的发生到被发现、维护团队到场、备机检查（或故障定位、备件到场、更换、补丁升级等）、决策、等待合适的变更窗口启用备机（或修好的设备）等流程的相应时间总和。
对于多节点冗余计算机系统来说，平均修复时间是指系统从停止运行到恢复运行所用的平均时间。
平均主备切换时间（MTTS）：是指在主备数据同步的冗余计算机系统中，系统发生主备切换所需的时间。MTTS通常会有30-60秒的时间，这期间系统会因主备机切换（备机需进行数据同步、状态切换等）或数据反复确认而暂时停止对外服务。
由于计算机设备发生故障是偶然独立的事件，具有无记忆性，即机器工作一段时间后，仍然如同新的机器一样，不影响以后的工作寿命。因此，在不考虑设备的疲劳、磨损、腐蚀、蠕变等情况下，我们假设单机的MTTF、MTTR、冗余计算机系统的MTTS分别服从参数为λ、μ、ν的指数分布，λ表示故障率，μ表示修复率，ν表示主备切换率，其中λ= 1/MTTF，μ=1/MTTR，ν=1/MTTS。

2.2可靠性

可靠性R(t)：是指单机在一定时间内可以正常工作的概率。典型指数分布类型的可靠性函数R(t)为：



单机工作的时间t越长，可靠性R(t)越低。

2.3可用性与不可用性

这两个指标用来表征系统无故障运行时间和总时间的关系,其定义为:对于主备数据同步的冗余计算机系统：
系统平均运行总时间 = 系统平均无故障时间 + 系统平均修复时间 + 系统平均主备切换时间，因此



本文主要使用可用性A来衡量多节点冗余计算机系统的可靠性。3.1马尔科夫（Markov）模型简介

本文采用Markov模型对系统可靠性进行分析研究，这种模型不但易于理解而且建模相对简单，很适合描述分析具有计算机容错系统的状态转移过程[3][4]。
Markov模型的过程定义如下：
过程{X(t),t≥0}称为连续时间的Markov过程，如果对一切s,t≥0, 非负整数i, j, x(u), 0≤u≤s,有


即已知现在时刻s时的状态和过去的一切状态的条件下，将来时刻t+s的状态只依赖现在的状态而与过去独立。这是Markov过程的最重要的性质，可以理解为系统的“将来”情况与“过去”的情况是无关的。此外若有P(X(t+s)=j|X(s)=i)与s无关，即系统状态转移的条件概率只与时间间距t有关，而与起始的时刻s无关，则称连续时间马尔可夫过程是平稳或齐次的。
由于单机的正常工作时间和故障修复时间均服从指数分布，具有无记忆性，所以系统在各个状态之间的游走是无记忆的，设备“将来”的正常工作时间与“过去”发生故障的次数、故障发生时间等情况无关，因此多节点冗余计算机系统是平稳的连续时间Markov过程。

3.2主备异步系统的Markov模型与系统可用性的计算方法

接下来我们首先考虑主备异步系统的Markov模型。主备异步系统与同步系统的区别是主备异步系统无需进行数据确认，主机通过可靠多播的方式将数据传送给备机并假设备机中至少有一台正确接收到了此数据，再由此备机将数据同步到其他备机，NasdaqOMX的Genium Inet系统中的重绕机Rewinder就起到此功能。因此，在主备异步系统中，无需考虑主备切换时间。
我们首先做如下假设：
（1）单机发生故障是独立统计的，无故障运行时间与故障修复时间分别服从参数为λ和μ指数分布，λ为单机的故障发生率, μ为修复率，其中故障发生率是指单位时间内单机发生故障的概率，也称速率。
（2）单机故障能被立刻检测出来，并得到修理，且机器的故障总是可修的，即故障的检测率和修复成功率都为100%。

3.2.1主备异步模式下双机热备系统的Markov模型与系统可用性

主备异步模式下双机热备系统的Markov模型共有三个状态：
状态0： 两台机器均能正常工作
状态1： 两台机器中有一台不能正常工作
状态2： 两台机器均不能正常工作
系统状态转移图如下：
在状态0时，系统以2λ的速率向状态1移动，这是因为一台机器发生故障的速率为λ，则两台机器同时工作，其中一台发生故障的速率为2λ；在状态1时，系统可以以λ的速率向状态2移动，表示在一台机器发生故障的同时，另一台机器也发生了故障，也可以以μ的速率向状态0移动，表示这台机器以速率μ被修复；在状态2时，两台机器均发生故障，因此其中一台被修复的速率为2μ。此外，系统在状态0，1时均能正常工作，是可用的，只有在状态2时，是不可用的。
系统可用性A的计算方法如下：
系统可用性A是根据马尔可夫平衡方程计算的。马尔可夫平衡方程是指系统进入状态i的速率和系统离开状态i的速率相等，即


其中P_i为系统在状态i停留的时间占总时间的比率，q_ij为系统从状态i转移到状态j的速率, i,j=0,1,2。
转移速率矩阵为


因此根据马尔科夫平衡方程（4），我们得到以下几个等式：
状态0： 2λP0=μP1
状态1： (μ+λ) P1=2λP0+2μP2
状态2： λP1=2μP2
并且由于系统在所有状态停留的总概率为1， 因此P0+P1+P2=1。 解得


因此主备异步模式下双机热备系统的可用性


===3.2.2===主备异步模式下多机热备系统的Markov模型与系统可用性
主备异步模式下三机热备系统的Markov模型共有四个状态：
状态0： 三台机器均能正常工作
状态1： 三台机器中有一台不能正常工作
状态2： 三台机器中有两台不能正常工作
状态3： 三台机器均不能正常工作
系统状态转移图如下：


图2. 主备异步模式下三机热备系统的状态转移图
同样根据马尔科夫平衡方程（4），我们得到以下几个等式：
状态0： 3λP_0=μP_1
状态1： (μ+2λ) P_1=3λP_0+2μP_2
状态2： (2μ+λ) P_2=2λP_1+3μP_3
状态3： λP_2=3μP_3
并且由于系统在所有状态停留的总概率为1， 因此P_0+P_1+P_2+P_3=1。 解得


因此主备异步模式下三机热备系统的可用性


以此类推得到主备异步模式下n机热备系统的Markov模型共有n+1个状态：
状态0： n台机器均能正常工作
状态1： n台机器中有一台不能正常工作
状态2： n台机器中有两台不能正常工作
⋮
状态n： n台机器均不能正常工作
系统状态转移图如下：


图3. 主备异步模式下n机热备系统的状态转移图
同样根据马尔科夫平衡方程（4），我们得到以下几个等式：
状态0： nλP_0=μP_1
状态1： (μ+(n-1)λ) P_1=nλP_0+2μP_2
状态2： (2μ+(n-2)λ) P_2=(n-1)λP_1+3μP_3
⋮
状态n： λP_(n-1)=nμP_n
并且由于系统在所有状态停留的总概率为1， 因此P_0+P_1+P_2+⋯+P_n=1。 解得


因此主备异步模式下n机热备系统的可用性


由上述n机热备系统的可用性公式可知，冗余设备的数量n越多，系统可用性越高。需要注意的是，上述结论只适用于主备异步的冗余计算机系统，对于主备同步的冗余计算机系统，结论则不然。

3.3主备同步系统的Markov模型与系统可用性的计算方法

主备同步系统要求数据零丢失，即主机与备机之间必须进行数据相互确认与应答之后才能继续工作。当主备机都正常工作时，数据确认与应答的过程是十分迅速的；当备机发生故障时，便无法应答主机发送的数据确认信息，这时主机会暂停对外服务并反复向备机发送数据确认信息，直到备机应答或时间超过规定限制才继续工作，通常的应答等待时间设置为30-60秒，这时由于主机会暂停对外服务，所以系统处于不可用的状态；当主机发生故障时，备机接收不到主机发送的数据信息，便会反复向主机确认，同样等待一段时间之后，如果主机还没有应答，备机会取代主机，即完成主备切换。我们将上述数据确认与主备切换的过程统称为主备切换过程，所需时间为主备切换时间，在此时间内，系统是不可用的。这里，假设主备切换时间与无故障运行时间、故障修复时间一样，服从指数分布，参数为ν，ν为主备切换速率。
在3.2中介绍的主备异步系统的Markov模型的基础上，加入主备切换状态，从而得到主备同步系统的Markov模型。

3.3.1主备同步模式下双机热备系统的Markov模型与系统可用性

主备同步模式下双机热备系统的Markov模型共有四个状态：
状态0： 两台机器均能正常工作
状态1^’： 进入状态1前的主备切换状态
状态1： 两台机器中有一台不能正常工作
状态2： 两台机器均不能正常工作
系统状态转移图如下：


图4. 主备同步模式下双机热备系统的状态转移图
系统从状态0转移到状态1，必须先经过状态1'，这是由于在主备同步系统中，任意一台设备发生故障，都必须经历主备切换状态。在状态1和1^’，系统都有λ的速率向状态2移动，μ的速率向状态0移动，这与主备异步系统的Markov过程相同。
同样根据马尔科夫平衡方程（4），我们得到以下几个等式：
状态0： 2λP0=μ(P1+P1')
状态1^’： 2λP0=(λ+μ+ν) P1'
状态1： (μ+λ) P1=νP1'+2μP2
状态2： 2μP2=λ(P1+P1')

并且由于系统在所有状态停留的总概率为1， 因此P0)+P1')+P1)+P2)=1。 解得


由于在主备同步系统中，主备切换状态时系统也是不可用的，所以双机热备系统在状态1^’和状态2都是不可用的，此时系统的可用性为


3.3.2主备同步模式下多机热备系统的Markov模型与系统可用性

主备同步模式下三机热备系统的Markov模型共有六个状态：
状态0： 三台机器均能正常工作
状态1'： 进入状态1前的主备切换状态
状态1： 三台机器中有一台不能正常工作
状态2'： 进入状态2前的主备切换状态
状态2： 三台机器中有两台不能正常工作
状态3： 三台机器均不能正常工作
系统状态转移图如下：


图5. 主备同步模式下三机热备系统的状态转移图
三机热备系统进入状态1后，与双机热备系统十分类似，因此从状态1转移到状态2之前，也需要经历一个主备切换状态2^’。
同样根据马尔科夫平衡方程（4），我们得到以下几个等式：
状态0： 3λP0)=μ(P1)+P1'))
状态1^’： 3λP0)=(2λ+μ+ν)P1')
状态1： (μ+2λ)P1)=νP1')+2μ(P2+P2')
状态2^’： 2λ(P1)+P1'))=(λ+2μ+ν) P2')
状态2： (2μ+λ)P2)=νP2')+3μP3)
状态3： 3μP3)=λ(P2)+P2'))
并且由于系统在所有状态停留的总概率为1， 因此P0)+P1')+P1)+P2')+P2)+P3)=1。 解得


三机热备系统在状态1^’、状态2^’和状态3都是不可用的，此时系统的可用性为


同理可得主备同步模式下n机热备系统的Markov模型共有2n个状态：
状态0： n台机器均能正常工作
状态1^’： 进入状态1前的主备切换状态
状态1： n台机器中有一台不能正常工作
状态2^’： 进入状态2前的主备切换状态
状态2： n台机器中有两台不能正常工作
⋮
状态n： n台机器均不能正常工作
系统状态转移图如下：


图6. 主备同步模式下n机热备系统的状态转移图
同样根据马尔科夫平衡方程，我们得到以下几个等式：
状态0： nλP0=μ(P1+P1')
状态1^’： nλP0=((n-1)λ+μ+ν)P1'
状态1： (μ+(n-1)λ)P1=νP1'+2μ(P2+P2')
状态2^’： (n-1)λ(P1+P1')=((n-2)λ+2μ+ν)P2'
状态2： (2μ+（n-2)λ)P2=νP2'+3μ(P3+P3)
⋮
状态n： nμPn=λ(Pn-1+Pn-1')
并且由于系统在所有状态停留的总概率为1， 因此P0+P1'+P1+P2'+P2+⋯+Pn=1。 解得


n机热备系统的可用性为


3.4 冗余计算机系统的可用性分析

3.2和3.3分别计算了主备异步系统与主备同步系统的可用性公式（7）和（10），接下来我们根据上述公式，进一步分析系统可用性A_n与冗余设备数量n之间的关系。
（1）由于λ/(λ+μ)An+1的最小值。


解得冗余设备数量的判定公式：


最佳冗余数量n的选择取决于参数选取的情况。

3.5 冗余计算机系统可用性的实例说明

举例说明，假设交易所总共有约500台左右的服务器，一年约有20台计算机发生停机故障，则单机一年内的可靠度为96%，因此可根据可靠度的计算公式得出单机的故障率λ=0.04年-1，单机的MTTF为25年；根据运维经验，假设设备的平均修复时间为24小时，主备机器的平均切换时间为30秒，则μ=365年-1，ν=1051200年-1。代入主备异步系统与主备同步系统的可用性计算公式（7）和（10），得到下表。

冗余设备数量主备同步系统可用性主备异步系统可用性

10.9998904220.999890422

20.9999999120.999999988

30.9999998860.999999999

40.9999998481.000000000

50.9999998101.000000000

60.9999997721.000000000

70.9999997341.000000000表1给出了在单机的故障率、修复率、主备切换时间不变的情况下，冗余设备数量对于系统可用性的影响。首先对比表格后两列，主备异步系统的可用性总是比主备同步系统的可用性高。然后对比表格的前两行，双机热备系统的可用性相比单机的可用性有了大幅度的提高，从4个9提高到了7个9的水平，随后随着冗余设备数量的增加，系统的可用性逐渐小幅减少。此时，冗余设备数量n=2，即双机热备时，系统可用性最高，与上文得出的判定公式（12）


的结论吻合。
当然，这是根据MTTF=25年，MTTR=24小时，MTTS=30秒的经验数值得出的结论，改变这些数值，结果可能会有所不同，但是系统可用性变化的大体趋势应该不变。将设备的平均修复时间改为48小时，代入主备异步系统与主备同步系统的可用性计算公式（7）和（10），得到下表。

冗余设备数量主备同步系统可用性主备异步系统可用性

10.9997808700.999780870

20.9999998760.999999952

30.9999998860.999999999

40.9999998481.000000000

50.9999998101.000000000

60.9999997721.000000000

70.9999997341.000000000从表2可以看出，主备同步系统的可用性随着冗余设备数量的增加先升高再降低的趋势没有改变，只是此时当冗余设备数量n=3，即三机热备时，系统可用性最高，同样与上文得出的判定公式（12）


的结论吻合。
以上结论都是基于本文理想化的模型得出的，实际系统架构设计过程中，冗余设备数量的选择，还要从具体的IT系统的运维情况和交易所能够承担的风险去考虑。例如交易所推出24小时连续交易，计算机系统将7×24小时连续运转，设备故障的维修必然会和系统的运行同步进行，在线维修极大的增加了人为失误所导致系统发生崩溃的风险（笔者单位曾发生过几次在修复故障设备时，维修人员无意碰到其他设备的网线，导致其他设备出现网络中断），如果交易所想尽量避免这种风险，三机热备可能会是更为稳妥的选择（目前银行的核心业务基本上都采取3机以上的冗余方案）。仿真法是评价计算机系统可靠性的一种常用方法[2]，通过在软件中模拟计算机系统的运行过程得到评估结果，评估的时间周期很短，复杂度低。本章节主要通过仿真法来验证系统可靠性计算公式的正确性。
在仿真法中，我们依然采用Markov模型来描述计算机系统的运行情况，并借鉴了Monte Carlo仿真的思想。这主要体现在两个方面： 一方面对故障发生和修复数据的采样上，采用了频数代替频率的思想，把随机发生的故障和修复的时间变量认为服从某种分布，用服从这种分布的随机变量模拟计算机系统的运行。另一方面，我们进行了多次反复的仿真，统计大量的数据来消除所采集样本的随机性，逼近实际系统的真值。本文所有的仿真数据是由统计软件R编写的程序模拟得到的。
以下简要描述主备同步的双机热备系统的可用性模拟方法：
（1）当系统在状态0时，将以λ的速率转移到状态1^‘，系统在状态0停留的时间（转移所需的时间）t_0服从参数为2λ的指数分布。
（2）当系统在状态1’时， 有三种选择：以μ的速率转移到状态0，以ν的速率转移到状态1或者以λ的速率转移到状态2，此时程序会生成3个服从指数分布的随机变量x0, x1, x2分别代表系统向状态0，1，2转移的时间，其中哪个时间最短，就意味着系统向哪个状态转移成功。记录下此时间，记为系统在状态1‘停留的时间t1’ 。
（3）当系统在状态1时，有两种选择：以μ的速率转移回状态0，或者以λ的速率转移到状态2，同步骤2类似，程序会生成两个服从指数分布的随机变量x0,

x2分别代表系统向状态0，2转移的时间，其中哪个时间最短，就意味着系统向哪个状态转移成功。记录下此时间，记为系统在状态1停留的时间t1。
当系统在状态2时，将以2μ的速率转移到状态1，系统在状态2停留的时间t_2服从参数为2μ的指数分布。
使系统在各个状态间转移10000次，记录下系统在每个状态停留的总时间T0、T1‘、T1、T2，则可用性
A=1-(T1’+T2)/(T0+T1‘+T1+T2)。
为了使模拟的结果更可靠，我们进行100次模拟，得到系统可用性的均值和样本方差


以及可用性与理论值之间的相对误差
E=|A-A'|/A
下表为MTTF=25年，MTTR=24小时，MTTS=30秒时，通过理论计算和仿真模拟得到的主备同步系统的可用性结果比较。

冗余数量可用性（理论计算）可用性（仿真模拟）样本方差相对误差

10.9998904220.9998904225*10-102*10-9

20.9999999120.9999999125*10-103.6*10-8

30.9999998860.9999998864*10-101.5*10-11从表3看出，理论计算与仿真模拟结果的相对误差为〖10〗^(-8)量级，即用仿真法得到的系统可用性数值与用本文中推导的统计计算公式计算的理论值非常接近，这说明了本文所建模型的正确性和仿真方法的有效性。本文采用连续时间的马尔可夫模型对多节点冗余计算机系统的可靠性进行建模分析，推导出了多机热备系统可靠性的数学计算公式。对于主备数据异步的多节点冗余计算机系统，系统可用性随着冗余设备数量的增加而不断提高；但对于主备同步的多节点冗余计算机系统，系统可用性随着冗余设备数量的增加呈现先迅速上升再缓慢下降的趋势。本文还推导出了使得系统可用性最高的冗余设备数量的判定公式，为交易所到底是选择几个节点实现热备提供了科学的理论依据，各交易所可根据自身的系统架构、IT运维响应时间及服务器可靠性数值进行决策。同时本文还采用了统计学中Monte Carlo仿真的方法对主备同步的多节点冗余计算机系统进行了可靠性测评，对仿真结果的分析验证了我们所建可靠性模型的正确性和仿真方法的有效性。

参考文献：
[1] Dan Byron, “Increasing Availability at the Cost of Reliability.”
[2] 刘逢清，“容错计算机系统的可靠性建模和分布式仿真”，南京邮电大学学报（自然科学版）， 2008，28(5)。
[3] 刑传星.，“VTS双机热备系统的可靠性研究和应用”，大连海事大学。
[4] 高继祥、郑俊杰，“双机热备计算机联锁系统可靠性与安全性指标分析”，北方交通大学学报，2008年第5期。



免责声明



本公众号内容仅供参考。对任何因直接或间接使用本公众号内容而造成的损失，包括但不限于因有关内容不准确、不完整而导致的损失，本公众号不承担任何法律责任。如有问题请反馈至tech_support@sse.com.cn。



--------------------------
上海证券交易所为证券公司、基金管理公司等市场参与者及相关行业机构提供交易技术支持与服务，包括日常交易技术支持、技术交流研讨、市场调查反馈、证券信息技术知识库、测试等服务。



点击"阅读全文"了解详情

    关注 上交所技术服务