« August 2007 | Main | October 2007 »

September 30, 2007

洗牌

今天从 svn 中取下一个同事的代码,浏览了一下。其中一段是关于洗牌的。感觉实现的很乱,算法也没有选好。自己重新写了一个。

因为国庆的缘故,负责这块代码的同事提前回家了。我只好自己读代码实现。看完后,发现旧的实现是这样的:对于 N 张牌,每次随机抽出一张来,检查这张牌是否抽过。如果被抽取过,就重复抽取过程,直到不重复。然后记录下抽取的牌的位置。重复这个过程,直到得到一个随机序列。最后用这个序列将原始排列打乱。

这个方案给我的第一感觉并不好,因为当 N 较大时,最后需要重复抽取多次才可以成功。我估算了整个的时间复杂度大约是 O(N^2)

当然,洗牌这件事情可以有许多算法来解决。我重新写了一个,采用了最简单实现的方案。

新的方案是从牌套里随机找到两个位置,将其位置的牌交换。重复若干次后,便可以将牌洗乱。这里最关键的是需要找到一个合适的重复次数。

这个问题首先需要定义什么叫作“洗乱”。

我随便给出了一个定义:在洗牌过程中,任意一张牌不被抽到交换的概率小于 1/1000 。(这个定义不太符合直观感觉,这个下面会讨论)

简单的列出方程:( (n-2)/n ) ^ m <=1/1000 得到 m >= -3* ln 10 / ln (1-2/n)

对于 52 张牌,大约是 176 次。


之后,另一个同事给了我另一个方案。产生 N 个不易发生碰撞的随机数,比如 (0,1) 的浮点数,或是 [0,4G) 的整数。将这些数字排序,则可以得到一个被打乱次序的序列。

这个方案看起来更好,因为更接近洗乱牌的目的。我重新给一个“洗乱”的定义:每张牌在每个位置出现的概率相同。

反过来,我想知道前面我给出的交换法洗牌有多接近它。

要得到严格的数学分析似乎很困难。偷懒 google 了一下,原来好多人研究过类似问题了。看这里:

http://mathworld.wolfram.com/Shuffle.html

从这个链接找过去,有一篇论文 。它讨论了另一种类似的洗牌方法,即第一次把第一张和随机一张牌交换,第二次把第二张和随机一张牌交换…… 重复做 N 次。

当 N 大于等于 18 时,用这个方法洗牌后,居然恒等排列(identity permutation)是最有可能出现的。(所谓恒等排列大概是指第 n 张排在第 n 个位置)。论文太长没精力读,不过这个结论还真是让人惊奇啊。

September 29, 2007

独立的游戏用户登陆认证

网易的所有产品都使用网易通行证系统做用户身份认证,包括游戏产品。

这是降低新产品用户门槛的好方法。几乎所有的网络服务提供商都弄了个自己的统一用户认证系统,网易通行证也是干的这挡子事,内部我们把这套系统简称为 URS。公司在 URS 系统上投入了很多人力和资源,但是其表现总是跟不上我们的需求。我个人从 03 年开始就不断的在提一些安全方面的改进建议。但是由于这些系统涉及面太广,想做出些实质性的改变举步维艰。

不断的写建议书,不断的参与北京 URS 部门的技术会议,让我充分理解了他们的困难,和其中许多非技术难点的难处。

但是,国内糟糕的网络安全环境,日益严重的游戏帐号失窃问题,让我不得不时常关注这方面的问题。最近,又想了个改进方案,希望可以有所改善安全问题。

缘起:

我们办公室最近搬入了一个新部门。没想到第一天我们就发现了 ARP 欺骗。不得不说 Windows 在这方面防护意识实在是太差了,装 Windows 的电脑一个上午都没发现这个问题。好在我们有几台 Freebsd 的桌面在用。很快的就发现了 console 上的警告,网关的 Mac 地址被更换了。

事故只持续了三四个小时,被木马感染的机器迅速被定位,果然是新部门同事进入带来的新机器被感染。我们也立刻让所有同事修改了在事发的那个上午用过的任何网络服务的密码。

这件事情再次警示我们,在今天的网络环境中,只保证自己的机器干净还是不足够安全的。

我们游戏目前的用户认证方案:

如果用户不选择额外的安全产品:例如 将军令电话密保 等等这些的话,我们对最常规的键盘密码的网络数据通讯所做的保护极其有限。

在游戏中,仅仅只是用私有加密算法对通讯做了加密。除去本身机器中木马的危险之外,只能防止最基本的网络数据监听。即,监听网络包的窃贼不能简单的查看数据流而得到用户输入的密码罢了。

但是,理论上,任何人只要得到所有的数据流,就有获取用户密码的可能性。他唯一缺少的只是私有的加密算法而已。而加密算法可以通过对 client 程序的逆向工程得到。

并非我们的技术人员知道这样做是极不安全的。只是,游戏系统跟 URS 有千丝万缕的联系。我们不能放弃 URS 而做一个独立的用户认证系统;而 URS 系统由于种种原因,一直没能增加我们需要的更安全的基于挑战策略的更为安全的认证方案。

ps. 关于用户认证的安全性讨论,可见云风以前的一篇旧文:多服务器的用户身份认证方案

曾经不只一次的提过,游戏系统应该适当的和 URS 分离。URS 在降低新用户门槛方面有巨大的作用。但是,它带来更多的木桶短板效应。很多只是基于网页的服务,无法做到更高的安全级,极为容易丢失密码。为了安全起见,我们又同时向用户宣传,不要在论坛等地方使用和游戏帐号相同的通行证。这还真是莫大的讽刺啊。

将军令等安全系统的加入,并鼓励用户使用,从另一方面又提高了用户门槛。而且这些安全产品,被一个个或是拍脑子,或是精心策划,或是作为应急方案想出来,不断的加入 URS ,形成了极大的历史负担。更重要的是,大多数并没有遭遇帐号失窃的用户,并不会采取额外的保护措施,他们钟情的依旧是最为便捷的键盘密码。

我曾经百般取笑过早年的一些诸如帐号安全码等临时安全方案,后来都理解了。这是一个复杂的问题,没有理想的解决方案的。

OK 。我现在知道我们不可能放弃 URS 独立做一套全新的密码认证系统,那么做一些改动怎样?

  1. 游戏新注册用户可以直接用通行证帐号密码,注册游戏新帐号。

  2. 注册游戏帐号后,强制要求修改密码(必须和通行证不同)。

  3. 玩家游戏密码丢失后,可以在通行证里申请重置,但 48 小时后生效。48 小时期间,一旦玩家正常登陆游戏,重置指令自动撤消,并在游戏中通知用户。

  4. 任何通行证密码的修改,都通知游戏用户(注:不需要修改 URS 的实现)。游戏服务器将 cache 通行证密码,在玩家登陆时自动重新验证。如果通行证密码被修改,玩家必须重新在游戏中核对通行证的身份(依旧需要正确输入游戏密码),才能再次进入游戏。

  5. 游戏中每次登陆都通告用户最近几次的登陆时间/IP列表。以及暴力猜测密码企图的尝试记录。强制用户在密码不安全的时候修改密码。

这样的改进方案重点在于,不在已有的 URS 系统上做任何修改,也不必增加新的接口;但游戏用户采用独立的认证系统。游戏认证系统必须和 URS 系统同时工作,用户才能够登陆游戏。但是 URS 系统验证不由最终用户主动操作。最用户体验方面,不增加任何用户负担。

对于游戏系统,两套系统相互牵制,用时间做为中间缓冲。

游戏帐户本质上依旧归属 URS 帐户,帐户冲值记费等依旧划归 URS 管辖。

September 21, 2007

泊松分布

周末,同事离去的都很早。我留在办公室,这周想做的事情基本完成,那就随便写点东西。

写写概率论中非常重要的泊松分布(poisson distribution)是我这周中间就有的想法。

具体的起因记的不太准确了,似乎是因为在一个接收新游戏 bug 反馈的 IM 群里跟同事聊天跑题。从游戏的 bug 扯到游戏的数值设定,然后说起概率,再跑题到大学中学到的数学知识;正好前几天睡觉前在翻《一生受用的公式》这本袖珍小册子,看到了泊松分布的公式以及关于它的有趣的插图;然后问起同事对这个东西的了解程度。

结果可想而知,当时没有人可以准确告诉我到底什么是泊松分布,它有什么用,当然更不用提它的公式是怎么推导出来的了。让我有点自鸣得意的是,自己大概还知道个所以然。不管怎么说,若不是当年本科的概率统计考试中的笔误,我就能拿个满分的。上大学时,考试前我很少复习,不感兴趣的课程也基本没去读书。不是说天才到可以以那种状态考试过关,只是那个时候我不太在意挂科而已 :)。相比较而言,没经过理解的东西让我去背公式应付考试这种事情,我是坚决不干的。

可惟独这本概率统计,我是相当喜欢,也就最认真的去学了。

自己明白不是真的明白,一旦想教给别人时就会露馅。当想把我曾经的理解和记忆写出来时,才发现自己写不太清楚。这几天没事翻了翻书,也 google 了一下,理清了点思路。今天记录下来,算是一个总结。

首先必须由二项分布引出:

如果做一件事情成功的概率是 p 的话,那么独立尝试做这件事情 n 次,成功次数的分布就符合二项分布。展开来说,在做的 n 次中,成功次数有可能是 0 次、1 次 …… n次。成功 i 次的概率是:

( n 中选出 i 项的组合数) * p ^ i * (1-p)^ (n-i)

以上公式很容易推导,用一点概率学最基本的知识就够了。因为每一特定事件成功的概率是 p ,不成功的概率是 1-p 。i 次成功的事件可以任意分布在总共的 n 次尝试中。把它们乘起来就是恰好成功 i 次的概率。

当我们把二项分布推而广之后,就可以得到波松分布。

可以这样考虑,在一个特定时间内,某件事情会在任意时刻随机发生(前提是,每次发生都是独立的,且跟时间无关)。当我们把这个时间段分成非常小的时间片构成时,可以认为,每个时间片内,该事件可能发生,也可能不发生。几乎可以不考虑发生多于一次的情况(因为时间片可被分的足够小)。

当时间片分的越小,该时间片内发生这个事件的概率 p 就会成正比的减少。即:特定时间段被分成的时间片数量 n 与每个时间片内事件发生的概率 p 的乘积 n*p 为一个常数。这个常数表示了该事件在指定时间段发生的频度。

回过头来再来看这段时间内,指定事件恰好发生 i 次的概率是多少?代入上面推导出来的公式得到:

n * (n-1)... (n-i+1) / i! * p^i * (1-p) ^ (n-i) => np(np-p)...(np-ip+p) / i! * ((1-p) ^ (-1/p))^(-np) / (1-p) ^i

当 n 趋向无穷大时,p 趋向 0 。而此时 (1-p)^(-1/p) 趋向 e 。注:推导过程可见文末。

上面这个公式可以划简为 lamda ^ i / i! * e ^ - lamda (lamda=n*p)

这个公式推导过程不复杂,耐心点一看就明白。而这个关于 i 的分布就是著名的泊松分布了。

为什么泊松分布很有价值,因为我们在推算某些特殊事件在一段时间内可能发生次数的时候经常会用到它。比如设计一个无聊的打怪练级的 MMORPG ,假如玩家到一个地图杀怪纯属独立随机事件,我们应该在这个地图按什么频率刷怪可以合适到让来的玩家不会找不到怪打。

玩家同时来到这个地图的数量就是满足泊松分布的,我们统计出一段时间来访玩家的平均数,就可以根据泊松分布公式推算出玩家峰值在什么数量上出现很大的概率。然后就可以进一步计算出合适的刷怪频率和密度了。

呵呵,想指责我这个想法过于天真的职业游戏策划请先别忙着骂。我承认我这个例子举的很不恰当。因为导致玩家去一个地区的因素很多,包括地图的怪的数量等等。而且玩家之间也有很强的联系。玩家到一个地图去并不是独立事件,最终的结果很可能偏离泊松分布很远。但请原谅我吧,今天太晚了,一下想不出什么跟游戏设计密切相关的例子。有机会我会补充个更好的。

不过请相信我,日常生活中有很多突发事件满足泊松分布的,不信请自己 google 之。


本着追根究底的原则,写一下前面提到的一个极限的推导。尽量用高中数学程度就可以理解的语言啦:

(1-p)^(-1/p) 当 p 趋向于 0 时,为什么它的值趋向 e ?

关于 e 可以看我写的另一篇文章 ,从那篇文章提到的知识,我们可知 ln x 的导数是 1/x ,由导数的定义可知

1/x = lim (( ln x' - ln x ) / ( x' -x )) 这里 x' 趋向 x

令 x' = x + 1/n ( n 趋向无穷大) 代到上式中, 并用对数计算法则化简得到

1/x = lim ( ln ((1+ 1/ (n*x)) ^ n)) 这里 n 趋向无穷大

再令 z = 1/x ,并再一次用对数运算法则化简可得

z = lim (ln (1+z/n)^ n ) 这里 n 趋向无穷大,两边取指数函数,可变化为 e^z = lim ((1+z/n)^n)

当 z = 1 时,我们可以得到特例: e = lim ( (1+1/n)^n ) ,n 趋向无穷大

回头再来看式子 (1-p)^(-1/p) ,令 n = 1/p ,因为 p 趋向于 0 ,所以 n= 1/p 趋向无穷大。前式可变形为:

(1+1/(n-1))^n ,当 n 趋向无穷大的时候,跟 (1+1/n) ^ n 有相同的极限 e 。

September 19, 2007

正确的迭代处理对象

昨天在写一个 AOI 模块,设计时又碰到一个对象迭代的老问题,必须谨慎对待,文以记之。

缘起:

当对象 A 进入 B 的 AOI 区域时,会触发一个 Enter 事件。这个事件处理是以回调函数的形式完成,如果回调函数中再次调用 AOI 模块,产生一次间接递归,就有可能破坏 AOI 模块内部的某些迭代过程。

更要命的是,如果回调函数内删除了一些相关对象,很有可能引起对已释放对象的访问错误。

这类问题在各种对象管理的程序框架中经常出现。除了上面提到的 AOI 模块,在 GUI 模块设计中也极其常见。下面谈谈我的解决方案吧。

首先,由于回调函数内部逻辑的不可预知性,我们一定要把实际的处理放在每个 API 实现的末尾。一旦真正的处理在中间,因为间接递归的可能性,极有可能保存在模块内部的上下文信息被其破坏。

正确的做法是在模块环境中创建一个唯一消息处理队列,把可能引发回调的消息都暂入到队列。由于队列只有 enter 和 leave 两个方法可以改变内部状态,迭代处理队列本身是不会出问题的。

另一个必须考虑的对象的释放时机。当我们用 C 或 C++ 这类没有 gc 机制的语言实现的时候,它是个相当头痛的问题。

因为,任何一个消息处理的回调函数都可能删除某些对象。而这些对象的指针极有可能放在消息队列中。不要跟我说在消息队列中放对象的智能指针,然后每个用到该对象的地方都使用智能指针访问。那样我会疯掉的,尤其是需要把回调函数这样的接口暴露给最终用户时,我可不希望在接口上暴露一个难看的智能指针类。即使拐弯没角的把接口问题解决掉,额外的性能付出也让人心里不大舒服。

解决方法有两个:

  1. 消息里不记对象的指针,而用一个进程生命期唯一 id 标识。 再用一张 hash 表做映射。对象删除后,id 不再找的到对应的对象。这个方案在上次的一篇文章 的留言中提过。

  2. 用一个间接指针。对象删除后把间接指针置一个标记。再次调用时就可以知道对象被删除了。间接指针本身占用的空间从额外的备用池里分配。定期回收,和真正的删除垃圾对象。

个人比较推荐性价比更高的第 2 方案。接下来展开谈一下细节。

所谓定期回收,应当隐藏起来让用户不可见。我们可以把回收过程放在新对象创建的时候,因为这个时候恰巧需要新的内存资源,是释放旧资源的最好时机。由于对象创建也可能发生在消息处理的过程中,我们不能在消息处理期间做这个工作。所以垃圾收集的时候必须检查消息队列为空,才可以开始。

回收分两个步骤:

一是删除垃圾对象,这个去检查间接指针中的删除标记位就可以了。

二是删除间接指针本身。当消息队列为空时,完全可以把所有间接指针整个一起拿掉。

以上问题考虑周全后,基本上万无一失了。:D

September 16, 2007

手工

玩龙与地下城的朋友应该知道,这个游戏需要一些平常我们见不到的骰子:四面的、八面的、十面的、十二面的、二十面的。通常我们在超市里能买到的只有六面骰,估计是给那些麻将爱好者用的。

我有一套专用骰子,前几年去成都公干,一个网友送我的,据说价格不菲。不过这一套一样只有一两个,玩起来不爽。今天兴起,打算自己做一套。

材料很好找,每个月都能收到各色广告信,有些用料极好。另外翻出了往年公司过年发的红包,纸张也不错(意外收获暂新二十元钞票一张 :) )。比较后决定用红包来做。

先拿正二十面体试试,展开图大约是这样的:plat20.png 。不过手头没啥工具,只有一支铅笔,一把剪刀,几张便签纸。

怎么画出正三角型来是我遇到的第一个难题。没有圆规和三角板。我找了一下,手头有几个硬币,但是无法方便的确定圆心。后来想了下,可以在白纸上画一个硬币大小的圆,然后折叠纸来找到圆心,这方法操作烦琐,误差比较大,没有采用。

最后的解决方案是用了三张一样大的便签纸,拼出了个正三角形,在此基础上,剪了了个简易的三角板。

大约花了半小时,把图样画好了,反复校对了绘图误差后,剪了下来。

第二个难题是怎么粘合起来。试了几种胶水都不太好用。这种纸面太光滑,沾不牢。而且最后封口时,需要从里面粘住,很是麻烦。

在文具柜里找了一下,发现了好东西:双面胶,试了一下果然非常方便 :) 几分钟就把纸骰子粘好了。

dice20.jpg


做这么个小玩意让我想起了小时候做手工。我受老爸影响喜欢做点小玩意。当然比不上他老人家厉害。

据说我爸追我妈的时候,经常做一些金属的小玩意,比如小调羹,钥匙串之类的东西送她。听说我出生的头天夜里,他连夜打了个小酒精炉,带到医院去偷偷煮鸡蛋(医院病房里不准生火,那个年代也没有电炉)。从我懂事起,我就一直在玩老爸 DIY 出来的玩具:手工雕刻的木马;去竹林里劈下来的竹子扎的各式风筝;套在手上的布偶…… 多的记不清了。

我没那么多本事,只会玩玩纸模型。那个时候物资稀缺,家里任何硬纸板和塑料蛋糕盒都被我保存下来。电视台放变形金刚的时候,上课没心思听讲,就在下面画设计图。回家就开始动手做。

今天再做手工,觉得现在的小孩子真幸福啊。再也不用愁材料的来源,还有科技进步带给我们的诸如双面胶这样方便的工具。还有更多的大把的时间。想我上学的时候,每天得花至少三个小时做家庭作业,一周只有一个休息日。

September 15, 2007

生日

9 月 15 日,一个人的生日。

我还记得,从来没有忘记。

September 09, 2007

C 的回归

周末出差,去另一个城市给公司的一个项目解决点问题。回程去机场的路上,我用手机上 google reader 打发时间。第一眼就看到孟岩大大新的一篇:Linux之父话糙理不糙 。主题是 C 与 C++ 的语言之争。转到刘江的 blog 下读完了 Linux之父炮轰C++:糟糕程序员的垃圾语言 大呼过瘾。立刻把链接短信发给了几个朋友。

语言之争永远是火药味十足的话题。尤其是 C 和 C++ 的目标市场又有很高的重合性,C++ 程序员往往对C++ 其有着宗教般的虔诚。我想,今天我在自己的 blog 上继续这个战争,一定会换来更多的骂名。只不过这次 Linus 几句话真是说到我心坎里去了,不喊出来会憋坏的 :D

首先,给不熟悉我的朋友做一个技术背景的自我介绍:

我不是一个 Linux 的 fans ,虽然我今天对 Windows 也没有什么好感,但我的大部分工作还是在 WIndows 上做应用软件开发的,对 Windows 还算熟悉。现在我也用非 Windows 的系统,但那是一台 FreeBSD 的机器,不是 Linux 。

我自认为对 C++ 相当熟悉,精读过市面上能买到的关于 C++ 的大部分书籍,像 D&E of C++ 这样的经典还读了不只一遍。用 C++ 写过至少数十万行代码,阅读过 STL 的大部分源码,和 ACE / Boost 的一小部分。

曾经我是 C++ 的忠实粉丝,如果谁说 C++ 的不是,要么会选择跟他辩论到底,要么会对此人不屑一顾。

还有一点我认为非常重要:我第一次爱上 C++ 是 15 年前(1992 年),然后对其慢慢冷淡,回归 C 的怀抱。而到了 2000 年,我又一次爱上 C++ 。也就是说,从热爱 C++ 到否定它,在我的个人经历中,有过两次。不排除未来有第三次的可能,但这一点足可说明,否定 C++ 是出于一种理性的判断,而不是一种冲动。

写上这些,并非是想倚老卖老。我知道,想骂我的 C++ 程序员,更讨厌有人倚老卖老的数落 C++ 的不是。而且论资格,我顶多及的上 Linus 大大的一个零头,既然有老人在前撑腰,下面说话的底气就可以足一些了 :)


C 是 C++ 的一个子集(从 C99 开始已经不是了),用 C 能写出来的代码,C++ 一样可以写出来,然后可以完成的更好。

这是新手们自以为是的攻击武器。Linus 用了一个很恰当的理由做出反击:“你当然可以用任何语言编写糟糕的代码。但是,有些语言,尤其是带有一些心智(mental)包袱的语言本身就非常糟糕。”

没错,我最想说的就是这个。C++ 就是一个“带有一些心智(mental)包袱的语言”。这对软件设计的影响非常之大,没有经年的软件开发实践很难理解这一点。

从这一点上展开,把 ASM 和 C 比较的问题和 C 与 C++ 的比较相提并论就没有意义了。

接下来要找到的问题要点就是,C++ 比 C 多出来那些东西后,真的会带来心智包袱吗?这个问题不好回答。单纯从 C++ 语言特性的繁杂导致的不易掌握和误用这些角度是很难说服我自己的,更别说去说服那些比我聪明的多,刻苦的多的 C++ 程序员们。我自认为对所谓 C++ 的高级特性掌握的还是不错的,并运用在诸多实际项目中。他们相当有趣,在某种程度上也非常的有效。代码可以获得相当高的执行效率,并可以缩短编码的时间(更少的键击数),完成他们也有很大的成就感。

好了,让我再引用 Linus 的一句说到我心坎里的话。“字符串/内存管理根本无关紧要。这不是重要的部分,而且也不复杂。唯一真正重要的部分是设计。”

设计!这才是重中之重。

如果要说,这最近 10 年的程序员生涯我学会了什么?我认为,我比以前能设计出更好的代码了。能更准确的把握设计的坏味道。而对编程语言的掌握,对操作系统的熟悉,工作相关知识的了解等等。那些只是自然而然发生的事,那些是知识的积累,而非能力的提高。

“抽象”,“面向对象”,“设计模式”,这些重要吗?重要。对软件开发相当重要。但重要不是必要,执迷于“抽象”会使你离目标越来越远。当我们一次又一次的提取出事物的共性,建立起抽象层的时候,我们可能丢弃了真实。C++ 继承了 C 语言中“信任程序员”这一设计哲学,致力于让程序员在建立抽象层时,可以不做出额外的消耗。他的解决方式是提供尽可能多的语言工具和设计选择,任何一个都允许你在不用的时候不带来额外的性能损失。

这是一个美好的愿景:C++ 程序员指望可以建立强大的可复用的抽象层,面对世界上一切的具体应用。同时 CPU 执行序列在穿越这个坚厚的抽象层的过程中,居然可以以光速通过(通过抽象层没有额外的执行效率付出)。为此:C++ 社区创造了 STL ,创造了 Boost 。它们共同的关键词是:效率、复用。

再往上呢?另一个问题产生了:“——低效的抽象编程模型,可能在两年之后你会注意到有些抽象效果不怎么样,但是所有代码已经依赖于围绕它设计的‘漂亮’对象模型了,如果不重写应用程序,就无法改正。”这一段依旧是 Linus 语,我不停的引用,是因为我明白这一点,但是不能表达的更清楚。

使用 C++ 的程序员不断的强调复用性,却不断的需要重写代码。如果一段代码可以不被重写,那多半是因为对重写工程量的妥协。是的,其实我们可以用 C++ 的各种特性写出更好,更漂亮,更高效的代码。两年前的框架不那么完美,不是 C++ 语言的错,是两年前的我能力有限的缘故。但是因为需要改写的是设计框架,这意味着我们必须跟着变更已经完成的功能模块,或是加上桥接层。

的确,STL 和 Boost 都是世界顶尖程序员完成的。代码质量非常的高(当然,我对 Boost 的一部分持保留意见)。我不拿编译器兼容性和可移植性或是编译速度说事,虽然这些的确是现实问题,但不足以成为反对 C++ 基础类库的理由。

好好的用好 C++ 当然得用好 STL ,Boost 也应该认真考察一下。能够仔细读一下源码更好。合格的 C++ 程序员应该做这个。否则作为 C++ 程序员你就违背了 C++ 语言的设计哲学:C++ 信任了你,你就该对的起这种信任,搞清楚你写的每一行代码背后,机器都去干了什么。

但是,STL 过于庞大了,Boost 更加是。我不是抱怨阅读和学习它们的源码的难度和需要的时间和精力。正相反,我在学习它们的过程中充满了乐趣和感激之情。高手前辈透过这些高质量的代码教会了我很多东西。我隐隐担心的是,这么庞大的代码,它的设计不可能是永远正确的。两年之后,他们的设计肯定依旧正确,再两年还是的。但是我几乎敢肯定,放之更长远的时间来看,绝对会在某些设计领域发现其不是最佳的选择。到那一天,我们会选择修改吗?我想 C++ 社区会被迫选择妥协。但是,C++ 程序员心中会充满痛苦。

C 在这个问题上的抉择是不一样的。在效率问题上,C 程序里最令人担心的是函数调用的消耗。C++ 程序员最津津乐道的案例就是 std::sort 全面击败了 C 库中的 qsort 。C 语言的失败正在于多余的函数调用消耗。

但是,从一开始 C 就选择了承认函数调用的消耗,而这一点几乎是唯一。付出了这个代价后,设计失误导致的效率下降问题几乎总可以避免。C 和 C++ 都可以选择重写设计失败的部分,但不一样的是, C 程序员几乎可以不考虑妥协的问题。同样的是考虑极端效率的语言,C 语言坦然面对缺陷,才是真正的符合了 KISS 原则。

我对这个问题的见解,可以再引用 Linus 的一段话作为收场。“如果你想用更花哨的语言,C++绝对是最糟糕的选择。如果想要真正的高级特性,那就选择有垃圾回收或者好的系统集成的,而不是既缺乏C的简约(sparseness)又缺乏C的直接而且没有重要概念的高层绑定(high-level bindings to important concepts)的东西。”。这是我最近几年来一直坚持的观点:C++ 的发展,一定要补充对 GC 支持所需要的特性

强调一下,我并不讨厌 C++ :) 。 C++ 的粉丝们可以随便骂我,但是不要带上阶级仇恨。


ps. 最近两年多,我在做一个游戏引擎的项目。这个项目现在是第三个版本了。第一个版本是用 C++ 实现的,但是没有用任何已存在的类库(包括 STL)。在第二个版本中,我去掉了所有使用 C++ 高级特性实现的部分,只使用了 C++ 基本特性实现所有。今年重写的第三个版本,全部换成 C 代码了。这个项目的发展,可以反应出我个人对 C/C++ 理解的心路过程。

September 06, 2007

玩了一下 ajax

起因是这样的:

几个同事在棋牌群里聊天,说找不到搭档打桥牌。网上也没啥好地方去,大家都比较讨厌下客户端和注册。我说,不如我做一个免客户端免注册的桥牌网站吧。然后就开始了。

直觉告诉我,ajax 技术可以实现这些。但是我没做过 web 方面的开发,仅有的一些知识只在几年前写过一个 php 留言本。一开始觉得 ajax 这些时髦玩意学一下午,然后一通宵就可以把想要的东西做出来。哪知道,结果不务正业干了半周了,中间还熬了两晚上,到今天都没做完。明天要出差,只好放一放了。

做这件事情之前,我先回忆了从前道听途说以及自己臆测得到的一些不完整的知识片段:

web 开发跟我们现在做的胖客户端长连接的网络游戏很不一样。web 软件几乎都是基于 http 协议通讯的,http 是一个短连接,每次发送一个请求,然后接收一段回应的文本,如此而已。

为了让浏览器可以记住有前后关联的事件,我们可以选择把一个 session key 保存在浏览器 cookie 中,或者直接编码在 url 里,在服务器和浏览器之间不停的传递。但是浏览器又天生允许用户无次序的刷新各个页面,且可以并发许多请求。所以从某种简单来看,浏览器跟 web 服务器的通讯类似 UDP 的协议。它不保证请求的次序,不保证处理所有的请求,甚至允许同一份请求解接收多次。

用户在使用 web 服务的时候,从技术层面上看,只能他主动向服务器索取数据。服务器不能主动发数据过来。这在交互性强的软件中,是一个极大的障碍。ajax 网站解决这个问题的方案通常是设置一个定时器,有事没事就去问服务器,“您老有什么交代吗?有事早奏,无事退朝”。

为什么 ajax 程序可以不刷新页面就可以对用户的操作做出反应?(不操作也能有反应,也就是上面提到的定时器)远古的做法是在页面上放一个 iframe,把它的尺寸缩到你看不见,或者挪到不碍眼的地方。由主页面上的 javascript 控制这个 iframe 的刷新,自然提交的 url 也是由主页面的逻辑来做适当编码的。服务器接到这个 iframe 的刷新请求,就会把相应的回应发过来。这些信息通常很短小,信带到了就行,不需要人来读。主页面的 js 分析这些反馈结果,就可以做出适当的动作了。

后来时代发展了,不用再创建一个看不见的 iframe 了。浏览器允许直接创建一个用来发送 http 请求的对象—— XMLHttpRequest ,还可以方便的从中获得服务器返回的数据。做这样的事情就简单了很多。

以上,就是 ajax 中最重要的基础技术点了吧。


动手做这件事的时候,我选择了最为熟悉的开发工具,Lua 。早就听说有牛人做了一套基于 Lua 的 web 开发平台 Kepler ,连同 Lua 实现的一个一个轻量的 web server 一起,安装包才 700k 大点。在 Windows 和 Unix 下都可以一键安装。

算上下载时间,我花了大约五分钟时间把开发平台搭建好了。就着文档开始堆代码。做起来才发现,事情没这么简单。

第一夜遇到的第一个实质问题是关于整个系统的结构该怎么搭建:

打牌这种互动性比较强的软件,必须在服务器上有一个地方保存牌局。我不想牵扯到数据库,这可能使我一晚上把东西做完的希望泯灭(因为我对数据库不太熟,得花不只一个晚上学习)。web 服务器处理 http 请求都是一个个独立的。每次请求结束,整个环境就消失了。翻了下文档,发现 Kepler 提供了一个左右 session 的模块,似乎可以解决这个问题。文档到细节处就没有了,好在源码并不长,读了下就明白了。它提供了一个 lua 的 table 持久化的工具,可以方便的把 lua 的环境写到一个文件中。session 模块管理了一堆这些 session 文件。可以在你需要的时候把以前持久化的数据读回内存。

接下来就发现了严重的问题:session 的 load 和 save 方法是不加锁的!因为一个牌局至少有 4 个用户共享一个 session 。不加锁一定会导致数据混乱。一开始我想试图用版本号避免数据冲突的问题,最后发现实现的复杂度过高。最终放弃。到现在我还没想明白,kepler 提供的这个 session 模块,在没有锁支持的情况下,到底有什么实用价值?

不过 kepler 并非工作在真的多线程环境下,它利用了 lua 的 coroutine ,而 coroutine 的切换似乎之发生在数据内容生成的时候,即 cguilua.put 的调用时。如果在所有内容生成前,把 session 里的数据生成后,没有锁还是勉强可行的。否则,只能换用数据库或自己写一个带锁的 session 管理模块了。

总之,第一晚研究这些东西,并读了大段 kepler 的源代码,花掉了不少时间。我的计划表就这样延长了。

第二天跟同事讨论了一下,继续研究 kepler 的代码。发现它时间了一个叫做 rings 的东西,这个玩意可以从一个 master lua state 中创建出若干 slave state 出来。这个方案可以轻松避免处理每个 http 请求过程可能发生的资源泄露。这个道理跟我们用进程来管理 os 中的各个活动的软件一样,杀掉进程总可以把资源回收完全,而不需依赖软件的正确实现。

比较有趣的事,我们可以从 slave state 中向 master state 读写数据。由于 master state 长期存在,放在里面的数据就是持久性的。把牌局放在 master state 空间中非常方便,还可以避免每次浏览器过来的请求都需要重新做一次数据持久化的工作。

甚至,我们不需要把逻辑放在 slave state 中实现。第一次初始化的时候把逻辑代码灌到 master state 空中,以后就可以方便的调用了。

第二夜我又遇到了另几个小问题。

kepler 的 1.1 目前还是测试版,存在 bug 是必然的。可是让我很不巧的第一次用就碰到了,很是郁闷。

cgilua.redirect 这个 api 居然不能工作 :( 。我对 http 协议不熟,结果晚上现找资料读。发现kepler 自带的 web 服务器在发送重定向数据头的时候,没有正确的发送回应码 301 或 302 ,而是发送了 204 。起初我我只想读一下相关代码找到 bug 修正。没想到,这一读,就读了一通宵。

总的来说,kepler 构架的是非常巧妙的。可是越巧妙的构架,弯弯就绕的越多。为了解决 lua 5.0 和 5.1 之间的语言差异,又不至于影响效率。它居然用了一段代码去生成另一段用于运行时生成代码的代码…… 看明白后,那个寒啊。幸亏没被饶进去晕死掉。估计动态语言这种用法,只有用 C++ 中模板之模板才可以媲美了。

好在这不是大问题,如果不是我好奇心太重,也不至于花这么多时间在跟原计划不相关的代码阅读上了。

第二晚,还是没做出啥东西来。

好好睡了一觉后,感觉思路理清楚了。整个项目最麻烦的一点在于浏览器上的应用跟有专有客户端的软件不同。浏览器用户有可能中途关闭窗口,或是半路杀进来。又或者把自己的窗口复制成多个。除非你在这些情况发生时,野蛮的让用户重新登陆,重置所有的状态。不然就得好好考虑这个问题如何解决。

一种方案是,让服务器每次通讯都传递牌局的完整状态。另一种是,让服务器维护牌局的多个状态版本,而让客户端的浏览器每次请求发送他拥有的版本。然后服务器之需要通知版本差异即可。

这两个方案前者比较容易实现,后者可能可以节约许多带宽。我考虑了一下,采用了第一个方案,但是依旧维护一个版本号用来检测状态变化。

睡了一觉醒来后,精神不错。只用了几个小时就做好了游戏大厅和发牌的逻辑。看起来一切都挺正常。中间鄙视了一下 IE 。明明在 Opera 上都是正确的,IE 下那个定时触发的 http 请求就是不正确。看了 web 服务器这边的记录,发现是 IE 私自决定 cache 住结果了。而按标准,URL 里带 ? 的动态页面请求是不应该被浏览器 cache 的。google 了一下,发现很多人也遇到过这种情况。加了个数据头就可以解决。

接下来的工作就是体力活了。编写打牌的逻辑,记分,还有做出漂亮的界面等等。重新估算了一下,全部完成可能还需要几十个小时的人工 :(


关于这个东西,我的想法是:不需要用户注册,第一次登陆则由服务器生成一个唯一用户 id 记录在用户 cookie 中。用户可以登陆任意房间,也可以让服务器创建新房间出来。每个房间有一个唯一房间编号,若想约朋友一起打牌,只需要告诉他房间号即可(或者直接发送一个 URL)。

房间没有权限管理。每个人都可以坐在任意位置。对于桥牌来说,就是 5 个位置:东南西北和旁观。每个人进入房间,默认坐到旁观席上。而前四个位置只能坐一个人。如果这个人一直和服务器保持通讯,就没人可以赶他走。但一旦他超时,任何一个旁观者都可以顶替他的位置。

整个系统不需要做积分和排名(当然要做也很容易),甚至不需要任何数据库。服务器里所有数据都保存在内存中。没有任何权限的限制,每个来玩的人都是平等的。约朋友一起下棋打牌只需要发送一个房间的 URL ,不需要安装插件,甚至可以做一个非 ajax 版本来适应手机浏览器。

如果以后需要做用户管理,可以让用户输入他的 email 地址做用户 id 。大多数情况下不需要密码登陆,email 地址只是为了用户 id 的绝对唯一性。如果某些用户需要密码保护的话,再将密码发送到 email 中即可。


ps. lua 的描述能力还是很强的,如果有人怀疑 lua 在 web 开发上的潜力的话,可以看看 Sputnik 这个 wiki 系统 。整个系统号称只用了不到 2000 行 lua 代码。作者宣称会继续努力把代码精简到 1000 行之内。

September 01, 2007

大恩莫言谢

题目是从黑三角借来的。读了南桥的大恩莫言谢,有些共鸣。前两天晚上突然有些聊天的兴致,跟一个未曾谋面的网友在 google talk 上聊了许多。他似乎是一个基督徒,一直都在跟我说些关于行善的事情,我便跟他谈了我的父母,尤其是我的母亲。

我的母亲前些年资助了一个大学生,话题从这里展开。

那一年长江发了洪水,像武汉这种工业重镇,市区自然不会受灾。但是湖北其他的地区就不是这样了。母亲在电视或是报纸上看到些消息,然后去了附近的一所大学。

武汉水运工程学院,现在改名叫武汉交通科技大了。离我家不远,公交车两站地的样子。母亲直接找到了学校,请帮忙介绍一个家里受灾的学生,希望可以资助他。学校里挺重视这件事,没多久就联系到了一个贫困大学生。在洪灾中他的父亲不幸过世,家里条件不太好。那一年,这个学生读大二(或是大一?记不清了),我当时在广州工作,收入远没现在这么宽裕。而那时母亲已经退休,父亲工资不高。

今天、他在天津南开读研。据说是跟企业签了合同,自己不用出学费,同时生活费也有了保障。离开武汉后,他偶尔给我父母打个电话问候一下。

过去好几年了,母亲资助了他本科的学费。每个月把一些生活费交到他手上,并在周末把他叫到家里改善一下伙食。这些年我在外面闯荡,不太熟悉这个人,只见过两面。印象中他有些内向,学习应当不错。第一次见面是在家一起吃饭,第二次他似乎从老家带了条活鱼过来。他没有流露出对我母亲特别的感激,取生活费也是很平常的事情,在我家也没多少不自在。但我知道,感谢是放在心底的。


母亲是个老党员,并以自己是党员为荣。她已经退休十年了,偶尔也参加党内组织生活,前两年的保鲜也参加过学习。有时候,她来看我,在我这住上几天。晚上睡觉前,我们总会聊天。她会跟我说一些她对于实事,对于周遭的人的一些见解。有时她也会表示她信佛,那种信不是宗教信仰的笃信。而且她承认作为共产党员,更应该唯物一些。由此我知道了母亲是个有思想的人,对人生也看的透彻。她的大半生都在帮助别人,并以此为乐。

从我记事起,母亲就在照顾一对没有儿女的老人,无亲无故的。仅仅只是她工作后,老人当了她几年师傅。直到前两年两位八十多岁老人相继去世,除了一些旧书和杂志,几乎没有留下遗产。老人是个老知识分子,据说我的名字就是老人起的,那么母亲无怨无悔的照顾这对老人应该有三十年了吧。不少人怀疑她有经济上的企图,她总是一笑了之,因为最后所有人都会看清结局的。母亲的师母走的时候留了个戒指给她,放在今天价值也不会超过几千块吧。据说走的时候,说,这一辈子欠一个人的太多。

除了这一对老夫妇,母亲还有另一位师傅还健在。老人在一间小屋子里独居,身体还算硬朗。据说前几年,八十多了还一个人骑车去钓鱼。后来骑不动了,就把自行车送给了我母亲。可人年纪大了总会有点不能根治的小病,需要定期服药。老人虽然没有积蓄,但是退休后福利不错,医疗方面的开销可以全额报销。那么只用每周去指定医院拿药就可以了。这位老人只有一个女儿,可惜女婿年纪也不小了,前几年中风也需要照顾。母亲便每周每周的跑一趟医院,排队取药,然后给老人送过去。这个病基本就是老人病,按常理母亲这个年纪不会得的。时间长了,每次一起排队的老头老太太忍不住好奇问起,母亲只是淡然说,“帮我师傅来取的。退休在家闲着也是闲着,出来跑跑腿也是好的”。旁人听了总是唏嘘不已。

我有两个堂妹,较小的那个幼年父母离异,后来我叔叔死了,她由我奶奶带着。没过几年,爷爷奶奶相继去世。父亲是老大,母亲便把这个小妹妹的户口过到了我家。那一年,我读初中,妹妹刚读小学。堂妹小时候很顽皮,反正我拿她没办法。这几年我回家,看见当年的小妹如今已经亭亭玉立,性格也温驯了许多。她妈妈回来了,现在搬出了我家,不过经济条件不好,正好我家另有一套宅院,借给她们住着在。

我的信用卡有一张副卡在母亲手里,她每个月都用一些钱,但是不多。她对我说,明年你妹妹大学就读完了,现在读大学学费涨了好多了。终于可以供完。妹妹学中文的,毕业后想去小城市教书育人。母亲记得她说过的一句话,“伯妈,我这辈子都会记得你”。

另一个堂妹好多年没有见过。我很小的时候他爸爸死了,她妈妈带着她离开,完全没有消息。去年坟地搬迁,政府追查户口查到了我家,母亲去看了一下,坟头已经很多年没有人拜祭过了。那天母亲给我打了个电话,问起我是否记得有一个死去的叔叔……

迁坟需要一万快,我知道父母的存款这些年是很少超过四位数的。他们都对金钱看的相当淡,除了我读大学那几年帮我存了点学费外,只要有余钱都接济亲朋好友了。突然要拿一万块出来是件很困难的事情。自然而然的,由我出了这笔费用。

因为这件事情,几经曲折找到了失散多年的这家亲戚。据说父亲很激动,对突然找到的侄女也是很喜爱。可她妈妈的情况就不那么好了,因为受到了一些打击,精神有了些问题,已经好几年没出过家门了。整天在家里不敢与人交流。这些日子,母亲总是上门去开导她。居然有了效果。每个人其实都需要正确方式的关爱。

过去的事情还有好多好多值得写,我只是忆起几件,随手记录。而母亲依然年轻,我相信以后会有更多的平凡故事。


每个人都有一个伟大的母亲,我也是这么认为的。