百度基础体系首席架构师林仕鼎分享系统架构领域论文精要

所谓“理论联系实际”、“万变不离其宗”。学术界的论文常常是指导工业界的圭臬，特别是在计算机相关科学领域：快速的发展，常常有赖于学术界几篇论文的突破。

百度基础体系首席架构师林仕鼎发布了一篇博客，指导大家如何阅读、学习系统架构领域的相关论文。

一开头，林仕鼎指出：

系统架构是一个工程和研究相结合的领域，既注重实践又依赖理论指导，入门容易但精通很难，有时候还要讲点悟性……要在此领域进阶，除了要不断设计并搭建实际系统，也要注意方法论和设计理念的学习和提炼。

对于工程师来说，到一定阶段后往往会遇到成长瓶颈。要突破此瓶颈，需要在所属技术领域更深入学习，了解本领域的问题本质、方法论与设计理念、发展历史等。

文中提到的东西虽然主要来自他 09 年的文章，没有包括近几年的工作，不过他认为：

其实也足够了，看 paper 是一个从少到多再到少的过程。对问题本质、背景和发展历史有大致了解，再辅以 hands-on 的实践（长期的真正的实践），足以摸到本领域的门径。

林仕鼎在文中一共提到 9 个领域：操作系统、虚拟机、系统设计、编程模型、分布式算法、覆盖网络和 P2P DHT、分布式系统、有争议的计算模型、调试。篇幅所限，本文只列举部分，全文请移步原文。

他首先分享了操作系统领域的相关论文：

Mach：相关介绍，论文链接。

传统的 kernel 实现中，对中断的响应是在一个“大函数”里实现的。称为大函数的原因是从中断的入口到出口都是同一个控制流，当有中断重入发生的时候，实现逻辑将变得非常复杂。大多数的 OS，如 UNIX，都采用这种 monolithic kernel architecture。

1985 年开始的 Mach 项目，提出了一种全新的 microkernel 结构，使得由于 70 年代 UNIX 的发展到了极致而觉得后续无枝可依的学术界顿时找到了兴奋点，也开始了沸沸扬扬的 monokernel 与 microkernel 的争论。

Exokernel：相关介绍，论文链接。

虽然 microkernel 的结构很好，但实际中并没有广泛应用，因为 performance 太差，而且大家逐渐发现 OS 的问题并不在于实现的复杂性，而更多在于如何提高 application 使用资源的灵活性。这也就是在 kernel extension（例如 loadable module in Linux）出现后，有关 OS kernel architecture 的争论就慢慢淡出人们视线的原因。

Exokernel 正是在这样的背景中出现的，它并不提供传统 OS 的 abstraction（process,virtual memory 等），而是专注于资源隔离与复用（resource isolation and multiplexing），由 MIT 提出。在 exokernel 之上，提供了一套库，著名的 libOS，用于实现各种 OS 的 interface。这样的结构为 application 提供了最大的灵活度，使不同的 application 可以或专注于调度公平性或响应实时性，或专注于提高资源使用效率以优化性能。以今天的眼光来看，exokernel 更像是一个 virtual machine monitor。

Singularity：相关介绍，论文链接。

Singularity 出现在 virus，spyware 取之不尽、杀之不绝的 21 世纪初期，由 Microsoft Research 提出。学术界和工业界都在讨论如何提供一个 trust-worthy computing 环境，如何使计算机系统更具有 manage-ability。

Singularity 认为要解决这些问题，底层系统必须提供硬件隔离，而以前人们都依赖的硬件 virtual memory 机制并无法提供高灵活性和良好性能。在.Net 和 Java 等 runtime 出现之后，一个软件级的解决方案成为可能。

Singularity 在 microkernel 的基础上，通过.Net 构建了一套 type-safed assembly 作为 ABI，同时规定了数据交换的 message passing 机制，从根本上防止了修改隔离数据的可能。再加上对应用的安全性检查，从而提供一个可控、可管理的操作系统。由于.Net CLR 的持续优化以及硬件的发展，加了这些检查后的 Singularity 在性能上的损失相对于它提供的这些良好特性，仍是可以接受的。

关于虚拟化技术，他重点提到如下几篇：

• 《 Scale and Performance in the Denali Isolation Kernel 》：为互联网服务而设计的应用层虚拟机，在普通机器上可运行数千个 VMs。其 VMM 基于 isolation kernel，提供隔离，但并不要求资源分配绝对公平，以此减少性能消耗。
• 《 The Entropia VirtualMachine for Desktop Grids 》 要统一利用公司内桌面机器资源来进行计算，需要对计算任务进行良好的包装，以保证不影响机器正常使用并与用户数据隔离。Entropia 就提供了这样的一个计算环境，基于 windows 实现了一个应用层虚拟机。其基本做法就是对计算任务所调用的 syscall 进行重定向以保证隔离。

在“系统设计”方面，他推荐的是： 《 Thirty Years Is Long Enough: Getting Beyond C 》：

C 可能是这个世界上最成功的编程语言，但其缺点也十分明显。比如不支持 thread，在今天高度并行的硬件结构中显得有点力不从心，而这方面则是 functional programming language 的长处，如何结合二者的优点，是一个很 promising 的领域。

编程模型的重点推荐是：《 SEDA: An Architecture for Well-Conditioned, Scalable Internet Services 》

Thread 不好，但 event 也没法解决所有问题，于是我们寻找一个结合的方法。SEDA 将应用拆分为多个 stage，不同 stage 通过 queue 相连接，同一个 stage 内可以启动多个 thread 来执行 queue 中的 event，并且可通过反馈来自动调整 thread 数量。

分布式算法：

• Byzantine （《 The ByzantineGenerals Problem 》）： 分布式系统中的错误各种各样，有出错就能停机的，有出错了拖后腿的，更严重的是出错了会做出恶意行为的，将会对系统造成严重影响。对于这类问题，Lamport 提出了 Byzantine failure model，对于一个由 3f+1 个冗余组成的状态机，只要叛变的冗余数量小于等于 f，整个状态机还能正常工作。
• Paxos （《 The part-time parliament 》,） 如何在一个异步的分布式环境中达成 consensus，这是分布式算法研究的最根本问题。Paxos 是这类算法的顶峰。

分布式系统方面的论文很多，他重点提到这一篇：《 Simulating Large-Scale P2P Systems with the WiDS Toolkit 》：

Distributed simulation 有意思的地方是 simulated protocol 是分布式的，而这个 simulation engine 本身也是分布式的。逻辑和物理的时间和事件交杂在系统中，需要仔细处理。

对于有争议的计算模型，他指出：

现在的软件系统已经复杂到了人已经无法掌握的程度，很多系统在发布时都仍然带着许多确定性 (deterministic) 或非确定性 (non-deterministic) 的 bug，只能不断打补丁。既然作为人类，不够精细的特性决定了我们无法把系统的 bug fix 干净，我们只能从其他角度入手研究一种让系统在这令人沮丧的环境中仍能工作的方法。这就像一个分布式系统，故障无法避免，我们选择让系统作为整体来提供高可靠性。

这个领域的论文主要研究内容都集中于：

• 如何正确保存状态；
• 如何捕捉错误并恢复状态；
• 在进行单元级恢复时，如何做到不影响整体。

在系统调试领域，林仕鼎推荐两篇论文：

• Black box debugging，《 Performance debugging for distributed systems of black boxes 》

对大型系统的 performance debugging 非常困难，因为里面的问题很多都是非确定性的，而且无法重现。只能通过对 log 的挖掘，找出配对的调用 / 消息以定位问题。

• 《 A Tool for Finding Copy-paste and Related Bugs in Operating System Code 》

很多人在重用代码的时候，都使用 copy-paste。但有时候简单的 CP 会带来严重的问题，例如局部变量的重名等。CP-miner 通过分析代码，建立语法树结构，然后 mine 出这类错误。

在文中，林仕鼎提出：

希望大家能通过对这些领域的了解和学习，掌握更多 system design principles，在自己的工作中得心应手，步入自由王国。