# ZStack 的伸缩性秘密（三）：无锁架构

> ZStack 提供了一个基于队列的无锁架构，允许任务很容易地控制它们的并行级别，从一个（同步）到 N 个（并行）都行。本文解释了 ZStack 如何利用一致性哈希算法和基于内存的工作队列来避免分布式锁。

- 发布时间: 2015-04-04
- 更新时间: 2015-04-04
- 作者: [张鑫](https://github.com/zxwing)
- 分类: 技术分享
- 标签: 核心架构, 无锁, 并发, 可扩展性, 无锁架构, 工作队列, 同步队列, 异步队列, 一致性哈希, ZStack, 线程池, 分布式协调

> *本文原发布于 [ZStack Blog](http://zstack.org/blog/lock-free.html)。
> ZSvirt 构建于 ZStack 之上，继承了以下描述的全部架构特性。
> 理解这些基础设计，有助于更深入地认识 ZSvirt 的性能优势与技术原理。*

*在 IaaS（Infrastructure as a Service，即基础设施即服务）软件里，许多任务要顺序地执行。例如，当一个启动虚拟机的任务正在运行时，一个停止该虚拟机的任务就必须等待之前的启动任务结束才行。另一方面，一些任务也需要并发地同时运行，例如，在同一主机上 20 个创建虚拟机的任务可以同时运行。同步和并行在一个分布式系统中是不容易控制的，并且常常需要一个分布式协调软件。针对这个挑战，ZStack 提供了一个基于队列的无锁架构，允许任务很容易地控制它们的并行级别，从一个（同步）到 N 个（并行）都行。*

## 动机

一个好的 IaaS 软件在任务的同步及并行上需要有精细的控制。大多数情况下，任务之间有依赖关系，需要以某一顺序来执行；例如，一个删除卷的任务不能被执行，如果另一个在此卷上做快照备份的任务正在执行中。有时，任务需要并发执行来提升性能；例如，在同一台主机上十个创建虚拟机的任务同时执行一点问题也没有。当然，没有适当的控制，并行任务也会损坏系统；例如，1000 个同时执行的创建虚拟机的任务虽不会使系统挂掉，但至少会导致系统有段时间没有响应。这种并发编程问题在多线程环境下已经很复杂，在分布式环境下就显得更加复杂了。

## 问题

教科书告诉我们，锁和信号量是同步和并行的答案；在分布式系统中，处理同步和并行的最直接的想法是使用某种分布式协调软件，像 [Apache ZooKeeper](http://zookeeper.apache.org/)，或者建立在 [Redis](http://redis.io/) 之上的类似软件。使用分布式协调软件（例如 ZooKeeper）的系统概况，像下面这样：

[图片可在规范 HTML 页面中查看: 使用 ZooKeeper 的分布式协调](https://zsvirt.io/zh/blog/lock-free-architecture/)

问题是，对于锁或信号量来说，**一个线程需要等待其它线程释放它们正在持有的锁或信号量**。在 [ZStack 的伸缩性秘密（一）：异步架构](https://zsvirt.io/zh/blog/asynchronous-architecture/) 一文中，我们解释了 ZStack 是一种异步软件，线程不会因等待其它线程的完成而阻塞；因此，锁和信号量不是可行的选项。同时，我们也关心使用分布式协调软件的复杂性和可扩展性，想象一下，一个满载 100,000 个需要锁的任务的系统，这既不容易，也不易扩展。

> **同步 vs. 同步化**：在[第一部分：异步架构](https://zsvirt.io/zh/blog/asynchronous-architecture/)中，我们讨论了**同步 vs. 异步**；在本文中，我们将会讨论**同步化 vs. 并行**。"同步"和"同步化"有时候是可互换使用的，但是它们是不同的。在我们的场景中，"同步"是在讨论执行一个任务是否会阻塞线程的问题；"同步化"是在讨论一个任务是否必须排他地执行的问题。如果一个任务在完成前一直占据一个线程的所有时间，这就是一个同步的任务；如果一个任务不能和其它任务在同一时间执行，这就是一个同步化的任务。

## 无锁架构的基础

使用一致性哈希算法来保证同一个服务实例能够处理所有到达同一资源的消息，这就是无锁架构的基础。通过这种方法把消息聚集到某一节点，可以减少从分布式系统到多线程环境的同步、并行化的复杂性（更多细节见 [ZStack 的伸缩性秘密（二）：无状态服务](https://zsvirt.io/zh/blog/stateless-clustering/)）。

[图片可在规范 HTML 页面中查看: 一致性哈希基础](https://zsvirt.io/zh/blog/lock-free-architecture/)

## 工作队列：传统的朴素解决方案

> **注意**：在深入了解细节之前，请注意，我们即将要谈论的队列，和 [ZStack 的伸缩性秘密（二）：无状态服务](https://zsvirt.io/zh/blog/stateless-clustering/) 一文中提到的 RabbitMQ 消息队列没有任何关联。消息队列是 RabbitMQ 的术语；ZStack 的队列则是内部数据结构。

在 ZStack 中的任务是由消息驱动的，聚合消息让相关的任务可以在同样的节点执行，减轻了经典的线程池并发编程的压力。为了避免锁竞争，ZStack 使用工作队列替代锁和信号量。同步化的任务可以一个接一个地执行，它们由基于内存的工作队列维护：

[图片可在规范 HTML 页面中查看: 同步工作队列](https://zsvirt.io/zh/blog/lock-free-architecture/)

并行任务可以以定义的并行级别执行，它们由带并行级别的工作队列维护。下面的例子展示了一个并行级别等于 4 的队列：

[图片可在规范 HTML 页面中查看: 并行工作队列](https://zsvirt.io/zh/blog/lock-free-architecture/)

> **注意**：一个工作队列可以同时执行同步化的和并行的任务。如果并行级别为 1，那么队列就是同步化的；如果并行级别大于 1，那么队列是并行的；如果并行级别为 0，那么队列就是无限并行的。

### 基于内存的同步队列

在 ZStack 中有两种工作队列。一种是同步工作队列，任务（通常是一个 [Java Runnable](http://docs.oracle.com/javase/7/docs/api/java/lang/Runnable.html)）在返回结果时才被认定为结束：

```java
thdf.syncSubmit(new SyncTask<Object>() {
    @Override
    public String getSyncSignature() {
        return "api.worker";
    }

    @Override
    public int getSyncLevel() {
        return apiWorkerNum;
    }

    @Override
    public String getName() {
        return "api.worker";
    }

    @Override
    public Object call() throws Exception {
        if (msg.getClass() == APIIsReadyToGoMsg.class) {
            handle((APIIsReadyToGoMsg) msg);
        } else {
            try {
                dispatchMessage((APIMessage) msg);
            } catch (Throwable t) {
                bus.logExceptionWithMessageDump(msg, t);
                bus.replyErrorByMessageType(msg, errf.throwableToInternalError(t));
            }
        }

        /* When method call() returns, the next task will be proceeded immediately */
        
        return null;
    }
});
```

> **强调**：在同步队列中，工作线程只要前一个 `Runnable.run()` 方法返回，就会继续读取下一个 Runnable，并且只有队列为空时才返回到线程池。因为任务在执行时会占据工作线程，所以队列是同步的。

### 基于内存的异步队列

另一种是异步工作队列，任务只有在发出一个完成通知时才被认定为结束：

```java
thdf.chainSubmit(new ChainTask(msg) {
    @Override
    public String getName() {
        return String.format("start-vm-%s", self.getUuid());
    }

    @Override
    public String getSyncSignature() {
        return syncThreadName;
    }

    @Override
    public void run(SyncTaskChain chain) {
        startVm(msg, chain);
        
        /* the next task will be proceeded only after startVm() method calls chain.next() */
    }
});
```

> **强调**：在异步队列中，`ChainTask.run(SyncTaskChain chain)` 方法可能在执行一些异步操作后立即返回；例如，发送一条消息并注册一个回调函数。在 `run()` 方法返回后，工作线程回到线程池中；但是，之前的任务可能还没完成，没有任务能够被处理，直到之前的任务发出一个通知（如调用 `SyncTaskChain.next()`）。因为任务不会阻塞工作线程等待其完成，所以队列是异步的。

### 基于数据库的异步队列

基于内存的工作队列简单快速，它满足了在单一管理节点 99% 的同步和并行的需要；然而，与创建资源相关的任务，可能需要在不同管理节点之间做同步。一致性哈希环基于资源 UUID 来工作，如果资源还未被创建，它将无法得知哪个节点应该处理这个创建的任务。在大多数情况下，如果要创建的资源不依赖于其它未完成的任务，ZStack 会选择此创建任务的提交者所在的本地节点来完成这个工作。不幸的是，有些进行中的任务依赖于名为虚拟路由 VM 的特殊资源。例如，如果使用同样的 L3 网络的多个用户 VM 由运行于不同管理节点的任务创建而成，同时该 L3 网络上并没有虚拟路由 VM，那么创建虚拟路由 VM 的任务就可能由多个管理节点提交。在这种情况下，由于存在分布式同步的问题，ZStack 使用基于数据库的作业队列，这样来自不同管理节点的任务就可以实现全局同步。

[图片可在规范 HTML 页面中查看: 基于数据库的作业队列](https://zsvirt.io/zh/blog/lock-free-architecture/)

数据库作业队列只有异步的形式；也就是说，只有前一个任务发出一个完成通知后，下一个任务才能执行。

> **注意**：由于任务存储在数据库之中，所以数据库作业队列的速度比较慢；幸运的是，只有创建虚拟路由 VM 的任务需要它。

## 限制

虽然基于无锁架构的队列可以处理 99.99% 的同步需求，但是有一个竞态条件从一致性哈希算法中产生：一个新加入的节点将分担一部分相邻节点的工作量，这是一致性哈希环扩张的结果。

[图片可在规范 HTML 页面中查看: 节点加入时的竞态条件](https://zsvirt.io/zh/blog/lock-free-architecture/)

在这个例子中，新节点 3 加入后，以前的目标定位从节点 2 转到了节点 3；在此期间，如果对于某个资源的一个旧任务依旧在节点 2 上运行，但是相同资源的新任务提交到了节点 3，这就会造成竞态条件。然而，这种状况并不是你想象中的那么坏。首先，冲突的任务很少存在于规则的系统中，比如，一个健全的 UI 不允许你停止一个正在启动过程中的 VM。其次，每一个 ZStack 资源都有状态，一个开始就处于错误状态的任务会立即返回错误；比如，如果一个 VM 处于停止状态，一个附加卷的任务就会立刻报错。第三，代理（agent）——大多数任务的最终目的地——有额外的同步机制；比如，虚拟路由代理会同步所有修改 DHCP 配置文件的请求，即使我们已经有了虚拟路由 VM 在管理节点端的工作队列。最后，提前规划你的操作是持续管理云的关键；运维团队可以在上线云之前快速启动足够的管理节点；如果他们真的需要动态添加一个新节点，应该在云工作负载比较小的时候做。

## 总结

在这篇文章里，我们展示了建立在基于内存工作队列和基于数据库作业队列之上的无锁架构。在不涉及复杂分布式协调软件的前提下，ZStack 尽可能地在屏蔽竞态条件的同时提升性能。

---

## ZStack 核心架构系列

- [第一部分：异步架构](https://zsvirt.io/zh/blog/asynchronous-architecture/)
- [第二部分：无状态服务](https://zsvirt.io/zh/blog/stateless-clustering/)
- [第三部分：无锁架构](https://zsvirt.io/zh/blog/lock-free-architecture/)
- [工作流引擎](https://zsvirt.io/zh/blog/workflow-engine/)
- [进程内微服务架构](https://zsvirt.io/zh/blog/in-process-microservices/)
- [通用插件系统](https://zsvirt.io/zh/blog/plugin-system/)
- [标签系统](https://zsvirt.io/zh/blog/tag-system/)

## 官方链接


- [规范 HTML 页面](https://zsvirt.io/zh/blog/lock-free-architecture/)
- [在 GitHub 讨论](https://github.com/ZSvirt/zsvirt/discussions)