存儲介質(zhì)

一個數(shù)據(jù)庫系統(tǒng)大致由以下幾個不同的部分組成：

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

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

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

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

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

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

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

數(shù)據(jù)庫系統(tǒng)對于磁盤管理的設(shè)計目標(biāo)，主要是以下幾個方面：

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

數(shù)據(jù)庫中，內(nèi)存和磁盤的結(jié)構(gòu)和關(guān)系大致如下圖，磁盤上的數(shù)據(jù)通常以 page 為單位進(jìn)行組織，內(nèi)存中維護(hù)了一個緩沖池 buffer pool，緩存了磁盤中的 page。

當(dāng)上層的執(zhí)行引擎需要讀寫數(shù)據(jù)時，首先從 buffer pool 中獲取數(shù)據(jù)，如果 buffer pool 中沒有，則從磁盤中加載到 buffer pool，然后返回到執(zhí)行引擎中。

這樣的組織方式比較類似操作系統(tǒng)提供的 MMap 機制，即內(nèi)存映射。

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

一個常見的問題是，為什么數(shù)據(jù)庫中不直接使用操作系統(tǒng)提供的 MMap 機制，而是自己去實現(xiàn)內(nèi)存 buffer 和 disk 的管理呢？

數(shù)據(jù)庫的上層執(zhí)行引擎通常是多線程并發(fā)執(zhí)行，如果此時訪問 MMap，訪問的 page 可能會各不相同，由此可能頻繁發(fā)生缺頁中斷，導(dǎo)致系統(tǒng) stall。

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

• 以正確的順序?qū)⑴K頁刷到磁盤
• 特定的預(yù)讀策略
• buffer 替換策略
• 線程/進(jìn)程調(diào)度

總之，數(shù)據(jù)庫系統(tǒng)希望能夠自己控制磁盤和內(nèi)存管理，而不依賴于操作系統(tǒng)，滿足自己特定的需求和場景。

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

進(jìn)程不直接持有操作系統(tǒng)的 fd，而是由數(shù)據(jù)庫系統(tǒng)分配的 vfd，如果進(jìn)程打開文件數(shù)達(dá)到了上限，那么會暫時關(guān)閉未被使用的文件。

在 vfd 之上，postgres 封裝了操作磁盤文件的基本 API，例如打開、關(guān)閉、刪除文件等，代碼可參考：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 概覽

絕大多數(shù)數(shù)據(jù)庫系統(tǒng)中的磁盤數(shù)據(jù)都是以 page 為單位進(jìn)行組織的，所以先來詳細(xì)看看磁盤 page 的結(jié)構(gòu)。

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

不同的數(shù)據(jù)庫的 page size 是不同的，常見的幾種如下：

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

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

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

• linked list
• page directory

linked list 是按照鏈表的方式組織 page，鏈表頭有兩個指針，一個指向 free page list，表示空閑的 page 列表，一個指向 data page list，指向?qū)嶋H存儲數(shù)據(jù)的 page。

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

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

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

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

Page 組織方式

  log structured

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

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

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

  slotted page

page 的內(nèi)部結(jié)構(gòu)，關(guān)系型數(shù)據(jù)庫中常用的組織方式叫做 slotted page，其大致結(jié)構(gòu)如下：

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

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

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

select *, ctid from some_table;

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

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

  Large Values

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

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

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

Tuple 的結(jié)構(gòu)

再來看一下 tuple 的內(nèi)部結(jié)構(gòu)，tuple 大致由兩部分組成，header 和數(shù)據(jù)部分。

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

postgres 中 tuple 的內(nèi)部結(jié)構(gòu)可以參考：https://github.com/postgres/postgres/blob/master/src/include/access/htup_details.h

Storage Model

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

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

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

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

OLAP，即 On-Line Analytic Processing，在線分析處理，其特征是查詢復(fù)雜，需要讀取大批量數(shù)據(jù)進(jìn)行統(tǒng)計分析。

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

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

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

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

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

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

列存更適合 OLAP 類型的數(shù)據(jù)庫。

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