Pony-ORCA：并发的actor模型垃圾回收协议

30 浏览量更新于2024-08-25 收藏 360KB PDF 举报

"Ownership and Reference Counting based Garbage Collection in the Actor World - Ponylang (2015)" 在本文中，作者Sylvan Clebsch、Sebastian Blessing、Juliana Franco和Sophia Drossopoulou探讨了一种名为Pony-ORCA的全新并发垃圾收集协议，该协议专门针对演员（Actor）模型设计。Pony-ORCA允许演员在不需任何跨演员同步的情况下并发执行垃圾收集，除了通过消息发送和接收引入的同步机制。传统的垃圾收集通常需要全局暂停或至少部分同步，这在高并发系统中可能成为性能瓶颈。Pony-ORCA解决了这一问题，它借鉴了所有权和延迟、分布式、加权引用计数的概念，并将其应用于演员间的通信系统，确保引用计数的一致性。文章首先介绍了演员模型的背景，该模型由Carl Hewitt在1973年提出，其特点是每个演员都是一个独立的计算实体，通过异步消息传递进行通信。在演员模型中，每个演员都有自己的状态并且并发执行，避免了共享状态导致的并发问题。 Pony-ORCA的关键在于，它建立在一组形式化的不变量基础上，这些不变量保证了垃圾收集的正确性。通过一个示例，作者展示了如何维护这些不变量，并概述了实现这些不变量的具体策略。此外，文章还提供了基准测试结果，证明了该协议可以高效地实现，对系统的整体性能影响较小。所有权在Pony-ORCA中的作用是定义对象的生命周期管理，确定哪个演员可以访问和修改特定对象。引用计数则是用于跟踪对象的活跃引用，当引用计数为零时，表明没有演员需要该对象，可以安全地进行垃圾收集。分布式和加权引用计数则是为了处理并发环境中的复杂情况，比如当演员之间发送消息时，对象的引用可能在多个演员之间转移。加权引用计数允许动态调整引用的权重，以适应不同场景下的垃圾收集需求。总结来说，Pony-ORCA是面向演员模型的一种创新的并发垃圾收集解决方案，它利用所有权和优化的引用计数策略，实现了高效且无需全局同步的垃圾收集，对于构建高并发、低延迟的分布式系统具有重要意义。

Ownership and Reference Counting based Garbage

Collection in the Actor World

Sylvan Clebsch Sebastian Blessing Juliana Franco Sophia Drossopoulou

Causality, and Imperial College London

{sylvan,sebastian,sophia}@causality.io j.vicente-franco@imperial.ac.uk

Abstract

We propose Pony-ORCA, a fully concurrent protocol for garbage

collection in the actor paradigm. It allows actors to perform garbage

collection concurrently with any number of other actors. It does not

require any form of synchronization across actors except those in-

troduced through the actor paradigm, i.e. message send and mes-

sage receive.

Pony-ORCA is based on ideas from ownership and deferred,

distributed, weighted reference counting. It adapts the messaging

system of actors to keep the reference count consistent.

We introduce a formal model and describe the invariants on

which it relies. We illustrate through an example and sketch how

these invariants are maintained. We show some benchmarks and

argue that the protocol can be implemented efﬁciently.

1. Introduction

The actor paradigm [4] was proposed in 1973 by Carl Hewitt [22].

An actor is a computational entity that, in response to a message it

receives, can: 1) send a ﬁnite number of (asynchronous) messages

to other actors; 2) create a ﬁnite number of new actors; and 3)

designate the code to be executed for the next message it receives.

The code executed upon receipt of a message is called a behaviour.

The actor paradigm has been adopted in a functional setting, e.g. in

Erlang [7], and in the object-oriented paradigm [5, 10, 14, 32].

Implicit garbage collection is crucial for convenience of pro-

gramming, however automatic garbage collection often proves to

be a performance bottleneck, e.g, [12] reports pauses of around 3

seconds.

In this paper, we propose Pony-ORCA, a garbage collection

protocol for actor-based object oriented programming languages.

We have implemented Pony-ORCA for the language Pony [6],

but our protocol is applicable for any languages which fulﬁls the

criteria we give later. Our protocol is based on ownership and

deferred distributed weighted reference counting.

Ownership types [15, 30] were proposed with the remit to de-

limit groups of related objects into different areas of the heap. They

were used for garbage collection under the requirement that there

are no incoming references to these areas [31]. Such a scheme

[Copyright notice will appear here once ’preprint’ option is removed.]

works well in the concurrent setting, but the no-incoming refer-

ences requirement is often far too strong.

Reference counting garbage collection puts no requirement on

the heap structure; instead, it tracks, for each object, a count of the

number of references to it held by other objects [8]. This approach

has been further developed to detect cycles and to deal with the

distributed setting [19, 28]. However, the approach has poor local-

ity and thus, in the concurrent setting, it requires synchronization

across the various threads [25].

We employ the locality found in actors, and the implicit syn-

chronisation afforded by the actor messaging system, to develop a

fully concurrent garbage collection algorithm. Pony-ORCA allows

the fully concurrent garbage collection of objects as well as actors.

In particular:

•

An actor may perform garbage collection concurrently with

other actors while they are executing any kind of behaviour.

•

An actor may decide whether to garbage collect an object solely

based on its own local state, without consultation with, or in-

specting the state of, any other actor.

•

No synchronization between actors is required during garbage

collection, other than potential message sends.

•

An actor may garbage collect between its normal behaviours,

i.e. it need not wait until its message queue is empty.

•

Pony-ORCA can be applied to several programming languages,

provided that they satisfy the following two requirements:

Actor behaviours are atomic.

Message delivery is causal—i.e. messages arrive before any

messages they may have caused, if they have the same

destination.

Our approach is based on implicit ownership, whereby an actor

owns any object that it has allocated. Each actor is responsible for

garbage collecting the objects it owns. The challenge is that an actor

may have no path to an object it owns, while other actors may still

have paths to that object, or the object may appear in messages

in some other actor’s message queue. It would be erroneous to

garbage collect such an object.

In our approach, an actor maintains a reference count for all the

objects it owns. The reference count is guaranteed to be non-zero

for any object which is accessible from any message or any actor

other than its owner. Thus, an actor can safely garbage collect any

object which is locally unreachable, and whose reference count is

zero.

There is the remaining challenge of ensuring that the reference

count indeed is non-zero for objects which are accessible from

actors other than their owner. This is maintained through a system

whereby all the actors which may reach an object they do not

1 2015/4/13

下载后可阅读完整内容，剩余8页未读，立即下载

weixin_38503233

粉丝: 9
资源: 918

Pony-ORCA：并发的actor模型垃圾回收协议

"全球SaaS趋势报告：近两年来，典型组织的SaaS堆栈有近一半发生了变化

"探索MFC电子课件：分组与研究型学习提升学习效果

"华润集团架构重组：穷则变，变则通

The Agile Culture - Leading through Trust and Ownership

ownership-status-collection

Ownership structure and performance of the largest German companies.pdf

Adminitrator's Reference 11gR2 for Unix-Based

Research on the relationship between ownership structure and growth of aperiodic Enterprise

Achieving proof of shared ownership for the shared file in collaborative cloud applications

existence-integrity-ownership-proof

最新资源