etcd在大規模數據場景中的性能優化

• 2019 年 12 月 4 日
• 筆記

作者：陳星宇，阿里雲軟件工程師

摘要

etcd是一個開源分佈式kv存儲系統，最近被CNCF列為孵化項目。etcd在許多分佈式系統中得到了廣泛的應用。例如，Kubernetes使用etcd作為分類賬，在集群中存儲各種元信息。本文首先介紹優化的背景。然後介紹etcd內部存儲的工作機制和具體的優化實現。最後給出了評估結果。

背景

由於阿里巴巴龐大的Kubernetes集群規模，對etcd的容量要求非常高，超出了支持的極限。因此，我們實現了一個基於etcd代理的解決方案，將溢出的數據轉儲到另一個像Redis的KV存儲系統。雖然這種方案解決了存儲容量問題，但是缺點是顯而易見的。由於etcd代理需要移動數據，因此操作延遲比原生etcd大得多。此外，由於使用另KV儲存系統，操作和維修費用較高。因此，我們希望了解決定etcd存儲支持限制的基本因素，並嘗試優化它以獲得更高的容量限制。

要了解etcd的容量問題，我們首先對etcd進行了持續注入數據的應力測試。當etcd中存儲的數據量超過40GB時，經過compact操作，我們發現put操作的延遲顯著增加，許多put操作超時。仔細查看監視工具，我們發現延遲的增加是由於boltdb的內部spill操作（參見下面的定義）變慢造成的，這大約需要8秒，遠遠高於通常的1ms。監視結果如圖1所示。在多次運行中，實驗結果是一致的，這意味一旦etcd容量超過40GB，所有的讀和寫操作都比正常情況下慢得多，這對於大規模數據應用程序來說是不可接受的。

圖1. 當數據超過40GB時，etcd的性能下降。

etcd內部

etcd存儲層由內存中基於btree的索引層和基於boltdb的磁盤存儲層兩大部分組成。文檔主要關注底層boltDB層，因為它是優化目標。以下是對boltDB的介紹，引用自https://github.com/boltdb/bolt/blob/master/README.md

Bolt最初是LMDB的一個移植，所以它在架構上是類似的。

它們都使用B+樹，具有ACID語義和完全可序列化的事務，並且使用一個寫入器和多個讀取器支持無鎖MVCC。

Bolt是一個相對較小的代碼庫（<3KLOC），適用於嵌入式、可序列化的事務鍵/值數據庫，因此它可以成為對數據庫如何工作感興趣的人的一個很好的起點。

如上所述，bolteDB設計簡潔，可以嵌入到其他軟件中作為數據庫使用。例如，etcd內置了boltDB作為內部存儲k/v數據的引擎。boltDB使用B+樹存儲數據，葉子節點存儲真實的鍵/值。它將所有數據存儲在一個文件中，使用mmap syscall將其映射到內存。它使用write syscall讀取和更新文件。基本的數據單元稱為頁（page），默認為4KB。當頁刪除發生時，boltdb不會直接回收已刪除頁的存儲。相反，它臨時保存已刪除的頁，以形成一個空閑的頁池供後續使用。這個自由頁池在boltDB中稱為freelist。圖2給出了一個boltDB頁元數據的示例。

圖2. boltDB頁元數據

紅色頁43、45、46、50正在使用，而42、44、47、48、49、51頁以後可以供使用。

問題

當用戶數據頻繁寫入etcd時，內部的B+樹結構將被調整（例如重新平衡、拆分節點）。spill操作是boltDB中將用戶數據持久化到磁盤的關鍵步驟，這發生在調整樹結構之後。它向freelist釋放未使用的頁，或者向freelist請求頁來保存數據。

通過對spill操作的深入調查，我們發現在spill操作中存在如下代碼的性能瓶頸：

// arrayAllocate returns the starting page id of a contiguous list of pages of a given size.  // If a contiguous block cannot be found then 0 is returned.  func (f *freelist) arrayAllocate(txid txid, n int) pgid {           ...      var initial, previd pgid      for i, id := range f.ids {          if id <= 1 {              panic(fmt.Sprintf("invalid page allocation: %d", id))          }          // Reset initial page if this is not contiguous.          if previd == 0 || id-previd != 1 {              initial = id          }          // If we found a contiguous block then remove it and return it.          if (id-initial)+1 == pgid(n) {              if (i + 1) == n {                  f.ids = f.ids[i+1:]              } else {                  copy(f.ids[i-n+1:], f.ids[i+1:])                  f.ids = f.ids[:len(f.ids)-n]              }              ...              return initial          }          previd = id      }      return 0  }

上面的代碼表明，當boltDB在freelist中重新分配頁時，它嘗試分配連續的n個空閑頁供使用，如果找到了連續的空間，則返回起始頁面id。代碼中的f.ids是一個數組，記錄了內部空閑頁的id。例如，對於圖2所示的情況，f.ids=[42,44,47,48,49,51]

該方法對連續n頁執行線性掃描。例如，當freelist中有很多內部片段時，freelist中存在的連續頁大多是小尺寸的，例如1或2，如果請求連續頁大小較大，則算法將花費很長時間執行。此外，算法需要移動數組的元素。當有很多數組元素時，即大量的數據存儲在內部，這個操作非常慢。

優化

通過以上分析，我們了解到線性掃描空頁並不是一個可伸縮的算法。受到前雅虎首席科學家Udi Manber的啟發，他曾經說過雅虎最重要的三種算法是哈希，哈希和哈希！（hashing, hashing and hashing!），我們嘗試使用多個散列來解決可伸縮性問題。

在我們的優化中，使用集（set）來組織大小相同的連續頁，然後使用哈希算法將不同的頁大小映射到不同的集。請參見下面新freelist結構中的freemaps數據結構。當用戶需要一個大小為n的連續頁時，我們只查詢freemaps來找到連續空間的第一個頁。

type freelist struct {    ...      freemaps map[uint64]pidSet // key is the size of continuous pages(span), value is a set which contains the starting pgids of same size      forwardMap map[pgid]uint64 // key is start pgid, value is its span size      backwardMap map[pgid]uint64 // key is end pgid, value is its span size      ...  }

此外，在釋放連續頁時，我們需要將儘可能多的內容合併到更大的連續頁中。原始算法使用一種耗時的方法（O（nlgn））。我們也使用哈希算法對其進行優化。新方法使用了兩個新的數據結構，forwardMap和backwardMap，在代碼上面的注釋中提供了解釋。

當一個頁被釋放時，它試圖通過查詢backwardMap與前一個頁合併，並通過查詢forwardMap與下一個頁合併。具體算法如下面的mergeWithExistingSpan函數所示。

// mergeWithExistingSpan merges pid to the existing free spans, try to merge it backward and forward  func (f *freelist) mergeWithExistingSpan(pid pgid) {      prev := pid - 1      next := pid + 1      preSize, mergeWithPrev := f.backwardMap[prev]      nextSize, mergeWithNext := f.forwardMap[next]      newStart := pid      newSize := uint64(1)      if mergeWithPrev {          //merge with previous span          start := prev + 1 - pgid(preSize)          f.delSpan(start, preSize)          newStart -= pgid(preSize)          newSize += preSize      }      if mergeWithNext {          // merge with next span          f.delSpan(next, nextSize)        newSize += nextSize      }      f.addSpan(newStart, newSize)  }

新的算法如圖3所示。當第45、46頁被釋放時，算法嘗試與第44頁合併，然後與第47、48、49頁合併，以形成一個新的自由頁跨。

圖3. 合併整個頁跨度的說明

上面的算法類似於內存管理中使用的隔離自由列表算法。它將頁分配時間複雜度從O（n）降低到O（1），並將發佈時間從O（nlgn）降低到O（1）。

評估

以下測試在一個單節點etcd集群中進行，以排除網絡等其他因素。該測試模擬了100個客戶機同時向etcd輸入100萬kv對。鍵/值內容是隨機的，我們將吞吐量限制為5000 op/s。測試工具是etcd官方基準測試工具。給出了延遲結果。

使用新的隔離hashmap的性能

舊算法的性能

有一些超時沒有完成測試。

比較

時間越短，性能越好。性能提升因子是歸一化到最新哈希算法的運行時。

新算法的性能在更大的場景下會更好。

結論

新的優化方法降低了etcd中的時間複雜度，內部自由列表分配算法從O（n）到O（1），頁釋放算法從O（nlgn）到O（1），解決了etcd在大數據庫規模下的性能問題。實際上，etcd的性能不再受存儲大小的限制。etcd存儲100GB數據時的讀寫操作可以與存儲2GB數據一樣快。此新算法是完全向後兼容的，你可以在不需要數據遷移或數據格式更改的情況下獲得此新算法的好處！目前，該優化在阿里巴巴已經進行了2個多月的反覆測試，沒有出現意外。它已被貢獻給開源社區，這裡有鏈接。你可以在新版本的boltdb和etcd享受它。

關於作者

陳星宇（github id: WIZARD-CXY），阿里雲軟件工程師。他是阿里巴巴etcd集群管理的所有者，也是etcd/kubernetes的活躍貢獻者。他的主要興趣是etcd集群的性能和穩定性。