Greenplum内核源码分析

目录

• 前言

• 一致性算法

• Steal/Force 和 WAL 协议

前言

Greenplum 公司是 2003 年成立的，在 2010 年被 EMC 公司收购。Greenplum 是从开源的 PostgreSQL 二次开发出来的， 早期的 Greenplum（version 3.x）是改写的 Postgresql（version 8.0）。所以，我们能看到 Greenplum 用的基础架构都是来自 PostgreSQL。 到了 5.x 版本，Greenplum 基本到达了一个稳定的阶段，中间经历了十多年。Greenplum 现在完全开源，而且也不停的在进步。 社区的策略是从 PostgreSQL 上游获取新的 feature，经过小改动直接拿到 Greenplum 里面使用。目前主要维护的是 6.x 版本的 Greenplum， 已经使用了 Postgresql 9.4。从 5.x 到 6.x，Greenplum 不但把上游的 PostgreSQL 换成了 9.4，而且做了很多大的改动，算是一个很大的进步。

作者对 Greenplum 源码的分析会使用Greenplum 5.x 版本，读者可以去 github 上面自行获取。

一致性算法

目前主要的一致性算法包括: 2PC(两阶段提交)， 3PC(三阶段提交) ， Paxos 和 Raft。

2PC：Two-Phase Commit ( 二阶段提交 ) 分两个阶段，Prepare，Commit Prepare。

第一阶段提交事务请求(投票阶段)，第二阶段：执行事务提交(执行阶段)。

算法优点是原理简单，实现方便。

缺点是有单点故障，会有同步阻塞，会出现数据不一致，脑裂。

协调者 coordinator 就是单点故障，如果协调者 fail 了，而且恢复不了，那么部分的参与者 participants 就再也不能把事务执行下去了。

对于参与者 participants，当它发送了 Yes Vote 给协调者以后，就必须一直等待协调者发送 Commit Prepare 或者 Rollback。中间这段过程是阻塞的。

尽管有缺点，绝大部分的分布式数据库都还是采用二阶段提交协议来完成分布式事务处理。

协调者 参与者 QUERY TO COMMIT --------------------------------> VOTE YES/NO prepare*/abort* <-------------------------------commit*/abort* COMMIT/ROLLBACK --------------------------------> ACKNOWLEDGMENT commit*/abort* <-------------------------------- end

复制代码

3PC：Three- Phase Commit ( 三阶段提交 ) 有 Prepare、PreCommit、Commit Prepare 三个阶段。

与 2PC 相比，增加了 PreCommit 阶段。3PC 想解决的问题是一种 2PC 里面的极端情况，就是协调者 coordinator 和有的参与者 participants，同时 fail。这时候剩下的参与者 participants，就不知道自己该回滚还是强制 commit 了。

3PC 和 2PC 相比，在参与者 participants 方面也加上了 timeout。

当然，3PC 也可能出现和 2PC 一样的情况，在最后一步也可能发生异常行为。所以也没有从根本上解决脑裂或者数据不一致的问题。只是将脑裂或者数据不一致的问题在一定的程度上缓解了。

Paxos 算法的目标是让整个集群对某个变更达成一致。对于某个变更，当 Proposer 收到半数以上的回复，那么变更就被 Accept。

Raft 算法把 Paxos 算法理论清晰化，简明化了，还提供了伪代码。

Greenplum 自己实现了 2PC 协议，后续的文章会结合内核源码深入分析。

Steal/Force 和 WAL 协议

我们都知道 Greenplum 和 PostgreSQL 使用了 MVCC 技术，WAL(Write Ahead Log)技术，使用这个技术背后的原因是什么？数据库的事务提交，为什么最后的落盘是 Xlog 的提交，而不是数据本身的提交？

数据库里面有个著名的算法叫做 ARIES 算法(Algorithms for Recovery and Isolation Exploiting Semantics)，这个算法描述了如何用 WAL(Write Ahead Logging)协议和 log 来恢复 crash 掉的数据库。

这个定义来自维基，

'In computer science, Algorithms for Recovery and Isolation Exploiting Semantics, or ARIES is a recovery algorithm designed to work with a no-force, steal database approach;'。

上面的描述里面，什么又是 no-force 和 steal 呢？围绕下面的图解释下这些概念。

数据库的数据最终会存放在磁盘里，但是在事务进行的过程中，中间数据是要存放在内存的 buffer 里面的。 关于磁盘和内存 buffer，或有甚者 cpu 的缓存，有方方面面的策略。这些策略，总体来说，无非是在速度和可靠性这两个方面取折衷。

steal 和 force 就是在表述这样的策略问题。 那么有 steal 和 force，就有 no-steal 和 no-force。

结合上面的图，四个大方框代表四种策略组合。

steal：   对于未提交的事务，buffer里面被修改过的脏页面可以被刷回持久存储。no-steal: 对于未提交的事务，buffer里面被修改过的脏页面不可以被刷回持久存储。
force：   在事务提交的时候，这个事务修改的数据页面强制被刷回持久存储。no-force: 在事务提交的时候，这个事务修改的数据页面不需要强制刷回持久存储。

复制代码

从直观上看 steal 和 force 这两个策略很清楚，为了保证数据库的 ACID 的原则，我们在实现数据库的时候，肯定会使用 force 和 no-steal 这个策略组合。

那为什么要提出来讲呢？因为我们的工程实现和理论不一样，会遇到种种问题。

force 策略的问题： 每次提交都要把数据刷回持久存储，那么持久存储的访问会非常频繁，导致数据库性能低下。

no-steal 策略的问题： 因为实际的数据库，系统的并发量有限，存储数据页面的 buffer 大小也是有限的。假设我们有一个很大的 sql， 这个 sql 请求修改的页面把所有的 buffer 都占满了，但是这个 sql 一直不提交。那么其他的 sql 就无法进行了。

所以图上，Force & No Steal 对应的方框标示的是 Slowest，代表使用这种策略组合的数据库运行执行效率是最低的。相反，它的对角线的方框代表的策略组合执行效率是最高的。

当然，还有另外一个考虑就是数据库在崩溃以后的 recoevry 恢复的效率，恢复效率和当前的运行执行效率是反过来的。以后有机会讲 Greenplum 数据库 recovery 的时候，再慢慢给大家讲。

上面的两个问题，是工程实现上向数据库提出的两个非常实际的问题。 那么怎么解决这样的问题呢？

工程上给出的答案是通过日志系统。

和摩尔定律一样，工程上面肯定是追求更高更快更强的策略的，所以选择的是图里面右上角的 Fastest，也就是 Steal & No Force 策略组合。

Steal 对应一种叫做 undo log 的日志文件，允许 buffer 里面被修改过的脏页面刷回持久存储，但是为了保证原子性，要先把 undo log 写入日志文件中。 undo log 里面记录了被修改的对象的旧值。

No Force 对应一种叫做 redo log 的日志文件，在事务提交的时候，这个事务修改的数据页面不需要强制刷回持久存储，但是为了保证持久性， 要先把 redo log 写入日志文件中。 redo log 里面记录了被修改的对象的新值。

这样记录的日志怎么使用呢？

就是在系统崩溃的时候使用。根据系统崩溃的时间点不同，使用方式也不同。

对于 undo log(它记录的是旧值)，系统在任何时候发生崩溃，恢复时是对 undo log 日志从后往前扫描，对未提交的事务的日志做 undo 操作。 这样就可以撤销那些未提交事务的修改，保证数据恢复到原来的值。

对于 redo log(它记录的是新值), 系统在任何时候发生崩溃，恢复时就对 redo log 日志从前往后扫描，对已提交的事务的日志做 redo 操作。 这样就可以把已经提交的事务恢复过来，保证数据变成新的值。

在使用的时候，把 undo log 和 redo log 的结合，既记录旧值，也记录新值。 恢复时，第一个阶段是分析阶段，第二个阶段是 redo 操作，第三个阶段是 undo 操作。

记录 redo/undo log 的日志，叫做 WAL 日志。它是按照 WAL(Write Ahead Logging)协议开发的，这个协议提出来以后，工程实现还是会遇到各种问题， 比如恢复过程中的异常，checkpoint，并发控制等等，后来 IBM DB2 的研发人员提出了一种叫做 ARIES 的恢复算法，这个算法提出来以后，才奠定了数据库按日志恢复的模型。

另外，数据库为了保证并发，都是用了 MVCC(Multi-Version Concurrency Control)技术，但是不同数据库实现 MVCC 是不一样的。

Greenplum/Postgresql 实现的 MVCC，更新元组操作不是 in-place update，而是重新创建 tuple。是在相同的存储空间里另外创建一个新的 tuple，把新值写到 tuple 里。 这样新值和久值都存储在一起，而且链接起来了。

就是因为这样的特点，Greenplum/Postgresql 不用记录 undo log，而且做 undo 的时候，是很快的。因为当事务的扫描到一个 tuple 时，可以通过可见性的判断来决定这个 tuple 是否对当前的事务可见。

与 Oracle/Mysql 比较，他们是有 undo log 段的，undo 操作的时候，也需要控制并发等等，也需要用 ARIES 的恢复算法来实现。

参考文献

https://en.wikipedia.org/wiki/Two-phase_commit_protocol

https://en.wikipedia.org/wiki/Algorithms_for_Recovery_and_Isolation_Exploiting_Semantics