[TOC]

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

NetCache:利用快速网内缓存平衡键值存储系统

出处：SOSP2017

作者：Xin Jin, Xiaozhou Li, Haoyu Zhang, Robert Soulé, Jeongkeun Lee,
Nate Foster, Changhoon Kim, Ion Stoica

单位：Johns Hopkins University, Barefoot Networks, Princeton University,
Cornell University, UC Berkeley

Concept

1.key-value 数据库

• Key-Value键值存储原理初识(NOSQL)
• Key-value数据库比关系型数据库更加新吗？
• 自己动手构建Key-Value Store系统
• key-value store
• Key-value存储简介
• Key-value数据库比关系型数据库更加新吗？
• Relational DB vs. Key-Value store

2.in-memory 数据库

• 内存数据库 (in-memory database) 的发展现状和前景如何？
• 内存数据库
• 内存数据库优劣势有那些？

3.ASIC（Application Specific Integrated Circuits）是专用集成电路，指应特定用户要求和特定电子系统的需要而设计、制造的集成电路，里面的电路结构式固定不可变的。文中提到的Barefoot Tofino和Broadcom Tomahawk都是内置这种电路芯片的交换机，可以高速处理网络数据。

4.Cache写操作策略

由于Cache的内容只是主存内容的一个子集，应当与主存内容保持一致，而CPU对Cache的写入更改了Cache的内容。为此，可选用写操作策略使Cache内容与主存内容保持一致。

• 写回法（Write-Back），当CPU写Cache命中时，只修改Cache的内容，而不是立即写入主存；只有当此块被换出时才写回主存。使用这种方法写Cache和写主存异步进行，显著减少了访问主存的次数，但是存在数据不一致的隐患。实现这种方法时，每个Cache块必须配置一个修改位，以反映此块是否被CPU修改过。
• 全写法（Write-Through），当写 Cache命中时，Cache与主存同时发生写修改。使用这种方法写Cache和写主存同步进行，因而较好地维护了Cache与主存的内容一致性。实现这种方法时，Cache中的每个块无需设置修改位以及相应的判断逻辑，但由于Cache对CPU向主存的写操作没有高速缓冲功能，从而降低了Cache的功效。
• 写一次法（Write-Once），写一次法是基于写回法并结合全写法的写操作策略，写命中与写未命中的处理方法与写回法基本相同，只是第一次写命中时要同时写入主存，以便于维护系统全部Cache的一致性。

Abstract

• 主题：NetCache，一种新型的键值存储结构。
• 作用：利用新一代可编程交换机的灵活性、可编程性处理热点数据条目的查询，同时平衡存储结点间的负载。
• 效果：1）NetCache即使在高偏斜(负载极度不均)和快速变化的工作负载下依然能同时提供高吞吐量和低延迟的服务。2）同时该解决方案以最低的开销保证了cache的一致性。
• 核心：NetCache的核心是一个分组处理管道，它利用了现代可编程交换机的功能实现了高效地检测、索引和处理交换机数据区域内的热数据对。
• 实验：在Barefoot Tofino交换机以及商用服务器上实现了NetCache的原型，实验证明单个交换机能处理每秒2亿多的查询(每个条目64K，16byte键，128byte值？？？) ，同时仅消耗很小一部分的硬件资源。
• 意义：网内缓存的应用层研究方面，这是首次在可编程交换机上以线性比率运行如此复杂的应用层功能。(？？？run at line rate ？？)，而且NetCache提高了3到10倍的吞吐量，同时减少40%到50%的查询延时。

Introduction

1.技术背景

现代的网络服务对高性能的键值存储（[key-value store](key-value store)，key_value分布式存储系统）非常依赖，甚至往往一个web页面都需要成百上千次存储器访问，故当用户量很大时，急剧上升的操作需要依赖内存键值存储来满足吞吐量和延时需求。

ps:简单说，就是访问量太大，不能再直接访问存储设备，改用内存缓存的方法解决

2.技术难点

不论是内存缓存还是存储器结点做键值数据对的存储，都有一个主要的难题，就是处理偏斜、动态的工作负载。热条目的查询次数往往比其他条目要多得多，但“热条目”的集合又会快速变化（时下热点、趋势、内容提供方的时限等因素）。根据对facebook的Memcached deployment研究显示10%的条目占据了60%到90%的查询量。这种偏斜（skew）导致系统负载不均衡，造成系统性能退化，吞吐量下降，响应时间变慢。当服务器采用（per-core sharding，每核心分片）技术处理高并发访问时，以上性能退化问题会被进一步放大。

对于高性能的内存数据对存储，工作负载不均问题尤为急切。传统的闪存或磁盘存储器可以通过快速内存缓存层来平衡工作负载（在数据的实际存储设备之上添加一层缓存层，nvram + memory形式）。或者，采用选择性副本机制，比如将热数据条目拷贝到一个额外附加的存储结点上，但是这种副本机制需要额外的硬件开销，同时需要复杂的机制来处理数据的移动、一致性、查询路由等问题，造成系统设计的复杂性，提高系统开销。（比如一种简单处理方法，查询的时候先查这个存储结点就可以了，命中率会高很多，但是这个结点的负载非常高，对该结点硬件要求很高，整个系统的性能会受到这个结点的影响——类似于“短板效应”）

ps:技术难点：1）in-memory和NVRAM存储都会存在偏斜、动态负载造成系统性能退化，降低吞吐量，增加延时的问题。2）针对NVRAM存在两种解决方案，a）增加cache层，或者b）采用副本机制。前者in-memory存储不适用，后者存在附加的问题。

4.本文解决方案

本文提出NetCache，一种新型的存储架构，利用新一代可编程交换机在网络中缓存数据。交换机在数据流动中被充分利用，相对传统的存储服务器提供了更好的性能，为高性能内存存储提供了一个理想的构建缓冲层的地点(switch)。传统的缓存通常需要很高的缓存命中率（>90%）来承受大部分的查询，NetCache使用交换机作为均衡负载的缓存，仅需要中等的缓存命中率(<50%)。热点数据条目使用负载均衡缓存访问，使得服务器中剩下的负载更加均匀。虽然交换机片内内存有限，NetCache在理论上仅需缓存$O(NlogN)$的条目就足以平衡N个存储服务器（或CPU核心）的工作负载，通过全部的哈希划分的键值存储簇。总的来说，整个系统能保证很高的整体吞吐量和低延时，即使在偏斜工作负载下。

NetCache的核心是一个分组处理管道，它可以检测、索引、存储和查询数据对。使用match-action table(??表)对keys做分类，这些keys由数据包头部携带，可编程交换机的片内内存中存储values。利用现代交换机ASICs的多管线多级结构更加有效得索引和压缩变长的values到有限的交换机表和内存资源中。

为了在交换机的数据区平面区分热点条目，NetCache为每一个缓存了的key维护一个计数器，以及一个未缓存key的热数据检测器（heavy-hitter detector，heavy-hitter，数据流及网络检测研究中的常用术语，在数据流方面，指频繁出现的数据项，在网络监测中，通常认为是发出的数据包超过一定阈值的流）。这里利用了一点，交换机自然得处于数据路径上，介入系统的所有查询。这个热数据检测器包含一个Count-Min sketch算法（统计一个实时的数据流中元素出现的频率，并且随时反应某个元素出现的频率，非精确统计，稍大估计）用于报告热点的但未缓存的keys，和一个布隆过滤器（Bloom filter，可以用于检索一个元素是否在一个集合中，优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率和删除困难,常用来实现数据字典，进行数据的判重）去过滤重复的热数据报告。两种数据结构（counter for cached keys and heavy-hitter detector）都能在交换机的数据区域以线性方式实现，使用最小的资源。热数据检测器避免了在服务器上独立建立部署和管理一个用于计数统计key访问情况的监视组件。

NetCache架构的另一个优势是用很小的开销就能自动保证缓存一致性。对于交换机缓存的条目的读请求可以无需访问存储服务器直接由交换机处理，而缓存条目的写请求，会使所有交换机上存储的该key的副本条目无效，数据存储服务器会自动更新新的value到交换机上（读的时候，直接交换机读，写的时候，不理交换机，在server上更新，然后刷新switches）。因此，控制平面基于缓存计数器和热数据检测报告仅对某些key的插入和删除操作负责。

NetCache是易部署的，它尤为适合当今的rack-scale(机架规模？)存储系统（每个机架rack包含上千个核心，为了更高的性能需求使用每个核心数据分库分表方式。什么情况下使用分布式数据库），仅需要安排一个ToR交换机就能增加NetCache的功能，网络的其他部分不需修改。NetCache完全兼容已有的路由协议和网络功能，我们为客户端提供了一个NetCache的库用于访问key-value存储系统，它使用类似于已有的key-value store的API。我们还为存储服务器提供了一个简单的中介层（shim layer），使得已有的key-value存储系统与NetCache的整合很容易实现。

总的来说，我们做了一下工作：

• 设计了NetCache，一种新的key-value存储架构，利用新一代可编程交换机缓存网络数据用以动态负载均衡。（part 3）
• 设计了一个分组处理管道（packet-processing pipline），能在交换机的数据平面上高效得检测、索引、存储和查询热数据对，同时实现一种保证缓存一致性的机制。（part 4）
• 在Barefoot Tofino交换机和商用服务器上实现了NetCache的原型，仅仅使用了Tofino的很小一部分片内资源，为传统的数据包处理留下足够的资源。（part 6）
• 对NetCache原型做了评估实验，证明NetCache能以直线比率运行在可编程交换机上。并极大提高了性能。（part 7）
• 讨论了系统的局限性和可能的解决方案。（part 5）

ps:这里紧接着之前的描述，传统存储系统和内存数据存储系统都会遇到共同的问题，有两个解决方案，其一不适合in-memory系统，其二本身存在很多问题，接着该部分给出本文的解决方案，NetCache，利用交换机在网络中缓存热数据条目。简要介绍了NetCache的以下几个情况：

• 单个switch满足的命中率要求
• 缓存量，也是资源占用量
• 核心，packet-process pipline
• 组成，cached keys' counter + uncached keys’ heavy-hitter detector（包含两个算法组成，counter-min sketch + bloom filter）
• 一致性策略（写、更改的处理）
• 实际部署难易度

Motivation

NetCahce的提出源于目前高性能内存键值存储系统的火热趋势，我们讨论认为类似于NetCache这样在网络中缓存热数据自然能在高偏斜和动态的实际工作负载中为内存数据存储提供性能和强一致性保证。

1.负载平衡

作为大规模英特网服务器的关键性构建块，键值存储系统为为十亿级的用户提供服务，故希望能提供高性能的保证以满足严格的服务等级协定（service level agreement，简称SLA，也称“服务水平协议” 服务级别协议是指提供 服务 的 企业 与 客户 之间就服务的 品质 、水准、 性能等方面所达成的双方共同认可的协议或契约）。理想情况下，如果每个存储结点的吞吐量是T，一个具有N个结点的键值存储系统能保证总体吞吐量为N*T，已知每个结点实际处理量不会超过T，且查询延时有限（不会无限延时阻塞），这些性能保证能使服务提供方很容易得扩展存储系统以满足特定的SLAs。

然而，真实的工作负载具有动态和偏斜性，很难提供上述保证，热点数据条目查询次数远远高于其他条目，这会造成系统的失衡。系统的瓶颈受限于过载的结点，导致其他许多结点不能充分利用，所以整个系统不能到达预期的总体吞吐量。而且，过载的结点查询量高于它能处理的量，造成很高的系统延时。

ps：理想和实际情况下系统的负载和延时在满足SLA时的差异，文章讨论的技术的一个实际场景（原因）

2.快速且小量缓存实现负载平衡

缓存是一种有效的减轻负载不均衡的技术。理论证明，缓存器仅需存储O(NlogN)的条目数就能平衡N个存储结点组成的一个key-value哈希划分簇的负载，而与key-value的条目总数无关。具体说，已知N个结点具有NT的系统总负载，如果缓存能承受所有的查询的最热的O(NlogN)的条目，那么极大的可能情况下将没有结点会受到超过T的负载，不论查询的负载分布如何。由于O(NlogN)相对而言是比较小的，所以热条目能被拷贝到所有的缓存结点上以避免在缓存层出现循环负载平衡问题。虽然O(NlogN)小到足以可分发到每个客户端，但是保证缓存一致性很难，如果有许多用户访问一个共同的热数据集，但这个集并不是对每个用户都是最热的，那么用户缓存就不会从这种缓存机制中受利。因此，在存储服务器上构建缓存层是更有效的。（ps：这里主要是动态问题，热点是变得，比如，hot items set分发到每个用户，但是此后活跃用户会的频繁访问会改变这个hot set，对于非活跃用户的hot set缓存来说，它缓存的数据失效了，故只能在用户到存储服务器之间建立一个cache layer*）

为了处理偏斜的工作负载，缓存层必须根据存储层提供一个总体吞吐量。(大致这样一个比例，缓存结点*每个结点的负载 约等于= 存储节点*每个结点的负载)。故负载近似时，缓存结点数需要和存储结点数近似，这成本太高，开销也高，因为存储结点热数据的修改要更新到每一个缓存结点上。因此为了构建高效率低开销的缓存层，需要缓存结点的负载远高于存储结点的负载。（缓存层的缓存结点负载需求）

ps：该部分介绍如何通过缓存平衡负载，为何需要缓存层，以及缓存层的负载要求

3.内存存储系统的网络缓存

内存缓存对于flash或disk存储系统很有效，因为DRAMs比SSDs或者HDDs快的多，但是当数据库本身就是内存数据库，那么内存缓存就不再有效了。一个内存键值存储系统有128个服务器，每个提供一千万QPS（每秒查询率，以每秒查询量衡量），那么系统总体能到达12.8亿的QPS吞吐量，缓存层需要提供相对应的吞吐量。

将缓存层建立在网络中是一种很自然的解决方案。交换机能够被IO充分利用。交换机有足够的处理能力，而且不需要额外添加硬件，不会有额外的延迟惩罚。另外FPGA或者NPU（Neural-network Processing Unit，嵌入式神经网络处理器）要么部署不方便，要么吞吐量达不到，要么太昂贵。

4.用于网络缓存的可编程交换机

现代的商用交换机具有数十MB的片内内存，而键值存储系统的values通常很小，故交换机足以在内存中存储O(NlogN)的数据用于平衡负载，同时留有足够的资源处理传统的网络功能。而对于大value，可以采用数据包划分的方式解决。(large item divided into smaller chunks to multiple packets)

传统交换机的ASIC处理电路功能固定，添加新功能需要重新设计制造新的ASIC，但新一代可编程交换机的ASIC允许用户编程控制分组处理管道而不需要替换交换机的ASIC。

• 可编程控制交换机识别特定的数据包格式，custom packet formats
• 可编程实现片内内存存储特定状态（热数据及查询统计）
• 可编程switch table去执行特定操作，如从内存中复制value到packets中，或者detect heavy hitters

ps：本节介绍了NetCache的设计动机、思路。从问题产生（实际workload通常不能满足SLA，到最终采用可编程交换机建立网络cache layer解决问题）

NetCache Overview

假设整个机架用于键值存储系统，数据条目key-value采用哈希划分到存储服务器上。使用ToR交换机连接到服务器，作为负载平衡缓存层。整个系统由ToR交换机、控制器、存储服务器三部分组成。

1.Switch

交换机是NetCache的核心组件，负责实现路径上的item缓存（on-path caching）以及传统的数据包路由工作（L2/L3协议）。本文预留了L4端口用于区分NetCache数据包，这样可以和传统网络协议和功能兼容。

cache模块存储热数据，读请求直接由switch处理，写请求会继续分发到存储服务器上。缓存一致性由一种轻量级的“直写”机制（write-though，直写模式，在数据更新时，同时写入缓存Cache和后端存储。此模式的优点是操作简单；缺点是因为数据修改需要同时写入存储，数据写入速度较慢，对应的有write-back，回写模式）来保证。

查询统计模块给controller提供key-access的统计，用于缓存更新（热数据集更新）。这实现了NetCache平衡动态负载。它包含两部分：1）cached items’ per-key counters。2）heavy hitter detector to identify hot keys which uncached。

switch是一个读缓存，switch宕机后，重启或直接采用后备ToR交换机即可，NetCache缓存量很小，重启后可以很快得refill。

ps：本节介绍了NetCache的关键组件switch的两个主要功能模块（存储、检测动态热数据），以及容灾问题（简单，直接重启？？这里关注一下下文的cache一致性如何解决，交换机重启后cache为空，如何同步cache）

2.Controller

控制器主要负责更新缓存（热数据），它接受HH reports（热数据报告，heavy-hitter通过两个算法检测去重后发出该报告），然后对比cached keys‘ counter，决定哪些该插入cache，哪些删除。

3.Storage servers

两个功能：1）映射NetCache packets到键值数据库的API，简单说就是什么packet该做什么操作。2）实现cache和storage的一致性策略。一种中间件的形式使得NetCache很容易整合到内存数据库中。

4.Clients

NetCache提供给用户一个client library，应用可以使用该库访问远程数据存储服务器，该库的接口与已有的数据库接口类似。

ps：这部分简要描述了NetCache的各个组成部分及其功能

NetCache Design

1.网络协议

a）包结构：NetCache属于应用层协议，嵌入到L4数据包的负载中，与其他的key-value存储系统一样，使用UDP进行读请求以满足低延时，使用TCP进行写请求以保证可靠性。NetCache字段包含在TCP/UDP数据包的负载中，并为NetCache保留了一个特定的TCP/UDP端口。NetCache交换机使用这个端口调用特定的packet处理逻辑，其他交换机不用了解NetCache的数据格式，正常处理packet就可以了。

b）网络路由：NetCache利用已有的路由协议转发数据包。NetCache对于整个而言是透明的，仅在NetCache交换机上处理NetCache的部分。这样它和其他的网络协议和功能能共存。

2.请求处理

NetCache的一个关键优势就是网络路径中的缓存提供了直接的处理。读请求直接由路由器处理而无需交付到存储服务器，具有很低的延时，写请求直接交付到存储服务器，中间无额外性能开销。

a）处理读请求：1）检查cache命中，且valid，在packet header添加value字段，从cache中取出value设置到字段上，增加该key的counter，交换packet header的源地址和目的地址，作为reply返回packet到用户端。2）若没有命中，HH detector计数，如果是hot数据就通知controller。非hot数据及新的未缓存的hot key，转发到服务器，由服务器处理。

b）处理写请求：检查cache是否存在，是则将cache中的value置无效，防止接下来的请求从cache读取到旧版本的该数据。写请求之后发送到服务器由服务器处理。

3.缓存一致性及缓存更新

1.缓存一致性

“直写”方式保证缓存一致性。当写请求的key是已缓存的，switch会将缓存的value置无效，然后修改packet header的操作字段为一个特殊值以通知服务器，本次请求的key是缓存在cache中的（服务器除了更新，还需要对switch做同步）。

服务器会更新本次写请求的数据，然后直接reply给client，不等待switch更新。同时服务器会从packet header识别这次更新的key在switch中有缓存，故会给switch发送another packet去更新switch。本次更新对应的switch没有更新之前，所有后续同一key的写请求会被服务器阻塞，以保证服务器和cache的一致性。switch的update完成之后，item重新valid，可以为后续的read queries服务。

2.缓存更新

为了处理动态工作负载，控制器频繁更新缓存。存在的主要问题是有限的交换表和注册更新速率。解决方案是由于NetCache仅需要50%的命中率，所以不用每一次请求到达都调整cache，做一个热度筛选，HH detection实现，足够热才会去调整cache。这样降低了处理量。

4.交换机数据平面设计

1.Switch Data Plane

主要包含三个部分：入口管道，流量控制，出口管道。一个交换机有多个出入口管道，一个管道又有多个端口（接口）。packet到达入口ingress pipe，先由入口的tables处理，然后在traffic manager中排队分发到出口egress pipe，最后由出口管道发送出去。

每个管道有三段（stage），三段按序处理，三段通过共享packet的header中的fields实现信息传递协同工作。每一段都有特定的tables，去匹配packet中特定的部分（a few header fields），然后做相应的action。

可编程交换机允许开发者自定义packet格式，指定自定义的处理流程，通过指定每个stage的table和它相匹配的fields及action。通过P4编写交换机程序，由交换机厂商提供的编译器编译P4程序到交换机能识别的二进制文件。

2.Variable-Length On-chip Key-Value Store

NetCache将key-value条目存储在每个stage内的memory的register array中，通过这个memory位置的索引可以直接线性的找到或更新该item。（流程：match-action table对packet header中的key做匹配，得到action data，即index，通过index及packet header中的operation type对memory中的数据做相应处理）

由于硬件资源问题，每个stage的每个register array从每个packet中读写的数据长度是固定的，故针对变长的items的values，需要使用多个register array，然后从多个stages中提取组合成一个大的value。这里就涉及到如何设计以实现最高的效率。我们的设计方式是使用一个lookup table对每个key做匹配，包含一个bitmap指示这个key对应的value所在的arrays的集合，一个index指示具体的value的data所在的arrays的location（每个register array处理的是同一个index）。

内存管理 ：NetCache的controller管理register array的index和item之间的映射。之后就是策略算法进行装箱问题（箱就是arrys的各个index，物品就是不同长度的values）

3.请求统计

请求统计模块包含三个组件：cached items' counters、Count-Min sketch、Bloom filter。三个组件都通过哈希函数构建在交换机数据平面的register arrays上（内存上）。

一个已缓存的item请求到来（key命中），那么它对应的counter array的index上的元素+1.

Count-Min sketch（计数最小略图）由4个register arrays组成，它用四个独立的哈希函数将一个key映射到arrays的4个index上，统计的时候这4个位置都+1，查询的时候采用最小的那个值作为该key的frequency（4个index的元素值中最小的）（防止哈希冲突），当这个frequency值超过一个阈值值，就认为是hot的，就需要向controller发送report。

Bloom filter作用就是防止一个uncached key多次report给controller，减少了不必要的开销。

4.Put Everything Together:Pipeline Layout

所有入口管道复制一份同样的lookup table做key的match，出口管道仅存储该管道对应的port链接的数据服务器的cached items' values。

之后就是各种类型key（是否是NetCache请求，已缓存，未缓存，有效或无效）的流动情况。

DISCUSSION

NetCache的一些缺陷，如它只针对单个服务器机架rack，不支持长度的key，不支持太大的value，不能很好的处理极度偏斜的负载，不能处理写密集型工作负载。

1.多机架服务器组的负载平衡问题。将NetCache交换机假设到更高的关口上，当然也需要更强大的硬件资源。

2.突破定长key的限制。通过将变长key映射到定长的hash key实现，需要处理hash碰撞问题，更加复杂。

3.密集写的工作负载问题。直接在switch进行hot item的写操作。但是要做容灾处理和一致性处理。

Evaluation

结论

• NetCache可以在可编程交换机上at line rate运行
• 提供巨大的性能提升，在吞吐量和延时方面
• 有效得处理很大范围的动态负载

细节：略

PPT概要

• 相关知识介绍：分布式-内存-键值数据服务器、switch、cache同步。
• NetCache主要思想：问题-解决方案。
• 问题场景
• 已有方案
• NetCache方案
• NetCache设计细节，按各个组件的构成
• 总体的工作流程，按不同类型的query的流动描述
• 实验方法及性能提升结果
• 不足之处及可能的改进方案