1.1分布式原理——一致性&持久性

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

[edit]Common architecture

In many cases the 2PC protocol is distributed in a computer network. It is easily distributed by implementing multiple dedicated 2PC components similar to each other, typically named Transaction managers (TMs; also referred to as 2PC agents), that carry out the protocol's execution for each transaction (e.g., The Open Group's X/Open XA). The databases involved with a distributed transaction, the participants, both the coordinator and cohorts, register to close TMs (typically residing on respective same network nodes as the participants) for terminating that transaction using 2PC. Each distributed transaction has an ad hoc set of TMs, the TMs to which the transaction participants register. A leader, the coordinator TM, exists for each transaction to coordinate 2PC for it, typically the TM of the coordinator database. However, the coordinator role can be transferred to another TM for performance or reliability reasons. Rather than exchanging 2PC messages among themselves, the participants exchange the messages with their respective TMs. The relevant TMs communicate among themselves to execute the 2PC protocol schema above, "representing" the respective participants, for terminating that transaction. With this architecture the protocol is fully distributed (does not need any central processing component or data structure), and scales up with number of network nodes (network size) effectively.
This common architecture is also effective for the distribution of other atomic commitment protocols besides 2PC, since all such protocols use the same voting mechanism and outcome propagation to protocol participants.[1] [2]
[edit]Protocol optimizations

Database research has been done on ways to get most of the benefits of the two-phase commit protocol while reducing costs by protocol optimizations [1] [2] and protocol operations saving under certain system's behavior assumptions.
[edit]Presume abort and Presume commit

Presumed abort or Presumed commit are common such optimizations.[3][2] An assumption about the outcome of transactions, either commit, or abort, can save both messages and logging operations by the participants during the 2PC protocol's execution. For example, when presumed abort, if during system recovery from failure no logged evidence for commit of some transaction is found by the recovery procedure, then it assumes that the transaction has been aborted, and acts accordingly. This means that it does not matter if aborts are logged at all, and such logging can be saved under this assumption. Typically a penalty of additional operations is paid during recovery from failure, depending on optimization type. Thus the best variant of optimization, if any, is chosen according to failure and transaction outcome statistics.
[edit]Tree two-phase commit protocol

The Tree 2PC protocol [2] (also called Nested 2PC, or Recursive 2PC) is a common variant of 2PC in a network, which better utilizes the underlying communication infrastructure. In this variant the coordinator is the root ("top") of a communication tree (inverted tree), while the cohorts are the other nodes. Messages from the coordinator are propagated "down" the tree, while messages to the coordinator are "collected" by a cohort from all the cohorts below it, before it sends the appropriate message "up" the tree (except an abort message, which is propagated "up" immediately upon receiving it, or if this cohort decided to abort).
The Dynamic two-phase commit (Dynamic two-phase commitment, D2PC) protocol[4][2] is a variant of Tree 2PC with no predetermined coordinator. Agreement messages start to propagate from all the leaves, each leaf when completing its tasks on behalf of the transaction (becoming ready), and the coordinator is determined dynamically by racingagreement messages, at the place where they collide. They collide either on a transaction tree node, or on an edge. In the latter case one of the two edge's nodes is elected as a coordinator (any node). D2PC is time optimal (among all the instances of a specific transaction tree, and any specific Tree 2PC protocol implementation; all instances have the same tree; each instance has a different node as coordinator): it commits the coordinator and each cohort in minimum possible time, allowing earlier release of locked resources.


    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认为：在很多互联网应用中，单读一致性＋读不旧于写一致性可以提供足够的一致性了。