1. 介绍
对于通常的互联网应用来说，read、write比例通常在8:2，所以提升read的性能是至关重要的，通常的做法是采用更快的介质作为更慢介质的Cache，在计算机系统中Cache的应用非常常见，例如：CPU有L1、L2、L3级缓存作为内存的Cache，文件系统有Page Cache，使用内存作为磁盘的Cache，LevelDB/RocksDB也在内存中维护了一个LRU Cache缓存热点的key-value，一些混合型存储中，使用SSD作为HDD的Cache；Memcached/Redis这两种基于内存的key-value存储也被广泛的被应用在缓存系统中。对于单机的Cache系统来说，通常提升Cache命中率是关键，一般通过LRU实现缓存淘汰可以做到不错的Cache命中率。而对于大规模的存储系统来说，Cache也是分布式，如何做到Cache的负载均衡将会是关键。本文将向大家介绍fast2019 best paper ——Distcache[1]提出解决的方案，其主要解决的是Large-Scale（multiple clusters ）存储系统的负载不均衡的问题。
2. Distcache
2.1. 场景
对于存储系统来说，通常基于元数据管理架构，例如GFS、HDFS等一般都容易做到容量的均衡，但是一般都很难做到负载的均衡，尤其是对于一些应用场景来说，会存在一些hot数据，而且这些hot数据是动态变化，因此造成storage server之间负载不均衡（skewness of the workload ），如下图，是文献[2]统计的一种典型的key-value存储的负载情况：
实际上，对于Large-Sacle（multiple clusters ）来说，每个cluster的负载也是不均衡的，如下图：
为了解决不同cluster之间的负载均衡问题，通常的做法会使用两层Cache，如下图，其中Lower-layer的Cache作为intra-cluster（单个cluster内部）的负载均衡，Upper-layer作为inter-cluster（多个cluster之间）的负载均衡；
（注意上图的圆圈表示一个Cache，其可以是多个Cache node组成的，并不是表示其就是一个Cache node）
2.2. Idea
两层Cache想解决的问题很明确，就是利用第二层Cache（也就是Upper-layer Cache）来实现inter-cluster之间的负载均衡，其面临的主要有三个问题：
1）How to allocate cached items?
解决的是将hot item放在哪个Cache node问题，DistCache的idea很简单，就是Cache allocation with independent hash functions， 每一层Cache使用不能的hash function来实现hot item到Cache node的映射，这样可以保证如果在层的Cache（Lower-layer）存在hot skewness的cluster数据会在第二层（Upper-layer）Cache被新的hash function打散。
这样做的好处，简单，可以容易实现，维护Cache一致性也容易，而且理论效果会很好。
2）How to query the cached items?
如何查询，DistCache的思路也很简单，也就是会根据hash function找到这个hot item分别所在的Upper-layer和Lower-layer Cache node，然后选择负载较轻的Cache node进行查询。这样做尽管会有两个rtt，但是其不依赖任何中心节点，扩展性很好
3）How to update the cached items?
同一个item可能会出现在多个Cache node上，显然的Upper-layer和Lower-layer上都会有同一个item，那么如何原子的update一个item是保证Cache一致性的关键。使用的是two-phase update protocol更新协议，本质上和普通的Cache update思路是一致的，也就是update之前，先将所有的Cache node上的cache item标记为，然后在更新server node上的数据，后再更新Cache node数据，这样保证在read/update的时候能够保证一致。详细不在赘述，可以参考论文相关章节。
2.3. App
为了证明DistCache的有效，文章实现了一种Switch-Based Caching，利用Programmable switches，将两层Cache都做在Switch上面，下面给一个Cache hit的例子，如下图，Get(A)的顺序是从Client Racks R3，到Switch S6，然后到下一层Switch（Upper-layer Cache），S1和S0，其中S1命中，S0转发到下一层Switch S3（Lower layer），命中。
3. 总结
fast2019的best paper？what ? 感觉有点水，尤其是在背景和motivation描述了两种通常解决方案Cache partition和Cache replication的时候，感觉有点扯了，完全是拍脑袋找的场景，可能是为了迎合文章内那段建模分析，提升一定的理论高度把，不过没细看，总之离实际工程应用比较远。以上言论纯属扯淡，看看就好，无奈看了，所以也就稍微整理在这里分享给大家，但不见得有什么帮助。
Notes
限于作者水平，难免在理解和描述上有疏漏或者错误的地方，欢迎共同交流；部分参考已经在正文和参考文献列表中注明，但仍有可能有疏漏的地方，有任何侵权或者不明确的地方，欢迎指出，必定及时更正或者删除；文章供于学习交流，转载注明出处
参考
[1]. Liu Z, Bai Z, Liu Z, et al. Distcache: Provable load balancing for large-scale storage systems with distributed caching[C]//17th {USENIX} Conference on File and Storage Technologies ({FAST} 19). 2019: 143-157.
[2]. Atikoglu B, Xu Y, Frachtenberg E, et al. Workload analysis of a large-scale key-value store[C]//ACM SIGMETRICS Performance Evaluation Review. ACM, 2012, 40(1): 53-64.
