Cache

为了实现多机架的负载均衡cache，提出两个idea。 一是多层的cache，每一层用不同的hash函数，即不同的划分方式。 二是Power of Two Random Choices的路由方法。Power of Two Random Choices的大白话解释是假如顺序地将请求发送到ｎ个服务器，策略是从n个服务器中随机独立均匀地选择两个，然后选择服务器负载最少的处理请求。这样的算法以非常高的概率，n个服务器中最大负载为(1+ｏ(1)) loglogn / log2 + Ｏ(1)个请求。 原始的Power of Two Random Choices和本文不同的地方在于，原始的是随机地找两个服务器，本文是hash到两个指定服务器。 多机架的负载均衡cache，可以很容易想到两种方法，Cache partition和Cache replication，前者是将不同的cache划分在不同的node上面，但这没有解决负载不均衡问题；后者将所有cache都放到不同的cache node上，这有一致性的开销和存储的开销。 下面层的cache node只负责cache自己服务器上的hot items，上面层用了不一样的hash function，相当于将下面层每个cache node的item都分散开来。然后对一个key上下两层会各有一个cache node，这时选负载最低的cache node响应请求。 文章把问题看成一个找完美匹配的问题，用了一些图论，排队论的知识去证明这个power of two choices可以实现，无论请求的分布如何，总的吞吐量都接近全部机器的最大吞吐量总和（也就是实现负载均衡）。其中一些截图没有解释的变量：m是cluster数量，p_i是i对象的请求概率，R是总的响应量，波浪T是一个cluster的最大吞吐量，P是所有的p_i。 其他的内容就和NetCache差不多，不同的主要在缓存一致性上面。怎么同时原子更新不同cache node上的缓存？文章的解决方法是two-phase update protocol，收到写请求时先无效化所有缓存，storage server让一个无效化的数据包传遍所有cache node最后回到storage server。最后传一个数据包更新cache。 cache的更新则用的是NetCache的HH detector的监测方法，但有些不同在于本文用一种不需要controller的方法。Specifically, the agent first inserts the new object into the cache, but marks it as invalid. Then the agent notifies the server; the server updates the cached object in the data plane using phase 2 of cache coherence, and serializes this operation with other write queries....

idea是用可编程交换机去做服务器in-memory KV的缓存。KV的workload是偏差很大的，容易造成负载不均衡，和其他方法相比，可编程交换机比内存快几个数量级，而且数据移动，一致性等要比在存储节点上做replication更好。 文章提出的不是一个高命中率的cache，它主要作用是load balancing，命中率只有不到50%，只保存O(NlogN)的个item。文章假设服务器是per-core sharding，缓存一致性不用考虑NUMA架构，只是写直通。也不考虑是否需要鉴权，就只考虑负载均衡cache这一件事。 整体架构如下，NetCache协议在L4数据包里面。 处理请求的流程。 可编程交换机的数据面是一个pipeline，每个pipe有多个ingress/egress ports和中间不同的stage，每个stage有自己的计算资源，stage之间也可以共享数据。数据包的处理可以抽象成match-action table，每个table检查header的字段，根据match的结果执行一些action。 通过可编程交换机保存cache的方式如下，首先一个lookup table保存所有的item元信息，通过bitmap来记录哪个stage的table上有数据，以及数据在什么index上。通过switch data plane更新值带来一个限制，它不能比旧值的数据更长，这是因为其他stage的同一个index可能已经放了别的数据。 而怎么选择cache应该放在哪里，可以看成背包问题，文章用的是first-fit，外加周期性的memory reorganization（这部分没有明说）。 有一个对每个key的counter和heavy-hitter detector的机制去决定缓存什么item，每次更新cache时，sample一些key的counter，与未cache的访问最多的key的访问次数比较，从而决定要不要更新。对于未cache的key，用的是Count-Min Sketch算法。而后面的bloom filter的作用应该是过滤掉已经report的key，在cache成功后应该会把它对应的位复原。 stage的放置也是有讲究的，lookup table要放在ingress pipe，每个pipe上都要有备份，这样可以处理所有ingress端口的请求；cache value要放在egress pipe，可以把属于不同server的内容放在它所对应的egress端口所在的pipe上。 这个系统也还是有一定缺陷： 目前是单机架的； key和value目前是限长的； 对写入占多数的workload不友好。