SSTabble的定義
SStable是排序字符串表，順序存儲(chǔ)key的key-value日志格式扛拨，要求每個(gè)key在合并的段文件中只出現(xiàn)一次（在壓縮的過(guò)程中確保）
SSTable相較于純哈希索引日志段的優(yōu)點(diǎn)
- 合并段更高效误续，支持文件大于可用內(nèi)存
合并方法類似于歸并排序箭养，并發(fā)讀取多個(gè)輸入文件蒿褂，比較每個(gè)文件的第一個(gè)key潘拨，將最小的key拷貝輸出到文件绩衷，重復(fù)這個(gè)過(guò)程蹦魔，最后生成一個(gè)按鍵排序的合并段激率。如果相同的鍵存在多個(gè)value，用最新的value進(jìn)行更新勿决。 - 在文件中查找特定key時(shí)乒躺，不需要在內(nèi)存中保存所有key 的索引，可以根據(jù)SSTable的有序性以及key的偏移量進(jìn)行查找低缩。
比如需要查找key:house嘉冒，在不知道key在段文件中的偏移量的情況下，如果知道home和how的偏移量咆繁，由于鍵是有序的讳推，則house一定在他們兩個(gè)之中。所以任然需要知道一個(gè)內(nèi)存索引來(lái)記錄某些key的偏移玩般，但是索引可以是稀疏的银觅，不必保存所有的key。
ps：如果所有key和value都有固定的大小坏为，則可以在分段文件上使用二分查找究驴，并完全不需要在內(nèi)存中保存索引。但是由于工程中都是可變長(zhǎng)度的匀伏，沒(méi)有索引的話洒忧，很難確定一條log的開(kāi)始和結(jié)束的位置。 - 將多條log保存到一個(gè)塊中够颠，并在寫(xiě)磁盤(pán)之前將其壓縮熙侍，然后稀疏的內(nèi)存索引的每個(gè)條目指向每個(gè)壓縮塊的開(kāi)頭，用以節(jié)省磁盤(pán)空間和I/O帶寬的占用摧找。
SSTable的構(gòu)建
并發(fā)寫(xiě)入可能讓log以任意的順序出現(xiàn)，如何讓數(shù)據(jù)按key排序呢牢硅。
- 在磁盤(pán)上排序（B-Tree）
- 在內(nèi)存上排序（紅黑樹(shù)/AVL樹(shù)）
使用內(nèi)存排序的存儲(chǔ)引擎基本工作流程
- log寫(xiě)入時(shí)蹬耘，將其添加到內(nèi)存中的平衡樹(shù)（內(nèi)存表）數(shù)據(jù)結(jié)構(gòu)中。
- 當(dāng)內(nèi)存大于某個(gè)閾值（通常為若干MB减余，如redis自動(dòng)aof的size是64mb）時(shí)综苔，將其作為SSTable文件寫(xiě)入磁盤(pán)。由于樹(shù)已經(jīng)維護(hù)了按key排序的key-value對(duì)位岔，寫(xiě)磁盤(pán)可以相對(duì)高效如筛。新的SSTable已經(jīng)成為數(shù)據(jù)庫(kù)的最新部分。當(dāng)SSTable寫(xiě)磁盤(pán)的時(shí)候抒抬，寫(xiě)入可以繼續(xù)添加到一個(gè)新的內(nèi)存表實(shí)例杨刨。
- 每次處理讀請(qǐng)求，首先常識(shí)在內(nèi)存表中查找key擦剑，然后是最新的磁盤(pán)段文件妖胀，然后是次新的磁盤(pán)段文件芥颈，以此類推，直到找到目標(biāo)或者為空赚抡。
- 后臺(tái)進(jìn)程周期性地執(zhí)行合并與壓縮的過(guò)程爬坑，來(lái)合并多個(gè)段文件，并丟棄哪些被覆蓋或者被刪除的部分涂臣。
- 如果數(shù)據(jù)庫(kù)崩潰盾计，在內(nèi)存表中但是尚未寫(xiě)入磁盤(pán)的log將會(huì)丟失，為了避免這種情況赁遗，可以在磁盤(pán)上保存單獨(dú)的日志署辉，每個(gè)寫(xiě)入都會(huì)立刻追加到日志。日志文件不需要按鍵排序吼和，它唯一的目的是在崩潰中恢復(fù)內(nèi)存表涨薪，當(dāng)內(nèi)存表寫(xiě)入SSTable時(shí)，相應(yīng)的日志就可以被丟棄了炫乓。
