小和尚的藏经阁

转自：http://nosql-wiki.org/foswiki/bin/view/Main/TwoPhaseCommit

2PC是工程上广泛使用的分布式一致性协议，它主要解决的问题是：一个事务，要么所有参与者都commit；要么所有参与者都abort。 在没有异常的情况下，2PC是很容易理解的。理解2PC的难点在于出现异常的情况下协议如何保证事务的正确执行执行。

2PC协议中有两种身份：协调者(coordinator)和参与制(participant)。2PC包括两个阶段，每个阶段各自包含两个步骤。下面请跟着 笔者的思路逐渐加深对2PC协议的理解。

2PC算法

理想时代：没有异常
此时，我们假设所有参与者、网络都不会出现异常，这种情况下2PC没有任何难度。

1. 协调者向所有参与者发出VOTE_REQUEST请求，然后协调者阻塞等待所有参与者的响应
2. 参与者在收到VOTE_REQUEST的时候，执行事务预处理，根据预处理的结果响应coordinator：VOTE_COMMIT或者VOTE_ABORT； 然后参与者等待协调者的最后决定(global_decision)
3. 协调者等待所有的参与者的响应，如果所有参与者都响应VOTE_COMMIT，那么协调者就向所有参与者发出GLOBAL_COMMIT； 如果至少有一个参与者响应VOTE_ABORT，那么协调者就向所有参与者发出GLOBAL_ABORT
4. 参与者根据协调者的决定(global_decision)在本地进行事务操作

在理想的时代，一切都是完美的，一切都是简单的。协调者的状态转移图如下：

参与者的状态转移图如下：

次理想时代：节点、网络异常会最终恢复
本节的算法摘自《Distributed Systems: Principles and Paradigms》。

Actions of Coordinator

write START_2PC to local log;
multicast VOTE_REQUEST to all participants;
while not all vote have been collected {
	wait for any incoming vote;
	if timeout {
		write GLOBAL_ABORT to local log;
		multicast GLOBAL_ABORT to all participants;
		exit;
	}
	record vote;
}
if all participants sent VOTE_COMMIT and coordinator votes COMMIT {
	write GLOBAL_COMMIT to local log;
	multicast GLOBAL_COMMIT to all participants;
} else {
	write GLOBAL_ABORT to local log;
	muticast GLOBAL_ABORT to participants;
}

Actions of participant;

WRITE INIT to local log;
wait for VOTE_REQUREST from coordinator;
if timeout {
	write VOTE_ABORT to local log;
	exit;
}
if participant vote COMMIT {
	write VOTE_COMMIT to local log;
	send VOTE_COMMIT to coordinator;
	wait for DECISION from coordinator;
	if timeout {
		multicast DECISION_REQUEST to other participants;
		wait until DECISION is received; /* remain blocked */
		write DECISION to local log
	}
	if DECISION == GLOBAL_COMMIT
		write GLOBAL_COMMIT to local log;
	else if DECISION == GLOBAL_ABORT
		write GLOBAL_ABORT to local log;
} else {
	write VOTE_ABORT to local log;
	send  VOTE_ABORT to coordinator;
}

最糟糕的时代：协调者和参与者在死亡后无法恢复

2PC很无辜的看着大家，其实这个与我无关。听我详细道来。

算法解析

2PC这个协议本身其实本不难，难的是很多人（包括我自己）在学习算法本身的时候会思考如何把他应用在实际系统上。是想， 如果我们假设任何阶段coordinator或者participant出现异常，那么整个算法就停止在那个地方一直循环等待，直到退出的节点 恢复，算法才继续往前走，这个算法其实一点难度都没有。但是每个人都会思考，这样的算法在实际过程中还有用吗？实际过程中 的工程师们是如何来处理这个问题的？只要一思考这些，读者就会觉得怎么都不对。其实就2PC而言，他本来就是一个阻塞的算法， 在所有participant都响应VOTE_REQUEST之后，在收到DECISION之前，coordinator宕机，那么算法就会一直阻塞，因为没有人 知道最后的decision是什么。既然它天生就是阻塞的，那么我们直接再弱化一下它好了，任何步骤主要出现异常，算法都阻塞。 这样理解到的才是算法的实质。

可能有人会问，上面算法中有的地方在超时后会进行一些操作，然后算法可以继续；有些地方在超时后算法无法继续；这是为什么？ 什么时候决定算法可以继续，什么时候应该阻塞？以我对算法本身的理解，继续还是阻塞的标准是：

是否会导致事务的结果处于一种不一致的状态（一部分参与者commit，一部分参与者abort）；如果不会出现不一致的情况， 那么算法可以继续；否则就必须阻塞。

可以这么理解：非阻塞的部分是算法的优化。算法继续，唯一会出现不一致状态的情况是，所有的参与者都响应了VOTE_REQUEST，在 任何参与者收到decision之前coordinator宕机死亡，此时所有参与者都必须等待coordinator恢复。

有个同事的观点：所有参与者(包括协调者)都必须通过多副本的方式保证自己的高可用性， 因为单副本不可用的问题不是2PC这个协议的 目的，如果没有2PC这个协议，单副本的不可用性也是存在的，因此这种问题与2PC无关。可以说2PC本身不解决高可用性问题，它仅仅 解决的是atomic group commit的问题，这是2PC的假设，也是理解2PC的关键。一句话：每个协议解决自己的问题，不要带着你面临的 n个问题来理解2PC(包括其他分布式协议)，这样只能使你自己陷入死角。

大家会说，那么每个协议如果这样去了解，岂不是都很简单，我作为架构师的最终目的是实现高可用的系统，而不是分开理解每个协议。 呵呵，可以理解，我和大家一样由于这个想法走了很多的弯路。我会后续慢慢的告诉大家2PC如何在高可用的系统中使用。在分布式 一致性这一系列文章中，我会为大家逐一解开谜底。

• Large-scale Incremental Processing Using Distributed Transactions and Notifications 看google如何使用2PC实现实时搜索，通过BigTable自身的高可用性解决解决participants的高可用性问题；通过 乐观锁解决coordinator不具备高可用性的问题。看了这篇分析，你会发现前面我关于2PC的分析是正确的。

• Chubby一种可能的实现解析，看2PC如何与PAXOS结合实现replicated state machine，通过 分布式选举解决coordinator的高可用性问题，通过replicated state machine解决participants的高可用性问题。

对工程实践的指导

还是从同事那里讨论得到的：如果在分布式系统中，协议包括这种逻辑：A发起一个请求给所有人； 等待所有人响应之后A继续进行处理。这样的东西一看就太复杂，不靠谱，因为这相当于实现了一个2PC，有些偏复杂，如果必须这么实现， 那么同学，你一定要按照2PC的理解方式去理解，去分析这个问题。

其实在分布式系统中，需要使用2pc思想指导设计的地方很多。一个很简单的例子，中心节点控制从一个数据节点拷贝一个分片到另外一个数据 节点就需要这样的协议。以gfs增加block副本为例，当gfs metaserver的后台线程发现某个block的副本数量小于配置的阈值的时候，就会发起 副本拷贝的任务：将block从一个chunkserver拷贝到另外一个chunkserver。这样的场景会产生如下问题：

• metaserver如何监控拷贝进度？
• 如果拷贝的源失败如何处理？
• 如果拷贝的目的失败如何处理？

一个比较挫的设计方法：meta不断的去询问源或者目的，任务是否结束，根据复制的结果决定如何进行后续的操作。想一想，这个实现起来有 多困难，metaserver上有上十万的block，如何处理？

看看伟大的google是如何处理的，metaserver为所有复制任务维护一个任务队列，任务队列中的任务有超时时间； 后台线程发现副本数量小于配置的阈值，首先查看任务队列中是否有任务正在进行该bock的复制操作，如果有任务 则不做任何事情；如果没有相应的任务，则发起任务。metaserver的工作到此为止。那么如何判断任务队列中的任务 完成与否呢？这是chunkserver的事情，复制的目的会在复制任务完成后向metaserver汇报新复制的block， metaserver在收到复制完成的汇报后会把相应的任务从任务队列中删除。这样，整个协议很简单，很清晰，不易出bug。 之前那种挫的设计，状态太难维护。在我们实际的工程实践中，一定要尽量少的使用一个进程去等待另外两个进程 完成某项任务的协议，这样的协议太难维护了。

（本文是《数据库系统实现》第2版 Hector Garcia-Molina Jeffrey D.Ullman Jennifer Widom 杨冬青等译 第6章系统故障对策的学习笔记）

undo日志有一个潜在的问题，即我们在将书屋改变的所有数据写到磁盘前不能提交该事务。有时，如果让数据库修改暂时只存在于主存中，我们可以节省磁盘IO;只要在崩溃发生时有日志可以恢复，这样做就是安全的。

如果我们使用redo日志机制，立即将数据元素备份到磁盘的需要就可以被避免。redo日志和undo日志的主要区别是：

1. undo日志在恢复时消除未完成事务的影响并忽略已提交事务，而redo日志忽略未完成的事务并重复已提交事务所做的改变。
2. undo日志要求我们在COMMIT日志记录达到磁盘前将修改后的数据元素写到磁盘，而redo日志要求COMMIT记录在任何修改后的值到达磁盘前出现在磁盘上
3. 当遵循undo规则U1和U2时，在恢复时我们需要的是发生改变的数据源的旧值，而是用redo日志恢复时，我们需要的是新值。

规则

在redo日志中，日志记录的含义是“事务T为数据库元素X写入的新值v”。在这个记录中没有指出X的旧值。每当一个事务T修改一个数据元素X时，必须网日志中写入一条形如的记录。

对于redo日志，数据和日志项达到磁盘的顺序可以用一条“redo规则”描述，这条规则成为先写日志规则：

R1: 在修改磁盘上的任何数据元素X以前，要保证与X的这一修改先骨干的所有的日志记录，包括更新记录及记录，都必须出现在磁盘上。

事务的COMMIT记录只有在事务完成后才能写入日志，因而提交记录必然在所有更新日志记录后，所以当使用redo日志时，与一个事务相关的材料写入到磁盘的顺序为：
1. 指出被修改元素的日志记录。
2. COMMIT日志记录
3. 改变数据元素自身

下面我们按照undo日志规则来考虑如下的事务T:

A := A*2
B := B*2

| 步骤 | 动作        |  t | M-A | M-B | D-A | D-B | 日志       |
|------+-------------+----+-----+-----+-----+-----+------------|
|   1) |             |    |     |     |     |     | <START T>  |
|   2) | READ(A, t)  |  8 |   8 |     |   8 |   8 |            |
|   3) | t := t*2    | 16 |   8 |     |   8 |   8 |            |
|   4) | WRITE(A, t) | 16 |  16 |     |   8 |   8 | <T, A, 16> |
|   5) | READ(B, t)  |  8 |  16 |   8 |   8 |   8 |            |
|   6) | t := t*2    | 16 |  16 |   8 |   8 |   8 |            |
|   7) | WRITE(B, t) | 16 |  16 |  16 |   8 |   8 | <T, B, 16> |
|   8) |             |    |     |     |     |     | <COMMIT T> |
|   9) | FLUSH LOG   |    |     |     |     |     |            |
|  10) | OUTPUT(A)   | 16 |  16 |  16 |  16 |   8 |            |
|  11) | OUTPUT(B)   | 16 |  16 |  16 |  16 |  16 |            |

恢复

redo规则R1的一个重要推论是，只要日志中没有记录，我们就知道事务T对数据库所做的更新都没有写到磁盘上。因此，恢复时对未完成事务的处理就可以像它们从未发生似的。然而，已提交的事务存在问题，因为我们不知道他们的那些数据库改变已经写到磁盘。幸运的是，redo日志正好有我们需要的信息：新值。我们可以讲新值写到磁盘而不管他们是否已经在磁盘上。在系统崩溃后要使用redo日志恢复，我们需要做以下事情：
1. 确定已提交的事务。
2. 从收不开始扫描日志。对遇到的每一个记录：
a) 如果T是未提交的事务，则什么也不做
b）如果t是提交的事务，则为数据库元素X写入值v
3. 对每个未完成的事务T，在日志中写入一个记录并刷新日志。

我们考虑上图中的日志，看看在不同步骤上发生故障时如何进行恢复。
1. 如果故障发生在第9步的任何时候，那么记录已被刷新到磁盘。T是一个提交的事务。当向前扫描日志时，日志记录和将A和B写入16.请注意，如果故障发生在第10和11步之间，那么写A是多余的，而写B还未发生，因而将B改变为16是恢复数据库的一致状态所必须的。如果故障发生在第11步以后，那么些A和写B都是多余的但也是无害的。
2. 如果故障发生在第8和第9步之间，那么尽管记录写入了日志，但可能还没有到达磁盘(依赖于日志是否因其他原因而刷新）。如果该记录到达磁盘，则恢复如情况1那样进行，而如果该记录没能到达磁盘，那么恢复和下面的情况3一样。
3. 如果故障发生在第8步以前，那么记录肯定没有达到磁盘。因此，T被看做一个未完成的事务。磁盘上的A和B不为T做任何改变，而最后一条记录被写到日志中。

检查点

对于redo日志的检查点，这儿有一个undo日志中没有的问题。由于已提交事务做的数据修改拷贝到磁盘的时间可能比事务提交的时间晚的多，因此我们不能仅仅考虑在我们决定创建检查点时活跃的事务。在检查点的开始和结束之间我们必须将已被提交事务修改的所有数据库元素写到磁盘。

另一方面，我们不需要等待活跃事务提交或中止就能完成检查点，因为他们呢无论如何都不被允许在那个时候将它们写到磁盘。进行redo日志的非静止检查点步骤如下：
1. 写入日志记录，其中T1,...,Tk是所有活跃（即未提交的）事务，并刷新日志
2. 将START CKPT记录写入日志时所有已提交事务已经写到缓冲区但还没有写到磁盘的数据写到磁盘
3. 写入日志记录并刷新日志

例：下图给出了一个可能的redo日志，其中发生了一个检查点。当我们开始检查点时，只有T2是活跃的，但T1所写的A值可能已经到达磁盘。如果没有，那么我们必须在检查点结束前将A拷贝回磁盘。我们表明检查点的技术在几个其他的事件后发生：T2为数据库元素C写入一个值，一个新事务T3开始并为D写入一个值。在检查点结束后发生的唯一的事情是T2和T3提交。

<START T1>
<T1, A, 5>
<START T2>
<COMMIT T1>
<T2, B, 10>
<START CKPT(T2)>
<T2, C, 15>
<START T3>
<T3, D, 20>
<END CKPT>
<COMMIT T2>
<COMMIT T3>

使用带检查点的redo日志恢复

首先假设崩溃发生前日志中的最后一条检查点记录是。现在，我们知道在对应的前提交的事务已经将其修改写到了磁盘，因此我们不必关心如何恢复这些事务的影响。但是Ti中的任一事务或检查点开始后启动的任一事务及时已经提交，都仍然可能未将其修改转到磁盘上。因此，需要进行恢复，但可以只关心最后一个START CKPT(T1,...,Tk)中提到的事务Ti与该日志记录中在日志中出现后开始的事务。在搜索日志时，我们在找到最早的记录后就不必继续向后看。蛋清注意，这些START记录可能出现在任意多个检查点前。将一个事务的所有日志记录向后链接在一起可以帮助我们找到所需记录。

现在建设日志中的最后一条检查点记录是：

<START CKPT(T1,...,Tk)>

我们不能确定再次检查点开始前提交的事务是否已经将其修改写到磁盘上。因此我们必须搜索到前一记录，找到与之匹配的记录，并重做这些已经提交的事务，这些事务要么在START CKPT后开始要么在Si中。

例：考虑上图中的日志。如果故障在尾部发生，我们向后搜索，找到记录。我们只需知道将所有在写记录后开始的事务以及出现在该记录的列表中的事务(T2)作为重做的候选者。因此，我们的候选集合是{T2, T3}。我们找到了记录和，于是我们知道他们都必须重做。我们向后搜索日志直到记录，为提交的事务找到更新记录, , 。由于我们不知道这些改变是否已经到达磁盘，我们分别为B、C、D重新写入值10、15、20.

现在我们假设崩溃在记录和之间发生。恢复过程与上述过程类似，只不过T3不再是已提交的事务，因此其修改不能被重做，并且在恢复中不对D做任何改变，尽管日志记录处于被检查记录范围内。恢复后我们也要在日志中写入一条记录。

最后，假设崩溃正好在记录前发生。原则上，我们必须i型昂后搜索到倒数第二个START CKPT记录并得到其活跃事务里诶包。但是，这种情况下没有前一个检查点，因为我们必须一致走到日志的开头。因此我们确定已提交的只有T1，重做其动作，并且在恢复后将记录和写入到日志中。

（本文是《数据库系统实现》第2版 Hector Garcia-Molina Jeffrey D.Ullman Jennifer Widom 杨冬青等译 第6章系统故障对策的学习笔记）

日志是日志记录构成的文件，每个日志记录记载着有关某个事务一座的事情。如果日志记录出现在非易失性的存储器中，那么在系统奔溃之后，我们就可以使用它们来将数据库恢复到一个一致的状态。
undo日志通过撤销事务在系统奔溃前可能没有完成的影响来恢复数据库的状态。

规则

U1: 如果事务T改变了数据元素X，那么形如的日志记录并需在X的新值写到磁盘之前写到磁盘中

U2: 如果事务提交，则其COMMIT日志记录必须在事务改变的所有数据库元素先写到磁盘之后写到磁盘中，但应尽快。

下面我们按照undo日志规则来考虑如下的事务T:

A := A*2
B := B*2

将A在内存缓冲区中的拷贝记为M-A, A在磁盘上的拷贝记为D-A。

| 步骤 | 动作       |  t | M-A | M-B | D-A | D-B | 日志       |
|------+------------+----+-----+-----+-----+-----+------------|
|   1) |            |    |     |     |     |     | <START T>  |
|   2) | READ(A,t)  |  8 |   8 |     |   8 |   8 |            |
|   3) | t := t*2   | 16 |   8 |     |   8 |   8 |            |
|   4) | WRITE(A,t) | 16 |  16 |     |   8 |   8 | <T,A,8>    |
|   5) | READ(B,t)  |  8 |  16 |   8 |   8 |   8 |            |
|   6) | t := t*2   | 16 |  16 |   8 |   8 |   8 |            |
|   7) | WRITE(B,t) | 16 |  16 |  16 |   8 |   8 | <T,B,8>    |
|   8) | FLUSH LOG  |    |     |     |     |     |            |
|   9) | OUTPUT(A)  | 16 |  16 |  16 |  16 |   8 |            |
|  10) | OUTPUT(B)  | 16 |  16 |  16 |  16 |  16 |            |
|  11) |            |    |     |     |     |     | <COMMIT T> |
|  12) | FLUSH LOG  |    |     |     |     |     |            |

恢复

恢复的第一个任务是将事务划分成已提交事务和未提交事务。如果日志记录，那么根据undo规则U2，事务T所做的全部改变在此之前已写到磁盘上。因此发生故障时，T自身不可能使数据库处于不一致的状态。

然而，假设我们在日志上发现了记录，但未发现记录，那么有可能在奔溃前T对数据库所做的某些修改写到了磁盘上，而T的另一些修改在内存缓冲区中还没有进行，或者在缓冲区中进行了但还未拷贝到磁盘上。在这种情况下，T是一个未完成的事务因而必须要撤销。也就是说，T所做的任何改变都必须重置为原有的值。

由于日志中有多个未提交的事务，并且可能有多个未提交的事务修改了X，所以我们在恢复值的顺序上必须是有计划的。我们从尾部开始扫描日志，在扫描过程中，记住所有的或记录的事务T。同时在其向后扫描过程中，如果看到记录，则

1. 如果T的COMMIT记录已经被扫描到，则什么也不做。T已经提交因为不需要撤销。

2. 否则，T是一个未完成的事务或者一个中止的事务。必须将数据库中X的值改为v，以防万一恰好在系统崩溃前X已经被修改了。

做了这些改变后，必须为以前未中止的且未完成的每个事务T写一个日志记录，然后刷新日志。现在数据库可以恢复正常的操作，新的事务可以开始执行。

下面我们来一个实际的例子：

1. 如果崩溃发生在12步之后。记录在崩溃前已经到达磁盘。表示T成功完成

2. 崩溃发生在11步和12步之间，包含COMMIT的日志记录可能已被刷新到磁盘，那么事务T已经完成；如果COMMIT记录尚未到达磁盘，那么事务T未完成。当它向后扫描日志时，首先遇到记录.于是它将B在磁盘上的值存为8.接着它遇到记录，并将A在磁盘上的值置为8。最后记录被写到日志中且日志被刷新

3. 崩溃发生在第10步和第11步之间。现在，COMMIT记录肯定没有写入，因此T未完成并且回想情况2中那样撤销。

4. 崩溃发生在第8步和第10步之间。于是T也被撤销。在这种情况下，A或B的更新可能尚未到达磁盘。不管怎样，这些数据库元素中的每一个都存为正确的值8。

5. 崩溃发生在第8步以前。现在，关于T的日志记录是否已到达磁盘上并不确定。然而根据规则U1我们知道，如果对A或B所做的更新已到达磁盘，则相应的日志记录也已达到磁盘。因而如果T在磁盘上改变了A或B，那么相应的日志记录将使恢复管理器撤销这些改变

检查点

正如我们看到的那样，恢复原则上需要检查整个日志。当采用undo类型的日志时，一旦事务的COMMIT日志记录被写到磁盘上，该事务的日志记录在恢复时就不再需要。我们可以设想在COMMIT前删除日志，但有时却不能。原因在于，常常是很多事务同时在执行。如果我们在一个事务提交后将日志截断，关于另外的某个活跃事务T的日志记录就可能丢失，从而不能再需要进行恢复时用来撤销T。

我们可以使用检查点来解决这个问题，步骤包括：
1. 写入日志记录并刷新日志。其中T1,...,Tk是所有活跃事务（即尚未提交和将其修改写到磁盘的事务）的名字或标记符。

2. 等待T1,...,Tk中所有事务提交或中止，但允许其他事务开始

3. 当T1,...,Tk都已完成时，写入日志记录并刷新日志

采用这种类型的日志，我们可以按照如下所述从系统故障中恢复。和通常一样，我们从尾部开始扫描日志，在进行扫描过程中找到所有未完成的事务，并将这些事务所改变的数据元素恢复为其旧值。根据在向后扫描时我们先遇到记录还是记录，有两种情况：
1. 如果我们先遇到记录，那么我们知道所有未完成事务在前一记录后开始。因此我们可以向后扫描知道下一个START CKPT记录，然后就停止；以前的日志没有用处因此可以抛弃。

2. 如果我们先遇到记录，那么崩溃发生在检查点过程中。但是未完成的事务只有在向后扫描过程中到达START CKPT前遇到的那些以及T1,...,Tk中在发生崩溃前还没有完成的那些。因此，我们扫描到这些未完成事务中最早的那个事务的开始就不必在继续向后扫描。前一个START CKPT记录当然比这些事务的开始都早，但是通常我们发现这些未完成事务的开始比到达上一检查点要早的多。

例如日志开始是：

<START T1>
<T1, A, 5>
<START T2>
<T2, B, 10>

现在我们来做一个检查点，由于T1和T2在这时是未完成的事务，我们写入日志记录

<START CKPT(T1, T2)>

假设在等待T1和T2完成时，另一个事务T3开始了。日志的后续部分为

<START T1>
<T1, A, 5>
<START T2>
<T2, B, 10>
<START CKPT(T1, T2)>
<T2, C, 15>
<START T3>
<T1, D, 20>
<COMMIT T1>
<T2, E, 25>
<COMMIT T2>
<END CKPT>
<T3, F, 30>

假设这时发生了崩溃。从尾部开始检查日志，我们发现T3是未完成事务因为必须被撤销。最后一条日志记录告我们元素F恢复为30.当我们发现记录，我们知道所有未完成事务在前一个START CKPT后开始。进一步向后扫描，我们发现记录，它告诉我们将E恢复为25。在该记录与START CKPAT之间没有其他已开始但尚未提交的事务，所以对数据库不再做进一步的改变。

（本文是《数据库系统实现》第2版 Hector Garcia-Molina Jeffrey D.Ullman Jennifer Widom 杨冬青等译 第6章系统故障对策的学习笔记）

在事务执行的过程中如果发生了掉电或者其他的软件错误，由于掉电后内存中的内容会丢失，导致数据库的状态不一致，虽然我们不能防止各种异常的发生，但是我们可以在发生这些情况后对数据进行修复，保证事务的正确执行。
假设事务T逻辑上由下述两步构成：

A := A*2
B := B*2

我们规定如下的记法来描述所有使数据在地址空间之间移动的操作，我们使用的源于包括：

1. INPUT(X): 将包含数据库元素X的磁盘拷贝到内存缓冲区中。
2. READ(X, t): 将数据库元素X拷贝到事务的局部变量t中。更准确的说，如果包含数据库元素
X的块不在主存缓冲区中，则首先执行INPUT(X)，接着将X的值赋给局部变量t。
3. WRITE(X, t): 将局部变量t的值拷贝到内存缓冲区中的数据元素X。更准确的说，如果包含数
据元素X的块不在内存缓冲区中，则首先执行INPUT(X), 接着将t的值拷贝到缓冲区中的X。
4. OUPUT(X): 将包含X的缓冲区中的块拷贝回磁盘。
T的执行包括从磁盘读A和B，在T的局部地址空间中执行算术运算，以及将A和B的 新值写入其缓冲区中。我们可以讲T表述成6个相关步骤的序列：
RREAD(A, t); t := t*2; WRITE(A, t); READ(B, t); t := t*2; WRITE(B, t);

下图给出了T的步骤，我们假设最初A=B=8。图中给出了每一步中A和B的内存拷贝的值、磁盘拷贝的值以及事务T地址空间中局部变量t的值。

第一步，T读A，如果A的块不再缓冲区中，这将导致缓冲区管理器产生INPUT(A)命令。 READ命令还将A的值拷贝到T的地址空间的局部变量t中。

第二步，将t加倍，这一步对A没有任何影响，不管是缓冲区中还是磁盘上。

第三步，将t写到缓冲区A中；它不会影响磁盘上的A。

接下来的3步对B做同样的事情，而最后两步将A和B拷贝到磁盘上

不难发现，只要所有的步骤都执行，数据库的一致性就能得到保值。如果在执行OUPUT(A)前发生了系统故障，那么磁盘上存储的数据库不会受到任何影响，仿佛T从未发生过，一致性得到保值。但是，如果磁盘故障发生在OUPUT(A)之后和OUPUT(B)之前，那么数据库就会处于不一致的状态。我们不能防止这种情况的发生，但是我们可以安排当这种情况发生时对问题进行修复–或者A和B都被重置为8，或者二者都更新为16。

原文：http://neopythonic.blogspot.jp/2008/10/sorting-million-32-bit-integers-in-2mb.html
译文：http://article.yeeyan.org/view/1345/17685

有人开玩笑地问我 如何使用python在2M内存中排序一百万个32位整数.为了应付这个挑战,我学习了一下缓冲I/O.

很明显,这是一个开玩笑的问题.假设是二进制编码,单单是数据就已经占了4M!唯一的解释就是: 给定一个包含一百万个32位整数的文件,你如何使用最少内存去排序好它们?这可能需要使用某种合并排序的方式,把数据分块在内存排序,并保存到临时文件中去,最后把临时文件合并获得最终结果.

下面是我的解决方案,稍候会解释.

注意:所有的例子都是使用python3.0. 这个例子的不同之处就是使用file.buffer访问二进制流的方式去访问字符流文件.

#!/usr/bin/env python3.0
import sys, array, tempfile, heapq
assert array.array('i').itemsize == 4
 
def intsfromfile(f):
  while True:
     a = array.array('i')
     a.fromstring(f.read(4000))
     if not a:
         break
     for x in a:
         yield x
 
iters = []
while True:
  a = array.array('i')
  a.fromstring(sys.stdin.buffer.read(40000))
  if not a:
      break
  f = tempfile.TemporaryFile()
  array.array('i', sorted(a)).tofile(f)
  f.seek(0)
  iters.append(intsfromfile(f))
 
a = array.array('i')
for x in heapq.merge(*iters):
  a.append(x)
  if len(a) >= 1000:
      a.tofile(sys.stdout.buffer)
      del a[:]
if a:
  a.tofile(sys.stdout.buffer)

在我的Google桌面(一个使用了3年,跑着Googlified Linux的个人电脑,用Python3.0的pystones测试得分是34000),在输入文件包含一百万个32位随机整数的情况下,这个程序大概花 了5.4秒.还不太差,如果直接在内存中排序大概需要2秒:

#!/usr/bin/env python3.0
import sys, array
a = array.array('i', sys.stdin.buffer.read())
a = list(a)
a.sort()
a = array.array('i', a)
a.tofile(sys.stdout.buffer)

回到合并排序方案.头三行非常明显:

#!/usr/bin/env python3.0
import sys, array, tempfile, heapq
assert array.array('i').itemsize == 4

第一行表示我们使用Python3.0.第二行引入将使用的模块.第三行检查到64位系统时中断程序,因为64位系统中'i'的类型值不是表示32位整数;这里我没有考虑代码的移植性.
然后我们定义一个辅助函数,它是一个从文件读入的整数的生成器:

def intsfromfile(f):
  while True:
      a = array.array('i')
      a.fromstring(f.read(4000))
      if not a:
          break
      for x in a:
          yield x

这个地方已经调优了算法性能: 它每次读入1000个整数,然后一个个yield.我原来没有用到缓冲 -- 它就每次只从文件读入4个字节,转换成整数,然后yield.但程序跑起来就慢了4倍!要注意的是我们不能使用a.fromfile(f,1000)因为 fromfile()方法在文件没有足够的值的情况下会出错,并且我想要代码能自动适应文件中的整数.(我原先设想大概会写入10,000个整数到一个临 时文件中.)

接着我们进入循环.反复地从输入文件读入10,000个整数,在内存中排序,然后写入临时文件.我们为临时文件增加一个迭代器,通过上面的intsfromfile()函数,使其成为迭代器中的一个列表,以备在随后的合并阶段使用.

iters = []
while True:
  a = array.array('i')
  a.fromstring(sys.stdin.buffer.read(40000))
  if not a:
      break
  f = tempfile.TemporaryFile()
  array.array('i', sorted(a)).tofile(f)
  f.seek(0)
  iters.append(intsfromfile(f))

要注意的是,为了应对包含一百万个值的输入,程序将会创建100个包含10,000个值的临时文件.
最后我们合并这些文件(每个都已经排序). heapq模块有一个非常实用的函数: heapq.merge(iter1, iter2, ...)它把多个已排序的输入值(如本例中的)合并排序，返回一个有序的迭代器。

a = array.array('i')
for x in heapq.merge(*iters):
  a.append(x)
  if len(a) >= 1000:
      a.tofile(sys.stdout.buffer)
      del a[:]
if a:
  a.tofile(sys.stdout.buffer)

这里也是一个必不可少使用缓冲I/O的地方:当一个值可用的时候就写入文件,这样会成倍地减慢算法速度.因此,通过简单地增加输入输出缓冲,可以获得上十倍的速度提升!

这就是程序的主要思路了.

另外我们还能体验到heapq模块的强大，它包含了在输出阶段需要的合并迭代器功能。当然，array模块管理二进制数据的便利也是令人印象深刻的。

最后,通过这个例子让你们知道,Python 3.0相对于Python2.5来说差别并不是很大!

如何估计排序1GB int32_t的数据需要多少时间？ Jeff dean在stanford演讲中给了我们一种方法。

数字比较花费的时间

比较次数：log(2^28) passes over 2^28 numbers = ~2^33 comparisons
1/2的比较会误判，因此 2^32 mispredicts * 5ns/mispredictt = 21 s

内存拷贝(顺序访问)

2^30 bytes * 28 passes = 28GB
Mermory bindwidth ~4GB/s
大约为 28GB/4Gb = 7s

总共需要大约30s的时间来排序1GB的数据。

下面我们来写测试一下实际的运行时间：

#include <iostream>
#include <vector>
#include <algorithm>
#include <sys/time.h>
#include <time.h>
#include <stdint.h>
using namespace std;
 
double get_time() {
    struct timeval tv;
    gettimeofday(&tv, NULL);
    return tv.tv_sec + tv.tv_usec / 1000000.0;
}
 
int main() {
 
    vector<int> array(1024 * 1024 * 1024 / sizeof(int32_t));
    srand(unsigned(get_time()));
    for (size_t i = 0; i < array.size(); i++) {
        array[i] = rand();
    }
    double start = get_time();
    sort(array.begin(), array.end());
    double end = get_time();
    cout << "time cost: " << end - start << endl;
    return 0;
}

以O2的参数编译并且运行

g++ -O2 sort.cc && ./a.out
time cost: 34.3306

附录：
Numbers Everyone Should Know

变量在使用前一定要有一个初值，否则会发生许多预想不到的结果，比如下面的例子。

// File example.cc
#include <iostream>
using namespace std;
int main() {
    {
        int x = 101;
    }
    int y;
    cout << y << endl;
    return 0;
}

g++ example.cc && ./a.out
101

在我的环境下g++ (GCC) 3.4.5 20051201 (Red Hat 3.4.5-2)，
y的值为101，因为在x在栈上的初始值为101，过了x的作用域之后，这块内存供y使用，所以y的默认值也是101.

当然如果以不同的选项编译，可能会得到不同的结果。

g++ -O1 example.cc && ./a.out
0

以O1的优化选项，结果y的初值为0.

g++ -O2 example.cc && ./a.out
-1073745352

以O2的优化选项编译，这个时候由于x没有被下面用到，编译器可能就直接忽略了x这个局部变量，因此y为一个随机值。

因此当变量没有初值时，往往会发生许多奇怪的事情，虽然我们有时过于自信认为没有初值没有关系，后面的处理逻辑肯定会给它一个值，不过为了以防万一还是有一个初值比较保险。

http://maxburstein.com/blog/python-shortcuts-for-the-python-beginner/

发现有些同学不知道，其实很简单。（Linux shell下的Python自动提示功能)
新建一个文件 ~/.python_init.py, 内容如下

import rlcompleter, readline
readline.parse_and_bind('tab: complete')

~/.bashrc 末尾加一行 export PYTHONSTARTUP=~/.python_init.py

上一篇我们介绍了Python中如何使用swig来调用C++，本节介绍一下如果有复杂对象 vector、string时如何使用swig。

1. 一个简单的School类，代码下载

// File: school.h 
#include <vector>
#include <string>
class School {
public:
    void SetName(const std::string& name);
    void AddStudent(const std::string& student_name);
    std::string name() const;
    std::vector<std::string> students() const;
private:
    std::vector<std::string>  students_;
    std::string name_;
};
 
// File: school.cpp
#include "school.h"
 
void School::SetName(const std::string& name) {
    name_ = name;
}
void School::AddStudent(const std::string& student_name) {
    students_.push_back(student_name);
}
std::string School::name() const {
    return name_;
}
 
std::vector<std::string> School::students() const {
    return students_;
}

2. swig接口文件, 注意我们使用了stl.i（vector, string)和StringVector(vector)

%module school
%{
#include "school.h"
#include <string>
#include <vector>
%}
 
%include stl.i
%include "school.h"
 
namespace std {
%template(StringVector) vector<string>;
}

3. 通过swig生成封装代码和动态链接库

swig  -python -c++ school.i
g++ -c school.cpp school_wrap.cxx -I /usr/local/include/python2.6/ -fPIC
g++ -shared school.o school_wrap.o -o _school.so

下面我们就可以使用了

>>> import school      
>>> zju=school.School()  
>>> zju.SetName('Zhejiang University')
>>> zju.name()
'Zhejiang University'
>>> zju.AddStudent('tom')
>>> zju.AddStudent('kate')
>>> for student in zju.students():
      print student
tom
kate

4. 当然我们也可以使用Python自带的安装工具(distutils)

# File: setup.py
from distutils.core import setup, Extension
from os import system
 
example_module = Extension('_school',
                           sources=['school.cpp', 'school_wrap.cxx']
                          )
 
system('swig -python -c++ ./school.i')
setup(name='pair',
      version='0.1',
      author='liming04',
      description="""Simple swig example""",
      ext_modules=[example_module],
      py_modules=['example'],
      )

有关swig更多的技术细节请大家参考http://www.swig.org/Doc1.3/Python.html 。