search

mrdrivingduck / paper-outline

🔍 To record the papers I have read.
24 stars 0 forks source link

Greenplum: A Hybrid Database for Transactional and Analytical Workloads #2

Open mrdrivingduck opened 3 years ago

mrdrivingduck commented 3 years ago

PDF: 2103.11080.pdf

Related publications:

mrdrivingduck commented 3 years ago

4 Object Lock Optimization

GP 如何优化数据库内的对象锁，并解决 全局死锁 问题。

mrdrivingduck commented 3 years ago

4.1 Locks in Greenplum

GP 中三种类型的锁：

其中自旋锁和轻量锁用于在读写共享内存时保护临界区内的数据，且遵循特定的锁获取规则 (比如按相同顺序获取锁)，因此不会发生死锁。对象锁直接影响并发操作数据库对象，并且有可能发生死锁。

GP 采用两阶段锁定 (2PL, two-phase locking)：第一阶段获得锁，第二阶段释放锁。并继承了 PostgreSQL 中的 8 种 lock mode。由于 GP 的 MPP (Massive Parallel Processing) 分布式特性，GP 中会出现单机 PG 不会出现的 全局死锁 问题。在早期版本的 GP 中，是通过提升 DML 操作的锁等级，使事务串行执行，从而避免这个问题。这种处理方式的并发性能很差。

mrdrivingduck commented 3 years ago

4.2 Global Deadlock Issue

在分布式系统中，INSERT / DELETE / UPDATE 三条 DML 的锁定行为：

  1. 解析分析阶段，事务对目标关系加锁
  2. 执行阶段，事务使用事务锁对元组加锁

在单机 PG 中，第一阶段的加锁通常使用 RowExclusive，因此多个事务可以并发操作同一个元组，除非两个事务 写 同一个元组，此时两个事务将会串行化等待。锁信息保存在实例的共享内存中，如果死锁发生，可以直接扫描共享内存中的锁信息，检测并打破死锁。

image

在 GP 的分布式架构中，上述方法无法处理跨实例的全局死锁。在 GP 5 及更早版本之前，上述第一阶段加锁的 lock mode 通常被升级为 Exclusive，从而使得 UPDATE / DELETE 实际上在串行执行，因此节点上不会出现对事务锁的等待。这将导致无法并发写入一个关系，即使写入的元组不同，从而引发很差的 OLTP 性能。

mrdrivingduck commented 3 years ago

4.3 Global Deadlock Detection Algorithm

GP 6 引入了 GDD 算法。工作过程：

  1. GP 在 master 上启动一个守护进程
  2. 守护进程周期性向每个 segment 采集信息，构造 wait-for graph
  3. 守护进程检查是否存在全局死锁
  4. 如果存在全局死锁，终结最年轻的事务

该算法被要求既正确又完全。GDD 守护进程采集每个 segment 的本地 wait-for graph，构造全局 wait-for graph。图中每个顶点代表一个 事物，边从等待锁的事务顶点指向持有锁的事务顶点。从各 segment 采集 wait-for graph 的过程是异步的。

图中的边分为两种类型：

所以算法的过程很直接，是一个死循环，循环体内：

  1. 如果一个顶点的全局出度为 0，移除所有直接指向该顶点的边
  2. 如果一个顶点的本地出度为 0，移除所有直接指向该顶点的 dotted edges
  3. 如果没有移除发生，循环结束

如果算法结束后，图内已经没有边，那么说明没有发生全局死锁。根据边的移除规则，算法一定会收敛到使图不可再改变的时候。此时，如果图中还有剩余边，那么一定存在环路 (如果没有环路，那么根据移除规则，边肯定都会被移除)。

GDD 启用后，DML 的锁等级下降，对相同关系进行更新或删除的事务可以并行执行。GDD 守护进程只会周期性地从各个 segment 上 fetch wait-for graphs，因此不会消耗 GP 集群中的很多资源。

mrdrivingduck commented 3 years ago

3 GreenPlum's MPP Architecture

GP 采用 大规模并行处理 (Massiely Parallel Processing) 架构，面向 HTAP (Hybrid Transactional and Analytical Processing) 场景设计。其架构设计解决了单机数据库的以下局限：

mrdrivingduck commented 3 years ago

3.1 Roles and Responsibility of Segments

GP 集群包含跨多个域的多个 segment。只有一个 segment 被称为 coordinator segment，其它就只是普通的 segment。Coordinator 接收查询并产生分布式计划，并分发到多个进程上执行，然后收集结果并返回；segments 作为实际保存用户表数据的地方。为了保证高可用，一些 segment 被配置为 standby，即 coordinator 的镜像：不直接参与计算，而是不断接收并重放 WAL。

GP 采用 share-nothing 架构，coordinator 和 segment 有着自己的内存及数据目录。节点之间使用网络通信。

image

mrdrivingduck commented 3 years ago

3.2 Distributed Plan and Distributed Executor

对于分布式的表，每个 segment 只存储表中一部分的数据。当对两个表进行 join 时，通常需要检查两个来自不同 segment 的元组是否满足 join 条件。这意味着 GP 需要在 segment 之间移动数据，保证满足 join 条件的元组在一个 segment 上。GP 提出 Motion 计划节点来实现数据移动。

Motion 节点使用网络在不同 segment 之间收发数据。计划树在 motion 节点被切成上下两个部分，上下两个部分分别被称为一个 slice。每一个 slice 都会被一组分布在不同 segment 上的进程执行，每组进程分别被称为一个 gang。

有了 motion 节点，GP 的查询计划和执行器自然而然就成了分布式的。查询计划被分发到每个进程上，每个进程执行自己的 slice 并完成查询。根据数据收发方式的不同，motion 算子被分为：

这篇文章 很形象地解释了 motion 算子。

image

mrdrivingduck commented 3 years ago

3.3 Distributed Transaction Management

GP 集群中的每一个节点都运行着一个加强版的 PG，一个事务的提交或中止需要在所有节点上保持同步。GP 使用 分布式快照 和两阶段提交 协议。

mrdrivingduck commented 3 years ago

3.4 Hybrid Storage and Optimizer

GP 支持 PostgreSQL 原生的面向行的 heap table，另外还支持：

AO (Append Optimized) 表支持使用不同算法进行压缩。GP 的执行引擎可以在同一个查询中 join 上述三种存储类型的表。