Fuhui

数据一致性(三)


一个人的时候多一点努力,才能让自己的爱情,少一点条件,多一点纯粹

Quorum

在有冗余数据的分布式存储系统中,数据会在不同的机器上存放多份拷贝。但是同一时刻一个对象的多份拷贝只能用于读或者用于写。该算法可以保证同一份数据对象的多份拷贝不会被超过两个访问对象读写。

分布式系统中每一份数据拷贝对象被赋予一票。每一个读操作获得的票数必须大于最小读票数 $V_r$,每个写操作获得的票数必须大于最小写票数 $V_w$才能读或者写。如果系统有V票,那么最小读写票数应该满足如下限制:

  1. $V_r$ + $V_j$ > V
  2. $V_w$ > V/2

第一条规则保证了一个数据不会被同时读写。当一个写操作请求过来的时候,它必须要获得$V_w$个冗余拷贝的许可。而剩下的数量是V-$V_w$不够$V_r$,因此不能再有读请求过来。同理,当读请求已经获得了$V_r$个冗余拷贝的许可时,写请求就无法获得许可了。

第二条规则保证了数据的串行化修改。一份数据的冗余拷贝不可能同时被两个写请求修改。

注:上述内容来自于维基百科:Quorum

上述算法的思想来自于鸽巢原理,也是摘自维基百科:鸽巢原理

假如有n个笼子和n+1个鸽子,所有的鸽子都被关在鸽笼里,那么至少有一个笼子有至少2只鸽子。

集合论的表述如下:若A是n+1个元素,B是n个元素,则不存在从A到B的单射。这里也体现了Lamport的思想。

$V_r$和$V_w$的设置会直接影响系统的性能、扩展性和一致性。比如将$V_r$或者$V_w$设置为1,会体现出系统对读和写的不同侧重。

Two-phase commit

在分布式系统中,虽然每个节点内部的事务可以保证,但却无法保证其他所有节点的操作都成功或失败。当一个事物跨多个节点时,为了保证数据的一致性,需要引入一个协调者来统一掌控所有节点的操作。

第一阶段提交请求,参与者节点执行事务的操作,并将Undo信息和Redo信息写入日志。第二阶段参与者正式完成操作,并释放整个事务期间占用的资源。

   协调者                                              参与者
                              QUERY TO COMMIT
                -------------------------------->
                              VOTE YES/NO           prepare*/abort*
                <-------------------------------
commit*/abort*                COMMIT/ROLLBACK
                -------------------------------->
                              ACKNOWLEDGMENT        commit*/abort*
                <--------------------------------  
end

注:内容来自于维基百科:二阶段提交

Optimistic Lock

在数据库低的隔离级别中,乐观锁也可以保证数据的一致性。区别于Pessimistic Lock,实际上Optimistic Lock并没有对数据库上锁,性能要优Pessimistic Lock。它的操作流程:

  1. 更新一个新值
  2. 校验在更新时数据是否发生改变

Optimistic Lock大多数基于数据版本记录实现,或者是不可逆的状态字段。实际工作中,PessimisticOptimistic需要根据实际需要来使用,比如,如果要对多个数据表进行更新操作,Optimistic Lock就有点力不从心了。

Summary

当意见不一致的时候,大家可以选择投票。当票数一致的时候,大家还是会有很多策略来执行最优选择。计算机的世界也一样。