单机存储系统
單機(jī)存儲(chǔ)系統(tǒng)就是單機(jī)存儲(chǔ)引擎的一種封裝，而單機(jī)存儲(chǔ)引擎分為：
- 哈希存儲(chǔ)引擎
- B樹(shù)存儲(chǔ)引擎
- LMS樹(shù)存儲(chǔ)引擎
哈希存儲(chǔ)引擎
Bitcask是一個(gè)基于哈希表結(jié)構(gòu)的鍵值存儲(chǔ)結(jié)構(gòu)。
它的特點(diǎn)是寫(xiě)時(shí)追加，也就是說(shuō)它每次在文件中只會(huì)追加數(shù)據(jù)而不會(huì)修改，所以文件大小超過(guò)限制時(shí)，會(huì)新建一個(gè)活躍數(shù)據(jù)文件，而達(dá)到大小限制的文件就叫作老數(shù)據(jù)文件。
Bitcask的數(shù)據(jù)結(jié)構(gòu)：
內(nèi)存中哈希索引表的數(shù)據(jù)結(jié)構(gòu)：
- 讀取操作：用內(nèi)存中的哈希索引表的數(shù)據(jù)結(jié)構(gòu)，通過(guò)主鍵找到對(duì)應(yīng)的文件編號(hào)，value長(zhǎng)度和位置，就可以在活躍數(shù)據(jù)文件找到對(duì)應(yīng)item（每一個(gè)item都是Bitcask數(shù)據(jù)結(jié)構(gòu)），得到value值。
- 刪除：原item的value中存入刪除標(biāo)記。
- 新增：直接添加一條item條目。
- 更新：原item不變，跟新增操作一樣。
定期合并：Bitcask系統(tǒng)中的記錄刪除后者更新后都會(huì)讓原來(lái)的數(shù)據(jù)變?yōu)槔募?#xff0c;所以要進(jìn)行定期合并，對(duì)同一個(gè)key只保留最新的一個(gè)。
快速恢復(fù)：哈希索引表存在內(nèi)存中，一旦斷電，重建這個(gè)哈希索引表需要掃一遍磁盤(pán)中的數(shù)據(jù)文件，為了加快重建速度，Bitcask通過(guò)索引文件來(lái)提高重建hash表的速度。索引文件其實(shí)就是內(nèi)存中的哈希索引表轉(zhuǎn)儲(chǔ)到磁盤(pán)生成的結(jié)果文件。
B樹(shù)存儲(chǔ)引擎
Mysql的Innodb是按照頁(yè)來(lái)組織數(shù)據(jù)的，也就是說(shuō)內(nèi)存中存儲(chǔ)的是頁(yè)，對(duì)應(yīng)B+樹(shù)的一個(gè)節(jié)點(diǎn)。
- 查詢(xún)：從B+樹(shù)的根節(jié)點(diǎn)開(kāi)始進(jìn)行二分查找知道找到葉子節(jié)點(diǎn)，而且每次讀取一個(gè)節(jié)點(diǎn)，如果頁(yè)不在內(nèi)存中，則需要從磁盤(pán)中讀取出來(lái)并把對(duì)應(yīng)的頁(yè)緩存起來(lái)。
- 修改：首先需要記錄提交日志，然后再修改內(nèi)存中的B+樹(shù)。內(nèi)存中修改的頁(yè)超過(guò)一定比率，就會(huì)將頁(yè)面刷新到磁盤(pán)中持久化。
緩存區(qū)管理
基本的LRU：將近期訪問(wèn)的item存到一個(gè)鏈表中，每次新訪問(wèn)的item加到鏈表頭部，同時(shí)淘汰掉鏈表尾部item（即最近最少訪問(wèn)到的item被淘汰掉）。
存在的問(wèn)題1：如每次訪問(wèn)item都要更新一次LRU鏈表，都需要對(duì)整個(gè)LRU加鎖
存在的問(wèn)題2：若果一次查詢(xún)中掃描了大量的item數(shù)據(jù)，則會(huì)導(dǎo)致緩存池LRU鏈表中的大部分或者全部數(shù)據(jù)被替換掉，從而污染緩存池。
改進(jìn)的LRU:
對(duì)問(wèn)題1：犧牲精度來(lái)減小鎖粒度
分段LRU鏈表（如Mysql）：將LRU鏈表分為前后兩部分，如果訪問(wèn)的item在前部分則不進(jìn)行任何操作，即不用將該item移動(dòng)到 頭部。只有在后半部分時(shí)才加鎖，移動(dòng)到頭部。
計(jì)時(shí)LRU鏈表（如memcached）:鏈表的每個(gè)節(jié)點(diǎn)item都存儲(chǔ)一個(gè)最近訪問(wèn)時(shí)間，每次訪問(wèn)該item時(shí)，只有當(dāng)距離上次訪問(wèn)時(shí)間 操作某個(gè)設(shè)定值才會(huì)移動(dòng)該item到鏈表頭部。
塊LRU鏈表（如OceanBase）：鏈表的每個(gè)節(jié)點(diǎn)不是單獨(dú)的一個(gè)item數(shù)據(jù)記錄而是以塊比如2MB的內(nèi)存塊。每次移動(dòng)或者淘汰都 以塊為基本單位。每個(gè)塊保存一個(gè)訪問(wèn)計(jì)數(shù)和最近訪問(wèn)時(shí)間，每次訪問(wèn)塊中的任何一個(gè)item都會(huì)將該塊的訪問(wèn)計(jì)數(shù)加1，當(dāng)該塊的訪問(wèn)計(jì)數(shù)達(dá)到某個(gè)設(shè)定值（比如所有塊的平均訪問(wèn)次數(shù)）時(shí)就更新該塊的最近訪問(wèn)時(shí)間。按塊的最近訪問(wèn)時(shí)間來(lái)淘汰塊。
對(duì)問(wèn)題2：分級(jí)緩存
LIRS算法（如MySQL InnoDB）：LIRS將數(shù)據(jù)分為兩部分：LIR（Low Inner-reference Recency）和HIR（High Inner-reference Recency），其中，LIR中的 數(shù)據(jù)是熱點(diǎn)，在較短的時(shí)間內(nèi)被訪問(wèn)了至少兩次。LIRS可以看成是一種分級(jí)思想：第一級(jí)是HIR，第二級(jí)是LIR，數(shù)據(jù)先進(jìn)入到第一級(jí)，當(dāng)數(shù)據(jù)在較短的時(shí)間內(nèi)被訪問(wèn)兩次時(shí)成為熱點(diǎn)數(shù)據(jù)則進(jìn)入LIR，HIR和LIR內(nèi)部都采用LRU策略。這樣，LIR中的數(shù)據(jù)比較穩(wěn)定。類(lèi)似的，如可以實(shí)現(xiàn)兩級(jí)cache，cache元素先進(jìn)入第一級(jí)cache，當(dāng)訪問(wèn)頻率達(dá)到一定值（比如2）時(shí)升級(jí)到第二級(jí)，第一級(jí)和第二級(jí)均內(nèi)部采用LRU進(jìn)行替換。
LSM樹(shù)存儲(chǔ)引擎
LSM的基本思想就是將的數(shù)據(jù)的修改增量保存在內(nèi)存中，當(dāng)內(nèi)存達(dá)到大小限制后將這些增量數(shù)據(jù)批量寫(xiě)入磁盤(pán)，讀取時(shí)需要合并磁盤(pán)中的歷史數(shù)據(jù)和內(nèi)存中的增量數(shù)據(jù)。
- 當(dāng)應(yīng)用寫(xiě)入一條記錄時(shí)，LevelDB會(huì)首先將修改操作寫(xiě)入到操作日志文件，成功后再將修改操作應(yīng)用到MemTable，這樣就完成了寫(xiě)入操作。
- 當(dāng)MemTable占用的內(nèi)存達(dá)到一個(gè)上限值后，需要將內(nèi)存的數(shù)據(jù)轉(zhuǎn)儲(chǔ)到外存文件中。LevelDB會(huì)將原先的MemTable凍結(jié)成為不可變MemTable，并生成一個(gè)新的MemTable。新到來(lái)的數(shù)據(jù)被記入新的操作日志文件和新生成的MemTable中。
- LevelDB后臺(tái)線(xiàn)程會(huì)將不可變MemTable的數(shù)據(jù)排序后轉(zhuǎn)儲(chǔ)到磁盤(pán)，形成一個(gè)新的SSTable文件，這個(gè)操作稱(chēng)為minor Compaction。
SSTable中的文件是按照記錄的主鍵排序的，每個(gè)文件有最小的主鍵和最大的主鍵。 - 當(dāng)某個(gè)層級(jí)下的SSTable文件數(shù)目超過(guò)一定設(shè)置值后，levelDB會(huì)從這個(gè)層級(jí)中選擇SSTable文件，將其和高一層級(jí)的SSTable文件合并，這就是major compaction。
- LevelDB的清單文件記錄了所有元數(shù)據(jù)，包括屬于哪個(gè)層級(jí)、文件名稱(chēng)、最小主鍵和最大主鍵，它會(huì)隨著Compaction進(jìn)行而重新生成新的清單文件，所以需要當(dāng)前文件來(lái)記錄了當(dāng)前使用的清單文件名。
LevelDB寫(xiě)入操作很簡(jiǎn)單，但是讀取操作比較復(fù)雜，需要先查看內(nèi)存中的MemTable，然后在不可變MemTable中查找，接下來(lái)再?gòu)腟STable文件中讀取。
總結(jié)
- 上一篇： 网易2019实习生Java编程题
- 下一篇： 数据库存储模型-数据存储