Raft以多数派机制化解2PC阻塞 确立分布式共识标准

Raft以多数派机制化解2PC阻塞 确立分布式共识标准 保持线性一致性的代价直接受制于网络延迟，传统两阶段提交因协调者单点故障易致系统死锁，工程落地须依托Raft等共识算法由存活多数派自动推进决议。 本次分享全面剖析了分布式系统领域最核心也最复杂的一致性与共识机制。讲者深入辨析了线性一致性与可串行化的边界，剖析了 CAP 定理下网络分区的必然性，并梳理了全序、偏序以及兰伯特逻辑时钟的适用场景与局限。随后，内容以生动的“教堂婚礼”比喻剖析了两阶段提交（2PC）的阻塞瓶颈，系统阐释了共识算法的四大核心属性，并对比了 Paxos 与 Raft 的设计演进及 FLP 不可能性定理。最后，讲座就 Gossip 协议与共识的区别、2PC 故障恢复路径以及线性一致性的外部观察等实际疑问进行了深入解答。 线性一致性（Linearizability）本质上是针对外部观察者的最新性保证（Recency guarantee），在数学等价上与全序广播及分布式共识互为充要映射，且其时间开销与网络延迟严格成正比。 (20:00) CAP 定理常被误解为三选二，但在真实的分布式环境中网络分区是无法消除的物理现实，实际权衡核心在于网络分区发生时选择牺牲线性一致性还是可用性。 (25:00) 两阶段提交（2PC）因协调者单点故障与阻塞机制会导致系统吞吐出现数量级暴跌（如从单机十万级跌至百级），且单主复制与 2PC 均无法保证共识所需的终止性（Termination）。 (60:00) Raft 算法通过拆分角色与任期机制降低了 Paxos 的工程实现复杂度，但受限于 FLP 不可能性定理，异步网络中不存在绝对能收敛的确定性共识算法，工程上依赖随机化超时破局。 (71:45)

讲者 Scott Shi 阐明了分布式系统中的核心权衡：在物理延迟与网络分区必然发生的现实下，系统无法兼得全序的线性一致性与极致的可用性；而分布式共识算法通过规范状态机演进与多数派表决，解决了单点协调阻塞难题，成为分布式容错系统的基石。 线性一致性的本质与时序判定 (0:00) 线性一致性（Linearizability）旨在将复杂的分布式系统抽象为单机数据库实例，保证最新写入即时可见。讲者辨析指出，线性一致性与事务隔离级别中的可串行化互不包含：例如可串行化快照隔离（SSI）虽保证事务串行等价，但事务可能读取旧快照，违反线性一致性；而针对单对象的线性写入则缺乏跨对象事务的原子性。判定系统是否满足线性一致性，关键在于能否在各客户端读写调用的耗时区间（发起至响应）内找到合理的原子生效点，并投影到单一虚拟时间轴上。若某个读操作的发起时间严格晚于另一个读到最新值（如 4）的操作完成时间，却读回了旧值（如 2），系统便构成了时序倒退违规；但若两者物理窗口存在重叠，则仍可通过合法串行化解释挽救其一致性。 网络分区的物理现实与 CAP 权衡 (25:00) 讲者指出流传甚广的 CAP“三选二”并不准确，因为在真实数据中心运营中，网络分区是必然发生的故障而非架构选项，长时间的高延迟在共识模型中亦等价于宕机。系统的核心抉择在于当分区不可避免地出现时，究竟是倒向可用性（如 DynamoDB 采用宽松法定人数与提示移交，容忍短时不一致），还是倒向强一致性（如传统 SQL 数据库配合严格锁机制，在分区时停止服务）。此外，根据 LinkedIn 在 Kafka 开发中的洞察，大数据环境下超过 99% 的操作并不需要强事务语义；强行拉出全局全序的开销受制于网络往返延迟，现代流式与分布式架构通常仅维持 Git 式的分支偏序与因果一致性，以此换取高吞吐。 两阶段提交机制与单点阻塞脆弱性 (50:00) 跨节点分片操作与全局二级索引（GSI）更新常依赖两阶段提交（2PC）。讲者将 2PC 比作教堂婚礼：协调者扮演牧师，参与者节点扮演新人。第一阶段协调者发起准备询问，各参与者执行预写并持久化投出 Commit 选票；第二阶段当且仅当协调者将最终决议刷入本地 Commit Log 时，系统达到原子提交点并下发确认。然而 2PC 存在致命的单点阻塞脆弱性：一旦参与者均已回复 Yes 且锁定数据行后协调者意外失联，参与者无法获知最终决议，既不敢自行提交也不敢擅自回滚，导致事务无限期挂起并死锁并发写入。该协议的多轮网络往返与锁竞争往往使系统吞吐量由单机的数万次断崖式跌落至数百次，严重硬件故障时还必须依赖人工排障干预。 分布式共识属性、Raft 与理论边界 (65:00) 为了在无单点协调者的前提下推进系统，分布式共识算法必须满足一致同意、完整性、有效性与终止性（Termination）四大属性；单主复制和 2PC 正是因为主节点宕机后无法保证终止性而不能算作完备共识。针对 Paxos 实现过于复杂的痛点，斯坦福学者提出的 Raft 算法通过明确拆分 Leader、Follower 与 Candidate 角色，基于任期（Term）与超时心跳实现状态流转，工程上通常要求心跳发送间隔比选举超时小一个数量级以避免误判与抖动。讲者同时澄清，Cassandra 等系统使用的 Gossip 协议属于低网络开销的数据异步广播模式，并非用于确定性裁决的共识算法；而在理论层面，根据 FLP 不可能性定理，在网络延迟无界的异步模型下哪怕仅单节点故障，也不存在必定能收敛的确定性共识算法，工业界主要依赖随机化选举超时在绝大多数场景下达成快速收敛。 讲者总结指出，一致性与共识是分布式系统中最复杂的理论基石。受物理网络延迟与 FLP 不可能性定理的硬性约束，工程实践的核心不是盲目追求单点线性一致性，而是看清全序与偏序、延迟与吞吐之间的客观取舍，按业务容忍度设计架构。

[0:00] Scott Shi: 把复杂的分布式多节点系统抽象得像一台单机数据库一样简单 [5:00] Scott Shi: 你真的不知道怎么解释的时候，需要你比较有想象力 [20:00] Scott Shi: 保持线性一致性的时间代价与网络延迟（Network Delay）成正比 [25:00] Scott Shi: 当网络分区不可避免地发生时，系统到底是要选择一致性（Consistency / Linearizability），还是可用性（Availability）？ [25:00] Scott Shi: 如果一个请求延迟达到一个小时甚至一百天，与目标节点彻底宕机在逻辑上毫无区别 [35:00] Scott Shi: 在海量大数据环境下，系统中超过 99% 的日志和数据操作根本不是严格的事务，真正的 Transaction 占比不足 1% [45:00] Scott Shi: 当你收集到两边的 Lamport 时间戳去比较大小时，你已经是在“事后追溯”（after the fact / audit）了 [55:00] Scott Shi: 协调者将 Commit 决策写入本地持久化日志（Commit Log to Disk）的物理落盘瞬间 [65:00] Scott Shi: 在安全性与一致性保证上与 Paxos 等价，但大幅简化角色定义与状态变迁 [77:15] Scott Shi: Gossip 并不属于共识算法

[0:00] Thank you. Thank you. I talked about it, but did you hear me? Thank you for listening to me. Thank you. Thank you. Oh So I just talked a few days ago, no one could hear me saying anything. I just said, I'll just say this. I'm sorry, I thought you could hear me. I'm not sure if I can hear you. I'm not sure if I'm talking about this mic. I can see it very fancy, but it's pretty bad. Okay, I can see it very fancy. I'll just say this. I'll just say this. I'll just say this. We talked about consistency and consensus. And then And this consistency is there two consistency? One is a database consistency, and one is a consensus consistency. And the database consistency, for example, in a period of time, there are two people on call. And this consistency is a client logic. The database doesn't care. That's false. That's a client logic of consistency. But we're talking about consensus consistency. It's a different replica of data and replica of different replicas. And this is because we are doing this replicate data. Data is actually to ensure at least one of the pieces. And the reason is that if you have one, you can use the server data, right? It can guarantee durability. So when one data center is broken, you can still read the data center. So consistency is very different. So we need to make sure that consistency is data based consistency or distributed system consistency. And this part, the main thing is distributed system consistency. And distributed system consistency is definitely going to exist. Because we have data replica, it will definitely exist. the replica, synchronized replication, so you can do committed data is not Inconsistent, but you actually have to do it in consistent. The on-committed data is still inconsistent. So consistency, because it's replication of the value, it's definitely存在. So we're talking about consistency. So we discussed the first distribution system of the concept. The first distribution system is to do the first distribution system. That's the distribution system. It's to simple simple. Simple is what? It's a lot of systems, but you want it to be a database. So it's called Lineability. So, if you have the storage behind the back, whether it's primary or secondary, or master/slave, or master/master, or whatever the database is replicated, From my client's perspective, you feel like in the same database. I feel like in the same way, I just have a database interaction. So this is Linearability's definition. [5:00] 然后这个Linear Benetting和Serialization是不一样的因为这两个是不一样的,最常见的不一样就是,比如说这个snapshot, Serialized Snapshot Isolation它是满足Serialization,但是不满足Linearability的,因为它不满足Linearability的原因是你这个Linearability应该是读的是,就是你读的是最新写的Data,但是你这个,你这个就是Snapshot Isolation,如果你有一个Transaction长的话,你读的是Still Data,是吧?所以它是不满足Linearability的但是另一方面如果你满足Linearability你不一定满足Serialization一个简单例子比如说你有多个Object去写的时候多个Object去写的时候你对于每个Object来说都可能都满足Linearability然后但是对于总体来说你可能不满足Serialization 是吧你对于整个多个Object的写你可能不是同时写入或者是Oh, Nothing, Serialization可能是不guaranteed的总体来说这个是其实非常复杂的一部分,大部分面试也不会考虑,但是对于你的理解来说,特别你要设计一些跟Teta Base相关的,不是这种casual的,不是这种你允许data loss啊,或者是这种的话,你可能都会有就是,可能会有所帮助。其次的话,你也可以就是帮你argue一些非常奇怪的case,是吧?然后我最近遇见了一个特别有趣的Case就是我们deploy一个coder嗯我老婆deploy code,然后她那个file descriptor直接往上找然后它有一个file descriptor leak,然后我们仔细看一下那个configuration好像没有 leak,然后它那个call还是一个redshift的call,所以它call非常infrequent然后它那个file descriptor是每半小时早大概好几千,大概早应两千,就是你file descriptor每半小时leg大概两三千所以就很奇怪,非常 weird scenario 是吧,然后我们就,现在没有讲解为什么,但是你就知道这个computer system里面,所有的 weird scenario 都可能haven它是用 Scala 写的,所以这个有可能是 lazy class load 的,因为 Scala 会 compile 从 java 执行所以有可能是这种lazy的class load,然后open了什么,但是我们现在的话还没有调查出来然后你看其他的那个就是包括其他的Engineering做Blog的时候,你也看到很多奇怪的东西啊比如说我记得我记得有个这个Twitter给了一个talk是叫Skill的TTL然后它造成的原因就是就是Twitter它做了很多cash比如说它对这个胡人队的这个胡人球队Los Lakers profile就是主页Company Profile和Brand Profile做了一个你搞Cache,然后你读这个Cache的时候,你就会看到这个忽人队主页,然后你不需要去读Database。然后这是一个真实的incidence,大概在2013年还是2014年的时候,你实际上访问不了胡门栋组业了,就是你去胡人队的组业,它会显示的是,没有组业就是NOT,就是Page Not Found, 404,然后他定了当时给的TekTok的原因是,他们不知道为什么他只知道的是他们当时开始 expired 然后去 database 读但是 somehow 读到了一个一个now value,然后这个now value被cash了12个小时就是说你现在你database这个cache value expire了,然后去database里面读一个字,这个是有一个talk,也有一个tagtalk的,你可以搜一下叫skill的ttl,然后然后去读database的值,然后读了一个NOT,然后这个NOT是被固定的开始12个小时,所以这个胡人队组业在12个小时内就是NOT FOUND然后这个12个小时的Cash Value expired 了以后呢,然后它还显示出那个互人队组业了。对于这个公司来说就是一个 big outage,他们花了很多地方时间去做这个 post analysis,分析不出原因来。所以这个talk 也很有趣,就是它当然设计了一些比较简单的方式来解决它,但是到底是什么原因?其实不知道的。你有一些很奇怪的东西你是很难看出来的原因并且这种东西的话即bug式即接耗时你很难解释的原因所以有时候说我们学的很深入,就是说学那么多transaction东西和linearability东西有什么作用?我觉得很大一个作用就是你真的不知道怎么解释的时候,就说potentially什么事情可能happen,这时候就需要你比较有想象力了需要比较有想象力,写程序的时候有想象力还是挺重要的好,这边的话就是说,Linear Billionty,其实是我觉得在工作中还是挺常见用的一个东西,因为这个就是经常会经常会经常 [10:00] 造成一个inconsistent的东西或者造成一个outage或者造成一个一个wrong answer然后这时候你就可能思考一下这个系统里面哪块没有满足linearability的问题然后我们看一下解释linearability的这个图我们看到这里的话,它其实是有多个Client在进行操作的。这个CAS是ComparedSet,就是先对比。比如说CASX24,就是先对比X值是不等于2。如果X等于2的话,把它set成4,就是ComparedSet。所以这个就是CAS所以我们看这块的话,它其实是有多个Client进行操作的首先是有一个,就是这个Client D在Write的这个,把X的设置成0,然后返回了OK然后它真正那个Automic Operation,就是说我们一直在强调一个Transaction和Lineability,一直在强调一个Automic Operation,就是在那个时间点之前你这个操作是没有 committed的,在那个时间点之后的操作是 committed的。它这个 atomic operation 是画成这个灰色的线,然后对应到这个时间轴上。所以呢,我们可以看到从这个Client的这个D的角度来讲,它是先把X写成0然后呢对比x是不是等于0,如果x等于0的话,把x4乘3,然后它fill掉了,因为这时候x不等于0了然后从climb c的角度来讲呢它是首先读了一下x的值然后读出x等于1然后又读了一下x的值读出x等于2然后在x等于2的情况下做了一个compared set然后把x设置从4然后最后返回是OK了如果从ClientB的角度来讲的话它首先是读X的值然后读Z是1然后做了一个Comparside,然后把这个X的值变成了2,然后这个Comparside是成功了,然后再读X的值,然后它这个X的值读出来2,然后这个值呢其实是有问题的,我们一会稍后看为什么这个值是violateLineability的然后这上面这个讲的就是什么呢?就是,上面ClientA呢是先把X的值写成了1,然后再读X的值,然后读出了4,好,这是所有的Client,就是我们每一个Client进程单独思考了一下。如果我们把它整合的话,你会发现这个时间轴是这样子的。首先这个Client D 呢,首先把X写成0。我们注意到,Client D 在把X写成0的时候,它其实返回给这个Client OK,其实是持于Client A 的。所以Client A在ClientD还没有写入X等于0的时候已经知道X就是已经把x等于1覆盖过去了如果它这块进行读的话比如说这个clientB来说clientB进行读的时候他读的时候这个值,他其实在这个读呢,是在这个地的写之前的,所以他这个开始时间是在大家写之前的。但是他这个读的时间其实在X写0和X写1之后的所以这个就是说,虽然它结束的时候,我们看这块这个例子其实相对来说比较比较有趣的,就是说在Client B读到X=1的时候最早的鞋还没有返回最早的写是这个x等于0的写还没有返回给clientD,然后clientB就读出来x等于1了这个是OK的,因为我们说在这个distribute system里面,你这个message是可以delay很久的。所以你这个写的时间,就是你最后拿到answer的时间,不一定是在database先后顺序发生的时间。就是在 database 先后的讯息发生时间不一定是拿到 answer 的时间所以这种情况下的话,这个操作是不违反 Linearability 的因为它就是存在一种time window它存在一种time window是什么呢?就是Client D 还没有写入的时候或者clientD写入了以后然后clientB进行读的操作然后读到这个值虽然clientB在这个操作之前是吧然后clientB还有一种可能结果是什么呢就是它的读的操作在这儿的就是在这个clientD写入之前那这样的话它会返回的一个结果是没有读到任何纸他没有读到任何值是吧所以这种情况下的话也是一个 valid answer 也是没有违反 linear ability 的我们就说比如说就只有两个 operationD进行写的操作然后在这块返回OK了然后B进行读的操作然后B读的操作是在他写之前的然后他返回是在很久之后的假设只有两个那这个也是满足 Linearability 的因为你不知道它整个这个transaction里面具体的读和写记在什么时候它存在一种possibility存在一种 possibility 它的读是在它写发生之前的那么如果它存在这种 possibility 的话它是不违反这个 linear ability 的也就是说你只要存在一种possibility,来把所有的这个database写和读,然后投影到像这种情况下,把所有database写和读,同意到同一个时间走上同意到一个Single Deja Base 上 [15:00] 能解释它,然后它没有 violation那他就不违反这个linearity所以我们看这种情况下,这个比较复杂的操作啊你先把x=0写过去没问题然后ClientA把X1等于写过去没有问题然后ClientB进行了一个X2的操作,然后返回了1这个是没有问题的,你没有违反这个Linearability,是吧,就是假设它是一个DataSingle Database,它确实是一个Single Database然后呢你Client C呢又进X2的操作也返回了11这个也是没有违反Linearability的然后你这块进行了compared set 把x设置成2了没有违反Lineability,然后进行读,读出来是2,没有违反Lineability,然后你这块进行了一个Comparset,然后你进行读,然后X等于2然后这块是没有影响Linearability,但是你这块如果读出x=0的话,那你其实是违反了Linearability,因为你这个时候x应该不等于0了。是吧所以你这个操作应该Arrow的,但如果这个操作过去的话,通过的话,那你其实是违反Linearability的。因为你是先是x=2,然后又revert back to x=0了。然后这块的话,set成了x=4,然后你有个读,然后这个读的话,返回来x=4。然后最后再有个读,然后说x=2,那这个是违反Linearability的因为这个x等于4已经返回了,并且这个x等于2的毒是严格的strictly after x等于4的这个x=2的读是strictly after x=4的,所以这个是影响这个linearity的。假设我们把x=2的读往前拖一点,就是这个更前一点,拖到这个位置。我看我能不能画一下嗯我尝试一下我看能不能画一下啊可以笑一下好我们假设这个呢,RAID是从这开始的甚至不需要那么多对是能不需要这么多只要从这开始的那么它是不违反 Linear Ability 的为什么呢 因为它这个读的时间呢可能会在这儿这个是他读的时间所以他在这读的话他确实等于2对吧,它如果在这读的话,它确实等于2,然后等于4,所以如果读的操作时间再长点的话,它是不违反linearability的。但是正是因为读呢,就是它这块有时间,所以是strictly after x 等于4,所以说他在x等于4读到以后又读到x等于2所以他是违反linearability的不知道有没有解决大家的疑惑相对来说这块逻辑是比较复杂的如果我们high level的说一下,就是说linearability是什么意思呢?linearability就是你有多个database,然后多个database有多个replication但是你对多个Diabase进行操作的时候就是一个是读一个写的是操作你可以投影到就是project到一个database上就假设就像只有一个database在处理所有的读和写操作你刚写入的值能被读到那就是recency guarantee,那就是lineability像这种情况下,当你argue一个系统是不是满足Linearability的时候,你只要有一种time scenario,只要有一种scenario它是在 Linearability Guarantee 情况下可能会出现那它就是满足 Linearability 的如果不存在这种 scenario 一定不存在的话那它就是Valid Linearability的然后对于Distribute System来说的话,因为它这个执行时间太快,并且它执行的scenario特别多所以任何可能出现的Case,给它足够长的时间就一定会出现,就像我们之前说的就是经常讲的一个很有趣的一个概念,就是说,如果给一个computer来不停的random print character 的话Random Print Character 给它足够长的时间,它总是能打出一个莎士比亚的作品,全部可以打出来的。这就是一个概率问题,给它足够的时间的话,即使是一个Random Output的一个Computer,也可以打出莎士比亚的作品。然后另一个概念就是一个概念就是说,假设你是一个随机漫步的人,在一个二维二Dimensional的一个2D就是一个平面实际漫步的一个人那么给足够长的时间你一定会回到原点在两维平面随机面部的人在给足够长时间一定会回到原点对三文是不敢听的,就是3 dimension的话,如果你是能上下左右前后走的话你是不能guarantee回到原点,这就是数据证明的但是如果是个两维平面的话,你是一定能回到原点的。这块一样的,就是理论上能出现的这个值,给时间足够长,它在这个Compure System中一定会出现的,特别如果给这个Distribute System打交道很多的话,它会一定会出现的。然后有人问说这会儿为什么B读的是2?他可能读的是个replica 是吧?如果你读那个 [20:00] Timerray的话应该读的是4但你如果读 Replica 的话可能就读的是 2 的所以他读这 2 的可能 2 的很有可能是读了一个 Replica 因为这个 Database 它不是一个一个database 如果是一个database的话就没有lineability什么事了是吧它肯定是多个database,然后多个database前有多个replication什么的好,我们看下一节我现在就把这个插掉谢谢大家嗯我怎么要把它擦掉呢? EraserOKOK 好 然后我们接着看,就是说,这边的话,LinearAbility这块的话然后它这块的话就是简单解释了不同的之前的那个replication就是single leader replication能不能实现Lineabilitysingle leader replication呢是可以potentially实现Lineability的这个是可以实践的,它需要进行一些优化然后因为我们思考一下这个Single Linder的这个Replication它本身是有Linearability的潜质的,因为它只有一个Single Linder,然后它所有的这个所有的log是可以从这个leader来进行发的,他把这个所有的这个replication log 发给所有的 follower然后 follower strictly follow replication log所以它是有实践 linear ability 的潜质的然后我们读的时候,我们读的时候就只要从这个leader上读的话,那它就是满足linearity的。或者是我们把它变成一个synchronized replication,那不管是从leader上读还是从follow上读,只要你不是read on committed的话,你都是有linearity的。然后,Consensus和Linearability是同一个概念,Consensus和Linearability是同一个概念,如果我们分的更细一点的话,Consensus应该是Linearability的Compare的Set,所以Lineability的Comparset和Consensus是同一个概念的,最终是等价的对于Multi-Leader Replication来说,它是不存在Linearability的,这个的话也是比较好证明的。为什么 multi-leader replication 不存在 linear ability 的?因为你你读不管是读Leader A还是B,你得错值是不一样的,是吧?它本身就是不同的server,并且这两个server之间是没有交互的,短时间内是没有交互的,它eventually会 consistenteventually will resolve the conflict但是一开始的时候他们是有conflict的所以他们之间是不满足Linearability的然后这个Leaderless replication是不是Linearability呢如果你是要看Denimal,Denimal说它是Linearability的,所以我们就说那个,我们不是上一次讲那个就是Uber的这个Payment怎么做的,它是用了Denimal的Linearability Guarantee,是吧?他们说他们是Linearability的,当然这块的话可能会各种Counter Case,各种Counter Case出来,它这个可能我觉得还是一个学术研究问题啊,就是看起来更不像是 Linearability,只不过它出现 Linearability violation 的概率很低,是吧?你可能得想一种非常奇怪的 scenario然后才能会出现违反 Linearability Guarantee 但是看起来更像是不是 Linearability 的然后这个书里面也画了大量篇幅解释为什么不是 Linearability 的但是这块很难arguer的一点就是其实Linearability本身就是一个非常复杂的概念,就是你的这个age case, risk condition 挺难找并且你早见了以后,你可能很快就fix掉,是吧?如果你早见一个Linearability,说它不是Linearability,很快就fix掉了。但是还有可能出现更多的risk condition,它这个risk condition可能是无穷无际的risk condition,是吧?你没办法从逻辑上证明它是Linearability的,那很有可能就不是Linearability,是吧?我记得好像Ross,我那天跟Ross聊,Ross也说他们这个payment里面用DynamoDB做payment,做这个payment好像确实出现一种比较weird的scenario就没法解释这个payment的为什么loss很多时候这个DynamoDB确实确实就是它那个比较confusing,特别是Lineability 这块比较confusing,所有的Race Condition 都可能出现好,最后我们说这个Linearability的Cost是什么,就是有人写PayPal证明过Linearability的Cost through Network Delay所以你的Linearability的这个就是你的Linearability的cost就是时间cost有proportional就是你的proportional to network delay这个是proportional的好然后最后一点的话就是这个CAP,我觉得相对来说,consensus algorithm,包括就consistent里面最有名的一个说法就是consistency availability partition 里面三个选两个,但是这个说法是不对的,这里面的 consistency 其实就是 linear ability其实讲就是Linearability,表示是Linearability的意思。这个说法是不对的就是因为这里面consistent [25:00] availability是你设计中可以选的但是partition它是一个fault它是一个一定会发生的事情就是partition是一定会发生的事情所以你其实是没法处死partition的因为你如果是做一个operating的话你比如说你要operate一个data centerpartition不是你能选的事情partition是一个fault给它足够长的时间partition是一定会发生的所以说给它足够长时间莎士比亚作品是一定能被水机写出来的是吧或者给它足够长时间你一定会走回一个二维平面的原点的所以这个partition你是不能假设的所以更多时候这个CAP它不满足的这个条件就是CAT这个就是你三条不能同时满足你应该这么解释就是说如果发生partition的话你是想要lineability你是想要consistency还是就是你想要consistency还是想要availability就是如果发生partition的话你是想要availability还是要consistency如果你想要availability的话,就是这个Denimal这样设计的我短时间内不consistent,无所谓,像Denimal的整个设计就是maximum availability 去设计它也是被 CAP inspired 的它就是maximum availability 去设计的如果你发生 partition 的话你去 lean over to consistency或者 linear ability 的话那你其实就是传统的 db还有包括这个传统的这个 two-phase commit 这种是吧用 two-phase commit 的这种就是 guarantee 这个 transaction当发生 partition 的时候我这系统就不 work 了不 available 了但是我的 consistency是有 strongest guarantee 的所以这个解释distribute system中一个设计,就是这个CAP解释的时候,就是说你不能同时选C和A,因为partition的发生是你不能控制的,所以你不能同时选C和A就简单问一个问题就是partition tolerance在这里是到底是指就是在一个系统里面任何两个node之间就是它可能会存在就是Network Delay还是指任何一个机器可能会挂掉这块的话这个partition tolerance的话好问题其实其实您可以这么想就是delay和挂掉是没有本质区别的你如果这个delaydelay了100天那你和挂掉是没有本质区别的但是computer sense这个里面你delay一个小时那和挂掉本质也没有区别的所以后面说的consensus algorithmdelay了就相当于是挂掉了基本上consensus algorithm的设置delay就等于挂掉它是不区分这两者的然后其次你一个node的挂掉和你和这个node发生了partition和其他所有的node分隔开其实也是没有本质区别的对吧你一个node挂掉了就是一个node挂掉或几个node挂掉和这几个node的和剩下的network发生的partition也没有本质区别从这个系统的观察角度来讲是一样的是吧但是有一种是有区别的就是如果你有就是比如说你有一个network然后你分成一半是吧然后一半是一半在线一半不在线不是你有一个network然后把它从中间切一半是吧平均切一半然后其中任何一半都没有任何offline但是这两半之间是没法相互沟通的那其实的话这种是比较一个特殊的存在这种情况下的话你其实任何一个partition就是任何你吃两个partition任何一个partition可能都是equal weight的那你可能会有各种conflict就没法去用这个多数来决定去resolve了这种情况可能稍微比较特殊一点不知道解决你的问题对对 我觉得是理解所以在distribute system 里面 我再强调一下在distribute system 里面 特别在考虑consensus的时候Network delay 和这个node的挂掉是没有本质区别的然后这个node的挂掉呢和这个partition 呢就是这个node会被partition掉了是有点区别的但是其实相对来说区别也不是那么大的对的所以这个如果从严格角度来讲的话你可以认为是这个node可能发生node的挂掉或者是network挂掉就是它link挂掉然后link挂掉的话就被partition了但是如果它这个link你可能会挂得更细一点有node然后有这个age然后你在certainage挂掉以后然后可能就会出现partition但是很多时候,比如说你两个cluster之间还有一个link相互连的话,其实也没有partation至少两个cluster之间还有一个link在连着,也没有partation所以CAP理论,比如说在实际上面应用,比如说master slave这种模式,比如像mysapl这种情况下 [30:00] 就假设是master down掉的时候你是没有availability,就是写的availability,真的就没有了对,其实就牺牲了availability,如果你想要availability的话,你要promote一个slave变成master当你promote slave 变成 master 的时候,就牺牲了 consistency当你promote的slave变成master的时候,你就牺牲了consistency,所以这个是个trade-off啊我不太懂 就是我肯定得要promote,假设一个机器,master down了,我肯定需要failover,对吧?没有,你可以不promote,你可以等master回来以后再serve,如果你不promote的话,你data是strongly consistent的,就是给他足够长的时间,你的master和slave是data 是 consistent 的对吧如果你不promote的话但你没有availability了吗但读的availability还是有的对吧你有读的availability但是没有写的就是availability吗但是如果你promote的话,你data是一定会inconsistent的的,因为depends on你是synchronized replicate还是asynchronized replicate,如果是Asynchronized Replicated的话,其实你的Master or Steel本来就会有discrepancy,然后当你在写新的data的时候,你之前的data可能都要discarded,可能都有data loss谢谢大家哦然后如果你是Synchronized Replicated,其实你本身就牺牲了一些Availability,因为你Synchronized,你整个这个时间会更长一点,就是你每一个Transaction消耗的时间会更长一点那你其实多少也是生了点availability吗谢谢大家OK谢谢大家如果是Synchronize Replicate的话,然后Synchronize Replicate的话,如果MasterDone,这个是Lintens增加的,如果是Lintens增加的话,其实这个哦你在 certain 之后的话,reacted 也是受影响的。但是这个 CEP 好像不是这么解释的,CEP 这个里面是,这个不是这么解释的,更多时候解释的就是说,在Asynchronize 啊,或者是这种它是非常general的一个解释,非常general的一个解释就是这两个没法一直保存,如果你要 strong consistency 的话或者你这个Linearability要guarantee的话那availability总是要受影响特别在发生partition的时候对了解一点,然后我其实想问的就是比如说DynamoDB也好,然后你选比如像MySQL就好,就为什么我们通常说DynamoDB是Preference Availability,然后比如说SQL这种是比较偏向于consistency,就具体到底是怎么比较,就是这个tadeoff到底发生在哪里首先我们先说为什么Sycle是prefer linear ability,就是我们不要用consistency, consistency比较confusing因为SQL设计的时候,它就是为Linearability设计的就是它设计的时候就是它transaction 当你写sicle rule 它这个transaction 其实就是如果对于single object 来说就基本上就guarantee 了nearability特别是这个two-phase log已经guarantee linear ability了所以当你用Sycle的时候,你的那个Consistency其实是很好的,但是你的Availability呢相对来说没有对availability进行优化然后我们为什么说这个Cassandra或DynamoDB是满足了AP呢?因为如果你看Cassandra那篇paper的话他从始至终他设计的这个priority就是availability所以不管是这个sloppy,sloppy,chorum,pinted,handoff啊他所有的设计的根本的原因就是为了availability包括这个chorum整个靠着我们设计的思路的这个原因就是为了 availability所以它这个好所以它这个设计的理念就是为了availability来设计的,它也是被CAP所inspired的,就是说我们需要不需要那么strong的consistency database,我们如果牺牲点consistency的话,那我们能不能保证我们的service永远不offline谢谢大家所以我不知道有没有解决你的问题就说解决了对谢谢大家谢谢大家所以,CAP 概念是2000年左右提出的,它提出来的概念就是鼓励database设计方,希望database设计方是什么呢?能多考虑一下其他的 possibility而不是只focus on linear-billage,因为当时2000年的时候,我们可以想一下这3PO system其实没有那么多吗?一会儿刚有这个就是这个Napster 就是刚刚这个peer-to-peer system 那会还是盗版音乐这种Peer to peer system,那会儿刚好这个东西其实它这个Distribute System 虽然更早 [35:00] 就有了 但是它其实这个大家focus还是在consistency,你设计这个系统还是为了这个Bank的Transaction设计的所以他当时提出这个理念就是说我们要不要额外考虑一下Vilibility不是所有的不是所有的这个database上的这个operation都是transaction 是吧?没必要一直guarantee consistency所以是有了这个database的设计力实际上你看的话我记得这个就是cafka这个conference里面的cafka founders写过一些blog说当时为什么设计cafka是因为他们观察到他们在linkedin的时候cafka是linkedin就是从linkedin的engineer设计出来他们在LinkedIn的时候发现99%的这个99%的这个Log和这个Datadata操作吧,data operation都不是transactionTransaction只占了不到1%那如果你transaction占了不到1%的话,那么我们是不是不需要把所有东西都变成transaction?那我们是不是可以牺牲一点consistency?我们是不是可以牺牲一点durability?然后做这个optimize down这个speed 是吧所以他们就设计了这个这个 Kafka 的 login system 是吧?就是你如果不是一个 transaction 的话就走 Kafka 全就行了 是吧?然后 Kafka 在这个再接一个SUNC,然后再存到什么其他地方然后为做Analysis,就是Offline Analysis,或者是Analytic Analysis但是你其实如果你不是Transactional Data的话你是不是可以用卡夫卡就放到卡夫卡里面就可以了正是因为有这样的想法,就是卡夫卡为什么被发明了,后面他想了各种什么event driven好像相对来说都是之后了吧就是之后的这个Event-Draven concept 然后后面to share把他写了卡夫卡里面但是他之前的话其实就想一个写一个比较 efficient 的 systemEfficient system 怎么样处理各种不是 transaction 的一个 data operation所以, again, Cassandra 就是为 Availability 设计的,所以它肯定提供 Availability 更好一点。所以我们读 Cassandra, Dinamo DB 这个 paper 的时候,它从事之中强调 Availability 。当它做 trade-off 的时候,因为它的go就是为了提高availability,所以它所有的tradeoff都是提高availability进行设计的。好我们看下早Total order replication, Total order and Partial order, this is a theory of a theory of a theory.你比如说A和B和B和C之间是没法进行排序的事吧,或者是A和B和B和C之间是没法进行排序的事吧,嗯因为它本身是没有等价的排列的价值嘛,就是没法进行排列的价值但是有些东西是可以partially order的,比如说多个operation比如说在Gate里面,GitHub里面,你有多个Branch,是吧?然后你最后有一个Master Branch,然后多个Branch merge到Master,是吧?最后eventually merge到Master,那么在两个多个Branch之间,这两个多个Concurrent Branch之间,你是没办法进行排序的但你最后merger的master是在这个多个brunch之后的,所以说你这个其实是个partial order这个pass order更多像一个就是有点像DAG 如果你把Parture Order画出来的话就是DAJ Graph然后你可以把它画成一个DA对管Total order更像一个link list,是吧?就是一个list,然后它之前的就是发生在前,然后之后就是发生在后所以我们如果从这个角度来看的话Linearability的cost还是太高,因为Linearability的cost和Lightwork和Lintensive的cost是一致的很多时候Linear Ability, Linear Ability 就是 Total Order, 是吧,我们把所有的 Operations把它一个一个拼到一个 single database 上,所以 Linearability 就是Total Ordered Operation但是很多时候,我们其实不需要知道Total Order的Operation,比如说我们思考一下在Database里面做那个Serialization的时候,如果有多个 concurrent transaction最后只要它是concurrent,它以什么样的先后顺序进行commit,其实我并不care反正它们都是Partial Order嘛就是你有多个Concarned的Transaction你最后这个A和B是concure的,A在前还是B在前,我们并不care,假设是这个假设是没有conflict的那你A在前和B在前我并不care那最后的话从database的角度我是有个total order的但是我们这个total order不管是AB还是BA从Database的角度是无所谓的虽然你最后有个Total Order但是从Database的角度是无所谓的所以 [40:00] So the concurrent operation, What is it? What is it? What is it? What is it? What is it? What is it? It's not a casual order. Partial order. What is it? So we often have a consistent distribution system in the distribution system. We don't have to seek total order. We only have a casualty guarantee. We can use partial order. So this is Lampod. This is Lampod. It is a very long time ago. It was a very long time ago. Lampod is a Lampod time stamp. What is this? In the database, we said in the database In the distributed system, the clock is It's not a high level. Your device A clock and your device B clock can be compared to the same. Lampod says, how can I set a reliable time? Can I do this casualty? Can I do this in the time stamp? So Lampod is set a time stamp. What is this time stamp? It means that you have every time stamp with your device. It is actually a logical time stamp. It's not a total time, because it's a relative concept. It's more than a time. It's a logical timestamp, so it's a logical time stamp. So in this timestamp, in this system, you have a time stamp. One is your node number, and one is your event sequence. So let's look at the node number 2. It's a simple way. You have the first event, so you have the counter is 1, the timestamp is 1. Then you have the second event, you have the timestamp to become 2, and the third event is the timestamp to become 3, and the fourth event is the timestamp to become 4. But this time you have a client from the other client. And this client, The max is 1, right? You can see the client request max is 1, and the local max is 4. Then you should return to the two points, so you return to the 5. And then after the request, because you've already written it, you have to write it in 6. that we do any node 2. He has any request for it is sequence. So in Node 2, the request is sequence. So the logic of the relationship is 2 at 3, 3 at 4, 4 at 5, 5 at 6. For the node 2, it is a sequence. And then we'll see node 1. Node 1, it was written in the first time. This one is in any time. So this 1, this 1 is the time stamp 1. It may occur in this This Node 2 of 1, it may be found in Node 2 and 4 of 1, it may be possible He wrote it again, because Klant said that the most small number of the number is 1, You have to write the next one in the second one. So the next one is written to the node 2. Then the next one is written to the node 2. So client A says, I write the sequence 5. I don't know the sequence in the next one is written to the node. The sequence in the next one is written to the node 5. So when he wrote this node 1, the sequence of node 1 will bump into 6. So we'll see this two of them. From node 1's perspective here, It is also a casual order. Why do it have casual order? In the first step, the small time stamp will be in the back, the small time stamp will be in the back, the small time stamp will be in the back, this is guaranteed. But in the cross node comparison, How do we do it? CrossNode's time stamp configuration is that your large time stamp is guaranteed to be bigger than the small time stamp. If these two timestamps are the same, you can decide who is the same. Because from this time frame of view Operation 1 and Operation 1,2,3次 are concurrently happening. Operation E2, Sensor Concurrent, is a operation E2, Sensor Concurrent, is a operation of the concurrent. So you can put it into any time, any time is making sense, not to violate the operation. and not valid concurrent linear ability But when we set up the design, we need to ask that if these two timestamps are not the same, Time stamp is the same thing. Time stamp is big, and it is happening in different devices. So in this case, it thinks that all the 2, 3, 4 events are happening in node 1 and time stamp 1. Although this is probably possible in time, in time, is possible. [45:00] Time-Time就这么设计了是吧,因为你没有一个你没有一个sauce of truth 告诉你说它到底在发生什么时候,那么我就用 time stamp 来比较。如果timestamp相同,那就用node number来比较。所以最后比较的结果就是这个Node1,TimeStamp1是在CIS所有的Event发生之前但是当它有一个cross node operation的时候,这两个timestamp相对来说就进行了一个sync之外。从这个节点之后呢从这几点之后呢,我们就知道这个Node11是一定发生在这个Node26之后的,是吧?就是这个不管是从它timestamp设计还是这个时间设计,一定发生在这个之后的,然后这个这个这个其实是,我们说这个其实是提供了一个什么呢?是把这个LampPod的timestamp是提供了一个unambiguous concurrency, ambiguous concurrent timestamp comparing tool.然后他Guaranteen the casual order is not violated我们用这个重新rephrase解释一下,就是说LinePod的TimeStamp是guarantee什么呢?多个Machine之间它的开入Time Stamp是没有被violated的它的Safety Guarantee没有被violated的就是你这个Time Stamp之间你用Lamp Power Time Stamp进行对比你的carot dependency是没有被violeted你是有carity guarantee的但是它到底是不是按你的order来进行发声呢有可能不是,就是如果你有一个Oracle,有一个先知的人物看这个全局这个事情发生的前后的话,它可能不是按那个lampod的timestamp这个order来发生的。但是它guarantee你的casual order没有被validated这是这个Lample Timestamp我们看见LampoutTimeTime其实是不能满足所有东西的,比如说比如说,我们现在同时有两台机器,说我要生存一个域名,我要生存Uber.com,或者我要生存Google.com,我要生存这个域名,那么你看到的时候,当你用Lambport的timestamp来进行order的时候,你已经是after effect,就是你事后才知道谁在前谁在后但你在当时的时候,你不知道有没有其他Node同时在声称Google.com这个域名,是吧?所以这个Lampout Timestamp这个Lanport的蓝博特时间Lanport time呢它只能做一个audit也就是说它可以事后追查实在前实在后但是它是没办法当时做出决定实在前实在后的所以这个呢,Lambop Timestamp是不能guarantee就是你不能解决这个 concurrent 的问题,你也不能解决这个 total order broadcast 的问题,或 linear ability 的问题,或 consensus 的问题因为它设计是不够的,就是它这个设计是不够解决的consensus问题的然后这块有一些论证解释为什么Total Order Broadcast是等于compared center linear ability等于consensus我们这块就略过了,就是它这个论证也是比较复杂的,有点证明这个NP问题为什么是整价的感觉。相对比较复杂的 我计划还是略够了 因为这张确实如果你不自己去读的话我觉得我只能给大家提到一点 就是启发大家去读 这张的话还是要需要大家自己去读才能理解这个Consensus它确实是比较复杂的简单解释一下,这三个问题是相互等价的。Total Order Broadcast是什么意思呢?Total Order Broadcast是什么意思呢?就是你首先要guaranteereliable delivery,就是你在broadcast的时候没有任何一个message丢失了如果一个Message deliver到一个Node,那它应该delive到所有Node,就是All Nothing没有Message Loss然后其次的话,你所有的Message的Order是guarantee的。你这个order是1234的话,那你所有的其他node的order应该是1234。其实这个totalorder broadcast就是synchronized replication,就是replication。就是 replication, total order broadcast,就是 synchronized replication是你用replication log 来实践它是一样的嘛,就是你synchronize replication 什么的,就是你database 当且紧张,所有的master和slave都说我收到这个交易并且有这个transactiondeliver到所有的slip上了,那我才返回OK是吧,那我的所有的这个,那这种情况下呢,你其实没有message loss嘛,其次的话呢,你的message order也是一致的如果你们order不一致的话 你可能会有一些set effect 是吧replication log的话是 这个order是要guarantee一致的 否则的话你会有set effect所以这个Total Order Broadcast 其实就是Synchronizedreplication 许可信号: single leader synchronized replication是一系列的,一系列的 [50:00] analyze the replication. Compare the set linear ability is linear ability guarantee. It is the linear ability guarantee. It is the final point of consensus. What is consistency? We talked about consistency, and we talked about Uh. Two-phase commit. Okay, let's talk about two-phase commit. We have two stages in two phases. I'm going to look at this one. This is the two-phase commit. This is the two-phase commit. The leader election and atomic commit. This is the case. This is a question about the total order broadcast and consensus between the two sides. In this case, the total order broadcast is how 等下于 single leader. replication And this one has a two-phase commit problem. If you are in several devices, you can commit to the commit. If you want to ensure more data is consistent, you can be able to make more nodes. Commit, For example, let's give a simple example. When you do a transaction, you can do A and B at the same time. But because of partition, A and B are in different partition. I'll give you a example You can say For example, the most famous example is when you were in transaction, you modified data, and you used global secondary index. You use Global Secondary Index. If you want your index to your transactions, you can also be committed to the same. Then you use Global Secondary Index. Your index and your data are similar. 90% is not in the same node. not in the same partition. The guarantee is not in the same partition. If you want your index If you have the data, the index will be changed, then you need an atomic commit. The data update and index update is the same. In the database system, there is a two-phase commit. If you are on distributed systems, the first big big thing is to create a two-phase commit. I remember when I was on the distribution system, When I was on the DISTRIBUTION SYSTEM, my first big job was to do two-phase commit. And in the two-phase commit, it's a bit like this It's a bit like a proposal, like a proposal. First of all, you have a coordinator. The coordinator is a bit like a teacher. Then you have database 1 and database 2. Database 1 can be considered as a new man. Database 2 can be considered as a new man. And when you say this, you say this coordinator, you first say you're a marriage, you're a marriage, and you're a marriage. And you're going to give two of them a marriage. and it表示 that this thing you agreed. You know the context is what? In the database, the coordinator will also write the data in the database 1 and the database 2. Guarantee is that it will be more than the database. The "结婚" means that it's not the database. The coordinator will also write the data in the database. It will ensure that the data is completed. But it will not commit. Then, the time This is the case for the case. The coordinator is the teacher. The teacher will say, "A, you want to marry with B?" and "A" will answer. And if you have any reason to say no, you can answer no, that's the whole relationship of the relationship. About 掉了, but if you decide to do it, I would like to do it for you. Then you say yes. When you say yes, when you commit yes, you can say no. you can't be able to do this. To face commit, any situation can be able to do this. You can ask B, "B, you want to do this?" If you want to do this, you can't be able to do this. If you want to do this, you can't be able to do this. If the teacher is the same, he says, "The situation is completed, and this is already done, so the commit point is what is the same?" and then he has a proposal to commit. If the teacher has a proposal, he has a proposal to commit. If the teacher has a proposal, he has a proposal to commit. [55:00] 同意A和B结婚这个事已经写到小本子上了然后A和B回来看的时候确实看到结婚这个事情通过了他们已经成为合法夫妇了这个是有一个atomic commit point就是牧师把这个事写到小本本上对应的就是这个coordinator把这个Commit log写到disk上这是一个atomic point在这个atomic point之前整个这个transaction是在多个database上没有committed在这个atomic point之后这个transaction是在这个database上committed的那么其实这个逻辑是比较简单的但是这个复杂点是什么呢复杂点是可能会发生各种failure是吧比如说有什么failure呢比如说我新郎和新娘说愿意互相嫁给对方就committed yes了然后这时候找不见牧师了牧师突然消失掉了被外星人绑走了那到底牧师有没有把它记录到小本子上牧师有没有把这个结婚的事情公正下来那其实是没有人知道的因为这个牧师当掉了那这种情况下呢新郎和新娘呢就是这个node1和node2呢都是不可以about这个transaction的因为当你回答yes的时候你就不停的要等就直到等到这个牧师online所以你是不可以about的你知道吧就是你必须知道这个牧师当时有没有记录下来有没有记录到小本上然后他有没有记录完整的完整的记录到小本上是吧如果完整记录到小本上然后你就是表示合法夫妻如果没有的话那就是表示这个结婚这个仪式还没有通过是吧所以就是说如果是这个就是这两个人回答yes以后这两个database回答yes以后这块是很有可能会发生死索的就是你这个不叫死索不叫dialog但是很有可能会stuck在这边为什么会stuck在这边就是coordinator状态不可知coordinator状态不可知所以coordinator没通知他们中的任何一个人所以他这个fill他这个coordinator failure point和commit point所以可能会出现思索的状态好,然后还有一些其他的简单的scenario比如说这个coordinator就是这个node fill了node在write data之前fuel了node在prepare之前fuel了那这个coordinator的任务相对比较简单了我就可以报的就可以了反正您可以认为是这个律师连结婚誓言都没有读文然后其中一个是新郎不想读文就是这个设计的设计就是这个设虑的任务相对比较简单了我就可以报了就可以了反正就是你可以认为是这个律师连这个结婚试验都没有读完然后其中一个是新郎新郎跑掉了是吧那你结婚礼就举行不成了或者是律师读完这个结婚试验了就是这个data写进去了但是他没有问就是他没有就是他问那个你是不是有愿意嫁给他什么时候然后那个新郎新娘又挂掉了是吧那也可以终止是吧等他回过来的时候再说是吧所以这个是可以用这个结婚仪式来进行解释的我觉得也比较有趣的你确实可以用结婚仪式进行对比一下这块有一点非常有趣的一点就是如果两个人进行committed就是这个node进行committed以后他是要在不顾一切的情况下来是一定要知道结果的不管是yes还是no 他一定要知道结果的并且这个结果是只有coordinator知道的你没法从另一个人身上知道这个结果如果这个Coordinator在这个之后在他回答你们到底有没有结婚之前挂掉了并且永远没有online的话那你这个结果永远是不可知的那你Database1和Database2这个Transaction是永远卡在这里的所以他不可以接受其他的Transaction他是不可以接受其他Transaction的因为它的其他Transaction如果和这个Transaction有Data Conflict 的话那它这个其他Transaction就被Block 掉了因为你如果写了Data你就Violet的誓言了是吧举个例子就是新郎和新郎表示可以什么可以就是都同意了是吧然后律师跑路了是吧律师跑路的话那你这种情况下新郎和新郎是不可以接受再嫁给其他人是吧因为你不知道这个当前的结婚仪式完成了没有所以就永远卡在那里了所以我们就说为什么说这个two-faced commit的在这个no turning point就是在这个commit的这个以后呢它其实这个performance是极其糟糕的就是有一种scenario就是当你的coordinator挂掉了以后你的performance会极其糟糕因为你很有可能有一个transaction所有人都回答了yes所有人都回答这个transaction回答了yes但是你的Cordination挂掉了那你这个Transaction就block掉了你整个Transaction就blocked伴随block是你这个TransactionTouch的Data就全部被lock住了那就没有人知道结果了好 这块的话我也是cover了这个律师挂掉的这个scenario所以这个Two-Face Commit [60:00] 这个 performance是比单独的Transaction Performance要慢一个数量级的,甚至很多时候要慢多个数量级。我们之前讨论过就是说,当你有一个single node的时候,就是你一个single node现在每秒就能handle10^5^2的Transaction如果你用2-phase commit的话,你可能每秒钟只能handle 1000 次 transaction,甚至是 100 次 transaction,差这么多,差一个数量级到两个数量级,并且如果你出现这种 coordinator failure的话,当你出现这个Coordinator failure,当你律师在最后公正的时候跑路的时候,你其实机器是没法解决的,你必须用人为的来解决。所以这个 two-phase commit 为什么不喜欢被人用?大家为什么不想用 two-phase commit 的原因?就是performance 实在太差了,差一百倍了你一秒钟只能 handle 100 个 transaction好,然后我们最后看一下这个Consensus这块Consensus呢它其实是多个要求吧我们看一下什么样的algorithm是满足Consensus的首先Consensus就是语义来讲是所有人都agree on the same thing,是吧?你就说比如说,我们说这个到底是中国发达还是美国发达,是吧?到底是这个TikTok更有趣还是Facebook更有趣,是吧?你要agree on the same thing,是吧?就是你有uniform agreement,你不会说A觉得中国发达,B觉得美国发达,是吧?然后A觉得TikTok好玩,B觉得Facebook好玩。就是你所有人必须要决定同一个东西上。然后integrate什么意思呢?你做出的决定你不能反悔你比如说你做错决定说我打算今天去吃麦当劳是吧你就不能反悔说我今天去吃肯德基,你只能做一次决定。你不做两次决定,你作为一个 decision,你只做一次决定,作为一个 node 来说validate什么意思呢意思说当你决定Ada Shahal就是当你决定A的时候,A是其他no的proposed的不是不是一个凭空来的value如果没有这个validate的话,其实这个consensus设计比较简单,所有node都同意是0就可以了,是吧?你不管propose什么值,所有node的propose是0,那你是有consistency的,是吧?你是有consensus的,你说node返回0的话,你是有consensus的,但是你这个0可能不是其他node的propose的值,虽然你agree 0 但是 0 可能不是Channel的proposer 值然后最后的话是Termination 什么意思呢?就是如果你没有Node, terminated,那你最后总是会做出就是你如果有node还活着的话你最后总是会能决定某一个value的所以说我们来看一下这个,如果我们这四个要求里面,假设你没有valid这个属性的话,假设你没有valid这个property的话那所有node就无脑的选0就可以了是吧那你这个0其他都是满足的吗就是所有node都做了一个决定就是0然后所有的Node的决定都是一样的就是0,那所有Node的只要没有挂就可以写0,无脑写0就可以了,但是它是不valid的,所以是不满足consensus的。然后如果没有termination的话,那我们刚才讨论的two-phase commit呢,是满足这个consensus的。什么意思呢就是说我们所有的这个node呢都是agree同一个东西的或者是Single Leader Replication是满足没有Termination的Consensus的所有的Node都是决定同一个东西的,因为它有Master决定就可以了然后没有一个node需要决定两次,因为master决定一次以后就可以push到slave上了然后其次的话,Master的决定值可以是它Propose的值嘛。所以这三项都是没有满足的,都是满足的。但是这个Single Node的Replication是不满足最后一项的。为什么不满足最后一项呢?是因为如果master crash掉,slave没有crash掉的话,那consensus要求是slave之间应该是要决定一个值的,但是这个single node replication呢,就是Single Node Replication这个模式呢Master Seals这个模式呢是没法而guarantee最后一项的就是Termination是没法而guarantee的好,然后我这块的话可能不花那么多时间,我其实给了一个RAFT的一个实践方式我们可以在这看一下这个里面的话就是,我们看一下这个,就是这块有个algorithm也很好,叫我今天又读了一遍,就是这个FreeCodeCamp的这个Graph的这个Consensus Algorithm时间方式。现在已有的主要的Consensus Algorithm,相对来说比较固定的有几个吧,一个比较有名的就是这个,LanPod提供的这个LanPod proposed的这个哦Pethos是LanPod提供的,但LanPod的这个方式 [65:00] Pexels其实是比较复杂的Pexels推出了这么多年以后Lanpot写了很多简化版的Pexels其实Lanpot发了很多论文我记得我还读过一个就是他写了一个简化的论文就是这个论文的目的就是为了解释Pexels给其他人解释Pexels的然后就说明这个algorithm真的理解起来比较难然后Pexels呢是因为他理解起来比较难Countercase比较多然后在13年的时候12年的时候就是这个Stanford的就是这个Professor呢就写了一个比较简化易懂的consensus algorithm叫RAFT algorithm这个其实是一二年写的然后之后的话就是之后的话第三年写了看他是获得了一四年的这家paper其实很新了其实我觉得对distributed system来说三四年新的东西基本上就是carting age了然后五六年的基本上就是业界主流了五六年的基本上业界主流了三四年新的基本上就是carting age了如果再新的话基本就是属于research范围了就不属于industry 范围了所以这个其实是非常新的一个 algorithm这个Roughed algorithmRoughed algorithm它唯一的目的就是说我其实是Paxos我其实跟Paxos是一致的但我比Paxos更好理解就是Roughed algorithm设计的目标因为它简化了这个这个里面这个leader electionfollower leader和candidate之间肉的角色它简化了这个肉的角色我们看我们简单直观看一下我们就不过可说那个algorithm那么复杂的细节了在Roughed里面每一个node呢是有一个timeout一个timeout period一般来说像这个Hbase这个timeout period设计都是几秒钟也就是说你很多时候就是七八秒钟九秒钟才timeout但有的这个timeout呢就是有的database的timeout设计时间比较短可能只有四五百毫秒三四百毫秒我好像见过最少的只有100毫秒到300毫秒就是一般来说是短timeout但是很多时候是就是像HBase设计啊是长timeout就是八九秒是九秒的一个timeout那在这个timeout之间呢就是你叫一个term knowledge叫term就是在这个选举期间呢这个期间呢你叫这个term在这个term之间你如果是leader的话那你整个这个term之间你都是leader那如果这个term在这个term之内呢然后你可以不停地去refresh你的term是吧你可以不停地通过这个你可以不停地通过这个这个ping point是吧refresh的term然后当你当你算了这个heartbeat的时候这个heartbeat你就把你的term给refresh掉了我们看到这个是时间是1%我们可以稍微看快点对吧看快点的话实际上稍微再快点的话它实际上很多时候它这个当它没有refresh的时候当这个sr没有refresh可能whatever reason可能是timeout可能是这个srfill的话那它就不是leader了那他需要去propose一个新的term然后propose一个新的term会有一个新的leader然后当他这个leader fill掉的时候就当他leader fill掉的时候你会有一个新的followerpropose自己为candidate然后当主要的candidate决定他是follower的时候主要的candidate同意他是leader的时候那这个刚才的follower就变成了leader像刚才我们非常快的快进了以后大概在15秒之后他这个是随机生成的他这个确实是一个它好像是软在你的这个browser里面的一个Roughed algorithm所以它这个是随机生存的在15秒之后我们看到在15秒之后它的leader从刚才的s2变成s5了然后它term变成4了刚才term我记得可能是1还是term2我忘了看了但现在term变成4了也就是说在term为4的时候s5变成leader了如果这时候另一个node另一个node它没有接到任何信息然后它Timeout的话它会Propose自己成新的Leader然后它会把Term变成5它会把自己的Term变成5然后它当Term变成5了以后它会跟所有的Node说我现在是新的Term换时代了我Propose我自己成为President那你们选不选我如果别人没有看到更高的Perm的话没有看到更高Term并且别人没有timeout的话他会选5作为一个新的president的话会选5进行新的leader然后这样的话他们会所有人会agree说5是新的leader那么我们要用5来作为新的leader来然后这个5会不停的发这个term5呢这个s4在term5里面是leader的话他会不停的发heartbeat然后保证其他的node是online的然后这个heartbeat也是有讲究的如果你的hardbeat太frequent的话你这个hardbeat是发的时间太frequent了我们看刚才他这个hardbeat的时间大概是大概是100毫秒到几百毫秒之间他说这个hardbeat的frequency应该是在那个paper里面的Rough的paper里面他说hardbeat的frequency应该是比timeout的时间是小一个数量 [70:00] 比如说你TimeMod是如果你Timeout是10秒的话,那你Heartbeat最高也是1秒是吧?如果你Timeout,这个Timeout如果是500毫秒的话,那你Heartbeat最高,就是你的这个Interval最高应该是50毫秒,你应该比发的比50毫秒更frequent这一点。所以当你变成leader的时候不停的发heartbeat然后这个hardbit越小呢那你就越有可能发现这个,你就越有可能subject to your network这个fault是吧,Network发生fault的时候,其实这个是Network发生delay了,其实这个node没有down,但是你认为它down了,然后就开始了新的这个是吧你的Heartbit越小,就是你的Heartbit发的越频繁,那你就有可能subject tosubject to 这个新的 election 但是你 heartbeat 发的越不频繁的话 你可能会就反应越 slow 比如说我们举个极端例子就是你 heartbeat 一秒发一次 是吧 你这个 term 是 10 秒 你 heartbeat 是一秒发一次 那么这个 node 可能在一秒之前就 down 掉了 那整个一秒它 down 的这个时间呢 是没有人被 detect 出来的 就是你没有 detect 出来这个 follower 在接下来一秒钟一直 down 的这个状态 是没有 detect 出来的所以这个是这个是你这个Hardbit的这个Sat的Tradeoff好,最后一点,我们说为什么要用Consensus?我们可以这么说好了就是当你有 leader 的时候当你有 single leader replication 而你不想把 leader进行hard code层次的leader 是吧你这个leader down掉以后你还希望有个follower进行replace 一个 leader 的话,那你就需要有这个 consensus algorithm 决定谁是新的 leader然后你就要决定自己的 leader你现在有 leader 不代表你之后有 leader你现在有 leader 的话 不代表你之后有 leader你现在 leader 你只能保证这 term 是十秒 是吧你现在Leader Term Guarantee 10秒那10秒之后谁作为新的Leader其实是要这么多distributed node进行decision的然后进行Decision的这个步骤就是在杂乱武装没有一个Single Source of Truth的时候就是没有一个Single Authority的时候在这些杂乱武装就去Build System里面让这些node自发的决定一个value,那就需要consensus如果你没有 consensus你都没办法在一堆node之间,你都没办法决定到底什么值是什么只是crack value 是吧?你node A 可能说是2,node B 可能说是3,那你是没办法进行达成一致的,所以Consensus可以认为是distribute system最本质的一个东西,就是它决定什么value是正确的value,什么value是dominant value然后其次的话Consensus可以用在什么呢?比如说可以做Membership Management,是吧?我们这块没有讨论的是,比如说我们就拿这个Rough的Algorithm来说如果这个Roughed algorithm 你这个node进行了更改怎么办如果你这个membership进行更改怎么样你现在不是S1到S5进行Roughed了你多了一个S6 你想用S6来取代的S4 是吧那你的membership改变了 那你怎么样达到consensus这个其实是需要专门讨论的就是说你比如说你的S1 S5 多了一个新的node或者减了一个新的node 会有一个node replace另一个node你怎么样达到consensus 你可能之前满足了consensus algorithm在新的这个条件下就不满足了就没有达到Consens你之前能达到Dominant的这个多数在新的条件下是没办法达成Dominant的所以这个 consensus 这个就是你用的就是很多嘛,就是你实际上是在一个district build system 里面在多个peer之间多个node之间达成没有争议的一个值做一个决定是没有争议的一个consensus的决定所以它可以用在什么呢?比如说Membership和Coordination Service比如说就是你现在一个cluster里面有多少个node属于你的member 是吧,你的cluster里面有多少个node属于memberRootkeeper就是实践了这个了因为Rootkeeper就是一个consensus algorithm的实践包括ETCD,ETCD实践的就是Roughed Alchism,我觉得ETCD好像是Roughed Alchism,还是不是我不是很确定,这块可能大家查一下,ETCD可能也是实现了一个consensus algorithm,然后它就是说当你有它的时候你可以因为它实践了consensus所以你可以用这个Rulekeeper你可以pick back onRulekeeper和etcd来implementing a membership or coordination service.所以说你可以用它来实践一个这个 service,然后Consensus也可以用来分配工作是吧当你有一大堆Works to allocate to nodes的时候,比如说这个Worker pool model,或者是当你说这个哪一个node是哪一个partition leader 是吧?比如说这个node12345是partition7的leader那么这个assignment其实是需要consensus的因为如果你没有达到consensus的话你觉得12345是partition7的leader别人觉得54321是partition7的leader [75:00] 那你的data会有crafted的所以这个assign work to nodes 也是需要consensus然后最后一点的话就是service discovery你比如说你现在要找一个user service你想知道user service 在哪一个node上或者说你给一个user1234你想知道user1234在哪个partition上那这个的话其实都是需要consensus去实践的也就是consensus的用处之一然后最后一点我想提到最后一点理论的一个知识了就是理论上来讲在一个就是network unbounded的环境下就是你network是unbounded的情况下你在node可能会有failure的情况下你是永远不可能达到consensus的就是你的consensus convergence理论上讲是无限大就是没办法达到consensus就是在network有failure的情况下是没办法达到consensus这是一个理论的paper这个paper也是比说我们看到这个algorithm更之前198几年还是1970几年就有这个paper了所以consensus的convergence可能会很慢可能会很慢 实际上我们刚才看的这个rough的algorithm如果这个S4和S5之间有一个node断掉了就是这个node之间这个connection断掉了那你很有可能就永远不conversion你可能就永远不conversion的就S4和S5不停的相互当leaderS4和S5不停的相互当leader然后做不了任何其他事情也就要那个consensu就有点像这个repartition stomp这种感觉就有点像consensus stomp的感觉就是S4和S5之间相互不停做leader然后任何事情都做不了但是更早之前就是有人从理论上证明说这个consensus很有可能是永远不converge的这个consensus如果在这个unbounded network的情况下是永远不converge好这个consensus就全部讲完了这张相对来说是比较复杂的我建议因为我自己读过这个raft的这个paper也读过这个paxos paper我建议你们读的话读raft就行了因为这个RAFT 近几年有多个实践我记得我看前两天17年的时候我看17年的时候Python是刚刚实践了一个algorithm我记得有一个叫Python-GosomPython-Gosom是那个Python的conference然后17年的时候Python有个developer实践了RAFT的algorithm像18年的时候18年最近到18年的时候Kafka他实践了RAFT的algorithm就是用RAFT做consensus,然后才把这个root paper给取代掉。总体来说这个RAFT,反正RAFT发生的时候,我是不知道这个algorithm,我当时学习Tribute System的时候,RAFT还没有很出名,但是它读起来,它确实是可读性啊,理解能力呢,相对来说这个logic其实是比这个paxels要好理解多了。Paxos非常难理解,Paper也非常晦涩难懂但Rapt相对来说,你看它这个有向转的finance machine 相对是比较好理解的然后Paxos和Rapt,它的那个就是Worth Case也不一样Paxos的Worth Case,因为它设计的缘故,它是实际上是不同的node在不同term的时候,它Worth Case就是它Worth Case在raft的话是两个node之间出现partition的时候它worst case是会出现worst case它的worst case实践的out规则不太一样但是相对来说raft也是比较新嘛然后也比较好理解所以如果你要读concenters的感兴趣的话可以读一下raft我觉得还是比较有趣的还是比较值得一读的比较商量就是比较像这个解释其实不是太商量其实我觉得你可以给一个初衷生解释清楚怎么回事但是你要是把这个所有的counter case 想一遍的话还是比较伤脑的一个过程然后大家有什么问题吗然后我可以帮助回答一下相对来之前看那个就是Cassandra那个是用Gossip就是Gossip也算是Consensus它其实Detect有没有机器当掉了Gossip它应该是做Membership Management是用Gossip吧对 是的对 Membership的话您可以认为Gossip就有点像这个了只不过它不是有一个Single Node它可能是A发到B,B发到C,C发到DGossip其实是Hardbit发的一种模式那它其实是解决一个Consensus问题吗还是有点理论没有,Gossip和Consensus不相关Gossip和Consensus不相关Sensus的逻辑是什么意思就是在任何一个时间点对于任何一个Node来说 [80:00] 你知道随时leader任何一个时间点对任何node来说,你只要是leader,可能没有leader,可能没有leader,这时候在做leader election,leader election可能会持续好几百毫秒但是这个Consensus就是任何一个设断之后知道任何一个Node谁是Leader但是这个Gossip是什么呢? Gossip是,它更多是一个data的一个spreading,就是你把这个data从S5,然后传到S4,然后S4再传到S2,然后S2传到S1,然后S5又传到S3,它是一个data的eventually consistency的一个pattern,它是一个 broadcasting pattern啊Gossip is a pattern of broadcasting. When you broadcast, for example, S5 has the latest dataS5得到最新data它可以说把自己的最新 data 同时写到S1 S2 S3 S4 是吧但是它带来的问题是对于它的这个Network压力太大了是吧它同时得写这么多它Network压力太大了很快它这个Network变成BotlNet因为我们之前讨论过很多次Network是最重要的resource在Data Center里面Network是最重要的resource它的优先级甚至高于memorageMemory CPU,CPU不值钱的,大部分时候CPU不值钱的但Network是最值钱的东西是吧所以它不能一上来就 broadcast 嘛那他broadcast的话,他对于他的Network负担太大了,那他怎么办呢?他就把S5传给S4,然后在下一个时间S4传给其他,这相当于是把这个broadcast的这个load呢,是eventually distribute到其他load上了。所以这个Gossip给他数过长的时间,他拿到最新Data是会在所有的S1到S5上达成一致的所以broadcast是gossip是broadcast的一种pattern它不是一下发给了所有的Node去Broadcast,它是这种间歇性的慢慢的进行 broadcast 然后最后的最后的目的是为了eventually consistent那我在想那个这个membership management不是就是想知道就是通过Hotbeat之间知道哪些机器是 leader 哪些机器是 leader 哪些机器那个地方是 leader 然后哪些机器已经 down 掉了 就这个 post 才应该做到的对 这块的话有两个概念这块有可能是我读的有点欠缺,我不知道是不是有人用gossip来做这个membership的这个heartbeat的我不知道有没有这么做的,但是当我们说的membership其实是两个概念,我个人理解我们说的membership是两个概念,我说的membership是是这个Consensus里面的Mendorship,就是说,你如果想作为Consensus的Participant,你想作为Consensus的这个或者你想作为Consensus的这个Leader或者是Participant你这个Membership,这个Membership是要非常快的Hardbit你说的那个Membership呢更多时候是看这个机器有没有在online 是吧这个机器有没有挂掉那个是不需要你挂掉两秒钟无所谓你挂掉三秒钟也无所谓但是你在Consensus里面这个Hardbit的话一般是几毫秒几十毫秒发一个我们可以看一下我们可以看一下我们这个现在是50分之一吗50分之一的播放数率然后一秒它差不多就是20毫秒一个Hardbeat,看到没有?它差不多就20毫秒一个hard bit 因为它是50分之一嘛,它大概是20毫秒到40毫秒一个hard bit所以说这个hardbeat呢这个consensus里面这个hardbeat呢是非常frequent的它和这个expiration,这个time range是直接相关的你说的那个gossip heartbeat呢,是detect node有没有档掉,那是不同的 heartbeat,它的go是不一样的,它都是heartbeat,但它go是不一样的,它一般来说也不会用在consensus里面。哦然后另一方面讲的话那个Cassandra的Gossip呢可是你可能在这一段时间很多时候就是为了做Data Broadcast的它设计的,我记得我没有记错的话,它设计的目的就是为了Broadcast Data的它就是说,如果一个Node去Broadcast Data,它对这个Output Link的压力太大了所以它希望用这种Gossip的方式来去Broadcast DataOK谢谢大家好谢谢大家我之前也实践过一个gossip,没有我没有实践gossip,我实践过一个heartbeat,我之前实践过一个heartbeat还是比较有气的也没有很复杂,其实没有很复杂,OK有没有什么其他 [85:00] 很解哦,Scott,我有两个问题。你的问题是那个Two Faces Commits,你刚刚只说了Coordinate,那如果是participant是怎么办的如果是他在没有发信息之前就fail了,那Coordinator他的decision是怎么样?好对,Participant的这个Fillure呢,其实Participant的Fillure也是分两个阶段,也是分两个时间就是这个可能分多个时间吧partition在RedData之后就是RedData这个phase呢failure的话这个transaction是被obot了嘛就是cordidator等这个这个participants给他answer然后他没有说到任何answer就要bought了是吧所以在Dread Data这部分是比较简单的然后在这个Prepare这部分也是比较简单的coordinator说牧师问这个牧师问新娘说你愿意嫁给新郎吗然后他没有得到回应他认为也是about了也是可以about的。然后是participant要是活过来了之后,他是在找coordinator的log看一下。哦对是怎么样对对对所以如果这种情况下比如说新娘这会儿刚说了yes然后这个yes没有到达牧师然后牧师认为是about了但是新娘不知道的话新娘可以看一下这个coordinator log然后看一下这个婚礼完成了没有是吧那如果如果还有一种情况是相对于说coldination就比较痛苦了就是这个牧师就比较痛苦了牧师收到新郎和新娘的yes然后牧师公赠完毕了然后新娘挂掉了什么新娘没反应了那牧师就不停地得聘新娘直到他活过来他就说你们婚礼完成了,知道吧?他得要不停的拼,我以为是那个participant他活过来的时候主动的哭谢谢对于这种情况下,participant也是要主动Pull的,因为participant send yes 以后,他没有多多Response,所以他也不知道目视 commit 了没有。如果是牧师,他就装导的已经把Commit写到Log里面的话,他一定得把这个Decision给发出去收到response为止他写到log以后他必须不停地通知这个database你已经完成这个transaction了他要没有收到response的话他就不停地通知他你知道吗也比较痛苦了哦,明天,明天另外一个问题就是这个Linear stability,就是你说的还是recency guarantee,但是我看到有一些discription是说recency guarantee,但是有一些discription是说只要有一个request read out most recent data,后面的request都必须得是mult.最多的那那就代表说这个第一个看到most recent data之前,这个request之前还可能有其他的request看到并不是most recent data,但是这个data其实已经right了对对,这个的话其实来说是满足Linearability的好就是Lineability就是Lineability满足不满足的你可以认为是一个理论的或者一个观察的理论上它可能不满足但是可能reproduce的概率比较低我觉得像你说的话其实是理论上它其实不满足Linearability但是你没有这个Oracle去知道它满足不满足,你只能通过观察来讲来解释吗然后Linearability如果从观察的角度来讲的话你必须有一个反例才能才能说它不满足Linearability像这个case的情况下如果这个RAID4没有发生的话,它其实是满足linear ability的对吧因为你可以解释他这个你可以迎来解释就是他这个他可能就是这个写是在这儿吗然后他读在这儿嘛所以他可以满足Linear Beta正是因为这个rate等于4发生了,所以它就戳破了这个它不满足linearability的这个事情这个真相是吧 否则的话你可能还懵在鼓励你可能还是觉得满足那点非得见所以理论上来说,你从理论分析的角度,说这个database满足linearability,是吧?像你刚才举的例子是理论上不满足linearability但从实际观察的角度是满足利点赔的如果Client B最后的那个read,只要有一部分跟Client A read等于4有一点点重合,它也满足了你的ability [90:00] 对,你从观察的角度来讲,你只要有一个解释能解释它满足LinearPilitude,就是满足LinearPilitude。好的除非你能从理论证明它不满足Linearability嗯我觉得我自己读这张的时候,当然我现在读一下可能相对比较轻松一点,但我之前读的时候还是挺烧闹的好 如果没有问题就这样的 今天也是最后一张讲这个Theory了 我觉得还是比较有趣的,如果大家有兴趣的话以后可以就是比如说有一个读书的一个什么一个meeting是吧,我们可以教论一下读书心得啊,这样的话相对来说我比较轻松一点,我们就是可以一张一张的读,然后讨论一下读书的心得,没必要我去准备一个slides,我觉得这样子用的我是相对来说比较可以接受的,但是准备slides这个工作量确实太大了一点,我还得再重新读一遍这一张。然后把其中比较难的一部分给摘出去,然后把简单的那部分说下来,但是其实简单一部分有时候也很难,有时候自己也把自己绕运了,也是挺正常的但是,如果有读书的话,我可以一周读一脚脏啊这样的,我觉得还是比较sustainable的。这个现在来说对我个人不是很sustainable。今天就到这好了谢谢大家谢谢大家谢谢大家。