kubernetes dashboard 安装并免密访问

官方的文档有点心累了。一个简单的需求硬是扣扣搜搜分成多个步骤,不一次性给出来。

索性记录现成的方案。

相关镜像如果在国内无法下载,可以在这里参考镜像名,用国外服务器 docker savedocker load加载到本地。

# Copyright 2017 The Kubernetes Authors.
#
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
#     http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.

apiVersion: v1
kind: Namespace
metadata:
  name: kubernetes-dashboard

---

apiVersion: v1
kind: ServiceAccount
metadata:
  labels:
    k8s-app: kubernetes-dashboard
  name: kubernetes-dashboard
  namespace: kubernetes-dashboard

---
kind: Service
apiVersion: v1
metadata:
  labels:
    k8s-app: kubernetes-dashboard
  name: kubernetes-dashboard-external
  namespace: kubernetes-dashboard
spec:
  ports:
    - port: 9090
      targetPort: 9090
  selector:
    k8s-app: kubernetes-dashboard

---
kind: Service
apiVersion: v1
metadata:
  labels:
    k8s-app: kubernetes-dashboard
  name: kubernetes-dashboard-external-test
  namespace: kubernetes-dashboard
spec:
  ports:
    - port: 9090
      targetPort: 9090
      nodePort: 30000
  type: NodePort
  selector:
    k8s-app: kubernetes-dashboard

---
apiVersion: v1
kind: Secret
metadata:
  labels:
    k8s-app: kubernetes-dashboard
  name: kubernetes-dashboard-certs
  namespace: kubernetes-dashboard
type: Opaque

---

apiVersion: v1
kind: Secret
metadata:
  labels:
    k8s-app: kubernetes-dashboard
  name: kubernetes-dashboard-csrf
  namespace: kubernetes-dashboard
type: Opaque
data:
  csrf: ""

---

apiVersion: v1
kind: Secret
metadata:
  labels:
    k8s-app: kubernetes-dashboard
  name: kubernetes-dashboard-key-holder
  namespace: kubernetes-dashboard
type: Opaque

---

kind: ConfigMap
apiVersion: v1
metadata:
  labels:
    k8s-app: kubernetes-dashboard
  name: kubernetes-dashboard-settings
  namespace: kubernetes-dashboard

---

apiVersion: rbac.authorization.k8s.io/v1
kind: ClusterRoleBinding
metadata:
  name: kubernetes-dashboard-v2
roleRef:
  apiGroup: rbac.authorization.k8s.io
  kind: ClusterRole
  name: cluster-admin
subjects:
- kind: ServiceAccount
  name: kubernetes-dashboard
  namespace: kubernetes-dashboard

---

kind: Deployment
apiVersion: apps/v1
metadata:
  labels:
    k8s-app: kubernetes-dashboard
  name: kubernetes-dashboard
  namespace: kubernetes-dashboard
spec:
  replicas: 1
  revisionHistoryLimit: 10
  selector:
    matchLabels:
      k8s-app: kubernetes-dashboard
  template:
    metadata:
      labels:
        k8s-app: kubernetes-dashboard
    spec:
      containers:
        - name: kubernetes-dashboard
          image: k8s.gcr.io/dashboard:v2.0.0-rc5
          ports:
            - containerPort: 9090
              protocol: TCP
          args:
            - --namespace=kubernetes-dashboard
            # Uncomment the following line to manually specify Kubernetes API server Host
            # If not specified, Dashboard will attempt to auto discover the API server and connect
            # to it. Uncomment only if the default does not work.
            # - --apiserver-host=http://my-address:port
          volumeMounts:
            - name: kubernetes-dashboard-certs
              mountPath: /certs
              # Create on-disk volume to store exec logs
            - mountPath: /tmp
              name: tmp-volume
          livenessProbe:
            httpGet:
              scheme: HTTP
              path: /
              port: 9090
            initialDelaySeconds: 30
            timeoutSeconds: 30
          securityContext:
            allowPrivilegeEscalation: false
            readOnlyRootFilesystem: true
            runAsUser: 1001
            runAsGroup: 2001
      volumes:
        - name: kubernetes-dashboard-certs
          secret:
            secretName: kubernetes-dashboard-certs
        - name: tmp-volume
          emptyDir: {}
      serviceAccountName: kubernetes-dashboard
      nodeSelector:
        "beta.kubernetes.io/os": linux
      # Comment the following tolerations if Dashboard must not be deployed on master
      tolerations:
        - key: node-role.kubernetes.io/master
          effect: NoSchedule

---

kind: Service
apiVersion: v1
metadata:
  labels:
    k8s-app: dashboard-metrics-scraper
  name: dashboard-metrics-scraper
  namespace: kubernetes-dashboard
spec:
  ports:
    - port: 8000
      targetPort: 8000
  selector:
    k8s-app: dashboard-metrics-scraper

---

kind: Deployment
apiVersion: apps/v1
metadata:
  labels:
    k8s-app: dashboard-metrics-scraper
  name: dashboard-metrics-scraper
  namespace: kubernetes-dashboard
spec:
  replicas: 1
  revisionHistoryLimit: 10
  selector:
    matchLabels:
      k8s-app: dashboard-metrics-scraper
  template:
    metadata:
      labels:
        k8s-app: dashboard-metrics-scraper
      annotations:
        seccomp.security.alpha.kubernetes.io/pod: 'runtime/default'
    spec:
      containers:
        - name: dashboard-metrics-scraper
          image: k8s.gcr.io/metrics-scraper:v1.0.3
          ports:
            - containerPort: 8000
              protocol: TCP
          livenessProbe:
            httpGet:
              scheme: HTTP
              path: /
              port: 8000
            initialDelaySeconds: 30
            timeoutSeconds: 30
          volumeMounts:
          - mountPath: /tmp
            name: tmp-volume
          securityContext:
            allowPrivilegeEscalation: false
            readOnlyRootFilesystem: true
            runAsUser: 1001
            runAsGroup: 2001
      serviceAccountName: kubernetes-dashboard
      nodeSelector:
        "beta.kubernetes.io/os": linux
      # Comment the following tolerations if Dashboard must not be deployed on master
      tolerations:
        - key: node-role.kubernetes.io/master
          effect: NoSchedule
      volumes:
        - name: tmp-volume
          emptyDir: {}


连接到 Github 时远程错误

发生了什么?

我在安装on my zsh时报错

fatal: remote error: 
  The unauthenticated git protocol on port 9418 is no longer supported.
Please see https://github.blog/2021-09-01-improving-git-protocol-security-github/ for more information.

原因?

根据官方博客,github升级了他们的安全机制,不再支持端口 9418 上未经身份验证的 git 协议错误。

解决:

  • 一 使用https:替换git:

    git config --global url."https://".insteadOf git://
    
  • 二 修改 git://github.com/

    git://github.com/... 
    

    替换成

    github:......
    

参考资料


人人都可以“机密计算”:Occlum 使用入门 —— 蚂蚁

以下原文: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 应用程序是一种基于划分的模型:在用户态的(不可信)应用程序(上图红色部分)可以嵌入 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

Occlum 是一款蚂蚁集团开源的 TEE OS,可以大幅降低 SGX 应用的开发门槛。那到底多低呢?只需要学会 Occlum的三条命令:newbuildrun。本节我们以利用 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 的用户接口为什么这样设计?而简单接口背后的技术架构又是怎样的?本节就试图回答这些问题。

Occlum 的一个设计理念是 Enclave-as-a-Container。在云原生时代,容器至关重要,容器无处不在。容器最常见的实现方式是基于 Linux 的 cgroup 和 namespace(比如 Docker),但也有基于虚拟化的实现(比如 Kata)。我们观察到,TEE 或者 Enclave 也可以作为一种容器的实现手段。因此,为了传达这种理念,同时给用户提供一种熟悉的体验,我们特意将 Occlum 的用户接口设计成与 Docker 和 OCI 标准接近。除了前面提到的 newbuildrun 三个命令,Occlum 还提供 startexecstopkill 等命令,其语意与 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% 的安全漏洞都与内存安全有关),因此更值得信赖;

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

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

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

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

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

机密计算简介

1. 应用容器安全现状

1.png

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

2. 机密计算时代到来

2.png

数据在整个生命周期有三种状态: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. 机密计算业务场景

3.png

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

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

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

4.png

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

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

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

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

5. TEE 硬件平台

5.png

支持 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)

6.png

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

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

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

7.png

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 的目标和价值

8.png

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

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

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

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

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

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

2. Inclavare Containers 架构

9.png

在介绍 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 工作流程

10.png

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

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

shim-rune 的工作流程为:

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

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

11.png

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

11-12.jpg

相比客户端签名,服务端签名优点如下:

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

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

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

5. 多团队共建合作

12.png

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 开源项目

13.png

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

目前支持的功能有:

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

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

7. Inclavare Containers 里程碑

14.png

14-15.jpg

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

15.png

ACK-TEE

1. 简介

16.png

ACK-TEE 于 2019 年 9 月立项

功能:

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

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

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

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

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

2. ACK-TEE 1.0

17.png

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

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

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

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

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

3. ACK-TEE 2.0

18.png

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字。(由于涉及安全的原因,本文已经删掉介绍公司自己平台相关的部分)。

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

主要参考的文章包括:

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

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

事实上,前面多篇文章的细节也来源于官方文档。 本人不保留本文的所有权,欢迎转载本文,让更多的人来了解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:

ARM的安全世界和非安全世界 图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介绍的应用示意图:

基于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: IRQ作为非安全世界的中断源 图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芯片的启动流程: 典型的TruestZone芯片启动流程 图7. 典型的TruestZone芯片启动流程

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

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

3. 各家TrustZone实现

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

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

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

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

4. 其它

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

    • EL0: 无特权模式(unprivileged)
    • EL1: 操作系统内核模式(OS kernel mode)
    • EL2: 虚拟机监视器模式(Hypervisor mode)
    • EL3: TrustZone monitor mode ARMv8-A Security Level
  • 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

参考资料


主机重启后网络概率性不通

云厂商的主机实例一般默认使用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

参考资料


美团集群调度系统的云原生实践 — 美团技术团队

原文: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)

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


代码优化卷翻天:莫队交易赛复盘 - 王润基

转自: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"))
 

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

img

最上面是输入的常数 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 的差别就能分出胜负,实在是太卷了!为了更直观地看出各位选手的内卷情况,官方还提供了最近一小时的分数增长曲线:

img

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

img

这时候其实还是相对势均力敌的,曲线均匀分布意味着每个人都有一些机会抢到 +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:基本递推

image-20220316173149582

进一步还可以发现,由于每次取模的数都小于 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 抓了个包:

img

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

img

结果依然没有回复!对比 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 步中提到,

image-20220316173339547

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

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

7. 猜 M4

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

img

我们发现如果答案比较长,那么中间就会以 ..... 省略,如果比较短就可以显示全,这其中肯定有些是 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 了一下程序:

img

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

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

img

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

img

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

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

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

img

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

image-20220316173426544

其中 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。

img

一跳一跳又一跳

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

img

氪金玩家

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

img

资格赛前的排行榜

下篇预告

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

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

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

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

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

img

抽到了低延迟服务器后,Omicron 毒株开始起飞(雾)

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

img

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

img

大预言家

img

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

这个时候,我思考了一番接下来的玩法:既然已经抽到了 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 位整数/浮点进行运算,大幅提升了并行计算效率。

img

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 位大整数运算。但随后的测试显示出它的性能并不好:

img

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

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

img

明明可以做得更好!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])
      }
  }

image-20220316174204654

img

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

image-20220316173856306

在具体实现上,由于我写的 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)] 生成默认的字典序比较。

image-20220316174040103

 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 的完整时间:

img

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

14. SIMD 优化 128 位整数计算

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

需要回答的问题有两个:

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

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

img

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

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

img

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

img

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

img

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

img

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

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

img

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

img

这篇文章还同时指出了 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 带来了多大的性能提升:

img

测试环境 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,并且表示效果显著: