红帽白皮书新鲜出炉!点击获取,让你的云战略更胜一筹! 了解详情
写点什么

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

  • 2009-08-02
  • 本文字数:2242 字

    阅读完需:约 7 分钟

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

2009-08-02 18:144027
用户头像

发布了 53 篇内容, 共 12.5 次阅读, 收获喜欢 2 次。

关注

评论 1 条评论

发布
用户头像
专家老师您好,我是Ryan Ding来自亮数据。我们是品牌方,寻求付费商业合作。请加我微信联系 ryanding-brd
2024-03-19 15:16 · 美国
回复
没有更多了
发现更多内容

2021年华为Java面经,【面试必备】

Java 程序员 后端

2021年大厂Java面经,Java高并发编程详解pdf下载

Java 程序员 后端

谈一谈最小二叉堆的几种操作

Regan Yue

算法 10月月更

2021最新Java大厂面试真题大全,不明白JVM虚拟机还怎么面试

Java 后端

2021年Java开发者跳槽指南,2021年我们程序员该如何进阶和规划

Java 程序员 后端

2021年大厂Java高级面试题分享,Java高并发秒杀面试题

Java 程序员 后端

2021年春招Java面试题,2021最新腾讯Java面试分享

Java 程序员 后端

阿里亿级长连网关的云原生演进之路

阿里巴巴终端技术

云原生 架构设计 网关 客户端开发

2021年上半年最接地气的Java面经,2021年Java常见面试题目

Java 程序员 后端

2021年是意义非凡的一年,差点挂在第四面

Java 程序员 后端

2021新一波程序员跳槽季,零基础如何成为高级Java开发

Java 程序员 后端

2021年Java常见面试题目,图灵学院诸葛,阿里P7大牛整理

Java 程序员 后端

2021年字节跳动74道高级程序员面试,2021Java面试真题精选干货整理

Java 程序员 后端

2021我是如何拿到小米、京东、字节的offer,Java篇

Java 程序员 后端

2021大厂Java面试经历,Java技术面试常见问题

Java 程序员 后端

2021年Java大厂面试分享,漫谈设计模式在Spring框架中的良好实践

Java 程序员 后端

2021年华为Java面经,顺利收获Offer

Java 程序员 后端

2021年网易Java岗面试必问,Java面试手册pdf

Java 程序员 后端

最新阿里P6-P7Java研发岗面经:技能要求+面试真题+经验总结

Java 程序员 面试 阿里

2021年百度Java面试真题,面试官老爱问适配器模式与外观模式

Java 程序员 后端

2021新鲜出炉阿里巴巴面试真题,王道训练营java百度云盘,阿里高级算法专家

Java 程序员 后端

Go 语言实现 gRPC 的发布订阅模式,REST 接口和超时控制

AlwaysBeta

golang gRPC Go 语言 publish REST API

2021年阿里+腾讯+快手offer都已拿到,Java开发环境

Java 程序员 后端

2021年Java岗位BAT大厂面试题知识点小结,挥泪整理面经

Java 程序员 后端

2021年京东Java岗面试必问,Java中级程序员面试题

Java 程序员 后端

2021年是意义非凡的一年,架构师带你玩转Redis高性能缓存设计实战

Java 程序员 后端

2021年最新Java面试精讲,java开发技术教程,Java简单入门教程

Java 程序员 后端

【AI 全栈 SOTA 综述 】这些你都不知道,怎么敢说会 AI?【语音识别原理 + 实战】

声网

AI 算法 音视频

2021年Java面试心得,从理论到实践!

Java 程序员 后端

2021年最新Java面试精讲,揭秘今年Java春招面试必问问题有哪些

Java 程序员 后端

2021最新Java大厂面试真题大全,附学习笔记+面试整理+进阶书籍

Java 程序员 后端

新的Scala Actor类型系统——谁说竞争安全与性能不可兼得_Java_Sadek Drobi_InfoQ精选文章