数据一致性算法-时间戳策略.pptx

数据一致性算法-时间戳策略北京信息职业技术学院|马东波主要内容12时间戳策略的定义时间戳的核心思想32逻辑时钟应用时间戳策略的定义时间戳策略在关系数据库中有广泛的应用,该策略主要用于关系数据库日志系统中记录事务操作,以及数据恢复时的Undo/Redo等操作。在并行系统中,时间戳策略有更加广泛的应用。从较高的层次来说,时间戳策略可用于SNA架构或并行架构系统中时间及数据的同步。时间戳策略的定义使用时间戳的策略将能够很好地解决这一问题。对时间戳策略进行改进,使其不依赖于任何单个的机器,也不依赖于物理时钟同步。该时间戳为逻辑上的时钟,并且通过时间戳版本的更新可以在系统中生成一个全局有序的逻辑关系。时间戳的核心思想假设发送或接受消息是进程中的一个事件,下面我们来定义分布式系统事件集中的先后关系,用"→"符号来表示,例如:若事件a发生在事件b之前,那么a→b。时间戳的核心思想下面我们通过图1说明系统中可能存在的事件先后关系。在图1中,纵向代表事件轴,虚线表示进程之间的消息通信。在该模型中,如果存在着一个从a到b的时间或消息的先后关系,那么a→b。时间戳的核心思想逻辑时钟现在将时钟引入到系统中。这里我们并不关心时钟值是如何产生的,它可以通过本地时钟产生,也可以为有序的数字。这里为每一个进程Pi定义一个时钟Ci,该时钟能够为任意一个事件a分配一个时钟值:Ci(a)。在全局上,同样存在一个时钟C,对于事件b,该时钟能够分配一个时钟值C(b),并且如果事件b发生在进程Pi上,那么C(b)=Ci(b)。时钟条件:如果对于事件a和事件b,a→b,那么C(a)<C(b)。事件a的逻辑时钟值小于事件b的逻辑时钟值并不意味着有a→b,因为可能事件a与事件b同时发生(见例3)。。逻辑时钟在图1中可以得到p2与q3同时发生,p3与q3也同时发生,那么这意味着p2与p3同时发生,但是这与实际情况相左,因为p2→p3。因此,我们给出下面两个限制条件。逻辑时钟现在可以进一步考虑下"时钟走表"的概念,若事件a发生在事件b之前,C(a)<C(b),例如C(a)=4,C(b)=7,那么在事件a和事件b之间存在4到5,5到6和6到7三个时间间隔。也就是说存在先后顺序的事件之间一定至少存在一个时间间隔。那么C1意味着,同一个进程中的两个事件之间一定存在至少一个时间间隔;C2意味着,每一条消息一定跨越了至少一个时间间隔。