存儲介質

一個數據庫系統大致由以下幾個不同的部分組成：

• query plan（執行計劃）
• operator execution（執行器）
• access method（訪問方法）
• buffer pool（緩沖池）
• disk manager（磁盤管理）

以及其他的的一些組成部分，例如并發控制、分布式等。這個課程系列將會自底向上逐一介紹。

首先來看看存儲管理，通常來說，不同的存儲介質，在存儲容量和速度上存在較大的差異，容量越大的介質速度越慢，反之容量越小的介質，速度越快。

以上圖為例，cpu 寄存器和高速緩存（L1、L2、L3），以及內存是常見的易失性存儲，容量小速度快，但是掉電之后無法恢復，不能持久化保存數據。

而磁盤例如 SSD 或者 HDD，容量更大，但是訪問速度慢，能夠持久化保存數據。

下面對這幾種存儲介質的訪問速度做一個簡單的量化（同比放大），可以看到 L1 緩存大概是秒級別的，而機械硬盤甚至長度16 周，容量越大訪問速度越慢。

對于磁盤來說，順序訪問也比隨機訪問更快，因為磁盤的主要時間消耗在于尋道。

數據庫系統對于磁盤管理的設計目標，主要是以下幾個方面：

• 能夠管理遠超過 memory 容量的數據
• 讀寫磁盤開銷巨大，因此需要盡量避免頻繁讀寫磁盤，或者更加高效的讀寫磁盤，防止 write stall 帶來的影響
• 盡量避免隨機磁盤 IO

數據庫中，內存和磁盤的結構和關系大致如下圖，磁盤上的數據通常以 page 為單位進行組織，內存中維護了一個緩沖池 buffer pool，緩存了磁盤中的 page。

當上層的執行引擎需要讀寫數據時，首先從 buffer pool 中獲取數據，如果 buffer pool 中沒有，則從磁盤中加載到 buffer pool，然后返回到執行引擎中。

這樣的組織方式比較類似操作系統提供的 MMap 機制，即內存映射。

內存映射（MMap）指的是將磁盤文件內容映射到內存地址空間中，進程訪問該地址時，觸發缺頁異常，將磁盤的內容加載到物理內存中進行讀寫。

一個常見的問題是，為什么數據庫中不直接使用操作系統提供的 MMap 機制，而是自己去實現內存 buffer 和 disk 的管理呢？

數據庫的上層執行引擎通常是多線程并發執行，如果此時訪問 MMap，訪問的 page 可能會各不相同，由此可能頻繁發生缺頁中斷，導致系統 stall。

而數據庫對于磁盤管理有著更加定制化的需求：

• 以正確的順序將臟頁刷到磁盤
• 特定的預讀策略
• buffer 替換策略
• 線程/進程調度

總之，數據庫系統希望能夠自己控制磁盤和內存管理，而不依賴于操作系統，滿足自己特定的需求和場景。

補充知識：在 PostgreSQL 中，底層的存儲管理基于虛擬文件描述符，即 Virtual File Descriptior，簡稱 VFD，使用 vfd 的主要目的是繞開操作系統對同一個進程最大打開文件數的限制。

進程不直接持有操作系統的 fd，而是由數據庫系統分配的 vfd，如果進程打開文件數達到了上限，那么會暫時關閉未被使用的文件。

在 vfd 之上，postgres 封裝了操作磁盤文件的基本 API，例如打開、關閉、刪除文件等，代碼可參考：https://github.com/postgres/postgres/blob/master/src/backend/storage/file/fd.chttps://github.com/postgres/postgres/blob/master/src/backend/storage/smgr/smgr.c

Page 概覽

絕大多數數據庫系統中的磁盤數據都是以 page 為單位進行組織的，所以先來詳細看看磁盤 page 的結構。

數據庫中的磁盤 Page 指的是一個有固定大小的文件塊，Page 中通常可以存儲元組、元信息、索引、日志等。每個 page 都有一個唯一的標識，稱為 page id。

不同的數據庫的 page size 是不同的，常見的幾種如下：

在數據庫系統中，page 肯定不止一個，那么如此多的 page 之間，需要進行統一管理，例如增加一個 page、刪除一個 page、遍歷所有的 page 等，該怎么組織這些 page 來實現這些目的呢？

最常見的組織方式叫做 heap file，heap file 指的是一個無序的 page 集合，page 是隨機進行排列的。

heap file 有兩種常見的組織方式：

• linked list
• page directory

linked list 是按照鏈表的方式組織 page，鏈表頭有兩個指針，一個指向 free page list，表示空閑的 page 列表，一個指向 data page list，指向實際存儲數據的 page。

這種方式雖然直觀，但是效率低下，因為 page 是通過指針完全無序排列的，查找 page 需要進行遍歷，這種組織方式實際使用并不多。

另一種更加常用的方式是 page directory。

page directory 實際上就是維護了一個特殊的 page，這個 page 中存儲的是其他 page 的位置，可以看做是 page 的元數據。

這個特殊的 page 還存儲了每個 page 的 free space 空間等信息，便于上層應用對需要讀寫的 page 進行選擇。

Page 組織方式

  log structured

page 中數據可以通過類似日志的方式組織，即對 tuple 的增刪操作都以日志追加的方式寫到 page 中，這樣做的最大好處是可以利用順序 IO，寫性能能夠得到提升。

但是這種 log 式的組織方式，需要進行數據的回收處理（compaction），并且在讀數據的時候，因為數據存在新舊多個版本，可能會有額外的磁盤 IO 消耗。

日志組織方式對于寫多讀少的應用非常合適，一些 NoSQL 引擎例如 leveldb、rocksdb、HBase 都采用了這種方式，但是在關系型數據庫中，這種方式并不是主流。

  slotted page

page 的內部結構，關系型數據庫中常用的組織方式叫做 slotted page，其大致結構如下：

page 最靠前的部分，叫做 page header，這通常是由一個固定 size， header 中通常包含一些關于此 page 的元數據，例如 page 大小、校驗和、DB 版本、事務信息、數據壓縮信息。

header 之后的部分叫做 slot array，每一個 solt array 都存儲了 tuple 的開始位置，這樣能夠快速定位到每條記錄。

例如 postgres 中對于每條記錄都有一個隱藏的 CTID，記錄的是該 tuple 的物理位置，其內容是 page id + offset，即 tuple 所在頁的 id，以及在頁內的位置。

select *, ctid from some_table;

每個 tuple 實際上就是一個不定長的字節序列，里面存儲了具體的數據信息。

讀者有興趣的話可以再看下 postgres 的磁盤 page 結構，與這里的 slotted page 基本上是一致的，代碼：https://github.com/postgres/postgres/blob/master/src/include/storage/bufpage.h

  Large Values

前面提到了一個 page 通常都有固定的 size，那么如果存儲的數據太大，超過了 page 的大小，應該怎樣存儲這些數據呢？

最常見的方式是使用一個額外的 page 來存儲，原來的 page 中保存一個指向它的指針，如果數據仍然很大，額外的 page 還是放不下，那么可以在新開一個 page，并且由上一個 page 指向它。

這個額外的 page 通常叫做 overflow page，不同的數據庫有不同的稱呼或做法，例如 PostgreSQL 中把這種存儲叫做 TOAST。

Tuple 的結構

再來看一下 tuple 的內部結構，tuple 大致由兩部分組成，header 和數據部分。

header 中主要存儲了一些元數據信息，例如 tuple 的可見性（用于并發控制），用于判斷 null 列的 bit map 等等。

postgres 中 tuple 的內部結構可以參考：https://github.com/postgres/postgres/blob/master/src/include/access/htup_details.h

Storage Model

最后再來看一下，在宏觀的角度，對于不同 workload 的數據庫的存儲方式有什么區別。

目前根據不同的應用場景和數據讀寫特征，大致將數據庫劃分為了兩種：OLTP 和 OLAP，他們的存儲方式也存在很大的差異。

OLTP，即 On-Line Transaction Processing，在線事務處理，其特征是讀寫簡單，通常是讀/寫一小部分數據，并且事務可保證數據的一致性。

目前大多數在線業務均使用 OLTP 類型的數據庫，例如電商，通常選擇、購買商品，針對一個用戶，大多數情況下，都只會讀取和更新一部分只關于這個用戶的數據。

OLAP，即 On-Line Analytic Processing，在線分析處理，其特征是查詢復雜，需要讀取大批量數據進行統計分析。

針對這兩種不同的 workload，數據庫中的數據組織上也有一些區別，分別是以行存和列存為主流。

行存是最常見、符合直觀思維的存儲模式，將不同屬性的數據一行行的組織起來，并且存儲到 page 當中。

這樣更適合 OLTP，因為能夠非常方便的更新或者獲取到某一條（或幾條）具體的數據（點查）。

但如果我們的查詢只需要取出一部分的列，而不是一個 table 中的全部列，那么這樣會造成一定的浪費，因為我們可能會把毫不相關的列取出來然后丟棄掉。

列存的組織方式則完全不同，它會將有相同屬性的數據一起組織起來，這樣更方便大批量掃描數據。

具體的存儲方式，是將表中一個列的數據存到 page 中。由于具有相同屬性的數據，會更可能有類似的特征，所以這樣的數據組織方式更適合壓縮，節省存儲空間。

列存更適合 OLAP 類型的數據庫。

這一節主要講述了數據庫的存儲管理，并且摻雜了一些 PostgreSQL 的 demo，大家可以自行參考。下一節會向上一層，來看看對于內存 buffer pool 的管理。