CMU 15-445 資料庫課程第四課文字版
熟肉視訊地址：
1. 面向紀錄檔的儲存
上節課我們講完了面向元組的儲存，這節課從面向紀錄檔的儲存設計開始。
在這裡，頁中不儲存元組資料，只會儲存紀錄檔記錄，即通過紀錄檔記錄我們插入的資料以及我們如何更新系統中的資料，包括：插入元組的語句紀錄檔，刪除元組的語句紀錄檔，更新元組的語句紀錄檔。
這種設計寫得很快，因為不用在一個頁裡尋找並更新單個元組，就是在末尾追加寫，這樣寫起來非常快，對於磁碟 I/O 也很好。
但是對於讀取，就很麻煩了。為了讀取一條記錄，我們要做的就是從後向前掃描這個紀錄檔，以便重新建立我們想要查詢的元組。
當然我們可以做一些優化，比如我們可以建立一個索引，用來找到應用於每個元組的不同紀錄檔記錄，這樣我們就不需要對所有的紀錄檔記錄進行完整的掃描。但是這帶來了而外的後設資料儲存消耗。
另一種優化方式就是定期壓縮這些紀錄檔，基本上只是把所有的紀錄檔記錄壓縮成單個值，過程是：獲取頁的鎖並鎖定，然後執行壓縮，然後釋放鎖。讓我們更深入地討論一下壓縮是如何進行的：
首先是層級壓縮(level compaction)的：從頂層開始是第 0 級，我們有這個按照執行順序排好序的紀錄檔檔案，它在不斷積累，隨著時間積累了所有這些頁。我們要做的是做一個週期性的壓縮，即當第 0 級有兩頁被填滿的時候，將它們裡面的記錄做歸併排序，並壓縮到一個更大的檔案中並放到下一級，即第 1 級。之後更多的紀錄檔檔案會在頂層第 0 級建立，我們只是不斷重複這個過程，第 1 級有兩頁滿了的就歸併排序壓縮成為一個新的放入第 2 級，依次類推。
另一種是全體壓縮(universal compaction)的：即沒有等級概念，只是合併歸併壓縮相鄰的頁檔案。
資料格式（Data Representation）
如果我們在頁面中有一個單獨的元組，我們如何儲存它，如何解釋儲存在裡面的資料，以及 DBMS 的其他層如何利用或從元組儲存中提取它們需要的資料。
元組本質上就是一個位元組序列，DBMS 目錄中會包含表的模式資訊，通過這個模式資訊可以解析出元組中的資料。
元組內的資料屬性可以有不同的型別，一般常見的型別包括：
- 整數型別：有不同的大小的整數，在 SQL 標準中是基於它們支援的值範圍定義的，一般有 BIGINT/SMALLINT/TINYINT/INTEGER 等等
- 浮點數型別或者小數型別：一種是基於 IEEE-754 標準定義的近似浮點值，還有就是固定小數點的小數，一般有 FLOAT/REAL，以及 NUMERIC/DECIMAL 等等。
- 變長型別：這種資料型別並非固定長度，所以帶有頭部標識資料長度，之後跟著實際資料，比如 VARCHAR/VARBINARY/TEXT/BLOB
- 時間型別：一般通過計算與 Unix Epoch（1970-01-01 00:00:00 UTC）時間經過的時間長度（單位為毫秒或者秒），儲存在一個 32 位或者 64 為的整數型別中儲存。
這裡最棘手的是浮點小數或者任意精度的小數的處理。
對於小數精度不確認的小數，例如不限制計算結果的數位的小數位數這種情況，由於精度是不確認的，所以很難通過一些計算機結構表示出來，例如 C/C++ 中對應的 FLOAT 和 DOUBLE/REAL 等型別，他們是通過 IEEE-754 標準去近似逼近實際儲存的小數：
- 最高位 bit 表示符號位（0x8000000000000000）
- 第二到第十二的 bit 表示指數（0x7ff0000000000000）
- 剩下的 bit 表示浮點數真正的數位（0x000fffffffffffffL）
舉個例子，78.5 這個數位，對於 double，實際儲存的就是：40 53 a0 00 00 00 00 00，轉換成二進位制：01000000 01010011 10100000 00000000 00000000 00000000 00000000 00000000，符號位：0，指數位10000000101 = 1029，減去階數 1023 = 實際指數 6，小數部分0.0011101000000000000000000000000000000000000000000000，轉換為十進位制為0.125 + 0.0625 + 0.03125 + 0.0078125 = 0.2265625， 加上隱含數位 1 為 1.2265625， 之後乘以 2 的 6 次方就是 1.2265625 * 64 = 78.5
double 使用的位數比較多，所以逼近的誤差更小一些，float 使用的位數比較少，可能的誤差就會大一些。
這裡使用一個指定精度顯示的程式展示了這種 IEEE-754 標準逼近帶來的可能的誤差。
如果你是在不需要那麼精確的場景，那麼可以使用這種 IEEE-754 標準逼近的近似小數，如果你需要很精確的場景，那麼就不要用這種了。你就需要使用固定精度的數位型別（Numeric Type）
可以在給數位型別設定一個任意的精度和位數，這些東西在實際系統中如何工作有很多不同的實現。一般來說，商業版的資料庫要複雜得多，因為他們知道商業應用對固定精度的數值有很大的需求。但是這裡需要權衡，因為你需要的精確度越高會在你的處理過程中需要更多的開銷。
postgres 是這樣實現其數位資料型別：
這個結構體包括：
int ndigits: 包含數位的個數int weight：第一個數位的權重，實際的數位由第一個數位乘以這個權重組成int scale：放大係數int sign：符號，是正是負還是空NumericDigit *digits：是一個字元陣列，儲存所有的數位
MySQL 的儲存結構也是類似的：
這個結構體包括：
int intg: 小數點前的數位個數int frac：小數點後面的數位個數int len：數位佔用位元組長度bool sign：符號，是正是負decimal_digit_t *buf：是一個 int32 陣列，儲存所有的數位
大多數系統不允許元組超過單個頁的大小，所以它要麼受列的大小限制要麼受列的個數限制，或者兩者都受限制，所以基本不能指定一個大於一頁大小的元組。但是如果元組的某個值大於一頁大小怎麼辦？例如一個某個元組有個值是 VARCHAR 型別，儲存了很長的字串，那麼我們不會把所有資料和元組其他資料放在一起，而是把它儲存在溢位頁中。
假設元組的 c 屬性是一個 VARCHAR 型別並且儲存的值很大，那麼元組內在 c 的位置會儲存一個指標，它會指向儲存在溢位頁中的 varchar 資料。溢位頁可能一頁存不下，不止一頁大小，所以會是一個頁連結串列。這在不同的系統中有不同的叫法：
- postgres 稱它為 toast，如果大於2KB，溢位頁就會出現
- MySQL：大於頁大小的一半就會出現溢位頁
- SQL Server：大於頁大小才會出現溢位頁
除了溢位頁還有另一種方式即儲存為外部檔案
某些 DBMS 允許你將這種大值儲存到外部的檔案中，以 BLOB 的方式處理這個資料，例如：
- Oracle： BFILE 資料型別
- Microsoft：FILESTREAM 資料型別
我們一般不不適合儲存進資料庫的巨量資料放入外部檔案儲存，例如視訊、圖片等等。我們只是儲存了一個指向資料的指標，實際指向的資料位於檔案系統的其他地方，我們可以在需要的時候參照它。
但是這樣就喪失了 DBMS 對其的管理特性，例如不能保證外部是否有修改或者刪除這個外部檔案，不能保證事務性修改等等。
對於非不適合放入資料庫儲存的那種巨量資料，比如大 JSON 等等，Jim Gray 曾經有一篇論文研究，評估資料大小對於是直接在溢位頁面記憶體儲blob好，還是在外部儲存blob更好的影響，這是一篇 15 年前的論文，這篇論文得出的結論是，他們得出的結論是256KB的大小在外部儲存更有利，現在這個數位可能變得更大了。但是我們要記住，如果它儲存在DBMS中，我們每次都要把這些巨大的物件通過很多頁寫入和從磁碟中讀取，這是我們要考慮的權衡。
3. 系統目錄（System Catalog）
我們接下來要講的是系統級別的目錄，DBMS 需要在內部儲存所有關於資料庫的後設資料以便於他能需要知道如何編碼和解碼儲存在代表元組的位元組中的資料。一般儲存關於表，列，索引，檢視的結構資訊，諸如此類的結構資訊。DBMS 通常還儲存有關使用者和許可權的資訊，就像存取許可權，即使用者應該能夠檢視或修改哪些資料。最後，DBMS 還儲存了大量的內部統計資料，比如不同值的數量，或者連線基數，或者資料範圍之類的，這些是構建查詢計劃，查詢執行中非常重要的。
大部分的 DBMS 都將資料庫儲存為目錄型別的結構，前面我們說過，在這個系統目錄中也會儲存關於表，列，索引，檢視的結構資訊，這些結構資訊也像普通的表一樣儲存。那麼現在就有了雞生蛋蛋生雞的問題，我們需要這些結構資訊解析讀取表資料，但是這些資訊也以表的形式儲存。所以一般的設計是它們有這些特殊的後設資料物件包裝器，系統可以用來直接編碼和解碼儲存在系統目錄中的值。
使用者可以查詢 DBMS 的這個內部目錄，它通常儲存在這個 INFORMATION_SCHEMA 中，以獲取關於資料庫的資訊以及各種統計資訊等等。這被 ANSI 標準定義為唯讀檢視的集合，在它標準化之前，這曾經很混亂，每個系統都有自己的方式來暴露這些後設資料。現在有了這個標準，大家都可以通過存取 INFORMATION_SCHEMA 來存取這些資訊。不過不同的系統還是暴露了其他的一些等價的快捷方式命令存取這些資訊，比如：
這是列出某個資料庫中所有表的命令：
- SQL-92 標準中是：
select * from information_schema.tables - Postgres 中是：
\d - MySQL 中是：
show tables - sqlite 中是：
.tables
這是檢視某個表的詳細資訊的命令：
- SQL-92 標準中是：
select * from information_schema.tables where table_name = 'student' - Postgres 中是：
\d student - MySQL 中是：
DESCRIBE student - sqlite 中是：
.schema student
4. 資料庫工作負載型別（Database Workload）
我們主要有三種不同型別的資料庫工作負載：
- 第一個是線上事務處理，簡稱 OLTP（Online Transaction Processing）：這意味著你有很多快速短小的執行操作，即每次唯讀取或更新一小部分資料。例如你的銀行賬戶場景，比如你想要得到你銀行賬戶的餘額，你只是讀取一個值，或者如果你想做一筆交易，比如存款，這是一筆相當短的交易。還有就是像亞馬遜這樣的網上商店，你瀏覽不同的產品把它們加到你的購物車結賬付運費，你存取的資料量相對於亞馬遜提供的所有產品來說是相對較小的，但是如果你思考下世界上有很多同時購物的人，這就積少成多了，即各個事務存取或修改的資料量積少成多了。
- 第二個是線上分析處理，簡稱 OLAP（Online Analytical Processing）：這些有點像分析查詢，讀取大量的資料，掃描表的大部分，會產生聚合，有很多表之間的連線，通常用於決策支援或商業智慧。同樣是亞馬遜的例子，比如亞馬遜想知道在過去的一個月裡，CMU 學生購買最多的五個商品是什麼。這種查詢需要掃描一個大的樣本，而不僅僅是更新單個或讀取單個記錄。
- 最後一個是最近越來越流行的混合事務和分析處理，簡稱 HTAP（Hybrid Transaction and Analytical Processing）：目標是能夠把 OLTP 和 OLAP 放在同一個資料庫範例上，事務處理和分析同時執行，這樣能夠得到關於交易資料更快或更實時的見解。
這個座標圖可能更直觀些，X 軸是從寫多讀少到讀多寫少，Y 軸是請求複雜度，從簡答到複雜。OLTP 的工作負載更多的是寫多一些並且比較簡單的請求，OLAP 的工作負載更多的是讀多一些並且比較複雜的請求，HTAP 介於兩者之間。
在實際使用中，一般公司會建立 OLAP 與 OLTP 獨立的環境：因此，在一端你通常會有多個 OLTP 資料筒倉，這裡做所有的線上業務請求；另一端非常大的 OLAP 資料倉儲，你要在資料倉儲轉儲所有的資料筒倉的資料以供分析。我們需要從資料筒倉到資料倉儲的資料傳輸，主要通過這個 ETL（Extract Transform Load，提取、轉換、載入）過程：我們從這些不同的資料筒倉中提取所有的資料，這些資料格式可能與我們最終需要的資料格式有差異，所以我們需要轉換這些資料，並且對資料做一些處理，比如合併，刪除重複等等，最後載入到資料倉儲中。還有一些資料分析的結果需要從資料倉儲傳回資料筒倉中，例如一些產品推薦資訊，在你存取商品網頁時為你推薦的產品。HTAP 的思想就是讓這些事務工作與查詢工作一起並行執行，並省略很多中間的同步操作。
為什麼區分不同型別的工作負載很重要？回顧一下關係模型，它為我們對資料進行不同操作提供了一定的規則和要求，但它並沒有告訴我們在物理上我們需要如何儲存資料。我們需要根據我們的業務即工作負載的型別，來決定我們的資料如何儲存。我們前面主要講的主要是基於行的儲存，即某一個元組的所有屬性的資料都緊密的儲存在一起。但是這種設計並不適用所有的場景，我們來看一個維基百科的例子：
我們有有一個 useracct 表，也就是維基百科的使用者，它包含 userId 和 userName；然後有 pages 表，儲存了維基百科資料；然後有 revisions 表，它說明哪個使用者對哪個頁面進行了哪些編輯或修訂。同時，userId 指向 useracct 表，pageId 指向 pages 表，其中 pages 表的 revId 指向 revisions 表。
對於維基百科 OLTP 業務場景舉幾個例子，這些場景都只會修改或者查詢表中很少的資料：
- 查詢某一個維基百科詞條，這樣就是查詢 pages 以及 revisions 表。
- 比如可能是使用者每次登陸的時候更新使用者記錄
- 獲取使用者上次登入時更新的詞條資料
- 修改詞條，即修改 pages 表以及新增一個新的記錄到 revisions 表中。這些是執行時間很短的簡單操作，只在資料庫中讀取或寫入一些值。
對於維基百科 OLAP 業務場景的一個例子是檢視上個月來自於 .gov 的使用者不同登陸次數，這種就會掃描表中的大部分資料。
我們引入儲存模型的概念，第一種是基於行的儲存模型，這就是所謂的n元儲存模型（N-ary Storage Model），在一個頁中儲存基於行的資料，所有東西都像一個位元組陣列，所有東西都是連續儲存的。這種格式對於 OLTP 業務請求更加友好，因為查詢傾向於操作單個記錄或者行這個行的所有資料是儲存在一起的，如果不考慮溢位頁的話就都在一頁，也就是大部分請求每個都只會操作一頁。
使用前面維基百科的 OLTP 例子，例如使用者登入需要查詢單個使用者，這個請求會走索引（索引在後面的課堂中會講到，在第七講），索引會告訴我們去哪個頁的哪個槽去獲取這個使用者元組的位置，讀取槽獲取到使用者元組位與頁中的位置，然後就能讀取到這個使用者元組的所有資訊。同時註冊新使用者需要插入記錄，這個插入也只會放在一頁上，並且使用者所有值都在一起。
但是這種儲存不太適合 OLAP 的場景，還是用前面提到的維基百科的例子，檢視上個月來自於 .gov 的使用者不同登陸次數，這個查詢不能走索引，我們需要遍歷這個表的所有頁，過濾 hostname 是.gov的以及 lastlogin 是上個月的，然後統計 lastlogin 欄位，也就是我們其實只需要 hostname 和 lastlogin 這兩個欄位的值，但是實際我們卻載入並解析了整個元組的所有屬性值。這些帶來了首先是磁碟 I/O 的浪費，以及對於解析整個元組資料帶來的額外的記憶體與 CPU 消耗。
我們總結下 n 元儲存模型的優缺點：
- 優點：
- 元組的增刪改查很快
- 適合需要查詢整個元組資料的查詢
- 缺點：
- 很不適合要掃描表中大部分資料，並且查詢的只是元組屬性的子集的場景
第二種是基於列的儲存模型，這就是所謂的分解儲存模型或 DSM（Decomposition Storage Model），即將一個元組的單一屬性的值於一個頁面中連續儲存，而不是連續地儲存單個元組的所有不同屬性值。我們將提取所有的元組這個列值並將他們連續儲存，這也是"列儲存"這個名字的來源。這對於有很多唯讀查詢的 OLAP 工作負載非常理想，一般這種查詢需要分析大部分行的某些屬性值，如果我們把同一屬性的值放在一起，我們就不用掃描查詢中用不到的屬性，並且同一屬性的值在一起這樣對於某個屬性執行聚合函數視窗函數就會效率更高。
我們回到前面提到的維基百科的 OLAP 例子，檢視上個月來自於 .gov 的使用者不同登陸次數，這個查詢我們只需要hostname和lastLogin，我們不需要表格中的任何其他屬性，所以我們現在就可以找到對應於這兩個列的頁，減少了要掃描的資料消耗。
但是對於那種需要返回元組所有屬性的請求，比如要查詢某一個元組的所有屬性，需要查詢每個屬性的所在的頁，然後彙總返回。那麼如何從每個屬性所在的頁找到這個元組對應的資料呢？
可以有兩種方式：
- 固定長度的偏移量：因為每個列值都是相同的型別，對於固定長度欄位，我們直接通過長度乘以個數就能得到對應資料的位置偏移。但是如果對於可變長度的欄位，例如可變長度的字串，可以通過一些方式轉換成固定長度的欄位，例如將字串填充拉長到特定的長度，或者進行編碼使用長度的整數程式碼替換字串，這個在之後的課程會詳細討論。這種方式雖然佔用空間小實現簡單，但是對於變長欄位實現比較麻煩並且會有空間浪費等問題。
- 另一種選擇是儲存元組的id直接嵌入到列中：一般這些列還是通過某種排序規則排序的，我們可以通過二分查詢來找到對應 id 的資料。
我們總結下 DSM 儲存模型的優缺點：
- 優點：
- 減少了I/O浪費，因為唯讀取查詢所需的列中的資料
- 對於實際儲存的列，您可以得到更好的查詢處理和壓縮（後面課程還會詳細討論這個，同一種型別的資料放在一起更好壓縮，例如我們儲存的是日期，那麼我們不用每一個值都儲存日期，而是第一個儲存日期，之後的儲存與第一個日期的相對日期）
- 缺點：
- 如果你想去重建一個單獨的元組的所有資料，那麼就比較慢
- 要做插入更新之類的事情要困難得多，因為你現在需要在多列多頁中新增值而不是一次寫完
DSM 系統並不是新的設計，它們已經存在了一段時間，第一個是在20世紀70年代釋出的 Cantor，它實際上不像DBMS，而是像一個檔案系統。在20世紀80年代，有了第一個關於DSM儲存的理論基礎或提議。在20世紀90年代，有一種產品叫做SybaseIQ，它就像Sybase這個行儲存的記憶體加速器，可惜並不流行。他們所做的是將資料以列儲存形式在記憶體中，以加速某些型別的查詢。在21世紀初到中期，這三個系統開始流行，Vertica, VectorWise 和 MonetDB，他們是第一個受歡迎的，商業上成功的列儲存，為很多目前很常見的列儲存技術鋪平了道路。從 2010 以後，基本所有人都會用到基於 DSM 的系統了。
總結一下，雖然課程開始的時候一直在說DBMS是由這些獨立的部分組成的技術棧，但其實並不是完全獨立的，比如這裡，為目標工作負載選擇正確的儲存模型非常重要，對於 OLTP 你想要行儲存，OLAP 需要列儲存。
微信搜尋「乾貨滿滿張雜湊」關注公眾號，加作者微信，每日一刷，輕鬆提升技術，斬獲各種offer：
我會經常發一些很好的各種框架的官方社群的新聞視訊資料並加上個人翻譯字幕到如下地址（也包括上面的公眾號），歡迎關注：
