存储引擎

摘要 本博客以循序渐进的方式，依次简要介绍PostgreSQL存储模块的各个子模块的基础功能，提及内容适合数据库内核初学者。本博客旨在介绍核心原理，以便于理解为首，部分内容可能不会100%准确与具体，针对每个提及的子模块，之后会分别单独写博客详细介绍 目录 摘要 目录 1 概述 1.1 PostgreSQL的使用流程 1.2 PostgreSQL的基础架构 1.3 PostgreSQL的功能场景 1.4 PostgreSQL存储模块的介绍流程 2 执行模块 3 存储模块 3.1 存储结构 (1) data_directory (2) oid (3) data-file (4) page (5) tuple 3.2 关键机制 (1) mvcc (2) delete 3.3 执行流程 (1) input (2) heapam (3) trancation (4) fsm (5) buffer (6) smgr (7) vfd (8) vm (9) wal (10) wal-buffer 3.4 关键进程 (1) bgwriter (2) walwriter (3) checkpointer (5) walsender (6) autovacuum 3.5 关键流程 (1) heap_insert (2) heap_delete (3) heap_update (4) heap_scan 3.6 辅助机制 (1) index (2) recovery (3) backup (4) toast (5) logical 1 概述 1.1 PostgreSQL的使用流程 本博客仅讨论存储模块的关键原理。简而言之，PostgreSQL将数据合理地组织并存储在磁盘上，并向用户提供SQL接口，让其读写磁盘上的指定数据。以下是PostgreSQL简单工作流程： ...

1 Page的概念 1.1 前置概念 首先，简单介绍一些基本概念： 关系 Relation：PostgreSQL是一款关系型数据库，在数据库中，1个表对应关系代数中的1个关系，即1个Relation。本博客中，将1个Relation指1个表 数据文件 RelFile：通过CREATE TABLE t1 (c1 INT, c2 TEXT)等语法创建1个表时，PostgreSQL会生成1个与表对应的数据文件，表中数据都将被存储至数据文件中 数据库页 Page：1个数据文件，由1个或多个大小为8192字节（即8k）的数据页组成 行 Row：在SQL语法INSERT INTO t1 VALUES (1, 'data1')中，(1, 'data1')是表中的1行数据 元组 Tuple：在PostgreSQL中，1个Tuple存储1行数据，数据越长，Tuple越长。1个Page可以存储多个Tuple 1.2 Page Page的格式如下：

接口 void smgrcreate(SMgrRelation reln, ForkNumber forknum, bool isRedo); // 创建文件 void smgrdounlink(SMgrRelation reln, bool isRedo); SMgrRelation smgropen(RelFileNode rnode, BackendId backend); void smgrclose(SMgrRelation reln); void smgrwrite(SMgrRelation reln, ForkNumber forknum, BlockNumber blocknum, char *buffer, bool skipFsync); void smgrread(SMgrRelation reln, ForkNumber forknum, BlockNumber blocknum, char *buffer); void smgrextend(SMgrRelation reln, ForkNumber forknum, BlockNumber blocknum, char *buffer, bool skipFsync); 调用关系 // 索引模块 btbuildempty() smgrwrite(metapage) _bt_blwritepage() smgrwrite() spgbuildempty() smgrwrite() |- FlushBuffer() ... |- FlushRelationBuffers() |- LocalBufferAlloc() smgrwrite() // FlushBuffer |- BufferAlloc() // readBuffer时，申请一个buffer，可能调用页面淘汰算法 |- FlushDatabaseBuffers() |- FlushRelationBuffers() |- FlushOneBuffer() FlushBuffer() // FlushOneBuffer XLogReadBufferForRedoExtended() FlushOneBuffer() // FlushRelationBuffers |- heap_sync() |- ATExecSetTableSpace() // ALTER TABLE SET TABLESPACE FlushRelationBuffers() // heap_sync when HEAP_INSERT_SKIP_WAL |- intorel_shutdown() |- CopyFrom() |- transientrel_shutdown() |- ATRewriteTable() heap_sync() // FlushDatabaseBuffers dbase_redo() FlushDatabaseBuffers() write时机： readBuffer时，如果buffer不在内存，且共享缓冲池已满，调用页面置换算法进行刷盘 alter table set table space copy

1 Buffer基本介绍 1.1 Buffer解决的问题 实际应用场景中，PostgreSQL可能需要1分钟处理数十万次事务，频繁读写Page。Buffer提供以下2个基本功能： 加载Page至内存：PostgreSQL需要读写数时，都需先从磁盘中，将指定的Page加载至内存中，再在内存中操作Page 缓存常用Page：Page被加载至内存后，还会在内存停留一段时间，降低PostgreSQL直接从磁盘读写Page的频率 1.2 Buffer的基本功能 Buffer缓存Page时，需考虑以下几个场景： 插入Page：大部分事务操作表的Page时，先从Buffer中查找Page，如果Page不在Buffer中，再从磁盘读取Page，将其放入Buffer中，再操作Buffer中的Page 查找Page：访问Page时，通过文件名和Page编号等信息可确定唯一Page 访问Page：所有事务均可访问Buffer，需考虑多事务并发读写同一Pape的场景 淘汰Page：Buffer能缓存的Page数量有限，在Page数量过多时，需淘汰一些Page 落盘Page：Buffer中通常缓存表数据文件的Page，前文提到，事务持久化的标志是WAL日志落盘，因此，Buffer中的Page无需实时落盘，仅需异步落盘即可 2 Buffer的基本原理 2.1 插入Page 插入Page主要由读Page操作触发，上层函数读取Page的主要流程如下： 上层模块统一调用ReadBuffer()接口，读取指定表的指定Page ReadBuffer()中，先从Buffer查找Page，如果找到Page，则直接返回Buffer中的Page 如果未从Buffer找到Page，现在Buffer中预留存储Page的空间 之后，调用Smgr模块，从磁盘读取指定Page，并将其放入预留的空间内，再返回Buffer中的Page 函数调用关系大概如下图所示： ReadBuffer(Relation, BlockNumber) # 1 ReadBufferExtended() ReadBuffer_common() BufferAlloc() # 2,3 查找Page，如找到，返回；如未找到，预留存储Page的空间 smgrread(.., BlockNumber) # 4 如果未找到Page，从磁盘将Page读入预留的Page空间内，返回 2.2 查找Page 上层函数读Page时，首先进入查找Page阶段。 1.1 buffer池模型 模型： 1.2 buffer池接口 缓冲区接口： /* bufmgr.h */ /* 1 buffer池管理 */ void InitBufferPool(void); void InitBufferPoolAccess(void); void InitBufferPoolBackend(void); /* 2 buffer管理 */ /* 2.1 读buffer */ Buffer ReadBuffer(Relation reln, BlockNumber blockNum); Buffer ReadBufferExtended(Relation reln, ForkNumber forkNum, BlockNumber blockNum, ReadBufferMode mode, BufferAccessStrategy strategy); Buffer ReadBufferWithoutRelcache(RelFileNode rnode, ForkNumber forkNum, BlockNumber blockNum,ReadBufferMode mode, BufferAccessStrategy strategy); /* 2.2 清理buffer */ oid ReleaseBuffer(Buffer buffer); void UnlockReleaseBuffer(Buffer buffer); void MarkBufferDirty(Buffer buffer); void IncrBufferRefCount(Buffer buffer); Buffer ReleaseAndReadBuffer(Buffer buffer, Relation relation, BlockNumber blockNum); /* 2.3 刷盘buffer */ void CheckPointBuffers(int flags); void FlushOneBuffer(Buffer buffer); void FlushRelationBuffers(Relation rel); void FlushDatabaseBuffers(Oid dbid); void BufmgrCommit(void); bool BgBufferSync(void); /* 2.4 删除关联buffer */ void DropRelFileNodeBuffers(RelFileNodeBackend rnode, ForkNumber forkNum, BlockNumber firstDelBlock); void DropRelFileNodesAllBuffers(RelFileNodeBackend *rnodes, int nnodes); void DropDatabaseBuffers(Oid dbid); /* 2.5 锁buffer */ void UnlockBuffers(void); void LockBuffer(Buffer buffer, int mode); bool ConditionalLockBuffer(Buffer buffer); void LockBufferForCleanup(Buffer buffer); bool ConditionalLockBufferForCleanup(Buffer buffer); bool HoldingBufferPinThatDelaysRecovery(void); 1.3 buffer调用 插入数据 ...

1 概述 1.1 思想 fsm结构 用数组表示完全二叉树 | 8 | | 4 | 8 | | 4 | 2 | 1 | 8 | 1.2 FSM涉及 物理页号 +-------+-------+-------+-------+-------+ FSMFile | 8k | 8k | 8k | 8k | ... | +-------+-------+-------+-------+-------+ FSMBlock | 0 | 1 | 2 | 3 | ... | +-------+-------+-------+-------+-------+ 逻辑页号 第2层：1个FSMBlock 第1层：4069个FSMBlock 第0层：4069 * 4069个FSMBlock，每个FSM可映射4069个DataBlock FSMAddress: [层次，页号]，页号即FSMBlock号 每个表最大容量是32T，只需3层也页面即可管理整个表的空闲空间 # [FSMAddress.level, FSMAddress.logpageno, FSMBlockNum（1个page即1个FSMBlock）] [2,0,0] | +---------------------------+---------------------------+ | | | [1,0,1] [1,1,1*4070+1] ... [1,4069,4069*4070+1] 本层共4069个FSMBlock | +----------+------------+ | | | [2,0,1+1] [2,1,1+2] ... [2,2,1+4069] ...... 本层共4069*4069个FSMBlock | （映射DataBlock 0 ~ 4065） 整体架构 3层FSMBlock [8] [8 0] [8 0 0 0] [...] [8 0 0 0 0 ...] [8] [8 0] [8 0 0 0] [...] [8 0 0 0 0 ...] [8] [8 0] [8 0 0 0] [...] [8 0 0 0 0 ...] 测试 ...

1 heamp的简介 前置知识：Relation的基本概念，Tuple的基本概念 1.1 heapam接口的功能 heapam是存储模块对上层提供的数据读写接口，这些接口通常是操作1个relation中的1个或多个tuple。 本文介绍以下4个最常用的接口，即如何向1个relation中写入、删除、更新、读取1个Tuple，接口定义如下： /* 向relatiion中写入1条tuple */ heap_insert(Relation relation, HeapTuple tup, ...) /* 从relation中删除1条tuple */ heap_delete(Relation relation, ItemPointer tid, ...) /* 在relation中，将旧tuple标记删除，并写入1个新tuple */ heap_update(Relation relation, ItemPointer otid, HeapTuple newtup, ...) /* 从relation中读取数据，每次读取1条数据 */ HeapScanDesc heap_beginscan(Relation relation, ...) HeapTuple heap_getnext(HeapScanDesc scan) 1.2 调用heapam接口 /* * 此处，以4个常见的SQL为例，介绍数据库如何调用heapam接口 * 1. INSERT INTO t1 VALUES (1, 'data1'); * 2. SELECT * FROM t1; * 3. DELETE FROM t1 WHERE c1 = 1; * 4. UPDATE t1 SET c2 = 'data2' WHERE c1 = 1; */ exec_simple_query("SQL语句") /* 该函数是所有SQL语句的统一处理入口 */ PortalRun() PortalRunMulti() ProcessQuery() ExecutorRun() standard_ExecutorRun() ExecutePlan() ExecProcNode() /* 从这里开始分叉，不同类型的SQL语句，由不同函数处理 */ ExecModifyTable() ExecInsert() /* 处理：INSERT INTO t1 VALUES (1, 'data1') */ heap_insert(relation, tuple, ..) 1.3 heapam接口的使用场景 实际应用场景中，数据库的存储模块需满足以下关键需求： ...

1 背景 1.1 数据检索 1 索引概述 1.1 概述 1.2 索引函数 1.2.1 调用索引函数 1.2.2 索引函数 2 索引实现 2.1 创建索引 ambuild 一、build整体流程 二、build插入tuple 2.2 索引写入数据 aminsert 3 operate 1 背景 1.1 数据检索 通常，应用会使用数据库存储大量数据，比如，单个表存储上百万、甚至上百亿条数据。此时，对表中数据进行某些查询时，将变得非常困难，比如等值查询、范围查询、模糊查询等。 1 索引概述 1.1 概述 索引方式：postgresql共有5种索引 唯一索引：不能出现重复的值 主键索引：主键自动创建唯一索引 多属性索引：多个列（最多32列） 部分索引：WHERE过滤索引 -- 示例 CREATE INDEX .. WHERE (c1 > 10); 表达式索引：和部分索引没太大区别，都是额外调用1个函数 -- 示例 CREATE INDEX .. WHERE (c1 = 10); 索引分类：postgresql有多种索引，本文见介绍以下4种 btree hash gist gin 索引系统表 pg_am：存储所有索引的方法 SELECT * FROM pg_am; amname | amhandler | amtype -------+-------------+-------- btree | bthandler | i hash | hashhandler | i gist | gisthandler | i gin | ginhandler | i spgist | spghandler | i brin | brinhandler | i pg_index：存储所有索引，索引列的下标 ...

1 概述 select reltuples,relhasoids,oid from pg_class where relname = 't1'; -- reltuples = 0 select pg_relation_filepath('t1'); -- oid = filepath = relfilenode vacuum full t1; select reltuples,relhasoids,oid from pg_class where relname = 't1'; -- oid 不变, reltuples = 0 -- oid != filepath = relfilenode != analyze t1; -- reltuples = 2，即有效tuple 启动autovacuum进程 standard_ProcessUtility(Node *parsetree) case T_VacuumStmt: ExecVacuum(VacuumStmt *vacstmt) vacuum(RangeVar *relation, Oid relid, VacuumParams *params) ServerLoop(void) StartAutoVacLauncher(void) AutoVacLauncherMain() /* if fail: 发送信号重启aotuvacuum进程 */ SendPostmasterSignal(PMSIGNAL_START_AUTOVAC_WORKER) sigusr1_handler(SIGNAL_ARGS) if CheckPostmasterSignal(PMSIGNAL_START_AUTOVAC_WORKER): StartAutovacuumWorker(void) Backend *bn = malloc(); bn->pid = StartAutoVacWorker(void) AutoVacWorkerMain(int argc, char *argv[])() BaseInit(); InitPostgres(NULL, dbid, NULL, InvalidOid, dbname) do_autovacuum() autovacuum_do_vac_analyze(autovac_table *tab) vacuum(RangeVar *relation, Oid relid, VacuumParams *params) proc_exit(0) dlist_push_head(&BackendList, &bn->elem) 查找所有待vacuum的表 do_autovacuum(void) /* table-by-table */ StartTransactionCommand() /* 查询pg_database系统表 */ tuple = SearchSysCache1(DATABASEOID) /* 打开pg_class系统表 */ classRel = heap_open(RelationRelationId) pg_class_desc = CreateTupleDescCopy(RelationGetDescr(classRel)) /* 为toast表创建hash表 */ table_toast_map = hash_create() /* 遍历pg_class系统表，记录所有需要vacuum和analyze的普通表和系统表 */ relScan = heap_beginscan_catalog(classRel) while tuple = heap_getnext(relScan) != NULL: Form_pg_class classForm = (Form_pg_class) GETSTRUCT(tuple) relid = HeapTupleGetOid(tuple) relopts = extract_autovac_opts(tuple, pg_class_desc) tabentry = get_pgstat_tabentry_relid(relid, classForm->relisshared) /* 检查表是否需要被vacuum和analyze */ relation_needs_vacanalyze(relid, relopts, classForm, tabentry, &dovacuum, &doanalyze) if dovacuum || doanalyze: /* 普通表加入list中 */ table_oids = lappend_oid(table_oids, relid) /* toast表加入hash表中 */ if OidIsValid(classForm->reltoastrelid): hentry = hash_search(table_toast_map, &classForm->reltoastrelid, HASH_ENTER) hentry->ar_relid = relid eap_endscan(relScan) /* 第二次遍历pg_class系统表 */ relScan = heap_beginscan_catalog(classRel) while tuple = heap_getnext(relScan) != NULL: Form_pg_class classForm = (Form_pg_class) GETSTRUCT(tuple) relid = HeapTupleGetOid(tuple) relopts = extract_autovac_opts(tuple, pg_class_desc) ... bstrategy = GetAccessStrategy(BAS_VACUUM) /* 开始遍历所有list中的表 */ foreach(cell, table_oids) Oid relid = lfirst_oid(cell) /* 再次检查是否仍需vacuum */ tab = table_recheck_autovac(relid, table_toast_map, pg_class_desc) if tab == NULL: continue MyWorkerInfo->wi_tableoid = relid autovac_balance_cost() AutoVacuumUpdateDelay() autovacuum_do_vac_analyze(tab, bstrategy) vac_update_datfrozenxid() CommitTransactionCommand() 对单个表进行vacuum ...

假设集群里已经存在表级透明加密模块，在此基础上设计一个高性能、高易用性的 WAL 加密模块。 WAL 加密的难点几乎不在"加密"本身，而在两件事：同一个 8KB 页会被反复重写，以及恢复路径要在拿不到 catalog 的时候就能解密。下面按设计决策的顺序展开。 1 威胁模型 先划清边界，因为它直接决定后面几个取舍。 要防的：磁盘 / 备份 / 归档介质被拖走；DBA 之外的运维人员直接读 pg_wal/；WAL 归档到对象存储。 不防的：有 root 权限的在线攻击者（内存里必然有明文）、旁路攻击。 1.1 为什么不用 dm-crypt 了事 如果只是防"介质丢失"，块设备加密（LUKS/dm-crypt）性价比高得多。在数据库内核里做 WAL 加密，真正的理由只有三个： 密钥要由数据库自己管，不能落在 OS 层（密评 / 国测要求）； 归档件要天然带密； 和已有的表级 TDE 共用一套密钥体系。 设计要始终对齐这三个理由，否则很容易做成一个又慢、又没多大意义的模块。 1.2 FPI 是必须堵的洞 既然表级 TDE 已经存在，那么 FPI（full page image）就是个必堵的泄漏点。 如果 TDE 是在 smgr 层做的（缓冲区里是明文、写盘时加密），那么 WAL 里的 FPI 记录的是明文页 —— 加密表的数据会原封不动地漏进 WAL。 只要集群里存在任何一张加密表，WAL 加密就必须强制开启，不能是两个独立开关。 实现上做成一个集群级的 data_encryption = on，或者至少让 CREATE ENCRYPTION POLICY 在 WAL 加密未开启时直接报错。这是易用性设计里最重要的一条：不要把一个"配错了就静默泄密"的组合留给用户。 ...