【技術總結】從Hash索引到LSM樹（一）
前言
數據庫算是軟件應用系統中最常用的一類組件了，不管是一個龐大而復雜的電商系統，還是一個簡單的個人博客，多多少少都會用到數據庫，或是存儲海量的數據，或是存儲簡單的狀態信息。一般地，我們都喜歡將數據庫劃分為關系型數據庫和非關系型數據庫（又稱NoSQL數據庫），前者的典型代表是MySQL數據庫，后者的典型代表是HBase數據庫。不管是關系型，還是非關系型，數據庫都離不開兩個最基本的功能：（1）數據存儲；（2）數據查詢。簡單來說就是，當你把數據丟給數據庫時，它能夠保持下來，并在稍后你想獲取的時候，把數據返回給你。
圍繞著這兩個基本功能，各類數據庫都運用了很多技術手段對其進行了優化，其中最廣為人知的當屬數據庫索引技術。索引是一種數據結構，它在犧牲少量數據存儲（寫）性能的情況下，可以大幅提升數據查詢（讀）性能。索引也有很多種類型，Hash索引算是最簡單高效的一種了，但是由于它自身的限制，在數據庫系統中并不被廣泛使用。當今最常用的索引技術是B/B+樹索引，被廣泛地應用在關系型數據庫中，主要應用于讀多寫少的場景。隨著NoSQL數據庫的興起，LSM（Log-Structured Merged-Tree）樹也逐漸流行，并被Google的BigTable論文所發揚光大。嚴格來說，LSM樹并不算一種傳統意義上的索引，它更像是一種設計思想，主要應用于寫多讀少的場景。
本系列文章，將從實現最簡單的Key-Value數據庫講起，然后針對實現過程中遇到的一些瓶頸，采用上述的索引技術，對數據庫進行優化，以此達到對數據庫的索引技術有一個較為深刻的理解。
最簡單的數據庫
Martin Kleppmann在《Designing Data-Intensive Applications》一書中給出了一個最簡單數據庫的實現：
#!/bin/bash db_set()?{ ??echo?","?>>?database } db_get()?{ ??grep?"^,"?database?|?sed?-e?"s/^,//"?|?tail?-n?1 }
這不到10行的shell代碼實現了一個簡單的Key-Value數據庫。它一共有兩個函數，db_set和db_get，前者對應數據存儲功能，后者對應數據查詢功能。該數據庫采用簡單的文本格式（database文件）進行數據存儲，每條記錄包含了一個鍵值對，key和value之間通過逗號（,）進行分隔。
數據庫的使用方法也很簡單，通過調用db_set key value可以將key及其對應的value存儲到數據庫中；通過db_get key可以得到該key對應的value：
$?db_set?123456?'{"name":"London","attractions":["Big?Ben","London?Eye"]}'? $?db_set?42?'{"name":"San?Francisco","attractions":["Golden?Gate?Bridge"]}' $?db_get?42 {"name":"San?Francisco","attractions":["Golden?Gate?Bridge"]}
透過db_set的實現我們發現，該數據庫每次寫都是直接往database文件中追加記錄，鑒于文件系統順序寫的高效，因此該數據庫的數據寫入具有較高的性能。但是追加寫也意味著，對同一個key進行更新時，其對應的舊的value并不會被覆蓋，這也使得每次調用db_get獲取某個key的value時，總是需要遍歷所有記錄，找到所有符合條件的value，并取其中最新的一個。因此，該數據庫的讀性能是非常低的。
最簡單的數據庫讀寫操作
下面我們采用Java對這個最簡單的數據庫進行重寫：
/** ?*?SimpleKvDb.java ?*?追加寫 ?*?全文件掃描讀 ?*/ public?class?SimpleKvDb?implements?KvDb?{ ????... ????@Override ????public?String?get(String?key)?{ ????????try?(Stream
使用JHM進行壓測結果如下：
Benchmark????????????????????????????????????????????Mode??Cnt??Score???Error??Units SimpleKvDbReadBenchmark.simpleKvDb_get_10000_test????avgt????8??0.631?±?0.033??ms/op?//?讀耗時，1w條記錄 SimpleKvDbReadBenchmark.simpleKvDb_get_100000_test???avgt????8??7.020?±?0.842??ms/op?//?讀耗時，10w條記錄 SimpleKvDbReadBenchmark.simpleKvDb_get_1000000_test??avgt????8??62.562?±?5.466?ms/op?//?讀耗時，100w條記錄 SimpleKvDbWriteBenchmark.simpleKvDb_set_test?????????avgt????8??0.036?±?0.005??ms/op?//?寫耗時
從結果可以看出，該數據庫的實現具有較高的寫性能，但是讀性能很低，而且讀耗時會隨著數據量的增加而線性增長。
那么如何優化SimpleKvDb的讀性能？引入索引技術！
索引（index）是從數據庫中的數據衍生出來的一種數據結構，它并不會對數據造成影響，只會影響數據庫的讀寫性能。對于讀操作，它能快速定位到目的數據，從而極大地提升讀性能；對于寫操作，由于需要增加額外的更新索引操作，因此會略微降低寫性能。
如前言所述，索引也有很多類型，每種索引的特點都各有差別。因此到底要不要采用索引，具體采用哪種索引，需要根據實際的應用場景來決定。
下面，我們將首先采用最簡單高效的Hash索引對SimpleKvDb進行優化。
給數據庫加上Hash索引
考慮到Key-Value數據庫本身就類似于Hash表的這個特點，我們很容易想到如下的索引策略：在內存中維護一個Hash表，記錄每個key對應的記錄在數據文件（如前文所說的database文件）中的字節位移（byte offset）。
對于寫操作，在往數據文件追加記錄后，還需要更新Hash表；對于讀操作，首先通過Hash表確定該key對應記錄在數據文件中的位移，然后通過字節位移快速找到value在數據文件中的位置并讀取，從而避免了全文遍歷這樣的低效行為。
加上索引之后的讀寫操作
給SimpleKvDb加上Hash索引，對應的代碼實現為：
/** ?*?HashIdxKvDb.java ?*?追加寫 ?*?使用Hash索引提升讀性能 ?*/ public?class?HashIdxKvDb?implements?KvDb?{ ????//?數據存儲文件 ????private?final?LogFile?curLog; ????//?索引，value為該key對應的數據在文件中的offset ????private?final?Map
在實現HashIdxKvDb之前，我們將數據存儲文件抽象成了LogFile對象，它的兩個基本方法是append（追加寫記錄）和read（根據offset讀記錄），其中，read函數通過RandomAccessFile的seek方法快速定位到記錄所處的位置，具體實現如下：
//?追加寫的日志文件，存儲數據庫數據 class?LogFile?{ ????//?文件所在路徑 ????private?Path?path; ??... ????//?向日志文件中寫入一行記錄，自動添加換行符 ????//?返回成功寫入的字節大小 ????long?append(String?record)?{ ????????try?{ ????????????record?+=?System.lineSeparator(); ????????????Files.write(path,?record.getBytes(),?StandardOpenOption.APPEND); ????????????return?record.getBytes().length; ????????}?catch?(IOException?e)?{ ????????????e.printStackTrace(); ????????} ????????return?0; ????} ????//?讀取offset為起始位置的一行 ????String?read(long?offset)?{ ????????try?(RandomAccessFile?file?=?new?RandomAccessFile(path.toFile(),?"r"))?{ ????????????file.seek(offset); ????????????return?file.readLine(); ????????}?catch?(IOException?e)?{ ????????????e.printStackTrace(); ????????} ????????return?""; ????} ????... }
使用JHM進行壓測結果如下：
Benchmark??????????????????????????????????????????????Mode??Cnt??Score???Error??Units HashIdxKvDbReadBenchmark.hashIdxKvDb_get_10000_test????avgt????8??0.021?±?0.001??ms/op?//?讀耗時，1w條記錄 HashIdxKvDbReadBenchmark.hashIdxKvDb_get_100000_test???avgt????8??0.021?±?0.001??ms/op?//?讀耗時，10w條記錄 HashIdxKvDbReadBenchmark.hashIdxKvDb_get_1000000_test??avgt????8??0.021?±?0.001??ms/op?//?讀耗時，100w條記錄 HashIdxKvDbWriteBenchmark.hashIdxKvDb_set_test?????????avgt????8??0.038?±?0.005??ms/op?//?寫耗時
從壓測結果可以看出，相比SimpleKvDb，HashIdxKvDb的讀性能有了大幅的提升，而且讀耗時不再隨著數據量的增加而成線性增長；而且寫性能并沒有明顯的下降。
雖然Hash索引實現很簡單，卻是極其的高效，它只需要1次磁盤尋址（seek操作），加上1次磁盤I/O（readLine操作），就能將數據加載出來。如果數據之前已經加載到文件系統緩存里，甚至都不用磁盤I/O。
數據合并——compact
到目前為止，不管是SimpleKvDb，還是HashIdxKvDb，寫操作都是不斷在一個文件中追加數據，這種存儲方式，通常我們稱之為append-only log。
那么，如何才能避免append-only log無休止的一直擴張下去，直到磁盤空間不足呢？
append-only log的一個顯著特點是舊的記錄不會被覆蓋刪除，但是這些數據往往是無用的，因為讀取某個key的value時，數據庫都是取其最新的值。因此，解決該問題的一個思路是把這些無用的記錄清除掉：
（1）當往append-only log追加數據到達一定大小后，另外創建一個新的append-only log進行追加。在這種機制下，數據分散到多個append-only log文件中存儲，我們稱這些log文件為segment file。
（2）保證只有當前的current segment file是可讀可寫，old segment file只讀不寫。
segment file機制
（3）對old segment file進行compact操作——只保留每個key對應的最新記錄，把的老記錄刪除。
單文件compact操作
compact操作往往是在后臺線程中執行，數據庫會將合并的結果寫到一個新的compacted segment file中，這樣在執行compact操作時，就不會影響從old segment file中讀數據的邏輯。等到compact操作完成之后，再把old segment file刪除，后續的讀操作遷移到compacted segment file上。
現在，單個compacted segment file中的key都是唯一的，但是多個compacted segment file之間還是有可能存在重復的key，我們還能夠更近一步，對多個compacted segment file再一次進行compact操作，這樣數據量會再次減少。
多文件compact操作
類似的compact操作可以一層層執行下去，比如，可以對level2 compacted segment file進行compact，生成level3 compacted segment file。但是并不是compact的層次越多越好,具體的compact策略需要結合實際的應用場景進行設計。
給HashIdxKvDb加上compact機制
下面，我們試著給HashIdxKvDb加上compact機制。由于在compact機制下，數據會分散在多個segment file中存儲，因此之前的Hash索引機制不再適用，我們需要給每個segment file都單獨維護一份Hash索引。當然，這樣也比較容易實現，只需要維護一個Hash表，key為segment file，value為該segment file對應的Hash索引。
多segment file下的hash索引
對應的代碼實現如下：
//?多文件哈希索引實現 class?MultiHashIdx?{ ????... ????private?Map
另外，我們還需要在CompactionHashIdxKvDb里分別維護一份old segment file、level1 compacted segment file和level2 compacted segment file集合，并通過ScheduledExecutorService定時對這些集合進行compact操作。
/** ?*?追加寫，當當前segemnt?file到達一定大小后，追加到新到segment?file上。并定時對舊的segment?file進行compact。 ?*?為每個segment?file維持一個哈希索引，提升讀性能 ?*?支持單線程寫，多線程讀 ?*/ public?class?CompactionHashIdxKvDb?implements?KvDb?{ ????... ????//?當前追加寫的segment?file路徑 ????private?LogFile?curLog; ????//?寫old?segment?file集合，會定時對這些文件進行level1?compact合并 ????private?final?Deque
相比于HashIdxKvDb， CompactionHashIdxKvDb?在寫入新的數據之前，需要判斷當前文件大小是否寫滿，如果寫滿了，則需要創建新的LogFile進行追加，并將寫滿后的LogFile歸檔到toCompact隊列中。
@Override public?void?set(String?key,?String?value)?{ ????try?{ ????????//?如果當前LogFile寫滿了，則放到toCompact隊列中，并創建新的LogFile ????????if?(curLog.size()?>=?MAX_LOG_SIZE_BYTE)?{ ????????????String?curPath?=?curLog.path(); ????????????Map
CompactionHashIdxKvDb 的讀操作相對麻煩，因為數據被分散在多個segment file上，所以需要按照如下順序完成數據查找，直到查詢到為止：當前追加的LogFile->toCompact隊列->compactedLevel1隊列->compactedLevel2隊列。因此，CompactionHashIdxKvDb 的讀操作在極端情況下（所查詢的數據存儲在comactedLevel2隊列上時）也會較為低效。
@Override public?String?get(String?key)?{ ????//?第一步：從當前的LogFile查找 ????if?(idx.idxOf(curLog,?key)?!=?-1)?{ ????????long?offset?=?idx.idxOf(curLog,?key); ????????String?record?=?curLog.read(offset); ????????return?Util.valueOf(record); ????} ????//?第二步：從toCompact中查找 ????String?record?=?find(key,?toCompact); ????if?(!record.isEmpty())?{ ????????return?record; ????} ????//?第三步：從?compactedLevel1?中查找 ????record?=?find(key,?compactedLevel1); ????if?(!record.isEmpty())?{ ????????return?record; ????} ????//?第四步：從?compactedLevel2?中查找 ????record?=?find(key,?compactedLevel2); ????if?(!record.isEmpty())?{ ????????????return?record; ????} ????return?""; }
對toCompact隊列里的old segment file進行單文件level1 compact操作時，可以利用Hash索引。因為Hash索引上所對應的記錄總是最新的，因此只需遍歷Hash索引，將每個key對應的最新記錄查詢出來，寫到新的level1 compacted segment file中即可。
//?進行level1?compact，對單個old?segment?file合并 void?compactLevel1()?{ ????while?(!toCompact.isEmpty())?{ ????????//?創建新的level1?compacted?segment?file ????????LogFile?newLogFile?=?LogFile.create(curLog.path()?+?"_level1_"?+?level1Num.getAndIncrement()); ????????LogFile?logFile?=?toCompact.getFirst(); ????????//?只保留每個key對應的最新的value ????????idx.allIdxOf(logFile).forEach((key,?offset)?->?{ ????????????String?record?=?logFile.read(offset); ????????????long?curSize?=?newLogFile.size(); ????????????if?(newLogFile.append(record)?!=?0)?{ ????????????????idx.addIdx(newLogFile,?key,?curSize); ????????????} ????????}); ????????//?寫完后存儲到compactedLevel1隊列中，并刪除toCompact中對應的文件 ????????compactedLevel1.addLast(newLogFile); ????????toCompact.pollFirst(); ????????logFile.delete(); ????} }
對compactedLevel1隊列進行多文件level2 compact的策略是：將當前隊列里所有的level1 compacted segment file合并成一個level2 compacted segment file。具體步驟如下：
1、生成一份compactedLevel1隊列的snapshot。目的是為了避免在level2 compact過程中，有新的level1 compacted segment file加入到隊列造成影響。
2、對snapshot進行compact操作，按照從新到舊的順序，將level1 compacted segment file中的記錄寫入新的level2 compacted segment file中，如果發現level2 compacted segment file已經存在該key，則跳過。
3、等完成任務后，再從compactedLevel1隊列里刪除已經合并過的level1 compacted segment file。
//?進行level2?compact，針對compactedLevel1隊列中所有的文件進行合并 void?compactLevel2()?{ ????... ????//?生成一份快照 ????Deque
總結
本文首先介紹了Martin Kleppmann給出的最簡單的數據庫，并使用Java語言對它進行了重新的實現，接著采用Hash索引和compact機制對其進行了一系列的優化。
SimpleKvDb采用append-only log的方式存儲數據，append-only log最主要的優點是具備很高的寫入性能（文件系統的順序寫比隨機寫要快很多）。追加寫也意味著同一個key對應的舊記錄不會被覆蓋刪除，因此在查詢數據時，需要遍歷整個文件，找到該key的所有記錄，并選取最新的一個。因為涉及到全文遍歷，因此SimpleKvDb的讀性能非常低。
為了優化SimpleKvDb的讀性能，我們實現了具有Hash索引的HashIdxKvDb。Hash索引是一個在內存中維護的Hash表，保存每個key對應的記錄在文件中的offset。因此每次數據查詢只需要1次磁盤尋址，加上1次磁盤I/O，非常高效。
為了解決append-only log一直擴張導致磁盤空間不足的問題，我們給HashIdxKvDb引入了compact機制，實現了CompactionHashIdxKvDb。compact機制能夠有效清理數據庫中的無效的舊數據，從而減緩了磁盤空間的壓力。
Hash索引雖然簡單高效，但是有如下兩個限制：
1、必須在內存中維護Hash索引。如果選擇在磁盤上實現Hash索引，那么將會帶來大量的磁盤隨機讀寫，導致性能的急劇下降。另外，隨著compact機制的引入，數據被分散在多個segment file中存儲，我們不得不為每個segment file維護一份Hash索引，這就導致Hash索引的內存占用量不斷增加，給系統帶來了很大的內存壓力。
2、區間查詢非常低效。比如，當需要查詢數據庫中范圍在[key0000, key9999]之間的所有key時，必須遍歷索引中所有的元素，然后找到符合要求的key。
針對Hash索引的這兩個限制，要怎樣進行優化呢？本系列的下一篇文章，我們將介紹另一種不存在這兩個限制的索引——LSM樹。
----------------------------
本文轉自“元閏子”
HashMap 數據庫 存儲 搜索引擎
版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。
版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。
相關文章
