基于Redis的熱點Key統(tǒng)計方案研究與實現(xiàn)

唐天兵 柳青

摘要：在互聯(lián)網(wǎng)電商業(yè)務(wù)中，用戶會在單位時間內(nèi)多次訪問同一緩存數(shù)據(jù)而形成緩存熱點，進而影響數(shù)據(jù)庫以及整個交易鏈路的穩(wěn)定。以Redis數(shù)據(jù)庫為背景，利用Libnids（網(wǎng)絡(luò)入侵檢測系統(tǒng)函數(shù)庫）捕獲網(wǎng)卡數(shù)據(jù)包，構(gòu)建Redis協(xié)議狀態(tài)機解析數(shù)據(jù)包，找出請求中的Key字段，利用時間復(fù)雜度為O（1）的LFU算法統(tǒng)計熱點Key，精確的熱點統(tǒng)計為熱點處理提供了可行方案。

關(guān)鍵詞：Redis;熱點Key;抓包;LFU

中圖分類號：TP393 ? ? ? ?文獻標識碼：A

文章編號：1009-3044（2020）31-0248-03

1 引言

伴隨著Web時代的飛速發(fā)展，用戶和業(yè)務(wù)對網(wǎng)站的要求均越來越高，用戶需要更快的訪問速度來獲得良好的體驗。因此出現(xiàn)了一種叫NoSQL[1]的新興數(shù)據(jù)管理系統(tǒng)，作為NoSQL數(shù)據(jù)庫中一個子集的 Key-Value 存儲系統(tǒng)[2]，如Redis[3]、Memcached[4]，存儲用戶Web Session，或者微博熱點消息等，從而達到加速Web訪問和減輕關(guān)系型數(shù)據(jù)庫訪問壓力的目的。在工業(yè)界，很多大公司都部署著大規(guī)模的分布式 Key-Value 系統(tǒng)集群充當關(guān)鍵系統(tǒng)的數(shù)據(jù)層。作為最著名的開源 Key-Value 系統(tǒng)之一的Redis，在分布式集群方案方面已經(jīng)有一些主流的集群方案。

單臺Redis的讀寫性能就是單Key最大的讀寫性能瓶頸，并且無法通過橫向擴展Redis數(shù)量解決。但是由于電商業(yè)務(wù)經(jīng)常會有諸如秒殺、搶票等活動，即在單位時間內(nèi)對一個Key進行多次請求，極易形成單Key熱點。此時如果Redis單點出現(xiàn)問題，則會對后端關(guān)系型數(shù)據(jù)庫造成極大的流量沖擊，從而影響整個服務(wù)鏈路質(zhì)量和集群健康，甚至造成服務(wù)不可用。因此，解決熱點Key的問題對于集群健康和業(yè)務(wù)平穩(wěn)運行都有非常重要的意義。

2 系統(tǒng)整體架構(gòu)

Redis熱點Key統(tǒng)計方案整體由五部分構(gòu)成，分別是客戶端流量構(gòu)造、數(shù)據(jù)包的捕獲、Redis協(xié)議解析，熱點Key判定和熱點Key前端頁面。系統(tǒng)整體架構(gòu)如圖1所示。

在圖1中，首先使用Redis的Java客戶端Jedis發(fā)起流量的寫入，其中流量中有一部分Key默認是熱點Key，其余Key均為隨機生成的，因此多次請求之后，熱點Key相比其余的Key會具有很高的訪問次數(shù)，之后由數(shù)據(jù)包捕獲模塊捕獲到網(wǎng)卡數(shù)據(jù)包，接著交給Redis協(xié)議狀態(tài)機解析Redis協(xié)議，找出訪問請求中的Key，然后通過熱點Key識別算法在一個統(tǒng)計周期內(nèi)找出訪問次數(shù)滿足熱點Key定義的Key。熱點Key的顯示模塊由后端提供API，前端通過Ajax請求后端提供的數(shù)據(jù)，完成顯示。

3 O（1）的LFU算法

3.1主要思想

LFU算法基于Prof. Ketan Shah等人的思想實現(xiàn)，通常的LFU算法時間復(fù)雜度為O（logn），利用HashMap和小頂堆配合實現(xiàn)。借助雙向鏈表將Key按照訪問頻率分類，實現(xiàn)快速索引，可使時間復(fù)雜度為O（1）[5]。

O（1）的LFU算法的主要思想為：使用兩個雙向鏈表，一個用于保存訪問頻率，一個用于保存訪問頻率相同的所有元素，擁有6個元素的LFU鏈。如圖2所示，矩形框表示訪問頻率，圓形框表示訪問頻率相同的Key。

圖2中x和y訪問頻率都為1，它們在同一個頻率鏈上，插入新元素時插入到訪問頻率最小的鏈表尾部，如果只是需要增加訪問頻率，比如get操作，那就將元素移動到當前訪問頻率加1的鏈表上最后一個位置。例如圖2中z元素被訪問一次之后，就將a元素加入和z元素同一個頻率的鏈上。

基于上述思想，本文實現(xiàn)的LFU算法具體如下：

用一個HashMap保存Key及其訪問的對應(yīng)信息，例如訪問次數(shù)等，稱為hotKeyMap，接著按照訪問次數(shù)對key分類，訪問次數(shù)相同的key，保存在同一個list中，并將所有的list保存進一個HashMap中，稱為hotKeyFreq，它的key對應(yīng)訪問頻率，最后還需要保存每個key對應(yīng)在鏈表中的位置，稱為hotKeyIter。這三個數(shù)據(jù)結(jié)構(gòu)定義為：

unordered_map>hotKeyMap_;

unordered_map>hotKeyFreq_;

unordered_map：：iterator>hotkeyIter_;

3.2 add操作

如果容量已滿，需要淘汰部分key，則首先從hotKeyFreq_里找到訪問數(shù)量最小的鏈，剔除最小鏈的第一個元素，即pop_front（）操作，并且從hotKeyMap_和hotKeyIter_刪除對應(yīng)Key的信息。

如果容量沒有滿，則是一個正常的添加操作，首先將Key的信息中訪問次數(shù)初始化為1，然后將key添加進hotKeyMap_，在hotKetFreq_訪問頻率為1的鏈表末尾添加key，即push_back操作。add操作的核心代碼如下所示：

void addKey（std：：string key， HotKeyInfo* keyInfo）

{ ? ?if （capacity_ <= 0） {

return;

}

if （hotKeyMap_.size（）>= capacity_） {

/* 獲取被淘汰的key */

std：：string evictKey = hotKeyFreq_[minFreq_].front（）;

/* 刪除迭代器 */

hotkeyIter_.erase（evictKey）;

hotKeyMap_.erase（evictKey）;

hotKeyFreq_[minFreq_].pop_front（）;

}

/* 插入新的key */

hotKeyMap_.insert（std：：make_pair（key， keyInfo））;

hotKeyFreq_[1].push_back（key）;

hotkeyIter_[key] = --hotKeyFreq_[1].end（）;

minFreq_ = 1;

}

3.3 update操作

對于update操作，不涉及淘汰的問題，因為沒有新增加Key，首先需要將hotkeyFreq_中相應(yīng)位置的元素刪除掉，而位置在hotKeyIter中已經(jīng)保存了，然后增加key的訪問次數(shù)，之后將key添加到訪問次數(shù)對應(yīng)的隊列中的最后一個元素，并且將迭代器保存在hotkeyIter_中。算法的核心代碼如下：

void updates（std：：string key） {

hotKeyFreq_[hotKeyMap_[key]->times].erase（hotkeyIter_[key]）;

hotkeyIter_.erase（key）;

/* 增加訪問次數(shù) */

hotKeyMap_[key]->times++;

hotKeyFreq_[hotKeyMap_[key]->times].push_back（key）;

hotkeyIter_[key] = --hotKeyFreq_[hotKeyMap_[key]->times].end（）;

if （hotKeyFreq_[minFreq_].size（） == 0） {

/* 保存訪問頻率中最小的 */

minFreq++;

}

}

4系統(tǒng)測試

為了對比測試O（1）的LFU算法，同時實現(xiàn)了時間復(fù)雜度為O（n）的HashMap算法。

4.1識別效率

分別在QPS（Queries Per Second：每秒查詢率）為60、600和4000的情況下對兩種識別算法識別熱點時間進行5次統(tǒng)計得到表1。

根據(jù)表1中的數(shù)據(jù)，在QPS相同的情況下，LFU算法識別熱點所用的時間和HashMap相比較少，主要原因是HashMap的統(tǒng)計算法需要在一個統(tǒng)計周期結(jié)束后比較所有的Key之后找出熱點Key，在QPS較大的情況下，需要遍歷的鏈表也更加長，因此使用的時間更加多，而因為LFU算法的淘汰機制，使得LFU維護的鏈表長度是固定的，因此可以在更短的時間內(nèi)發(fā)現(xiàn)熱點Key。

4.2內(nèi)存消耗

在不同的QPS下，通過系統(tǒng)自帶的進程監(jiān)視器檢測兩種算法的內(nèi)存消耗，可以得到表2。

根據(jù)表2中的數(shù)據(jù)，可以看到，隨著QPS的增長，HashMap統(tǒng)計算法在內(nèi)存消耗上持續(xù)增加，因為需要將所有Key都保存，而LFU算法的內(nèi)存消耗主要取決于預(yù)設(shè)的capacity，即需要保存多少Key的容量大小，超過此容量意味著需要逐出，所以在capacity不變的情況下，內(nèi)存消耗幾乎不會發(fā)生變化。

綜上，對于兩種算法的對比情況如表3所示。

因此，選用LFU作為熱點識別的默認算法，但是如果需要做全量Key的信息統(tǒng)計或者審計等操作，也可以使用HashMap算法做到。

5結(jié)束語

熱點Key的識別是熱點處理的基礎(chǔ)和前提，本文的Redis熱點Key統(tǒng)計方案通過捕獲網(wǎng)卡數(shù)據(jù)包，解析Redis網(wǎng)絡(luò)協(xié)議，使用熱點Key識別算法完成了對熱點Key的精準識別，提供了一套完整的數(shù)據(jù)捕獲、協(xié)議分析、熱點識別、監(jiān)控顯示的Redis熱點統(tǒng)計方案。

參考文獻：

[1] Pokorny J.NoSQL databases：a step to database scalability in web environment[J].International Journal of Web Information Systems，2013，9（1）：69-82.

[2] DeCandiaG， HastorunD， StevenGrimm， etal. Dynamo： Amazon'shighly available key-value store[J]. OperatingSystems Review， 2007， 41（6）： 205-20.

[3] Antirez. Redis[EB/OL]. https：//github.com/antirez/redis. 2018

[4] Brad Fitzpatrick. Memcached[EB/OL]. https：//github.com/memcached/memcached. 2018

[5] Shah K， Mitra A， Matani D. An O （1） algorithm for implementing the LFU cache eviction scheme[J]. Technical report， 2010.

【通聯(lián)編輯：代影】