« April 2011 | Main | June 2011 »

May 31, 2011

游戏开发中美术资源的管理

今天,公司的同事在 popo 群中讨论 svn 管理美术资源的问题。当资源量大了以后,工作起来效率特别低。因为 svn 储存的是压缩过的文件 diff ,对于大文件,计算最终结果的时候比较消耗 cpu 。

我认为 git 会好一些,但是 git 不满足权限管理的需要。不过更换同质工具并没有解决本质问题。就这个,我想了一下。或者应该换个思路,从工具入手,可能会更适合 3d 游戏的开发。当然,前提是,要有足够的引擎开发和改造能力。对现有工具做适量改进。

我希望从模型编辑器入手。这个工具通常是资源处理环节的最底层,直接面向美术人员的生产工具(max maya 等)。资源在这个工具中被转换到 engine 可用的状态,然后在其它开发工具中被加工。

这个工具,或在这个工具之下建立一个层次,制作成 C/S 结构,并直接集成版本管理工具的功能。即,Server 负责收集美术提交的原始资源。最好能直接让美术提交 max 文件,由工具去收集相关的贴图,然后置入数据库。Server 按照 engine 需要,转换制作成 engine 能用的格式。如果要服务于多个 engine 也没有问题。

美术开发人员,通过 tag 去标识他们上传的资源。比如可以自动把作者 id 作为 tag 打上。这些 tag 仅供事后检索使用。Server 同时也负责合并相同共用的贴图等。最终为每个独立资源生成唯一的 uuid 。我想说,这套东西可能很接近 Alien Brain ,但我需要的是和 Engine 其它部分集成的更好的 Alien Brain 。

其它工具在使用资源的时候,一律引用 uuid 。当然,在工具使用过程中,使用者检索资源的时候,是通过 tag 。但底层引用则使用 uuid 。在资源管理的层次的 Client ,除了负责上传资源原始文件外,也负责建立本地 cache ,提交检索请求。甚至提供浏览。一切工具需要加载资源,都通过 IPC 协议去获取数据。也可以退一步,由这个 Client 同步到新版的资源文件,并返回 cache 中的文件名。

当然,最终的游戏也可以通过相同的资源获取协议达到及时网络加载的特性;同样也可以不用这个特性,从由资源管理器最终打包好的资源包中读取。

这个系统设计成和 Engine 以及其它工具尽量功能正交化。适合独立开发维护。本文只是一个思路,设计方案还需要斟酌。


嗯,总结一下需求要点:

美术资源和程序代码不一样。不是每个人都需要一份完整的数据仓库的最新版镜像。需求只在他所维护的一部分素材以及当前项目需要的一部分。而整个美术素材仓库往往很大,没必要同步同步下来。这是和 svn 这样的版本管理工具处理的问题不同的。

美术资源原始素材和最终运行环境用到的数据不同,好比源代码和目标文件。协同开发时,程序员需要其它程序员的源代码帮助编译调错。但美术人员几乎不会用到其它人员的原始文件。因为场景中的一颗树和一张桌子中间没有什么会相互影响的东西。

美术资源大多交叉关联,并非树状结构。一个模型很可能由许多文件构成,但开发人员往往只关心顶层的个体。且在使用这些个体的时候,对它是什么更关心,对它在文件系统的那个位置不太关心。tag 会是对人更友好的检索方法。

开发工具多为自行开发,或有二次开发需求,以适合自己的游戏项目。集成少量资源管理接口难度不大。

May 27, 2011

聊天信息加密的乱想

信息加密技术已经很成熟了。不过想把加密信息伪装隐藏在看似明文的信息中的工具我还没有见到。

我的意思是,监听方完全察觉不到有密文在传输的情况下,把加密信息传输给对方。我记得有工具可以在图片中隐藏一些信息,即使图片经过扫描,隐藏在其中的密文信息依然可以读出。

我能想到的方式有好几个。一是在正常的聊天通讯中,通过对语句的语法分析,找到一些常用,却可以同义替换的词,或是常见的由于拼音输入法输入错误的同音字。做有规律的替换。每个替换可以编码 1 bit 的数据进去。换句话说,一个别字相当于 1 ,一个可以错的字写对了,可以编码为 0 。为了让别字不那么多,可以定规则为每句话的固定次序的某个字包含有额外信息等等。这些规则可以扩展开。

也可以选用另一种方法,找到一篇共享的长文,截取出若干段落,每个小段文字为一段编码(这篇文章其实是密码本),例如,一篇文章被切份挑选出 1024 短句的话,每句就可以为 10bit 信息的编码。

后一种方法没有前一种方法的伪装性好。不过更容易实现。

设想有一个工具,可以 hook qq 的聊天。双方都启动这个插件,就可以在聊天的信息管道之上架设一段低带宽,但秘密的信息通道了。用户只需要把想传输的文字事先写好,然后谈谈天气,玩玩暧昧,信息就夹杂在那些“呵呵,哦,嗯”中间发过去了。这些密文经过传统的加密手段加密,压缩,添加上校验码后,由同样的算法解码出来。

虽然这样在正常的聊天文字中能携带的信息量很少,不过非常安全。

May 25, 2011

电子书平台及英文阅读

这个想法是大约一个月以前细化的。类似的想法我在 97 年就有,当时网络并不普及,我为之做了一个单机版的 DOS 小程序。放在 cfido 上传播,以及放在个人网站上,有零星的几个用户。

我设想有这样一个工具,可以辅助我阅读英文小说,或是论文。它不应该是一个简单的词典,我不喜欢在阅读时有过多的交互。我希望作为阅读者,只是单方面的输入信息。那么,一个好的工具应该了解我的熟悉的单词领域,知道那些对我陌生的单词。并且明白,如何解释他们我可以明白其含义。

有时候,我只需要一个简单的中英文词汇对应关系;有时候我需要更多的解释。

一个好的辅助工具,能做到,在我需要简单解释的时候,在生词后面打上括号,写上对应的中文词。并在我尚未遗忘之前,同样的词不再注释。对于复杂的词汇,我希望它能排版在同一页的边侧,我第一感觉它应该在的地方。而不是让我费力的移动一下鼠标选中。

软件应该学习我的记忆习惯,知道我需要提醒多少次才能熟悉一个单词。它了解我的过去,我读过哪些书,那些书里的核心词汇我应该随着阅读而掌握。较少的用我认识的单词干扰阅读版面。这,都是计算机智能应该做好的部分。

当我拿起《冰与火之歌》的英文版时,需要这么一个工具的愿望又强烈的出现了。虽然我阅读计算机相关的材料已经不太需要词典的帮助。但文学作品完全不同,每个自然段落里都出现不认识的词简直让我崩溃。

我以为,这样一个阅读工具,会是电子书领域的一个好的切入点,虽然有英文阅读需求的群体远远小于阅读网络YY小说的。我和有道词典的同事谈论这个点子,因为这是他们的本行。我觉得有必要写这篇 blog 整理我的思路。

我设想,这是一个阅读平台。交给用户的可以是 web 界面、ipad 工具、windows 上的客户端,等等。它们有一致的使用感觉最好。这个平台一开始可以只支持用户上传材料。无论是 pdf 还是 txt 还是别的电子书格式,一律在上传后保存在服务器,并转换为特有的格式,方便统计分割里面的文字,以及排版。对于用户,他们把他们拥有的电子书储存在了云端,并允许同步到自己的设备上。

每个用户自己上传自己的书,不和其他人自由分享。这回避了版权问题。它和臭名昭著的百度文库不同。用户也是上传自己的(多半是无版权的)电子书。但平台并不会分发它们。它更像是一个网络储存空间而已。当然在实现上,我们会 cache 这些数据。如果两个用户上传的数据完全相同,则只储存一份。甚至在 client 实现时,可以分段做 hash ,一旦发现 hash 值相同的文字,连上传带宽都省了。

用户在云端建立起自己的书库,平台给予它们一直的阅读感受。更重要的是,对于英文阅读,平台会学习每个人的英语知识领域,做最好的辅助。这样,用户对平台会建立起依赖性。btw, 我觉得大多数人的英文单词认知领域是有相似性的。他和他受的英文教育有关,更和他曾经的阅读经历有关。读过同一本书的人会认识差不多类似的一组单词集。

当用户有了粘性后,这个平台可以考虑收费的形式售卖电子版的版权读物,也不限于英文版了。作为增值服务,可以帮助用户订阅阅读英文的 RSS 。

这个平台的建立之初,应该是公益性的工具。它可以帮助民众启迪智慧,我们需要直接阅读更多的外文的一手资料,而不是被人咀嚼过的东西。它应该是慢慢培养用户的版权意识和支付习惯,就像 apple 的 app store 做的那样。让平台了解用户,用户对平台产生依赖性,英文阅读是一个好的切入点。或许有人会嘲笑这个需求过于小众,但毕竟是有人需要的。而且到今天为止,我没有见过哪个词典软件做的足够好用。

把词典单纯的放在词典的定位,是否过于局限了?词典大多运用环境就是阅读。首先是阅读,它才是主体需求。

May 20, 2011

扯两句电厂经理

不知道我的读者里有多少桌游玩家。昨天我写那篇软件项目需要很多人一起完成可能是一个骗局 莫明其妙的就想到了 Power Grid: Factory Manager 这款游戏。

这是款我个人比较喜欢的偏计算类的游戏。玩家需要安排 5 个回合的工厂生产计划。购买机器、扩建仓库、发电。玩家需要支付电力成本,如果人手不够,需要雇佣临时工。偶尔,会因为场地不够扩建厂房。但是游戏只有固定 5 个回合。结束后,看谁赚到的钱多。当然,固定资产是不折现的。

初学者往往会一味的扩大生产规模。希望每个回合能比上个回合生产更多的产品。但是,玩过一两盘之后,就会发现,其实大多数情况下,到最后一个回合,扩大生产规模经常是入不敷出的。到第 5 回合开始采购的时候,一开始定下收益最大的采购方案,却发现利润是负的。然后削减经费,发现收支平衡;再削减,发现有的赚。最终发现如果什么都不采购,甚至关掉上回合采购的机器有正收入。

这个时候就该反思,上个回合雇佣的用来这回合采购的临时工其实是浪费了钱,上回合或许就应该减少开支,反正机器这次都停工了……

当软件开发遇到瓶颈时,我们很自然的想到,加几个人就好了。当然要加能干的人,属于领域知识的人,能干活的人。OK ,一切妥当后,团队磨合了,项目最终完成了,虽然比预期时间多了几个月,但最终完成了。

上一篇 blog ,在 reader 上有人反馈说,对于有时间限制的软件项目,个人精力有限是大敌,不得不增加人手,容不得时间你一两个人折腾。我其实想说的正是这点。表面上看,经过周密的组织,慢慢的增加合适的人手,项目终于做完了。表面上看起来,如果不增加人手是做不完那些浩如烟海,枯燥无味的工作的。但实际上还有一种可能,如果当初你决定不增加人手,一个人慢慢来,其实也能按期完成这看起来不可能完成的任务。

就好比,我玩了一盘电厂经理,完成了 5 个回合后,反过来发现,在第 3 个回合开始我就不应该扩大厂房,购买新机器,一样可以赢得游戏一样。增加的那些机器产能,让我不得不扩建厂房、优化人力、支付成本,最后也没多赚到钱。

May 19, 2011

软件项目需要很多人一起完成可能是一个骗局

本文的标题只是一个猜想,并不是我坚信的观点。事实上,我这几年自觉学到的重要东西之一,就是如何在开发过程中分工,如何信任队友开发的组件,如何组织许多人做同一个项目。

可是,如果这是一个骗局呢?那也未尝不是一种可能。

这个世界上我们需要做的软件可能没有太多真正庞大到需要很多人合作才做的出来。需要配置产品经理,需要设计人员,需要前端开发,后端开发等等。

更多时候,你需要很多人一起来完成仅仅是因为别人都这样在做。或者是,你缺乏某方面的专业知识,需要属于这个领域的人。又或者是有些工作很枯燥,你需要一个只是打工的人来帮你完成这些枯燥的你不想干的部分。也可能是你的老板觉得你进度太慢,觉得必须想办法加快进度,他觉得增加人手或许可以……

如果你真的一个人做一个别人看起来了不起的大项目,结果要么就是被膜拜(几率很小),要么就是被嘲笑成小作坊思维。你可能也很累,觉得在做那些不得不自己做的体力活时,盼望有人帮你解脱一下。

实际上,如果你抱着己所不欲,勿施于人的思想,怎么能把自己不愿意干的活推给别人呢?当是一个团队开发的时候,这块工作不属于我就成了一个很好的借口。其实,如果一个工作过于枯燥繁琐,其实说明的是没有找到好的方法让机器代劳而已。

如果缺乏某些领域知识,对于程序员,更重要的是自己去学习,掌握它。

产品经理?如果你爱你做的软件,你就是他最忠实的用户,你比所有人都明白你需要这个软件有什么功能,怎样才好用。

如果打一开始,你就打定主义自己包干所有的活,就好象 google 当年,因为不懂 HTML ,就设计了那么一个阳春白雪的首页,用 GIMP 随便做一个 logo 一样。如果你给自己断了后路,任何活都没有人代劳,你自己就咬紧牙关自己去做了。其实整个项目的总体开发时间,未必比一个好的团队来开发长多少。当然,比一个糟糕团队花的时间肯定要少的多。

成功率也未必很低。软件质量你心里明白,它只取决于你自己的能力。

我知道,开发软件全部由一个人亲力亲为听起来很糟糕。只是,大多数人都不相信,团队开发或许更糟糕。把一个项目加到足够多的人手后,看起来就勉强可以运转了(我听说的谣言: IBM 开发维护一个软件就是用一个集团军的),不会有人会相信其实所有事情一个人来做就够了。

只是随便想想而已。

我觉得吧,如果你真打算一个人做点东西的话,最大的敌人不是你个人的精力不够;而是不够坚定,总想以后会有人进来一起干。

你获得的好处是,不会有人跟你争论设计方案,不会有人讨厌你的编码规范。如果你发现做错了,通宵改掉就行,不用担心其他人的开发受到影响。过程本身,无论是苦是乐,都是值得回忆的记忆,乐趣不在于最后的结果。而且,做完了,东西再烂,你也至少拥有一个用户。

May 18, 2011

Bitcoin 的基本原理

昨天读到了 Bitcoin 的中文介绍,觉得非常有意思。不过上面这篇文章解释的非常不靠谱,我花了一晚上去Bitcoin的官方网站 仔细研究了一下,总算理解了其原理。感觉非常有启发,尤其是对虚拟货币的流通和发行有许多借鉴意义。今天写这篇 Blog 理一下。

什么是货币呢?货币就是商品(包括服务)交换的媒介。现在我们通行的货币是由有信誉的银行发行的,基本上是由其信誉来担保的。只要用的人都认可,那么我们就可以用它来交易。货币有一定的保值特性,我把我的劳动/服务/所有的商品换成货币后,银行担保我在日后的某一天,我还可以用它交换会差不多等值的东西。这个保证的前提是,银行不会滥发新的货币以及大家都信任这一点。

以前,我们用贵金属做货币。因为贵金属产量不高,货币新增加的速度有限,而经济体在不断增大,市场需要更多的货币来让商品尽量的流通。有需求就有价值,从这个意义上来说,贵金属本身制造别的东西具备的价值是次要的,经济体需要货币来流通商品这个需求才是主要的。而贵金属产量有限,且曾经流通着的贵金属货币由于各种原因会退出市场,那么即使是新造的贵金属货币也有同样甚至更高的价值。

Bitcoin 为什么保值,BTC (Bitcoin 的货币简称)存在于一个庞大的 p2p 网络中。使用 Bitcoin 的群体公认了一种算法,这种算法在现今的条件下,每小时只会新产生大约 6 组新的 BTC ,目前一组是 50 个。也就是说,这个世界上,每个小时大约只会产生 300 个 BTC 。这个产量还会由网络自动调整难度来限制产量。你没办法通过修改所有人的 Client 的算法及参数(client 是开源的)来加快货币产量。伪造的货币会被网络丢弃(除非你可以控制大部分网络节点)。

BTC 本身有什么价值?

BTC 的价值就是交易渠道本身。一组新制造出来的 BTC 提供了把旧的 BTC 从一个帐户转移到另一个帐户的数学保证。这个安全保证背后的代价是大量的计算力。生产这么一个安全通道是需要消耗大量能源的,所以整个 BTC 用户群体,奖励那个造币者(目前是 50 BTC)。

简单说,我的理解就是,现在世界上所有的 BTC 背后都是用运行计算机的能量产生出来的,它们的总价值,(到现在一共有大约 12w 组 BTC 被生产出来,每组 50 个,市场价格大约 7.3 美金一个),应该是少于消耗掉的能源的总市场价值的。不过我想,用于生产 BTC 的能源大都原本就是不用也被浪费掉的资源。


一个没有中心节点的“银行”是怎么让大家信任并工作起来的呢?

答案是,这个 p2p 网络上每个节点都记录了 BTC 诞生以来的每笔交易的详单,并从中可以推测出每个 BTC 唯一的属于谁。这样你接受一笔交易时,就能知道别人给你的钱是不是合法的。

从最基本的说起:

每个帐户其实就是一对公私匙,有私匙的人就是帐户的主人。如果 A 要给 B 转一笔钱,A 就把钱的数量加上 B 的公匙,用自己的钥匙签名。而 B 看到这个签名,就可以了解,的确是 A 转给了他如数的 BTC 。

那么这笔交易需要一个见证人,担保交易发生过。这样,以后 B 想用这笔钱的时候才是合法的。担保人就是整个使用 BTC 的网络。

A 在发起这笔交易的时候,必须把签过名的交易单尽量的广播到 p2p 网络上,最终会让每个节点都知道这件事。B 从 p2p 网络上不断的收到别人的确认信息。当它收到足够多的确认信息后,就认为 A 的确发出了这条交易单。这以后,B 就可以自由使用这笔钱了。

当 B 使用 A 转给它的钱给 C 时,也会广播给足够多(最终所有人都收到)的人让他们担保。每个担保人只有确信 B 有足够多的钱可以支付的时候才做确认。本质上,BTC 网络并没有记录每一块钱属于谁,它记录的是从诞生起到当前的每一笔交易,并推算出每个帐户里有多少钱。任何人试图确认一个交易单时,它需要确认的是转出帐号上有没有那么多钱。

Bitcoin 需要解决的核心问题是,如何避免一笔钱被花两次。

整个帐单序列是一环套一环的。每个人在完整的全局帐单上签上新的一笔的时候,都需要利用前面信息生成后面的。这个帐单序列被称为 chain of blocks 。每个 block 里面包含有若干条经过确认并 hash 签名 (难以伪造) 的交易记录。每个 block 都和全局表上的上一个 block 有关联。每条帐单都会通过 p2p 网络最终被转发给制造新 block 的节点上。

这个制造新 block 的过程被叫做 mining ,制造新 block 就是把最近收到的帐单打包在刚制造的 block 里。这个打包的过程即制作的过程,只有极其稀少的几率被制造成功。(你可以理解成把新收到的帐单合在一起,一次成型不可修改,如果制造失败就要再来一次)一旦制造成功,你就把新的 block (被认为是对老的全局 block 链的延续)广播出去。

因为是 p2p 网络,可能有许多人都在同时制造新的 block ,但有一个排序机制保证只有最优(最难,花费最大计算时间的)的那个新 block 被网络群体接受,挂在全局的 block 链上。重复一次,整个 BTC 网络只有一个全局帐单表,每个节点都完整的保存有一份。

这个全局帐单表会越来越大,block 链越来越长,在最新的部分,必然有许多分茬。这是因为 p2p 网络的 mining 过程是分开并行进行的,每条新帐单也不能立刻广播给所有的节点。每个 mining 的节点都有责任把他新收到的,在他认可的老的全局帐单上不存在的帐单,合在他准备制造的新 block 中。一旦新 block 被制造出来,就立刻广播出去,争取得到更多人的认可。主要是得到那些想 mining 的人的认可,这些人会在这个 block 的基础上制造新的 block 。

如果 p2p 网络过大,交易帐单不能尽量的迅速的广播到全网络。就会出来 p2p 的网络的局部保持有小群体共同认可的一份全局帐单。多个全局帐单的分支同时发展是有可能的。因为每个小群体都可能认为他们看见的那部分更长更有效。但是,只有有人发现另一条分支更长,它就会转换阵营。所以,有一定的可能性,你的帐单被一个小群体接受,但在一段时间后,被更大的阵营抛弃。

不过,算法参数决定了,新的 block 产生速度很慢,如果你的帐单被多达 6 个人确认,基本上就保证了它合并到的那份全局帐单,就是 p2p 网络全体认可的。


既然生成新 block 费时费力,制造出新 block 的几率好象买彩票中大奖,还有那么多人去执行程序计算出新 block 呢?答案是,每个制造出新 block 的人,都有权利构造一条帐单声明老天给了我 50 BTC 。这个规则是被所有 BTC 用户共同承认的。把制造 block 等同于成挖金矿 (mining) 只是一个形象上的比喻。实际上,没有人可以把金子挖出来囤积。每个新 block 必须包含全局表上的上一个 block 的 hash 值,BTC 网络自我调节难度,让每 10 分钟大约产生一个新 block 。如果你 10 分钟内没制造出新的 block ,差不多就是说你前面 10 分钟干的活白干了。从最新版的 block 继续演算。

所以更恰当的比喻是买彩票。一个每 10 分钟开一次的彩票。你不停的花钱买,10 分钟内开中了就是你的,开不中先买的都作废,然后下一轮。


数学上怎样保证 mining 的过程需要消耗大量的 CPU 时间?并只有很小的几率成功?

这里用到一个叫做 Hashcash 的系统。它最早是为了改善 email spam 的问题被发明出来的。

就是给一段特定信息(比如这封 email 是从谁发给谁)加一个特定的 hash 头。这个 hash 头需要大量的 CPU 时间计算出来。发 spam 的人没有那么多 CPU 时间为群发的每一封 email 计算一个符合要求的 hash 头,所以认为有这个合法 hash 头的 email 不太可能是 spam (花了 CPU 时间在上面)

这个算法就是,为你想保护的信息,找到一串数字,附加上去后,使用某种公认的 hash 算法,比如 SHA-2 ,算出一个 hash 值。如果 hash 值由一长串 0 打头(具体多少个决定了难度),那么就成功了。

为一段信息,找到这串数字,在目前来说,除了暴力尝试没有什么好的方法。也就是随机更换数字,换一次就 hash 一次比对。在一个可以预期的尝试次数后,一般都能找到想找的数字。

每个想 mining 赚 BTC 的人,不停的从 BTC 网络上监听信息。如果有人发布了新的合法的 block ,他就合并到本地的全局表里。并重置自己的计算过程,从新得到的 block 开始。如果有新发布的交易单,也记录下来。不断的把最新的 block 的 hash 值、新收到的交易单,自己获得 50 BTC 的那条奖励单合并在一起,计算 SHA-256 ,看看结果是否满足条件。一旦满足,就把这个新的 block 广播出去。

当足够的人认可它,(以它为基础计算后面的 block ),他也就获得了那 50 BTC 。


为了匹配 BTC 的经济规模。所有的 Bitcoin client 都被设置成,每 210000 个 block ,生产新 block 的人被认可凭空获得的 BTC 数量比之前的少一半(如果这个时候他还在包内写上自己获得 50 BTC ,其他人不会确认他的这个 block )。这会让 BTC 的总量增速变缓。新的 block 产生的速度是由难度来调节的。这个难度会由 p2p 网络根据最近生产 block 的速度自动调节。所以即使日后计算能力增加,也能保证大约 10 分钟一个的速度。

而且,随着生产新 block 的收益减少,愿意贡献自己的 CPU 来 mining 的节点也会变少。(如果减少太多,只需要减少难度即可)

最终,p2p 网络不再凭空制造出新的 BTC ,这个时候制造新的 block 的动力是什么呢?那就是交易税。因为没有什么人愿意生产新的 block ,发起交易就变的困难。(没有 block 可以容纳交易单)希望交易被确认的人可以声明,如果有人制造出新的 block 接纳他的交易单,他会支付一小笔交易税给他。当许多人都这么做的时候,制造 block 又变的有利可图了。只不过,直接上不再有新的 BTC 诞生,只是在这些 BTC 用户之间流通。

总有一些 BTC 会消失,主要是那些帐号的私匙丢失了,没有任何人可以转移走帐户上的钱。不能流通的货币就不是货币了。但最终 BTC 总体会达到一个比较大的规模,准确说是两千一百万个。但 BTC 本身是可以切割的,比如你可以支付给别人 0.01 个 BTC 。所以 BTC 本身会升值,总数也一直够用。


如果你觉得这篇文章对你有用,可以捐赠一点 BTC 给我玩玩。帐号是 1CDPtAPKf3EKLby85nnR35yBwPPsqHn8Cr

这里有人免费派 BTC ,每个 gmail 帐号给 0.02 BTC 。

May 11, 2011

闲扯几句 GC 的话题

今天跟同事闲扯的时候谈到 GAE SDK 刚刚支持了 Go 语言。这对于 Go 语言爱好者来说是个让人欢心鼓舞的消息。几乎所有人都相信它能比 Python 的执行效率高一些。从开发效率上来说,不会比 Python 差,那么 Go 语言的支持可能是比 Java 更好的选择(开发效率和执行性能的均衡)?

这也让我想到了前段在北京时跟 Douban 的同学聊 Go 的事情。那天,有同学问起 GC 的事,是个 C++ 程序员。C++ 程序员对 GC 知之甚少是可以理解的。我大约花了 10 分钟介绍简单的 GC 算法(:根扫描清理、三色标记、移动或不移动内存等等。那段时间我正在研究 lua 的 gc 实现,刚巧看了不少文章。

那天吃饭的时候,Davies 同学说到他做的 beansdb 的 proxy 用 go 实现,GC 的代价使他不得不考虑优化。我回来翻看了 Go 的代码仓库,roadmap 里,开发小组的确也有改进 GC 实现的计划。从某种意义上来说,python 的 gc 的方案不失可取之处。python 采用引用计数来立刻释放可以释放的内存,然后用扫描清理的方法来清除循环引用的死对象。这样可以减缓运行过程中的临时内存增速。甚至于,你可以在编写代码时刻意回避循环引用,像 C++ 那样管理内存。

这让我想到,其实 C/C++ 那样的手工管理内存和大多数其他现代语言支持的自动 GC 方案,其实培养的是用户(程序员)习惯。从性能上讲,各有优劣。引用计数方式并没有想象的那么廉价,扫描清理的 GC 算法也不至于拖慢系统。还有 C/C++ 惯用的有着无比性能优势的 stack 内存使用模型,stack 足够大,大到可以假设 stack 可以安全的一直使用,其实有它的局限性。像 Go 里面,把 goroutine 看成是廉价物的做法,如果按传统 C 的 stack 内存模型的话,就必须考虑 stack 的大小限制了。就算是 C/C++ 程序,老练的程序员也知道回避栈溢出。

我这几天用 C 写了一个小模块。可能早就被人无数遍造过的轮子:分析一个 path 路径字符串,划简里面的 ./ ../ 。程序最后并不长。几百行代码。各种例外让人写的很纠结,还需要设计各种测试案例来检查每种特殊情况,程序是否能正确处理。

我不由得去想,如果我用 Go 或其它现代语言会怎么干这件事情。我想,我会自动调用 strings 模块内的 split 函数,把原始字符串按 / 切分开,变成若干子串序列。然后分析其中的 . 或 .. ,把这个序列划简掉。加起来恐怕不会超过 10 行程序。

按这个思维,我完全可以用 C 实现相同的东西。也不至于纠结到在一个 buffer 上来回出来那个串。但是我在写 C 代码时没有这么做。为什么?我想是一种编码习惯吧。我在 C 程序员的角色下,想使用 O(1) 的空间,O(n) 的时间解决问题。不想分配临时对象然后最后释放它们。string 不是 first-class 类型,我无法把它当成简单的值一般使用。我在一个比较低的层面看问题,我计较每个字节内存的使用。

同样,如果身份转变为 Go 程序员,我会把那些负担转嫁给 gc 给编译器,祈祷他们可以做的很好。无形中,我的代码临时分配了许多对象,把数据复制转移到低层次的模块(strings 模块)去处理。其实,在 Go 里,你还是完全可以采用 C 语言中同样的算法解决问题。

回到 Davies 的问题,我想,如果仔细推敲的话,或许可以不用 unsafe 模块中的方法去直接调用 malloc/free 。做一个 buffer 池,应该也能让程序的内存空间不至于暴涨。我们用 lua/python/go 这些内建 GC 的语言编写程序时,有心留意,总可以让临时对象不至于增加的太快,这样就能减少 GC 的负担。但是少有项目做的到。因为语言给你的思考方式决定了你怎样编写程序。

有另一个有意思的比较:

C++ 的 STL 看起来是很高效的,如果你仔细阅读过 STL 的源代码,你更会同意这点。可是,少有 C++ 程序员肯承认,使用 STL 拖慢了他们的程序。真正的 C++ 程序员鄙视那些对 STL 拙劣的模仿,他们叫嚣,要使用 std::vector ,不要重造轮子,少用 C 风格的数组。还有 std::algorithm 里的那些东西……

若干年前我考察过我经历的两个功能类似的项目,一个是用 C 风格的 C++ 写的,一个是用 STL 风格的 C++ 写的。hook 内存管理器我能发现,C 风格的项目中内存分配的频率远远少于 STL 风格的项目。大约只有 1/3 左右。从那时起,我相信,C++ 项目普遍会比 C 项目稍慢一点。根源不在于语言编译器生成的目标码的区别,在于语言带给程序员的思考方式。所以也不必迷信那些语言性能评测报告。那些精心优化过的短小代码说明不了实战中的问题。

May 05, 2011

写了一个 proxy 用途你懂的

用 linode 有一年多了 ,除了架设 blog ,我也折腾点小程序放在上面跑。在互联网上有一台自己的主机,对于一个程序员来说,还是很有必要的。当然这 vps 绝对不能选国内的,原因你懂的。这样,附带的一个好处就是可以用 ssh -D ,相信许多同学都喜欢用。

没来由的,我想自己写一个小程序,完成 ssh -D 一样的功能,不过,不走 SSL 加密。当然也不能走明文,由于众所周知的原因,明文通讯很容易引起奇异的连接断开或长期超时的 bug ,此 bug 绝对不在于你的程序。网络连接永远不是 100% 可靠的嘛。

我花了两天实现我的构想,本来第一天已经完成了,但实现的过于复杂,且 bug 重重。花了一个通宵都没完全解决。在补了个好觉后,我在梦中意识到,应该简化方案,然后在第二天重写了一遍,终于可以跑起来了。代码是用 Go 实现的,比较玩具,quick & dirty 。不过我还是把它们放在后面。有兴趣的同学可以拿去改进。目前这个雏形已经够我用了,所以即使有改进或许也懒得再贴出来了。

主体想法是由两个部分的程序构成,一边放在本机上,对 localhost 开启一个兼容 socks5 的本地端口。当然只这一部分是不够用的,我们需要在墙外再设置一个程序,它才是真正的 proxy server 。这两个程序之间保持一个 TCP 连接。由本地的程序负责把本地的 proxy 请求都转发到墙外。

最初的想法,我阅读了 socks5 的 RFC1928 ,觉得实现一个 socks5 server 没什么大不了的。我要做的只是把所有的 socks5 请求编码成私有协议,通过唯一的 TCP 连接转发到墙外,由墙外的程序正确的 proxy 。事实证明,想在一天时间内正确的实现 socks5 协议还是有点难度的。即使用 Go 语言,对于我这个新手来说也不现实。ps , 通宵不睡觉调 bug 的效率也太低,不推荐在 30 岁以后还经常干。

睡了一觉后,我修正了我的方案。整个系统由三部分构成:

本地 n:1 连接转发服务 ----(传说中的墙)---- 墙外 1:n 连接转发服务 ---- socks5 服务器

简单的说,本地可以向本地服务提起若干个 TCP 连接,请求 socks5 服务。然后,我的程序把他们合成一个,通过一个长连接,通通转发到墙外。这中间可以做简单的加密或数据压缩。

在墙外的 vps 上,我放置一个私有程序,接收这些合并起来的连接。然后分解为一个个独立的请求。然后去连接 vps 本地的一个 socks5 服务器。

因为是个人使用,墙的两边的自写程序,只保持一个连接,一旦连接建立起来后,墙外的服务不在监听接受新的连接。只做 1:1 的服务。这样比较安全。不过想扩展成多个服务的,对于 Go 语言来说也相当容易,只是我懒的做罢了。

私有程序没有做身份认证。这是因为我只提供 1:1 服务,所以即使不认证也不会被人盗用。我只需要在需要使用时,手动开启即可。当然加上认证机制也不难,没加的理由还是我比较懒 :)

真正的 socks5 服务器就不用自己写啦。我用的 ssocks 比较轻量,也很单纯,就是一个 socks5 server 而已。不过这个东东目前的版本(0.0.10)有个小问题,它默认的监听绑定地址是 0.0.0.0 且不能配置(写死在代码里了)。在 README 中,我们看到 TODO 里作者有让它可配置的计划。在我这个应用中,我希望 socks5 server 只给本地用。所以需要自己做点小修改了。

只需要把 src/libsocks/net-util.c 中 new_listen_socket 函数里

      addrS->sin_addr.s_addr = htonl(INADDR_ANY);  /* All Local addresses */

这一行中的 INADDR_ANY 改成 INADDR_LOOPBACK 即可。

我的程序的源代码看这里。如有 bug 欢迎指出,若有问题概不解答 :) 。写的很乱,估计自己都不想再看一遍了。


ps. 最近买了一套新桌游,七大奇迹,很是不错,推荐一下。