« December 2010 | Main | February 2011 »

January 31, 2011

父亲

我写过很多次父亲。我并不奢望每次能完整描绘出他的形象,向我的朋友们展示出这个已是白发苍苍的老人的全部人格魅力。我曾经写过,他是个程序员, 是个 Geek ,是个手艺人,是论坛斑竹。

这几年,他更多的是在帮助身边的人维护自己的权利。

我爸他老人家在我家这个小区当业主委员会主任已经好些年了,每届都是高票当选。无论哪个物业公司摊上这么个业主委员会,都一定头大不已。每每我回家,都能看见老爸再翻各种法律文件,编写函件。晚上跟我妈闲聊时,总能听到些新鲜故事。我爸是不太主动把搞定了的那些“小事情”跟我说的。不过我能感觉的到跟老人家在小区散步时,街坊们对他的尊敬,当然还包括小区的保安们。

我在武汉住的这个小区,在周边地区算是价格最高的。这导致大部分在这里购房的都是在外打拼的年轻人,或是一些本地的生意人。这样的人群是不愿意管那些个“小事情”,太花精力,值不了回报。若是我,也不会为了配小区的电子门卡多收了几十块钱,或是停车费高出了标准,开发商从小区公众地上划出一小块做经营等等一些小事去具理力争的。向我爸这样的"闲"人不多。

曾经有一次,业委会换届,上面发文件说,主任必须是房产证上具了名业主。嗯,房子是我买了,写的也是我的名字。不过我很庆幸我接下来又从小区一个人手中买了套 2 手房,落了我爸的名字。还吧,这下名正言顺了 :D 今年回来,又在桌上看到我爸起草的文件。反对新的政策。原来,这次改选,候选人资格需要由街道里审核批准了。鉴于,我爸他老人家每次都在选举中高票当选,嗯,你们懂的。

红头文件我就不转贴了 :) 据说全国各地都在搞这个。要把业主委员会这种民间组织正式纳入党的领导下。不过话说回来,我爸也是个老党员呢 ;)


附上老爸写的信函,他正拿着这个在有关部门理论:


XXXX 管理委员会:

XX管[2011]6号文《关于认真做好各住宅小区业主委员会换届工作的通知》(以下简称《通知》)已经收到,经过认真学习,我们对《通知》提出以下意见:

1.《通知》援引的《武汉市物业管理条例》第二十二条属于《条例》“第二节 业主大会筹备组”,针对的是在业主大会尚未成立的特殊时期的筹备组人事安排。本条不适用业主委员会的换届选举。 “第三十九条 业主委员会任期届满三个月前,应当召开业主大会会议进行换届选举。”明确了召开业主大会会议进行换届选举的主体是业主委员会。

2.《通知》第三条要求成立的筹备小组,是《条例》第二十二条错误引用的结果,《通知》第三条不具备行政强制性;

3.《通知》第四条 “根据《武汉物业管理条例》规定,各小区换届选举筹备小组要在管委会指导组具体指导下召开业主大会,及时制订换届选举工作方案并经二分之一以上业主同意后,分别上报钢都花园管委会社会事务管理科和区房产局物业科审批。各业主委员会上报之换届工作方案必须取得管委会批准后方可实施,未经批准擅自组织换届或直接进入操作阶段其结果无效。”据查《武汉市物业管理条例》并无相关类似规定。也没有给予政府机关“未经批准擅自组织换届或直接进入操作阶段其结果无效。”的行政执法权利。

4.《通知》第五条“各业主委员会在工作过程中要保持与管委会指导小组的紧密联系,及时汇报各阶段工作情况,每个阶段工作完成后必须经管委会验收后方可进入下阶段。”我们会随时与管委会指导小组紧密联系,听取指导小组的意见,但是我们和政府机关不存在隶属关系,换届选举也是业主民主自治的自己的工作,不是政府交待的任务,我们反对所谓的验收。

5.《通知》第六条“新吸纳进入小区业委会换届工作小组的人员名单必须经管委会审查批准后方可公示,预备侯选人必须按正式侯选人的2倍上报并得到批准方可公示(正式侯选人以管委会批准为准),工作方案附二分之一以上业主签字方可上报并在获批后方可公示。所有公示必须7天以上。”政府机关对换届工作小组人员和业主委员会侯选人的审查批准、对公示的前提要求于法无据。上报2倍的所谓“预备侯选人”由政府机关进行圈选,更是史无前例的。我们不可能接受上述强制性干预。

业主大会、业主委员会制度是新生事物,他们要维护的自己掏钱买房子带来的公共利益。实行的是民主自治管理。希望政府机关能划清指导、监督和行政管理的界限。在提倡政治文明、依法行政的今天不动用公权力来解决物业管理中出现的利益冲突,我们要求撤消错误的《通知》。

祝新春快乐

XXX 业主委员会

2011年1月30日

January 28, 2011

如何给指定地址空间拍一个快照

需求来自于,我希望可以对 lua 虚拟机中的内容做持久化,却又不希望 stop the world 。这需要利用 os 的功能,对内存做一个快照。简单的 fork 就可以达到快照的要求,但是 fork 会快照整个进程的地址空间,这不是我想要的。

这两天和几位同学讨论了各种方案,比如 memcpy ,比如 fork+exec 传递 shm_open 的 fd , fork 后 munmap 不用的区域等等。最后我认为如下方案相对更满意一些。我并没有实现出来, 写 blog 只是做个记录。

在启动主进程之初,把需要快照的地址空间用 mmap 设置好。使用 MAP_SHARED 方式。这个时候,子进程是干净的,占用的物理内存很小。这个子进程休眠待命。

在主进程中创建 lua state ,自定义 alloc ,指向前面 mmap 的空间。这里这样做的前提是,确定 lua state 占用的空间不会超过预留的空间。

当主进程想做 lua state 的 snapshot ,通知待命子进程。再由子进程 fork 一份出来,并使用 minherit 把之前 mmap 的地址段修改为 MAP_PRIVATE 的,至此,快照完成。

做完快照的进程,可以把 lua state 指针指向那块地址空间里,按部就班的做持久化工作了。

这里需要使用一个锁,保证主进程下达 snapshot 操作指令后一直等待最终持久化进程做完 minherit 的修改完成,这样才确保 snapshot 的时刻是确定的。


这样做是比直接 fork 要繁琐需要,适合 lua state 占用的内存仅仅是主进程数据区的一小部分的情况。且持久化时间较长,如此可回避 fork 后,大量不必要的内存页复制。

如果整个系统都由自己设计,也可以 fork 后调用 munmap 去掉显然不再需要的数据区,不过这需要对进程内其它模块有足够了解,我比较怀疑可以做的好。


我在这方面经验不足,或许还有更简单有效的方案。

January 26, 2011

顿悟?

greader 上读了一篇 真正的学习 。里面有则小故事:

“美国伟大的催眠大师米尔顿•艾瑞克森有阅读障碍,他读书时的多数时间就是在翻字典,因为他不知道字典是怎样排序的,所以每次查找一个字时,他都是从头查起。

一直到16岁,一天他在家中地下室里,还是在查字典,突然间好像一道白光将整个地下室照亮,一个巨大的喜悦从心中涌出,他发现——原来字典是从A排到Z的。

原来,他自己发现了字典排序的奥秘。”

读到这则故事,十分感慨,因为我有同样的经历。

在读书以前,都是我妈教我认字的。但是除了认字,并没有教我学校里的那些东西,比如汉语拼音,比如查字典,等等。一般都是我有不认识的字就开口问。

读小学一年级时,老师教我们汉语拼音,教我们查字典。新华字典有两种查法,一种是拼音检字法,一种是部首检字法。拼音检字法,先按汉语拼音的读音在索引页找到页码,然后翻到那一页再逐个找到想查的字,老师如是说。

我学此法查了不少字,有天晚上,突然发现这样太累了。在索引表里查拼音实在是多此一举。那些字按读音是有序排列的。大体上可以随便一翻,就能在心里估算是翻过了多少还是没翻到。然后根据剩下的厚度再翻一次,多次之后,就可以翻到位置了。如果估算得体,最多也就是翻动 4,5 次而已。

自然,我那时年纪太小,也还没开始学编程。不知道所谓二分检索。不过我还是很欣喜,觉得发现了老师没有教过的方法。很兴奋的就跟我妈讲。我妈也很高兴,好象赞了我两句,记不清了。不过她建议我介绍给老师。

第二天,我把我”发明“的方法介绍给了我的语文老师。记得那天下课后,老师带我去他办公室,让我做演示。同办公室的另一个老师似乎不以为然,说,这样你会翻更多次的。不如在索引表里直接查到页码来的快。还跟我比试了一下。当然,我查字典的速度远不如她。当时我是有点怀疑我的方法是有问题的,不过也没多想,还是很高兴。

其实,成年人查字典很少去查索引表的吧?


想起来,我中学之前的求学经历都是如此。大部分知识都并非被教来的,几乎都是自己悟来的。高中以后,我的成绩一直不太好。考试成绩在班上永远是中流。(我们班 64 人,我的综合成绩在 35 到 40 之间)我会觉得很多知识其实很难,不是那么好理解。比如正弦交流电的有效功率为啥要除个根号2 之类。三角公式每次考试都要推导一下,导致考场时间不够。一考化学就想睡觉,完全记不住那些个东西。

物理老师觉得我高考物理考了高分(只错了一道题)是奇迹,而那年物理卷是有名的难。只有数学老师觉得我天资不错。可是我数学考试一贯成绩不佳,极少满分。得到老师的认同这点我一直还是满奇怪的。

可毕业这么多年过去,有时过年和老同学说起中学学过的那些东西,不少人都忘记了。我却记忆尤新。与我来说,学会的东西再忘记怕是很难的事情吧。只是学的过程辛苦一些。

极不和谐的 fork 多线程程序

继续前几天的话题。做梦幻西游服务器优化的事情。以往的代码,定期存盘的工作分两个步骤,把 VM 里的动态数据序列化,然后把序列化后的数据写盘。这两个步骤,序列化工作并没有独立在单独线程/进程里做,而是放在主线程的。IO 部分则在一个独立进程中。

序列化任务是个繁琐的过程。非常耗时(相对于 MMORPG 这个需要对用户请求快速反应的环境)。当玩家同时在线人数升高时,一个简便的优化方法是把整个序列化任务分步完成,分摊到多个心跳内。这里虽然有一些数据一致性问题,但也有不同的手段解决。

但是,在线人数达到一定后,序列化过程依然会对系统性能造成较大影响。在做定期存盘时,玩家的输入反应速度明显变大。表现得是游戏服务器周期性的卡。为了缓解这一点,我希望改造系统,把序列化任务分离到独立进程去做。

方法倒是很简单,在定期存盘一刻,调用 fork ,然后在子进程中慢慢的做序列化工作。(可以考虑使用 nice)做完后,再把数据交到 IO 进程写盘。不过鉴于我们前期设计的问题,具体实现中,我需要通过共享内存把序列化结果交还父进程,由父进程送去 IO 进程。

因为 fork 会产生一个内存快照,所以甚至没有数据一致性问题。这应该是一个网络游戏用到的常见模式。

可问题就出在于,经过历史变迁,我们的服务器已经使用了多线程,这使得 fork 子进程的做法变的不那么可靠,需要自己推敲一下。


多进程的多线程程序,听起来多不靠谱。真是闲得淡疼的人才会做此设计。但依旧可以使用万能的推辞:历史造成的。

在 POSIX 标准中,fork 的行为是这样的:复制整个用户空间的数据(通常使用 copy-on-write 的策略,所以可以实现的速度很快)以及所有系统对象,然后仅复制当前线程到子进程。这里:所有父进程中别的线程,到了子进程中都是突然蒸发掉的。

其它线程的突然消失,是一切问题的根源。

我之前从未写过多进程多线程程序,不过公司里有 David Xu 同学(他实现维护着 FreeBSD 的线程库)是这方面的专家,今天跟徐同学讨论了一下午,终于觉得自己搞明白了其中的纠结。嗯,写点东西整理一下思路。

可能产生的最严重的问题是锁的问题。

因为为了性能,大部分系统的锁是实现在用户空间的。所以锁对象会因为 fork 复制到子进程中。

对于锁来说,从 OS 看,每个锁有一个所有者,即最后一次 lock 它的线程。

假设这么一个环境,在 fork 之前,有一个子线程 lock 了某个锁,获得了对锁的所有权。fork 以后,在子进程中,所有的额外线程都人间蒸发了。而锁却被正常复制了,在子进程看来,这个锁没有主人,所以没有任何人可以对它解锁。

当子进程想 lock 这个锁时,不再有任何手段可以解开了。程序发生死锁。

为何,POSIX 指定标准时,会定下这么一个显然不靠谱的规则?允许复制一个完全死掉的锁?答案是历史和性能。因为历史上,把锁实现在用户态是最方便的(今天依旧如此)。背后可能只需要一条原子操作指令即可。大多数 CPU 都支持的。fork 只管用户空间的复制,不会涉及其中的对象细节。

一般的惯例,多线程程序 fork 前,应该由发起 fork 的线程 lock 所有子进程可能用到的锁,fork 后,把它们一一 unlock 。当然,这样的做法就隐含了锁的次序。如果次序和平时不同,那么就会死锁。

不光是显式的使用锁,许多 CRT 函数也会间接的使用。比如 fprintf 这些文件操作。因为对 FILE * 的操作是依靠锁来达到线程安全的。最常见的问题是在子线程里调用 fprintf 写 log 。

除此之外,就是要小心一些不依赖锁的数据一致性问题了。比如若在父进程里另一个线程中操作一个链表,fork 发生时,因为其它线程的突然消失,这个链表就可能会因为只操作了一半而是不完整的数据。不过这一般不会是问题,或者可以归咎于对锁的处理。(多个线程,访问同一块数据。比如一条链表。就是需要加锁的)

最后引用讨论中, David Xu 的话 “POSIX这个问题一直是讨论的热门话题。而且双方立场很清楚,一方是使用者,另外一方是实现者,双方互相指责”


突然想到,lua / java 这些 VM 的实现,是不是可以利用 fork 来缓解 gc 造成的停滞呢?只需要在 gc 时,fork 一份出来做扫描。找到不被引用的垃圾,

January 25, 2011

有关英语阅读

不知不觉,我最近两年居然读了许多英文读物。书、手册、论文、blog 等等。前段想翻一点资料原文,居然记错了,以为自己曾在中文版中读到的,后来才发现我以前读的是英文版。

昨天晚上在小店客厅的沙发里窝着,读 Dungeon Twister 2 Prison 的规则书。然后把游戏 setup 好自娱。里面包间几个阿里巴巴的 mm 出来看到我摆的满桌的小模型很好奇,顺手翻桌子上规则书。惊奇的说,这都是英文的怎么看啊?哎哟,不是经过 9 年制义务教育的同学,都能认几个字母的吗?慢慢读呗。其实,读多了也就那么点东西,况且还图文并茂的写的很清楚。文章嘛,关键是条理清晰,用什么语言写的并不重要。

我觉得一切技艺,都是靠熟能生巧的。英语阅读这挡子事,我小时候是极其排斥的。初中的时候被英文老师整伤了。一次寒假作业,老师发了 10 本英文入门读物,让我们每个人都翻译完。当时头都大了,把我过年回家的舅舅都搬出来,帮我翻了大部分,我只管抄译文。后来学计算机,能有中文的资料,绝不看英文的。即使必须看英文的,也自己一点点翻译好,哪怕慢点。

高中时,我在的是个英语实验班,又是大阅读量以及口语听力的训练。完全的逆反心理,从来不做那些作业,只抄同学的。每次英语考试都是全班倒数第一,每次都被老师拉到走廊训话。大学英语课就没去上过,CET-4 考试第一次只考了 58 分。后来怎么过的这四级?全靠我想玩 Allegro ,自己翻译了整本手册。终于对英语语感好一点了,单词量也超过了 1000 :) 当时苦啊,还在用 DOS ,没有电子词典,自己写了一个小软件,把每次翻译碰到的生词翻完字典后记下来,后面翻译再碰到就自动提示。

慢慢的,感觉英语不那么可怕了。慢慢的,喜欢用英文关键词做搜索。搜到的东西有中文的也有英文的。无视语言去读,读过之后,居然常常没有意识到知识是用什么语言描述的 ;(

笑来兄说,语言学习需要在关键期的说法是胡扯 ,深以为然。我们的母语也不是一蹴而就的。同样经过了 10 多年不断的练习,才比较利索。我 2000 年之前一直用右手拿筷,后来改为左手至今,现在右手虽能用筷,已经不那么习惯了。

不过呢,我人还是太懒。拜现在方便的工具,脑子里的单词量还是十分的匮乏。也没有想过要特别去记。毕竟平常用的多的还是阅读,而无需直接和人用英文交流。每每看见一生词,第一反应就是启动词典。看过就忘。即使是做翻译,那个单词在我脑子里的存活时间也不超过一天。所以总是给有道词典提这那的建议:弄点可行的方案可以辅助我真正把单词记住的功能出来。我可是实在的吃过一次这方面的亏,就是没吸取教训。前两个月去新西兰自驾游,飞机一落地过海关就被卡。我琢磨着起因就是因为我背了个大登山包,看行头就像来户外的。海关人员问我包里有没帐篷啥的。我楞是每想起来 tent 是何物。吱吱呜呜了半天,结果人家把我打发到旁边仔细检查。我一转头掏出手机一查,方觉冤枉。拉着旁边一洋鬼子解释半天人家也不听了。据说新西兰人比较担心外来登山者把些外部的生物通过靴子啥户外用品带入镜,顾查的较严。最后,还是给我耽搁了一个多小时。


其实于我来说,同样靠不断练习的技能,除了编程之外,还有写作。

小时候我同样痛恨的还有写作文。每次这种作业都让我头痛不以。我妈因此还十分担心。没想到这十年,不算前些年写的那本书,光在网上写的文字应该也有数百万字了,都快达到我这辈子写的代码的数量级。把想法表达出来,整理好思想自省,变成了件很自然的事情。如何表达真的是件很重要的事。

说起写书,昨天周老师 又督促我写本新的了。我是有这个想法的。上一本回想起来越来越不满意。还有许多同学批评我写了半本自传。唉,主要当年受 Abrash 大神的图形程序开发人员指南 的写作风格影响太深。下一次(如果有的话)不会了。想写本更纯粹的,专注于一个比较窄的技术领域的书。初步想的题材是,关于使用 C 语言构建软件的东西。大部分都是自己沉淀的经验。如果有同学一直都在跟我的 blog ,会发现我一直都在整理思路,收集材料。不过是,始终觉得沉淀还不够,不敢动笔罢了。

另,最近下决心把 LaTeX 学好。排版这种事情,跟写作一样,不在于看起来多漂亮,但求逻辑结构清晰。我十分的崇尚简约之美。唯有用程序式语言把思路的结构关系理出来,方觉舒心。下次不会直接把 txt 档直接交给编辑去处理了。

January 20, 2011

洋画

这几年一直被人怂恿着玩集换式卡牌。那帮玩万智牌的同事不给力,一直没把我忽悠进坑。最近我开始玩魔兽卡牌了。我觉得啊,这玩意和我小时候玩的洋画有那么点相似。不过那时“集换”的概念几乎没有罢了。

小时候一度以为自己生活的小圈子就是整个世界。直到上了大学,和室友们一交流,才发现大家的童年游戏并不那么相同,比如踢毽子,在我们那里女生是玩不来那些花活的,我的水平仅仅是末流。而到了大学踢毽球,同学居然不会踢的居多。在我小学初中的孩子圈中,毽子可是一社交工具,放学只要鸡毛毽一拿出来,认识不认识的男生都能聚在一起比试,有完整的比赛规则。我曾经因为脚法不入流,还狠狠的练习过。

同样成为孩子们社交工具的还有洋画。

在网上流传着几篇古老的帖子,所谓 70 后或 80 后童年的游戏。其中提到过洋画。可在我的记忆里,把洋画放在地上拍,只有极少的小 P 孩才那么玩的。因为洋画太贱了,只到 80 年代末,8 分钱还可以买一版 25 张。输赢一点意思都没有。若要玩这种体力游戏,我们只拍不干胶的贴画(价格要贵许多)

我曾看到另一个帖子,提到过赌洋画的玩法,但是规则的细节却和我玩过的不太一样,缺少许多技术含量。

洋画就是印在硬壳纸上的彩色小画片。一版 25 张, 5 * 5 排版。正面是人物图片,背面是人物介绍。在电视机还不普及的日子里(86 年之前),以评书背景的居多。我见得最多的是岳飞传,也有杨家将的。早期也见过霍元甲题材,以及济公题材的等等。后来电视机普及后,又以动画片的居多。发行时间时间最长的是变形金刚,然后是圣斗士。中间还一度流行过小飞龙。

孩子们把这些画片买到剪开成一张张的。那时,我们那儿几乎每个小男孩口袋里都揣着一寸来厚的一叠,用皮筋捆着。随时需要拿出来于认识不认识的人一战。每个学校门口的地摊上,卖洋画的摊贩们总能保持每天几十版的销量。就好象今天万智牌店可以靠买卡包维持一样。当然,这种游戏有明显的赌博性质,学校是禁止学生玩的,我没问过我父母,估计也是反对的吧。反正我是偷着玩儿的。在长达数年的时间里,每天放学,总能在街区的某个楼道里,聚集着大堆的孩子,围在那里赌洋画。大多相互并不认识,大家认可的只是一致的规则。除了参加游戏的,总还有更多围观的小子。玩到天暗了,就散去,那些围观的,就纷纷找赢了游戏的,“分我一张 XXX 吧”。第二天,又是不同的人在新的地方聚集在一起。我们也有星期天,认识的朋友们聚在某个人家中玩。一般都是楼下喊一嗓子,就能集到人的。

游戏规则是这样的:

每张画片上以文字描述的人名或事件为准,大多数卡片之间有严格的克制关系。以流行最早时间最长的岳飞传为例:秦侩是能克制岳飞的,而岳飞可以克制金兀术,金兀术可以克制赵构,而赵构自然能收了秦侩。只要任意两张卡片再一起,就一定有大小规则。

这种游戏很少两个人一起玩,因为每张卡自有价值。两个人玩,没有人会使用高价值的卡片。通常是 4,5 人在一起。我也经常参加 7,8 人的游戏,一局要进行很久。每一轮,每个人把一张特定的卡放在自己一迭卡的最上面,用拳头握起朝下,说声“请”。等所有玩家都准备后,按准备的次序反向打开亮出(其实保证亮的次序每太大意义,不如同时亮牌,反而留下了一定出千的机会)。如果有人出的卡片可以克制所有在场玩家的卡,那么他就赢得了当局游戏。否则,称之为“绑”,所有的卡片需要堆在中间。因为游戏通常并不在室内进行,很可能就在街头围成一圈,所以也可以由其中一人保管。把卡片反过来迭在自己的卡堆后面即可。“绑”住的卡片一直堆积,只有有人赢得游戏,就赢得了所有历史上大家出过的卡。

当人数上升时,“绑”发生的机会远远大于直接赢得游戏的。所以公共牌堆会越绑越多,非常刺激。一般说来,我们会限制禁止在游戏过程中新买卡片,需要带上足够使用的,如果出完牌,也算退出游戏。(这个规则也可以不严格执行)

我大约玩过 3,4 年洋画,回想游戏的规则演变感觉很有趣。

通常是当下流行什么,洋画就玩什么。时间最长,规则最完善的是岳飞传,然后是变形金刚(其它体系流行时间段都不是很长,每种大约一个学期吧)。到了变形金刚的时代,一版洋画已经卖到 2 角。但是,也有一角钱的洋画同时也在卖,剪开后,大家并不区分单张牌的价值。

规则上,还是以岳飞传为例,基本上就是先分成四大类,金人,宋方武将,奸臣,宋皇帝。大体上,岳飞/韩世忠一系是可以克制金人的,金人可以克制奸臣和皇帝,皇帝可以管住奸臣,奸臣可以搞定武将。同类牌里一般会分出大小来。比如宋朝皇帝主要有五位,按从祖孙辈排下来,自然是赵匡胤最大,赵构最小。至于为何把北宋皇帝搬到南宋故事中来,没人理会。反正辈分够大就行。以至于后来,印刷这些卡片的,不断的出版狼主的祖宗,狼主的祖宗的祖宗,亿万年前的狼主祖宗。把金兀术的祖宗十八代都印出来了。保证你总能出的出更大的牌。

但是,总有一些牌在细节上是有用的。秦侩、张邦昌之流,在功能上类似,但是本身又有大小之分,虽然从输赢概率上讲,总是出同类牌中最大的是最佳策略。但是在小规则上,会有些特例。比如作为最小的皇帝赵构,是唯一可以收了全部奸臣的牌。而其他皇帝虽然比他大,但都只能针对性的管住特定奸臣或武将。

可以想象,在出版商还没有介入规则制定的时候,洋画上印的最多的是那些名人的图案。岳飞传里,岳飞的卡是最多的。但玩家不希望市场上充斥着大量的神卡。自然,岳飞传体系中,岳飞是最没用的卡。为了提升单张卡的价值,大部分卡片都是没有特别多用途的。玩家们称之为“副水”,正规游戏中,是不允许使用它们的。一般说来,一版洋画 25 张里,会有 17,8 张卡片属于“副水”。当年,我的学校门口的地摊上,洋画品众繁多,从画风上看,是不同的地方印刷的。孩子们的乐趣就在于淘那些卡片,看那一版更有价值。而那些副牌,买来后就被人扔掉了。街道上几乎随处可以拣到。

我记得当年一度最有价值的一张牌是杨再兴血战小商河,许多人花上一毛钱就为买这一张卡。对比现在,万智牌把稀有卡藏在封闭的卡包内,凭运气抽到。这种看到再买的方式,要显得仁慈多了。

到现在,我还比较好奇,当年那些繁杂的牌之间的大小规则是如何形成的。每出现一两张新卡,就能迅速的在相互不太熟悉的玩家群中达成一致。每个街区的规则会略有不同,我们在游戏前会申明玩哪个街区的规则。每个老手都非常熟悉自己家附近几个街区的规则之小不同。这些小不同,也导致了街区间卡的交换。

比如当初我常活动的区域,有一张卡叫做“十二道金牌招岳飞”,因为有皇命金牌印在上面,就和普通岳飞卡非常的不一样。但是稍远的地方,就有许多人把它当做普通的岳飞卡使用。我就曾经去找人交换过。从这点上,已经有些现代集换式卡牌的影子了。


每类题材流行过一段时间后,都会被新的题材取代,新的规则不知从何处冒出来,老的卡片慢慢作废。玩家们需要掏腰包少吃几顿早饭,购买新的系列。

到了九十年代初的几年,赌洋画的游戏就开始没落了。最明显的是规则的逐步简化。画洋画的人开始只认某个体系中的三张或五张卡片。(其它不用的卡,买来后都简单撕掉)游戏退化成石头剪子布一样直接。我忍受不了这种毫无技术含量的游戏,也没再玩了。当然据玩的人说,还是有技巧的,正如石头剪子布一样有技巧一样。

再后来,为了迎合市场,街上卖的洋画都直接成版的印成同样的画片,这样单张的卡的价值更是直接下降。我就几乎没再看见有人玩这个游戏了。估计那个时候,没有开发商意识到破坏游戏平衡的严重性吧。又或者是竞争太激烈,自砸了饭碗。


ps. 去年我在一个假期回家。在小区的草坪上,两个 8,9 岁的小男孩跪在地上,面前摆了十多张卡片。我饶有兴趣的凑过去观摩,是万智牌。嗯,居然不是游戏王。

January 12, 2011

网络游戏物品校验系统的设计

网络游戏若要有支持一个稳固的经济系统,服务器底层必须有一个可靠的数据服务。要设计出精简的数据协议可不容易。它需要保证在发生异常(可能是硬件异常,也可能是软件异常)时,不会出现物品/货币丢失,复制的问题。

使用带事务的数据库是一个不错的选择,但对程序员的要求较高。程序员需要仔细考虑每个数据操作如何编写事务才是安全的,还需要考虑数据操作的异步性。这对需求变化迅速,量又比较大的游戏,做的好真的是很困难。

我思考了很久,几经易稿,大约得到了这么一个东西:

数据存储和合法性校验应该分开,独立为不同的服务,这样才容易做的稳固。也就是说,数据服务不必做到完全的完备,简单的去读写修改数据即可。这部分,我倾向于用简单的 key/value 方式储存数据到数据库,可以自己实现,也可以用 redis 这样的现成产品。不必使用事务机制。

但是我们应该提供一个强的校验系统,所有的虚拟物品发放、转移,都应该经过这个校验系统。一切操作都需要经过事后的核对。由此系统来修正数据异常。


简单来说,我们需要保证的是游戏世界中的每件物品都有唯一的拥有者,如果不被玩家拥有,则被系统所有。虚拟货币也是如此。应该避免物品的蒸发(平白无故丢失)或是被复制。

物品和所有者的关系是简单的,单层的,不必实现多层次拥有的树状关系。每个玩家以及可以拥有货币和物品的 Entity 都有独立的帐号(用一个 64bit ID 表示)。而每件物品 Goods ,都有其唯一的 ID (64bit 整数),以及唯一的拥有者。

Entity 和 Goods 是独立正交的两个概念,一个 Entity 不可能是一个 Goods ,反之亦然。Goods 对 Entity 是一个 n:1 的关系。

这样看来,这个数据校验系统的 API 设计就可以比较简洁了。

本来,Entity 和 Goods 可以有相同的 id ,因为它们相互不影响(类型不同)。但为了实现方便,我们让 Entity 和 Goods 公用一个 id 空间,不会使用相同的 id 。

ApplyID(number)

申请一段 ID 备用。这是一个有返回值的 API 。多在服务启动时调用。数据服务返回 number 个空闲 ID 。这样,请求者之后,可以任意使用这段 ID 中的某一个,而不用担心和其他人冲突。一旦申请的 ID 接近枯竭,则可以提前申请下一批。0~1023 为保留 id ,通常 0 表示系统。

CreateEntity(id)

创建一个 entity ,赋予它一个空闲 id 。如果 id 是正确的通过 ApplyID 得到,这个 API 通常不会调用失败。

CreateGoods(id)

创建一个 Goods ,赋予它一个空闲 id 。它的所有者,默认为 0 ,即系统。

ExchangeGoods( { entity1 , funds , goods[] } , ... )

这个 API 接收若干组数据,每组数据包含 entity 的 id ,货币 funds 数量,以及它可以获得的 goods

这个 API 用于在几组物品以及货币的所有者间做交换。所有的 goods 的所有者必须存在于传入的列表内。 所有的 funds 总数必须为 0 。例如:

玩家 player1 用 1000 块钱,交换 player2 的编号为 12345 的物品,系统抽取 player1 的 10 块钱税。则可以表达为 ExcahngeGoods ( { player1 , -1010 , [12345] } , { player2 , 1000 , [] } , { 0 , 10 } ) 即,每组数据表达了某个 Entity 在这次交易中将获得什么。

系统发放(凋落)物品则可以先用 CreateGoods 创建出来,再用 ExchangeGoods 来发放。

VerifyGoods( entity , goods [] )

这个 API 用于校验 entity 所拥有的物品的合法性。API 传入他所拥有物品 id 列表 goods[]。校验服务校验完毕后,将告诉调用者,entity 拥有的物品是否有缺失,或是否有冗余。一般说来,再服务正常的情况下,这个校验是多余的。所以可以在服务维护时,离线跑一次。也可以在玩家上线时(或定期)做一次校对。

QueryGoods( entity )

可以获取 entity 所拥有的所有物品列表以及货币数量。这个 API 仅供调试使用。功能上和 VerifyGoods 有所重复。

如果一个玩家拥有的东西过多,可以考虑把仓库和背包分离成两个 Entity ,这样可以减轻 VerifyGoods 的负担(如果需要定期去做的话)


数据校验服务和数据存储服务是独立的,所以数据储存服务中还是记录有玩家对物品的拥有关系。游戏逻辑不应该依赖数据校验服务提供的物品列表,它只是用来保证游戏内的交易系统、怪物凋落系统都是正常工作的。并可以在异常发生时(硬件异常或软件异常),提供一份数据来修复。


1 月 13 日 补充:

关于一个玩家拥有多件相同物品的优化。

其实大多数物品并不具备唯一性,比如血瓶,材料等等。每个玩家都可能拥有多件。这种东西界于货币和特有物品之间。如果每个都为其分配一个 uuid ,可能会浪费大量的储存空间。

解决方法有三:

  1. 对于这个数据校验服务,不记录这些无关紧要的物品。

  2. 当同一件物品达到一定数量,以一定数量和系统兑换大面额 ID 。比如 10 个 id 兑换 1 个表示 10 个数量的 id 。这个方法不用为校验服务增加新协议,只需要在使用方约定即可。需要特殊处理的只是把系统 id 0 特殊对待,因其只换出不换入,就不需要把换掉的 id 进入数据库,写一下 log 即可。

  3. 保留的 1~1023 号 id 做特殊用途(当然从协议上说,不限于某一段 id ,每个 id 都可以允许多份,但不利于做一个简洁健壮的实现),每个表示特定物品。每个 entity 可以拥有这些小 id 多件。在校验服务的实现里,可以优化储存,保存 id 和数量即可。这个方法需要在 ExchangeGoods 里增加 Entity 失去的 id 列表,另外需要为实现做一定的优化。

January 06, 2011

梦幻西游服务器的优化

在历史工程上修补是件麻烦的事情。

前两天说起梦幻西游服务器的优化。这几天我到广州住下来,打算专门花一周时间搞定这件事。由于以前都是网上聊天,只有坐到一起才能真正理解问题。

目前,梦幻西游,只使用单台机器,最高配置 8 个 CPU ,配置 8G 内存。就算最热闹的服务器,也用不完这些资源(大约只用满了 3 个 CPU ,一半的内存)。核心程序差不多就是 10 年前写的,从大话西游延续至今。这两年一直在享受免费的午餐,随着硬件配置提升,现在单台服务器同时在线容量达到一万两千人。观察服务器回应速度的图表可以发现,目前的问题在于,定期会出现反应迟钝的现象。周期性的,服务器回应时间会超过 1000ms 。查得原因在于那个时候,磁盘 IO 非常拥塞。有定期保存玩家数据的服务对 IO 的占用,以及 SA 做的定期备份数据的脚本占用了大量的 IO 时间。最终造成了机器负荷过重。

IO 负荷过重最终怎样影响到游戏服务的性能,这个暂时不过于深入探讨。我这两天主要是分析以有的系统结构,并想一下改进方案。

其实老的系统并不复杂,代码量也相当之小。相关的服务代码仅仅数千行干净的 C 代码而已。一直没有人动它,因为事关重大,牵扯着数百万用户的数据,以及记费流程。无论设计是好是坏,实现的性能有无问题,都让位于稳定。“历史原因”造成的种种,也只能在闲聊时抱怨一句,如果重新设计,肯定不会这样写了。近两年,我越发的对重构这件事情显的兴趣漠然,为何不这样做,为何不那样? 更多的时候都只是程序员们饭局上的聊资。每个系统一旦编写完成,就充满了种种的遗憾。如果它能用,最大的可能就是它就将一直用下去。一切的新想法,留给下一次吧。

对于已经稳定运行了很多年的陈旧的系统,找到好的方法去改造的意义不大。最重要的是,如何对已有系统影响最小的增加一些东西,提高性能。模块间清晰的划分显得相当重要。服务的独立性也是必要的。现在运行的数据服务和记费以及用户鉴权服务居然放在一个服务程序中恐怕是一个大失误。它使得我们把数据读写剥离出来非常困难。

数据服务采用的是一个 C/S 结构。但没有使用数据库,而是直接使用的本地文件系统。整个设计算是良好,但数据服务本身的机制却很糟糕。C 和 S 之间采用共享内存交换数据,这是为了提高 IPC 性能。C 只有一个,就是游戏主进程,而 S 可以有多个。可以并发的提供服务。多个 S 和 C 之间用管道传输命令,用共享内存交换数据。本意是好的,但协议设计是有问题的。因为 C 直接操控数据区,而有唯一性,结果设计时,把数据区的区块管理放在了 C 上,而不是由 S 提供。

举例来说,如果游戏进程(C) 需要加载一个用户的数据,它自己先寻找数据区中的空位,然后通知 S 把这个用户的数据加载到它指定的数据位置。数据区的清理工作同样是由 C 这边做的。这使得 S 不能直接在数据区上做 Cache ,如果需要 Cache 暂时不用的数据(比如一个玩家离线)就得由 C 自己来做。或者额外的再做一个 Cache 服务(这需要多出一倍的内存,以及内存复制的操作)当初这么实现恐怕是考虑到有多个 S 同时为一个 C 服务的需求,但我只能认为是设计欠佳。

结果就是,整个数据服务,无论是读还是写,都是无 Cache 的。Cache 仅仅依赖 OS 来做。对于当初低一个数量级的时候,这没有问题。但在线人数从千级达到万级后,问题就显露出来了。毕竟你为最终需求最更多的定制,越能充分发挥硬件的性能。


下面记录一下我已经实现好的内存 Key/Value 数据库的设计思路。

要实现前几天想好的,只保存差异信息的策略(经实测,可以减少 90% 的写 IO 操作),必须先统一数据读写服务的位置。不能依赖本地文件系统做数据交换。我之前考察过若干内存数据库,比如 Redis ,最终决定自己实现一个。因为我已经非常了解需求,可以高度定制算法,最大发挥硬件的能力。代码量也不会太大。(控制在 500 行 C 代码之内,最后实际写下来,不过 300 行 C 程序)

我们的需求是这样的:服务程序每周会停机一次。每周总共涉及的玩家数据 10 万组。每组数据 4k 到 32K 之间。都是文本数据。可以看成一个 id 到数据串的 key/value 数据储存服务。经估算,总数据可以全部放入内存。数据会频繁更新,更新后长度会改变。

我花了一天实现这个 k/v 内存数据服务。为了最大利用内存,并同时保证效率,以及代码实现的简洁。我采用预先分配好整块内存的方案,把内存切割成 1K 为单位的区块。并用单向链表串起来。考虑到内存 cache 的命中效率。链表指针本身和数据储存区分离。(大多数时候,我们只需要访问链表指针,而不需要访问具体数据)

链表指针采用序号,而非内存地址。这样即使在 64bit 系统上,依然使用 4 字节索引(可以最大可管理 4T 数据,足够了)。单向链表可以比双向链表节省一半的指针操作以及节约少量内存。代价是代码写起来繁杂一点。

所有内存区块分成两部分:空闲区块和已用区块。一开始全部空间都是空闲。一旦向内放入一段数据,就从空闲链表上摘下够用的区块,放到已用链表的尾部。如果 cache 空间满,则从已用区块链表头部移掉一些空间还给空间区块(这些数据区是长久未访问过的)。每次读取一段数据,都将其调整到已用链表的末尾,保证最后才清理。

另外做一个 hash 表,从 id 映射到在 cache 中区块段的头(由于是单向链表,具体实现时应保存上一个节点)。这样可以用 O(1) 时间查询指定 id 对应的数据区,

保存在 cache 中的数据不必在地址上完全连续,这好比磁盘的分簇管理。和磁盘不同,内存的随机访问性能和顺序访问性能差异更小。这样有利于内存空间利用效率。