云主机可以放多少网站,安徽住房与城乡建设门户网站,网站建设任务,wordpress 博客同步目录 简略 详细 附录 1 分布式系统不能使用NTP的原因 简略 分布式系统中不同于单机系统不能使用NTP(网络时间协议#xff08;Network Time Protocol#xff09;)来获取时间#xff0c;所以我们需要一个特别的方式来获取分布式系统中的时间#xff0c;mvcc也是使用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本机{001} 消息{012}。消息的每个节点的count都大于等于本机的那么舍弃本机同步消息 b:本机{012} 消息{011}。消息的每个节点的count都小于等于本机的那么舍弃消息保留本机 c:本机{031} 消息{012}。出现冲突有的大有的小无法判断出来到底谁是最新版本。就要进行冲突仲裁。 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本机{001} 消息{012}。消息的每个节点的count都大于等于本机的那么舍弃本机同步消息 b:本机{012} 消息{011}。消息的每个节点的count都小于等于本机的那么舍弃消息保留本机 c:本机{031} 消息{012}。出现冲突有的大有的小无法判断出来到底谁是最新版本。就要进行冲突仲裁。 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.c0) 否则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 我们引入一个虚拟事件gl.e1 l.g l.f 并且 c.g 0这样的虚拟事件肯定是能找到的并且引入一个虚构事件并不影响真实事件发生的先后关系。注意了这个虚拟事件的时钟其实是可以跟全局的节点比较时序的(l.g, 0) ! 也就意味着我们可以拿一个本地时钟去确定一个快照了我们读取HLCHLC.g的数据即可 快照是只要happens before我的我一定能够看到。混合逻辑时钟通过保留了物理时钟部分使得拿到全局的时间戳成为可能而逻辑时钟里面happens before的因果关系仍然可以保留。 Timestamp Oracle(与Tidb 使用raft来实现时间一致保证性能呢最够好保证能读到数据即可使用raft同步一写多读的话性能上会更好点) 无论上面的Ture Time还是Hybrid Logic Time都是为了在分布式情况下获取全局唯一时间如果我们整个系统不复杂而且没有spanner那种跨全球的需求有时候一台中心授时服务没准就可以了。 在GooglePercolator系统这他们就提到使用了一个timestamp oracleTSO的服务来提供统一的授时服务为啥叫oracle我猜想可能底层用的就是oracle数据库。。。 使用TSO的好处在于因为只有一个中心授时所以我们一定能确定所有时间的时间但TSO需要关注几个问题 网络延时因为所有的事件都需要从TSO获取时间所以TSO的场景通常都是小集群不能是那种全球级别的数据库。 性能TSO是一个非常高频的操作但鉴于它只干一件事情就是授时通常一个TSO每秒都能支持1m 以上的QPS而这个对很多应用来说是绰绰有余的。 容错TSO是一个单点所以不得不考虑容错而这个现在基于zookeeperetcd也不是特别困难的事情。 所以如果我们没法实现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.pdfDistributed systems for fun and profitCS 417 Documentspt, for physical timel, logical, holds maximumptheard so farc, captures causality 附录 1 分布式系统不能使用NTP的原因 NTP是网络时间协议Network Time Protocol的缩写这是一种网络协议用于同步计算机的时钟与世界统一的时间。通常单个计算机或网络内的多台计算机可以使用NTP服务器来校准其系统时钟保持与统一时间例如UTC协调世界时的一致性减少时间误差。 但是在分布式系统中仅仅依赖NTP来同步时间可能不足够因为 1. 分布式系统跨越广泛的地理位置网络延迟和变化可以造成同步的不精确。 2. NTP无法确保绝对的时钟同步一致性通常会有毫秒级别的误差这对于需要高精度时钟同步的分布式系统可能是不可接受的。 3. 分布式系统中的某些算法和应用可能需要比NTP更强的时间协调机制比如逻辑时钟或向量时钟它们能够提供系统事件的顺序一致性而不仅仅是时间同步。 因此虽然NTP可以在分布式系统中提供基本的时钟同步但它可能不足以满足所有分布式系统所需的精确时间同步要求。复杂的分布式系统可能会采用额外的协议和技术如真实时间时钟RTCs、时钟同步算法比如Google的TrueTime API以及各种容错机制来更准确地同步各个节点的时钟。
