1.引入
PostgreSQL是一款開源關系型數據庫，起源於1986年加州大學伯克利分校的”POSTGRES“項目。依托20多年的社區發展，PostgreSQL逐漸發展成一個高度穩定、功能強大的數據庫管理系統。與Postgres同類型的數據庫中，較知名的有閉源的Oracle，以及同樣開源的mysql。有趣的是，PostgreSQL和Mysql分別自稱為“最先進的“和”最受歡迎的“開源關系型數據庫。雖然這隻是宣傳語，但可以從中看出，PG是以穩定可靠、功能強大為主要賣點的。
PG內核涉及的范圍很廣，包括但不限於存儲、查詢、事務、故障恢復、復制等領域，本文主要聚焦於PG的存儲方面。在理論方面，本文將分析PG的存儲格式，以及與存儲相關的機制。在實踐方面，本文將舉例說明：(1)如何快速上手PG(2)如何利用pageinspect擴展，分析數據頁的具體細節。
2.Postgres存儲
2.1 PG存儲架構
下圖是PG的邏輯存儲結構，一個數據庫集群由多個數據庫對象構成，每個數據庫對象有各自的oid(object identifiers)。每個數據庫有各自oid命名的目錄，統一存放在$PG_DATA/base下，每個數據庫由表文件、索引文件和其他文件（視圖、函數、序列）構成。
- 數據庫集群 – database cluster
也叫數據庫集簇。它是指有單個PostgreSQL服務器實例管理的數據庫集合，組成數據庫集群的這些數據庫使用相同的全局配置文件和監聽端口、共用進程和內存結構。
- 數據庫 – database
在PostgreSQL中，數據庫本身也是數據庫對象，並且在邏輯上彼此分離，其他數據庫對象（例如：表、索引等等）都屬於他們各自的數據庫。
- 表空間 – tablespace
數據庫在邏輯上分成多個存儲單元，稱作表空間。默認情況下，PG將用戶數據存儲在base目錄，表空間為pg_default。如果創建一個新的表空間，會在$PG_DATA目錄下新建一個目錄，與base目錄隔離。
- 表 – table
表主要分為用戶表和系統表。
用戶表(user table)通過CREATE TABLE創建，下文將介紹具體格式。
系統表(system catalog)是pg_* 格式(pg_class,pg_attribute…..)的表，存放schema、系統狀態和統計信息等。需要註意，另一類pg_*格式的，可以通過select查詢到的“表”並不屬於系統表，而是系統視圖(system view)，它們隻是方便用戶查詢系統表和PG Server內部信息的快速路徑，沒有實際的數據文件。詳細可以參考 https://www.postgresql.org/docs/11/catalogs.html
2.2 PG存儲格式
關系型數據庫的存儲格式分為三個部分：
(1)文件存儲：數據存儲在磁盤文件中，由storage manager負責管理這些文件。
(2)頁面佈局：頁面是數據庫存儲數據的最小單位。本文主要介紹PG頁面結構的細節。
(3)元組佈局：數據庫事務的存在，決定瞭元組不僅僅包含數據部分，還需要記錄額外信息。對於這個問題，各個數據庫的實現細節各不相同。
下面分別展開介紹。
2.2.1 文件存儲
數據庫文件組織方式是指在數據庫中存儲數據的方式，它包括如何組織數據文件、索引文件和日志文件。常見的文件組織方式包括：堆文件(heap file)組織、順序文件(sequential file)組織、哈希文件組織、索引文件組織等。
PG采用堆文件組織方式，如下圖所示，每個文件由固定大小(8KB)的頁面構成，新寫入的數據以append的形式追加到堆文件末尾，當頁寫滿時創建一個新頁繼續寫入，每個頁由block id唯一標識。堆文件組織的優勢在於寫入性能較好，插入數據時不需要進行排序和重組。但由於堆文件數據無序的特性，查詢需要借助索引定位到數據的準確位置。
磁盤文件的更新不是實時的，寫操作會先修改內存中的Buffer Page，並標記為臟頁。事務提交時隻規定要將WAL日志落盤，不需要落盤buffer page。buffer page的刷臟是由PG的checkpointer進程或background writer進程進行的。具體細節見PG事務部分。
2.2.2 頁面佈局
PG的頁面包含以下內容：
- Header Data：存儲頁面相關的事務、版本、校驗信息。
- line pointers：即下圖中的ItemId，充當指針的作用指向heap tuple。
- heap tuple：即下圖中的Item，存放實際數據以及相關的事務信息。查詢時走索引找到line pointers，再指向對應數據。
- free space：註意到line pointer是從前往後插入的，而heap tuple是從文件末尾從後向前插入的，二者之間的空間就是free space。
這裡有兩個問題需要解釋。
Q1：為什麼指針從前向後存放，而tuple從後向前存放？
A1：數據不是定長的，因此無法知道一個頁面能容納多少tuple。如果指針和數據同樣采取順序存放，無法通過計算得到第一個tuple開始的位置。而采用上圖中的方式，不會造成空間浪費，指針和tuple邊界相交就說明頁面寫滿。
Q2：為什麼是通過索引找到指針，再由指針指向數據？索引中不能直接存放數據的位置嗎？
A2：MVCC的機制會產生數據的多個版本，同一數據的多個版本通過版本鏈連接，查詢時通過索引找到Head，然後遍歷版本鏈找到對於當前事務可見的版本。在PG存儲引擎下，多個版本數據同時存在於頁面中，會造成數據膨脹，需要由垃圾回收進程（PG中稱為vacuum）清理過時的數據，這會導致鏈表頭發生變化。如果我們在索引中直接存放數據位置，那麼清理時還需要修改索引值。相反，如果索引存放指針id，隻要在清理時修改指針的值，無需訪問索引。
下面(a)(b)兩張圖分別對應兩種索引管理方式，PG使用的就是邏輯指針方式。
2.2.3 元組佈局
如下圖，PG tuple由三部分構成：HeaderData、NULL bitmap、User data。
這裡主要關註HeaderData，這部分數據記錄瞭數據行的事務信息。各個字段的含義可以參考另一篇講PG並發控制的文章：https://zhuanlan.zhihu.com/p/535457521。
上文提到的版本鏈在PG中是通過tid字段(t_ctid)實現的。tid是由block id和pointer offset構成的一個pair，block id表示存放元組的頁序號，pointer offset表示指向元組的行指針偏移量，通過t_ctid可以確定數據的具體位置。對某一行數據做修改時，將新版本數據的block id和pointer offset寫入舊版本的tid字段，就形成瞭版本鏈。
Heap Only Tuple
PG中的HOT機制(Heap Only Tuple)，其實就是版本鏈。當新版本tuple滿足以下兩個條件時，被認為是HOT。
（1）更新操作不涉及有索引的列。
（2）舊版本數據和新版本數據在同一個頁中。
HOT有兩個好處，一是可以不需要為HOT單獨新增索引項，可以通過版本鏈找到。
另一點在於，HOT可以優化垃圾回收。隨著更新操作不斷累積，版本鏈越來越長，找到tuple最新版本的開銷會非常大，所以需要vacuum進程定時清理dead tuple。而眾所周知，任何程序的垃圾回收進程都會影響程序本身的運行，因此我們不希望vacuum一次性清理太多dead tuple。對於這個問題，PG通過defragmentation操作減輕vacuum的壓力。由於PG的版本鏈是由最舊數據指向最新數據，在Select/Update/Insert/Delete過程中一定會最先遍歷到dead tuple，PG就在這個過程中清理部分dead tuple，這個過程更通用的叫法是cooperative cleaning。
當然我們還要考慮到，清理過程讓版本鏈的頭部發生瞭變化，索引不再指向最舊數據的指針瞭。不過由於使用的是邏輯指針(tid)，這裡仍然不需要修改索引，具體做法是不刪除舊的頭指針，將頭指針指向下一個指針。
以下面的圖為例：
- T1是版本鏈的頭部，索引指向T1的指針。T2是HOT，是更新T1產生的新版本，T1的t_ctid指向T2。
- 清理T1後，將T1的指針重定向到T2指針，而索引仍然存T1的指針。
- 要查詢key=1000的行，通過索引找到T1指針，T1指針指向T2指針，再由T2指針指向T2。
2.3 PG vacuum機制
上文中已經簡單提到瞭vacuum機制，本節將詳細展開其細節。
vacuum進程的主要任務是：(1)刪除dead tuple(2)凍結事務id，凍結事務id是為瞭重用有限的事務id，這裡不作討論。
刪除dead tuple的操作分為Concurrent Vacuum和Full vacuum。
Concurrent Vacuum會對表（可選擇某個表或所有表）的磁盤文件進行清理，先刪除dead tuples對應的索引（存疑，如果版本鏈上還有live tuples，應該需要重定向指針？），然後刪除dead tuples，刪除dead tuple後，live tuple之間的空間碎片也需要消除。具體流程如下圖所示。
PG8.0版本後支持autovacuum，默認1分鐘執行一次vacuum。如果配置開啟系統數據監控系統(cumulative statistics system），vacuum會根據某些條件自動觸發。比如autovacuum_vacuum_scale_factor = 0.2 表示自從上次vacuum後，這個表的更新次數超過瞭table size的20%，就要對該表進行一次vacuum。
#autovacuum = on # Enable autovacuum subprocess? 'on'
#autovacuum_vacuum_threshold = 50 # min number of row updates before vacuum
#autovacuum_analyze_threshold = 50 # min number of row updates before analyze
#autovacuum_vacuum_scale_factor = 0.2 # fraction of table size before vacuum
#autovacuum_analyze_scale_factor = 0.1 # fraction of table size before analyze
#autovacuum_freeze_max_age = 200000000 # maximum XID age before forced vacuum