快速,持续,稳定,傻瓜式
支持Mysql,Sqlserver数据同步

分布式数据库的数据版本合并

在线QQ客服:1922638

专业的SQL Server、MySQL数据库同步软件

众所周知,在分布式数据库系统中,为了避免对硬盘进行随机IO读写,通过插入新数据来替换数据的更新操作。同时,为了使数据库具有很高的容错性,通常在一致的哈希环上执行N个备份,因此这导致数据存在于不同的备份服务器中。然后在不同的时间,因为一致的散列环中可能存在停机节点,所以同一客户端的数据通常会在不同的时间分发到不同的服务器以访问数据,或者将不同的客户端请求散列到不同的服务器。用于处理,然后在不同服务器上对相同键值数据的更改将导致冲突。为了始终使用户能够随时随地写入数据,在同步所有备份服务器数据之前拒绝任何可能导致文件冲突的写入操作并不简单。因此,服务器上的同一密钥将有多个版本的数据记录。

要了解此问题,我们必须首先了解QNW模型。在所谓的QNW模型中,N表示如果有N台服务器备份相同的数据,R表示至少应同步R服务上的数据以确定要读取的数据量,W表示要写入输入数据时,有必要同步写入W服务器以考虑数据写入成功。需要说明的是,R和w是同步操作,R是同步读取R服务器,W是同步写入W服务器。当R + W> N时,可以确保数据的一致性。这个公式很容易理解。应该注意的是,当W N,则写入数据将以异步方式备份到其余N-W服务器。当W = N时,备份同步完成。此QNW需要考虑2个问题:

图片

\\ n

图1

备份同步冲突

例如,如下所示:

四个服务器1,2,3,4形成一个一致的哈希环,该环的方向为顺时针。 Count = 1作为原始数据存储在2、3、4上。假设我们定义N = 3,即3台服务器备份数据。选择不同的R和W决定服务器的读写特性,例如R = 1,W = 3,然后是可读取的最大值,如果W = 1,R = 3,则是可写入的最大值。如果R = 2且W = 2,则读写可用性相对平衡。

假设我们取R = 2和W = 2,则数据将异步同步到3个服务器(W \\ N)。有一个用户x(用户x在哈希环上的位置如图所示)可以对数据D(计数++)执行自我更新,应将自我更新分为两个步骤,第一步步骤是读取count的值,然后运行count = count + 1计算并写入服务器,一个是读取,另一个是写入),他首先读取数据D,得到count = 1,然后然后生成数据D1(计数= 2),然后服务器开始准备将D1(计数= 2)写入服务器3和4,然后数据D1将异步地同步到服务器1。当用户x完成读取和计算但尚未将数据实际写入服务器时,用户y还将对数据D(计数++)执行自更新更新,因为此时用户x尚未实际写入D1 (下划线表示尚未写入数据),则此时y连续读取两个服务器2、3(需要读取两次,R = 2,因为服务器1目前没有任何计数数据,因此)服务器R的计数中不能计入1的读数)在添加之前找到计数值并找到数据D(计数= 1),它将数据相加得到D2(计数= 2),然后准备添加它写并同步到三个服务器1、2和3。但是,当y准备写时,用户x的数据已完成写和同步,服务器1上的数据已更改,并且用户x生成的count = 2已到达服务器1。这样,由相同数据D的不同版本引起的写操作冲突为g在服务器上启动(最初,我的自添加操作是基于count = 1 = 2的版本执行的。)我应该不加思索地写数据,还是应该丢弃此写操作(因为我的自添加操作已更改,并且该操作似乎是非法的)?在理想的语义中,我们应该希望y更新的数据为count = 3,因为y的行为发生在x之后。

这种情况下的冲突是在数据异步同步时发生的,因此称为备份同步冲突

冗余读取冲突

写入数据时发生冲突。这样,不同版本的冗余备份将在读取数据时发生冲突。假设不存在上述写冲突,则在y执行自我添加操作之前,x的数据已更新为1,因此,当用户y读取数据D时,会从两个服务器1、2获得两个数据版本(尚未删除所有历史数据,并且已更新和添加的数据已添加到实际数据库中的数据记录中:count = 1(原始数据),count = 2(x改变)。那么哪个数据D是正确的呢?

冗余读取冲突也可能在同一台计算机上发生。为了在同一台计算机上修改相同的数据,为了避免随机的磁盘IO开销,通常将替换替换为附加,这也会引起冲突。

解决问题

想法1 Lamport 时间戳

对于冗余的读取冲突,自然的想法是为同一数据的不同记录版本打上时间戳,然后进行比较以查看哪个记录是最新的。针对上述问题,当用户y读取数据D时,发现了两个版本:count = 1(原始数据)和count = 2(x改变)。此时,count = 1的时间戳是系统创建的时间,count = 2的时间戳是x创建D1的时间。显然,count = 2比count = 1更新,因此在读取D时,count =2。这似乎没有问题。

对于备份同步冲突,时间戳似乎也起作用。当用户y准备写入count = 2时,他发现count = 2的数据已同步到服务器1,并且时间戳相对较新(x写入2的时间),并且在添加之前读取count =它自己。时间戳1相对较旧(创建系统时的时间戳),然后丢弃您这次所做的更新,并抛出更新异常以通知调用方。这不仅解决了写冲突,语义结果似乎也很理想(y写的比x更新,因此不应在旧数据库上更新,而应在x的基础上更新,系统抛出异常通知呼叫者,一旦收到异常用户的通知,用户就可以了解状态并进行适当的处理,或者呼叫者可以重新执行该操作,或者呼叫者可以根据其合理的逻辑进行操作。)

一切都是完美的,但是如果仔细考虑,上述想法仍然值得考虑。

在这里的时间戳,我们假设它应该是绝对时间,例如我们使用的GMT时间。但是实际上,绝对时间很难100%完全同步。服务器1上的绝对时间不能与服务器2上的绝对时间100%相等。由于服务器的CPU频率和线程负载不完全相同,因此您始终可以在适当的条件下找到它们在服务器上的绝对时间戳不相等。时间粒度。然后,基于绝对时间戳确定记录是新记录还是旧记录是不可靠的。怎么做?

因此,有Lamport时间戳算法。 Lamport时间戳算法使用相对时间戳。每个服务器都维护自己的时间戳。该时间戳是一个计数器(初始化为0)。对于每次事件或检查,计数器将增加1。 (这意味着每个检查点计数器加1,并且该检查点可以是任何事件。只要有一件事情需要用Lamport时间戳标记以测量相对时间,那么此事件就是一个检查点并将被标记带有Lamport时间戳)之间的时间间隔只是一个相对时间。在同一台计算机上,它可以很长也可以很短,具体取决于检查点之间的实际时间。不同服务器上的时间戳不具有可比性。只有同一服务器上的时间戳才能校准检查点顺序。当服务器1将数据发送到服务器2时,您需要将此时服务器1的时间戳附加到消息上并将其一起发送。如果此时服务器1的时间戳小于服务器2的时间戳,则服务2将标记数据。服务器2的Lamport时间戳(该值是服务器2上的当前最大计数值加1)。如果服务器1的时间戳大于服务器2的时间戳,则可以将服务器1 +1的时间戳用作服务器2的时间戳。换句话说,服务器2上的Lamport时间戳等于max(消息上的时间戳[代表发送消息时服务器1的时间戳],以及服务器2上当前可用的最大时间戳)+1。请看下面的图片:

 image

\ n;

图2

上面的图2显示了前面提到的备份同步的示例。冒号右边的数字是Lamport时间戳,左边是服务器1上的自我添加更新操作(自我添加分为四个步骤:a,b,c和d。读取,再次添加,写入再次,然后与其他服务器同步),右侧是服务器2上的自添加更新操作。蓝色节点表示发生冲突的节点。在h事件中,服务器2准备好写入数据D,但是它面对这样的数据:e:count = 1(原始数据); g:count = 2(由服务器1同步的数据)。 g的Lamport时间戳为5,e的时间戳为1,看来count = 2是最新数据(因为5> 1),我们应该基于count = 2进行添加。但是,实际上,您可以”可以这样想,请参见下面的图3。当e出现在a之前时,我们应该让count = 1增加。因此,基于同一台计算机上的Lamport时间戳,我们可以获得该计算机上所有事件的总顺序,但是对于不同的机器,Lamport时间戳不能用于比较时间序列,只能获得所谓的”部分序列”:如果C(a)> = C(b),则a不可能决定影响b(所谓的决策影响力是指a,b在一个方向上可以通过箭头到达的序列链中,并且a在b之前的位置,例如2,b影响c,影响g,但不能可以说b影响f,因为不能通过一个方向上的箭头到达这两个方向),例如,在图2中,i,i> g,i早于g,a nd g> d,g早于d,因此不要期望能够相应地确定新数据和旧数据。

但是有人可能会问,Lamport时间戳如何帮助同步备份冲突?实际上,此时间戳仅检测到数据版本已更改,但是只要我们能够检测到更改,我们就会知道数据已发生冲突(但是尽管我们不知道谁应该留下此冲突数据)。对于冗余的读取冲突,如果同一台机器上的数据发生冲突,我们可以自然地合并(此能力称为部分顺序能力),但是其中一个冲突的数据是另一台机器的备份,那么我们只能检测到该冲突,并且让用户处理其余的事情。 Lamport可以检测到冲突,但是没有合并大多数冲突的能力。

 image

\ n;

图3

想法2 :矢量时钟

我们可以改进Lamport算法吗?是否可以在一定程度上比较不同服务器之间的旧数据和新数据?答案是矢量

时钟。

矢量

时钟本质上是一个时间戳,但是此时间戳是一个向量。向量中的每个组件都代表一台服务器。每个服务器中的检查点只能添加到表示向量中其自身服务器的位。服务器之前和之后的相邻事件的向量

时钟只会在代表该服务器的时钟上有所不同。向量的具体介绍和解释请参考文献[2],[9],文献讲得很清楚。

每个事件都有一个向量

时钟,然后可以比较事件。如果事件1的向量时钟中的任何分量都小于或等于事件2的向量中的相应分量,则事件1的时间早于事件2的时间。这种关系称为”小于”。如果两个向量时钟之一大于向量1,另一个大于向量2,如果是这种情况,则两个事件将发生冲突,需要用户做出合并决定。

返回上述备份合并冲突:

 image

\ n;

图4

对于上图所示的示例,g个事件合并了[4,-],[-。3],这两个向量的关系不小于,因此这两个事件发生冲突,因此用户必须做出以下决定:处理冲突。解决冲突后,可以将向量组合起来获得[4,3]。对于此示例,您可能认为矢量时钟的影响很小。但是,如果有许多服务器,并且同步更加复杂,则更常见的情况是,当发生备份合并时,两个向量是”小于”关系。两者可以直接合并而不会发生冲突。系统可以直接合并两者。

对于冗余的读取冲突,系统还可以合并在不同机器上的时钟向量之间具有”小于”关系的事件。对于同一机器上的事件,根据算法,它们必须具有”小于”关系,因此也可以将它们合并。

因此,我们可以看到,相对于Lamport时间戳,矢量时钟可以解决合并涉及多台计算机的某些事件的问题。对于确实发生冲突的事件的其他部分,无法将其自动合并,但可以将其检测到。除了能够在同一台计算机上合并事件之外,Lamport时间戳对于涉及多台计算机的任何事件合并都是无能为力的,并且它可以检测到备份合并冲突。从这个角度来看,矢量时钟要比Lamposts时间戳好得多。

从本质上讲,时钟向量表达了这样一个想法:我根据其他服务器事件创建了此事件。向量中反映了我进行此事件的逻辑环境背景。如果”时钟向量1″小于”时钟向量2″,则意味着事件1的基础相对较旧,则自然会基于相对较新的环境将其替换为事件2。这是时钟向量背后的想法。

参考:

[1]:”为什么矢量时钟比Lamport更强大

时间戳》 http://skipperkongen.dk/2011/07/26/vector-clocks-vs-lamport-timestamps/

[2]:Lamport时间戳Wiki http://en.wikipedia.org/wiki/Lamport_timestamps

[3]:Wiki http://en.wikipedia.org/wiki/Happened-before

[4]:http://basho.com/blog/technical/2010/04/05/why-vector-clocks-are-hard/

[5]:http://basho.com/blog/technical/2010/01/29/why-vector-clocks-are-easy/

[6]:Dynamo存储引擎的详细分析

http://www.google.com.hk/urlsa=t\\u0026rct=j\\u0026q=vector+clock\\u0026source=web\cd = 3 \ved = 0CEQQFjAC \url = http://storage.it168.com/a2009/1013/757/000000757579_all.shtml \ei = js-nToP_KIXLhAeZ7o38DQ \ usg = AFQjCNGD2aywzjBFfNY00 >

[7]:关于NoSql数据库的书面讨论

http://sebug.net/paper/databases/nosql/Nosql.html#I_O_9886723485627446_373115905_5228612841633498

[8]

http://skipperkongen.dk/2011/07/26/vector-clocks-vs-lamport-timestamps/

[9]”分布式计算基础知识:

矢量时钟系统

http://net.pku.edu.cn/~course/cs501/2008/reading/a_tour_vc.html#sidebar1

相关推荐

咨询软件
 
QQ在线咨询
售前咨询热线
QQ1922638