[Fwd]为什么函数式编程至关重要？

为什么函数式编程至关重要？

• 作者：John Hughes
• 翻译：CloudiDust
• 修订：ShiningRay
• 原文地址：http://www.md.chalmers.se/~rjmh/Papers/whyfp.html
  本作品采用知识共享署名-非商业性使用-相同方式共享 2.5 中国大陆许可协议 进行许可。

Why Functional Programming Matters
John Hughes,
Institutionen f?r Datavetenskap,
Chalmers Tekniska H?gskola,
41296 G&oumlteborg, SWEDEN.
rjmh@cs.chalmers.se

此论文作于1984年，作为查麦兹大学的备忘录流传了多年，经过小幅度修订的版本出现于1989年与1990年，即［Hug89］与［Hug90］。此版本基于原查麦兹大学备忘录的nroff 源码，为LaTeX做了改动,使其更接近于印刷版本，并纠正了少许错误。请容忍这种有点过时的排版吧，另外文中的例子也不是用Haskell写的！

摘要

随着软件变得越来越复杂，良好的软件结构也越来越重要。结构良好的软件易于编写，易于调试，同时提供可复用模块以降低未来开发的成本。常见的语言在对问题进行模块化方面具有理念上的局限性，而函数式语言超越了这些局限。在本文中我们将特别展示函数式语言的两大特性――高阶函数与惰性求值，它们能够极大地促进模块化。作为例证，我们运用列表和树编写了一些数值算法，并实现了alpha-beta启发式搜索（一个人工智能算法，用于游戏系统中）。由于模块化是成功程序设计的关键，所以函数式语言对现实世界而言便极其重要了。

1 引言

本论文试图向"现实世界"证明函数式程序设计是极其重要的，同时本文也试图明确指出函数式编程的长处，以帮助使用函数式语言的程序员们将这些长处发挥到极致。

函数式语言之所以如此称呼，是因为程序完全是由函数组成的。主程序本身也是一个函数，以程序的输入为参数，并给出其输出作为结果。主函数一般是根据其他函数进行定义的，而这些函数又同样是根据更多的其他函数来定义，直到最低层的函数是语言的原生函数。这些函数与普通的数学函数很相像，因此在本文中将以普通等式来定义它们。本文的标记法遵循Turner的程序语言Miranda(TM)中的表示方法，不过对于之前没有函数式语言相关知识的读者，也可以看得懂。（Miranda是 Research Software Ltd.的商标）

函数式程序设计的特性与优点差不多都总结为：函数式程序不包含任何赋值语句，因此变量一旦被赋予一个值，就不再改变。更一般地说，函数式程序不包含任何副作用：除非对函数进行求值，它不会有任何效果。这一特性消灭了错误的一个主要来源，同时也使执行顺序不再重要――因为没有副作用能够改变表达式的值，因此可以在任何时刻对它求值。这一特性将程序员从规定控制流的重担之下拯救出来。由于表达式可以在任何时刻被求值，程序员便可以随心所欲地使用自己要的值来代替变量，反之亦然――也就是说，程序是"引用透明"的。这一自由使得函数式程序与它们传统的对应物相比，更容易数学化地控制。

这样一些"优点"都很不错，但如果说外行人不把它当回事，也不会令人惊讶。它列出了很多关于函数式程序设计"没有"什么（它没有赋值，没有副作用，没有控制流）但却没多说它"有"什么。函数式程序员听起来很像是中世纪的僧侣似的，他们禁绝了尘世中的种种乐趣并且期望这能使自己变得高洁。对于那些更关心物质利益的人而言，这些"优点"并没有多大的说服力。

函数式程序员们会争辩说，函数式程序设计确实有巨大的物质利益――一个函数式程序员拥有比其他使用常见语言的同行高得多的生产力，因为函数式程序短得多。但这有什么道理吗？在这些"优点"的基础之上，唯一的很靠不住的借口就是，一般的程序中有90％是赋值语句，而在函数式程序中这些全都可以省略！这真是太荒唐了，如果省略赋值语句可以带来如此巨大的好处，那么FORTRAN程序员们二十年前早该这样干了。通过省略特性来使语言更加强大在逻辑上是不可能的，不论这些特性是多么糟糕。

甚至函数式程序员都应该对这些所谓的"优点"表示不满意，因为它们对于发掘函数式语言的威力毫无帮助。不可能写出一个刻意缺少赋值语句或者刻意引用透明的程序。这里没有衡量程序质量的标准，因此没有作为目标的理想典范。

很明显，对函数式程序设计的特性的描述是不完备的。我们必须找出一些东西来填补――它们不但要解释函数式程序设计的威力，更要给函数式程序员们一个明确的追求目标。

2 与结构化程序设计进行类比

指出函数式与结构化程序设计之间的相似性是很有帮助的。过去，结构化程序设计的特性与优点大致被总结为这样：结构化程序不包含goto语句；结构化程序中的语句块没有多个入口与出口；结构化程序与非结构化的对应物相比，更容易数学化地控制。这些结构化程序设计的"优点"与我们之前所谈到的函数式程序设计的 "优点"在本质上很相似。这些叙述本质上都是否定式的，从而导致了诸如"goto是否必要"之类一大堆没有结果的争论。

事后诸葛亮式地说，很明显，结构化程序设计的这些特性，尽管很有用，但没有触及问题的核心。结构化程序与非结构化程序之间最重要的区别就是，结构化程序是用模块化的方法设计的。模块化设计带来了生产力的巨大提升：首先，小模块可以很快很容易地编写；其次，通用模块可以被重用，使后续的程序可以更快地开发；再次，程序的模块可以独立进行测试，有助于减少调试的时间。

"不使用goto"等等这一类特性，和这没有什么关系。这些特性促进了"程序设计的小改良"，然而模块化设计却促进了"程序设计的大进化"。因此，程序员在FORTRAN或汇编语言中都可以享受结构化程序设计带来的好处，哪怕那需要一点额外的工作。

模块化设计是成功的程序设计的关键，这一观点现在已经被普遍地接受了，而诸如Modula-II[Wir82]，Ada[oD80]以及Standard ML[MTH90]之类的程序语言都内置了语言特性以促进模块化。然而，有一点非常重要，却常常被忽略。当编写一个模块化程序以解决问题的时候，程序员首 先把这个问题分解为子问题，而后解决这些子问题并把解决方案合并。程序员能够以什么方式分解问题，直接取决于他能以什么方式把解决方案粘起来。因此，为了 能在观念上提升程序员将问题模块化的能力，必须在程序语言提供中提供各种新的黏合剂。复杂的作用域规则与对分块编译的支持只对文本层面的细节有帮助，它们没有提供能表达新观念的工具以分解问题。

通过与木匠行业的类比可以认识到黏合剂的重要性。先制作椅子的各部分――坐垫，椅子腿，靠背，等等――而后用正确的方法钉起来，那么制作一把椅子是很容易的。但这取决于将木板与插接口结合起来的能力。如果缺乏这种能力，那么制作椅子的唯一方式，就是 将它从一大块木头里整个地切割出来，这是一项艰巨得多的任务。这个例子同时表明了模块化的非凡威力与拥有合适的黏合剂的重要性。

现在让我们回到函数式程序设计上来。在这篇论文余下的部分里，我们将指出，函数式语言提供了两种新的、非常重要的黏合剂。我们将给出许多可以使用新方法模块化的示 例程序，它们因此变得很简洁。这就是函数式程序设计威力的关键――它允许了大幅改进的模块化设计。这也正是函数式程序员必须追求的目标――更小、更简洁、更通用的模块，用我们将要描述的新黏合剂黏合起来。

3 把函数粘起来

两种黏合剂中的第一种，使简单的函数可以聚合起来形成复杂的函数。以一个简单的处理问题来说明：将列表中的元素累加起来。我们用下面的语句定义列表：

listof X :: = nil | cons X (listof X)

这说明，一个元素类型为X的列表（不论X是什么）可以是nil，代表一个没有元素的空列表，也可以是一个X与另一个由X组成的列表的cons。一个cons就代表一个列表，其首元素为X，而第二个以及后续元素即是另一个X的列表的元素。此处的X可以代表任何类型――例如，如果X是一个"Integer"（整数类型），那么这个定义就是说，一个整数列表，或者是空的，或者是一个整数与另一个整数列表的 cons。依照通常的实践，我们写列表时，仅仅将其元素包含在方括号里，而不是将cons和nil显式地写出来。这是为了标记方便的缩写。例如：

[]        表示    nil [1]       表示    cons 1 nil [1 2 3]   表示    cons 1 ( cons 2 ( cons 3 nil ))

列表中的元素可以通过一个递归函数sum进行累加。sum必须针对两类参数进行定义：一种是空列表（nil），另一种是cons。没有数字时，和是0，因此我们定义：

sum nil = 0

又因为cons的累加和可以通过将列表的第一个元素加到其余元素的累加和上的方式进行计算，所以可以定义：

sum (cons num list) = num + sum list

研究这个定义可以发现，只有下面用方框标出的部分是特定于计算总和的：

          +---+ sum nil = | 0 |           +---+                           +---+ sum (cons num list) = num | + | sum list                           +---+

这说明求和的计算可以进行模块分割，通过一个通用的递归模式和上面框出的部分进行组合。这个递归模式习惯上被称为"归纳"（reduce），因此求和可以表达为：

sum = reduce add 0

方便起见，reduce传递了一个二元函数add而不是一个运算符。add的定义如下：

add x y = x + y

只要将sum的定义参数化，我们便可以得到reduce的定义，即：

(reduce f x) nil = x (reduce f x)(cons a l) = f a ((reduce f x) l)

这里我们写出了(reduce f x)两边的括号以强调它代替了sum。习惯上括号是省略的，因此((reduce f x) l)写作(reduce f x l)。一个三元函数如reduce，当只提供两个参数时，将成为关于那个余下参数的一元函数。一般地，对一个n元函数，给出了m(< n) 个参数后，该函数便成为了关于余下的n-m个参数的函数。我们在下文中将遵守这一约定。

用这种方式将sum模块化之后，我们就可以通过对这部分的重用来获得好处了。最有趣的部分就是reduce了，无需要进一步编程，就可以用于编写一个函数来计算列表中元素的累乘积：

product = reduce multiply 1

它也可以用来测试一个布尔值的列表中是否至少有一个元素为真：

anytrue = reduce or false

或者它们是否都为真：

alltrue = reduce and true

理解(reduce f a)的一种方式是，将其看作一个将列表中的所有cons替换为f，将所有nil替换为a的函数。以列表[1,2,3]为例，既然它表示：

cons 1 (cons 2 (cons 3 nil))

那么(reduce add 0)将其转换为：

add 1 (add 2 (add 3 0)) = 6

而(reduce multiply 1)将其转换为：

multiply 1 (mulitiply 2 (mulitiply 3 1)) = 6

于是，很明显地，(reduce cons nil)将复制列表本身。既然将一个列表追加到另一个列表上的方式是将前一个列表的元素cons到后一个列表前部，我们便得到：

append a b = reduce cons b a

例如：

append [1,2] [3,4] = reduce cons [3,4] [1,2]                    = (reduce cons [3,4]) (cons 1 ( cons 2 nil ))                    = cons 1 ( cons 2 [3,4]))                      （将cons替换为cons，将nil替换为[3,4]）                    = [1,2,3,4]

一个用于将列表中全部元素翻倍的函数可以写作：

doubleall = reduce doubleandcons nil where doubleandcons num list = cons (2*num) list

doubleandcons可以进一步模块化，首先分解为：

doubleandcons = fandcons double where double n = 2*n       fandcons f el list = cons (f el) list

继续分解：

fandcons f = cons . f

其中"."（函数复合，一个标准运算符）的定义为：

(f . g) h = f(g h)

通过代入一些参数，我们可以看出fandcons的定义是正确的：

   fandcons f el = (cons . f) el                   = cons (f el) 所以 fandcons f el list = cons (f el) list

最终得到的版本是：

doubleall = reduce (cons . double) nil

继续模块化，我们得到：

doubleall = map double map f = reduce (cons . f) nil

其中map使任意的函数f作用于列表的全部元素上。映射map是另一个很有用的函数。

我们甚至可以写出一个累加矩阵中的所有元素的函数，该矩阵用列表的列表表示。这个函数是：

summatrix = sum . map sum

map sum使用函数sum分别计算所有行的元素之和，而后最左边的sum将每一行的元素之和累加起来，从而得到整个矩阵的累加和。

这些例子应该已经足以使读者确信，一点模块化的努力可以产生很大的效果。通过将一个简单的函数（sum）模块化为一个"高阶函数"与一些简单参数的组合，我们得到了一个可以用于编写与列表有关的许多函数的部件（reduce），而又不再需要更多的编程努力。不止是对有关列表的函数可以这么干，举另外一个例子，考虑数据类型"有序标记树"，其定义是：

treeof X ::= node X (listof (treeof X))

这个定义表明，一棵X的树，由一个标记类型为X的结点（node），以及一个子树列表组成，而这些子树也是X的树。例如，树：

      1 o        / \       /   \      /     \   2 o       o 3             |             |             |             o 4

可以被表示成：

node 1     (cons (node 2 nil)           (cons (node 3                 (cons (node 4 nil) nil))                  nil))

我们不再给出一个函数例子并将它抽象为高阶函数，取而代之的是，直接给出一个类似于reduce的函数redtree。回忆一下，reduce有两个参数， 一个用于取代cons，另一个用于取代nil。既然树由node，cons和nil组成，那么redtree必须有三个参数――用于分别取代上述三者。由 于树和列表不是同一种类型，我们得定义两个函数分别处理它们。因此我们定义：

redtree f g a (node label subtrees) =         f label (redtree' f g a subtrees ) redtree' f g a (cons subtree rest) =              g (redtree f g a subtree) (redtree' f g a rest) redtree' f g a nil = a

很多有趣的函数都可以通过把redtree和其他函数粘起来的方法来定义。例如，要把一棵数字树上的所有标记累加起来，可以使用：

 sumtree = redtree add add 0

以我们刚才表述的那棵树为例，sumtree展开成：

add 1     (add (add 2 0)           (add (add 3                     (add (add 4 0) 0))                0)) = 10

要生成一个包含树中全部标记的列表，可以用：

labels = redtree cons append nil

仍然是那个例子，得到：

cons 1             (append (cons 2 nil)                     (append (cons 3                                  (append (cons 4 nil) nil))                            nil))     = [1,2,3,4]

最后，可以定义一个类似于map的函数，此函数使函数f作用于树中的全部标记上：

maptree f = redtree (node . f) cons nil

以上这些操作之所以可行，是因为函数式语言允许将传统型语言中不可分解的函数表达为一些部件的聚合――也就是一个泛化的高阶函数与一些特化函数的聚合。这样的高阶函数一旦定义，便使得很多操作都可以很容易地编写出来。不论何时，只要一个新的数据类型被定义，就应当同时定义用于处理这种数据的高阶函数。这样就简化了对数据类型的处理，同时也将与它的表示细节相关的知识局部化了。与（函数式语言）最相像的传统程序语言是 可扩展语言――只要有需求，这种程序语言就好像随时都可以扩展出新的控制结构一样。

4 把程序粘起来

函数式语言提供的另一种黏合剂使得所有程序都可以粘在一起。回忆一下，一个完整的函数式程序只不过是一个从输入映射到输出的函数。如果f和g是这样的程序，那么对程序(g.f)当提供了输入参数input之后，得到：

g (f input)

程序f计算自身的输出，此输出被用作程序g的输入。传统上，这是通过将f的输出储存在临时文件中实现的。这种方法的毛病是，临时文件可能会占用太大的空间， 以至于将程序黏合起来变得很不现实。函数式语言提供了一种解决方案。程序f和g严格地同步运行，只有当g试图读取输入时，f才启动，并且只运行足够的时间，恰好可以提供g需要读取的输出数据。而后f将被挂起，g将继续执行，直到它试图读取另一个输入。一个额外的好处是，如果g没有读取完f的全部输出就终止了，那么f也将被终止。f甚至可以是一个不会（自行）终止的程序，它可以产生无穷多的输出（而不会出现问题），因为当g运行结束时，f也将被强行终止。这就使得终止条件可以与循环体

分离――一种强大的模块化形式。

这种求值方式使得f尽可能地少运行，因此被称为"惰性求值"。它使得将程序模块化为一个产生大量可能解的生成器与一个选取恰当解的选择器的方案变得可行。有些其他的系统也允许程序以这种方式运行，但只有函数式语言对每一个函数调用都一律使用惰性求值，使得程序的每个部分都可以 用这种方式模块化。惰性求值也许是函数式程序员的拿手利器中威力最大的模块化工具。

4.1 牛顿－拉夫森求根法

我们将编写一些数值算法以展现惰性求值的威力。首先，考虑用于求解平方根的牛顿－拉夫森算法。该算法从一个初始的近似值a0开始计算数N的平方根，为了求得更好的解，它使用下述规则：

a(n+1) = (a(n) + N/a(n)) / 2

如果近似值序列趋近于某一个极限a，那么

      a = (a + N/a) / 2 故    2a = a + N/a       a = N/a       a*a = N       a = squareroot(N)

事实上，这个近似值序列确实迅速地趋近于一个极限。平方根算法取一个允许误差（eps）为参数，当两个相邻的近似值之差（的绝对值）小于eps时，算法便终止了。

这个算法通常被编写为类似下面这样：

  C   N IS CALLED ZN HERE SO THAT IT HAS THE RIGHT TYPE           X = A0           Y = A0 + 2.*EPS   C   THE VALUE OF Y DOES NOT MATTER SO LONG AS ABS(X-Y).GT.EPS   100   IF (ABS(X-Y).LE.EPS) GOTO 200             Y = X             X = (X + ZN/X) / 2   200   CONTINUE   C   THE SQUARE ROOT OF ZN IS NOW IN X

［译注：这是一段FORTRAN的程序，C代表注释行，保留不翻译。.LE.是"Less than or Equal to"（小于或等于）的缩写，.GT.是Greater than"大于"的意思。]

在传统型语言中，这个程序是不可分解的。我们将利用惰性求值将其化为更加模块化的形式，而后演示所生成部件的一些其他用途。

由于牛顿－拉夫森算法计算的是一个近似值的序列，故将它写作一个使用近似值列表的程序就再自然不过了。每个近似值都可以通过下面的函数从前一个值计算得到：

 next N x = (x + N/x) / 2

因此(next N)是从一个近似值映射到下一个值的函数。调用函数f，得到近似值序列：

[a0, f a0, f(f a0), f(f(f a0)), ...]

我们可以定义一个函数来计算：

repeat f a = cons a (repeat f (f a))

因此近似值序列可以这样计算：

repeat (next N) a0

repeat是一个具有"无穷"输出的函数的例子――但这没关系，因为超出程序其余部分需求的近似值并不会被计算。无穷性只是潜在的：它只说明，只要有需求，就可以计算出任意数量的近似值，repeat本身不会强加任何限制。

求根函数的剩余部分是函数within，它取一个允许误差与一个近似值列表作为参数，并在列表中查找差值不超过允许误差的一对相邻的近似值。这个函数可以定义为：

 within eps (cons a (cons b rest)) =               = b,                        当 abs(a-b) <= eps               = within eps (cons b rest), 否则

将这两个部件结合起来，

  sqrt a0 eps N = within eps (repeat (next N) a0)

现在我们得到了求根函数的两大部件，便可以尝试用不同的方式组合它们。将要进行的修改之一，是将判断条件改为"相邻近似值的比趋近1"而不是"差趋近0"。 这对于非常小的数字而言更加合适（当初始的相邻近似值之间的差值很小时），对非常大的数字也是如此（当舍尾产生的误差比允许误差大很多时）。我们只需要定 义一个函数来替换within：

  relative eps (cons a (cons b rest)) =               = b,                          当 abs(a-b) <= eps*abs b               = relative eps (cons b rest), 否则

而并不需要改写生成近似值的部件。

4.2 数值微分

我们已经重用了平方根近似值序列，当然，对函数within和relative的重用也是可能的，它们能够与任何一个生成近似值序列的数值算法配合。我们将这样来编写数值微分算法。

函数在某一点的微分，便是其图象在该点的斜率。通过分别计算函数在该点与一个临近点处的取值，而后计算两点连线斜率的方法，可以很容易地估计出微分的值。这基于一个假定：如果这两点靠得足够近，那么函数图象在两点之间不会弯曲得很厉害。于是有下述定义：

easydiff f x h = (f(x+h)-f x) / h

为了得到良好的近似值，h应该很小。不幸的是，如果h太小，那么f(x+h)与f(x)会相当接近，因此在相减过程中产生的舍尾误差可能会掩盖了计算结果。 如何为h选取恰当的值呢？解决这个矛盾一种方案是从一个合理的较大取值开始，不断减小h的值，并求出一个（微分的）近似值序列。这个序列将趋近于该点的导 数，但最终会由于舍尾误差的存在而不可救药地变得不精确。如果我们用(within eps)来选取第一个足够精确的近似值，那么舍尾误差影响结果的风险将会大大降低。我们需要一个函数来计算这个序列：

  differentiate h0 f x = map (easydiff f x) (repeat halve h0)   halve x = x/2

此处h0是h的初值，而后继取值是通过不断减半得到的。通过这个函数，任意点处的导数可以这样计算：

  within eps (differentiate h0 f x)

但是，甚至这个方案也不是那么令人满意的，因为近似值序列收敛得相当慢。解决这个问题需要一点数学知识，序列中的元素可以记为：

  （微分的）精确值 ＋ 一个关于h的误差项

理论表明，该误差项与h的某一次幂大致成正比，因此当h减小时，误差也会减小。设精确值为A，而误差项为B*h**n [me：**是求幂运算符］。由于计算每个近似值时所用的h取值是下一个的两倍，故任意两个连续的近似值可以表示成：

 a(i)   = A + B*(2**n)*(h**n)  a(i+1) = A + B*(h**n)

现在就可以消去误差项了，我们得到：

      a(i+1)*(2**n) - a(i)    A=----------------------            2**n - 1

当然，误差项只不过"大致"与h的某一次幂（成正比），因此这个结论也是近似的。但这是一个好得多的近似。这一改进可以通过下述函数作用于所有相邻的近似值对之上：

 elimerror n (cons a (cons b rest)) =               = cons ((b*(2**n)-a)/(2**n-1)) (elimerror n (cons b rest))

从一个近似值序列中消除误差项的操作产生了另一个收敛速度快得多的序列。

使用elimerror之前还有一个问题需要解决――我们必须知道n的正确值。通常这个值很难预测，但却很容易衡量。不难验证，下述函数能够正确地消除误差项，但在此我们并不给出证明。

  order (cons a (cons b (cons c rest))) =               = round(log2( (a-c)/(b-c) - 1 ))    round x = 最接近x的整数    log2 x  = x以2为底的对数

现在，一个通用的近似值序列优化函数可以定义为：

 improve s = elimerror (order s) s

使用improve能够更加高效地计算函数f的导数，如下：

  within eps (improve (differentiate h0 f x))

improve只对利用一个不断减半的参数h计算得到的近似值序列
适用。但是，如果improve作用于这样的序列，那么其结果也是一个这样的序列！这意味着一个近似值序列可以优化不止一次。每一次优化的过程中，都有一个不同的误差项被消除，因此优化产生的序列收敛得越来越快。因此，可以非常高效地计算导数：

within eps (improve (improve (improve (differentiate h0 f x)) 

从数值分析的角度讲，这似乎是一个"四阶方法"，可以迅速地给出准确的结果。甚至可以定义：

super s = map second (repeat improve s) second (cons a (cons b rest)) = b

super函数使用repeat improve来生成一个不断被优化的近似值的序列的序列。同时，super提取出每个近似值序列中的第二个元素，构造出一个新的序列（已经确认，第二元素是最佳选择――它比首元更精确，而且不需要额外的计算）。这个算法的确非常复杂――更多的近似值被计算的同时，它使用了不断优化的数值方法。可以用下面的程序非常非常高效地计算导数：

 within eps (super (differentiate h0 f x)) 

这个案例可能就像是用高射炮打蚊子，但关键是，甚至一个像super一样复杂的函数，当被惰性求值的方法模块化时，也会变得很容易表达。

4.3 数值积分

在这一部分我们将讨论的最后一个例子是数值积分。问题的描述很简单：给出一个返回实数并有一个实数参数的函数，以及两个端点a和b，估算两点之间f描述的曲线下方的面积。估算面积的最简单方法是假定f趋近于直线，此时面积就是：

 easyintegrate f a b = (f a + f b)*(b-a)/2

不幸的是，除非a与b足够接近，否则这个估算似乎非常不精确。更好的估算方法是，将a与b之间的区间分为两段，分别估算子区间上的面积，再将结果加起来。我们可以使用前面的公式进行第一次近似来定义一个不断趋近于准确值的积分近似值序列，后面的项是将前面项的各个部分再进行二分，并相加，来获得对不断趋近于积分的值。计算这个序列可以使用函数：

intergrate f a b = cons (easyintergrate f a b)                    (map addpair (zip (intergrate f a mid)                        (intergrate f mid b))) 其中 mid = (a+b)/2

Zip是另一个标准的列表处理函数。它读取两个列表，并返回一个有序对的列表，每个有序对由两个输入列表中对应的元素组成。所以第一对由列表一和列表二的首元组成，第二对由列表一和列表二的第二个元素组成，以此类推。Zip可以定义为：

 zip (cons a s) (cons b t) = cons (pair a b) (zip s t)

在函数intergrate中，zip用于生成由两个子区间上相对应的积分近似值对组成的列表，而map addpair用于将有序对中的元素相加，从而生成一个原积分的近似值列表。

实际上，这个版本的intergrate函数相当低效，因为它持续不断地重复计算f的值。就像所写的一样，easyintergrate计算了f在a和b两处的值，而对intergrate的递归调用将重复计算它们。同样的，(f mid)也在递归调用中重复计算了。因此，最好使用下述从不重复计算f的版本：

intergrate f a b = interg f a b (f a) (f b) integ f a b fa fb = cons ((fa+fb)*(b-a)/2)                          (map addpair (zip (interg f a m fa fm)                                            (interg f m b fm fb)))      其中 m = (a+b)/2            fm = f m

integrate给出了一个不断趋近准确值的积分近似值列表，正如differentiate在上一小节中所做的一样。因此可以写出计算式以求出所需任意精度的积分值，如下：

within eps (intergrate f a b) relative eps (integrate f a b)

这个积分算法与上一小节中的第一个微分算法有着同样的缺点――它收敛得相当慢。序列中的第一个近似值仅仅用了两个相距(a-b)的点来计算（通过easyintergrate）。第二个近似值也（除了a、b之外）用到了中点，因此相邻两点之间的间距仅为(b-a)/2。第三个近似值在两个子区间上 作同样的处理，因此间距仅为(b-a)/4。很清楚，每个近似值对应的相邻两点之间的间距在计算下一个值时被减半了。将这一间距看作"h"，那么这个序列 就可以成为上一小节中定义的"improve"函数的优化对象了。因此我们可以写出（函数来计算）快速收敛的积分近似值序列，例如：

super (intergrate sin 0 4)    improve (intergrate f 0 1) 其中 f x = 1/(1+x*x)

（后一个序列是用于计算pi/4的"第八阶方法"。其中的第二个近似值只需要计算5次f的取值，但却具有5位准确数字。）

在 本节中我们选取了一些数值算法并将它们函数化地编写出来，把惰性求值当做了黏合部件的黏合剂。由于惰性求值的存在，使得我们可以用很多新的方式来模块化这 些算法，从而产生用途广泛的函数，例如within，relative和improve。通过这些部件的不同组合，我们简单而明了地编写出了一些相当不错的数值算法。

5 人工智能中的例子

我们已经指出，函数式语言威力强大主要是因为它们提供了两种新的黏合剂：高阶函数和惰性求值。在本节中，我们将讨论人工智能中一个大一点的实例，并演示如何使用这两种黏合剂来十分简单地编写它。

我们选取的实例是alpha-beta"启发式搜索"，一个用于估计游戏者所处形势好坏的算法。该算法预测游戏局势的可能发展，但会避免对无意义局势的进一步探究。

令游戏局势使用"position"类型的对象来表示。这个类型依据游戏的不同而不同，我们不对此作任何假定。必然有一种方法可以知晓对某一个局势能够采取的行动：假定有一个函数：

moves: position -> listof position

该函数以一个游戏局势为参数，并返回一个可以由自变量出发，通过一步行动而形成的position的列表。以noughts and crosses游戏（tic-tac-toe）为例：

      | |      X| |   |X|   | |      -+-+-     -+-+- -+-+- -+-+- moves | |   = [ | | , | | , |X| ]      -+-+-     -+-+- -+-+- -+-+-       | |       | |   | |   | | 	         | |    O| |   |O|      -+-+-   -+-+- -+-+- moves |X| = [ |X| , |X| ]      -+-+-   -+-+- -+-+-       | |     | |   | | 

这个函数假定通过当前局势总是可以判定现在是哪位游戏者的回合。在noughts and crosses中，可以通过数出"0"与"X"的数目来做到这一点。在类似于象棋的游戏中，可能必须在"position"类型中显式包含这一信息。

利 用函数moves，第一步是构造一棵博弈树。这棵树的结点都用局势来标记，而一个结点的子结点用从该结点一步便可到达的局势标记。也就是说，如果一个结点 标记为局势p，那么它的子结点将使用(moves p)中的局势来标记。一棵博弈树完全有可能是无穷的，如果这个游戏可以在双方都不胜的情形下永远进行下去的话。博弈树与第2节中讨论的树完全类似――每个 结点都有一个标记（它所代表的局势）与一个子结点列表。因此我们可以使用相同的数据类型来表示它们。

博弈树是通过反复运用moves而构造出来的。构造从根局势开始，moves用于生成根结点处子树的标记，而后moves被用于生成子树的子树，依此类推。这一递归模式可以用一个高阶函数表示：

reptree f a = node a (map (reptree f) (f a))

使用这个函数可以定义另一个函数，该函数从一个特定的局势开始生成博弈树：

gametree p = reptree moves p

例如图1所示。此处使用的高阶函数(reptree）与上一节中用于构造无穷列表的函数repeat是类似的。

          | |          -+-+- gametree  | |          -+-+-           | |                             | |                            -+-+- =                           | |                            -+-+-                             | |                           /  |  \                          /   |   \                         /    |    \                        /     |     \                       /      |      \                      /       |       \                  X| |       |X|      | |                  -+-+-     -+-+-    -+-+-                   | |       | |      |X|                  -+-+-     -+-+-    -+-+-                   | |       | |      | |                   /|\       /|\       /\                   ...       ...      /  \                                     /    \                                    /      \                                O| |       |O|                                -+-+-     -+-+-                                 |X|       |X|                                -+-+-     -+-+-                                 | |       | |                                 /|\       /|\                                 ...       ... 

图1： 一棵博弈树的实例

alpha -beta算法从一个给定的局势出发，就游戏的发展将会是有利还是不利作出判断。然而，要做到这一点，它必须能够在不考虑下一步的情况下粗略地估计某一个 局势的"价值"。在后继局势不可预测时必须使用这一函数，它也可以用来对算法进行先期引导。静态估价的结果是从计算机的角度考虑的，是对该局势的前途的度 量（假设在游戏中计算机与人对抗）。结果越大，局势对计算机而言越好。结果越小，局势越糟。最简单的此类函数将会，比如说，对计算机确定胜利的局势返回+ 1，对计算机确定失败的局势返回-1，而对其它的局势返回0。在现实中，静态估价函数会衡量各种使局势"看上去不错"的因素。例如，具体的好处，以及象棋 中对中心的控制。假定有这样一个函数：

static: position -> number

既然一棵博弈树是一个(treeof position)，那么它就可以被函数(maptree static)转换为一个(treeof number)，该函数对树中所有的（也许是无穷多个）局势进行静态估价。此处使用了第2节中定义的函数maptree。

给 出一棵静态估价树之后，其中各个局势的真值究竟是多大？特别地，对根局势应该赋予什么值？不是它的静态值，因为那只是一个粗略的猜测。一个结点被赋予的 值，必须由其子结点的真值决定。这一过程的完成，基于每个游戏者都会选择对自己最有利的行动的假定。回忆一下，高值意味着计算机的有利形势。很明显，当计 算机从任意的局势开始下一步行动时，它将选择通往真值最高的子结点的行动。类似地，对手将会选择通往真值最低的子结点的行动。假定计算机与其对手轮流行 动，那么当轮到计算机行动时，节点的真值用函数maximise计算，反之用minimise计算。

maximise (node n sub) = max (map minimise sub) minimise (node n sub) = min (map maximise sub)

此处max和min是关于列表的函数，分别返回列表中元素的最大值与最小值。上述定义是不完整的，因为它们将永远递归下去――没有给出边界情形。我们必须定 义没有后继的结点的值（其标记）。因此静态估价用于任一游戏者胜利或者后继局势不可预测的情况下。maximise与minimise的完整定义是：

maximise (node n nil) = n maximise (node n sub) = max (map minimise sub) maximise (node n nil) = n maximise (node n sub) = min (map minimise sub)

在这个阶段，几乎已经可以写出一个取一个局势作为参数并返回其真值的函数了。可能是：

evaluate = maximise . maptree static . gametree

这个定义有两个问题。首先，它不适用于无穷树。maximise不断地递归直到找到一个没有子树的结点――树的端点。如果没有端点那么maximise就不会返回结果。第二个问题与第一个有关――甚至有穷的博弈树（如noughts and crosses里的那棵）事实上也可能相当大。估价整棵博弈树是不现实的――搜索必须被限定在接下去的几步之内。为此可以将树剪至一个固定的深度：

prune 0 (node a x) = node a nil prune n (node a x) = node a (map (prune (n-1)) x)

(prune n)取一棵树作为参数并"剪去"与根结点的距离超过n的所有结点。如果一棵博弈树被剪枝，那么将强制maximise对深度为n的结点执行静态估价而不是进一步递归。因此evaluate可以被定义为：

evaluate = maximise . maptree static . prune 5 . gametree

这将考虑其后（比如说）5步的形势。

在 此开发过程中我们已经使用了高阶函数与惰性求值。高阶函数reptree和maptree使得我们能够很容易地构造与处理博弈树。更重要的是，惰性求值确 保了我们可以使用这种方式模块化evaluate。由于博弈树具有潜在的无穷结果，在没有惰性求值的情况下，程序将永远不会终止。我们将不能写：

 prune 5 . gametree

而不得不将这两个函数整合成一个只构造树的前五层的函数。更糟糕的是，甚至那前五层都可能已经太大以至于无法在同一时间内存储于内存中。而在我们所写的程序中，函数

 maptree static . prune 5 . gametree

只是构造出了树中maximise所需的部分。由于每一部分都可以在被maximise处理完之后丢弃（被垃圾收集器回收），故完整的树从来没有存储于内存 中。只有树的一小部分在某一段时间内被储存着。因此这个惰性程序很有效率。这一效率取决于maximise（组合链上的最后一个函数）与gametree （第一个函数）的相互作用，因此在没有惰性求值的情况下，要完成任务，只能将组合链上的所有函数整合成一个大函数。这是对模块化的强烈破坏，但也是通常的 做法。通过单独修补每个部件，我们就可以优化估价算法――这相对简单。而一个传统型程序员必须把整个程序作为一个单元来修改，这就困难多了。

到目前为止，我们只是描述了简单的对最大最小值的处理（minimaxing）。但alpha-beta算法的核心是"计算maximise与minimise的值时常常不需要考虑整棵树"这一观察结果。考虑树：

       max        / \       /   \      /     \     /       \   min       min   / \       / \  /   \     /   \ 1     2   0     ?

相当奇怪地，为了估价这棵树，并不需要知道问号处的值。左子树的最小值是1，但右子树的最小值显然是一个小于或等于0的值。因此这两个最小值的最大值必然是1。这一观察结果可以被泛化并内建到maximise和minimise之中。

第一步是将maximise拆分成max对一个数字列表的作用。也就是，将maximise分解为：

  maximise = max . maximise'

（minimise可以用类似的方法分解。由于maximise和minimise是完全对称的，故我们将只讨论maximise，而假定minimise也照此处理。）一旦这样分解之后，maximise可以使用minimise'来发现minimise将对哪些数字求最小值，并且不再使用minimise本身。而后便可 以在不查看某些数字的情况下便将它们丢弃。由于惰性求值的存在，如果maxmise并不会查看所有的数字列表，那么一部分列表将不会被计算，这是对计算机 时间的潜在节约。

将max从maximise中"约分出来"是很简单的，得到：

maximise' (node n nil) = cons n nil maximise' (node n l) = map minimise l                      = map (min . minimise') l                      = map min (map minimise' l)                      = mapmin (map minimise' l) 其中 mapmin = map min

由于minimise' 返回一个数字列表，而这个列表的最小值是minimise的结果，故(map minimise' l)返回一个数字列表的列表。Maximise'应该返回这些列表中每个列表的最小值组成的列表，但只有这个列表中的最大值才有用。我们应该定义一个mapmin的新版本以忽略那些最小值不重要的列表。

  mapmin (cons nums rest) =                = cons (min nums) (omit (min nums) rest)

函数omit传递一个"潜在的最大值"――当前所发现的最小值中最大的一个――并忽略任何比该值小的最小值。

 omit pot nil = nil    omit pot (cons nums rest) =               = omit pot rest,                          当 minleq nums pot                = cons (min nums) (omit (min nums) rest), 否则

minleq 以一个数字列表和一个潜在最大值为参数，如果列表的最小值小于或等于潜在最大值就返回真。要完成这一工作，它并不需要扫描整个列表！如果列表中有任意一个 元素小于或等于潜在最大值，那么列表的最小值肯定也是如此。该特别元素之后的所有元素都是无关紧要的――它们就像是上面例子中的问号一样。因此 minleq可以被定义为：

  minleq nil pot = false   minleq (cons num rest) port = true,            当 num<=pot                               = minleq rest pot, 否则

如是定义了maximise'和minimise'之后，要写出一个新的估价函数就很简单了：

  evaluate = max . maximise' . maptree static . prune 8 . gametree

由于惰性求值的存在，使得maximise'只查看树的更小部分，这意味着整个程序会更加高效，正如prune只查看无穷树的一部分使得程序可以终止一样。对maxmise'的优化，尽管相当简单，却能对运算的速度产生戏剧性的效果。因此也使得估价函数可以看得更远。

对估价函数还可以进行其它优化。例如，刚刚描述的alpha-beta算法只有在最佳行动被最先考虑时才能够工作得最好，因为如果有一方发现了一着妙棋，那就没必要再考虑较差的行动了，除非他证明对手至少能有一种很好的回应方式。因此可能会希望对每一个结点的子树进行排序，当计算机行动时将最高值放在第一，而人行动时则相反。这可以使用函数：

highfirst (node n sub) = node n (sort higher (map lowfirst sub)) lowfirst (node n sub) = node n (sort (not.higher) (map highfirst sub)) higher (node n1 sub1)(node n2 sub2) = n1>n2

此处sort是多用途排序函数。现在估价函数定义为：

  evaluate = max . maximise' . highfirst . maptree static . prune 8 . gametree

也可能认为，为了限制搜索，只要考虑计算机或者对手的前三个最佳行动也已经足够了。要编写这样的程序，只需要把highfirst换成(taketree 3 . highfirst)，其中：

  taketree n = redtree (nodett n) cons nil   nodett n label sub = node label (take n sub)

taketree 将树上所有的结点替换为最多有n个子结点的结点，它使用了函数(take n)，而该函数返回列表的前n个元素（如果列表比n短，那么返回的元素就少一些）。

另一种优化是对剪枝的改良。上述程序甚至在局势非常机动的情形下也会向前搜索固定的深度――有时可以决定不再搜索，例如在国际象棋中皇后受到威胁的时候。通常可以定义某些"机动"的形势，并在遇到这样的结点之一时，不再继续搜索而停止。假定有函数"dyramic"用以确定这样的形势，那么只需要为prune追加一个定义等式：

prune 0 (node pos sub) = node pos (map (prune 0) sub), if dynamic pos

在像这个程序一样模块化的程序里，作出这样的改动是很简单的。如前所述，这个程序的效率，关键是由链中的最后一个函数maximise与第一个函数 gametree的相互作用决定的，因此若没有惰性求值，就只能写成一个单一的程序。这样的程序难于编写，难于修改，而且，非常难于理解。

6 结论

在本论文中，我们指出，模块化是成功的程序设计的关键。以提高生产力为目标的程序语言，必须良好地支持模块化程序设计。但是，新的作用域规则和分块编译的技 巧是不够的――"模块化"不仅仅意味着"模块"。我们分解程序的能力直接取决于将解决方案粘在一起的能力。为了协助模块化程序设计，程序语言必须提供优良 的黏合剂。函数式程序语言提供了两种新的黏合剂――高阶函数与惰性求值。利用这些黏合剂可以将程序用新的、令人激动的方式模块化，对此我们举出了很多实 例。越小、越通用的模块越可能被广泛地重用，使后续的程序设计工作变得简单。这解释了为什么函数式程序与传统型程序比较，要小得多，也容易编写得多。它也 为函数式程序员提供了一个追求目标。如果程序的任何部分是杂乱或者复杂的，那么程序员就应当尝试将其模块化并泛化其部件。他应当期望把高阶函数和惰性求值 用作他做此事的工具。

当然，我们并不是指出高阶函数与惰性求值的力与美的第一人。例如，Turner展示了这两者如何在一个生成化学结构 的程序里大显身手［Tur81］。Abelson和Sussman强调"流"（惰性列表）是构架程序的强大工具［AS86］。Henderson使用了流来构架函数式操作系统［P.H82］。本论文的主要贡献是，断言了模块化自身，便是函数式语言强大威力的关键。

这与当前有关惰性求值的论战也有关联。有些人认为函数式语言应当是惰性的，而其他人认为不是这样。有些人走折衷路线，只提供惰性列表以及用于构造它们的特殊语法（例如，在Scheme中［AS86］）。本论文提供了更进一步的证据，证明惰性求值非常重要以至于不能被降为二等公民。这也许是函数式程序员所拥有的最强大的黏合剂。人们不应当阻碍对这样一个极为重要的工具的使用。

致谢

在牛津程序设计研究组与Phil Wadler和Richard Bird的多次交谈对本论文的写作帮助甚大。约特堡查麦兹大学的Magnus Bondesson指出了一个数值算法的早期版本中的严重错误，同时也协助了很多其他算法的开发。本论文在英国科学与工程研究评议会提供的研究基金赞助下发表。

参考文献

[AS86] H. Abelson and G.J. Sussman. Structure and Interpretation of Computer Programs. MIT Press, Boston, 1986.
[Hug89] J. Hughes. Why Functional Programming Matters. Computer Journal, 32(2), 1989.
[Hug90] John Hughes. Why Functional Programming Matters. In D. Turner, editor, Research Topics in Functional Programming. Addison Wesley,
1990.
[MTH90] R. Milner, M. Tofte, and R. Harper. The Definition of Standard ML. MIT Press, 1990.
[oD80] United States Department of Defense. The Programming Language Ada Reference Manual. Springer-Verlag, 1980.
[P.H82] P.Henderson. Purely Functional Operating Systems. 1982.
[Tur81] D. A. Turner. The Semantic Elegance of Applicative Languages. In Proceedings 1981 Conference on Functional Languages and Computer
Architecture, Wentworth-by-the-Sea, Portsmouth, New Hampshire, 1981.
[Tur85] D. A. Turner. Miranda: A non-strict language with polymorphic types. In Proceedings 1985 Conference on Functional Programming
Languages and Computer Architecture, pages 1�C16, Nancy, France, 1985.
[Wir82] N. Wirth. Programming in Modula-II. Springer-Verlag, 1982.

--
----------------------------------

   你的支持 我的坚持
  Lead to The IT Future

----------------------------------

[Fwd]轻松实现可伸缩性，容错性，和负载平衡的大规模多人在线系统

作者：Joel Reymont
译文：神宗冥浩 ( chao.yan<at>imperial.ac.uk )
原地址：http://www.devmaster.net/articles/mmo-scalable-server/

！！转贴请注明出处！！

<译者序>:

本文是DevMaster.net上的一篇精华文章，也被很多相关E文论坛转载。翻译这篇文章基本是个冲动，因为我刚刚结束了这周的 programming test，一下子闲下来很是不适应。其实我们一直不明白，为什么学校除了C++一定要逼我们在其他"小语种"比如Haskell, Prolog 等等浪费那么多工夫。在最近阅读了一些journal，也学习过一下往届学生做的projects之后，我慢慢开始感谢学校了。

 

在读到本文之前，我刚好看完了水木里的一篇文章，内容是某位牛人对于网游开发的未来阶段展望云云。其理念确实发人深省，可是对于他后几阶段完全扎根于J2EE的论述就不敢苟同了。曾有文说：国人喜欢起哄。当某个事物突然吹起了风吹对了风，大家都一哄而上，没有条件创造条件也要上，遇到麻烦了，也得硬着头皮跟大家走下去。本文作者做了 9个月的前期research，在他的blog上也有详尽的关于 Erlang与Haskell, 与java之间在此领域的比较（注意是在多人在线服务端方面的比较！以免某些同胞没看清楚就炮轰我）或许你认为那个什么什么 Erlang纯粹rubbish，或许对其他问题有很大分歧，我不置可否。翻译本文的目的主要是因为原作者能够从多角度看待问题。对于优化方案的仔细充足的研究。

 

最近看了我们学校一组学生的group project，大体是用java编写的带 GUI的一个复杂智力游戏的AI solver。他们在项目前期最头疼的就是这个AI solver 的部分的实现。后来选择了使用Prolog(在逻辑编程方面有天生优势)编写AI 部分再用一个现成的plugin作为脚本嵌在java程序里。这样他们的进度大大加快了，有足够的时间制作精美的GUI 。甚至还作了一个java实现的AI部分用作比较，虽然Prolog 的代码是解释运行的，仍然比经典算法快了很多！文中的Erlang也是类似，只不过是在concurrency并行计算方面。

 

我现在是个刚考完试的大闲人，无聊简单翻译一下这篇文章，希望能有所用处。

简介： 

本文以我的 OpenPoker项目为例介绍另一种构建大规模多人在线系统的方案。OpenPoker 是一个大型多人扑克网游，内建支持了容错能力，负载平衡和无限制的规模大小。OpenPoker 的源代码遵循GPL协议可以从我的网站下载，大约包含一万行代码，有三分之一是用来测试的。  

在Openpoker 最终版出台之前，我花了很大精力设计参考，尝试过Delphi, Python, C#， C/C++还有Scheme。我甚至还用 Common Lisp完成了一个可运行的Poker引擎。虽然我花了 9个多月研究设计，最终代码编写却只用了6个星期，这最后的高效率要归功于选择了 Erlang作为编写平台。 

根据比较， 老版本的OpenPoker需要4 ～5个人的小组9 个月时间完成。原班人马还另外完成了一个Windows版的客户端，就算把这个开发时间的一半（ 1个半月）算进去，也比预期的18个月少得多，就当今游戏开发的客观环境，如此可观的时间节省不可小看！  

什么是Erlang  

我建议你先读一读 Erlang FAQ，不过我在这里尽量概括一下： 

Erlang是一个结构化，动态类型编程语言，内建并行计算支持。最初是由爱立信专门为通信应用设计的，比如控制交换机或者变换协议等，因此非常适合于构建分布式，实时软并行计算系统。  

使用Erlang 编写出的应用运行时通常由成千上万个轻量级进程组成，并通过消息传递相互通讯。进程间上下文切换对于Erlang来说仅仅只是一两个环节，比起 C程序的线程切换要高效得多得多了。 

使用Erlang 来编写分布式应用要简单的多，因为它的分布式机制是透明的：对于程序来说并不知道自己是在分布式运行。 

Erlang运行时环境是一个虚拟机，有点像 Java虚拟机，这样代码一经编译，同样可以随处运行。它的运行时系统甚至允许代码在不被中断的情况下更新。另外如果你需要更高效的话，字节代码也可以编译成本地代码运行。  

请参考 Erlang网站上的 教程、 文档、 范例等精彩资源。 

为什么选择 Erlang 

内建的并行计算模型使得Erlang 非常适合编写多人在线服务器。 

具有良好伸缩性的大型多人后台系统用Erlang 是这样构建的：由很多被分配不同任务的"节点 (Node)"组成的 "集群(Cluster)"。一个 Erlang节点就是一个Erlang虚拟机的实例，你可以在一台机器 (服务器，台式机或者笔记本电脑)上运行多个节点。我推荐一块 CPU一个节点。 

Erlang节点自动跟踪所有连接着的其他节点。要添加一个节点你仅仅需要把它指向任何一个已建节点就可以了。只要这两个节点建立了连接，所有其他的节点马上就会感应到新加入的节点。  

Erlang进程使用进程 ID向其他进程传递报文，进程ID包含着运行此进程的节点的信息。因此进程不需要理会正在与其交流的其他进程实际在何处运行。一组相互连接的 Erlang节点可以看作是一个网格计算体或者一台超级计算机。 

将大型多人在线游戏里的玩家，NPC 以及其他个体抽象为很多并行运行的进程是最理想的，但是通常并行运算的实现让人十分头疼。Erlang天生就是简化并行计算的实现。  

Erlang语法里的比特操作让二进制操作变得异常简单，极大发挥了 Perl和Python 的打包/解包结构。使得Erlang 非常适合操作二进制网络通讯协议。 

<!--[if !supportLineBreakNewLine]-->
<!--[endif]--> 

OpenPoker的体系结构  

OpenPoker里的一切的一切都是进程。玩家，机器人，游戏，抬面等等等等，都是一个个进程。每一个连接到 OpenPoker的客户端都有一个扮演 "代理"角色的玩家进程用来处理网络消息。取决于玩家是否登陆，某些消息被忽略而有些被传递到处理游戏逻辑的进程。  

纸牌游戏进程是一个状态机宿主：由多种游戏状态的各种状态机模块组成。这样我的纸牌游戏进程可以向乐高积木一样随意添砖加瓦 ――只要加入状态机就可以添加新的纸牌游戏。此方案可以参考我写的初始函数(在 cardgame.erl里) 

纸牌游戏状态机根据目前游戏的状态接受不同的消息。而且我用一个独立的进城来处理通用信息，比如跟踪玩家状态，抬面情况，各种限制等等。在我的笔记本电脑上模拟 27，000个扑克游戏，会产生 136,000个玩家和大约800， 000个进程。 

这说明了为什么我极力专注于使用OpenPoker 为例讨论Erlang如何轻松的实现可伸缩性，容错性，和负载平衡。此方案不仅仅局限于扑克纸牌游戏。相同的机制完全可以胜任其他类型大规模可伸缩多人在线后台系统，便宜简单一点儿也不郁闷！  

<!--[if !supportLineBreakNewLine]-->
<!--[endif]--> 

可伸缩性 

我使用多层体系实现高伸缩性和负载平衡。第一层是网关节点。第二层是游戏服务端节点，最后一层是 Mnesia主节点。 

Mnesia是 Erlang的实时分布式数据库系统。Mnesia FAQ 解释得很详细，它是一个高速，重复性，内存驻留的数据库。Erlang本身没有对象支持但是 Mnesia可以被看作是面向对象的因为它存贮所有Erlang数据。  

有两种Mnesia 节点：访问磁盘的和不访问磁盘的。无论怎样，所有Mnesia节点在内存中存储数据。 OpenPoker里的Mnesia节点是用来访问磁盘的。网关和游戏服务层只操作内存，启动后从 Mnesia访问数据库。 

Erlang虚拟机有一套很方便的命令行参数来通知 Mnesia主数据库存在哪里。任何新的Mnesia 节点只要和主节点建立了连接，新的节点马上成为集群的一部分。 

假设主节点位于apple 和orange两台主机上，那么添加新的网关节点，游戏服务节点等等到你的 OpenPoker集群仅仅需要如下命令行启动： 

erl -mnesia extra_db_nodes \[' db@apple','db@orange'\] -s mnesia start

-s mnesia start 也可以用Erlang控制台启动 Mnesia:

erl -mnesia extra_db_nodes \['db@apple','db@orange'\]
Erlang (BEAM) emulator version 5.4.8 [source] [hipe] [threads:0] 

Eshell V5.4.8  (abort with ^G)
1> mnesia:start().
ok

OpenPoker在 Mnesia数据表里保存配置信息，此信息在Mnesia启动的时候自动被新节点下载。完全零配置！

 

容错性 

添置几个便宜的Linux 系统到我的服务器组，OpenPoker可以要多大规模有多大规模。组合一打 1U服务器系统可以轻松胜任五十万甚至一百万玩家同时在线。当然不仅仅是纸牌游戏，对于其他多人RPG 网游( MMORPG)也是一样的。 

我可以指派几个服务器做网关节点，另外几个做数据库节点访问存储介质上的数据，然后剩下的一些做游戏服务器。我还可以限制单台服务器最高接纳 5000玩家同时在线，所以任何一台当机，最多5000 个玩家受影响。 

另外要指出的是任何一台游戏服务器当机都不会有数据损毁因为所有 Mnesia的数据访问操作都是由多个游戏，Mnesia节点实时备份的。  

考虑到某些潜在错误，游戏客户端需要做一些辅助工作让玩家顺滑的重新连接到 OpenPoker服务器集群。每当客户端发现网络错误，就会尝试连接网关节点，通过接力网络包得到一个新的游戏服务节点地址然后重新连接。这里需要点技巧因为不同的情况要不同对待： 

OpenPoker划分如下需要重新连接的情况：  

1. 游戏服务器当机 
2. 客户端当机或者网络延迟超时 
3. 玩家尝试从另外一个网络连接上线 
4. 玩家在游戏中切换到另一个网络继续连接  

最常见的就是客户端因为网络错误而断开连接。最不常见但是还是有可能的是同一个客户端在游戏中的时候从另一个电脑尝试连接。  

每个OpenPoker 游戏缓存发送给玩家的数据包，每次客户端重新连接都会收到自游戏开始的所有数据包然后再开始正常接受。OpenPoker使用 TCP连接所以不用考虑数据包的发送顺序――所有数据包保证是按顺序收到的。  

每个客户端连接由两个OpenPoker 进程组成：套接字进程还有玩家进程。还有一个受限制的访客进程被使用直至玩家成功登陆，访客不能加入游戏。套接字进程虽网络中断而停止，但是玩家进程仍然保持活动。 

玩家进程发送游戏数据包的时候可以侦测到已经中断的套接字进程，此时会进入自动运行状态或者暂停状态。登陆代码会在重新连接的时候同时参考套接字进程和玩家进程。用来侦测的代码如下：

login({atomic, [Player]}, [_Nick, Pass|_] = Args) 
  when is_record(Player, player) ->
	Player1 = Player#player {
		socket = fix_pid(Player#player.socket),
		pid = fix_pid(Player#player.pid) 
	       },
	Condition = check_player(Player1, [Pass], 
			     [
			      fun is_account_disabled/2,
			      fun is_bad_password/2,
			      fun is_player_busy/2,
			      fun is_player_online/2,
 			      fun is_client_down/2,
			      fun is_offline/2
			     ]),
	...	

其中的各个条件是这么写的：

 

 

 

 

 

is_player_busy(Player, _) ->
	{Online, _} = is_player_online(Player, []),
	Playing = Player#player.game /= none,
	{Online and Playing, player_busy}.

is_player_online(Player, _) -> 
	SocketAlive = Player#player.socket /= none,
	PlayerAlive = Player#player.pid /= none,
	{SocketAlive and PlayerAlive, player_online}.

is_client_down(Player, _) ->
	SocketDown = Player#player.socket == none, 
	PlayerAlive = Player#player.pid /= none,
	{SocketDown and PlayerAlive, client_down}.

is_offline(Player, _) ->
	SocketDown = Player#player.socket == none,
	PlayerDown = Player#player.pid == none,
 	{SocketDown and PlayerDown, player_offline}.

 

要注意login 函数首先要做的是修复已失败的进程ID。这样简化了处理过程，代码如下：  

fix_pid(Pid)
  when is_pid(Pid) ->
	case util:is_process_alive(Pid) of
	true ->
	    Pid;
	_ ->
	    none
	end;

fix_pid(Pid) ->
	Pid. 

和:

 

 

 

 

 

-module(util).

-export([is_process_alive/1]).

is_process_alive(Pid) 
  when is_pid(Pid) ->
	rpc:call(node(Pid), erlang, is_process_alive, [Pid]). 

 

Erlang里的进程 ID包含运行进程的节点的Id. is_pid(Pid)返回参数是否为一个进程 Id但是无法知道进程是否已中断。Erlang 的内建函数erlang:is_process_alive(Pid)可以做到。 is_process_alive也可以用来检查远程节点，用起来是没区别的。 

更方便的是，我们可以用 Erlang RPC功能，联合node(pid)来调用远程节点的 is_process_alive()。用起来和访问本地节点一样，所以上面的代码实际上也是全局分布式进程检查。  

最后剩的工作就是处理登陆的各种情况了。最直接的情况是玩家处于离线状态然后启动了一个玩家进程，连接玩家进程到套接字进程，然后更新玩家数据。  

login(Player, player_offline, [Nick, _, Socket]) ->
	{ok, Pid} = player:start(Nick),
	OID = gen_server:call(Pid, 'ID'),
	gen_server:cast(Pid, {'SOCKET', Socket}), 
	Player1 = Player#player {
		oid = OID,
		pid = Pid,
		socket = Socket
	       },
	{Player1, {ok, Pid}}.
 

如果登陆信息不正确就返回错误然后记录登陆尝试次数。如果尝试超过一定次数，可以用如下代码关闭账户：

 

 

 

 

 

login(Player, bad_password, _) ->
	N = Player#player.login_errors + 1,
	{atomic, MaxLoginErrors} = 
	db:get(cluster_config, 0, max_login_errors),
	if
	N > MaxLoginErrors -> 
	    Player1 = Player#player {
			disabled = true
		       },
	    {Player1, {error, ?ERR_ACCOUNT_DISABLED}};
	true ->
	    Player1 = Player#player {
			login_errors = N
		       },
	    {Player1, {error, ?ERR_BAD_LOGIN}} 
	end;

login(Player, account_disabled, _) ->
	{Player, {error, ?ERR_ACCOUNT_DISABLED}};

注销用户时，先用ObjectID 找到玩家进程ID，然后停止玩家进程并更新数据库记录：

 

 

 

 

 

logout(OID) ->
	case db:find(player, OID) of
	{atomic, [Player]} ->
	    player:stop(Player#player.pid),
	    {atomic, ok} = db:set(player, OID, 
				  [{pid, none}, 
				   {socket, none}]);
	_ ->
	    oops
	end.

如果注销不正常，可以分别针对各种重新连接条件处理。如果玩家在线却处于闲置状态，比如说停在大厅或者正旁观一个游戏 (可能在喝着瓶百威，喂喂！)，然后尝试从另一台电脑连接，那么程序先将其登出然后重新将其登入，就像从离线状态下登入一样：

 

 

 

 

 

login(Player, player_online, Args) ->
	logout(Player#player.oid),
	login(Player, player_offline, Args);

如果玩家正在闲置而客户端断开连接了，那么只需要在记录里替换他的套接字进程地址然后通知玩家进程新的套接字：

 

 

 

 

 

login(Player, client_down, [_, _, Socket]) ->
	gen_server:cast(Player#player.pid, {'SOCKET', Socket}),
	Player1 = Player#player {
		socket = Socket
	       }, 
	{Player1, {ok, Player#player.pid}};

如果玩家在游戏中，那么除了运行上面那段以外，通知游戏重新发送过往事件。

 

 

 

 

 

login(Player, player_busy, Args) ->
	Temp = login(Player, client_down, Args),
	cardgame:cast(Player#player.game, 
		  {'RESEND UPDATES', Player#player.pid}),
 	Temp;

 

总而言之，包含着实时冗余数据库，智能重连的客户端，还有一些精巧的登陆代码的这一套组合方案可以提供高度的容错性，而且对于玩家来说，是透明的。  

负载平衡  

我可以用想多少就多少的服务器节点组建我的OpenPoker 集群。也可以自由调配，比如说每个服务器节点5000个玩家，然后在整个集群中平摊工作负载。我可以在任何时候添加新的服务器节点，新节点自己会自动配置并开始接受新玩家。  

网关节点控制着向OpenPoker 集群里的所有活动节点平衡负载。网关节点的作用就是随机选择一个服务器节点，查询已连接玩家数，主机地址，端口等等。只要网关节点找到一个游戏服务器未达到负载最大值，它就把服务器的地址信息传递给客户端然后关闭连接。 

很明显网关节点工作量不大，而且指向这个节点的连接都是瞬时的。你可以随便用个便宜机器做你的网关节点。  

节点一般应该是一对一对的，这样如果一个失败，另一个可以马上替补。你可以采用 Round-robin DNS来配置多个网关节点。 

那么网关如何找到游戏服务器呢？ 

OpenPoker采用 Erlang的分布式进程组( Distributed Named Process Groups)来分组游戏服务器。所有节点都可以访问组列表，这一过程是自动的。新的游戏服务器只需加入服务器组。某个节点当机自动从组列表里剔除。  

查找服务玩家最少的服务器的代码如下： 

find_server(MaxPlayers) ->
	case pg2:get_closest_pid(?GAME_SERVERS) of 
	Pid when is_pid(Pid) ->
	    {Time, {Host, Port}} = timer:tc(gen_server, call, [Pid, 'WHERE']), 
	    Count = gen_server:call(Pid, 'USER COUNT'),
	    if
		Count < MaxPlayers ->
		    io:format("~s:~w: ~w players~n", [Host, Port, Count]),
		    {Host, Port};
		true ->
 		    io:format("~s:~w is full...~n", [Host, Port]),
		    find_server(MaxPlayers)
	    end;
	Any ->
	    Any
	end.

pg2:get_closest_pid() 返回一个随机的游戏服务器进程ID（网关节点上不运行任何游戏服务器）。然后向返回的服务器查询地址端口以及目前连接的玩家数。只要未足最大负载额就把地址返回给调用进程，否则继续查找。  

多功能插座中间件  

OpenPoker是一个开源软件，我最近也正在将其投向许多棋牌类运营商。所有商家都存在容错性和可伸缩性的问题，即使有些已经经过了长年的开发维护。有些已经重写了代码，而有些才刚刚起步。所有商家都在 Java体系上大笔投入，所以他们不愿意换到Erlang 也是可以理解的。 

但是，对我来说这是一种商机。我越是深入研究，越发现Erlang 更适合提供一个简单直接却又高效可靠的解决方案。我把这个解决方案看成一个多功能插座，就像你现在电源插头上连着的一样。 

你的游戏服务器可以像简单的单一套接字服务器一样的写，只用一个数据库后台。实际上，可能比你现在的游戏服务器写得还要简单。你的游戏服务器就好比一个电源插头，多种电源插头接在我的插线板上，而玩家就从另一端流入。  

你提供游戏服务，而我提供可伸缩性，负载平衡，还有容错性。我保持玩家连到插线板上并监视你的游戏服务器们，在需要的时候重启任何一个。我还可以在某个服务器当掉的情况下把玩家从一个服务器切换到另一个，而你可以随时插入新的服务器。  

这么一个多功能插线板中间件就像一个黑匣子设置在玩家与服务器之间，而且你的游戏代码不需要做出任何修改。你可以享用这个方案带来的高伸缩性，负载平衡，可容错性等好处，与此同时节约投资并写仅仅修改一小部分体系结构。  

你可以今天就开始写这个Erlang 的中间件，在一个特别为TCP连接数做了优化的Linux 机器上运行，把这台机器放到公众网上的同时保持你的游戏服务器群组在防火墙背后。就算你不打算用，我也建议你抽空看看Erlang 考虑一下如何简化你的多人在线服务器架构。而且我随时愿意帮忙！ 

Ende  

--
----------------------------------

   你的支持 我的坚持
  Lead to The IT Future

----------------------------------

[FW]Writing Low-Pain Massively Scalable Multiplayer Servers

Writing Low-Pain Massively Scalable Multiplayer Servers



Creating massive multiplayer game servers with fault-tolerance, load balancing and unlimited scalability all built-in

Joel Reymont

07/10/2005


Introduction

This article describes an alternative approach to building massively scalable online multiplayer systems using my OpenPoker project as an example. OpenPoker is a massively multiplayer poker server with fault-tolerance, load balancing and unlimited scalability built-in. The source code to OpenPoker is available from my site under the GPL and comes in under 10,000 lines of code of which about 1/3 are dedicated to testing.

I prototyped extensively before coming up with the final version of OpenPoker and tried Delphi, Python, C#, C/C++ and Scheme. I also wrote a full-blown poker engine in Common Lisp. While I did spend over 9 months on research and prototyping, the final rewrite only took about 6 weeks of coding. I attribute most of the time and cost savings to choosing Erlang as my platform.

By comparison, it took a team of 4-5 people about 9 months to build the old OpenPoker. The original team also built a Windows poker client but even if I cut development time in half to account for this 1.5 month, it is far from 18 months that I will end up with. In today's world of bloated game development budgets such savings are nothing to sneeze at!

What is Erlang

I suggest you browse through the Erlang FAQ before continuing but I'll give you a quick summary here...

Erlang is a functional, dynamically typed language with built-in support for concurrency. It was specifically designed by Ericsson for telecommunications applications such as controlling a switch or converting protocols, and thus is particularly suitable for building distributed, soft real-time concurrent systems.

Applications written in Erlang are often composed of hundreds or thousands of lightweight processes communicating via message passing. Context switching between Erlang processes is typically one or two orders of magnitude cheaper than switching between threads in a C program.

It's easy to write distributed applications in Erlang because its distribution mechanisms are transparent: programs need not be aware that they are distributed.

The Erlang runtime environment is a virtual machine (VM), much like the Java virtual machine. This means that code compiled on one architecture runs anywhere. The runtime system also allows code in a running system to be updated without interrupting the program and the byte code can be compiled to native code when you need that extra boost.

Please head to the Erlang site and check out the excellent resources in the Getting started, Documentation and Examples sections.
Why Erlang

The concurrency model built into Erlang makes it particularly suitable for writing online multiplayer servers.

A massively scalable multiplayer backend in Erlang is built as a "cluster" with different "nodes" dedicated to different tasks. An Erlang node is an instance of the Erlang VM and you can run multiple Erlang nodes/VMs on your desktop, laptop or server. One node per CPU is recommended.

Erlang nodes track all other nodes connected to them. All you need to do to add a new node to the cluster is point it to an existing node. As soon as the two nodes establish contact all other nodes in the cluster become aware of the new node.

Erlang processes send messages to other processes using a process id which encodes information about the node where the process is running. Processes need not be aware of where other processes are located to communicate with them. A bunch of Erlang nodes linked together can be viewed as a grid or supercomputing facility.

Players, NPCs and other entities in massively multiplayer games are best modelled as concurrently running processes but concurrency is notoriously hard to work with. Erlang makes concurrency easy.

Erlang's bit syntax∞ makes it trivial to work with binary data and bests the structure packing/unpacking facilities of Perl and Python. This makes Erlang particularly suitable for handling binary network protocols.
The OpenPoker architecture

Everything in OpenPoker is a process. Players, bots, games, pots, etc. are all processes. For every poker client connected to OpenPoker there's a player "proxy" handling network messages. Depending on whether the player is logged in, some messages are ignored while others are passed to the process handling card game logic.

The card game process is an uber-state machine composed of state machine modules for every stage of the game. This lets me treat card game logic as a Lego constructor and add new card games by putting together the state machine building blocks. Take a look at the start function in cardgame.erl if you want to learn more about my approach.

The card game state machine lets different messages through depending on the game stage. It also uses a separate game process to handle the machinery common to all games such as keeping track of players, pots, limits and so on. When simulating 27,000 poker games on my laptop I found that I had about 136,000 players and close to 800,000 processes in total.

That said, I would like to focus on how Erlang makes it simple to implement scalability, fault tolerance and load balancing using OpenPoker as an example. My approach is not particular to poker or card games. The same approach can be used to quickly put together massively scalable multiplayer backends, do it cheaply and with a minimum amount of pain.
Scalability

I implement scalability and load-balancing by means of a multi-tier architecture. The first tier is represented by gateway nodes. Game server nodes form tier two and Mnesia "master" nodes can be thought of as the third tier.

Mnesia is the Erlang real-time distributed database. The Mnesia FAQ has a good explanation but Mnesia is basically a fast, replicating, in-memory database. There are no objects in Erlang but Mnesia can be thought of as object-oriented as it can store any Erlang data.

There are two types of Mnesia nodes: those that write to disk and those that do not. Regardless of this, all Mnesia nodes keep their data in memory. Mnesia master nodes in OpenPoker are nodes that write to disk. Gateways and game servers pick up their database from Mnesia masters upon startup and are memory-only nodes.

There's a handy set of command-line arguments that you can give to the Erlang VM and interpreter when starting up to tell Mnesia where the master database is located. After the new local Mnesia node establishes contact with the master Mnesia node, the new node becomes part of the master node's cluster.

Assuming that the master nodes are located on hosts apple and orange, adding a new gateway, game server, etc. node to your OpenPoker cluster is as simple as

erl -mnesia extra_db_nodes \[' db@apple','db@orange'\] -s mnesia start

where

-s mnesia start

is equivalent to starting Mnesia from the erlang shell like this

erl -mnesia extra_db_nodes \['db@apple','db@orange'\]
Erlang (BEAM) emulator version 5.4.8 [source] [hipe] [threads:0]

Eshell V5.4.8 (abort with ^G)
1> mnesia:start().
ok

OpenPoker keeps configuration information in Mnesia tables and this information is automatically downloaded by new nodes as soon as Mnesia starts. Zero configuration required!
Fault tolerance
OpenPoker lets me grow as high as I want by adding cheap Linux boxes to my server farm. Put together a couple of racks of 1U servers and you can easily handle 500,000 or even 1,000,000 players online. This would work just as well for a MMORPG as for poker.

I can dedicate some boxes to run gateway nodes and some to be database masters that write database transactions to disk. I can dedicate the rest of my boxes to run my game servers. I can limit game servers to accept a maximum of, say, 5000 simultaneous players so that no more than 5000 players are affected when my game server box crashes.

It's important to note that no information is lost when a game server crashes since all the Mnesia database transactions are replicated in real-time to all other nodes running Mnesia, game server nodes included.

In case of errors some assistance from the game client is required for the player to smoothly reconnect to the OpenPoker cluster. As soon as the poker client notices a network error it should connect to the gateway, receive a new game server address in a hand-off packet and reconnect to the new game server. What happens then is a little tricky as different types of reconnect scenarios need to be handled.

OpenPoker will handle the following reconnect scenarios:

1. The game server crashed
   
2. The client crashed or timed out due to a network error
   
3. The player is online on a different connection
   
4. The player is online on a different connection and is in a game
   

The most common scenario will probably be a poker client that disconnected due to a network error. A less likely but still possible scenario is a client reconnecting from one computer while already playing at another.

Each OpenPoker game buffers packets sent to players and every reconnecting poker client will first receive all the game packets since the game started before starting to receiving packets as usual. OpenPoker uses TCP connections so I don't need to worry about packet ordering -- packets will simply arrive in proper order.

Every poker client connection is represented by two OpenPoker processes: the socket process and the actual player process. A visitor process with restricted functionality is used until the player logs in. Visitors cannot join games, for example. The socket process will be dead after a poker client disconnects while the player process will still be alive.

A player process can notice a dead socket when attempting to forward a game packet and should put itself into auto-play mode or fold the hand. The login code will check for the combination of a dead socket and live player process when reconnecting. The code to determine the condition looks like this:

login({atomic, [Player]}, [_Nick, Pass|_] = Args)

when is_record(Player, player) ->

Player1 = Player#player {
socket = fix_pid(Player#player.socket),
pid = fix_pid(Player#player.pid)

},
Condition = check_player(Player1, [Pass],
[

fun is_account_disabled/2,
fun is_bad_password/2,
fun is_player_busy/2,
fun is_player_online/2,
fun is_client_down/2,
fun is_offline/2

]),

...

whereas the conditions themselves will be determined by the following code:

is_player_busy(Player, _) ->

{Online, _} = is_player_online(Player, []),
Playing = Player#player.game /= none,
{Online and Playing, player_busy}.

is_player_online(Player, _) ->

SocketAlive = Player#player.socket /= none,
PlayerAlive = Player#player.pid /= none,
{SocketAlive and PlayerAlive, player_online}.

is_client_down(Player, _) ->

SocketDown = Player#player.socket == none,
PlayerAlive = Player#player.pid /= none,
{SocketDown and PlayerAlive, client_down}.

is_offline(Player, _) ->

SocketDown = Player#player.socket == none,
PlayerDown = Player#player.pid == none,
{SocketDown and PlayerDown, player_offline}.

Notice that the first thing the login function does is to fix up dead process ids. This makes processing simple down the road and is accomplished with the following bits of code:

fix_pid(Pid)

when is_pid(Pid) ->

case util:is_process_alive(Pid) of
true ->
Pid;
_ ->
none
end;

fix_pid(Pid) ->
Pid.

and

-module(util).

-export([is_process_alive/1]).

is_process_alive(Pid)

when is_pid(Pid) ->
rpc:call(node(Pid), erlang, is_process_alive, [Pid]).

A process id in Erlang includes the id of the node where the process is running. is_pid(Pid) tells me if its argument is a process id (pid) but cannot tell me if the process is alive or dead. Erlang's built-in erlang:is_process_alive(Pid) tells me whether a local process (running on the same node) is dead or alive. There's no variant of is_process_alive for checking remote nodes.

Fortunately, I can use the Erlang rpc facility together with node(pid) to call is_process_alive() on the remote node. In fact, this will work just as well on the local node so the code above functions as a universal distributed process checker.

All that is left to do is to act on the various login conditions. In the simplest case where the player is offline I start a player process, connect the player to the socket and update the player record.

login(Player, player_offline, [Nick, _, Socket]) ->

{ok, Pid} = player:start(Nick),
OID = gen_server:call(Pid, 'ID'),
gen_server:cast(Pid, {'SOCKET', Socket}),
Player1 = Player#player {
oid = OID,
pid = Pid,
socket = Socket
},
{Player1, {ok, Pid}}.

Should the player login information not match I can return an error and increase the number of bad login attempts. If this number exceeds a predefined maximum I disable the account like this:

login(Player, bad_password, _) ->
N = Player#player.login_errors + 1,
{atomic, MaxLoginErrors} =
db:get(cluster_config, 0, max_login_errors),
if
N > MaxLoginErrors ->
Player1 = Player#player {
disabled = true
},
{Player1, {error, ?ERR_ACCOUNT_DISABLED}};
true ->
Player1 = Player#player {
login_errors = N
},
{Player1, {error, ?ERR_BAD_LOGIN}}
end;

login(Player, account_disabled, _) ->
{Player, {error, ?ERR_ACCOUNT_DISABLED}};

Logging out the player involves finding the player process id using their Object ID (which is just a number), stopping the player process and updating the player record in the database. This is accomplished by the following bit of code:

logout(OID) ->

case db:find(player, OID) of
{atomic, [Player]} ->
player:stop(Player#player.pid),
{atomic, ok} = db:set(player, OID,
[{pid, none},
{socket, none}]);
_ ->
oops
end.

With logout out of the way I can address the various reconnect conditions. If the player is online but idle, i.e. hanging out in the lobby or watching a game (drinking a Bud? Wazzup!) and is reconnecting from a different computer, I can just log them out and log them back in as if they were offline:
login(Player, player_online, Args) ->
logout(Player#player.oid),
login(Player, player_offline, Args);

If the player was idle when their poker client disconnected then all I need to do is replace the socket process id in the player record and tell the player process about the new socket.

login(Player, client_down, [_, _, Socket]) ->
gen_server:cast(Player#player.pid, {'SOCKET', Socket}),
Player1 = Player#player {
socket = Socket
},
{Player1, {ok, Player#player.pid}};

If the player was in a game then we run the code above and tell the game to resend the event history.

login(Player, player_busy, Args) ->
Temp = login(Player, client_down, Args),
cardgame:cast(Player#player.game,
{'RESEND UPDATES', Player#player.pid}),
Temp;

Overall, a combination of a real-time replicating database, a poker client that knows to reconnect to a different game server and some crafty login code allows me to provide a high degree of fault tolerance transparently to the player.
Load balancing

I can build my OpenPoker cluster from as many game server nodes as I want . I might want to allocate, say, 5000 players per game server and spread the load among the active game servers in my cluster. I can add new game servers at any time and they will automatically make themselves available to accept new players.

Gateway nodes spread the player load among the active game servers in the OpenPoker cluster. The job of a gateway node is to pick a random game server, ask it for the number of players connected and its address, host and port number where the game server is running. As soon as the gateway finds a game server where the number of players connected is less than the preset maximum it will return the address of that game server to the connected poker client and close the connection.

There's absolutely no load on gateway nodes and connections to them are extremely short-lived. You can have any cheap box acting as your gateway node.

Nodes should generally come at least in pairs so that if one node fails another one can take over. You would need a mechanism like Round-robin DNS to employ more than a single gateway node.

How do gateways learn about game servers?

OpenPoker uses the Erlang Distributed Named Process Groups facility to group game servers. The group is globally visible on all nodes, this happens automatically. New game servers join the game server group and when a game server node goes down it's automatically deleted.

This is what the code to find a game server with a maximum capacity of MaxPlayers looks like:

find_server(MaxPlayers) ->
case pg2:get_closest_pid(?GAME_SERVERS) of
Pid when is_pid(Pid) ->

{Time, {Host, Port}} = timer:tc(gen_server, call, [Pid, 'WHERE']),
Count = gen_server:call(Pid, 'USER COUNT'),
if
Count < MaxPlayers ->
io:format("~s:~w: ~w players~n", [Host, Port, Count]),
{Host, Port};
true ->
io:format("~s:~w is full...~n", [Host, Port]),
find_server(MaxPlayers)
end;
Any ->
Any
end.

pg2:get_closest_pid() returns a random game server process id since a gateway node is not expected to run any game servers. If a process id of the game server is returned I ask the game server for its address (host and port) as well the number of players connected. So long as the number of players connected is less than the maximum I return the game server address to the caller, otherwise I keep looking.
Multiple-outlet powerstrip middleware

OpenPoker is open source software and I have been pitching it to various poker vendors recently. All the vendors have the same problem with scalability and fault tolerance, even after several years of development. Some have recently finished major rewrites of their server software while others are just embarking on this journey. All of the vendors are heavily invested in their Java infrastructure and, understandably, do not want to switch to Erlang.

Still, it sounds to me like there is a need to be filled. The more I think about it the more it looks like Erlang can still be used to provide a cost-efficient solution while keeping things simple and straightforward. I see this solution as a multiple-outlet electrical power strip, just like the one you are probably using right now.

You write your game server as a simple socket-based server that uses a database backend. In fact, more likely than not this is how your game server is written now. Your game server is the standard electrical plug and multiple instances of your game server are plugged into my power outlets while players flow in through the other end.

You supply the game servers and I provide you with scalability, load balancing, and fault tolerance. I keep players connected to the power strip and monitor your game servers, restarting them as needed. I switch your players to another game server when one goes down and you can plug in as many game servers as you like into my power outlets.

The power strip middleware is a black box sitting between your players and your servers and likely won't even require any changes to your code. You will get all the benefits of a highly scalable, load-balanced, fault-tolerant solution while keeping your investment and modifying little of your existing infrastructure.

You can write this middleware in Erlang today, run it on a Linux box with a kernel specially tuned for a high number of TCP connections and put this box in a demilitarized zone while keeping your game servers behind a firewall. Even if you don't, I suggest that you take a close look at Erlang today and think about using it to simplify your massively multiplayer server architectures. And I will be here to help!


--