NetCache -- Balancing Key-Value Stores with Fast In-Network Caching

NetCache: Balancing Key-Value Stores with Fast In-Network Caching

0x00 引言

这篇Paper和之前的NetChain都是类似的工作，这个NetCache发表在SOSP 2017上面。提出了一种新的KVS的架构(a new rack-scale key-value store architecture that leverages in-network caching to provide dynamic load balancing across all storage servers，注意它的范围是在一个rack的范围内)，主要的内容就是如何利用可编程的交换机来实现KVS的负载均衡，

We implement a NetCache prototype on Barefoot Tofino switches and commodity servers and demonstrate that a single switch can process 2+ billion queries per second for 64K items with 16-byte keys and 128-byte values, while only consuming a small portion of its hardware resources. ... . Furthermore, we show that NetCache improves the throughput by 3-10x and reduces the latency of up to 40% of queries by 50%, for high-performance, in-memory key-value stores.

0x01 基本思路

NetCache的基本思路就是利用交换机本身作为KVS的Cache。对于负载均衡的情况，现在的一些理论依据证明了：对于N台的主机，只需要缓存O (N log N )个数据想就可以满足要做，而且不论Key/Vale Pair具体的数量是多少。对于交换机作为缓存，现在的交换机有了很多的编程的功能，而且也有不少的片山的内存。NetCache一个基本的架构如下，它主要由下面几个部分组成：

交换机，NetCache就是为如何利用现在的可编程的交换机存在的。所以交换机当然是器最核心的一个部分。它复杂Cache数据项、处理 L2/L3 层协议。它的Cache模块就负责Cache热点数据，对于命中的读请求，可以直接通过交换机就处理了；对于写入请求，为了减少相同的复杂度，它使用的是write-through的方式。查询统计模块就是为了给出查询的一些统计信息，为了从其中挑选出热点的数据。主要包括了2个部分：1 对于已经Cached的数据的每一个的计数器，2. 一个使用 Count-Min sketch实现的计数器。
控制器，控制器负责更新Cache的数据项。它接受来自heavy-hitter(HH)的数据报告来决定Cache的行为。
存储服务器，主要就是两个功能：1. 映射NetCache的查询数据包到KVS的API；2. 实现一个缓存连贯性协议来保证数据的一致性；
客户端，就是KVS的使用者。

netcache-arch

0x02 设计

NetCahe的设计中主要包括了网络协议的设计、查询处理、缓存连贯性与缓存更新、交换机数据面设计等部分。

网络协议，上面图的(b)子图是NetCache的一个包的结构，它使用UDP作为读取请求的数据包，而使用TCP作为写入的数据包。这个和一些KVS的设计也是一致的，

 The major header fields for NetCache are OP, SEQ, KEY and VALUE. OP stands for operator and denotes whether it is a Get, Put, Delete or any other type of query. SEQ can be used as a sequence number for reliable transmissions by UDP Get queries, and as a value version number by TCP Put and Delete queries.

路由，NetCache的路由方案采用的既有的解决方法。

查询处理，NetCache一个查询处理的伪代码实例，基本的处理逻辑在伪代码中已经表现得比较清楚了，

– cache: on-chip key-value cache
– stats: on-chip query statistics 
if pkt.op== Get then
  if cache.hit(pkt.key) and cache[pkt.key].valid() then 
    add pkt.value header
    pkt.value <- cache[pkt.key] 
    stats.cache_count(pkt.key)
  else
    stats.heavy_hitter_count(pkt.key) 
    if stats.is_hot_key(pkt.key) then
       inform controller for potential cache updates 
else if pkt.op == Put or pkt.op == Delete then
   if cache.hit(pkt.key) then cache.invalidate(pkt.key)
Update packet header and forward

缓存连贯性与缓存更新，使用write-through的方式使得Cache coherence的实现变得简单，这样的处理机制也是NetCache一个机架规模的解决方案的一个原因。缓存的更新的决定是控制器来做的，控制器如下面所言依赖于交换机提供的统计信息。另外缓存更新的时候cache coherence也要处理，
```
 To guarantee cache coherence during cache updates, when the controller is inserting a key to the cache, write queries to this key are blocked at the storage servers until the insertion is fnished, which is the same as handling write queries to cached items. 
```

Switch Data Plane Design

交换机的数据面是NetCache的一个核心内容。它主要包括了三个组件：ingress pipeline, trac manager, 和 egress pipeline，主要直线下面这几个功能，

片上的KVS；NetCache利用可编程交换机的stateful memory来保存数据项，

netcache-dataplane

查询统计；如前面所言，查询统计主要包括了每一个Cached的像的访问统计信息，一个Count-Min sketch用来探查热点数据项，另外一个Bloom Filter来移除重复的key的报告。这些统计信息会定期地被控制器清空。
流水线处理；NetCache的处理方式是流行线化的，基本的思路如下面的图，

netcache-logical

0x03 一些问题

多机架，NetCache利用来存储服务器之间连接的ToR交换机的特点简化了系统的设计，如果要支持多机架的话，系统会复杂很多，

... This requires us to cache hot items to higher-level switches in a datacenter network, e.g., spine switches. Ideally, we would like to provide a “one big memory” abstraction where the on-chip memories of all switches work as a single big cache. We need to carefully design a cache allocation mechanism to minimize routing detours and maximize switch memory utilization, as well as a cache coherence mechanism to en- sure cache coherence with multiple switch caches. A full exploration is our future work.

收限制的KVS接口，目前的接口只支持key大小固定为为16字节，value最大的128字节；
写密集的负载，在写密集的负载表现可能一般。直接由交换机处理写热点是一个解决方案，不过又会引入其它的问题；
…..[1]

0x04 评估

这里具体信息可以参看[1]

netcache-perf

参考

Xin Jin, Xiaozhou Li, Haoyu Zhang, Robert Soulé, Jeongkeun Lee, Nate Foster, Changhoon Kim, Ion Stoica. 2017. NetCache: Balancing Key-Value Stores with Fast In-Network Caching. In Proceedings of SOSP ’17, Shanghai, China, October 28, 2017, 17 pages. https://doi.org/10.1145/3132747.3132764.