基于Redis的热点Key统计方案研究与实现
2020-12-28唐天兵柳青
唐天兵 柳青
摘要：在互联网电商业务中，用户会在单位时间内多次访问同一缓存数据而形成缓存热点，进而影响数据库以及整个交易链路的稳定。以Redis数据库为背景，利用Libnids（网络入侵检测系统函数库）捕获网卡数据包，构建Redis协议状态机解析数据包，找出请求中的Key字段，利用时间复杂度为O（1）的LFU算法统计热点Key，精确的热点统计为热点处理提供了可行方案。
关键词：Redis;热点Key;抓包;LFU
中图分类号：TP393 文献标识码：A
文章编号：1009-3044（2020）31-0248-03
1 引言
伴随着Web时代的飞速发展，用户和业务对网站的要求均越来越高，用户需要更快的访问速度来获得良好的体验。因此出现了一种叫NoSQL[1]的新兴数据管理系统，作为NoSQL数据库中一个子集的 Key-Value 存储系统[2]，如Redis[3]、Memcached[4]，存储用户Web Session，或者微博热点消息等，从而达到加速Web访问和减轻关系型数据库访问压力的目的。在工业界，很多大公司都部署着大规模的分布式 Key-Value 系统集群充当关键系统的数据层。作为最著名的开源 Key-Value 系统之一的Redis，在分布式集群方案方面已经有一些主流的集群方案。
单台Redis的读写性能就是单Key最大的读写性能瓶颈，并且无法通过横向扩展Redis数量解决。但是由于电商业务经常会有诸如秒杀、抢票等活动，即在单位时间内对一个Key进行多次请求，极易形成单Key热点。此时如果Redis单点出现问题，则会对后端关系型数据库造成极大的流量冲击，从而影响整個服务链路质量和集群健康，甚至造成服务不可用。因此，解决热点Key的问题对于集群健康和业务平稳运行都有非常重要的意义。
2 系统整体架构
Redis热点Key统计方案整体由五部分构成，分别是客户端流量构造、数据包的捕获、Redis协议解析，热点Key判定和热点Key前端页面。系统整体架构如图1所示。
在图1中，首先使用Redis的Java客户端Jedis发起流量的写入，其中流量中有一部分Key默认是热点Key，其余Key均为随机生成的，因此多次请求之后，热点Key相比其余的Key会具有很高的访问次数，之后由数据包捕获模块捕获到网卡数据包，接着交给Redis协议状态机解析Redis协议，找出访问请求中的Key，然后通过热点Key识别算法在一个统计周期内找出访问次数满足热点Key定义的Key。热点Key的显示模块由后端提供API，前端通过Ajax请求后端提供的数据，完成显示。
3 O（1）的LFU算法
3.1主要思想
LFU算法基于Prof. Ketan Shah等人的思想实现，通常的LFU算法时间复杂度为O（logn），利用HashMap和小顶堆配合实现。借助双向链表将Key按照访问频率分类，实现快速索引，可使时间复杂度为O（1）[5]。
O（1）的LFU算法的主要思想为：使用两个双向链表，一个用于保存访问频率，一个用于保存访问频率相同的所有元素，拥有6个元素的LFU链。如图2所示，矩形框表示访问频率，圆形框表示访问频率相同的Key。
图2中x和y访问频率都为1，它们在同一个频率链上，插入新元素时插入到访问频率最小的链表尾部，如果只是需要增加访问频率，比如get操作，那就将元素移动到当前访问频率加1的链表上最后一个位置。例如图2中z元素被访问一次之后，就将a元素加入和z元素同一个频率的链上。
基于上述思想，本文实现的LFU算法具体如下：
用一个HashMap保存Key及其访问的对应信息，例如访问次数等，称为hotKeyMap，接着按照访问次数对key分类，访问次数相同的key，保存在同一个list中，并将所有的list保存进一个HashMap中，称为hotKeyFreq，它的key对应访问频率，最后还需要保存每个key对应在链表中的位置，称为hotKeyIter。这三个数据结构定义为：
unordered_map
unordered_map
unordered_map
3.2 add操作
如果容量已满，需要淘汰部分key，则首先从hotKeyFreq_里找到访问数量最小的链，剔除最小链的第一个元素，即pop_front（）操作，并且从hotKeyMap_和hotKeyIter_删除对应Key的信息。
如果容量没有满，则是一个正常的添加操作，首先将Key的信息中访问次数初始化为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_中相应位置的元素删除掉，而位置在hotKeyIter中已经保存了，然后增加key的访问次数，之后将key添加到访问次数对应的队列中的最后一个元素，并且将迭代器保存在hotkeyIter_中。算法的核心代码如下：
void updates（std：：string key） {
hotKeyFreq_[hotKeyMap_[key]->times].erase（hotkeyIter_[key]）;
hotkeyIter_.erase（key）;
/* 增加访问次数 */
hotKeyMap_[key]->times++;
hotKeyFreq_[hotKeyMap_[key]->times].push_back（key）;
hotkeyIter_[key] = --hotKeyFreq_[hotKeyMap_[key]->times].end（）;
if （hotKeyFreq_[minFreq_].size（） == 0） {
/* 保存访问频率中最小的 */
minFreq++;
}
}
4系统测试
为了对比测试O（1）的LFU算法，同时实现了时间复杂度为O（n）的HashMap算法。
4.1识别效率
分别在QPS（Queries Per Second：每秒查询率）为60、600和4000的情況下对两种识别算法识别热点时间进行5次统计得到表1。
根据表1中的数据，在QPS相同的情况下，LFU算法识别热点所用的时间和HashMap相比较少，主要原因是HashMap的统计算法需要在一个统计周期结束后比较所有的Key之后找出热点Key，在QPS较大的情况下，需要遍历的链表也更加长，因此使用的时间更加多，而因为LFU算法的淘汰机制，使得LFU维护的链表长度是固定的，因此可以在更短的时间内发现热点Key。
4.2内存消耗
在不同的QPS下，通过系统自带的进程监视器检测两种算法的内存消耗，可以得到表2。
根据表2中的数据，可以看到，随着QPS的增长，HashMap统计算法在内存消耗上持续增加，因为需要将所有Key都保存，而LFU算法的内存消耗主要取决于预设的capacity，即需要保存多少Key的容量大小，超过此容量意味着需要逐出，所以在capacity不变的情况下，内存消耗几乎不会发生变化。
综上，对于两种算法的对比情况如表3所示。
因此，选用LFU作为热点识别的默认算法，但是如果需要做全量Key的信息统计或者审计等操作，也可以使用HashMap算法做到。
5结束语
热点Key的识别是热点处理的基础和前提，本文的Redis热点Key统计方案通过捕获网卡数据包，解析Redis网络协议，使用热点Key识别算法完成了对热点Key的精准识别，提供了一套完整的数据捕获、协议分析、热点识别、监控显示的Redis热点统计方案。
参考文献：
[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.
【通联编辑：代影】
