ACID vs BASE vs CAP
CAP：首先Eric Brewer, a professor at the University of California, Berkeley, and cofounder and chief scientist at Inktomi提出了CAP理论：CAP: Consistency, Availability and Tolerance of network Partition。并证明了CAP最多只能同时满足两个。He presented the CAP theorem, which states that of three properties of shared-data systems—data consistency, system availability, and tolerance to network partition—only two can be achieved at any given time. A more formal confirmation can be found in a 2002 paper by Seth Gilbert and Nancy Lynch.那么如果要满足all-or-nothing的原子性和强一致性，这也是ACID事务所要满足的需求，就不得不牺牲可用性。如果想要获得可用性和P(tolerance of network partition).那就不得不牺牲一致性，也就不存在原子性，这也就是BASE所能满足的需求。
ACID: Atomicity, Consistency, Isolation, Durability.
BASE: Basic Available, Soft-state, Eventual Consistency.
Eric Brewer这里的C值得不是ACID中的一致性，而是原子性。
CAP
证明为什么CAP不能三个同时满足
The Proof in Pictures
在Network N1和N2中分别有两个node A和B，这两个节点上面都包含数据V0（天龙八部在货仓中的数目）。
在某一个星期日，A将自己的数量从V0更新到V1，并通知B，更新到V1。这样任何从B读出的书的数目也是V1。
如果网络出现分区则A更新到V1之后B仍然是V0。
开始讨论了：1）如果不考虑分区耐受性，那么很简单N1只需要将自己更新而不需要考虑N2，当有消息的时候只需要读取A。如果A失败了那么网络也就失败了。这相当于一个单机系统那么是可以保证Consistency&Availability的。2）如果要保证分区耐受性，也就是也能够从B读取数据。如果牺牲Availability，那么更新数据的时候A使用两阶段提交协议将B锁住就可以保证A和B的数据是一致的。或者说存在另外的一个Coordinator用两阶段提交协议更新数据，将A和B都锁住。如果牺牲一致性，那么就可以直接更新A和B而不需要考虑是否满足consistency。
假设有这样的一个transaction，a1阶段write，a2阶段read。如果实在一个单机系统上，通过简单的写锁是可以控制系统的一致性和可用性的，只是需要尽量缩短synch的时间。但是在分布式系统里面，由于各种原因很难控制synch的时间。我们只能控制什么时候a2开始，但是我们不能保证在a2开始的时候一定能读到a1写的数据。
ACID
满足ACID属性又被称为是事务，被广泛应用在以数据库为代表的对可靠性和安全性有极高需求的应用场景。单对于Atomicity（原子性）数据库领域和操作系统领域的理解是有相应差异的。在数据库领域原子性指的是all-or-nothing的原子性，而操作系统是指一个操作在没有完成之前是不能被其他操作干预的，实际上是isolation的原子性。原子性和隔离性又是实现一致性的基础。
持久性满足当对数据提出需求时，数据扔然能够被正常读取。根据不同的场景，对持久性提出了不同程度的要求。计算机的一条指令只需要寄存器级别的持久性，运行程度的中间变量需要的是内存级别的持久性，而文件系统需要硬盘级别的持久性，为了获得更高级别的持久性，并防止因为硬盘故障或者是网络故障导致的无法正常读取数据的问题，产生了将数据分片存储的需求（如RAID）。或者将数据备份如（Master-Slave架构）。
对于采用分片或者M-S结构的持久性实现方式，对于一致性提出了新的挑战。在某种程度上可以认为，分布式系统的一致性问题的根源来源于为了保证系统的持久性也就是可靠性。
BASE
研究BASE就需要和REST做对比，因为这是衡量一个互联网应用的准则。不同于ACID面相的商业应用，互联网应用对可用性的要求更高，而对可靠性的要求在某种意义上要比商业应用低。
BASE的应用场景
你是怎样为像“出价竞拍”这样的操作实现原子性的？
出价竞拍本身就是一个很有意思的问题，原子性并不是重点，更多的是关系到在拍卖关键的最后几秒钟里不要阻塞任何出价人。如果改成在显示时刻而不是在出价时刻计算最高出价人和最高出价，就会变得非常简单。所有出价都被插入到一个单独的子表，插入操作不太会引起资源争用的情况。每次显示产品的时候，再重新取回所有的出价，并且在这个时候应用业务逻辑来决定最高的出价人。
你的问题背后隐藏的真正问题是我们如何实现一致性？要在大型系统中实现一致性，你必须放弃ACID，转而使用BASE：
基本可用（Basically Available）
软状态（Soft state）
最终一致（Eventually consistent）
如果你能够在每个客户端请求快结束的时候放松对数据一致的要求，就有可能消除分布式事务，并使用其它机制来达成一致的状态。举例来说，在上面的出价案例中，我们也更新视图数据表，视图数据表是按照出价人来组织数据的，目的是加速“我的eBay”页面的显示。这里用两个异步事件来完成。一个是依靠内存中的队列，因为我们希望尽量缩短从出价到在显示在“我的eBay”页面上之间的响应时间。但是，内存中的队列不可靠，所以在发生出价操作的时候，我们同时用一个服务器端事务来捕获出价事件。即使内存中队列的操作失败了，这个出价事件也能根据还原机制被处理。出价人视图数据表因此而解耦，但不总是与出价表的状态保持一致。不过这是我们可以接受的让步，它让出价表和出价视图表之间不必服从ACID要求。
一致性&持久性
1. 什么是一致性、持久性以及事务
当一个原子操作具有了一致性，隔离性和持久性之后，这个原子操作就可以被称为事务。
Consistency is an application-defined requirement that every update to a collection of data must preserve some specified invariant. Different applications can have quite different consistency invariants.
我们一直讨论一致性，并将一致性理解为我们所看到的数据和一系列操作所更新的数据是一致的。但是实际上这并不是一致性的最本质的含义。本质的含义是，根据应用的需求，我们对一系列数据集的操作要维持一个不变量。例如，表的行号应和行数是对应的。cache应和后台数据是对应的。
书中花费了很大段讨论Atomicity。原子性分为all-of-nothing atomicity和isolation atomicity.
强一致性：就是将不一致隐藏在系统边缘内部。从外部看任何时候系统都是一致的。
最终一致性：主要表现在更新数据时，有一段时间从系统边缘外看，是不一致的，但是在某个时间段后，一致性会得到保证。
有时最终一致性反倒是一个优点。比如Download一个网页时，先出现文字，后出现图片。在download过程中，页面与后台数据是不一致的，但是这反而改善了用户体验。
2. Cache coherence
Cache的一致性要求在于Cache中存储的数据应当和二级存储中的数据应当的相等的。但是由于从Cache到二级存储的延迟，存在某个时间段，Cache和二级存贮中的数据是不同的。
Cache应当满足读写一致性：The result of a read of a named object is always the value of the
most recent write to that object.
请求对一个Object读，读到的应该是最近一次写的结果。
Cache分成：
1. Write through cache（直写式缓存）每次写操作不光写cache还写到二级存储，这样就容易造成性能的瓶颈。
2. Write back cache（回写式缓存）先是将写操作写到cache中，这时应用就可以认为写操作已经完成了。而将cache中的数据更新到二级存储是由cache manager来完成。
如果只有一个cache那么回写式缓存也能够提供强一致性，但是如果thread能够直接从二级缓存读数据或者有多个cache，可能其中某个cache并不是最新数据那么一致性就受到了破坏。
如何在分布式缓存中仍然能够获得一致性？
1. 如果shared和writable的数据很少，那么可以将这些数据标示成“不可缓存”。
a) World Wide Web采用了这种方式。在HTTP头有一个字段，可以设置“不可缓存”这样Web Page就不会被缓存。
b) Java内存模型中一种思想类似的方法是将一个变量声明为volatile。
2. 另外一种思想是将那些与权威副本不一致的缓存标示为无效。
a) 一个设计思想，如果在多个处理器共享的二级存储上共享cache，则可以避免不一致性。但是共享cache会导致处理器对cache的竞争和互斥。这样会降低系统性能。因此对于每个处理器提供一个单独的私有的cache。这样就产生了不一致性。即使是使用直写式缓存，处理器A对数据Data的更新却无法写到处理器B的私有缓存上，这样就导致了不一致性。这就需要有一种机制去告诉那些使用了数据Data的处理器，数据Data已经失效。
i. 当有一个处理器写的时候，告诉其他所有处理器他们的私有缓存全部都失效了。
另外一种方法是使用更多的wire，去告诉其他私有缓存内存中的那个地址的数据失效了。一种方法就是私有缓存都侦听memory bus。当memory bus上有写操作的时候。A slightly more clever
design will also grab the data value from the bus as it goes by and update, rather than invalidate, its copy of that data. These are two variations on what is called the snoopy cache*—each cache is snooping on bus activity.
ii. 即使使用了Snoopy Cache仍然会遇到问题。cache的问题解决了，但是register却会带来新的同步问题。
3. 只要是允许副本被多个请求并发的访问，如何维护隔离性和一致性就是一个复杂的问题。采用锁的方式避免并发访问是一种解法，但是又会影响到性能。一种可行的方法是使用概率。
3. 持久性，以及有多个副本带来的一致性问题
持久性就会带来多个副本之间的一致性问题：下面都是处理多个副本之间的不一致性。
The durability mantra
Multiple copies, widely separated and independently administered…
Multiple copies, widely separated and independently administered…
1. Replicated state machine
If the data is written exactly once and never again changed, the management plan can be fairly straightforward。这个是Hadoop和Cassandra能够保证多个副本一致的前提。
2. Master and Slave结构
M/S结构的一个很大的弱点就是M更新的时候，读S读到的都是旧的数据。设计一个MS的结构会面对一系列的问题:比如M和S瞬时的不一致。还有就是M的数据decay了，S如果还没有同步，则同步的数据也是错误的。
3. 保证分布式数据的完整性？
a) 可以在副本之间做校验，但是一旦这些数据之间的传输开销很大的话，聚会造成很大的时间成本。
b) 并不是直接对比而是传输MD5checksum
总结：
1）简单副本（RAID）2）为了避免地震等故障，更加分布的副本GFS3）按照某种逻辑写数据，也就是大家写数据的时候都遵循一定的规则，从而避免不一致的情况4）运用概率提升性能5）Replicated state machines6）Master/Slave结构->为了避免M和S的不一致性，可以将M的表划分细小，然后每个细小的表有一个Master->为了避免M和S的不一致使用两阶段提交协议->当M失效之后使用选举算法选出新的Master->If the application is one in which the data is insensitive to the order of updates, implement a replicated state machine without a consensus algorithm.->增量更新->传递的不是增量而是操作的log7）quorum算法
4. 协调（Reconciliation）算法
什么是协调？当系统update到一半，或者M-S结构里面M宕机了，或者数据副本出现不一致状态了。那么从这种不“和谐”的状态重新归于“和谐”就是reconciliation。
1. Occasionally connected operation
这个场景就例如iphone和iMac之间的数据同步。更好的比喻是SVN，client和SVN上面文件的同步。
如何发现文件之间的不同：
a) checksum
b) 维护一个统一的文件id，一旦产生变化就将id加1。
c) 通过时间戳。文件更改了则时间戳就会更新。
5. Atomicity across layers and multiple sites
两阶段提交协议的两个阶段：（注意区分两阶段提交协议2PC和两阶段锁协议2PL）
达成协议阶段：
在这个阶段协调者向所有要执行commit操作的节点发出“尝试commit”的请求。节点接受到请求后“尝试commit”，例如包括更新log——在undo log中增加新的信息，在redo log中增加新信息。当发现可以正常的commit，则返回一个Yes的消息，否则返回一个No的消息表示abort。
如果coordinator收到了全部的Yes消息，则发出一个commit消息，则所有的节点都commit，并释放占有的资源锁。
如果coordinator收到的消息中有No消息，表示某个节点不能够commit，则coordinator群发一个rollback的消息。这时每个节点根据undo log中的日志回滚，然后释放占用的资源锁。这里正是memento模式的用武之地!
缺点：
这是一个异步协议，对系统的可用性影响极大；如果coordinator失效了，可能会导致一些node的锁永远不会被释放，被永远绑定。如果node向coordinator发送了agreement消息，并等待commit或者rollback的反馈。如果这个时候coordinator挂了，这个就会被永远锁住，除非从其他的coordinator那里能得到相应的反馈。
当coordinator发送一个“Query-to-commit”消息的时候，在收到全体相应之前coordinator也是被阻塞的。但是如果一个node没有响应，coordinator不会被永久阻塞。因为coordinator可以引入一个timeout机制避免被永久阻塞。
因为上面提到的time out机制，这个协议的另外一大弱点是：偏向于abort一个case，而不是complete一个case。
Implementing the two-phase commit protocol
6. 一致性判别
数据一致性通常指关联数据之间的逻辑关系是否正确和完整。而数据存储的一致性模型则可以认为是存储系统和数据使用者之间的一种约定。如果使用者遵 循这种约定，则可以得到系统所承诺的访问结果。
常用的一致性模型有：
严格一致性（linearizability, strict/atomic Consistency）：读出的数据始终为最近写入的数据。这种一致性只有全局时钟存在时才有可能，在分布式网络环境不可能实现。
弱一致性（weak consistency）：只要求对共享数据结构的访问保证顺序一致性。对于同步变量的操作具有顺序一致性，是全局可见的，且只有当没有写操作等待处理时 才可进行，以保证对于临界区域的访问顺序进行。在同步时点，所有使用者可以看到相同的数据。
最终一致性（eventual consistency）：当没有新更新的情况下，更新最终会通过网络传播到所有副本点，所有副本点最终会一致，也就是说使用者在最终某个时间点前的中间 过程中无法保证看到的是新写入的数据。可以采用最终一致性模型有一个关键要求：读出陈旧数据是可以接受的。
顺序一致性（sequential consistency）：所有使用者以同样的顺序看到对同一数据的操作，但是该顺序不一定是实时的。
因果一致性（causal consistency）：只有存在因果关系的写操作才要求所有使用者以相同的次序看到，对于无因果关系的写入则并行进行，无次序保证。因果一致性可以看 做对顺序一致性性能的一种优化，但在实现时必须建立与维护因果依赖图，是相当困难的。
管道一致性（PRAM/FIFO consistency）：在因果一致性模型上的进一步弱化，要求由某一个使用者完成的写操作可以被其他所有的使用者按照顺序的感知到，而从不同使用者中 来的写操作则无需保证顺序，就像一个一个的管道一样。 相对来说比较容易实现。
释放一致性（release consistency）：弱一致性无法区分使用者是要进入临界区还是要出临界区， 释放一致性使用两个不同的操作语句进行了区分。需要写入时使用者acquire该对象，写完后release，acquire-release之间形成了 一个临界区，提供 释放一致性也就意味着当release操作发生后，所有使用者应该可以看到该操作。
delta consistency：系统会在delta时间内达到一致。这段时间内会存在一个不一致的窗口，该窗口可能是因为log shipping的过程导致。
最终一致性的几种具体实现：
1、读不旧于写一致性（Read-your-writes consistency）：使用者读到的数据，总是不旧于自身上一个写入的数据。
2、会话一致性（Session consistency）：比读不旧于写一致性更弱化。使用者在一个会话中才保证读写一致性，启动新会话后则无需保证。
3、单读一致性（Monotonic read consistency）：读到的数据总是不旧于上一次读到的数据。
4、单写一致性（Monotonic write consistency）：写入的数据完成后才能开始下一次的写入。
5、写不旧于读一致性（Writes-follow-reads consistency）：写入的副本不旧于上一次读到的数据，即不会写入更旧的数据.
6、选举一致性：
Werner Vogels认为：在很多互联网应用中，单读一致性＋读不旧于写一致性可以提供足够的一致性了。