1 追加式數(shù)據(jù)庫
1.1 基本數(shù)據(jù)操作
1）set：在文件末尾追加一個(gè) KV 對。
2）get：匹配所有 Key瞭恰，返回最后（也即最新）一條 KV 對中的 Value。時(shí)間復(fù)雜度o（n）。
1.2 優(yōu)缺點(diǎn)
優(yōu)勢：順序?qū)懘疟P张弛，性能不錯(cuò)绸罗。
缺點(diǎn)：查找性能差意推。
適合頻繁寫，讀少的數(shù)據(jù)珊蟀。
1.3 建立哈希索引菊值，加快讀速度
1.3.1 哈希索引
把value寫到磁盤，把key和value在磁盤偏移記錄到內(nèi)存育灸。
（這里如何確定磁盤value間的數(shù)據(jù)邊界呢腻窒？采用分隔符或者先記錄長度再記錄數(shù)據(jù)的形式）
1.3.2 優(yōu)缺點(diǎn)
優(yōu)點(diǎn)：仍然是順序?qū)懘疟P，性能好磅崭。
讀數(shù)據(jù)儿子，只需要根據(jù)磁盤偏移進(jìn)行一次IO，性能不錯(cuò)砸喻。
缺點(diǎn)：磁盤資源耗盡柔逼。
適合頻繁讀寫的場景。
1.3.3 磁盤壓縮
1）當(dāng)寫入數(shù)據(jù)達(dá)到一定規(guī)模后割岛，進(jìn)行數(shù)據(jù)分割即寫入到新的文件中愉适。我們把每個(gè)文件叫做一個(gè)段。
2）段內(nèi)數(shù)據(jù)可以進(jìn)行壓縮（只保留最新的key數(shù)據(jù)）癣漆。段之間也可以進(jìn)行合并儡毕。
3）每個(gè)段都有自己的內(nèi)存哈希表。讀請求一定從最新的段開始查找KEY ，最新的段沒有指定KEY腰湾，查找次新的段雷恃。
1.4 一些其他問題
- 文件格式。對于日志來說费坊，CSV 不是一種緊湊的數(shù)據(jù)格式倒槐，有很多空間浪費(fèi)。比如附井，可以用 length + record bytes 讨越。
- 記錄刪除。一般是寫一個(gè)特殊標(biāo)記（比如墓碑記錄永毅，tombstone）以表示該記錄已刪除把跨。之后 compact 時(shí)真正刪除即可。
- 宕機(jī)恢復(fù)沼死。在機(jī)器重啟時(shí)着逐，內(nèi)存中的哈希索引將會丟失。當(dāng)然意蛀，可以全盤掃描以重建耸别，但通常一個(gè)小優(yōu)化是，對于每個(gè) segment file县钥， 將其索引條目和數(shù)據(jù)文件一塊持久化秀姐，重啟時(shí)只需加載索引條目即可。
- 記錄寫壞若贮、少寫省有。系統(tǒng)任何時(shí)候都有可能宕機(jī)，由此會造成記錄寫壞谴麦、少寫蠢沿。為了識別錯(cuò)誤記錄，我們需要增加一些校驗(yàn)字段细移，以識別并跳過這種數(shù)據(jù)搏予。為了跳過寫了部分的數(shù)據(jù)熊锭，還要用一些特殊字符來標(biāo)識記錄間的邊界弧轧。
- 并發(fā)控制。由于只有一個(gè)活動(dòng)（追加）文件碗殷，因此寫只有一個(gè)天然并發(fā)度精绎。但其他的文件都是不可變的（compact 時(shí)會讀取然后生成新的），因此讀取和緊縮可以并發(fā)執(zhí)行锌妻。
順序?qū)懭牒驮馗邢啾却耍瑑?yōu)勢有：
- 以順序?qū)懘骐S機(jī)寫。對于磁盤和 SSD，順序?qū)懚家入S機(jī)寫快幾個(gè)數(shù)量級搁吓。
- 簡易的并發(fā)控制原茅。由于大部分的文件都是不可變（immutable）的，因此更容易做并發(fā)讀取和緊縮堕仔。也不用擔(dān)心原地更新會造成新老數(shù)據(jù)交替擂橘。
- 更少的內(nèi)部碎片。每次緊縮會將垃圾完全擠出摩骨。但是原地更新就會在 page 中留下一些不可用空間通贞。
當(dāng)然，基于內(nèi)存的哈希索引也有其局限：
- 所有 Key 必須放內(nèi)存恼五。一旦 Key 的數(shù)據(jù)量超過內(nèi)存大小昌罩，這種方案便不再 work。當(dāng)然你可以設(shè)計(jì)基于磁盤的哈希表灾馒，但那又會帶來大量的隨機(jī)寫茎用。
- 不支持范圍查詢。由于 key 是無序的你虹，要進(jìn)行范圍查詢必須全表掃描绘搞。
2 按KEY排序的kv存儲表（SSTable，LSM-Tree）
上一節(jié)的存儲結(jié)構(gòu)傅物，key如果比較多會把內(nèi)存耗盡夯辖。需要一種更加緊密的key存儲方式，來容納更多的key董饰。
2.1 基本操作
在段文件中蒿褂，按照key排序存儲，每個(gè)鍵在一個(gè)段文件中只出現(xiàn)一次卒暂。（這就不是順序?qū)懭肓俗乃ǎ總€(gè)段文件不應(yīng)該太大，因?yàn)閷懭胧莖（n）的時(shí)間復(fù)雜度了）
key在內(nèi)存中是順序表存儲而不是存在hash表中也祠。
2.2 優(yōu)點(diǎn)
2.2.1 段合并更高效
每個(gè)段都是按照key排序的昙楚，合并段本質(zhì)就是多路歸并排序。
2.2.2 稀疏索引诈嘿，節(jié)省能存空間
把段文件分成多個(gè)數(shù)據(jù)塊堪旧，給數(shù)據(jù)塊的頭部建立順序表索引。
2.2.3 數(shù)據(jù)壓縮
相鄰 Key 共享前綴奖亚，既然每次都要批量取淳梦，那正好一組 key batch 到一塊，稱為 block昔字，且只記錄 block 的索引爆袍。
如圖，壓縮hand前綴
2.3 提高寫入性能
每個(gè)寫請求都寫入段文件，時(shí)間復(fù)雜度為o（n）陨囊。這很慢弦疮，比較直觀的想法是，攢夠一批數(shù)據(jù)蜘醋，寫入段文件挂捅。
2.3.1 寫入
內(nèi)存中維護(hù)平衡樹（插入，刪除堂湖，查找闲先，時(shí)間復(fù)雜度logn），這個(gè)樹叫做內(nèi)存表无蜂。當(dāng)內(nèi)存表達(dá)到某個(gè)閾值大小伺糠，寫入磁盤，遍歷平衡樹實(shí)現(xiàn)順序?qū)懭氪疟P斥季，高效??训桶。
2.3.2 讀
先看鍵是否在內(nèi)存表，再按從新到舊的順序查找段文件索引酣倾。
2.3.3 周期性段合并和壓縮數(shù)據(jù)
2.3.4 crash-safe
為了避免斷電造成內(nèi)存表數(shù)據(jù)丟失舵揭。引入一個(gè)寫操作追加日志，實(shí)現(xiàn)crash-safe（變隨機(jī)寫為順序?qū)懀?mysql和redis都有類似的設(shè)計(jì)）躁锡。
