探索对等网维护数据副本一致性的乐观复制技术
摘要：
在对等网环境中，保持数据对象的多个副本可极大提高数据的可靠性和访问效率，但同时需要维护副本数据的一致性。乐观复制在保证数据一致性的同时放松了对操作顺序的要求。提出了数据乐观复制系统形式化模型，应用模型推导了数据达到一致的基本条件，提出基于处理操作的最优化算法，并对实际应用中可能出现的问题提出改进方法。
关键词： 对等网 乐观复制 依赖关系
1 引言
在对等网环境中使用复制技术将数据保存到多个节点可极大的提高数据的可靠性与访问效率。即使节点失效，数据仍可从备份节点读取，从而使数据更加可靠。通过有选择的访问延迟较小的节点，也提高了数据的访问效率。但数据可靠性及访问效率的提高是以需要保持数据副本的一致性为代价的，在实际应用中需要在可靠性、访问效率与数据副本一致性之间做出权衡。
传统的复制技术在数据副本间保持单拷贝一致性，Primary Copy、Tokens等算法是其典型代表。这些算法的共同特点是阻止对处于不一致状态的数据副本的访问。由于保持数据副本单拷贝一致性的代价过大，因此这些算法只能在高速、低延迟的局域网环境中使用。对许多具体应用而言，单拷贝一致性过于严格，在不同节点对相同数据对象副本的冲突访问实际上是很少发生的，因此可以通过放松对数据副本一致性的限制来提高性能，与传统复制技术对应的乐观复制技术就采用了这种思想。乐观复制不要求各数据副本时刻一致，因此适合在广域网及移动环境下使用，节点高度自治，可独立处理查询和更新操作，数据副本发生冲突时可使用冲突解决策略使数据恢复一致。乐观复制已成功应用在异步协作系统Bayou，点对点复制文件系统Ficus等系统上。
由于目前存在的乐观复制协议缺乏普遍的抽象模型，而乐观复制协议本身较为复杂，导致不同的乐观复制协议的无法进行相互比较，进而也限制了更好的乐观复制协议的提出。针对这种情况，本文提出一个基于传输操作的数据乐观复制模型，应用该模型推导了数据副本达到一致的基本条件，即为使数据副本达到一致乐观复制协议应满足的基本条件，最后提出一个使数据达到一致的操作最优处理算法。
2 基于传输操作的数据乐观复制模型
将某用户在一段时间内对节点的一系列连续访问操作称为一次会话，会话包含一个或多个操作，操作提交到节点执行，并可能改变节点的数据内容。提交操作的节点称为操作的主节点。操作分查询操作与更新操作两种类型，查询操作对数据对象进行只读操作，更新操作对数据对象进行修改、追加或删除操作。为使各数据副本达到一致，提交到主节点的更新操作必须传输到所有节点且执行完成，而查询操作只需在主节点提交并执行。为简化模型又不失一般性，假设一次操作只对一个数据对象进行，且节点每次只执行一个操作。
数据乐观复制系统用五元组表示，其中为节点集，O为数据对象集，为对象操作集，为上的顺序关系，(TSEPONNPSEPT为上的依赖关系。在对等网环境中，受软硬件摘要： 在对等网环境中，保持数据对象的多个副本可极大提高数据的可靠性和访问效率，但同时需要维护副本数据的一致性。乐观复制在保证数据一致性的同时放松了对操作顺序的要求。提出了数据乐观复制系统形式化模型，应用模型推导了数据达到一致的基本条件，提出基于处理操作的最优化算法，并对实际应用中可能出现的问题提出改进方法。
关键词： 对等网 乐观复制 依赖关系
1 引言
在对等网环境中使用复制技术将数据保存到多个节点可极大的提高数据的可靠性与访问效率。即使节点失效，数据仍可从备份节点读取，从而使数据更加可靠。通过有选择的访问延迟较小的节点，也提高了数据的访问效率。但数据可靠性及访问效率的提高是以需要保持数据副本的一致性为代价的，在实际应用中需要在可靠性、访问效率与数据副本一致性之间做出权衡。
传统的复制技术在数据副本间保持单拷贝一致性，Primary Copy、Tokens等算法是其典型代表。这些算法的共同特点是阻止对处于不一致状态的数据副本的访问。由于保持数据副本单拷贝一致性的代价过大，因此这些算法只能在高速、低延迟的局域网环境中使用。对许多具体应用而言，单拷贝一致性过于严格，在不同节点对相同数据对象副本的冲突访问实际上是很少发生的，因此可以通过放松对数据副本一致性的限制来提高性能，与传统复制技术对应的乐观复制技术就采用了这种思想。乐观复制不要求各数据副本时刻一致，因此适合在广域网及移动环境下使用，节点高度自治，可独立处理查询和更新操作，数据副本发生冲突时可使用冲突解决策略使数据恢复一致。乐观复制已成功应用在异步协作系统Bayou，点对点复制文件系统Ficus等系统上。
由于目前存在的乐观复制协议缺乏普遍的抽象模型，而乐观复制协议本身较为复杂，导致不同的乐观复制协议的无法进行相互比较，进而也限制了更好的乐观复制协议的提出。针对这种情况，本文提出一个基于传输操作的数据乐观复制模型，应用该模型推导了数据副本达到一致的基本条件，即为使数据副本达到一致乐观复制协议应满足的基本条件，最后提出一个使数据达到一致的操作最优处理算法。
2 基于传输操作的数据乐观复制模型
将某用户在一段时间内对节点的一系列连续访问操作称为一次会话，会话包含一个或多个操作，操作提交到节点执行，并可能改变节点的数据内容。提交操作的节点称为操作的主节点。操作分查询操作与更新操作两种类型，查询操作对数据对象进行只读操作，更新操作对数据对象进行修改、追加或删除操作。为使各数据副本达到一致，提交到主节点的更新操作必须传输到所有节点且执行完成，而查询操作只需在主节点提交并执行。为简化模型又不失一般性，假设一次操作只对一个数据对象进行，且节点每次只执行一个操作。
数据乐观复制系统用五元组表示，其中为节点集，O为数据对象集，为对象操作集，为上的顺序关系，(TSEPONNPSEPT为上的依赖关系。在对等网环境中，受软硬件的正确性，这些操作序列必定也都是正确的。 □上述定理表明为使复制系统最终一致，只需保证具有依赖关系的操作的执行顺序，无依赖关系的操作的执行顺序不会影响最终状态的一致性。
3 乐观复制模型的进一步讨论
下面主要针对不丢弃操作的情况进行讨论。在实际应用中，对象的操作一般包括Create、Read、Write和Delete四种类型，Read属于查询操作，Create、Write和Delete属于更新操作。对象的生命周期从Create操作开始到Delete操作结束。若两个操作访问同一数据对象，且至少有一个是更新操作，那么称这两个操作是冲突的。
假设对等网中的各节点使用Vector Clock标识操作的提交顺序。提交到相同节点的操作都可被Vector Clock定序，而提交到不同节点的操作可能无法由Vector Clock定序，将这些无法被完美定序的操作称为并发操作。属于同一会话的操作可由会话操作序号定序。将原子操作集及所有非并发的冲突操作定义为依赖关系T，如果操作属于同一原子操作集则定义及bTa，如果操作是非并发冲突的，则若定义反之定义。ba,aTbba,aSEbaTbbTa操作的状态分为四种类型：提交态，接受态，执行态和确认态。操作提交到主节点或从其它节点传送到本节点后即处于提交态。对提交到节点的操作，若中不存在该操作的并发冲突操作，那么该操作的状态将变为接受态。对处于接受态且不属于原子操作集的操作a，如果对，操作已在该节点执行，则将操作的状态变为执行态。若操作属于原子操作集，则需要原子操作集中的所有操作都传输到该节点且都无其它未执行的依赖操作的情况下才可将状态变为执行态。处于执行态的查询操作在节点执行完后状态将变为确认态，处于执行态的更新操作在主节点执行完且传输到当前节点集的所有节点并被接受，才可将其状态变为确认态，只有在操作处于确认态后才可将其从节点操作集中删除。PSaTbPSb,∈?b操作提交到节点后，如果在节点操作集有与其并发的冲突操作或操作本身不合理，那么操作将是不可接受的。这时需要节点间对操作进行协商，必要时还需将已执行的操作进行回溯。
操作在被所有节点接受前需进行缓存。使用操作依赖图表示操作间的关系。以操作为点，依赖关系为有向边，构造操作依赖图。若操作有则连接的有向边以为起点为终点。可从节点操作集生成一个或多个操作依赖图，同一操作依赖图中的操作都可用顺序关系定序。ba,aTbba,ab使用下述规则，去掉操作依赖图中的冗余边，并将原子操作集用一个复合操作代替，生成简化操作依赖图。
1) 将属于原子操作集用一个复合操作代替。如果为原子操作集中的操作，a为对应原子操作集的复合操作，那么对不属于该原子操作集的操作若有或则分别令bTa或。'ab'bTaTba'aTb2) 对不属于同一原子操作集的操作若有cba,,aTcaTb∧且或cTb两者之一成立，则若bTc那么去掉对应aTc的边否则去掉对应aTb的边。bTc例：下面是操作依赖图化简的例子，简化依赖图中的yx,为对应原子操作集的复合操作。
证明：设为节点的两个不丢弃操作的操作序列，它们均与节点操作集的所有简化依赖图无回路。假设与不等价，那么分别按执行后，节点至少有一个数据对象内容不同。因为只有更新操作才会改变数据对象内容，而更新操作必定满足依赖关系。由于操作序列与简化依赖图无回路，因此执行这些更新操作的顺序也相同，意味着数据对象在这两个操作序列作用下内容必定相同，与假设矛盾。
在不丢弃操作的情况下，为保证操作序列的执行是正确性，它与简化依赖图必定无回路。
定理2：在不丢弃操作的情况下，复制系统可达到最终一致当且仅当各节点执行的操作序列与其简化依赖图无回路。
证明：
充分性：由于各节点的更新操作集都相同，与简化依赖图无回路的操作序列都等价。由定理1可得复制系统可达到最终一致。
必要性：复制系统可达到最终一致，则在各节点执行的操作序列都等价，而为保证复制系统的正确性，这些操作序列必定与简化依赖图无回路。□4 复制系统数据一致最优化算法定理2表明只需保证操作序列与简化依赖图无回路，复制系统必可达到最终一致，而且不按操作的提交顺序执行也可使复制系统达到一致。定理2中的条件是在不丢弃操作的情况下，复制系统达到最终一致的基本条件，据此提出一个满足该条件的操作处理算法，它是在上述条件下使复制系统达到最终一致的最优化算法。
算法：
void OpState(Operate newOp) //状态处理
{SetState(newOp, SUBMIT); //置提交态
if(newOp.node==CurrentNode) //置接受态
SetState(newOp,ACCEPT);else{if(!HaveConflict(newOp)) //是否存在并发冲突操作
SetState(newOp,ACCEPT); //不冲突置接受态
else{negotiate(newOp); //存在冲突则需进行协商
return;}
}
if(!CheckDependence(newOp)){ //是否缺少依赖操作
SetState(newOp, RUNABLE); //置执行态
ResetState(newOp,RUNABLE);//将依赖新操作的操作置为可执行态}
}
void OpRun() //操作运行处理
{FindRunableOp(&Op); //查找可执行操作
Run(Op); //执行操作
SetState(Op, CONFIRM); //置确认态
}
上述算法不但可使复制系统具有最终一致性，而且最大限度的使用了节点接收到的操作的信息，不受操作提交顺序的影响，是在上述条件下使复制系统达到一致的最优化算法。
5 依赖关系的扩充
复制系统最终一致有时并不满足要求。例如，用户在一次会话中更新了某节点的对象，接着在另一次会话中从另一节点读取该对象，由于最终一致没有限定数据达到一致的时间，因此更新操作可能仍未传输到该节点，这将导致读出过时的数据。
针对这种情况，可对依赖关系T施加更严格的限制。例如，要求同一用户不同会话间的操作也受依赖关系的限制，即如果是同一用户属于不同会话的两个冲突操作，若则规定。依赖关系扩充后仍可使用上面的算法，但解决了同一用户不同会话间可能导致的奇异情况。vu,uSEvuTv6 总结与展望本文针对乐观复制协议缺乏普遍抽象模型的问题，提出了乐观复制系统普遍的形式化模型。使用依赖关系表示操作间的关系，研究了依赖关系对复制系统数据一致的影响，并推导了复制系统达到数据数据一致的条件，并提出了一种基于操作的最优化算法，最后针对实际应用中可能出现的问题提出了依赖关系扩充的方法。
随着分布式应用，尤其是移动环境下数据应用的迅速发展，数据乐观复制技术会有更为广阔的发展前景，而对乐观复制技术的研究也将变的越来越重要。
