search

mrdrivingduck / paper-outline

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

Database System Concepts (Seventh Edition) - Chapter 32 - PostgreSQL #5

Open mrdrivingduck opened 2 years ago

mrdrivingduck commented 2 years ago

Chapter 32 为 这本书 的网上章节，详细介绍了 PostgreSQL 的技术细节，甚至还介绍了一些内核代码 😁。对这个章节进行学习能够很快建立 PostgreSQL 的世界观。

PostgreSQL 由 UC Berkeley 的 Michael StoneBraker 教授开发的 POSTGRES 系统发展而来。目前，PostgreSQL 支持：

用户可以使用新的数据类型、函数、运算符、索引来扩展 PostgreSQL。

PostgreSQL 支持大量编程语言 (接口)，也支持 JDBC/ODBC 等数据库接口。PostgreSQL 能够运行在所有类 Unix 操作系统下。

mrdrivingduck commented 2 years ago

32.1 Interacting with PostgreSQL

32.1.1 Interactive Terminal Interfaces

PostgreSQL 内置提供了 psql 作为命令行工具，是用户能够与 PostgreSQL 进行交互：

32.1.2 Graphical Interfaces

PostgreSQL 自己本身不带图形接口，但是有很多开源或商业的图形界面。

32.1.3 Programming Language Interfaces

PostgreSQL 提供两套客户端接口：

mrdrivingduck commented 2 years ago

32.2 System Architecture

多进程 架构。PostMaster 是中央协调进程，负责系统初始化：

也负责系统关闭。另外，还管理与客户端的连接：为每一个新连接的客户端分配一个 backend server 进程。因此 postmaster 进程需要不断监听端口。PostgreSQL 是一个 process-per-connection 模型。

除了 postmaster 和负责对接客户端的 backend server 进程以外，PostgreSQL 还有一些后台工作进程：

在内存管理上，分为进程 local memory 和 shared memory。内存中的 buffer pool 被放置在共享内存中，同时需要被多个进程共享的 lock 等信息也会放在共享内存里。由于使用共享内存，因此 PostgreSQL 只能运行在单机上，如果没有第三方的支持。但是现在很多 PostgreSQL 都被构建为 shared-nothing 的并行数据库。

mrdrivingduck commented 2 years ago

32.3 Storage and Indexing

PostgreSQL 依赖于文件系统的文件作为存储，而不是直接使用物理磁盘分区上的 raw 数据。PostgreSQL 维护了一堆 目录 用于存放文件，这些目录被称为 tablespace。每个 PostgreSQL 安装完都会被初始化一个 default tablespace。

这种存储系统的设计导致了一些性能局限 - double buffering。文件块首先被操作系统读取到内核空间的文件系统缓存中，然后再被拷贝到 PostgreSQL 共享内存的 buffer pool 中。另一个局限是 PostgreSQL 的 block 是 8KB 的，与 OS 内核的 block 大小不一致。

但是现在很多企业都使用了外部存储系统，这种存储系统的性能优化独立于数据库，因此 PostgreSQL 可以直接享受这些系统带来的性能提升。

32.3.1 Tables

在 PG 中，表内的元组被存放在所谓 heap file 中。其格式是一个 page header，后续跟上一个数组的 line pointer。Line pointer 中包含元组在 page 内的 offset 和长度。实际的元组从 page 的结尾处开始倒序存放：

image

Heap file 中的每一个记录都由 tuple ID (TID) 标识：

由于 MVCC 的存在，表中可能会有同一个 tuple 的多个版本，每个元组都有其有效的开始时间和结束时间。删除操作不会立刻删除元组，而是更新元组的结束时间；更新操作不会修改一个元组，而是将旧版本的元组复制一份，旧版本的结束时间被设置为小于新版本的开始时间。无法被任何事务可见的旧元组会在之后被彻底删除，从而引发 page 中有洞。可以对 tuple 进行压实，从而腾出一些空间，同时不影响元组的 TID 值。

物理元组的长度由 page 的大小决定，PG 是无法跨页存储元组的。对于大元组，PG 提供 TOAST 机制，对元组进行压缩，并切分存储到专门的位置。如果压缩后还是存不下，存储在 toast 属性中的数据将会变为只想外部关联 toast 表的指针；在 toast 表中，元组将会被切分为小块 (一页至少能放四块)，每块都是独立的一行。

32.3.2 Indices

PG 中的所有索引类型也是用 slotted-page 格式。

32.3.2.1 Index Types

32.3.2.2 Other Index Variations

32.3.2.3 Index Construction

  1. 扫描目标 relation 目前可见的元组
  2. 根据索引列排序
  3. 构建索引结构

这个过程中可能会有并发的元组更新。因此创建索引的过程中会上锁防止一切对元组的更新，这会导致表无法并发更新。create index concurrently 支持创建索引时允许表被并发更新，它将会扫描基表两次：

  1. 第一次扫描，构建初始版本的索引
  2. 第二次扫描，插入所有依旧需要被索引的元组，同时与其它事务同步，保证并发更新的元组也被插入到了索引中

32.3.2.4 Index-Only Scans

只使用索引就可以返回结果，不需要回表。因为 PG 中的索引都是 二级索引，与堆表存放在不同的文件中。如果想要执行 index-only scan，那么查询中只能引用索引中存在的列，且索引类型需要能够支持 index-only scan；或者可以用到 covering indices。

在 PG 中，使用 index-only scan 并不能保证不需要回表，因为 PG 中的元组是多版本的，索引中包含的数据可能对于执行扫描的事务来说不可见。元组的可见性信息存放在堆表中，因此需要进行表扫描得到元组的可见信息。PG 提供了一种优化：对于每一个堆表，维护一个 visiability map (每个 page 只占两 bit，I/O 很小)，追踪每一个页中的元组是否对所有事务可见：

如果页内的元组对所有事务都可见，那么 index-only scan 就不必访问堆表来判断元组是否可见了；否则 index-only scan 需要访问一下堆表，从而退化为 index scan。

32.3.3 Partitioning

分区表能够在查询包含分区列时提高性能，能够只扫描一个或一小部分分区，同时也可以减少批量加载和删除的开销。分区表也使 vacuum 或 reindex 等维护性操作更快。分区表上的索引也比全局索引更小，从而能够 fit in memory。分区类型：

分区表可以通过 表继承 或 显式分区声明 实现。不支持外键引用、不支持将一个已有的表转换为分区表，以及反向操作。

mrdrivingduck commented 2 years ago

32.4 Query Processing and Optimization

32.4.1 Query Rewrite

规则重写。比如视图，将会根据视图定义把视图查询转换为 select 查询。规则全部被保存在 catalog 中。重写首先处理 update/delete/insert，最终处理 select。可能需要重复或递归处理，直到没有任何规则可以被应用为止。

32.4.2 Query Planning and Optimization

每一个 block 都被视为一个隔离的部分产生 plan，顺序为从底向上，从重写后的计划的最里面的子查询开始进行。PG 的优化器大部分是基于代价的，代价模型的输入为 I/O 开销和 CPU 开销。查询的优化可以通过以下两种途径进行：

优化的结果是一个 query plan，是一棵关系代数运算符节点的树，节点可以是一元/二元/n 元的。

代价模型的核心是准确估算每一个运算符节点需要处理的元组数量，估算基于每一个 relation 上的统计信息来进行：

DBA 需要周期性地运行 analyze 来保持统计信息的有效性。

32.4.3 Query Executor

执行器基于 demand-driven 的流水线模型，每个运算符节点都需要实现迭代器接口：

一些重要概念：

32.4.4 Parallel Query Support

利用多 CPU 核心完成查询。由优化器负责决定是否使用并行，以及并行进程的数量。在 PG 11 中，只有 只读查询 可以使用并行。

当使用并行时，backend 进程负责协调：

并行查询计划包含以下两种节点，它们都只会有一个孩子节点：

协调进程和工作进程通过共享内存区来进行通信。

并行支持的操作：

32.4.5 Triggers and Constraints

触发器和约束不是在 rewrite 阶段实现，而是在执行器中实现的。

32.4.6 Just-In-Time (JIT) Compilation

在对元组进行选择运算和投影元算时，实际上是通过解释执行的方式实现的。对于 JIT 来说，可以根据运行时的元组数据类型，直接把函数编译为 native code。在 PG 11 中，使用 JIT 来处理 表达式验证 和 tuple deforming (元组的磁盘表示转换为内存表示) 的工作，因为它们都是 per-tuple 的操作，会很频繁。

JIT 对于长时间占用 CPU 的查询较有优势。在优化器中，根据代价估算以及一些阈值决定是否启用 JIT。PG 使用 LLVM 实现 JIT，以动态链接的方式按需加载。PG 11 中默认不开启。

mrdrivingduck commented 2 years ago

32.5 Transaction Management in PostgreSQL

PostgreSQL 的事务管理同时使用以下两种协议：

32.5.1 Concurrency Control

32.5.1.1 Isolation Levels

SQL 标准定义了三种等级的弱一致性，以允许更高的并发。应用可以根据需要选择一些非最强保证。SQL 标准根据违反串行化的现象来定义 隔离级别：

PG 用户可以使用四种隔离级别中的任意一种，但是 PG 实际上只实现了三种隔离级别 (后三种)，默认隔离级别为 Read Committed。

32.5.1.2 Concurrency Control for DML Commands

快照隔离的具体实现：多版本并发控制 (MVCC)。核心思想：在同一时间维护每一行的不同版本。在执行命令之前，事务只会选择：

MVCC 带来的特性是：读不阻塞写，写不阻塞读。冲突只有可能发生在两个 writer 更新同一行时。光有快照隔离并不能满足串行化。使用 SSI (Serilizable Snapshot Isolation) 可以在保留快照隔离的性能优势的同时，保证串行化。在运行时，SSI 会检测并发事务之间的冲突，并在错误发生时回滚事务。

32.5.1.3 Implementation of MVCC

MVCC 的核心是 元组可见性。对于事务 T 来说，元组可见的必要条件为：

  1. 在事务 T 获取其快照前，创建元组的事务已经 commit
  2. 对元组进行更新的事务 (如果有) 回滚 (修改撤销) / 在 T 获取快照之后开始运行 (未开始) / 当 T 获取快照时处于 active 状态 (未提交)

这两个条件确保每个事务看到的是一致的数据。PostgreSQL 维护了以下状态信息来高效检查元组的可见性：

有这些数据后，元组可见的条件可以被改写为：

  1. 元组的 xmin 需要同时满足：
    • 在 pg_xact 中该事务已提交
    • 小于当前事务的 SnapshotData 中的 xmax
    • 不是 SnapshotData 中的活跃事务
  2. 元组的 xmax (如果有) 需要满足以下之一：
    • 在 pg_xact 中该事务已回滚
    • 大于等于 SnapshotData 中的 xmax
    • 是 SnapshotData 中的活跃事务之一

对于 insert 语句，插入一条元组，并将元组的 xmin 初始化为当前事务 id - 这个过程不需要任何并发控制协议，除非 insert 需要检查约束；对于 delete，主要操作时更新元组的 xmax 为当前事务 id；对于 update，除了这一步，还需要创建一个新元组并初始化 xmin 为当前事务 id，并将旧元组的 forward-link 指向新元组。

对于 select/update/delete 来说，需要使用 MVCC 协议，SnapshotData 的获取时机由隔离级别决定：

对于 read committed 下的 update/delete 来说，事务开始时，元组可能已经被其它正在进行的事务更新，那么就需要等待其它事务的结束：

对于 serializable 下的 update/delete 来说，如果其它事务提交，那么将无法保证串行化，当前等待事务将会回滚报错。另外，为了解决幻读，SSI 使用了 谓词锁。

32.5.1.4 Implications of Using MVCC

存储多版本的行可能导致额外的存储开销。一个行版本可以被删除，当且仅当它无法被任何事务可见。元组的删除是由 vacuum 机制实现的。PG 使用了一个后台进程自动对表进行 vacuum：

可以通过同一个页面的死元组指向活元组的优化，避免修改索引。

Vacuum 的两种模式：

MVCC 更适合读比写多的场合；两阶段锁定更适合写较多的场景。

32.5.1.5 DDL Concurrency Control

MVCC 无法阻拦一些需要独占表的操作。DDL 遵从严格的两阶段锁定协议来对表上锁。DML 一般使用最低级的三种表级锁，这三种锁互相兼容，因为 MVCC 能够实现这些操作的互相保护。

锁被实现在共享内存中的一个 hash 表中，key 为被锁定对象的签名。如果一个事务想要对另一个事务已经上锁的对象上锁，则需要等待。锁等待是由信号量实现的，每个事务与一个信号量相关联。因此锁等待的实现模式是 per-lock-holder 而不是 per-lock-object。每个事务对应一个信号量，而不是每个锁对象对应一个信号量。

32.5.1.6 Locking and Indices

索引使用 page-level 的共享/排他锁，在索引行被读写后立刻释放；另外 hash 索引使用 bucket-level 的共享/排他锁，在整个 bucket 被处理完毕后立刻释放。

32.5.2 Recovery

PostgreSQL 使用基于 WAL 的恢复来保证原子性和持久性。在 PG 中，恢复不需要做 undo，只需要在 pg_xact 中更新事务状态，就可以使这个事务更新的元组不被其它事务可见。唯一可能发生问题的情况是进程发生了 crash，那么它没有机会更新 pg_xact 中的事务状态。PG 的解决方法是在查看 pg_xact 时，判断事务是否在任意一个进程上运行：如果没有，那么说明执行该事务的进程可能已经 crash，将该事务的状态更新为 aborted。

32.5.3 High Availability and Replication

PG 的 HA 集群是通过 WAL 回放实现的。一台机器处于归档模式，另一台机器处于恢复模式。PG 实现了基于文件的日志迁移，虽然性能开销很低，但是可能存在数据丢失的时间窗口。可以通过设置归档周期，强制使归档中的 PG 切换新的 WAL 文件。

流复制能够使备份机器更加 up to date。不需要等待 WAL 文件被写满，就可以异步 (by default) 将操作发送到备份库上。同步备份也是支持的，主库需要等待备库把 WAL 写到磁盘上后，才可以继续下一个操作。这样提升了数据可靠性，但是吞吐量可能会下降。

除了物理备份，PG 还支持逻辑备份。逻辑备份保存逻辑修改操作，而不是物理操作。逻辑备份使用 发布-订阅 模式，主要用于不同平台、不同版本的 PG 数据库之间。

mrdrivingduck commented 2 years ago

32.6 SQL Variations and Extensions

32.6.1 PostgreSQL Types

PG 具有对一些非标准类型的支持，也支持通过 create type 命令创建类型。

一些开源贡献的扩展类型：

32.6.2 Extensibility

PG 将数据库、表、列等信息全部存放在 system catalog 中。其它数据库需要修改硬编码的源代码来扩展新类型，而 PG 只需要向 catalog 中添加行即可。数据类型、函数、access method 等信息也全部存放在 catalog 中。内置类型和扩展类型的唯一区别是：内置类型已经链接在 backend 中，并且被提前注册在了 system catalog 里；而扩展类型则需要被手动注册，动态加载并链接到 backend。

32.6.2.1 Types

组合类型类似表定义的方式，定义好 C 结构体，定义好读写该类型的 C 函数，然后注册到 catalog 中。

32.6.2.2 Functions

PG 支持函数重载。函数可以使用 SQL 实现，或者其它过程语言，或者 C 语言。

32.6.2.3 Index Extensions

添加索引扩展需要提供运算符的定义：

32.6.2.4 Procedural Languages

PL/pgSQL、PL/Tcl、PL/Perl、PL/Python。

mrdrivingduck commented 2 years ago

32.7 Foreign Data Wrappers

FDW 允许用户连接外部数据源，但可以像数据在数据库内部一样使用。FDW 允许 PG 访问其它关系型数据库、KV 数据库、文件，但大部分扩展都不被 PG 官方支持。PG 官方支持的 FDW 模块有：

mrdrivingduck commented 2 years ago

32.8 PostgreSQL Internals for Developers

32.8.1 Installation From Source Code

32.8.2 Code Organization

后端代码组织：

32.8.3 System Catalogs

扩展功能可以被优雅地实现为向 pg_* 表中插入条目。

32.8.4 The Region-Based Memory Manager

实现了层次化的 memory context，一次调用就可以释放特定 memory context 中所有的对象。这样不仅更加高效，还可以避免内存泄漏的问题。

常见的 memory context 有：

Memory context 的基本操作：

其中 reset/delete 将会自动 reset/delete 所有 children memory context。

32.8.5 Node Structure and Node Functions

PG 使用了支持 单继承 的对象系统。所有节点的基类：

typedef struct {
    NodeTag type;
} Node;

所有节点都需要把 Node 放在结构体定义的第一位，这样就有了类似继承的效果。

任何节点类型都可以通过指针类型强制转换得到一个 Node * 指针，并能够访问到节点类型。而将基类指针转换为子类指针则需要经过运行时判断 - castNode 会对 NodeTag 进行判断决定是否可以转换；或者在调用 IsA() 之后直接进行转换。

32.8.6 Datum

Datum 是用来存放内部表示的通用数据类型，可以存放值，也可以存放指针。使用 Datum 的代码必须知道它的数据类型，因为 Datum 本身只存放值。内核里提供了很多基本数据类型和 Datum 相互转换的宏。

32.8.7 Tuple

一个 tuple 包含一系列的 Datum。HeapTupleData 是指向元组的内存数据结构，其中包含了元组的长度，以及指向 tuple header 的指针。该指针有如下几种指向元组的方式：

MinimalTuple 是 HeapTuple 的一种替代表示，用于在执行器内部转移元组，其中的一些事务状态信息已经不需要了。这样可以为每个元组省下一些空间。

PG 开发者推荐使用 TupleTableSlot 来访问各种元组，它屏蔽了 tuple 指针指向哪里的细节。

32.8.8 Query Execution Stack

32.8.8.1 Memory Management and Context Switches

ExecutorStart()
    CreateExecutorState()：创建 per-query 的 memory context
    (swith to per-query memory context)
    InitPlan()
        ExecInitNode()
            CreateExprContext()：创建 per-tuple 的 memory context
            ExecInitExpr()
ExecutorRun()
    ExecutePlan()
        ExecProcNode()
            ExecEvalExpr()：在 per-tuple 的 memory context 中调用
            ResetExprContext()：释放 per-tuple 的 memory context
ExecutorFinish()
ExecutorEnd()
    ExecEndPlan()
        ExecEndNode()
    FreeExecutorState()：释放 per-query 的 memory context 及其 child contexts

32.8.9 Error Handling

32.8.10 Tips For Adding New Functionality

如果想要添加新功能，最好的方法是看看类似的系统函数是如何实现的。鼓励使用内核中已经实现的 API 和数据结构：