个人网站网站建设方案书,网站备案名字要怎么写,wordpress monk,做网站的保证承诺背景 DSP系统是互联网广告需求方平台#xff0c;用于承接媒体流量#xff0c;投放广告。业务特点是并发度高#xff0c;平均响应低#xff08;百毫秒#xff09;。 为了能够有效提高DSP系统的性能#xff0c;美团平台引入了一种带有清退机制的缓存结构LruCache(Least Rec… 背景 DSP系统是互联网广告需求方平台用于承接媒体流量投放广告。业务特点是并发度高平均响应低百毫秒。 为了能够有效提高DSP系统的性能美团平台引入了一种带有清退机制的缓存结构LruCache(Least Recently Used Cache)在目前的DSP系统中使用LruCache 键值存储数据库的机制将远端数据变为本地缓存数据不仅能够降低平均获取信息的耗时而且通过一定的清退机制也可以维持服务内存占用在安全区间。 本文将会结合实际应用场景阐述引入LruCache的原因并会在高QPS下的挑战与解决方案等方面做详细深入的介绍希望能对DSP感兴趣的同学有所启发。 LruCache简介 LruCache采用的缓存算法为LRU(Least Recently Used)即最近最少使用算法。这一算法的核心思想是当缓存数据达到预设上限后会优先淘汰近期最少使用的缓存对象。 LruCache内部维护一个双向链表和一个映射表。链表按照使用顺序存储缓存数据越早使用的数据越靠近链表尾部越晚使用的数据越靠近链表头部映射表通过Key-Value结构提供高效的查找操作通过键值可以判断某一数据是否缓存如果缓存直接获取缓存数据所属的链表节点进一步获取缓存数据。LruCache结构图如下所示上半部分是双向链表下半部分是映射表不一定有序。双向链表中value_1所处位置为链表头部value_N所处位置为链表尾部。 LruCache读操作通过键值在映射表中查找缓存数据是否存在。如果数据存在则将缓存数据所处节点从链表中当前位置取出移动到链表头部如果不存在则返回查找失败等待新数据写入。下图为通过LruCache查找key_2后LruCache结构的变化。 LruCache没有达到预设上限情况下的写操作直接将缓存数据加入到链表头部同时将缓存数据键值与缓存数据所处的双链表节点作为键值对插入到映射表中。下图是LruCache预设上限大于N时将数据M写入后的数据结构。 LruCache达到预设上限情况下的写操作首先将链表尾部的缓存数据在映射表中的键值对删除并删除链表尾部数据再将新的数据正常写入到缓存中。下图是LruCache预设上限为N时将数据M写入后的数据结构。 线程安全的LruCache在读写操作中全部使用锁做临界区保护确保缓存使用是线程安全的。 LruCache在美团DSP系统的应用场景 在美团DSP系统中广泛应用键值存储数据库例如使用Redis存储广告信息服务可以通过广告ID获取广告信息。每次请求都从远端的键值存储数据库中获取广告信息请求耗时非常长。随着业务发展QPS呈现巨大的增长趋势在这种高并发的应用场景下将广告信息从远端键值存储数据库中迁移到本地以减少查询耗时是常见解决方案。另外服务本身的内存占用要稳定在一个安全的区间内。面对持续增长的广告信息引入LruCache 键值存储数据库的机制来达到提高系统性能维持内存占用安全、稳定的目标。 LruCache Redis机制的应用演进 在实际应用中LruCache Redis机制实践分别经历了引入LruCache、LruCache增加时效清退机制、HashLruCache满足高QPS应用场景以及零拷贝机制四个阶段。各阶段的测试机器是16核16G机器。 演进一引入LruCache提高美团DSP系统性能 在较低QPS环境下直接请求Redis获取广告信息可以满足场景需求。但是随着单机QPS的增加直接请求Redis获取广告信息耗时也会增加无法满足业务场景的需求。 引入LruCache将远端存放于Redis的信息本地化存储。LruCache可以预设缓存上限这个上限可以根据服务所在机器内存与服务本身内存占用来确定确保增加LruCache后服务本身内存占用在安全范围内同时可以根据查询操作统计缓存数据在实际使用中的命中率。 下图是增加LruCache结构前后且增加LruCache后命中率高于95%的情况下针对持续增长的QPS得出的数据获取平均耗时(ms)对比图 根据平均耗时图显示可以得出结论 QPS高于250后直接请求Redis获取数据的平均耗时达到10ms以上完全无法满足使用的需求。增加LruCache结构后耗时下降一个量级。从平均耗时角度看QPS不高于500的情况下耗时低于2ms。下图是增加LruCache结构前后且增加LruCache后命中率高于95%的情况下针对持续增长的QPS得出的数据获取Top999耗时(ms)对比图 根据Top999耗时图可以得出以下结论 增加LruCache结构后Top999耗时比平均耗时增长一个数量级。即使是较低的QPS下使用LruCache结构的Top999耗时也是比较高的。引入LruCache结构在实际使用中在一定的QPS范围内确实可以有效减少数据获取的耗时。但是QPS超出一定范围后平均耗时和Top999耗时都很高。所以LruCache在更高的QPS下性能还需要进一步优化。 演进二LruCache增加时效清退机制 在业务场景中Redis中的广告数据有可能做修改。服务本身作为数据的使用方无法感知到数据源的变化。当缓存的命中率较高或者部分数据在较长时间内多次命中可能出现数据失效的情况。即数据源发生了变化但服务无法及时更新数据。针对这一业务场景增加了时效清退机制。 时效清退机制的组成部分有三点设置缓存数据过期时间缓存数据单元增加时间戳以及查询中的时效性判断。缓存数据单元将数据进入LruCache的时间戳与数据一起缓存下来。缓存过期时间表示缓存单元缓存的时间上限。查询中的时效性判断表示查询时的时间戳与缓存时间戳的差值超过缓存过期时间则强制将此数据清空重新请求Redis获取数据做缓存。 在查询中做时效性判断可以最低程度的减少时效判断对服务的中断。当LruCache预设上限较低时定期做全量数据清理对于服务本身影响较小。但如果LruCache的预设上限非常高则一次全量数据清理耗时可能达到秒级甚至分钟级将严重阻断服务本身的运行。所以将时效性判断加入到查询中只对单一的缓存单元做时效性判断在服务性能和数据有效性之间做了折中满足业务需求。 演进三高QPS下HashLruCache的应用 LruCache引入美团DSP系统后在一段时间内较好地支持了业务的发展。随着业务的迭代单机QPS持续上升。在更高QPS下LruCache的查询耗时有了明显的提高逐渐无法适应低平响的业务场景。在这种情况下引入了HashLruCache机制以解决这个问题。 LruCache在高QPS下的耗时增加原因分析 线程安全的LruCache中有锁的存在。每次读写操作之前都有加锁操作完成读写操作之后还有解锁操作。在低QPS下锁竞争的耗时基本可以忽略但是在高QPS下大量的时间消耗在了等待锁的操作上导致耗时增长。 HashLruCache适应高QPS场景 针对大量的同步等待操作导致耗时增加的情况解决方案就是尽量减小临界区。引入Hash机制对全量数据做分片处理在原有LruCache的基础上形成HashLruCache以降低查询耗时。 HashLruCache引入某种哈希算法将缓存数据分散到N个LruCache上。最简单的哈希算法即使用取模算法将广告信息按照其ID取模分散到N个LruCache上。查询时也按照相同的哈希算法先获取数据可能存在的分片然后再去对应的分片上查询数据。这样可以增加LruCache的读写操作的并行度减小同步等待的耗时。 下图是使用16分片的HashLruCache结构前后且命中率高于95%的情况下针对持续增长的QPS得出的数据获取平均耗时(ms)对比图 根据平均耗时图可以得出以下结论 使用HashLruCache后平均耗时减少将近一半效果比较明显。对比不使用HashLruCache的平均耗时可以发现使用HashLruCache的平均耗时对QPS的增长不敏感没有明显增长。下图是使用16分片的HashLruCache结构前后且命中率高于95%的情况下针对持续增长的QPS得出的数据获取Top999耗时(ms)对比图 根据Top999耗时图可以得出以下结论 使用HashLruCache后Top999耗时减少为未使用时的三分之一左右效果非常明显。使用HashLruCache的Top999耗时随QPS增长明显比不使用的情况慢相对来说对QPS的增长敏感度更低。引入HashLruCache结构后在实际使用中平均耗时和Top999耗时都有非常明显的下降效果非常显著。 HashLruCache分片数量确定 根据以上分析进一步提高HashLruCache性能的一个方法是确定最合理的分片数量增加足够的并行度减少同步等待消耗。所以分片数量可以与CPU数量一致。由于超线程技术的使用可以将分片数量进一步提高增加并行性。 下图是使用HashLruCache机制后命中率高于95%不同分片数量在不同QPS下得出的数据获取平均耗时(ms)对比图 平均耗时图显示在较高的QPS下平均耗时并没有随着分片数量的增加而有明显的减少基本维持稳定的状态。 下图是使用HashLruCache机制后命中率高于95%不同分片数量在不同QPS下得出的数据获取Top999耗时(ms)对比图 Top999耗时图显示QPS为750时分片数量从8增长到16再增长到24时Top999耗时有一定的下降并不显著QPS为1000时分片数量从8增长到16有明显下降但是从16增长到24时基本维持了稳定状态。明显与实际使用的机器CPU数量有较强的相关性。 HashLruCache机制在实际使用中可以根据机器性能并结合实际场景的QPS来调节分片数量以达到最好的性能。 演进四零拷贝机制 线程安全的LruCache内部维护一套数据。对外提供数据时将对应的数据完整拷贝一份提供给调用方使用。如果存放结构简单的数据拷贝操作的代价非常小这一机制不会成为性能瓶颈。但是美团DSP系统的应用场景中LruCache中存放的数据结构非常复杂单次的拷贝操作代价很大导致这一机制变成了性能瓶颈。 理想的情况是LruCache对外仅仅提供数据地址即数据指针。使用方在业务需要使用的地方通过数据指针获取数据。这样可以将复杂的数据拷贝操作变为简单的地址拷贝大量减少拷贝操作的性能消耗即数据的零拷贝机制。直接的零拷贝机制存在安全隐患即由于LruCache中的时效清退机制可能会出现某一数据已经过期被删除但是使用方仍然通过持有失效的数据指针来获取该数据。 进一步分析可以确定以上问题的核心是存放于LruCache的数据生命周期对于使用方不透明。解决这一问题的方案是为LruCache中存放的数据添加原子变量的引用计数。使用原子变量不仅确保了引用计数的线程安全使得各个线程读取的引用计数一致同时保证了并发状态最小的同步性能开销。不论是LruCache中还是使用方每次获取数据指针时即将引用计数加1同理不再持有数据指针时引用计数减1。当引用计数为0时说明数据没有被任何使用方使用且数据已经过期从LruCache中被删除。这时删除数据的操作是安全的。 下图是使零拷贝机制后命中率高于95%不同QPS下得出的数据获取平均耗时(ms)对比图 平均耗时图显示使用零拷贝机制后平均耗时下降幅度超过60%效果非常显著。 下图是使零拷贝机制后命中率高于95%不同QPS下得出的数据获取Top999耗时(ms)对比图 根据Top999耗时图可以得出以下结论 使用零拷贝后Top999耗时降幅将近50%效果非常明显。在高QPS下使用零拷贝机制的Top999耗时随QPS增长明显比不使用的情况慢相对来说对QPS的增长敏感度更低。引入零拷贝机制后通过拷贝指针替换拷贝数据大量降低了获取复杂业务数据的耗时同时将临界区减小到最小。线程安全的原子变量自增与自减操作目前在多个基础库中都有实现例如C11就提供了内置的整型原子变量实现线程安全的自增与自减操作。 在HashLruCache中引入零拷贝机制可以进一步有效降低平均耗时和Top999耗时且在高QPS下对于稳定Top999耗时有非常好的效果。 总结 下图是一系列优化措施前后命中率高于95%不同QPS下得出的数据获取平均耗时(ms)对比图 平均耗时图显示优化后的平均耗时仅为优化前的20%以内性能提升非常明显。优化后平均耗时对于QPS的增长敏感度更低更好的支持了高QPS的业务场景。 下图是一系列优化措施前后命中率高于95%不同QPS下得出的数据获取Top999耗时(ms)对比图 Top999耗时图显示优化后的Top999耗时仅为优化前的20%以内对于长尾请求的耗时有非常明显的降低。 LruCache是一个非常常见的数据结构。在美团DSP的高QPS业务场景下发挥了重要的作用。为了符合业务需要在原本的清退机制外补充了时效性强制清退机制。随着业务的发展针对更高QPS的业务场景使用HashLruCache机制降低缓存的查询耗时。针对不同的具体场景在不同的QPS下不断尝试更合理的分片数量不断提高HashLruCache的查询性能。通过引用计数的方案在HashLruCache中引入零拷贝机制进一步大幅降低平均耗时和Top999耗时更好的服务于业务场景的发展。 作者简介 王粲2018年11月加入美团任职美团高级工程师负责美团DSP系统后端基础架构的研发工作。崔涛2015年6月加入美团任职资深广告技术专家期间一手指导并从0到1搭建美团DSP投放平台具备丰富的大规模计算引擎的开发和性能优化经验。霜霜2015年6月加入美团任职美团高级工程师美团DSP系统后端基础架构与机器学习架构负责人全面负责DSP业务广告召回和排序服务的架构设计与优化。招聘 美团在线营销DSP团队诚招工程、算法、数据等各方向精英发送简历至cuitaomeituan.com共同支持百亿级流量的高可靠系统研发与优化。
