SOSP：计算机系统研究的风向标

SOSP （操作系统原理大会）自 1967 年创办以来，两年一届，已经有 50 个年头了。从 1969 年的 UNIX 系统到 21 世纪初的 MapReduce 、 BigTable 、 GFS ，系统领域一系列最有影响的工作都是发表在 SOSP 以及与它隔年举行的兄弟会议 OSDI 上。如果把 SOSP 和 OSDI 历年最具影响力（ Hall of Fame Award ）的论文汇集成册，就是大半本操作系统和分布式系统的教科书。作为系统领域的最高学术会议， SOSP 和 OSDI 每年只收录 30 至 40 篇高质量论文，因而能够在 SOSP 上发表论文是系统研究者的荣誉。

SOSP’17开幕式（图片来源：陈海波教授）

今年， SOSP 首次走出北美和欧洲来到中国上海，微软亚洲研究院副院长周礼栋博士和上海交通大学陈海波教授担任本届大会组委会主席，康奈尔大学 Lorenzo Alvisi 教授和密歇根大学 Peter Chen 教授担任程序委员会主席。本届 SOSP 会议创下了多项记录和第一：最多的注册参会者（ 850 位）；最多的赞助商数量和金额；首次提供会议直播和在线提问；首次设立了 AI Systems Workshop ，共商 AI 系统这个新生的重要应用；由微软研究院赞助，首次举办了 ACM 学生研究竞赛（ SRC ），吸引到 40 多篇投稿。

Ada Workshop参会人员合影

特别值得一 提的是，本届 S OSP大会首次在美国以外举办了Ada Workshop。微软亚洲研究院联合SOSP'17，邀请了国内外多位女性研究员，共同探讨计算机系统领域的未来。1987年，美国计算机科学家Anita Borg参加SOSP’87大会，惊讶地发现自己是唯一的女性科学家，由此三十年如一日地推动提升女性在计算机科研中的地位。如今，女性研究者在系统研究领域的声音已经举足轻重。本届SOSP唯一两次上台演讲的论文作者Kay Ousterhout就是UC Berkeley的女性博士毕业生，她的导师Sylvia Ratnasamy也是著名的女性科学家。我们希望Ada Workshop能助力系统研究领域的女性快速成长，激励更多心怀梦想的女性投身系统研究领域。

微软在SOSP’17大会上的展台

本届 SOSP 会议吸引了来自五大洲 23 个国家和地区的 232 篇投稿，录用论文 39 篇，投稿数量比上届增加了 30% ，录用率保持不变。微软不仅是 SOSP’17 的金牌赞助商，还发表了 8 篇主会论文（其中第一作者论文 4 篇），是发表论文最多的机构（第二名为麻省理工学院，发表论文 6 篇）。 SOSP 的 55 位审稿人都是学术上的泰山北斗，对审稿工作极其严肃认真，每篇投稿平均收到 4.9 个审稿意见，每个审稿意见平均长达 6.5 KB 。审稿结束后，程序委员会选出 76 篇论文，由 23 位主要审稿人经过两天的会议，选出最终录用的 39 篇论文。

北京航空航天大学与微软亚洲研究院联合培养的博士生肖文聪在AI Systems Workshop上展示研究成果。AI系统是微软亚洲研究院系统组的主要研究方向之一。

微软亚洲研究院实习生左格非在 SOSP 学生研究竞赛（ SRC ）上向 SIGOPS 主席 Robbert van Renesse 教授展示研究成果，该成果获得本科生组银牌。

39 篇主会论文采用 single track 形式满满地排在三天的 13 个 session 里，每篇论文都有 25 分钟的口头报告和提问，涵盖了寻找 bug 、可扩放性、网络计算、资源管理、操作系统内核、验证、系统修复、隐私、存储系统、安全、故障诊断、数据分析等多个领域。

下面我们将从让系统更高效、更可靠两个方面，与大家分享 SOSP 上的系统研究最新进展。

更高效的数据中心

摩尔定律对CPU而言基本上终结了，但对GPU、FPGA、TPU等定制化硬件而言仍在继续

如今的数据中心越来越像一个仓库规模的大型计算机，而不再是传统意义上松散的分布式系统。一方面， 硬件的计算与互联性能越来越高 ，例如网络的速度与 PCIe 总线、 DRAM 总线的速度已经相差不远了， RDMA 也可以把延迟从几百微秒降到几微秒； NVMe SSD 的延迟在 100 微秒量级，比机械硬盘延迟低了两个数量级， NVM （非易失性内存）更是把延迟进一步降低了两个数量级； GPU 、 FPGA 、 TPU 等加速设备的能效在很多场景下比 CPU 高两个数量级。然而传统操作系统访问外设、任务切换和多核同步的机制不能充分利用日新月异的硬件性能。

可编程的数据中心硬件，微软使用搭载了FPGA的可编程网卡作为数据中心加速平面

另一方面， 数据中心硬件的可编程性越来越强 。例如可编程交换机和可编程网卡使得网络除了转发数据包以外还可以做缓存、聚合和调度。 CPU 支持的硬件虚拟化、 PCIe 设备支持的 SR-IOV 虚拟化、 CPU 支持的 SGX 安全容器和 TSX 事务内存，提供了很多软件难以高效实现的隔离性，对多租户的云环境至关重要。 RDMA/RoCE 网卡、 GPU-Direct 、 NVMe Over Fabrics 等技术使设备间可以绕过 CPU 直接互联。如何在系统设计中充分利用这些可编程性成为了系统研究领域新的挑战。

分布式协调的性能瓶颈

本次 SOSP 上约有半数的论文致力于提高系统的性能。其中的一个常见性能瓶颈在于分布式协调，且节点数量越多瓶颈越严重。

分布式协调的第一个问题是 多个节点（服务器或者 CPU 核）负载不均衡，热点节点的最坏情况延迟（ tail latency ）较高 。一种解决方案是 用集中分配取代分布协调 。在键值存储（ key-value store ）系统中， NetCache 用可编程交换机作为缓存，实现了同一机柜内不同服务器间的负载均衡； KV-Direct 用可编程网卡作为缓存，可以实现同一服务器内不同 CPU 核间的负载均衡；另一种解决方案是 重新分配任务 。在网络处理系统中， ZygOS 在 IX 基础上构建（让网卡把任务分配到多个 CPU 核对应的不同队列），为了负载均衡，空闲的 CPU 核从其他核的队列里“窃取”任务（ work stealing ），并利用核间中断（ IPI ）降低响应包的处理延迟。

Linux文件系统的系统调用接口之间有很多共享内存冲突，ScaleFS消除了绝大部分冲突情况（图片来源：Scaling a file system to many cores using an operation log, SOSP’17）

分布式协调的第二个问题是 通信占用的带宽和延迟较高 。一种办法是 在语义上减少冲突 ，使各个节点互不干扰。在文件系统里， ScaleFS 基于可交换的文件系统 API （ sv6 ）来改进语义冲突较多的 LinuxAPI ，在内存里构建了一个核间无冲突的文件系统抽象，把各个核的文件系统操作记录到日志里，需要写盘的时候再合并不同核的日志；在数字货币系统中，为了高效实现互不信任的大量节点间的拜占庭共识，现有系统往往需要竞争“挖矿”来选出代表，而 Algorand 利用可验证随机函数（ VRF ），无需通信和大量计算就可选出公认的代表；在匿名通信系统中， Atom 系统通过对用户随机分组，无需全网所有节点互相通信，就能实现匿名广播，并以很高概率发现不诚实的节点。另一种减少分布式协调中通信开销的方法是 引入中心节点 。 Eris 利用网络上天然的中心（可编程交换机）来充当“顺序发号器”，用很低的开销实现了严格按序广播消息，进而大大简化分布式事务中的并发控制。为实现多核共享内存的并发控制， ffwd 把往常用原子操作实现的“抢锁”操作委托给一个 CPU 核来做协调，实现了更高的吞吐量。

系统接口抽象

系统领域有句名言， ” 计算机科学的任何问题都可以通过增加一个中间层来解决 ” 。 过于底层的接口会导致上层应用编程复杂，并发访问时还面临一致性问题 。例如， LITE 和 KV-Direct 两篇论文都指出， RDMA 的抽象并不完全适合数据中心应用。首先， RDMA 把缓冲区管理等底层信息暴露给用户，使得 RDMA 编程比 TCP socket 复杂很多，而且在连接较多的情况下，内存地址虚实映射表很容易导致网卡缓存溢出。为此， LITE 提出了一套更灵活易用的 API ，并把虚实映射的工作从网卡转移到 CPU 。其次，对于需要多次内存访问才能完成一次操作的数据结构，为了保证数据结构操作的原子性，多个客户端的并发写操作有较高的同步开销。为此 KV-Direct 把 RDMA 内存访问语义扩充到了键值操作的更高层语义，在服务器端的可编程网卡中实现了并发原子操作的乱序执行。

百度提出的USS，把socket语义翻译到RDMA。学术界也有多个类似工作。

然而抽象的层次不是越多越好。抽象层次过多时， 两个中间层可能做了重复的事情 ，反而不能充分利用底层硬件的性能。例如，在虚拟化环境中，每个虚拟机往往只做一件小事，此时虚拟机操作系统的调度、资源管理等抽象就显得多余。 Unikernel 的设计应运而生，把应用程序、运行库和内核中的驱动程序编译到一起，成为一个不分用户态和内核态的轻量级虚拟机；对于系统调用较为复杂或者需要多进程的应用，也可以用 Tinyx 为应用定制精简的 Linux “发行版”，仍然使用 Linux 内核，但启动速度快了很多。再如， SSD 上的键值存储可能组织成日志树（ log-structured tree ）的形式，而 SSD 底层的 FTL 也是类似的结构， NVMKV 就把两者合并，降低了写操作的开销。

为应用定制的Unikernel (右) 与Linux (左) 的比较（图片来源：Unikernels: The Rise of the Virtual Library Operating System, ACMQueue, Jan. 2014）

经典的抽象背后可能藏着很多不必要的功能和 不适合现代硬件架构的设计 。众所周知，新生的用户态网络协议栈和文件系统比 Linux 内核的实现高效得多。 ScaleFS 及其研究组之前的工作表明， Linux 的系统调用接口存在很多不利于多核扩放的设计。一篇在 64 KB 的嵌入式计算机（如 Yubikey 这样的 USB 令牌）上用 Rust 实现多进程、隔离和内存共享的论文说明现代操作系统的核心机制并不复杂。 NVMM （非易失性内存）的低访问延迟意味着应用需要 mmap 直接访问 NVMM （无需经典文件系统中的物理内存缓存）， 然而持久化存储的一致性又要求有快照和纠错功能，NOVA-Fortis文件系统就是为此设计。在论文Strata: A Cross Media File System中，作者也指出，传统文件系统把一个小的写操作放大成一整块的写操作，本是为机械硬盘和SSD设计的，但是对能高效执行小的随机写的NVM就浪费了。

即使 CPU 提供的抽象缺少某些功能，系统设计者也往往能够用软件来实现，而无需等待千呼万唤始出来的下一代硬件。例如， ARM v8.0 不支持嵌套虚拟化， NEVE 系统就采用半虚拟化（ para-virtualization ）的方法，修改内层虚拟机（ guest hypervisor ）的软件，模拟调用外层虚拟机的陷门（ trap ）。再如， Intel SGX 不支持动态分配内存，也存在操作系统通过缺页异常来侦测受保护代码行为的安全漏洞， Komodo 就用经过验证的软件取代 CPU 硬件实现的特权指令，实现更快和更灵活的演进。因此，高性能系统不意味着把软件里尽可能多的功能放进硬件，而是 找到软硬件之间合理的边界和接口 。

“万金油”系统

传统流式处理与数据库系统（左）与Wukong+S（右）的比较  (图片来源：Stateful Stream Querying over Fast-evolving Linked Data, SOSP’17)

除了解决现有系统的瓶颈，另一个系统研究的方向是构建 多种应用场景下都能高效工作的系统 。例如，流处理系统往往假定流计算函数是持续运行且无状态的，而数据库系统假定数据在查询执行过程中是不变的，这就很难在一个系统里同时做持续运行的流式查询和一次性的简单快照查询。 Wukong+S 系统在去年 OSDI 的 Wukong 系统基础上更进一步，把不随时间改变的状态和随时间改变的状态分开存储，使流式和一次性查询都可以高效完成。类似地，在 OLAP 与 OLTP 共存的数据库系统中，如果 OLAP 查询在一个快照上运行，获得的统计信息是陈旧的。获得 SOSP 学生研究竞赛研究生组金牌的 Xylem 系统把 OLAP 查询看成一个视图， OLTP 修改数据时增量更新视图，这样 OLAP 的结果就能反映数据库的最新状态。再如，流处理系统延迟低但恢复时间长，批处理系统能快速恢复但延迟高。 Drizzle 系统把数据处理周期和故障恢复周期解耦合，实现了低延迟、快速恢复的流处理。

更可靠的系统

SOSP开幕式上，会议主席对OSDI 2018关键词的建议

在生产环境中，相比性能，可靠性往往是更重要的考虑因素。今年 SOSP 开幕式上，会议主席列举了若干希望在明年 OSDI 上看到的词，其中包括了 enclave 、 specification 、 crash 、 bug 、 verification 和 testing 。提高软件可靠性有几个途径：找 bug 、形式化验证、故障诊断与恢复、虚拟化与隔离。

最佳论文DeepXplore自动生成的测试用例，第一行是原图，第二行改变光照条件；第三行是另一组原图，第四行增加干扰方块（图片来源：DeepXplore: Automated Whitebox Testing of Deep Learning Systems, SOSP’17）

今年 SOSP 的两篇最佳论文都在可靠性领域，一篇提出了深度神经网络的自动白盒测试问题，一篇提出了高效 Web 服务器审计问题，两篇论文提出的问题新颖且重要，并给出了漂亮的解法。 DeepXplore 指出，之前深度对抗网络生成的测试用例既不现实也不全面。类比软件测试代码覆盖率，提出了神经网络测试覆盖率的概念，一个神经网络输入如果使得某个神经元处于激活状态，就认为覆盖到了这个神经元。 DeepXplore 还提出了一种优化方法来生成测试用例最大化神经元覆盖率，在自动驾驶、恶意软件识别等神经网络中发现了很多被错误识别的边界情况。

另一篇最佳论文 旨在通过记录Web服务器的执行过程，发现异常的Web服务器行为（如程序被篡改，或不可信的服务提供商）。Web服务器对共享对象的访问和网络交互都被记录下来，这样一个请求的处理过程就是纯函数式的。用类似符号执行的方法把多个请求的处理过程合并起来推导，使得验证器的时间开销比重复执行每个请求大大降低。微软的另一篇论文CrystalNet也致力于高效仿真问题。传统网络仿真器在仿真大规模网络时速度缓慢，且很难仿真控制平面的软件，然而大多数网络故障的原因在于控制平面而非数据平面。为此微软使用虚拟机或容器来仿真交换机固件和网络控制器，模拟控制平面的行为，并仿真广域网上其他运营商的行为，使得数据中心规模的网络仿真成为可能。