(OSDI '20) 大规模键值存储系统的负载特性分析

2020/11/13 Storage

主要讨论osdi 20一篇来自Twitter和CMU的工业界大规模键值存储负载特性的工作[1]。在这之前12年有一篇来自facebook的类似负载特性工作[3]。这篇博客讲讲这两篇工作。

OSDI 20在11月初开完了,菜鸡看不到线上会议。。。感谢交大IPADS的OSDI一手分享[2]。

Workload analysis of a large-scale key-value store

facebook那篇[3]是分析内部memcached集群的280 billion请求的。

read/write ratio

统计中,分出了五种不同特征的负载(数据来自相同性能的memcached实例)。

  • USR 用户状态
  • APP 应用元数据
  • ETC 通用的缓存,也是最大的池
  • VAR 服务端浏览器
  • SYS 服务位置上的系统数据

不同池子有不同的访问负载特性,如下图 image.png

  • USR,因为是存状态,很少更新,99.8%都是读(像是个适合持久化的好兑现)。是个按需填充的,所以当发生了未命中才会有写操作。
  • APP,DELETE数量比较多。数据来源一般是数据库的缓存,当数据库条目被删除的时候,引发的缓存删除。
  • ETC,类似于APP,但是DELETE高一些。这是一个最大、且异构的池子,是本文重点。读写比例为30:1,高于通常的假设。
  • VAR,以写为主,存的都是很短期的数据,如浏览器的窗口大小等。

Key value size

image.png

如图三个CDF展示键值数据的大小分布,可以看到值在500B以下的数据占了90%。SYS类别里大部分都是320B以上的值(92%)。【by total weight指的是通过访问数量加权的】

在除了ETC以外的池上,特征比较明显,如APP的都是小key,USR的key长只有两种。
在ETC上,有1MB的大value,也有占总请求数目40%的11B小请求。

大量的小请求会引发1.网络开销占主导,2.内存碎片。
因此batching,slab的优化效果会非常明显。

话说memcached只支持key最大到250B,大key的数据会不会影响数据采样呢?

temporal pattern (时间模式

高峰出现在欧洲和北美的白天。

cache behavior

image.png

image.png 比较明显的特征就是USR的命中率随着时间而上升,因为在启动后,通过PUT逐渐提升USR池的命中率。

locality

image.png

ETC池里有50%的key只出现一次。而有的key能出现百万次,就很适合优先缓存下来。除了SYS以外,其他曲线都比较类似。作者认为SYS第一次转折是因为启动导致的,后面的曲线才是正常的SYS场景。

image.png SYS的不重复key只有3.3%,而USR则高达34.6%

对比上下两图,可以发现大多数的key一小时内,被访问概率是快速下降的,通常这能够导致更高的整体命中率。在键的重用周期统计的实验部分,这个下降的时间可以长到300+h。ETC池的重复key,从一小时的88.5%下降到4%。

image.png

通过对ETC的命中率的研究,发现ETC的命中率即使在很大的RAM上也只能达到80%。其中大部分miss来自访问超过10天前的数据。
因为1%的访问到了50%的数据,demand-filled cache基本无意义。

statical modeling

image.png

inter-arrival gap(两次到达的间隔)和key大小、value大小,三个属性互相都不相关。
然后分别对这三个属性做模型拟合建模,具体见原文。

ETC基本符合Zipf’s law

通过测量miss GET和恢复该值的后续SET过程的开销来估算miss的开销。这个开销和值大小成正比。因此字节命中率这个指标并不重要,而应该关注命中率(较小的值更重要)。

文章后面说,“替换策略、分配策略都大有文章可做。可以研究动态slab或slab-free的分配方法”,slab除了元数据管理开销比较大,有啥缺点呢?


A large scale analysis of hundreds of in-memory cache clusters at Twitter

采集了twitter 153个集群超过80TB的数据,通过twitter魔改的memcached和redis。

[1]给了三个用途分类

  • storage,当database用的
    • 读为主,cache命中率很高,α of zipf很大
  • compute,计算的中间结果,具体特征取决不同类型的计算
    • ML类型的都是读为主,很符合zipf
    • mapreduce等需要存中间值的,就会写为主,比较偏离zipf,TTL更短
  • cache,短时的cache

read/write ratio

image.png

在>35%的集群上都是写密集的(>30%)【常见于compute场景中】。

这个指标比facebook ETC负载要高很多

object size

image.png

在键值大小上,24%的集群的平均对象大小小于100字节,中位数在230字节。
另外因为memcached就用了56字节做元数据,这很影响缓存的命中率。

image.png

文章还探讨了键和值的比例关系。15%的集群上键的大小大于值,50%的集群上5*键的大小大于值。
原因是因为很多应用在使用键时,命名空间(前缀)占得部分很长。如ns1:ns2:obj。

所以以后可以做key压缩。所以整个unique id还是有必要的

image.png

同时访问的大小并不是静态的。上面的热度图展示了object size随着时间的变化而变化的情况。导致这个现象的原因有很多,比如同key的value随着时间增长,或访问受时差访问之类的影响。

这样的问题会对内存分配系统造成挑战,很难预测未来大小解决碎片化问题。
slab分配也会遇到slab钙化的问题。

TTL

image.png

大部分数据的TTL都很短,大部分数据小于48h。所以设计一个好的清理过期数据的方法很重要,甚至很多系统上,这比缓存替换更重要。

这点和上一篇差不多,cold-hot分级存储启动

popularity (locality)

基本符合zipf。一个小 区别在于最热的数据不会zipf那么热,最冷的数据比zipf更冷。

这里原文说facebook那篇说负载不符合zipf。明显没看仔细,那篇文章说的是一些强特征的池不符合而已,ETC还是很符合的。

cache evict

LRU除了在cache非常小的情况下,效果和FIFO很接近。系统就更注重简单、不会引起碎片问题的替换算法。

实验选择的替换算法很少,就是不同粒度的LRU和FIFO

others

image.png

读写比例和TTL、Zipf参数等指标相关性很强。如更高的写比例,一般就会有更短的TTL。
影响效果如下图所示 image.png

ref

  1. Yang, Juncheng, Yao Yue, and K. V. Rashmi. “A large scale analysis of hundreds of in-memory cache clusters at Twitter.” Proceedings of the 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI’20), Banff, AL, Canada. 2020.
  2. OSDI2020——SJTU-IPADS的“云见闻”(一)
  3. Atikoglu, Berk, et al. “Workload analysis of a large-scale key-value store.” Proceedings of the 12th ACM SIGMETRICS/PERFORMANCE joint international conference on Measurement and Modeling of Computer Systems. 2012.

Search

    Table of Contents