文档章节

如何解决分布式系统的Logical Time问题?(一)

UCloudTech
 UCloudTech
发布于 2017/09/08 11:12
字数 2115
阅读 5
收藏 0
点赞 0
评论 0

前言
在一个分布式系统中存在着各种各样的并发事件,对于某些存在内在因果关系的事件需要知道事件的先后顺序,并且能够按照正确的顺序处理这些事件,区分事件的先后顺序在单机系统中可以靠本地时钟来做到,但在分布式系统中如何做到呢,这就是分布式系统中的logical time问题。
本文为大家介绍logical time算法的鼻祖Lamport Clock。

为了形象地描述logical time问题,我们举个简单的例子,假设客户A下单购买了一本书,这时系统向订单系统提交a请求(客户买书的订单),然后购买该书还有个优惠活动,能够获得一本赠书,这时系统需要向优惠活动管理系统发送b请求(客户要求赠书x),优惠活动管理系统检查准许客户的赠书请求,于是将b请求转发给订单系统,在该例子中显然订单系统应该先收到买书的订单,然后是赠书的订单,但是由于网络延时的原因,可能存在赠书请求先于买书请求到达订单系统的情况,那么这种情况需要如何处理?

我们用简单的图来描述上面的过程,图中P0代表订单系统,P1代表客户,P2代表优惠活动管理系统,a请求就是买书请求,b请求就是赠书请求。

为了解决该问题比较容易想到的做法就是同步通信,发送a请求后等待P0处理完成并回复后再开始发送b请求,该方法简单易实现但是并不能发挥分布式系统的并发性能,效率低下,也不能简单地用给时间a和b打上本地时间戳的方式来处理,因为分布式系统中本地时钟是无法做到完全同步的,所以需要一种适用于分布式系统的能将事件的先后顺序信息也被称为“ happened before”信息识别出来的算法,本文主要介绍logical time算法的鼻祖Lamport clock。

Lamport clock算法
Lamport clock算法的思想很简单,主要有以下两个规则:
1.每个process在成功完成一个事件后都增加自己的时间戳,通常是加1;
2.(a)如果process Pi通过消息m发送了事件a,那么该消息m中包含了当前pi的时间戳Ci(a);
(b)process Pj收到消息m后,取消息m中带的时间戳和Pj当前的时间戳Cj中的较大值然后加1;
例如一个较为复杂的例子,已经用Lamport clock算法为每个事件加了时间戳,如下图:

通过该例子可以发现存在一些并没有明确的先后关系的并发事件,比如p1上的时间戳为3的事件和p2上的时间戳为4的事件,这些事件可以是任意先后或者同时发生,但在Lamport clock算法中这些事件却有了明确的时间戳,该时间戳的大小并不代表事件的先后顺序。

重要属性
用简单的公式来描述logical time算法的Clock Condition,C表示时间戳,ei 和 ej表示两个事件,假设ei先于ej发生,并用->表示该“happened before”关系,那么存在以下两个Clock Condition:
1)ei -> ej => C(ei) < C(ej) 表示如果ei先于ej发生,那么ei的时间戳C(ei)必定小于C(ej)。 2)ei -> ej <=> C(ei) < C(ej) 表示如果ei先于ej发生,那么ei的时间戳C(ei)必定小于C(ej),如果C(ei)小于C(ej),那么ei必定先于ej发生。

根据算法是否满足以上Clock Condition来区分其所具备的属性,如果一个算法满足Clock Conditon 2,那么该算法具备strongly consistent属性,本篇文章介绍的Lamport clock算法只满足Clock Condition 1,所以不具备strongly consistent属性,但后续介绍的vector clock算法具备strongly consitent属性。 strongly consistent属性的意义在于是否可以通过C时间戳来判断出事件ei与ej的顺序关系,具备该属性的算法,当时间戳C(ei) > C(ej)时,可以确定ei先于ej发生,否则可以认为ei与ej是冲突的(这里的冲突表示ei与ej可以是任意的先后关系),所以可以用来检测事件的冲突。

案例分析
使用Lamport clock对之前的例子做排序,如下图:

P1发送a消息和b消息,因为P1的初始时间戳为0,所以按照Lamport clock算法事件a和b的发送时间戳为1和2。

P0收到P1的消息a,取两者时间戳的较大值max(0,1)并+1得到时间戳为2。

P2收到b消息后,取两者时间戳的较大值max(0,2)并+1得到时间戳为3。

P0收到P2转发的事件b后,取两者时间戳的较大值max(2,3)并+1得到时间戳为4。
所以在P0端可以得到事件a是先于事件b的。

但在实际的应用中由于存在网络延时,会出现以下情况:

因为网络延时导致P0先收到P2转发的b事件,再收到P1的a事件,然后根据Lamport clock算法计算出来的时间戳也变成了b事件先于a事件了,这显然是错误的,那么要如何避免出现这个情况,为了关注解决该问题的实际算法,假定系统已经满足以下条件:
1.消息的接受顺序与发送顺序一致;
2.所有的消息最终都会被收到;

每个process都有自己的请求队列,并且对其他process不可见,请求队列中的初始时间戳为0,算法由以下5条规则组成:
1.请求资源时,process Pi发送消息Tm,给其他所有process,并且将消息Tm置于它的请求队列中
2.prcocess Pj收到Pi的资源请求消息Tm后,将该消息置于自己的请求队列中并发送一个带有时间戳的回复给Pi
3.释放资源时,Pi将消息Tm从请求队列中移除,并发送资源释放消息给所有其他process
4.process Pj收到Pi的资源释放消息后将之前的资源请求消息Tm从请求队列中移除
5.当满足以下2个条件时认为Pi获取了资源
(i) Pi的请求队列中有请求消息Tm,并且按照顺序排列好的,这里以消息的发送顺序为准;
(ii) Pi收到了任意一个时间戳比Tm要大的消息;

把这个算法带入到上面的例子中,相当于P1发起了两个事件a和b来请求资源,a比b要先发生,那么也期望a比b要先被P0处理(这里处理可以理解为获取了P0的资源),那么当出现上述例子中的情况,事件b先被P0收到,按照算法,P0发送Tm给所有其他process,然后等待回复,当收到P1的回复时a事件也必然被收到了(按照系统假定满足的条件1)消息的接受顺序与发送顺序一致),这时按照规则5的(i)条件,会根据事件a和b的发送端的时间戳比较,重新排序为a事件先于b事件,这样就解决了因为网络延时导致的消息乱序问题。

总结
Lamport clock虽然作为分布式系统中解决logical time问题的鼻祖,为后续其他算法提供了思路,但其不具备strongly consistent,无法满足分布式数据库场景中写冲突的检测,所以实际场景中更多是使用后来的vector clock,下一篇文章我们将会给大家介绍vector clock。

参考
Lamport, L. (1978).“Time, Clocks, and the Ordering of Events in a Distributed System”

本文转载自:http://blog.ucloud.cn/archives/2400

共有 人打赏支持
UCloudTech
粉丝 3
博文 16
码字总数 19843
作品 0
逻辑备库之ORA-01403解决方法

Oracle 的Data Guard环境中, 逻辑备库应用进程停止,日志显示错误为ORA-01403 not data found 。 它具体信息如下: Mon May 21 10:39:31 2012 LOGSTDBY status: ORA-01403: no data found L...

zylhsy ⋅ 2014/08/07 ⋅ 0

为什么我们在 TiDB 里面使用全局授时服务

前言 在 TiDB 里面,为了支持分布式事务,我们通过 PD,这个全局的单点服务,为事务分配全局唯一的时间,这个做法就是简单高效,但获取 timestamp 的时候会有网络开销。这点对一些人来说,就...

siddontang ⋅ 2017/11/26 ⋅ 0

系统架构领域的一些学习材料

标签:架构学习材料系统systemresearch 转载:http://qing.blog.sina.com.cn/2244218960/85c41050330031zq.html?utmsource=tuicool&sudaref=www.tuicool.com 系统架构是一个工程和研究相结合的......

Michaelyn ⋅ 2015/05/27 ⋅ 0

开源NewSQL – CockroachDB在百度内部的应用与实践

NewSQL起源 对于MySQL、Oracle、PostgreSQL这样的单机数据库,随着数据量的增长在计算容量和存储容量上都会出现问题。于是后续又推出了基于中间件或者NoSQL的方案,但是都并非完美,比如中间...

技术小能手 ⋅ 05/17 ⋅ 0

使用 Rust 构建分布式 Key-Value Store

欢迎大家前往腾讯云社区,获取更多腾讯海量技术实践干货哦~ 引子 构建一个分布式 Key-Value Store 并不是一件容易的事情,我们需要考虑很多的问题,首先就是我们的系统到底需要提供什么样的功...

腾讯云社区 ⋅ 2017/11/20 ⋅ 0

nutch的分布式部署问题

@xieyi 你好,想跟你请教个问题:问题类似于你早前提问的这一问题http://www.oschina.net/question/271491_72802?sort=time,不知你解决没有,如何解决的,谢谢~~~...

青蚨侠 ⋅ 2013/07/15 ⋅ 0

《Apache Spark 设计与实现》

本文主要讨论 Apache Spark 的设计与实现,重点关注其设计思想、运行原理、实现架构及性能调优,附带讨论与 HadoopMapReduce在设计与实现上的区别。不喜欢将该文档称之为“源码分析”,因为本...

叶秀兰 ⋅ 2015/07/16 ⋅ 1

市场是衡量一切的标准

“少年不知愁滋味,为赋新词强说愁,而今识愁滋味,却道天凉好个秋!”,这就是我对这些年我职业发展的比较贴近的比喻。 遥想当年,年少轻狂的我,凭借自己学习来的一些技术皮毛,一直标榜是...

边缘行者 ⋅ 2015/11/30 ⋅ 0

亿级流量电商详情页系统的大型高并发与高可用缓存架构实战

对于高并发的场景来说,比如电商类,o2o,门户,等等互联网类的项目,缓存技术是Java项目中最常见的一种应用技术。然而,行业里很多朋友对缓存技术的了解与掌握,仅仅停留在掌握redis/memca...

登录404 ⋅ 2017/06/05 ⋅ 0

分布式事务数据库发展及特点

分布式数据库发展背景 “双十一”指数型的成交总额发展曲线,让世界看到了中国电商业务的火箭式发展势头。 而同时,对于背后的业务支撑系统来说,他们同样经历了火箭式的系统压力增长。 “双...

外陈内罗 ⋅ 2017/12/18 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

zblog2.3版本的asp系统是否可以超越卢松松博客的流量[图]

最近访问zblog官网,发现zlbog-asp2.3版本已经进入测试阶段了,虽然正式版还没有发布,想必也不久了。那么作为aps纵横江湖十多年的今天,blog2.2版本应该已经成熟了,为什么还要发布这个2.3...

原创小博客 ⋅ 48分钟前 ⋅ 0

聊聊spring cloud的HystrixCircuitBreakerConfiguration

序 本文主要研究一下spring cloud的HystrixCircuitBreakerConfiguration HystrixCircuitBreakerConfiguration spring-cloud-netflix-core-2.0.0.RELEASE-sources.jar!/org/springframework/......

go4it ⋅ 今天 ⋅ 0

二分查找

二分查找,也称折半查找、二分搜索,是一种在有序数组中查找某一特定元素的搜索算法。搜素过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜素过程结束;如果某一特定元素大于...

人觉非常君 ⋅ 今天 ⋅ 0

VS中使用X64汇编

需要注意的是,在X86项目中,可以使用__asm{}来嵌入汇编代码,但是在X64项目中,再也不能使用__asm{}来编写嵌入式汇编程序了,必须使用专门的.asm汇编文件来编写相应的汇编代码,然后在其它地...

simpower ⋅ 今天 ⋅ 0

ThreadPoolExecutor

ThreadPoolExecutor public ThreadPoolExecutor(int corePoolSize, int maximumPoolSize, long keepAliveTime, ......

4rnold ⋅ 昨天 ⋅ 0

Java正无穷大、负无穷大以及NaN

问题来源:用Java代码写了一个计算公式,包含除法和对数和取反,在页面上出现了-infinity,不知道这是什么问题,网上找答案才明白意思是负的无穷大。 思考:为什么会出现这种情况呢?这是哪里...

young_chen ⋅ 昨天 ⋅ 0

前台对中文编码,后台解码

前台:encodeURI(sbzt) 后台:String param = URLDecoder.decode(sbzt,"UTF-8");

west_coast ⋅ 昨天 ⋅ 0

实验楼—MySQL基础课程-挑战3实验报告

按照文档要求创建数据库 sudo sercice mysql startwget http://labfile.oss.aliyuncs.com/courses/9/createdb2.sqlvim /home/shiyanlou/createdb2.sql#查看下数据库代码 代码创建了grade......

zhangjin7 ⋅ 昨天 ⋅ 0

一起读书《深入浅出nodejs》-node模块机制

node 模块机制 前言 说到node,就不免得提到JavaScript。JavaScript自诞生以来,经历了工具类库、组件库、前端框架、前端应用的变迁。通过无数开发人员的努力,JavaScript不断被类聚和抽象,...

小草先森 ⋅ 昨天 ⋅ 0

Java桌球小游戏

其实算不上一个游戏,就是两张图片,不停的重画,改变ball图片的位置。一个左右直线碰撞的,一个有角度碰撞的。 左右直线碰撞 package com.bjsxt.test;import javax.swing.*;import j...

森林之下 ⋅ 昨天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部