本文将会以 Minecraft 为例介绍 3D 沙盒游戏服务器的运行模型、该单线程模型的限制，提出一种可行的、基于区域锁的并行化模型，分析其可行性，并给出对应的实现细节、调度优化方法等。

介绍

Minecraft 是一个 3D 建造沙盒游戏，发行内容包含一个单独的服务端程序可供多人联机游玩。Minecraft 服务器使用单线程运行，一次完整的逻辑循环称为一个游戏刻。

正常情况下服务器每秒运行 20 次逻辑循环，即以 20 TPS(Ticks per second) 运行。当性能达到瓶颈时，服务器难以在 50 毫秒内处理一次游戏刻，客户端将会体验到服务器出现明显卡顿，服务器性能下降的数值体现为 TPS 低于 20。通常情况下，服务器的计算任务与客户端连接数量成线性关系，由于服务器上几乎所有逻辑都运行于单个线程，其性能取决于处理器的运算能力，因此单个服务器能够为客户端提供良好服务的数量受到单个处理器性能限制。一般认为，单个服务器最多能为数十个客户端提供服务。

目前来说，提升服务器处理能力有三种方法。第一种可靠的方法是优化代码以减少计算量，以 Spigot、Paper 等项目为代表，但这种方法并没有改变服务器的单线程模型，因此伸缩性仍然较差。第二种可靠的方法是通过转发软件如 BungeeCord 进行负载均衡，但这种方法降低了客户端的服务体验，对于同一场景下多个客户端的场景仍然不能提供良好服务，但这一方法可以让单个负载均衡集群处理高达数万个客户端连接。第三种方法是改变服务器的处理模型，引入并行化处理，其中 Aikar 提出了一种被动拆分的并行化模型56，但该模型的最小并行粒度是区块，并暴露了线程安全问题给插件开发者；部分服务端实现了并行的光照计算7、异步实体寻路计算、多个维度并行计算8，但都未达到生产环境可用，并且对第三方注入的代码（插件及模组）做出了能够正确处理并行的假设，而这一点通常是无法达到的。

并行化服务器由于以下原因变得十分有挑战性。

  1. 在线问题。服务器需处理客户端的网络包，因此存在不可预测的逻辑计算。对于单个游戏对象的逻辑计算，我们不知道其何时会停止。
  2. 存在嵌套。游戏在处理方块更新时会传播其方块更新，而这样的方块更新会引入新的方块更新，该过程是不可预测的9。对于含有外部代码如插件和模组事件的逻辑，可能存在递归调用。
  3. 存在时序（依赖）。服务器内的对象在逻辑循环内有一定的顺序，有时这样的顺序是重要的，例如红石电路对于处理顺序有一定要求9。对于严格依赖时序的游戏内容，并行化后自然会乱序执行，因此这种情况超出了讨论范围，这里认为其本身为未定义行为，任何情况皆可接受。
  4. 存在外部代码。几乎所有第三方服务端都提供了加载外部代码的功能，不限于模组和插件，因此应该存在一种机制正确处理外部代码。部分框架提供了字节码处理的功能，这种情况显然超出了讨论范围。
  5. 存在全局状态。红石线方块存在被享元对象修改的全局状态（shouldSignal），其他部分代码也有类似情形。

为解决这些问题，本文将包含以下内容。

  1. 提供一种并行化运行模型。我们将 Minecraft 服务器的各类逻辑运算抽象为事务，并以合适的方式调度之，利用细粒度的互斥锁和共享锁保证其并发安全性。本文还将讨论该模型与一般的事务性数据库的区别。
  2. 提出一种线程池的实现，并对运行的计算任务以合适的方式、或利用 JVM 的 Continuation 机制进行管理，并使用一种启发式算法进行调度优化。
  3. 提出一种对拓展及事件开放的 API 设计，用于描述事务的属性。

问题描述

在这一节内，我们将分析 Minecraft 服务器的计算任务架构，并提出我们的并行化运行模型。

游戏刻循环

如同大部分游戏服务器，Minecraft 服务器使用单线程运行，一次完整的逻辑循环称为一个游戏刻。

在一个游戏刻内，服务器会按顺序更新（tick）每个世界及其中的每个区块，而区块通常被认为是更新的最小单位。区块更新包含了对于实体的更新和对于方块的更新，其中实体更新包括 AI 计算、寻路、移动和碰撞等，方块更新包括计划刻更新、随机刻更新和方块实体更新，这几个内容组成了多数服务器的主要计算任务。

分析几个主要的计算任务之后不难得出，对于单个对象如实体而言，其自身的计算任务是有依赖关系的，因此我们不能首先计算移动再计算寻路；而对于不同对象之间，尽管它们之间可能会互相影响，如两个 TNT 实体的爆炸顺序会导致不同的结果，但对于 Minecraft 而言，并没有明确定义的依赖关系：对于实体更新列表使用哈希表存储，方块更新顺序使用哈希表存储因此表现为随机9。因此，我们可以将不同对象的更新并行化，同时保留单个对象更新任务的顺序。

对于单个对象不同阶段的更新任务而言，我们可以分析其对于服务器内存数据这一资源的访问模式。大部分更新任务都具有良好的“空间局部性”，例如对于实体碰撞而言，更新中只会读取附近一小部分的实体并修改它们的速度值。同时，大部分更新任务需要读写的部分具有不同的类型，如实体寻路会读取世界的方块数据并写入自身实体的目标寻路数据。因此，对于不同的更新任务，我们可以在空间上使用锁保证其执行的正确性，同时对不同的读写类型分别进行细粒度锁定。

运行模型

我们接下来提出一个基于以上分析得出的模型。

对于每个更新任务，我们定义区域（Extent）用于描述其对于资源的使用属性。每个区域 E 描述了其类型 T 、其范围形状 R 和其是否互斥 F，F 为 S (Share) 共享或 X (Exclusive) 独占。为简化模型，我们将形状 R 定义为正方体，记作 [l,x,y,z]:r，例如对于世界 1 坐标 0,0,0 处附近 16 格的范围记作 [1,0,0,0]:16，其为从 -16,-16,-16 到 16,16,16 的 32x32x32 正方体。

我们接下来定义类型 T 的树形结构。由前分析得知，不同的更新任务可以读写分离的不同部分世界数据，如实体寻路读取方块数据写入实体数据。同时，某些类型的更新任务可能包含全局状态，因此我们可以得出一个类型的树形结构，以 GLOBAL 为根。

        GLOBAL
          |
        LEVEL
      ___/ \___
     /         \
   BLOCK      ENTITY
     |
BLOCK_ENTITY

对于任意一个类型 T，T 包含了所有子类型。对于这一类型树，可以拓展其以获得更细的粒度。

接下来我们定义区域 E 的重叠。对于区域 E1{T1,R1,F1} 和 E2{T1,R1,F1}，有以下规则：

  • 如果 T1 为 GLOBAL 或 T2 为 GLOBAL，则重叠；
  • 否则，如果 T1 和 T2 互相不包含对方，且 T1 T2 不相等，则不重叠；
  • 否则，如果 R1 R2 的维度 l 不相等，则不重叠；
  • 否则，如果 E1 E2 都不独占，即 F1 == F2 == S，则不重叠；
  • 否则，如果 R1 R2 的距离（任意坐标差绝对值的最大值 max{abs(x1-x2), abs(y1-y2), abs(z1-z2)}）小于 R1 R2 的 r 之和，则重叠。
  • 否则不重叠

每个更新任务由一系列区域 E 组成，当两个更新任务的每个区域互不重叠，则它们不重叠。重叠的更新任务不能并发进行。至此，我们的模型与一个事务数据库相似，但仍有一定不同。

处理死锁

当一个线程会请求对资源的独占控制，且已经占有资源后再次请求其他资源独占，且除了中断（Abort）以外无法释放资源时，死锁将会发生10。对于我们的模型，可能会包含嵌套的更新任务，这三个条件均可以满足，因此会发生死锁。

在事务性数据库中，事务可以被中断，因此可以使用类似 2PL 的技术，在发生死锁时中断某个事务的执行进行重试11。我们的模型不同之处在于，其更新任务无法被中断。同时，对于一个更新任务而言，一定需要对一个区域的独占访问以保证执行的正确性。因此，我们需要破坏“已经占有资源后再次请求其他资源独占”这一死锁发生的条件。

常见的防止发生死锁的方法有几种，分别是串行化执行、一次性请求所有资源、抢占式资源占有和对资源排序1012。串行化执行完全抛弃了并发，与本文的目标不符，因此不作考虑。抢占式的资源需要修改已有代码以支持对一个更新任务的中断，同时不对拓展开放，因此不作考虑。在本模型中，难以对三维空间中的范围这一资源进行排序，因此不作考虑。

本模型使用一次性请求所有资源进行死锁避免，因此需要要求所有的更新任务提供其占有资源的范围，即一系列区域。在每个更新任务开始前，对这一系列区域进行锁定。如果无法在任务开始前确定占有资源的范围，则进行 GLOBAL 的锁定。

实现

本节将会介绍以上提出的模型的实现方式。

区域锁

本模型需要对不能并行的更新任务进行正确的约束，因此需要一个对区域进行锁定的实现。我们在这里提出一种“无锁”的区域锁（ExtentLock）实现，并且支持 lock 和 tryLock 两种锁定方式。这里的无锁指多个线程可以并发地查询、插入该区域锁对象，而不需要对区域锁对象本身进行互斥访问。

因为我们需要满足一次性请求所有资源，因此所有的锁定操作都接受一系列区域作为参数。

区域锁将会有三种基本的操作：锁定、尝试锁定和释放。锁定操作将会阻塞至成功锁定对应区域；尝试锁定将会尝试锁定区域，并在存在重叠的区域时立刻返回失败；释放将会释放一个已经锁定的区域。

区域锁将使用一个线程安全队列实现，满足其锁定的发生顺序。

对于锁定操作，我们希望 1) 对重叠的区域释放的操作发生在返回之前，同时 2) 对于两个并行发生并且互相互斥的锁定操作，我们希望先成功的锁定操作对应的释放操作发生在后成功的锁定操作之前。对于这样的语义，我们可以使用 CountDownLatch 保证发生的先后顺序：CountDownLatch 的 countDown 操作发生在 await 操作返回之前。因此锁定操作的实现如下：

  • 新建一个 CountDownLatch，记作 L，传入的一系列区域对应该 L
  • 向队列插入传入的一系列区域
  • 对队列内所有插入时已经存在的区域，检查其是否与请求锁定的区域重叠
    • 如果重叠，则等待其 L 释放
  • 返回成功

对于尝试锁定操作，其实现与锁定类似，但在重叠时不进行等待而直接返回：

  • 新建一个 CountDownLatch，记作 L，传入的一系列区域对应该 L
  • 向队列插入传入的一系列区域
  • 对队列内所有插入时已经存在的区域，检查其是否与请求锁定的区域重叠
    • 如果重叠，则移除插入的一系列区域，然后释放 L，返回失败
  • 返回成功

对于释放操作的实现如下：

  • 移除插入的一系列区域
  • 释放 L

对于该实现，锁定返回之前等待了之前锁定所有区域的释放，因此满足了第一个条件；插入的先后顺序由队列的实现保证，而插入后检查了插入前的所有区域，因此满足了第二个条件，故该实现正确。

执行更新

在具体执行游戏对象的更新时，我们将需要并行化的更新任务投入线程池，并等待所有任务完成。大部分耗时且有并行可能的任务通常由一个循环开始，对于该循环，我们将其中的每个元素更新的调用和该更新任务的描述（即其一系列区域）提交至线程池，使用区域锁进行互斥保护，并等待线程池中所有任务执行完成。在等待并行执行时，主线程被挂起。

前文提到了我们可以对同一个对象的更新任务进行阶段的切分。切分的主要目的是在完成某个任务后释放其占有的资源，并等待申请新资源的锁。切分的实现可参考 Minecraft 对于 Profiler 的实现方式，在每个阶段切换时通过一个 popPush 调用，完成对原有资源的释放和新资源的锁定。该方法对于代码的修改较小，实现为插入一条方法调用，通常不会影响类似 Mixin 等字节码操作框架的执行。

任务调度算法

在对任务切分并提交至线程池后，我们的目标变为将这一系列任务的执行以最短的时间完成。该目标与一个事务型数据库的事务处理相似，需调度一系列存在竞争的任务。对这一方面的研究称为竞争感知调度1314（Contention aware scheduling），但与一般的事务型数据库不同的是，本模型既不能中断事务也不能部分分配一个锁，因此大部分适用于事务数据库的优化不适用此处。同时，我们不在意尾延迟（tail latency）、平均事务延迟等一般事务数据库需要考虑的指标，唯一的目标是最大化吞吐量，即最小化总延迟。

对于任务的调度，本模型采用在每个阶段开始之前挂起线程后，通过调度器编程进行指定任务的线程启动。同时对于支持协程15的 JVM 而言，可以在更新任务切换阶段时挂起该协程，进行任务的调度。理论上而言，协程并不是一个必须的技术，因为对于线程模型而言，我们也可以挂起线程进行调度，但达到相同的调度效率需要启动与调度集大小相同的线程数，这可能是数千，而几千个线程将消耗数 GB 的内存。

对于本模型的任务，我们可以使用一种启发式算法进行调度。每个更新任务可以提供其将要占用的资源，即一系列区域。我们引入竞争度优先调度，利用前文定义的更新任务重叠，定义一个更新任务的竞争度为该任务与更新任务队列中参与调度所有任务的重叠数量。对于所有任务，优先执行竞争度最大的。该启发式算法对于仅有互斥锁的情况下可降低一半以上的调度时间消耗，对于存在共享锁的情况优化能力稍弱，但相比原始实现仍有显著提升。

我们也进行了对于该调度问题的其他算法尝试。一个尝试是进行 k-means 聚类16后按 cluster 进行调度，相比于原始算法有所提升，但弱于竞争度优先算法。另一个尝试是实现了一个一般的事务型数据库基于图的调度器，但在对于区域切分时遇到困难，同时难以实现一次性分配所有锁的同时对锁进行调度。

处理嵌套

本模型中存在这样一种情况，在一个更新任务运行时会启动另一个任务，即存在任务的嵌套。对于一般的线程池而言，其遵循一个先进先出的队列模型，而对于嵌套的任务，其完成发生在上一级任务完成之前，即遵循后进先出的栈模型。

对于嵌套的任务执行，一种解决方法是立刻执行，不向线程池提交，但这种方法在一种情况下会降低并行性，即当前任务可以生成多个嵌套任务时；另一种方法是向线程池提交，但 Java 默认的线程池实现将会使得一个线程等待另一个线程完成，对于固定大小线程池可能会导致死锁，也可能造成运行时产生过多线程数影响性能。如果提高并行性，我们就需要在原来任务等待时执行嵌套任务，执行完嵌套任务后执行原来任务省下的部分1718。

对于这种情况通常有三种方式实现。第一种方式是类似异步函数一般直接返回，但这种方法需要对代码进行转换，因此不作考虑。第二种方法是在等待时直接执行其他任务，这种方法需要充足的栈空间。第三种方法是将栈直接保存，重新执行其他任务后恢复原来的栈继续执行，这种方法需要 JVM 支持。

  1. 5.https://github.com/PaperMC/Paper/issues/1001 ↩
  2. 6.https://github.com/PaperMC/Paper/issues/1031 ↩
  3. 7.https://github.com/TorchSpigot/Torch/blob/master/sources/src/main/java/io/akarin/server/mixin/lighting/MixinWorldServer.java ↩
  4. 8.https://github.com/WearBlackAllDay/DimensionalThreading ↩
  5. 9.https://bugs.mojang.com/browse/MC-11193 ↩
  6. 10.Isloor S S, Marsland T A. The Deadlock Problem: An Overview[J]. Computer, 1980, 13(9): 58-78. https://doi.org/10.1109/MC.1980.1653786 ↩
  7. 11.Philip P. Macri. Deadlock detection and resolution in a CODASYL based data management system[C]. , 1976. https://doi.org/10.1145/509383.509392 ↩
  8. 12.Havender J W. Avoiding deadlock in multitasking systems[J]. IBM systems journal, 1968, 7(2): 74-84. https://doi.org/10.1147/sj.72.0074 ↩
  9. 13.Blagodurov S, Zhuravlev S, Fedorova A. Contention-aware scheduling on multicore systems[J]. ACM Transactions on Computer Systems (TOCS), 2010, 28(4): 1-45. https://doi.org/10.1145/1880018.1880019 ↩
  10. 14.Tian B, Huang J, Mozafari B, et al. Contention-aware lock scheduling for transactional databases[J]. Proceedings of the VLDB Endowment, 2018, 11(5): 648-662. https://doi.org/10.1145/3177732.3177740 ↩
  11. 15.https://bugs.openjdk.java.net/browse/JDK-8277131 ↩
  12. 16.Hartigan J A, Wong M A. Algorithm AS 136: A k-means clustering algorithm[J]. Journal of the royal statistical society. series c (applied statistics), 1979, 28(1): 100-108. https://doi.org/10.2307/2346830 ↩
  13. 17.Felleisen M. The theory and practice of first-class prompts[C]//Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages. 1988: 180-190. https://doi.org/10.1145%2F73560.73576 ↩
  14. 18.Bob N. What Color is Your Function[EB/OL]. 2016. https://journal.stuffwithstuff.com/2015/02/01/what-color-is-your-function/ ↩