完整版链接：https://www.usenix.org/sites/default/files/osdi20-full_proceedings.pdf

Correctness

1. Theseus: an Experiment in Operating System Structure and State Management

这篇论文用 Rust 写了一个叫做 Theseus 的操作系统。

Theseus 希望解决的问题是：1. 提升 OS 的模块化程度；2. 充分利用 Rust 的特性。

提升 OS 的模块化程度，意味着：1. 避免一个模块的错误波及至其他模块；2. 能让模块迅速地从错误中恢复；3. 可以实时更新一些模块而不影响其他模块的工作。

模块之间错误传递的现象叫做 state spill。例如，安卓系统的某个系统服务一旦出现故障，整个用户空间的进程都会崩溃，哪怕一些应用并没有使用出现故障的服务。再比如，传统的内存管理模块（MM）需要维护一张表来记录分配出去的虚拟内存区域（VMA），其他进程只能通过 MM 分配给它们的 handler 访问这些区域。因此，一旦 VMA 失效，所有使用 handler 的进程都会出错。

为了让模块迅速恢复，Theseus 采取了三步走：首先清除报错的 task，如果不行就重启之。如果还不行，就直接重装模块。这种策略之所以能够实现，是因为 Theseus 具有实时更新模块的特性。

不同于传统操作系统，Theseus 不需要停止所有进程就能完成一些模块的替换，而这要归功于模块之间的弱依赖性。Theseus 把整个系统拆分成很多个相对独立的 cell ，每个 cell 都由一份代码文件实现，编译成单独的 object file，运行时被装载到不同的内存区域，实现了高度隔离。

Theseus 将 Rust 的特性充分利用在了内存管理和进程管理中。例如，进程申请分配虚拟内存时，Theseus 会将这片内存打包为 object 返回给申请者，而不是像传统 OS 那样返回一个指针。根据 Rust 的 Ownership 机制，申请者就“拥有”了该片内存。当申请者试图访问它时，必须通过对应的接口指定一个类型。Theseus 检查该类型不会越界后，才会返回一个该类型的 slice，这样就把潜在的地址越界扼杀在了编译阶段。当拥有该内存的申请者离开其作用域后，该内存也会随之被释放（Ownership 机制），所有对它的引用都会报错，这就在编译阶段消除了 use-after-free 的可能。总之，Theseus 充分利用了 Rust 编译阶段严格的安全检查，拥有了比 C 语言系统更好的安全性。这种将语言特性整合进系统特性的做法，作者称之为 intralingual approach。

从第二篇文章起，我主要会关注它解决的问题和提出的新思路，不会再仔细研究具体做法。

2. RedLeaf: Isolation and Communication in a Safe Operating System

这篇论文用 Rust 写了一个叫做 RedLeaf 的操作系统。

Abstract

本系统探索OS的语言安全性。比起商业OS，RedLeaf不通过地址空间隔离错误，而是通过类型与内存的安全性。提出了domain的概念，一种基于语言的轻量级“隔离域”，可以隐藏信息、隔离错误。domain可以动态装载、干净地清除。一个domain的错误不会影响其他domain的运行。通过RedLeaf的隔离机制，我们实现了设备驱动的“end-to-end zero-copy, fault isolation, and transparent recovery”。我们还验证了它的性能。

Introduction

内核子系统之间的隔离是保证系统可靠性与安全性的重要机制，但是现代OS依然以单内核为主，在隔离方面软硬件层面做得都不够。这主要是因为隔离机制需要牺牲性能。同样的道理，一些安全性较强的语言不适合写底层的OS，因为它们需要GC或者特定的runtime，开销很大（比C语言慢20～50%）。Rust的出现缓解了隔离与性能的矛盾，它通过ownership机制保障了类型与内存安全，不需要GC。

我们想证明：语言安全的真正好处，在于提供轻量级、细粒度的隔离机制，以及其他数十年都未能落地的重要机制（fault isolation, transparent device driver recovery, safe kernel extensions, fine-grained capability-based access control）。

RedLeaf不使用硬件提供的隔离机制，只通过Rust的类型与内存安全实现这些机制。然而语言本身提供的机制不足以实现一个足以隔离内核与用户的系统。它还需要fault isolation机制，能在不影响系统正常运行的情况下，处理模块的异常情况。它需要回收该模块的资源、保留分配给其他模块的资源、使调用其接口的程序报错（而不是继续运行或阻塞）。

RedLeaf domain遵循以下原则：

  • 堆隔离，domain不使用指向其他domain私有堆的指针，保证了释放私有堆的安全性（另外有共享堆用于domain之间的通信）
  • 可交换类型，仅指定类型的对象可以在domain之间交换
  • 所有权跟踪，跟踪共享堆上所有对象的owner，确保对象传递时原来的domain里没有别的alias（？），这样就能安全地释放故障domain在共享堆上的资源
  • 接口有效性，跨domain的接口只允许传递可交换类型
  • 跨domain调用代理，domain之间的通信要通过一个安全的proxy传递，它会更新对象的owner，处理故障domain

这些原则实现了开销很小的数据隔离和有效的错误隔离：domain故障时由proxy终止线程、回收资源，再被呼叫时由proxy报错而不会panic；由故障domain传递给其他domain的对象不会被回收，因为我们跟踪了对象的ownership。

RedLeaf Architecture

略，我们先看看其他文章。总之本文的重点是用Rust写一个模块之间充分隔离的、实现了高效fault isolation的操作系统。

3. Specification and verification in the field: Applying formal methods to BPF just-in-time compilers in the Linux kernel

本文涉及了一个我不了解的领域：Linux内核扩展、Berkeley Packet Filter、Just-in-time compiler。

扩展内核的常用方式，是将应用层的代码下载到内核。应用向内核提交一个由专用语言写成的程序，然后内核通过解释器执行，或者用JIT编译成machine code执行。BPF就是这样一个语言，它已经被广泛应用在了Linux内核的多个模块，例如网络、安全、tracing以及其他服务。

BPF JIT compiler非常重要，但又容易出一些小错，所以本文实现了一个叫做Jitterbug的框架，辅助了JIT的实现和验证过程。

由于我并不了解该领域，而且也不太感兴趣，就先跳过吧。

4. Cobra: Making Transactional Key-Value Stores Verifiably Serializable

不了解数据库，本文的核心问题是“用户如何验证黑盒数据库满足了serializability”，这与数据库的正确性、稳定性、安全性相关。本文有一些数学模型和算法设计。

5. Determinizing Crash Behavior with a Verified Snapshot-Consistent Flash Translation Layer

现代计算机在存储数据时，会经过一个存储栈（storage stack），例如应用-文件系统-物理设备。要设计一个存储栈没那么简单，例如为了维持性能、节省等待时间，I/O操作的顺序可能会被打乱；系统断电或崩溃时，存储系统需要正确地恢复数据。本文针对系统断电或崩溃的场景，设计了一个叫做 snapshot-consistent flash trasaction layer (SCFTL) 的硬盘模型，能保证硬盘崩溃时能够恢复到上一次进行 flush 操作前的状态。这个领域我也不懂，就不深究了。

6. Storage Systems are Distributed Systems (So Verify Them That Way!)

完了，这篇文章我从Introduction开始就一句话都看不懂，似乎是跟software verification有关。我只知道它的核心idea是把分布式系统的一些特点（异步、易出错的环境）类比到了存储系统。

Storage

7. Fast RDMA-based Ordered Key-Value Store using Remote Learned Cache

Network-attached in-memory key-value stores 是许多数据中心应用（数据库、分布式文件系统、Web服务、Serverless computing等）常用的技术。随着网络技术的发展，CPU成了数据传输的瓶颈。于是出现了一种技术叫做RDMA，是用来访问远程机器数据的，相当于联网版的DMA，可以绕过CPU传输数据。不过RDMA的一个缺点是“traversing tree-based index with one-sided RDMA primitives is costly and complex”，于是又出现了“index caching”的办法。本文针对index caching，用机器学习（真是万能）训练了一个learned cache，以及其他相关的解决方案。

8. CrossFS: A Cross-layered Direct-Access File System

终于有了一个我懂的领域。

本文提出了一个跨层级的文件系统（FS）。所谓层级，即该FS处于计算机系统的哪个位置，例如用户层、内核层、固件层。最典型的是内核层FS，它能满足最基本的要求，例如 integrity, consistency, durability, and security，但它有三大瓶颈。1. 要做I/O必须经过OS，这会带来1-4us的延迟；2. 常出现不合理的串行操作，并行性不够好，例如即使在访问一个文件的不同部分时也要给inode上锁；3. 没有充分利用存储硬件的能力，例如计算、几千个I/O队列、固件层的调度，最终影响了I/O密集型应用的延迟、吞吐量、并行性。

用户层FS可以绕过OS读写存储介质，但是用户层往往不可信任，很难有一个满足基本要求的设计。固件层FS能利用好存储层的计算能力，但无法利用 host-level multi-core parallelism，而且都继承了 inode-centric design for request queuing, concurrency control, and scheduling, leading to poor I/O scalability。总之，这些FS都缺乏不同层面间的配合。

然而，本文提出的跨层级FS可以解决上述一切问题！牛！具体的我就不看了哈。

9. From WiscKey to Bourbon: A Learned Index for Log-Structured Merge Trees

本文针对LSM树做了一些优化：https://yetanotherdevblog.com/lsm/。

B树是数据库系统里一种传统的索引结构，它可以用ML优化，称为 learned index。LSM树也有广泛的应用，例如BigTable、LevelDB等。本文将 learned index 应用到了LSM树。这里有一大挑战，就是LSM树适合写操作频繁的场景，但 learned index 更适合读操作，频繁的写操作会使它的模型失去效用。不过本文仔细研究了LSM的特性，找到了一种方法融合两种技术，并得到了一个不错的结果。

10. LinnOS: Predictability on Unpredictable Flash Storage with a Light Neural Network

又是一篇将ML融合进传统技术的。本文要优化的问题是：闪存设备的内部结构日益复杂，使得I/O操作的延迟难以预测（比如当你向某设备发出I/O请求时，你很难知道它是不是在进行垃圾回收、自我修复等操作），影响了I/O性能。

目前有三种解决方案：“白盒子”重新设计了闪存设备的内部结构，但问题是供应商不一定愿意这么制造；“灰盒子”同时从设备层与软件层入手，问题是一样的；“黑盒子”将设备视为完全的黑盒，只依靠软件层的解决方案。目前 speculative execution 是比较受欢迎的。本文提出了一种新的“黑盒子”方案，不修改文件系统或者应用，只是用ML学习设备的行为。LinnOS就是这样一种可以学习并推导每次I/O延迟的操作系统。

这个模型需要在准确率和计算量之间平衡，因为每次I/O都要用它推断延迟。预测精确的延迟太难了，而且90%的情况下延迟都比较稳定，只有10%的情况下的延迟较大，形成一个“长尾”图案。因此，该模型的输出仅有“快”和“慢”，是一个简单的二分类模型，当判断结果为“慢”时就拒绝该请求并通知应用层处理（例如换用其他节点）。模型的输入特征也很简单，主要是当前pending I/O的个数，以及近几次I/O的实际延迟。

个人觉得这篇文章写得挺好，有时间了可以详细读一读。

11. A large scale analysis of hundreds of in-memory cache clusters at Twitter

这一篇与服务器缓存（in-memory caching）有关，主要研究如何提升大型网络服务的缓存利用率，并与Twitter进行了合作。他们研究了Twitter提供的大量数据，找到了一些规律，不过大部分内容都在展示数据和图表，没看到哪里跟系统设计有关。跳过。

12. Generalized Sub-Query Fusion for Eliminating Redundant I/O from Big-Data Queries

好了，这一篇我一个字也没看懂，完全不懂SQL。跳过。

OS & Networking

13. A Simpler and Faster NIC Driver Model for Network Functions

现在的网络驱动模型过于灵活，其实现的功能超过了一般情况下的需求，使得性能下降。例如，现在的驱动支持乱序处理packet，然而互联网的很多骨干架构都不需要这个功能。所以本文提出了一个新的网卡驱动模型，并为Intel 82599编写了长度仅550行的驱动，使其性能大大提升（吞吐率提高60%）。

本文用两节的篇幅做了一些科普，对读者十分友好（不过内行人看了可能要说在水长度吧）。第二章介绍了 network function 的概念，我不知道中文名，后面就用 NF 代替吧。第三章介绍了网卡（NIC）的工作步骤，也让我好好补充了一下网络知识。

Network Functions

In this section, we introduce network functions: packet-processing appliances performing tasks such as routing, rate limiting, access control or caching.

硬件NF是实现高负荷网络的传统方式，它的处理逻辑全部写在硬件上，一经部署不可修改，所以灵活性很差。要想改变这部分网络，必须从物理意义上替换掉它们。

软件NF运行在通用的计算平台（例如x86 & Linux）上，通过网络协议栈（例如驱动、IP、TCP）与网卡通信。显然，软件NF更加灵活，更容易调试、部署和升级。不过，它的形式化验证是一个难题，性能也是个问题。网络性能的下限会影响到商业层面的行为，例如服务级别协议（Service Level Agreements）。一个10Gb/s的网络要保证在67.2ns内处理一个84B的packet，跟读取内存在一个数量级。换句话说，NF甚至没时间从CPU cache之外获取数据，由此可见性能的重要性。

现代OS的网络协议栈不适合NF的原因有三。第一，传统的协议栈使用的是push模型（硬件通过中断通知软件packet到了），这在低负荷的情况下管用，但是高负荷的NF承受不起大量中断带来的开销，它更适合pull模型（软件主动查询硬件的packet处理情况）。第二，传统的协议栈通过OS与硬件交互以实现隔离，中间隔着的这一层OS带来了额外的开销，然而NF一般是独立运行的，没必要与上层软件隔离。第三，传统的协议栈允许以完全灵活的方式处理packet buffer，然而NF的行为是比较固定的，没必要为它们实现这么灵活的处理方式，这只会给性能带来负担。

Kernel-bypass stacks 允许程序直接与硬件交互，并且着重于pull模型、批量处理packet以及更加固定的buffer管理模式。实际应用中的例子有DPDK。

驱动很不受开发者们喜欢。首先，开发者只能从制造商的手册里了解硬件的行为，有些手册甚至不是公开的，逆向工程也不甚可行。由于驱动常常由制造商内部维护，所以文档和注释都很缺乏，程序的bug也很多。于是开发者们只好把驱动看作黑盒子。但是驱动对于整个网络栈的性能至关重要。DPDK的驱动代码都超过了1000行，最长的甚至有66000行。

14. PANIC: A High-Performance Programmable NIC for Multi-tenant Networks

现在网速越来越快，CPU处理数据的速度有点跟不上了，于是出现了一种智能网卡（SmartNIC），除了提供联网功能，还能帮助CPU完成一些处理数据的任务，减轻CPU的负担。本文设计了一种新的SmartNIC，可以适用于很多场景，填补了现在SmartNIC适用范围窄的缺陷。

15. Semeru: A Memory-Disaggregated Managed Runtime

有关分布式计算的，说服务器之间有一种 resource disaggregation 的搞法，就是让每种资源由专门的服务器管，而不是给每样都给服务器一点。这么搞的好处有 1. 更容易通过调度来高效地利用资源；2. 某个服务器崩了只会影响一种资源（但是这个资源也全没了不是吗）3. 可以给服务器配备专门的硬件，便于替换和升级。

不过这么搞的问题在于，远程访问内存的延迟比较大。以往的解决办法都是从底层入手，但本文提出了一个新的视角，就是从runtime的角度提升数据的locality，例如减少cache missing，减少远程访问的次数等。具体的我不太懂，就不多说了。

16. Caladan: Mitigating Interference at Microsecond Timescales

Web搜索、社交网络、在线零售都是互动型、数据密集型的Web服务，会把收到的请求分发给上千个服务器。尾延迟（tail latency）很关键，因为它决定了最终的响应时间。不过为了提升数据中心整体的效率，同一台机器往往会同时处理多个任务*（据我理解，这里的意思是，虽然多个任务分享资源会让尾延迟上升，但也避免了其他机器空闲着等待最慢的响应结果）*。于是，任务之间必须抢占资源，导致延迟大大提高，这种现象叫做 interference。

为了缓解这种干扰，有一种办法是明确地为各个任务划分CPU资源，互相不得抢占。然而在现实中，负载往往是突变或者周期性的，例如在微秒级别的时间内突然爆发出大量请求，或者每隔一段时间被GC占据大量的内存带宽。现在的系统都检测不出这么突然的变化。

本文提出的 Caladan 就是用来解决这个问题的。它是一个CPU调度器，由一个专门的调度核和一个Linux内核模块 KSCHED 组成。该调度器能迅速给出分配的决策，提高CPU的使用率。

17. Overload Control for μs-Scale RPCs with Breakwater

现代数据中心的应用由一系列微服务 (microservice) 组成，通过RPC交互。为了满足现代应用对低延迟的要求，微服务有严格的“服务级别目标” (Service-level objective, SLO)，是对客户作出的服务保证的量化指标，有些是微秒级别的。虽然现代OS和网络硬件能在普通负载下满足微秒级SLO，但是系统过载时就很难了。

服务器过载会导致 receive livelock，服务器忙着处理新收到的packet（高优先级）以至于没空把处理完的请求发出去。这种情况对于微秒级RPC更严重，因为稍微延迟一会就达不到SLO的要求。此外，一些短RPC只需要较少的资源，服务器每秒被允许处理几百万个请求。当大量客户端同时发起请求，服务器会堆积起庞大的队列，造成系统过载，这个叫做 RPC incast 导致。

控制过载是为了移除超量的负荷，保证服务的高利用率和低延迟。目前的方案大概分两种，一种在系统过载时主动丢包，另一种则限制客户端的请求频率。这些方案都不适合微秒级的RPC。如果丢包，在通信上损失的时间都与处理请求差不多了；如果限制频率，客户端首先需要了解服务器的状态，而这又需要额外的通信时间。

另一个难题是把过载控制系统扩散到大量的客户端。在这种大规模系统中，客户端很少对某一个特定的服务器有需求，对它发送请求的频率很低，所以它对服务器状态的了解往往是落后的。如果在发送请求之前主动询问，又会带来额外的负担，尤其是对于微秒级的RPC。

本文为微秒级RPC设计了一个叫做 Breakwater 的过载控制系统，主要思路是根据SLO的完成情况对客户端进行“加分”和“扣分”。由此想法引发的后续问题及其解决方案不再赘述。

18. AIFM: High-Performance, Application-Integrated Far Memory

内存是现在数据中心最紧缺的资源，但也是最不灵活的。如果某个服务器的内存不足了，必须终止一些进程，导致之前消耗的运行资源都白费了。而且这时候其他服务器上往往还有多余的内存，但就是没法用。甚至本地的内存也不能用，例如服务器有30%的内存都是几分钟都未曾访问过的，说明有些内存是可以暂时回收的。

说到内存回收，现在OS普遍使用了内存交换技术，但它有几个问题：1. 粒度很低。哪怕只需要很少的数据，也至少得换入一页，即4KB（可是这也可以理解为prefetching啊）；2. 开销很大。为了换入一个页面，必须触发page fault进入内核，然后等待换入完成，这期间的CPU都被浪费了。

本文提出了 application-integrated far memory (AIFM) ，是一种把本地内存交换到远程服务器上的技术。开发者可以指定数据结构的“可远程性”，表示它是否可以被交换到远端。当AIFM发现内存压力很大时，它会把一些对象交换出去，并把指向它们的指针改为“远程指针”。当应用解引用远程指针时，会有一个 green thread runtime 把对象恢复到本地的内存。由于这个runtime上下文切换的开销很小，它可以利用恢复对象的等待时间，让其他线程做事，从而抵消了远程访问的延迟，保持了较高的吞吐量。

Consistency

19. Performance-Optimal Read-Only Transactions

本文只研究分布式存储系统里的一次性读事务。读事务是最主要的事务（其他的可能只占千分之几），发送的读事务会分散到各个服务器，返回数据的不同碎片。这种碎片化的访问方式可以提升读事务的性能，但是数据会有连贯性不足的问题。如何在保持一定连贯性的条件下，尽可能优化性能呢？本文对“最优性”作了严格的定义，并提出了“最优性能的读事务”。这篇理论性较强，而我对该领域了解少，不能把握它的idea，故止步于此。

20. Toward a Generic Fault Tolerance Technique for Partial Network Partitioning

本文解决了一种“奇怪的”（取自原文“peculiar”）网络错误，叫做 partial network partition，即一个集群里面仅有部分节点无法建立连接，但整个连接图是连通的。例如，A、B不能连接，但它们都能与C连接。另外一种将集群分成两半的 complete partition 与此不同，这种错误已经被深入研究过了，遗憾的是它的解决办法并不适用于 partial partition。本文的话题对我来说过于陌生，跳过。

21. PACEMAKER: Avoiding HeART attacks in storage clusters with disk-adaptive redundancy

分布式存储系统用冗余机制保护磁盘数据，例如100%复制和纠删码（Erasure Code）。不同的冗余级别对应着不同质量的磁盘——磁盘越容易出错，就越需要更多的冗余数据。

存储集群由多种品牌及型号的磁盘组成，并且会随时间变化。不同种类的磁盘有不同的失效率，但是集群往往“一刀切”，把所有磁盘都按照同一种冗余级别处理，以此保护其中最容易出错的磁盘。这样做的开销是非常大的，因为很多磁盘并不需要这么多冗余数据。

为了解决这一问题，有个不错的方法是根据失效率（AFR）调整磁盘的冗余级别。这使得磁盘必须经过一个转变级别的过程，然而它需要耗费相当多的I/O资源。当一大批磁盘需要同时转变时，集群的I/O带宽会被立刻占满，造成“转变过载”（transition overload）的问题。本来在转变前，数据就已经处于保护不足的状态（从失效率升高到开始转变之间有一定的延迟），结果还必须等待转变完成才能恢复安全。文中举了一个例子，某集群的数据整整一个月都保护不足，而且带宽全部都在了状态转变上。

本文提出的 PACEMAKER 是一个更优秀的冗余级别转变算法，解决了上述问题。细节我就不深究了。

22. Pegasus: Tolerating Skewed Workloads in Distributed Storage with In-Network Coherence Directories

本文解决的问题：分布式存储系统中有一些非常受欢迎的数据，每天可能要被访问几百万次。这样的访问量超出了单个服务器的负荷，所以必须把它们复制很多份存放到其他服务器来分担压力。然而在互联网的大背景下，“热搜”每天都在变化，我们无法预测哪些数据在将来会成为“热搜”。如果把所有数据都复制几份，这样的开销太大了，所以我们需要对数据进行实时跟踪。不过这个问题并不简单，

本文提出了一个叫做 Pegasus 的分布式存储系统，它受CPU cache coherency protocol的启发，用 in-network coherence directory 跟踪被复制的数据。每次进行写操作时，Pegasus都能重新平衡replica set，同时保持一致性。

23. FlightTracker: Consistency across Read-Optimized Online Stores at Facebook

Facebook专属研究。从Introduction章节来看，整个研究都建立在Facebook的系统上，作出的贡献也只适用于Facebook，除了一些“lesson learned”。本文解决的问题：用户每发送一个请求，我们就要向数据库发起成百上千个请求，然后汇总到一起。我们已经有了足够多的机制来优化这一过程，但是还要为开发者提供一个统一且符合直觉的一致性模型。

24. KVell+: Snapshot Isolation without Snapshots

快照隔离（Snapshot Isolation，SI）是数据库事务处理中的一个隔离级别，保证事务的读操作能看到一个一致的数据库的版本快照。例如联机分析处理（OLAP）需要扫描数据库的大量内容，此时如果有并发的联机事务处理（OLTP），修改了尚未扫描的数据，那么OLAP应该以旧数据为准。

传统的SI实现方式是留下数据的每一个版本，等OLAP扫描完数据后，再由GC线程回收旧版本。这显然会带来额外的存储负担，而且OLAP的时间越长，存储负担越大。本文强调了存储空间的重要性，例如Facebook发现“瓶颈在存储空间”、阿里将GC的优先级设为最高来防止存储空间的浪费，由此引出了他们“无需快照的快照隔离”。

他们发现，大部分OLAP对扫描的顺序没有要求，并且每个数据一般只扫描一次（例如求平均值等）。如果在OLAP的过程中有OLTP修改了还未扫描的数据，OLAP可以立刻跳转到该数据，扫描其旧版本并丢弃，然后回到原来的位置继续扫描。这样做并不会影响结果，但是节省了很多存储空间，因为旧版本的寿命大大减少了。他们把这种改良的OLAP称作OLCP，C代表“commutative”，可交换的。

不过这里会引申出几个问题：1. 如果同一个数据被更新了多次，如何保证只扫描最老的版本？2. 如何在相对乱序的情况下记住哪些是已经扫描过的数据？这些都在文章里有回答，不多赘述。

Machine Learning 1

25. Serving DNNs like Clockwork: Performance Predictability from the Bottom Up

模型inference广泛地应用在了Web服务中，Facebook一天要处理200万亿个inference请求。不过inference请求的响应时间会受尾延迟影响，为此传统的解决办法是为inference请求提供充分或过量的计算资源，确保它可以立刻执行而不会pending，不过这会使计算资源的利用率降低。

当前的系统普遍把组件的延迟量视作不可预测的。尽管inference服务的不稳定性有时候来自外界（例如任务量陡增），但我们可以消除它内部的不稳定性，例如缓存决策、分支预测、与其他进程的并行性等。本文提出并实现了Clockwork，用来提供稳定延迟的模型inference服务。

26. A Unified Architecture for Accelerating Distributed DNN Training in Heterogeneous GPU/CPU Clusters

本文提出了BytePS，一种分布式训练集群。这个成果在工业界还比较有影响力，可以直接在网上搜到中文介绍，我在这里只总结一些知识点。

分布式训练主要有两种架构，一种是all-reduce，它只需要GPU。每个GPU都存有相同的模型，然后分别取不同的数据计算梯度，再互相同步计算结果并更新模型，保持彼此状态的一致。它的主要问题是如何让多个GPU之间保持同步。另一种是PS（Parameter Server），其中运行在GPU上的多个worker取数据、计算梯度，并把结果传递给运行在CPU上的PS，由PS计算新的参数。worker开始下一轮训练时，统一从PS更新参数。根据我的理解，这两种方法的区别在于参数同步的“去中心化”与“中心化”方式。

本文对PS的优化在于PS更新参数的方式。原本是在CPU上进行“梯度优化”、“梯度整合”，但BytePS把优化器放到GPU上运行了。我的理解不一定准确，读者可以自行上网搜索相关资料。

27. Heterogeneity-Aware Cluster Scheduling Policies for Deep Learning Workloads

现在DNN训练经常要放到集群上进行，而一个集群的计算资源多种多样。例如，一些公有云有NVIDIA GPU和Google TPU可供租借；本文作者的实验室的集群里有NVIDIA Titan V、Titan X、P100 GPU。

这些资源的性能表现各有差异：ResNet-50在NVIDIA V100上训练比K80快10倍，但是从性价比（per dollar）的角度出发，P100又比V100好。有时候便宜和贵的GPU混用，可以在满足时限的条件下节省最多的资源（也就是钱）。在多任务的情况下，这个问题更加复杂。

用户的需求也有多种：有时候希望同一批训练尽快结束，有时候需要为临时任务安排适当的资源，有时候同一集群的资源会被划分给不同级别的用户。现在常用的调度策略（fairness、makespan、least attained service）可以对应一些场景，但是并不能做到最优，因为它们都没有考虑计算资源之间的差异，更不能实现多种资源相互配合的“混合训练”。

本文提出的 Gavel 是一种新的集群调度器，它把目前最常用的一些调度策略综合起来，抽象为一个任务吞吐量的优化问题，例如makespan相当于求最长完成时间的最小值。它会为每个任务寻求 “混合分配”，例如60%的时间独占V100，40%的时间与其他任务共用A100。它也实现了易于使用的API，兼容Tensorflow和PyTorch。

28. PipeSwitch: Fast Pipelined Context Switching for Deep Learning Applications

现在模型的training和inference往往使用分开的计算资源，导致GPU总体的使用效率不高。本文受CPU上下文切换的启发，使不同的training和inference任务能够以较低的开销在同一个GPU上切换，达到接近100%的使用率。

GPU任务切换的难点在于开销太大。CPU内存比GPU充足得多，大部分时候都可以把数据留在内存，因此只需要切换一些寄存器和指针。而GPU的内存紧俏，很难把所有任务的模型都容纳进来，所以必须把不使用的模型换出内存才能为另一个任务腾出空间，而这是相当费时的。相比于inference通常所需的几十到几百毫秒，装载模型可能需要数秒才能完成。本文针对这一难题，提出了流水线式的切换方法：利用模型的分层结构，让GPU一边计算，一边装载模型的剩余部分。

29. HiveD: Sharing a GPU Cluster for Deep Learning with Guarantees

大公司使用集群为自己的各个team提供训练服务，每个team都能分到一些“quota”，即计算资源的配额。然而quota只能保证数量，不能保证其他要求（文中叫做GPU affinity）。例如，有些任务希望使用8个8-GPU node训练，如果此时没有足够多的8-GPU node，就只能等待，或者使用别的组合（例如16个4-GPU node）。无论选择哪种，都会影响训练的效率。

本文针对该问题提出了一种更加高效的GPU资源划分方案，它和解决内存碎片化、分配连续物理内存的方法非常相像，即内核常用的virtualization、buddy system。刚才提到的问题，本质上也是资源碎片化的问题。具体的我不想看了，毕竟它只是整理了一下碎片化的GPU资源，没什么特别的地方（在我看来）。

30. AntMan: Dynamic Scaling on GPU Clusters for Deep Learning

这篇idea比较难懂，放着以后再看，网上有不少相关资料。

Consensus

31. Write Dependency Disentanglement with Horae

这篇idea比较难懂，我就大概讲一下它解决的问题。

写依赖（Write Dependency）指的是IO请求之间的依赖关系。软件层发起一系列IO请求，这些请求进入 Software Queue，又被分发到设备的Hardware Queue（HWQ），最后由设备完成操作。但SWQ会被I/O scheduler调整顺序，HWQ又会为了性能（device-side scheduling）和简洁（ request retries）而无视队列里的请求顺序。这样当IO请求之间有依赖时，IO stack只好每次只发送一个请求，直到完成后才发送下一个。这种做法不能利用多设备、多队列的并发机制，使得效率大打折扣。例如，当IO之间没有依赖时，设备越多、HWQ越多，IO效率越高；但是有依赖时，IO效率一直很低，无论有多少个设备或HWQ。

作者的Horae是一个新的IO stack，核心idea好像是把IO请求的数据与metadata分开，使得数据的处理能够并行，而metadata保持顺序。

32. Blockene: A High-throughput Blockchain Over Mobile Devic

本文提出了一种新型区块链Blockene，计算量小，可以在手机上运行。它的核心idea是两种节点：“公民”和“官员”。公民节点运行在手机上，是区块链的核心成员，它们参与consensus，并且假定其中三分之二是诚实的（在数百万规模的情况下还算合理）；官员节点运行在服务器上，它们不受信任，不参与consensus，并且只要求其中20%是诚实的。尽管存储区块链的任务由官员节点承担，但Blockene可以保证：即使80%的官员节点与三分之一的公民节点都存有恶意，另外三分之二的公民依然可以发现并纠正它们的异常行为。这样一来，官员节点分担了大部分计算和存储任务，公民节点则只负责监督，大大减少了负担。（所以有了政府，社会效率还是高一些哦，不过前提是这个政府能被有效监督……）

这篇文章的idea相当有趣，但是区块链并不是我的感兴趣的领域，所以不再深究细节，等有需要再看吧。

33. Tolerating Slowdowns in Replicated State Machines using Copilots

本文和下面三篇文章都是围绕一致性算法展开的（其实上一篇也是），读懂它们需要先了解一下基础知识，就以Raft为例吧：

34. Microsecond Consensus for Microsecond Applications

35. Virtual Consensus in Delos

36. Byzantine Ordered Consensus without Byzantine Oligarchy

Bugs

37. From Global to Local Quiescence: Wait-Free Code Patching of Multi-Threaded Processes

互联网有很多24/7在线的服务，当它们发现自己的系统存在漏洞后，必须尽快修补以防黑客趁虚而入。然而补丁一般需要服务重启之后才能生效，这会给用户造成不便。*（我不太明白，为什么不能轮流更新？例如100台服务器，一次更新10台、分10次完成，这样的代价很大吗？）*一个主要的例子就是OS更新，重启一次需要花掉几分钟。此外，有些应用的补丁更新也很麻烦，例如Redis这样的in-memory database，它的寿命非常长，有很多运行时产生的volatile state。如果要重启，要么 (1) 事先把它的volatile state转移到nonvolatile memory，重启后再转移回去，要么 (2) 在重启后经历一个warm-up phase。无论哪种方法都会影响性能。

热补丁（live patching）是解决上述问题的一个方法，它将binary形式的补丁直接插入进程的地址空间，避免了重启。不过这一方法有个要求：给函数f打补丁之前，所有进程/线程的调用栈上都不能有f（该状态称为“quiescent”），否则当它们从f返回时可能会跳转到被补丁覆盖后的地址，引发系统崩溃。以往进入quiescent状态的方法是设置一个全局屏障（global barrier），让所有相关线程运行到某个地方就停下来，然后再打补丁。但这个方法有很多问题：

  1. 如果其他线程都进入了屏障，只有一个线程要计算很久或等待IO操作，那么其他线程也必须等待，等待时间甚至没有上限。虽然可以设置一个timeout，但是万一一直碰不到所有线程都在timeout之内进入屏障的情况呢？
  2. 如果A线程进入了屏障，但B线程block了，需要A线程signal才能进入屏障，那么就会产生死锁。当然，事先设计好屏障的位置可以避免死锁，但这么做很复杂，也很不靠谱。

本文提出了一个 local quiescent 的方法，能够避免 global quiescent 的问题。它的思路很简单，就是让线程们不再需要等待彼此，只要自己进入了屏障就能打补丁。具体的实现方法是复制出另一份地址空间（Address Space，AS），其中所有页面的映射都维持原样，但是把需要打补丁的页面映射到补丁的位置。当一个线程进入屏障时，就把它线程控制块（TCB）里的AS切换成新的，这样就实现了单个线程的热补丁。

但该方法会造成一个明显的问题：打补丁的过程中，有些线程运行的是新版本，有些线程却还在运行老版本。作者声明说这在大部分情况下都不会造成影响，如果真的需要，则可以在 local 和 global 之间取一个平衡，即 group quiescence。

此外，本文提出的方法只能修改程序的text和rodata段，无法修改data段（例如一些数据结构、全局变量），虽然绝大部分软件升级都只涉及text段。所以作者建议只把WFPATCH作为短暂的过渡，为正式的维护提供缓冲。

38. Testing Database Engines via Pivoted Query Synthesis

数据库管理系统（DBMS）已经有了很多寻找 crash bug 的方法，本文提供了一个寻找 logical bug 的方法。所谓 logical bug 不会使系统崩溃，但是会返回错误结果。本文的思路是在数据库里设置一个 pivot row，然后合成很多测试语句，并保证它们的正确结果一定包含 pivot row。如果某次结果不包含，就说明有 logical bug。

本文还提到了另一个叫做 differential testing 的方法，就是对比同一语句在多个DBMS上的结果。虽然这个方法很有效，但是它要求这些DBMS的底层实现完全一致，然而现实中的DBMS针对SQL有各种各样的扩展，有比较微妙的差别。作者的意思应该是，本文抓到了其他方法抓不到的bug。

39. Gauntlet: Finding Bugs in Compilers for Programmable Packet Processing

本文针对P4的编译器寻找bug。P4是一个领域特定语言（DSL），用来实现可编程NIC和交换机。本文的核心idea是观察P4和C这种通用语言的区别，然后对症下药，提出了几个适合P4的debug方法，叫做Gauntlet。Gauntlet已经合入了P4的官方集成pipeline。

40. Aragog: Scalable Runtime Verification of Shardable Networked Systems

这篇文章似乎要用runtime verification的方式捉network function的bug。前面的第13篇论文提到过network function的概念。该方法是相对于static verification来说的，作者认为随着NF越变越复杂，static方法已经不好用了，所以作者提出了一个runtime方法。由于本文长句子很多，比较难读，还涉及很多我不了解的概念，就不仔细读了。

41. Automated Reasoning and Detection of Specious Configuration in Large Systems with Symbolic Execution

很多软件都支持大量的自定义参数，使用户有更大的定制空间，例如 MySQL 是一个拥有超过300个自定义参数的大型系统。不过有时候错误的配置会带来性能损失，甚至是软件故障。以往有很多捕捉引起软件故障的“无效配置”，但本文着重于寻找那些不足以引起故障、却会严重影响性能的配置，我自己称之为“垃圾配置”。

当前的捕捉办法主要是运维人员根据经验手动做一些测试，然后根据一些指标（例如吞吐量）判断是否存在垃圾配置，但这种方法并不十分有效，因为有些配置只有在特定的条件下才表现得很差，例如与特定的参数、输入、运行环境相关。例如，文中举了一个MySQL AUTOCOMMIT的例子，当系统负荷不大时，打开AUTOCOMMIT并不会明显地降低性能，但是系统很忙的时候就会很明显。

作者发现，这些垃圾配置拖慢性能的根本原因，在于它们引导代码走向了更慢的执行路径。因此，本文提出了一套叫做Violet的分析工具，使用符号执行（symbolic execution）对程序进行静态分析，为配置们生成一个“性能影响模型”（performance impact model）。用户使用软件时，Violet会根据模型检查其配置是否合理。如果发现了可疑配置，则会向用户报告潜在的风险。

42. Testing Configuration Changes in Context to Prevent Production Failures

本文又是一个寻找配置bug的成果，不过和上一篇的程序分析思路不同，它的主要方法是建立更完善的测试。作者观察到，配置bug很少由typo引起（因为一般都有review和validation流程），其根本原因常常是与配置相关的代码写错，或者配置了一个看上去有效却不合理的值（这与上一篇的论点有点像）。如果只看配置更改的diff本身，是定位不到这些bug的。

本文提出的 ctest 工具不仅测试配置本身，还测试与之相关的代码；它在选取测试参数时，会参考实际应用场景下的值，而不是随机选取；它可以根据配置diff，选择性地测试某次更新的配置。此外，它还能将以往的测试用例转化成自己的用例。

Scheduling

43. Providing SLOs for Resource-Harvesting VMs in Cloud Platforms

云计算服务商为了利用多余的计算资源，常常低价提供低优先级的“spot VM”，等更高优先级的VM需要资源时再把它们回收。这虽然能够提升资源的利用率，但存在一些问题。首先，一个较大的spot VM可能会因为仅仅要腾出一点点资源而被整个回收，这是很不合理的，如果使用多个小VM，又会带来额外的创建和维护VM的开销。其次，spot VM并不能充分利用所有的多余资源，所以利用率依然有提升空间。

本文观察了Microsoft Azure多余资源的情况，发现它们随时间涨落，有充分的利用空间。于是本文提出了Harvest VM来改进spot VM。Harvest VM一开始拥有“最低需求”的资源，但它会根据系统的多余资源扩张或收缩自己的资源，只有当系统需要用到自己“最低需求”的资源时它才会被释放。为了给用户更清晰的预估，本文还为Harvest VM配备了SLO。用户给定自己要创建多少个Harvest VM以及每个VM的最低资源，由后台预测出它们不同时间段内的存活率并告知用户，例如一小时后会剩下60%、一天后会剩下40%、一周后会剩下20%，等等。这个预测过程是由机器学习实现的（又是一个AI for system）。

Harvest VM目前只支持CPU资源的动态利用。

44. The CacheLib Caching Engine: Design and Experiences at Scale

大型Web服务依赖缓存系统来提升性能，例如在Facebook，CDN缓存满足了70%的请求。

Facebook有很多个独立的缓存系统，例如CDN cache、key-value cache、social-graph cache、media cache。每个cache系统都是针对某种资源专门设计的，因此架构各不相同，需要单独维护。随着缓存系统越来越复杂，维护成本也越来越高，产生了大量冗余代码（简称屎山要塌了？），于是CacheLib应运而生。CacheLib是一个专门为缓存而写的C++ library，它提供了一套公共的缓存功能，例如驱除策略、缓存索引、稳定性优化。有了CacheLib，不同的缓存系统可以共享它们的缓存策略，并且大大简化了代码。

在开发CacheLib的过程中，作者也总结了一些有价值的发现。

  1. 缓存系统并非越专一化越好，使用通用的CacheLib反而能利用其他缓存系统的优点；
  2. 高效缓存需要的工作集比我们想象的大。以往的研究都假设缓存对象的popularity满足alpha=0.9的Zipf分布，于是以为DRAM能在大部分情况下满足需要，而忽略了对flash memory缓存的研究。

还有其他关于实际应用中的cache的论述，参见论文的前三节。虽然看不太懂，但我感觉这是一篇总结了大量现实数据和经验的深度好文。

45. Twine: A Unified Cluster Management System for Shared Infrastructure

这篇文章讲infra-structure的，太抽象了，我看不懂。。。。。。

46. FIRM: An Intelligent Fine-Grained Resource Management Framework for SLO-Oriented Microservices

现在很多Web服务都是由多个“微服务”（microservice）组成的，每个微服务运行在容器里，只提供一项特定的功能，然后通过通信机制协同工作。比起以前将多个进程绑定在一个容器里的整体服务架构，微服务更容易更新、缩放，使用更加灵活。例如，整体型服务中的一环负载过重时，必须扩大整个服务的规模；而某个微服务负载过重时，只需要扩大这个微服务的规模。

微服务有时候无法满足SLO对响应延迟的限制，这一般是因为某一关键服务的负载出现峰值，或者计算资源不足。传统的解决办法有“overprovisioning”、“recurrent provisioning”、“autoscaling”，但是它们有两个缺点。第一，没有充分multiplex每种资源，无法检测出所有资源的短缺；第二，制作策略的过程耗时耗力，而且不能适应系统整体随时间的变化。

本文提出了FIRM框架，它能检测出是哪个微服务的实例导致了超时，以及为该服务制定降低延迟的策略（例如分配更多资源、增加实例数）。这两个关键功能分别由不同的机器学习模型实现。检测超时的是一个SVM模型，制定策略的是一个增强学习（RL）模型。FIRM通过在系统中人为制造高负载来训练它们。

47. Building Scalable and Flexible Cluster Managers Using Declarative Programming

现在的数据中心由Kubernetes、DRS、Openstack这样的集群管理器支持，它们需要管理容器的部署。管理器对部署方式有一些规定，例如硬性的“每个容器至少要有多少磁盘空间”、软性的“使容器尽可能分散在不同的机器上”。为了满足这些规定，管理器需要提前计算好的部署方式，而这往往涉及复杂的算法问题。尽管如此，现在的管理器依然使用 custom, system-specific best-effort heuristics，这对于其开发者来说是一场灾难。随着新规定的引入，开发者需要解决非常困难的组合优化问题，导致部署算法的开发成本极高。

以Kubernetes为例，它将待部署容器排成一个队列，然后逐个使用“greedy, best-effort heuristic”计算部署策略。它首先选出所有符合硬性规定的机器，然后给它们符合软性规定的程度打分，最后为该容器选择得分最高的机器。这种做法有很多问题：

  • 无法保证选中最佳的机器。在多个机器上部署多个容器，其本质上是一个 NP-hard 的多维背包问题，无法用贪心算法得到最好的结果。而当问题规模较大时，Kubernetes不得不限制备选机器的数量。
  • 不支持全局的容器再分配。例如A、B容器之间有anti-affinity，给某机器分配A容器可能会挤走B容器，此时需要为B容器寻找新的机器，但Kubernetes并不支持这一功能。
  • 代码实现非常复杂：这种调度算法流程很长、跨度很大、条件分支很多，因此开发难度很大，而且写出的代码往往是“铁板一块”动不得，可扩展性很差。

本文提出了 Declarative Cluster Managers (DCM)，它与典型的集群管理器截然不同。它将集群状态存储在关系数据库，然后用户使用SQL指定要采用的部署规定。DCM的编译器将用户的SQL语句合成一个程序（encoder），该程序会从数据库获取集群状态，并计算出满足用户要求的部署策略。encoder将集群状态和部署规定编码为一个优化模型（相当于更加一般的数学问题），然后使用专门的工具“constraint solver”（例如ILP算法）解出部署策略。这样，DCM兼具可规模性、可扩展性，并且能做出高质量的决策。

  • 可规模性：Can scale to problem sizes in large clusters (e.g., 53% improved p99 placement latency in a 500-node cluster over the heavily optimized Kubernetes scheduler).
  • 高质量决策：constraint solver能保证算出最佳结果
  • 可扩展性：DCM的集群状态、对部署规定的描述、以及算法逻辑高度模块化，使得加入新部署规定、支持新型容器变得更加简单

本人18年在百度实习的时候恰好碰到过类似的问题，同样是把很多实例部署到集群上，同样是背包问题的变种。当时也想过用数学方法求解，不过实力有限无法实施，没想到今天能在OSDI的论文上看到正式的系统性的解法。

48. Protean: VM Allocation Service at Scale

本文介绍了Microsoft Azure的VM分配器Protean。Azure的服务规模非常大，几百万台物理机遍布世界各地，500多种不同的VM满足各种用户的需求。要在合理的时间内为用户的每个请求做好分配，需要一个健壮的、高扩展性的（便于适应新特性）、灵活的（可运用于各种场景）、高性能的（即使是1%的资源碎片也会造成每年100万美元的浪费）分配器。

本文不仅提出了Protean，还总结了Azure workload的规律。Protean正是按照这些规律设计的，例如作者发现Azure常常遇到重复的请求，甚至有80%的请求是连续重复的，所以Protean会缓存请求的处理结果，大大提升了性能。

本文经常强调自己的大规模，我只能说，云服务这块还是大公司拿捏得死死的，其他机构根本没有这么多实操经验。

Machine Learning 2

49. Ansor: Generating High-Performance Tensor Programs for Deep Learning

本文讲了一个高效寻找“tensor program”的方法。tensor program是一种自动生成的tensor运算符，主要靠搜索不同的优化组合得到。

妈的，看不懂，而且实在没啥兴趣。深度学习模型是黑盒也就算了，连优化方法都要靠搜？

50. RAMMER: Enabling Holistic Deep Learning Compiler Optimizations with rTasks

终于看到一篇北大的论文了，泪目。

现在DNN计算方式一般分为两层，上层“inter-operator parallelism”把模型看作一个由operator组成的图（data flow graph，DFG），每个operator都是DFG的节点，数据的流向是边；下层“intra-operator parallelism”是利用硬件加速的手段使单个operator并行计算。这两层计算的scheduler一般是分开的，例如inter-operator scheduler只关注哪些operator可以并行计算，然后将它们分配到不同的加速设备上，而设备上的intra-operator scheduler只关注如何利用自己的加速机制，使某个operator用最快的速度完成计算。作者指出：

  1. 运行时的动态调度会给计算带来大量额外开销。调度由CPU完成，模型计算由GPU、FPGA等专用设备完成，随着后者的性能不断提升，调度占用的时间比例越来越大，影响了总体性能。例如，inter-operator scheduler会消耗16%-55%的时间在调度上，并且batch size越小，调度占用的时间越长；intra-operator scheduler也会降低GPU的利用率。
  2. 分层的scheduler不能获得最佳的并行状态。例如A、B两个operator是并行的，A的可并行性很高，而B的可并行性比较差。其中A先被上层的scheduler分配到了某个GPU上，所以为A分配了全部的并行线路。此时，上层scheduler也将B分配到了同一个GPU，但由于A已经占用了所有线路，所以B只能等待A完成后才能开始计算。由于B的可并行性较低，它并不能利用GPU的全部线路。如果scheduler能提前看到A、B的需求，那么它其实可以为B预留一些线路，这样就能达到更好的并行效果。

为了解决上述问题，本文提出了一个新的深度学习编译器RAMMER。它统一了上下两层的scheduler，利用静态的编译信息为调度节省了很多不必要的重复计算。此外，它抽象了底层硬件，因此可以应用在绝大部分并行计算设备上。

51. A Tensor Compiler for Unified Machine Learning Prediction Serving

“传统ML”是区分于DNN的机器学习方式，它的模型使用scikit-learn、Pandas等框架，这些框架为了适配不同的底层，需要为每种底层编写operator的实现，这导致了大量的重复性工作。例如所有框架一共有 NN 种operator，运行在 MM 种环境里，就需要 M×NM \times N 种实现。与之相比，DNN的计算都可以抽象为tensor的转换，因此深度学习的框架只需要用tensor operator实现框架层的operator，再由底层硬件实现每种tensor operator即可。假如tensor operator有K种，所有框架总共就只需要 M×K+K×NM \times K + K \times N 种实现。

本文提出了HUMMINGBIRD，它创新性地将传统ML的operator转换成了tensor operator，然后使用并行计算领域已经比较成熟的infra来进行模型的inference。虽然训练传统ML模型依然需要使用传统的框架，但模型一经训练完毕，就可以与训练方式脱钩。实验结果证明，这不仅提升了inference的性能，还加强了传统ML模型inference的跨平台兼容性。

52. Retiarii: A Deep Learning Exploratory-Training Framework

这篇好像是AutoML领域的啊……实在超出我的知识范围了。

个人理解，这篇文章提出了一个高效的模型探索方式。它一改之前“大量训练+人工筛选”的方式，采用“基准模型+变化样式”的组合，使模型在训练的过程中半自动化地调整自身。

53. KungFu: Making Training in Distributed Machine Learning Adaptive

ML训练时必须提前设置好一大批参数，例如与模型相关的超参数、与训练系统相关的系统参数，tune起来很麻烦，而且训练期间不能变动。但实际上一些参数需要动态变化才能收到更好的效果，例如学习率、batch size、训练的worker个数。本文的KungFu是一个“distributed ML training library”，可以在训练过程中动态地调节各种参数。本文的三大贡献是：1. Expressing Adaptation Policies; 2. Making training monitoring efficient; 3. Distributed mechanism for adapting parameters。

Hardware

54. FVM: FPGA-assisted Virtual Device Emulation for Fast, Scalable, and Flexible Storage Virtualization

不太懂硬件……本文好像是提供了一种利用了FPGA辅助的虚拟存储机制，相比纯硬件和纯软件的虚拟存储更有优势。

55. hXDP: Efficient Software Packet Processing on FPGA NICs

又是一个关于FPGA的，先跳过吧，一大堆缩写根本看不懂。

56. Do OS abstractions make sense on FPGAs?

我也不知道。

57. Assise: Performance and Availability via Client-local NVM in a Distributed File System

非易失性内存（non-volatile memory，NVM）是指当电流关掉后，所存储的数据不会消失的存储器。目前分布式文件系统的常用范式是由server存储所有文件，client的内存相当于这些文件的缓存。这种设计简化了数据管理，但是cache miss的代价很大，不能利用好NVM的性能。所以本文提出了分布式文件系统Assise，能充分发挥client-local的文件系统。

58. Persistent State Machines for Recoverable In-memory Storage Systems with NVRam

在数据量越来越大的今天，分布式系统的各个部件性能越来越高，只有in-memory的存储系统能跟得上，但是它最大的缺点是易失性。有些系统引入了persistence机制提高系统的稳定性，但也带来了额外的性能负担。这一问题有望通过非易失性内存（Persistent Memory，PM）解决，但PM系统还需要“crash consistency”，即保证系统崩溃后仍然能维持其性质。这又需要所有操作都具有“failure atomicity”，例如释放内存和更新指针必须同时成功或失败，否则会导致野指针的问题。failure atomicity让PM系统变得非常复杂和精巧，但即便如此，它的性能还是比不上in-memory系统。本文针对以上问题提出了Persimmon，“a PM-based system that converts existing in-memory distributed storage systems into durable, crash-consistent versions with low overhead and minimal code changes”。

59. AGAMOTTO: How Persistent is your Persistent Memory Application?

本文专门解决PM系统的测试问题，由于我见都没见过PM系统，就不深入了。

Security

60. Orchard: Differentially Private Analytics at Scale

我对用户隐私的话题很感兴趣，差分隐私算法也很有趣，但是一些关键的句子我看不懂。

本文主要探讨如何高效而安全地使用用户数据，提出了Orchard系统：“We present a system called Orchard that can automatically perform these steps for a large variety of queries. Orchard accepts centralized queries written in an existing query language, transforms them into distributed queries that can be answered at scale, and then executes these queries using a generalization of the CaT mechanism from Honeycrisp.”

61. Achieving 100Gbps Intrusion Prevention on a Single Server

Intrusion Detection and Prevention Systems (IDS/IPS) 面临着一个问题：网络流量太大，连接数太多，现有的硬件和软件不足以支撑。但本文提到的FPGA、SmartNIC我都不懂，不细看了。

62. DORY: An Encrypted Search System with Distributed Trust

云端存储服务为了安全起见，会把服务器上的用户文件加密，然后把密钥放在用户本地。然而为了用户的方便，服务商还需提供在线搜索的功能，所以“searchable encryption”成为了一个研究课题，如何让用户在服务器上搜索加密过的内容，又不造成安全隐患？攻击者虽然看不到文件的具体内容，但他可以观察其访问模式。举个例子：攻击者给Alice发送一封只含有单词“flu”的邮件，如果服务器上的index 924（我还不太清楚这个index具体指什么）更新了，那么攻击者就能知道924对应着单词“flu”。如果攻击者以此法穷举所有单词，那么Alice之后收到邮件时，攻击者就能根据index的更新读出所有内容。

当然，有一种叫做Oblivious RAM的技术，可以隐藏RAM的访问模式，然而作者认为其成本过高，不够实用。

本文提出了DORY (Decentralized Oblivious Retrieval sYstem), an encrypted-search system that splits trust to meet the real-world efficiency and trust requirements summarized above (and detailed in §2). DORY ensures that an attacker who cannot compromise every trust domain does not learn search access patterns.

63. SafetyPin: Encrypted Backups with Human-Memorable Secrets

前言：安全不止是加密、网络、软件，分布式的“安全系统”也是重要的组成部分。

云端备份虽有加密，但真正的密钥往往不是直接交给用户保管，而是用易于记忆的PIN来认证用户。为了防止PIN轻易被猜出来，现代的备份系统都使用了 hardware-security modules (HSMs)。用户设备上保存着经HSM加密的密钥（不是PIN），以及PIN的hash值，供HSM识别身份。为了更好地容错，设备上会同时存放由几个不同的HSM加密的密钥，只要通过任何一个HSM的认证都可以。这一系统存在许多问题：攻击者只需要hack掉一个HSM，就能获得许多用户的备份密钥，而且该系统很难检测到攻击痕迹，例如攻击者真的猜出了某用户的PIN，该用户也不会发现。

本文的SafetyPin仍然是基于PIN的备份系统，但是安全性更强。如果攻击者猜不出PIN，那么他必须能够hack一定数量的HSM，并且这些HSM的具体位置是隐藏的（在系统后台由PIN决定），攻击者无法得知。作者称之为“location-hiding encryption”。其他安全性质暂不详述。

64. Efficiently Mitigating Transient Execution Attacks using the Unmapped Speculation Contract

Transient execution CPU vulnerabilities are vulnerabilities in a computer system in which a speculative execution optimization implemented in a microprocessor is exploited to leak secret data to an unauthorized party. The classic example is Spectre that gave its name to this kind of side-channel attack, but since January 2018 many different vulnerabilities have been identified.

本文说现在kernel防止transient execution的开销太大了，很影响性能，所以提出了新的解决办法“unmapped speculation contract”，大概的意思是将所有进程的内核空间分开，每个进程都不会映射其他进程的物理内存。本文主要介绍了USC的思路及其实现方法。

Clusters

65. Predictive and Adaptive Failure Mitigation to Avert Production Cloud VM Interruptions

Microsoft Azure团队又来结合实际经验投论文了。这次他们研究的问题是如何预测和避免VM的崩溃，而不是等崩溃后再应急处理。Narya is an end-to-end service with predictive and smart failure mitigation fully integrated in the Azure compute platform for its Virtual Machine (VM) host environment. The design goal of Narya is to prevent VM failures ahead of time and enhance the self-managing capability of the Azure compute platform for providing smooth VM experience to customers.

一说到“预测”，我心里就开始怀疑是不是又要搞AI for system。果不其然，Narya使用了强化学习：To address the limitation of rule-based prediction, Narya employs an additional learning-based predictor, which analyzes more signals and patterns during a larger time window.

66. Sundial: Fault-tolerant Clock Synchronization for Datacenters

Sundial大大缩短了数据中心不同节点之间的时钟同步偏差，提高了事务响应的延迟。Sundial provides ∼100ns time-uncertainty bound (ε) under failures including temperature-related, link, device and domain failures and reports ε to applications – two orders of magnitude better than current designs.

67. Fault-tolerant and Transactional Stateful Serverless Workflows

Serverless Functions，指的是用户可以直接在云计算平台定义一个函数，让平台完成计算资源的调度，无需关心服务器的具体细节。基本上来说，每当函数被调用时，平台都要创建一个临时的VM或容器，装载好运行环境，执行代码，然后将其释放。

一开始Serverless Functions是没有状态的，毕竟它原本的定位只是提供一个临时的计算，但是后来人们提出了Stateful Serverless Functions (SSFs)，尝试把运行时产生的数据存放到数据库里。然而这样做有个问题：如果某个VM在计算过程中挂了，下一个VM接替时，就可能再次改变状态。

如何能让SSF具有良好的容错性呢？于是本文提出了Beldi, a library and runtime system for writing and composing fault-tolerant and transactional stateful serverless functions。

68. Unearthing inter-job dependencies for better cluster scheduling

“任务间依赖”对集群调度的影响：现在有些集群是共享数据的（称为Data lakes），因此任务之间有可能形成依赖关系，但是目前的调度系统并不会考虑这些，反而有可能产生“优先级倒挂”，即高优任务依赖低优任务。作者通过分析发现这种现象广泛存在于Microsoft Cosmos data lake，所以提出了Wing。The Wing dependency profiler analyzes job and data provenance logs to find hidden inter-job dependencies, characterizes them, and provides improved guidance to a cluster scheduler.

69. RackSched: A Microsecond-Scale Scheduler for Rack-Scale Computers

Head-of-line blocking (HOL blocking) in networking is a performance issue that occurs when a bunch of packets is blocked by the first packet in line. It can happen specially in input buffered network switches where out-of-order delivery of packets can occur.

为了满足越来越大的流量、越来越严格的SLO，多核处理已经不够了，需要多个机器同时处理（即机架式电脑）。本文提出的RackSched是第一个机架级、微妙级的调度器，能将整个机架抽象为一个对外的服务。要做到这一点并不容易，因为现代OS的调度几十个核就需要几微秒，但机架有几百、几千个核。如果简单地用单个核进行中心化调度，那么它会成为性能瓶颈。

70. Thunderbolt: Throughput-Optimized, Quality-of-Service-Aware Power Capping at Scale

数据中心的机房很花钱。2019年，五大公司（亚马逊、微软、谷歌、苹果、脸书）一共在数据中心上花了1200亿美元，这些钱主要都用来建造机房、冷却设备、供电，等等。于是有聪明人想到，虽然我一个机房的供电量有限，但并非所有机器都会同时用电，所以我可以多放点机器（power oversubscription），这样能少修好多机房，节约好多钱。万一真的超过额定功率了，就采取措施把用电量压下去（power capping），例如暂停低优先级任务、给CPU降频等各种操作。这些操作既要把用电量降下来，还要保证服务质量稳定。这对要求高吞吐量和低延迟的集群提出了挑战。

本文提出了Thunderbolt，a simple, robust, and hardware-agnostic power capping system, Thunderbolt, to address these challenges. It throttles the CPU shares of throughput-oriented workloads to slow them down “just enough” to keep power under specified budget, while leaving latency-sensitive tasks unaffected.

本文让我明白，除了CPU、内存、网络等计算资源，电力也是集群重要的有限资源，power oversubscription的概念也很有意思。

结语

70篇论文，最好当科学杂志一样看个乐，涨涨见识。如果强迫自己每一篇都细看，一是没有必要，二是劳心费神。