Hello World
Spiga

ActorLite:一个轻量级Actor模型实现(上)

2009-05-11 20:10 by 老赵, 33888 visits

Actor模型

Actor模型为并行而生,具Wikipedia中的描述,它原本是为大量独立的微型处理器所构建的高性能网络而设计的模型。而目前,单台机器也有了多个独立的计算单元,这就是为什么在并行程序愈演愈烈的今天,Actor模型又重新回到了人们的视线之中了。Actor模型的理念非常简单:天下万物皆为Actor,Actor之间通过发送消息进行通信。Actor模型的执行方式有两个特点:

  1. 每个Actor,单线程地依次执行发送给它的消息。
  2. 不同的Actor可以同时执行它们的消息。

对于第1点至今还有一些争论,例如Actor是否可以并行执行它的消息,Actor是否应该保证执行顺序与消息到达的一致(祥见Wikipedia的相关词条)。而第2点是毋庸置疑的,因此Actor模型天生就带有强大的并发特性。我们知道,系统中执行任务的最小单元是线程,数量一定程度上是有限的,而过多的线程会占用大量资源,也无法带来最好的运行效率,因此真正在同时运行的Actor就会少很多。不过,这并不影响我们从概念上去理解“同一时刻可能有成千上万个Actor正在运行”这个观点。在这里,“正在运行”的含义是“处于运行状态”。

Actor模型的使用无处不在,即使有些地方并没有明确说采用的Actor模型:

  • Google提出的Map/Reduce分布式运算平台
  • C#,Java等语言中的lock互斥实现
  • 传统Email信箱的实现
  • ……

Actor模型的现有实现

提到Actor模型的实现就不得不提Erlang。Erlang专以Actor模型为准则进行设计,它的每个Actor被称作是“进程(Process)”,而进程之间唯一的通信方式便是相互发送消息。一个进程要做的,其实只是以下三件事情:

  • 创建其他进程
  • 向其他进程发送消息
  • 接受并处理消息

例如《Programming Erlang》中的一段代码:

loop() ->
    receive
        {From, {store, Key, Value}} ->
            put(Key, {ok, Value}),
            From ! {kvs, true},
            loop();
        {From, {lookup, Key}} ->
            From ! {kvs, get(Key)},
            loop()
    end.

在Erlang中,大写开头的标识表示“变量(variable)”,而小写开头的标识表示“原子(atom)”,而大括号及其内部以逗号分割的数据结构,则被称作是“元组(tuple)”。以上代码的作用为一个简单的“名字服务(naming service)”,当接受到{From, {store, Key, Value}}的消息时,则表示从From这个进程发来一个store请求,要求把Value与Key进行映射。而接受到{From, {lookup, Key}}消息时,则表示从From这个进程发来一个请求,要求返回Key所对应的内容。服务本身,也是通过向消息来源进程(即From)发送消息来进行回复的。

从Erlang语言的设计并不复杂,其类型系统更加几乎可以用“简陋”来形容,这使得其抽象能力十分欠缺,唯一的复杂数据结构似乎只有“元组”一种而已——不过我们现在不谈其缺陷,谈其“优势”。Erlang语言设计的最大特点便是引入了“模式匹配(pattern matching)”,当且仅当受到的消息匹配了我们预设的结构(例如上面的{XXX, {store, YYY, ZZZ}}),则会进入相应的逻辑片断。其次便是其尾递归的特性,可见上面的代码中在loop方法的结尾再次调用了loop方法。

如果说Erlang语言专为Actor模型而设计,那么Scala语言(学Java的朋友们都去学Scala吧,那才是发展方向)中内置的Actor类库则是外部语言Actor模型实现的经典案例了:

class Pong extends Actor {
  def act() {
    var pongCount = 0
    while (true) {
      receive {
        case Ping =>
          if (pongCount % 1000 == 0)
            Console.println("Pong: ping " + pongCount)
          sender ! Pong
          pongCount = pongCount + 1
        case Stop =>
          Console.println("Pong: stop")
          exit()
      }
    }
  }
}

Pong类继承了Actor模型,并覆盖其act方法。由于没有Erlang的尾递归特性,Scala Actor使用一个while (true)进行不断的循环。获取到消息之后,将会使用case语句对消息进行判断,并执行相应逻辑。Scala的Actor类库充分利用了Scala的语法特性,让Actor模型好像是Scala内置功能一样,非常漂亮。

此外,其他较为著名的Actor模型实现还有Io LanguageJetlang、以及.NET平台下的MS CCRRetlang。后文中我们还会简单提到.NET下Actor Model实现,其他内容就需要感兴趣的朋友们自行挖掘了。

Actor模型中的任务调度

Actor模型的任务调度方式分为“基于线程(thread-based)的调度”以及“基于事件(event-based)的调度”两种。

基于线程的调度为每个Actor分配一个线程,在接受一个消息(如在Scala Actor中使用receive)时,如果当前Actor的“邮箱(mail box)”为空,则会阻塞当前线程直到获得消息为止。基于线程的调度实现起来较为简单,例如在.NET中可以通过Monitor.Wait/Pulse来轻松实现这样的生产/消费逻辑。不过基于线程的调度缺点也是非常明显的,由于线程数量受到操作系统的限制,把线程和Actor捆绑起来势必影响到系统中可以同时的Actor数量。而线程数量一多也会影响到系统资源占用以及调度,而在某些情况下大部分的Actor会处于空闲状态,而大量阻塞线程既是系统的负担,也是资源的浪费。因此基于线程的调度是一个拥有重大缺陷的实现,现有的Actor Model大都不会采取这种方式。

于是另一种Actor模型的任务调度方式便是基于事件的调度。“事件”在这里可以简单理解为“消息到达”事件,而此时才会为Actor的任务分配线程并执行。很容易理解,我们现在便可以使用少量的线程来执行大量Actor产生的任务,既保证了运算资源的充分占用,也不会让系统在同时进行的太多任务中“疲惫不堪”,这样系统便可以得到很好的伸缩性。在Scala Actor中也可以选择使用“react”而不是“recive”方法来使用基于事件的方式来执行任务。

现有的Actor Model一般都会使用基于事件的调度方式。不过某些实现,如MS CCR、Retlang、Jetlang等类库还需要客户指定资源分配方式,显式地指定Actor与资源池(即线程池)之间的对应关系。而如Erlang或Scala则隐藏了这方面的分配逻辑,由系统整体进行统一管理。前者与后者相比,由于进行了更多的人工干涉,其资源分配可以更加合理,执行效率也会更高——不过其缺点也很明显:会由此带来额外的复杂度。

我们即将实现的简单Actor Model类库,也将使用了基于事件的调度方式。同样为了简化资源分配的过程,我们将直接使用.NET自带的线程池来运行任务。

Creative Commons License

本文基于署名 2.5 中国大陆许可协议发布,欢迎转载,演绎或用于商业目的,但是必须保留本文的署名赵劼(包含链接),具体操作方式可参考此处。如您有任何疑问或者授权方面的协商,请给我留言

Add your comment

24 条回复

  1. 老赵
    admin
    链接

    老赵 2009-05-11 20:17:00

    刚看到一个新闻:微软发布了Axum。
    微软在并行计算上的投入可谓不遗余力。
    Axum正是构建于MS CCR之上的。

  2. 躺着读书[未注册用户]
    *.*.*.*
    链接

    躺着读书[未注册用户] 2009-05-11 20:49:00

    基于Actor模式的对Java的扩展语言还有JR
    http://www.cs.ucdavis.edu/~olsson/research/jr/
    可惜这个远没有Scale有名。不过它对Actor的处理不是通过类库,而是在语言级别实现的。

  3. DiryBoy
    *.*.*.*
    链接

    DiryBoy 2009-05-11 20:58:00

    沙发没了……

  4. zhangz
    *.*.*.*
    链接

    zhangz 2009-05-11 21:05:00

    既保证了

  5. Indigo Dai
    *.*.*.*
    链接

    Indigo Dai 2009-05-11 21:36:00

    老赵慢点啊,和你的差距越来越大呀,不然没法机会追赶上你了。
    要研究函数式编程等玩意,都要自学一些数学等基础课程,不然深入不下去。
    加油中。呵呵。

  6. 老赵
    admin
    链接

    老赵 2009-05-11 22:02:00

    @躺着读书
    在JVM,CLR上实现一个Actor Model容易,但是实现一个Erlang就很困难,而最大的难点其实是它的link机制,一个process崩溃后提示另外一个……

  7. 老赵
    admin
    链接

    老赵 2009-05-11 22:06:00

    @zhangz
    谢谢。
    文章里不会有例子,例子您可以自己去找的,我已经给出一些资源了。

  8. zhangz
    *.*.*.*
    链接

    zhangz 2009-05-11 22:35:00

    @Jeffrey Zhao
    谢谢,想问老赵个问题,把泛型作为操作数,比如对泛型参数T做sum,CLR via C#里提到用操作符重载或者反射。或者定义一个额外的泛型参数C,约束C实现接口ICalculator<T>,把sum的算法实现委托给接口。但是这样写起来感觉不自然,有点绕,而且有性能问题吧。

  9. 老赵
    admin
    链接

    老赵 2009-05-11 22:37:00

    @zhangz
    没有听懂你的意思,你到底是要做一件什么事情?

  10. zhangz
    *.*.*.*
    链接

    zhangz 2009-05-11 23:26:00

    比如我想实现一个矩阵类Matrix<T> class,定义了矩阵的加法:
    Matrix<T> Add(Matrix<T> m)。
    使用如下:
    Matrix<Int> a = new Matrix<Int>(3,3,data);//初始化,3行3列
    Matrix<Int> b = new Matrix<Int>(3,3,data);//初始化,3行3列
    Matrix<Int> c = a.Add(b);
    因为不能把+,-,×用于泛型类型的变量,在Matrix<T>的Add方法里对T相加是不行的。
    可以定义:
        public interface ICalculator<T>
        {
            T Sum(T a, T b);
        }
        public class IntCalculator : ICalculator<Int>
        {
            public Int Sum(Int a, Int b)
            {
                return a + b;
            }
        }
    然后修改Matrix<T>的定义为class Matrix<T, C> where C : ICalculator<T>, new()。
    在Matrix<T>的Add方法里调用IntCalculator的Sum方法,就把对T的+操作委托给IntCalculator了:
    Matrix<Int, IntCalculator> a = new Matrix<Int, IntCalculator>(3,3,data);//初始化,3行3列
    Matrix<Int, IntCalculator> b = new Matrix<Int, IntCalculator>(3,3,data);//初始化,3行3列
    Matrix<Int, IntCalculator> c = a.Add(b);
    不知道我说清楚了吗?

  11. 老赵
    admin
    链接

    老赵 2009-05-11 23:36:00

    @zhangz
    谢谢您的耐心,呵呵。
    不过您想问的是性能如何吗?性能不会有任何问题的,这里没有调用反射等特别的东西。

  12. Nick Wang (懒人王)
    *.*.*.*
    链接

    Nick Wang (懒人王) 2009-05-12 10:28:00

    这个Actor中文叫什么啊

  13. 老赵
    admin
    链接

    老赵 2009-05-12 10:32:00

    @Nick Wang (懒人王)
    上次在图灵那边问了一下,得到的结果是“不翻译”,就叫Actor模型……

  14. 装配脑袋
    *.*.*.*
    链接

    装配脑袋 2009-05-12 11:49:00

    --引用--------------------------------------------------
    zhangz: @Jeffrey Zhao
    谢谢,想问老赵个问题,把泛型作为操作数,比如对泛型参数T做sum,CLR via C#里提到用操作符重载或者反射。或者定义一个额外的泛型参数C,约束C实现接口ICalculator&lt;T&gt;,把sum的算法实现委托给接口。但是这样写起来感觉不自然,有点绕,而且有性能问题吧。
    --------------------------------------------------------

    “定义一个额外的泛型参数C,约束C实现接口ICalculator<T>,把sum的算法实现委托给接口。”这种做法是非常不对的。如果你定义了ICalculator<T>,应该将这个对象直接传递给你的算法。也就是说,完全采用面向对象的方式提供辅助计算的能力。不要定义额外的类型参数C,它没有任何意义。

  15. 装配脑袋
    *.*.*.*
    链接

    装配脑袋 2009-05-12 11:53:00

    绝对不要写这样的代码(很多.NET泛型滥用者的做法)
    void MyAlgorithm<T, C>(T a, T b) where C : ICalculator<T>

    而是要写成这样:
    void MyAlgorithm<T>(T a, T b, ICalculator<T> calc)

    你可以提供一个不带calc参数的重载,然后利用类型字典等方式提供默认的辅助方法。

  16. zhangz
    *.*.*.*
    链接

    zhangz 2009-05-12 16:55:00

    --引用--------------------------------------------------
    装配脑袋: 绝对不要写这样的代码(很多.NET泛型滥用者的做法)
    void MyAlgorithm&lt;T, C&gt;(T a, T b) where C : ICalculator&lt;T&gt;

    而是要写成这样:
    void MyAlgorithm&lt;T&gt;(T a, T b, ICalculator&lt;T&gt; calc)

    你可以提供一个不带calc参数的重载,然后利用类型字典等方式提供默认的辅助方法。
    --------------------------------------------------------

    谢谢脑袋,看到了你的这篇文章,
    http://www.cnblogs.com/Ninputer/archive/2006/04/14/374921.html
    不过除了“不要定义额外的类型参数C,它没有任何意义。”这个原因外,还有别的坏处吗?

  17. 装配脑袋
    *.*.*.*
    链接

    装配脑袋 2009-05-12 20:53:00

    @zhangz
    多出来的类型参数会让你受很多罪,比如统一功能类没有一个统一的基类,对ICalculator的实现增加了很多限制,而你却没有获得比直接使用接口多任何好处。接口是面向对象的特性,就应该遵照面向对象的方式来使用。泛型用在这里无法增加任何抽象力。

  18. 技术爱好者
    *.*.*.*
    链接

    技术爱好者 2009-05-13 21:32:00

    真找到差距了,我现在才知道基础知识的重要性,真后悔上学的时候……

  19. Arthraim[未注册用户]
    *.*.*.*
    链接

    Arthraim[未注册用户] 2009-05-14 13:41:00

    Axum的确有actor模型的实现~

  20. 老赵
    admin
    链接

    老赵 2009-05-14 13:45:00

    @Arthraim
    从兄弟你的blog上看,你很关注Axum呢,希望今后有机会交流。

  21. Rayn0r[未注册用户]
    *.*.*.*
    链接

    Rayn0r[未注册用户] 2009-07-09 12:01:00

    老赵好!
    小弟现在美国读硕士 导师的导师是UIUC的Gul Agha 当年的Actor Model推动者之一 所以读过您一系列文章感觉很亲切:)

    还有问一下 您的“我的情况”里的图是怎样生成的呢 感觉很直观 也很吸引眼球:)

  22. 老赵
    admin
    链接

    老赵 2009-07-09 17:41:00

    @Rayn0r
    右键属性看看,呵呵

  23. liancheng
    60.166.245.*
    链接

    liancheng 2012-10-05 15:46:45

    文章开头处对Actor模型的描述写道

    每个Actor,单线程地依次执行发送给它的消息。

    “执行”消息总觉得别扭,不如换用“处理”消息。

  24. xfguo
    116.231.207.*
    链接

    xfguo 2014-05-22 12:52:09

    hi, 最近用Lua实现了一个Actor的库,欢迎关注 https://github.com/xfguo/luactor

发表回复

登录 / 登录并记住我 ,登陆后便可删除或修改已发表的评论 (请注意保留评论内容)

昵称:(必填)

邮箱:(必填,仅用于Gavatar

主页:(可选)

评论内容(大于5个字符):

  1. Your Name yyyy-MM-dd HH:mm:ss

使用Live Messenger联系我