2017雙11技術揭秘—分散式緩存服務Tair的熱點數據散列機制

作者：劉歡（淺奕）

1 問題背景

分散式緩存一般被定義為一個數據集合，它將數據分布（或分區）於任意數目的集群節點上。集群中的一個具體節點負責緩存中的一部分數據，整體對外提供統一的訪問介面[1]。分散式緩存一般基於冗餘備份機制實現數據高可用，又被稱為內存數據網格（IMDG, in-memory data grid）。在雲平台飛速發展的今天，作為提升應用性能的重要手段，分散式緩存技術在工業界得到了越來越廣泛的關注和研發投入[2]。彈性緩存平台[3]是分散式緩存集群在雲計算場景下的新形態，其強調集群的動態擴展性與高可用性。動態擴展性表達了緩存平台可提供透明的服務擴展的能力，高可用性則表達了緩存平台可以容忍節點失效。

Tair是阿里巴巴集團自研的彈性緩存/存儲平台，在內部有著大量的部署和使用。Tair的核心組件是一個高性能、可擴展、高可靠的NoSQL存儲系統。目前支持MDB、LDB、RDB等存儲引擎。其中MDB是類似Memcached的內存存儲引擎，LDB是使用LSM Tree的持久化磁碟KV存儲引擎，RDB是支持Queue、Set、Maps等數據結構的內存及持久化存儲引擎。

Tair的數據分片和路由演算法採用了Amazon於2007年提出的一種改進的一致性哈希演算法[4]。該演算法將整個哈希空間分為若干等大小的Q份數據分區（也稱為虛擬節點，Q>>N，N為緩存節點數），每個緩存節點依據其處理能力分配不同數量的數據分區。客戶端請求的數據Key值經哈希函數映射至哈希環上的位置記為token，token值再次被哈希映射為某一分區標識。得到分區標識後，客戶端從分區伺服器映射表中查詢存放該數據分區的緩存節點後進行數據訪問。使用該演算法對相同數據Key進行計算，其必然會被映射到固定的DataServer上，如圖：

此時DataServer單節點的讀寫性能便成了單數據Key的讀寫性能瓶頸，且無法通過水平擴展節點的方式來解決。由於阿里巴巴集團內部電商系的促銷活動天然的存在熱點數據，所以要增強整個彈性緩存/存儲平台的穩定性和服務能力，就必須提升熱點數據的讀寫能力，使其能做到水平擴展。

2 解決方案

解決方案分為三部分：熱點識別、讀熱點方案和寫熱點方案。

其中讀寫熱點方案都是以服務端能對熱點訪問進行精準的識別為前提的。另外對於可以提前預知熱點Key的情況，也提供相應的客戶端API以支持特定數據Key或者特定Namespace的所有數據Key預先標記為熱點Key的能力。

2.1 DataServer上的熱點統計過程

DataServer收到客戶端的請求後，由每個具體處理請求的工作線程（Worker Thread）進行請求的統計。工作線程用來統計熱點的數據結構均為ThreadLocal模式的數據結構，完全無鎖化設計。熱點識別演算法使用精心設計的多級加權LRU鏈和HashMap組合的數據結構，在保證服務端請求處理效率的前提下進行請求的全統計，支持QPS熱點和流量熱點（即請求的QPS不大但是數據本身過大而造成的大流量所形成的熱點）的精準識別。每個採樣周期結束時，工作線程會將統計的數據結構轉交到後台的統計線程池進行分析處理。統計工作非同步在後台進行，不搶佔正常的數據請求的處理資源。

2.2 讀熱點方案

2.2.1 服務端設計

原始Tair的數據訪問方式是先進行Hash(Key)%BucketCount的計算，得出具體的數據存儲Bucket，再檢索數據路由表找到該Bucket所在的DataServer後對其進行讀寫請求的。所以相同Key的讀寫請求必然落在固定的DataServer上，且無法通過水平擴展DataServer數量來解決。

本方案通過在DataServer上劃分一塊HotZone存儲區域的方式來解決熱點數據的訪問。該區域存儲當前產生的所有讀熱點的數據，由客戶端配置的緩存訪問邏輯來處理各級緩存的訪問。多級緩存架構如下：

所有DataServer的HotZone存儲區域之間沒有權重關係，每個HotZone都存儲相同的讀熱點數據。客戶端對熱點數據Key的請求會隨機到任意一台DataServer的HotZone區域，這樣單點的熱點請求就被散列到多個節點乃至整個集群。

2.2.2客戶端設計

2.2.2.1 客戶端邏輯

當客戶端在第一次請求前初始化時，會獲取整個Tair集群的節點信息以及完整的數據路由表，同時也會獲取配置的熱點散列機器數（即客戶端訪問的HotZone的節點範圍）。隨後客戶端隨機選擇一個HotZone區域作為自身固定的讀寫HotZone區域。在DataServer數量和散列機器數配置未發生變化的情況下，不會改變選擇。即每個客戶端只訪問唯一的HotZone區域。

客戶端收到服務端反饋的熱點Key信息後，至少在客戶端生效N秒。在熱點Key生效期間，當客戶端訪問到該Key時，熱點的數據會首先嘗試從HotZone節點進行訪問，此時HotZone節點和源數據DataServer節點形成一個二級的Cache模型。客戶端內部包含了兩級Cache的處理邏輯，即對於熱點數據，客戶端首先請求HotZone節點，如果數據不存在，則繼續請求源數據節點，獲取數據後非同步將數據存儲到HotZone節點裡。使用Tair客戶端的應用常規調用獲取數據的介面即可，整個熱點的反饋、識別以及對多級緩存的訪問對外部完全透明。HotZone緩存數據的一致性由客戶端初始化時設置的過期時間來保證，具體的時間由具體業務對緩存數據不一致的最大容忍時間來決定。

客戶端存儲於本地的熱點反饋過期後，數據Key會到源DataServer節點讀取。如果該Key依舊在服務端處於熱點狀態，客戶端會再次收到熱點反饋包。因為所有客戶端存儲於本地的熱點反饋信息的失效節奏不同，所以不會出現同一瞬間所有的請求都回源的情況。即使所有請求回源，也僅需要回源讀取一次即可，最大的讀取次數僅為應用機器數。若回源後發現該Key已不是熱點，客戶端便回到常規的訪問模式。

2.2.2.2 散列比和QPS偏差的關係

設集群普通QPS為 C，熱點QPS為 H，機器數為 N，則每台機器QPS為:

A=(C+H)/N

則普通機器QPS偏差比為：

P_c=(C/N)/A=(C/N)/((C+H)/N)=C/(C+H) ，當 H=0 時，P_c=1

則熱點機器偏差比為：

P_h=(C/N+H)/A=(C/N+H)/((C+H)/N)=(C+HN)/(C+H) ，當 H=0 時，P_h=1

進行散列後，設散列機器數為 M，則熱點機器偏差比為：

P_(h)=(C/N+H/M)/A=(C/N+H/M)/((C+H)/N)=(CM+HN)/(M(C+H))

設散列比為 K，即 M=KN，則有：

P_(h)=(CM+HN)/(M(C+H))=(CKN+HN)/(KN(C+H))=(CK+H)/(K(C+H))，當 K=1 時， P_(h)=1

2.3 寫熱點方案

2.3.1 服務端設計

2.3.1.1 處理方式

對於寫熱點，因為一致性的問題，難以使用多級緩存的方式來解決。如果採用寫本地Cache，再非同步更新源DataServer的方案。那麼在Cache寫入但尚未更新的時候，如果業務機器宕機，就會有已寫數據丟失的問題。同時，本地 Cache會導致進行數據更新的某應用機器當前更新周期內的修改對其他應用機器不可見，從而延長數據不一致的時間。故多級Cache的方案無法支持寫熱點。最終寫熱點採用在服務端進行請求合併的方式進行處理。

熱點Key的寫請求在IO線程被分發到專門的熱點合併線程處理，該線程根據Key對寫請求進行一定時間內的合併，隨後由定時線程按照預設的合併周期將合併後的請求提交到引擎層。合併過程中請求結果暫時不返回給客戶端，等請求合併寫入引擎成功後統一返回。這樣做不會有一致性的問題，不會出現寫成功後卻讀到舊數據，也避免了LDB集群返回成功，數據並未落盤的情況（假寫）。具體的合併周期在服務端可配置，並支持動態修改生效。

2.3.2 客戶端設計

寫熱點的方案對客戶端完全透明，不需要客戶端做任何修改。

2.3.3 性能指標

LDB集群實際壓測效果為單Key合併能做到單Key百萬的QPS（1ms合併，不限制合併次數），線上實際集群為了儘可能保證實時性，均採用了最大0.1ms以及單次最大合併次數為100次的限制。這樣單Key在引擎層的最大落盤QPS就能控制在10000以下（而合併的QPS則取決於應用的訪問頻率）。Tair服務端的包處理是完全非同步化的，進行熱點請求的合併操作並不阻塞對其他請求的處理。唯一的影響就是增大客戶端對熱點key的寫請求的RT. 按照現在的配置，最壞情況下，客戶端的熱點key的寫操作會增大0.1ms，這個影響是微乎其微的。

【招聘傳送門】歡迎感興趣的同學加入我們，詳情請點擊：

Tengine資深開發工程師/研發專家 分散式存儲研發專家 超大規模內存存儲系統研發專家 系統運營開發(Devops)專家

參考文獻

[1] Oracle Coherence,http://www.oracle.com/technetwork/cn/middleware/coherence/distributed-caching-089211-zhs.html

[2] Qin XL, Zhang WB, Wei J, Wang W, Zhong H, Huang T. Progress and challenges of distributed caching techniques in cloud computing. Ruanjian Xuebao/Journal of Software, 2013,24(1):50?66 (in Chinese). http://www.jos.org.cn/1000-9825/4276.htm

[3] Gualtieri M, Rymer JR. The forrester wave: Elastic caching platforms.Q2, 2010. ftp://ftp.software.ibm.com/software/solutions/soa/pdfs/wave_elastic_caching_platforms_q2_2010.pdf

[4] Hastorun D, Jampani M, Kakulapati G, Pilchin A, Sivasubramanian S, Vosshall P, Vogels W. Dynamo: Amazon』s highly available key-value store.In: Proc. of the ACM Symp. on Operating Systems Principles (SOSP 2007). 2007. 205?220. [doi: 10.1145/1323293.1294281]

推薦閱讀：