什么是 CloudLab

OSDI、FAST 或者 SOSP 顶会文章里经常能看到作者是在 CloudLab 上做实验的。这是美国的大学和科研机构联合搭建的裸金属服务器集群，对科研工作者是免费开放使用的。和普通的云服务器不同的是，在上面申请的节点都是裸金属的，没有任何虚拟化，研究人员可以直接以 root 权限操控物理硬件。而且在 CloudLab 机型文档可以看到，它提供的硬件种类多样，有带 GPU 的也有带 FPGA 的机型，甚至还有带 BlueField 智能网卡的机器，方便科研人员探索不同的计算机系统架构。每次申请新的节点时都会恢复机器上硬件和软件的配置，所以也不用担心研究过程会对其他人造成影响。如果自己不小心搞砸了配置，也可以直接重新创建节点来恢复初始实验环境。

由于 CloudLab 提供了统一的硬件配置，所以在上面提供可复现的完整系统也很方便。其他研究人员可以直接在网站上用相同的机型配置创建相同的实验集群，然后使用预设好的磁盘镜像或者脚本就能方便地复现实验了。这样也不需要自己提供服务器让别人连进来做实验了。

如果你们实验室也有裸金属服务器想像 CloudLab 一样管理，可以参考我之前发布的OpenStack Ironic 裸金属服务器集群搭建指南用 OpenStack 搭建自己的集群。

注册使用 CloudLab

使用 CloudLab 之前需要注册账号。在 Personal Information 填个人信息，上传 SSH 秘钥方便之后连接服务器，然后在 Project Information 填入需要加入/创建 Project 的信息。建议使用 edu 邮箱。

CloudLab 不是自由注册的，而是需要加入 Project。每个 Project 都有自己的管理员，需要管理员审批之后账号才能生效。如果你所在的实验室已经有人是 Project 的管理员，那么选择 Join Existing Project 然后填上 Project 的名称，通知管理员审批通过即可。

如果还没有 Project，则选择 Start New Project 创建新的 Project，之后会有 CloudLab 的管理员来审核你的注册请求。ID 填 Project 的名称，以后别人就可以用这个 ID 加入你的 Project。Title 则简单描述你的 Project，比如实验室的名称，或者研究的课题。URL 可以填实验室组织的主页，或者 Github 地址都可以。Description 则是需要详细描述你的 Project 的用途，这里可以简单介绍下你的研究方向或者工作，打算用 CloudLab 做什么研究等等。

第一个创建 Project 的账户默认就是管理员，可以审批其他加入 Project 的请求。CloudLab 建议是教授或者长期在职的人来创建 Project，否则可能不会通过创建 Project 的申请。

开始使用 CloudLab

账号注册并审核通过后就可以登录并使用 CloudLab 的硬件资源了。需要注意的是 CloudLab 不太适合炼丹之类的应用，更多地还是适合系统方向的研究者使用。而且由于 CloudLab 提供了对底层硬件的控制权，有可能你的操作会波及到同一个交换机或者集群的其他用户（比如不小心搞挂了网络或者发起了 DDoS），如果造成严重后果的话会封号。同时 CloudLab 也不能拿来运行 Web 服务或者挖矿等，违规者也会封号。

CloudLab 上申请节点是通过创建 Experiment 来实现的。在新建实验界面可以选择需要使用的 Profile。Profile 可以理解为对集群的一系列预创建的配置，比如网络拓扑，硬件配置等，想要快速体验的话可以选默认的 small-lan 配置文件，这个是数个节点连接到同一个局域网的配置。

不同 Profile 有不同可以配置的参数。small-lan 提供了一些基本参数，例如节点数量，系统镜像，指定物理节点机型等。

图里是启动 1 个节点，镜像使用 CentOS 8 Stream，并且指定使用 c6525-25g 这个机型。可用机型在 CloudLab 机型文档可以查到。由于集群资源有限，可能你指定的节点类型不一定有空闲机器，需要到集群资源状态页面查询你想要的机器有没有空闲节点。如果当前时间没有，可以使用预约的功能来预留资源。

这里可以填实验的名称，还有针对单独的节点定制一些参数等。确认无误之后就可以点下一步开始实验了。

实验可以在指定时间之后开始（通常是配合预约资源功能使用）也可以马上开始，实验时长默认最长是 16 小时，如果需要更长需要在实验开始之后申请延长。

之后就会开始实验，分配节点，初始化机器。

初始化的时间会比较长，一般在 5~10 分钟。启动的时候可以进入节点的 Console 查看启动进程：

如果有别的需要可以在 Console 界面和启动过程交互。

节点启动完成之后可以直接在 Console 登录到 root 账户操作，或者使用列表里的 ssh 命令连接到服务器。sudo 默认是免密的。之后就可以自由的进行实验了。

实验在到期之后就会默认释放所有机器，并删除磁盘上的内容，所以如果有代码或者实验结果需要保存的，需要自行上传到云服务或者用 scp 保存下来。在 /proj 目录下也有网络挂载的持久化共享存储可以使用。

节点默认是连通外网的，下载 Github 或者装 RPM 什么的都飞快。装好软件包之后，为了节省时间，可以创建磁盘镜像，下次启动的时候就可以用这个磁盘镜像快速拉起相同的环境了：

创建磁盘镜像之后可以在镜像列表查到自己创建的所有镜像，并且会有一个 URN 全局资源标识符（类似 urn:publicid:IDN+utah.cloudlab.us+image+xxxx-PG0:lustre-2.15.3）

在创建实验的时候，我们可以 Copy Profile，然后修改 small-lan 这个 Profile 的代码，把自己的镜像的 URN 添加进去，之后就能在创建实验的时候使用了：

2022 年秋招的凌冽寒风刮到了 2023 年的春招实习，经过漫长又折磨的面试流程，终于有幸得到了珍贵的阿里云 OSS 对象存储实习 offer。或许是因为阿里系的集团拆分战略调整，尽管在三月底就完成了面试流程，主管也在四月初给了明确的通过，意向书还是拖到了五月中旬才发出，等入职已经是五月底了。

当初煎熬的等待过程中，四月中还拿了字节的 SDN 部门实习 offer 以及 RisingWave 的存储引擎实习 offer，对我来说都是很大的诱惑。但最后还是对这个能跟 AWS S3 掰手腕的系统的技术架构更感兴趣，所以还是选择了这个老牌产品。

在学校的时候也仔细阅读过阿里云在 FAST ’23 上发表的介绍盘古 2.0 的文章，也曾经投递过盘古部门，不过由于个人感觉盘古过于底层，可能和在学校的科研项目也比较接近，加上论文也已经把架构介绍得很完整了，所以选择了更贴近业务，公开资料也更少的 OSS 部门。

当然，进来之前也担忧 OSS 作为一个已经沉淀了十多年的成熟产品，新人会不会没有什么可以做的新东西。等真正开始实习并且大致了解 OSS 背后技术原理以及当前的用户需求后，发现其实我的担忧是多余的。哪怕是 OSS 最基本的桶管理以及对象存储以及读取的功能，面对爆发增长的数据量和数据性能需求，也会暴露出老架构的局限性，这里面就有很多性能优化的点可做；而在数据存储之上，有各种各样的增值功能（大部分对标 S3），例如跨区域复制、数据湖生态、HDFS 生态、对象函数计算等功能开发和优化也是还有很多问题等待解决；多种多样的存储介质，磁带、ZNS SSD、SMR HDD 等让存储成本有进一步优化的空间，也带来了软件层面的适配问题；对于专有云、私有云的部署场景也催生了针对小规模硬件集群的软件架构调整需求。所以，十几年的沉淀并不会掣肘开发者，其沉淀的首屈一指的数据规模、五花八门的用户需求反而是 OSS 生命力所在。

虽然有许多面向用户的需求，但和淘宝之类的系统并不一样，OSS 的需求是可以长期保留的，而不是像购物节大促一样生命周期极短，并且许多需求也具有相当的技术挑战性；而盘古等底层技术又过于接近硬件，脱离了需求后演进较慢，接口变化也不大，更多的时间在性能优化和硬件适配上；EBS、NAS 等则并不提供公网服务，和虚拟机 ECS 服务捆绑得更紧密。另一方面来说，OSS 作为低成本大容量的存储，往往是数据的最终流向。例如虚拟机或者块存储的快照、各种日志的归档、各种媒体文件的存储，即使是现在最火的 AI，数据集和模型权重最终也是会存放在对象存储中长期存储。所以，在可见的未来，对象存储仍有顽强的生命力。

就和 ChatGPT 极简的用户界面一样，OSS 只需要通过简单的 HTTP 请求就能读写数据，不需要格式化、不需要预分配空间、随存随取、容量无限、成本低；而在最简单的用户交互背后，往往是最复杂的技术在支撑。由于使用了廉价的硬件，如何在不可靠、低性能的硬件上构建出可靠、高效的系统变为一个非常有挑战性的问题。例如，硬盘可能随时达到读写寿命而下架，需要多副本保存数据来保证数据的可用性。但是多副本一方面会浪费空间，另一方面也会影响读写性能，这就需要设计高效的高可用机制，既能够满足数据安全性，又能提供不错的数据读写性能。另外，也需要设计有效的监控系统，及时发现并自动化处理硬件故障。

由于 OSS 也是直接提供公网服务，这里面也有很多网络安全相关的技术沉淀。和通用的安全防护不一样，OSS 的安全防护有更多结合业务的功能。例如，安全防护可以只针对某个被攻击的 Bucket 生效。

而对象存储的无限容量，实际上背后是有多套集群支撑的。一方面，机器过保等情况需要大批量下架替换服务器的情况下，需要将原有数据迁移到其他的集群；另一方面加入的新机器也可以参与到原有工作负载的平衡上。对于这些内部迁移的任务，也需要复杂的一致性算法设计来保证用户能够读写到正确的数据版本。

更多的技术细节可以参考《打造具备极致容灾能力的对象存储》 这篇技术分享文章。

接下来谈谈一些实习的感受吧。我分到的团队是服务层的跨区域复制小组，工作更多的是用 C++ 开发上层的业务逻辑。作为实习生，工作也是以完成小的功能需求、性能优化和修复一些 Bug 为主。跨区域复制牵扯到 Bucket 和 Object 的管理、网络、计算资源的调度，任务 SLA 保障和容错等，开发过程中需要利用到很多数据的底层组织结构还有 KV 存储的原理相关的知识。所以尽管不是做底层的 KV 存储工作，和一般的业务 CRUD 也有所区别。总体来说在整个产品处于一个中后台的位置，能接触到的技术面还是很广的，在工作的过程中慢慢就了解了 OSS 整体的业务和核心技术了，实习体验非常好。

团队的氛围还是比较融洽和纯粹的，大家的心思都是放在如何把产品做好以及打磨技术上，并不会有网上传言的 PUA 等现象。而我认识的一些在其他团队实习的朋友的体感则并不是那么好。在技术上，也有丰富和详细的技术文档沉淀，新人能快速地了解系统的整体架构和演进历程及其背后的一些设计过程等。由于是基础存储产品，对于代码质量的要求也是十分严格的，Code Review 和测试覆盖率等工程实践都执行得非常贯彻，这也是 OSS 系统稳定性的根基。和在学校写程序或者做项目随便手工测试不同，这边的测试都需要以代码形式固化下来，同时会有严格的回归测试保证新加入的代码不会影响旧的功能。对于新手或者实习生，就会出现开发功能可能只需要一两天，然后花上一两周甚至更长来 CR 还有补全测试。不过，对于代码正确性的保证还只是依赖于 CR 和测试覆盖率，导致线上还是会有一些 bug 的出现，和 S3 采用的形式化验证还有一些先进性上的距离。实习生的权限也很少，看不了内网的技术社区，有点可惜。不过短短几个月能把自己组内的技术细节吃透也已经受益匪浅了。

工作之余的话，组里偶尔会有聚餐活动，也有每周固定的羽毛球活动，下班时间也基本不谈工作（线上出问题需要 oncall 除外）。阿里云总部现在搬到了云谷园区，是真正意义上的荒郊野岭，周围只有工地、农田和山，也没有地铁，交通不是很便利。吃饭方面，食堂的话中规中矩，菜式还是挺多样的，但味道就确实一般般，价格在 20 元一顿左右；也有 KFC 或者和府捞面等商家入驻，价格就贵一些；园区太荒，也点不到什么外卖；聚餐也基本上要开车去几公里外才有繁华一点的商圈或者饭店。饮料店的话有古茗、星巴克、瑞幸、manner，虽然茶水间没有免费咖啡机，自费买咖啡提提神也是可以的。晚饭时间有 20 元餐券，可以去食堂吃，也可以拿面包牛奶走人，过时作废，不能累计。夜宵则是有 10 元餐券，同样是过时作废。总的来说，能满足大部分吃喝需求，不过选择不多。不知道以后那边会不会繁华起来。

@王润基 在 这篇文章 里介绍了如何使用 Async Rust 封装 UCX 通信库。在那篇文章中，rjgg 已经介绍过 UCX 的机制，这里就不再重复。和 Rust 相提并论的 C++ 20 中也提供了 co_await 等异步编程语法关键词，我们可不可以也用它来封装异步通信、降低编程复杂度，而性能开销又有多大呢？答案是：可以，而且是零开销封装！

和 Rust 的异步 Future 需要一个 Runtime 负责 poll 不同，C++ 的协程仅仅是帮助编译器进行代码变换的一个语法，也就是说 C++ 的协程实际上是不需要借助类似 Tokio 等通用运行时来驱动协程运行，而是可以完全由用户决定运行的时机。正如使用 C++ 20 封装 RDMA 操作中提到的，我们只需要开启一个轮询线程，不断地轮询事件的发生，然后调用预先定义好的回调函数，就能让协程运行起来了。

具体到 UCX，这个驱动协程运行的函数就是 ucp_worker_progress ，通过不断调用这个函数，UCX 会检查 IO 事件是否完成，并调用我们发起请求时注册的回调函数。我们只需要将编译器提供的继续运行被暂停协程的函数地址保存到上下文中，并且在回调函数中调用继续运行的函数，就能驱动协程的运行了。UCX 中提供了一系列 *_nbx 函数用来发起异步操作。这些函数调用之后不会阻塞，如果操作没有完成，就返回一个地址，我们后续可以通过轮询这个地址的状态，来检查我们的操作是否完成。也就是：

ucp_request_param_t param = {};
// ... 
auto request = ucp_*_nbx(..., &param); 
while (ucp_request_check_status(request) != UCS_OK) 
  ucp_worker_progress(worker);

但很显然，如果我们使用这种阻塞的方法去轮询的话，并发度会很低，效率肯定不高。为了充分发挥 UCX 的异步性能，我们需要想办法把 C++ 提供的协程语法和回调机制结合起来。正如使用 C++ 20 封装 RDMA 操作中提到的，所有的异步操作的最终实现形态就是 awaitable，那么实现思路就很清晰了

• 在构造函数中，我们保存此次操作需要的参数。
• 在 await_ready 中发起操作，将当前 awaitable 指针保存到请求上下文。如果操作立刻完成了，那就可以节省一次打包状态的开销。
• 在 await_suspend 中，我们简单的将 coroutine_handle 保存到 awaitable 中。
• 在 await_resume 中，将操作的结果返回。对于 stream_recv，需要返回接收的字节数。对于 tag_recv 需要返回接收的字节数和发送方的 tag。

另一个需要注意的地方是，每次需要发起操作的时候都需要构造 awaitable 并调用相关函数，也就是 awaitable 处于热点路径上，我们必须尽可能减小 awaitable 的尺寸，减少代码分支，并且在传参的时候尽量避免开销大的复制操作（例如 shared_ptr 的复制，以牺牲安全性为代价换取性能）。

最终封装完成的代码见：https://github.com/howardlau1999/ucxpp

目前支持的功能有：

• UCP：Tag/Stream Send/Recv、RMO

性能测试

实现完成后，我们来看看 UCX++ 的性能如何。使用协程，可以很方便地就写出高并发的测试程序。

测试使用了两台物理服务器进行，它们的软硬件配置相同。测试环境详情：

• OS: Ubuntu 22.04 (5.15.0-46-generic)
• CPU: Intel(R) Xeon(R) Gold 6230N CPU (1 socket, 20 physical cores, 40 logical cores)
• RAM: 192 GB DDR4 2666
• HCA: Mellanox ConnectX-4 Infiniband 56G
• Compiler: gcc (Ubuntu 11.2.0-19ubuntu1)
• UCX: v1.13.0 (./contrib/configure-release)
• Infiniband Driver: MLNX_OFED_LINUX-5.6-2.0.9.0

这里就简单测试一下小包和大包的性能。Baseline 就是 UCX 附带的 ucx_perftest，这里运行的是 tag_bw 测试，测试方法是客户端不停向服务端发起 tag_send 请求，是单向的测试。对于 8B 和 256B 的测试，并发数为 1，对于单次发送 4K 和 64K 的测试，并发数为 32。测试程序全部都是单线程的，通过 taskset 以及内核的 isolcpus 选项单独隔离一个物理核进行测试。

可以看到基本上 IOPS 差距为 1% 以内，这其中还有计时方法的影响，所以可以放心使用 UCX++ 而不用担心性能问题。

重铸 C++ 荣光，我辈义不容辞！

C++ 20 中的协程非常适合封装异步操作，可以像 JavaScript 或者 Rust 那样按照顺序的方法去编写异步代码。没有协程的时候，异步操作往往是通过回调函数的方式来实现的。这就要求我们手动将程序的状态保存起来，然后在回调操作的时候重新恢复之前的执行状态。对于一些简单的操作而言，手动保存状态也可以接受，但是这不 scalable。当一个函数涉及到很多异步操作的话，手动管理保存状态就会显得很繁琐。此外，由于操作被拆分成多个回调函数，在编写代码的时候逻辑会显得比较零散，既不方便编写，也不方便阅读。

协程实际上就是将状态的打包和回调函数的编写交给编译器来实现，这样程序员就可以用顺序而且紧凑的方法去编写异步代码了。C++ 20 中的协程比起其他语言的协程实现要复杂许多，而且不像其他语言有一个比较广泛使用的运行时库。换句话说，如果你想使用 C++ 20 的协程，需要按照你自己的应用需求去编写一个驱动协程运行的运行时。这个运行时做的事情并不复杂，只需要调用编译器打包好的回调函数就可以了，理论上使用什么作为运行时都无所谓。可以是 epoll 事件循环，可以是一个线程池，也可以是 RDMA。

本文提供了一种基于 epoll 和 ibverbs 编写的 RDMA 操作库实现思路，将复杂的 RDMA 操作封装成基于协程的函数，大大提升了程序的可读性。其中 epoll 方面的作用类似 rdmacm，是在 Queue Pair（类似 TCP Socket）建立过程中使用 TCP 交换 QP 信息的。

完整代码见：https://github.com/howardlau1999/rdmapp

C++ 20 协程入门

网上关于 C++ 20 的协程资料比较多而且杂，但是都比较专注于某一个点的细节解析，比较少结合实际场合讲解的。正如前文所说，C++ 的协程实际上是编译器对我们的程序做的一种变换。我们使用协程语法，更像是在使用一种非常高级的宏，告诉编译器应该如何变换。例如，使用协程编写 TCP 服务器程序，伪代码可以理解为：

auto handle_connection(tcp_connection conn) {
  for (;;) {
    char buffer[4096];
    int n = co_await conn.recv(buffer, 4096);
    if (n == 0) co_return; // Connection closed
    // Process buffer... 
  }
}

这里的 recv 函数签名是：

tcp_connection::recv_awaitable tcp_connection::recv(char *buffer, size_t length) 

那么对于 co_await 那一行，实际上编译器会将程序转换为以下一系列操作：

1. 调用 recv 函数，这个函数返回一个类 awaitable。一个 awaitable 可以理解为一个 promise，也就是一个可能完成了，也可能没有完成的异步操作。一个 awaitable 无需继承任何类，只需要实现以下三种方法：

   class recv_awaitable {
   public:
   bool await_ready();
   // 这里的返回值类型是什么后面会讲到
   ??? await_suspend(std::coroutine_handle<> h);
   int await_resume(); 
   };

2. 然后，调用 awaitable 的 await_ready 函数，检查这个异步操作完成了没有。如果返回 true，就不用进行一系列复杂的打包操作了，继续执行。
3. 重点来了，如果 await_ready 返回 false，也就是这个异步操作还没完成（例子里就是 TCP 还没数据可读），那么编译器会将函数还没执行完成的部分以及需要使用的状态（例如 buffer 和一些局部变量）打包成一个 coroutine_handle，我们不需要关心里面具体是怎么实现的，只需要知道，这个 coroutine_handle，有一个 resume 方法，用来执行函数还没执行完的部分，以及 done 方法，检查还有没有需要执行的部分。所以很简单，无论我们使用的库是什么，只需要在事件处理函数去调用 resume 方法就可以了！
4. 那么这个 coroutine_handle 要怎么获取到？答案就是 await_suspend 方法，它的签名可以是：

   void await_suspend(std::coroutine_handle h);
   bool await_suspend(std::coroutine_handle h);
   std::coroutine_handle await_suspend(std::coroutine_handle h);

第一次看到这些签名，一个疑惑就是为什么可以有参数相同返回值不一样的签名？还有一个疑惑就是 coroutine_handle<> 是什么意思？

对于第一个疑问，答案就是，这几个签名只能选择一种实现在 awaitable 里。编译器在编译的过程中，是可以分辨出不同返回值的签名的。根据返回值类型的不同，它们对于后续协程运行过程也有不同的影响。

对于第二个疑问，这其实是 C++ 中的一种编程技巧：类型擦除。这是因为实际上每一个协程的”剩余部分“都是不同的类型，而我们又不想用虚函数这种对性能有影响的方法，那么就可以将具体的类型给”擦除“掉，变成同一种类型，从而也可以使用统一的接口。

回到 await_suspend 的三幅面孔，不同的返回类型的作用是：

• 对于 void 类型，当前函数（例子是 recv）的执行就到此为止了，直到下次调用 h.resume() 方法才会继续执行
• 对于 bool 类型，含义和 await_ready 是相反的，如果返回了 false，函数就不会暂停，会继续执行，适合调用 API 失败的时候使用，否则就和 void 一样，暂停执行
• 对于 std::coroutine_handle<> 类型，会调用这个返回了的协程类型的 resume 方法

那么我们需要在 await_suspend 方法里做的事就很清楚了，也就是调用其他库，把调用 h.resume() 作为回调函数注册到事件处理函数中。

最后，无论这个协程是在 await_ready 返回 true 后继续执行，又或者是 await_suspend 之后被继续执行了，都会在继续执行的一开始调用 await_resume 函数，并且把它的返回值作为整个 co_await 的返回值。

梳理下来，recv_awaitable 的实现思路就很清楚了：在 await_ready 里我们先试着 recv 一下，返回 EAGAIN 或者 EWOULDBLOCK 的话我们就返回 false，让编译器把协程抓手传递给我们，我们在 await_suspend 里把相关的 fd 和这个抓手的地址注册到 epoll 里。最后，在 await_resume 里，检查我们需不需要再 recv 一次，再把 recv 返回值返回即可。

伪代码就是：

extern int epfd;
class recv_awaitable {
  int fd_;
  int n_;
  char *buffer_;
  size_t length_;
public:
  recv_awaitable(int fd, char *buffer, size_t length) : fd_(fd), buffer_(buffer), length_(length) {}
  bool await_ready() {
    n_ = ::read(fd_, buffer_, length_);
    return n_ >= 0;
  }
  void await_suspend(std::coroutine_handle<> h) {
    struct epoll_event event;
    event.events = EPOLLIN;
    event.data.ptr = h.address();
    ::epoll_ctl(epfd, EPOLL_CTL_ADD, fd_, &event);
  }
  int await_resume() {
    if (n_ < 0) {
      ::epoll_ctl(epfd, EPOLL_CTL_DEL, fd_, nullptr);
      n_ = ::read(fd_, buffer_, length_);
    }
    return n_;
  }
};

而在事件循环中，我们像往常一样，不停 epoll_wait，然后调用事件的回调函数即可：

for (;;) {
  struct epoll_event event;
  ::epoll_wait(epfd, &event, 1);
  auto h = std::coroutine_handle<>::from_address(event.data.ptr);
  h.resume();
}

可以看到，我们只需要对代码进行一点点封装，就可以享受到使用协程编程的便利了。封装的方法就是将以前的 epoll_ctl 等系统调用封装成 awaitable 即可，这样经验也能轻松迁移。

当然，还有一个大问题没有解决，就是 handle_connection 这种调用了 co_await 的函数应该返回什么？我们也没有像普通函数一样使用 return，而是使用了 co_return，这又会带来什么不同？

首先，既然它能被 co_await，那么这个函数的返回值一定也需要提供上面说的 awaitable 的三个接口，否则编译器无法完成变换。而且，它也可以被“暂停执行”，也会被编译器打包成 std::coroutine_handle<>，同时，由于函数有返回值，也可能抛出异常，我们还需要更多接口去处理。

对于这种情况，我们需要返回一种 task 类型，它同样不需要继承任何类，需要实现的接口有：

template<class T>
class task {
public:
  struct promise_type {
    task<T> get_return_object() { return std::coroutine_handle::from_promise(*this); }
    awaitable initial_suspend();
    awaitable final_suspend();
    void return_value(T &&value);
    // 或者 
    void return_void();
  };
  task_awaitable operator co_await();
  task(std::coroutine_handle<promise_type> h) : h_(h) {}
  ~task() { h_.destroy(); }
  std::coroutine_handle<promise_type> h_;
};

其中一定要包含一个类型 promise_type，编译器才能做变换，变换后的结果大概是：

{
    promise-type promise promise-constructor-arguments ;
    try {
        co_await promise.initial_suspend() ;
        function-body
    } catch ( ... ) {
        if (!initial-await-resume-called)
            throw ;
        promise.unhandled_exception() ;
    }
final-suspend :
    co_await promise.final_suspend() ;
}

其中 initial_suspend 的作用是允许函数在开始执行之前先用一个 awaitable 暂停一下，比如你想先创建好任务，再一起运行。而 return_value 和 return_void 就如字面意思，在 co_return 的时候会调用。在返回前，还会再调用 final_suspend，也可以用 awaitable 暂停执行。这是为了可以做一些收尾工作，同时也可以嵌套调用协程。

这里的 task_awaitable 实现接口虽然相同，但是具体实现则不太一样。首先 await_ready 直接检查 h_.done()，而 await_suspend 则需要把这个 h_ 保存到某个位置，我们可以给 promise_type 添加一个成员变量 continuation_ 来保存，然后在 final_suspend 的时候返回出去，继续嵌套的协程。await_resume 则不需要实现什么。

template<class T>
class task {
  class task_awaitable {
    std::coroutine_handle<task<T>> h_;
    bool await_ready() { return h_.done(); }
    void await_suspend(std::coroutine_handle<> suspended) {
      h_.promise().continuation_ = suspended;
    }
    void await_resume() {}
  };
};

而这个 continuation_ 可以在 final_suspend 的时候返回出去，让它能够继续执行：

struct promise_type {
// ...
  auto final_suspend() noexcept {
    struct awaiter {
      bool await_ready() noexcept { return false; }
      std::coroutine_handle<>
      await_suspend(CoroutineHandle suspended) noexcept {
        if (suspended.promise().continuation_) {
          return suspended.promise().continuation_;
        } else {
          return std::noop_coroutine();
          }
        }
      void await_resume() noexcept {}
    };
    return awaiter{};
  }
};

这样，完整可用的协程运行时就编写完成了。代码量其实并不大，主要难度在于理解编译器是如何变换我们的程序，一旦理解后就可以轻松自如地编写协程程序了！

RDMA

RDMA 编程也和 epoll 类似，有一个循环不停地获取“完成事件”，这个完成事件中同样可以携带一个指针，利用这个指针，就可以完成我们的回调操作了，需要注意的是一般我们不在 poll 线程直接执行回调，而是放到别的线程去做，避免影响 poll：

for (;;) {
  struct ibv_wc wc;
  if (auto n = ::ibv_poll_cq(cq, &wc, 1); n > 0) {
    auto cb = reinterpret_cast<callback_ptr>(wc.wr_id);
    executor->run(cb);
  }
}

而 recv_awaitable 则和上面的 epoll 实现思路大同小异，在 await_suspend 函数中，发布一个 recv 操作（send 同理），把回调地址传到 wr_id 里就可以了。

void qp::send_awaitable::await_suspend(std::coroutine_handle<> h) {
  // ...
  auto callback = executor::make_callback([h, this](struct ibv_wc const &wc) {
    wc_ = wc;
    h.resume();
  });
  // ...
  send_wr.wr_id = reinterpret_cast<uint64_t>(callback);
  qp_->post_send(send_wr, bad_send_wr);
}

这里需要注意回调函数的生命周期起码要在回调结束之后才能结束。

扩展

如果想把协程放到后台去运行（类似 tokio::spawn 或者 thread::detach ），我们可以利用 std::promise 和 std::future，在协程运行结束时通过 promise 来设置值，调用方则使用 future 来等待执行完成或者获取返回值。而为了避免 task 被提前销毁，我们需要将其移动到堆上：

void detach() {
  auto detached_task = new task<void>(std::move(*this));
  h_.promise().set_detached_task(detached_task);
  detached_ = true;
}

对于已经被放到后台的任务，我们在 ~task 里就不销毁 coroutine_handle 了，而是在 final_suspend 后去注意释放 task 的内存即可。由于一旦注册回调之后，协程就会在事件循环的驱动下不断执行，所以我们也不需要轮询 task 的状态，如果想在完成后收到通知，用 std::future 就足够了。

前几天加的一个学校原神群里想趁原神躲猫猫活动之前在群里举办一个躲猫猫大赛，一开始是想大家简单各自比一比，然后记录分数就好。不过这样就太没意思了，躲猫猫活动里经常有人有骚操作，如果能够直播就好了。而且躲猫猫是四个人玩，观众如果能看到猎手和游侠的位置，就更有意思了。按理来说，如果大家都在校园网内，那么直播是很简单的，我只需要在我的电脑上开一个 OBS，然后让大家推流到我的电脑，我再推流合成后的画面，但是此时已经是寒假，很多人已经回家了，所以这个办法马上就被否决了。大家此时又想到了用会议软件来实现多人同屏，可是目前国内常用的飞书还有腾讯会议都不支持多人同时共享屏幕，而 Zoom 虽然支持，但并不是每个人都能方便地连接上 Zoom。因此，最终只能选择开一个云服务器，然后让云服务器接收大家的推流之后再推到 B 站即可。按理来说，我只需要开一个 Windows 的服务器，在上面安装一个 OBS，再安装一个 RTMP 服务器就大功告成了。可是作为程序员怎么能不用 Linux！但是我之前并没有音视频处理的经验，也想借这个机会学习一下音视频编程的知识，于是，我开始了研究在 Linux 下进行音视频处理的踩坑之路……

最终的效果：https://www.bilibili.com/video/BV1vT4y1y7ve

完整代码：https://github.com/howardlau1999/live/blob/main/live.cpp

总结一下需求就是，需要实现四人直播同屏，且四个人是异地的，都从公网推流，并且希望延迟尽可能低。这个看上去很简单的需求其实有很多细节需要注意处理。

当然，在 Linux 下处理音视频也是有现成的工具的，那就是 ffmpeg。经过一番简单的搜索，发现使用 ffmpeg 命令行工具就可以实现需求，只需要使用一个稍微复杂的滤镜即可。但是经过测试之后发现，这个方法虽然简单，但是稳定性却很差，如果四个流其中一个发生卡顿，会造成整个画面都会卡顿，而且经常出现时空回溯的现象。也就是说，ffmpeg 命令行工具是要等所有的输入都有响应之后才会处理下一帧。考虑到大家都是公网推流，且大家的网络以及设备高度不可控，这样的稳定性是无法接受的。所以，一个很自然的想法就是在拉流解码端和编码推流端加入一个中间层，来缓冲数据流不同步的问题。我开始研究能不能使用一些命令行工具组合来提高稳定性。首先想到的就是 mkfifo 命名管道，先用四个拉流的程序拉取每个人的直播流并解码，然后往四个命名管道写入数据，然后编写一个程序从四个管道读取数据并缓存，然后写入到新的命名管道中，如果某个拉流管道没有新的数据，就不断写入缓存中的数据。负责整合画面的推流程序则不断从管道中读取数据。程序很简单，很快就编写完毕了，但实际测试发现并没有什么用，画面反而卡顿得更厉害了，这个简单的思路行不通。而且，我们无法知道写入管道里的数据是不是刚好是一帧数据。所以，最后不得不采用了重量级的解决办法——自己调用 ffmpeg 的库函数写一个拉流推流程序。

ffmpeg 这个命令行工具实际上是 libavformat 等库函数的封装，所以，我们首先得安装 libavformat 等库。

sudo apt install libavformat-dev libavdevice-dev libavcodec-dev libavutil-dev libavfilter-dev libswscale-dev

平时我们见到的 mp4、flv 等文件实际上是一个“容器”，也就是说它只负责将已经编码好的视频和音频合并起来，而不负责编码，关于封装格式的处理，都是由 libavformat 处理的。而具体到音视频的编解码则是由 libavcodec 来处理，例如，我们网上的直播视频通常采用的是 H.264 编码，而音频则是使用 AAC 进行编码。当视频被解码之后得到的原始数据则可以使用 libavfilter 进行一些处理，比如缩放、旋转、叠加文字等等。

关于音视频部分的编解码，其实没有什么好说的，直接传入自己需要的参数给编码器，然后使用函数从编解码器获取需要的数据即可。

在新版本的 ffmpeg/libav 库中，基本上音视频数据都被抽象成 packet 和 frame 这两个数据结构了。可以认为 packet 对应的是原始数据，也就是编码后的数据，而 frame 则是解码后的数据。无论是将 RAW 的数据用 avcodec 编码成 H.264 或者 AAC，还是将编码好的 H.264 和 AAC 用 avformat 封装成 FLV 格式，都是统一采用的 frame 和 packet 来进行数据的传输。这里需要注意的是，一些函数会帮你释放 frame 和 packet，一些则会拷贝数据，在开发的时候，建议先不要写 free 和 unref 的函数，也就是任他内存泄漏，等跑通了之后，再去仔细地添加释放函数。

在解码之后，将 frame 传给 avfilter 由它来合并画面之后，将输出的 frame 重新编码为 packet 推给 B 站 RTMP 服务器。

服务器搭建

服务器除了视频合成程序以外，还需要启动一个 RTMP 服务器来接收客户端的推流，然后视频合成程序再从这个服务器进程分别把流拉下来解码处理，然后再推送给 B 站。RTMP 服务器可以使用 nginx，我这里直接使用了 OpenSRS，只需要一行命令就能启动：

docker run --rm -it -p 1935:1935 -p 1985:1985 -p 8080:8080 registry.cn-hangzhou.aliyuncs.com/ossrs/srs:5 ./objs/srs -c conf/realtime.conf

客户端推流，移动端使用的是 Larix Screencaster，体积很小而且没有广告，App Store 和 Google Play 都可以下载，电脑端就还是使用 OBS Studio。

后记

可以看到直接使用 ffmpeg/libav 库来操作音视频编解码还是比较底层的，而且也比较繁琐，如果只是单纯的想合成画面之类的，可能使用 libobs 会更好一些，但是没有时间去研究了。

实验室有二十台 R740 服务器给大家用，由于涉及到内核以及硬件方面的实验，时间一长的话不同服务器上的环境就很混乱，运维管理也很麻烦，并且虚拟化不适合我们的场景。之前 OSDI 22 AE 提供了 https://cloudlab.us 的账号，这个网站上面就是像虚拟机一样使用物理机器，可以自由组网、选择操作系统镜像直接启动、给服务器做镜像等，体验相当不错。但是他们的系统并不开源，所以我想看看有没有办法用开源的软件像他们一样直接管理裸金属服务器。

OpenStack Ironic 就是基于 OpenStack 生态的裸金属计算服务，但是网上资料比较少，虽然官方文档已经很详细了，但是针对到自己特定的需求的话还是有不少坑需要解决。这篇文章记录了搭建 Ironic 的过程，记录一下参数的配置以及如何调整具体服务的思路，也是给 Ironic 生态添加一点资料吧。

前提条件

想要搭建 Ironic，服务器必须支持带外管理 (Out-of-band management)，也就是就算不运行操作系统也能对服务器的电源、BIOS 设置等进行调整。一般的商业服务器都提供了这种功能，例如 Dell 的 iDRAC。然后需要有一台服务器作为控制节点长期运行，并且能够连接远程管理接口，通过这个管理接口远程操作其他机器。控制节点由于需要设置网络等，需要有 root 权限。

元数据的话通过 HTTP API 提供，可以保存在其他机器，但是需要确保裸机的控制节点可以访问这个 API 服务器，裸机本身也需要访问。也可以 API 服务器和控制节点都在同一台服务器，按照自己需求确定拓扑。

参考网络拓扑

上图是一种可行的网络拓扑，其中 API 和 DB 服务器和普通的 Web 服务器一样，可以部署在任意的地方，只要裸机控制节点和裸金属服务器可以访问就行了，托管在云上也是 OK 的。裸机控制节点则建议提供 3 个不同的子网，一个用于访问 API 服务器，一个用于提供裸金属集群的业务网，一个用于连接管理接口的管理网。如果没有路由器，裸机控制节点也作为可以 NAT 网关，让裸金属集群访问 API。

当然如果嫌麻烦的话，业务网和其他网络合并，然后控制器和 API 跑在同一台服务器上也是可以的，后面进行 IP 地址分配的时候注意不要产生冲突即可。业务网 IP 是后面通过 DHCP 服务分配的。

服务器配置

因为 OpenStack 服务很多，而且全部是用 Python 写的，外加需要跑一个 SQL 数据库和消息队列，所以 API 服务器尽量使用配置高一点的，否则会爆内存或者 API 超时。在我的小型部署环境里，API 服务器实测常驻内存会到 16G 以上，建议选择 32G 的内存，CPU 可以选择 8 核或者 16 核。控制节点同样需要跑不少服务，以计算为主，内存建议 16G 以上，CPU 8 核以上。

服务运行总体流程

Ironic 由于是直接操作物理服务器，所以整体的流程比虚拟机要复杂一点。这里先介绍一下一台裸金属服务器是怎么启动和关闭的，先对服务之间的互动有个大局上的把握，后面填配置的时候不至于两眼一黑。

部署 Ironic 涉及到的服务有：

• Keystone：鉴权服务
• Nova：计算服务，包含 API Server、Scheduler，依赖 Placement
• Placement：资源分配服务
• Glance：镜像存储服务，用到的启动镜像、内核、RAMdisk 都存放在这
• Neutron：网络服务，这个是最复杂的服务之一，除了 API Server，还有不同的 Agent 用来设置好网络
• Ironic：包含 Neutron Agent 接收网络配置，绑定虚拟接口到服务器上，Conductor 负责接收 Nova 指令，完成服务器管理操作
• Horizon：Web 管理界面，方便操作

开关机的流程：

1. 用户通过 API/Web 创建实例，指定裸金属服务器作为实例类型
2. Scheduler 调用 Placement 服务寻找可用的服务器，指定给 Compute 服务进行启动
3. Compute 服务标记占用服务器，调用 Ironic Conductor 开始启动过程
4. Conductor 完成 Neutron 网络等配置，尤其是 DHCP 服务
5. Conductor 从 Glance 镜像服务下载 Ironic Python Agent (IPA) 镜像，调用服务器管理接口从这个镜像启动
   • 这里的 IPA 镜像相当于一个 PE 预加载环境，就像平时安装操作系统那样启动一个纯内存的操作系统，然后通过这个操作系统完成后续的操作，所有硬件驱动必须打包在这个镜像里
6. IPA 启动后，回调 Conductor，通知它下载用户镜像，然后 IPA 开始部署用户操作系统镜像
   • 这里的操作系统镜像分为全盘镜像和分区镜像，全盘镜像包含分区表等，分区镜像就是一个普通的虚拟磁盘
   • 实际上就是把镜像 dd 到硬盘里
7. Conductor 再次调用远程管理接口，将服务器引导到用户的操作系统启动，部署完成
8. 用户删除实例后，Compute 服务调用 Conductor 进行清理操作
9. Conductor 调用服务器远程管理接口，重新引导到 IPA，清理磁盘
10. 清理完成后，调用远程管理接口，关机

以上这些服务还依赖于一些数据库用于持久化和消息队列用于 RPC 通信：

• MySQL
• Memcache
• RabbitMQ

OpenStack 整个都是用 Python 实现的，所以还需要安装 Python 3.6 以上版本。

下面所有操作都在 Yoga 版本验证过，如果没有特别说明的话，就是安装在 API 服务节点。需要注意的是，API 服务如果通过包管理安装，有的是以 systemd 系统服务形式，直接启动 Python 程序提供服务，有的是安装到 Apache 2 作为 WSGI 服务。

Keystone 鉴权服务

这个服务没什么坑，就是根据用户名密码检查权限，下发 Token 的 HTTP API 服务，直接按照官网文档安装就可以了。这个服务是其他所有服务的基础，必须最先安装好。如果有 LDAP 服务的话，建议先不接入，后续再使用其他 OpenID 服务实现统一鉴权。 这个是以系统服务形式安装的。

https://docs.openstack.org/keystone/yoga/install/index.html

Placement 资源分配服务

这个服务也没有什么坑，也直接按照官网教程操作，配置好 Keystone 服务地址和凭据即可。

https://docs.openstack.org/placement/yoga/install/index.html#installation-packages

我在 CentOS 8 上默认是以 WSGI 方式安装的，要配置一下 Apache 2，打开访问权限，否则其他服务无法访问 API，对比以下内容修改你的配置文件就可以了：

<VirtualHost *:8778>
  WSGIProcessGroup placement-api
  WSGIApplicationGroup %{GLOBAL}
  WSGIPassAuthorization On
  WSGIDaemonProcess placement-api processes=3 threads=1 user=placement group=placement
  WSGIScriptAlias / /usr/bin/placement-api
  <IfVersion >= 2.4>
    ErrorLogFormat "%M"
  </IfVersion>
  ErrorLog /var/log/placement/placement-api.log
  #SSLEngine On
  #SSLCertificateFile ...
  #SSLCertificateKeyFile ...
  <Directory /usr/bin>
    Require all denied
    # 添加以下内容
    <Files "placement-api">
      <RequireAll>
        Require all granted
        Require not env blockAccess
      </RequireAll>
    </Files>
    # 添加以上内容
  </Directory>
</VirtualHost>

Glance 镜像存储服务

这个也很简单，按照官网操作，需要注意存储镜像的路径选择一个硬盘空间足够的路径。这个默认也是安装成系统服务。

https://docs.openstack.org/glance/yoga/install/index.html

Horizon Web 界面服务

按照官网操作，并配置好和 Keystone 的 SSO 鉴权通信：

https://docs.openstack.org/horizon/yoga/install/index.html

CentOS 8 的包管理把这个安装成 WSGI，需要改 Apache 2 的配置文件，找到关于 OpenStack Dashboard 的，对比以下内容，添加好访问权限，否则访问会报 403

WSGIDaemonProcess dashboard
WSGIProcessGroup dashboard
WSGISocketPrefix run/wsgi
WSGIApplicationGroup %{GLOBAL}
WSGIScriptAlias /dashboard /usr/share/openstack-dashboard/openstack_dashboard/wsgi.py
Alias /dashboard/static /usr/share/openstack-dashboard/static

<Directory /usr/share/openstack-dashboard/openstack_dashboard>
  Options All
  AllowOverride All
  Require all granted
</Directory>

<Directory /usr/share/openstack-dashboard/static>
  Options All
  AllowOverride All
  Require all granted
</Directory>

Neutron 网络服务

API 服务

这里裸机网络的配置和虚拟机的非常不同，先按照官网把 neutron-server 配置起来，是安装成系统服务的。网络插件按照 Ironic 的教程配，跳过 Configure networking options 和 Configure the metadata agent，不要配 linuxbridge 的部分，然后也不要配 Metadata Agent：

https://docs.openstack.org/neutron/yoga/install/controller-install-rdo.html

Configure networking options 这一节，用下面 Ironic 的步骤代替，配置到 3. Restart the neutron-server service, to load the new configuration. 服务器部分就算配完了了，后面的步骤是配置裸机控制服务的

https://docs.openstack.org/ironic/yoga/install/configure-networking.html

配好 ml2 服务器部分之后，回到 https://docs.openstack.org/neutron/yoga/install/controller-install-rdo.html ，把 Finalize installation 配完

裸机控制服务

需要在裸机的控制节点安装 Open vSwitch，安装之后不要用 Unix 套接字启动 Open vSwitch 的 server，要监听 TCP 的 6640 端口，因为 neutron 是用 TCP 去连接的。还有通过 ovs-vsctl br-add 添加的网桥默认是 down 的，不要急着把物理端口加进去，否则会断网，先用 ip link set dev br-xxx up 把它拉起来，然后设置好 IP，再把物理端口加进去。配置好后，启动 neutron-openvswitch-agent 和 neutron-dhcp-agent，这两个服务都需要用到 sudo 权限，需要提前给运行服务的用户配置好免密 sudo，否则服务会起不来

在裸机控制节点，配置 Ironic 的网络 agent，从 4. Create and edit /etc/neutron/plugins/ml2/ironic_neutron_agent.ini and add the required configuration. 开始配，做到执行 ovs-vsctl show，后面的命令是在 API 节点运行的。注意创建 subnet 的时候，如果你是用域名访问的 API 服务器，需要顺便填一下 DNS，否则后面裸金属启动的时候会因为没有办法通知 OpenStack 而导致整个启动过程卡住。

https://docs.openstack.org/ironic/yoga/install/configure-networking.html

启动 neutron-openvswitch-agent 如果报了 ModuleNotFoundError，需要编辑一下报错的包名下面的 __init__.py，在文件最后 import 一下报错的模块名。

接着配置一下 Metadata Agent，这个服务是用来给 cloud-init 提供初始化元数据的，按照 Configure the metadata agent 和 Configure the Compute service to use the Networking service 做，nova 的部分先跳过不做，后面装好 nova 了再把配置填上就行：

https://docs.openstack.org/neutron/yoga/install/controller-install-rdo.html

最后安装配置 DHCP Agent，看 DHCP agent setup: OVS plug-in 一节，这个是为了 PXE 启动和动态 IP 分配，需要在机器上安装 iproute2（ip 命令） dnsmasq dhcp_release haproxy：

https://docs.openstack.org/neutron/yoga/admin/archives/config-agents.html#dhcp-agent-setup-ovs-plug-in

最后，务必确认防火墙是否放行了 DHCP 的 UDP 端口，至少需要裸金属服务器是可以访问的。

Nova 计算服务

API 服务

官网的教程是安装虚拟机的，Ironic 安装的话需要按照 Ironic 的教程来，控制节点只需要启动 openstack-nova-api、openstack-nova-conductor 和 openstack-nova-scheduler 就行了，openstack-nova-novncproxy 用不到，不需要启动，也不需要配置。

https://docs.openstack.org/nova/yoga/install/controller-install.html

上面安装好 API 服务之后，配置按照下面这个链接填：

https://docs.openstack.org/ironic/yoga/install/configure-compute.html

裸机控制服务

感觉可以装在 API 服务器上，不过我不太确定，还是安装在了裸机控制节点上。

首先参考 https://docs.openstack.org/nova/yoga/install/compute-install.html 安装 compute 服务，但是配置的话按照下面这个链接填：

https://docs.openstack.org/ironic/yoga/install/configure-compute.html

可以偷懒直接用 API 服务器的配置文件。

Ironic 裸金属服务

API 服务

按照官网配置即可。只需要装 openstack-ironic-api，可以装成系统服务，也可以装成 WSGI：

https://docs.openstack.org/ironic/yoga/install/install.html

裸机控制服务

在裸机控制节点装 openstack-ironic-conductor，主要是那一堆 driver 比较麻烦，但是官网有给了示例配置，直接复制粘贴没有什么大问题。

https://docs.openstack.org/ironic/yoga/install/setup-drivers.html

装好之后，用下面的命令检查 conductor 是不是注册成功了，务必保证两台服务器时间同步：

baremetal driver list

如果是空的，说明没注册成功，检查一下 API 服务器的防火墙是不是拦截了消息队列或者 API 服务的端口，也有可能是两台机器时间不同步。

配置 PXE 服务器

也是按照官网操作就行，可以直接下载需要的 deb、rpm 包等把引导文件解压出来，放到指定目录就可以了。

https://docs.openstack.org/ironic/yoga/install/configure-pxe.html

需要注意防火墙是否放行 TFTP 的 UDP 端口和 HTTP 服务器的 TCP 端口。

注册裸机节点

创建镜像

按照官网文档操作就行。

https://docs.openstack.org/ironic/yoga/install/configure-glance-images.html

一些参考命令：

通用软件包

export COMMON_ELEMENTS="cloud-init cloud-init-datasources mellanox growroot devuser dynamic-login baremetal dhcp-all-interfaces grub2"

# 下面这个不设置的话，会导致 cloud-init 不启动，密钥之类的注入不了
export DIB_CLOUD_INIT_DATASOURCES="Ec2, ConfigDrive, OpenStack"

CentOS 8 Stream

export DIB_RELEASE=8-stream
export DIB_DISTRIBUTION_MIRROR=https://mirrors.tuna.tsinghua.edu.cn/centos/ 
export DIB_DEV_USER_USERNAME=username
export DIB_DEV_USER_PWDLESS_SUDO=true
export DIB_DEV_USER_PASSWORD="password"
disk-image-create centos $COMMON_ELEMENTS --ramdisk dracut-ramdisk -o centos-8-stream

Debian 11

export DIB_RELEASE=bullseye 
export DIB_DISTRIBUTION_MIRROR=https://mirrors.tuna.tsinghua.edu.cn/debian/
export DIB_DEV_USER_USERNAME=username
export DIB_DEV_USER_PWDLESS_SUDO=true
export DIB_DEV_USER_PASSWORD="password"
disk-image-create debian $COMMON_ELEMENTS -o debian-11

Fedora 36

export DIB_RELEASE=36
export DIB_DEV_USER_USERNAME=username
export DIB_DEV_USER_PWDLESS_SUDO=true
export DIB_DEV_USER_PASSWORD="password"
export DIB_DISTRIBUTION_MIRROR=https://mirrors.tuna.tsinghua.edu.cn/fedora/
disk-image-create fedora $COMMON_ELEMENTS -o fedora-36

从虚拟机镜像转换

先像平时一样把虚拟机安装好，然后装好硬件需要的驱动，打开所有网络接口的 DHCP 功能，安装 cloud-init 包和其他需要的软件，把 vmlinuz 和 initrd 拷贝出来，导出虚拟磁盘之后用 qemu-img 转换 qcow2。

qemu-img convert -O qcow2 VMware-machine-disk1.vmdk VMware-machine-disk1.qcow2

上传镜像

for OS in centos-8-stream fedora-36 debian-11; do
    openstack image create ${OS}-kernel --public --disk-format aki --container-format aki --file ${OS}.vmlinuz 
    openstack image create ${OS}-initrd --public --disk-format ari --container-format ari --file ${OS}.initrd
    openstack image create ${OS} --public --disk-format qcow2 --container-format bare --property kernel_id=$(openstack image show -c id -f value ${OS}-kernel) --property ramdisk_id=$(openstack image show -c id -f value ${OS}-initrd) --file ${OS}.qcow2
done

注册裸机

如果是第一台机器，需要先创建 Flavor （也就是“机型”）：

export RAM_MB=191736
export VCPU=40
export DISK_GB=500
# 上面的信息不重要，不影响调度
export FLAVOR_NAME=baremetal
export RESOURCE_NAME=CUSTOM_$(echo $FLAVOR_NAME | tr '.:-' '___' | tr '[:lower:]' '[:upper:]')
openstack flavor create --ram $RAM_MB --vcpus $VCPU --disk $DISK_GB $FLAVOR_NAME

# 必须设置下面全部选项，否则无法调度
openstack flavor set --property resources:$RESOURCE_NAME=1 $FLAVOR_NAME
openstack flavor set --property resources:VCPU=0 $FLAVOR_NAME
openstack flavor set --property resources:MEMORY_MB=0 $FLAVOR_NAME
openstack flavor set --property resources:DISK_GB=0 $FLAVOR_NAME

配置好之后，使用 OpenStack 命令行创建一个裸金属服务器，注意 --resource-class 要和上面 flavor 对应：

export SERVER_NAME=bm-server
export DRIVER=idrac
baremetal node create --driver $SERVER_NAME --name $SERVER_NAME --resource-class $FLAVOR_NAME

这时候可以对名称之类的信息修改，然后，指定远程管理 driver 所需要的信息：

export IPA_KERNEL_UUID=xxxxxxxx-xxxx-xxxx-xxxx-xxxxxxxxxxxx
export IPA_INITRD_UUID=xxxxxxxx-xxxx-xxxx-xxxx-xxxxxxxxxxxx
export DRAC_ADDRESS=1.2.3.4
export DRAC_USERNAME=root
export DRAC_PASSWORD=123456
export REDFISH_ADDRESS=https://$DRAC_ADDRESS/redfish/v1
export REDFISH_USERNAME=root
export REDFISH_PASSWORD=123456
baremetal node set $SERVER_NAME \
  --driver-info deploy_kernel=$IPA_KERNEL_UUID \
  --driver-info deploy_ramdisk=$IPA_INITRD_UUID \
  --driver-info agent_verify_ca=False \
  --driver-info drac_address=$DRAC_ADDRESS \
  --driver-info drac_username=$DRAC_USERNAME \
  --driver-info drac_password=$DRAC_PASSWORD \
  --driver-info redfish_address=$REDFISH_ADDRESS \
  --driver-info redfish_verify_ca=False \
  --driver-info redfish_username=$REDFISH_USERNAME \
  --driver-info redfish_password=$REDFISH_PASSWORD

设置之后，使用命令将节点转移到管理状态：

baremetal node manage $SERVER_NAME

这时候，你可以手动用 baremetal port create 命令创建网卡 MAC 和节点 UUID 对应的关系，也可以用 baremetal node inspect 命令让 Ironic 自动调取远程管理接口来填充信息。

之后，运行 baremetal node validate $SERVER_NAME 验证节点配置，没有问题之后，运行 baremetal node provide $SERVER_NAME ，节点就准备完成了。

添加完之后，一定延迟之后节点就可以被调度了，如果着急的话，可以用 nova-manage cell_v2 discover_hosts 扫描一次节点。

可以用下面的命令检查能不能被调度到，列表不为空就是可以：

openstack allocation candidate list --resource $RESOURCE_NAME='1'

如果是空的话，检查一下 baremetal node show $SERVER_NAME -c provision_state 有没有问题。

部署裸机系统

Web

直接点 Create Instance，按照向导填好资料就可以了。

命令行

看文档： https://docs.openstack.org/ironic/yoga/user/deploy.html

运维命令

BIOS 设置

看文档，因机器而异：https://docs.openstack.org/ironic/yoga/admin/bios.html

baremetal node bios setting list $SERVER_NAME

下架指令

先 baremetal node retire：

https://docs.openstack.org/ironic/yoga/admin/retirement.html

然后 baremetal node delete。

救急命令

有时候节点进入了错误的状态的话，就需要人工干预修改状态，具体参考 ironic 状态机文档：

https://docs.openstack.org/ironic/yoga/user/states.html#state-machine-diagram

常用 iDRAC RACADM 命令

查询网卡 MAC 和 PCI-E 地址

racadm get nic.VndrConfigPage.1

1 可以换成其他数字。

查询网卡配置

racadm get nic.niCconfig.1

主要看 LegacyBootProto 是不是 PXE ，不是的话用 set nic.niCconfig.1.LegacyBootProto PXE 设置，不会马上生效，需要用 jobqueue create NIC.Integrated.1-1-1 -r pwrcycle -s TIME_NOW 命令创建配置任务，注意这个命令会重启 iDRAC，有失联风险。

这篇文章是 Processor Microarchitecture An Implementation Perspective 的读书笔记。虽然这本书是 2011 年出版的，讲的东西都已经有点过时了，但是作为一个入门 CPU 微架构的材料还是不错的。对于程序员来说了解 CPU 的工作原理也有助于写出更高性能的代码，充分发挥硬件性能。

在大学本科里学习的计算机组成原理一般是顺序执行标量五级流水线的 CPU，但是在现代的高性能 CPU 中，在一个时钟周期里不同的执行部件可以有多条指令同时执行（例如同时执行两个整数加法）。另外，CPU 也有可能乱序执行程序的指令（在没有数据依赖的情况下）。而在不同的执行阶段中，还可能划分更小的流水线（例如浮点数操作）。所以，现在的 CPU 的流水线可能不止五层，而且是执行模型乱序多发射的。当然，在一些对性能要求不高，而对能耗和芯片面积比较敏感的平台上，CPU 的设计则可能会简化为三级流水线。

首先介绍一下 CPU 的分类维度，第一个是是否采用了流水线设计；第二个是乱序还是顺序执行，在乱序执行中，指令可以不按程序指定的顺序执行，减少阻塞，但对外表现的行为还是和顺序执行的处理器一样；第三个是标量和超标量处理器，标量处理器的 IPC 最多为 1，因为只有一套执行单元，而不是标量处理器的就是超标量处理器，IPC 可以大于 1，例如 VLIW 处理器；第四个是向量处理器，向量处理器可以使用一条向量指令处理多个元素的向量，也就是 SIMD，例如 Intel 的 AVX 指令就是 SIMD 指令；第五个是是否多核；第六个是是否多线程，多线程和多核的区别是，多核处理器中每一个核心的硬件资源相对独立不共享，而多线程中的线程通常共用大部分的硬件资源，比如 Intel 的超线程就是多线程，一个核心上有两个线程。

大体上讲，CPU 的流水线是这样工作的。首先，取指模块从内存中获取下一条需要执行的指令，然后译码模块将指令解码为相应的控制指令。在重命名阶段，CPU 将给需要执行的指令分配寄存器，并将指令分配到一条发射队列中。在发射阶段，CPU 检查发射队列中的指令的操作数是否已经准备好了（例如已经从内存中读取了数据），将已经就绪的指令发送到执行单元执行。执行完毕之后，则需要将操作数写回寄存器，在乱序 CPU 中，则是写回重排缓冲区（ROB）。最后，当一条指令可以提交后，就真正修改 CPU 的内部状态，完成一条指令。

缓存

现在 CPU 的大多数访存操作都需要通过缓存进行（有一些 CPU 支持绕过缓存的指令），所以，有必要了解缓存的设计原理。

目前的 CPU 都通过虚拟地址来访问内存，在访问前需要进行地址转换。虚拟地址转换为物理地址的映射关系也是存储在内存中的，但由于地址转换是非常频繁的操作，所以 CPU 中有 TLB 缓存用来加速地址转换。TLB 使用虚拟地址索引，里面存放的都是页表项。

得到物理地址之后，就可以向数据缓存发起访问请求了。缓存一般是截取物理地址的一部分作为缓存行索引。在缓存中，一个缓存行索引可以对应一路或多路缓存行，具体数量称为关联度。一个索引对应一路缓存行的，称为直接映射；一个索引对应整个缓存的称为全相连；剩下的就称为 n 路组相连。

由于不同地址可能有相同的缓存行索引，所以地址除了页内偏移量以及缓存行索引的剩下的比特作为缓存行的标签，用来确定缓存是否有效。缓存的标签和数据访问可以并行执行，也可以先比较完标签再访问数据。

由于缓存处于关键路径上，为了满足现在 CPU 的高频率要求，缓存控制器本身也是流水线化的。在第一阶段，先计算出索引和标签位等，然后在第二阶段进行消歧义操作，第三阶段访问缓存，第四阶段根据偏移量从缓存行中取出相应的数据。

缓存也可以设计为先比较标签再访问数据。这样做虽然引入了额外的一个时钟周期的延迟，但是由于比较标签后可以只访问命中的那一路数据，可以减少能耗，同时缩短了关键路径，进一步提高时钟频率。

可以看出序列比较标签的缓存的流水线多了一级。对于乱序执行处理器来说，乱序执行可以掩盖多出来的一个周期，所以使用序列比较的缓存有利于频率提升。顺序处理器使用并行比较标签更为合理。

关联度越大的缓存产生冲突的几率越小，但是占用芯片面积更大，电路复杂，能耗更高，所以一般的缓存关联度不会太大，例如常见的有 12 路、16 路等。

缓存在未命中的时候需要访问下一级存储获取数据，简单的做法是阻塞这条指令，直到缓存获取到数据。但是这样对性能损失很大。在乱序处理器中，缓存允许在一条指令还没有获取到数据的时候，就执行其他不依赖这个数据的指令。另外，还有一个要求就是非阻塞，或者称为无锁的。无锁的缓存即使在有未命中的指令执行的时候，也允许处理器发射新的访存指令。为了跟踪还没有完成的访存请求，缓存中使用了未命中状态保持寄存器（MSHR）。另外，数据到达缓存的时候，会进入输入栈（现代 CPU 称为填充缓冲区 Fill Buffer），然后才写入到数据矩阵中。

对于无锁缓存来说，未命中的情况可以分为三类：

• 初级未命中：发生的第一次未命中，此时缓存会向下一层存储请求数据。
• 次级未命中：还在请求数据的缓存块再一次发生未命中的情况。
• 结构阻塞未命中：由于硬件资源不足而无法处理的次级未命中。这种未命中会因为结构冒险而导致阻塞。

MSHR 也有很多种组织方法。

上图是隐式寻址 MSHR，如果一个缓存块包含 N 个字，那么就有 N 个目的寄存器，并且还有一个寄存器保存块地址。发生初级未命中的时候，会设置这个地址寄存器以及相应字的目的寄存器。如果后续发生了次级未命中，就比较地址，并设置目的寄存器。MSHR 里保存了一个缓存块里的一个字的目的寄存器，以及一些格式信息，例如此次访存指令的位宽，是否需要符号扩展等。也就是说一个访存指令在块内的地址隐式地由目的寄存器的编号决定。

相对地就有显式寻址 MSHR。这种 MSHR 不要求目的寄存器的数量和块的大小相同，但是需要显式地在寄存器中编码一次访存请求的块内偏移。这样可以允许任意数量的未完成请求，和缓存块大小解耦。

还有一种缓存内 MSHR。因为在缓存块还没有读取完毕的时候缓存块是没有数据的，所以可以利用这个空间来保存 MSHR 信息，也不必使用额外的地址寄存器。这种设计要求缓存块额外带一个 transient 标记位，用来标记这个缓存块是不是还在获取。

现代 CPU 通常支持一个周期内发射 2 条访存指令，为了支持 CPU 的带宽需求，缓存需要提供多个读写端口。

一种简单的设计是，缓存真的提供两个读端口，也就是每个数据块都连接到两个读端口上。但是这样能耗高、延迟高、占用面积大，没有 CPU 采用这样的设计。

另一种方法是将标签和数据块复制两次，每个数据块只连接到一个读端口，这样可以降低延迟，但是在写入的时候需要同时写入两个数据块。

现代的 CPU 通常采用多 Bank 的设计，在一个周期内，不同 Bank 的请求可以并发执行，而同一个 Bank 的则会冲突，需要阻塞。每个 Bank 内都有独立的标签和数据矩阵，比较器等。这体现了分而治之的思想。

对于指令缓存来说，一般使用的是阻塞的缓存。数据缓存使用非阻塞是因为处理器可以发射多条不依赖数据的指令来掩盖延迟，但是取指的时候，之后的指令按照程序顺序隐式依赖与前面的指令。所以指令缓存发生未命中的时候，需要等之前的指令获取完毕后才能执行后面的指令。所以指令缓存就算实现为非阻塞的也没有多大用处。

由于并行比较标签可以节省一个周期的延迟，所以指令缓存可能更喜欢用这个。但是这也会导致时钟频率下降和能耗上升，需要仔细权衡 trade-off。

取指

在现代 CPU 中，取指单元一个周期可以取一条指令，也就是说取指单元需要每个周期都计算出下一条指令的地址。然而在如果是分支指令，在真正执行分支指令之前是没有办法知道下一个执行的地址是什么的。如果让取指单元空等直到执行完毕的话，那么会浪费许多 CPU 周期，造成性能下降。所以，现在的 CPU 都有一个分支目标缓冲区（BTB），用来预测下一个指令地址。由于程序里许多跳转也涉及函数的返回，一些 CPU 还有返回地址栈（RAS）。

一条简单的取指流水线可能包含四个阶段，第一个阶段是不同的分支预测器预测下一个地址，第二个阶段是根据预测器的结果确定取指地址，第三阶段则是从指令缓存中取指，第四阶段是将指令从缓存行中取出并驱动译码单元。虽然这样取指需要四个周期，但由于是流水线化的，实际上可以做到一个周期取一条指令，并且能够提供较高的时钟频率。

译码

译码单元和 ISA 有很大的关系，RISC 指令集通常是定长的，而且操作数编码在相对固定的位置，译码单元比较简单，并行度也比较高。而像 x86 这种变长的 CISC 指令集，译码单元则相当复杂，并且译码单元还需要在指令字节流里面切割出不同的指令。由于 CISC 指令太过复杂，实际上在 CPU 内部，一条 CISC 指令通常也是进一步译码为多个类似 RISC 的微指令。P6 的微指令长度为 118 位，可以从大小看出这个相比于 RISC 指令（32 位）来说，更像是译码之后的 RISC 指令。

在 Intel Core CPU 中，取指单元的指令会先放在预取缓冲区，然后指令长度译码器负责分割出多个指令，送入指令队列。译码器从指令队列取出指令并将指令译码为微指令，送入指令译码队列。对于一些简单的指令，例如寄存器-寄存器指令，只需要译码为一个微指令，而一些复杂的指令则需要译码为至多 4 个微指令，这样设计的好处是在大多数指令都是简单指令的情况下，可以节省一部分能耗而不牺牲译码带宽。对于一些极其复杂的指令，例如字符串相关的指令，则会停止正常的译码流水线，并将控制转移到 MSROM。这个 ROM 无非也是一个序列发生器，生成指令对应的微码流。

分配

在这个阶段中，CPU 主要完成两个操作：寄存器重命名和资源分配。其中寄存器重命名是为了解决命名冲突（读后写，写后写），而资源分配则是预留发射队列、重排缓冲区项、Load/Store 队列等指令后续操作可能使用的硬件资源。如果资源不足，那么这条指令就需要等待到资源可用才可以分配。有时候不同的硬件功能单元（例如访存、浮点数、整数）会有各自独立的发射队列，在分配过程中，也有可能按照指令的类型分配到不同的发射队列中。

寄存器重命名一个出名的算法是 Tomasulo 算法，这个算法用执行单元来命名输出结果的寄存器，但有个缺点是它在指令执行完成之前都要占用保留站的资源。所以现在的处理器在指令发射之后就释放发射队列项，提高执行效率。

在汇编指令中的寄存器名称是逻辑寄存器，而因为寄存器重命名，一个逻辑寄存器可能在不同时候会对应不同的物理寄存器。而实现寄存器重命名有多种方法，例如使用重排缓冲区、使用重命名缓冲区以及使用合并寄存器堆的方法。

通过重排缓冲区重命名是一种重命名方法，指令执行的结果会写入到 ROB 中，在指令提交的时候，再将 ROB 中的值写入到寄存器堆相应的位置。使用这种方法的时候，一个逻辑寄存器的值可能会映射到 ROB 中，也可能是在寄存器堆中，在执行的时候需要判断究竟需要从哪里取指。

另一种方法是上面方法的一个小改进，也就是使用重命名缓冲区。由于许多指令其实不需要写寄存器，所以如果为这些指令分配重排缓冲区项的话会浪费一些资源。所以，在改进的方法中，只为那些需要写寄存器的指令分配一个重命名项，而在指令提交的时候同样将对应的值写入寄存器堆中即可。

上面两种方法的一个缺点就是一个值需要写入两次，一次写入到缓冲区，一次写入到寄存器堆，而合并寄存器堆则节省了一次写入，而且只需要从寄存器堆读，不需要判断是否在 ROB 中。这种方法的 CPU 内部有比逻辑寄存器数量多的物理寄存器，并且 CPU 会维护一个映射表，将逻辑寄存器映射到物理寄存器。另外，还有一个环形队列，用来维护当前空闲的寄存器列表。在一条指令需要写入结果的时候，从空闲寄存器堆中分配一个寄存器，没有空闲的寄存器则需要等待。

在指令提交的时候，只需要释放原来的物理寄存器，并更新映射表即可，不需要将值复制写入。

还有一个重要的问题需要解决的是指令在什么时候读寄存器。一种是在发射前读寄存器的值，并且在发射队列中的项包含了具体的值；另一种是在发射后再读寄存器，发射队列中的项只包含逻辑寄存器编号，这种方法只需要读一次，而且不需要将值一直复制下去。理论上读寄存器的方法和重命名方法是正交的，对于合并寄存器来说，两种读的方法没有什么区别，但是使用重排缓冲区的方法更适合在发射前读寄存器。这是因为如果一条指令在执行之前，它的一个操作数寄存器有指令提交写入了，那么提交的时候就需要找到所有使用这个寄存器的指令，并将其 ROB 指针修改为指向寄存器堆。这在硬件电路实现上非常麻烦，所以使用重排缓冲区或者重命名缓冲区的 CPU 一般都是在发射前读寄存器。

在发生分支预测错误或者异常的时候，已经分配了的指令需要重置，释放队列项等，并将修改的重命名表等恢复到原来的状态。

发射

在发射阶段，CPU 会检查发射队列中的指令的源操作数是否已经就绪，一旦操作数就绪，就会将指令发射到执行单元执行。一些 CPU 可能会给不同的执行单元分配不同的发射队列，而一些 CPU 所有的执行单元共用一条发射队列。正如前面所说，读取操作数有两种方法，一种是发射前读取，另一种是发射后读取。

发射前读取的发射单元中保存了指令所需的数据（data）和寄存器编号（id）。对于一些只使用一个寄存器的指令，指令对应的有效位会置零，而就绪位标识了一个操作数是否就绪，如果就绪的话，对应的数据项则保存了对应的值。

和发射单元相关的主要有三个事件，一是发射队列分配，二是指令唤醒，三是指令选择。

在分配阶段，分配单元会尝试在发射队列分配一个发射队列项，然后进行寄存器重命名操作。然后，分配单元读取寄存器和映射表，对于已经就绪的寄存器，直接读取值，没有就绪的就保留寄存器号，最后，分配单元将指令以及相关的信息写入发射队列中。

在一个指令执行完成的时候，会发送一个唤醒信号，包含重命名之后的寄存器 ID 以及相应的值。发射单元此时根据信号匹配发射队列中的指令的源操作数寄存器 ID，并将匹配的项的就绪位设置为 1。一旦一条指令的所有有效操作数都就绪了（指令被唤醒了），那么这个指令就可以考虑被选择单元选择发射执行了。需要注意的是信号只会发送一次，如果有指令还没进入发射单元的话将无法收到信号，此时需要修改寄存器映射表中的记录，将对应的寄存器设置为可用。另外，为了避免死锁，在分配器写入发射队列项之前，也需要检查是否有信号。

正如前面所说，唤醒信号是在一个指令产生了操作结果后发出的。如图所示，如果每个指令都等到执行完成之后才唤醒的话，那么就会造成唤醒前有三个周期在空等。为了进一步提高流水线的利用率，唤醒信号可以在指令选择阶段就发出，这样等到下一条指令准备开始执行的时候，上一条指令恰好执行完成，通过转发电路，可以直接获取操作结果，避免流水线气泡。如果指令选择和唤醒不能在同一个周期完成的话，就会带来很大的性能损失。

产生唤醒信号有多种办法。一种是在指令执行前三个周期的时候就发出信号，当然具体几个周期需要根据指令的类型确定，例如整数加法操作可能只需要一个周期，而整数乘法周期则需要多个周期完成。另一种办法是将就绪位实现为移位寄存器，在指令选择之后，根据指令的执行周期数，将移位寄存器对应位置的位设为 1，同时在每一个周期都进行移位操作。这样，在第 0 位被置为 1 的时候操作数就就绪了。需要注意的是这些方法只适合延迟已经确定的指令。对于访存指令，由于实际的延迟取决于是否命中 TLB、数据缓存等，需要等到地址计算完成并访存结束之后才能唤醒。一种优化是在缓存返回命中的时候就直接唤醒，在缓存未命中的时候则等到访存结束再唤醒。另一种优化则是预测执行，在缓存未命中的时候付出一定代价，加速缓存命中的执行速度。

指令选择单元检查一条指令的操作数是否就绪和执行单元是否空闲。例如，一个只有一个乘法器的 CPU 是无法同时执行两条乘法指令的。指令选择单元非常重要，正如前面所说，为了支持指令“背靠背”地执行，选择逻辑必须在一个周期内完成。为了提高性能，现在的 CPU 通常会实现不止一个指令选择器，而是将其拆分成多个仲裁器或调度器。例如，一个支持 4 发射的 CPU 可能会实现 2 个或 4 个仲裁器，不同的执行单元静态地绑定到一个仲裁器。指令重命名之后，就会根据指令类型发送到不同的仲裁器的发射队列中。当就绪的指令多于发射宽度的时候，调度器需要根据一定的算法确定不同指令的优先级。

当指令发射到执行单元开始执行之后，对应的发射队列项就已经可以安全地回收了。一个例外是如果这条指令是访存指令，并且处理器使用了预测唤醒的话，那么就要等到安全的唤醒之后才可以回收。

对于在发射后读取寄存器的设计来说，发射器就不需要保存寄存器的值了，但是在唤醒和执行之间多了一个读取寄存器的周期。另外，发射后读取需要寄存器堆有和发射宽度一样多的读端口，而发射前读取只需要寄存器堆有和机器宽度一样多的端口。有点反直觉的是发射宽度有时候会大于机器宽度。这是因为不同的发射队列绑定了不同的执行单元，一个 4 发射的整数执行单元和一个 4 发射的浮点数执行单元的发射宽度是 8。

由于读端口的数量会影响芯片面积以及功耗，所以在发射后读取的设计中需要想办法减少读端口的数量。Alpha 21264 的优化方法是将寄存器堆分为两个复制的堆，每个有减半数量的读端口。而处理器还可以大胆地使用比最坏情况更少的读端口。为了解决读端口不足的问题，调度器可以互相协商，如果发射的指令多于读端口，那么一些调度器就暂停发射指令。但是分布式的调度器本来就是为了降低延迟，采取这样主动协商的办法可能导致延迟上升。另一种被动的方法是调度器一律发射指令，在指令执行发现读端口不足的情况下，取消指令并重新发射。这种情况有可能导致活锁问题，所以需要调度器采用更复杂的调度算法。

以上的调度算法只适用于非访存操作的。访存操作的发射要更加复杂，在一个访存操作发射的时候，要确保它和其他的访存操作没有冲突。负责处理内存依赖的机制就叫做内存消歧义策略。不同的 CPU 可能会采用不同的策略，大概可以分为非预测和预测的消歧义策略。非预测的消歧义策略在确定一个内存操作不会和之前任何的内存操作产生依赖的时候才允许执行；而预测策略则是想办法预测一个内存操作是否和另一个正在执行的内存操作产生依赖。过于保守的策略会限制指令的并行度，而过于激进的策略则会导致恢复的机制非常复杂，预测失败的时候的能耗也会急剧上升。

非预测消歧义策略主要有全序、偏序、加载/存储序。全序中，所有内存操作都是按照顺序执行的，目前已经没有乱序处理器会使用这种办法，因为这样会大大减少并行度。剩下的策略允许加载操作相对于存储操作乱序执行。加载/存储序中，加载操作按照自己的顺序执行，存储操作按照自己的顺序执行，但是加载操作不需要等待之前的存储操作访存完毕。而在偏序中，加载操作可以乱序执行，只要之前的所有存储操作的内存地址已经计算完毕即可。

一旦存储操作的内存地址计算完毕，CPU 就可以进行内存消歧义了。所以一些 CPU 会将存储操作进一步划分为两个子任务，一个是计算地址，另一个是进行实际的写入操作。

在 AMD K6 处理器中，实现的是加载/存储序。

在访存流水线中，加载队列用于按照程序顺序存放加载指令。指令在重命名之后插入到这个队列，直到它的操作数就绪并且到达了队列头部。地址生成器则是计算访存操作的地址。存储队列和加载队列类似，按照程序顺序存放存储指令，也是在重命名之后插入，并且等待操作数和到达队列头部。存储缓冲区则按程序顺序存放了存储操作，当一个操作变成 CPU 中最旧的指令的时候才会更新内存。值得注意的是，存储操作不需要等存储数据就绪就可以发射，也就是存储缓冲中的存储指令还有可能需要等待存储数据执行完成才能写入内存。

加载指令会将自己的地址和存储缓冲中的比自己旧的指令的地址做比较，同时如果正在计算地址的存储指令更旧，也会和它的地址做部分比较。之所以是部分比较是因为在比较的时候地址还没能计算完毕，所以如果一部分的位相同就认为是相同。最后加载指令检查调度器看看是否还没有更旧的存储指令没有计算出地址。如果一条加载指令和任何之前的存储指令地址相同，或者发射队列还有更旧的存储指令，整个加载流水线就需要暂停。虽然看起来加载需要按序执行有点多余，但是这是一种实现 x86 内存语义的简单方法，也就是存储需要按顺序可见，加载需要看起来像是按序执行的。Intel Core 处理器中，这个一致性要求也实现了，但是它允许预测的内存消歧义，也允许加载乱序执行，甚至允许在有存储没有计算出地址的情况下执行。

对于预测内存消歧义来说，加载指令不需要等待之前的存储指令计算出地址，但是需要特殊的硬件来识别出错误的预测并恢复执行。

图中可以看出多了一个等待表，内容是使用虚拟地址索引的 1024 个比特。当一个加载依赖于一个更早的存储指令的时候，会触发存储-加载陷阱，并相应地更新等待表，将加载指令地址相应的位置位。为了避免等待表里全部都是 1，每 16384 个周期等待表就会重置一次。

加载指令将计算好的地址写入到加载队列中，并且比较更新的加载指令的地址，如果有相同的，会触发加载-加载内存违例陷阱，这个陷阱会使得处理器从触发陷阱的指令处开始执行，如果没有需要触发陷阱，那么加载指令就继续访问内存和缓存。

在内存消歧义阶段，存储指令同样将自己的地址写入到存储队列。另外，它们还会检查是否有更新的加载指令的地址和自己的相同，如果有，就会触发存储-加载违例陷阱，并继续从加载指令开始执行。另外等待表也会更新，避免这种情况再次发生。需要注意的是没有存储-存储违例，因为存储只有在指令提交才生效，而指令提交本身就是按程序顺序的。

对于加载指令的数据消费者而言，一种保守的唤醒策略是在计算出缓存是否命中之后才发出唤醒的信号，这样会引入流水线气泡；另一种策略是预测唤醒，不管是否命中都发出唤醒信号，避免气泡。但是在缓存未命中的情况下，需要取消依赖指令的执行，并重新放入发射队列。如果发射队列这时候没有空闲位置，并且队列里的指令都依赖于这个被取消的指令，那么就会发生死锁。

死锁的解决办法也有多种，各有各的优劣势，一种办法是直接清空比被取消的指令更新的所有指令，然后重新开始执行。这种方法在预测错误很多的时候会造成性能的急剧下降。另一种方法是在确定一条指令不会被重新发射之前，不要清空对应的发射队列项。实现方法是每一个队列项都有一个发射位标记这个指令是否已经发射，如果已经发射了那指令选择逻辑就不会考虑这条指令。这种方法的性能损失比前面那种方法要少，但是需要很深的发射队列，但通常发射队列不会很长，如果队列里全是已发射而未完成的指令，同样会造成性能下降。因此，一些处理器选择另外实现一条重放队列，已经发射但还没有执行完毕的指令会先进入重放队列，在需要重发射的时候，调度器则给重放队列里的指令更高的优先级。

执行

在执行阶段，指令结果被真正地计算出来。不同的指令有不同的复杂度，因此也有不同的延迟。现在的 CPU 一般会有多个不同功能的功能单元。例如常见的有 FPU 浮点计算单元，ALU 算术逻辑单元，AGU 地址生成单元以及 BRU 分支计算单元。数据缓存是访存操作中的重要组成部分，同时访存操作还包括了地址转换单元，将虚拟地址转换为物理地址。另一个重要的结构是旁路网络，它将源数据和计算结果在不同的功能单元传递。另外，如果一些有依赖的指令想背靠背地执行，也需要旁路网络提前转发操作结果。

ALU 执行的是简单的整数操作，例如加法、减法、位操作，而整数乘除法因为太过复杂，通常由单独的功能单元执行（IMUL、IDIV）。另外，一些处理器为了节省芯片面积和能耗，会利用浮点数单元来计算整数乘除法，也就是先将整数转换为浮点数之后进行运算，最后再转换为整数。

内存地址空间模型有线性模型和分段模型，线性模型对于程序来说内存就是一整段连续的内存地址，而分段模型就是将内存分为不同的段，在段内使用偏移量访问。x86 的分段模型是最复杂的地址模型之一，它的 AGU 输入有基址、偏移量、尺度和索引四个部分。

最终的地址为 Offset = Base + (Index × Scale) + Displacement，另外 AGU 还需要检查地址是否越界。由于计算过程太复杂，可能无法在高时钟频率的条件下计算出来，所以 AGU 还可能分为多级流水线。

另一种办法是将访存操作拆分为更多的微码，但是这样会牺牲一定的发生宽度，而且访存指令就不能使用简单译码器了。

分支单元计算的是下一个需要执行的指令地址：

一般分支有三个寻址模式：直接绝对寻址、直接相对寻址以及间接寻址。直接绝对寻址的指令直接包含了下一个 PC 的值，直接相对寻址则包含了相对当前 PC 的偏移量，间接寻址则指定一个存放了下一个 PC 的寄存器。

浮点计算单元一般比较复杂，占用芯片面积很大，内部也是有多级流水线的。浮点寄存器和通用寄存器通常是分开的寄存器堆。FPU 通常除了支持乘除法以外，还可以支持三角函数运算，求平方根等。x86 除了支持 IEEE 754 的 32 位和 64 位浮点数以外，还支持 80 位的浮点数操作。

SIMD 计算单元通常用于向量计算。在最早的 Cray 超算里，SIMD 实现为向量处理器操作，支持上百个元素的向量。而 Intel CPU 的 SIMD 功能最早是为了支持游戏和多媒体应用，这些应用的向量不会很大，只有 4 个元素或者多一点。由于设计理念的不同，通常将元素较多的操作称为向量操作，而元素较少的称为 SIMD 操作。

SIMD 单元内部同样有浮点计算单元等，而且每一个单元内部还会进一步划分 Lane。一个 Lane 对应的就是一个元素的操作。Lane 的数量可能小于 SIMD 操作的宽度，在这种情况下，一个 SIMD 操作可能需要多于一个时钟周期完成。

假如一个 Lane 宽度是 64 位，SSE 操作的位宽是 128 位，那么如果有两个 Lane，一次 SSE 操作就可以在一个周期内完成（中图），否则需要两个周期（下图）。

如果等到写回阶段执行的时候才读取数据，会造成流水线气泡，流水线越深的时候气泡带来的性能损失越严重。为此，现代 CPU 都实现了旁路网络，等到计算结果一出来，就直接转发给消费者。

这种设计需要添加额外的电路和多路选择器。有一些处理器为了减少设计复杂度和提高时钟频率，也会选择不实现旁路网络，引入流水线气泡开销，并通过乱序执行填充气泡。

没有旁路网络的 CPU 中，功能单元的输出直接连接到寄存器堆的写端口，寄存器堆的读端口连接到功能单元输入。在简单的旁路网络中，输出除了连接到写端口，还直接和寄存器的读端口一起，经过多路选择器，连接到功能单元的输入端，形成了结果总线。

在比较深的流水线里面，数据可以从不同阶段的生产者转发到不同阶段的消费者。

而对于顺序处理器，旁路网络的设计可能会非常复杂。在顺序处理器中，写回阶段必须等到流水线中最慢的功能单元执行完毕之后才可以执行。对于这种延迟写入结果的操作，就称为 Staging，存放结果的寄存器成为 Staging 寄存器。

现在的处理器有很多功能单元，如果每一个单元都和其他的连接，就会形成极其复杂的旁路网络，影响时钟频率的提升。所以，一般浮点数单元和 SIMD 单元、整数单元有各自的旁路网络，减少网络复杂度。另外，AGU 一般和整数单元有关，它们也会有旁路网络连接。

当然，为了进一步降低复杂度，提升时钟频率，可以采用分而治之的原则，将不同的电路聚合在一起，不同的聚合体之间相互独立。

例如，我们可以允许一个功能单元只能旁路自己的操作结果，虽然会引入流水线气泡，但是可以降低电路复杂度，提高时钟频率，最终提高性能。这体现了系统设计中的 trade-off 考虑。

另一种思路是将寄存器堆分为两个，每个只有一半的端口（Alpha 21264），如果一个结果在其中一个寄存器堆产生，在另一个寄存器堆旁路使用，那么就需要额外的时钟周期复制一次。两个寄存器堆的内容是一样的。

更激进的做法是两个寄存器堆中的内容并不相同，执行结果只会写入局部的寄存器堆，而不会广播到另一个寄存器堆。需要使用的时候通过额外的复制机制使用。一个集群中的指令只会竞争自己集群内部的资源。

通常这种设计也会涉及到分布式的发射队列，依赖于分配阶段的指令分配机制来调度依赖的指令到同一个集群中执行。但是这对分配算法有很高的要求，需要尽可能平衡两个集群中的指令分配，不要出现一个集群很忙而另一个集群空闲的状态。

提交

为了让乱序执行的指令最终看起来像是顺序执行的，处理器在最后还需要一个提交阶段，用来强制指令以程序顺序修改最终的寄存器状态。一个 CPU 有两个状态：架构上的状态以及预测的状态。预测的状态就是架构状态加上还在执行的指令修改的状态。预测的状态并不保证最终会落实到架构状态上，因为分支预测有可能出错，也有可能在执行过程中发生异常。如果一个 CPU 可以在异常发生的时候，保证异常指令后的所有指令都不会真正修改架构状态，那么就说这个 CPU 可以提供精确的异常。

架构状态包含了每一个逻辑寄存器的状态加上内存的状态。所以，存储操作必须等到指令提交的时候才可以修改内存，而正在执行的加载指令需要检查是否在同一个地址上有更早的存储指令还没有提交。

在 Intel P6 中，使用的是 ROB 重排缓冲区来暂时保存预测状态，RRF 退休寄存器堆保存了架构状态。

在分配阶段的时候，从重排缓冲区分配一项，而在提交的时候释放重排缓冲区项，并更新架构寄存器。

提交的时候，需要通知指令队列和发射队列中的指令，指示它们需要从退休寄存器堆中读取值，而不是去重排缓冲区读。正如前面所说，所有还没执行或者读取寄存器的指令都需要检查这次通知，重命名表也需要更新。

基于重排缓冲区的乱序执行最好是在发射前读取，否则会变得很复杂。而基于合并寄存器堆的可以使用发射后读取的方式。但是这种办法相比重排缓冲区的方法，需要更复杂的管理机制。它需要一个额外的列表来保存可用的物理寄存器，而且在它能确定一个物理寄存器不再需要之前，都不能释放这个物理寄存器。一般来说，一条指令 A 写入的物理寄存器需要在另一条更新的指令 B 写入相同的逻辑寄存器后才可以释放。

对于预测执行出错的情况，需要清空流水线，并将 PC 重新设置为正确的值后开始执行。前端主要需要恢复分支预测表和 PC 寄存器，后端则需要恢复分配表、发射队列、重排缓冲区等等。对于 Intel Pentium 处理器来说，如果发生了预测错误，那么它就会等预测错误的那条分支指令以及这之前的所有指令都提交后，才开始恢复过程。恢复的过程只需要将所有的逻辑寄存器指向退休寄存器堆即可。

对于合并寄存器堆的 CPU 来说，一般不会等到分支指令提交之后才开始恢复过程。在执行的时候，CPU 会保存一个日志，记录重命名表的修改过程以及指令分配过的资源。需要恢复的时候，就根据日志恢复。日志项一般包含指令写入的逻辑寄存器以及分配给这条指令的物理寄存器或者分配给同一个逻辑寄存器的上一个物理寄存器编号。如果日志太长，那么恢复过程也会很长，所以一些处理器使用了检查点的方式截断日志。

异常一般是在提交的时候才处理，一方面我们需要保证触发异常的指令不是预测执行的，另一方面我们需要在异常发生的时候保证架构状态和异常指令之前所有指令执行完毕一样。

Berkeley 的 RISELab 最近又搞了个大新闻，在 The Sky Above The Clouds 论文中提出了 Sky Computing 的概念。总的来讲，尽管目前市场上有许多云服务可供选择，但是不同云服务使用的 API 不同，数据在不同云服务之间迁移也很麻烦，需要用户自己处理数据的迁移和不同云服务 API 调用的编写。为了更方便地使用不同云服务厂商的优势服务，需要有一个中间层来连接不同的云服务，并向用户提供一个统一的 API 来描述任务，由中间层来负责在不同云之间调度服务。

举个例子，如果用户想使用脱敏的线上数据训练一个机器模型并部署，那么他可以先在 Azure 云上进行数据脱敏，然后使用 GCP 云的 TPU 快速低成本地训练模型，然后将训练好的模型传输到 AWS 云上使用 T4 提供线上服务。

这样做的好处一是可以让使用云服务更加简单，从而扩大云服务的市场；二是可以促进更加专门的云服务；第三是允许整合不同的计算资源；第四则是出于合规性的考虑，例如对于数据存放位置在不同国家地区可能有不同的要求。

但是这个中间层并不是要重新定义一个统一的 API，然后让不同云厂商去实现，相反，它是定义了一套兼容特性集合，实现了相应特性的云服务可以加入到 Sky 中，而用户则可以在任务中指定需要的特性，由中间层自动决定可以调用哪些云服务。作者也希望未来能够提供开源的测试用例，用来测试不同的云服务是否兼容某个特性。

	分区多云	可移植多云	Sky
在不同的云上运行相同的应用	否	是	是
对用户来说云是否透明的	否	否	是
统一 API（所有的云提供同样的 API）	否	是	否
提供不同级别的 API	是	否	是

Sky 的目标并不是想要提供完整的兼容性在所有的云上运行所有的应用，而是提供一部分兼容性，使得一部分应用可以在一部分的云上运行。这是由于提供太强的兼容性会使得标准过于复杂而难以实现，并且可能阻碍创新，放宽兼容性的要求可以使得 Sky 更有实用性，也允许创新的出现。

Sky 希望用户感知不到云服务的存在，用户无需和云服务厂商打交道。虽然现在也有 Kubernetes 这种分布式集群管理调度软件，但是它没有办法让用户不关心云服务的细节，用户还是需要自己到云服务厂商购买服务并部署软件，而且它也不能自动打通不同云服务，用户想要在不同的云上运行应用还得自己手动迁移数据。Sky 则免除了这些烦恼，用户只需要指定任务的运行脚本等，然后让 Sky 自动完成即可。

Sky 并不是对未来的被动预测，而是号召大家一起来实现这个宏图，构建一个细粒度的双边市场，避免价格战或者公司勾结，并在初期推出“杀手应用”来推进 Sky 的使用。例如机器学习就是一个可能的杀手级应用，用户可以使用 Ray 配合 Sky 在不同的云上同时进行超参数搜索，而无需分别编写不同的云 API 脚本。

一开始 Sky 支持的任务可能相当有限，例如只支持使用 DAG 描述的批处理任务，同时支持的云特性也比较有限，可能只支持 GPU 等。这样做可以让开发者节省精力专注在常用的应用场景中，随着使用人群的扩大，再根据需求排定优先级开发其他的功能，也就是使用一种类似“敏捷开发”的方法来迭代系统。

而这个中间层重要的一个组件就是优化器，就和数据库中的优化器一样，负责将用户的输入根据不同云平台的成本以及迁移开销，转换为实际的执行计划，从而最小化用户的成本。虽然现在用户也可以自己按照一定的方法来计算，但是当任务变得复杂之后计算也会变得困难，同时云服务的市场价格可能随时变动，让计算机去计算更合适。优化器生成执行计划后，先由分配器在不同的云服务预留资源，如果预留失败，就让优化器重新生成计划，然后执行器在预留的资源中真正地执行任务。

而在未来，作者展望云服务厂商之前可以达成对等协议，从而使得数据在对等的云服务之间传输不需要额外的费用，进一步促进 Sky 的发展，降低用户的使用成本。

总的来说，随着云计算的成熟，以及 Serverless 的成熟，能让用户能快速上手，不用纠结选择什么云服务的什么实例规格，只需要描述自己的任务就能轻松上云的 Sky，还是很有前景的，或许是分布式计算的又一个里程碑。

End-To-End Arguments in System Design 提出在系统设计中，将一些功能放到底层实现可能是没有价值甚至多余的，相比起实现它们的成本而言。相反，只有终端的应用知道自己的具体需求是什么，无论怎么样都需要在终端的应用中实现相同的功能。在底层实现的功能往往只能起到提高性能的作用。

因为底层的抽象层往往对上层应用细节不了解，如果提供太多功能，那么所有使用到的应用都需要负担额外的开销，哪怕实际上它们并不需要相关的功能。而且，有时候底层实现的功能可能核应用的需求不符合，这时候应用反而需要想办法绕过或者修改底层，来实现自己的功能。哪怕底层的功能确实是应用所需要的，其提供的保证往往不足或者过多，应用仍然需要实现自己的一套功能。

例如，在文件传输中，哪怕底层采用了可靠的传输协议，在发送方读取文件或者接收方写入文件的过程中仍然有可能发生错误，导致文件传输出错。而这时候底层的协议并不知道文件传输的语义，也就不能对文件传输的全过程进行校验。所以，应用还是需要实现文件级别的校验和，从而确保文件传输的正确性。如果接收方发现校验和出错，那么可以简单地要求发送方重传。在这种情况下，底层网络是否可靠也不影响应用的正确性。但如果底层网络太过不可靠，那么可能导致无限的出错和重试，造成应用无法正常运行。此时，一个可靠的底层网络可以提高传输的成功率，减少重试次数，节省网络流量，提高系统的整体性能。

而贴近生活一点的例子，比如微信，即使底层使用了 TCP 的连接，我们仍然不能保证消息在发送到服务器之后服务器处理不出错，或者你的号没有被封，所以微信在应用层还是需要一套单独的确认机制来确认消息有没有发送成功。这时候的终端指的是双方的微信软件。但是即使发送成功了，你也没办法保证对面一定看到了消息，如果你想进一步确认，那么你就需要发一条“收到请回复”的消息，然后等对方回复。这时候的终端就是你和聊天对象。

可以看出，端到端的对象即使在同一个应用中，随着终端定义的不同，也会发生改变。再举一个例子就是语音通话。实时语音通话的时候，底层网络如果提供了可靠性，那么意味着会发生重传等情况，造成延迟越来越大。但是在语音通话的过程中，出现偶尔的破音、静音都是可以接受的，大不了没听清的人让对面再说一次。哪怕断线了，也可以重拨。这时候底层的可靠性就是完全多余的，这也是为什么现在的实时音视频协议喜欢用 UDP 协议而不是 TCP 协议。但是，假如不是实时音频通话，而是远程录音，那么如果发生丢包等情况，是没有办法让说话的人重新说一次的，而且由于是写入到录音文件中，实时性没有要求。在这种情况下，底层网络提供可靠性可以简化应用程序的设计，也提高了录音的质量。随着终端的改变，对于不同层次的功能设计要求可能也会发生巨大的改变。

而例如在操作系统中，以前的设计思想是操作系统内核包办一切，例如网络、存储等。但是随着硬件和应用的发展，也出现了类似 DPDK、SPDK 这种应用程序直接接管网络和存储硬件，自己从头实现网络存储栈的。也有类似 eBPF 等技术，修改内核的行为，来适应应用的需求以及提升性能。从另一方面看，这也是 Linux 实现的一个败笔，大家也喜欢在内核修修补补，最后内核变成了忒修斯之船。

CppCon 2018: G. Nishanov “Nano-coroutines to the Rescue! (Using Coroutines TS, of Course)” 的笔记。

无栈协程切换的开销很小，几乎等于一次函数调用，而在 LLC Miss 的时候，访问内存通常需要 60 ns 以上的延迟，而如果访存命令后的命令都依赖于访问的数据，那么此时 CPU 流水线就被阻塞了，无法充分并行执行指令。而 CPU 通常提供了 prefetch 指令，内存系统也提供了一定程度的并行度，可以先发出预取命令，然后切换到其他的请求执行，使得多个访存指令重叠，充分利用流水线。这时候协程也可以看成是软件实现的指令级并行调度技术。而如果使用线程切换，那线程切换的开销会比请求内存的开销还大，所以不太合适。而无栈协程的低开销则可以完美用来重叠访存和计算。

总体的思路是，把 prefetch 当成一个类似 socket 编程中的异步 read 调用，发出 prefetch 指令之后就暂停当前的协程，切换到别的协程运行。在并发请求足够多的时候，同时可以发出足够多的 prefetch 指令，而且，大概率在切换到一个需要真正访问数据的协程的时候，数据已经在 Cache 中，此时访问延迟将大大降低。

template <typename Iterator, typename Value, typename Found, typename NotFound>
auto binary_search(Iterator first, Iterator last, Value val, Found on_found, NotFound on_not_found) -> root_task {
  auto len = last - first;
  while (len > 0) {
    auto half = len / 2;
    auto middle = first + half;
    auto middle_key = co_await prefetch(*middle);
    if (middle_key < val) {
      first = middle + 1;
      len = len - half -1;
    } else {
      len = half;
    }
    if (middle_key == half) {
      co_return on_found(val, middle);
    }
  }
  co_return on_not_found(val);
}

上面是一个二分查找的例子，在数组很大的时候，可能不能完全放入 Cache 中，而且 middle 的访问模式接近于随机。这时候，如果并发请求很多（比如在一个数据库中的 Join 操作），那么就可以先发出 prefetch 指令，然后切换到另一个协程。而这个 prefetch 函数也很简单，只需要返回一个 Awaitable，在暂停协程的时候发出真正的 prefetch 指令，然后在协程恢复运行的时候发起读取内存的请求并返回值即可。

template <typename T>
struct prefetch_awaitable {
  T& value;
  prefetch_awaitable(T& value) : value(value) {}

  bool await_ready() { return false; }

  auto await_suspend(coroutine_handle<> h) {
    _mm_prefetch(static_cast<char const *>(std::addressof(value))), _MM_HINT_NTA);
    scheduler.push_back(h);
    return scheduler.pop_front();
  }

  T& await_resume() { return value; }
};

然后，对于一大堆的请求，我们生成很多协程，然后运行即可，当然，硬件能够支持的并发访存请求有限，我们需要限制并发数，否则可能导致 thrashing：

void parallel_lookup(std::vector<int> const& arr, std::vector<int> const& lookups, int concurrency) {
  size_t found = 0;
  size_t not_found = 0;

  throttler t(concurrency);
  for (auto key : lookups) {
    t.spawn(binary_search(v.begin(), v.end(), key, [&](auto) { ++found; }), [&](auto) { ++not_found; });
  }
  t.join();
}

接下来还是需要解决怎么让这些协程运行起来的问题，也就是 throttler 怎么实现。总的来说就是在生成任务的时候查看并行的协程是否达到了限制，有的话就优先执行队列里面的，否则就加入任务队列。

struct throttler {
  size_t limit;
  explicit throttler(size_t limit) : limit(limit) {}

  void spawn(root_task t) {
    if (limit == 0) {
      scheduler.pop_front().resume();
    }
    auto h = t.set_owner(this);
    scheduler.push_back(h);
    --limit;
  }

  void on_task_done() { ++limit; }
  void join() { scheduler.run(); }
  ~throttler() { join(); }
};

为了能够在运行结束的时候反馈给 throttler，协程的 task 类型需要提供接口设置对应的 throttler。而为了在生成大量协程的时候提高效率，可以使用自定义的内存分配器提高内存分配效率。

struct root_task {
  struct promise_type {
    throttler *owner = nullptr;
    suspend_never final_suspend() { owner->on_task_done(); return {}; }
    void *operator new(size_t sz) { return allocator.alloc(sz); }
    void operator delete(void *p, size_t sz) { allocator.free(p, sz); }
    /* ... */
  };

  auto set_owner(throttler *owner) {
    auto result = h;
    h.promise().owner = owner;
    h = nullptr;
    return result;
  }

  ~root_task() { if (h) h.destroy(); }
private:
  coroutine_handle<promise_type> h;
};

上面的代码在演讲者的服务器上，每次查找平均只要 7.56 ns，达到了 1.46 的 IPC，效率非常高。他还和自己手写状态机的代码进行了对比，手写状态机的实现平均每次查找需要 10 ns。他觉得这可能是由于编译器在编译协程的时候，会先进行一次函数优化，然后再编译成状态机，在编译为状态机后，针对每一个状态再进行优化。而对于手写的状态机，编译器可能就比较难优化。所以，协程甚至有“Negative-cost Abstraction” 的效果。

这个技术有一个缺点，那就是并发度应该设置多少需要手动调整， 和硬件支持的并发度相关，需要通过不断测试调参数。

参考资料

https://www.youtube.com/watch?v=j9tlJAqMV7U

视频里提到的两篇论文：

Interleaving with coroutines: a practical approach for robust index joins (VLDB 2018)

Exploiting coroutines to attack the "killer nanoseconds" (VLDB 2017)

VLDB 2021 上有个利用了相同思想的 CoroBase：GitHub – sfu-dis/corobase: Coroutine-Oriented Main-Memory Database Engine, VLDB 2021.

The Memory System: You Can’t Avoid It, You Can’t Ignore It, You Can’t Fake It 和 Innovations in Memory System 是 Synthesis Lectures on Computer Architecture 系列中关于内存的两本书。这篇文章总结了一些内存系统的细节。

内存条通常没有什么计算能力，只是作为内存控制器的一个从设备。内存控制器连接到主板上的内存通道（平时装机说的双通道就是内存通道），一个内存通道由地址/命令线和数据线组成。地址/命令线是单向的，从内存控制器到内存芯片，包含 a 位宽的地址线以及 c 位宽的命令线；数据线是双向的，包含 d 位宽的数据线。下面假设 a = 17, c = 5, d = 64。

内存通道通常运行在比 CPU 低的频率，我们买内存的时候标注的 DDR 是 Double Data Rate 的意思，也就是在时钟的上升和下降沿都传输一位数据，也就是说在一个时钟周期内，一条数据线可以传输 2d 位数据。需要注意的是，DDR 2400 的内存其实时钟频率是 1200MHz，而且地址/命令线运行的是单倍的数据传输率，也就是一个时钟周期只传输 a 位地址和 c 位命令。

为了支持这么高的通道频率，受物理电气的限制，内存通道的走线要比较短，而且负载不能太高。所以，一个内存通道上能连接的内存是有限的。高端服务器能插几十根内存条，也是因为主板上有很多的内存通道，而且不同的内存通道是由不同的内存控制器驱动的。

DDR 协议方便了内存厂商和 CPU 厂商，但是也成为了创新的一个阻力。DDR 的升级通常会带来更高的带宽以及更低的能耗，虽然 DDR5 已经面世，DDR6 还是有很大的不确定性。因为技术的升级往往会带来更高的错误率，所以新的 DDR 技术也会增加更多的保证可靠性的功能。

我们买的内存条叫 DIMM，电路板正面和背面都有 DRAM 芯片。主板上的插槽则对应内存通道，一个内存通道可能有多个插槽。DIMM 上有 Rank，一个 Rank 上的 DRAM 芯片是同时操作的，同时向数据总线读写数据。如果单个 DRAM 芯片的数据线是 8 位的，那么就叫做 x8 芯片，4 位的就叫 x4 芯片。假如数据总线是 64 位的，那么一个 Rank 需要 8 个 x8 芯片组合，或者 16 个 x4 芯片，这样才能满足数据总线的位宽。一个 DIMM 上可以有多个 Rank，例如正面是一个 Rank，背面是另一个。

一个内存通道里的一条数据线只会连接到一个 Rank 上的一个 DRAM 芯片引脚。如果内存通道支持 4 个 Rank，那么数据线就要驱动到 4 个不同引脚。为了避免总线过载，Rank 数量不能太大。一个内存通道里的地址/命令线则同时连接到了通道里所有 Rank 的每一个 DRAM 芯片上。因为负载太大，所以地址/命令线并没有采用 DDR，否则会导致信号不稳定。有时候为了进一步减少负载，DIMM 上面可能也有一个缓冲芯片，接收地址/命令后，再由缓冲芯片广播到每一个 DRAM 芯片上，这样每个地址/命令线都只需要驱动所有 DIMM 上一个单独的芯片就可以了。

因为 DRAM 芯片电路相对来说还是比较慢的，从一个 Rank 中读取数据可能需要花费 40 ns，如果我们每次都等上一个内存请求完成之后再进行下一个内存请求，那么内存系统将会慢的难以接受。和 CPU 类似，内存系统也有流水线。当内存请求在地址/控制线上发送之后，和这个请求相关的一个 Rank 内 DRAM 芯片就开始激活电路，读取数据，然后再将数据放到数据总线上发回。当一个 Rank 还在读取数据的时候，地址/控制总线就可以向其他 Rank 同时发起请求了。这样，不同 Rank 就可以同时并行地读取数据了。当然，最终数据的发回还是串行的，因为它们都连接到了一条共享的数据总线上。

这三个流水线阶段时间非常不平衡，例如发送地址/命令只需要 1 ns，读取数据则可能需要 35 ns，最终数据总线的传输需要 5 ns。虽然一个内存通道可以支持多个 Rank，但也并不会太多，例如常见的台式机上面只有双通道四插槽，那么其实每个通道只有 4 个 Rank。如果我们只利用 Rank 的并行，那么最多只能有 4 个并行的请求，还无法充分地利用流水线重叠请求。

所以，每一个 Rank 内还会划分成多个 Bank。假如一个 Rank 内再划分了 8 个 Bank，那么一个内存通道就有 32 个 Bank。每个 Bank 可以独立地处理请求，大大地增加了并行度，提高了数据总线的利用率。如果一个 Rank 由 8 个 DRAM 芯片组成，那么这个 Rank 里的每一个 Bank 都会横跨这 8 个芯片。每个 Bank 内部还会划分成子 Bank，一个子 Bank 指的是那个 Bank 的在每一个内存芯片上的每一部分。每个子 Bank 包含子 Array 和比特矩阵，这样做是为了减少数据查找的延迟以及互联的开销。一个子 Array 就是子 Bank 里比特矩阵矩阵的一行。每个比特矩阵其实就是 DRAM 单元组成的一个矩阵，每个 DRAM 单元存储 1 位数据。如果这个比特矩阵有 512 行 x 512 列，那么这个矩阵就有 256 Kb 容量。横跨一行的线叫字线，而在每一行里，每个 DRAM 单元连接的纵向的线叫位线。在每个矩阵下面都有负责处理位线信号的放大器。读取一行数据到放大器需要大概 13 ns，这也叫行激活，由 RAS 命令发起。

CPU 以一个 Cache Line 为单位向内存发起读写请求。常见的 Cache Line 大小是 64 字节。这 64 字节会分散在组成这个 Rank 和 Bank 的所有 DRAM 芯片上。如果一个 Rank 由 8 个 x8 的芯片组成，那意味着每个芯片贡献了 Cache Line 的 64 位，这 64 位又分散在了子 Bank 里的多个矩阵里。所以，一次 Cache Line 读取请求，可能会涉及到 64 个不同矩阵一行 512 位宽的数据的读取。所以，所有放大器加起来会保存 32 Kb（4 KB）的数据，一个 Bank 里保存有效数据的放大器就叫行缓冲。请求的 64 字节的 Cache Line 则从这 4 KB 的数据里截取出来，通过数据总线传输回内存通道。这时，每个矩阵负责 8 位。这个过程由 CAS 命令发起。可以看出，一次 Cache Line 的传输，虽然只需要读取 64 字节数据，但实际上激活了 4 KB 数据，这种情况就叫 “overfetch”，如果下一次 Cache Line 请求已经在行缓冲区中，那么就不用重新读取矩阵了，行缓冲充当了 DRAM 里的 Cache！

当数据读取完成后，需要 8 次 64 位的传输，每次 64 位传输里，8 个芯片里的每个负责其中不同的 8 位。因为我们使用的是 DDR，所以 8 次传输只需要 4 个内存时钟周期。

需要注意的是，一个 Bank 里同时只有一行能够被激活，在行里的数据可以读取之前，需要给 DRAM 单元充电，这个过程大概需要 13 ns，一旦充电完成，之前存放在行缓冲中的数据就丢失了。

因此，实际上内存请求还可以进一步细化为三类。第一类就是命中行缓冲的，这时候访问延迟最低，只需要 13 ns，也就是将缓冲中的数据传输到 DRAM 芯片的输出引脚的延迟；第二类是空的行访问，也就是行缓冲中没有数据，并且位线已经预充电好了，这时候需要 13 ns 来将数据传输到行缓冲，再需要 13 ns 传输到 DRAM 芯片的输出端口；第三类情况是，行缓冲中已经有数据了，而且需要访问不同的行，这时候需要 13 ns 给位线充电，13 ns 将数据传输到行缓冲，再需要 13 ns 传输到输出端口。内存控制器需要负责在合适的时机发起预充电命令，以增加第一、二类请求的可能性。

当 LLC 未命中的时候，内存访问延迟可能超过 100 ns，比如说有 60 ns 的时间，请求在内存控制器中排队，39 ns 的时间花在第三类请求的处理上，然后有 4 ns 的时间用于数据总线的传输。

看到这里，相信你也有点晕了，我也有点晕了，作者也觉得这确实太绕了。总的来讲，内存系统也是有自己的层次化结构的，从大到小分别是 DIMM、Rank、Bank、子 Bank、子 Array、比特矩阵。对于装机人员，只关心 DIMM；对于设计内存系统的工程师，则主要研究 Rank 和 Bank 带来的并行度；而微架构工程师，也就是负责内存的电路设计的人员，就主要关心子 Bank、子 Array、比特矩阵的具体物理组织方式。

CPU 发起的内存请求会先放到请求队列中，然后内存控制器翻译 CPU 请求，发送到 DRAM 队列，每个 DRAM 队列对应的是单独的内存通道。每个队列对应的是单独的内存控制器。为了增加带宽聚合在一起的内存通道通常共享同一个控制器和队列。至于物理上的 DRAM 队列是怎么实现的，通常会按 Rank 划分队列和按 Bank 划分队列。按 Bank 划分有两种方式，一种是 Bank i 的请求全部发往同一个队列，不管 Rank 是多少。另一种是每个 Bank 都有自己的队列。按 Bank 划分可能是现代计算机中限制每个内存通道的 Rank 数量的瓶颈。DRAM 队列里存放的命令包含通道号、Rank 号、行号和列号。

CPU 的命令和 DRAM 的命令都可能被乱序调度执行（而不是 FIFO）。调度器应该尽可能地保持一行是打开状态的，这样可以处理行缓冲命中的情况，这称为 Open-page 策略，对于局部性好的程序很友好。但是这个策略会导致在发生行缓冲冲突的时候有很大的延迟，所以如果程序的局部性不好，那么采取 Close-page 策略会更好，也就是在一行读完之后，就马上给位线充电，清空行缓冲。现在的内存控制器使用的是介于这两者之间的调度算法。

此外，虽然数据总线是双向的，但是每次切换方向的时候也会有一定的延迟，称为总线转向时间，大约需要 7.5 ns。所以，读和写都是分别分批处理的。读比较重要，总是第一时间处理，写的话有 Write Buffer，等 Buffer 快满了之后才切换总线方向，然后一大批地写。

为了提高行缓冲的命中率，调度器需要在每一个时钟周期都检查队列中的请求，使用 FR-FCFS 算法，尽可能选择已经充电好的请求处理，但这会导致一些线程优先级过高，需要另外的算法保证公平性。

虽然读内存的时候，CPU 是以 64 字节为单位取到缓存里，但是内存在读取数据返回给总线的时候，是需要多个时钟周期的，这些时钟周期也叫节拍。如果数据总线是 64 位（8 字节）的，那么就需要 8 拍才能把数据传输完。

DRAM 返回数据的时候，并不是直接发送到 CPU，而是先到内存控制器的缓冲区，然后再传送到 CPU。这样做的好处就是可以允许两个带宽不一致，CPU 的带宽和 DRAM 的带宽可以不同。在一些乱序的总线上，可以通过事务 ID 来区分不同的请求。

为了减轻内存控制器以及总线的电流负载，一些 DIMM 上可能会带有额外的缓冲区芯片，RDIMM 只在地址/命令线添加缓冲区，缓冲区将地址/命令数据广播到 DRAM 芯片上，DRAM 芯片的数据引脚仍然直接连接到数据总线。而 LRDIMM 则是将数据引脚也接入到缓冲区，DDR 3 是接入到一个大的缓冲区，DDR 4 则是每个DRAM 芯片有自己的缓冲区。

实际的带宽最大值往往只有理论最大值的 65%~75%，随着内存带宽使用率上升，内存延迟也会上升。带宽利用率不同阶段的延迟上升程度不一样。

另外，由于内存控制器队列、硬件 Prefetcher、总线利用率、DIMM Rank 和 Bank 都可能影响内存访问的延迟，在使用理论模型分析内存访问延迟的时候，不能简单地认为内存访问延迟是一个常数，而是需要更加复杂的访问模型来计算，例如下面的伪代码就考虑了总线带宽，硬件 Prefetch 的影响。对于复杂的系统，必须使用更复杂的模型，否则结果将出现相当大的偏差，造成“Garbage in, garbage out”的结果。

目前 DDR DRAM 的内存发展遇到了一定的瓶颈，HBM 等新技术也开始得到广泛应用。另外，为了解决 CPU 和内存之间的传输瓶颈，近数据处理也成为了热门话题，例如 In-Memory Computing。有的是利用了内存的物理电气规律来进行简单的逻辑运算，有的则是在内存芯片上安装额外的简单的处理器。目前这个领域也是方兴未艾，相关的编程语言等支持也还在研究之中。

这篇文章主要讲了当前流行的异步编程以及协程语法在 Rust 和 C++ 的基本应用，怎么封装自己的协程，以及有哪些实现细节需要注意。

协程出现的时间其实很早，最早的操作系统运行程序就是使用协程的方式，这个时候操作系统和应用程序互相协作，处于平等的地位，如果应用程序不主动返回到操作系统，那么操作系统将永远没有机会执行其他操作。

协程其实是一个比较宽泛的概念，粗略地讲，普通函数调用后，所有的局部变量都会销毁，也无法保存状态，而协程在返回之后，会保持自己的状态，在下次调用的时候，可以根据这个状态从函数的中间继续运行。例如，编译器中的词法分析器（Lexer），在每次调用之后都会根据当前的分析状态，解析出下一个词法单元给语法分析器，在返回之后，会保存当前的位置信息提供给下一次调用。这个简单的例子也可以认为是一个协程：

int counter() {
  static int count = 0;
  return count++;
}

通过将 count 变量声明为 static 类型，在函数返回之后，count 的值不会被重置，我们可以多次调用 counter 函数，得到一个递增的整数序列。复杂一点来说，假如我们在编写 HTTP 服务器，那么我们可以写出一个这样的状态机函数：

void serve_http() {
  static int step = 0;
  static int fd = ...;
  static char buffer[BUFFER];
  int n = 0;
  for (;;) {
    switch (step) {
    case 0: // Parse header
      n = read(fd);
      if (n == EWOULDBLOCK) return;
      // ...
      step = 1;
    case 1: // Parse body
      // ...
    case 2: // Send response
      // ...
    }
  }
}

可以看到，每次调用这个函数的时候，都会从 static 变量中读取之前保存的状态，看看目前应该是解析 Header 还是 Body，而如果发现还没有数据可以读的时候，就返回，让这个线程的别的函数有机会继续执行。

当然，如果使用 static 变量，那么同时只能处理一个请求，换个方法，我们可以先分配好保存状态所需的内存，然后在每次调用这个函数的时候，都将状态作为参数传入，这样我们就可以使用一个函数处理多个请求了：

struct client_state {
    int step, fd;
    char buffer[BUFFER];
};

void serve_http(struct client_state *state) {
  // Use state...
}

而主函数其实也非常简单，通过 select、epoll 等系统调用，在新的 I/O 事件发生的时候获取对应的状态指针，然后调用协程函数就可以了：

int main() {
  for (;;) {
    epoll_wait(...);
    for (struct epoll_event* p = head; p != NULL; p = p->next) {
      struct state* state = (struct state *) p->data;
      serve_http(state);
    }
  }
  return 0;
}

所以其实协程并不是什么很复杂深奥和神秘的东西，它就是方便我们异步编程的一种编程方式而已。

上面这种只保存需要的状态的协程，使用状态机的方式实现具体逻辑的，叫做无栈协程。无栈协程优势在于性能好、占用空间少，只需要保存需要的状态，但是可以看出其编程十分复杂，和平时我们直接调用函数相比有很大差别。另外，如果在协程中想要继续调用协程，则需要状态的嵌套。例如，假如发送回复的时候，我们想调用一个单独的 write_response 函数，里面又分为写 Header 和写 Body 两个步骤，那么我们可以写：

struct resp_state { int step, fd; int finished; /* ... */ };

void write_response(struct resp_state *state) {
  for (;;) {
    switch (state->step) {
    case 0:
      // ...
    case 1:
      // ...
    }
  }
}

那么我们要怎么在 serve_http 里面调用这个函数呢？一种办法是，我们在 client_state 里面保存一个 resp_state 指针，然后，在状态处于发送回复的时候，我们就在状态机中，调用 write_response 函数，然后看看 resp_state 里面的 finished 是否为 1，是就说明发送回复的状态机也执行完了，可以进行下一步操作了，否则就直接返回，等待下一次 I/O 事件。这种方法就是自顶向下的方法，每次都要从 serve_http 这个最上层的协程开始执行，并通过它来驱动子协程。

另一种办法，则需要我们对代码的整体结构做一些修改，在调用 write_response 之后，其实我们没必要每次都从 serve_http 开始往下执行，我们可以告诉主循环，让它下次收到 I/O 事件的时候，直接调用 write_response。但这时候，resp_state 就需要保存指向 client_state 的指针，在自己执行完成之后，调用 write_response，并且重新设置相应的数据结构，在下次 I/O 事件的时候，调用 write_response。

例如：

struct connection {
  (void *f)(void *state);
  void *state;  
  int fd;
}

struct resp_state { /* ... */ (void *parent)(void *state); void *parent_state; };

void write_response(struct resp_state *state) {
  for (;;) {
    switch (state->step) {
    case 0:
      // ...
    case 1:
      // ...
    }
  }
  state->parent(state->parent_state);
}

int main() {
  // ...
    for (/* each event p*/) {
      struct connection *c = (struct connection *) p->data;
      c->f(c->state);    
    }
  // ...
}

这种方法就是自底向上的方法，每次继续执行的时候，都从最后一个被调用的协程开始执行，并且子协程会保存返回点，在执行完成后返回到父协程。这样，就节省了从顶级协程一路调用下来的开销。

当然，既然有无栈协程，那么就有有栈协程。有栈协程相比无栈协程，就简单得多了。它就是在协程需要主动返回的时候，将当前的调用栈保存到堆内存中，这样就实现了状态的保存。具体来说，其实就是将系统调度线程的逻辑实现到了用户态中。而执行函数的切换，也和操作系统中切换线程进程的逻辑一样，设置 CPU 相关的寄存器，尤其是栈指针，然后跳转到指定的函数地址就完成了切换。那么问题就在于应该跳转到哪？如果像操作系统一样，那么所有协程不管如何调用，只要遇到需要挂起的情况，就将控制权转移给一个中心的调度器，调度器再选择下一个需要执行的协程继续执行，这就是对称协程。而像上面那种，在需要挂起的时候，一路返回到一开始调用的函数的，就是非对称协程了。

上面其实就是协程的一些基本概念了，但是比实际场景的协程还缺少了一些东西。例如，协程要怎么返回值呢？这里同样有多种解决办法，在自底向上的模型中，可以使用一个共享的变量来交换信息，例如在 client_state 里面添加一个 resp_ret 变量，write_response 函数可以设置这个变量，然后在继续执行 serve_http 的时候，就可以通过读取这个变量获得返回值。而在自顶向下的模型中，也可以直接使用函数的返回值。

对于无栈协程，如果全部都手写状态机的话，其实都是重复的工作，而且容易出错。所以，现代语言通常都会加入对于协程的原生支持，由编译器来生成这些状态机代码。对于有栈协程，则一般是通过库函数的方式来实现的。

如果是无栈协程，那一般在代码里会有 async 或者 await 这样的关键词，await 就是用来告诉编译器划分状态机的位置。而有栈协程，在编写程序的时候感知不到，只是需要调用协程库提供的协程创建函数，在可能阻塞的地方，协程库都会拦截系统调用，转移控制权。

例如，像 JavaScript、Python、C++、Rust 这些使用了 await 关键词的，就是使用的无栈协程，而像 Go 语言，用户像普通函数一样调用例如 read 这样的函数，只是需要使用 go 关键词来创建协程，就是有栈协程了。

通常来讲，无栈协程比有栈协程开销更小，性能更高，而非对称协程和对称协程在功能上没有区别。

无栈协程在有 GC 的语言里实现比较简单，而在没有 GC 的语言，例如 C++ 和 Rust 中，就需要注意非常多的细节。

C++

C++ 中需要实现的东西：

template<class T>
struct Task {
  struct promise_type {
    ReturnObject get_return_object() { return ReturnObject(coroutine_handle<promise_type>::from_promise(*this)); }
    std::suspend_never initial_suspend() { return {}; }
    std::suspend_never final_suspend() noexcept { return {}; }
    std::suspend_always yield_value(unsigned value) {
      value_ = value;
      return {};
    }
    void unhandled_exception() {}
    void return_value(T&& value) {
      value_ = value;
    }
    // void return_void() {}
  };
  std::coroutine_handle<promise_type> h_;
  T value_;
  ReturnObject(std::coroutine_handle<> h) : h_(h) {};
  operator std::coroutine_handle<promise_type>() const { return h_; }
};

template<class T>
struct Awaiter {
  std::coroutine_handle<> *hp_;

  // optional
  Awaiter operator co_await();

  bool await_ready() const noexcept { return false; }
  bool await_suspend(std::coroutine_handle<> h) { *hp_ = h; return false; }
  T await_resume() const noexcept {}
};

一共九个方法需要实现，看的头都大了。先来看一个简单的例子感受一下上面的代码分别有什么用：

Task counter() {
  for (unsigned i = 0; i < 3; ++i)
    co_yield i;
  co_return 42;
}

int main() {
  auto h = counter().h_;
  auto &promise = h.promise();
  while (!h.done()) { // Do NOT use while(h) (which checks h non-NULL)
    std::cout << "counter: " << promise.value_ << std::endl;
    h();
  }
  h.destroy();
  return 0;
}

这是一个简单的计数器协程，每次运行都会递增值。前面的 Task 就代表一个协程，里面可以保存返回值，而 promise_type 就是协程对应的 Promise。Promise 和 Future 一般是成对出现的，Promise 用来写入一个未来的值，而 Future 则用来读取一个未来的值。所以，在上面的 promise_type 中，yield_value 和 return_value 就是用来写入值的方法，而我们可以使用 get 方法得到返回的值。一般来说，Future 的值可以有阻塞的和非阻塞的读取的方法，非阻塞就是无论 Promise 有没有已经写入值，都立刻返回，而阻塞的则是等到 Promise 写入值之后再返回。计数器在 Promise 中设置返回值，然后我们就可以在 Task 中读取这个值。C++ 标准说协程的代码相当于：

{
    promise-type promise promise-constructor-arguments ;
    try {
        co_await promise.initial_suspend() ;
        function-body
    } catch ( ... ) {
        if (!initial-await-resume-called)
            throw ;
        promise.unhandled_exception() ;
    }
final-suspend :
    co_await promise.final_suspend() ;
}

那么 co_await 又是如何驱动协程的运行呢？再来看一个复杂一点的例子：

#include <coroutine>
#include <iostream>
#include <stdexcept>
#include <thread>

auto switch_to_new_thread(std::jthread& out) {
  struct awaitable {
    std::jthread* p_out;
    awaitable(std::jthread* p_out) : p_out(p_out) {
      std::cout << __FUNCTION__ << std::endl;
    }
    ~awaitable() {
      std::cout << __FUNCTION__ << std::endl;
    }
    bool await_ready() {
      std::cout << __FUNCTION__ << std::endl;
      return false;
    }
    void await_suspend(std::coroutine_handle<> h) {
      std::cout << __FUNCTION__ << std::endl;
      std::jthread& out = *p_out;
      if (out.joinable())
        throw std::runtime_error("Output jthread parameter not empty");
      out = std::jthread([h] { h.resume(); });
      // Potential undefined behavior: accessing potentially destroyed *this
      // std::cout << "New thread ID: " << p_out->get_id() << '\n';
      std::cout << "New thread ID: " << out.get_id() << '\n';  // this is OK
    }
    void await_resume() { std::cout << __FUNCTION__ << std::endl; }
  };
  return awaitable{&out};
}

struct task {
  struct promise_type {
    task get_return_object() {
      std::cout << __FUNCTION__ << std::endl;
      return {};
    }
    std::suspend_never initial_suspend() {
      std::cout << __FUNCTION__ << std::endl;
      return {};
    }
    std::suspend_never final_suspend() noexcept {
      std::cout << __FUNCTION__ << std::endl;
      return {};
    }
    void return_void() { std::cout << __FUNCTION__ << std::endl; }
    void unhandled_exception() {}
  };
  task() {
    std::cout << __FUNCTION__ << std::endl;
  }
  ~task() {
    std::cout << __FUNCTION__ << std::endl;
  }
};

task resuming_on_new_thread(std::jthread& out) {
  std::cout << "Coroutine started on thread: " << std::this_thread::get_id()
            << '\n';
  co_await switch_to_new_thread(out);
  // awaiter destroyed here
  std::cout << "Coroutine resumed on thread: " << std::this_thread::get_id()
            << '\n';
}

int main() {
  std::jthread out;
  auto t = resuming_on_new_thread(out);
  std::cout << "Main finished" << std::endl;
}

使用支持 C++ 20 标准的编译器编译运行之后，可以得到以下的输出：

task::promise_type::get_return_object
task::task
task::promise_type::initial_suspend
Coroutine started on thread: 3804
switch_to_new_thread::awaitable::awaitable
switch_to_new_thread::awaitable::await_ready
switch_to_new_thread::awaitable::await_suspend
New thread ID: 2556
Main finished
task::~task
switch_to_new_thread::awaitable::await_resume
switch_to_new_thread::awaitable::~awaitable
Coroutine resumed on thread: 2556
task::promise_type::return_void
task::promise_type::final_suspend

这个例子里，resuming_on_new_thread 是一个协程，而 switch_to_new_thread 则是协程里 co_await 的一个函数，在 co_await 这个函数之后，协程剩余的部分就会在另一个线程中执行。

co_await 这个是一个操作符，在调用之后，首先会调用函数，得到一个 Awaitable，然后，调用这个 Awaitable 的 co_await 操作符，获取一个 awaiter，然后执行 awaiter 的 await_ready ，判断是否需要让出控制权，如果需要的话，就调用 await_suspend，暂停执行，然后返回。在可以继续执行之后，会调用 await_resume，获取返回值。用伪代码来描述就是：

auto awaiter = awaitable.operator co_await();  
if (!awaiter.await_ready()) {  
   awaiter.await_suspend(current_coroutine_handle);  
   continue return;  
}  
auto value = awaiter.await_resume();

可以看到 await_suspend 这个方法，接受了一个 coroutine_handle，并且在新开的线程中执行了。这个 coroutine_handle，就是编译器打包好的，协程的状态以及还没有执行完成的部分，只要调用这个对象，就可以继续执行协程了。

协程能够运行起来，关键是 await_suspend 这个方法，这个方法需要负责设置回调之类的操作，并且在回调中，调用传进来的 Callable，这样协程才能继续运行，否则就卡住了。例如，在服务器程序中，调用 await_suspend 的时候，就将协程注册到 epoll 的 fd 列表里，然后设置在下一次 I/O 发生的时候调用传入的 coroutine_handle 以继续执行暂停的协程。

非常奇怪的是，await_suspend 的返回值类型会影响这个函数实际的行为。如果这个函数返回的是 void，那么当前的协程（调用 co_await 的协程）会立即返回；如果这个协程返回的是 bool，那么在返回 true 的时候，当前协程会立即返回，而如果返回 false 表明当前协程可以继续执行，不会返回；而如果这个协程返回的同样是一个 coroutine_handle，那么就执行这个对象。

C++ 中如果想要嵌套调用协程，是需要自己在 await_suspend 里保存并调用 Callable 的：

struct task<T>::promise_type { 
  std::coroutine_handle<> continuation; 
  auto final_suspend() noexcept { 
    struct awaiter { 
      auto await_suspend(std::coroutine_handle suspended) { 
        if (suspended.promise().continuation)  
          return suspended.promise().continuation.resume();
        else
          return std::noop_coroutine{};
      }
    }; 
    return awaiter{};
  }
}

这里的 final_suspend 是看看当前协程在运行结束返回时，是否有需要返回的协程，有的话就返回到上一个协程，否则就啥都不做，结束执行。

auto task<T>::operator co_await() const {
  struct awaiter {
    std::coroutine_handle<promise_type> handle;
    auto await_suspend(std::coroutine_handle<> suspended) {
      handle.promise().continuation = suspended;
      return handle;
    }
  };
  return awaiter{*_coro};
}

这里的 operator co_await 函数则是为了能在一个 task 里面 co_await foo()，其中 foo() 返回的是另一个 task，可以看到这个函数做的东西很简单，就是设置了一下被调用的协程的返回协程为当前协程。

有了这些基础之后，只需要对系统的异步 API 进行简单的封装就可以使用协程编程了。例如 co_await read() 可以是在 read 的 await_suspend 中将连接的 fd 注册到 epoll fd 里，然后把协程的调用函数作为回调函数保存起来。

Rust

Rust 则需要实现 Future 这个 trait：

enum Poll { Ready(T), Pending }

trait Future {
    type Output;
    fn poll(
        // Note the change from `&mut self` to `Pin<&mut Self>`:
        self: Pin<&mut Self>,
        // and the change from `wake: fn()` to `cx: &mut Context<'_>`:
        cx: &mut Context<'_>,
    ) -> Poll<Self::Output>;
}

只有一个方法：poll()，返回 Poll::Pending 表示协程还没有结束，这时候需要负责设置回调，获取 Context 里的 waker，保存起来，然后在回调处理函数中调用 waker.wake()，将协程重新加入调度队列中，而返回 Poll::Ready(()) 表示协程完成了。

struct Context { 
  // ...
};

impl Context {
  fn waker(&self) -> &Waker;
}

struct Waker { 
  // ...
};

impl Waker {
  fn wake(self);
  fn wake_by_ref(&self);
}

当前，Context 的唯一作用就是保存 Waker 对象，而 Waker 唯一作用就是用来 wake，至于协程所需要的其他信息，可以保存在 Future 对象中。

pub fn waker_fn<F: Fn() + Send + Sync + 'static>(f: F) -> Waker {
  let raw = Arc::into_raw(Arc::new(f)) as *const ();
  let vtable = &Helper::<F>::VTABLE;
  unsafe { Waker::from_raw(RawWaker::new(raw, vtable)) }
}

struct Helper<F>(F);

impl<F: Fn() + Send + Sync + 'static> Helper<F> {
  const VTABLE: RawWakerVTable = RawWakerVTable::new(
    Self::clone_waker,
    Self::wake,
    Self::wake_by_ref,
    Self::drop_waker,
  );

  unsafe fn clone_waker(ptr: *const ()) -> RawWaker {
    let arc = ManuallyDrop::new(Arc::from_raw(ptr as *const F));
    mem::forget(arc.clone());
    RawWaker::new(ptr, &Self::VTABLE)
  }

  unsafe fn wake(ptr: *const ()) {
    let arc = Arc::from_raw(ptr as *const F);
    (arc)();
  }

  unsafe fn wake_by_ref(ptr: *const ()) {
    let arc = ManuallyDrop::new(Arc::from_raw(ptr as *const F));
    (arc)();
  }

  unsafe fn drop_waker(ptr: *const ()) {
      drop(Arc::from_raw(ptr as *const F));
  }
}

值得一提的是，Waker 中保存的是一个 RawWaker 对象，这个对象需要实现 clone_waker、wake、wake_by_ref、drop_waker 这四个方法。为了能够使 Waker 可以静态分配，这四个方法并不是通过实现 trait 的方式来实现的，而是通过手动构造虚函数表来实现的。上面就是一个简单的调用一个函数的 RawWaker 实现。

和 C++ 不同，Rust 中的协程，需要在函数声明前添加 async 关键词，而函数的返回类型并不是 Future，而是实际返回值的类型。

async fn write_header(conn: Connection) -> Result<usize>;

对比

Rust 中嵌套调用协程是编译器帮忙生成的，不需要自己做额外的操作。函数的签名需要加特殊的关键词，返回值的类型是实际返回值的类型。

C++ 的接口显然更复杂，但是它的模型是“自底向上”的，只有当协程能够继续运行的时候才会调用继续函数。函数不需要加特殊的关键词，而是返回一个特殊的包装了返回值类型的协程类型。C++ 也使得你对执行过程有更精细的控制权。

而 Rust 接口简洁不少，基于轮询，模型是“自顶向下”的，需要有一个执行器负责调用 Future 的 poll 接口，整个状态机才能推进，也就是说，Rust 的协程有时可以被不必要地轮询。

另外，Rust 中的 Future 状态类型，在编译的时候就已经确定了，可以当成普通对象一样放在栈上，但也造成有些时候一些变量保存过久，浪费空间；而 C++ 中的 coroutine_handle 则被类型擦除了，编译的时候无法知道具体的类型，也无法知道状态的具体大小，只有在优化结束之后才能确定，这样导致了协程的状态必须分配堆内存，好处是 C++ 的协程，仅会保存需要的状态，比如一个变量只在前面部分使用了，就没有必要保存到后面了。

事件循环逻辑

前面提到，协程在暂停之后，需要有其他代码主动调用协程函数才能让协程继续运行。而所有的协程，通常都是在程序的主函数中，通过一个事件循环来不停调用协程函数来驱动它们的。也就是上面的 HTTP 服务例子里的：

  for (/* each event p */) {
    p->data->state->event = p->event;
    p->data->callback(p->data->state);
  }

当然，要想正确的设置回调函数，需要追踪每一个 fd，这也是为什么在使用异步编程库的时候，需要使用库提供的 TCP 函数和连接类型等，因为这样它们最终负责调用系统函数的时候才能区分不同的连接上的不同事件。

对于事件循环，也有多种模式。一种是，类似于 Go 语言和 tokio 运行时，不同的协程可以在不同的操作系统线程上执行，这样的执行模型就像操作系统一样了，不同的进程可以在不同的 CPU 核心上执行，而且在一些核心空闲的时候，可以从其他核心那里“窃取”任务执行，提高 CPU 的利用率。

而另一种执行模型是 Loop Per Core，也就是每个核心单独执行一个单线程的事件循环，这样做的好处是程序的局部性大大提升，而且避免了协程在多核之间迁移执行时的同步开销（例如任务队列需要加锁），协程使用的数据结构也不必考虑多核同步的问题。相比于多核模型，执行效率会更高。但是如果出现了任务负载不均衡的现象，那么这种模型的 CPU 利用率就会下降，此时性能就没有多核模型好了。

所以，使用哪一种执行模型还是取决于应用程序本身的负载特性，并没有说哪一种模型有绝对的优势。

生命周期管理

和多线程编程一样，在使用协程经常犯的一个错误就是对象的生命周期问题。因为协程可以被暂停，然后再在之后继续执行，如果协程保存了对一个对象的引用或者指针，那么必须确保这个对象在协程执行完成之前都一直存活，否则将发生内存错误。在 GC 语言中，这个问题不存在，编程非常简单。而在 C++ 中，可以使用智能指针 unique_ptr 或者 shared_ptr 等来管理对象的生命周期，在 Rust 中，编译器的 Ownership 模型可以帮助程序员发现生命周期问题。

取消

另一个复杂的问题就是怎么样取消协程。例如，在一个耗时的操作中，可能用户已经等得不耐烦了，取消了请求，也有可能超时了，需要终止请求防止过载。

协程的取消难点在于需要追踪一切涉及到的资源，并在取消的时候正确地释放。例如，在 Go 语言中，所有需要取消的协程，参数一定会带一个 ctx context.Context，并且在所有的异步操作中，同时 select ctx.Done()，在取消的之后，ctx 则会一路传播信号，通知涉及到的协程清理资源并退出。

而在 Rust 和 C++ 中则没有约定俗成的取消方法，但是原理也是类似的。在每一个 await 的调用的时候，都可能是这个协程的一个取消点。如果想要处理取消，那么我们可以在设置回调的时候，同时设置一个监听取消的回调，这样在取消信号发生的时候，协程就可以被唤醒，处理异常情况了。在 Rust 的 tokio 中提供了一个 select! 宏，用法和 Go 语言中的类似，原理就是轮流或者随机查询 select! 的每一个 Future，一旦其中一个 Ready，就执行对应的代码。

锁

在实际应用场景中，一个协程在被暂停之后，可能会在另一个线程被调度执行，而普通的操作系统的锁，有可能需要解锁的线程和加锁的线程是同一个，那么如果在协程中一个锁加锁的时间可能横跨多个 await 点的时候，就不能直接使用普通的锁了，而是要使用支持追踪异步调用信息的异步锁，这样才能在正确的线程释放，避免错误。当然，异步锁的开销比普通的锁的开销要更大，如果加锁的时间没有横跨 await，那么就不需要使用异步锁。

参考资料

https://www.jonathanmueller.dev/talk/accu2022/

https://www.scs.stanford.edu/~dm/blog/c++-coroutines.html

https://lewissbaker.github.io/2017/09/25/coroutine-theory

https://rust-lang.github.io/async-book/01_getting_started/01_chapter.html

https://github.com/madsys-dev/async-ucx

https://github.com/sekirio-rs/Kuro

Paxos 本身以晦涩难懂而闻名，更不要说对它的优化了。为了破除大家心中的阴影，UCB 的几个大佬在 Journal of Systems Research 期刊上发表了 SoK: A Generalized Multi-Leader State Machine Replication Tutorial 的论文。这篇文章也是我对这篇论文的阅读笔记了。

https://mwhittaker.github.io/frankenpaxos/ 有不同 Paxos 算法的动画演示。

概览

自从 Lamport 老爷子提出 Paxos 算法以来，许多工程师和学者都投入到对这个算法的实现和改进的工作中。首先最经典的就是将单个 Paxos 算法扩展到分布式状态机复制的 MultiPaxos 还有尝试让 MultiPaxos 变得更加易懂、易实现，将其中细节问题讲清楚的 Raft 算法。他们的特点都是将上层应用的状态视为状态机，共识算法则负责决定这个状态机执行的日志。将状态变更组织成日志的好处是实现简单，但是显而易见的会有性能问题。例如在 Raft 中，日志不允许存在空洞，日志后面的命令需要等到日志前面的日志提交后自己才能提交。例如，两个用户分别更新自己的用户名，两个操作执行的顺序其实并无要求，谁先修改成功都可以，只要所有副本都保证最后的结果一致即可。而日志则强行为两个并发的操作规定了一个全序，将操作串行化了。尽管可以通过 Sharding 的方式来一定程度上缓解串行化执行的问题，但是在一个 Shard 内的操作仍然是有全序的。

Lamport 自己也意识到了这个问题，提出了泛化的 Paxos 算法，也就是 GPaxos。它的思想也很简单，既然日志强行施加了一个全序，那么我们想办法以一种偏序的方法表达操作即可。也就是说，现在需要共识的不是一个线性的日志了，而是一个可以有依赖关系的有向图。在这个有向图中（为什么允许有环在后面讲），顶点就是需要执行的操作，而如果一个操作 b 依赖另一个操作 a，那么就有一条从 b 指向 a 的有向边。很显然，我们只需要按照这个图的逆拓扑序执行操作就可以了，两个没有依赖关系的顶点可以并发执行。

但是，上面提到的算法，都有一个瓶颈：它们实际上都有一个 Leader 节点。Leader 节点负责所有的请求，而且比其他的节点要收发多得多的信息。尽管我们也可以用 Sharding 的方式来缓解 Leader 的热点问题，但是同样的，对于一个 Shard 内部 Leader 还是有可能成为瓶颈。所以大家就开始在泛化的 Paxos 算法基础上去研究多 Leader 的算法。

多 Leader 算法中，不同的节点互相都是平等的，客户端的请求可以随便发往任意一个节点处理，而且那个节点可以自己处理请求，而不是将请求转发到别的节点去执行。

消除了 Leader 节点的瓶颈问题之后，还有一个问题需要解决，那就是请求的延迟问题。在普通的 Paxos 算法中，需要 7 次 RPC 消息延迟才能提交一个操作，显然这个延迟有点太高了。Lamport 老爷子依然神机妙算，提出了 Fast Paxos 算法，在没有冲突的情况下只需要 4 次 RPC 消息延迟就可以提交一个操作。考虑到最理想的情况下也还需要 2 次 RPC 消息延迟才能提交客户端的操作，4 次相比于 7 次已经是一个很可观的改进了。

当然，在多 Leader 的情况下，冲突的可能性更大，而且 Fast Paxos 对于泛化的 Paxos 没有进一步说明，如何将这个快速提交的算法应用到多 Leader 的泛化的 Paxos 算法，就是更进一步的挑战了。

这篇论文从基本的 MultiPaxos 算法出发，按照上面说的思路一步步地去改进基本的算法，通过对比差异之处，来试图给读者一个更清晰的印象，让读者更好地理解不同的算法的优化点是怎么提出来的。文章里没有希腊字母，可以放心食用。

基本 Paxos 算法

在基本的 Paxos 算法中，Phase 1 用来确认是否已经有值被大多数的 Acceptor 接受过，Phase 2 则用来通知 Acceptor 接受值。这个只是针对一个值的共识算法。如果将不同操作视为不同的值，那么就可以引出 MultiPaxos 算法了。我们都知道，假如需要容忍 $f$ 个进程发生故障，那么需要至少 $2f+1$ 个节点，这样才能保证故障前和故障后的大多数有交集，从而避免不一致的情况发生。

MultiPaxos 算法

如上图所示，MultiPaxos 首先通过 Leader 选举算法在 $f+1$ 个 Proposer 中选出一个 Leader，选举完成后，Leader 对之前每一个日志项执行一次 Paxos 的 Phase 1，之后这个 Leader 负责所有客户端的交互。Leader 在收到客户端的操作命令之后，确定一个日志编号 $i$，直接执行 Phase 2 进行共识。在收到大多数的 Acceptor 的确认之后，Proposer 就可以确定这个日志项的值了，并将这个日志项发送到 Replica 中执行，Replica 执行完成后通知客户端。当然这里的 Proposer、Accpetor 和 Replica 并不是真的都是独立的进程，可以理解为他们是一个服务进程里的不同线程。可以看到 Leader 需要处理所有的客户端请求，而且 Leader 一共需要收发 7 次消息，而其他进程只需要最多收发 2 次消息，显然 Leader 会成为系统的瓶颈。另外，日志也应该是连续的，Replica 是以一个操作日志的前缀执行操作的，这就使得不同的操作串行化了。

冲突图

实际上，真实的应用场景中，很多操作都是可以并发执行的，不关心执行顺序，而只有一些操作需要规定严格的依赖关系。为了能最大化执行效率，我们需要定义哪些操作之间是可以并发执行的，哪些是不可以的，也就是冲突的。从日志角度来看，如果两个操作交换了顺序执行，而不影响最终的状态的话，那么这两个操作就是不冲突的，否则就是冲突的。例如，对于不同变量的赋值是没有冲突的，可以并发执行，而那些依赖于赋值后变量的值的操作就是冲突的，需要规定顺序执行。例如在图中，a=2 和 b=1 这两个操作就是可交换的，不冲突的，可以并发执行。而 b=a 如果被交换到 b=1 之前执行，那么最终 b 的值会变为 1，和原来 b 的值为 2 结果不一样，所以这两个操作是冲突的，不能并发执行，因为并发执行不能保证执行的顺序，有可能导致不同副本上的执行结果不一致。

根据上面冲突的定义，可以画出一个执行日志对应的冲突图，图中的顶点就是日志中的操作，而顶点之间的有向边则代表了冲突关系。显然，我们可以以冲突图的任意一个逆拓扑序去执行操作。也就是说，对于不冲突的操作，我们可以并发执行。而如果想要往这个图中添加新的操作，需要检查这个新的操作和已有的所有操作是否冲突，是的话就添加一条边，保证执行的顺序不会错乱。

形式化一点来讲，图中的顶点为 $v$，那么它所依赖的顶点的集合就是 $\text{deps}(v)$。

有了冲突图的定义之后，就可以将普通的 Paxos 算法扩展为泛化 Paxos 算法了。泛化的 Paxos 算法需要满足共识不变式以及依赖不变式。

共识不变式很好理解，就是对于每一个顶点 $v$ ，最多只能够有一个值 $(x, \text{deps}(v))$，就如同 Raft 的日志中，一个日志项要么没有提交，一旦提交了所有节点都是同一个值。

而依赖不变式，则是形式化的描述了依赖图中的冲突关系。对于一个已经确定了值 $(x, \text{deps}(v_x))$ 的顶点 $v_x$ 和$(y, \text{deps}(v_y))$ 的顶点 $v_y$ ，如果 $x$ 和 $y$ 存在冲突，要么 $v_x \in \text{deps}(v_y)$ ，要么 $v_y \in \text{deps}(v_x)$，或者两者同时满足。前面两个都很好理解，因为节点新增的时间可能不同。但是为什么可以同时满足要等到后面实现细节才好理解。

有了偏序定义之后，就可以开始对基本的 Paxos 的算法进行改进了。泛化的 Paxos 算法如上图所示，它和 MultiPaxos 最大的不同就是增加了 $2f+1$ 个 Dependency Service，这个就是用来计算依赖关系的节点。另外，在这个改进的算法中，不再有单一的一个 Leader，所有 Proposer 都可以处理客户端发送过来的操作命令。Acceptor 进行共识的是冲突图的顶点，而 Replica 执行的也不再是日志，而是上面提到的冲突图。相应地，处理客户端请求的步骤也变多了。这个算法处理请求的流程有 7 步：

1. 客户端发送请求 $x$ 到任意一个 Proposer；
2. Proposer 生成一个全局唯一的顶点 ID $v_x=(p_i, m)$，其中 $p_i$ 是进程的标识符，$m$ 是这个进程里单调递增的一个序列号。然后，将 $v_x$ 以及 $x$ 发送到所有的 Dependency Service；
3. 依赖服务计算 $\text{deps}(x)$ 发回给 Proposer；
4. 收到至少 $f+1$ 个回复后，Proposer 针对 ID 为 $v_x$ 的顶点发起一次 Paxos 共识算法，值就是操作以及依赖的顶点 $(x, \text{deps}(v_x))$。这里可以直接发起 Accept 请求的原因是因为这个顶点是刚刚生成的全局唯一的 ID，此时应该还没有别的进程发起过 Accept 请求，所以 Proposer 可以安全地发起任何值；
5. Acceptor 发送回复；
6. 当大多数确定了 $v_x$ 的值之后，Proposer 将确认的值 $(x, \text{deps}(v_x))$ 发送给 Replica 执行；
7. Replica 执行操作后，回复客户端。

那么依赖服务如何计算一个操作的依赖呢？首先，每一个依赖服务节点 $d_i$ 都会保存一份无环的冲突图，当一个节点收到了 $x$ 和 $v_x$ 之后，如果检查发现冲突图中已经包含了 $v_x$，那么就不做任何操作，不改变冲突图，直接返回 $v_x$ 指向的所有节点的集合；否则，就将 $v_x$ 加入到冲突图，并检查所有其他的顶点 $v_y$，如果 $x$ 和 $y$ 冲突，就添加一条从 $v_x$ 指向 $v_y$ 的边。遍历完成后，同样返回 $v_x$ 指向的所有顶点的集合。

当 Proposer 收到至少 $f+1$ 个回复之后，取所有回复的并集作为顶点的依赖。例如，假设 $f=1$，$d_1$ 的回复是 $\left\{v_w, v_y\right\}$，$d_2$ 的回复是 $\left\{v_w, v_z\right\}$，那么 $\text{deps}(x)=\left\{v_w, v_y, v_z\right\}$。

经过这样的操作，就可以得到另外一个不变式：如果 $v_x$ 和 $v_y$ 中的操作 $x$ 和 $y$ 冲突了，并且依赖关系服务计算出了 $\text{deps}(x)$ 和 $\text{deps}(y)$，要么 $v_x \in \text{deps}(v_y)$ ，要么 $v_y \in \text{deps}(v_x)$，或者两者同时满足。这个和依赖不变式的不同在于，这个不变式的 $\text{deps}(x)$ 是从依赖服务返回的。

但是，两个冲突的操作，可能是同时发起的，而不同的消息到达不同的依赖服务节点的顺序有可能不同，这就导致了在不同服务节点中的依赖关系可能不同。即使依赖服务维护的冲突图是无环的，Replica 中形成的冲突图也有可能有环。以上图为例，$x$ 和 $y$ 是两个冲突的操作，分别同时发送给了 $p_1$ 和 $p_2$。$p_1$ 发送 $x$ 和 $v_x$ 给依赖服务，同时 $p_2$ 发送 $y$ 和 $v_y$ 给依赖服务。由于网络问题，$d_1$ 和 $d_2$ 先收到了 $x$，然后接收到了 $y$，所以根据这两个节点计算得到 $\text{deps}(v_x)=\emptyset$， $\text{deps}(v_y)=\left\{v_x\right\}$。$d_3$ 则是先收到了 $y$ 再收到了 $x$，所以计算得到 $\text{deps}(v_x)=\left\{v_y\right\}$， $\text{deps}(v_y)=\emptyset$。之后，由于网络问题，$d_1$ 的回复丢失了，$p_1$ 和 $p_2$ 分别都收到了 $d_2$ 和 $d_3$ 的回复，根据上面的算法，因为已经收到了大多数的回复，他们各自对自己关心的节点的依赖取并集，然后向 Acceptor 发送对应的值。$p_1$ 认为 $v_x$ 的值是 $(x, \left\{v_y\right\})$，$p_2$ 认为 $v_y$ 的值是 $(y, \left\{v_x\right\})$。这两个值都能够顺利的被 Acceptor 接受并提交了，然后 Proposer 将确认后的值发送给 Replica。Replica 将 $v_x$ 和 $v_y$ 加入到自己的冲突图中，并在接收到两个操作之后执行操作，并返回操作结果给客户端。可以看到，Replica 中的冲突图成环了。对于这种情况，需要以一种确定的预先规定好的算法来打破循环。

引入依赖图和日志有一个同样的问题，如果一个操作的依赖中有顶点因为各种原因一直没能确定值（比如 Proposer 突然挂了），那么这个操作也永远执行不了。为了解决这种问题，可以设置一定的超时时间，如果一个操作等依赖执行等得太久了，就用一个空操作来取代原来的节点。空操作指的是一个对于状态机安全的，不会改变状态的操作。恢复的过程也很简单，只需要对于那个节点，以第 $r (r\gt 0)$ 轮从 Phase 1 执行一次 Paxos 算法即可。这时需要执行 Phase 1 的原因是，有可能上一个 Proposer 已经让大多数的 Acceptor 接受值了，这时候需要做的就是将没有完成的流程进行下去，不能提交空操作。通过执行一次完整的 Paxos 就完成了恢复，也让整个算法变得更简单。

当然，上面的这个算法为了提交一个操作，需要等 7 次消息的延迟，显然有点不能接受。为了提高性能，还需要想办法减少消息的数量。

快速提交 Fast Paxos

为了改进 Paxos 交换信息次数太多的缺点，Lamport 又提出了 Fast Paxos。这个算法和原始的 Paxos 算法一样，只是用来确定单个值的。

就像之前的 MultiPaxos 一样，如果很确定自己是第一个提出一个值的话，那么就可以安全地跳过第一阶段，直接进入第二阶段提交。类似地，在这个改进版的算法中，客户端不再和 Proposer 通信，而是乐观地直接向 Acceptor 发起 Accept 请求，如果 Acceptor 没有接受过更早的消息（包括第 0 轮），那么就接受这个请求，返回 ${\rm P{\small HASE}2B}\left $ 消息给 Leader。定义多数函数 $\text{maj}(n)=\lceil \frac{n+1}{2} \rceil$，也就是求 $n$ 个人最少需要多少人算大多数。只有当 Leader 收到至少 $f+\text{maj}(f+1)$ 条 ${\rm P{\small HASE}2B}\left $ 回复且 $v’$ 相等之后，才能确定这个值为 $v’$。可见，为了能够安全提交一个值，需要的 Acceptor 比 $f+1$ 多。但随之而来的好处是，提交一个值只需要 4 次消息的延迟。

现在来考虑一下出错的情况。如果是 Leader 挂了，那么其他的 Proposer 需要针对这个值从头进行一次 Paxos 算法。Proposer 和普通的 Paxos 算法一样，需要先确定一个轮数 $i$，并且用这个轮数发送 ${\rm P{\small HASE}1A}\left $ 给至少 $f+1$ 个 Acceptor，收到至少 $f+1$ 个 ${\rm P{\small HASE}1B}\left $ 消息之后，Proposer 计算 $k=\max{\{vr\}}$ ，也就是和 Paxos 算法一样取最大的那个数。另外，记收到回复的 Acceptor 的集合为 $A$。如果 $k=-1$，那说明还没有任何值被提交过，Proposer 可以自由地提交任意值；如果 $k\gt 0$，那么 Proposer 就要继续完成没有完成的共识，只能够提交 $k$ 对应的 $vv$ 。

当 $k=0$ 的时候，说明有一些 Acceptor 收到过来自客户端的消息。此时，$v$ 有可能已经确定了某个值，也有可能还没有确定，需要分情况讨论。

如果 $\text{maj}(f+1)$ 个 Acceptor 已在第 0 轮的时候投票给了某个值 $v’$，那么这个值可能已经被决定了。如果 $A$ 集合之外的 $f$ 个进程也投票给了 $v’$，那么这时候就满足了 $f+\text{maj}(f+1)$ 的数量要求，可以安全地提交 $v’$ 了。如果没有哪个值得到了 $\text{maj}(f+1)$ 的票数，那么 Proposer 就可以断定在第 0 轮的时候没有决定一个值，此时它可以提出任意值。换句话说，如果一个值想要被快速提交，它不仅要得到大多数成员的认可，还要在大多数的大多数中得到认可，才能安全地提交。

确定了要提交哪个值之后，Proposer 就可以继续进行 Phase 2 的 Paxos，将值提交了。需要注意的是，想要快速提交一个值的话必须得到至少 $f+\text{maj}(f+1)$ 的票数，否则会出现脑裂的情况。假如 $f=2$，Acceptor 分别为 $a_1, a_2, \dots, a_5$。如果一个值只需要 3 个 Acceptor 同意，那么假如按照上面恢复的过程，接手的 Proposer 使用 $i=1$ 向 $a_3, a_4, a_5$ 发起 Phase 1 请求，此时 $a_3$ 回复它给 $x$ 投票了，$a_4$ 回复它给 $y$ 投票了，$a_5$ 说它没投票。注意它们都是第 0 轮。现在，因为 $a_1$ 和 $a_2$ 的状况未知，如果它们投票给了 $x$，根据我们的假设，满足了至少 $f+1$ 的票数，那么被选中的就是 $x$；但是它们也有可能投票给了 $y$，此时被选中的就是 $y$。Proposer 此时并不能决定提交哪个值才是正确的，算法就无法进行下去了。如果我们要求快速提交的时候需要 $f+\text{maj}(f+1)$ 的票数，那么这种情况就无法发生，要么有一个值得到了剩下的 $f+1$ 个成员的大多数的投票，此时可以断定这个值已经能够提交，要么剩下的 $f+1$ 个成员没有达成大多数的共识，那按照快速提交的规则，没有值能够安全提交，这时候就可以安全地提交任意一个值了。

快速提交发生冲突的情况也是类似的处理，要是没有哪个值能够达到要求的票数，那么就由 Proposer 发起普通的 Paxos 过程。

需要注意的是 $f+\text{maj}(f+1)$ 的限制只是为了安全的快速提交而设的。如果中途 Acceptor 挂了或是发生了别的情况，我们还是可以向剩下的至少 $f+1$ 个进程发起普通 Paxos 请求来提交值的。

这里还有一个可以优化的点，在冲突发生的时候，除了重新进行一次普通的 Paxos 算法，其实在冲突发生的时候 Leader 就已经能够收集到足够的信息了。在第 1 轮的 Paxos 算法中，${\rm P{\small HASE}1B}\left $ 包含的信息和第 0 轮的 ${\rm P{\small HASE}2B}\left $ 信息是完全一样的。所以我们可以将 ${\rm P{\small HASE}2B}\left $ 看成是 ${\rm P{\small HASE}1B}\left $。这样，第 1 轮的 Proposer 就可以直接跳到 Paxos 的 Phase 2 进行恢复了。

不安全的快速泛化 Paxos

了解了 Fast Paxos 算法后，我们可以依葫芦画瓢地改进普通的泛化的 Paxos 算法了。

在改进的算法中，同样编号的角色都跑在同一个服务器上，这样同一个编号的不同角色之间的消息传递都是本地通信，不需要引入网络开销。

客户端还是需要通过任意一个 Proposer 来提交操作请求。Proposer 收到请求之后，一样是生成一个编号 $v_x$，并将操作 $x$ 和 $v_x$ 发送到依赖服务节点，和之前不同的是，依赖服务节点收到新的节点之后，并不是直接将 $\text{deps}(v_x)$ 发送回 Proposer，而是直接向自己本地的 Acceptor 发送 $(x, \text{deps}(v_x))$ 作为 $v_x$ 的值。Acceptor 和 Fast Paxos 中的 Acceptor 一样，当接收到值之后，按照规则投票或忽略，并将回复发送回 Proposer。同样的，Proposer 在收到 $f+\text{maj}(f+1)$ 个同样值的回复之后，就返回客户端操作成功，否则执行恢复流程。

但是这个算法是不安全的。假设还是 $f=2$ 的情景，$p_1$ 和 $p_5$ 分别同时收到了冲突的请求 $x$ 和 $y$，$p_1$ 将节点 $v_x$ 和 $x$ 发送给了 $d_1$ 和 $d_2$，它们由于不知道 $y$，计算得到 $\text{deps}(v_x)=\emptyset$，并向 $a_1$ 和 $a_2$ 提出 $v_x$ 的值为 $(x, \emptyset)$。发给 $d_3, d_4, d_5$ 的消息被丢包了。类似地，$a_4$ 和 $a_5$ 提出 $v_y$ 的值为 $(y, \emptyset)$。$d_3$ 自始至终都没有收到任何消息，所以 $a_3$ 没有投票给任何值。这时候 $p_1$ 和 $p_5$ 都挂了，$p_2$ 负责恢复 $x$ 。它向 $a_1, a_2, a_3$ 发起了 Phase 1 的 Paxos 请求，这时候它收到了 $a_1$ 和 $a_2$ 的回复 $(x, \emptyset)$，因为 $\text{maj}(f+1)=\text{maj}(3)=2$，所以 $p_2$ 只能提交 $(x, \emptyset)$。类似地，$p_4$ 负责 $y$ 的恢复，并最终确定只能提交 $(y, \emptyset)$。这时候，Replica 分别收到 $(x, \emptyset)$ 和 $(y, \emptyset)$，所以在它们看来，$x$ 和 $y$ 不冲突，可以并发执行，就有可能导致不同 Replica 执行顺序不一致导致最终状态的不一致。

问题就出在，$\text{deps}(v_x)=\emptyset$ 并没有得到大多数依赖服务的节点的共识。单独保证共识不变式很简单，单独保证依赖不变式也很简单，但是要同时确保两者就有点 tricky 了。在恢复的过程中，共识不变式强制要求 Proposer 提交一个特定的值，而依赖不变式则强制要求 Proposer 不要提交那个值。这种两个不变式之间的矛盾，论文作者称之为基本矛盾。怎样在恢复过程中解决这个矛盾，是所有泛化的多 Leader 的 Paxos 算法最核心的挑战。EPaxos、Caesar 以及 Atlas 都是类似的，它们的进程组织是类似的，正常的执行流程也是类似的，最大的不同之处就在于它们是如何解决这个基本矛盾的。

解决这个基本矛盾的方法有两种，一种是避免矛盾，另一种则是解决矛盾。避免矛盾是通过调整 Quorum 的大小来避免矛盾的发生；而解决矛盾则更加复杂，需要在发现矛盾之后尝试解决它。

避免矛盾

在 Fast flexible paxos: Relaxing quorum intersection for fast paxos 这篇论文中，作者指出，只要满足以下两个条件，Fast Paxos 算法就是安全的：

1. 每一个 Phase 1 的 Quorum 集合（也就是大多数节点的集合）$Q$，和每一个 Phase 2 的 Quorum 集合 $Q’$ 相交。也就是 $Q \cap Q’\ne \emptyset$ 。
2. 每一个 Phase 1 的 Quorum 集合 $Q$ 和每一对快速 Phase 2 的 Quorum 集合 $Q’, Q”$ 相交，也就是 $Q\cap Q’ \cap Q”\ne \emptyset$ 。

那么，根据这个结果，只需要将不安全的快速泛化 Paxos 算法的快速提交需要的票数提高到 $f+(f+1)$ 就可以了。但是这意味着要想快速提交一个值得全体进程统一才可以。

和不安全的算法对比，在恢复阶段，当 $k=0$ 时，只有当 Proposer 收到了 $f+1$ 个同样的 ${\rm P{\small HASE}1B}\left $ 回复后，才是被强制提交 $v’$ 的，在其他情况下，Proposer 都可以选择任意的满足依赖不变式的值提交。这个算法用更大的进程集合为代价，完全避免了矛盾的发生。因为在 $f+1$ 个相同的回复后，说明 $\text{deps}(v_x)$ 已经被大多数节点接受了，此时就不会发生依赖不一致的现象了。

显然，如果每一次提交都要和所有进程通信，那么万一有一个进程比较慢，就会拖慢整个算法，如果有一个进程挂了，那么算法就无法继续进行了（虽然还是可以通过其他方法用基本 Paxos 算法执行）。无论是从性能的角度还是可用性的角度这个算法都不太实用，所以还需要进一步的改进。

基本的 EPaxos 改进

通过对上面的算法进一步改进，可以将快速提交的票数要求降低为 $f+f$。

第一个改动是 Proposer $p_i$ 在收到请求之后不再广播请求到所有的依赖服务节点，而只在本地计算依赖。

第二个改动是，本地的 $d_i$ 像普通的算法一样先计算出依赖节点，然后由依赖服务负责将 $v_x, x$ 和 $\text{deps}(v_x)_i$ 广播给其他节点。当其他节点 $d_j$ 接收到之后，按照自己的依赖图计算 $\text{deps}(v_x)_j$，然后向 $a_j$ 提出 $(x, \text{deps}(v_x)_i \cup \text{deps}(v_x)_j)$ 。

Acceptor 还是像之前一样投票给提出的值。

最后一个改动是，当 Proposer 接收到 $f+f$ 票后（包括本地的 $a_i$）就认为这个值确定了，并将确定的值 $v$ 发给本地的 $a_i$，如果此时 $a_i$ 还处于第 0 轮，那么这个值就是真正地确定了。如果不是的话，就拒绝这次请求，回复错误信息给 $p_i$。这整个过程都只涉及本地进程，不需要网络通信。

在正常情况下，$v_x$ 就正式确定了，$a_i$ 将 $v$ 广播到所有 Acceptor，如果有 Acceptor 拒绝了，就执行一次恢复过程。

需要注意的是，上面所说的优化只在 $f\gt 1$ 的时候成立，在 $f=1$ 的时候，所有的 Quorum 集合大小都是 $f+1=f+f=2$ ，不满足前面所说的两条定理，因此是不安全的。这时候，快速提交仍然需要 $f+f+1$ 票才能安全提交。

Atlas 优化

Atlas 优化的思想是放宽一致投票的要求，并增加 Proposer 执行快速提交的可能性。它定义了 $\text{popular}(X_1, X_2, \dots, X_{2f+1})=\left\{x|x 至少在 f+1 个集合中出现 \right\}$ ，其中 $X_i$ 是集合。当 Proposer 收到了来自 $2f+1$ 个 Acceptor 的回复后，如果 $\text{deps}(v_x)=\text{popular}\left(\text{deps}(v_x)_1, \text{deps}(v_x)_2, \dots, \text{deps}(v_x)_{2f+1} \right)$，那么就执行快速提交，并且 $\text{deps}(v_x)=\text{deps}(v_x)_1\cup \text{deps}(v_x)_2\cup \cdots\cup \text{deps}(v_x)_{2f+1}$。也就是说，Proposer 只有在每一个依赖服务计算出的依赖顶点 $v_y$ 也被大多数的依赖服务节点计算出来的时候，才执行快速提交。

解决矛盾

避免矛盾需要很多的节点才可以快速提交，所以并不是很实用。为了达到和 Fast Paxos 一样的 $f+\text{maj}(f+1)$ 的快速提交票数，还需要进一步优化算法，允许矛盾发生，并在发现矛盾的时候去解决矛盾。再回顾一下基本矛盾，在执行恢复的时候，共识不变式要求 Proposer 提出 $(x, \text{deps}(v_x))$，但同时，它无法保证 $\text{deps}(v_x)$ 是由大多数的依赖服务节点计算出来的，这就导致了它不能提交 $(x, \text{deps}(v_x))$。依赖避免算法通过增大 Quorum 大小，保证了 Proposer 提交的 $\text{deps}(v_x)$ 是由大多数的依赖服务节点计算出来的，这也导致了性能和可用性的下降。

矛盾解决算法则并不要求更多的 Quorum 节点，并且允许在恢复的时候出现这种不一致的现象，但通过更复杂的机制，要么确定 $\text{deps}(v_x)$ 没有被提交成功，要么确定 $\text{deps}(v_x)$ 已经被大多数节点接受，可以提交。矛盾解决算法更加抽象复杂，需要更多的逻辑推理。

这个算法需要引入一个剪枝依赖的概念。假如一个 Proposer $p$ 已经知道 $v_y$ 的值是 $(y, \text{deps}(v_y))$，对于依赖里的一个顶点 $v_x\in \text{deps}(v_y)$ ，就没有必要依赖 $v_y$ 了，因为它们的冲突关系已经在 $v_y$ 的值中表达出来了（回忆一下之前的依赖算法没有避免环的产生）。也就是说，对于互相冲突的操作 $x$ 和 $y$，要么 $v_x\in \text{deps}(v_y)$ 要么 $v_y\in \text{deps}(v_x)$ 。注意这时候两者同时成立的可能被排除了。

所以，我们可以剪枝掉一些不必要的依赖节点。假设 $v_x$ 的依赖是 $\text{deps}(v_x)$ ，那么可以计算出一个集合 $P\subseteq \text{deps}(v_x)$ ，对于 P 里面的元素 $v_y$ ，要么 $v_y$ 提交了一个空操作，要么 $v_y$ 提交的 $\text{deps}(v_y)$ 中包含了 $v_x$ 。最后，计算出 $\text{deps}(v_x)-P$ ，就是节点 $v_x$ 的剪枝后的依赖了。

对于这个剪枝后的依赖，提出一个新的剪枝依赖不变式，对于每一个节点 $v_x$，它的值要么提交了 $(\text{noop}, \emptyset)$，要么提交了 $(x, \text{deps}(v_x)-P)$，其中 $\text{deps}(v_x)-P$ 就是按照上面的算法计算出的剪枝后的依赖。

接下来，就开始修改之前的快速泛化 Paxos 算法了。第一个大的改动是，每一个 Acceptor 和 Replica 一样，也需要维护一个冲突图，当 Acceptor 收到消息确定 $v_x$ 提交了 $(x, \text{deps}(v_x))$ 之后，也按照算法，将 $v_x$ 加入到图中，并添加 $v_x$ 指向 $\text{deps}(v_x)$ 每一个顶点的边。其次，Proposer 执行的恢复算法要复杂得多。

具体来说，按照快速泛化 Paxos 算法，Proposer 收到至少 $f+1$ 个 ${\rm P{\small HASE}1B}\left $ 消息（记发送消息的 Acceptor 集合为 $A$）之后，如果 $k=0$ 且 $v’=(x, \text{deps}(v_x))$ 获得了至少 $\text{maj}(f+1)$ 票，按照快速算法，Proposer 需要提交 $v’$。但按照泛化算法，却无法保证 $\text{deps}(v_x)$ 是原来大多数节点所求依赖的并集，所以这个值不能提交。这时候，冲突解决算法需要做一些额外的工作，来断定要么 $v’$ 并没有被提交，要么 $\text{deps}(v_x)$ 是 $v_x$ 的一个剪枝依赖集合。

首先要做的是，Proposer 向发送消息的 $f+1$ 个依赖服务（和对应的 Acceptor 在同一个进程中）发送 $v_x$ 和 $x$，并将这些依赖服务返回的依赖集合求并集，保存到 $\text{deps}(v_x)_A$ 中，并且计算一个差集合 $Y=\text{deps}(v_x)_A-\text{deps}(v_x)$，也就是用返回的依赖和 Acceptor 保存的依赖作差（因为 $\text{deps}(v_x)$ 是 $\text{maj}(f+1)$ 个 Acceptor 返回的，$\text{deps}(v_x)_A$ 是 $f+1$ 个节点返回的，前面的集合是后面集合的自己）。

然后，需要对这个集合开始剪枝操作。一开始 $P=\emptyset$ ，对于 $Y$ 中的每一个顶点 $v_y$，如果还不确定 $v_y$ 是否已经提交值，那么就需要先对 $v_y$ 执行恢复操作。在确定了 $v_y$ 的提交值之后，根据提交的内容来执行进一步的操作。如果 $v_y$ 提交的是一个空操作，或者 $v_x\in \text{deps}(v_y)$，那么就直接剪枝，将 $v_y$ 添加到 $P$ 中。否则，则需要向 Acceptor 的大多数集合 $A’$ 确认 $v_x$ 的状态。如果有 Acceptor 返回 $v_x$ 已提交，那么就直接终止恢复过程。如果所有的 Acceptor 都没有认为 $v_x$ 已提交，那么 Proposer 就可以安全地提出任何一个满足依赖不变式的值 $v$，并向所有 Acceptor 发送 ${\rm P{\small HASE}2A}\left $ 的消息。关于为什么这个时候就可以断定在第 0 轮中没有值被提交，可以提交任意值，需要更复杂的推理，放到后面讲。

循环结束之后，说明剪枝完成，此时 $\text{deps}(v_x)=\text{deps}(v_x)_A-P$，也就是原来的 $v’$ 可以直接提交，这时候，就可以发送 ${\rm P{\small HASE}2A}\left $，以及 $P$ 中每一个顶点的最终提交值给至少 $f+1$ 个 Acceptor 进行 $v_x$ 的提交了。

现在再回头看看，为什么上面说 Proposer 可以断定没有值被提交。首先，执行到这个分支的时候，我们知道 $v_y$ 不是空操作，而且 $v_x \notin \text{deps}(v_y)$ ，根据剪枝依赖不变式，$\text{deps}(v_y)=\text{deps}(v_y)_D-P’$，其中 $\text{deps}(v_y)_D$ 是由至少 $f+1$ 个依赖服务节点 $D$ 计算得到的集合的并集。因为 $v_x\notin \text{deps}(v_y)_D-P’$，要么 $v_x$ 本来就不在依赖中 $v_x\notin \text{deps}(v_y)_D$，要么被剪枝了 $v_x\in P’$。

但是 $v_x$ 是不可能在 $P’$ 中的。因为此时节点已经达成了 $v_y$ 的 $\text{deps}(v_y)=\text{deps}(v_y)_D-P’$ 共识，同时也达成了 $P’$ 中的所有顶点已经提交了的共识，根据相交定理，肯定至少有一个联系到的 Acceptor 确定 $v_x$ 已经提交。如果 $v_x$ 在 $P’$ 中，就产生了矛盾，因为这时候算法认为 $v_x$ 还没有提交。因此，$v_x\notin \text{deps}(v_y)_D$ 成立。所以，$D$ 中的所有节点都先处理了 $v_y$，再处理 $v_x$。又因为 $v_y\notin \text{deps}(v_x)$（因为 $\text{deps}(v_x)$ 是 $\text{deps}(v_x)_A$ 子集，如果 $v_y\in \text{deps}(v_x)$，那它就不可能出现在循环中），这时候就需要有快速提交的大多数达成共识 $v_x$ 在 $v_y$ 前处理，但已经有 $D$ 个节点达成了 $v_y$ 在 $v_x$ 前处理的共识，前面的共识是不可能被提交的。所以 $v’=(x, \text{deps}(v_x))$ 肯定没有被提交，Proposer 可以任选一个值提交。

经过一番推理之后，我们得到了一个解决冲突的算法。但是这个算法有一个缺点：它有可能死锁。这是因为，有可能存在节点 $v_1, v_2, \dots, v_n$ 其中每一个 $v_i$ 都依赖 $v_{i+1 \mod n}$，那么在递归解决未提交的顶点的时候，就会死锁。

为了解决死锁问题，我们还需要修改算法，具体来说，Proposer 会在两个条件都满足的情况下，认为一个顶点 $v_x$ 快速提交了 $v=(x, \text{deps}(v_x))$。首先当然是这个值得到了来自快速提交所需的 $f+\text{maj}(f+1)$ 票，并且记投票了的 Acceptor 集合为 $F$，并且对于每一个 $v_y\in \text{deps}(v_x)$ ，都有 $f+1$ 个 Acceptor $A\subseteq F$，在投票的时候知道 $v_y$ 已经提交了。其次，在 Acceptor $a_i$ 发送 ${\rm P{\small HASE}2B}\left $ 回复（$v=(x, \text{deps}(v_x))$）的时候，顺带发送 $\text{deps}(v_x)$ 中 $a_i$ 知道已经提交了的节点和它们的值。

最后，在恢复的过程中，要检测出是否发生了循环依赖。具体来说需要在上面的恢复算法中的第 10 行之后插入以下算法：

在获得 $v’=(x, \text{deps}(v_x))$ 的信息之后，首先计算出投票给了 $v’$ 的 Acceptor 集合 $M$，Proposer 检查 $\text{deps}(v_x)$ 是否存在一个 $M$ 中没有 Acceptor 知道是否已经提交值的顶点 $v_y$，存在的话，说明 $v’$ 不可能在第 0 轮中提交。如果 $v’$ 提交了，那么说明 $F$ 中的 Acceptor 投票给了 $v’$，同时存在 $A’\subseteq F$ 中的 Acceptor 知道 $v_y$ 已经提交了。由于 $A’\cap A\ne\emptyset$，但又没有 Acceptor $a$ 同时投票并且知道 $v_y$ 已经提交，这就产生了矛盾。因此，Proposer 可以提出任意值。

其次，Proposer 可能之前正在恢复 $v_z$ ，然后根据算法递归调用来恢复 $v_x$，如果此时 $v_z\in \text{deps}(v_x)$，那么 $M$ 中肯定有 Acceptor $a$ 已经知道 $v_z$ 被提交了，这时候就可以终止 $v_z$ 的恢复过程了。否则，$v_z \notin \text{deps}(v_x)$，那么每一个 $M$ 中的节点的依赖服务都是先处理 $v_x$ 后处理 $v_z$。又因为 $|M|\ge \text{maj}(f+1)$，所以肯定只有少于 $f+\text{maj}(f+1)$ 个节点有可能认为 $v_z$ 早于 $v_x$ 处理。如果 Proposer 在恢复 $v_z$ 的时候需要递归恢复 $v_x$，那么 $v_x\notin \text{deps}(v_z)$（要不然的话 $v_x$ 已经确定提交了，不需要恢复）。因此，如果 $v_z$ 想要带着 $v_x\notin \text{deps}(v_z)$ 快速提交，那么就需要至少有 $f+\text{maj}(f+1)$ 个节点认为 $v_z$ 早于 $v_x$ 处理，但这和之前的条件矛盾，所以 $v_z$ 不可能被快速提交，这时候就可以提出任意值了。

这样，通过对 Paxos 算法循序渐进地改进，我们就得到了一个可以解决冲突的，不会死锁的快速泛化 Paxos 算法了。

总结

作者根据 Leader 的数量、是否泛化、能否快速提交、怎样处理基本矛盾，大致给不同的 Paxos 变种分到不同类别中。

真实算法

作者为了更清楚地说明 Paxos 算法的改进过程，对一些细节忽略或者做了修改。EPaxos 使用了带基本 EPaxos 改进的快速算法，来减少快速提交所需的票数，同时也使用了最后所说的依赖剪枝以及避免死锁的递归恢复算法。Caesar 则进一步地改进 EPaxos 算法，和 Atlas 优化类似，Caesar 在快速提交的时候不需要 Acceptor 都投票给完全一样的值。此外 Caesar 没有使用递归恢复算法，而是使用了逻辑时间戳以及在协议中仔细加入 Barrier 来避免递归的恢复。

和单 Leader 日志型算法的比较

相比于 MultiPaxos、Raft 以及 Viewstamped Replication 这些将所有的操作赋予全序形成线性的日志的算法，泛化的多 Leader Paxos 算法虽然更复杂，但也有性能和可用性上的优势。

首先，多 Leader 避免了单 Leader 成为瓶颈的问题，任何 Proposer 都可以接受处理命令，提高了吞吐量。

其次，多 Leader 算法能更好地应对故障。在 Raft 和 MultiPaxos 这些算法里，一旦 Leader 发生故障，那么吞吐量会立即降为 0，直到新的 Leader 被选举出来后才能恢复。像 EPaxos 这种算法，如果有 Leader 死机了，那么吞吐量虽然也会下降，但不会下降到零，其他 Leader 还是可以继续处理命令。故障的 Leader 恢复后，吞吐量也能回归正常。

第三，对于地理上分开的应用来说，多 Leader 算法可以达到更低的延迟。和单 Leader 对比，可以在不同的数据中心各放置一个 Leader，这样不同数据中心的客户端感受到的延迟都是一样的，整体的延迟也会更低。

最后，泛化的 Paxos 能降低操作之间依赖关系很少的应用的尾延迟。在 Raft 中，一个命令如果因为网络问题没能提交，那么后面所有的命令都会受到影响。任何一个命令的延迟执行，都会影响到串行化到它后面的命令的延迟。而泛化的 Paxos 算法中，即使一个命令延迟执行了，和它不冲突的命令都可以不受影响地并发执行，降低了尾延迟。

更多相关工作

SpecPaxos 和 NOPaxos 采取更加激进的推测执行（Speculative Execution），对 Fast Paxos 改进到最佳情况下只需要 2 次网络延迟就能完成操作。CURP 则进一步地扩展泛化性，允许可交换的命令以任何顺序执行。但是，随着提交延迟的降低，算法的复杂性也在上升，进一步影响了它们在工程中的应用。

Mencius 则是一个多 Leader 的非泛化的 Paxos 变种，其中不同的 MultiPaxos 日志项在不同的 Leader 中分块处理，同样地，一个日志项只有等到它之前的日志项执行完成后才能执行。为了同步日志，Mencius 中的 Leader 会执行 All-to-All 的广播操作。它的优点是相比起 EPaxos 等算法简单很多。这也说明了对 Paxos 算法优化的复杂性主要来自于泛化而不是多 Leader。当然多 Leader 也是会带来一定复杂性的。

Paxos 之外

除了千奇百怪的 Paxos 变种，还有很多其他的分布式共识算法。例如 Chain Replication，不同的节点组成了一条复制链，写的时候往头节点写，然后沿着复制链复制日志，读的时候只从尾节点读。链复制算法比 MultiPaxos 能达到更高的吞吐量，因为负载在不同节点上更加均衡。

Scalog 则使用了一种复杂的批处理方式来复制日志。客户端并不直接将日志项发送到一个中心的 Leader，而是发送到批处理节点中的任意一个。按照一定时间间隔，批处理的每一批数据会被封存，并且分配一个 ID，然后这个 ID 被当做日志 ID，就像 MultiPaxos 的日志编号一样，发往一个状态机复制协议。

这两个算法也说明 Leader 带来的瓶颈可以不通过多 Leader 来解决。

而 PQR、Harmonia、CRAQ 这些算法则实现了对于读操作的优化，对于不涉及状态机修改的命令，都可以不通过 Leader 来执行（Raft 也有类似的 Follower Read 优化），写命令还是要通过 Leader 执行。比较有趣的是，对于泛化后的 Paxos 能不能也实现读优化还是一个值得研究的问题。

Paxos 算法通过限制未来，用大多数集合相交排除可能性达到了各个节点的一致性。它简单，但仍有许多值得深入研究的地方。这正是它最引人入胜的地方。从泛化性和一致性的拉扯也可以看出系统设计中的一些 trade-off，如何找到其中的 sweet point，也是计算机系统研究的乐趣之一。

调试内核模块和调试 Linux 程序本身差不多，都可以使用 gdb + qemu 来调试，也可以使用 Linux 内核自带的 kgdb 工具调试。不过因为内核模块是动态加载的，需要 add-symbol-file 来指定模块的加载地址。

使用 kgdb 调试

需要使用到串口进行通信。可以在 qemu 启动系统的时候加入参数 -serial tcp:localhost:4321,server,nowait，将内核的串口设备映射到本机 tcp 连接上，然后编辑 /etc/default/grub 在系统启动参数里加入 kgdboc=ttyS1,115200 nokalsr ，并运行 sudo update-grub 之后重启虚拟机，启动 gdb 使用 target remote localhost:4321 连接到串口调试端口，之后，在虚拟机操作系统里，运行 echo g > /proc/sysrq-trigger 触发断点，将控制权交给 gdb，使用 gdb 设置好断点后按 c 继续运行。后续想要将控制权交给 gdb 都需要使用上面的 echo 语句触发断点。需要注意的是，如果是给内核模块打断点，需要先通过 cat /sys/module/<模块名>/sections/.text 查看模块被加载到哪里了，然后再使用 add-symbol-file /path/to/foo.ko <输出的地址> 加载调试符号。另外，给内核模块打断点需要使用 hbreak 打硬件断点，否则 gdb 会提示无法插入断点。另外退出 gdb 之前记得删除所有断点，不然会导致客户机在下一次触发断点的时候卡死。

使用 qemu gdb server 调试

qemu 本身也支持 gdb 连接到 qemu 程序对客户机进行调试，这种方法只需要在 qemu 启动的时候加入参数 -gdb tcp::1234 就可以了，后面直接启动 gdb 用 target remote localhost:1234 连接到 qemu 调试服务器，这时候按 Ctrl+C 可以直接取得控制权，进行打断点操作。如果要调试内核模块，需要在编译内核的时候以下的配置项都是关闭的（可以直接修改 .config 文件）：

CONFIG_DEBUG_RODATA=n
CONFIG_DEBUG_RODATA_TEST=n
CONFIG_DEBUG_SET_MODULE_RONX=n

然后参照上面的方法加载调试符号即可，可以直接使用 break 来设置断点，不需要用硬件断点。

如果需要访问内核模块的全局变量，还需要加载其他段的地址，可以用这个脚本快速获得所有地址的加载命令：

#!/bin/bash
cd /sys/module/$1/sections
echo -n add-symbol-file $2 `/bin/cat .text`
for section in .[a-z]* *; do
    if [ $section != ".text" ]; then
echo " \\"
echo -n " -s" $section `/bin/cat $section`
    fi
done
echo

脚本第一个参数是模块名，第二个参数是模块 .ko 文件地址。