CMU 15-445/645-筆記-03-數(shù)據(jù)庫存儲-part1
- 課程目標(biāo)
?
? ??
? ? 1. DBMS 是怎么用磁盤上的文件來表示數(shù)據(jù)庫的（主要是這個）
? ? 2. DBMS 是怎么管理內(nèi)存的，是怎么在磁盤間來回移動數(shù)據(jù)的
- 課程大綱
? ??
? ? 上述展示的就是一個數(shù)據(jù)庫中應(yīng)該包含的東西，一個數(shù)據(jù)庫就是建立在這些層面之上
- 面向磁盤的數(shù)據(jù)庫架構(gòu)
? ??
? ? 由于這門課是面向磁盤（Disk-Oriented）的數(shù)據(jù)庫管理系統(tǒng)，即數(shù)據(jù)庫的主要存儲位置都是放在磁盤上的，意味著每次執(zhí)行查詢時，所要訪問的數(shù)據(jù)都不在內(nèi)存（Memory）中。所以在設(shè)計這個數(shù)據(jù)庫管理軟件時，要基于一些假設(shè)來設(shè)計一系列的組件，來保護這個數(shù)據(jù)庫系統(tǒng)，使其免于數(shù)據(jù)丟失、保存無效或錯誤的數(shù)據(jù)等情況。
? ??
? ? 此外還需要區(qū)分
? ??
? ? 1. 易失性存儲
? ? 2. 非易失性存儲
? ??
? ? 簡單來講就是，我們所要的 數(shù)據(jù)系統(tǒng) 管理了數(shù)據(jù)從非易失性存儲到易失性存儲的移動
? ??
? ? 計算機的存儲結(jié)構(gòu)如圖所示
? ??
? ??
? ? 1. 越上面的容量越小，速度越快，也越貴
? ? 2. 越下面的容量越大，速度越慢，也越便宜
? ??
? ??
? ? 注意這里在 DRAM 和 SSD 有條分界線，這里就是易失性和非易失性存儲的分界
? ??
? ? 需要穩(wěn)定的能量（電能）維持它所存儲的東西的存儲設(shè)備，叫做易失性存儲，那么反之就是非易失性存儲
? ??
? ? 1. 如果數(shù)據(jù)是保存在易失性存儲設(shè)備中，那么它就支持 快速隨機訪問，即無論在什么位置訪問數(shù)據(jù)，訪問數(shù)據(jù)的順序是怎么樣的，訪問的速度都大體一致
? ? 2. 如果數(shù)據(jù)是保存在非易失性存儲設(shè)備中，由于它們具備的是 塊尋址（非字節(jié)尋址） 能力，無法準(zhǔn)確地得到數(shù)據(jù)的 位大小的數(shù)據(jù)（32bit, 64bit），所能得到的是包含要訪問的數(shù)據(jù)的 塊（Block） 或者 頁（Page）
? ? 3. 但是在非易失性存儲設(shè)備中，比起隨機讀取不同位置上的內(nèi)容，它能更有效率地去讀取一段連續(xù)的 塊 中的內(nèi)容。所以對于非易失性存儲來講，是希望按順序讀取的數(shù)據(jù)量越大越好
? ??
? ? Memory 和 Disk 的區(qū)分
? ??
? ??
? ? 現(xiàn)在已經(jīng)沒人用磁帶機來存數(shù)據(jù)了，但是可用來做容災(zāi)
? ??
? ? Network Storage 現(xiàn)在指類似于 Amazon 的 EBS 或者 S3 之類的東西
? ??
? ? 實際上在分割線處還有新的一類存儲設(shè)備，它被稱之為非易失性內(nèi)存（Non-Volatile Memory）
? ??
? ??
? ? 比如 Intel 的 傲騰（Optane）內(nèi)存，牙膏廠雖然是第一個發(fā)布這種內(nèi)存的廠商，但這類技術(shù)的研究已經(jīng)有 15-20 年左右的歷史了
? ??
? ? 它可以像 DRAM 一樣，可以插在 DIMM 槽內(nèi)，卻具備 字節(jié)尋址 能力，也可以像 SSD 那樣，斷電也能持久保存數(shù)據(jù)。
? ??
? ? 但殘念的是，目前這種既能又能的存儲設(shè)備并沒有被廣泛應(yīng)用
? ??
? ? 順便老師在課上寫的這本書有賣嗎？
? ??
? ??
? ? 一張關(guān)于各種存儲設(shè)備的訪問耗時表
? ??
- 系統(tǒng)設(shè)計目標(biāo)? ??
? ??
? ? 目標(biāo)就是，給應(yīng)用程序提供一種錯覺，即這個系統(tǒng)能提供足夠的內(nèi)存，能把整個數(shù)據(jù)庫導(dǎo)入到內(nèi)存中。并且最小化每次從磁盤讀取/查詢內(nèi)容所帶來的影響
? ??
? ? 比如這種最小化的方式可以通過以下幾種方式達到
? ??
? ? 1. 允許在同一時間運行不同的線程/查詢
? ? 2. 緩存
? ? 3. 提前計算某些數(shù)據(jù)
? ??
? ? 一個訪問磁盤數(shù)據(jù)的示意圖
? ??
? ??
? ? 可以看到有幾個關(guān)鍵的地方，Directory、Buffer、Page
? ??
? ? 那么這個有點像什么呢？-- 虛擬內(nèi)存
? ??
? ? 那么操作系統(tǒng)能做這件事，為什么還這樣設(shè)計而不直接使用操作系統(tǒng)來做呢？
? ??
? ??
? ? > 注意 mmap 指的是 maps files or devices into memory
? ??
? ? 雖然操作系統(tǒng)可以利用虛擬內(nèi)存通過 mmap 來映射到文件，但是這只適用于 只讀 的訪問，對于有多個 writer 的情況就復(fù)雜很多了
? ??
? ??
? ? 因為操作系統(tǒng)并不知道某些 pages 必須要先于其他 pages ，從內(nèi)存刷到磁盤，這里有一個競爭的關(guān)系
? ??
? ? 那么有沒有解決方案呢？有的
? ??
? ??
? ? 1. 使用 madvise 告訴 OS 怎么去訪問某些頁面（順序/隨機讀?。?/p>
? ? 2. 使用 mlock 阻止 pages 被 OS 回收（盡管可以被鎖定但并不能阻止它被寫出到磁盤）
? ? 3. 使用 msync 告訴 OS 要把數(shù)據(jù)刷到磁盤中
? ??
? ? 使用 mmap 和 部分使用 mmap 的 Database
? ??
? ??
? ? 1. 實際上 MemSQL 已經(jīng)完全擺脫了 mmap
? ? 2. SQLite 有一個特殊的引擎，在嵌入式設(shè)備上 mmap 是可選的，默認(rèn)情況下用不到
? ? 3. InfluxDB 只有在只讀緩存上才使用 mmap?
? ? 4. mongoDB 第一次被開發(fā)出來時，它的默認(rèn)存儲引擎用的就是 mmap，但為了讓這個引擎能正常工作，開發(fā)人員也做了很多無用功，因為這里面存在著巨大的瓶頸，然后等他們籌到很多錢之后，就把 mmap 干掉了，再然后他們買了一個叫做 WiredTiger 的非 mmap 的存儲引擎
? ??
? ? 注意這張圖里面少了很多主流的 Database，比如 MySQL，Oracle，DB2 以及 SQL server，這些數(shù)據(jù)庫都沒有使用 mmap，因為 mmap 是一個糟糕的想法，因為缺少人為寫代碼去控制這種行為。
? ??
? ? 所以如果 mmap 是一個好的想法，那么這群土豪（指 mongoDB）手下的頂級工程師肯定能證明這的確是，然后并沒有（哈哈哈哈好好笑）
? ??
? ? 老師痛恨 mmap
? ??
? ??
? ? 畢竟操作系統(tǒng)啥也不懂，它只看到了一些讀寫和調(diào)用（
? ??
- 文件存儲? ??
? ??
? ? 數(shù)據(jù)庫其實就是磁盤上的一堆文件，SQLite 把數(shù)據(jù)庫存儲為一個文件，而其他大部分?jǐn)?shù)據(jù)庫比如 PostgreSQL 則會把這些分為多個文件來存儲，因為數(shù)據(jù)庫可能非常大，甚至可能有 PB 級別的數(shù)據(jù)量，你不會想要對這么大的一個文件做錯誤修復(fù)
? ??
? ? 現(xiàn)在的一些"企業(yè)級"的數(shù)據(jù)庫系統(tǒng)還支持自定義的專屬文件系統(tǒng)，但近些年的一些數(shù)據(jù)庫系統(tǒng)已經(jīng)不支持了，因為非常不值得，要管理這種文件系統(tǒng)是一個很大的坑，同時也大大降低了可移植性。
- 存儲管理器
? ??
? ? 存儲管理器也叫存儲引擎，它負(fù)責(zé)維護磁盤上的數(shù)據(jù)庫文件。
? ??
? ? 某些高端數(shù)據(jù)庫系統(tǒng)在文件系統(tǒng)之上還有一個 shim 層，它允許數(shù)據(jù)庫去做一些磁盤的調(diào)度，這就像是可以通過一堆線程來對彼此鄰近的區(qū)塊進行寫入，也可以將這些區(qū)塊合并后做一次寫入請求。
- Database Pages? ??
? ??
? ? 一個 page 的集合，就是這一堆文件的一個組織形式。本質(zhì)上來講，一個 page 就是一個固定大小的數(shù)據(jù)塊
? ??
? ? self-contained 的意思是，page 的內(nèi)容必須存儲在 page 本身內(nèi)。比如 Orcale 就需要將描述該 page 中內(nèi)容的所有元數(shù)據(jù)，和這些內(nèi)容數(shù)據(jù)一起保存在該 page 中，避免數(shù)據(jù)庫故障的時候你找不到，這樣即便丟了一個 page，也不會影響其他的 page
? ??
? ? indirection 層允許將一個 page ID 映射到某個集合中一個文件的某個位置。相當(dāng)于記錄一個相對位置，方便文件整體移動后，只要知道整體文件的初始位置，依然可以通過該相對位置即 page ID 找到某個文件某個位置的數(shù)據(jù)所對應(yīng)的 page。因為一個 page 的大小是固定的，page ID * page Size 即為 offset
? ??
? ? 一些 page 的概念
? ??
? ??
? ? Database Page 大小各有不同
? ??
? ??
? ? 但我們更需要關(guān)注的是 Hardware Page 的大小，因為它是原子的，即一次只能寫入這么大的 page 數(shù)據(jù)，如果超過了，那么剩下的數(shù)據(jù)就會丟失寫不進去，寫入失敗也不會回滾，數(shù)據(jù)就會損壞
? ??
? ? 高級數(shù)據(jù)庫可以設(shè)定它們自己 page 的大小
? ??
? ? 那么為什么有些數(shù)據(jù)庫系統(tǒng)使用的是空間更大的 page 呢？
? ??
? ? 這里是有一些權(quán)衡的，比如在數(shù)據(jù)庫系統(tǒng)的內(nèi)部，通過內(nèi)存中的 Page 目錄將 page 映射到內(nèi)存或者磁盤上的某個位置，如果現(xiàn)在用一個 page ID 來表示一個更大量的數(shù)據(jù)，那么一個表所占用的大小就會變小。因為固定容量下，一個 ID 表示的數(shù)據(jù)量越大，那么它所需要的 ID 數(shù)也越小。比如 CPU 中 TLB（頁表緩存），如果嘗試去匹配所有的 page，那么 page 表將會變得非常的大，然后就會出現(xiàn) cache misses 的現(xiàn)象。因為 page ID 表示的數(shù)據(jù)范圍太小，在高速緩存中無法全部命中。所以這里可以通過更少的 page ID 來表示更多的數(shù)據(jù)
- Page 存儲架構(gòu)
? ??
? ? 比較重要的就是 Heap File Organization
? ??
? ? - Database Heap
? ??
? ? ? ??
? ? ? ? 數(shù)據(jù)庫中的 heap 文件是一個無序的 page 集合，即可以以隨機的順序把 tuple 數(shù)據(jù)存儲在里面
? ? ? ??
? ? ? ? 鏈表來實現(xiàn)一個 page 是很 low 的，更好的方案是使用 Page 目錄
? ? ? ??
? ? - Heap File: 鏈表
? ??
? ??
? ? ? ? 這里的例子中，如果要支持反向查找，那還得是一個雙向鏈表
? ? ? ??
? ? ? ? 如果需要在 page 中 insert 一些東西，那么還是需要對這個鏈表做遍歷，直到找到 free page 為止，在這個位置 insert。為什么需要遍歷，因為有些 page 的剩余空間可大可小，所以需要遍歷到那個足以容納下要 insert 的數(shù)據(jù)的一個剩余空間里面去
? ? ? ??
? ? ? ? 寫數(shù)據(jù)時需要注意的問題，即數(shù)據(jù)寫一半，寫滿一個出了問題，后一半還沒來得及寫，數(shù)據(jù)就會損壞，所以要保證寫數(shù)據(jù)的原子性和完整性，需要做很多工作
? ? ? ??
? ? ? ? 寫入數(shù)據(jù)崩潰，如何查找原因？使用 checksum，類似于 CRC 或者 md5
? ? ? ??
? ? - Heap File: Page 目錄? ??
? ??
? ? ? ??
? ? ? ? Page 目錄是一個通常的做法，好處是假如想要插入一些數(shù)據(jù)時，沒必要像鏈表那樣對整個鏈表做一次遍歷，只需要在 Page 目錄中做查找就可以。例子中的每個小格中不僅有對應(yīng) page 所在位置，也包含了 page 剩余空間的信息
? ? ? ??
? ? - Page 頭? ??
? ??
? ??
? ? - Page 層
? ??
? ? ? ??
? ? ? ? 1. 面向 tuple 的組織方式
? ? ? ??
? ? ? ? ? ??
? ? ? ? ? ? 這種組織方式是一個 bad idea，為什么呢？
? ? ? ? ? ? - 如果 tuple 都是固定長度的，那么要增刪 tuple 的話，通過將其移到一個新的空間來取代這個老的空間就可以了不是么（聯(lián)想到了 V8 的新生代老生代的 GC 算法了）
? ? ? ? ? ? - 如果 tuple 不是固定長度的，那么你插入 tuple
? ? ? ? ? ? 的那個位置可能就沒有足夠的空間
? ? ? ? ? ? - 每次要增刪 tuple 時，都需要維護頂部的元數(shù)據(jù)，也就是 Num Tuples，告訴你哪個位置能插數(shù)據(jù)，或者遍歷整個 page 看看哪里能插
? ? ? ? ? ??
? ? ? ? ? ? 但更好的方式是使用 slotted pages
? ? ? ? ? ??
? ? ? ? ? ??
? ? ? ? ? ? 在頂部有一個稱之為 slot 數(shù)組 的東西，在底部則用來保存想要保存的數(shù)據(jù)
? ? ? ? ? ??
? ? ? ? ? ? 本質(zhì)上來講，slot 數(shù)組是將一個特定的 slot 映射到 page 上的某個 offset 上，根據(jù)這個 offset，就能找到想找的哪個 tuple
? ? ? ? ? ??
? ? ? ? ? ? 注意 slot 存的是 offset
? ? ? ? ? ??
? ? ? ? ? ??
? ? ? ? ? ? 而填充 page 的方式是
? ? ? ? ? ? - 從前往后對 slot 數(shù)組進行填充
? ? ? ? ? ? - 從后往前對數(shù)據(jù)進行填充
? ? ? ? ? ??
? ? ? ? ? ? 什么是 page 已滿，指的是數(shù)據(jù)占用了該 page 的一半以上的大小，再也無法存入任何信息了
? ? ? ? ? ??
? ? ? ? ? ? 當(dāng)然也可以用一種 Postgres 中的 vaccum 的操作來整理數(shù)據(jù)庫，或者使用壓縮，也可以對數(shù)據(jù)庫進行掃描并整理碎片
? ? ? ? ? ??
? ? ? ? ? ? 對于這種例子來講，肯定是不能把視頻存在數(shù)據(jù)庫里面的，因為單個 page 根本放不下它。
? ? ? ? ? ??
? ? ? ? ? ? 一般來講，要存 tuple 不應(yīng)該分散地存在多個 page 上，因為維護元數(shù)據(jù)很麻煩。最好是當(dāng)我們想要去訪問這個 tuple 的時候，它就在這個 page 上。
? ? ? ? ? ??
? ? ? ? ? ? 為什么需要這么組織結(jié)構(gòu)呢？
? ? ? ? ? ??
? ? ? ? ? ? 因為不管是將數(shù)據(jù)庫文件中的 page 移動到磁盤還是網(wǎng)絡(luò)上，系統(tǒng)的其他部分都不會關(guān)心這個 page 實際移動到了哪里，因為有 page ID 的存在，就可以通過 Page 目錄來找到它實際所保存的位置，而這些 indirection 層避免了這些位置的更新會傳播到系統(tǒng)的其他上層部分。比如某些 GC 算法，只需要保證對象間的引用關(guān)系就好，對象存在內(nèi)存的哪個位置會隨著 GC 的進行而變化，page ID 有有點像是在維護這個引用關(guān)系
? ? ? ? ? ??
? ? ? ? 2. 日志結(jié)構(gòu)的組織方式
? ? ? ? ? ? // Todo:
? ? ? ? ? ? 主要這里 3-1 沒有講到
- Tuple 層? ? ? ??
? ? > 注: 課程時間不夠，這里是簡略版本
? ??
? ??
? ? 一個 tuple 基本上就是一串字節(jié)，數(shù)據(jù)庫的工作就是再次解釋這些字節(jié)的實際含義
? ??
? ? - Tuple 頭
? ??
? ? ? ??
? ? ? ? 通常沒必要將該 tuple 的元數(shù)據(jù)保存在這個 tuple 里面，因為更高級的元數(shù)據(jù)信息保存在這個 tuple 對應(yīng)的 page 中，但可以可以放在 catalog page 里
? ? - Tuple Data
? ??
? ? ? ??
? ? ? ? 通常大部分?jǐn)?shù)據(jù)庫系統(tǒng)會按照它們創(chuàng)建時的順尋進行存儲，我們知道在關(guān)系模型中沒必要這么做，但是大部分系統(tǒng)都做了
? ? ? ??
? ? - Denormalized Tuple Data
? ??
? ? ? ??
? ? ? ? 如果來自不同表的數(shù)據(jù)保存在同一個 page 中，會發(fā)生什么問題？
? ? ? ? 注意這里大部分?jǐn)?shù)據(jù)庫系統(tǒng)都不會這么做，因為如果想讓 page 變得獨立，那么也就不應(yīng)該去保存一大堆關(guān)于不同表的額外的元數(shù)據(jù)。當(dāng)對表進行反范式化設(shè)計或者對表進行 prejoin 時，就會出現(xiàn)上述圖中的情況，也就是數(shù)據(jù)冗余，一個 page 中存在多個表數(shù)據(jù)，更新、刪除、或者壓縮都要對多個表進行處理
? ? ? ??
? ? ? ? 而數(shù)據(jù)庫規(guī)范基本上就是講如何講數(shù)據(jù)庫拆分到不同的表中（使用外鍵時就自然拆分了）
? ? ? ??
? ? ? ? 下面是一個反范式化的處理例子，將 bar 的 tuple 直接內(nèi)嵌在 foo 的 tuple 中
? ? ? ??
? ? ? ? 因為每個 bar 表中的 tuple 復(fù)制了 a 屬性，如果將它打包進 foo 表的 tuple 中，就沒必要重復(fù)記錄這些數(shù)據(jù)了，foo 表所擁有的這些列對其他表來說是獨一無二的，就像是 prejoin 一樣，將 tuple 彼此包裝在一起。這樣，應(yīng)用程序依然覺得，這個 db 里面有兩張單獨的表，但在 db 內(nèi)部，page 實際上會將它們合并在一起
? ? ? ??
? ? ? ??
? ? ? ??
? ? ? ? 但這并不是什么新鮮東西，早在 1970 年代，IBM 在發(fā)明它們第一個關(guān)系型數(shù)據(jù)庫 System R 的時候，就引入了這個概念
? ? ? ??
? ? ? ? 然而當(dāng) IBM 做出了 DB2 之后，這個方式就被廢棄掉了，因為維護它很操蛋
? ? ? ??
? ? ? ? System R 是 IBM 發(fā)布的第一個關(guān)系型數(shù)據(jù)庫，但 IBM 并沒有將它商業(yè)化，也沒有賣掉，10 多年之后，IBM 抽取了 System R 中的部分代碼，做出了 DB2?
? ? ? ??
? ? ? ? 實際上在更現(xiàn)代的數(shù)據(jù)庫系統(tǒng)中也出現(xiàn)了這種反范式化的設(shè)計
? ? ? ??
? ? ? ??
? ? ? ? 1. G 家的 Cloud Spanner，如果你定義了一個 Protobuf API，那么你就可以將兩張不同表的數(shù)據(jù)合并在同一個 tuple 中
? ? ? ? 2. 10 年前有一個叫 Akiban 的初創(chuàng)公司，他們把他們的存儲引擎賣給了 MySQL，MySQL 就可以做到這種反范式化的操作。然后他們被 Foundation DB 收購，之后 Foundation DB 又被蘋果收購
? ? ? ? 3. 一些文檔型數(shù)據(jù)庫或者 JSON 數(shù)據(jù)庫也能做到。比如你在定義你的 JSON document 時，就可以預(yù)先對相關(guān)屬性進行 join 操作
- 記錄 ID? ? ? ??
? ??
? ? 保存元數(shù)據(jù)的大小
? ??
? ? - PostgreSQL CTID（4 bytes）
? ? - SQLite ROWID（8 bytes）
? ? - Oracle ROWID（10 bytes）
- 結(jié)論
