面向分布式交互应用的事件完全序问题研究

李 永,陆 伟

(盐城师范学院 信息工程学院，江苏 盐城 224002)

1 概 述

随着计算机网络的飞速发展，各种计算机应用不再局限于单机的或独立的系统，而是通过网络进行连接，以分布式的形式开展各种应用，地理上分散的多个端用户端节点能够在一个共享的统一网络虚拟环境中通过分布式交互和协作完成特定任务。这类应用称为分布式交互应用(distributed interactive application，DIA)，是近年来的研究热点[1-4]。目前分布式交互应用主要体现在分布式虚拟环境、分布式交互仿真、协同设计与制造、军事仿真系统、网络在线游戏、视频会议等方面。

DIA中事件序一致性问题解决的好坏会直接影响其可用性，在DIA中所有参与同一应用的端节点应该具有实体状态的一致性和事件处理顺序的一致性。DIA中的事件一致性往往是有延时约束一致性，因此，良好的DIA一致性控制方法主要体现在两个方面：一致性和响应性。一致性能够保证DIA在功能上的正确性，实时响应性能够给用户良好的DIA体验。由于存在网络传输延迟，各节点间的事件消息不一定能及时到达，会产生消息序错乱等情况，进而导致理解歧义、违背期望、因果颠倒[5]等问题，严重影响交互应用的正常运行；并且一致性问题还会影响系统的公平性和正确性，使得最终应用得到的结果不可信；因此，能否有效解决交互应用中各节点间的一致性问题，已经成为了制约分布式交互应用系统进一步发展的关键。近年来，针对一致性问题的研究一直是DIA的热点，许多一致性控制方法相继提出。

Mauve提出了本地滞后方法[6-7]，事件在发送节点产生后要延迟一段时间才能在本地执行，其延迟时间最好不要小于发送节点和所有接收节点间通信延迟的最大值；该方法通过牺牲系统的响应能力来增强系统的一致性，是对一致性和响应性的折衷，故该方法受系统整体的通讯情况影响较大。Thomas提出了基于锁机制的同步技术[8]，该方法强制阻塞节点的时钟推进，为了避免了不一致现象的发生，当所有节点完成当前时间步的事件操作后才进入下一个时间步。Qin X提出了基于间距一致的延迟一致性[9-10]，对于系统中全局事件在各节点的延迟时间由接收节点决定；对于某个接收节点来说，其接收的全部来自异地的消息都延迟相同的时间，而发送节点在发出事件后在本地不经过延迟立即执行，使系统各节点获得较好的响应能力，但该方法会造成不一致现象的发生。例如，如果两个节点同时向对方发送消息，由于发送方在发送消息后不延迟直接执行该事件，因此两个消息在这两个节点上的执行顺序刚好相反。总之，该方法采用只延迟异地事件而不延迟本地事件的方法来提高系统的响应性，以牺牲系统功能来达到提高性能的方法，无法真正达到事件完全序一致性，会导致不一致现象的发生。Jefferson提出了Time warp[11]，DIA节点对接收到的事件立即执行，当出现不一致时，就通过回滚操作纠正DIA的错误；该方法在网络条件不好时性能很差。Roberts提出了预测时间管理技术[12]，在DIA事件发生前对其进行预测，并通知其他节点该事件即将发生的时间和内容，当预测准确时该技术能够提高系统的性能；当预测错误时，执行回滚操作纠正错误的结果。但只有少数DIA事件能够预测，且预测准确率低[13]。

综上，已经提出的许多DIA一致性控制方法，在一定程度上能够满足DIA的需求，但由于DIA一致性问题本身的难度和复杂性，针对DIA一致性问题的研究还有很大的探索空间。文中研究的目的是在确保DIA事件完全序一致性的前提下，提高系统响应性，增强DIA的用户体验。提出了面向DIA的基于周期采样和事件序列号的一致性控制方法(consistency control method based on periodic sampling and event sequence number，CCM_SE)，CCM_SE包括周期采样和事件序列号机制两个方面，其中周期采样用来确保DIA的一致性，事件序列号机制用来及时确定事件的可处理时刻，以提高DIA事件的响应性。

2 DIA事件完全序一致性问题描述

在DIA中，地理上分散的节点通过网络进行连接，不同节点间事件的发生只能通过消息的发送、传输、接收和提交等实现节点间的交互。消息主要由两部分构成：事件内容和一致性控制信息。对事件消息处理的关键步骤是确定节点上接收的事件消息何时被提交执行，接收事件的DIA节点通过处理接收到消息的一致性控制信息，确保事件能够在该节点以正确的顺序执行。

在DIA中发生在两个不同节点上的事件如何排序，如何判断某个事件当前是否可以提交处理是非常关键的。由于网络传输时延的异构，不同DIA节点接收到事件的顺序是不一样的，一个DIA节点显然不能把事件的接收顺序作为处理顺序，也不能将已接收到的最小时间戳的事件作为当前需处理的事件，因为它无法判断是否有更小时间戳事件仍在网上传输，还未接收到。为了突出文中的研究内容，这里在时钟同步的前提下研究事件完全序一致性问题。CCM_SE采用统一时钟来刻画不同节点上事件发生的时间，维护事件间的先后顺序。同时，进一步结合事件序列号机制及时确定事件的可处理时刻，提高DIA的响应性。CCM_SE事件完全序一致性问题描述如下：

V表示DIA内节点的集合；E表示DIA中事件的集合。

对于任意的事件em∈E，则g(em)表示事件em的产生节点；R(em)表示能够接收到事件em的节点集合；F(em)={g(em)}∪R(em)表示可感知到事件em的节点集合。

对于任意的节点vi,vj∈V，则tgi(em)表示事件em在vi上的产生时间；trj(em)表示节点vj接收到事件em的时间；tej(em)表示事件em在vj上开始执行的时间。dij表示节点vi,vj∈V间的通信延时。

在DIA中，节点间只能通过收发消息来通信，消息传输延迟的动态性使事件的自然先后关系在各个节点失去了必然性。因此，针对分DIA中的事件定义一种排序关系，即“发生在先”关系，用于描述真实世界中的因果事件先后关系[14]。

定义1：“发生在先”关系，满足下面的两个条件之一。

(1)若a、b是同一DIA节点上发生的两个事件，且a在b之前发生，则a→b；

(2)若a是一个发送消息事件，b是另一个DIA节点相应的接收消息事件，则a→b。

对于不同于a、b的任意事件c，由“happened before”发生在先关系，可以得到：若a→b且b→c，则a→c。

定义2：设em、en是DIA中的两个事件，若em、en满足(em→en)∧(em→en)，则称em、en是DIA中的两个并发事件，记为em‖en。

定义3：事件完全序一致性，即DIA中不同节点按相同的顺序执行事件：

∀em,en∈E;vi,vj∈F(em)∩F(en);

tei(em)≤tei(en)→tej(em)≤tej(en)

(1)

定义4：事件开始执行时间一致性，即任意一个事件在不同节点上的开始执行时间都相同。

∀em∈E;vi,vj∈F(em);tei(em)≤tej(em)

(2)

事件开始执行时间一致性是要求最为严格的一致性。

定义5：事件的响应时间，即事件从触发到开始提交执行的间隔时间。

∀em∈E;vi=g(em);rti(em)=tei(em)-tgi(em)

(3)

定义6：节点的响应时间，即某个节点上产生的所有事件的响应时间的平均值。

∀em∈E;vi=g(em);rti=avg[tei(em)-tgi(em)]

(4)

定义7：系统的响应时间，即系统中所有节点响应时间的平均值。

(5)

3 周期采样机制

针对DIA的事件完全序一致性控制问题，提出的事件完全序一致性控制方法CCM_SE主要包括周期采样机制和事件序列号机制。下面介绍CCM_SE的周期采样，并分析其一致性。

在CCM_SE中，各节点采用时钟同步机制进行时钟同步，使得不同DIA节点上触发的事件可以通过事件时间戳来确定事件的发生顺序。CCM_SE的周期采样机制把DIA中的时间划分为固定的时间长度T，即采样周期。采样周期T表明多长时间更新一次DIA的状态，采样周期的频率1/T决定DIA状态的更新速度。在实际应用中，以25帧每秒的频率(T=40 ms)更新DIA状态对用户来说已经在视觉上很连贯了[15]。这里通常取固定的T(T≤40 ms)。CCM_SE的周期采样机制为了保证一致性，一个DIA节点在第i个采样周期[ti-T,ti]之内，提交执行发生在[ti-T-Δ,ti-Δ]时间间隔内的所有事件。CCM_SE的周期采样机制的原理如图1所示。

图1 CCM_SE周期采样机制原理

图1中的三个DIA节点A、B、C，节点A在时间time1触发了事件eA1，节点B在时间time2触发了事件eB2，节点C在时间time3和time4触发了事件eC3、eC4，节点B在第i个采样周期[ti-T,ti]将按序提交执行发生在[ti-T-Δ,ti-Δ]时间间隔内的事件eA1、eB2和eC3，对于已接收到的eC4将不会执行。

在CCM_SE的周期采样机制中，为了抵消DIA节点间因网络延时不同造成的不一致性影响，一个DIA节点在第i个采样周期[ti-T,ti]内，提交执行发生在[ti-T-Δ,ti-Δ]时间间隔内的所有事件。可见DIA节点触发一个事件后，不是立即执行该事件，而是延迟一定时间Δ后再提交执行。事件滞后时间Δ后再提交执行，可以消除或显著减小所有DIA节点间的不一致现象。

下面利用上面对DIA事件完全序一致性问题的形式化描述和定义，分析CCM_SE的周期采样机制的一致性。

定理1：在CCM_SE的周期采样中，当Δ的取值满足式6时，CCM_SE的周期采样能够达到定义4中描述的“事件开始执行时间一致性”。

(6)

在CCM_SE的周期采样机制中，一个DIA节点在第i个采样周期[ti-T,ti]内，提交执行发生在[ti-T-Δ,ti-Δ]时间间隔内的所有事件。当Δ≥max{rti},vi∈V时，使得在周期[ti-T-Δ,ti-Δ]内发生的任何事件都能够被传输到所有接收节点，从而实现在能够感知某个事件的所有节点上，同时执行该事件，定理1得证。证毕。

“事件开始执行时间一致性”是要求最为严格的一致性。因此，周期采样机制能够实现DIA的事件完全序一致性。在CCM_SE的周期采样机制中，每个节点维护自己的DIA状态的改变，DIA状态的改变与事件的提交执行相对应。事件的推进是DIA的基础，它由“事件接收”和“事件处理”两个过程构成。CCM_SE的周期采样为了保证交互的正确性，一个DIA节点在第i个采样周期[ti-T,ti]内，提交执行发生在[ti-T-Δ,ti-Δ]时间间隔内的所有事件。

4 基于周期采样和事件序列号的一致性控制方法CCM_SE

针对DIA的事件完全序一致性问题，若只采用周期采样机制，在第i个采样周期[ti-T,ti]将按序提交执行发生在[ti-T-Δ,ti-Δ]时间间隔内的事件，该方法存在把所有的事件都滞后执行的缺点，即没有对接收到的事件进行判断是否可以及时提交执行。对一些已经接收到的满足可执行条件的事件，由于它们不是发生在[ti-T-Δ,ti-Δ]间隔内，而得不到执行。因此这里引入事件序列号机制，在周期采样机制中结合事件序列号来判定一个事件何时可以提交执行。

事件序列号机制主要用来判断来自同一个节点的两个事件是不是连续事件，即若节点vi接收到来自节点vj的两个事件ej1和ej2，需要判定是否在ej1和ej2之间vj是否触发了其他事件如ej3，只是由于网络延迟的原因，节点vi还没有接收到ej3。

若ei、ej分别是DIA节点vi、vj上产生的两个事件，产生事件的时间戳分别为ti、tj，且ti

定义8：DIA事件序列号。若把节点vi生成的第一个事件的序列号设置为1，把在节点vi发生的事件序列号为p的事件记为ei,p，则ei,p的下一个事件的序列号为p+1，该事件记为ei,p+1。

可见，同一节点vi上触发事件的先后关系可用事件序列号来描述。基于事件序列号可以判断vi在处理完ei,p后，是否能接着处理ei,q。

(1)若q>p+1，则在事件序列号为p+1,…,q-1的事件处理之前，不能处理ei,q；

(2)若q=p+1，则在vi上不存在时间戳为ti,r的事件ei,r，使得ti,p

定义9：DIA事件的属性除了包含物理操作，还要具有以下属性：

(1)产生事件的DIA节点；

(2)事件在DIA节点上产生时的事件序列号；

(3)事件在DIA节点上产生时的时间戳。

定义10：已处理事件的序列号向量。vi为任意一个DIA节点，其上已处理事件的序列号向量为(D1,D2,…,Dj,…,Dn)，其中，Dj,j=1,2,…,n表示从DIA节点vj传输到vi的事件中，vi已处理的最大事件序列号。

基于事件序列号机制可以及时判定一个事件是否可以提交执行，一个发生在[ti-T-Δ,ti-Δ]时间间隔的事件，并非一定要滞后在[ti-T,ti]内被提交执行。当然如果一个发生在[ti-T-Δ,ti-Δ]时间间隔的事件，在Δ取值比较小的情况下，会造成在[ti-T,ti]内仍然没有达到。此种情况，在采样周期末，可以对已接收到且未提交执行的发生在[ti-T-Δ,ti-Δ]时间间隔的事件进行提交执行，以便更新用户节点的状态，但同时将在以后的时间里对迟到事件的到来采用修复机制。对于DIA交互性控制修复机制的研究将在以后进行。

5 仿真模拟与分析

由于DIA的全部到全部路由具实时性、高带宽等特点，为每一个需要发送数据的DIA节点都以它为根构造一棵数据分发树，费用开销太大，而所有需要发送数据的DIA节点都基于单棵共享树进行数据分发树，又会造成流量集中，DIA延时无法保障。因此，文中采用多棵共享树来分发DIA数据，构造了基于多共享树的DIA全部到全部路由问题模型DARP，并提出了求解DARP问题的禁忌遗传算法DARP_TGA。

为了验证上面提出的DIA事件完全序一致性控制方法CCM_SE的有效性，需要确定仿真模拟的实验环境和相关参数的设置。这里采用通用的拓扑产生器Brite生成网络拓扑数据，模拟底层的物理网络，采用随机模型Waxman作为实验拓扑的生成算法，生成具有实际网络特点的拓扑图。在多组实验中，将提出的CCM_SE与文献[6-7]中的本地滞后(local lag，LL)以及文献[9-10]中的延迟一致性控制(delayed consistency，DC)在DIA事件不一致百分比和DIA平均响应时间(即定义5的“系统的响应时间”)上进行对比，得到的实验结果分别如图2和图3所示。

图2 CCM_SE的一致性控制效果

LL为了保证节点间的状态一致性，事件在发送节点产生后要延迟一段时间才能在本地执行，其延迟时间大小很难确定，因为DIA节点间通信延迟是动态的；LL通过牺牲系统的响应能力来增强系统的一致性，故该方法受系统整体的通讯情况影响较大，在DIA规模小和网络稳定的情况下，事件完全序一致性较好，但该方法事件平均响应时间不好。延迟一致性控制DC采用只延迟异地事件而不延迟本地事件的方法来提高系统的响应性，属于以牺牲系统功能来达到提高DIA响应性的方法，故事件平均响应时间较好，但通常DC无法满足消息序的一致性，会导致不一致的现象的发生。

由图2可知，由于DC无法保证事件发生的完全序关系，事件不一致现象相对较多；而文中提出的CCM_SE和LL的事件一致性控制较好，CCM_SE和LL在节点规模小时事件不一致百分比相近，但当节点规模增大时，由于LL由发送节点确定延迟值，受DIA网络的规模和网络延时的动态性影响较大，从而导致LL中事件不一致现象增多。由图3可知，CCM_SE和DC的事件平均响应时间相差不大，都远远好于LL的事件平均响应时间，其原因在于CCM_SE中引入了事件序列号机制，能够及时判定满足执行条件的事件尽快提交执行，而DC不延迟本地事件的执行，所以事件的事件平均响应时间小。

图3 CCM_SE的事件平均响应时间

6 结束语

在研究现状的基础上，提出了基于周期采样和事件序列号的DIA事件完全序一致性控制方法CCM_SE，CCM_SE包括周期采样机制和事件序列号机制两个方面。其中周期采样可以确保DIA的一致性；事件序列号机制可以及时确定事件的可处理时刻，一个发生在[ti-T-Δ,ti-Δ]时间间隔的事件，并非一定要滞后在[ti-T,ti]内被提交执行。仿真结果表明，该方法在确保DIA事件完全序一致的前提下，提高了系统响应性，增强了DIA的用户体验。