面對key數量多和區間查詢低效問題：Hash索引趴窩，LSM樹申請出場
我們通過append-only log的數據結構，實現了一個具備高寫入性能的key-value數據庫。append-only log之所以有很高的寫入性能，主要得益于磁盤的順序寫入。這可能違反了我們對磁盤的認知，因為在我們的印象中，寫磁盤總是很慢。其實不然，準確地說應該是隨機寫磁盤很慢，因為在寫之前可能會進行多次尋址。如果只是順序寫磁盤，性能是非常的高，如下的一個ACM報告中顯示，順序寫磁盤甚至比隨機寫內存的性能還要高！
舉個例子，Kafka是一個高性能的消息隊列，它的厲害之處就在于極致地利用磁盤的順序寫入性能，如果生產者和消費者的速率相當，消息甚至可以在操作系統的Page Cache層面就完成了傳遞。所以，以后別再認為寫磁盤很慢了！
append-only log大幅提升了數據寫入性能，但是隨之而來的是，非常低的數據讀取性能。針對這一點，我們采用Hash索引進行了優化，優化的效果也非常的顯著。然而，Hash索引有兩個明顯的限制：（1）當key的數量很多時，維護Hash索引會給內存帶來很大的壓力；（2）區間查詢很低效。如何對這兩個限制進行優化呢？這就輪到本文介紹的主角，LSM樹，出場了。
LSM樹（Log-Structured Merge Tree）并不是一種數據結構，準確來說是一種存儲模型，由MemTable、Immutable MemTable、SSTable等部分組成。它也是利用了append-only log的優勢，大幅提升了寫入性能。同時，因為key的存儲有序性，所以具備了不錯的讀取性能，也克服了上文所述Hash索引的兩個限制。下面，本文將一步步分析LSM樹是如何做到這一點的。
SSTable
在最簡單的數據庫例子中，因為數據是無序存儲的，所以在讀取某個key的值時，就需要遍歷整個數據文件，算法復雜度是O(n)。為了提升讀性能，我們不得不在內存中維護所有key的Hash索引。
假如存儲數據時，對記錄按照key進行排序的會怎樣？
對于key有序存儲這種情況，即使不用Hash索引，也能得到很好的查詢效率，因為我們可以使用二分查找法（Binary Search）來快速找到key所在的位置，算法復雜度是O(logn)。LSM樹正是采用key有序這種方式來組織數據存儲的，并稱之為SSTable。
SSTable（Sorted String Table）是LSM樹最基礎的一個存儲結構，存儲在磁盤中，并且數據按照key進行排序的。數據保持key有序的好處是可以在O(logn)的時間下，快速找到一個key值，相比于純粹的append-only log有了很大的提升。但是，如果所有的數據都存儲在一個SSTable上，數據量一大，查詢效率也會下降。因此，LSM樹通常會將數據分散存儲在多個SSTable中，并且記錄每個SSTable的最大key和最小key，這樣就能快速定位到一個key存儲在哪個SSTable上了。
SSTable數據查找示例
//?SSTable，數據保存到SSTable后只讀不寫
public?class?SSTable?{
...
//?數據存儲路徑
private?final?LogFile?logFile;
//?該SStable中存儲的最小Key
private?String?minKey;
//?該SStable中存儲的最大Key
private?String?maxKey;
//?使用二分查找法獲取key值
public?String?get(String?key)?{
//?step1：先判斷是否在SSTable的范圍內
if?(key.compareTo(minKey)??0)?{
return?"";
}
//?step2：二分查找
long?start?=?0;
long?end?=?logFile.size();
while?(start?
long?mid?=?start?+?(end?-?start)?/?2;
//?先找到一條record到起始offset
long?startOffset?=?logFile.startOffsetOf(mid);
String?record?=?logFile.read(startOffset);
String?midKey?=?Util.keyOf(record);
if?(key.compareTo(midKey)?==?0)?{
return?Util.valueOf(record);
}?else?if?(key.compareTo(midKey)?
end?=?mid;
}?else?{
//?找到一條record到起始offset時可能會有mid?==?start的情況
if?(mid?==?start)?{
break;
}
start?=?mid;
}
}
return?"";
}
...
}
這里只是介紹了一種比較簡單的SSTable實現方式，實際上，各種LSM樹存儲引擎對SSTable的實現都有所差異，比如LevelDB就將SSTable劃分成兩大塊，數據存儲區存儲key:value數據，數據管理區存儲索引等數據。
那么怎樣才能保證SSTable的有序性呢？
類似的在磁盤中維護數據有序的存儲結構最常見的當屬B/B+樹了，如果對SSTable也采用類似的存儲結構，那么帶來的第一個問題就是每次寫入都會伴隨著磁盤的隨機寫，從而影響了數據的寫入性能，這明顯就違反了LSM樹的初衷。為了同時兼顧SSTable的有序性以及寫入性能，LSM樹采用了MemTable這一組件。
MemTable
相比于磁盤上維護一個有序的數據結構，在內存上實現數據有序要簡單得多，而且具備較高的讀寫性能，常見的有序數據結構有紅黑樹、AVL樹、跳表等，不管你插入的順序如何，讀出來的數據總是有序的。MemTable正是LSM維護在內存中的一個有序的數據結構，接下來我們看下LSM是如何利用Memtable做到同時兼顧SSTable的有序行和寫入性能的：
1、當寫入請求過來時，先將record寫入到Memtable中，這樣就能保證record在內存中有序了，而且具備較高的寫入性能。
2、當Memtable的大小達到一定的閾值后（通常是幾個Mb的大小），將MemTable轉成Immutable MemTable（一個只讀不寫的MemTable），并創建新的MemTable接收寫請求。
和《從Hash索引到LSM樹（一）》中的segment file機制類似，一個時刻只有current segment file接收寫請求，其他的只讀不寫。
3、通過后臺任務，定時將Immutable MemTable的數據刷到SSTable中，因為Immutable MemTable本身的有序性，所以就能保證SSTable中的數據是有序的，而且數據寫入SSTable文件時完全是順序寫入，做到了有序性和寫入性能的兼顧。
4、當讀請求過來時，查找的順序是MemTable->Immutable MemTable->SSTable，找到則返回，否則一步步執行下去。
Memtable同時兼顧有序和寫性能
Memtable底層通常采用跳表來實現（LevelDB、HBase都采用了這一實現方法），相比較AVL和紅黑樹，跳表在插入數據的時候可以避免頻繁的樹節點調整操作，所以寫入效率很高，而且實現起來也更簡單些。
//?LSM維護在內存中的有序數據結構，數據寫入時先寫MemTable
public?class?MemTable?{
//?基于跳表實現的key-value結構
private?final?ConcurrentSkipListMap
//?當前存儲數據的大小
private?AtomicInteger?size;
...
//?查找key
public?String?get(String?key)?{
if?(!cache.containsKey(key))?{
return?"";
}
return?cache.get(key);
}
//?添加key:value，并更新當前Memtable的大小
public?void?add(String?key,?String?value)?{
cache.put(key,?value);
size.addAndGet(key.length()?+?value.length());
}
//?返回當前Memtable的大小（字節為單位）
//?用于判斷達到閾值之后，轉成Immutable?MemTable
public?int?size()?{
return?this.size.get();
}
//?達到閾值之后轉儲到SSTable
public?void?compact2Sst(SSTable?sst)?{
cache.forEach(sst::add);
}
...
}
LsmKvDb
使用LSM樹作為存儲引擎的數據庫，通常對SSTable進行分層管理，方便查詢以及后續的Compact操作。本文也將采用對SSTable進行分層的架構實現LsmKvDb。
LsmKvDb存儲架構
首先對Level進行抽象，每個Level都由多個SSTable組成：
//?對LSM的層的抽象，由SSTable組成
public?class?Level?{
private?final?List
...
public?void?add(SSTable?sst)?{
ssts.add(sst);
}
//?在當前level總查找key對應的value,?從老到新遍歷所有SSTable
public?String?find(String?key)?{
for?(int?i?=?ssts.size()?-?1;?i?>=?0;?i--)?{
String?value?=?ssts.get(i).get(key);
if?(!value.equals(""))?{
return?value;
}
}
return?"";
}
//?sst與當前level進行compact操作
public?void?compactWith(SSTable?sst)?{...}
//?對給定sst集合與當前level進行compact操作
public?void?compactWith(List
}
LsmKvDb的實現代碼如下，寫數據時寫入MemTable，當達到閾值后轉Immutable MemTable。Immutable MemTable與MemTable具有相同的數據結構，唯一不同的是前者只讀不寫，后者既讀也寫。
/**
*?基于LSM樹的key-value數據庫,?采用分層架構
*?MemTable?->?Immutable?MemTable?->?Level0?->?Level1?->?Level2
*/
public?class?LsmKvDb?implements?KvDb?{
...
//?存儲SSTable的目錄
private?final?String?sstDir;
//?當前寫入的MemTable
private?MemTable?memTable;
//?MemTable到達閾值大小后轉儲到immutableMts
private?final?List
//?后臺定時將immutableMts中的MemTable刷到Level0，各SSTable之間可能由Key重疊
private?final?Level?level0;
//?后臺定時將Level0中的SSTable與Level1中的進行合并
private?final?Level?level1;
//?當Level1中的SSTable的數量到達一定閾值后，選擇最老的SSTable與Level2中的進行合并
private?final?Level?level2;
...
@Override
public?String?get(String?key)?{
//?step1:?從MemTable中讀取
String?value?=?memTable.get(key);
if?(!value.equals(""))?{
return?value;
}
//?step2:?從Immutable?MemTable中讀取，從新到老
for?(int?i?=?immutableMts.size()?-?1;?i?>=?0;?i--)?{
value?=?immutableMts.get(i).get(key);
if?(!value.equals(""))?{
return?value;
}
}
//?step3:?從Level0中讀取
value?=?level0.find(key);
if?(!value.equals(""))?{
return?value;
}
//?step4:?從Level1中讀取
...
//?step5:?從Level2中讀取
...
return?"";
}
@Override
public?void?set(String?key,?String?value)?{
memTable.add(key,?value);
//?當MemTable大小到達閾值后轉成Immutable?MemTable
if?(memTable.size()?>?MEMTABLE_MAX_SIZE)?{
synchronized?(this)?{
immutableMts.add(memTable);
memTable?=?MemTable.create();
}
}
}
...
}
Compaction
在文章《從Hash索引到LSM樹（一）》已經對Compaction機制已經有了講解，其目的是清除掉已經被覆寫或刪除了的紀錄，避免數據存儲文件無休止的增長下去。對于LSM樹而言，該機制同樣適用，隨著數據的不斷添加、更新和刪除，一些SSTable之間必然存在著重疊的key或被刪除的key。通過Compaction，可以將多個SSTable合并成一個，從而節省了磁盤空間。
在上篇文章中，對segment file的compact操作主要依賴于Hash索引。因為是索引覆蓋全部的key，所以可以很容易通過新的segment file的Hash索引來判斷該key是否已經被處理過。但對于SSTable而言，并沒有覆蓋全部key的Hash索引，那么如何進行compact才高效呢？
得益于SSTable的有序性，我們可以應用歸并排序算法來進行compact操作！
LSM樹的Compaction通常有三種類型，分別是minor compact、major compact和full compact。
Minor Compact
minor compact指的是將Immutable MemTable中的數據直接轉存到Level0中的SSTable。
minor compact
因為是直接將各個Immutable MemTable的數據轉儲成SSTable，并沒有做合并的操作，因此在Level0中，各個SSTable之間的key可能存在重疊的現象。
Major Compact
major compact指的是將Level n中的SSTable合并到Level n+1中。
Level0 -> Level1的合并步驟如下：
1、選中Level0中的最老的SSTable?sst0，然后在Level0中找到與sst0?的key存在重疊的所有SSTable?sst0...n。
2、在Level1中，選取所有與?sst0...n存在key重疊的SSTable?sst'0...m。
3、對sst0...n和sst'0...m采用多路歸并排序算法進行合并，得到新的sst‘’0...k，并存儲在Level1中。
4、刪除sst0...n和sst'0...m。
major compact Level0 -> Level1
不同于Level0，Level1和Level2中各個SSTable之間并不存在key重疊的現象，因此Level1 -> Level2的合并會稍微簡單些。
Level1 -> Level2的合并步驟如下：
1、選中Level1中的最老的SSTable?sst0。
2、在Level2中，選取所有與?sst0存在key重疊的SSTable?sst'0...m。
3、對sst0和sst'0...m采用多路歸并排序算法進行合并，得到新的sst''0...k，并存儲在Level2中。
4、刪除sst0和sst'0...m。
major compact Level1 -> Level2
Full Compact
full compact指的是對Level0、Level1、Level2中所有的SSTable進行compact操作，同樣也是采用多路歸并排序算法。
full compact
通常full compact耗時較多，所以一般都會選擇在流量較少的時刻進行。
優化LSM樹
為SSTable引入block
到目前為止，對于在一個SSTable中查找一個key，我們首先會根據min key和max key判斷該key是否屬于該SSTable所屬的范圍，如果屬于，則對SSTable采用二分查找法進行搜索。二分查找之所以在LsmKvDb中行得通，是因為這是一個簡單的SSTable實現 —— 數據按string存儲和\n分隔。在實際的運用中，為了盡可能地利用磁盤空間，SSTable中數據通常都是以字節碼的形式存儲，也不會以\n分隔每條record，這種情況下采用二分查找的實現就比較復雜了，而且效率也會太高。
一個常見的優化方法是，在SSTable中對record按照一定的size組織成多個block，并以block為單位進行壓縮。為了能夠快速找到某個key所屬的block，需要在內存中維護每個block的起始key對應在SSTable中的offset（一個稀疏的Hash索引）。
按block存儲的SSTable
在查找key的步驟如下：
1、根據索引定位到key所屬的block。
2、將該block加載到內存中，并解壓。
3、對內存中的數據采用二分查找。
在設計block的大小時，應該利用磁盤的空間局部性原理，使得系統能夠只花費一次磁盤I/O就能將整個block加載到內存中。
為SSTable引入Bloom Filter
其實當目標key屬于某個SSTable的key范圍時，該key也不一定會存在于該SSTable中。但是到目前為止，只要目標key在某個SSTable的范圍內，LsmKvDb都會進行查找操作。隨著系統中的SSTable數目的增多，查詢效率必然會隨之下降。
一個常見的優化方法時，為SSTable引入布隆過濾器Bloom Filter。
Bloom Filter是保存在內存中的一種數據結構，可以用來告訴你 “某樣東西一定不存在或者可能存在”。它由一個超長的二進制位數組和一系列的Hash函數組成。二進制位數組初始全部為0，當有元素加入集合時，這個元素會被一系列Hash函數計算映射出一系列的值，所有的值在位數組的偏移量處置為1。如果需要判斷某個元素是否存在于集合當中，只需判斷該元素被Hash后的值在數組中的值，如果存在為0的，則該元素一定不存在；如果全為1，則可能存在，這種情況可能有誤判。
Bloom Filter
通過Bloom Filter，我們可以很快就能判斷目標key是否不存在于SSTable中，從而提升了讀性能。
Google的Guava庫就提供了一個BloomFilter的實現，并且可以按需來設置誤判率。
總結
本文承接上《從Hash索引到LSM樹（一）》，主要介紹了LSM樹的基本原理，并且在原來append-only log的基礎上實現了一個簡單的基于LSM樹的key-value數據庫LsmKvDb。LSM樹主要由MemTable、Immutable MemTable、SSTable組成，其中MemTable和Immutable MemTable在內存中維護，而SSTable則存儲在磁盤中。SSTable的有序性使得LSM樹在無需Hash索引的情況下具有不錯的讀取性能，而且支持區間查詢；而Memable則使得LSM樹具備很高的寫入性能。
本系列文章，我們從一個最簡單的key-value數據庫起步，一步步通過Hash索引、LSM樹、布隆過濾器等技術手段對其進行了優化，從中也深入分析了各個技術點的實現原理。但數據庫的索引技術遠不止這些，比如最常用到的B/B+樹，也是非常值得深入學習的，以后有機會再對其進行深入分析～
HashMap 數據庫 數據結構
版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。
版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。
相關文章
