COPS论文总结——Lec17

一、简介

1.论文的标题是‘Don’t Settle for Eventual:
Scalable Causal Consistency for Wide-Area Storage with COPS’，可以看出，论文提出了相对于‘最终一致性’更强的因果一致性的可扩展性，即Wide-Area存储COPS。
2.这篇论文的设计思想其实主要解决的是异地数据中心复制的问题，同时要保证因果一致性PLUS
3. 本文介绍一个KV存储系统COPS，其实现了集群级别的“带有收敛冲突处理的因果一致性”（Causal+），并有很好的扩展性。
收敛冲突处理，指的是不同的副本之间，通过相同的处理（解决冲突的行为相同），最终都会收敛至同一个结果。
4.本文还提出了具有事务一致性的KV存储：COPS-GT。

二、ALPS

1.可用性。

(availablity) 发出到数据存储的所有操作均已成功完成。 任何操作都不能无限期地阻塞或返回表明数据不可用的错误。

2.低延迟。

(low-latency) 客户操作“迅速”完成。商业服务级别的目标表明平均性能为几毫秒，而最差情况的性能（即99.9％）为10或100毫秒[16]。

3.分区容忍。

(partition-tolerance) 数据存储继续在网络分区下运行，例如，一个将亚洲的数据中心与美国的数据中心分开的网络。

4.高可扩展性。

(high scalability) 数据存储线性扩展。 向系统中添加N个资源可使总吞吐量和存储容量增加O（N）
以上条件满足1-3可表示系统在线。

5.对比CAP

相对于分布式数据库的CAP理论（C-consistency一致性，A-availability可用性，P-partition分区），ALPS舍弃了C一致性的高要求，在保留AP的基础上，增加了L低延迟，实际上低延迟也是可用性的一种表现，即ALPS在CA之间选择了高可用性。COPS在一致性上，退而求其次达到带收敛冲突处理的因果一致性Causal+, 收敛冲突处理使得副本之间不会有分歧。

三、COPS的一致性

1.一致性的分类

linearizability 线性化（或强一致性），可保持全局实时ordering；
sequential consistency 顺序一致性，确保至少全局排序；
causal consistency 因果一致性，保持依赖（happens-before）操作的偏序；
FIFO（PRAM）一致性，保持单线程依赖操作的偏序，而不保留线程之间的顺序。
per-key sequential consistency键顺序一致性，可确保对于每个键，所有操作都具有全局顺序；
eventual consistency 最终的一致性，副本最终会收敛于某个值；
前两个不能达成ALPS。因为强一致性无法达到low lantency

可参考另一篇博客什么是一致性

2.Causal+ 一致性

（1）模型抽象

操作：只有两个，即put(k,v) get(k,v)
逻辑副本：值存储和访问的地方，在COPS中，一个逻辑副本对应一个本地集群的所有节点
潜在的因果关系：用⇝表示，规则如下：
a)线程内规则：若一个线程先后有a，b两个操作，则a⇝b
b)读取规则：若a是put操作，b是get操作且读到a写的值，则a⇝b
c)传递规则：若a⇝b, b⇝c，则a⇝c

（2）Causal+ 定义

a)因果一致
get操作读到的值，和之前⇝顺序的操作得到的结果，两者一致。
但是⇝是一个偏序关系，可能出现a⇝̸b且b⇝̸a，即a和b是并发操作。若并发操作作用于相同的键，则它们是冲突的，这会带来一些问题：
①得到的副本可能是发散的，即冲突操作得到的值不能确定 ②带来一些额外的异常，需要特殊处理
因此就需要“+”的部分，即收敛的冲突处理。（针对没有因果关系的冲突操作做处理）
b)收敛冲突处理
所有的冲突写操作，都会以相同的行为（解决冲突），作用于所有的副本。
这个冲突解决函数记为h，必须满足交换率和结合律，即h(a,h(b,c))=h(c,h(b,a))。这保证了冲突操作不论顺序如何，都可以得到一个相同的值，即达成收敛。
冲突函数由很多种，常用的如last-writer-wins（即取最后一个操作值），也可以自定义该函数（如Bayou和Dynamo）。
COPS可自定义冲突函数，不过默认是last-writer-wins。