向量时钟解决数据一致性

向量时钟解决数据一致性

向量时钟简介

向量时钟,最早是用于分布式系统中进程间的时间同步。由于在分布式系统中没有一个直接的全局逻辑时钟。在一个由n个并发进程构成的系统中,每个事件的逻辑时钟均由一个n维向量(n元组)构成,其中第i维(分量)对应于第i个进程的逻辑时钟Vi

向量时钟的维护方法:

*初值

*第i个进程在事件发生时,继承上一事件的逻辑时钟并将自身所对应的分量Vi增加一个步长

*任何进程Pi在发出任何消息m时都要将自己当前的逻辑时钟分量Vi一起发送出去

*如果是接收事件,且发送方为j,则比较自己继承的Vj和收到的逻辑时钟,并取其中较大者为自己的Vj

形式化表示如下:

在向量时钟方法中,每个进程Pi和一个向量LCi[1...n]相关联,其中

* LCi[i]描述了进程Pi,即自身进程

* LCi[j]表示Pi关于Pj进程的知识

* LCi[1...n]组成Pi对于逻辑全局时间的局部视图

对每一个进程LCi的更新规则如下

*规则1:在发生一个事件(一个外部发送或内部事件)之前,我们更新LCi[i]:

LCi[i] := LCi[i] + d (d > 0)

*规则2:每个消息捎带发送方在发送时的向量时钟。当接收到一个消息(m, LCj, j)时,Pi执行更新:

LCi[k] := max(LCi[k], LCj[k]), 1<=k<=n

LCi[i] := LCi[i]+d

下图为增量值d=1,初始值init=0时的示例图

数据一致性(Quorum)

定义

N:系统中数据的备份数

R:读取操作最小成功数

W:写操作最小成功数

要求:R+W>N

配置

R+W>N,保证读操作至少能读取到一个最新数据

读写速度受性能最差的节点影响

R和W越小,系统的响应越快

W越大,数据的一致性,可用性越强

通常:N=3, R=W=2

时钟向量与数据冲突处理

*将上述向量时钟应用到解决数据一致性的问题上来

*向量时钟在分布式环境中表示对象或事件的逻辑关系

*分布式系统中每个消息都附加Vector Clock的信息

*当某个节点内部处理一个事件时,将其自身对应的counter加1

*节点发送一个消息前,将其自身对应的counter加1

*节点收到一个消息时,将其自身对应的counter加1;同时,根据消息中的Vector Clock信息更新所有其他counter

在Dynamo系统中为了可用性,所以对一致性的约束做了妥协。使得整个系统对“写”一直是可用的,而将数据不一致性的处理部分放到了客户端程序读数据时再进行处理。

在客户端使用get获取数据时,coordinator对node返回数据依据时钟向量进行version处理。如果数据一致则将取得的值返回给客户端。如果数据冲突,则将所有数据返回给客户端,由客户端进行解决。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏杨建荣的学习笔记

MySQL备份调度器的实现

对于MySQL方向的调度需求考虑了好久,总是感觉不够优雅,不够灵活。从我的感觉来看,如果设置成为crontab,其实管理起来是比较臃肿的。

1293
来自专栏FreeBuf

使用Python以及C++简单绕过反爬虫机制

0x00 某些网站有反爬虫的机制 对于刚学习了几天python的我,对爬虫颇有兴趣,但是某些“想要的”网站上具有反爬虫机制,如果说使用延迟或者代理,这样的效率并...

25110
来自专栏何俊林

使用TensorFlow进行训练识别视频图像中物体

本教程针对Windows10实现谷歌公布的TensorFlow Object Detection API视频物体识别系统,其他平台也可借鉴。

5352
来自专栏SAP最佳业务实践

想学FM系列(16)-SAP FM模块:预算结构(7)-预算结构操作-多层预算结构维护

3.2.2.3 多层预算结构的维护 ? 1)FMHIE_HIEID- 编辑层次结构标识 功能为多层预算结构备用树定义一相标识ID,并定义相关属性,为之后生成备...

4808
来自专栏企鹅号快讯

技术分享连载|UGUI对于emoji表情的处理|加载资源时的内存波动|Animator采样……

我们将从日常技术交流中精选若干个开发相关的问题,建议阅读时间15分钟,认真读完必有收获。如果您有任何独到的见解或者发现也欢迎联系我们,一起探讨。 内存管理 Q:...

3756
来自专栏恰童鞋骚年

操作系统核心原理-3.进程原理(中):进程调度

PS:在多进程并发的环境里,虽然从概念上看,有多个进程在同时执行,但在单个CPU下,在任何时刻只能有一个进程处于执行状态,而其他进程则处于非执行状态。那么问题来...

1035
来自专栏前端笔记

【新手指南】浅谈几种WordPress固定链接的优劣势

新手建站须知: 所谓“固定链接”,其实就是指访问某个网页的特定链接。也是我们站长将网站提交给各大站长平台的重要参数之一!建站初期我们必须确定好“固定链接”(准确...

3207
来自专栏IT派

从零开始:手把手教你安装深度学习操作系统、驱动和各种python库!

为了研究强化学习,最近购置了一台基于 Ubuntu 和英伟达 GPU 的深度学习机器。尽管目前在网络中能找到一些环境部署指南,但目前仍然没有全面的安装说明。另外...

4448
来自专栏GreenLeaves

EF基础知识小记二

1、EF的常用使用场景 (1)、维护一个已经存在的数据库,VS提供了工具帮助我们把数据库中的表和视图等对象导入到实体框架.        [数据库=>模型(Da...

1957
来自专栏施炯的IoT开发专栏

Endnote for Windows Mobile

  想必园子里有好多朋友都写过paper吧,在阅读文献的时候,是不是觉得管理文献这个事情很麻烦。我正处于刚刚起步的阶段,英语写译老师Greatlion给我们推荐...

2066

扫码关注云+社区

领取腾讯云代金券