CONSENSUS:BRIDGING THEORY AND PRACTICE(第5章)

日志壓縮

Raft日志會随着包含了越來越多的用戶端請求而持續增長。當它變得很大的時候，将會占據更多的空間并且需要花費更多的時間去回放。如果沒有一些日志壓縮的手段，最終将會引起可用性問題：servers将或者執行到空間不足，或者要花費很久啟動。是以，在任何實際系統中對日志以某些形式上的壓縮都是必要的。

最一般的壓縮想法是随着時間的流逝會有越來越多的日志成為廢棄無用的并且可以被丢棄。例如，一個将x指派為2的操作會在x指派為3之後就成為廢棄的了。一旦log entries被送出并且應用到狀态機了，到達這個狀态過程中的中間狀态和操作都不再需要了，它們就可以被壓縮掉。

不像核心的Raft算法和成員變更，不同的系統将會有不同的日志壓縮需求。沒有一個普适的日志壓縮方案，這有幾個原因。第一，不同的系統可能在易用性和性能上有着不同角度的權衡。第二，狀态機必須與日志壓縮密切相關，并且狀态機在大小和存儲媒體(disk/memory)方面也存在很大差異。

本章的目标是讨論各種各樣的日志壓縮方法。在每一個方法中，日志壓縮的大部分責任落在狀态機上，狀态及負責将狀态寫入磁盤并壓縮狀态。狀态及可以通過不同的方法實作，通篇都會介紹，下圖5.1是概括：

• memory-based狀态機的快照在概念上是最簡單的方法。快照時，整個目前系統的狀态被寫入到持久化存儲的快照中，之後log中到這個點之前的都會被丢棄掉。快照在Chubby和Zookeeper中有所使用，并且我們在LogCabin中也實作了快照。快照是本章5.1節中講述最深的。

• 對于disk-based狀态機，系統最近狀态的拷貝會維護在disk上，作為正常操作的一部分。是以，一旦狀态機映射到了disk上Raft log就可以丢棄了，并且快照隻會被用來為保證一緻性而發送給其他servers(

  譯者注：當然server restart的時候也會load

  )(5.2節)。
• 增量的方法做log壓縮，比如日志清理和LSM-tree，在5.3節中有描述。這些方法可以高效的寫入disk，并且能随着時間平坦的利用資源。
• 最後，5.4節讨論了一個通過把快照直接存儲在log中的有着最小化的機制需求的日志壓縮方法。然而實作很簡單，這種方法隻适合非常小的狀态機。

LogCabin目前隻是先了memory-based的快照方法(内嵌的一個memory-based的狀态機)。

各種壓縮方法其實共享一些核心概念。第一，不是将壓縮決策集中在leader身上，而是每一個server獨立地根據committed狀态把之前的log進行壓縮。這避免了leader把已經在follower中存在在log中的資料傳輸給follower。這也提高了子產品性：大部分額日志壓縮的複雜性留在了狀态機中，不會太多地影響Raft本身。這也保持了整個系統的複雜性最小化：日志壓縮特性的引入對整體複雜度的影響是加法性的增加，而不是乘法性的增加。可供選擇的方法即leader集中化的壓縮方式會在5.4節中有所讨論(并且對于非常小的狀态機，leader-based的方法可能更好)。

第二，狀态機和Raft的基本互動涉及到将之前的log的維護責任由Raft轉給狀态機。在entries被應用到狀态機後，遲早狀态機會把那些entries映射到disk上以便可以恢複系統目前狀态。一旦完成，狀态機将通知Raft可以丢棄相應的log。在Raft放棄對這些log的責任之前，它必須把它擁有的一些用于描述這些log的狀态資訊進行儲存。特别地，Raft要儲存最後被丢棄的entry的index和term；這個狀态機狀态點後面是剩餘的Raft維護的log entries，同時也保證了AppendEntries一緻性檢查可以繼續工作(它需要log中的第一個entry之前的index和term

譯者注：Raft剩下的log的第一條之前的部分就是狀态機儲存的狀态

)。Raft也儲存了丢棄log中的最近的配置以支援叢集成員變更

譯者注：成員變更失敗需要回退配置，最近的配置必須儲存

。

第三，一旦Raft丢棄了log前面的部分，狀态機就負有了兩個新的責任。如果server重新開機了，狀态機在可以應用任何Raft log中的entry之前需要把相應丢棄的log entries對應部分的狀态加載了。此外，狀态機可能需要生成一個狀态的鏡像以便可以發送給較慢的follower(遠落後于leader log的server)。等到叢集中的每個成員都日志一緻後再壓縮是不可行的，由于minority成員不會影響叢集可用性，而且新的server也随時可能被加入到叢集中。是以，慢的followers或者新的servers将偶爾地需要通過網絡收到它們的初始狀态。Raft如果發現一個server的next entry在被丢棄了的log entries中，則狀态機會提供一個狀态的一緻鏡像并發送給follower。

memory-based狀态機的快照

第一個快照應用是當狀态機的狀态保持在記憶體中的時候。這在狀态機的資料集處于GB和10GB這個數量級的時候是合理的選擇。由于不用去disk擷取資料，操作會快速完成；這樣做也使得變成更加簡單了，因為有大量的資料結構可以使用并且每個操作都可以執行到完成(沒有IO阻塞)。

圖5.2顯示了Raft中當狀态機狀态儲存在記憶體中時的基本想法。每一個server獨立的取得快照，隻覆寫log中已送出的entries。快照工作的大部分涉及到序列化狀态機目前狀态，并且這對于獨有的不同狀态機都是特殊的。例如，LogCabin的狀态機使用一個tree作為其主要資料結構；使用先序(前序)的深度優先周遊方式序列化tree(是以當應用快照時，父節點會在它的子節點之前建立)。狀态機也需要把它為了用戶端提供線性一緻性特性保持的資訊進行序列化(見第6章)。

一旦狀态機寫完了快照，log就可以被截斷了。Raft首先存儲重新開機需要的狀态：快照中包含的最後entry的index和term以及直到該索引處的最新配置。然後就通過這個index丢棄log前面直到該index的entries。任何之前的快照也可以被丢棄了，它們已經沒有用了。

由上面的介紹，leader可能偶爾需要把它的狀态發送給慢followers并且發送給加入叢集的新servers。在快照邏輯中，這個狀态就是最新的快照，leader會通過一個新的InstallSnapshot RPC來傳輸，如圖5.3。當一個follower通過這個RPC收到一個快照時，它必須決定對已存在的log entries做什麼處理。通常快照将包含follower log中沒有的新資訊。這種情況下，follower會丢棄它所有的log；它将完全被快照取代并且可能存在與快照中沖突的未送出的entries(

譯者注：以leader發來的快照為準

)。否則如果follower收到的快照内容已經包含在的它的log之中(由于重傳或者錯誤)，則快照中表達的部分對應的log entries就會被删除，在快照後面部分的日志仍然有效并且需要被保持。

剩下段落的部分讨論memory-based狀态機快照的次要問題：

• 5.1.1節讨論如何在生成快照和正常操作之間并行，進而最小化對用戶端的影響
• 5.1.2節讨論什麼時候擷取快照，平衡空間使用和快照生成的負載
• 5.13.節讨論快照實作過程中出現的問題

快照的并發性

建立一個快照需要花費很長時間，包括序列化狀态和disk的寫入。例如，在今天的伺服器上拷貝10GB的記憶體花費大約1秒鐘，并且序列化它通常将花費更長的時間：即使SSD 1秒鐘也僅能寫入大約100MB。是以，序列化和寫快照都必須與正常操作并發以避免可用性問題。

幸運的是copy-on-write技術允許新更新的應用不影響快照的寫入。有兩個方法來實作：

• 狀态機可以用不可變的(功能性的)資料結構來支援建構實作。因為狀态機指令不會in-place的方式修改狀态(

  比如說通過追加的形式實作修改，擷取的時候擷取最新的追加的内容，後面再定期或定量整理垃圾。這樣的話之前的狀态就維持住了，就可以容易的生成快照了

  )，快照任務可以引用之前狀态的并把狀态一緻地寫入到快照。
• 可選擇的，作業系統的copy-on-write也可以被使用(如果程式設計環境允許)。比如在Linux上，in-memory狀态機可以使用fork來得到server的整個位址空間的拷貝。然後子程序就可以把狀态機的狀态寫出并退出，整個過程中父程序都可以持續地提供服務。LogCabin中目前使用的就是這種方法。

Servers并發地制作快照需要額外的記憶體，這應該被我們計劃和管理。狀态機通過流式的接口來做快照檔案是必要的，以便快照建立時不會整體在記憶體中逗留。然而，copy-on-write機制下狀态機的狀态需要的額外記憶體的比例是會改變的。此外，依賴于作業系統的copy-on-write技術也會由于僞共享而使用更多的記憶體(例如兩個不相關的資料落在了一個記憶體page上，當僅第一個資料失效時，第二個資料也就會在父子程序間産生多餘的副本

譯者注：第二條資料沒有變更本可以一個記憶體副本，但是由于和第一條落在了一個page上，os是page為粒度管理記憶體的，則第二個也會copy-on-write進而産生一個多餘副本

)。不幸的事件發生的話可能導緻記憶體在快照期間被耗盡，這時候server應該停止接收log entries直到完成快照；這将臨時地犧牲server的可用性(叢集可能還是保持可用的)，但是這樣至少server将會恢複。取消快照并在稍後重試可能并不好，因為下一次嘗試可能面臨相同問題(LogCabin使用流式的刷盤接口，但是目前也沒有優雅地處理記憶體耗盡的問題)。

什麼時候做快照

Servers需要決定什麼時候做快照。如果一個server太過頻繁地做快照，将來浪費disk帶寬和其他資源；如果太不頻繁地做快照，則有存儲空間耗盡的風險，并且重新開機服務需要更長的重放日志時間。

一個簡單的政策是當log達到了一定的大小後做快照。如果這個大小門檻值設定的顯著地大于快照預期的大小，那麼快照帶來的disk帶寬負載将會是小的。然而，這會導緻對于小的狀态機時有着不必要的大的logs。

一個好的方法是引入快照大小和日志大小的對比。如果快照比日志小幾倍，可能更值得做快照。然而，在制作快照之前計算快照的大小是困難并且繁重的，将會引入顯著地狀态機跟蹤負擔，或者需要幾乎和制作快照差不多的動态大小計算的工作量。壓縮快照檔案也會帶來空間和帶寬的節省，但是預測壓縮後的輸出大小是困難的。

幸運的是，使用前一個快照的大小而不是下一個快照的大小會是比較合理的行為。一旦日志的大小超出了前一個快照的可配置的擴充因子倍數，servers就做快照。這個擴充因子權衡空間和帶寬使用率。例如擴充因子為4的話會有20%的帶寬用于快照(每1byte的快照寫入有對應的4bytes的log寫入)和大約6倍的硬碟空間使用(舊的快照➕log➕新的快照)。

快照會導緻cpu和disk io的突發使用可能會影響用戶端性能。這可以通過硬體方案來減輕狀況，比如新增一個disk driver以提供額外的帶寬。

也可能通過排程快照的制作以使得快照對用戶端請求沒有影響。servers需要協調保證在某一時刻叢集隻有小部分成員集同時在做快照。由于Raft是majority成員構成的commit，是以這樣就不會影響請求的送出了。當leader想做快照的時候，首先要先下台，讓其他server上司叢集。如果這個方法充分地可行，就可能消除快照的并發，server在快照期間其實是不可用的(這可能會造成叢集的容錯能力降低的問題)。這是一個令人興奮的提升叢集性能并降低實作機制的機會。

實作的關注點

這一節回顧快照的主要元件的實作并讨論實作的難點：

• 儲存和加載快照： 儲存快照牽涉把狀态機狀态序列化後的資料存儲到disk，而加載是一個相反的過程。我們發現這是相當直截了當的，盡管序列化不同本地情況的資料有幾分乏味。狀态機提供一個流式的接口将資料刷到disk是有必要以避免狀态機暫存全部序列化的狀态資料。可能對流進行壓縮并附帶一個checksum比較好。LogCabin先把快照寫入一個臨時檔案，當寫完并且刷到disk之後，再把檔案改名。這是為了避免server啟動的時候加載到部分的快照。
• 傳輸快照： 傳輸快照牽涉到主和從實作InstallSnapshot RPC。這是相當直截了當的，可能可以共享在磁盤上儲存和加載快照的一些代碼。傳輸的性能通常不是非常重要（一個需要這種動作的跟随者不會參與到entries的commitment決策中，是以不需要立即完成；另一方面，如果叢集遭遇額外的失敗，就可能需要盡快使得落後的follower趕上來以恢複叢集的可用性）。
• 排除不安全的日志通路和丢棄日志條目： 我們最初設計LogCabin的時候沒有考慮日志壓縮，是以代碼上假定了如果entry i 在日志中，那麼entry 1 到 i - 1 也一定在日志中。有了日志壓縮，這就不再成立了；例如，當AppendEntries RPC要确定前一個entry的term時，那個entry可能已經被丢棄了。貫穿代碼移除這些假定需要仔細地推敲和測試。可能對一些強類型的系統做這些是簡單的，編譯器會強制檢查日志通路并處理越界的問題。一旦我們使得所有的日志通路都是安全的，丢棄前面的日志就是直截了當的了。直到這點，我們都隻能單獨地測試儲存、加載和傳輸快照，但是當日志條目可以被安全地丢棄的時候，就可以做令人興奮的系統級的測試了。
• 通過copy-on-write并發地做快照： 并發做快照可能需要重做狀态機或者利用作業系統的fork操作。LogCabin目前使用的是fork，不需要與線程和C++的析構打交道，通過這些做一個正确地工作是困難的。然而，以較少的代碼消除了對狀态機資料結構的修改，我們認為這是正确的方法。
• 決定什麼時候做快照： 我們建議在開發的過程中每應用一條日志就做一個快照，這樣便于快速定位問題。一旦實作完成，就需要增加一個更有效的機制選擇什麼時候做快照（例如使用Raft log和上一個快照的統計資訊）。

我們發現分段開發和測試快照是有挑戰的。在丢棄log entries的時候大多數元件都需要in-place，但是僅僅在系統內建測試的時候才能擁有這些新的代碼。是以實作者應該小心考慮實作和測試元件的順序。

Disk-based狀态機的快照

這一節讨論一個對于大的狀态機(在十或百GB這個量級)實作快照的方法，使用disk作為主存。這些狀态機的運作是不同的，他們會在disk保持一份狀态的副本以應對crash。應用沒一個Raft log entry都會改變disk上的狀态，進而等于生成了一個新的有效的快照。是以，一旦一個entry被應用之後就可以從Raft log中丢棄了（狀态機也可以在記憶體中做緩沖以提升disk使用的性能；一旦緩沖寫入了disk，相應的entries就可以從Raft log中丢棄了）。

Disk-based的狀态機的主要問題是基于disk的狀态變化會導緻較差的性能體驗。如果沒有寫緩沖，沒一個指令的應用需要一個或者更多的随機disk通路，這會限制系統整體的寫吞吐（即便又寫緩沖也沒有太大幫助）。5.3節會讨論一種增量的日志壓縮方法，它會利用大的、順序的寫來提升寫disk的性能。

Disk-based狀态機必須要有能力提供一緻的disk快照以滿足傳送給較慢的follower的需求。盡管它們在disk有快照，但是也在連續不斷地修改它。是以，它們仍然需要copy-on-write技術以在一定期間内保持一個一緻地快照以供傳輸。幸運的是，disk格式基本都是以邏輯塊為單元，是以在狀态機中實作copy-on-write技術是直截了當的(自己實作很直接簡單，比如模仿linux fork後的cow機制)。Disk-based狀态機也可以依賴作業系統的支援。比如，linux上的LVM可以被用來建立快照。

拷貝一個disk的鏡像需要花費較長時間，并且由于disk的修改是累積的，是以為了保持快照額外的disk使用是必須的。盡管我們沒有實作disk-based的快照，但是我們推斷disk-based的快照可以通過下面的算法避免大多數的disk内容傳輸負載：

1. 對于沒一個disk塊，跟蹤其last modified。
2. 在持續的普通操作期間，一個塊一個塊地傳輸整個disk的内容到follower。在這個過程中，在leader上沒有額外的disk空間使用。由于塊是會并發地被修改，這可能會導緻從的disk鏡像不一緻。當每一塊從leader傳輸的時候，注意它的last modification time。
3. 擷取一個disk内容的copy-on-write快照。一旦取得了，leader就有了一個disk内容的一緻性拷貝，但是由于用戶端繼續的操作disk會被修改，進而占用額外的disk空間。
4. 僅重傳第2步和第3步的快照中相比變化了的塊。

增量清理的方法

增量的方法做壓縮，如同log cleaning和LSM tree，是可能的。盡管他們快照的實作會更複雜，增量的方法仍然有幾個令人渴望的特點：

• 每次隻操作資料的一部分，是以壓縮的負載随着時間來看是均勻的。
• 對disk的寫入更有效率，包括正常操作和壓縮期間，都會使用大的、順序寫。增量的方法也可以有選擇地壓縮disk上最具可回收價值的空間，是以相比memory-based的狀态機會寫入更少的資料到disk上。
• 可以非常簡單地傳輸一緻性狀态快照 ，因為并不會in-place地修改disk的區域。

5.3.1節和5.3.2節首先描述了log cleaning和LSM tree通常情況下的基礎知識。之後[5.3.3]節讨論如果應用到Raft中。

log清理基礎

Log cleaning是在log-structured檔案系統

譯者注：可以參考維基百科

詞條的内容中被引入的，并且最近被提議應用到記憶體檔案系統比如RAMCloud中。原則上講log cleaning可以被使用在任何資料結構上，盡管一些相比其他有效地實作起來會更困難。

Log cleaning維護日志作為記錄系統狀态的地方。為了優化順序寫而設計，并且也使得随機讀更有效。是以，需要索引結構提升讀取時的定位速度。

在log cleaning中，日志被分割到連續的區域(regions)之中，稱之為段(segments)。每個log cleaner壓縮日志的途徑都使用一個3步的算法：

1. 首先選擇要清理的段，這些段累積了大量的廢棄entries。
2. 然後把有效的entries從那些段中拷貝到日志的頭部。
3. 最後釋放那些段的存儲空間。

為了最小化對正常操作的影響，這個過程應該并發地做。

由于将有效的entries轉發到日志的頭部，是以這些entries将失去重放的順序。Entries可以包含附加的資訊(比如version number)以在log應用的時候重建正确的順序。

選擇哪些段做清理的政策對性能有非常大的影響；先前的工作提出了一個成本-效益政策，該政策不僅考慮到有效entries所占用的空間量，而且還考慮了這些條目可能存活的時間。

log-structured merge trees基礎

LSM tree最先是被O’Neil提出并且之後通過BigTable流行于分布式系統(Cassandra、HyperDex、LevelDB、RocksDB)。

LSM tree像tree的結構存儲有序的kv對。在高層級，對disk使用類似于log cleaning的方法：大的順序寫并且不in-place地修改disk上的資料。然而，LSM tree并沒有在日志中維護所有狀态，而是重新組織狀态以便更好地進行随機通路。

典型的LSM tree将最近的寫入在disk保持一份小的log。當log達到一定的大小後，對key進行排序并且寫入一個叫做run的檔案中。Runs不會in-place修改，但是會周期性地對runs進行merge，産生新的runs并丢棄舊的，merge的過程像merge sort，參考圖5.1。

在正常操作期間，狀态機可以直接在這些資料上操作。對于讀一個key來說，首先檢查是否在最近的log中有修改，之後檢查每一個run。為了避免對每一個run做key的檢查，一些系統對每一個run建立了bloom filter。

Raft中的日志清理和LSM-tree

我們還沒有嘗試在LogCabin中實作log cleaning或者LSM tree，但是我們推測兩者都會做的很好。把LSM tree應用到Raft是相當直截了當的。因為Raft log已經在disk上持久存儲了最近的entries，LSM tree可以在記憶體中以更友善的tree的格式儲存最近的entries。這将提高查找的性能，并且當Raft log達到指定大小的時候，這個tree也可以直接刷成disk的一個新run。傳輸狀态的時候leader需要把所有的run發送給follower(不包含in-memory tree)；幸運地是runs都是不可變的，是以傳輸期間不設計runs被改變。

把log cleaning應用到Raft就不是這麼明顯了。

譯者注：懶得翻譯了，反正應用有限，自己看看論文原文吧。簡單說下就是原始的log cleaning算法meta和data混合在日志裡，這樣的話一旦開始前文提到的日志清理了，就會導緻整理後的entries順序亂了，也會出現類似于檔案洞的section空洞。解決辦法就是對于log cleaning，改造為meta和data分離，meta做Raft log，data在狀态機中。

可供選擇的：leader-based的方法

略。

日志中存儲快照

略。

非常小的狀态機使用Leader-based的方法

略。

讨論

略。