当前位置: 首页 > news >正文

【时钟】分布式时钟HLC|Logical Time|Vector Clock|True Time

目录

简略

详细

附录

1 分布式系统不能使用NTP的原因


简略

分布式系统中不同于单机系统不能使用NTP(网络时间协议(Network Time Protocol))来获取时间,所以我们需要一个特别的方式来获取分布式系统中的时间,mvcc也是使用time保证读写相互不影响

Logical Time

      使用 接收到的消息内的时间和自己的时间中最新的那个。

      各个节点发送消息时附带自己的时间Ci,对方收到之后和自己的时间Cj 比对,选择大的时间更新为自己的时间Cj = max{Cj,Ci}.

Vector Clock

      接收到的消息有所有节点的“时间戳”集合,每个时间戳都比本地的集合对应节点的大,就用对方的,都比本地的节点小就用自己的,不是全部都大或者都小就裁决。

        VectorClock一个集合内包含所有节点的“时间戳”:{Node1:0,Node2:2,Node3:3.......}(这个时间戳并不是物理意义上的时间而是由程序赋予的逻辑计数(count)),收发消息时比对和更新自身VectorClock:

a本机:{0,0,1}  消息:{0,1,2}。消息的每个节点的count都大于等于本机的,那么舍弃本机,同步消息

b:本机:{0,1,2}  消息:{0,1,1}。消息的每个节点的count都小于等于本机的,那么舍弃消息,保留本机

c:本机:{0,3,1}  消息:{0,1,2}。出现冲突,有的大,有的小,无法判断出来到底谁是最新版本。就要进行冲突仲裁。

True Time

需要专用硬件支持

Google Spanner里面,通过引入True Time来解决了分布式时间问题。Spanner通过使用GPS + Atomic Clock来对集群的机器进行校时,精度误差范围能控制在ms级别. 需要专用硬件支持

Hybrid Logic Clock(HLC/混合逻辑时钟)

HLC存储两部分信息:本地时钟(物理部分)l,计数器(逻辑部分)c

本地时钟部分l=集群节点的本地时钟的最大值(每次进行事务通信时更新这部分信息)

计数器部分c=每次事件或者消息通信时++(累加),类似逻辑时钟里每次事件都++(累加)。

HLC比较大小时,先用比较l部分,如果l相等再看c是否为零。

详细

摘抄自:分布式系统中的时间 - https://www.jianshu.com/p/18f063573aae

Logical Time

本质是通过事件发生的顺序,通过相互通信更新自己的时间,即通过a->b 根据通信得到C(a) > C(b);

每个进程Pi维护一个本地计数器Ci,相当于logical clocks,按照以下的规则更新Ci

1 每次执行一个事件(例如通过网络发送消息,或者将消息交给应用层,或者其它的一些内部事件)之前,将Ci加1

2 当Pi发送消息m给Pj的时候,在消息m上附着上Ci

3 当接收进程Pj接收到Pi的发送的消息时,更新自己的Cj = max{Cj,Ci}

未解决问题:我们不能通过C(a) > C(b) 得出a->b,不能使用真实时间进行事务查询

Vector Clock

VectorClock是一种用向量来表示偏序关系的逻辑时钟,从数据结构上可以理解为一个集合内包含所有节点的“时间戳”,当然这个时间戳并不是物理意义上的时间(也有些实践会同时加入timestamps以解决冲突问题),而是由程序赋予的逻辑计数(count),{Node1:0,Node2:2,Node3:3.......},如果我们已经统一了向量内的位置对应的node,那么时钟可以直接用一个{0,2,3}来表示。

对于每一个分布式存储的对象副本都有这样一个时间戳,那么存在一下几种关系:

a本机:{0,0,1}  消息:{0,1,2}。消息的每个节点的count都大于等于本机的,那么舍弃本机,同步消息

b:本机:{0,1,2}  消息:{0,1,1}。消息的每个节点的count都小于等于本机的,那么舍弃消息,保留本机

c:本机:{0,3,1}  消息:{0,1,2}。出现冲突,有的大,有的小,无法判断出来到底谁是最新版本。就要进行冲突仲裁。

ps:vector clock类似于quorum协议,更新的时候将本机vector clock与事务vector clock进行对比,根据规则进行更新

未解决问题:不能使用真实时间进行事务查询

True Time

前面我们说了,NTP是有误差的,而且NTP还可能出现时间回退的情况,所以我们不能直接依赖NTP来确定一个事件发生的时间。在Google Spanner里面,通过引入True Time来解决了分布式时间问题。Spanner通过使用GPS + Atomic Clock来对集群的机器进行校时,精度误差范围能控制在ms级别,通过提供一套TrueTime API给外面使用。

TrueTime API很简单,只有三个函数:

MethodReturn

TT.now()TTinterval: [earliest, latest]

TT.after(t)true if t has definitely passed

TT.before(t)true if t has definitely not arrived

首先now得到当前的一个时间区间,spanner不能得到精确的一个时间点,只能得到一段区间,但这个区间误差范围很小,也就是ms级别,我们用ε来表示,也就是[t - ε, t + ε]这个范围,

假设事件a发生绝对时间为tt.a,那么我们只能知道tt.a.earliest <= tt.a <= tt.a.latest, 所以对于另一个事件b,只要tt.b.earliest > tt.a.latest,我们就能确定b一定是在a之后发生的,也就是说,我们需要等待大概2ε的事件才能去提交b,这个就是spanner里面说的commit wait time,保证误差时间消除掉。

未解决问题:需要专用硬件支持

Hybrid Logic Clock

      混合逻辑时钟HLC存储两部分信息,一部分取值来源于本地时钟(物理部分)l,另一部分取值来自于计数器(逻辑部分)c。

    来源于物理的部分,里面保存的其实是当前所有参与节点的本地时钟的最大值(每次进行事务通信时更新这部分信息),另一部分则是每次事件或者消息通信时++(累加),类似逻辑时钟里每次事件都++(累加)。

    HLC将这两部分称为l和c。混合逻辑时钟比较大小时,先用比较l部分,如果相等再看c是否为零。

 混合逻辑时钟HLC的算法描述如下:

本地事件或者发送消息时:

如果本地时钟(pt)大于当前的混合逻辑时钟的l,则将l更新成本地时钟,将c清零。

否则,l保持不变,将c加1。

if pt.j  >  l.j {

    l.j = pt.j

   c.j = 0

} else {

      l.j = l.j

      c.j := c.j

}

return l.j c.j

收到消息时,l 等于(当前的逻辑时钟的l、机器的本地时钟pt、收到消息里面带的l)三者中的最大值。

如果l部分是更新为本地时钟了,则将c清零。(保证HLC最大,如果本地时钟最大则重置HLC.c=0)

否则,c取较大的那个l对应到的c加1。

l'.j = l.j;

l.j = max(l'.j, l.m, pt.j);

if l.j = l'.j = m.j then c.j = max(c.j, c.m) + 1

else if l.j = l'.j then c.j = c.j + 1

else if l.j = l.m then c.j = c.m + 1

else c.j = 0

return l.j c.j

        各节点相互通信的最终结果是,节点的“本地时钟”的物理部分,最终记录的是所有参与者中最大的本地时钟。这里有一个问题是由于HLC是一个 相对的时间所以当集群中有一台机器时间快了的话,所有时间都提前了,另外这个时间不是一个True Time,这样 导致snapshot读的时间和整体系统运行时间不一致

       那么HLC怎么实现snapshot 读呢?我们将HLC作为数据的version,假设e和f事件发生成同一节点上,l.e < l.f ,我们引入一个虚拟事件g,l.e+1 <= l.g <= l.f ,并且 c.g = 0,这样的虚拟事件肯定是能找到的,并且引入一个虚构事件并不影响真实事件发生的先后关系。注意了!这个虚拟事件的时钟其实是可以跟全局的节点比较时序的(l.g, 0) ! 也就意味着,我们可以拿一个本地时钟去确定一个快照了!我们读取HLC<=HLC.g的数据即可

  快照是只要happens before我的,我一定能够看到。混合逻辑时钟通过保留了物理时钟部分,使得拿到'全局'的时间戳成为可能,而逻辑时钟里面happens before的因果关系仍然可以保留。

Timestamp Oracle(与Tidb 使用raft来实现时间一致,保证性能呢最够好,保证能读到数据即可,使用raft同步一写多读的话性能上会更好点)

       无论上面的Ture Time还是Hybrid Logic Time,都是为了在分布式情况下获取全局唯一时间,如果我们整个系统不复杂,而且没有spanner那种跨全球的需求,有时候一台中心授时服务没准就可以了。

在GooglePercolator系统这,他们就提到使用了一个timestamp oracle(TSO)的服务来提供统一的授时服务,为啥叫oracle,我猜想可能底层用的就是oracle数据库。。。

使用TSO的好处在于因为只有一个中心授时,所以我们一定能确定所有时间的时间,但TSO需要关注几个问题:

网络延时,因为所有的事件都需要从TSO获取时间,所以TSO的场景通常都是小集群,不能是那种全球级别的数据库。

性能,TSO是一个非常高频的操作,但鉴于它只干一件事情,就是授时,通常一个TSO每秒都能支持1m+ 以上的QPS,而这个对很多应用来说是绰绰有余的。

容错,TSO是一个单点,所以不得不考虑容错,而这个现在基于zookeeper,etcd也不是特别困难的事情。

所以,如果我们没法实现TrueTime,同时又觉得HLC太复杂,但又想获取全局时间,TSO没准是一个很好的选择,因为它足够简单高效。

TSO方案

作者:羊吃白菜

链接:https://www.jianshu.com/p/18f063573aae

Hybrid Logical Clock (HLC) (sergeiturukin.com)

References

  • http://www.cse.buffalo.edu/tech-reports/2014-04.pdf
  • Distributed systems for fun and profit
  • CS 417 Documents
  • pt, for physical time
  • l, logical, holds maximumptheard so far
  • c, captures causality

附录

1 分布式系统不能使用NTP的原因

NTP是网络时间协议(Network Time Protocol)的缩写,这是一种网络协议,用于同步计算机的时钟与世界统一的时间。通常,单个计算机或网络内的多台计算机可以使用NTP服务器来校准其系统时钟,保持与统一时间(例如,UTC,协调世界时)的一致性,减少时间误差。

但是,在分布式系统中,仅仅依赖NTP来同步时间可能不足够,因为:

1. 分布式系统跨越广泛的地理位置,网络延迟和变化可以造成同步的不精确。

2. NTP无法确保绝对的时钟同步一致性,通常会有毫秒级别的误差,这对于需要高精度时钟同步的分布式系统可能是不可接受的。

3. 分布式系统中的某些算法和应用可能需要比NTP更强的时间协调机制,比如逻辑时钟或向量时钟,它们能够提供系统事件的顺序一致性而不仅仅是时间同步。

因此,虽然NTP可以在分布式系统中提供基本的时钟同步,但它可能不足以满足所有分布式系统所需的精确时间同步要求。复杂的分布式系统可能会采用额外的协议和技术,如真实时间时钟(RTCs)、时钟同步算法(比如Google的TrueTime API),以及各种容错机制来更准确地同步各个节点的时钟。

相关文章:

【时钟】分布式时钟HLC|Logical Time|Vector Clock|True Time

目录 简略 详细 附录 1 分布式系统不能使用NTP的原因 简略 分布式系统中不同于单机系统不能使用NTP(网络时间协议&#xff08;Network Time Protocol&#xff09;)来获取时间&#xff0c;所以我们需要一个特别的方式来获取分布式系统中的时间&#xff0c;mvcc也是使用time保证读…...

人工智能AI与3D视觉技术的结合正在引领新一代移动机器人的革新

随着科技的飞速发展&#xff0c;人工智能AI与3D视觉技术的结合正在引领新一代移动机器人的革新。富唯智能移动机器人&#xff0c;以其独特的3D视觉技术&#xff0c;赋予了移动机器人一双“智慧之眼”&#xff0c;从而为现代工业自动化带来了前所未有的突破。 富唯智能移动机器…...

NSSCTF 简单包含

开启环境: 使用POST传flag&#xff0c;flag目录/var/www/html/flag.php 先使用post来尝试读取该flag.php 没反应: 查看一下源码index.php&#xff0c;看有什么条件 base64解密: <?php$path $_POST["flag"];if (strlen(file_get_contents(php://input)) <…...

FlinkSQL处理Canal-JSON数据

背景信息 Canal是一个CDC&#xff08;ChangeLog Data Capture&#xff0c;变更日志数据捕获&#xff09;工具&#xff0c;可以实时地将MySQL变更传输到其他系统。Canal为变更日志提供了统一的数据格式&#xff0c;并支持使用JSON或protobuf序列化消息&#xff08;Canal默认使用…...

玩转贝启科技BQ3588C开源鸿蒙系统开发板 —— DevEco Studio下载与安装

一、下载DevEco Studio IDE开发工具 1. 登录鸿蒙官网 网址为&#xff1a; ​​​​​​​华为HarmonyOS智能终端操作系统官网 | 应用设备分布式开发者生态 页面如下&#xff1a; 2. 搜索“DevEco Studio IDE” 点击右上角的“请输入关键词”&#xff0c;在其中搜索“DevEc…...

大模型上下文长度的超强扩展:从LongLora到LongQLora

前言 本文一开始是《七月论文审稿GPT第2版&#xff1a;从Meta Nougat、GPT4审稿到Mistral、LongLora Llama》中4.3节的内容&#xff0c;但考虑到 一方面&#xff0c;LongLora的实用性较高二方面&#xff0c;为了把LongLora和LongQLora更好的写清楚&#xff0c;而不至于受篇幅…...

pdf格式转换为txt格式

pdf文档转换为txt文档 首先在python3虚拟环境中安装PyPDF2 Python 3.6.8 (default, Jun 20 2023, 11:53:23) [GCC 4.8.5 20150623 (Red Hat 4.8.5-44)] on linux Type "help", "copyright", "credits" or "license" for more infor…...

scss使用for循环遍历,动态赋值类名并配置不同颜色

需求&#xff1a;后端要传入不同的等级&#xff0c;前端通过等级展示不同的字体颜色&#xff0c;通过scss遍历更有利于动态修改颜色或者增删等级 1.通过 for $i from 1 through 4 定义循环&#xff0c;索引值为i 2.nth($colors, $i) 取出对应的颜色 $colors: #ff0000, #00ff…...

GaussDB数据库使用COPY命令导数

目录 一、前言 二、GaussDB数据库使用COPY命令导数语法 1、语法COPY FROM 2、语法COPY TO 3、特别说明及参数示意 三、GaussDB数据库使用COPY命令导数示例 1、操作步骤 2、准备工作&#xff08;示例&#xff09; 3、把一个表的数据拷贝到一个文件&#xff08;示例&…...

SunFMEA软件免费试用:FMEA的目标和限制是什么?

免费试用FMEA软件-免费版-SunFMEA FMEA&#xff0c;即故障模式与影响分析&#xff0c;是一种预防性的质量工具&#xff0c;旨在识别、评估和优先处理潜在的故障模式及其对系统性能的影响。其目标是提高产品和过程的可靠性和安全性&#xff0c;降低产品故障的风险&#xff0c;并…...

【Redis交响乐】Redis中的数据类型/内部编码/单线程模型

文章目录 一. Redis中的数据类型和内部编码二. Redis的单线程模型面试题: redis是单线程模型,为什么效率之高,速度之快呢? 在上一篇博客中我们讲述了Redis中的通用命令,本篇博客中我们将围绕每个数据结构来介绍相关命令. 一. Redis中的数据类型和内部编码 type命令实际返回的…...

APK 瘦身

APK 瘦身的主要原因是考虑应用的下载转化率和留存率&#xff0c;应用太大了&#xff0c;用户可能就不下载了。再者&#xff0c;因为手机空间问题&#xff0c;用户有可能会卸载一些占用空间比较大的应用&#xff0c;所以&#xff0c;应用的大小也会影响留存率。 1 APK 的结构 …...

GitHub上的15000个Go模块存储库易受劫持攻击

内容概要&#xff1a; 目前研究发现&#xff0c;GitHub上超过15000个Go模块存储库容易受到一种名为“重新劫持”的攻击。 由于GitHub用户名的更改会造成9000多个存储库容易被重新劫持&#xff0c;同时因为帐户删除&#xff0c;会对6000多个存储库造成重新劫持的危机。目前统计…...

避免3ds Max效果图渲染一片黑的4个正确解决方法

在进行3ds Max效果图渲染时&#xff0c;有时候会遇到渲染一片黑的情况&#xff0c;这给我们的工作带来了很大的困扰。为了解决这个问题&#xff0c;下面我将介绍4个正确的解决方法。 1.相机位置 首先需要考虑场景内的相机位置是否有问题。如果相机放在了模型的内部或者墙体的外…...

UI演示双视图立体匹配与重建

相关文章&#xff1a; PyQt5和Qt designer的详细安装教程&#xff1a;https://blog.csdn.net/qq_43811536/article/details/135185233?spm1001.2014.3001.5501Qt designer界面和所有组件功能的详细介绍&#xff1a;https://blog.csdn.net/qq_43811536/article/details/1351868…...

添加一个编辑的小功能(PHP的Laravel)

一个编辑的按钮可以弹出会话框修改断更天数 前台 加一个编辑按钮的样式&#xff0c;他的名字是固定好的 之前有人封装过直接用就好&#xff0c;但是一定放在class里面&#xff0c;不要放在id里面 看见不认识的方法一定要去看里面封装的是什么 之前就是没有看&#xff0c;所以…...

YOLOv8改进 | 主干篇 | ConvNeXtV2全卷积掩码自编码器网络

一、本文介绍 本文给大家带来的改进机制是ConvNeXtV2网络,ConvNeXt V2是一种新型的卷积神经网络架构,它融合了自监督学习技术和架构改进,特别是加入了全卷积掩码自编码器框架和全局响应归一化(GRN)层。我将其替换YOLOv8的特征提取网络,用于提取更有用的特征。经过我的实…...

elasticsearch7.17.9两节点集群改为单节点

需求 将数据从node-23-1节点中迁移到node-83-1节点。但是现在node-83-1并没有加入到集群中&#xff0c;因此首先将node-83-1加入到node-23-1的集群 解决方案 使用ES版本为7.17.9&#xff0c;最开始设置集群为一个节点&#xff0c;node-23-1的配置如下 cluster.name: my-app…...

二叉树的层序遍历,力扣

目录 题目地址&#xff1a; 题目&#xff1a; 我们直接看题解吧&#xff1a; 解题方法&#xff1a; 方法分析&#xff1a; 解题分析&#xff1a; 解题思路&#xff1a; 代码实现&#xff1a; 代码补充说明&#xff1a; 题目地址&#xff1a; 102. 二叉树的层序遍历 - 力扣&…...

构建Dockerfile报错/bin/sh: 1: cd: can‘t cd to /xxx/yyy问题记录

目录 关键的命令行 排查分析 原因 附&#xff1a;Dockerfile构建时打印命令输出的办法 关键的命令行 WORKDIR /app COPY record . RUN cd record && xxx 执行到RUN时报了错&#xff1a; /bin/sh: 1: cd: cant cd to /app/record 并且宿主机当前目录也准备好了re…...

XCTF-web-easyupload

试了试php&#xff0c;php7&#xff0c;pht&#xff0c;phtml等&#xff0c;都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接&#xff0c;得到flag...

Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)

文章目录 1.什么是Redis&#xff1f;2.为什么要使用redis作为mysql的缓存&#xff1f;3.什么是缓存雪崩、缓存穿透、缓存击穿&#xff1f;3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...

Objective-C常用命名规范总结

【OC】常用命名规范总结 文章目录 【OC】常用命名规范总结1.类名&#xff08;Class Name)2.协议名&#xff08;Protocol Name)3.方法名&#xff08;Method Name)4.属性名&#xff08;Property Name&#xff09;5.局部变量/实例变量&#xff08;Local / Instance Variables&…...

全球首个30米分辨率湿地数据集(2000—2022)

数据简介 今天我们分享的数据是全球30米分辨率湿地数据集&#xff0c;包含8种湿地亚类&#xff0c;该数据以0.5X0.5的瓦片存储&#xff0c;我们整理了所有属于中国的瓦片名称与其对应省份&#xff0c;方便大家研究使用。 该数据集作为全球首个30米分辨率、覆盖2000–2022年时间…...

多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验

一、多模态商品数据接口的技术架构 &#xff08;一&#xff09;多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如&#xff0c;当用户上传一张“蓝色连衣裙”的图片时&#xff0c;接口可自动提取图像中的颜色&#xff08;RGB值&…...

【2025年】解决Burpsuite抓不到https包的问题

环境&#xff1a;windows11 burpsuite:2025.5 在抓取https网站时&#xff0c;burpsuite抓取不到https数据包&#xff0c;只显示&#xff1a; 解决该问题只需如下三个步骤&#xff1a; 1、浏览器中访问 http://burp 2、下载 CA certificate 证书 3、在设置--隐私与安全--…...

DIY|Mac 搭建 ESP-IDF 开发环境及编译小智 AI

前一阵子在百度 AI 开发者大会上&#xff0c;看到基于小智 AI DIY 玩具的演示&#xff0c;感觉有点意思&#xff0c;想着自己也来试试。 如果只是想烧录现成的固件&#xff0c;乐鑫官方除了提供了 Windows 版本的 Flash 下载工具 之外&#xff0c;还提供了基于网页版的 ESP LA…...

论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一)

宇树机器人多姿态起立控制强化学习框架论文解析 论文解读&#xff1a;交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架&#xff08;一&#xff09; 论文解读&#xff1a;交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化…...

NFT模式:数字资产确权与链游经济系统构建

NFT模式&#xff1a;数字资产确权与链游经济系统构建 ——从技术架构到可持续生态的范式革命 一、确权技术革新&#xff1a;构建可信数字资产基石 1. 区块链底层架构的进化 跨链互操作协议&#xff1a;基于LayerZero协议实现以太坊、Solana等公链资产互通&#xff0c;通过零知…...

tree 树组件大数据卡顿问题优化

问题背景 项目中有用到树组件用来做文件目录&#xff0c;但是由于这个树组件的节点越来越多&#xff0c;导致页面在滚动这个树组件的时候浏览器就很容易卡死。这种问题基本上都是因为dom节点太多&#xff0c;导致的浏览器卡顿&#xff0c;这里很明显就需要用到虚拟列表的技术&…...