《云数据管理》 2.1 逻辑时间和Lamport时钟
若两个事件e和f满足下列任一条件,则事件e发生在事件f之间,记作e→f:
1. 如果e和f是发生在同一进程内的两个事件,并且e发生在f之前,那么e→f;
2. 如果e代表了某个进程的消息发送事件send(m),f代表另一进程中针对这同一个消息的接收事件receive(m),那么e→f;
3. 如果存在一个事件g,满足e→g并且g→f,那么e→f。
图2-1 事件和消息
“发生在前”(happens-before)关系可以很好地反映任意两个事件之间的潜在因果依赖关系。并且,如果两个事件e和f既不存在e→f关系,也不存在f→e关系,那么e和f是并发的。在图2-1中,事件e4发生在事件e6之前,而事件e3与事件e2和e4都是并发的。
时间概念以及时间与事件之间的关系对很多分布式系统协议来说都是至关重要的。一般情况下,不一定需要实时时钟或近似实时时钟,只要有一个时间概念能够捕获潜在的因果关系就足够了。Lamport引入了一种可以捕获事件之间的潜在因果关系的逻辑时钟概念。逻辑时钟为每一个事件e赋一个值clock(e),因此,对任意两个事件e和f,存在如下关系:
如果e→f,那么clock(e)<clock(f)。
为了能够实现这种逻辑时钟,Lamport为每一个进程设置了一个时钟计数器。该计数器在同一进程中的任意两个事件之间都必须是递增的,并且,每一个消息都携带了发送者的时钟值。当消息到达目的地之后,本地时钟计数器被设置为本地值的最大值,同时消息的时间戳加1。这种实现方式可以满足上述逻辑时钟的条件。
在图2-2中,使用与图2-1相同的例子,为系统中的所有事件都赋一个逻辑时间。
图2-2 Lamport时钟
因为“发生在前”关系是一个偏序,因此,多个事件可能被赋值相同的逻辑时钟。但是,在很多协议中,为每一个事件赋一个唯一的时间值更为方便。这种情况下,为了打破这种关系,时间值可以设置为<t, p>,其中,t是本地时钟计数器设置的逻辑时间,p是事件执行所在进程的进程标识。一般情况下,每一个进程都被赋值一个唯一的全序的进程标识,这些进程标识可以打破具有相同逻辑时间的事件之间的关系。
相关文章
- 在 Go 里用 CGO?这 7 个问题你要关注!
- 9款优秀的去中心化通讯软件 Matrix 的客户端
- 求职数据分析,项目经验该怎么写
- 在OKR中,我看到了数据驱动业务的未来
- 火山引擎云原生大数据在金融行业的实践
- OpenHarmony富设备移植指南(二)—从postmarketOS获取移植资源
- 《数据成熟度指数》报告:64%的企业领袖认为大多数员工“不懂数据”
- OpenHarmony 小型系统兼容性测试指南
- 肯睿中国(Cloudera):2023年企业数字战略三大趋势预测
- 适用于 Linux 的十大命令行游戏
- GNOME 截图工具的新旧截图方式
- System76 即将推出的 COSMIC 桌面正在酝酿大变化
- 2GB 内存 8GB 存储即可流畅运行,Windows 11 极致精简版系统 Tiny11 发布
- 迎接 ecode:一个即将推出的具有全新图形用户界面框架的现代、轻量级代码编辑器
- loongarch架构介绍(三)—地址翻译
- Go 语言怎么解决编译器错误“err is shadowed during return”?
- 敏捷:可能被开发人员遗忘的部分
- Denodo预测2023年数据管理和分析的未来
- 利用数据推动可持续发展
- 在 Vue3 中实现 React 原生 Hooks(useState、useEffect),深入理解 React Hooks 的