JVM上的确定性执行机制

摘要：

在很多情况下（比如加密总账），我们需要确保程序能够按照确定性来运行，并且能够运行结束。在这片文章里，Ben Evans介绍了WhitelistClassLoader背后的原理。

正文：

要点

• 目前的加密货币并不适用于一般性的支付网络
• 具有加密验证机制的分布式共享总账能够在一些场景下发挥它的作用
• 通过编程框架编写“智能契约”（smart contract）来构建共享总账，并用于操作共享总账的状态，这已成为一种趋势
• 从基础计算机科学角度来看，智能契约语言不可避免地存在一些问题
• JVM的类加载机制可以规避这些问题，并为智能契约提供了确定性执行（deterministic execution）机制

很多开发人员对比特币和加密货币都有所了解。媒体上充斥着各种耸人听闻的非法交易和犯罪活动事件，这些事件的中心内容都与比特币有关。

比特币的主要属性（公开的交易匿名总账、不可逆的交易、不可靠的账号网络）在支付网络的日常合法交易中表现得力不从心，这种趋势日渐突显。

不过，如果单纯从技术角度来看，加密货币的开发在某些方面还是很有趣的。它们在合法领域的应用开发才刚刚起步。随着比特币和加密货币技术的发展，一些有趣的技术开始显现出来。

这类系统可能在一些行业领域取得成功，比如供应链管理、金融技术（包括清算系统）和所有权登记（特别是对于那些在行政区域内存在录入或腐败问题的物理资产）。2016年的“区块链”热潮正在褪去，不过其相关的技术可以被用于真实场景。

由Linux基金维护的Hyperledger就是一个很有趣的项目，包括分布式总账、区块链和机密货币相关技术，有80多个组织对此感兴趣。

这篇文章将聚焦在这个新兴领域的一个特定技术上。试想这样的一种情况，如果共享总账的参与各方彼此了解（可能存在某种被信任的集中式第三方机构，它会分发秘钥对给参与者），那么不可靠性就不再成为问题，公开挖矿（以及大量相关的验证工作）也可以被丢弃掉。

不过即使是这种非常简单的情景，仍然存在一些问题。我们比较关注的一个问题是，如何能够确保每个参与方执行的是一个智能契约，而且这些契约对总账产生的效果是相同的（假设所有参与方都是从相同的总账状态开始的）。

换句话说，健壮的智能契约框架需要确保每一个契约都能够按照确定性来执行，并能够终结执行。这是计算机科学理论研究领域的一个老问题。

每个计算机专业的学生都知道，图灵机是计算机程序执行模型的理论基础。图灵机理论揭示了图灵机与运行在物理机上的等价程序之间的相关性。

因此，编程语言可以被归入图灵语言的范畴，图灵语言可以模拟出所有可能的图灵机（假设内存是无限制的）。非图灵语言显然不如图灵语言来得强大，而且对于计算机科学来说，非图灵语言也不如图灵语言来得有趣。

这种划类是有意义的，但它仍然存在停机问题，这是计算机科学领域的一个基础问题。该问题最初由阿兰·图灵提出：在一个给定的初始状态，不可能存在一种通用的算法，可用于确定一个图灵机是会停止还是会一直运行下去。

这个问题给确定性执行的概念带来了阻碍，在一些基本条件无法得到满足的情况下，比如停机行为不可预测，我们该如何确保所有的程序能够产生相同的结果？幸运的是，有一些技术可以帮组我们绕开停机问题。

首先，我们知道图灵机的定义里有一个前提，就是存储是不受限制的（对于内存也是如此）。但现实的计算机所使用的存储是有限的。或许我们可以通过限制程序和计算的规模来规避停机问题，而函数编程为我们带来了一些启示。假设我们把程序看成从X到Y的有限状态的单次转换（这里的状态可以指有限的图灵机存储），使用符号表示如下：

f : X -> Y

现在，我们把所有可能的程序看成一个空间（有限的），我们往这个空间里添加了一个特别的状态，表示程序在一定时间内不会停止，那么我们就建立起了一个有限（但是很大）的map。

这个map代表了所有可能的程序。map的键是（start_state，program_code），map的值是程序的停止状态，这些状态可以通过在程序上应用start_state获得。这是著名的函数编程技术——备忘录（memoization）。在一个不存在副作用的编程语言里，我们可以使用预计算的结果代替函数调用。也就是说，对于有限状态空间和有限程序来说，它们可以避免停机问题。

不仅如此，函数式思维还为我们带来了关于确定性执行的一般性定义：

给定状态X和函数f，在有限的时间内，不管是谁将函数f应用在X上（假设运行平台具有一致的语义），总能产生相同的状态Y。

不过要注意，确定性执行要求我们在不执行代码的情况下，使用一些编程手段确定一个函数是否满足确定性执行条件。

有了理论基础，我们现在开始进入实际的例子。我们以Corda项目（最近贡献给了Hyperledger项目）的确定性类加载器为例。Corda为编写确定性智能契约提供了一个JVM框架，用于操作分布式总账的状态。

示例代码可以在Corda项目的Github主页上找到。如果有人想参与到项目中，或者想参与讨论、拉取分支，随时欢迎。

乍一看，把JVM看作一个确定性执行平台有点奇怪。JVM的很多东西都是动态的，例如多线程Java程序、垃圾回收、JIT编译的竟态条件所导致的方法运行差异性，等等。

不过，JVM有如下优势。

• JVM字节码语义易于理解和管理
• Java的安全模型被证明是健壮的
• JVM字节码工具已经很成熟
• 类加载机制为确定性代码分析提供了一个便利的平台

Corda沙箱使用类加载机制和运行时组件来达成如下目的。

• 拒绝明显的非确定性程序
• 在加载类时插入资源追踪代码
• 提供了一个系统，用于终结那些试图违反资源约束的程序（回滚事务）

WhitelistClassLoader是Corda框架里的一个类加载器。它会拒绝加载直接或间接创建线程的代码，因为所有多线程程序都是非确定性的。

这个类加载器包含了一个白名单，名单里列出了所有已知的安全方法，比如Object::getClass()，这个方法是允许被调用的（包含了native代码的方法会被踢出名单）。

这个类加载器会往加载的类里面注入运行时追踪代码，用于检测类的资源使用情况。

这个类加载器系统已经知道JRE包里面的哪些方法是确定性的，这些方法可以被用户代码自由调用。有了这些类加载器组件，就可以为智能契约代码构建一个确定性执行系统。

类加载器客户端在加载类时会调用它的loadClass()方法。这个方法先尝试从缓存里查找类，如果找不到，会委托给父加载器去加载。如果父加载器也无法加载，它会委托findClass()方法去加载。

这个过程遵循标准的Java类加载机制。自定义类加载器一般会通过覆盖findClass()方法来实现自定义的类加载功能。

也就是说，真正实现类加载的是findClass()方法。在WhitelistClassLoader里，findClass()方法会扫描被加载的类是否是确定性的。它使用ASM来读取和检查被加载的类。扫描代码看起来是这样的（经过少许的简化）：

public boolean scan() throws IOException {
  try (final InputStream in = Files.newInputStream(
               classDir.resolve(classInternalName + ".class"))) {
    try {
      // 使用输入流创建一个ASM ClassReader对象
      final ClassReader classReader = new ClassReader(in);
      // 创建一个ClassVistor，用于分析加载的类是否是确定性的。
      // 我们使用CandidacyStatus对象持续跟踪在扫描过程中遇到的方法, 
      // 并标记它们是否为确定性的。
      ClassVisitor whitelistCheckingClassVisitor
        = new WhitelistCheckingClassVisitor(classInternalName, 
                                            candidacyStatus);
      // 使用ASM的reader和vistor模式来读取要加载的类
      classReader.accept(whitelistCheckingClassVisitor, 
                         ClassReader.SKIP_DEBUG);
    } catch (Exception ex) {
      // ... 这里忽略异常处理部分
    }
  }
  return candidacyStatus.isLoadable();
}

类加载过程最关键的部分是class visitor，它负责给代码添加特定的约束。

例如，关键字strictfp在Java语言里很少被用到，它要求强制遵循IEEE 754浮点数标准。一般来说，很少类会使用这个关键字。不过如果不使用这个关键字，JVM一般会选择在硬件层面进行浮点数运算，其精确度完全取决于硬件。

运行在现代CPU上的JVM一般会给出比IEEE 754更高精确度的结果，不过这也意味着不同的硬件和不同的实现会产生不同的结果，从而造成了不确定性。

确定性类加载器会简单粗暴地拒绝加载没有使用strictfp关键字的程序代码，但很少程序员会用到这个关键字，所以这个让人感到沮丧。不过，WhitelistClassLoader会为所有加载的类打开strictfp开关，以确保浮点数运算行为的一致性。

class visitor在进入主要的分析阶段之前会处理strictfp关键字问题和其他与确定性有关的问题（比如不允许使用finalizer），每个方法对应一个WhitelistCheckingMethodVisitor对象。

在扫描过程中，类加载器会用到CandidacyStatus，它知道某些方法的确定性状态（一般指单类的方法）。从它的名字我们就可以看出，这些方法会被认为是可加载的候选方法。

WhitelistCheckingMethodVisitor的主要任务是为方法调用创建调用图。规则很简单，如果候选方法只调用确定性的方法，那么它也是确定性的。在对整个类进行了扫描之后，调用图可以帮助我们判断整个类是否是确定性的。

这个实现起来很简单，我们通过覆盖AMS Visitor API的visitMethodInsn()方法来实现。

public void visitMethodInsn(int opcode, String owner, String name, 
                            String desc, boolean itf) {
  CandidateMethod candidateMethod = 
              candidacyStatus.getCandidateMethod(currentMethodName);
  String internalName = owner + "." + name + ":" + desc;
  if (candidacyStatus.putIfAbsent(internalName)) {
    candidacyStatus.addToBacklog(internalName);
  }
  CandidateMethod referencedCandidateMethod = 
              candidacyStatus.getCandidateMethod(internalName);
  candidateMethod.addReferencedCandidateMethod(referencedCandidateMethod);
      // ...
}

method visitor也需要考虑到一些边界情况，还需要做一些清理工作。例如，Java运行时会停止超限的线程，并抛出ThreadDeath错误，捕捉到ThreadDeath异常的代码会试图绕过确定性检查。

对于这种情况，为了避免ThreadDeath异常或者它的父类（Error或Throwable）被捕捉到，method visitor需要实现一些逻辑，这些逻辑代码需要在访问try-catch代码块时被调用。

public void visitTryCatchBlock(Label start, Label end, 
                               Label handler, String type) {
  if (type == null)
    throw new IllegalArgumentException("Exception type must " + 
            "not be null in try/catch block in " + currentMethodName);
    // 不允许ThreadDeath或它的父类被捕捉到，从而保证了确定性
    if (type.equals(Utils.THREAD_DEATH) || type.equals(Utils.ERROR)
                    || type.equals(Utils.THROWABLE)) {
      CandidateMethod candidateMethod = 
             candidacyStatus.getCandidateMethod(currentMethodName);
      candidateMethod.disallowed("Method " + currentMethodName + 
             " attempts to catch ThreadDeath, Error or Throwable");
    }
  }
}

在确定了单个方法的调用图之后，通过简单的分析就能判断方法是否是确定性的。如果一个方法具有如下两个特点，那么它就是确定性的。

• 没有明显的非确定性特征。
• 只调用了确定性的方法。

单个方法扫描完毕之后，程序返回。等所有方法扫描完毕，class visitor会检查是否所有方法都被标记为确定性的。如果是，那么这个类就被标记为可加载的，并在加载之前注入运行时资源监测代码。

这个白名单框架刚面世不久，建议对其多做一些测试。它所提供的确定性执行机制不仅适用于新的需求场景，也为那些对确定性要求很高的生产系统提供了良好的基础。

关于作者

Ben Evans是jClarity的联合创始人。jClarity是一个初创公司，致力于为开发和运维团队提供性能方面的工具和服务。他是LJC（London Java User Group）的组织者，也是JCP执行委员会成员，为Java生态系统制定规范。他获得过Java Champion殊荣，并3次拿下JavaOne Rockstar Speaker的称号。他是《Java程序员修炼之道》（The Well-Grounded Java Developer）和《Java技术手册》（Java in a Nutshell）的合著者，还是Java平台、性能、并发等相关主题的演讲常客。Ben擅长演讲、教授、协作和咨询，可以直接联系他以便获得更多的信息。

查看英文原文：Deterministic Execution on the JVM