« January 2012 | Main | March 2012 »

February 28, 2012

主题论坛的一些想法

虽然现在 twitter google+ facebook (你也可以把前面的产品换成新浪微博,人人)已经成为网上公众信息交流的主流工具了。但论坛这一形式始终有它存在的价值。至少,在 mailling list 无法成为主流的状态下,产品在网上发布,大多还是需要一个类似论坛的形式为用户提供服务的。当然,google groups 本质上是一个邮件列表,它也把自己称为“网上论坛”的。我说的这个东西,应该大体上归类于 forum 。但 forum 这个词大多数中国人拼不清楚,大家更习惯称之为 bbs (我知道 forum 和 bbs 其实是有差别的)。

当年 ROR 正火爆的时候,有人说用 ROR 搭建一个网站只需要几行代码,没有更简单的了。有人回,不,用 Discuz 搭建一个论坛更简单。

以为然。

但是我始终不喜欢 Discuz 形式的论坛,尤其是它之后的发展。过于花哨繁杂了。我更喜欢 douban 小组那样的简单设计。只不过那个设计过于简单,如果单独抽出来做为一个产品,对于我有许多信息过滤的需求无法满足。

对于为某特定产品服务的论坛,比如为特定网络游戏的用户服务的论坛,我构想的形式大约是这样的。

首先不需要分板块。对于集中话题,按时间整理出信息流就足够了。

twitter 式的,一条条的信息,不分主题和回复的信息流又过于嘈杂。所以还是需要有主贴和回复之分的。由于论坛是集中的特定主题,所以不需要转发(share)的功能。当然,需要有把老贴精彩贴筛选意义的顶贴(+1) 功能下面会再提到。

对于特定需求来说,我们往往需要把帖子分成几个大类,比如新手帮助,bug 报告,玩家经验,帮会活动等等。传统意义上的论坛是用板块区分的,这对用户过滤出自己需要的信息非常有意义。如果取消掉板块(我不想展开谈分板块的负面作用),那么最直接的功能补偿就是打 TAG 。

TAG 等于是作者对帖子分类的建议,其实和分板块是等价的。读者选择板块阅读其实就是选择了特定的 TAG 做过滤。TAG 的不同在于同一个帖子可以同时拥有不同的 TAG ,并且用户还可以自由的添加新 TAG 。这可以参考 douban 对读书,电影的分类。

我设想,系统可以预设一些 TAG ,供用户写完帖子后选择。当然对于新手,最好的方式是减少他的选择。新人的帖子可以自动 TAG 上新手标签。对于有一定经验的用户,则可以允许(默认)他们在自己的 timeline 里过滤掉新手 TAG 的帖子。这对垃圾广告信息过滤会很很大帮助。

管理员则有权限修改、添加、删除已有帖子的 TAG ,这样,可以把更有价值的帖子展现给需要阅读它们的读者。这里提到管理员,而不是由用户自发构建,是因为这种特定主题下的论坛,我觉得更适合有组织的管理信息。

用户的权利是过滤。他可以不看自己不想看的帖子。

任何自己创作和回复过的帖子,都任何和参与者相关。那么对帖子的任何修改,都应该提到该用户的信息流顶。即,你写的帖子,你回复过的帖子,总会按时间次序排到你打开的页面最上方。当然,你可以通过主动关注这个帖子达到同样的效果。反之,这个帖子一定随时间沉没。你也可以通过主动点忽略(google+ 里叫 Mute)来取消你对特定贴的关注。

用户可以收藏他觉得有价值的帖子,收藏不等于关注。这样一个收藏列表相当于一个私人 TAG ,当用户公开他的 TAG 时,这可以认为是一个信息整理的列表。每个用户都可以把一些他觉得有价值的 TAG 放在他的主界面里方便操作。这些 TAG 就是一个个过滤器。你可以认为这就是 google reader 的 share 功能。而不需要用拙劣的顶贴操作来影响其他人的阅读。

特别提出来一说的是,管理员的收藏 TAG 可以叫做精华贴,以及公告贴。公告自然是强制所有人关注的。


我设想的这个系统界面应该是整洁如 douban 小组或 google+ 的信息流的。左边有一系列的默认 TAG 可以开关。右边可以有一些推荐的 TAG 供加入。中间是信息流。按时间排序你关注的 TAG 上的信息流。对于老贴的回复,应该只显示最后没有查看过的几条回复信息,其余的老信息以及太多没有查看的后续新信息都被折叠起来了。帖子不必有标题,但长贴并不全部展开。可以贴图,但不支持图文混排。可以获得单贴的独立链接方便传播到论坛之外的地方。

帖子的正文只支持有限的 markdown 语法,和少量的表情符号。可以用 @ 提到论坛中的其他用户,但文本中的 @名字 并不会直接被翻译成对用户的链接,而只有在输入框中主动按下 @ 后,才会列出提到的人的列表(见 google +)。@ 一个人主要的目的是提起此人的注意,把该贴注入该用户的信息流前端。无论他是否关注了当前贴。

follow 和 unfollow 具体某人在这个特定系统中没有太大意义。这是一个论坛而不是微博。但 follow 此人的收藏是有意义的。

如果有人利用这个系统发布连载小说的话,还需要允许用户对特定 TAG 做逆序排列。这是我对在各种 blog 系统,论坛系统上做连载的最大怨念之一了 :D


以上是零碎想到的一些想法,很多细节不太完整,也没有仔细整理。我真心希望未来可以看到类似这样的论坛出现。

February 21, 2012

开发笔记 (11) : 组播服务

最近一口气招了 5 个程序员, 在他们没有到岗之前,我不想把自己过多陷入游戏实现的细节上面。所以,除了维护一些前面的代码,陆续发现和修复一些 bug 外,我计划再完善一些基础设施的设计。这些基础模块暂时可以没有,如果实现好了又可以直接加入现有系统。这样比较利于后面的工作划分。

其中之一是服务器组播的模块。

先回顾一下前面提到的服务器架构(skynet ),它可以解决各个服务节点的命名问题,以及把消息从一个节点发送到另一个节点的能力。在不改变接口协议的前提下,最简单实现组播的方法就是把一个组命名为一个节点,由这个节点负责群法消息。

其工作原理类似于 UDP 的局域网组播。我还在网易时,实现过另一个类似的服务,见这篇 blog 。这次重新在另一个系统结构上做,有稍许不同。

主要的问题在于,组的管理(加入,退出组)和组本身如何区分。

按道理,组的管理和组播本来依赖同一份数据,即组员列表。系统构架最好是实现为表里如一。也就是说,接口上看起来是怎样切分功能的,那么实际功能就怎样物理上隔离比较好。那么,组播消息和组管理,最好看起来就在一个组的节点上。

但这样,会把“组”变成一个于单点不同的对象。必须对网络框架的 API 做修改。我首先放弃了这种方案。

另一个自然的方案是,把所有组的管理放在一起,由一个具名服务来提供。任何一个节点可以向这个组管理节点发送组管理的请求。比如创建一个新的组,并且把若干节点加入这个组里。并给这个组取一个名字。以后向这个特定名字的节点发送的消息,均组播给所有组员。

这样做比较干净,对组发消息可以和对单节点发消息一致。但组管理服务器和组本身看起来是两个名字。如果遵循表里如一的原则,它们的实现也最好在两个节点上。可是用现有的 skynet 接口,它们两者之间很难通讯。

蜗牛同学说服我,组播将是一个重要的基础设施,可以做在底层,成为系统的一部分。那么脏一点也无所谓了。就是说,表面上看起来它是一个独立服务,实际上是系统的一部分。我接受这个建议,这样就不用纠结于怎么把这个东西设计的更好的问题上了。反正不改动之前的设计,额外加这么一块最不影响开发进度了。

有了这样一个基础服务,下面做场景服务、队伍 API 、聊天服务,都会简单很多。

在没有把这个基础服务在通讯框架上实现出来之前,暂时先在 lua 层的库里面做个钩子,截获这些组播相关的调用,由每个节点自行群发消息也很容易模拟出来。

February 17, 2012

跟踪调试 Lua 程序

我们用 lua 做主要的项目开发语言,一直有同学希望可以在 IDE 里单步跟踪调试 lua 代码。我总觉得这个坏习惯是被 Windows 带坏的。当然,很多年前,我也尝试过编写一个图形界面的 debugger 。后来这玩意半途而废了。因为我觉得没啥实用价值,需要这样去调试 lua 程序的程序员反正也写不好 lua 程序。宁可不要这种工具让 lua 程序员的代码质量能提高一点。

后来过了两年,还在网易时,又有同学要求有一个方便点的调试器。我又写过一个远程调试器,gdb like 的界面,用 C/S 方式调试,并用 GTK 配了一个 GUI 的 client 。主要就是远程设置断点,观察变量等。有兴趣的同学可以看这一篇

这套东西不多提了。今天又有人老话重提。我觉得吧,与其做一个交互式的调试器,不如做一个 trace log 简单实用。毕竟在生产环境,不是有那么多机会让你中断下服务单步调试的。

我们如果可以 log 下需要监控的函数的内部执行流程,以及相关变量的变化。是很容易找到 bug 的。

只要 log 格式规范,很容易另外写一个独立的 GUI 工具,带代码编辑器,可以交互式的重现运行流程。

我花了两小时随手写了一个 trace 工具,还凑合能用。它可以跟踪调用 trace 的当前函数的运行。当函数返回后,自动把 debug hook 取消。

如果再花点精力,可以加上监视 foo.bar 这样的变量。这需要对 table 访问的支持,不过我懒得做了。

有兴趣看看的同学可以从 github 仓库自取

February 14, 2012

开发笔记 (10) :内存数据库

离上一次写 开发笔记 快有一个月了。当然,中间我们放了 10 天的长假。

项目的进展比较缓慢、主要是解决一些琐碎的技术问题,客户端的比较多,服务器这边就是节前的一些 bug 修改和功能完善。大部分工作都不是我自己在做。由于感到人手不足,小规模私下的做了一点点招聘工作。也算物色到一两个同学可以过来一起干的。好久没做招聘工作了,都不知道怎么开始谈。唉,我们这里条件不算好,要求还多,都不好意思开口。

可写的东西其实也不少。今天挑一点来记录一下。

话要说回 开发笔记第六篇 ,我谈过结构化数据的共享存储。这个模块细化其实有挺多工作要做。核心部分我自己完成了,没有用太多时间。然后,有位华南理工的同学想来实习。想到他们学校距离我们办公室仅有十分钟步行距离,我便考虑让 logicouter 同学过来试试接手这个模块,做后续开发。当然,他不能全职来做,对旧代码也需要一定时间熟悉,进度比较慢。

我的规划大约是这样的:

核心部分仅仅实现了结构化数据在内存中的表达。但储存在内存中的数据还不能直接使用。C API 虽然实现好了,但性能比较低。我实现的是无锁的数据结构,采用单向链表保存。检索一项属性值都是 O(n) 的复杂度。这显然是不能在项目中直接使用的。为了提供性能,需要再做一层 cache 。在 Lua 虚拟机中,用 hash 表映射。使得读写数据的速度都降低到 O(1) 。因为我自己对 Lua 比较熟悉,所以这步 Lua 的薄封装还是我自己完成的。实测下来,和原生的 Lua 表访问差距不到一个数量级(3,4 倍左右),是可以接受的范围。比常规 IPC 通讯要快的多,也没有异步通讯的负担。以后编写逻辑代码的时候稍微注意一点就好了。

需要额外开发的工作是,要定义一个数据描述的小语言。类似 C 语言的结构定义。在数据储存中,我没有实现无格式信息的字典类型。 map 的 key 都是在结构定义中预先定义好的,内存中存放的是编号。这一是因为实现简单,而是可以实现成无锁的数据结构。再就是数据结构也能严谨一些,减少 typo (可以立刻检查到)。

一开始我打算直接使用 google protobuf 的协议定义语言。开始做的时候发现意义不大。不如自己定义一个更为简单一些的,切合需求。另外,我们需要更好的多版本支持。大概的样子是这样的:

type Etc {
  int[] object_id = 1
}

enum Gender {
  male = 1
  female = 2
}

type main {
  string name = 1
  int id = 2
  Gender gender = 3
  Etc etc = 4 [deprecated]
}

这只是一个示意,没有定稿。具体也想让 logicouter 同学自己来设计决定。对于版本更替的问题,我想是必然遇到的。暂时我们采用简单的策略,就是只增加新的域,而不修改老的。但是可以在一些不再支持的域上面标记 deprecated 。有这个标记,我们可以在持久化这些数据的时候做一些处理,并能够逐步淘汰老版本的协议。

Lua 层不会直接利用这段文本来分析数据结构,而是从这段文本生成必要的数据结构信息。它将是一张 lua table 。我们可以动态生成并序列化后 cache 起来。当然直接用 lpeg 直接解析这段文本并不困难。只是,lpeg 的内存开销略大,我们的服务器想尽量保持单个 lua state 的精简, 以方便在同一台机器上可以开出上万个 lua state 。

btw,之前我提到过,我希望尽量把单一的事情放在单一的 lua state 里去做。每个 lua state 处理的业务很小,甚至处理完后可以直接关闭,而不需要承受 gc 的代价。lua 的 bootstrap 过程非常之快,调整后,空的 lua state 占内存非常小(可以减少到 10k 之下)。这样,加载 lua 代码甚至是比较大的一个开销。因为 parser 本身是要消耗内存的,至少要多一份文本代码。你可以把 lua 文本代码做预编译,但是那样对开发不太友好(流程较多)。有些代码是动态生成的,也不方便做这个工作(比如利用 lpeg 解析上述 DSL 并生成 lua 表再做序列化)。如果 lua state 间通讯做的比较完善的话,你可以在一个独立的 lua state 中做这些代码动态生成,或是编译加载的工作,dump 出 byte code (适当做 cache),最后传递给最终的 lua state 使用。既然是 BTW ,那么这些并不是这次工作的重点,只是一个优化方向了。

自定义 DSL 的好处是,你可以对 DSL 做解析,对同一段描述做不同的理解。就拿 deprecated 来说,就可以有专门负责数据持久化的模块分析出来做妥善的数据管理。而当前的逻辑运算的模块则可以忽略掉这些域。

在最终的应用环境中,我们将严格保证按生产消费模式使用这些数据。

对于玩家数据,是一个单一类型的机构(就是例子中的 type main )。agent 进程 attach 对应玩家的 id ,得到共享内存对象。只有这个 agent 有权力改写共享对象的内容。其它所有服务都只能读这个对象的数据,包括其它的 agent ,场景服务,等等。其它人对这个对象的修改,都需要用 RPC 调用通知 agent 来实现。共享内存带来的好处是,不需要通过 RPC 调用来同步对象的内部数据。而只需要传递 id 和更改消息即可。

数据持久化工作是额外服务完成的,这个服务是一个特例,它可以读写共享数据体。但是在它写的过程中,没有任何其它服务可以读(包括 agent)。它负责从外部数据库中读出对象的全部信息,并写入共享数据体,然后通知 agent 准备好了。或是另一个用来实现离线玩家数据查询的异步 API 。根据之前的分析,这个共享数据体是可以很安全的做数据快照的,不需要 OS 的支持。只需要顺序遍历数据体即可。这个工作也是由这个服务一并完成的,可以采用定期将数据写入数据库的这种策略工作。

这样,保存玩家数据的外部数据库到底用什么反而不太重要了。Redis 也好,Mysql 也罢,是可以替换的。

重要的是,最后提到的这个玩家数据持久化服务对开发尤其重要。我们可以把它看成是一个自制的内存数据库系统。只是可以不通过低效的 socket 访问。除了备份和读取外部数据库数据的功能外,不可缺少的是遍历已有数据的相关 API。围绕这些可能需要做一个工具集。好在我们现在大体的基础设施已经完成,做这些都比较容易了。


姑且把这个叫做内存数据库吧。如果日后不仅仅想用它来保存玩家数据怎么办?我觉得有个简单的方法可以实现。

type Player {
}

type Npc {
}

type Scene {
}

type main {
  Player player = 1
  Npc npc = 2
  Scene scene = 3
}

我们可以用两层的数据结构解决这个问题,类似 google protobuf 中推荐的 union 的模拟方案。我们在内存数据库中的每个对象都按 type main 保存。并仅填写其中的一个域。以上面的例子为例,要么它有一组 Player 数据,要么是 Scene 数据。在储存空间上不会有太大浪费,也并影响检索效率。只是在用到的地方,需要了解哪个 id 具体是什么类型的数据罢了。

February 02, 2012

Ring Buffer 的应用

这是一篇命题作文,源于今天在微薄上的一系列讨(好吧,也可以说是吵架)。其实方案没有太多好坏,就看你信不信这样做能好一些或坏一些。那么,整理成 blog 写出,也就是供大家开拓思路了。

我理解的需求来源于网络服务提供程序的一个普遍场景:一个服务器程序可能会收到多个客户端的网络数据流,在每个数据流上实际上有多个独立的数据包,只有一个数据包接收完整了才能做进一步的处理。如果在一个网络连接上数据包并不完整,就需要暂时缓存住尚未接收完的数据包。

问题是:如何管理这些缓冲区比较简洁明了,且性能高效。

其实这个有许多解决方案,比如为每个网络连接开一个单独的固定长度的 buffer 。或是用 memory pool 等改善内存使用率以及动态内存分配释放,等等。今天在微薄上吵架也正是在于这些方案细节上,到底好与不好,性能到底如何。既然单开一篇 blog 了,我不像再谈任何有争议的细节,仅仅说说,用 Ring Buffer 如何解决这个问题。


具体点说,我倾向于用 C 语言来做这种偏底层、业务简单的模块。为了减低工作量,可以使用一些成熟的库,比如 libev 等。

类似的库多半提供的是一种回调机制的框架,设置好对应的 IO 异步请求的 callback 函数,然后启动框架的主循环,每个 socket (或别的句柄)可读写时,回调注册好的函数。

把这件事情做的干净漂亮的关键点之一在于数据缓冲区的管理。

拿到需求后,我们应该适当估算我们的程序需要解决多大的数据吞吐量。比如,我们可以假设,一个逻辑完整的数据包在 TCP 连接上,可能最长大约会经过一两秒时间,通过 1 到 10 个包发送过来。整个系统每秒会处理 100M 字节(千兆网)的数据流,那么大约在 10 秒内,处理的数据量大约就在 1G 。

根据对实际业务的估算,这个值可能不到 1G ,128M 就够,也可能多达几个 G 。没关系。我们只是估算出,大致在这个范围内,一个独立的逻辑包一定存在于整个数据流的截段中。我指的数据流是服务程序从网卡上读到的所有数据。

就以 1G 为例,那么这个服务程序只需要开单个这么大的 buffer 就足够了,不必再有任何的动态内存管理。

我们把所有的数据,不论它来至哪个 TCP 连接,都以循环队列的方式,无差别的循序置入这个 buffer。放置的时候,以每次 IO 可读时可以读入的最大字节长度为限。一旦放不下,就折返到 buffer 头部。

buffer 里大概的数据结构是这样的:

[数据长度 连接号 下一块的位置 数据] [数据长度 连接号 下一块的位置 数据] [数据长度 连接号 下一块的位置 数据] ...

另外,内存里开一张 hash 表,记下连接号到数据块的映射关系。如果不想用 hash 表的话,也可以在 buffer 中直接记下连接对象在内存中的地址。

每当一个连接可读的时候,无论读到多少字节,都向这个 buffer 后面追加。并且用链表将其和历史上曾经读过的数据连起来。

同时,可以分析一个逻辑包是否完成。如果没有完成,则继续下面的工作。完成了的话,则利用已有的链表,将分离的数据块拼合在一块连续的内存上。之后,如何处理这个逻辑包,就不在是这个层次上的工作了。

对于处理掉的数据块,可以做一个记号表示废弃即可。我的做法是对数据长度段取反,这样 buffer 在循环使用时,可以判断出下面的内存空间是否可以安全使用。

处理完一个逻辑包后,有可能最后一块数据被切分出去。我的做法时调整这个块,前半块标记为废弃数据块,后半块为待处理数据块。

理论上,如果你的估算没有错且留有余量的话,每次新到来的数据包都能在 buffer 中找到储存它们的空间。因为根据估算,消费速度是要大于生产速度的。不然整个系统都跑不下去。

但如果碰到例外怎么办? 比如有个客户端半个逻辑包发来以后,迟迟不发下半个包。最简单的做法是,碰到 ring buffer 回卷后,碰到那些未废弃的数据块(尚未处理掉),索引到对应的连接,直接 close 掉连接,把没有处理的数据扔掉即可。因为在互联网上,连接本来就是不稳定的。你的协议原本就要处理主动断开连接的情况。无非是根据 ring buffer 的大小和当时的负载情况,设置了一个超时而已。

有兴趣的同学,可以用这个思路实现一下几年前我提到的连接服务器 。代码量应该不大。


另,在更高层的应用上,同样可以使用类似的策略。即循环使用一个 ring buffer 。当 buffer 回转时碰到有对象占用 buffer 拦路时,杀掉对象。对于一些对象比较复杂占用的数据段不固定,对象生命期很短的应用,ring buffer 都有参考价值。例如 3d engine 中的粒子系统。对于要个别需要长期生存的对象,还可以定期复制自己,重新压入 ring buffer 的方式来延长生命期。


使用 ring buffer 的优势是内存使用率很高,不会造成内存碎片,几乎没有浪费(比如传统动态内存分配需要的 cookie)。业务处理的同一时间,访问的内存数据段集中。可以更好的适应不同系统,取得较高的性能。内存的物理布局简单单一,不太容易发生内存越界、悬空指针等 bug ,出了问题也容易在内存级别分析调试。做出来的系统容易保持健壮。


2 月 3 日 补充:

读了几位同学的反馈,发现在几个地方没讲清楚,造成许多疑惑。

一、从 ring buffer 里切分出去的数据块是可以任意合并或再切分的。数据块头上的数据块长度正是为了找到下一块的位置,可以把邻接的两个被标记(废弃)的块合成一个;为了可以任意切分,这里数值上制定的长度和实际占用的长度可能略微不等。实际占用的长度是 4 字节对齐的,而记录的长度则是真实值。比如,记录长度为 6 ,那么在推算下一块位置的时候,需要先圆整到 8 。这样做的话,可以让数据块长度至少为 4 。我们用 4 字节记录长度信息的话,就足够了。更细节的位置还有,我们需要利用连接号域做一个标记,比如空出一个不存在的连接号,表示这个块废弃且无关联连接。实际上,ring buffer 初始化时,就是把整个空间初始化为一个块,并打上可用(废弃)标记。使用的时候就从这个块中一分为二,取其一而用。

经过网友提醒, 这里还需要多设置一个单字节的 offset 域, 记录未处理的数据块头部偏移。

二、ring buffer 中切分出去的块的分配过程是顺序依次进行的,回收的次序则是随机的。初看起来这会导致使用一段时间后,buffer 里有很多空洞。但是, ring buffer 不是一个 memory pool ,并不做复杂的内存块管理工作。如果你想那样做的话,不如直接使用 malloc/free 。也不用为预测的数据量留大一个数量级的空间。ring buffer 在使用时,留足了空间和时间,当 buffer 回转,头指针继续从低地址位移动时,那些先前分配出去的数据块应该都被打上废弃标记了。我们要做的只是根据需要,把这些连续废弃块合成我们需要的程度。万一碰到中间有个别继续被占用的数据块怎么办?那就是上文中提到的,根据连接号强行回收的工作了。