以下原文：https://segmentfault.com/a/1190000023717761

大家好，我是今天的讲师田洪亮（花名：樱桃），蚂蚁集团技术专家，也是 Occlum 开源负责人。今天我和大家分享一下如何使用 Occlum 的轻松开发机密计算应用以及 Occlum 技术架构和特色。

前言

云计算、大数据、人工智能，我们正处在一个数据爆炸的时代。如何能够在享受和利用海量数据所产生的价值的同时，保证数据的安全和用户的隐私呢？这无异是一个用户、企业和监管部门共同关注的问题。

近年来兴起的机密计算（Confidential Computing），正是为了解决这个问题而来。利用可信执行环境（Trusted Execution Environments，简称 TEE）技术，机密计算使得数据始终保持加密和强隔离状态，从而确保了用户数据的安全和隐私。机密计算可以解决诸多应用场景中“信任”难题，比如多个不互信组织之间的数据融合与联合分析、区块链上的智能合约的机密性保护、公有云平台对外部或内部攻击的防御、高敏感信息（比如密码学材料、医疗档案等）的安全保护等等。

但是，机密计算底层依赖的 TEE 技术——比如目前最成熟的云端 TEE 技术 Intel SGX——也带来了额外的功能限制和兼容问题。这使得机密计算的开发者面领一个巨大的阻碍：应用开发难。

在本文中，我们会首先分析当前 SGX 应用开发者会遇到的各种挑战和痛点，然后介绍蚂蚁集团自研的开源 TEE OS 系统 Occlum 如何大幅降低 SGX 应用开发的门槛，真正做到人人都可以玩转机密计算。

为什么 SGX 应用开发难？

SGX 应用程序是一种基于划分的模型：在用户态的（不可信）应用程序（上图红色部分）可以嵌入 SGX TEE 保护的区域（上图绿色部分），被称为 Enclave。支持 SGX 的 Intel CPU 保证 Enclave 中的受保护内容是在内存中加密的，并且与外界强隔离。外界的代码如果想进入 Enclave 中执行其中的可信代码必须通过指定的入口点，后者可以实施访问控制和安全检查以保证 Enclave 无法被外界滥用。

由于 SGX 应用程序是基于这种划分的架构，应用开发者通常需要使用某种 SGX SDK，比如 Intel SGX SDK、Open Enclave SDK、Google Asylo 或 Apache Rust SGX SDK。但无论使用上述哪种 SDK，开发者会遭遇下面的开发困境：

• 必须将目标应用做二分：开发者需要决定哪些组件应该置于 Enclave 内部，哪些置于 Enclave 外部，以及双方如何通信。对于复杂的应用，确定高效、合理且安全的划分方案本身就是一件颇具挑战的工作，更不要说实施划分所需的工程量。
• 被限定在某个编程语言：无论使用上述哪种 SDK 开发，一个开发者都将被限定在该 SDK 所支持的语言，这通常意味着 C/C++（当使用 Intel SGX SDK、Open Enclave SDK 或 Google Asylo 时），而无法使用 Java、Python、Go 等更加友好的编程语言。
• 只能获得很有限的功能：处于硬件限制和安全考虑，Enclave 中是无法直接访问 Enclave 外的（不可信）OS 的。由于 Enclave 中缺乏 OS 的支持，各种 SDK 只能提供普通不可信环境下的一个很小的功能子集，这使得很多现有的软件库或工具都无法在 Enclave 中运行。

上述困境使得为 SGX 开发应用成为一件十分痛苦的事，制约了 SGX 和机密计算的普及度和接受度。

学会 Occlum 的“三板斧”

Occlum 是一款蚂蚁集团开源的 TEE OS，可以大幅降低 SGX 应用的开发门槛。那到底多低呢？只需要学会 Occlum的三条命令：new、build和run。本节我们以利用 Occlum 在 SGX 中运行一个 Hello World 程序为例进行说明。

这里有一个非常简单的 Hello World 程序。

$ cat hello_world.c
#include <stdio.h>

int main() {
    printf("Hello World!\n");
    return 0;
}

首先，我们用 Occlum 提供的 GCC 工具链（occlum-gcc）编译这个程序，并验证它在 Linux 上能正常工作。

$ occlum-gcc hello_world.c -o hello_world
$ ./hello_world
Hello World!

然后，我们为这个程序创建一个 Occlum 的实例目录（使用 occlum new 命令）。

$ occlum new occlum_hello
$ cd occlum_hello

该命令会创建一个名为 occlum_hello 的目录，并在该目录中准备一些必要的文件（如 Occlum.json 配置文件）子目录（如 image/）。

接下来，我们基于刚刚编译好的 hello_world 制作一个 Occlum 的 Enclave 文件和可信镜像（使用 occlum build 命令）。

$ cp ../hello_world image/bin
$ occlum build

最后，我们在 SGX 中运行 hello_world（使用 occlum run 命令）。

$ occlum run /bin/hello_world
Hello World!

更复杂的程序也可以用类似上面的流程通过 Occlum 移植进 SGX 中。用户无需理解 SGX 的二分编程模型，无需或只需少量修改应用代码，还可以自由选择编程语言（比如 Java、Python、Go 等）。使用 Occlum，应用开发者可以将宝贵的精力集中在编写应用上，而非为 SGX 做应用移植。

用起来像 Docker 的 TEE OS

在了解了 Occlum 的基本用法和体验之后，很自然地会好奇 Occlum 的技术原理：Occlum 的用户接口为什么这样设计？而简单接口背后的技术架构又是怎样的？本节就试图回答这些问题。

Occlum 的一个设计理念是 Enclave-as-a-Container。在云原生时代，容器至关重要，容器无处不在。容器最常见的实现方式是基于 Linux 的 cgroup 和 namespace（比如 Docker），但也有基于虚拟化的实现（比如 Kata）。我们观察到，TEE 或者 Enclave 也可以作为一种容器的实现手段。因此，为了传达这种理念，同时给用户提供一种熟悉的体验，我们特意将 Occlum 的用户接口设计成与 Docker 和 OCI 标准接近。除了前面提到的 new、build和run 三个命令，Occlum 还提供 start、exec、stop、kill 等命令，其语意与 Docker 同名命令类似。

简单的用户接口隐藏着复杂的实现细节。为了高层次地描述 Occlum 的技术原理，我们分可信的开发环境和不可信的部署环境两个视角来讨论。

在可信的开发环境（上图中的上半部分），用户使用 occlum build 命令打包和制作可信镜像，该可信镜像是利用 Merkel Hash Tree 来保证镜像在上传到不可信的部署环境之后，无法被攻击者篡改。可信镜像的内容是 Occlum 启动时所载入的 rootfs，组织结构与通常的 Unix 操作系统类似，具体内容由用户决定。

在不可信的部署环境（上图中的下半部分），用户使用 occlum run 命令启动一个新的 Occlum Enclave，该 Enclave 中的 Occlum TEE OS 会从可信镜像中载入并执行相应的应用程序。Occlum 向应用程序提供与 Linux 兼容的系统调用，因此应用程序无需修改（或只需少量修改）即可运行在 Enclave 中。应用程序的内存状态由 Enclave 保护，应用程序的文件 I/O 由 Occlum 做自动的加解密，因此可以同时保护应用在内存和外存中数据的机密性和完整性。

更高效、更强大、更安全和更多内容

除了提供类容器的、用户友好的接口以外，Occlum 还有三个主要特色：

• 高效多进程支持：Occlum 实现了一种轻量级的进程，相比此前最先进的开源 TEE OS（Graphene-SGX），进程启动提速 10-1000 倍，进程间通信的吞吐量提升 3 倍（详见我们的论文，链接见文末）；
• 强大文件系统：Occlum 支持多种文件系统，比如保护完整性的文件系统、保护机密性的文件系统、内存文件系统、主机文件系统等等，满足应用的各种文件 I/O 需求；
• 内存安全保障：作为全球首个使用 Rust 语言开发的 TEE OS，Occlum 极大降低了内存安全问题的几率（据统计，Linux 有 50% 的安全漏洞都与内存安全有关），因此更值得信赖；

下面的传送门提供了更多资料：

• Occlum 官方网站：https://occlum.io
• Occlum 项目地址：https://github.com/occlum/occlum
• Occlum 学术论文：https://arxiv.org/abs/2001.07450
• SOFAChannel 直播回顾视频：https://www.bilibili.com/video/BV1S5411a7gr

以下原文：当 Kubernetes 遇到机密计算，阿里巴巴如何保护容器内数据的安全？

8 月 26 日，我们发起了第 6 期 SIG Cloud-Provider-Alibaba 网研会直播。本次直播主要介绍了机密计算的概况， InclavareContainers 开源项目架构、已支持的功能和迭代计划，以及阿里云 ACK-TEE 的发展现状和规划。

本文汇集了此次直播完整视频回顾及资料下载，并整理了直播过程中收集的问题和解答，希望能够对大家有所帮助~阿里巴巴云原生公众号后台回复“826”即可下载相关 PPT。

直播视频回顾链接：https://v.qq.com/x/page/z3143a6agsg.html

机密计算简介

1. 应用容器安全现状

Portworx and Aqua Security 发布的《2019 容器接受度调研》报告显示，安全性成为了用户使用容器技术和业务上云面临的最大挑战，其中数据安全问题最为突出；根据 Risk Based Security 发布的数据泄露报告显示，2019 年数据泄露事件发生的数量和泄露的数据量与 2018 年相比均增加了 50%+。

2. 机密计算时代到来

数据在整个生命周期有三种状态：At-Rest（静态）、In-Transit（传输中）和 In-Use（使用中）。

• At-Rest 状态下，一般会把数据存放在硬盘、闪存或其他的存储设备中。保护 At-Rest 状态的数据有很多方法，比如对文件加密后再存放或者对存储设备加密；
• In-Transit 是指通过公网或私网把数据从一个地方传输到其他地方，用户可以在传输之前对文件加密或者采用安全的传输协议保证数据在传输中的安全，比如 HTTPS, SSL, TLS, FTPS 等；
• 然而 In-Use 状态的数据很长时间内都没有很好的保护的方法，直到机密计算的出现。

机密计算联盟给机密计算的定义是：机密计算是在一个基于硬件的可信执行环境（TEE）中保护数据执行计算。

机密计算的核心功能有：

• 保护 In-Use 数据的机密性：内存中的数据是被加密的，即便被攻击者窃取到内存数据也不会泄露数据；
• 保护 In-Use 数据的完整性：度量值保证了数据和代码的完整性，使用中有任何数据或代码的改动都会引起度量值的变化；
• 保护 In-Use 数据的安全性：相比普通应用，机密计算应用有更小的 TCB（Trusted Compute Base），意味着更小的攻击面，也意味着更安全。，以 Intel SGX 为例，除了 CPU 和可信应用自身以外，其他软硬件的访问都是被拒绝的，包括操作系统、Hypervisor 等。

在 2019 年 Gartner 的《计算基础设施成熟度曲线》中把机密计算也列入其中，虽然还处在早起阶段，这也说明机密计算开始逐步进入大家的视野并得到重视。

在 2020 年 Gartner的《云厂商本地安全解决方案比较》中，阿里云在 Trusted execution enviorments 中拿到一个 H，是因为 2020 年年初阿里云容器服务发布了机密计算产品 ACK-TEE，更多参考链接。

3. 机密计算业务场景

机密计算旨在保护敏感的代码和数据。业务场景有：区块链、秘钥管理、金融、AI、多方计算、数据租赁、边缘计算等。

以多方计算为例，不同用户或厂商之间相互共享数据以便计算挖掘出更大的数据经济价值，但不想把自己的数据泄露给对方。机密计算可以保护共享数据运行在受硬件保护的可信执行环境中，数据在内存中是加密的，从而保证数据不会被泄露。

4. 安全容器与机密计算的区别

除了机密计算外，还有一个与安全相关的概念-安全容器。阿里云在安全容器和机密计算领域都有布局，虽然二者都与安全相关，但它们的定位和应用场景是不同的。

安全容器的定位是隔离，把恶意应用隔离起来，防止它出去对其他应用搞破坏。主要的应用场景有三类：

• 不可信负载隔离
• 多租户应用隔离
• 性能和故障隔离

机密计算的定位是保护，保护应用不会被其他恶意应用进来窃取数据和搞破坏。应用场景是保护敏感代码和数据。

5. TEE 硬件平台

支持 TEE 的硬件平台主要有 3 个：Intel SGX、ARM TrustZone 和 AMD SEV，它们有不同的应用场景和实现方式：

• ARM TrustZone 把硬件资源分为安全世界和非安全世界两部分，所有需要保密的操作在安全世界执行，其余操作在非安全世界执行，安全世界和非安全世界通过一个名为 Monitor Mode 的模式进行转换。典型的应用场景有移动支付、数字钱包等；
• AMD 利用 SEV（AMD Secure Encrypted Virtualizationn），SME（AMD Secure Memory Encryption）和SEV-ES（Secure Encrypted Virtualization-Encrypted State）等技术实现虚拟机的 Guest 内存加密和安全隔离；
• Intel SGX 是 Intel 提供的一组指令，用于提高应用的代码和数据的安全性，用户可以把敏感数据放入到 Encalve 中，Enclave 是一种受保护的可信执行环境。

阿里云 ACK-TEE 和开源项目 Inclavare Containers 都是基于 Intel SGX 实现的机密计算。

6. Intel SGX 有更小的 TCB(Trusted Computing Base)

按照普通方式部署敏感应用，应用会依赖操作系统、VMM、硬件甚至是云厂商，TCB 非常大，面临的攻击面也非常大。只要 TCB 中只要有一处遭到攻击，应用都有数据泄露和破坏的风险。

而把敏感应用部署在 Intel SGX 的 TEE 中，TCB 只有 CPU 和 TEE 本身。一方面攻击面变得很小，另一方面 TEE 的安全机制也会使应用更安全。

7. 基于 Intel SGX 的可信应用开发和使用流程

Intel SGX 把应用分成了可信区和不可信区。用户可通过在 EDL（Enclave Definition Language）中定义可信区和不可信区以及用到的函数。这些函数用户可信区和不可信区之间的通信，分为 ECALL 和 OCALL。ECALL 用于不可信区访问可信区的数据，OCALL 用于可信区访问不可信区的数据。

基于 Intel SGX 的可信应用开发和使用流程如下：

• 申请秘钥：向 Intel 申请 SGX 相关的商业签名加密密钥；
• 安装环境：
  • 安装 Intel SGX 驱动
  • 安装 SGX SDK 和 PSW
  • 安装 AESM 服务
• 开发应用：
  • 明确应用可信区中须保护的代码和数据；
  • 编写 EDL 文件，明确 ECALL 和 OCALL 函数；
  • 编写可信区代码和非可信区代码；
• 编译构建
  • 使用 sgx_edger8r 基于 edl 文件生产用于 ECALL 的不可信区的代理函数和用于 OCALL 的可信代理函数；
  • 编译 Enclave动态链接库文件；
  • 签名上一步骤的 Enclave 动态链接库文件；
  • 编译应用，打包镜像。
• 用 Docker 运行容器

Inclavare Containers 保护敏感应用和数据

1. Inclavare Containers 的目标和价值

Inclavare，是 Enclave 一词的拉丁语词源，读音是 [ˈinklɑveə]。Enclave 指的是一种受保护的执行环境，能为其中的敏感和机密数据提供基于密钥学算法的强安全隔离，阻止不可信的实体访问用户的数字资产。

Inclavare Containers 是由阿里云操作系统安全团队和阿里云云原生容器服务团队主导，并联合了阿里经济体内多个研发团队（蚂蚁安全计算团队、云安全团队、语言 runtime 团队等）共同研发的面向机密计算场景的开源容器运行时技术栈。

当前机密计算在云原生场景中提供的技术，有很多缺陷和不足：

• 使用和开发成本都比较高；
• 容器化和对接 Kubernetes 的成本和复杂度高;
• 服务提供商提供的技术解决方案也相对单一

由于以上原因，非常不利用机密计算技术的普及和应用。而 Inclavare Containers 目的就是为业界提供一款面向机密计算领域的开源容器运行时引擎和安全架构，其价值在于：

• 抹平机密计算的高使用门槛，为用户提供与普通容器一致的使用体感；
• 基于处理器提供的多种硬件安全技术，为用户的工作负载提供多种不同的 Enclave 形态，在安全和成本之间提供更多的选择和灵活性。

2. Inclavare Containers 架构

在介绍 Inclavare Containers 架构之前，先介绍一下架构中各个组件的作用：

• kubelet：Kubernetes 集群中每个 Node 节点上运行的主要“节点代理”，负责与 Apiserver 的通信和管理节点上 Pod；
• Containerd：一个工业级标准的容器运行时，它强调简单性、健壮性和可移植性，Containerd 可以在宿主机中管理完整的容器生命周期：容器镜像的传输和存储、容器的执行和管理、存储和网络等；
• shim-rune：为容器运行时 rune 提供的 shim，主要负责管理容器的生命周期、把普通镜像转换成 TEE 镜像；
• rune：rune 是一个命令行工具，用于根据 OCI 规范在容器中生成和运行 Enclave。 rune 是在 runc 代码基础上开发的，既可以运行普通 runc 容器也可以运行 Enclave 容器；
• SGX LibOS：SGX LibOS 是为了让普通应用在不做或做很少更改的情况下，就能够在 Intel SGX 上运行起来。目前 Inclavare Containers 支持的 LibOS 有 Occlum，Graphene-SGX 正在对接中；
• 语言 Runtime：LibOS 对多语言的支持，比如 Occlum 中提供了 Golang 和 JDK 语言运行时；
• PAL-API：rune 和 LibOS 之间通信的接口。比如 pal_init 用于初始化 Enclave，pal_create_process 用于创建 Encalve。
• liberpal.so：是实现了 PAL-API 的 Linux 动态库，主要负责 rune 和 LibOS 的通信。

Inclavare Containers 的工作流程如下：

1. kubelet 向 Containerd 发起 CRI（Container Runtime Interface） 请求，比如请求创建一个 Pod
2. Containerd 中有一个 cri-containerd 的插件实现了 CRI 接口，Containerd 接收到请求后，把请求转给 shim-rune
3. shim-rune 既可以创建 runc 容器也可以创建 rune 容器。在创建 runc 和 rune 容器的处理流程也有差异：
   1. 创建 runc 容器：与创建普通 runc 容器过程完全一样，比如 Pod 的 pause 容器就是 runc 容器。
   2. 创建 rune 容器：利用 LibOS 把普通镜像转换成 TEE 镜像，rune 会在容器内创建 Enclave 并把应用运行在 Enclave 中。
4. rune 加载 liberpal.so，用于 rune 与 LibOS 的通信。
5. rune 把 Intel SGX 驱动载入容器内，并在容器内创建 1 号进程 init-runelet，再由 init-runelet 创建 Encalve。Enclave 是一个受 Intel SGX 保护的可信执行环境，Enclave 内包含：LibOS、语言 Runtime 和 应用本身。至此一个可信应用就运行起来了。

总结下来，Inclavare Containers 的特点有：

• 将 IntelSGX 与容器生态结合，兼容 OCIRuntime 和 OCI 镜像标准，实现 Enclave 容器形态；
• 与 Kubernetes 生态无缝整合；
• 基于 LibraryOS 技术，改善 IntelSGX 引入的约束条件所带来的兼容性问题；
• 提供对高级语言 Runtime 的支持，进一步提升兼容性；
• 定义通用的 EnclaveRuntimePALAPI 规范，构建 EnclaveRuntime 生态。

3. shim-rune 工作流程

shim-rune 包含两部分 Core 和 Carrier，它们的作用分别是：

• 管理容器生命周期
• 利用 LibOS 把普通容器转换为 TEE 镜像

shim-rune 的工作流程为：

1. 以容器镜像为输入，利用 LibOS 生成未签名的 Enclave 动态库；
2. 从 Enclave 动态库中导出签名材料；
3. 以签名材料为输入，请求签名服务进行签名，返回的内容有摘要文件和公钥；
4. 生成签名的动态库；
5. rune 加载签名的动态库，创建并启动 Enclave。

4. 客户端签名与服务端签名

Inclavare Containers 支持客户端签名和服务端签名两种工作方式，两种工作方式的差异如下：

相比客户端签名，服务端签名优点如下：

• 降低了开发者使用门槛，开发者不需要掌握 Intel SGX 的技术，按照 LibOS 要求构建出普通镜像即可；

注意：每种 LibOS 对普通镜像也有一定要求，比如 Occlum 只支持 musl libc 而不支持 glibc，所以 glibc 应用需要改造为 musl libc 应用之后才能在 Inclavare Containers 中运行起来。

• 用户不需要自己向 Intel 申请商业证书；
• 可运行在 Kubernetes 集群中。

5. 多团队共建合作

Inclavare Containers 项目是由多个团队共建合作而成的，各组件作用和团队分工如下：

• Occlum：由蚂蚁安全计算团队自研的基于 Intel SGX 技术并实现了内存安全的多进程 Library OS
• Graphene-SGX：基于 IntelSGX 技术并可以运行未经修改程序的开源 library OS
• Dragonwell：由阿里编译器团队定制的 LTS OpenJDK 发行版本
• sgx-device-plugin：由阿里云容器服务团队和蚂蚁安全计算团队针对 IntelSGX 联合开发的 Kubernetes Device Plugin
• AliyunLinux：由阿里 BaseOS 团队对 Inclavare Containers 提供全栈适配 aliyun linux 的支持

6. Inclavare Containers 开源项目

Inclavare Containers 是业界首个面向云原生的机密计算场景下的开源容器运行时技术栈，被阿里巴巴开源委员会评为重点开源项目。并且已经加入到官方机密计算 OCIRuntime 参考实现列表。

目前支持的功能有：

• 支持通过 K8s 和 Docker 启动 Enclave 容器
• 支持 Occlum 和 Graphene 两个主流 LibOS
• 支持 Java 和 Golang 语言 Runtime

该项目每个月月底进行一次发布，面向社区提供 CentOS 和 Ubuntu 的 binary release，并对内提供 AliyunLinux 发行版本。

7. Inclavare Containers 里程碑

8. 2020 年机密计算技术业产业

ACK-TEE

1. 简介

ACK-TEE 于 2019 年 9 月立项

功能：

• 对数字资产（算法、数据、代码）有强安全诉求的云用户提供基于硬件加密技术的可信执行环境(TEE)
• 降低机密计算技术的应用门槛
• 简化可信/机密应用的开发、交付和管理成本。

合作团队：阿里云容器服务团队、操作系统内核团队、云安全团队、蚂蚁安全团队和运行时语言团队

定位：云原生机密计算容器平台

使命：让天下没有难用的机密计算

产品原则：可信安全、易开发交付、标准开放、云原生

2. ACK-TEE 1.0

ACK-TEE 1.0 于 2020 年 1 月份上线

目标用户群体：原生 SGX 用户

全新 K8s 托管集群形态：机密计算专用集群，支持 Intel SGX1。

复用 Managed K8s 已有能力，包括各种云产品集成，K8s 集群运维能力，降低 K8s 集群的运维复杂度；

支持 EPC 加密内存的管理和调度，降低用户使用 SGX 设备的复杂度。

3. ACK-TEE 2.0

ACK-TEE2.0 计划在 2020 下半年上线

功能：支持原生应用在 TEE 中运行起来

目标用户：没有掌握机密计算技术但有数据安全需求的用户

方案

• 把普通镜像转换成 TEE 镜像后运行在 TEE 中；
• 通过 controller 提供安全可信的服务组件，如 KMS-Enclave-Plugin 等。

Q & A

Q1：这个依赖于 Intel 的芯片？为啥还需要单独找 Intel 申请密钥？ A1：Intel 芯片能保证应用执行在基于硬件的 Enclave （一种可信执行环境）中，保证应用的安全，但不能保证创建者一定是合法的。而在构建 Enclave 时我们会用 Intel 的秘钥对其签名，保证使用者是合法的。

Q2：Inclavare Containers 本质上是一个容器运行时实现吗？它能完全替代 Docker 容器运行时的场景吗？ A2：Inclavare Containers 是一个软件栈，它包含了 rune、shim-rune、runelet 等多个工具。其中 rune 是一个容器运行时，它是在 runc 代码基础上开发的。既可以运行普通 runc 容器，也可以跑有 Enclave 的容器。功能上说，可以替代 Docker 容器运行（runc）时，但最大的意义在于运行 Enclave 容器，保证代码和数据的安全。

Q3：应用的性能有多少影响，有做过类似的测试吗？ A3：Inclavare Containers 的重点是解决数据安全问题的。底层是基于 Intel SGX 的技术，目前 Intel SGX1 的 ECP 只有 128 MB 内存，相比原生容器应用的性能肯定会差很多。

Q4：所以理解下来，只把它用在最核心的需要 in-use 加密的地方，对吗？ A4：是的，保护 In-Use 代码和数据的安全是机密计算的最大价值。

Q5：ACK 现在有这个使用方法和 sample 吗？ A5：ACK 里有托管版“加密计算”，即分享里讲到的 ACK-TEE 1.0。但面向客户是 SGX 原生客户，需要客户自己基于 SGX 做应用改造和构造镜像。ACK-TEE 2.0 还在规划中，计划年底上线，会把 Inclavare Containers 的能力移植过来。我理解你是想要 ACK-TEE 2.0 的 sample 是吗？如果有兴趣，你可以按照 Inclavare Containers 0.3.0 的文档，搭建一个支持机密计算的 Kubernetes 集群。

以下原文：一篇了解TrustZone

这篇文章源于老板想了解TrustZone，要求我写一篇文章简单介绍TrustZone的原理。既然是给领导看的，只介绍原理哪里够，因此也添加了公司自己现有TEE环境的设计、实现和发展，也顺带加入了一些题外话。也是因为要给领导看，所以文章也不能涉及太多技术细节，包括TrustZone模块的详细设计以及示例代码等，所以只从总体上讲解了什么是TrustZone，TrustZone是如何实现安全隔离的、TrustZone相关的一些资源等。

如果你之前对TrustZone亦无所知，好吧，本文或许值得你一看；如果你已经了解了TrustZone，想知道更多的实现细节，抱歉，本文并不适合你，或许阅读ARM官方网站和文档以及各开源项目源码是更好的选择。

本文先交代TrustZone的安全背景，然后从较高层次展开介绍TrustZone的工作机制和原理（包括AXI总线架构、CPU、内存和中断模型，以及安全隔离机制），列举了几个常见ARM平台上的实现以及当前博通ARM平台上的状况，最后附带一些TrustZone相关的开源项目以及其他资源链接，全文约7500字。（由于涉及安全的原因，本文已经删掉介绍公司自己平台相关的部分）。

本文内容主要来源于网络，综合了网上的多篇文章，也加入了一些自己的理解，重新组织了文章结构使其便于理解。

主要参考的文章包括：

• TrustZone领域先行者
• TrustZone技术简介
• trust zone之我见
• 简谈高通Trustzone的实现

本文还参考了贴吧、知乎等部分文章，由于涉及较多，无法一一列举，再次对原作者的付出一并表示感谢！

除上面列举的资源外，本文主要资料参考了ARM官方对TrustZone的介绍，主要有：

• 网站 https://developer.arm.com/technologies/trustzone
• 文档 Building a Secure System using TrustZone Technology

事实上，前面多篇文章的细节也来源于官方文档。 本人不保留本文的所有权，欢迎转载本文，让更多的人来了解TrustZone。由于不想再次以类似 《TrustZone原理介绍》 一类作为标题，但又不知道以什么作为标题贴切，所以随手用了现在标题党的套路，抱歉。

1. TrustZone介绍

1.1 安全背景

在介绍TrustZone前有必要简单回顾下目前的一些安全手段。

CPU通过内存映射手段给每个进程营造一个单独的地址空间来隔离多个进程的代码和数据，通过内核空间和用户空间不同的特权级来隔离操作系统和用户进程的代码和数据。但由于内存中的代码和数据都是明文，容易被同处于内存中的其它应用偷窥，因此出现了扩展的安全模块，应用将加密数据送往安全模块，由安全模块处理完后再返回结果给相应的应用。

很多消费电子设备都使用扩展的安全模块来确保数据安全，目前常见的方式有：

1. 外部挂接硬件安全模块

   数据的处理交由外部的安全模块实现，这些模块能够保护自己的资源和密钥等数据的安全，如SIM卡、各种智能卡或连接到外部的硬件加解密模块等，但其同主芯片的通信线路暴露在外部，容易被监听破解。另外，通信的速率比较低。

2. 内部集成硬件安全模块

   将外部安全模块的功能集成到芯片内，因此一个芯片上至少有两个核：一个普通核和一个安全核。优点是核与核之间的通信在芯片内部实现，不再暴露在外面。缺点是核之间的通信速度仍然较低，而且单独的安全核性能有限，还会会占用SoC面积，成本较高。

1.2 TrustZone是个什么鬼？

TrustZone是ARM针对消费电子设备设计的一种硬件架构，其目的是为消费电子产品构建一个安全框架来抵御各种可能的攻击。

TrustZone在概念上将SoC的硬件和软件资源划分为安全(Secure World)和非安全(Normal World)两个世界，所有需要保密的操作在安全世界执行（如指纹识别、密码处理、数据加解密、安全认证等），其余操作在非安全世界执行（如用户操作系统、各种应用程序等），安全世界和非安全世界通过一个名为Monitor Mode的模式进行转换，如图1：

图1. ARM的安全世界和非安全世界

处理器架构上，TrustZone将每个物理核虚拟为两个核，一个非安全核（Non-secure Core, NS Core），运行非安全世界的代码；和另一个安全核（Secure Core），运行安全世界的代码。

两个虚拟的核以基于时间片的方式运行，根据需要实时占用物理核，并通过Monitor Mode在安全世界和非安全世界之间切换，类似同一CPU下的多应用程序环境，不同的是多应用程序环境下操作系统实现的是进程间切换，而Trustzone下的Monitor Mode实现了同一CPU上两个操作系统间的切换。

AMBA3 AXI(AMBA3 Advanced eXtensible Interface)系统总线作为TrustZone的基础架构设施，提供了安全世界和非安全世界的隔离机制，确保非安全核只能访问非安全世界的系统资源，而安全核能访问所有资源，因此安全世界的资源不会被非安全世界（或普通世界）所访问。

设计上，TrustZone并不是采用一刀切的方式让每个芯片厂家都使用同样的实现。总体上以AMBA3 AXI总线为基础，针对不同的应用场景设计了各种安全组件，芯片厂商根据具体的安全需求，选择不同的安全组件来构建他们的TrustZone实现。

其中主要的组件有：

• 必选组件
  • AMBA3 AXI总线，安全机制的基础设施
  • 虚拟化的ARM Core，虚拟安全和非安全核
  • TZPC (TrustZone Protection Controller)，根据需要控制外设的安全特性
  • TZASC (TrustZone Address Space Controller)，对内存进行安全和非安全区域划分和保护
• 可选组件
  • TZMA (TrustZone Memory Adapter)，片上ROM或RAM安全区域和非安全区域的划分和保护
  • AXI-to-APB bridge，桥接APB总线，配合TZPC使APB总线外设支持TrustZone安全特性

除了以上列出的组件外，还有诸如 Level 2 Cache Controller, DMA Controller, Generic Interrupt Controller等。

逻辑上，安全世界中，安全系统的OS提供统一的服务，针对不同的安全需求加载不同的安全应用TA(Trusted Application)。 例如：针对某具体DRM的TA，针对DTCP-IP的TA，针对HDCP 2.0验证的TA等。

图2是一个ARM官网对TrustZone介绍的应用示意图：

图2. 基于TrustZone的应用示意图

图中左边蓝色部分Rich OS Application Environment(REE)表示用户操作环境，可以运行各种应用，例如电视或手机的用户操作系统，图中右边绿色部分Trusted Execution Envrionment(TEE)表示系统的安全环境，运行Trusted OS，在此基础上执行可信任应用，包括身份验证、授权管理、DRM认证等，这部分隐藏在用户界面背后，独立于用户操作环境，为用户操作环境提供安全服务。

可信执行环境（TEE, Trusted Execution Environment）是Global Platform（GP）提出的概念。对应于TEE还有一个REE(Rich Execution Environment)概念，分别对应于安全世界(Secure World)和非安全世界(Non-secure World, Normal World)。

GlobalPlatform（GP）是跨行业的国际标准组织，致力于开发、制定并发布安全芯片的技术标准，以促进多应用产业环境的管理 及其安全、可互操作的业务部署。目标是创建一个标准化的基础架构, 加快安全应用程序及其关联资源的部署，如数据和密钥，同时保护安全应用程序及其关联资源免受软件方面的攻击。

2. TrustZone原理和设计

以下主要从TrustZone的总线设计，CPU设计(包括处理器模型、内存模型和中断模型)和安全隔离机制来介绍TrustZone的设计和工作原理。

2.1 总线设计

• 总线

设计上，TrustZone 在系统总线上针对每一个信道的读写增加了一个额外的控制信号位，这个控制位叫做Non-Secure或者NS位，是AMBA3 AXI总线针对TrustZone作出的最重要、最核心的扩展设计。

这个控制信号针对读和写分别叫做ARPORT[1]和AWPORT[1]：

• ARPROT[1]: 用于读操作(Read transaction), 低表示Secure, 高表示Non-Secure
• AWPROT[1]: 用于写操作(Write transaction), 低表示Secure，高表示Non-Secure

总线上的所有主设备(master)在发起新的操作(transaction)时会设置这些信号，总线或从设备(slave)上解析模块会对主设备发起的信号进行辨识，来确保主设备发起的操作在安全上没有违规。

例如：硬件设计上，所有非安全世界的主设备（Non-Secure masters）在操作时必须将信号的NS位置高，而NS位置高又使得其无法访问总线上安全世界的从设备（Secure Slaves），简单来说就是对非安全世界主设备发出的地址信号进行解码时在安全世界中找不到对应的从设备，从而导致操作失败。

NS控制信号在AMBA3 AXI总线规范中定义。可以将其看作为原有地址的扩展位，如果原有32为寻址，增加NS可以看成是33位寻址，其中一半的32位物理寻址位于安全世界，另一半32位物理寻址位于非安全世界。

当然，非安全世界的主设备尝试访问安全世界的从设备会引发访问错误，可能是SLVERR(slave error)或者DECERR(decode error)，具体的错误依赖于其访问外设的设计或系统总线的配置。

• 外设

在TrustZone出现前，ARM的外设基于AMBA2 APB (Advanced Peripheral Bus)总线协议，但是APB总线上不存在类似AXI总线上的NS控制位。为了兼容已经存在的APB总线设计，AMBA3规范中包含了AXI-to-APB bridge组件，这样就确保基于AMBA2 APB的外设同AMBA3 AXI的系统兼容。AXI-to-APB bridge负责管理APB总线设备的安全事宜，其会拒绝不合理的安全请求，保证这些请求不会被转发到相应的外设。

例如：新一代的芯片可以通过增加AXI-to-APB bridge组件来沿用上一代芯片的设计来使其外围设备可以支持TrustZone。

2.2 处理器设计

2.2.1 处理器模型

TrustZone中，每个物理处理器核被虚拟为一个安全核(Secure)和一个非安全核(Non-Secure)，安全核运行安全世界的代码，非安全核运行除安全世界外的其它代码。由于安全世界和非安全世界的代码采用时间片机制轮流运行在同一个物理核上，相应的节省了一个物理处理器核。

多核处理器上，也有建议说让将某一个或几个核指定为安全专用核，只运行安全系统代码来构建安全世界，其余核运行非安全代码，暂不清楚目前有哪些平台采用这个实现。

图3中，系统有4个物理核，每个又分为两个虚拟核（安全核和非安全核）的情况： 图3. 多核处理器上的安全核和非安全核

2.2.2 L1内存模型

• MMU

MMU是一种硬件电路，它包含两类部件，一类是分段部件，一类是分页部件，对应于内存管理的分段机制和分页机制。分段机制把一个逻辑地址转换为线性地址；接着，分页机制把一个线性地址转换为物理地址。

当CPU访问一个虚拟地址时，这个虚地址被送到MMU翻译，硬件首先把它和TLB中的所有条目同时(并行地)进行比较，如果它的虚页号在TLB中，并且访问没有违反保护位，它的页面会直接从TLB中取出而不去访问页表，从而提高地址转换的效率。

安全世界和非安全世界都有自己的虚拟MMU，各自管理物理地址的映射。实际上只是两个世界都有一份TTBR0、TTBR1、TTBCR寄存器，因此就会对应两个MMU表。

尽管MMU有两套，但TBL缓存硬件上只有一套，因此TBL对于两个世界来说是共享的，其通过NS位来标志其每一项具体属于哪一个世界。这样在两个世界间进行切换时不再需要重新刷新TLB，提高执行效率。

对于TLB共享并不是硬性规定的，部分芯片在两个世界间切换时可能通过硬件部分或全部刷新TLB。

• Cache

同TLB类似，硬件上两个世界共享一套Cache，具体的Cache数据属于哪一个世界也由其NS位指定，在世界间切换也不需要刷新Cache。

2.2.3 中断模型

基于TrustZone的处理器有三套异常向量表：

• 一套用于非安全世界，
• 一套用于安全世界，
• 还有一套用于Monitor模式。

与之前非TrustZone的处理器不同的是，这三套中断向量表的基地址在运行时可以通过CP15的寄存器VBAR(Vector Base Address Register)进行修改。

复位时，安全世界的中断向量表由处理器的输入信号VINITHI决定，没有设置时为0x00000000，有设置时为0xFFFF0000；非安全世界和Monitor模式的中断向量表默认没有设置，需要通过软件设置后才能使用。

默认情况下，IRQ和FIQ异常发生后系统直接进入Monitor模式，由于IRQ是绝大多数环境下最常见的中断源，因此ARM建议配置IRQ作为非安全世界的中断源，FIQ作为安全世界的中断源。这样配置有两个优点：

• 当处理器运行在非安全世界时，IRQ直接进入非安全世界的处理函数；如果处理器运行在安全世界，当IRQ发生时，会先进入到Monitor模式，然后跳到非安全世界的IRQ处理函数执行
• 仅将FIQ配置为安全世界的中断源，而IRQ保持不变，现有代码仅需做少量修改就可以满足

将IRQ设置为非安全世界的中断源时系统IRQ的切换见图4： 图4. IRQ作为非安全世界的中断源

2.2.4 系统模式切换

基于TrustZone的系统有三种状态，安全世界、非安全世界和用于二者切换的Monitor Mode。

协处理器CP15的寄存器SCR(Secure Configuration Register)有一个NS位用于指示当前处理器位于哪一个世界，该寄存器在非安全世界是不能访问的。当CPU处于Monitor Mode时，无论NS位是0还是1，处理器都是在安全世界运行代码。因此Monitor Mode下总是安全世界，但如果此时NS为1，访问CP15的其它寄存器获取到的是其在非安全世界的值。

非安全世界到Monitor模式的切换

处理器从非安全世界进入Monitor Mode的操作由系统严格控制，而且所有这些操作在Monitor Mode看来都属于异常。 从非安全世界到Monitor Mode的操作可通过以下方式触发：

• 软件执行SMC (Secure Monitor Call)指令
• 硬件异常机制的一个子集（换而言之，并非所有硬件异常都可以触发进入Monitor Mode），包括：
  • IRQ
  • FIQ
  • external Data Abort
  • external Prefetch Abort

Monitor Mode

Monitor Mode内执行的代码依赖于具体的实现，其功能类似于进程切换，不同的是这里是不同模式间CPU状态切换。

软件在Monitor Mode下先保存当前世界的状态，然后恢复下一个世界的状态。操作完成后以从异常返回的方式开始运行下一个世界的代码。

为什么安全模式和非安全模式不能直接切换？

非安全世界无权访问CP15的SCR寄存器，所以无法通过设置NS来直接切换到安全世界，只能先转换到Monitor Mode，再到安全世界。

如果软件运行在安全世界(非Monitor Mode)下，通过将CP15的NS位置1，安全世界可以直接跳转到非安全世界，由于此时CPU的流水线和寄存器还遗留了安全世界的数据和设置，非安全模式下的应用可以获取到这些数据，会有极大的安全风险。因此，只建议在Monitor Mode下通过设置NS位来切换到非安全模式。

综上，安全世界和非安全世界不存在直接的切换，所有切换操作都通过Monitor Mode来执行。

图5展现了安全世界和非安全世界之间的切换方式： 图5. 安全世界和非安全世界之间的切换

2.3 隔离机制

除了CPU执行时实行安全世界和非安全世界的隔离外，AMBA3 AXI总线提供了外设隔离的基础。

2.3.1 内存隔离机制

这里的内存指外部的DDR和片上的ROM以及SRAM，其隔离和保护通过总线组件TZASC和TZMA的设置来实现。

• TZASC (TrustZone Address Space Controller)
  • TZASC可以把外部DDR分成多个区域，每个区域可以单独配置为安全或非安全区域，非安全世界的代码和应用只能访问非安全区域。TZASC只能用于内存设备，不适合用于配置块设备，如Nand Flash。
• TZMA (TrustZone Memory Adapter)
  • TZMA可以把片上ROM和SRAM隔离出安全和非安全区域。TZMA最大可以将片上存储的低2MB配置为安全区域，其余部分配置为非安全区域。大小划分上，片上安全区域可以在芯片出厂前设置为固定大小，或运行时通过TZPC动态配置。TZMA使用上有些限制，其不适用于外部内存划分，而且也只能配置一个安全区域。

2.3.2 外设隔离机制

外设上，基于APB总线的设备不支持AXI总线的NS控制信号，所以AXI到APB总线需要AXI-to-APB bridge设备连接，除此之外，还需要TZPC (TrustZone Protection Controller) 来向APB总线上的设备提供类似AXI上的NS控制信号。

由于TZPC可以在运行时动态设置，这就决定了外设的安全特性是动态变化的，例如键盘平时可以作为非安全的输入设备，在输入密码时可以配置为安全设备，只允许安全世界访问。

2.3.3 隔离机制示意图

整个系统内存和外设隔离机制示意图见图6.

图6. 系统内存和外设隔离机制示意图

此图来源于网上，实际上TZPC还连接到片内的ROM/RAM设备上，用于配置片上存储的安全区域。

2.4 安全启动

AMBA3 AXI总线机制隔离出安全世界和非安全世界，但这是系统启动之后的事情。如何确保系统本身是安全的呢？这就涉及到系统启动的过程。

系统上电复位后，先从安全世界开始执行。安全世界会对非安全世界的bootloader进行验证，确保非安全世界执行的代码经过授权而没有被篡改过。然后非安全世界的bootloader会加载非安全世界的OS，完成整个系统的启动。

在非安全系统的bootloader加载OS时，仍然需要安全世界对OS的代码进行验证，确保没有被篡改。

图7是典型的TrustZone芯片的启动流程： 图7. 典型的TruestZone芯片启动流程

整个启动流程跟目前博通平台的安全启动原理基本一致，上电后安全芯片先启动，然后校验主芯片的bootloader，接下来bootloader提交系统的OS和文件系统给BSP进行校验，通过后加载主系统，确保主系统是安全的。

从上电复位开始的整个启动过程中，下一级的安全基于上一级的验证，最终依赖于芯片内置的OTP和安全硬件，逐级的验证构成了整个系统的信任链。信任链中的某一个环节被破坏，都会导致整个系统不安全。

3. 各家TrustZone实现

基于安全考虑，各家TrustZone都实行闭源，关于其实现细节的介绍都较少。

网上能找到少许关于高通方案上TrustZone的介绍：

• 安全世界 QSEE (Qualcomm Secure Execution Environment)
• 非安全世界 HLOS (High Level OS)

整个系统的架构如图8： 图8. 高通QSEE系统架构图

4. 其它

• ARMv8-A架构定义了四个异常等级，分别为EL0到EL3，其中数字越大代表特权(privilege)越大:

  • EL0: 无特权模式(unprivileged)
  • EL1: 操作系统内核模式(OS kernel mode)
  • EL2: 虚拟机监视器模式(Hypervisor mode)
  • EL3: TrustZone monitor mode

• TrustZone设计的相关方

  • ARM公司，定义TrustZone并实现硬件设计，TEE，TZAPI等
  • 芯片厂家，在具体芯片上实现TrustZone设计，包括三星、高通、MTK、TI、ST、华为等
  • 应用提供方，如DRM厂家和安全应用开发商，实现DRM、Playready、DTCP-IP和一些其它安全应用开发和认证

• Trust OS

  TEE环境下也要有一个操作系统，各家都有自己的Trustzone的操作系统，如Trustonic、高通的QSEE、国内的豆荚，还有开源的OPTEE等。在操作系统之上自然要有应用程序，在Trustzone里面我们一般叫TrustApp，当然TEE里面每个TrustApp都在一个沙盒里，互相之间是隔离的。比如说支付，就可以做成一个App（需要注意的是，和Normal World里面的App是两个概念），这个App简单来说就负责用私钥把网上发来的Challenge签个名，而这个签名的动作是需要在Secure World里面做的，避免恶意程序窃取到私钥来伪造签名。

  例如支付宝，其实支付宝也是只支持几个Trust OS的。同时，支付宝还定义了一系列标准，用来完成他的行为。

  现在的Trust OS大都会遵循GlobalPlatform的规范，这个组织致力于制定统一的Trust OS的API的接口规范，这样一个TrustApp只要用GP API，就可以方便移植到各个不同的TEE操作系统上了。

• Intel 平台的 SGX

  针对可信计算，类似ARM的TrustZone，Intel也针对x86平台提出了自己的安全架构SGX：

  Intel® Software Guard Extensions (Intel® SGX)

  https://software.intel.com/zh-cn/sgx-sdk

  SGX全称Intel Software Guard Extensions，顾名思义，其是对因特尔体系（IA）的一个扩展，用于增强软件的安全性。这种方式并不是识别和隔离平台上的所有恶意软件，而是将合法软件的安全操作封装在一个enclave中，保护其不受恶意软件的攻击，特权或者非特权的软件都无法访问enclave，也就是说，一旦软件和数据位于enclave中，即便操作系统或者和VMM（Hypervisor）也无法影响enclave里面的代码和数据。Enclave的安全边界只包含CPU和它自身。SGX创建的enclave也可以理解为一个可信执行环境TEE（Trusted Execution Environment）。不过其与ARM TrustZone（TZ）还是有一点小区别的，TZ中通过CPU划分为两个隔离环境（安全世界和正常世界），两者之间通过SMC指令通信；而SGX中一个CPU可以运行多个安全enclaves，并发执行亦可。

  简单来讲, Intel SGX最关键的优势在于将程序以外的software stack如OS和BIOS都排除在了TCB（Trusted Computing Base）以外。换句话说，就是在容器enclave里的code只信任自己和intel的CPU。

  网上有人是这样对比TrustZone和SGX的：

  Trustzone默认相信SecureOS，安全世界。SGX仅相信CPU core，通过SGX指令构建enclave容器。简单比喻，TEE是个公用大保险柜，什么东西都装进去，有漏洞的app可能也进去了，而且保险柜钥匙在管理员手上，必须相信管理员。SGX每个app有自己的保险柜，钥匙在自己手上

  SGX要进入工业界应用尚需时间，一个重要的问题是现在在intel发行的服务器芯片上还没有SGX，而SGX的重要应用就是在数据中心和云端的应用。

5. TrustZone开源项目

除了各家私有实现外，ARM也有不少开源项目，知名度较高的有：

• Arm Trusted Firmware
  • 基于ARMv8-A应用处理器，ARM官方提供了一个开源参考实现BL31。
  • https://github.com/ARM-software/arm-trusted-firmware
• Openvirtualization
  • 带有一些商业属性的开源项目，部分TEE实现只有商业版支持
  • http://www.openvirtualization.org/
• Op-Tee
  • Linaro 推出的开源TEE
  • https://github.com/OP-TEE

参考资料

• 2021 IBM 科技创新架构系列说 - 1月7日 - 混合云的安全典范：实现机密计算
• 从可信计算到机密计算
• 隐私保护计算技术研究-信通院.pdf 原处, 备份
• 机密计算: 一种基于硬件的、服务于应用和数据的可信执行计算形态
• Architecture
  • https://developer.arm.com/products/architecture
• TrustZone: https://developer.arm.com/technologies/trustzone
• Building a Secure System using TrustZone Technology
• ARM Trusted Firmware
  • https://github.com/ARM-software/arm-trusted-firmware
• Development of TEE and Secure Monitor Code
  • http://www.arm.com/products/security-on-arm/trustzone/tee-and-smc

云厂商的主机实例一般默认使用DHCP（动态主机设置协议，Dynamic Host Configuration Protocol）为弹性网卡自动分配IP地址，并获得IP地址租约到期时间。正常情况下，Linux 实例的dhclient进程会定期向DHCP服务器更新租约到期时间，以确保实例IP地址的可用性。以下情况可能引发Linux实例的DHCP服务出现异常，导致实例网络不通：

• 网卡配置文件存在错误
• 网卡对应的dhclient进程未运行

网卡配置文件和操作系统有关，这里暂不展开了，只讲dhclient的内容。在Linux实例中执行以下命令，检查对应网卡的dhclient进程运行状态。我的网卡名叫eth0。

ps aux | grep dhclient | grep eth0

系统无返回结果，说明dhclient进程未运行。执行如下命令启动：

dhclient eth0
# 或者
ifup eth0

参考资料

• Linux实例中本地网卡的DHCP配置检查与修复
• openstack镜像-关于通过clone虚拟机制作的镜像开机后网卡eth0启动失败的问题
• dhclient命令 – 动态获取或释放IP地址

原文：https://tech.meituan.com/2022/02/17/kubernetes-cloudnative-practices.html

导语

集群调度系统在企业数据中心中占有举足轻重的地位，随着集群规模与应用数量的不断激增，开发者处理业务问题的复杂度也显著提升。如何解决大规模集群管理的难题，设计优秀且合理的集群调度系统，做到保稳定，降成本，提效率？本文将会逐一进行解答。

集群调度系统介绍

集群调度系统，又被称为数据中心资源调度系统，普遍用来解决数据中心的资源管理和任务调度问题，它的目标是做到数据中心资源的有效利用，提升资源的利用率，并为业务方提供自动化的运维能力，降低服务的运维管理成本。工业界比较知名的集群调度系统，如开源的OpenStack、YARN、Mesos和Kubernetes等等，再如知名互联网公司Google的Borg、微软的Apollo、百度的Matrix、阿里巴巴的Fuxi和ASI。

集群调度系统作为各互联网公司核心的IaaS基础设施，在近十几年经历了多次架构演进。伴随着业务从单体架构向SOA（面向服务的架构）演进和微服务的发展，底层的IaaS设施也从物理机裸机时代逐步跨越到容器时代。虽然在演进过程中我们要处理的核心问题没有改变，但由于集群规模和应用数量的急剧膨胀，问题的复杂度也成指数级增长。本文将阐述大规模集群管理的挑战和集群调度系统的设计思路，并以美团集群调度系统落地实践为例，讲述通过打造多集群统一调度服务，持续提升资源的利用率，提供Kubernetes引擎服务赋能PaaS组件，为业务提供更好的计算服务体验等一系列云原生实践。

大规模集群管理的难题

众所周知，业务快速增长带来的是服务器规模和数据中心数量的暴增。对于开发者而言，在大规模集群调度系统的业务场景下，必须要解决的两个难题是：

1. 如何管理好数据中心大规模集群部署调度，特别是在跨数据中心场景下，如何实现资源的弹性和调度能力，在保障应用服务质量的前提下尽可能地提升资源的利用率，充分降低数据中心成本。
2. 如何改造底层基础设施，为业务方打造云原生操作系统，提升计算服务体验，实现应用的自动化容灾响应和部署升级等，减少业务方对底层资源管理的心智负担，让业务方可以更专注于业务本身。

运营大规模集群的挑战

为了在真实的生产环境解决上述两个难题，具体又可以再拆分成以下四个大规模集群运营管理挑战：

1. 如何解决用户多样化需求并快速响应。业务的调度需求和场景丰富且动态多变，作为集群调度系统这样的平台型服务，一方面需要能够快速交付功能，及时满足业务需求；另一方面还需要把平台打造得足够通用，将业务个性化需求抽象为可落地到平台的通用能力，并长期进行迭代。这非常考验平台服务团队的技术演进规划，因为一不小心，团队就会陷入无休止的业务功能开发中，虽然满足了业务需求，却会造成团队工作低水平重复的现象。
2. 如何提高在线应用数据中心的资源利用率且同时保障应用服务质量。资源调度一直是业界公认的难题，随着云计算市场快速发展，各云计算厂商不断加大对数据中心的投入。数据中心的资源使用率却非常低，更加剧了问题的严重性。Gartner调研发现全球数据中心服务器CPU利用率只有6%～12%，即使是亚马逊弹性计算云平台（EC2，Elastic Compute Cloud）也只有7%～17%的资源利用率，可见资源浪费有多严重。究其原因，在线应用对于资源利用率非常敏感，业界不得不预留额外资源以保障重要应用的服务质量（QoS，Qualityof Service）。集群调度系统需要在多应用混合运行时消除应用间的干扰，实现不同应用之间的资源隔离。
3. 如何为应用，特别是有状态应用提供实例异常自动处理，屏蔽机房差异，降低用户对底层的感知。随着服务应用规模的持续扩大，以及云计算市场的日趋成熟，分布式应用往往会配置在不同地域的数据中心，甚至是跨越不同的云环境，实现了多云或混合云部署。而集群调度系统需要为业务方提供统一的基础设施，实现混合多云架构，屏蔽底层的异构环境。同时降低应用运维管理的复杂性，提升应用的自动化程度，为业务提供更好的运维体验。
4. 如何解决单集群过大或集群数量过多，而带来的与集群管理相关的性能和稳定性风险。集群本身的生命周期管理复杂度会伴随集群规模和数量的增多而增大。以美团为例，我们所采取的两地多中心多集群方案，虽然在一定程度上规避了集群规模过大的隐患，解决了业务隔离性、地域延迟等问题。随着边缘集群场景和数据库等PaaS组件上云需求的出现，可以预见小集群数量将会有明显的上涨趋势。随之带来的是集群管理复杂度、监控配置成本、运维成本的明显增加，这时集群调度系统需要提供更有效的操作规范，并保证操作安全性、报警自愈和变更效率。

设计集群调度系统时的取舍

为了解决上述挑战，一个好的集群调度器将发挥关键作用。但现实中从来不存在一个完美的系统，所以在设计集群调度系统时，我们需要根据实际场景在几个矛盾中做出取舍：

1. 集群调度系统的系统吞吐量和调度质量。系统吞吐量是我们通常评估一个系统好坏很重要的标准，但在面向在线服务的集群调度系统里更重要的是调度质量。因为每次调度结果的影响是长期的（数天、数周甚至数月），非异常情况不会调整。所以如果调度结果错误，会直接导致服务时延增高。而调度质量越高则意味着需要考虑的计算约束条件越多，而且调度性能越差的话，系统吞吐量越低。
2. 集群调度系统的架构复杂度和可扩展性。系统对上层PaaS用户开放的功能和配置越多，通过支持更多功能来提升用户体验（比如支持应用资源抢占回收和应用实例异常自愈），也就意味着系统复杂度越高，各子系统越容易发生冲突。
3. 集群调度系统的可靠性和单集群规模。单集群规模越大，则可调度范围则越大，但对集群的可靠性挑战也越大，因为爆炸半径会增加，出现故障的影响也越大。单集群规模较小的情况下，虽然可以提升调度并发度，但可调度范围变小，调度失败概率变高，且集群管理复杂度变大。

目前，业内的集群调度系统按照架构区分，可以分为单体式调度器、两级调度器、共享状态调度器、分布式调度器和混合调度器这五种不同架构（见下图1），都是根据各自的场景需求做了不同的选择，没有绝对的好与坏。

图1 集群调度系统架构分类（摘自Malte Schwarzkopf - The evolution of cluster scheduler architectures）

• 单体式调度器使用复杂的调度算法结合集群的全局信息，计算出高质量的放置点，不过延迟较高。如Google的Borg系统、开源的Kubernetes系统。
• 两级调度器通过将资源调度和作业调度分离，解决单体式调度器的局限性。两级调度器允许根据特定的应用做不同的作业调度逻辑，且同时保持了不同作业之间共享集群资源的特性，可是无法实现高优先级应用的抢占。具有代表性的系统是Apache Mesos和Hadoop YARN。
• 共享状态调度器通过半分布式的方式来解决两级调度器的局限性，共享状态下的每个调度器都拥有一份集群状态的副本，且调度器独立对集群状态副本进行更新。一旦本地的状态副本发生变化，整个集群的状态信息就会被更新，但持续资源争抢会导致调度器性能下降。具有代表性的系统是Google的Omega和微软的Apollo。
• 分布式调度器使用较为简单的调度算法以实现针对大规模的高吞吐、低延迟并行任务放置，但由于调度算法较为简单并缺乏全局的资源使用视角，很难达到高质量的作业放置效果，代表性系统如加州大学的Sparrow。
• 混合调度器将工作负载分散到集中式和分布式组件上，对长时间运行的任务使用复杂算法，对短时间运行的任务则依赖于分布式布局。微软Mercury就采取了这种这种方案。

所以，如何评价一个调度系统的好坏，主要取决于实际的调度场景。以业内使用最广泛的YARN和Kubernetes为例，虽然两个系统都是通用资源调度器，实际上YARN专注于离线批处理短任务，Kubernetes专注于在线长时间运行的服务。除了架构设计和功能的不同（Kubernetes是单体式调度器，YARN是两级调度器），二者的设计理念和视角也不同。YARN更专注任务，关注资源复用，避免远程数据多次拷贝，目标是以更低成本、更高速度执行任务。Kubernetes更专注服务状态，关注错峰、服务画像、资源隔离，目标是保障服务质量。

美团集群调度系统演变之路

美团在落地容器化的过程中，根据业务场景需求，集群调度系统核心引擎由OpenStack转变为Kubernetes，并在2019年底完成了在线业务容器化覆盖率超过了98%的既定目标。但依然面临资源利用率低、运维成本高等问题：

• 集群整体的资源利用率不高。如CPU资源平均利用率还处于业内平均水平，相较于其他一线互联网公司差距较大。
• 有状态服务的容器化率程度不够，特别是MySQL、Elasticsearch等产品没有使用容器，业务运维成本和资源成本存在较大的优化空间。
• 从业务需求考虑，VM产品会长期存在，VM调度和容器调度是两套环境，导致团队虚拟化产品运维成本较高。

因此，我们决定开始对集群调度系统进行云原生改造。打造一个具有多集群管理和自动化运维能力、支持调度策略推荐和自助配置、提供云原生底层扩展能力，并在保障应用服务质量的前提下提升资源使用率的大规模高可用调度系统。核心工作围绕保稳定、降成本、提效率三大方向来构建调度系统。

• 保稳定：提升调度系统的健壮性、可观测性；降低系统各模块之间的耦合，减少复杂度；提升多集群管理平台的自动化运维能力；优化系统核心组件性能；确保大规模集群的可用性。
• 降成本：深度优化调度模型，打通集群调度和单机调度链路。从资源静态调度转向资源动态调度，引入离线业务容器，形成自由竞争与强控结合，在保障高优业务应用服务质量的前提下，提升资源使用率，降低IT成本。
• 提效率：支持用户自助调整调度策略，满足业务个性化需求，积极拥抱云原生领域，为PaaS组件提供包括编排、调度、跨集群、高可用等核心能力，提升运维效率。

图2 美团集群调度系统架构图

最终，美团集群调度系统架构按照领域划分为三层（见上图2），调度平台层、调度策略层、调度引擎层：

• 平台层负责业务接入，打通美团基础设施，封装原生接口和逻辑，提供容器管理接口（扩容、更新、重启、缩容）等功能。
• 策略层提供多集群统一调度能力，持续优化调度算法和策略，结合业务的服务等级和敏感资源等信息，通过服务分级提升CPU使用率和分配率。
• 引擎层提供Kubernetes服务，保障多个PaaS组件的云原生集群稳定性，并把通用能力下沉到编排引擎，降低业务云原生落地的接入成本。

通过精细化运营和产品功能打磨，我们一方面统一纳管了美团近百万的容器/虚拟机实例，另一方面将资源利用率从业内平均水平提升到了一流水平，同时还支撑了PaaS组件的容器化和云原生落地。

多集群统一调度：提升数据中心资源利用率

评估考核集群调度系统的好坏，资源利用率是最重要的指标之一。因此，虽然我们在2019年完成了容器化，不过容器化不是目的，只是手段。我们的目标是通过从VM技术栈切换到容器技术栈，为用户带来更多的收益，比如全面降低用户的计算成本。

而提升资源利用率受限于集群的个别热点宿主，一旦扩容，业务容器就有可能扩容到热点宿主，业务的性能指标如TP95耗时会出现波动，以至于我们只能像业界其他公司一样，通过增加资源冗余来保障服务质量。究其原因，Kubernetes调度引擎的分配方式仅简单考虑了Request/Limit Quota（Kubernetes为容器设定了请求值Request和约束值Limit，作为用户申请容器的资源配额），属于静态资源分配。导致不同宿主机虽然分配了同样多的资源，却因宿主机的服务差异性使得宿主机的资源利用率也存在较大的差异。

在学术界和工业界中，有两种常用的方法解决资源使用效率和应用服务质量之间的矛盾。第一种方法是通过高效的任务调度器在全局角度解决；第二种方法是通过单机资源管理手段来加强应用之间的资源隔离。不管是哪一种方法，都意味着我们需要全面掌握集群状态，所以我们做了三件事：

• 系统地建立了集群状态、宿主状态、服务状态的关联，并结合调度仿真平台，综合考虑了峰值利用率和平均利用率，实现了基于宿主历史负载和业务实时负载的预测和调度。
• 通过自研的动态负载调节系统和跨集群重调度系统，实现了集群调度和单机调度链路的联动，根据业务分级实现了不同资源池的服务质量保障策略。
• 经过三版迭代，实现了自有集群联邦服务，较好地解决了资源预占和状态数据同步问题，提升了集群间的调度并发度，实现了计算分离、集群映射、负载均衡和跨集群编排控制（见下图3）。

图3 集群联邦V3版本架构

集群联邦服务第三版本（图3）按照模块拆分为Proxy层和Worker层，独立部署：

• Proxy层会综合集群状态的因子及权重选择合适的集群进行调度，并选择合适的Worker分发请求。Proxy模块使用etcd做服务注册、选主和发现，Leader节点负责调度时预占任务，所有节点都能负责查询任务。
• Worker层对应处理一部分Cluster的查询请求，当某集群任务阻塞，可以快速扩容一台对应的Worker实例缓解问题。当单集群规模较大时会对应多个Worker实例，Proxy将调度请求分发给多个Worker实例处理，提升调度并发度，并减少每一个Worker的负载。

最终通过多集群统一调度，我们实现了从静态资源调度模型转向动态资源调度模型，从而降低了热点宿主比例，减少了资源碎片比例，保障了高优业务应用的服务质量，将在线业务集群的服务器CPU利用率均值提升了10个百分点。集群资源利用率均值计算方式：Sum(nodeA.cpu.当前使用核数 + nodeB.cpu.当前使用核数 + xxx) / Sum(nodeA.cpu.总核数 + nodeB.cpu.总核数 + xxx），一分钟一个点，当天所有值取平均。

调度引擎服务：赋能PaaS服务云原生落地

集群调度系统除了解决资源调度的问题之外，还解决服务使用计算资源的问题。正如《Software Engineering at Google》一书中提到的，集群调度系统作为Compute as a Service中关键组件之一，既要解决资源调度（从物理机拆解到CPU/Mem这样的资源维度）和资源竞争（解决“吵闹邻居”），还需要解决应用管理（实例自动化部署、环境监控、异常处理、保障服务实例数、确定业务需求资源量、不同服务种类等）。而且从某种程度上来说应用管理比资源调度更重要，因为这会直接影响业务的开发运维效率和服务容灾效果，毕竟互联网的人力成本比机器成本更高。

复杂的有状态应用的容器化一直是业界难题，因为这些不同场景下的分布式系统中通常维护了自己的状态机。当应用系统发生扩缩容或升级时，如何保证当前已有实例服务的可用性，以及如何保证它们之间的可连通性，是相较无状态应用复杂许多的棘手问题。虽然我们已经把无状态服务都容器化了，但我们还没有充分发挥出一个良好的集群调度系统的全部价值。如果要想管好计算资源，必须管理好服务的状态，做到资源和服务分离，提升服务韧性，而这也是Kubernetes引擎所擅长的。

我们基于美团优化定制的Kubernetes版本，打造了美团Kubernetes引擎服务MKE：

• 加强集群运维能力，完善了集群的自动化运维能力建设，包括集群自愈、报警体系、Event日志分析等，持续提升集群的可观测性。
• 竖立重点业务标杆，与几个重要的PaaS组件深入合作，针对用户的痛点如Sidecar升级管理、Operator灰度迭代、报警分离做快速优化，满足用户的诉求。
• 持续改进产品体验，持续优化Kubernetes引擎，除了支持用户使用自定义Operator之外，也提供了通用的调度和编排框架（见图4），帮助用户以更低的成本接入MKE，获得技术红利。

图4 美团Kubernetes引擎服务调度和编排框架

在我们推进云原生落地过程中，一个广泛被关注的问题是：基于Kubernetes云原生方式来管理有状态应用，相比于之前自己打造管理平台有什么区别？

对于这个问题，需要从问题根源——可运维性考虑：

• 基于Kubernetes意味着系统做到了闭环，不用担心两套系统经常出现的数据不一致问题。
• 异常响应可以做到毫秒级别，降低了系统的RTO（Recovery Time Objective，即恢复时间目标，主要指所能容忍的业务停止服务的最长时间，也是从灾难发生到业务系统恢复服务功能所需要的最短时间周期）。
• 系统运维复杂度也降低了，服务做到了自动化容灾。除了服务本身之外，服务依赖的配置和状态数据都可以一起恢复。
• 相比于之前各个PaaS组件“烟囱式”的管理平台，通用能力可以下沉到引擎服务，减少开发维护成本，而通过依托于引擎服务，可以屏蔽底层异构环境，实现跨数据中心和多云环境的服务管理。

未来展望：构建云原生操作系统

我们认为，云原生时代的集群管理，会从之前的管理硬件、资源等职能全面转变为以应用为中心的云原生操作系统。以此为目标，美团集群调度系统还需从以下几方面发力：

• 应用链路交付管理。随着业务规模和链路复杂度的增大，业务所依赖的PaaS组件和底层基础设施的运维复杂度早已超过普遍认知，对于刚接手项目的新人更是难上加难。所以我们需要支持业务通过声明式配置交付服务并实现自运维，给业务提供更好的运维体验，提升应用的可用性和可观测性，减少业务对底层资源管理的负担。
• 边缘计算解决方案。随着美团业务场景的不断丰富，业务对边缘计算节点的需求增长，比预期快很多。我们会参考业内最佳实践，形成适合在美团落地的边缘解决方案，尽快为有需求的服务提供边缘计算节点管理能力，实现云边端协同。
• 在离线混部能力建设。在线业务集群的资源利用率提升是有上限的，根据Google在论文《Borg: the Next Generation》中披露的2019年数据中心集群数据，刨去离线任务，在线任务的资源利用率仅为30%左右，这也说明了再往上提升风险较大，投入产出比不高。后续，美团集群调度系统将持续探索在离线混部，不过由于美团的离线机房相对独立，我们的实施路径会与业界的普遍方案有所不同，会先从在线服务和近实时任务的混部开始，完成底层能力的构建，再探索在线任务和离线任务的混部。

总结

美团集群调度系统在设计时，整体遵循合适原则，在满足业务基本需求的情况下，保证系统稳定后再逐步完善架构，提升性能和丰富功能。因此，我们选择了：

• 在系统吞吐量和调度质量中我们选择优先满足业务对系统的吞吐量需求，不过度追求单次调度质量，而是通过重调度调整完善。
• 在架构复杂度和可扩展性中我们选择降低系统各模块之间的耦合，减少系统复杂度，扩展功能必需可降级。
• 在可靠性和单集群规模中我们选择通过多集群统一调度来控制单集群规模，保障系统可靠性，减少爆炸半径。

未来，我们也会根据同样的逻辑持续优化迭代美团的集群调度系统，彻底转变为以应用为中心的云原生操作系统。

转自：https://zhuanlan.zhihu.com/p/478486523

https://tuna.moe/event/2022/high-frequency-trading/

一周前，莫涛组织了一场 “莫队交易赛”，我和十几位同学一起受邀参加。这是一场模拟高频交易的编程比赛，选手需要编写程序，在一个实时推送的数据流中找到符合规则的模式，然后不断优化，比谁的程序最快找到结果。这是一个完全内卷的游戏，因为每个数据点的总分是固定的，按照抢到的顺序分配，比较符合赢者通吃的原则，所以卷起来十分刺激。

在过去的一周里，我除了吃饭睡觉以外的大部分时间都在卷这个比赛。最终在 10 人决赛中以极其微弱的分差获得了能拿奖金的最后一位：第 6 名。比赛前天晚上 8 点结束，恰逢冬奥会闭幕。在闭幕式的过程中大家纷纷公布了自己的解法，看完以后我人都傻了：原来这是一个算法比赛，而我和几个高性能所的小伙伴都把它当成了高性能计算题来做，一个劲儿地卷性能，结果被人家几个算法优化轻松吊打。这场比赛带给我的收获和影响都非常大，我决定趁着这股热乎劲儿写一篇复盘总结，和大家分享一下一个系统开发者眼中的算法题是什么样的 。更为重要的是，反思一下自己为什么是这么想的。

本文的主要内容包括：

• 介绍比赛规则和题目
• 按时间顺序记录我对程序做的主要优化
• 介绍其他选手的解题思路，探讨系统优化的进一步方向
• 这场比赛带给我的收获与反思：系统思维和算法思维的区别

由于想写的东西太多，我打算把它拆成三篇边写边更：

• 上篇：主要包含比赛介绍和前半周我所做的优化
• 中篇：主要介绍后半周 SIMD 相关优化和决赛实况
• 下篇：主要介绍其他选手的精彩解法和自己的一些感悟

欢迎大家围观~

上篇：比赛介绍和前半周我所做的优化

文档， 备份

本次比赛的题目非常简单：给定一个无限长的数字流，从中找出长度不超过 N 的连续数字串，满足其组成的正整数是任意 M 的倍数。

以下是一组样例：

 # 样例输入
 123456789987654321......
 N=6
 M1=823
 M2=108
 # 样例输出
 12345  # 823 的倍数
 3456   # 108 的倍数
 9876   # 823 的倍数
 432    # 108 的倍数

选手需要通过 HTTP 协议访问指定 IP 地址获取输入、提交输出。输入输出服务器分别位于两个端口。向输入服务器发送 GET 请求，服务器会返回一个流，表示输入的数字流。提交答案需要向输出服务器发送 POST 请求，内容是找到的数字串，服务器会返回是否提交成功。官方提供了一个 Python 写的样例程序，演示如何参与这个比赛：

 import requests
 
 N = 256
 M = 20220217214410
 user = "user"
 passwd = "passwd"
 
 s = b""
 with requests.Session().get("http://172.1.1.119:10001", stream=True, headers=None) as fin:
     for c in fin.iter_content():
         s += c
         if len(s) > N:
             s = s[-N:]
         for i in range(len(s)):
             if s[i] != ord("0") and int(s[i:]) % M == 0:
                 requests.post(f"http://172.1.1.119:10002/submit?user={user}&passwd={passwd}", data=s[i:])
                 print("submit", s[i:].decode("ascii"))
 

看上去非常简单，是不是有点跃跃欲试了？！当我们运行程序提交答案后，可以在一个页面上看到自己和其它选手的提交情况：

最上面是输入的常数 N 和 M，这个我们后面再具体讨论。接下来是排行榜，展示了每位选手的分数和性能指标。前面几列 +8/+4/+2/+1 表示每个人获得了多少次对应分数。具体的计分规则是，对于每个合法数字串出现前后 5 秒内的提交：（注意这个“前后”很有意思）

• 第 1 名：+8
• 第 2-3 名：+4
• 第 4-6 名：+2
• 第 7-10 名：+1
• 之后的不得分

继续往后看，>5s/wrong/dup 都是异常提交情况，同样不得分。submit 是总提交次数，比赛中每次提交都有固定 -1 分的成本。所以如果卷不到前 10 位，还不如不提交，不然还扣分。接下来是所有提交延迟的统计指标，10%/50%/90%/99% 是分位数，mean/std 是平均值和标准差。在这个比赛中延迟分位数是最重要的性能指标，它决定了你的每次提交能卷过多少对手。可以看出最终的分数排名和 10%/50% 延迟分位数基本是正相关的。

最后一个关键指标是 ping，表示你的机器和服务器之间的网络延迟。服务器位于北京阿里云上。在资格赛中，选手自己找机器部署程序，通过公网访问服务器，ping 本身的延迟就高达 2-5 ms。此外，每位选手的机器算力不同，其实也不是公平竞争。所以资格赛出线的秘诀其实就是在阿里云上开奖开出一个低延迟的多核机器。到了决赛，官方为每位选手提供了统一的内网服务器（2vcpu 4GB 内存），ping 降低到 130±10us 的范围。所有人又回到了同一起跑线，此时比拼的就是程序本身的运行速度了。

在排行榜下面还公布了最近生成的答案和每位选手提交的时间点。这张图是决赛结束后的截下来的，可以看到竞争已经进入了 10us 级别，甚至有时 1us 的差别就能分出胜负，实在是太卷了！为了更直观地看出各位选手的内卷情况，官方还提供了最近一小时的分数增长曲线：

这张图是决赛刚刚开始半小时的赛况。由于每位选手的起跑时间不同，场上依然是一种你追我赶的局面。但是长期来看体现选手实力和排名的是曲线的增长速度，也就是相同时间内能够卷到多少分数。决赛开始几个小时后，场面就变得稳定下来：

这时候其实还是相对势均力敌的，曲线均匀分布意味着每个人都有一些机会抢到 +8 或 +4。到了决赛后期，真正的卷王会让你们知道什么叫赢者通吃、菜鸡互啄 。

看到这里，各位同学是不是已经摩拳擦掌、准备好一起卷翻天了？接下来我就带大家看看过去一周我是怎么（被）卷的。

比赛过程复盘

这里我回看了一下自己的 git log，按时间顺序以流水账的形式整理了一下做的每一步优化，主要是为了给自己留个记录。各位同学可以只看标题，然后选感兴趣的内容阅读，点击标题可以传送到代码。

按照类别索引：

• 算法优化：4 基本递推，7 猜 M4
• 计算优化：6 优化取模，8 定长整数，9 手动二分取模
• 系统优化：2 多线程，3 编译参数，5 提前 TCP 连接，10 避免 malloc，11 避免 async，12 低延迟服务器
• SIMD 优化：TODO

1. Rust 实现样例代码

我的程序是用 Rust 写的，一方面是因为我已经发誓下半辈子再也不写 C++，另一方面这也是我第一次写针对低时延的程序，想知道用 Rust 效果如何。所以第一步是把官方提供的 Python 样例代码改写成 Rust。

这里有两个需求需要用第三方库解决，一个是大整数运算，一个是 HTTP 客户端。在 Rust 中我分别使用了 num-bigint 和 reqwest 库。考虑到涉及到网络 IO，还同时引入了 futures 和 tokio 异步框架。

2. 多线程并行化

为了提高性能，第一步想到的最简单的方法是用多线程加速。注意到每添加一个数字后的计算任务是互相独立的，所以每次就创建一个协程出来。然后将底层的 tokio 改成多线程执行器，这样就能够自动利用上所有 CPU 核的算力了。我的 MacBook 有 6 核 12 线程，因此运行时间即可降低到 1/6 以下。此时每找到一个数，从收到消息到发出答案的延迟一般在 100ms-1s 之间。

3. 利用本机指令

Rust 默认的编译配置出于兼容性考虑，不会利用上本机 CPU 支持的全部指令集，这其中就包括非常强大的 AVX2 等高级向量指令。于是我修改编译配置 -C target-cpu=native ，让程序利用上本机支持的 AVX2 指令集。

为了测试效果，我还用 criterion 框架编写了两个 micro benchmark。实验表明 num-bigint 的大整数一次字符串解析时间是 1.6us，一次取模的时间是 1.0us。修改编译配置前后几乎没有差别，说明向量指令没有派上用场。这也可以理解，因为目前没有什么规整的数组运算，编译器的自动向量化不起作用。不过我还是用 objdump 看了一下生成的汇编，并搜索 “ymm”，结果还真发现了不少。然而仔细一看都是用来加速数据移动的，llvm 你可真是个小机灵鬼！

 100006e26: 0f 84 72 02 00 00           je     0x10000709e <__ZN88_$LT$hyper..client..dispatch..Envelope$LT$T$C$U$GT$$u20$as$u20$
 core..ops..drop..Drop$GT$4drop17h1f08c1f01b0c4845E+0x2ae>
 100006e2c: c5 fc 10 87 c0 00 00 00     vmovups 192(%rdi), %ymm0
 100006e34: c5 fc 11 85 60 fe ff ff     vmovups %ymm0, -416(%rbp)
 100006e3c: c5 fc 10 87 a0 00 00 00     vmovups 160(%rdi), %ymm0
 100006e44: c5 fc 11 85 40 fe ff ff     vmovups %ymm0, -448(%rbp)
 100006e4c: c5 fc 10 87 80 00 00 00     vmovups 128(%rdi), %ymm0
 100006e54: c5 fc 11 85 20 fe ff ff     vmovups %ymm0, -480(%rbp)

4. 算法优化1：基本递推

进一步还可以发现，由于每次取模的数都小于 10M，因此取模可以优化成最多 9 次减法。（事实上可以进一步降到 4 次，当时没有想到，见第 6 步优化）

重写完以后，单线程的平均延迟降低到了 90ms 左右。然后再次做多线程并行化，第一步是对每一个 M 并行，第二步是对每个 N 并行，将任务拆得足够细使得每个核的计算量尽量均衡。这样平均延迟降低到 20ms 左右。

看到这里各位 OI 选手可能已经开始豹笑了：折腾半天原来就写了个暴力啊。

5. 提前建立 TCP 连接

这时我发现，发送答案的时间已经成为了瓶颈，有将近 10ms。仔细一想，我是在要发送的时候才开始建立连接。HTTP 基于 TCP，TCP 建立连接需要三次握手，消耗 1.5 RTT 的时间，而我的 ping 就有 4.8ms，这开销可就大了。显然，我们可以预先建立好 TCP 连接，等算出答案后立刻发送，避免三次握手的延时。

但在实现的时候，我又被自己给坑了。因为一开始使用了 reqwest 库，而这个库是个 high-level 的封装，我没法控制让它建立连接和发送数据分开啊。于是我找到了它依赖的另一个更 low-level 的 HTTP 库：hyper。研究半天接口以后，实现了这样的逻辑：开一个协程循环做 TCP 握手——接收答案——发送，用一个 channel 连接计算协程和网络协程。看到自己写出了这种非常 async 的代码，我露出了满意的笑容。然后笑容逐渐僵硬——因为我发现答案发不出去了！

一开始我怀疑是网络问题，但随后我试着用 curl 发——正常，退回到上一个版本——也正常。这说明锅在新的库 hyper 头上！然而原来的 reqwest 底下也是 hyper 怎么就没事呢？一定是我用法不对！

为了搞清楚到底发生了什么，我打开了 Wireshark 抓了个包：

原来是发出的 POST 请求服务端不给回复了！那应该是 HTTP 头有问题，于是我又仔细看了看 HTTP 包的内容，发现 hyper low-level 接口发的包没有填 Host 等字段，手动填上以后的包是这样的：

结果依然没有回复！对比 curl 的包看一下，我发现有两处区别：一个是没有 User-Agent ，另外就是 key 首字母没有大写。于是我立刻上网集成学习了一下 HTTP 协议，得知 HTTP 头是大小写不敏感的。但是我不信邪，非得把它整成大写不可！接下来我对着 hyper 的源码折腾了几个小时，就是没办法发出正确的包。绝望之时，我开始想能不能绕过 hyper 自己发包，于是再次上网集成学习 HTTP……

突然之间，我悟了：md HTTP 就是个基于 TCP 的简单文本协议啊，你直接把 curl 发的包粘贴过来发 TCP 不就完了，用什么库？？？这一刻，我沉默了。我就知道自己当年没有好好学网络原理，早晚会为此付出代价。我怀着沉重的心情删掉 hyper，换上自己构造的 HTTP 头：

 const HEADER: &str = "POST /submit?user=omicron&passwd=y8J6IGKr HTTP/1.1\r\nHost: 47.95.111.217:10002\r\nUser-Agent: Go-http-client/1.1\r\nContent-Type: application/x-www-form-urlencoded\r\n";
 let content_length = format!("Content-Length: {}\r\n\r\n", body.len());
 let iov = [
     IoSlice::new(HEADER.as_bytes()),
     IoSlice::new(content_length.as_bytes()),
     IoSlice::new(&body),
 ];
 stream.write_vectored(&iov).await.unwrap();

还不忘秀一把零拷贝的 IO Vector 接口。终于，提交成功了，延迟降到 10ms。

6. 计算优化：递推乘加取模

在第 4 步中提到，

取模可以优化成 4 次减法，分别是 8M、4M、2M、M（或者两次 4M 也行）。注意到 M 是给定的常数，因此可以预先计算好这几个值。

更进一步，我们可以预先计算 [M, 2M, 3M, …, 9M]，然后在这个数组中二分查找，最多比较 4 次即可算出商，随后只需要 1 次减法即可算出余数。（在第 9 步中我们会利用 M 是常数的性质进一步优化这个计算）

7. 猜 M4

接下来，我把目光投向了隐藏数字 M4 上。这怎么猜呢？还记得排行榜下面的提交信息吗：

我们发现如果答案比较长，那么中间就会以 ..... 省略，如果比较短就可以显示全，这其中肯定有些是 M4 的倍数！所以，我们可以写一个脚本定期爬 board，通过正则表达式 \n[0-9]+\n 提取出所有完整的答案，然后依次模 M1/2/3。如果都不能整除，那说明它肯定能被 M4 整除。然后分别提取它（3,7,11）因子的个数，对所有数取最小值即可（最大公约数）。

悲催的是，我的 Python 脚本写错了。整数除法 x // 3，我写成了 x / 3，然后变成了浮点，后面结果全错了。动态类型一时爽，算错了你都不知道。更恐怖的是，后面很长时间我都没有发现这个错误，白白浪费了很多算力。因为在输入流中根本找不到能被错误 M4 整除的数，所以榜上看不出有错误提交。并且我还没在 log 中输出每一个数的类型，看不出异常。这个教训说明：一定要尽量详细地打 LOG！

8. 变长大整数转定长

找到 M4 以后，仔细观察这四个数的长度：

 M1 = 20220217214410
 M2 = 104648257118348370704723119
 M3 = 125000000000000140750000000000052207500000000006359661
 M4 = 10885732038215355481752285039386319187390558900925053798518152998488201

发现都不怎么长啊：M1 可以用 u64 放下，M2 可以用 u128 放下，M3、M4 可以用 u256 放下。

可能因为从样例程序一路改过来的缘故，在改成递推算法时竟然没有意识到其实并不需要高精度运算，用定长类型就够了。u64 和 u128 都是 Rust 内置的基本类型，其中 u128 会由编译器拆开放在两个 64 位寄存器中，由 compiler_builtin 库软件实现所有运算。但是 u256 就不支持了，于是我又上 docs.rs 搜索到一个定长整数运算库 primitive-types，分分钟换掉 num-bigint。

9. 计算优化2：手动展开二分比较取模

做完上一步之后我 perf 了一下程序：

发现开销最大的是一个叫 __umodti3 的函数，这个就是上面提到的编译器内置函数，用来计算 u128 % u128。可见取模运算是非常慢的！

在第 6 步优化中我们提到可以利用二分查找将取模优化成 4 次比较和 1 次减法。但是在数组中二分查找每一步都需要访问内存。虽然这个数据量很小，肯定能在 L1 Cache 中命中，但毕竟 CPU 执行访存指令还是比计算要慢不少的。回头看我们的数组 [M, 2M, …, 9M]，一共没几个数，所以干脆把整个二分比较的过程硬编码到代码中：

由于函数标记了内联，编译器知道传入的 M 是个常数，因此会自动做常数传播优化，最终生成如下指令：

可以看到编译器把每个常数都计算出来，然后塞到了 mov 指令里面！这样就避免了访问内存。更加亦可赛艇的是，由于 u128 需要拆成高低两个 u64 进行比较，只有在高位相等的情况下才需要比较低位，而高位相等是极其罕见的，因此低位比较几乎不会被执行（除了二分的最后一轮）。所以整个取模操作平均只需要 4 次 u64 比较 + 1 次 u128 减法即可完成，是非常高效的。同样的方式也可以应用到 u256 上面，平均是 7 次 u64 比较 + 1 次 u256 减法。

但是，这种将逻辑硬编码到大量分支中做法的也有它的问题，那就是难以扩展到 SIMD 并行化。在第 14 步优化中我们会讨论如何在 SIMD 中实现取模。

另外我还发现了一个很有趣的现象：对于 u64 % 常数 u64，编译器会将其优化成两次乘法：

我人肉反汇编了一下，算法大概是

其中 C1、C2、K 是三个魔法常数。感兴趣的同学可以打开 Python 验算一下：

 >>> m = 20220209192254
 >>> c1 = 0x6f5d238e7a7e04bf
 >>> c2 = 0x1263e262dd3e
 >>> x = m * 5 + 23333
 >>> x % m
 23333
 >>> x - ((x * c1) >> 107) * c2
 23333

看上去是利用了一些神奇的数学原理，哪位大佬可以解释一下嘛。

UPDATE：评论区有同学给出了答案

SuperSodaSea：【编译笔记】变量除以常量的优化（一）——无符号除法

Barrett Reductionen.wikipedia.org/wiki/Barrett_reduction

10. 避免动态内存分配和数据拷贝

在 perf 中我还发现了 malloc 占了 1% 左右的开销，于是我看了一下代码中哪里用到了动态内存分配。原来是在计算过程中我用了一个 VecDeque 也就是循环队列来维护最近 N 个数字，当发现答案后，将其拷贝到一个 Vec 的连续空间中。这一步也是不必要的，因为在循环数组中任意一个子区间只会由至多两个离散的 slices 组成，标准库中也提供了 VecDeque::as_slices API 来获取它们。所以，我们可以用两个 slices 来表示答案，然后通过 IO Vector 直接从 TCP 发出去。

这个优化不会对性能带来很大提高，但还是随手做了，因为实在是分秒必争啊。

11. 避免 async，使用阻塞 IO

由于我之前做的大部分都是面向高并发的工作，因此习惯性起手就是一个 async。然而稍微想想就会发现，异步模式是不适用于低时延场景的，因为一条 IO 路径可能会被拆成多段由不同的人执行，它们在交接时调度器会引入额外的延迟。

以 tokio 的 TcpStream 为例，它的 read 操作是个异步函数。如果此时服务器还没有发数据过来，read 系统调用会返回 WouldBlock 错误，导致上层协程挂起，并向后台 reactor 注册一个回调函数等待唤醒。当输入数据到达内核后，内核首先唤醒 epoll 线程，然后根据事件查表触发回调函数唤醒协程，随后还要等待调度器重新调度协程，才能开始执行真正的计算逻辑。而最原始的阻塞 read，当数据到达内核后就会立刻唤醒线程开始计算，延迟最低。

想明白这一点后，我返璞归真，把 tokio::net::TcpStream 换回了 std::net::TcpStream。

12. 获得低延迟服务器

到目前为止，我的程序一直是在我的 MacBook 上跑的，距离阿里云上的服务器有 5ms 的 ping 延时，而榜上最低的 ping 只有 1.8ms。

一跳一跳又一跳

此时我的平均计算延迟已经进入了 3ms 级别，感觉卷不动了，于是将希望寄托在了降低 ping 上面。此前我曾经尝试过在服务器所在的阿里云北京 H 区开服，但是开出来 ping 竟然有 4.6ms，十分不理解。后来我发现是交换机选错了，选成了 A 区。改成 H 区以后第一次就开出了一个 1.8ms 的服！后来我又先后尝试以同样的配置开服，但开出来 ping 都在 2ms 以上，再也没能复现第一次 SSR 的欧气。我的小伙伴们说他们甚至搞过 100 连抽，无一命中，还给阿里云送了不少银子。

氪金玩家

将程序迁移到服务器上后，曲线一下就卷上去了，总分排到了第四位。可以看到，排名靠前的基本都是抽到好机器的欧皇，这充分说明一个好的出生点是多么重要。这次比赛后，我对北京市内的网络延迟有了更加刻骨铭心的认识。

资格赛前的排行榜

下篇预告

到这里比赛进程已经过半，接下来是两天的资格赛和两天更加激烈的决赛。在后半周的时间里，我主要利用 Rust 的 SIMD 模块来对计算做进一步加速，在服务器 CPU AVX512 的加持下成效显著。

下篇文章我们来讨论一下 Rust 独特的可移植 SIMD 模块，以及如何用 SIMD 处理大整数的乘加和取模运算。欢迎关注~

中篇：SIMD 相关优化和决赛实况

上周我参加了一场莫队举办的高频交易模拟赛。这篇文章作为比赛复盘系列的第二篇，主要介绍一下使用 Rust 编写 SIMD 加速计算的技巧和经验。

上回说到，在前半周的比赛中，我拿着暴力递推算法一通常数优化，凭借刷出低延迟服务器的加持，成功卷到第四位进入资格赛。随着比赛正式打响，战况也愈发激烈：前两名遥遥领先，后面的紧追不舍，场面看似波澜不惊、实则暗流涌动。每隔一段时间就出现一条曲线突然上扬，被卷过的选手纷纷躺平的场面上演。

抽到了低延迟服务器后，Omicron 毒株开始起飞（雾）

当然也会有黑天鹅现象出现，比如第一名突然卷飞了。。。

为了不被对手卷走，各位选手八仙过海各显神通。赛场上陆续出现了大预言家，还有潜伏的 OS 专家开始着手研发专用内核：

大预言家

现在开始写操作系统还来得及！

这个时候，我思考了一番接下来的玩法：既然已经抽到了 1.8ms 的服务器，资格赛保住前 10 名晋级应该比较稳了，那么可以直接为决赛作准备。而决赛和资格赛的环境是很不一样的，资格赛中排名靠前的选手很有可能是用了更多核的算力，但是决赛只有 2vcpu，所以多线程的作用不大，主要比的是单核的算力。而我之前已经把单核计算优化到了汇编级别，进一步提升的空间很小，因此是时候开始用 SIMD 挖掘更多的单核算力了！

这里简单做一下科普：SIMD 全称 Single Instruction Multiple Data，即单指令流多数据流。是 CPU 中用单条指令对一组数据执行相同运算的一种并行计算技术。SIMD 技术很早就被应用到主流处理器当中。x86 系列处理器从上个世纪开始就逐步引入了 MMX/SSE/AVX 系列扩展指令集，以及相应的 mm/xmm/ymm/zmm 向量寄存器。目前，最新的 AVX512 指令集已经完全部署到了近几年的 Intel 服务器 CPU 当中。它引入了 32 个 512 bits 的 zmm 寄存器，一条指令就可以同时对 8 个 64 位整数/浮点、或 16 个 32 位整数/浮点进行运算，大幅提升了并行计算效率。

x86 的三代向量寄存器，图源：https://cvw.cac.cornell.edu/vector/hw_registers

虽然 SIMD 的算力远不如同一时代的 GPU，但它在灵活性上远超 GPU：GPU 是独立的计算设备，通过 PCIe 总线与主板连接，需要厂家专用的驱动、指令集和开发工具才能使用。每次执行计算时，还需要 CPU 向 GPU 发送指令，将数据从内存搬到显存上，执行计算后再搬回来，整体延迟非常大。而 SIMD 是 CPU 的内置功能，直接编写向量指令就可以使用。现代编译器通常还可以做自动向量化，对数组循环计算等操作自动生成 SIMD 指令。此外，SIMD 还可以很好地和原有的计算逻辑相结合，数据移动的开销也很小。这些特性使得 SIMD 相比 GPU 具有更低的延迟，更容易上手开发，非常适合在这个比赛的场景下使用。

接下来我们继续复盘比赛过程，具体说明如何用 Rust 编写 SIMD 在支持 AVX512 的 CPU 上加速大整数运算。

比赛过程复盘（续）

分类索引：

• 计算优化：13 U256
• SIMD 优化：14 U128x8，15 U192x8，17 U64x8，19 进位处理
• 算法优化：18 质因数分解
• 系统优化：16 监控程序

13. 自己实现 256 位整数计算

在第 8 步优化中，我引入了第三方库 primitive-types 来做 256 位大整数运算。但随后的测试显示出它的性能并不好：

perf 显示有大量时间消耗在了 U256 相关计算上

首先，这几个函数没有被内联，这意味着每次都会有至少 4 个 u64 通过内存传递，而不是寄存器。其次，这个库的实现方法更加注重通用性，它可以同时生成 U128、U256、U512 等不同类型，但没有对性能做特别优化。我们进入 add 函数内部看看，发现简直一团糟：

明明可以做得更好！x86 指令集中有一条 ADC（Add with Carry）指令可以用来优化大整数加法。它相当于一个全加器，多条指令级联起来即可高效完成大数的加法运算。Rust 标准库中也有对它的封装函数 u64::carrying_add（不过还在 nightly 阶段）。有了这个函数，我们就可以写出既优雅又高效的代码：

 pub struct U256(pub [u64; 4]);
 
 impl Add for U256 {
      type Output = U256;
      #[inline]// 记得 inline
      fn add(self, rhs: Self) -> Self::Output {
          let [a0, a1, a2, a3] = self.0;
          let [b0, b1, b2, b3] = rhs.0;
          let (c0, carry) = a0.carrying_add(b0, false);
          let (c1, carry) = a1.carrying_add(b1, carry);
          let (c2, carry) = a2.carrying_add(b2, carry);
          let (c3, _) = a3.carrying_add(b3, carry);
          U256::new([c0, c1, c2, c3])
      }
  }

可以看到还是非常紧凑而高效的。

在具体实现上，由于我写的 U256 采用小端序存储，因此需要翻转顺序后再按字典序比较：

 impl Ord for U256 {
      #[inline]
      fn cmp(&self, other: &Self) -> std::cmp::Ordering {
          let [a0, a1, a2, a3] = self.0;
          let [b0, b1, b2, b3] = other.0;
          [a3, a2, a1, a0].cmp(&[b3, b2, b1, b0])
      }
  }

而假如采用大端序存储就更简单了，可以直接写 #[derive(PartialOrd, Ord)] 生成默认的字典序比较。

 impl Sub for U256 {
      type Output = U256;
      #[inline]
      fn sub(self, rhs: Self) -> Self::Output {
          let [a0, a1, a2, a3] = self.0;
          let [b0, b1, b2, b3] = rhs.0;
          let (c0, carry) = a0.carrying_add(!b0, true);
          let (c1, carry) = a1.carrying_add(!b1, carry);
          let (c2, carry) = a2.carrying_add(!b2, carry);
          let (c3, _) = a3.carrying_add(!b3, carry);
          U256::new([c0, c1, c2, c3])
      }
  }

接下来我们做一下性能测试。需要说明的是这个测试是我写这篇文章的时候补测的，当时就直接上线了。然而最终复盘的时候还是有必要知道一下每一步优化到底起到了多大效果。下图中左侧是前后两种实现每个基本运算的时间，右侧是算一轮 N=256 个元素 M3 的完整时间：

可以看出我自己的实现相比原来的第三方库，在各种基本运算上的性能都有相当程度的提高。其中加法优化到了原来的 2.5 倍，减法 1.3 倍，移位和比较运算则达到了离谱的 10 倍以上，最终计算 M3 的整体性能提高了整整一倍。可见原来的实现性能实在是不行啊。

14. SIMD 优化 128 位整数计算

在实现过一遍完整的 U256 之后，我发现自己写一个定长大整数还是挺简单的。下面就可以正式开始卷 SIMD 了！我们首先拿 128 位试试水。

需要回答的问题有两个：

1. 如何用向量寄存器表示大整数？
2. 在这种表示下，如何用 CPU 提供的指令实现大整数的加法、减法、移位、比较运算？

我的第一想法是，把一个大整数完整塞进一个寄存器里。比如我们有一个 128bits 的 xmm 寄存器，那就让它像普通的通用寄存器一样表示一个 u128。

但随后问题来了，CPU 中没有一个指令能够把 xmm 看作一个完整的 128 位整数做加法，而只能把它看作 2 个 u64 分别做加法。

既然如此，有没有可能使用 2 个 64 位加法分别计算高低位，然后自己处理进位呢？似乎是可行的，我们只需要把低位的进位结果平移到高位，然后再相加即可。其中平移这步需要用到一种 shuffle 指令，它能够将原向量的各个元素按指定顺序重组成一个新的向量。

并且这种方法不限于 xmm，还可以扩展到 2 个 128 位整数的 ymm 和 4 个 128 位整数的 zmm：

减法运算和加法同理。而对于左移运算，我们也需要用类似的做法，将低位的溢出部分移动并组合到高位去：

最有意思的是比较运算。对于 128 位整数来说，我们需要先比较高位，如果高位相等再比较低位。因此这里会有一个 select 或者叫 blend 操作：根据一个 mask 向量的值来决定从 A/B 两个向量中选取哪个。

以上我们就完成了用 SIMD 进行 128 位整数运算的一个完整设计！看上去还不错，但是总觉得有点麻烦。麻烦的原因在于 SIMD 的一组数据之间是完全无关的，然而大整数的高低位之间却存在着数据依赖性，比如加减要进位、移位要填充、比较也有先后。这就使得即使 SIMD 可以一次性做完对等位置的运算，也还需要将低位移动到高位再算一次。更加麻烦的是，如果数字的长度发生变化，比如变成 192 位不能整除了，甚至变成 1024 位直接越界了。这种情况下各种边界处理将成为一大噩梦。有没有更加简单且自然的方法呢？

我上网搜索了一下相关话题，找到了 StackOverflow 上的一篇回答，它给出了完全另一种角度的实现：用两个向量寄存器分别存储一组数的高低位！

当时我就惊呆了，原来这才是使用 SIMD 的正确姿势！在这种数据排布下，一组向量寄存器内的数据是完全无关的，这样向量和标量的计算过程就完全统一了，在代码中直接把原来的数据类型和运算改成向量版本即可。

这篇文章还同时指出了 SIMD 处理加法进位的问题：传统的标量指令会在发生进位时设置特定的标志位（CF），而向量指令则是直接丢弃溢出的部分，所以我们无法直接地知道是否发生了进位。那怎么办呢？文中给出的方法是再对运算结果做一次比较，如果和小于其中一个被加数，就说明发生了进位。利用这一特性，我们可以在 AVX512 中仅用 4 条指令实现 128 位整数加法：

 vpaddq      xmm2, xmm0, xmm2 # x_low += y_low;
 vpcmpuq     xmm0, xmm0, xmm2 # x_low < y_low
 vpaddq      xmm1, xmm1, xmm3 # x_high += y_high
 vpsubq      xmm0, xmm1, xmm0 # x_high += xmm0

不过在 AVX2 及以前的指令集中，并没有一条直接对无符号整数比大小的指令，只支持有符号整数比较，因此需要额外两条 vpxor 指令来对符号位做反转。后面我们会发现，由于这一点差异导致 AVX2 和 AVX512 的性能产生了天壤之别。

在学习完先进设计后，下面我们就来在 Rust 中实现这个做法！

自 SIMD 诞生以来，开发者想在自己写的程序中用上它基本上只有三种途径：要么让编译器自动向量化，要么使用编译器提供的 intrinsic 内置函数，或者干脆自己手写汇编代码。这三种做法的灵活性和可达的性能上限依次提高，但是开发成本也随之陡然上升。一般最常用的 intrinsic 函数通常画风这个样子的：

 // 节选自上面 Stack Overflow 的回答
 __m256i sign64 = _mm256_set1_epi64x(0x8000000000000000L);
 __m256i aflip = _mm256_xor_si256(a, sign64);
 __m256i bflip = _mm256_xor_si256(b, sign64);
 __m256i cmp = _mm256_cmpgt_epi64(aflip, bflip);

实际上它们就是对底层向量指令的一个简单包装，跟直接写汇编区别不大，只是编译器帮你处理了寄存器分配这种脏活累活。一旦使用的指令集发生变化，比如从 x86 迁移到 ARM，或者是从 AVX2 升级到 AVX512，基本都要对整个代码进行重写，开发成本十分巨大。我的另一个参赛同学就花了一整天将 C++ AVX2 代码迁移到 AVX512，过程中不但要学习新的指令集，还要处理各种细节的差异，花了非常多时间 debug。

Rust 也支持使用 intrinsic 函数编写 SIMD（需要 nightly），不过我们今天要介绍一种更简单的方法。Rust 社区从 2020 年开始就组建了可移植 SIMD 工作组，目前他们的成果——平台无关的 std::simd 模块已经初步完成并进入了主线 nightly 版本中。下面我们就来感受一下用这个模块编写 SIMD 是一种怎样的体验。

 // 需要使用 nightly-2022-02-01 以上版本
 // 目前使用此模块还需要开启指定 feature
 #![feature(portable_simd)]
 
 // 导入向量类型。为了最大化并行度，直接一次拉满 8 组数据。
 use std::simd::{mask64x8, u64x8};
 
 // 模仿上面的风格，定义一个 128 位无符号整数的向量类型
 #[derive(Default, Debug, Copy, Clone, PartialEq, Eq)]
 pub struct U128x8 {
     // 高位和低位分别存储在两个 512 位向量中
     hi: u64x8,
     lo: u64x8,
 }
 
 impl U128x8 {
     // 构造函数：从给定标量扩展为每一个元素都相同的向量
     #[inline]
     pub const fn splat(x: u128) -> Self {
         Self {
             hi: u64x8::splat((x >> 64) as u64),
             lo: u64x8::splat(x as u64),
        }
    }
 }
 
 // 实现加法，减法是类似的略过
 impl Add for U128x8 {
     type Output = U128x8;
     #[inline]
     fn add(self, rhs: Self) -> Self::Output {
         let lo = self.lo + rhs.lo;
         // 将进位扩展为全 0 或全 1（即 -1）
         let carry = lo.lanes_lt(rhs.lo).to_int().cast::<u64>();
         // 所以这里 -carry 也就是 +1
         let hi = self.hi + rhs.hi - carry;
         Self { hi, lo }
    }
 }
 
 // 实现移位
 impl Shl<u8> for U128x8 {
     type Output = U128x8;
     #[inline]
     fn shl(self, rhs: u8) -> Self::Output {
         let lo = self.lo << u64x8::splat(rhs as u64);
         let hi = self.hi << u64x8::splat(rhs as u64);
         let hi = hi | (self.lo >> u64x8::splat(64 - rhs as u64));
         Self { hi, lo }
    }
 }
 
 impl U128x8 {
     // 比较操作（大于）
     #[inline]
     fn lanes_gt(self, other: Self) -> mask64x8 {
         let hi_eq = self.hi.lanes_eq(other.hi);// 先看高位是不是相等
         let hi_gt = self.hi.lanes_gt(other.hi);// 如果不等取高位比较结果
         let lo_gt = self.lo.lanes_gt(other.lo);// 如果相等取低位比较结果
         hi_eq.select_mask(lo_gt, hi_gt)
    }
 
     // 条件减法：如果不会下溢出就相减，否则保持不变
     #[inline]
     fn sub_on_ge(self, other: Self) -> Self {
         let c = self - other;
         let underflow = other.lanes_gt(self);
         Self {
             hi: underflow.select(self.hi, c.hi),
             lo: underflow.select(self.lo, c.lo),
        }
    }
 
 // 取模，假设被除数范围是 [0,10M)
     #[inline]
     pub fn rem10(mut self, m: u128) -> Self {
         // 向量取模采用四次比较减法的方式，因为之前标量优化中手动二分的方法难以使用
         // 由于 inline，当传入的 m 是常数时，编译器可以将下面的减数都提前计算出来
         self = self.sub_on_ge(U128x8::splat(m * 4));
         self = self.sub_on_ge(U128x8::splat(m * 4));
         self = self.sub_on_ge(U128x8::splat(m * 2));
         self = self.sub_on_ge(U128x8::splat(m * 1));
         self
    }
 }

是不是非常简洁优雅？最关键的是，这份代码是平台无关的，也就是说它会在支持 AVX512 的机器上将 u64x8 映射为 zmm，在支持 AVX2 的机器上映射为两个 ymm，在 Apple M1 上映射为四个 Qn，在没有任何 SIMD 扩展的指令集上映射为 [u64; 8] 数组。

接下来是激动人心的时刻，我们快速跑一下 benchmark 来看看 SIMD 带来了多大的性能提升：

测试环境 Intel(R) Xeon(R) Gold 6240R CPU @ 2.40GHz（并不是比赛当时的环境）

从左到右分别是 8 组乘加运算、8 组取模运算、N=256 计算一轮 M2 整体的时间开销。这个结果让我非常沮丧：取模的时间开销竟然是标量版本的 2 倍以上，而乘加操作也没有提高多少，所以整体算一轮 M2 的时间也远不及标量版本。当时我给出的解释是，一方面因为标量版本已经非常优化了，一次 u128 的取模只需要 4 次 u64 比较和 1 次 u128 减法；另一方面向量版本由于无法利用分支跳转，所以只能靠大量的计算，一次 u128 取模需要 12 次 u64 比较和 4 次 u128 减法，还有不少 select 操作。整体来说 SIMD 算力的优势难以抵消计算量的劣势，所以性能还不如原来好。

当时测出这个结果以后，我几乎已经要放弃 SIMD 这条路了。不过随后我跟师兄

@Liu Yiyuan

交流了一番，发现他也写了 AVX2，并且表示效果显著：

得知这个情报以后，我马上就放心多了。这说明 SIMD 这个方向是对的，肯定是我哪里搞错了，这里面一定还有优化空间。到底是哪里搞错了呢？我 lscpu 一看，原来这台测试机上没有 AVX512。这是因为我为了避免编译和测试影响线上程序的运行，用了另一台阿里云免费送给我 1 个月的 ECS 做开发，而这台 ECS 的 CPU 比较古老只有 AVX2（果然便宜没好货啊）。其实对于这两种指令集我之前都没怎么接触过，只是看过一篇 Linus 狂喷 AVX512 的文章，给我留下了一种 AVX512 华而不实的印象。这让我当时对它并没有抱很大的期待，但还是死马当活马医，把程序换到支持 AVX512 的机器上测试了一发：

好家伙！时间直接缩短到 1/3，让 SIMD 的性能一举超过了标量版本。可为什么这两个指令集之间会有如此大的差距呢？我们看看生成的汇编代码就能发现一些端倪：

上图是我分别 perf 了 AVX2 和 AVX512 运行取模 bench 的结果。第一眼从颜色分布上就可以看出，右边 AVX512 具有更高的性能密度，基本上每条指令都利用上了，看不出有什么瓶颈；而左边 AVX2 就明显稀疏了很多，除了多出了 xor 指令外，还意料之外地出现了不少 extract 和 pack 指令（提取元素并重组）。我猜测这些都是由于 AVX2 不支持无符号整数比大小而生成的辅助指令。再进一步看看内容，右边 AVX512 使用的都是 zmm 和新引入的 kn mask 寄存器，而左边的 AVX2 主要使用 ymm 和少量 xmm，数据密度低了一倍，因此指令数量也就多了一倍。我还仔细过了一遍 AVX512 生成的指令，感觉基本已经是最优解了。

通过以上分析，我觉得可以得出这样的结论：

1. Rust SIMD 模块能够生成接近最优的本机向量指令。
2. AVX512 相比 AVX2 有不小的改进，并且在无符号整数比较方面有巨大优势，并不像人们所说的那样一无是处。

在解锁了 AVX512 的洪荒之力之后，经过 SIMD 优化的 M2 和 M4 计算时间降低到了原来的一半左右。曲线一下子就起飞了，最终卷到了和 OS 专家（chi）并列第二名的位置：

AVX512 助力 omicron 迅速起飞

15. SIMD 优化 192 位整数计算

SIMD 获得大成功之后，我继续乘胜追击，打算将 M1 和 M3 也 SIMD 化。此时开销最大的已经变成了 M3，所以就先从它下手。

首先我注意到，M3 的数据范围并不需要 256 位，其实 192 位就够了，这样可以从 4 个 u64 减少到 3 个。于是我先把标量版本的 U256 优化到了 U192。

接下来我们仿照上面的过程实现 U192x8。整体逻辑是差不多的，唯一的区别是多了一个中间位：

 pub struct U192x8 {
     hi: u64x8,
     mi: u64x8,
     lo: u64x8,
 }

这个中间位给计算加法进位造成了不小的麻烦，因为原来的算法失效了：如果低位有进位的同时加数为全1，那么 a+b+carry 就会等于 a，结果和 a 比较大小无法判定是否发生了进位。解决方法是多做一次比较，增加了不少计算量：

 impl Add for U192x8 {
     type Output = U192x8;
     #[inline]
     fn add(self, rhs: Self) -> Self::Output {
         let lo = self.lo + rhs.lo;
         let lo_carry = lo.lanes_lt(rhs.lo);
         let mi = self.mi + rhs.mi - to_u64x8(lo_carry);
         let mi_carry = mi.lanes_lt(rhs.mi) | (self.mi.lanes_eq(u64x8::splat(u64::MAX)) & lo_carry);
         let hi = self.hi + rhs.hi - to_u64x8(mi_carry);
         Self { hi, mi, lo }
    }
 }

类似地，其它操作也都增加了不少计算量。直接来看性能测试的结果：

基本上也获得了接近一倍的性能提升，其中主要贡献来自乘加运算（不知为何标量 u192 这么慢）。然而悲催的事情又出现了，当时我在写性能测试的时候，把 U192 改成 U192x8，却忘了将数组长度缩小到 N/8，导致 SIMD 的结果变成了真实值的 8 倍。因此迟迟没有将 M3 改写成 SIMD，很久之后才发现这个乌龙。

16. 实现监控程序

在比赛开始后，由于选手们纷纷建立多个连接导致服务器压力过大，有时会被主动限流导致连接断开。此时程序中的 TCP socket 就会返回错误，如果没有处理好就会导致程序卡死或者崩溃。下图就展示了一段网络不是很稳定的时期，可以看到在多个时间点上出现了部分选手直接“躺平”的场面。

为了避免网络原因导致程序崩溃造成的损失，我从网上抄来了一份监控脚本：

 while true
 do
 ps -ef | grep most | grep -v "grep"
 if [ "$?" -eq 1 ]
 then
 nohup nice -n -20 ./target/release/most >> nohup.out &
 echo "restart"
 fi
 sleep 5
 done

它的功能就是定期检查指定程序是否还活着，如果没了就自动重启。接下来只需应用 “let it crash” 的思想，让程序发生任何错误都直接崩溃，就可以避免意外躺平。这里需要提醒 Rust 开发者注意的是，在 tokio 中运行的协程 panic 并不一定会导致程序崩溃退出。部署完监控脚本后还带来了另一个效果，那就是新版本上线只需要先编译然后 killall most 即可。

17. SIMD 优化 64 位整数计算

最后我们来用 SIMD 优化 M1 的 64 位整数计算。在上篇的第 9 步优化中我们提到，编译器会利用数学原理自动将 u64 % 常数 u64 优化为两次乘法。这个优化在 SIMD 中是否依然有效呢？经过实验，答案是否定的。因为计算过程需要取乘积的高 64 位，而主流的 SIMD 指令集都是没有这种操作的。Rust 面对这种情况会将 u64 从向量寄存器中逐一提取出来，进行标量计算后再逐一塞回去。。。

同样的代码重复了十几次，真是辛苦您了（

既然这条路行不通，那只好复用之前的老套路做四次减法了。不过其中有一处计算可以简化，那就是比较-选择可以用 min 代替：

 #[inline]
 fn rem_u64x8(mut f: u64x8, m: u64) -> u64x8 {
     f = f.min(f - u64x8::splat(M1 * 4));
     f = f.min(f - u64x8::splat(M1 * 4));
     f = f.min(f - u64x8::splat(M1 * 2));
     f = f.min(f - u64x8::splat(M1 * 1));
     f
 }

原理也很简单：如果减法发生下溢出，那么在无符号数的表示下一定是一个很大的数。把它跟原来的数取个最小值就能过滤掉溢出的结果。

然而，接下来的性能测试却显示出这里有一个天坑！虽然我想用的是 Simd 结构上的 min 函数，但实际上编译器使用的是标准库中的 min 函数。由于 Simd 结构实现了 PartialOrd 和 Ord trait，因此标准 min 函数会进一步调用 Simd 的 cmp 函数，反映到指令上就是要把所有元素从向量寄存器中逐一提取出来做比较，然后从两个输入中选它认为“小”的那个。很明显这无论在性能还是正确性上都是不对的！

从指令和调试信息上都能明显看出它使用了错误的函数

我尝试了很久也没能找到一种让它选择正确函数的方法，所以迫不得已在这里写了 intrinsic，成为了整个程序中唯一不 portable 的部分（

 #[inline]
 fn rem_u64x8(x: u64x8, m: u64) -> u64x8 {
     use std::arch::x86_64::_mm512_min_epu64;
     use std::mem::transmute;
     unsafe {
         let mut x = transmute(x);
         x = _mm512_min_epu64(x, transmute(u64x8::from(x) - u64x8::splat(m * 4)));
         x = _mm512_min_epu64(x, transmute(u64x8::from(x) - u64x8::splat(m * 4)));
         x = _mm512_min_epu64(x, transmute(u64x8::from(x) - u64x8::splat(m * 2)));
         x = _mm512_min_epu64(x, transmute(u64x8::from(x) - u64x8::splat(m * 1)));
         u64x8::from(x)
    }
 }

以下是性能测试结果，从左到右分别是标量实现、SIMD 的错误实现和 intrinsic 实现。可以看出 SIMD 相比标量性能提升了 2 倍以上。

18. 算法优化2：质因数分解

终于又出现一个算法优化了。。。我们小学二年级就知道：一个数被 M 整数，当且仅当它能够被 M 的每一个质因子 P 整除。所以我们只需对每一个 M 做质因数分解，然后分别对每一个质因子计算即可。什么？你问我怎么连这都想不到？其实我一开始就想到了，并且发现 M1 可以分解成若干小质数的乘积，M2 是个质数，M3 太大了计算机算不出来，而 M4 干脆就是以 3 个质因子的形式给出的。

 $ factor 20220217214410
 20220217214410: 2 5 431 46589 100699
 $ factor 104648257118348370704723119
 104648257118348370704723119: 104648257118348370704723119
 $ factor 125000000000000140750000000000052207500000000006359661
 ...

好吧我来自己打脸了，这个优化对于标量的性能提升还是相当可观的，而对于向量也有 20% 的提升。多会一点小学数学就能分分钟大幅提高性能，怎么看都比吭哧吭哧搞性能优化要强啊。

19. SIMD 优化进位处理

到这里我们已经对所有计算完成了向量化改造，下面需要对 SIMD 的实现做进一步的调优了。

之前我在和

@Liu Yiyuan

交流 SIMD 的时候，他问我你是怎么处理进位和溢出的，结果发现我们对此的处理方式并不一样。@Liu Yiyuan 提出了一种预留进位的方式，让所有低位都预留 4bits 的进位，平时只保存 60bits 的有效数字。选择 4bits 是为 x10 考虑的。这样在 x10+b 以及加减法的时候就可以直接计算然后处理进位。跟我之前的实现相比，多了一些移位和 mask 操作，但避免了很多比较。

另外，我还想到一处代码细节的优化。在取模运算中，减法是非常耗时的。所以如果一组数据中的 8 个元素全部都下溢出了（这种情况在 -8M 的时候是容易出现的），就没必要执行减法了，可以提前返回：

  #[inline]
  pub fn sub_on_ge(self, other: Self) -> Self {
      let underflow = other.lanes_gt(self);
 +    if underflow.all() {
 +        return self;
 +    }
      let c = self - other;
      Self {
          hi: underflow.select(self.hi, c.hi),
          mi: underflow.select(self.mi, c.mi),
          lo: underflow.select(self.lo, c.lo),
      }
  }

同理在比较运算中，高位全部不相等的情况也是非常可能出现的，这时候就可以跳过所有后面低位的比较。不过这个优化只对 192 位比较有意义，因为在 128 位中只能跳过一次比较，有些得不偿失。

  #[inline]
  pub fn lanes_gt(self, other: Self) -> mask64x8 {
      let hi_eq = self.hi.lanes_eq(other.hi);
      let hi_gt = self.hi.lanes_gt(other.hi);
 +    if !hi_eq.any() {
 +        return hi_gt;
 +    }
      let mi_eq = self.mi.lanes_eq(other.mi);
      let mi_gt = self.mi.lanes_gt(other.mi);
      let lo_gt = self.lo.lanes_gt(other.lo);
      hi_eq.select_mask(mi_eq.select_mask(lo_gt, mi_gt), hi_gt)
 }

加上这两步优化以后，M2 和 M3 的计算时间进一步降低到 1/3 和 1/4 左右，相比原始的标量实现已经有了一个数量级的提升！

20. 决赛开始

做完上面这些优化以后，差不多也快到了决赛开始的时间。2 月 18 日晚 8 点，随着莫队在微信群里一声令下，比赛正式开始。排行榜和形势图清零，页面放出了新的 N 和 M——看上去和资格赛没有什么不同，按惯例做一番质因数分解，跑脚本爬一遍 M4 即可。10 分钟后，我的程序就改完数据上线了。在此期间，其他选手也陆续冲出了起跑线：

令我十分惊喜的是，我的程序 omicron 曲线斜率超过了所有人，竟然一路狂飙不久就冲到第一了。没想到卷王就是我自己！哈哈，提前写了 SIMD 真是个明智的决定！

合影留念：omicron 第一次拿到第一，也是最后一次（

然而好景不长，半个小时后，官方号 alpha 突然大幅升级，马上又把我反超了过去。几个小时后，又有四大天王陆续觉醒，纷纷超过了 alpha。一个晚上的时间，我就从第一名被卷到了第 8 名，心里哇凉哇凉的。这个比赛可真是太卷了！

下篇预告

这篇文章主要介绍了我在资格赛期间用 SIMD 所做的优化，相比标量版本取得了近 10 倍的性能提升，并借此短暂地拿下了增长曲线的第一名。

经过这段时间的实践后我认为，Rust 的 SIMD 模块是一个相当优雅的解决方案：它对底层指令做了跨平台的封装，能够在不同平台上自动生成高效的向量指令，并且写起来十分方便。强烈推荐各位开发者在需要 SIMD 的时候尝鲜体验一下。

下篇文章我会继续记录我在决赛期间垂死求生的故事，分享其他选手的精彩做法，以及我在比赛后的收获和反思。欢迎继续关注~

下篇：其他选手的精彩解法和自己的一些感悟

两周前我参加了一场高频交易模拟赛，这一系列文章是我对这场为期一周比赛的复盘总结。在前两篇中我主要记录了从比赛开始到资格赛为止，我对程序做的各种优化手段和技巧。转眼两周时间过去了，曾经比赛时的那股激情也逐渐平复下来，是时候谈谈这一周经历带给我的感触和思考了。不过在此之前，我们先快速回顾一下比赛题目和决赛过程，然后揭晓其他选手使用的神奇策略吧。

比赛题目

给定一个实时推送的数字流，从中找出长度不超过 N 的连续数字串，满足其组成的正整数是任意 M 的倍数。其中给定常数：

 N = 256
 M1 = 20220217214410
 M2 = 104648257118348370704723119
 M3 = 125000000000000140750000000000052207500000000006359661
 M4 = 3^50 * 7^30 * 11^20

这些前期工作让我在决赛刚开始的时候短暂地获得第一，但随后又被其他选手纷纷超越。下面我们继续回放一下决赛过程，对细节不感兴趣的同学可以直接跳过看后面的内容。

比赛过程回放（决赛）

21. 模拟服务端测试

由于决赛时比赛服务器只对参赛选手的内网地址开放，其它机器无法访问，所以如何在不影响线上运行的同时进行调试就成了个问题。我们知道这个比赛是非常看重响应时延的，而且决赛时选手间的比拼已经卷进了 10us 量级。经过我的测试，一旦在比赛机器上进行编译等重 CPU 负载的工作，排名就会刷刷往下掉，说明此时程序的响应时延大大加长了（即使已经设置了实时调度和最高优先级）。

这样看来在比赛机上做测试是不太可能了。所以为了验证程序的正确性，我还是自己写了一个简单的服务端做 mock。它的数据生成方式非常简单，就是随机生成一些 M 的倍数，再随机生成一些数字串，最后随机地混合起来。如果我的程序识别出的数字串不符合服务端生成它的频率，就说明我的程序写错了。实践表明这个方法非常有用，多次识别出了程序中存在 bug，避免了直接上线出锅的惨剧发生。

22. 发现 M3 的质因数分解

虽然前面我对大整数运算做了很多优化，但最长的 M3 运算依然是开销很大的部分。我盯着 M3 = 125000000000000140750000000000052207500000000006359661 这个数字，陷入了久久的沉思：这明显是一个很有规律的数字，很有可能是精心构造出来的。我们把几个非零的部分拿出来分解一下试试看：

 125 = 5 * 5 * 5
 14075 = 5 * 5 * 563
 522075 = 3 * 5 * 5 * 6961
 6359661 = 3 * 3 * 3 * 7 * 7 * 11 * 19 * 23

果然是这样。我们再数数 0，发现每一部分加上前导 0 都是 17 位，而 10^17 刚好在 u64 的表示范围内！这么看来应该把它表示成 10^17 进制做运算？但是这样似乎也没有什么好处……感觉真相近在眼前了，但就是隔了层窗户纸没法捅破，难受。

到最后我还是回到了质因数分解这条路上来，既然 factor 对此无能为力，那就试试更高级的工具吧！于是我打开了著名的 Wolfram Alpha，向它发出了灵魂之问：

结果没有响应。。。不管我问什么都没有响应，这破网属实不行！于是我继续搜索在线分解质因数的网站，终于找到了一家能够工作的，而且竟然支持分解 70 位：

https://zh.numberempire.com/numberfactorizer.php

原来是这样，我悟了。现在我还有点好奇它使用了什么算法能这么快分解大整数，但当时这都已经不重要了，赶快改代码卷上去要紧啊！

23. 回归单线程

到目前为止我的程序一直是以多线程模式在运行。虽然决赛机上有 2 vcpu，但后来我们意识到它其实只是一个物理核上的两个超线程（云厂商可真会做买卖）。这就意味着实际上我们只有一个核的计算资源，对计算密集型程序来说开两个线程几乎没有什么好处，还会增加线程之间同步的开销。

多线程模式下四个计算任务的平均时延（第二列）

于是我就把程序从多线程改回了单线程，并且彻底扬掉了 tokio，因为不再需要多线程调度器了。但是，我们依然需要一个后台线程来创建 TCP 连接，并通过 channel 发送给计算线程。这样改完以后，整体的计算时间并没有显著增加，反而使得第一个计算的 M1 平均时延降低到了 100us 以内。从排行榜上可以看出抢到前三的次数明显增加了，说明还是有一定效果的。

这一现象让我意识到，相比多线程自动调度来说，单线程具有计算顺序可控的优势。我们可以把计算量最小的放在第一个算，计算量最大的放在最后算，这样整体的平均时延是最低的。更进一步，在整体性能对别人没有明显优势的局面下，还可以使用田忌赛马的战术：优先处理自己最擅长的部分，放弃做的不好的部分。由于比赛规则接近于赢者通吃，因此通过合理地排列计算顺序，也能够抢到更多的分数。

最后还想说一下的是，我做这个优化通宵到了第二天早上 6 点。然而根据后来莫队放出的时延曲线图显示，还有不少选手也在同时通宵内卷，着实恐怖：

决赛第一天各位选手的平均时延曲线图，横轴是时间，纵轴是时延（单位us）。红圈内的后半夜时段仍有多条曲线时延显著降低。

24. 优化 SIMD 取模

19 日白天我一直没有什么新的想法，只好继续琢磨怎么对 SIMD 进行优化。SIMD 开销最大的还是在取模操作上，需要四次比较和减法。之前我们提到过，两个数的比较可以转化为先做减法然后看正负，所以其实比较和减法可以合在一起来做，使用开销较低的判断正负代替两个数的比较。

上图是优化后的比较减法代码和生成的汇编指令。不过我感觉这份指令可能并不是最优的，因为出现了两个 vpcmpgtq 比较指令，并且它们的比较对象 zmm4 和 zmm5 都是一开始生成的常数（zmm4 我看出来是 0，zmm5 没看懂它生成了啥）。理论上和 0 比较大小只需要看符号位，所以用 vptestnmq 就够了，开销一定比 cmp 要低。不过虽然我能看出这里指令还有优化空间，但却也没有什么好办法去手动纠正它，只能等待日后 Rust 编译器或者 SIMD 库来解决了。

指令有问题，自然性能也没有太好，结果和优化前基本持平。所以可以说到这里 SIMD 的性能基本没有多少提升空间了。

25. 莫队算法？

各种方向都已经走入了死胡同，接下来只能再想想算法了。这时候我灵光一闪，别忘了这个比赛的主办者是谁，那可是我 10 年前高一的时候就知道的莫队啊。当年学过的莫队算法，不就是解决区间查询问题的嘛，跟这个题目很像啊！虽说我除了“莫队算法”和“区间查询”这几个字以外就不记得别的东西了，但这些年在贵系摸爬滚打，也算练就了一身在考场上现场预习的本领，不慌！于是我打开 Google 开始集成学习莫队算法。

https://oi-wiki.org/misc/mo-algo/ 感谢 OI Wiki！

看着看着我就感觉不太对劲了。因为莫队算法是给定若干查询做离线处理，但这个题目里并没有给查询啊，或者说任何一个子区间都是查询，不满足 N=M 的条件。在剩余系里做乘加运算好像也没什么可以投机取巧之处，只能一个一个硬算……总之这个思路也彻底失败了。

26. 算法优化3：跳过序列

随后我又开始想能不能从生成的数字串中挖掘一些规律出来。比如哪些数字、哪些长度的出现频率高，就可以优先算哪部分。于是我对匹配数字的日志做了一番统计，结果很遗憾地发现，各种特性都是均匀分布的：M1-M4 每种数字串出现的频率相同，各种长度的数字串出现的频率也相同。

不过最终通过观察日志，我还是意识到了两个有价值的性质：

1. 任意一个能被整除的数字串后面跟上若干个 0 也可以被整除。
2. 任意两个能被整除的数字串不会重叠。

第一个十分显然。第二个也很好理解，如果这些数字串都是分别独立构造生成的，然后再混入随机串里，那就几乎不可能出现重叠的情况。

利用这两个性质，我们可以对程序做出如下优化：

1. 找到一个能被整除的数字串后，马上向后查看是不是跟着 0，如果有就一起提交答案。
2. 做完第一步后，清空 M1-M4 的所有状态。扔掉前面的串从头来过。

这个优化对于以 0 结尾的答案和在一个输入块中的第二个答案，理论上都有比较好的效果。但是由于满足这两个条件的答案并不是很多，所以不会有显著的提升。

27. TCP 使用单连接

这里又一次吃了没学好网络原理的亏：HTTP 从 1.1 开始引入了长连接，所以一个 TCP 连接可以用来发多个请求，并不需要每次都新建连接。在上一步优化中，如果有答案数字串后面跟着 0 的情况，那么可以将多个请求打包在一个 TCP write 操作中一起提交。这个优化可以为后面的答案节省 20us 以上的时间。考虑到当我们发现一个答案后，肯定希望用最快的速度调用 TCP write 将它发出去，而不是再去计算后面的内容，所以整个程序其实只需要一个 TCP 连接发答案就够了。

另外前面其实还做了两个关于 TCP 的设置：NO_DELAY 和 NON_BLOCKING。前者是对低延迟很关键的一个配置，用来禁用 Nagle 拥塞控制算法，让每次写入的数据都立刻发出；后者是为了防止发送陷入阻塞，耽误后面的计算。但我观察到在实际运行中并没有出现阻塞的情况，应该是因为每次发送的包都比较小，几乎不会占满内核缓冲区。

28. 算法优化4：单质因子

决赛即将过半，卷不过的群友们开始分析排行榜上对手的性能指标。一番估算以后惊恐地发现，人家已经把平均一个数字的计算时间压到了 50ns，按照正常的计算方法是很难做到的。于是，群友从中得出了一个非常关键的信息：

重点不是快速找到答案，而是快速排除非答案！哪怕排除算法不是 100% 准确，有一些漏网之鱼也是可以接受的！这让我立刻回忆起了曾经学过的费马小定理和快速判定质数等算法。不过对于这个题目来说根本不用这么复杂，有一个显而易见的判定方法：对于任何非质数的 M 来说，一个数能被 M 整除意味着一定能被 M 的任何一个因子整除。反过来，如果一个数对于 M 的某一个因子不能整除，那么它也不能被 M 整除。所以对于每个 M，我们都只需选一个因子来递推计算余数就好了。所有余数非 0 的直接排除掉，筛选出余数为 0 的再做一次验算即可。例如对于 M1 = 20220217214410 = 2 * 5 * 431 * 46589 * 100699，我们可以只算 1006990 的余数，找到余 0 的数字串后，再递推一遍算它对 431 * 46589 的余数。这样计算量就变成了原来的一半。对于 M3 和 M4，计算量可以降低到 1/3。并且由于它们的因数非常大，在随机数中出现假阳性的概率已经很低了，因此甚至可以不做验算直接提交答案。当然能这么做也是得益于莫队没有故意构造这样的数据来卡。

经过这个优化以后，计算量降低到了原来的 1/2-1/3 左右，大幅降低了计算时间。下图展示了我的程序从决赛开始到结束，测量的从收到数据到提交答案的时延分布变化情况。

决赛期间三个时间点的时延分布情况

从图中可以看出，10% 分位延迟基本维持在 50us 左右，中位数从 150us 降低到了 80us，90% 分位从 500us 降低到了 200 us，看起来相当不错了。

29. 思考内核旁路

然而，如果我们再看看榜上的统计数据……

……就会发现，本地延迟和服务端看到的延迟之间有 250-350us 左右的差值，这其中有 130us 的网络延迟，剩下 200us 左右就是操作系统和网络协议栈带来的开销了。对程序的 perf 结果也表明，内核的开销占到了整体的 7% 以上，其中大部分都和 TCP 相关。

终于，我们的瓶颈转移到了 OS 上面！

在决赛的最后一天，我开始思考如何 bypass 掉内核的网络协议栈。我能想到大致有四种方案，按照实现难度排序依次是：

1. 使用 Raw Socket 代替 TCP

这种方案只绕过了内核的 TCP 协议栈，由用户程序从二层或三层开始接管特定 IP 网络包的处理过程。这样不会对其它网络包造成影响，因此可以在云上直接开发调试。但是很有可能对性能不会有显著提高。

1. 使用 DPDK 等用户态协议栈

这个是业界标准的 kernel bypass 方案，将网卡驱动和协议栈都移到了用户态，从收包到发包的整个过程都可以留在用户态处理，彻底绕过了内核。但是由于目标机器在阿里云上，并且只有一个虚拟网卡，因此一旦部署 DPDK 接管网卡，随时都有 ssh 失联的危险。另外 DPDK 目前只有几个实验性质的 Rust binding，不知是否好用。虽说也可以将我的程序导出成 C 库用 C 代码粘起来，但是无论怎样都有不小的学习和试错成本。

1. 注入内核模块

这种方案和 kernel bypass 反其道而行之，将计算逻辑封装成内核模块注入内核，并挂载到网络协议栈的特定位置执行。它和 DPDK 方案一样都能避免上下文切换和进程调度的开销，也同时具有把内核搞崩溃导致失联的风险。与 DPDK 不同的是，写内核模块需要熟悉 Linux 内核环境和相关 API。 和内核模块类似的方案是 eBPF，这是一种在能在内核虚拟机中运行的程序，主要用来过滤网络报文。但是由于它在虚拟机中解释执行或 JIT 执行，性能肯定会受影响，而且八成无法利用 SIMD 指令做加速。因此从性能角度考虑这个方案并不适合。

\4. 扔掉 Linux 自己写内核

这就是在上篇文章开头 @松 提出的方案。由于 OS 跑在阿里云的 KVM 虚拟机上，所以至少需要实现 virtio-net 驱动和网络协议栈。这种方案可以对整个软硬件系统有最彻底的控制，避免 OS 中断开销，并且可以简化 TCP 复杂的状态机模型，以达到最极致的性能。但是即使有丰富的内核和网络开发经验，要实现这样一个工程并调试正确也至少需要几天的时间。

开了这么多脑洞，到最后其实哪个也没动手做，因为实在来不及了。在最后一天下午，我用 Rust 又写了一版高性能的服务端，并开了一个内网机器，全真模拟测量端到端的延迟。这么做其实是为了执行上面第一个 Raw Socket 方案做准备，但这也就是我最后的挣扎了。剩下的几个小时，我开始躺平等死。

30. 决赛结束

2 月 20 日下午 5 点 26 分，在距离比赛结束还有 3 个小时之际，本次比赛的最后一个逆转出现——松的 OS 上线了！！！

Welcome to JudgeDuck-OS-64 !!!

随即，松的得分曲线也开始起飞：

在这个时候，按照积累的总分排名，我排在第 5，

@Liu Yiyuan

排第 6，@松 排第 7。按照比赛规则，前六名可以获得奖金，所以这个位置的排名是非常关键的。而此时恰好我们三人的分数都很接近，并且差距还在不断缩小，所以在比赛的最后时刻开始了一场精彩的奖金争夺战。首先是松的分数开始快速增长，半个小时后超越 @Liu Yiyuan 来到第六，两个小时后又超过了我拿到第五。而 @Liu Yiyuan 和我之间的分差也在以每小时 2000 左右的速度逼近，经过估算大约 4 个小时后能够反超，然而此时比赛只剩下 3 个小时了。所以最后就差这么一点点，我保住了自己的第六名，拿走了最后的奖金 23333

比赛结束时的排行榜

晚上 8 点，比赛结束。与此同时，2022 北京冬奥会闭幕式开始。放下了这场连续 10 天不眠不休的内卷，我怀着 emo 的心情，去欣赏张 emo 的艺术盛会了。

解题报告

比赛结束后，选手们陆续在群里公布了自己的代码和解题报告。正如第一篇文章开篇所提到的，整个比赛从头到尾我都认为这是一场低延迟系统优化赛，所以想当然地以为别人都写了 SIMD 并且代码优化得比我好。因此当看到别人做法的时候我整个人都傻了：原来这真的是一个算法题啊！除了我和师兄

@Liu Yiyuan

在平方级算法上玩命卷 SIMD 以外，其他选手基本都想到了线性算法，并且做了预处理等优化，跟我们完全不在一个赛道上，是妥妥的降维打击啊。

下面的内容我综合了排名靠前的几位选手 xi, gamma, lambda, epsilon 和 chi 的解题报告，向大家展示一下这个比赛的“正确”做法是什么样的。

利用 M 的性质

首先不管使用了怎样的算法，各位选手基本都想到了利用 M 本身的性质来降低数据规模和计算量。其中最重要的是我在第 28 步优化中提到的，首先对 M 做质因数分解，然后使用一个小因子来快速排除不可能整除的数。利用这一性质可以使 M1-M4 的数据规模分别下降到 u32/u128/u64/u32，避免高精度运算。

以外，还可以利用的性质有：

• 对于 M1 = 20220217214410，直接排除结尾非 0 的数字串
• 对于比较长的 M3 / M4，可以排除长度小于 54 / 71 的数字串

平方递推

所有选手一开始都能想到这个平方级别的递推算法。准确地说它的复杂度是

，N 是答案的最大长度，L 是输入串的总长度。我在第 4 步优化和本文开头提到过，这里再复述一下：

对于每个 M，维护以当前位置结尾的长度分别为 1-N 的数字串模 M 的余数，然后逐个追加数字递推后面的余数，公式为

线性递推

预处理

在这个比赛中输入的数字串是一块一块发过来的，而在发送的间隙 CPU 是闲置状态，因此我们可以在这期间做一些预处理以加速下一次的计算。

预言

预处理更进一步就是预言：在输入发过来之前就提前猜测并提交答案。能这么做的基础假设是，答案都是人为生成的。所以如果发现结尾的串再加几个数字就能被整除，那它很有可能就是答案。

这种预言所需的计算量比较大，是平方级别的，并且只能对 M 整体进行取模，所以需要高精度运算。不过好在这部分不在关键路径中，稍微慢一点也是可以接受的。在比赛过程中，群友 @大嗨子 很早就点亮了预言的技能，在前期借此获得了大量 +8，决赛时又开了一个 ping 接近 1ms 的外网机器专门做预言。不过由于能够预言的数字串出现频率较低，加上后来好多选手都学会了预言，所以到后期这个策略的收益就不高了。

以上我们揭晓了这个题目在算法上的正确做法和一些优化技巧。如果全部实现应该就可以拿第一了。不过虽然比赛已经结束了，但是我们对于极致的追求是永无止境的！下面我们就来继续探讨，在算法已经做到最优的基础上，系统方面还有哪些可以挖掘的地方吧。（别忘了还有一位选手写了 OS 呢）

SIMD

首先是我和 @Liu Yiyuan 主攻的 SIMD。在平方递推中，由于有数组运算，SIMD 能发挥很大的威力。但是在线性递推中，SIMD 似乎就没什么用了。考虑到经过预处理之后，我们只需要查表计算前缀和，而前缀和的计算是一个严格顺序的过程，很难并行化。尽管我找到一些 关于 SIMD 加速前缀和的研究，但是也需要多线程的辅助才有比较显著的加速效果。所以结论是在正确算法下 SIMD 没什么用，呜呜呜。

OS

当计算时延进入 10us 量级以后，OS 内核就成为了整个系统的瓶颈。为了让大家了解内核中都有哪些开销，我们写一个最简单的 echo 程序（不停地从 TCP Socket 中收发包），然后对它 perf 一下：

可以看出，这个程序有接近 90% 的时间都在内核态执行，其中 20% 的时间在查文件描述符表，10% 的时间在做系统调用的上下文切换，还有 30% 的时间在处理 TCP。如果只看有效工作的话，其中至少一半开销都是可以避免的。

在第 29 步优化中我简单介绍了绕过内核的四种方案：Raw Socket，DPDK，内核模块，自己写 OS。猛男松爷选择了最硬核的手撸 OS 并成功上线，让我们直接看 @松 自己写的解题报告吧：

…… （前三条是算法就不再贴了） \4. 此时操作系统已成瓶颈（计算 30us，内核协议栈 ??us……），因此考虑任何一种 kernel bypass 的方案（DPDK？eBPF？Linux 内核模块？自己写个 OS？） \5. 曾经写过一个带 UDP/IP 协议栈的纯内核态 OS，还缺个 TCP 和云服务器的网卡驱动（virtio-net），搞了两个通宵之后放弃了 TCP，写好了网卡驱动然后接了 lwIP 库上去，好用 \6. 想办法如何在云服务器这种困难环境下部署：用 grub 启动，且设置 GRUB_DEFAULT=saved 及使用 grub-reboot 命令来保证从自己的 OS 重启后能回到 Linux，以防止丢失控制权 \7. 应该还可以优化，lwIP 很慢（应自行实现 TCP 协议栈）、上述离线算法也很慢（启动一次附带 O(N) 时间）

我来具体解读一下：松之前自己写过一个操作系统内核 “评测鸭”，为了上云也曾尝试写过 virtio-net 网卡驱动，但是当时没有成功。这次比赛松又拿出了自己的鸭子，修好了网卡驱动，接上了嵌入式网络协议栈 IwIP，然后把计算逻辑塞了进去。为了在没有控制台的云服务器上部署调试，松首先在网络上做了特殊配置，当收到某种特定的网络包时就立刻重启（称为 GG reboot）。然后松把编译好的内核放在 grub 中，使用 grub-reboot 进入自己的内核，通过 VNC 远程连接获取屏幕输出，之后想离开时就发送特殊的网络包触发 GG reboot，接着就回到了 Linux！这一系列操作让我直接跪倒在地 (:з」∠)

评测鸭内核标志性技术：GG, reboot

通过 VNC 获取远端的屏幕输出

松的定制版评测鸭内核上线后，拿到了全场最低的 10% 延迟 188us，比第二名快了 16us。然而松表示，现在用的 lwIP 还是太菜了，如果换成自己写的网络协议栈还可以再快 20us！

lwIP 太菜了

内核态选手，respect！

FPGA

那么，自己手写内核就是这个比赛的终点了吗？并不是！因为在理论上还存在着一种终极解决方案：FPGA——把所有逻辑全部固化到硬件上，直接 bypass 掉整个冯诺依曼机！

在 FPGA 方案中，输入的网络包到达网卡，通过总线协议直接进入 FPGA 上的硬件协议栈，抽取出数字串后，再进入运算电路，可以一个时钟周期做一次递推计算。在这里算法复杂度已经不重要了，因为即使是平方级别的算法，也可以通过大规模并行电路变成线性的。对于线性递推中找相同数的操作，可以开 N 个寄存器连接 N 个比较电路，在一个时钟周期内获得结果。最后再通过硬件协议栈把答案发送出去即可。

如果我们假设 FPGA 的时钟频率是 100MHz 的话，一个长度为 100 的输入串只需 1us 的计算时间。但是考虑到 CPU 具有主频优势，如果使用线性算法的话谁快谁慢还真不好说。不过再考虑到 FPGA 中硬件协议栈和网卡之间可以近乎无缝衔接，从收到数据到发出答案的时延应该可以做到 10us 以下。整体来看 FPGA 还是要比传统计算机快很多的。

虽说本次比赛的环境并不允许 FPGA 部署，但是如果未来真的开放线下接入的话，那么 FPGA 将成为整场比赛的终极大杀器。不过，FPGA 的实现难度也是很大的，主要是硬件调试起来非常困难，而且每次调试的反馈周期很长，光编译就要等十几分钟。但是，既然同学们可以三星期造台计算机，一学期造出路由器，想必距离造出“莫队交易机”也是指日可待了！

总结与反思

以上是我对整场比赛技术上的分析，最后和大家聊聊这一周经历带给我的收获和思考。

技术上的收获

首先是技术上的收获。通过这次比赛的实践，我改变了一些固有观念，同时也获得了一些教训。这些内容在前面的流水账中也都有提到，这里再集中总结一下：

\1. 异步编程模式不适用于低延迟系统

异步模式本是为高并发而生，虽然能提升整体性能，但却是以牺牲每条链路的延迟为代价的。因此在这种对实时性要求很高的场景下，异步模式并不适用，传统的同步阻塞 IO 反而是更好的选择。

\2. Rust SIMD 非常好用

本次比赛是我第一次对 Rust SIMD 库进行深入体验，感觉确实相比传统 intrinsic 在开发效率上有巨大提高，而且生成的指令质量也可以接受。相信等它稳定之后，会大幅降低开发者使用 SIMD 的门槛，使得 SIMD 的全面普及成为可能。

\3. 性能关键部分慎用第三方库

Rust 一个很香的地方就是可以方便地引用第三方库，让我们得以快速实现功能。但这也容易让人产生依赖，不加思考和审查就随手调库。事实上这些库的质量可能并没有我们想象的高，尤其是性能方面。对于程序中性能关键的部分，最终很可能需要手动对这些第三方库做优化，甚至自己重新造一遍轮子。就像我在比赛前期引入了很多看上去很 fancy 的库，到最后还是全都扬掉了。所以对于性能来说，大道至简永远是真理，没有代码胜过一切代码。

\4. 多打日志以洞察程序的行为特征

详细的日志可以帮你尽早发现程序中的异常，将 Bug 扼杀在萌芽时期。此外多输出一些统计数据也可以帮你更精准地把握程序的性能特征，甚至从数据中发现更多的 insight。

做系统做傻了怎么办

其实上面这些收获都是小菜，打完这场比赛真正让我大受震撼，直击心灵的问题是：为什么我没想到这是算法题？！

更加震撼的是，不光我一个人没想到，和我一起参加比赛的两位群友——曾经的 OI 金牌选手统统都没想到：

为什么会这样呢？只能有一个解释，那就是最近几年我们一直都在做系统，给人做傻了。

三位精通网络、操作系统、体系结构和高性能计算的专家在得知真相后逐渐自闭

当然，「做傻了」只是一种调侃的说法，这背后的原因其实相当值得回味和讨论。在我看来，这件事至少能反映出几个问题：

\1. 思维定势

很明显，我们都陷入了自己的思维定势之中。由于长期做系统相关方向，我们拿到一个问题自然会想用系统的方法解决。而恰好这个比赛的背景又是量化投资公司组织的一场“交易赛”，很容易让人联想到低延迟高频交易系统，而这又是我们比较擅长的方向。所以当球向着系统的方向踢出去之后，很容易就一条路走到黑，再也停不下来了。

\2. 信息茧房

在参加比赛的选手中，我和两位群友平时很熟，会经常在群里讨论比赛话题。而剩下还有一半的选手据说都来自公司内部，想必他们之间也会有一个群来讨论这些话题。然而我们两拨人之间却互相不认识，不知道对方是怎么做的。这样就形成了各自独立的讨论圈，或者叫信息茧房，因为你获得的信息是不断被周围环境所强化的：既然我周围的人都在讨论系统，那我就更加相信这是系统题，并且以为系统就是整个世界，完全没有意识到还有另一个世界的存在。

\3. 知其可为

所以事情的关键不在于知道它怎么做，而是知道这件事可以做。如果莫队一开始就告诉我们这是算法题，或者有人告诉我们存在线性时间的算法，那么凭借我们的知识储备总是能把它想出来的。

而事实上在比赛过程中，大部分时候我们也是看到了排行榜上别人能做到多快，才开始逼自己去想怎么才能做到这么快。最初大家都在毫秒级别互啄的时候，我是万万想不到存在微秒级别的解法的。或许有一天会出现一位大佬能把时延做到 1us 以下，我想到那时仅仅是知道这条消息就足以让人万分激动了。

\4. 用进废退

当然，上面扯了这么多，说到底还是要承认一个基本规律：人的技能是用进废退的。长期不碰算法，不写代码也不刷题，对算法的敏感度就是会衰退。其实我在比赛中也多次尝试思考算法，但是就碰到这么一个简单的区间求和问题，愣是想不到前缀和。只能说是脑子笨了，长期思考工程和哲学问题，导致数理逻辑能力下降了。

意识到这些问题，接下来是该亡羊补牢了。这件事对我有什么启示呢？其实道理大家都懂，但很多时候只有自己掉进坑里了才能意识到它们真的有用：

\1. 对于系统开发者来讲，要保持对算法和其它计算机领域的敏感度。

算法的重要性就不多说了。尽管我一直很鄙视的认为做系统不需要会算法，但不可否认目前算法能力依然是整个计算机行业里唯一的硬通货：凭竞赛上大学要考算法，上研究生要考算法，公司面试也还是考算法。 保持对其他领域的敏感同样很重要，虽说计算机系统是一切上层应用的基础，但是系统不是万能的、也没什么可高贵的。很多时候对上层应用做一点小小的改进就能起到四两拨千斤的效果。

\2. 保持开放的心态，多多接触其它圈子和不同领域的人。

过去一年的时间里我借着秋招的机会接触了很多公司和各种领域的人，给我的感觉就像打开了新世界的大门。让我意识到除了自己所在的象牙塔小圈子以外，外面其实还有很多广阔的世界：有做 DB 的，做 AI 的，做交易的；在技术之外，还有重业务的，做产品的，推商业的，搞投资的；在人生道路的选择上，有读博当老师的，有去公司挣钱的，有创业当老板的，还有在家躺着享受生活的……到处都有成功人士，人生并不是只有卷 GPA 写代码发论文这一条路，而且现实中很多事情比在学校里做一个玩具项目、水几篇论文要困难得多——这也是我很想对还在学校里的贵系同学们分享的话。所以我认为，要想避免自己被困在思维定势和信息茧房当中，就要不断扩展视野、接触更广阔的世界。只有知道了更多事情可以做，才能更从容地去选择做什么，去思考怎么做。

系统思维与算法思维

上面有点扯远了，我们继续说回系统和算法。在这个比赛中，为了做到极致的低时延，系统和算法二者都是缺一不可的。但是它们之间的思维方式其实有很大的差别，甚至可以说是正交的。

• 系统的思维是：假设计算量不变，挖掘硬件性能，增加算力，减少不必要的开销
• 算法的思维是：假设硬件性能不变，挖掘计算特征，减少计算量

回顾我的整个比赛过程，我觉得非常明显地受到了系统思维的影响：

• 首先开局无脑把一个能工作的原型实现出来，而不是去想这个问题的正确解法

• 接着为了提高性能直接上多线程增加算力，而不是想算法能怎么降低计算量

• 后面的优化完全通过性能测试指导前进的方向

• • 在宏观上：通过端到端的 perf 找出整个系统目前最大的瓶颈
  • 在微观上：通过 microbenchmark 判断一个改进是不是有效
  • 甚至于说算法上的改进，比如最简单的递推，我都是通过 benchmark 找到大整数解析的瓶颈，然后才想到的。

• 当简单的线程级并行挤不出牙膏之后，我又开始去搞更困难的指令级并行，也就是 SIMD

• 随后陷入到 SIMD 的自我娱乐当中——现代 CPU 真神奇，大整数计算真好玩

• 当 CPU 的性能被榨干之后，开始思考整个系统的瓶颈，然后打开 OS 工具箱，从里面翻出锤子扳手之类的东西，反复掂量做 tradeoff

• 然后发现所有方案的工作量都太大了，全部放弃

• 最后实在卷不过别人，达成精神胜利法：给我足够多的时间，一定能做出一个很 nb 的系统出来，大不了上 FPGA 嘛，谁能卷得过我

而一个正常的算法选手会怎么做这个题呢？我大概设想了一下 2014 年的我会怎么想：

• 首先读题，发现是个数论题。观察数据范围，发现 M 的范围有 64/128/256，可能需要使用高精度

• 思考暴力算法：发现可以用平方级别的复杂度递推

• 思考有没有线性算法

• • 结局 A：对递推公式一通变换之后，发现问题转换为在一定范围内找两个相同数字，加一个哈希表解决
  • 结局 B：没推出来，继续思考可不可以分块或者分治

• 思考常数优化：发现可以将 M 分解成多个因数分别计算

• 思考骗分策略：发现其实只算一个因数就可以了，正确率也挺高

• 思考在输入空闲期间能做什么：发现可以打表预处理后面的计算，还可以预测后面的输入……

很明显，算法思维是针对具体问题的，而系统思维更像是一种工程经验。科学的做法应该是先想算法，然后再优化系统。换言之，先思考再动手，想得越多写的越少。我觉得我做系统时间长了，就不自觉地陷入了工程师的思维陷阱，过于注重实践，认为 talk is cheap，code 才是真理。很多时候遇到问题就不会去想根本性的解决方案，而是习惯性地去找 workaround。这是一个比较危险的信号，以后真的需要多动动脑子了。

计算机系统能力

还有一个我特别想在这里讨论的话题：什么是真正的计算机系统能力？

最近几年教育部陆续举办了多场“全国大学生计算机系统能力大赛”，分别面向 CPU、编译器和操作系统（其中 CPU 赛就是同学们比较耳熟的“龙芯杯”）。虽然我有些遗憾没有参加过这些比赛，但我认识很多同学他们都在这些比赛的历练中展示出了极为惊人的能力水平。在我看来，“莫队交易赛”在某种意义上来说也是一种“计算机系统能力大赛”，而在本次比赛中 @松 的表现向我们诠释了“系统能力”的真正内涵，那就是：利用计算机系统的原理和手段 去解决实际问题的能力。

解决问题！而不是自己造轮子玩儿。这才是做系统的终极目的——这也是让我感触最深的一点。

莫队交易赛所体现出的实际问题就是，怎样以最快的速度做交易，从而在市场上赚钱。这是一个很现实的问题，也是一个很有诱惑力的问题，同时是一个很有挑战的问题。要解决这个问题，除了算法上的优化以外，还需要懂网络的原理、CPU 的原理、体系结构的原理、操作系统的原理，而这些都不是比赛规则会告诉你的。更重要的是，你需要在有限的时间里，依据这些原理，选择适当的工具，运用合理的手段，改造一个系统或者做一个新系统出来，使得你比别人快。只有做到这一点，我认为才算掌握了真正的计算机系统能力。

重温经典。试问一下如果是你你能完成吗？

所以我很敬佩松爷的一点是，他从一开始做系统的出发点就是为了解决问题。因为观察到信息竞赛中选手程序运行时间总是测不准的问题，松自己做了一个操作系统内核 评测鸭，并且把它封装成了 OJ 供大家使用。在这个 OJ 上面你的程序运行时间可以稳定在微秒级别，再也不用担心评测机波动被卡常了。松在造鸭子的过程中，陆续掌握了手撸内核、手撸驱动、手撸协议栈的技能。因此他在本次比赛中故技重施，拿鸭子一通魔改，最终成功翻盘，完全是在情理之中的事情。

相比之下，我倒要问问自己：你有勇气拿出 rCore 来和松爷对卷吗？？我觉得我属实不行，系统能力有待提高。

比赛周的精神状态

最后讲讲我在比赛周的生活状态。尽管莫队在首页上友情提醒过：「不要因为比赛影响到正常的学习工作生活」，但是面对这么刺激的场面，谁能坚持得住啊！整整一周我的大脑里面就只有这一件事：MOST！白天卷，晚上卷，上午做梦还在卷。

做梦还在卷

那一周我停下了手头所有工作，甚至组会都不开了，带着老板一起讨论这个比赛策略（康总饶命）。经常整个人处于一种极度亢奋的状态，大脑完全停不下来，因此晚上也根本睡不着觉，常常是想到了什么就立刻爬起来“再卷卷”。最后一天吃午饭的时候我甚至收到了 Apple Watch 的预警：

现在我有点理解为什么有些同学不去做量化交易了，确实太刺激了，小心脏承受不住啊。这次比赛还仅仅是模拟了在线交易中手快者得、赢者通吃的环境，就已经让人魂牵梦绕了。如果再让选手能够影响“市场”，增加策略和对打的成分，更加接近真实的交易环境……想想就更可怕了。所以为了选手的身心健康，建议下次再办比赛可以和股市交易时间同步：上午 9 点开盘，下午 3 点收盘。帮助大家养成良好的作息习惯：）

致谢

以上就是我想说的全部内容了，感谢各位读者坚持看到这里！

过去几天我陆续收到了多位读者的催更请求，也感谢各位的期待。久等了！拖了两周才更完。主要是我无法做到下笔文思泉涌，以后还是要常写点儿东西才行。

最后，还要特别感谢组织本次比赛的莫涛和罡兴投资团队，以及和我一同参赛的 @Liu Yiyuan @松 @大嗨子 @小源 同学。我个人对这种比赛形式是非常资瓷的，因为这是对主办方和参赛方都非常有利的一件事。对于公司来说，我理解办比赛的最大作用是宣传自己、招揽人才，让更多同学了解工业界在做的事情；对于参赛同学来说，这是一个学习各种奇怪知识的非常难得的机会！除此之外，还可以认识更多大佬，了解一个行业，顺便投个简历……两边都赢麻了。

正如松给出的参赛理由一样：机会难得！

希望日后还有机会参加这样有意思的比赛。我们下场比赛再见！

先查看配置

git config --global --list

再修改配置，或者进去全部删除

git config --global --edit

来源：https://e.jd.com/30797971.html

目录

• 卷首语：开源云原生和数字化新实践
• 云原生时代的开发者
• 专题导读：云原生时代的开发者
• 云原生的定义及其关键技术
• 中国云原生用户调查报告：技术应用及应用建设现状
• 2021云原生开发者现状：K8s稳居容器榜首，Docker冲顶技术热词，微服务应用热度不减
• Kubernetes联合创始人Brendan Burns：Kubernetes及其未来
• 云原生与大数据、AIoT、开源的碰撞之路——专访小米崔宝秋
• 基础设施即代码：一场变革即将到来
• Kubernetes与云原生运行时的前世今生
• Serverless：从云计算的默认编程范式到生产力
• 混沌工程+韧性工程：云原生时代可靠性治理的“王炸”
• API——现代软件基石与数字世界的连接者
• 云原生时代，如何构建一款简单易用且安全的应用管理平台？
• Kubernetes生产实践下的可观测性及故障定位
• 降本增效——美团集群调度系统的云原生实践
• 火山引擎张鑫：“原生云”时代的四个改变
• 大规模服务治理的云原生实践
• Dubbo在云原生时代的进化之道
• 网易轻舟服务网格落地实践
• 混沌工程在中国工商银行的应用实践
• 开源云原生大潮下的消息和流系统演进
• Network Service Mesh：让电信网络虚拟化迈向云原生时代
• 云原生运行时的下一个五年
• 云原生时代的异地多活架构畅想
• 云原生时代开发者，如何“变”与“不变”？
• 全面数字化转型
• 程序员的数字化转型
• 蒋涛对话英特尔中国区董事长王锐：数字化已成为推动世界革新的原动力
• 企业数字化转型的前世今生
• 企业数字化转型路径和实现技术
• 数字化转型方法论：数字化转型的失败原因及成功之道
• 数字化转型的锦囊妙计：数字化平台
• “离·坚白，合·同异”：微软数字化转型实践的思考
• 构建新一代数据服务与管理平台的背后思考
• 阿里云张瑞：程序员3.0时代到来
• 基于云原生技术突破数字化软件生产瓶颈
• 数字化就是释放比特的能力
• 字节跳动的“数字化原生”之路
• 以数据治理为价值驱动的产业数字化转型
• 企业数字化转型：因企制宜，久久为功
• 狭义工业互联网底层体系架构及应用部署
• 施耐德电气：开放自动化是工业控制系统的未来
• 工业数字化：IT+OT的数与智
• 基于数字孪生理念重新思考、架构和实现新一代工业软件
• 超融合时序数据库：消除工业数据“孤岛”
• 百味
• 《神秘的程序员们》之高并发需求

前言

　　我们正在进入一个开发范式转移的大时代！

　　十年前，Netscape创始人、硅谷著名投资人马克·安德森（Marc Andreessen）预言“软件正在吞噬世界”；数年后，软件里90%以上的代码都是开源代码，“开源正在吞噬软件”；如今，“云原生吞噬开源”，开源项目正在向云化演进。

　　近年来，容器、虚拟化、DevOps等技术快速发展，将整个开发过程、开发流程带入云端，开发范式发生巨变。同时，Kubernetes、微服务、Service Mesh等一系列新技术规范涌现，开发模式、开发工具、开发成果甚至开发商业模式都在迭代升级。

　　我们已经从过去的互联网时代步入移动互联网、云计算和大数据的时代，逐步进入全新的云原生时代。在云原生的发展道路上，开源有着非常关键的作用，它推动了云原生的发展。同样，云原生也为开源带来了最好的商业化模型。PaaS、SaaS以及IaaS服务都已进化到更加原生（Native）的状态，全面云化要来了！

　　未来，开发者的代码调用等各种服务都将被云化，随之而来的是服务将拥有更好的弹性，用户体验也将提升。当开源项目被云化后，其收入模型将更加清晰，用户能够得到最新、最可靠的服务。一方面，云原生等新技术顺应市场与企业的需求而生，另一方面，越来越多的企业正在借助云原生应用架构助力业务的数字化转型。

　　当数字化成为当下社会的主旋律之一时，企业对技术力量的需求也将不断升级。在《新程序员·开发者黄金十年》专辑里，我们曾谈到中国正迎来开发者市场的三大红利：人人都是开发者、家家都是技术公司、十万亿开发者新生态。而今，我们已经处在了全面数字化的时代，数字化正在吞噬传统行业。

　　当业务皆被数字化和数据化以后，企业的竞争力是什么？答案是：你所拥有的开发力量。

　　2021年，CSDN注册用户数量增长了近700万，实名总用户数3200万。这意味着，企业对开发者的需求仍在持续上涨。在数字化转型趋势下，开发者的机遇与挑战并存。开发者不仅要掌握新一代开发范式、学习新一代的云原生技术，未来也将朝着两大方向发展：一个方向是升级为架构级工程师，去帮助开发者开发更好的程序；另一个方向则是转变为业务专家，向以低代码驱动企业的业务发展。

　　一个拥有复合能力的程序员才能拥有更多的成长机会。随着技术开发范式的变化，数字化转型加速实现，开发者最需要做的仍然是不断学习、提升自我。

　　在《新程序员.003》中，我们聚焦“云原生时代的开发者”与“全面数字化转型”两大主题。阿里、字节跳动、网易、快手、亚马逊等互联网大厂的云原生技术的赋能者，从技术定义、技术应用、实践案例分享等方面，以直击内核的硬核输出全面解析云原生，帮助开发者在云原生时代快速找到适合自身发展的技术范式。同时，我们也将对微软、英特尔、华为、施耐德、西门子等首批开启数字化转型的企业展开报道，通过十多位技术专家分享的鲜活案例，一窥金融、新零售、工业物联网等领域的数字化转型成果，帮助更多关注数字化转型的开发者从先驱者的经验中获得启迪。

　　微软（中国）首席技术官韦青在分享他对微软数字化转型实践的思考时谈到：“真正进入数字化转型深水区的公司，会越发认识到转型的不易，也会发现很多理论性知识与现实脱节的情况。”然而，我们相信，数字化转型已是大势所趋，未来将有更多行业逐步进入全面数字化的时代。

我们之前使用Jenkins构建容器镜像，做法是 Jenkins容器挂载宿主机的socket文件到容器内部，容器内部运行 docker build 就行。

但是这样有一个问题。如果宿主机的 docker daemon 重启的话，必须把Jenkins容器也重启一遍（因为原有socket文件已失效了，但是容器内部是不知道的，还用着原有的socket文件），否则就会报错。

另外由于 /var/run/docker.sock 文件是root权限，将其挂在在容器里就存在风险了，所以挂载socket文件不是一种优雅的 docker build 方式。

kaniko

Kaniko是谷歌开源的一款用来构建容器镜像的工具。Kaniko 不依赖于Docker daemon进程，它在用户空间根据 Dockerfile 的内容逐行执行命令来构建镜像，这就和宿主机上的docker解绑了，更加安全可靠。

Kaniko 以容器镜像的方式来运行的，同时需要三个参数: Dockerfile，上下文，以及远端镜像仓库的地址。

1. Kaniko会先提取基础镜像(Dockerfile FROM 之后的镜像)的文件系统
2. 根据Dockerfile中所描述的，一条条执行命令，每一条命令执行完以后会在用户空间下面创建一个snapshot，并与存储与内存中的上一个状态进行比对，如果有变化，就将新的修改生成一个镜像层添加在基础镜像上，并且将相关的修改信息写入镜像元数据中。
3. 等所有命令执行完，kaniko会将最终镜像推送到指定的远端镜像仓库。

demo

$ cat Dockerfile
FROM alpine:latest
    
MAINTAINER <devops008@sina.com xiaomage>
    
RUN apk add busybox-extras curl
    
CMD ["echo","Hello DevOps"]

在kubernetes cluster上面创建一个pod，yaml文件如下：

apiVersion: v1
kind: Pod
metadata:
name: kaniko
spec:
 containers:
 - name: kaniko
   image: gcr.io/kaniko-project/executor:latest
   args: ["--dockerfile=/workspace/Dockerfile",
          "--context=/workspace/",
          "--destination=dllhb/kaniko-test:v0.4"]
    volumeMounts:
      - name: kaniko-secret
        mountPath: /kaniko/.docker
      - name: dockerfile
        mountPath: /workspace/Dockerfile
        subPath: Dockerfile
restartPolicy: Never
volumes:
      - name: dockerfile
        configMap:
          name: dockerfile
      - name: kaniko-secret
         projected:
         sources:
         - secret:
              name: regcred
              items:
                - key: .dockerconfigjson
                  path: config.json

• args 部分

  这部分就是上面所讲的，kaniko运行时需要三个参数: Dockerfile(–dockerfile)，上下文(–context)，远端镜像仓库(–destination)

• secret 部分

  推送至指定远端镜像仓库需要credential的支持，所以需要将credential以secret的方式挂载到/kaniko/.docker/这个目录下，文件名称为config.json，内容如下:

{   
    "auths": {
        "https://index.docker.io/v1/": {
            "auth": "AbcdEdfgEdggds="
       }
    }
    
}

其中auth的值为: echo"docker_registry_username:docker_registry_password"|base64

参考资料

• Kaniko github repo
• Kaniko- 以一种更安全可靠的方式在Kubernetes平台上构建容器镜像