一周一论文（翻译）——[Acta 1996] The Log-Structured Merge-Tree (LSM-Tree)
Abstract
高性能事務系統通常會通過向一個歷史表中插入記錄以追蹤各項活動行為；與此同時事務系統也會因系統恢復的需要而生成日志記錄。這兩種類型的生成信息都可以從高效的索引方式中獲益。眾所周知的一個例子，TPC-A benchmark{TPC是Transaction Processing Performance Council的簡稱，是一個專門針對數據庫系統性能benchmark的非盈利性組織，TPC-A是其中的一個測試集合，主要關注于事務處理的吞吐量，更具體來說是每秒的事務處理能力，通過TPS(transactions per second)測量}中的測試程序，修改下就可以在給定的History表上對給定account的活動記錄進行高效的查詢支持。但這需要在快速增長的History表上建立一個針對account id的索引。不幸的是，標準的基于磁盤的索引結構，比如B-樹，要實時性地維護這樣的一個索引，會導致事務的IO開銷加倍，從而會導致系統的整體開銷增加50%{!通過例1.1可知，磁盤成本大概占系統總成本的50%}。很明顯，這就需要一種維護這種實時性索引的低成本的方式。The Log-Structured Merge-Tree (LSM-Tree)就是設計用于來為那些長期具有很高記錄更新(插入或刪除)頻率的文件來提供低成本的索引機制。LSM-Tree通過使用某種算法，該算法會對索引變更進行延遲及批量處理，并通過一種類似于歸并排序的方式聯合使用一個基于內存的組件和一個或多個磁盤組件。在處理過程中，所有的索引值對于所有的查詢來說都是可以通過內存組件或者某個磁盤組件來進行訪問的(除了很短暫的加鎖期外)。與傳統訪問方式比如B-樹相比，該算法大大降低了磁盤磁臂的移動，同時也會提高那些使用傳統訪問方式進行插入時，磁盤磁臂開銷{!尋道+轉動}遠大于存儲空間花費的情況的性價比。LSM-Tree方式也可以支持除插入和刪除外的其他操作。但是，對于那些需要立即響應的查找操作來說，某些情況下，它也會損失一些IO效率，因此LSM-Tree最適用于那些索引插入比查詢操作更常見的情況。比如，對于歷史記錄表和日志文件來說，就屬于這種情況。
1. Introduction
?????? 隨著activity flow(活動流)管理系統中的long-lived(長生命期)事務的商業化使用，針對事務日志記錄提供索引化的訪問需求也在逐步增長。傳統的，事務日志機制主要專注于失敗和恢復，需要系統能夠在偶然的事務回滾中可以回退到一個相對近期的正常歷史狀態，而恢復的執行則通過批量化的順序讀取完成。然而，隨著系統需要管理越來越多的復雜行為，組成單個長生命期活動的事件的持續時間和個數也會增長到某種情況，在該情況下，需要實時查看已經完成的事務步驟以通知用戶目前已經完成了哪些。與此同時，一個系統的處于活動狀態的事件總數，也會增長到某種情況，在該情況下，用于記錄活動日志的基于內存的數據結構開始無法工作，盡管內存價格的不斷下降是可以預計的。這種對于過去的行為日志的查詢需求，意味著索引化的日志訪問將會越來越重要。?????? 流計算是一種計算范例，能夠以高效且可擴展的方式執行分析任務。 通過將傳入的數據流通過放置在一組分布式主機上的Operator網絡，流計算提供了即時的處理模型。 由于數據不直接存儲在磁盤上，因此流計算避免了更傳統的數據管理存儲和處理模型所面臨的性能問題。 商業流處理系統的出現，如StreamBase [28]和InfoSphere Streams [16]，開源系統，如S4 [34]和Storm [27]，以及現有的學術系統，如STREAM [5]，Borealis [1]和System S [18]，是流計算范式未來增長和過去成功的證據。
?????? 即使是對于當前的事務系統來說，如果對在具有高插入頻率上的歷史記錄表上的查詢提供了索引支持，其價值也是很明顯的。網絡應用，電子郵件，和其他的近事務系統通常會產生不利于它們的主機系統的大量日志。為了便于理解，還是從一個具體的大家都熟知的例子開始，在下面的例1.1和1.2中我們使用了一個修改版的TPC-A benchmark。需要注意的是，為了便于表述，本文中的例子都采用了一些特定的參數值，當然這些結果應該都很容易進行推廣。還要指出的是，盡管歷史記錄表和日志都是一些時間序列相關的數據，LSM-Tree中的索引節點并不一定具有與之相同的key值順序。唯一的假設就是與查詢頻率相比的高更新率。
5分鐘法則
?????? 下面的兩個例子都依賴于5分鐘法則。該法則是說當頁面訪問頻率超過每60秒就會被訪問一次的頻率后，可以通過加大內存來將頁面保存到內存，以避免磁盤訪問來降低系統總體開銷。60秒在這里只是個近似值，實際上是磁盤提供每秒單次IO的平攤開銷與每秒緩存4K bytes的磁盤頁的內存開銷的比值。用第3節的術語來說，就是COSTp/COSTm。在這里，我們會從經濟學的角度上簡單看下如何在磁盤訪問和緩存在內存之間進行權衡。需要注意的是，由于內存價格與磁盤相比下降地更快，60秒這個值實際應該會隨著時間而變大。但是在1995年的今天它是60秒，與1987年的5分鐘相比，它卻變小了，部分是因為技術性的(不同的緩存假設)原因，部分是因為介于二者之間的廉價量產磁盤的引入。
?????? 例1.1 考慮TPC-A benchmark中描述的每秒執行1000個事務(該頻率可以被擴展，但是此處我們只考慮1000TPS)的多用戶應用程序。每個事務會更新一個列值，從一個Balance列中取出數目為Delta的款項，對應的記錄(row)是隨機選定的并且具有100字節大小，涉及到三個表：具有1000條記錄的Branch(分公司)表，具有10000條記錄的Teller(出納員)表，以及具有100,000,000條記錄的Account表；更新完成之后，該事務在提交之前會向一個歷史記錄表中插入一條50字節的記錄，該記錄具有如下列：Account-ID，Branch-ID，Teller-ID，Delta和時間戳。
?????? 根據磁盤和內存成本計算下，可以看出Account表在未來的很多年內都不可能是內存駐留的，而Branch和Teller表目前是可以全部存入內存中的。在給定的假設下，對于Account表的同一個磁盤頁的兩次訪問大概要間隔2500秒{!磁盤頁是4K bytes，Account表每行是100bytes，這樣每次讀會涉及到4k/100=40條記錄，TPS是1000,這樣2500秒內讀到的行數就是40*1000*2500=100,000,000。2500秒就是這么算出來的}，很明顯這個值還未達到5分鐘法則中緩存駐留所需要的訪問頻率?，F在每次事務都需要大概兩次磁盤IO，一次用于讀取所需的Account記錄(我們忽略那種頁面已經被緩存的特殊情況)，一次用于將之前的一個臟的Account頁寫出來為讀取騰出緩存空間(necessary for steady-status behavior)。因此1000TPS實際上對應著大概每秒2000個IO。如果磁盤的標稱速率是25IO/s，那么這就需要80個磁盤驅動器，從1987年到如今(1995)的8年間磁盤速率(IOPS)每年才提高不到10%，因此現在IOPS大概是40IO/s，這樣對于每秒2000次IO來說，就需要50個磁盤。對于TPC應用來說，磁盤的花費大概占了整個系統成本的一半，盡管在IBM的大型機系統中這個比例要低一些。然而，用于支持IO的開銷很明顯在整個系統成本中正在不斷增長，因為內存和CPU成本下降地比磁盤要快。
例1.2 現在來考慮一個在具有高插入量的歷史記錄表上的索引，可以證明這樣的一個索引將會使TPC應用的磁盤開銷加倍。一個在“Account-ID+Timestamp”上的聯合索引，是歷史記錄表能夠對最近的account活動進行高效查詢的關鍵，比如：
Select * from History Where History.Acct-ID = %custacctid And History.Timestamp > %custdatetime;?????? 如果Acct-ID||Timestamp索引不存在，這樣的一個查詢將需要搜索歷史記錄表中的所有記錄，因此基本上是不可行的。如果只是在Acct-ID上建立索引，可以得到絕大部分的收益，但是即使將Timestamp排除，我們下面的那些開銷考慮也不會發生變化{!即去掉Timestamp也不會省掉什么開銷}，因此我們這里假設使用的是最有效的聯合索引。那么實時地維護這樣的一個B-樹索引需要多少資源呢？可以知道，B樹中的節點每秒會生成1000個，考慮一個20天的周期，每天8小時，每個節點16字節，這意味著將會有576,000,000{!1000*20*8*3600}個節點，占據的磁盤空間是9.2GBytes，即使是在沒有浪費空間的情況下，整個索引的葉節點都大概需要2.3million個磁盤頁。因為事務的Acct-ID值是隨機選擇的，每個事務至少需要一次讀取，此外基本上還需要一次頁面寫入。根據5分鐘法則，這些索引頁面也不應該是內存駐留的(磁盤頁大概每隔2300秒被讀一次)，這樣所有的IO都是針對磁盤的。這樣針對Account表的更新，除了現有的2000IO/s就還需要額外的2000IO/s，也就需要再購買50個磁盤，這樣磁盤的需求就加倍了。同時，這還是假設用于將日志文件索引維持在20天的長度上的刪除操作，可以作為一個批處理任務在空閑時間執行。
?????? 現在我們已經分析了使用B-樹來作為Acct-ID||Timestamp索引的情況，因為它是當前商業系統中使用的最通用的基于磁盤的訪問方法。事實上，也沒有什么其他經典的磁盤索引結構可以提供更好的IO性價比。在第5節中我們還會討論下如何得出這樣的結論的。
?????? 本文提出的LSM-Tree訪問方法使得我們可以使用更少的磁盤運動來執行在Acct-ID||Timestamp上的頻繁插入操作。LSM-Tree通過使用某種算法，該算法會對索引變更進行延遲及批量處理，并通過一種類似于歸并排序的方式高效地將更新遷移到磁盤。正如我們將在第5節看到的，將索引節點放置到磁盤上的這一過程進行延遲處理，是最根本的，LSM-Tree結構通常就是包含了一系列延遲放置機制。LSM-Tree結構也支持其他的操作，比如刪除，更新，甚至是那些具有long latency的查詢操作。只有那些需要立即響應的查詢會具有相對昂貴的開銷。LSM-Tree的主要應用場景就是像例1.2那樣的，查詢頻率遠低于插入頻率的情況(大多數人不會像開支票或存款那樣經常查看自己的賬號活動信息)。在這種情況下，最重要的是降低索引插入開銷；與此同時，也必須要維護一個某種形式的索引，因為順序搜索所有記錄是不可能的。
?????? 在第2節，我們會引入2-組件LSM-Tree算法。在第3節，我們會分析下LSM-Tree的性能，并提出多組件LSM-Tree。在第4節，我們會描述下LSM-Tree的并發和恢復的概念。在第5節，我們會討論下其他的一些訪問方式，以及它們的性能。第6節是總結，我們會指出LSM-Tree的一些問題，并提出一些擴展建議。
2. The Two Component LSM-Tree Algorithm
?????? LSM-Tree由兩個或多個類樹的數據結構組件構成。本節，我們只考慮簡單的兩個組件的情況，同時假設LSM-Tree索引的是例1.2中的歷史記錄表中的記錄。如下圖
?????? 在每條歷史記錄表中的記錄生成時，會首先向一個日志文件中寫入一個用于恢復該插入操作的日志記錄。然后針對該歷史記錄表的實際索引節點會被插入到駐留在內存中的C0樹，之后它將會在某個時間被移到磁盤上的C1樹中。對于某條記錄的檢索，將會首先在C0中查找，然后是C1。在記錄從C0移到C1中間肯定存在一定時間的延遲，這就要求能夠恢復那些crash之前還未被移出到磁盤的記錄?；謴蜋C制將會在第4節討論，現在我們只是簡單地認為那些用于恢復插入的歷史記錄數據的日志記錄可以被看做邏輯上的日志；在恢復期間我們可以重構出那些已經被插入的歷史記錄，同時可以重建出需要的那些記錄并將這些記錄進行索引以恢復C0丟失的內容。
?????? 向駐留在內存中的C0樹插入一個索引條目不會花費任何IO開銷。但是，用于保存C0的內存的成本要遠高于磁盤，這就限制了它的大小。這就需要一種有效的方式來將記錄遷移到駐留在更低成本的存儲設備上的C1樹中。為了實現這個目的，在當C0樹因插入操作而達到接近某個上限的閾值大小時，就會啟動一個rolling merge過程，來將某些連續的記錄段從C0樹中刪除，并merge到磁盤上的C1樹中。圖2.2描述了這樣的一個過程。
?????? C1樹具有一個類似于B-樹的目錄結構，但是它是為順序性的磁盤訪問優化過的，所有的節點都是100%滿的，同時為了有效利用磁盤，在根節點之下的所有的單頁面節點都會被打包(pack)放到連續的多頁面磁盤塊(multi-page block)上；類似的優化也被用在SB-樹中。對于rolling merge和長的區間檢索的情況將會使用multi-page block io，而在匹配性的查找中會使用單頁面節點以最小化緩存需求。對于root之外的節點使用256Kbytes的multi-page block大小，對于root節點根據定義通常都只是單個的頁面。
?????? Rolling merge實際上由一系列的merge步驟組成。首先會讀取一個包含了C1樹中葉節點的multi-page block，這將會使C1中的一系列記錄進入緩存。之后，每次merge將會直接從緩存中以磁盤頁的大小讀取C1的葉節點，將那些來自于葉節點的記錄與從C0樹中拿到的葉節點級的記錄進行merge，這樣就減少了C0的大小，同時在C1樹中創建了一個新的merge好的葉節點。
?????? merge之前的老的C1樹節點被保存在緩存中的稱為emptying block{!掏空ing，即該block中的那些節點正在被掏空}的multi-page block中，而新的葉節點會被寫入到另一個稱為filling block{!填充ing，即該block正在被不斷地用新節點填充}的緩存中的multi-page block。當C1中新merge的節點填滿filling block后，該block會被寫入到磁盤上的新空閑區域中。如果從圖2.2中看的話，包含了merge結果的新的multi-page block位于圖中老節點的右側。后續的merge步驟會隨著C0和C1的索引值的增加而發生，當達到閾值時，就又會從最小值開始啟動rolling merge過程。
?????? 新的merge后的blocks會被寫入到新的磁盤位置上，這樣老的blocks就不會被覆蓋，這樣在crash發生后的恢復中就是可用的。C1中的父目錄節點也會被緩存在內存中，此時也會被更新以反映出葉節點的變動，同時父節點還會在內存中停留一段時間以最小化IO；當merge步驟完成后，C1中的老的葉節點就會變為無效狀態，之后會被從C1目錄結構中刪除。通常，每次都是C1中的最左邊的葉節點記錄參與merge，因為如果老的葉節點都是空的那么merge步驟也就不會產生新的節點，這樣也就沒有必要進行。除了更新后的目錄節點信息外，這些最左邊的記錄在被寫入到磁盤之前也會在內存中緩存一段時間。用于提供在merge階段的并發訪問和從crash后的內存丟失中進行恢復的技術將會在第4節詳細介紹。為了減少恢復時的重構時間，merge過程需要進行周期性的checkpoints，強制將緩存信息寫入磁盤。
2.1 How a Two Component LSM-Tree Grows
?????? 為了追蹤LSM-tree從誕生那一刻開始的整個變化過程，我們從針對C0的第一次插入開始。與C1樹不同，C0樹不一定要具有一個類B-樹的結構。首先，它的節點可以具有任意大小：沒有必要讓它與磁盤頁面大小保持一致，因為C0樹永不會位于磁盤上，因此我們就沒有必要為了最小化樹的深度而犧牲CPU的效率{!如果看下B-樹，就可以知道實際上它為了降低樹的高度，犧牲了CPU效率。在當整個數據結構都是在內存中時，與二分查找相比，B-樹在查找時，在節點內部的比較，實際上退化成了順序查找，這樣它查找一個節點所需的比較次數實際上要大于AVL的比較次數}。這樣，一個2-3樹或者是AVL樹就可以作為C0樹使用的一個數據結構。當C0首次增長到它的閾值大小時，最左邊的一系列記錄將會從C0中刪除(這應是以批量處理的模式完成，而不是一次一條記錄)，然后被重新組織成C1中的一個100%滿的葉子節點。后續的葉節點會按照從左到右的順序放到緩存中的一個multi-page block的初始頁面中，直到該block填滿為止；之后，該block會被寫到磁盤中，成為C1樹的磁盤上的葉級存儲的第一部分。隨著后續的葉節點的加入，C1樹會創建出一個目錄節點結構，具體細節如下。
?????? C1樹的葉節點級的后續multi-page block會按照鍵值遞增的順序被寫入到磁盤中，以防止C0樹大小超過閾值。C1樹的上級目錄節點被存放在獨立的multi-page block buffers或者是單頁面緩存中，無論存在哪里，都是為了更好地利用內存和磁盤；目錄節點中的記錄包含一些分隔點，通過這些分隔點可以將用戶訪問導引到單個的singe-page節點中，像B-樹那樣。通過這種指向葉級節點的single-page索引節點可以提供高效的精確匹配訪問，避免了multi-page block的讀取，這樣就最小化了緩存需求。這樣在進行rolling merge或者按range檢索時才會讀寫multi-page block，對于索引化的查詢(精確匹配)訪問則讀寫singe-page節點。[22]中提出了一種與之類似但又稍有不同的結構。在一系列葉級節點blocks被寫出時，那些由C1的目錄節點組成的還未滿的multi-page block可以保留在緩存中。在如下情況下，C1的目錄節點會被強制寫入磁盤：
?
?
?????? 對于第一種情況，只有被填滿的那個block會被寫出到磁盤。對于后兩個情況，所有的multi-page block buffers和目錄節點buffers都會被flush到磁盤。
?????? 當C0樹的最右邊的葉節點記錄首次被寫出到C1樹后，整個過程就又會從兩個樹的最左端開始，只是從現在開始，需要先把C1中的葉子級別的multi-page block讀入到buffer，然后與C0樹中的記錄進行merge，產生出需要寫入到磁盤的新的C1的multi-page leaf block。
?????? 一旦merge過程開始，情況就變地更復雜了。我們可以把整個兩組件LSM-tree的rolling merge過程想象成一個具有一定步長的游標循環往復地穿越在C0和C1的鍵值對上，不斷地從C0中取出數據放入到磁盤上才C1中。該rolling merge游標在C1樹的葉節點和更上層的目錄級都會有一個邏輯上的位置。在每個層級上，所有當前正在參與merge的multi-page blocks將會被分成兩個blocks：”emptying block”-它內部的記錄正在搬出，但是還有一些信息是merge游標所未到達的，”filling block”-反映了此刻的merge結果。類似地，該游標也會定義出”emptying node”和”filling node”，這兩個節點此刻肯定是已在緩存中。為了可以進行并發訪問，每個層級上的”emptying block”和”filling block”包含整數個的page-sized C1樹節點。(在對執行節點進行重組的merge步驟中，針對這些節點的內部記錄的其他類型的并行訪問將會被阻塞)。當所有被緩存的節點需要被flush到磁盤時，每個層級的所有被緩存的信息必須被寫入到磁盤上的新的位置上(同時這些位置信息需要反映在上層目錄信息中，同時為了進行恢復還需要產生一條日志記錄)。此后，當C1樹某一層級的緩存中的filling block被填滿及需要再次flush時，它會被放到新的磁盤位置上。那些可能在恢復過程中需要的老的信息永不會被覆蓋，只有當后續的寫入提供了足夠信息時它們才可以宣告失效。第4節來還會進行一些關于roling merge過程的更細節的解釋，在那一節里還會考慮關于并發訪問和恢復機制的設計。
?????? 在C1的某個層級上的rolling merge過程，需要很高的節點傳輸速率時，所有的讀寫都是以multi-page blocks為單位進行的，對于LSM-tree來說，這是一個很重要的效率上的優化。通過減少尋道時間和旋轉延遲，我們認為與普通的B-樹節點插入所產生的隨機IO相比，這樣做可以得到更大的優勢(我們將會在3.2節討論其中的優勢)?？偸且詍ulti-page blocks為單位進行寫入的想法源自于由Rosenblum和Ousterhout發明的Log-Structured File System，Log-Structured Merge-tree的叫法也源于此。需要注意的是，對于新的multi-page blocks的寫入使用連續的新的磁盤空間，這就意味著必須對磁盤區域進行包裝管理，舊的被丟棄的blocks必須能被重用。使用記錄可以通過一個內存表來管理；舊的multi-page blocks作為單個單元被置為無效和重用，通過checkpoint來進行恢復。在Log-Structured File System中，舊的block的重用會引入顯著的IO開銷，因為blocks通常是半空的，這樣重用就需要針對該block的一次讀取和寫入。在LSM-tree中，blocks是完全空的，因此不需要額外的IO。
2.2 Finds in the LSM-tree index
?????? 當在LSM-tree index上執行一個需要理解響應的精確匹配查詢或者range查詢時，首先會到C0中查找所需的那個或那些值，然后是C1中。這意味著與B-樹相比，會有一些額外的CPU開銷，因為現在需要去兩個目錄中搜索。對于那些具有超過兩個組件的LSM-tree來說，還會有IO上的開銷。先稍微講一下第3章的內容，我們將一個具有組件C0，C1，C2…Ck-1和Ck的多組件LSM-tree，索引樹的大小伴隨著下標的增加而增大，其中C0是駐留在內存中的，其他則是在磁盤上。在所有的組件對(Ci-1,Ci)之間都有一個異步的rolling merge過程負責在較小的組件Ci-1超過閾值大小時，將它的記錄移到Ci中。一般來說，為了保證LSM-tree中的所有記錄都會被檢查到，對于一個精確匹配查詢和range查詢來說，需要訪問所有的Ci組件。當然，也存在很多優化方法，可以使搜索限制在這些組件的一個子集上。
?????? 首先，如果生成邏輯可以保證索引值是唯一的，比如使用時間戳來進行標識時，如果一個匹配查找已經在一個早期的Ci組件中找到時那么它就可以宣告完成了。再比如，如果查詢條件里使用了最近時間戳，那么我們可以讓那些查找到的值不要向最大的組件中移動。當merge游標掃描(Ci,Ci+1)對時，我們可以讓那些最近某個時間段(比如τi秒)內的值依然保留在Ci中，只把那些老記錄移入到Ci+1。在那些最常訪問的值都是最近插入的值的情況下，很多查詢只需要訪問C0就可以完成，這樣C0實際上就承擔了一個內存緩沖區的功能。[23]中也使用了這一點，同時這也是一種重要的性能優化。比如，用于短期事務UNDO日志的索引訪問模式，在中斷事件發生時，通常都是針對相對近期的數據的訪問，這樣大部分的索引就都會是仍處在內存中。通過記錄每個事務的啟動時間，就可以保證所有最近的τ0秒內發生的事務的所有日志都可以在C0中找到，而不需要訪問磁盤組件。
2.3 Deletes，Updates and Long-Latency Finds in the LSM-tree
?????? 需要指出的是刪除操作可以像插入操作那樣享受到延遲和批量處理帶來的好處。當某個被索引的行被刪除時，如果該記錄在C0樹中對應的位置上不存在，那么可以將一個刪除標記記錄(delete node entry)放到該位置，該標記記錄也是通過相同的key值進行索引，同時指出將要被刪除的記錄的Row ID(RID)。實際的刪除可以在后面的rolling merge過程中碰到實際的那個索引entry時執行：也就是說delete node entry會在merge過程中移到更大的組件中，同時當碰到相關聯的那個entry，就將其清除。與此同時，查詢請求也必須在通過該刪除標記時進行過濾，以避免返回一個已經被刪除的記錄。該過濾很容易進行，因為刪除標記就是位于它所標識的那個entry所應在的位置上，同時在很多情況下，這種過濾還起到了減少判定記錄是否被刪除所需的開銷{!比如對于一個實際不存在的記錄的查找，如果沒有該刪除標記，需要搜索到最大的那個Ci組件為止，但是如果存在一個刪除標記，那么在碰到該標記后就可以停止了}。對于任何應用來說，那些會導致索引值發生變化{!比如一條記錄包含了ID和name，同時是以ID進行索引的，那么如果是name更新了，很容易，只需要對該記錄進行一個原地改動即可，但是如果是ID該了，那么該記錄在索引中的位置就要調整了，因此是很棘手的}的更新都是不平凡的，但是這樣的更新卻可以被LSM-tree一招化解，通過將該更新操作看做是一個刪除操作+一個插入操作。
?????? 還可以提供另一種類型的操作，可以用于高效地更新索引。一個稱為斷言式刪除(predicate deletion)的過程，提供了一種通過簡單地聲明一個斷言，就可以執行批量刪除的操作方式。比如這樣的一個斷言，刪除那些時間戳超過20天的所有的索引值。當位于最大組件里的受斷言影響的記錄，通過日常的rolling merge過程進入到內存時，就可以簡單地將他們丟棄來實現刪除。另一種類型的操作，long-latency find，對于那些可以等待很長時間(所需等待的時間實際上是由最慢的那個merge游標的速度決定的)的查詢來說，它提供了一種高效地響應方式。通過向C0中插入一個find note entry，它被移入到更大的組件的過程實際上也就是該查詢執行的過程，一旦該find note entry到達了LSM-tree中最大的那個組件的對應位置，該long-latency find所對應的那些匹配的RID列表也就生成完畢了。
3. Cost-Performance and the Multi-Component LSM-Tree
?????? 本節我們會從一個兩組件LSM-tree開始分析下LSM-tree的性價比。同時會將LSM-tree與具有與之類似的索引規模的B-樹進行對比，比較下它們在大量插入操作下的IO資源利用情況。正如我們將在第5節所述的那樣，其他的基于磁盤的訪問方式在插入新索引節點所需的IO開銷上都基本上與B-樹類似。我們在此處對LSM-tree和B-樹進行比較的最重要的原因是這兩個結構很容易比較，它們都在葉子節點上為每個以特定順序索引的記錄行保存了一個entry，同時上層目錄信息可以沿著一系列頁面大小的節點將各種訪問操作進行指引。通過與低效但是很好理解的B-樹的對比分析，對于LSM-tree在新節點插入上的所具有的IO優勢的分析，可以更好地進行表達。
?????? 在3.2節中，我們會比較IO開銷，并將證明兩組件LSM-tree的開銷與B-樹的開銷的比值實際上兩個因子的乘積{!即3.2節中的公式3.4}。第一個因子， ，代表了LSM-tree通過將所有的IO以multi-page blocks進行得到的優勢，這樣通過節省大量的尋道和旋轉延遲可以更有效地利用磁盤磁臂。COSTπ代表了磁盤以multi-page blocks為單位讀寫一個page時的開銷，COSTp則代表了隨機讀寫一個page時的開銷。第二個因子是1/M，代表了在merge過程中的批量處理模式帶來的效率提升。M是從C0中merge到C1中的一個page-sized的葉節點中的記錄的平均數目。對于B樹來說，每條記錄的插入通常需要對該記錄所屬的節點進行兩次IO(一次讀出一次寫入)，與此相比，可以向每個葉子中一次插入多條記錄就是一個優勢。根據5分鐘法則，例1.2中的葉子節點在從B樹中讀入后之后短暫地在內存中停留，在它被再一次使用時它已不在內存了。因此對于B樹索引來說就沒有一種批量處理的優勢：每個葉節點被讀入內存，然后插入一條記錄，然后寫出去。但是在一個LSM-tree中，只要與C1組件相比C0組件足夠大，總是會有一個批量處理效果。比如，對于16字節的索引記錄大小來說，在一個4Kbytes的節點中將會有250條記錄。如果C0組件的大小是C1的1/25，那么在每個具有250條記錄的C1節點的Node IO中，將會有10條是新記錄{!也就是說在此次merge產生個node中有10條是在C0中的，而C0中的記錄則是用戶之前插入的，這相當于將用戶的插入先暫存到C0中，然后延遲到merge時寫入磁盤，這樣這一次的Node IO實際上消化了用戶之前的10次插入，的確是將插入批量化了}。很明顯，由于這兩個因素，與B-樹相比LSM-tree效率更高，而rolling merge過程則是其中的關鍵。
?????? 用來代表multi-page block比single-page的優勢之處的 實際上是個常量，為了使它生效我們無需對LSM-tree的結構進行任何處理。但是merge中的1/M的批量模式效率是跟C0和C1的大小之比成比例的；與C1相比，C0越大，效果越好；某種程度上說，這意味著我們可以通過使用更大的C0來節省額外的磁盤磁臂開銷，但是這也需要更大的內存開銷來容納下C0組件。這也是在使用LSM-tree時需要考慮的，會在3.3節中對此進行研究。一個三組件LSM-tree具有一個內存組件C0和兩個基于磁盤的組件C1和C2，并且隨著組件大小隨下標增加而增大。這樣，除了C0和C1之間會有一個rolling merge過程，在C1和C2之間也會存在一個rolling merge過程，來負責在小的組件達到閾值大小時，將記錄從小的組件中移到大的組件中。三組件LSM-tree的優勢在于，它可以通過選擇C1的大小來實現C0和C1以及C1和C2之間的比率大小來提高批處理效率。這樣C0的大小就可以變得更小，可以大大地降低開銷。{!因為在只有C0和C1的情況下，C1的大小有一個硬性要求，它必須能夠容得下所有的記錄，這樣C0的大小選擇就沒有多少自由，而引人C2后，我們可以利用C2來保證可以存儲下所有的記錄，而C1就可以用來調整與C0的比例，而它就可以小點，這樣由于目標是為了讓C0/(C1+C0)盡量小，那么C0也可以變得小點就可以達到兩組件下的效果}。
3.1 The Disk Model
?????? 與B-樹相比LSM-tree的優勢主要在于降低IO開銷方面(盡管與其他的已知的磁盤結構相比，它的磁盤組件都是100%慢，這也降低了容量方面的開銷)。LSM-tree在IO開銷上的優勢，部分是因為一個page IO可以平攤到一個multi-page block中的多個page上。
?????? 定義3.1.1 IO開銷和數據熱度 當我們將某種特定數據存儲在磁盤上時，比如表中的行或者是索引中的記錄，會發現隨著數據量的增加，在給定的應用環境下，磁盤磁臂的利用率會越來越高。當我們購買了一塊磁盤時，我們實際上為兩樣東西付了款：首先是磁盤容量，其次是磁盤IO能力。對于任意類型應用來說，通常其中的一個會成為限制因素。如果容量是瓶頸，我們會發現磁盤填滿時，應用程序只使用了磁盤磁臂所提供的IO能力的一部分；反過來，如果我們發現在添加數據時，磁盤磁臂已經被充分使用，但是磁盤還有剩余空間，這就意味著IO能力是瓶頸。
?????? 設峰值期間的一次隨機的page IO使用所具有的開銷為：COSTp，它是基于對磁盤臂的使用算出的，同時作為multi-page block的一部分的一次磁盤page IO的開銷我們用COSTπ表示，該值要小很多，因為它將尋道時間和旋轉延時平攤到了多個page上。我們使用下面的這些名詞來表示各項存儲開銷：
COSTd= 1Mbytes磁盤存儲的開銷 COSTm= 1Mbytes內存存儲的開銷 COSTp=disk arm cost to provide 1 page/second IO rate, for random pages COSTπ=disk arm cost to provide 1 page/second IO rate,as part of multi-page block IO?????? 假設一個應用程序需要S Mbytes的數據存儲以及每秒H個random page訪問的IO傳輸需求(假設數據不會被緩存)，那么磁盤臂的費用就是H·COSTp，磁盤存儲的費用就是S·COSTd。取決于哪個是瓶頸，剩下的那個就是免費可得的，這樣磁盤數據的訪問開銷COST-D就是：
COST-D=max(H·COSTp, S·COSTd)?????? 在數據不會被緩存的假設下，COST-D也就是該應用程序用于支持數據訪問的總開銷，COST-TOT。在這種情況下，如果總的磁盤存儲需求S是個常量，那么總開銷就是隨隨機IO率H線性增長的。在磁盤IO上升到與磁盤存儲S相同的開銷時{!如果磁盤IO還未上升到與存儲S相同開銷時，它就是免費的，也就不需要考慮用內存支持它}，就可以考慮使用內存緩存來取代磁盤IO。假設在這些情況下，可以用內存緩存來支持隨機IO請求，那么磁盤的開銷就又只取決于所需的磁盤存儲空間，那么訪問緩存數據的開銷COST-B，就可以簡單地表示為內存的開銷加上磁盤存儲的開銷：
COST-B= S·COSTm+ S·COSTd那么現在用于支持該應用程序的數據訪問的總開銷就是由min(COST-D, COST-B)決定的：
COST-TOT=min(max(H·COSTp, S·COSTd), S·COSTm+ S·COSTd)這樣隨著針對給定大小的數據S的頁面訪問頻率H的增長，COST-TOT就由三部分組成。如圖3.1，我們畫出了COST-TOT/MByte與H/S的變化關系。在S比較小的情況下，COST-TOT由磁盤存儲開銷S·COSTd決定，對于固定的S它是個常量。隨著H/S的值的增長，開銷逐漸由磁盤磁臂的使用開銷H·COSTp所控制，同時對于固定的S來說，它與H/S成正比。最后，在五分鐘法則所指出的內存駐留點上，主要因素變成了S·COSTm+ S·COSTd，這就主要由內存開銷來決定，因為COSTm >> COSTd。師從論文[6]，我們將數據的熱度定義為H/S，同時我們命名出三個區域：cold，warm和hot。Hot數據足夠高的訪問頻率H，因此它的熱度H/S，表明它應該被放入內存。另一個區域，cold數據受限于磁盤空間：它所占據的磁盤空間所能提供的IO能力已足夠使用。居于兩者之間的是warm數據，對于它來說磁盤磁臂是限制因素。它們之間的邊界劃分如下：
Tf= COSTd/ COSTp=cold和warm數據之間的分界點(freezing-冰點) Tb= COSTm/ COSTp=warm和hot數據之間的分界點(boiling-沸點)?????? {!首先數據熱度是用H/S來定義的，而Tf和Tb不過是一種特殊的熱度，因此它們不過是代表了H/S= COSTd/ COSTp 和H/S= COSTm/ COSTp 的情況。簡單分析下H/S= COSTm/ COSTp的情況，此時H·COSTp=S·COSTm ，意味著該份數據所承受的隨機訪問開銷已經等于將其完全放入內存所需的內存開銷，可見其著實是很hot了}
?????? 通過使用COSTπ替代COSTp我們可以得出multi-page block訪問模式下的類似邊界。Warm和hot區域間的分界實際上就是五分鐘法則[13]的通用化。
?????? [注：注意圖中橫坐標的單位的理解，accesses/sec/Mbyte->( accesses/sec)/( Mbyte)，其中accesses/sec即是H的單位，Mbyte則對應著S的單位]
?????? 正如[6]所說，在訪問很均勻的情況下，可以很容易地計算出一個數據庫表的熱度來。然而，熱度還依賴于具體的訪問方式：熱度實際上是與實際的磁盤訪問頻率相關，而不是邏輯上的插入頻率。可以這樣說，LSM-tree的成功之處就在于它減少了實際的磁盤訪問次數，因此就減低了索引的數據的熱度。該第6節中我們會重新討論下該觀點。
Multi-page block IO Advantage
?????? 通過采用multi-page block IO獲取的優勢對于幾個早期的訪問方式來說是至關重要的，比如Bounded Disorder files，SB-tree，和Log Structured files。一個1989年的IBM出版物針對DB2在IBM 3380磁盤上的性能進行了分析，給出了下面的結果：“…用于完成一次單個page讀取的時間大約是20ms(10ms用于尋道，8.3毫秒的旋轉延遲，1.7ms用于讀取)…用于執行一次順序式預讀[以64個連續頁面大小為單位]大約是125ms(10ms用于尋道，8.3毫秒的旋轉延遲，106.9ms用于讀取64條記錄[page])，這樣每個page只需2ms”。因此multi-page block IO情況下的2ms比上隨機IO下的20ms，也就是COSTπ/COSTp，大概等于1/10。最近的一個關于SCSI-2磁盤的分析，提到讀取4Kbyte頁面大小大概需要9ms的尋道時間，5.5ms的旋轉延遲，1.2ms的讀取時間，總共是16ms。而讀取64個連續的4Kbyte頁面，需要9ms的尋道時間，5.5ms的旋轉延遲，80ms的讀取時間，總共是95ms，算下來單個頁面需要95/64=1.5ms。COSTπ/COSTp仍還是大概等于1/10。
我們來分析一個具有1GByte(它的開銷大概是1000$)的SCSI-2磁盤的工作站，IO峰值大概是每秒60-70個IO請求。通常情況下的IO頻率要更低一些，大概是每秒40個IO請求。multi-page block IO的優勢是很明顯的。
1995年的一個典型工作站的成本
COSTm=$100/Mbytes COSTd=$1/Mbytes COSTp=$25/(IOs/sec)COSTπ=$2.5/(IOs/sec) Tf= COSTd/ COSTp=0.04IOs/(sec·MBytes) (freezing point) Tb= COSTm/ COSTp=4IOs/(sec·MBytes) (boiling point)我們通過Tb可以推導出五分鐘法則所對應的時間間隔值τ，該值表明數據所維持的每秒的單個page的IO訪問開銷已經達到了用來保存它所需的內存開銷，即：
(1/τ)·COSTp=pagesize·COSTm。對τ進行求解，可得τ=(1/ pagesize)·(COSTp/ COSTm)=1/( pagesize·Tb)，根據上面所給出的值，及pagesize=0.004Mbytes，可得τ=1/(0.004*4)=62.5seconds/IO。
例3.1 為了達到例1.1中TPC-A應用的1000TPS，首先這意味著針對Account表的H=2000 IOs/sec，它本身由100,000,000個100字節的行組成，總大小S=10GBytes。此處的磁盤存儲開銷就是S·COSTd=$10,000，而磁盤IO開銷將是H·COSTp=$50,000。數據熱度T=H/S=2000/10,000=0.2，在冰點之上(是它的5倍，冰點是0.04,0.2/0.04=5)，同時也還在浮點之下。該warm數據只用到了磁盤存儲能力的1/5，這樣瓶頸就是磁盤磁臂。例1.2中歷史記錄表的20天的Acct-ID||Timestamp索引也是類似的情況。正如我們在例1.2中的計算結果，這樣的一個B-樹索引大概需要9.2GBytes的葉級節點。如果樹只有70%的full，整個樹大概需要13.8GBytes的存儲，但是它具有與account表相同的IO請求率，這也意味著它們具有類似的數據熱度{!H值相同，S值一個是9.2，一個是13.8，因此H/S值相差不大，都屬于warm數據}。
3.2 Comparison of LSM-tree and B-tree I/O costs
我們將會分析下如下那些mergeable的索引操作的IO開銷：插入，刪除，更新，和long-latency find。下面的討論將會提供LSM-tree與B-樹的對比分析結果。
B-樹的插入開銷公式
?????? 考慮執行一次B-樹插入操作的磁盤磁臂開銷。首先需要對該記錄所需要放置到的樹中的位置進行訪問，這將會產生沿著樹節點的自上而下的搜索過程。假設針對樹的后續插入是針對葉子上的某個隨機的位置，這樣就不能保證訪問路徑上的節點所在的頁面會因為之前的插入操作而進入內存。如果后續的插入是在一系列遞增的key-values，即insert-on-the-right的情況，這種情況就是一種不滿足上述假設的常見情況。需要指出的是，這種insert-on-the-right的情況是可以高效地被B-樹數據結構所處理的，因為如果B-樹一直是往右增長的話，只需要很少地IO開銷；事實上這也是B-樹所擅長處理的情況?，F在已有很多其他類似的結構可以用來作為這種值不斷增長的日志記錄的索引機制。
[21]提出了B-樹的實際深度(effective depth)概念，用De表示。它代表了在B樹的一次隨機查找中，不在緩存中的page的平均個數。對于例1.2中的用來索引Account-ID||timestamp的B-樹大小來說，De的值大約是2。
?????? 為了執行B-樹的一次插入，首先我們需要對葉級page執行一次key-value搜索(需要De個IO操作)，進行更新，然后寫出一個對應的臟頁(1次IO)。我們忽略相對不那么頻繁的節點分裂帶來的影響。在這個過程中的page的讀寫都是開銷為COSTp的隨機訪問，這樣一次B-樹插入的總的IO開銷COST(B-ins)就是：
(3.1) COST(B-ins)= COSTp·(De+1)
LSM-tree的插入開銷公式
為了計算出LSM-tree的一次插入的開銷，我們需要對多次插入進行平攤分析，因為針對內存組件C0的單個插入只是不定期的對IO產生影響。正如我們在本節開始所解釋的，LSM-tree比B-樹相比，它的性能上的優勢基于兩種批處理模式的影響。第一個就是前面提到將單頁面IO的開銷降低為COSTπ。第二個就是，將新插入的記錄merge到C1中的延遲效果，這就允許被插入的記錄可以積累在C0中，這樣在C1的葉級page從磁盤讀入到內存在寫回到磁盤的過程中，可以一次將幾條記錄同時merge進來。與此相比，我們已經假設對于B-樹來說，很少會一次向一個葉級page中插入多于一條的記錄。
定義3.2.1 Batch-Merge參數M. 為了對這種multiple-entries-per-leaf的批量模式的影響進行量化，對于給定的一個LSM-tree，我們定義M為在rolling merge過程中，C1樹的每個單頁面葉子節點中來自于C0樹的記錄的平均個數。對于特定的LSM-tree來說，M基本上是一個很穩定的值，M的值實際上是由索引entry的大小和C1與C0的葉級數據大小比例來決定的。我們定義如下幾個大小參數：
Se=entry(index entry)size in bytes Sp=page size in bytes S0=size in Mbytes of C0 component leaf level S1=size in Mbytes of C1 component leaf level那么，一個page里的entries個數就是Sp/Se，LSM-tree中位于C0中的entries比例是S0/(S0+S1)，那么參數M可以表示為：
(3.2) M=(Sp/Se)·(S0/(S0+S1))
?????? 可以看出，C0比C1大的越多，M也越大。典型情況下，S1=40·S0，同時每個磁盤頁的記錄數，Sp/Se=200，此時M=5。給定M的情況下，我們就能夠給出LSM-tree的一次插入所具有的開銷的嚴格的公式化表示。我們簡單地將C1樹的葉級節點讀入和寫出的開銷，2·COSTπ，平攤到被merge到C1樹的葉級節點中的M次插入中。
(3.3) COST(LSM-ins)=2·COSTπ/M
需要注意的是，我們忽略了LSM-tree和B-樹中那些與索引更新產生的IO相關的但又無關緊要的開銷。
{!理解上面這些內容的關鍵在于理解平攤分析的思想，在LSM-tree中，插入操作實際上不是來了就真正執行地，而是會被保存在C0中，這樣C0中的每條記錄實際上就對應著用戶的一次插入操作，然后這些插入操作實際上回被延遲到后面的rolling merge過程中，之后才會被反映到磁盤上，我們具體到rolling merge過程中的一個節點來看，該節點會首先從C1中讀入到內存，然后會與C0做merge，就看它能從C0中帶出幾條記錄，帶出多少條記錄也就意味著它將之前的多少個插入操作寫入到了磁盤，因此這一個節點的讀寫實際上就包含了之前的多個插入操作，也就是插入操作達到了批量化處理的目的。而C0中有多少條記錄會落在該節點內，則是與C0與C1的記錄總條數相關的，基本上C1中應該有占S0/(S0+S1)是在C0中的。}
LSM-tree與B-樹插入開銷的比較
如果我們將這兩種數據結構所對應的開銷公式(3.1)和(3.3)進行比較，我們可以得到如下比率：
(3.4) COST(LSM-ins)/ COST(B-ins)=K1·(COSTπ/COSTp)·(1/M)
此處，K1是一個(near)常數，2/(De+1)，對于我們所考慮的索引大小來說大概是0.67。上述公式表明，LSM-tree和B-樹的一次插入的IO開銷的比值與我們之前討論過的兩個批量處理模式是直接相關的：COSTπ/COSTp，一個很小的分數，代表了以multi-page block為單位的page IO和隨機的page IO之間的開銷之比，而1/M，M是rolling merge期間每個page所批量導出的C0中的記錄數。通常，這兩個因素的乘積可以帶來接近兩個數量級的成本降低。當然，這種改進只有在數據熱度相對比較高的情況下才能體現出來，這樣將數據從B-樹遷移到LSM-tree將會大大減少所需的磁盤數。
例3.2 如果我們假設例1.2中的索引需要1GBytes的磁盤空間，但是需要存放到10GB的磁盤空間上以獲取必需的磁盤IO能力來支撐所需的磁盤訪問頻率。那么其中對于磁盤磁臂開銷來說肯定存在提升空間。如果公式(3.4)給出的插入開銷比率是0.02=1/50，那么這就意味著我們可以減少索引和磁盤開銷：LSM-tree只需要0.7GBytes的磁盤空間，因為它采用了被packed的記錄保存方式，同時降低了磁盤所需的IO能力。但是，需要注意的是無論多么有效的LSM-tree最多也只能將它降低到磁盤容量所需的那個開銷水平上。如果我們是針對從一個需要存放到35GB磁盤上所提供的IO能力的具有1GBytes大小的B-樹的話，那么就完全達到上面所提到的那個1/50的成本提升。{!也就是說在10GB的情況下，如果按照上面1/50的比率來算，如果使用LSM-tree按理來說只需要10/50GB=0.2GB，但是另一方面為了滿足硬性的存儲需求，LSM-tree所需的磁盤空間不能小于0.7GBytes，因此實際上沒有完全發揮出LSM-tree所帶來的IO上的降低，也就是說這種情況下對于0.7 GBytes 的磁盤來說，它的IO能力還有空閑。但是對于35GB的情況來說，按照上面1/50的比率來算就剛好是0.7GB，這樣因使用LSM-tree所帶來的IO開銷上的降低就被全部利用了。}
?
總結
以上是生活随笔為你收集整理的一周一论文（翻译）——[Acta 1996] The Log-Structured Merge-Tree (LSM-Tree)的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 高阶数据结构：SSTable
- 下一篇： 一周一论文（翻译）——[SIGMOD 2