为了实现多机架的负载均衡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....
这个工作也是可编程交换机上实现KV store，但相比于之前的NetCache的优点是可以直接在可编程交换机的数据面上写数据，并用多个交换机实现chain replication去做备份，并且带有整套完备的routing, handling out-of-order delivery, failure recovery的机制。
文中提到采用了Vertical Paxos去备份数据，其实也就是chain replication，Vertical Paxos的本质是它将数据备份的协议和控制的master分离，可以change the configuration of acceptors within individual consensus instances，是一个普遍的共识算法类型，并不特指某种算法，chain replication是Vertical Paxos的一种实现。
there is only one consensus protocol, and that’s Paxos
系统支持在数据面直接Read和Write，但是Insert和Delete需要控制面的操作，也就需要更多时间，由client对key进行一致性哈希，选择(f+1)个virtual nodes组成的chain，就可以决定在哪条chain上存取。所以chain replication是对于virtual node来说的，一个switch在 (f+1)*virtual node数目 条chain上。发生reconfiguration的时候需要client，server和switch同时调整，但reconfiguration只在fail的时候触发，所以可以接受。
路由直接用已有的underlay的协议（也就是IP层路由），不用真的连接成一条chain。
保证一致性的方法是通过seq number实现的，这样如果一个事务要写入多个值，就会导致脏写，但这个也很好保证，就是在写入的时候block其他写入，但这样系统的吞吐就不会那么好看。文章后面也提到NetChain does not support multi-key transactions，并argue说如果一定要实现的话可以把多个value pack起来，但这明显并不是general的方法。虽然最终的值是一致的，但不同节点的log可能是不一致的。
因为考虑了多个备份chains，而且是带虚拟节点的一致性哈希，所以当一个switch fail之后要重配置很多个switch。文章考虑只重配置neighbor switches（它不一定是保存数据的可编程交换机），在neighbor switches上加规则绕开failed switch，然而因为virtual nodes+一致性哈希，所有的switch都是neighbor switch。
在恢复时把fail switch对应的virtual nodes分配给不同的live switches，也可以全部分配给一个新的switch。对于中间节点和头节点的恢复，过程大概是先预复制后一个节点当前的状态，此时不停止写入；然后停止写入，完全复制后一个节点当前的状态，再将新switch入链。
对于头节点的恢复，因为头节点是确定写请求seq number的，所以为了保证严格大于fail node的seq num（极端情况是新的头节点恢复后还有数据包飘在头节点和第二节点的路径上，而新的头节点复制第二节点的状态里没有这些数据包，导致seq num不一致），将seq num设计为 (session number, sequence number)，在换头节点的时候session number加一。
而对于尾节点的恢复，尾节点要复制前一个节点的状态，但在第二阶段的完全复制时需要drop掉neighbor switch的所有写入和读取请求，但这样此时新的尾节点和前面n个节点是不一致的，而可编程交换机又不支持回滚，不会导致之后读取到写入未成功返回的值吗（比如在client retry之前新的尾节点再fail一次，然后系统让前一个节点接受读取请求，但前一个节点有未commit的数据），我不理解。除非在client端保证，在写入操作没有成功返回之前，不能任何其他client访问这个key，否则感觉这个方法在机制上有硬伤，作者又没有讲清楚。
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不友好。
随着存储媒介的发展，我们逐渐可以以网络的速度去存取存储媒介里的内容，而网络和程序的开销可能会成为分布式文件系统的瓶颈。RDMA可以加速传输，但处理storage policies目前还是靠存储节点的CPU。文章提出将分布式文件系统的storage policies卸载到智能网卡上，storage policies包括authentication, replication, erasure coding等。这篇文章是SC22的best paper finalist，这种文章看起来和jin xin老师的netcache，netchain有点像，都是找到了很适合in-network computing的点。
作者对比了其他一些对数据包处理的方法，RDMA、eBPF、DPDK等没有办法同时做到：1. 不需要在存储节点上中断CPU和保存额外数据结构的单向请求；2. 编程的灵活性；3. 用户态更新storage policies，且只处理自己的数据包（隔离）。
作者用一个叫PsPIN的硬件设计去实现可以满足以上要求的数据包处理方法，文章的创新主要是将sPIN这个新的编程模型用在分布式文件系统的领域。sPIN的优势主要是可以对数据流中的数据包应用处理函数，可以直接运行C++（而不是P4）且没有太多限制，并且可以将指定数据包映射到用户态应用指定的上下文中而不是统一处理所有数据包。
sPIN的处理函数叫handler，可以为第一个包，中间的payload包和最后一个包分别指定handler。后面的内容就是authentication, replication, erasure coding三种类型policy的应用和模拟下的性能。文字部分大概就是一些状态要怎么存储和传递，没有特别值得提的idea。
erasure coding这部分有点复杂，不太了解文中的TriEC的校验块的生成过程，所以看不太懂。
我比较喜欢这个工作的风格，但不确定是否应该投入到这个方向，即分布式系统+RDMA+INC。
这是一个将programmable switch当成一个分布式机器学习的parameter server，从而实现line rate的梯度聚集的工作。它是第一个提出将programmable switch用在分布式机器学习的梯度聚集上的工作，引用量也比较多。和parameter server相比，可以避免end-host processing，达到“sub-RTT” latency；和allreduce相比，可以将传输数据量减少大约2倍。和一些梯度压缩的技术相比也不一定慢，同时还有无损梯度聚集的优点。
它有三个创新点：
为了适应programmable switch的弱算力，文章提出将参数的更新分成小块，从而可以被programmable switch流水线处理。这个严格来说可能不算创新，而是一种adaptation。逻辑上的设计都是非常简单的。 这个算法虽然很简单，但是其实很巧妙。将需要聚集的分块后，worker和switch的分块是一个有序的直接相联映射，它隐含了多个worker之间的共识：收到switch的返回就说明梯度聚集完成，并且下一个需要聚集的分块的位置也是确定且一致的。
The coordination is implicit because the mapping between model updates, slots, and packets is deterministic.
为了保证worker之间的同步，以及检测和恢复丢包的问题，控制面需要能够区分是回传正确结果时的丢包还是worker传数据的时的丢包。文章的解决方案是保存两个switch状态：上一次slot里面的结果的shadow copy，以及当前的slot接收到的worker发来的数据。这个机制只能应对worker落后一个chunk的情况，如果worker持续掉线的话是会阻塞的，而分布式机器学习也不会像一般的分布式系统那样考虑太多的可用性，就简单阻塞住就行。它给的switch端算法逻辑9-17行好像有点问题，大概理解就行。 为了适应programmable switch不支持浮点运算，文章提出在switch上做定点数加法，然后在worker端做scaling。worker首先要对这个scaling的幂值达成共识，文章用的方法是在发一个block的时候带上下一个block的梯度的最大幂值，然后在switch返回的时候带上全局最大的幂值给每个worker。第一个block的幂值怎么办文章没说。 implementation部分还有一些P4和RDMA的具体实现的讨论，但我暂时不太懂，这部分比较复杂，可能实际用到的时候才有动力去学。extention部分讨论了这个框架可以怎样扩展到多机架（跨交换机）的场景，引入拥塞控制模块，不同的硬件设备以及多租户的集群环境。
这篇文章认为in-network aggregation对减少训练时间的提升很有限，它的作用应该在于减少在一个共享ML集群中的网络带宽的使用。
文章refer了另一篇文章An In-Network Architecture for Accelerating Shared-Memory Multiprocessor Collectives的分析，in-network aggregation对ring allreduce的理论最大提升只有2倍，考虑ring allreduce分为scatter-reduce和Allgather两个阶段，每个都需要传输和接收一次和设备数量n成比例的信息，in-network aggregation可以看成一个超快的parameter server，可以做到需要一个阶段，所以理想是2倍，现实往往还没有2倍。文章构造了很多communication bound的场景去说明，即使通信被优化，实际加速效果也没有那么好。
为了解决可编程交换机的浮点数限制，作者将可编程与交换机解耦，设计了一个新的支持浮点数运算的加速器硬件。这样看好像智能网卡一类的硬件的应用要更general一点，不一定要交换机。
为了更好地共享网络带宽，提出了一些在共享ML集群中用可编程交换机需要解决的问题（负载均衡和拥塞控制）的方案。
考虑fat tree的拓扑结构，文章提出的框架假设使用什么节点是其他算法给定的，而且不假设是否所有任务都使用in-network aggregation，流量超过某个大小的流才用ING。
文章提出的load balencing方法就是对每个任务规定多棵聚集树，每棵树负责相同大小的gadient块（round robin分配），树内用标号大小来区分顺序。
对于拥塞控制，文章是在TCP的ECN拥塞控制上面做了一些算法上的适配，我的理解是它的算法在逐层聚合梯度的时候，顺便将ECN位聚合起来，如果ECN不为0，则整颗聚集树一起降低传输速率，同时会有一个由加速器硬件指定的可用buffer空间，防止溢出，总体来说都是简单的heuristic。
作者用FPGA实现了它设计的加速器硬件，因为对FPGA不是很了解，这部分看不懂的名词特别多（只看懂个lookup-table和flip-flop），感觉之后做FPGA的可能性不大，有需要再看。PS: 想看有没有开源代码看看整个FPGA项目是怎么实现的，发现只有两个空的代码仓库。https://github.com/nadeengebara