- 課程目標(biāo)

- 上節(jié)課回顧

?

? ??

? ? 畫紅線的部分

? ??

? ? 1. 想要能夠去支持超出我們所擁有的內(nèi)存容量大小的數(shù)據(jù)庫

? ? 2. 最小化在磁盤上執(zhí)行查詢時速度緩慢帶來的影響

? ? - 數(shù)據(jù)庫 Workloads

? ??

? ? ? ??

? ? ? ? HTAP（混合事務(wù)分析處理 Hybrid Transaction Analytical Processsing），是幾年前 Gartner 發(fā)明的一個新流行詞，它所描述的是既做 OLTP 又做 OLAP 的數(shù)據(jù)庫系統(tǒng)

? ??

? ? - Bifurcated Environment

? ??

? ? ? ??

? ? ? ? 一般數(shù)據(jù)庫的標(biāo)準(zhǔn)配置是這樣的

? ? ? ??

? ? ? ? 1. 前端 OLTP 數(shù)據(jù)庫

? ? ? ? 2. 后端 OLAP 大型數(shù)據(jù)倉庫（back-end data warehouse）

? ? ? ??

? ? ? ? 這兩者有時候被稱為 Data Silo，即數(shù)據(jù)孤島，數(shù)據(jù)存儲相互獨立，彼此之間不會真的交流

? ? ? ??

? ? ? ??

? ? ? ? 然后就可以進(jìn)行 ETL（Extract Transform Load） 的操作，即將業(yè)務(wù)系統(tǒng)的數(shù)據(jù)經(jīng)過抽取、清洗、轉(zhuǎn)換之后加載到數(shù)據(jù)倉庫的過程

? ? ? ??

? ? ? ? 以 Zynga 這家游戲公司為例，Zynga 收購了很多游戲初創(chuàng)公司，比如 FarmVille，它買下這些公司時，會去運行他們自己的前端 OLTP 數(shù)據(jù)庫，只有他們將這些數(shù)據(jù)放入他們的后端大型倉庫時，他們才能更高地分析出怎么做才能讓你們在 FarmVille 上買東西

? ? ? ??

? ? ? ? 等后端 OLAP 數(shù)據(jù)倉庫拿到分析后的信息數(shù)據(jù)后，就推到前端 OLTP 數(shù)據(jù)庫中，并對外暴露

? ? ? ??

? ? ? ??

? ? ? ? 所以 HTAP 基本上在做一些平常只能在 OLAP 端所做的，可以直接在前端的 Data Silo 里面做這些，并且不用等數(shù)據(jù)傳回到后端數(shù)據(jù)倉庫了

? ? ? ??

? ? ? ? 這可以用 MySQL、PostgreSQL、mongoDB 來做前端數(shù)據(jù)庫，可以用 Hadoop、Spark、Greenplum、Vertica 來做后端數(shù)據(jù)倉庫

? ??

? ? - 數(shù)據(jù)庫存儲? ??

? ??

? ? ? ??

? ? ? ? 1. 空間管理

? ? ? ? ? ? 這里指的是在哪里將數(shù)據(jù)寫入磁盤

? ? ? ? 2. 時間管理

? ? ? ? ? ? 這里指的是什么時候?qū)?pages 讀入內(nèi)存

? ??

? ? - 面向磁盤的 DBMS

? ??

? ? ? ??

? ? ? ? 如果執(zhí)行引擎在請求 page 時，內(nèi)存中沒有足夠的空余來容納我們需要的那個 page，這個時候就必須要決定哪個 page 進(jìn)行寫出操作，即 "remove"，而這正是 Buffer 池要解決的問題

? ? ? ??

? ? ? ? 系統(tǒng)的其他部分無須知道或者關(guān)系哪些東西在內(nèi)存里，哪些東西不在，它只會等它需要拿到的東西，然后返回一個指針給到執(zhí)行引擎

? ??

- Buffer 池的組織? ??

? ??

? ? Buffer 池需要我們在數(shù)據(jù)庫系統(tǒng)內(nèi)部分配一塊很大的內(nèi)存，就是調(diào)用 malloc，拿到一些內(nèi)存塊，并將從磁盤中讀取到的所有的 pages 都放到這個里面去。注意這段內(nèi)存完全是由數(shù)據(jù)庫系統(tǒng)來控制，而不是交給操作系統(tǒng)來做。

? ??

? ? 然后，這段內(nèi)存區(qū)域被分成一個個固定大小的 chunk，它被稱為 frame，frame 對應(yīng)的是之前提到的 slot（slot 存儲的雖然是對應(yīng) tuple 的 offset，但對外來看，相當(dāng)于指代了一段存儲區(qū)域），即 Buffer 池內(nèi)存區(qū)域中的區(qū)塊或者是 chunk，frame 里存放的是 page

? ??

? ? 當(dāng)數(shù)據(jù)庫系統(tǒng)發(fā)出一個請求 page 的請求，會發(fā)生啥呢？

? ??

? ??

? ? 首先會去看 Buffer 池中有沒有這個 page，如果沒有就拷貝一份到內(nèi)存中，也就是其中一個 frame

? ??

? ??

? ? 注意 Buffer 池中 page 的順序可能和磁盤上的順序不一致，所以在此之上，就需要一個額外的 indirection 層，如果需要某個特定的 page，只要通過這個 indirection 層就能知道這個 page 在哪個 frame 中

? ??

- Buffer 池元數(shù)據(jù)? ??

? ??

? ? page 表其實就是一個 hash 表，用來跟蹤在內(nèi)存中有哪些 page，可以通過 page 表和 page ID 找到在 frame 中對應(yīng)的那個 page

? ??

? ? 數(shù)據(jù)庫系統(tǒng)必須維護一些額外的元數(shù)據(jù)，以此來跟蹤當(dāng)前 Buffer 池中的 page 發(fā)生了什么

? ??

? ? 要跟蹤的有倆

? ??

? ? 1. Dirty Flag

? ? ? ? 這個 flag 表示的是，從磁盤讀取到這個 page 后，這個 page 是否被修改過，比如查詢或者事務(wù)對其修改過

? ? 2. Pin/引用計數(shù)

? ? ? ? 這個表示 想要使用該 page 的當(dāng)前線程數(shù)量/正在對該 page 進(jìn)行的 查詢 的數(shù)量（這里又聯(lián)想到 GC），page 目前還在被強引用，說明此時不應(yīng)該將 page 寫出到磁盤上

? ??

? ??

? ? 比如在上圖的例子中，如果不想讓 page3 從 Buffer 池中移除掉，就把他 Pin 住

? ??

? ??

? ? 如果想要去讀取一個不在當(dāng)前內(nèi)存中的 page2，那么就要在這個 page 表中加上一個 latch 鎖，這樣 Buffer 池就可以從磁盤中拿到這個 page2，然后更新 page 表里面指向 page2 的指針。為什么要加鎖？因為同一時間可能有多個線程在跑，資源會有沖突

? ??

? ? 這也解釋了為什么 mmap is suck，因為操作系統(tǒng)不會管你是不是在用 page2，它可能會提前將 page2 寫出到磁盤

? ??

? ??

- Locks vs. Latches? ??

? ??

? ? 以數(shù)據(jù)庫的語義來講，lock 是某種高級邏輯原語（high-level logical primitive），它會去保護數(shù)據(jù)庫中的邏輯內(nèi)容，比如 tuple、表以及數(shù)據(jù)庫，事務(wù)在運行時會去持有這個 lock

? ??

? ? latch 是一種低級保護原語（low-level protection primitive），它用來保護數(shù)據(jù)庫系統(tǒng)內(nèi)部的關(guān)鍵部分，比如物理數(shù)據(jù)結(jié)構(gòu)、內(nèi)存區(qū)域

? ??

? ? 在執(zhí)行操作 （operation）期間，數(shù)據(jù)庫會持有這些 latch，用來保護某些東西

? ??

? ? 如果在執(zhí)行操作時，沒能拿到對應(yīng)的 latch，那么這個操作就會被中止，同時也不需要關(guān)心回滾問題

? ??

? ? 在操作系統(tǒng)的語義里面，latch 就相當(dāng)于 mutex，mutex 也被用來保護一些關(guān)鍵內(nèi)容，但是在 latch 中所使用的 mutex 實現(xiàn)其實是 spin lock（自旋鎖）

? ??

- Page 表 vs. Page 目錄? ??

? ??

? ? Page 表是內(nèi)存中的內(nèi)部映射，它將 page ID 映射到它們在 Buffer 池中 frame 的位置，這個沒必要做持久化，但必須要保證它是線程安全的。因為如果系統(tǒng)崩潰了，恢復(fù)后 Buffer 池里面的東西丟了就丟了，對數(shù)據(jù)庫而言沒有影響

? ??

? ? Page 目錄是用來找到 page 在數(shù)據(jù)庫文件中的位置，對 Page 目錄做出的所有改變都必須持久化，它們必須要被寫到磁盤上。因為如果系統(tǒng)崩潰了，恢復(fù)后我們需要知道在哪里可以找到之前的 page

? ??

- Buffer 池內(nèi)存分配策略? ??

? ??

? ? 1. 全局策略

? ? ? ? 即這個策略能使整個要試著執(zhí)行的 workload 都受益，比如查看所有運行在該系統(tǒng)上的查詢/事務(wù)，選擇哪些內(nèi)容應(yīng)該存儲到內(nèi)存

? ? ? ??

? ? 2. 局部策略

? ? ? ? 針對每個單個查詢/事務(wù)，讓其進(jìn)行得更快的最佳方法

? ??

? ? 大多數(shù)數(shù)據(jù)庫系統(tǒng)可能會試著盡量同時采取全局和局部優(yōu)化策略

? ??

? ? - Buffer 池優(yōu)化

? ??

? ? ? ??

? ? ? ? 1. 多 Buffer 池

? ? ? ??

? ? ? ??

? ? ? ? ? ? 可以在每個 Buffer 池上使用局部策略，這樣就可以為放入的數(shù)據(jù)進(jìn)行量身定制，比如讓每個表都有一個 Buffer 池，當(dāng)處于以下情況時，

? ? ? ? ? ??

? ? ? ? ? ? - 在某些表中可能會進(jìn)行一系列的循環(huán)掃描

? ? ? ? ? ? - 在某些表中可能會進(jìn)行索引查詢

? ? ? ? ? ? - 某個時刻需要跳轉(zhuǎn)到某個 page 上（表內(nèi)查詢）

? ? ? ? ? ??

? ? ? ? ? ? 就可以根據(jù)這 2 種?workload 類型來決定使用不同的替換策略，比如讓一個 Buffer 池處理索引，另一個 Buffer 池處理表

? ? ? ? ? ??

? ? ? ? ? ? 這么做同時也會減少那些嘗試訪問 Buffer 池的不同線程之間爭搶 latch 鎖的情況，比如，如果有多個 page 表，那么每條線程就能在同一時間訪問不同的 page 表，因此它們就不會去爭搶這些 latch（這我是有點懷疑的，是不是一定要 page 表的數(shù)量要大于線程數(shù)？？）

? ? ? ? ? ??

? ? ? ? ? ??

? ? ? ? ? ? Oracle、DB2、Sybase、SQL server、Informix 這些全都支持多 Buffer 池， MySQL 的做法是，對于一個給定的 page ID，它會通過 round-robin hash 來判斷這個數(shù)據(jù)在哪，放在哪個 Buffer 池里面。

? ? ? ? ? ??

? ? ? ? ? ??

? ? ? ? ? ? 有 2 種方式來使用這些

? ? ? ? ? ??

? ? ? ? ? ? - Buffer 池通過管理和維護數(shù)據(jù)庫對象（Database Object）的 record ID，來管理數(shù)據(jù)庫對象，即將數(shù)據(jù)庫對象的 record ID 維護到一個列表中，這樣就能根據(jù)每個 ID 找到對應(yīng)的對象條目。通過 record ID 能找到 Object ID、page ID、slot number，通過 Object ID 能找到對應(yīng)的 Buffer 池，通過 page ID 和 slot number 就能找到對應(yīng)的數(shù)據(jù)

? ? ? ? ? ? - 傳入 record ID，通過 hash 來確定數(shù)據(jù)在 Buffer 池中的位置，通過取模來確定在哪個 Buffer 池里

? ? ? ??

? ? ? ??

? ? ? ? 2. Pre-Fetching（預(yù)?。?/p>

? ? ? ??

? ? ? ? ? ??

? ? ? ? ? ? 當(dāng)處理完 page1 后，如果要繼續(xù)請求 page2 或 page3 的數(shù)據(jù)，通過 pre-fetching 的方式，它已經(jīng)在 Buffer 池中了，那么也無序停頓去從磁盤中把相關(guān) page 取出然后寫入到 Buffer 池內(nèi)存中

? ? ? ? ? ??

? ? ? ? ? ? 另外，mmap 也是可以做到 pre-fetching 的

? ? ? ? ? ??

? ? ? ? ? ? 有一個 index game 例子（這個例子主要是講操作系統(tǒng)怎么去做 pre-fetching 的）

? ? ? ? ? ??

? ? ? ? ? ??

? ? ? ? ? ??

? ? ? ? ? ? index-page3 和 index-page5 它們在磁盤上并沒有連續(xù)排列在一起，所以操作系統(tǒng)會嘗試去 pre fetch page2 和 page3，但實際上并不需要 page2，需要的是 page5，但是還沒有 pre fetch 到它。出現(xiàn)這個的原因是操作系統(tǒng)并不知道查詢要去做什么，因為操作系統(tǒng)做的是 索引掃描（像例子中的樹那樣的一個結(jié)構(gòu)，需要 dfs 遍歷），它不像數(shù)據(jù)庫系統(tǒng)那樣做的是 按照順序掃描

? ? ? ? ? ??

? ? ? ? ? ? 而對于 Buffer 池的 pre-fetching 來講，這不是沒有代價的，因為需要跟蹤一些額外的元數(shù)據(jù)

? ? ? ? ? ??

? ? ? ? 3. 掃描共享 scan sharing

? ? ? ??

? ? ? ? ? ??

? ? ? ? ? ? 這個優(yōu)化策略想的是，查詢之間可以利用彼此的結(jié)果，某個查詢可以復(fù)用另一個查詢從磁盤中讀取到的數(shù)據(jù)，也可以將該數(shù)據(jù)用于其他的查詢

? ? ? ? ? ??

? ? ? ? ? ? 但這和結(jié)果緩存（result caching）的方式不同，結(jié)果緩存指的是，當(dāng)運行完全相同的查詢時，計算出了某些結(jié)果，然后將這些結(jié)果緩存起來，遇到相同的查詢時就再展示出來，而不是去重新執(zhí)行這個查詢

? ? ? ? ? ??

? ? ? ? ? ? 而掃描共享的工作方式是，當(dāng)允許將多個查詢附加到一個單個游標(biāo)（這個游標(biāo)指的是上文所說的移動的 Q1 箭頭 →）上，即將這些查詢注冊到這個游標(biāo)數(shù)據(jù)結(jié)構(gòu)管理的一個集合中時，掃描 pages，并將它們放入 Buffer 池中

? ? ? ? ? ??

? ? ? ? ? ? 這有點像是那種 發(fā)布/訂閱 的模式：我想知道你是否拿到了一個新的 page，然后你就可以去通知可能在等待這個 page 的線程，即便這個線程并不是真的要去拿到這個 page 去讀取數(shù)據(jù)?

? ? ? ? ? ??

? ? ? ? ? ??

? ? ? ? ? ? DBMS 開始工作后，如果一個查詢開始了一次掃描，然后它意識到這里有另一個查詢也在做相同的掃描，它就將它自己附加到第一個查詢的游標(biāo)上，當(dāng)這個查詢拿到 page 時，它就通知我們該查詢拿到了這個 page，我們也就可以去訪問它了

? ? ? ? ? ??

? ? ? ? ? ? 所以第二個查詢出現(xiàn)的位置必須被跟蹤到，記錄好這個位置后，拿到數(shù)據(jù)即可返回，然后繼續(xù)走原來剩余的邏輯

? ? ? ? ? ??

? ? ? ? ? ? 知道了第一個查詢結(jié)束時的游標(biāo)位置，如果那里可能還有其他數(shù)據(jù)需要回去讀取，就能直接回到之前那個點上，去獲取剩余的數(shù)據(jù)

? ? ? ? ? ??

? ? ? ? ? ? 這項技術(shù)只有 DB2 和 SQL server 完全支持，而 Oracle 支持一種基本的掃描共享技術(shù)，稱之為游標(biāo)共享（Cursor Sharing），但只有當(dāng)有 2 個查詢在同一時刻執(zhí)行時，它才會有效

? ? ? ? ? ??

? ? ? ? ? ? 兩個相同查詢的例子

? ? ? ? ? ??

? ? ? ? ? ??

? ? ? ? ? ? 假設(shè)第一個查詢 Q1，它要計算 SUM，那么它需要從磁盤中遍歷整個 pages，然后將遍歷的 page 寫出到 Buffer 池中，按照慣例，此時 Buffer 池中已滿，它需要將 page0 移除掉，并替換上 page3

? ? ? ? ? ??

? ? ? ? ? ??

? ? ? ? ? ? 替換成功后，繼續(xù)掃描，但是這個時候，第二個查詢 Q2 出現(xiàn)了，它也想從磁盤中遍歷整個 pages

? ? ? ? ? ??

? ? ? ? ? ??

? ? ? ? ? ? 在沒有掃描共享的情況下，就會出問題，因為此時 Buffer 池已滿，對于 Q2 來講它需要的是 Buffer 池中的 page0，但是剛剛 page0 已經(jīng)被 Buffer 池扔回到磁盤里面去了，那么 Q2 這個查詢就 gg 了

? ? ? ? ? ??

? ? ? ? ? ? 所以在有掃描共享的情況下，Q2 只需要跳到 Q1 目前所在的位置，并且去讀取 Q1 要讀的相同的數(shù)據(jù)，并計算出 Q2 所找的那部分?jǐn)?shù)據(jù)的結(jié)果

? ? ? ? ? ??

? ? ? ? ? ??

? ? ? ? ? ? 而當(dāng) Q1 結(jié)束時，Q1 的游標(biāo)就消失了，Q2 查詢從頭開始

? ? ? ? ? ??

? ? ? ? ? ??

? ? ? ? ? ? 直到遍歷到 page2，Q2 結(jié)束，這就是 Q2 掃描的路徑

? ? ? ? ? ??

? ? ? ? ? ? 那么每個查詢在讀取數(shù)據(jù)的同時也在計算中間結(jié)果，它們也需要一塊內(nèi)存區(qū)域去存放這些數(shù)據(jù)，而這個內(nèi)存區(qū)域跟這個 Buffer 池是分開的，但通常情況下，這塊內(nèi)存區(qū)域也可以由一個 Buffer 池所支持。但它到底是在一個全局 Buffer 池中還是在這個查詢所私有的 Buffer 池中，還得取決于具體實現(xiàn)

? ? ? ? ? ??

? ? ? ? ? ? 如果在掃描 Buffer 池中的數(shù)據(jù)，并更新中間結(jié)果時，可能會遇上內(nèi)存溢出，為了騰出空間保留中間結(jié)果，會將 Buffer 池中的 page 數(shù)據(jù)刷出到磁盤

? ? ? ? ? ??

? ? ? ? ? ? 通過 locks 可以對一些 pages 進(jìn)行跟蹤管理是否允許對這些 pages 進(jìn)行讀寫，或者時將 locks 應(yīng)用于一些數(shù)據(jù)庫對象上

? ? ? ? ? ??

? ? ? ? ? ? 如果將 Q2 的查詢修改下，讓它去計算 100 條數(shù)據(jù)的平均值

? ? ? ? ? ??

? ? ? ? ? ??

? ? ? ? ? ? 這里并沒有明確說這里要的是否是 前 100 個 tuple 的數(shù)據(jù)。因為現(xiàn)在 Q2 的游標(biāo)是在 page2 處，所以遍歷可以從 page3 開始，然后看下這前 3 個 page 中前 100 個 tuple，計算出結(jié)果。但如果從 page0 開始掃描計算，那可能會得到一個不同的結(jié)果。但因為關(guān)系模型中數(shù)據(jù)庫是無序的，所以根據(jù)關(guān)系模型，這是沒問題的。

? ? ? ? ? ??

? ? ? ? 4. Buffer 池 Bypass

? ? ? ??

? ? ? ? ? ??

? ? ? ? ? ? 思路是，分配一小塊內(nèi)存給執(zhí)行查詢的那條線程，當(dāng)它從磁盤中讀取 page 時，如果該 page 不在 Buffer 池中，那么它將會把這個 page 從磁盤寫入本地內(nèi)存而不是 Buffer 池。當(dāng)查詢完成時，所有的這些 page 都會被丟棄掉。

? ? ? ? ? ??

? ? ? ? ? ? 這么做是為了避免去 page 表中進(jìn)行查詢所帶來的開銷，因為 page 表中對應(yīng)的條目是帶鎖的。

? ? ? ? ? ??

? ? ? ? ? ? 在 Informix 中，這叫做 "Light Scans"，主流數(shù)據(jù)庫都支持它

? ? ? ? ? ??

? ? ? ? ? ? 注意，只有當(dāng)操作的是中間結(jié)果以及查詢掃描的量不大的場景才適用

? ? ? ? ? ??

- 操作系統(tǒng) Page 緩存

? ??

? ? 數(shù)據(jù)庫所有的磁盤操作都是通過最底層的 OS API 來做的，比如 fopen/fread/fwrite 等。默認(rèn)情況下，操作系統(tǒng)會維護它自己的文件系統(tǒng)緩存，比如，當(dāng)從磁盤讀取一個 page 時，OS 會去在它的文件系統(tǒng)緩存中保存一份副本，寫入到 Buffer 池中時，里面就會有另一個副本。但大部分?jǐn)?shù)據(jù)庫系統(tǒng)不會讓 OS 對要讀取的文件進(jìn)行任何緩存處理，因為它們要自己管理內(nèi)存。

? ??

? ? 但是，唯一利用操作系統(tǒng) page 緩存的就是 PostgreSQL，因為從它們工程師的角度看，他們就無須再管理一個額外的緩存，他們依然有他們自己的 Buffer 池，但沒有那么大，這樣就不會去使用系統(tǒng)中所有的內(nèi)存。但像 MySQL 或 Oracle 就會

? ??

? ? htop

? ??

? ??

? ? Mem 部分，橙條代表操作系統(tǒng)的 page 緩存，綠條代表該計算機上運行的進(jìn)程的實際使用物理內(nèi)存

? ??

? ? 使用如下命令清除 OS page 緩存

? ??

? ? ```bash

? ? sync; echo 3 > /proc/sys/vm/drop_caches

? ? ```

? ??

? ??

? ? 可以看到機器使用的總內(nèi)存已經(jīng)下降到 3GB 左右

? ??

? ? 順便，如果 Buffer 池的大小小于要讀取的數(shù)據(jù)庫表的大小的話，那么在 Buffer 池中命中 pages 的數(shù)量，要小于在磁盤中讀取 pages 的數(shù)量

? ??

? ??

? ? 比如上圖中，從磁盤讀取的 27932 >> Buffer 池中的 16316

? ??

? ? 這取決于 Buffer 池的大小，如果把 Buffer 池大小設(shè)置（下圖為修改 PostgreSQL 的配置文件，修改項為 shared_buffers）為比要讀取的數(shù)據(jù)庫表大小還大，那么

? ??

? ??

? ? Buffer 池就會命中（hit）全部的 pages，因為給了數(shù)據(jù)庫系統(tǒng)合適大小的內(nèi)存量，對于這個查詢而言，就沒必要去從磁盤拿 page 了

? ??

? ? hit 的意思是找的東西在 Buffer 池中的數(shù)量

? ??

? ? pg_prewarm 會告訴數(shù)據(jù)庫系統(tǒng)去讀取磁盤上該表的所有數(shù)據(jù)，并將他放入 Buffer 池中（SELECT pg_prewram('testreals')）

? ??

? ? 為什么其他主流數(shù)據(jù)庫系統(tǒng)不依賴操作系統(tǒng) page 緩存呢？因為假設(shè)在 OS page cache 中放入一個 page，而在 Buffer 池中放入該 page 的一個副本，如果這個時候要對 Buffer 池中修改這個 page 部分，那么 OS page cache 和 Buffer 池中的 page 就不再是同一個東西了，OS page cache 中存的就是老 page 數(shù)據(jù)，那么這個數(shù)據(jù)就冗余了。

? ??

? ? 同時，不同數(shù)據(jù)庫支持的操作系統(tǒng)也不一樣，如果都用操作系統(tǒng) page 緩存，那么可能出現(xiàn)性能上的差異，為了保證跨 OS 間的一致性，必須要把這個交給數(shù)據(jù)庫系統(tǒng)本身來管理

? ??

? ? 如果使用的是 Direct IO，這就會告訴操作系統(tǒng)不要去緩存任何東西，這樣數(shù)據(jù)庫系統(tǒng)就始終得跑到磁盤上去獲取數(shù)據(jù)了

? ??

? ? 操作系統(tǒng) page 緩存是磁盤和數(shù)據(jù)庫之間的東西

? ??

- Buffer 替換策略

? ??

? ? 如果現(xiàn)在需要講一個 page 放入內(nèi)存中，但是內(nèi)存里沒有空間放它，這個時候該怎么辦呢？

? ??

? ? 在替換策略中，最重要的就是 準(zhǔn)確性，因為要確保移除的 page 是在未來不太會被用到的那些 page

? ??

? ? 1. 運行某些算法來弄清楚該移除哪個 page 會比讀取 page 時所花的時間要長

? ? 2. 跟蹤大量額外的元數(shù)據(jù)也會帶來開銷，因為可能會出現(xiàn)跟蹤的元數(shù)據(jù)的體積比 page 本身還要大

? ??

? ? 非常高端的、價格很昂貴的企業(yè)級數(shù)據(jù)庫和開源數(shù)據(jù)庫之間有什么區(qū)別呢？

? ??

? ? 1. 高端數(shù)據(jù)庫擁有非常復(fù)雜的替換策略，它們會跟蹤統(tǒng)計 page 的相關(guān)使用數(shù)據(jù)，會嘗試從查詢實際所做的事情中推斷出最好的決策

? ? 2. 開源數(shù)據(jù)庫的某些比較新的系統(tǒng)中，它們在這方面并沒有做的像高端數(shù)據(jù)庫那么好，它們就只能做些簡單版的東西了

? ? - Least-Recently Used（LRU）

? ??

? ? ? ? 一種使用起來超簡單的技術(shù)就是 LRU，即跟蹤一個 page 最后一次被訪問時的時間戳，然后只要看哪個 page 擁有的時間戳是最老的，哪個就應(yīng)該要被移除掉

? ? ? ??

? ? ? ? 那么此時就可以維護一個單獨的數(shù)據(jù)結(jié)構(gòu)，比如隊列，根據(jù) page 的時間戳進(jìn)行排序

? ? - Clock

? ? ? ? 一個 LRU 的近似算法，就是 Clock

? ? ? ??

? ? ? ??

? ? ? ? 在 Clock 中，沒必要去追蹤每個 page 的時間戳，相反，唯一需要去跟蹤的信息是每個 page 的標(biāo)志位（reference bit），它會告訴你自從上次檢查過該 page 后，這個 page 是否被訪問了，所以你需要將你的 page 弄成一個環(huán)形的 Buffer，like a clock。在一圈時鐘這個時間段內(nèi)，如果標(biāo)志位沒有變化，就可以從 Buffer 池中移除這個 page。

? ? ? ??

? ? ? ??

? ? ? ? 假設(shè)某些查詢訪問了 page1，那么此時 page1 的標(biāo)志位會被設(shè)置成 1，注意這里無論多少查詢訪問過這個 page1 多少次，這里的值始終都被設(shè)置為 1，因為標(biāo)志位不是計數(shù)器。

? ? ? ??

? ? ? ? 當(dāng)現(xiàn)在需要去移除 page 時

? ? ? ??

? ? ? ??

? ? ? ? clock 會從 page1 這個地方開始走起來，當(dāng)看到 page1 的標(biāo)志位為 1 時，說明這個 page1 被訪問過，所以不應(yīng)該去移除掉 page1，但現(xiàn)在只是將 page1 的標(biāo)志位設(shè)置成 0。然后走向下一個 page2。此時它發(fā)現(xiàn) page2 的標(biāo)志位是 0，就可以將 page2 移除掉（因為它不是 1，如果是 1 會被先設(shè)置成 0 然后遍歷下一個 page）

? ? ? ??

? ? ? ? 使用 Clock 算法的優(yōu)點是，在移除 page 時，不會精確地移除最近最少使用的那個 page。

? ? ? ??

? ? ? ? 在某些查詢上表現(xiàn)得很好，比如點查詢（point query）時訪問單個東西

? ? ? ??

? ? - 問題

? ??

? ? ? ??

? ? ? ? 但 Clock 和 LRU 都容易受到 sequential flooding 帶來的影響

? ? ? ??

? ? ? ? 這意味著，當(dāng)進(jìn)行讀取每個 page 的特殊掃描時，這可能會污染 page 緩存，可能會將接下來真正要用到的 page 從 Buffer 池中移除掉。因為它掃描并讀取了一堆 page，所有的這些 page 的時間戳都會比實際想要的那個 page 要新。因為要被移除的那些 page 應(yīng)該是 最近 被使用的，而不是 最近最少 被使用的

? ? ? ??

? ? ? ? 例子

? ? ? ??

? ? ? ? Q1 是一個點查詢，它讀取了 page0，并放入了 Buffer 池中

? ? ? ??

? ? ? ??

? ? ? ??

? ? ? ? 接著有另一個遍歷查詢 Q2，它會讀取所有的 page

? ? ? ??

? ? ? ??

? ? ? ? 現(xiàn)在想要在 Buffer 池中給 page3 分配一個空間，如果用的是 LRU，那么它會指出 page0 是 Buffer 池中最近最少使用的 page，那么移除掉 page0，放入 page3

? ? ? ??

? ? ? ??

? ? ? ? 但是在 workload 中，會有不斷地去執(zhí)行類似于 Q1 那樣的查詢

? ? ? ??

? ? ? ??

? ? ? ? > 注意上圖中，在 Disk Pages 上的紅色 Q2 應(yīng)為 Q3

? ? ? ??

? ? ? ? 不斷的執(zhí)行 Q3，它要讀的是 page0。但是之前 page0 已經(jīng)從 Buffer 池中被移除掉了，這樣就 fucked up 了。

? ? ? ??

? ? ? ? 而真正應(yīng)該要被移除的應(yīng)該是 page1 和 page2，因為 Q2 會去讀取更多的數(shù)據(jù)，而其他查詢（Q1 和 Q3）并不會到 Buffer 池中讀取這些數(shù)據(jù)（page 0 之后的 page）

? ? ? ??

? ? - 更好的策略：LRU-K

? ??

? ? ? ??

? ? ? ? 思路是，將最近使用過 1 次的判斷標(biāo)準(zhǔn)擴展為最近使用過 K 次，沒有達(dá)到 K 次訪問的數(shù)據(jù)并不會被緩存。訪問記錄不能無限記錄，當(dāng)訪問次數(shù)達(dá)到 K 次后，將 數(shù)據(jù)索引 從 歷史隊列 移到 緩存隊列 中

? ? ? ??

? ? ? ? 相比于 LRU 比較時間戳，LRU-K 看的是時間戳?xí)r間的間隔，統(tǒng)計哪一個 page 的上一次和下一次的訪問的時間間隔最長，那么哪一個 page 就是最近最少使用的

? ? ? ??

? ? - 更好的策略：本地化（Localization）

? ??

? ? ? ??

? ? ? ? 使用多個 Buffer 池，讓每個查詢本地化，即每個 Buffer 池能對應(yīng)住一個查詢，那么對于單個查詢來講，只會去移除對于這個查詢而言最近最少使用的那個 page，而不是對于整個查詢而言最近最少使用的那個 page

? ? ? ??

? ? - 更好的策略：優(yōu)先級提示（Priority Hints）

? ??

? ? ? ??

? ? ? ? 有索引時，就知道查詢時如何進(jìn)行掃描的，也能知道哪些不同的 page 被訪問了，可以使用這個信息來判斷該移除哪些 page

? ? ? ??

? ? ? ? 例子，假設(shè)有一個 Insert 的操作 Q1，對應(yīng)的表里面有一個全局的計數(shù)器，每次 Insert 時，它就會加 1

? ? ? ??

? ? ? ? > 注意這里索引的存儲結(jié)構(gòu)一般是類似 B+ Tree 的結(jié)構(gòu)

? ? ? ??

? ? ? ??

? ? ? ? 如果根據(jù)這個 id 從小到大排序，意味著遍歷始終是沿著樹的右側(cè)往下走，去拿到這些 page 的

? ? ? ??

? ? ? ??

? ? ? ? 因此這個時候就應(yīng)該提示 Buffer 管理器，這些被紅色框圈起來的 page 就應(yīng)該試著待在內(nèi)存中

? ? ? ??

? ? - 處理 Dirty Pages? ??

? ??

? ? ? ??

? ? ? ? 在 page 上有一個 dirty bit，它表示自從上次它被放入 Buffer 池中后，是否還有查詢對該 page 的內(nèi)容做了修改。

? ? ? ??

? ? ? ? 快的方式：如果一個 page 在 Buffer 池中不是 dirty 的，直接 drop 掉它就好?

? ? ? ? 慢的方式：如果一個 page 在 Buffer 池中是 dirty 的話，在將該空間重新用于新的 page 之前，必須將這個 page 安全地寫回磁盤

? ? ? ??

? ? ? ? 而這是有 trade-off 的，因為一大堆不是 dirty 的 page，可能最近需要用到它，所以直接 drop 掉會帶來后面重新讀取磁盤并寫入內(nèi)存的 I/O 影響。

? ? ? ??

? ? ? ? 而如果不想要 drop 掉這些不是 dirty 的 page，那就要花點代價將 dirty page 從 Buffer 池中移除掉，然后復(fù)用移除掉的這些空間。但是這么做就需要 2 次磁盤 I/O 了，一次 I/O 是用來寫出 dirty page，從 Buffer 池中移除，另一次 I/O 則是讀取那個想要的 page（感覺和上面那個 drop 非 dirty page 的情況差不多）

? ? ? ??

? ? - 后臺寫操作（Background Writing）

? ??

? ? ? ??

? ? ? ? 為了避免 必須立即 將 page 寫出以便在 Buffer 池中釋放可用空間的問題，在數(shù)據(jù)庫系統(tǒng)中有一條執(zhí)行定時任務(wù)的線程，它會在 Buffer 池中找出那些被標(biāo)記為 dirty 的 page，將它們寫出到磁盤上，然后可以將這些 page 標(biāo)記為 clean。那么當(dāng)使用替換策略去決定該移除哪個 page 時，就有一堆 clean 的 page 可以 drop 掉了。

? ? ? ??

? ? ? ? 但是這個操作要小心，因為在該 dirty page 對應(yīng)的修改操作寫入日志之前，我們不希望將這些 dirty page 寫出到磁盤

? ? ? ??

? ? ? ? 同樣的，這也是 mmap 無法做到的事情

? ? ? ??

- 其他內(nèi)存池

? ??

- 結(jié)論

? ??

? ? 這節(jié)課的重點在于我們該如何去管理內(nèi)存并做得比 OS 更好