Greenplum：A Hybrid Database for Transactional and Analytical Workloads

Introduction

Greenplum是一个老牌的、基于MPP架构的数据仓库系统，主打的OLAP功能，采用了share nothing和sharding的架构，能够处理PB级别的数据。Greenplum存在一个固定的coordinator节点，负责与client交互，查询计划的生成与分布式执行、事务的管理等，是一个比较重要的节点。其他segment节点（单机Postgres）则存储数据与本地查询和事务。为了增强Greenplum的OLTP能力，往HTAP的方向发展，论文中提到了Greenplum对以下几个方面进行了增强：

事务能力的增强：加入了全局的死锁检查器，避免了过去由于严格的锁机制导致并发能力不够的问题；对于单个segment server上的事务，由2PC转变为1PC；
提高点查询的性能；
引入了资源管理组，避免OLAP与OLTP两种查询负载相互影响；

从某种角度来说，Greenplum演变成HTAP数据库的路径与大多数数据库不一样，它是在传统的OLAP数据库上加强了OLTP功能的支持。

GreenPlum’s MPP Architecture

GreenPlum是一个典型的MPP架构，集群由多个worker segments组成，每个segment都是一个增强版的PostgreSQL。下图就是GreenPlum的架构。

Roles and Responsibility of Segments

一个GreenPlum集群由许多个跨主机的segments组成，其中会有一个segment是coordinator，其他的统称为segment server。coordinator是一个比较重的节点，负责接收client请求，生成分布式查询计划，根据计划生成分布式进程，将计划分配到每个进程，收集结果，返回到client。

segment server则是存储数据，从coordinator接收查询计划。为了提高可用性，segment也可以配置镜像节点，不参与计算，但会接收WAL并回放日志。

作为一个share nothing的架构，GreenPlum中每个segment都会有自己的共享内存和数据目录。

Distributed Plan and Distributed Executor

由于是share nothing的架构，当两个表需要进行join时，通常需要检查不同的segment server的元组是否满足条件，免不了需要在segment server移动数据。GreenPlum引入了一种叫Motion的算子来实现移动。Motion算子会通过网络来接发数据，Motion算子将查询计划切成不同的slice，在slice之间会做数据的分发，每个slice的执行都由一组特定的worker负责，这组进程就是gang。coordinator将查询计划分配个跨集群的进程组，不同的segment server生成不同的进程，都有相关的上下文信息。

如下图，顶部是一个join的分布式计划，下方则是在两个segment server集群的执行过程。在segment server上有两个slice，一个slice会扫描class表并通过redistributed Motion发送元组，两个slice则是从Motion节点接收元组，并扫描Student表执行hash join，将结果发送至顶部的coordinator。

Distributed Transaction Management

Greenplum通过分布式快照和2PC来确保ACID属性，在单个segment节点上，则是Postgres原生的事务机制。

Hybrid Storage and Optimizer

Greenplum支持三种表类型：PostgreSQL原生的heap表，行存储；还有就是两种新加入的，Append Optimized的行存储和列存储。AO表更有利于批量IO而不是heap表的随机访问模式，因此更适合AP的工作负载。特别是AO column表，可以用不同的压缩算法对不同的列进行压缩。Greenplum的查询引擎不敢直表的存储类型，同一个查询可以join不同的表类型。

表可以按用户指定的key和分区策略（list、Range）进行分区，其中每个分区可以是heap、AO-row、AO-column、甚至是外部表（比如AWS的S3）。以下图的销售表为例，每个分区由日期范围定义，从老到新分别是外部表、heap表和AO-column表。

至于优化器、Greenplum也提供两种选择（不是自适应的），分别是适合执行时间长的Orca和适合短查询Postgres原生的优化器。

OBJECT LOCK OPTIMIZATION

这一节主要讲的是锁优化，这是Greenplum增强OLTP性能的关键，着眼于解决分布式系统的全局死锁。

Locks in Greenplum

Greenplum有三种锁：spin锁、LW锁和对象锁。前两种用于保护读写共享内存的临界区，并遵循某些规则来避免死锁。这里主要关注的是操作表、元组或事务等数据库对象时的对象锁。

其锁级别如下，level越高，并发控制粒度更严格。

Global Deadlock Issue

在Greenplum中处理全局死锁时，DML语句的锁定级别非常重要：在分析阶段，事务会对表上锁；在执行阶段，则是用tuplelock。由于Greenplum会夸与多个segment server执行锁，很难避免全局死锁。如下图，在segment server0上，事务B等待事务A，而在segment server1上，事务A等待事务B。但本地的PostgreSQL却没有发现本地死锁。

更复杂的例子如下，包括协调者在内的所有segment server都导致了全局死锁。

在旧版本的Greenplum中，会在coordinator分析阶段，用X模式锁定目标表。因此对于执行写操作的事务来说，它们是以串行的方式运行，而且即便是更小不同元组也会串行运行，降低了OLTP的性能。

Global Deadlock Detection Algorithm

新版的Greenplum的全局死锁检查方法（GDD）如下：会在coordinator起一个守护进程，然后该进程会定期收集每个segment server上的Wait-for图，并检查是否发送全局死锁，然后用预定的策略终止全局的死锁。（比如终止最新的事务）

对于全局Wait-for图来说，事务就是顶点，其中输出边是顶点的出度，输入边数量则是入度。顶点的局部度是在某单个segment server的wait-for图中计算的值；顶点的全局度则是在所有segment server的所有局部度的总和。另外考虑收集Wait-for图的过程是异步的，因此在下检测结论的时候，需要判断下涉及的事务是否还存在。如果有事务结束了，则放弃本轮检测，等待下一个周期。

对于Wait-for图有两种类型的边，实边是指等待的锁只有在事务结束的时候才能释放，pg中大多数对象都是这个类型。如果等待的锁无需事务结束则可以释放，比如tuple lock，则对应虚边。

至于具体的检测方法如上图，是一种贪婪的算法，在每一轮的循环中：

首先会将全局出度为0的顶点对应的输入边删除掉，出度为0的事务没有等待任何锁，本身可以正常结束，对它的等待也不会导致死锁，这一步可以持续直到没有这种顶点；
接着关注局部graph，接着删除局部出度为0的点所对应的输入虚边删除掉。虚边本身依赖的是tuple lock，但因为没有局部出度，因此该依赖关系可以在事务执行完之前就结束了，可以直接删掉。

如果仍然存在无法消除的边，则认为死锁存在，此时再确认下之前的事务是否还存在。

下面就是一个具体的例子，上面一个图是全局和局部的Wait-for图，下图则是GDD算法执行过程。由于事务C没有全局出度，因此删除它和关联的边，变为(b)图。再看局部图，s1中A到B是一个虚边，并且B的局部出度为0，这条边也可以去掉，变成(c)图。再看全局图中B -> A的边，A没有全局出度了，可以继续消除而变为(d)。

DISTRIBUTED TRANSACTION MANAGEMENT

Greenplum的事务是由coordinator创建的，并将其分发到各个segment server中。coordinator为每个事务分配了一个单调递增的整数，作为分布式事务id。在每个局部segment上，根据分布式事务id也会利用原生的PG事务机制来生成本地事务标id。

Distributed Transaction Isolation

Greenplum利用了Postgres原生的snapshot机制来构建全局的分布式snapshot，可以应付分布式环境下的事务隔离。元组的可见性是由本地事务id和分布式事务id共同决定的。对于一个给定的事务，在修改一个元组时会给该元组创建一个新版本并打上局部事务ID，维护局部事务到分布式事务ID的映射。

考虑到维护本地事务ID映射分布式事务ID的开销较大，因此仅维护一个最大的分布式事务ID，和周期性地截断映射关系的元数据。

One-Phase Commit Protocol

一般来说，coordinator会使用2pc来保证事务在所有segment server上要么abort要么commit。至于这里说的一阶段优化，则是指如果事务只会修改单个segment上的数据，则可以省掉不必要的PREPARE过程。如下图，coordinator将跳过PREPARE阶段，直接把Commit命令分发至参与segment server上，节省掉一个网络来回的PREPARE消息：

还有进一步的优化，最后一个Query可以和Prepared/Commit消息合并，多节省一轮roundtrip。

RESOURCE ISOLATION

Greenplum还引入资源组的概念，考虑到TP和AP同时运行时，AP的工作负载会对TP产生极大的影响，通常前者会消耗大量的CPU、内存和IO带宽，并对后者的查询性能产生影响。目前Greenplum主要是实现了对CPU和memory的限制。

CPU的使用隔离是利用cgroup实现的，可以通过cpu.shares来控制着CPU的使用百分比或者优先级，也可以通过cpuset.cpus来指定资源组的cpu的核数。

内存的使用隔离则是基于内存管理模块Vmemtracker实现的，但由于想要显式控制内存的使用不是那么容易，引入了三个层次来管理内存使用情况：

slot memory：单个查询的内存使用情况，通过资源组的非共享内存除以并发数得出；
shared memory：在同一资源组中的查询超过slot memory时使用该层；
global shared memory：最后一层，前面的都限制不了时会使用这个配额；

CONCLUSION

论文主要讲了主要面向OLAP的数据库如何转换成一个HTAP系统，考虑到OLAP的工作负载会极大影响OLTP的性能，论文提出的方法如全局死锁检测器和1PC的提交协议会显著提高OLTP性能。另外就是通过资源组的使用，限制CPU和内存，保证了在单个系统中同时运行OLTP和OLAP工作负载不会有太大的影响。