1概述
etcd 是一個開源的分布式的 kv 存儲系統, 最近剛被 CNCF 列為沙箱孵化項目。etcd 的應用場景很廣，很多地方都用到了它，例如 Kubernetes 就用它作為叢集内部存儲元資訊的賬本。本篇文章首先介紹我們優化的背景，為什麼我們要進行優化, 之後介紹 etcd 内部存儲系統的工作方式，之後介紹本次具體的實作方式及最後的優化效果。
2優化背景
由于阿裡巴巴内部叢集規模大，是以對 etcd 的資料存儲容量有特殊需求，之前的 etcd 支援的存儲大小無法滿足要求， 是以我們開發了基于 etcd proxy 的解決方案，将資料轉儲到了 tair 中(可類比 redis))。這種方案雖然解決了資料存儲容量的問題，但是弊端也是比較明顯的，由于 proxy 需要将資料進行搬移，是以操作的延時比原生存儲大了很多。除此之外，由于多了 tair 這個元件，運維和管理成本較高。是以我們就想到底是什麼原因限制了 etcd 的存儲容量，我們是否可以通過技術手段優化解決呢？
提出了如上問題後我們首先進行了壓力測試不停地像 etcd 中注入資料，當 etcd 存儲資料量超過 40GB 後，經過一次 compact(compact 是 etcd 将不需要的曆史版本資料删除的操作)後發現 put 操作的延時激增，很多操作還出現了逾時。監控發現 boltdb 内部 spill 操作(具體定義見下文)耗時顯著增加(從一般的 1ms 左右激增到了 8s)。之後經過反複多次壓測都是如此，每次發生 compact 後，就像世界發生了停止，所有 etcd 讀寫操作延時比正常值高了幾百倍，根本無法使用。
3etcd 内部存儲工作原理
etcd 存儲層可以看成由兩部分組成，一層在記憶體中的基于 btree 的索引層，一層基于 boltdb 的磁盤存儲層。這裡我們重點介紹底層 boltdb 層，因為和本次優化相關，其他可參考上文。
etcd 中使用 boltdb 作為最底層持久化 kv 資料庫，boltdb 的介紹如下:
Bolt was originally a port of LMDB so it is architecturally similar.
Both use a B+tree, have ACID semantics with fully serializable transactions, and support lock-free MVCC using a single writer and multiple readers.
Bolt is a relatively small code base (<3KLOC) for an embedded, serializable, transactional key/value database so it can be a good starting point for people interested in how databases work。
如上介紹，它短小精悍，可以内嵌到其他軟體内部，作為資料庫使用，例如 etcd 就内嵌了 boltdb 作為内部存儲 k/v 資料的引擎。
boltdb 的内部使用 B+ tree 作為存儲資料的資料結構，葉子節點存放具體的真實存儲鍵值。它将所有資料存放在單個檔案中，使用 mmap 将其映射到記憶體，進行讀取，對資料的修改利用 write 寫入檔案。資料存放的基本機關是一個 page, 大小預設為 4K. 當發生資料删除時，boltdb 不直接将删掉的磁盤空間還給系統，而是内部将他先暫時儲存，構成一個已經釋放的 page 池，供後續使用，這個所謂的池在 boltdb 内叫 freelist。例子如下：
紅色的 page 43, 45, 46, 50 頁面正在被使用，而 page 42, 44, 47, 48, 49, 51 是空閑的，可供後續使用。
如下 etcd 監控圖當 etcd 資料量在 50GB 左右時，spill 操作延時激增到了 8s。
4問題分析
由于發生了使用者資料的寫入, 是以内部 B+ tree 結構會頻繁發生調整(如再平衡，分裂合并樹的節點)。spill 操作是 boltdb 内部将使用者寫入資料 commit 到磁盤的關鍵一步, 它發生在樹結構調整後。它釋放不用的 page 到 freelist, 從 freelist 索取空閑 page 存儲資料。
通過對 spill 操作進行更深入細緻的調查，我們發現了性能瓶頸所在, spill 操作中如下代碼耗時最多：
1// arrayAllocate returns the starting page id of a contiguous list of pages of a given size.
2// If a contiguous block cannot be found then 0 is returned.
3func (f *freelist) arrayAllocate(txid txid, n int) pgid {
4 ...
5 var initial, previd pgid
6 for i, id := range f.ids {
7 if id <= 1 {
8 panic(fmt.Sprintf("invalid page allocation: %d", id))
9 }
10
11 // Reset initial page if this is not contiguous.
12 if previd == 0 || id-previd != 1 {
13 initial = id
14 }
15
16 // If we found a contiguous block then remove it and return it.
17 if (id-initial)+1 == pgid(n) {
18 if (i + 1) == n {
19 f.ids = f.ids[i+1:]
20 } else {
21 copy(f.ids[i-n+1:], f.ids[i+1:]) # 複制
22 f.ids = f.ids[:len(f.ids)-n]
23 }
24
25 ...
26 return initial
27 }
28
29 previd = id
30 }
31 return 0
32} 之前 etcd 内部内部工作原理講到 boltdb 将之前釋放空閑的頁面存儲為 freelist 供之後使用，如上代碼就是 freelist 内部 page 再配置設定的函數，他嘗試配置設定連續的 n個 page頁面供使用，傳回起始頁 page id。 代碼中 f.ids 是一個數組，他記錄了内部空閑的 page 的 id。例如之前上圖頁面裡 f.ids=[42,44,47,48,49,51]
當請求 n 個連續頁面時，這種方法通過線性掃描的方式進行查找。當遇到内部存在大量碎片時，例如 freelist 内部存在的頁面大多是小的頁面，比如大小為 1 或者 2，但是當需要一個 size 為 4 的頁面時候，這個算法會花很長時間去查找，另外查找後還需調用 copy 移動數組的元素，當數組元素很多，即内部存儲了大量資料時，這個操作是非常慢的。
5優化方案
由上面的分析， 我們知道線性掃描查找空頁面的方法确實比較 naive, 在大資料量場景下很慢。前 yahoo 的 chief scientist Udi Manber 曾說過在 yahoo 内最重要的三大算法是 hashing, hashing and hashing!（From algorithm design manual)
是以我們的優化方案中将相同大小的連續頁面用 set 組織起來，然後在用 hash 算法做不同頁面大小的映射。如下面新版 freelist 結構體中的 freemaps 資料結構。
1type freelist struct {
2 ...
3 freemaps map[uint64]pidSet // key is the size of continuous pages(span), value is a set which contains the starting pgids of same size
4 forwardMap map[pgid]uint64 // key is start pgid, value is its span size
5 backwardMap map[pgid]uint64 // key is end pgid, value is its span size
6 ...
7} 除此之外，當頁面被釋放，我們需要盡可能的去合并成一個大的連續頁面，之前的算法這裡也比較簡單，是個是耗時的操作 O(nlgn).我們通過 hash 算法，新增了另外兩個資料結構 forwardMap 和 backwardMap, 他們的具體含義如下面注釋所說。
當一個頁面被釋放時，他通過查詢 backwardMap 嘗試與前面的頁面合并，通過查詢 forwardMap 嘗試與後面的頁面合并。具體算法見下面mergeWithExistingSpan 函數。
1// mergeWithExistingSpan merges pid to the existing free spans, try to merge it backward and forward
2func (f *freelist) mergeWithExistingSpan(pid pgid) {
3 prev := pid - 1
4 next := pid + 1
5
6 preSize, mergeWithPrev := f.backwardMap[prev]
7 nextSize, mergeWithNext := f.forwardMap[next]
8 newStart := pid
9 newSize := uint64(1)
10
11 if mergeWithPrev {
12 //merge with previous span
13 start := prev + 1 - pgid(preSize)
14 f.delSpan(start, preSize)
15
16 newStart -= pgid(preSize)
17 newSize += preSize
18 }
19
20 if mergeWithNext {
21 // merge with next span
22 f.delSpan(next, nextSize)
23 newSize += nextSize
24 }
25
26 f.addSpan(newStart, newSize)
27} 新的算法借鑒了記憶體管理中的 segregated freelist 的算法，它也使用在 tcmalloc 中。它将 page 配置設定時間複雜度由 O(n) 降為 O(1), 釋放從 O(nlgn) 降為 O(1)，優化效果非常明顯。
6實際優化效果
以下測試為了排除網絡等其他原因，就測試一台 etcd 節點叢集，唯一的不同就是新舊算法不同, 還對老的 tair 作為後端存儲的方案進行了對比測試. 模拟測試為接近真實場景，模拟 100 個用戶端同時向 etcd put 1 百萬的 kv 對，kv 内容随機，控制最高 5000qps，總計大約 20~30GB 資料。測試工具是基于官方代碼的 benchmark 工具，各種情況下用戶端延時如下：
舊的算法時間
有一些逾時沒有完成測試。
新的 segregated hashmap
etcd over tail 時間
在資料量更大的場景下，并發度更高的情況下新算法提升倍數會更多。
7總結
這次優化将 boltdb中 freelist 配置設定的内部算法由 O(n) 降為 O(1), 釋放部分從 O(nlgn) 降為 O(1), 解決了在超大資料規模下 etcd 内部存儲的性能問題，使 etcd 存儲 100GB 資料時的讀寫操作也像存儲 2GB 一樣流暢。并且這次的新算法完全向後相容，無需做資料遷移或是資料格式變化即可使用新技術帶來的福利！
目前該優化經過 2 個多月的反複測試, 上線使用效果穩定，并且已經貢獻到了開源社群（
https://github.com/etcd-io/bbolt/pull/141），在新版本的 boltdb 和 etcd 中，供更多人使用。