在圖3-3中，每個(gè)日志結(jié)構(gòu)的存儲(chǔ)段（Segment）都是鍵-值對(duì)的序列。這些成對(duì)出現(xiàn)在它們被寫入的順序中，并且在日志中靠后的值優(yōu)先于之前相同鍵的值。除此之外，文件中鍵值對(duì)的順序無關(guān)緊要。
現(xiàn)在，我們可以對(duì)分段文件的格式做一個(gè)簡(jiǎn)單的更改：我們要求鍵-值對(duì)的順序按鍵排序。乍一看，這個(gè)需求似乎破壞了我們使用順序?qū)懙哪芰Γ俏覀凂R上就會(huì)講到。
我們稱這種格式為排序的字符串表，簡(jiǎn)稱SSTable。我們還要求每個(gè)密鑰只在每個(gè)合并段文件中出現(xiàn)一次（壓縮過程已經(jīng)確保了這一點(diǎn)）。與哈希索引的日志片段相比，SSTable有幾個(gè)大的優(yōu)勢(shì)：
- 1.合并段(Segment)是簡(jiǎn)單和有效的，即使文件比可用內(nèi)存大。該方法類似于mergesort算法中使用的方法，如圖3-4所示：您開始逐個(gè)讀取輸入文件，查看每個(gè)文件中的第一個(gè)鍵，將最低鍵（根據(jù)排序順序）復(fù)制到輸出文件，然后重復(fù)。這會(huì)產(chǎn)生一個(gè)新的合并文件，也按鍵排序。
如果相同的鍵出現(xiàn)在幾個(gè)輸入段（Segment）中會(huì)怎樣？請(qǐng)記住，每個(gè)段（Segment）包含在一段時(shí)間內(nèi)寫入數(shù)據(jù)庫的所有值。這意味著一個(gè)輸入段（Segment）中的所有值必須比其他段（Segment）中的所有值都要近（假設(shè)我們總是合并相鄰段）。當(dāng)多個(gè)段（Segment）包含相同的鍵時(shí)，我們可以將值保存在最近的段（Segment）中，并丟棄舊段（Segment）中的值。
- 2.為了在文件中找到一個(gè)特定的鍵，你不再需要保存內(nèi)存中所有鍵的索引。請(qǐng)參見圖3-5中的示例：假設(shè)你正在尋找關(guān)鍵的手工制品，但你不知道該段（Segment）文件中該鍵的確切偏移量。然而，你確切知道鑰匙手提包和漂亮東西的偏移量，而且因?yàn)榉诸悾阒朗止ぶ破房隙ㄔ谶@兩者之間。這意味著你可以跳轉(zhuǎn)到手提包的偏移量，然后從那里掃描直到你找到手工制品（當(dāng)然如果它不在文件中也可能找不到）。
你仍然需要一個(gè)內(nèi)存索引來告訴你一些鍵的偏移量，但是它可能是稀疏的：每幾kb的段（Segment）文件的一個(gè)鍵就足夠了，因?yàn)榭梢院芸斓貟呙鑾讉€(gè)千字節(jié)。
- 3.由于讀請(qǐng)求需要在請(qǐng)求的范圍內(nèi)掃描多個(gè)鍵-值對(duì)，所以可以將這些記錄分組到一個(gè)塊中，并在將其寫到磁盤之前壓縮它（如圖3-5所示的陰影區(qū)域）。稀疏內(nèi)存索引的每個(gè)條目都指向一個(gè)壓縮塊的開始。除了節(jié)省磁盤空間，壓縮還減少了i/o帶寬的使用。
構(gòu)建和維護(hù)SSTables
到目前為止還不錯(cuò)——但是如何讓你的數(shù)據(jù)首先按鍵排序呢？我們的寫操作可以以任意順序出現(xiàn)。
在磁盤上維護(hù)一個(gè)排序結(jié)構(gòu)是可能的（詳見后面的BTree），但是在內(nèi)存中維護(hù)它要容易得多。有許多眾所周知的樹數(shù)據(jù)結(jié)構(gòu)，比如紅黑樹或AVL樹。有了這些數(shù)據(jù)結(jié)構(gòu)，你可以按任意順序插入鍵，并按順序讀取它們。
我們現(xiàn)在可以讓我們的存儲(chǔ)引擎工作如下：
- 當(dāng)一個(gè)寫入進(jìn)來時(shí)，將其添加到內(nèi)存中平衡的樹數(shù)據(jù)結(jié)構(gòu)中（例如，紅黑樹）。這個(gè)內(nèi)存中的樹有時(shí)也被稱為memtable。
- 當(dāng)memtable大于某個(gè)閾值時(shí)——通常是幾兆字節(jié)——將其寫到磁盤上作為一個(gè)SSTable文件。這可以有效地完成，因?yàn)闃湟呀?jīng)維護(hù)了按鍵排序的鍵值對(duì)。新的SSTable文件成為數(shù)據(jù)庫中最新的部分。當(dāng)SSTable被寫到磁盤上時(shí)，寫操作可以繼續(xù)寫到一個(gè)新的memtable實(shí)例。
- 為了服務(wù)于讀請(qǐng)求，首先要在memtable中找key，然后在最近的磁盤段（Segment）中找key，然后在下一個(gè)較新的段（Segment）中找key.....
- 通常，在后臺(tái)運(yùn)行合并和壓縮過程，用來合并段（Segment）文件并丟棄被覆蓋或刪除的值。
這個(gè)計(jì)劃很有效。它只會(huì)遇到一個(gè)問題：如果數(shù)據(jù)庫崩潰，最近的寫入（在memtable中，但還沒有寫到磁盤）就會(huì)丟失。為了避免這個(gè)問題，我們可以在磁盤上保留一個(gè)單獨(dú)的日志，每一個(gè)寫入都立即被追加，就像在前一節(jié)中一樣。該日志不是按順序排列的，但這并不重要，因?yàn)樗奈ㄒ荒康氖窃诒罎⒑蠡謴?fù)表。所以每當(dāng)memtable被寫到一個(gè)SSTable時(shí)，相應(yīng)的日志就會(huì)被丟棄。
用SSTables實(shí)現(xiàn)LSM-Tree
這里描述的算法是在LevelDB和RocksDB中使用的，鍵值存儲(chǔ)引擎庫被設(shè)計(jì)成嵌入到其他應(yīng)用程序中。除此之外，LevelDB可以在Riak中作為Bitcask的替代品。在Cassandra和HBase中也使用了類似的存儲(chǔ)引擎，這兩種引擎都受到了Google的Bigtable paper的啟發(fā)（它引入了SSTable和memtable的術(shù)語）。
最初，這個(gè)索引結(jié)構(gòu)是由Patrick o'neil等人在“Log-Structured Merge-Tree ”（或LSM-Tree）中描述的，它建立在早期的日志結(jié)構(gòu)文件系統(tǒng)的工作基礎(chǔ)上。而基于合并和壓縮排序文件的存儲(chǔ)引擎通常被稱為LSM存儲(chǔ)引擎。
Lucene，是Elasticsearch和Solr全文搜索索引引擎的內(nèi)核，它使用了一種類似的方法來存儲(chǔ)它的詞匯字典。全文索引要比鍵值索引復(fù)雜得多，但它基于一個(gè)類似的想法：在搜索查詢中給定一個(gè)單詞，找到提到這個(gè)單詞的所有文檔（web頁面、產(chǎn)品描述等）。這是用一個(gè)鍵值結(jié)構(gòu)來實(shí)現(xiàn)的，其中鍵是一個(gè)單詞（一個(gè)術(shù)語），值是包含單詞的所有文檔的id列表（term）。在Lucene中，從term到發(fā)布列表的映射保存在類似于SSTable的排序文件中，這些文件在需要的時(shí)候被合并到后臺(tái)。
性能優(yōu)化
和通常一樣，在實(shí)踐中，存儲(chǔ)引擎的性能很好。例如，LSM-tree算法在查找一個(gè)數(shù)據(jù)庫中不存在的鍵時(shí)是可以非常緩慢的：你必須檢查memtable，然后檢查段（Segment）直到追溯到最古老（可能需要從磁盤讀取每一個(gè)）的，可以肯定的是，鍵是不存在的。為了優(yōu)化這種訪問方式，存儲(chǔ)引擎通常使用額外的Bloom過濾器 。（Bloom過濾器是一種內(nèi)存高效的數(shù)據(jù)結(jié)構(gòu)，用于近似一組內(nèi)容。它可以告訴你，如果一個(gè)鍵沒有出現(xiàn)在數(shù)據(jù)庫中，這樣就可以為不存在的鍵節(jié)省許多不必要的磁盤讀取）。
也有不同的策略來確定壓縮和合并SSTables的順序和時(shí)間。最常見的選擇是size-tiered和leveled compaction。LevelDB和RocksDB使用了leveled compaction（所以叫LevelDB嘛），HBase使用size-tiered，而Cassandra支持兩者。在size-tiered，更新的和較小的SSTables相繼合并成更久的、更大的SSTables。在leveled compaction中，關(guān)鍵的范圍被分割成更小的SSTables，舊的數(shù)據(jù)被移動(dòng)到單獨(dú)的“級(jí)別”中，這使得壓縮可以更增量地進(jìn)行，并且使用更少的磁盤空間。
盡管有許多微妙之處，但lsm的基本理念——保持在后臺(tái)融合的一系列的SSTables——是簡(jiǎn)單而有效的。即使數(shù)據(jù)集比可用內(nèi)存大得多，它仍然可以很好地工作。由于數(shù)據(jù)是以排序的順序存儲(chǔ)的，所以你可以有效地執(zhí)行范圍查詢（掃描最小值以上和最大值一下的鍵），并且由于磁盤寫的順序是連續(xù)的，因此lsm可以支持非常高的寫吞吐量。
