存儲

第五人格:etcd 在超大規模數據場景下的性能優化

作者 | 阿里云智能事業部高級開發工程師 陳星宇(宇慕)

劃重點

  • etcd 優化背景
  • 問題分析
  • 優化方案展示
  • 實際優化效果

本文被收錄在 5 月 9 日 cncf.io 官方 blog 中,鏈接:https://www.cncf.io/blog/2019/05/09/performance-optimization-of-etcd-in-web-scale-data-scenario/

概述

etcd 是一個開源的分布式的 kv 存儲系統, 最近剛被 CNCF 列為沙箱孵化項目。etcd 的應用場景很廣,很多地方都用到了它,例如 Kubernetes 就用它作為集群內部存儲元信息的賬本。本篇文章首先介紹我們優化的背景,為什么我們要進行優化, 之后介紹 etcd 內部存儲系統的工作方式,之后介紹本次具體的實現方式及最后的優化效果。

優化背景

由于阿里巴巴內部集群規模大,所以對 etcd 的數據存儲容量有特殊需求,之前的 etcd 支持的存儲大小無法滿足要求, 因此我們開發了基于 etcd proxy 的解決方案,將數據轉儲到了 tair 中(可類比 redis))。這種方案雖然解決了數據存儲容量的問題,但是弊端也是比較明顯的,由于 proxy 需要將數據進行搬移,因此操作的延時比原生存儲大了很多。除此之外,由于多了 tair 這個組件,運維和管理成本較高。因此我們就想到底是什么原因限制了 etcd 的存儲容量,我們是否可以通過技術手段優化解決呢?

提出了如上問題后我們首先進行了壓力測試不停地像 etcd 中注入數據,當 etcd 存儲數據量超過 40GB 后,經過一次 compact(compact 是 etcd 將不需要的歷史版本數據刪除的操作)后發現 put 操作的延時激增,很多操作還出現了超時。監控發現 boltdb 內部 spill 操作(具體定義見下文)耗時顯著增加(從一般的 1ms 左右激增到了 8s)。之后經過反復多次壓測都是如此,每次發生 compact 后,就像世界發生了停止,所有 etcd 讀寫操作延時比正常值高了幾百倍,根本無法使用。

etcd 內部存儲工作原理


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。

問題分析

由于發生了用戶數據的寫入, 因此內部 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????????}1011????????//?Reset?initial?page?if?this?is?not?contiguous.12????????if?previd?==?0?||?id-previd?!=?1?{13????????????initial?=?id14????????}1516????????//?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????????????}2425????????????...26????????????return?initial27????????}2829????????previd?=?id30????}31????return?032}

之前 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 移動數組的元素,當數組元素很多,即內部存儲了大量數據時,這個操作是非常慢的。

優化方案

由上面的分析, 我們知道線性掃描查找空頁面的方法確實比較 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?size4????forwardMap?????map[pgid]uint64?????????????//?key?is?start?pgid,?value?is?its?span?size5????backwardMap????map[pgid]uint64?????????????//?key?is?end?pgid,?value?is?its?span?size6????...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)1011????if?mergeWithPrev?{12????????//merge?with?previous?span13????????start?:=?prev?+?1?-?pgid(preSize)14????????f.delSpan(start,?preSize)1516????????newStart?-=?pgid(preSize)17????????newSize?+=?preSize18????}1920????if?mergeWithNext?{21????????//?merge?with?next?span22????????f.delSpan(next,?nextSize)23????????newSize?+=?nextSize24????}2526????f.addSpan(newStart,?newSize)27}

新的算法借鑒了內存管理中的 segregated freelist 的算法,它也使用在 tcmalloc 中。它將 page 分配時間復雜度由 O(n) 降為 O(1), 釋放從 O(nlgn) 降為 O(1),優化效果非常明顯。

實際優化效果

以下測試為了排除網絡等其他原因,就測試一臺 etcd 節點集群,唯一的不同就是新舊算法不同, 還對老的 tair 作為后端存儲的方案進行了對比測試. 模擬測試為接近真實場景,模擬 100 個客戶端同時向 etcd put 1 百萬的 kv 對,kv 內容隨機,控制最高 5000qps,總計大約 20~30GB 數據。測試工具是基于官方代碼的 benchmark 工具,各種情況下客戶端延時如下:舊的算法時間

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

新的 segregated hashmap

etcd over tail 時間

在數據量更大的場景下,并發度更高的情況下新算法提升倍數會更多。

總結

這次優化將  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 中,供更多人使用。

我還沒有學會寫個人說明!

同程旅游微服務最佳實踐

上一篇

美埃默里大學華人實驗室突遭關閉,兩華人教授及部分中國雇員被強制遣返

下一篇

你也可能喜歡

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

長按儲存圖像,分享給朋友

ITPUB 每周精要將以郵件的形式發放至您的郵箱


微信掃一掃

微信掃一掃