新的 Scala Actor 类型系统——谁说竞争安全与性能不可兼得

Philipp Haller 和 Martin Odersky 发表了一篇论文。论文中介绍了一种新的方法，可以保证Scala Actor 模型的实现能够进行安全的消息传输。尽管基于消息的并发有利于构建可伸缩的支持并发进程的体系架构，但是它其实暗含了一项重要的权衡，一方面是性能与功能（灵活度），另一方面则是竞争安全。

在理想的情况下，一个被发送出去的消息应该是“从发送者的一段内存区域（可能不是连贯地）移动到接收者的一段内存区域中”。但是，由于临界代码对性 能具有很苛刻的要求，因此消息必须传递于“运行在相同的共享存储的计算机的不同进程之间”。这些“临界代码需要处理大数据量的消息，比如图像处理管线或者 网络协议栈”。为了避免在这种情况下的数据竞争，应该对消息的特征进行一些限制：它们必须是不可变的，或者是别名自由（alias-free）的。然而， 这样肯定会对性能产生消极的影响，因为“存储在对象图中的数据如果不满足特定的约束，那么首先必须要被序列化为一种合法的形式，然后才能存储在消息中发送 出去。”

Scala 的 Actor 与 Erlang 的不同，前者可以是任意类型：不可变的或者可变的，并且在“同一机器上的不同 Actor 之间传递消息时”，不 会复制它们的状态。这样的确可以获得一些性能和灵活性上的优势，但是对于确保共享内存的竞争安全就要面临挑战了。到目前为止，竞争安全并不是程序库的设计 语言所强制要求的特性，而只是编程约定，这些约定限制了消息传递机制的能力（capabilities）。

为了减少所需的约束条件，Haller 和 Odersky 提出了一种基于能力检查（比如对象的访问权限）和外部唯一性的类型系统。外部唯一性可以“用 来控制被传送对象的别名”，并且可以确保引用的唯一性。他们还深入讨论了引用唯一性的概念，认为在各种基于消息的并发方式中，引用唯一性是确保竞争安全的 核心因素。他们给出了一个例子，其中一个 Actor“接收到一个 linked list 的引用”以及另一个 list，后者“可能是在本地构建的，也可能是从其他地方接收到的”。在程序继续之前，第二个 list 会拼接到第一个 list 上：

 
actor {
   receive {
   	case rlist: LinkedList =>
   		val other: LinkedList = ...
   		rlist.append(other)
   		next.send(rlist)
   }
}
 
class Node {
   var el: Object
   var prev, next: Node
}
class LinkedList {
   var head: Node
   def append(other: LinkedList) {
   	if (head == null)
   		head = other.head
   	else if (other.head != null) {
   		var h = head
   		while (h.next != null) h = h.next
   		h.next = other.head
   		h.next.prev = h
   	}
   }
}

为了能够安全地发送合并后的 list，就必须要检查“有没有引入任何 [外部] 的别名，从而破坏竞争安全”，换句话说，“到 list 的一个唯一的引用，比如 rlist，应该在调用了它的 append 方法后，依然保持唯一性。”

文章作者将满足上述特性的系统命名为“对象能力类型（Object Capability Types，OCT）”，并且还将它形式化为 EPFL Scala 编译器的扩展。为了实现它，Haller 和 Odersky 引入了一系列注释，以一种简单有效的方式添加用于类型检查的必要信息。Scala 标准 库的通用集合类的所有方法不需要改变它们的实现，就可以用这种方法实现改变。三个注释——@unique、@transient 和 @exposed——可 以用于本地变量、方法参数和方法返回结果：

 
class Node {
   var el: Object
   var prev, next: Node
}
class LinkedList {
   var head: Node
   @transient
   def append(other: LinkedList @unique) {
   	expose (this) { xl =>
   		val ol = localize(other, xl)
   		if (xl.head == null)
   			xl.head = ol.head
   		else if (ol.head != null) {
   			var h = xl.head
   			while (h.next != null) h = h.next
   			h.next = ol.head
   			h.next.prev = h
   		}
   	}
   }
}

注释 @transient[…] 可以用于接收者，比如 this。这要求 this 应该是唯一的；尽管如此，调用 this 的方法并不会消耗掉 this 引 用，也就是说，调用以后，引用仍然是可用的（并且是唯一的）。这与我们的需要是一致的，即调用 append 以后，（对象）所有权的转移应该是安全的。用于 参数类型的注释 @unique 要求参数必须是唯一的。然而，它给予方法以消费参数的权利，这意味着当调用返回以后，再访问参数就是非法的了。

[…]

为了防止别名可能会破坏对象的唯一性，在对象被暴露以前，它的域必须能够被访问。

被传送的对象会包含子对象，子对象可能会以更复杂的方式获得别名。为了解决这个问题，作者引入了“簇（cluster）”的概念。尽管如此，簇并没有显式地声明“类型系统根据对象构造和被操作的方式，检查簇的属性”：

在我们的系统中，传送对象是否安全取决于通过该对象能够到达的各个对象。当且仅当对象 O2 的某个域指向另一个对象 O1，或者一个指向 O1 的对象，那么我们称 O2 可以到达 O1。我们的系统的可以保证那些标识为簇的对象图的安全转移。[…]

[它] 能够静态地保证一个对象簇在传输的过程中是外部唯一的，这样可以实现类型安全的目的。

OCT 系统除去了现有方法所必需的一些针对消息的关键约束，同时在处理大尺寸消息的应用程序中，能够兼顾竞争安全性和性能。尽管它已经实现为了 Scala 的轻量级扩展，为了更进一步地推广这种方法，Philipp Haller 和 Martin Odersky 打算引入类型推理，从而能够替开发者完成更多的事情。

查看英文原文： A Type System for Scala Actors to Enforce Race Safety Without Sacrificing Performance