论文地址 : COPS
上一篇文章我们讲了BAYOU，他是实现的一个拥有causal consistency的系统。但是他有一个问题，他是基于LOG，然后还需要一个PRIMARY，也就是说至少一台机器需要存下所有的LOG数据，然后要和PRIMARY交互。这样的设计不利于PARTITION，比如基于KEY SHARD，因为需要PRIMARY去决定全局的LOG顺序。那么这篇论文就是解决这个SCALE的问题。所以论文的标题是：Scalable Causal Consistency for Wide-Area Storage with COPS
论文里还提到另一个特性，这个个系统是Wide-Area,也可以称为异地容灾的。那么也就是有多个数据中心。在不同的地域上。
image.png
多个数据中心的好处，还有可以就近服务，这样可以服务的更快。设想如果美国有个服务器，中国有个服务器，那么中国的用户访问中国的服务器得到响应速度会快很多。
同时在一个数据中心里，很多个SERVER是SHARD的。这个特点是BAYOU不支持的
image.png
这篇论文的设计思想其实主要解决的是异地数据中心复制的问题，同时要保证因果一致性PLUS
ALPS
大家都知道CAP理论，说一个系统在这3个特性里最多只能选2个。这篇论文给出了ALPS。
1.可用性。(availablity) 发出到数据存储的所有操作均已成功完成。 任何操作都不能无限期地阻塞或返回表明数据不可用的错误。
2.低延迟。(low-latency) 客户操作“迅速”完成。商业服务级别的目标表明平均性能为几毫秒，而最差情况的性能（即99.9％）为10或100毫秒[16]。
3.分区容忍。(partition-tolerance) 数据存储继续在网络分区下运行，例如，一个将亚洲的数据中心与美国的数据中心分开的网络。
4.高可扩展性。(high scalability) 数据存储线性扩展。 向系统中添加N个资源可使总吞吐量和存储容量增加O（N）
特性1,2,3如果被一个系统满足，我们可以说这个系统会一直在线。
当然可扩展性，表示，只要我们增加机器，存储和吞吐量也可以线性增加。
一致性
什么是一致性？ 就是对操作的时机和顺序的限制。
强一致性，可以使得编程简单，就和单机没有区别。同时可以保证用户体验很好。因为是REAL TIME的。但是CAP理论指出，一个系统如果拥有分区容忍和高可用性是不可能实现强一致性的。
我们看一下，还有哪些一致性呢？
linearizability 线性化（或强一致性），可保持全局实时ordering； sequential consistency 顺序一致性，确保至少全局排序； causal consistency 因果一致性，可确保相关操作之间的部分排序； FIFO（PRAM）一致性，仅保留执行线程的部分顺序，而不保留线程之间的顺序。
per-key sequential consistency键顺序一致性[15]，可确保对于每个键，所有操作都具有全局顺序； eventual consistency 最终的一致性，今天使用的“包罗万象”一词暗示最终会收敛到某种类型的协议。
在ALPS里，强一致性和 顺序一致性是不可能的了。
image.png
image.png
知道这些一致性，简单介绍下因果一致性。比如你想去朋友圈里发一个找工作的状态，你必须要先把老板设置为看不到你的朋友圈。然后再发。所以一条状态依然与你前一个屏蔽老板的操作。在满足因果一致性的系统里是不会出问题的。如果不满足，就会出现乱序，比如你老板先看到你要找新工作的朋友圈，然后才被屏蔽。
image.png
下面我们来说下，什么是CAUSAL + 一致性。
其实就是在原来的因果一致性上加上一个冲突消解策略。假设2个没有因果关系的操作是可以并行的。那么我们不能允许不同的SERVER持有不同的值。必须要所有的机器统一这个值。所以一旦2个操作不一样了，最后要决定使用哪个值。当然可以用系统默认提供的LAST WRITE WIN， 当然也可以由程序员指定如果合并2个不一样的值，比如用SUM。
image.png
下图是用SUM来冲突消解。
image.png
上一篇我们介绍的BAYOU也是具备CAUSAL+的一致性系统。但是它采用日志定序的模式，那么就是需要单独的节点来做。但是它限制了scalability，并且无法做到跨SERVER的因果性。因为要单机定序。
那么COPS是如何解决这个问题呢？
COPS设计了一个dependency metadata，这个变量里携带了具有因果关系的操作，把这个变量显示的传给其他节点来SYNC。那么就用一个分布式的验证来取代了单点序列化。
当一个节点收到一个指令，它首先会去验证他的前置依赖指令是否完成，如果没有完成，就延迟暴露这个需要被复制的指令。
我们看一下COPS的架构
image.png
在一个本地的数据中心上，所有的存数据节点是SHARD的，他们被分布在一个consistent hash环上（一致性HASH是个经典的分布式技术，不懂的小伙伴可上网学习） 前方有一个CLIENT LIBRARY他的作用是维护那些DEPENDENCY METADATA，可是使得一个CLIENT发过来的请求，LIB附加上这个请求的前置依赖。随后当一个请求在本地中心被落库了额，他会把这个请求发给其他数据中心去SYNC。数据中心和数据中心间的SYNC拥有causal+ consistency
一个GET请求就是请求最新版本的数据，所以不需要加上DEPENDENCY METADATA。直接GET即可。
image.png
一个写请求就需要带上METADATA，当本地DATACENTER落库后，要把写请求和METADATA都同步到其他DC上。每个DC会去判断，这个写的前置请求是否满足。如果满足则落库进DB。
依赖关系是值的显式元数据，库跟踪并将它们附加到put_afters
image.png
知道了传参，我们现在来聊一下RETURN。 一个put_after(Key,Val,deps) 会RETURN 一个版本号。 这个版本号会被落库到CLIENT LIBRARY的DEPS里。被用来保证(Thread-Of-Execution Rule)（单个线程从，操作顺序有序）。
这里具体说下Client Library, 会在里面保存一个CONTEXT，它是用来构建一个依赖关系图的，所以每个操作需要存version。代表一个unique的value，如果未来有人要改这个value，这个VALUE 有这个VERSION，他就会知道他的这个写是依赖于这个VALUE的这个VERSION，当写成功返回了一个新version 的时候，CONTEXT就能对这2个写的VERSION构建一个dependency的关系。这也是保证因果一致性的方式。
image.png
image.png
之后的GET，会return3样东西。value,version,deps'
version 可以用来保证(Gets-From Rule).
deps 可以用来保证(Transitivity Rule)
version 会被落库到Library 的context里，用以构建DEPENDENCY GRAPH和传递因果一致性。
这个返回的deps'， 在实现get transaction的时候有很大作用。现在暂且不表。
一个PUT全流程回顾
首先用户发送一个put(k,v) 给CLIENT LIBARAY， Client libaray根据这个Key, 和自己维护的CONTEXT计算出dependency -> list（other key, other key's vsion）,然后变成一个put_after发送给server, server当它把这个put 落库之后，会返回给CLIENT成功，并且告知CLIENT 一个UNIQUE VERSION。同时在后台进程，会把这个成功的落库异步发送给其他的DATA CENTER。
下图是其他的DC，收到这个发来的PUT_AFTER，会做的事情。
image.png
他去看DEP 有哪些要验证的KEY，然后发送到对应的SHARD KEY的SERVER是去dep_check, 如果都返回TRUE,则可以把这个PUT的VALUE给落库。如果有一个为FALSE，需要BLOCK直到这个版本更新了。
上述就是一套流程。
他是有"always on:的特性，可以serve operation在本地，并且异步后台去复制。 拥有可扩展性，因为他可以SHARD KEY在很多节点上。同时控制复制的时候有dependency check来保证因果一致性。
但是仅仅有get api 还不够。比如遇到一个操作依赖于一个GET的条件，这个时候就会出错。因为你第一个GET判断完的条件和后一个操作之间有时间，使得这个条件发生变化。
我们来举个例子。T1 BOSS来看你的朋友圈，他去拿权限，还是你的朋友。T2你把BOSS移除了。 T3，你发了一个NEW JOB！。T4， BOSS根据还是你朋友，所以拿到了你的所有朋友圈，就看到了这条你不想让他看到的朋友圈。
上述问题在DB里需要用事务来解决。但是再COPS里，它构建了一个get_trans的API，他通过2次GET来实现读事务的效果。
这个时候上面说到的GET 返回的deps 参数就需要被用到。同时还需要一个GET指定VERSION的API，就是说不一定GET一定是去拿最新的VERSION。用户可以指定一个版本去GET。
2次GET实现的GET事务，因为没有锁，没有阻塞，所以是低延迟的。
我们看下怎么做？
image.png
第一轮get keys, 比如说老板去拿朋友圈权限acl和朋友圈内容content。根据上述时间线，拿到了 public acl (version A), new job content (version X).
但是员工那边肯定是先设置为private acl, 随后发布 new job. 所以new job content 的retrun deps 里必定含有 （acl, version : B）, 而B 一定会 大于 A。
所以在更新的时候，
image.png
这句话就会把VERSION 更新到B， 在外面判断的时候就会有B > A，所以去拿B版本的ACL，最后拿到private acl, 这样老板就无法读到朋友圈NEW JOB CONTENT了。
到目前为止，我们已经得到了一个ALPS + causal+的系统。但是系统存在一个问题？
就是metadata 越来越多，坏处就是需要很多的verification 且发送和保存的数据量都很大。 我们需要做一个剪枝。
在发送dependency 的时候，我们其实只需要发送nearest的，因为nearest 已经包含了之前的一些DEPENDENCY。
同时我们可以对没有的dependency 做GC。
我们可以看到下图只需要验证2块绿色的即可。
image.png
那么在发送的时候只要发送nearest, 还需要保存non-nearest的dependency吗，答案是需要的，因为在做get transaction的时候，我们需要 full dependency 来保证txn 的正确性，但是我们依然只需要CHECK nearest dependency.
同时还有GC帮助我们清理用不到的VERSION，用不到的DEPENDENCY和CLIENT LIBARAY用不到的METADATA，这块具体可以读论文。
image.png
容错
CLIENT 失败了，就让他失败，不会有什么问题。
如果K/V NODE失败了，可以用链式复制的技术
当一个节点写的时候先去写头，然后向后传递，在尾部COMMIT。读的时候去读尾。复制的时候是从本地DC的尾节点发送put_after给远端DC的头节点。然后头结点向后传递，由远端尾节点COMMIT。同时头结点会给远端的其他SHARD NODE的尾节点去发送dep_check.
数据中心失败了或者PARTITION了。整个体系依然可以WORK，只是会有些KEY不一样。但是当恢复之后，这些KEY又会一致。但是有一个数据中心失效的情况，DEPENDENCY会没法GC，所以存储会是一个问题。这个时候需要ADMIN来决定判断数据中心会很快恢复还是把这个数据中心从配置里移除。
性能
几乎是线性SCALE
image.png
总结：
COPS是第一个支持ALPS同时拥有causal+ 的一致性的系统。它首创了基于dependency check 的非集中式的复制，和对dependency 剪枝的策略
网友评论