返回顶部
关闭软件导航
位置:首页 > 资讯 > 电商资讯>性能提升2.58倍阿里很快KV存储引擎揭秘
性能提升2.58倍阿里很快KV存储引擎揭秘

阿里妹导读:阿里云智能数据库Tair团队主要负责自研分布式键值存储(KVS)系统,几乎涵盖了淘宝、天猫、阿里妈妈、菜鸟、钉钉、优酷、高德等阿里巴巴所有核心业务。十多年来,始终如一为阿里业务提供着高可靠、高性能、低成本的数据存储与访问服务。

作者:民泰

01概述

近日,Tair团队的一篇论文——HotRing:AHotspot-AwareIn-MemoryKey-ValueStore被FAST'20ResearchTrack接收(USENIXConferenceonFileandStorageTechniques(FAST),CCFA类会议,存储领域顶会,2020年接受率16%)。

HotRing是Tair团队的创新性纯内存KV存储引擎设计。其引擎吞吐性能可达600Mops/s,与目前很快的KVS系统相比,可实现2.58倍的性能提升。HotRing很重要的创新点是:极大的提升了KVS引擎对于热点访问的承载能力。这对于KVS系统的稳定性以及成本控制尤为 关键。

为了方便大家更通俗全面的理解这篇论文,本文将从阿里巴巴的双十一零点峰值讲起,介绍峰值下数据库整体架构所面临的热点问题,再介绍Tair团队在解决热点方面一次次的优化提升,很后介绍Tair的创新性引擎HotRing。

02背景

2021年天猫双11再次刷新世界纪录,零点的订单峰值达到54.4万笔/秒。有订单就涉及到交易,有交易就需要数据库的事务保证,因此阿里巴巴数据库将在这时面临巨大的冲击。

现实往往更加严重,在业务方面,一次订单随着业务逻辑在后端会放大为数十次的访问;在客户方面,大量的客户只是疯狂的访问,并没有生成订单。因此,在双11的零点峰值,业务实际的访问量级是10亿次/秒。

Tair作为高并发分布式的KVS系统,在这时发挥了重要作用。如下面的逻辑图所示,Tair作为数据库的分布式缓存系统,缓存了大量的热点数据(例如商品,库存,风控信息等),为数据库反抗了巨大的访问量。2021年双11,Tair的峰值访问为9.92亿次/秒。

在业务层面,热点问题很好理解,很典型的就是双十一零点秒杀。这会导致数据访问呈现严重倾斜的幂律分布。

我们分析了多种业务的数据访问分布,如下图所示,大量的数据访问只集中在少部分的热点数据中,若用离散幂率分布(Zipfian)刻画,其θ参数约为1.22。相似地,Facebook的一篇论文同样也展示了近似的数据访问分布(参考论文[3])。

直观上可以用下图来解释。以苹果新手机发售举例。手机的库存等信息只存在KVS的一个节点中。当新手机发售后,大量的果粉疯狂进行抢购下单,业务的访问量基本都聚集在这一个节点上。节点可能无法承载大量的热点访问,进而引发系统崩溃,严重影响用户体验。

为了保证双十一丝般顺滑的购物体验,Tair针对热点问题进行了多层优化:

客户端缓存:通过预先标记热点,设置客户端层面的缓存。以上图来理解,就是将访问在业务层面返回,直接减小了KVS系统的负载压力。

热点散列技术:通过将热点数据备份到多个KVS节点上,分摊热点访问。以少量成本的资源与系统开销,换取了成倍的系统承载力。

RCU无锁引擎:通过采用Read-Copy-Update的方式,实现内存KV引擎的无锁化(lock-free)访问(参考论文[1,2])。成倍提升KVS引擎的性能,进而提高热点的承载力。

HotRing:在RCU无锁引擎基础上,我们进行索引结构的热点感知设计,提出了一种名为HotRing的新型热点感知内存KVS。HotRing可动态识别热点,并实时的进行索引结构的无锁调整,对于幂律分布场景实现成倍的引擎性能提升。

经过十年的技术沉淀,我们已将集团Tair数据库的缓存技术释放到云上,普惠大众,即“阿里云Redis企业版”。

03HotRing

现有的内存KVS引擎通常采用链式哈希作为索引,结构如下图所示。首先,根据数据的键值(k)计算其哈希值h(k),对应到哈希表(Hashtable)的某个头指针(Headi)。根据头指针遍历相应的冲突链(CollisionChain)的所有数据(Item),通过键值比较,找到目标数据。假如目标数据不在冲突链中(readmiss),则可在冲突链头部插入该数据。

在链式哈希索引结构中,访问位于冲突链尾部的数据,需要经过更多的索引跳数,即更多次的内存访问。很直观的想法是,假如可以将热点数据放置在冲突链头部,那么系统对于热点数据的访问将会有更快的响应速度。

但是,数据在冲突链中的位置由数据的插入顺序决定,这和数据的冷热程度是互相独立的。因此,如图所示,热点数据(HotItem)在冲突链中的位置是完全均匀分布。

理想的设计也很直观,就是将所有热点数据移动到冲突链的头部。但有两方面因素使得这个问题非常难解。一方面,数据的热度是动态变化的,必须实现动态的热点感知保证热点时效性。另一方面,内存KVS的引擎性能是很敏感的(一次访问的时延通常是100ns量级),必须实现无锁的热点感知维持引擎的高并发与高吞吐特性。

HotRing在传统链式哈希索引基础上,实现了有序环式哈希索引设计。如下图所示,将冲突链首尾连接形式冲突环,保证头指针指向任何一个item都可以遍历环上所有数据。然后,HotRing通过lock-free移动头指针,动态指向热度较高的item(或根据算法计算出的很优item位置),使得访问热点数据可以更快的返回。

下面通过如下4方面进行介绍:

设计1:为什么要实现为有序环?

设计2:如何动态识别热点并调整头指针?

设计3:如何保证无锁的并发访问?

设计4:如何根据热点数据量的动态变化进行无锁rehash?

实现环式哈希索引后,第一个问题是要保证查询的正确性。若为无序环,当一个readmiss操作遍历冲突环时,它需要一个标志来判定遍历何时终止,否则会形式死循环。但是在环上,所有数据都会动态变化(更新或删除),头指针同样也会动态移动,没有标志可以作为遍历的终止判定。

利用key排序可以解决这个问题,若目标key介于连续两个item的key之间,说明为readmiss操作,即可终止返回。由于实际系统中,数据key的大小通常为10~100B,比较会带来巨大的开销。哈希结构利用tag来减少key的比较开销。

如下图所示,tag是哈希值的一部分,每个key计算的哈希值,前k位用来哈希表的定位,后n-k位作为冲突链中进一步区分key的标志。为了减小排序开销,我们构建字典序:order=(tag,key)。先根据tag进行排序,tag相同再根据key进行排序。

下图比较了HotRing与传统链式哈希。以itemB举例,链式哈希需要遍历所有数据才能返回readmiss。而HotRing在访问itemA与C后,即可确认Breadmiss。因此针对readmiss操作,链式哈希需要遍历整个冲突链;而HotRing利用字典序,不仅可以正确终止,且平均只需遍历1/2冲突环。

HotRing实现了两种策略来实现周期性的热点识别与调整。每R次访问为一个周期(R通常设置为5),第R次访问的线程将进行头指针的调整。两种策略如下:

随机移动策略:每R次访问,移动头指针指向第R次访问的item。若已经指向该item,则头指针不移动。该策略的优势是,不需要额外的元数据开销,且不需要采样过程,响应速度极快。

采样分析策略:每R次访问,尝试启动对应冲突环的采样,统计item的访问频率。若第R次访问的item已经是头指针指向的item,则不启动采样。

采样所需的元数据结构如下图所示,分别在头指针处设置TotalCounter,记录该环的访问总次数,每个item设置Counter记录该item的访问次数。因为内存指针需要分配64bits,但实际系统地址索引只使用其中的48bits。我们使用剩余16bits设置标志位(例如TotalCounter、Counter等),保证不会增加额外的元数据开销。该策略的优势是,通过采样分析,可以计算选出很优的头指针位置,稳态时性能表现更优。

这一部分的细节设计有很多:

采样分析策略如何选出很优位置;

针对RCU更新操作的采样优化,

热点继续防止冷启动。

本文不再具体描述,有爱好请参考HotRing论文。

Tair的RCU无锁引擎是HotRing的设计基础。参考论文[1,2]对如何实现无锁链表进行了具体讲解,后续的所有无锁设计基本都沿用了他们的策略。有爱好可以读一下。这里我们举一个典型的并发示例进行介绍。

如下图所示,在链A->B->D上,线程1进行插入C的操作,同时线程2进行RCU更新B的操作,尝试更新为B'。线程1修改B的指针指向C,完成插入。而线程2修改A的指针指向B'完成更新。两个线程并发修改不同的内存,均可成功返回。但是这时遍历整条链(A->B'->D),将发现C无法被遍历到,导致正确性问题。

解决措施是利用上图(ItemFormat)中的Occupied标志位。当线程2更新B时,首先需要将B的Occupied标志位置位。线程1插入C需要修改B的指针(NextItemAddress),若发现Occupied标志位已置位,则需要重新遍历链表,尝试插入。通过使并发操作竞争修改同一内存地址,保证并发操作的正确性。

利用相同原理,我们保证了头指针移动操作,与CRUD操作的并发正确性。因此实现了HotRing的无锁并发访问。

如背景所述,对于极端的幂率分布场景,大量的数据访问只集中在少部分的热点数据中。因此只要保证热点数据可以位于头指针位置,冲突环即使很长,对于引擎的性能表现并不影响。引擎性能的降低,必然是因为冲突环上存在多个热点。因此HotRing设计了适应热点数据量的无锁rehash策略来解决这一问题。

HotRing利用访问所需平均内存访问次数(accessoverhead)来替代传统rehash策略的负载因子(loadfactor)。在幂率分布场景,若每个冲突环只有一个热点,HotRing可以保证accessoverhead

在本论文中,我们进行索引结构的热点感知设计,提出了一种名为HotRing的新型热点感知内存KVS,针对幂率分布的热点场景进行大量优化。HotRing可动态识别热点,并实时的进行索引结构的无锁调整,进而提供高并发高性能的无锁化访问。

性能提升2.58倍阿里很快KV存储引擎揭秘1

与传统的内存KVS索引相比,HotRing采用轻量级的热点识别策略,且没有增加元数据存储开销。但在幂律分布的应用场景中,HotRing的引擎吞吐性能可达600Mops/s,与目前很快KVS相比,可实现2.58倍的性能提升。

如果您觉得 性能提升2.58倍阿里很快KV存储引擎揭秘 这篇文章对您有用,请分享给您的好友,谢谢
文章地址:https://www.tianxianmao.com/article/online/12530.html
解放双手无尽可能,有问题添加天线猫微信