这篇我们主要来聊一下一个ALPS的系统可以拥有的最好的CONSISTENCY。 Causal+ Consistency.
论文地址：Bayou
Bayou 这篇论文介绍了一种思想，而不是真正的一个系统。他是写于95年，当时终端设备如笔记本电脑，手机正处于黎明时期。因为这些设备有一个问题就是，他们时常出于断网的状态，或者即使连上网，由于当时基础设施的落后，信号非常差，上网稳定性很差。网速很慢。
那么要在这么一个环境下，使得设备间可以协同运作BAYOU设计了一套可以让weakly connected operation拥有最终一致性的分布式系统。同时还定义了如何解决UPDATE CONFILICT的问题。
在BAYOU的设计里，有下面的4个技术要点：
- 操作日志就是数据
- 日志可以在排序，重执行，合并的基础上实现最终一致性。
- 日志帮助冲突消除
- 因果一致性依赖于LAMPORT时间戳
- 版本向量可以帮助压缩日志
下面我们带着问题去看我的这篇博客，其实讲的就是BAYOU的设计。
第五章 分布式系统一致性（下）
问题是，我们使用bayou构建了一个分布式文件系统。里面有个复制操作。文件A 含有FOO， 文件B含有BAR。 在一个节点，用户复制文件A去文件B（覆盖的复制）， 在另一个节点，用户复制文件B去文件A（覆盖的复制）
当上面的2个操作都提交了，我们希望2个文件要么同时为FOO，要么同时为BAR。BAYOU是如何确保所有NODE都看到A和B 要么同时是FOO要么同时是BAR的？
预定一个会议在11:00，单机下会怎么做。为什么作者不满足一个中心节点。
因为作者考虑的是一个充满着DISCONNECTED的操作。然后希望不会影响到这些DISCONNECTED的DEVICE的APP继续使用。在联网的时候再去SYNC。那么就要求每个设备都有自己的DB，即是一个REPLICA。这样就会有冲突发生，BAYOU希望冲突让用户去定义如何消除，而不是默认把一个覆盖另一个。
BAYOU的另一个思路是去同步UPDATE FUNCTION而不是DB的RECORD。 同时UPDATE FUNCTION 需要提供冲突消除策略， 比如Meet at 9 if room is free at 9, else 10, else 11.
如果我们只是简单的来一个FUNCTION就做一个，就无法达到一致。
A's fn: staff meeting at 10:00 or 11:00
B's fn: hiring meeting at 10:00 or 11:00
X syncs w/ A, then B
Y syncs w/ B, then A
上述的例子里，X和Y的状态就是一致的。
为了达到最终一致性，我们需要定义UPDATE LOG的ORDER。这样的目的是所有的机器拿到同样顺序的LOG，根据这个LOG去做，就必定可以得到同样的DB内容。（RAFT也是使用这个思想）
一开始我们使用设备的时间，如果设备时间相同，就用设备ID来打破平局。这样LOG就可以比大小了。有了顺序，当一台机器SYNC之后，发现日志顺序不对，就需要回滚自己的日志，随后REPLAY正确顺序的日志。
到这里之前的那个问题就有答案了。
上述问题解决后，会出现一个因果一致性的问题。
比如别人发了朋友圈，你看到了之后点了赞，但是你的机器设备时间比较早。跑到另一个朋友拿，你的点赞的LOG会排序在发朋友圈的LOG前。然后就会有问题。
这里的解决思路是LAMPORT时间戳。可以确保你看到一个值之后在产生的其他操作一定比你看到的这个操作的时间戳要大。
LAMPORT时间戳有的特性是
- 如果TS(A) < TS(B), A和B不知道谁发生在前
- 如果在同一台DEVICE上，先A后B那么一定有TS(A) < TS(B)
下面一个要解决的问题是，LOG膨胀的问题。这个系统随着时间的推移LOG会越来越多。还有用户会不知道什么时候这个会议时间会定下来，因为会因为一个时间戳更早的日志还没到，所以现在看到的不是最终的。之后还有REPLAY。为了使得知道一个UPDATE是STABLE的，就是之后不会被ROLLBACK然后REPLAY的。
有2种做法，一种是分布式的，一种是集中式的。BAYOU选择了集中式的。
首先看分布式的做法，这个需要NODE去和其他所有NODE确认，所有的NODE都看到了<10,A>这条记录，我们就知道TS<=10的都同步好了，那么<10,A> 就是STABLE的，之后不会被REPLAY了。
上述方案的问题是，一旦有一个设备DISCONNECTED，这个STABLE的TS就会永远固定在那。
那么集中式的方案，是选一台SERVER为PRIMARY，所有的UPDATE LOG都会在PRIMARY这边，打上CSN(COMMIT SEQUENCE NUMBER)。被打上CSN的UPDATE就是STABLE的，之前不会再有其他UPDATE FUNCTION没来了。然后PRIMARY会把COMMITED 去和其他NODE SYNC。
所以现在一个完整的时间戳为<CSN, logical-time, device-id>
为什么CSN可以保证stability?
Primary 只产生 increasing CSNs.
Device logs 排序所有 updates with CSN 在那些没有 CSN的update前.
一旦CSN被打上了，之前的UPDATE就被固定下来了。
Commit order大多数情况应该和tentative order一致。当然也有可能会不一致。
image.png
image.png
不一致时，需要ROLLBACK然后REPLAY，以PRIMARY的带CSN的为准
BAYOU是如何SYNC（反熵）？
如果A发一个SYNC给B，那么A首先问B的CSN在哪？然后A给B所有B CSN之后的UPDATE FUNCTION
那么那些没有COMMITED UPDATE怎么SYNC？
这时会用一个版本向量。
image.png
A has:
<-,10,X>
<-,20,Y>
<-,30,X>
<-,40,X>
B has:
<-,10,X>
<-,20,Y>
<-,30,X>
A's Full version vector: [X:40,Y:20]
B's Full version vector: [X:30,Y:20]
同样也只要发送版本向量之后的tentative update。比如上述例子A要发送 <-,40,X>给B
版本向量是个很重要的值得记住的技术。它被使用在很多系统里。是一个参与者状态的总结。一个ENTRY一个参与者。代表我看见了PI更先到VI的版本。
设备可以丢掉已经COMMITED UPDATE的LOG。但是如果一个机器要来SYNC已经丢掉的LOG怎么办？ 这个时候就需要把整个DB传输过去，然后告诉他这个DB的CONTENT是基于哪个CSN的。
最后如何新加进一个SERVER Z怎么处理呢？
发送一个通知，然后其他NODE的VV里都给Z加一个版本。
所以当Z宣布离开时，只需要通知其他节点，把Z从VV抹去即可。
当Z 加进来的时候，他需要一个其他SERVER的时间作为桥梁，不然其他SERVER不知道自己的版本向量里没有Z，是因为还没看见Z进来，还是Z进来过已经离开。
所以当Z进来的时候，他的ID会借用另一个SERVER的，比如是X
Z's ID is <Tz,X>
Tz is X's logical clock as of when Z joined
X issues <-,Tz,X>:"new server ID=<Tz,X>"
我们假设是<20,X>.
现在A去和B sync了。
A有LOG from Z <-,25,<20,X>>
B的版本向量里没有Z。
这个时候B可以去版本向量里看X的TS，如果X的TS是10，代表B还没看到X的来了个新NODE Z的update
如果X的TS是30，因为30>20,那么意味着B曾经见过Z，但是看到一个Z的RETIREMENT UDPDATE。
FAQ
Q： 有人在用BAYOU吗，如果没有，为啥要读这篇论文？
A：今天没有人使用Bayou。 这是一个旨在探索新架构的研究原型。 Bayou使用了多个有价值的想法值得了解：最终一致性，冲突解决，记录操作而不是数据，使用时间戳帮助达成顺序，版本向量以及通过Lamport逻辑时钟达成因果一致性。
Q：冲突结局的方案有没有被用在其他的分布式系统里？
A ： 有些同步系统具有特定于应用程序的冲突解决方案。 git将不同用户的更改合并到同一文件中的不同行。 当某人将其iPhone与Mac同步时，日历会以一种了解日历结构的方式进行合并。 同样，Dropbox具有一个API，当Dropbox检测到对同一文件的更新冲突时，应用程序可以进行干预。 但是，除了Bayou之外，我不知道有任何其他系统可以同步update function的日志（其他系统通常会同步实际文件内容）。
Q：最终一致性是不是最好的当我们需要支持离线的操作？
A：是的，最终一致性（或因果一致性等轻微改进）是可以做的最好的事情。 如果我们想支持对断开连接的数据副本的读写（如Bayou所做的那样），我们必须容忍用户看到过时的数据，并且用户造成冲突的写操作仅在同步后才明显。 有可能在这样的系统中获得最终的一致性是很好的！
Q：似乎为各种操作编写依赖项检查和合并过程可能是程序员难以处理的接口？
A：确实需要程序员工作。 但是作为回报，Bayou为解决相同数据的冲突更新这一棘手的问题提供了一个非常灵活的解决方案。
Q：BAYOU的PRIMARY REPLCA是不是单点失败？
A : 有点。 如果主数据库关闭或无法访问，则一切工作正常，但写入不会被声明为稳定。 例如，日历应用程序基本上可以运行，尽管用户必须担心会出现带有低时间戳的新日历条目并更改显示的时间表。
Q：dependency checks如何检测写－写冲突？该论文说：“可以通过使dependency checks查询正在更新的任何数据项的当前值，并确保它们与提交写入时的值没有变化来检测到此类冲突”，但我不了解依赖检查的预期结果是什么。
A：假设应用程序要修改日历条目“ 10:00”，仅当没有条目时。当应用程序运行时，没有任何条目。因此，应用程序将产生此Bayou写操作：
dependency_check = { check that the value for "10:00" is nil }
update = { set the value for "10:00" to "staff meeting" }
mergeproc = { ... }
如果没有其他写入修改10:00，则dependency_check将在所有服务器上成功执行，并且它们都将值设置为“ staff Meeting”。
如果大约在同一时间由其他客户端进行其他写操作，则设置
10:00进入“成绩会议”，那么这就是写/写冲突：
两次不同的写入都希望将同一数据库条目设置为不同的值。
依赖性检查将在同步时检测到冲突
使某些服务器看到两个写入。一次写入将首先在日志中进行（因为它的时间戳比较短）；其依存关系检查将成功，并将更新10:00条目。日志中第二次写入将使依赖项检查失败，因为10:00的DB值不再为nil。
也就是说，检查数据库条目是否具有与应用程序最初运行时相同的值，确实会检测到在日志中首先订购了冲突写的情况。
Q : 什么时候去CALL dependency checks
A ： 每个服务器都会执行同步期间听到的新日志条目。 对于每个新的日志条目，服务器将调用该条目的依赖项检查； 如果检查成功，则服务器将条目的更新应用于其DB。
Q：当您首次插入写操作时，依赖项检查中的逻辑看起来会发生，但是您不会从分区服务器上发现任何冲突。
A：每当服务器进行同步时，它都会将其数据库回滚到同步修改其日志的最早点，然后在该点之后重新执行所有日志条目（包括依赖性检查）。
Q：如何将特定服务器指定为主服务器？
A：我认为是人选的。
Q：如果在反熵会话过程中通信失败，该怎么办？
A：Bayou在同步时总是按顺序发送日志条目，因此，即使接收者没有听到来自发送者的后续条目，接收者也可以将接收到的条目添加到其日志中。
问：论文提到的session guarantees 是什么？
答：Bayou允许应用程序切换服务器，以便客户端设备可以通过网络与Bayou服务器通信，而不必运行完整的Bayou服务器。 但是，如果应用程序在运行时切换服务器，则新服务器可能看不到该应用程序发送给先前服务器的所有写入。 session guarantees 是一种解决此问题的技术。 该应用程序保留一个session版本向量，以总结它已发送到任何服务器的所有写入。
当它连接到新服务器时，应用程序首先检查新服务器与会话版本向量是否最新。 如果不是，则该应用程序查找最新的新服务器。
网友评论