作者：Jim Gray & Leslie Lamport 2004
原文：http://research.microsoft.com/pubs/64636/tr-2003-96.pdf
译者：phylips@bmy 2013-10-07
译文：http://duanple.blog.163.com/blog/static/70971767201419111256135/
[序：很早之前就注意到这篇文章了，冲着这超豪华的作者阵容当时二话不说就将它加入到了待读列表中，只是最近才有时间将它看完。提到Paxos，人们会禁不住想到Lamport，提到事务，那当仁不让就是Jim Gray了。而由这两位所写的关于Paxos和事务提交的文章，还有让你错过的理由吗?
另为帮助阅读，还可参考A Historic Survey of Transaction Management关于事务历史的描述，Principles of Transaction-Oriented Database Recovery关于ACID的描述，A Comparison Of Byzantine Agreement And Two Phase Commit中关于事务提交的描述。
]
摘要
分布式事务提交问题需要在事务是提交还是撤销上达成一致。在协调者不工作的时候，经典的两阶段提交协议会阻塞。容错的一致性算法也需要达成一致，但是只要有半数以上的进程正常工作就不会被阻塞。Paxos提交算法会在每个参与者关于是提交还是撤销的决定上运行一个Paxos一致性算法，这样就得到了一个具有2F+1个协调者同时只要至少F+1个正常工作就不会被阻塞的事务提交协议。与两阶段提交相比，Paxos提交具有相同的稳定性存储写延迟，同时在没有错误发生的情况下可以具有相同的消息延迟，但是需要使用更多的消息。经典的两阶段提交算法可以看做是Paxos提交在F=0时的一个特例。
1. 导引
分布式事务由运行在多个站点上的一系列操作组成，结束时需要确定事务是提交还是撤销。这些站点通过运行一个事务提交算法来决定事务是提交还是撤销。只有当所有站点都决定要提交时事务才能被提交。要在一个分布式系统中实现这种all-or-nothing原子性并不简单。对事务提交的需求将在第2节进行更精确地描述。
第3节中描述的两阶段提交[9]是最经典的事务提交协议。它采用一个协调者来确保达成一致。协调者的故障可能导致协议被阻塞，没有进程知道结果，直到它恢复为止。在第4节中，我们采用Paxos一致性算法[12]来构建一种采用多个协调者的事务提交协议，它可以在半数以上进程正常的情况不会被阻塞。第5节将两阶段提交和Paxos提交进行了比较。通过我们的介绍可以看到两阶段提交只是Paxos提交只有一个协调者时的特例，在这个协调者正常的时候不会被阻塞。第6节讨论了一些事务管理中的实际概念。最后在总结那一节中讨论了相关研究。
我们的计算模型假设算法运行在通过消息通信的一组进程集合上。每个进程运行在网络中的一个节点上。进程可以将数据存储到稳定性存储上。不同的进程可能运行在同一个节点上。我们的开销模型会计算节点间消息数，消息延迟和稳定性存储写操作数，以及写延迟。我们假设相同节点上的不同进程间的消息开销可以忽略。我们的故障模型，假设节点及其进程可能会发生故障；消息可能会被丢失、重复，但不会发生(不可检测的)损坏。对于故障节点来说，它上面的进程会停止运行；不会执行错误的动作，也不会丢失状态。要实现这种进程故障模型，需要向稳定性存储中写入信息，因此可能需要开销昂贵的操作。后面可以看到，这种稳定性存储导致的延迟，对于两阶段提交和Paxos提交来说是一样的。
通常来说，算法需要满足两种正确性属性：安全性和活性。直观来说，安全性描述了哪些是允许发生的，活性描述了哪些是必须发生的[2]。
如果说算法的安全性并不依赖于进程的某些时间性的执行过程，或者消息延迟的上界，我们就说算法是异步的。但是，进度可能依赖于进程响应速度和消息传输延迟。
我们将正常节点定义为那些它们上面的进程可以在某个已知的时间边界内进行响应的节点。当且仅当所有的节点都是正常的，并且运行在这些节点上的进程间的消息可以在一定的时间内完成发送，我们才认为节点网络是正常的。
本文的主要内容描述了事务提交和我们的两个协议(两阶段提交和Paxos提交)。
pdf完整版本下载：
http://pan.baidu.com/s/1mgG39t2