週末，杭州大雪，悽風慘雨，只能待在家裡喝茶讀文。
微軟之前提出了一個叫做Deuteronomy（dutəˈrɑnəmi，a book of the Bible that repeats the Ten Commandments and records much of Mosaic Law。）的架構，這套架構的核心思想是將資料裡的事務元件（Transaction Component）和儲存元件（Storage Component）分開，這樣帶來的好處就是系統的靈活度增加了，而且各個模組可以獨立的向前演進，方便適配快速變化的基礎環境。精細分工+尖端化這個演進方向是個很有意思的話題，想想微服務，小而美，日本製造和德國製造，啊扯遠了。
論文中實現的LLAMA［1］可以作為Deuteronomy的儲存元件，其提供了面向page操作的快取和儲存功能，並保證對page狀態的修改是原子的。
LLAMA架構圖見下，既可以作為一個通用的儲存元件，也可以作為資料庫核心的儲存模組提供服務。
圖1 LLAMA 架構
LLAMA的背景是隨著硬體的快速發展，傳統軟體架構雖然也獲得了紅利，但是沒有充分的利用硬體能力，論文認為需要重新思考資料庫架構。重新思考的核心是三個方面，
充分利用無鎖發揮多核能力
考慮多級Cache的影響，減少cache invalidtions（偏重指CPU cache）
透過Log Structuring節約寫，變隨機為順序
LLAMA從兩個角度去解決上面三個問題。
首先，使用delta（圖2裡面的record）描述對page的修改，而不是直接修改page 本身（見下圖）。傳統B+Tree在更新page時候是加鎖，修改，放鎖，這種操作對上面三個問題的前兩個都造成了很大的破壞。頻繁的加鎖放鎖導致較低的多核效能（如果將CPU每次操作的流程視覺化，我們就能更直觀的認識鎖對效能的巨大影響，只是我也沒見過這樣的工具），且讓系統變得複雜。同時，頁面被修改之後，舊的頁面被回收也導致了cache失效，進一步影響了效能。使用delta同時緩解了兩個問題。首先，對page的修改先放到delta裡面，這樣原始的page不用做任何改動，自然也不用加鎖，也不會導致cache失效。如果修改很多，將delta和page做一次consolidation（讀的時候是從最新的delta一直讀下去，所以如果長時間不做consolidation，讀效能會很差，這裡跟一些K-V系統使用的Log-Structured-Merge思路類似，只是更加偏向讀一些），使用新page換掉舊page，此時會有一次cache失效，但是並沒有加鎖，原因見下一條。
圖2 頁面以及對其的修改delta
第二，使用page mapping table隔離頁面真正的物理位置，見圖3。每個page都有一個唯一的ID，這個ID可以認為是邏輯ID，是在新頁面生成的時候系統分配的（從文章看，這個ID是自然數且會回收利用），邏輯ID和物理位置構成了mapping table裡面的一項。從圖3看到，頁面不管是儲存在記憶體中（Cache）還是磁碟上，都可以用64bit表示，這樣如果頁面consolidation後要換成新的頁面，只要根據被替換頁面的邏輯ID找到其物理地址，然後CAS就可以了，這就解決了上面問題一中的替換頁面時候鎖的問題。
圖3 page mapping 示意
至此，LLAMA的背景和核心思路已經清楚，即LLAMA是一個頁面管理器，透過page mapping table隔離了頁面的物理位置和邏輯位置，以增加其自身的靈活性，且為無鎖打下基礎；其不僅管理固定大小的頁面，還管理變長的delta page；不僅管理儲存，還管理快取；不僅保證單個頁面的操作原子性還保證多頁面聯合操作（分裂、合併）的原子性。
下面看一些關鍵細節。
關鍵細節一：LLAMA提供的操作。主要有兩類，一類是針對頁面資料的操作，主要有三個
Update-D（PID， in-ptr， out-ptr， data），將某個頁面的修改（Delta）連線到頁面上，data是輔助結構，一般跟呼叫方有關
Update-R（PID， in-ptr， out-ptr， data），將某個頁面換掉（Replace）
Read（PID， out-ptr），頁面讀取，如果頁面不在記憶體，會從磁碟讀出來，跟檔案系統的page cache行為類似，呼叫方很好用
第二類是跟頁面狀態有關，
Flush（PID， in-ptr， out-ptr， annotation）：將頁面複製到LSS（Log Structure Store，寫盤模組）的buf並將返回地址填充到out-ptr，annotation不知道明確目的，可能跟上層呼叫方的某些約束有關。文中強調這個行為只是將page複製到buf，並不落盤。論文中還提到有專門策略控制buf裡面哪些資料可以落盤，這是系統無鎖得以實現的一部分
Mk-Stable（LSS address）：保證LSS address之前的頁面全部落盤（secondary storage）
Hi-Stable（out-LSS address）：返回當前落盤的最高LSS地址
Allocate（out-PID）：分配一個頁面ID，所有分配過的頁面都得記錄，否則分配重了就不對了，這裡是依靠事務機制完成的，論文稱為system transaction
Free（PID）：釋放PID，也是要記錄的。文中說有一個和epoch相關的free list專門記錄，epoch是LLAMA回收模組（Garbage Collection，GC）的概念，也是比較通用的GC手段
關鍵細節二：系統事務（System transaction）
LLAMA在完成頁面狀態管理的時候，也需要保證一致性。比如頁面分裂，父頁面和子頁面狀態都要改，此時有一個事務會更加容易理解。具體做法文中說的不多，提到了為了避免undo帶來的複雜性，Update-R不允許使用在事務中，看起來可以接受，畢竟有了Update-D，Update-R可以基於Update-D實現。同時，這個事務也做的非常簡單（重啟後事務ID不需要唯一），直到Commit所有操作才會應用，跟一些K-V系統裡面的簡單事務有點類似。
關鍵細節三：頁面刷盤
如果發現delta太多，可以在記憶體中就把這些delta變成contiguous delta，然後寫入LSS，這樣的話，LSS裡面會同時存在多個小的delta和一個大得contiguous delta，多佔用了一些空間，交給LSS Cleaner解決。
文中特意提到了一個無鎖帶來的難題，即當頁面flush到儲存的時候，同時也需要修改mapping table的page state，那麼是先flush再嘗試修改mapping table還是反過來？簡單的組合都是有缺陷的，作者巧妙的利用預留位置和可能多用一些儲存解決掉了，該方案如果衝突嚴重可能也會浪費很多空間，感興趣可以看原文。從對這個問題的討論看，LLAMA對無鎖的實現是貫穿到方方面面的。
關鍵細節四：貫穿全域性的回收
因為無鎖是系統的主旋律，那麼所有資源類的釋放就只能依靠後臺回收，而後臺回收的核心思路是epoch，見圖4。如果有一個參與方判斷某個物件要被回收了，就將其link到一個不斷遞增epoch連結串列上，當所有參與者都越過這個epoch後，那麼這個epoch以及之前epoch上掛接的物件都可以回收了。這個epoch和事務約束（MVCC）可以互相做對映，從而使得整個系統的回收都可以很方便的執行。圖4只是記憶體物件的GC，store的GC思路是類似的，策略會多一些，這些內容被包括在文中提到的LSS Cleaner部分。
圖4 。 系統GC
關鍵細節五：page在LSS的組織
圖5是mapping table和LSS page佈局的示意圖。可以看到類似一個磁碟上的連結串列，每個delta必然指向一個base或者其他delta，delta的大小是變化的，也即是一個磁碟物理塊裡面可能包含多個delta，這也是文中說該系統利用率高的一個原因，畢竟之前的Log Structuring Filesystem還是固定大小的page，邏輯page和物理page是一對一的，有空間浪費的嫌疑。另外，文字還給了一個數字，即傳統基於塊的B-tree空間利用率只有69%，這樣使得Log Structure的優勢又多了一個。
圖5 mapping table和LSS page 佈局
關鍵細節六：mapping table的failover
mapping table的變化是隨著LSS寫下去的，這裡LSS有點像是mapping table這個Database的Write-Ahead-Log一樣的角色，保證了其持久化，但是不可能每次系統起來都replay所有的log，所以還是要定期做checkpoint。文中提到說可以使用增量方式一點點對mapping table做checkpoint，提到了增量的起始和結束點如何選擇，這就解決了增量checkpoint的一個難題，即如何選額一個穩定的增量邊界。當然，增量checkpoint還會有其他的問題，比如合併問題。
從全文來看，LLAMA的設計充分踐行了無鎖和減少隨機寫的思想，順便也把資料庫系統設計靈活性提高了一個檔次，是一個很新穎的設計。其中也有很多細節值得學習探討，歡迎讀過此文的一起討論。
無特殊說明，所有圖片來自論文［1］。
［1］。 LLAMA： A Cache/Storage Subsystem for Modern Hardware
