存儲(chǔ)介質(zhì)

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

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

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

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

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

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

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

對(duì)于磁盤來(lái)說(shuō)，順序訪問(wèn)也比隨機(jī)訪問(wèn)更快，因?yàn)榇疟P的主要時(shí)間消耗在于尋道。

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

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

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

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

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

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

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

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

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

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

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

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

進(jìn)程不直接持有操作系統(tǒng)的 fd，而是由數(shù)據(jù)庫(kù)系統(tǒng)分配的 vfd，如果進(jìn)程打開文件數(shù)達(dá)到了上限，那么會(huì)暫時(shí)關(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ù)庫(kù)系統(tǒng)中的磁盤數(shù)據(jù)都是以 page 為單位進(jìn)行組織的，所以先來(lái)詳細(xì)看看磁盤 page 的結(jié)構(gòu)。

數(shù)據(jù)庫(kù)中的磁盤 Page 指的是一個(gè)有固定大小的文件塊，Page 中通?？梢源鎯?chǔ)元組、元信息、索引、日志等。每個(gè) page 都有一個(gè)唯一的標(biāo)識(shí)，稱為 page id。

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

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

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

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

• linked list
• page directory

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

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

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

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

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

Page 組織方式

  log structured

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

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

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

  slotted page

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

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

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

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

select *, ctid from some_table;

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

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

  Large Values

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

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

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

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

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

header 中主要存儲(chǔ)了一些元數(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

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

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

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

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

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

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

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

這樣更適合 OLTP，因?yàn)槟軌蚍浅７奖愕母禄蛘攉@取到某一條（或幾條）具體的數(shù)據(jù)（點(diǎn)查）。

但如果我們的查詢只需要取出一部分的列，而不是一個(gè) table 中的全部列，那么這樣會(huì)造成一定的浪費(fèi)，因?yàn)槲覀兛赡軙?huì)把毫不相關(guān)的列取出來(lái)然后丟棄掉。

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

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

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

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