标签归档:互联网

浅谈部落冲突的协议设计

部落冲突(Clash of Clans)是一款风靡全世界的手机游戏。部落冲突的忽然流行造就了又一家神奇的芬兰公司Supercell,同时也带来了很多关于游戏成功秘诀的讨论。在这里我们暂且不论部落冲突为啥会吸引那么多玩家这个话题,简单来看看部落冲突里的底层协议设计。

部落冲突的底层协议可以说设计的非常的好,从技术上说,也是非常先进而且高效的。首先客户端和服务器端采用RC4进行加密。在第一次握手之后,服务器端会传回一个秘钥seed,然后客户端和服务器端把新seed扔给Scramble7算法,产生新秘钥。这个算法在客户端更新之后还经常进行变换,可见Supercell程序员的用功刻苦程度。算法握手大致描述如下:
client.rc4 = RC4(INIT_KEY)
server.rc4 = RC4(INIT_KEY)
client: login(user_id, user_pwd, client_version, device_info, client_seed)
server: login_success(user_id, user_pwd, client_version, client_bind, server_seed)
server: set_key(new_key)
prng = Scramble7(server_seed)
reset_key = prng.get_key(new_key)
client.rc4 = RC4(reset_key)
server.rc4 = RC4(reset_key)

在经过这一系列解密之后,我们才能开始看到明文,知道客户端和服务器之间到底交流了什么。

接下来让我们仔细分析一下部落冲突目前的核心玩法:部落战的协议内容:
client: attackwar(user_id)
server: attackwar_fail(user_id, reason) # If fail
server: attackwar(map_info) # If success
client: action(tick, checksum, [action1, action2, action3, ...])
action_list:
action_army: (x, y, army_id, tick)
action_ally: (x, y, ally_id, tick)
action_end: (tick)
action_spell: (x, y, spell_id, tick)
action_hero: (x, y, hero_id, tick)
action_herospell: (hero_id, tick)
action_start: (tick)
action_data: (data_content, tick)

我们先来看一个设计的非常巧妙的action指令。这个指令的头是tick和checksum,tick是以1/60秒为单位的整数(60就是第一秒,120就是第二秒),而checksum是一个客户端信息的总和。

信息的总和是如何算出来的呢?这里非常巧妙的是,客户端会把目前绝大多数数据做一个求和,再算上当前tick数,得到一个总的checksum。这个checksum非常的关键,因为服务器会校验。服务器如果不了解客户端信息,是怎么校验的呢?很简单,服务器在连接建立之后,会跑着一套和客户端同样逻辑的代码,然后对客户端发来的每一条信息进行checksum校验。

比如说,客户端说我第一秒在某处放了一条龙。客户端经过模拟后,发现第二秒龙会摧毁一个对方的建筑,这时候checksum就会有显著变化,因为一个建筑没了。这时候给服务器的checksum必须有体现,服务器也会跑一个模拟程序,检验第二秒龙摧毁了一个建筑,如果客户端发来的checksum对不上,那么服务器就会断掉连接,认为客户端非法。

所以要做一个脱机离开客户端直接向服务器发送请求的程序很难,因为必须包含客户端完整的模拟战斗逻辑。而这套逻辑是部落冲突的代码核心,每次版本更新都会大改,非常难以完整进行模拟。

在此基础上的协议基本杜绝了第三方脱机机器人的存在。大部分机器人必须依靠客户端才能进行,比如BlueStacks上运行的虚机。

然而,这样的协议之上依然存在很多漏洞。还是拿部落战举例,如果有一个Men-In-The-Middle拦截了打的不好的协议包,只传送打的好的协议包,那么其实是可以保证每一次部落战都完成三星。

在最近的一次更新中,新增了action_start和action_data两条指令,这是做什么用的呢?Supercell为了阻止日益猖獗的叉叉助手和iMod所谓沙盒模拟(就是脱机练习进行演练),将对手的一部分信息(电塔援军陷阱)进行了隐藏。在付出一次攻击代价的情况下,服务器会给客户端返回这些信息,客户端才能进行完整的游戏。大概的逻辑如下:
client: attackwar(user_id)
server: attackwar(map_without_key_info)
client: action(60, checksum_60, [action_start(0)])
server: key_info(data)
client: action(120, checksum_120, [action_data(61, data)])
client: action(180, checksum_180, [action_army(125, x, y, army_id), ...])
......

简单说就是在action_start之后,服务器才会返回关键信息,让客户端能够完整进行模拟。那么action_data的作用是什么呢?由于checksum机制的存在,服务器需要和客户端同步加入这部分关键信息,所以客户端需要在收到key_info之后,告诉服务器,我在何时(tick)把这些key_info加入到地图形成完整地图的。然后服务器收到之后,可以和客户端一起进行模拟,并且校验checksum。

那么目前版本有一个致命的bug,就是服务器对action_data返回的data并没有进行检验。导致的后果就是客户端如果发回的key_info和服务器之前传回的不一样,也能正常模拟下去。如果客户端发一个空的key_info,服务器会认为陷阱电塔援军都神奇的消失了!

当然这种bug可能并不影响普通玩家,可能只有深入研究了协议的才会发现。尽管存在很多bug,但是笔者认为部落冲突依然是一款从技术上设计非常精良的游戏。不管何时,技术上的完善都是一款游戏坚实的基石。如果外挂横行漏洞百出,不管游戏表面有多美丽,都是一摊烂泥无法流行起来。

 

浅谈 Swift 语言

在刚过去不久swift_taylor的万众瞩目的 WWDC 2014 上,苹果发布了 Swift 语言。注意这个和已存在很久的 Swift Parallel Language (http://swift-lang.org/) 是两个东西。这是由苹果独立开发完成的,基于 LLVM 的全新语言,是一个从头到脚都打上苹果烙印的新东西。作者于是来赶趟儿简单写写对 Swift 语言的体会和感受。

Swift 做为一个崭新的2014年才发布的语言,全身上下都透着各种狂拽酷炫吊炸天的味道。从各家语言中博采众长,非常具备时代气息。关于 Swift 从哪些语言里继承了哪些特点,各家说法都有。个人第一印象觉得 Swift 更像 Ruby 一些。

然而做为一个新生语言,Swift 也有着一些小缺点:

  • 你依然需要学Objective C。Swift的大量底层库还是Objective C写的。如果真想写个游戏的话,难免还是会涉及调用大量的Cocoa风格的API。当然,有一部分Objective C的库已经专门为Swift进行了参数简化和改写,你有时候不需要再写Objective C里的反人类的长达几十个字母的常量名了。比如:let myTableView: UITableView = UITableView(frame: CGRectZero, style: .Grouped)
  • 缺少私有属性、异常处理等机制。私有属性很多语言都没有,个人觉得没有太大关系;异常处理的话,做为新时代语言来说,缺少了还是比较不应该,虽说Objective C里也没有。
  • 类型非常诡异的复制特性。比如下面代码
    var ages = ["Peter": 23, "Wei": 35, "Anish": 65, "Katya": 19]
    var copiedAges = ages
    copiedAges["Peter"] = 24
    println(ages["Peter"])
    // 23
    var a = [1, 2, 3]
    var b = a
    a[0] = 42
    println(a[0])
    // 42
    println(b[0])
    // 42
    a.append(4)
    a[0] = 777
    println(a[0])
    // 777
    println(b[0])
    // 42

    大家可以体会一下这让人毛骨悚然的设计。简单说就是字典赋值都会复制一份出来,而数组不会。但是数组一旦长度做了更改也会立刻原地复制一份出来。这种设计模式很让人摸不到头脑,比较反常识。
  • 文档依然不是很齐全。需要较长时间来补充。
  • 无法跨平台。说到这一点确实有人要说这是勉为其难了。Apple凭啥做个能跨Android的东西来呢。然而,大概询问了几家游戏开发公司,都表示最大得导致他们不会用Swift开发游戏的原因就是没法跨平台。而现有的很多游戏引擎都做到了跨平台开发。

由于 Swift 的优点太多,网上也有很多人做了分析,这里就不一一详述了。这里只想总结说,Swift 确实是门开发效率非常高的语言。如果你只做 iOS/Mac 开发,Swift 现在是你的第一选择。

有人问 Swift 会不会是 iOS 开发的未来。我可以毋庸置疑的回答,是的。Apple的策略倾向导致,将来会有大量的资源像 Swift 倾斜。对于一个公司策略级的开发语言来说,Swift 的前途已经注定灿烂了。就像 Apple 描述 Swift 的那样:A complete replacement for both the C and Objective-C languages。

最后祝大家在 Swift 学习中能找到乐趣。

 

云服务为什么会是未来?

今天在交流时候有记者问过我,使用云服务主要还是成本的考虑吗?是的。和传统服务相比,云服务实际上没有哪一点是完全不可替代的。而成本恰恰是小团队最关心的一个问题,时间成本、人力成本、以及最直接的机时售价价格,这些问题累积在一起,才是做为初创公司选择云服务的所有理由。

 

英国经济学家杰文斯曾经在《煤矿问题》中指出一个看似互相矛盾的问题:对蒸汽机性能的改进提高了煤炭的能源转化率,用更少的煤可以产生更多的能源了,而能源的价格降低往往又导致了煤矿的消费量增加。这种现象被称为杰文斯悖论,既:对资源的利用率降低了资源的价格,最终会增加资源的使用量。在云计算领域,该悖论也非常的适用,云服务大大改进了计算资源的利用率,改进的方式包括:更简单的获取计算资源的方式,以及将闲置计算资源更好的释放出来。当开关服务器就和开关水龙头一样便捷之后,公司以及个人对服务器资源的需求会大大的增加。

举个切身体会到的例子。曾几何时,公司弄一台线上服务器是如此的困难。早先我们需要首先买一台服务器,然后找个机房托管,签完各种合同,交完押金和钱,将庞大的机器搬到机房里的某个机柜,插好各种线,终于可以接入互联网开始服务了。再然后有了服务器租赁业务,依然会比较麻烦,填完合同之后,大概需要2-3天不等,机器才能准备好。在如今云服务提供的便利之下,5分钟可以开一台服务器,用完即关。

对于传统互联网公司来说,一方面,在计算资源获取困难的时候,一个项目或者一个新计划只能压缩到有服务器的时候才能开展,而根据流量动态调节服务器响应能力变得几乎不可能。另一方面,在计算资源过剩的时候,闲置在那里的服务器资源对于能源的浪费,简直是一件令人发指的事情。有一个听来的真实的笑话是这么说的,老板发现了公司服务器CPU闲置的非常厉害,让手下想办法。某公司手下用脚本检查CPU占用率,如果没满就写一个死循环占满。另一个公司觉得这样太直白了不太好,就暗示开发把代码写的烂一点,以占用更多的CPU让数字看上去好看些。对于大型互联网公司来说,目前每年都有无数的钱财和资源浪费在了闲置服务器上。

如果将传统服务器比作每天早上下山挑水喝,那么云服务就像是自来水入户,打开水龙头,水就流了出来,不用的时候,可以随时关上水龙头。既充分利用了资源,也没有造成资源浪费,把成本降到了最低。将计算能力分割成块然后当成自来水一样出售给大众,这无疑是大势所趋。在未来,任何一个普通学生想起一个复杂的算法,都可以经过简单的操作,然后开启100台服务器进行计算,最后在验证完算法之后关闭。云服务会真正像自来水一样走进千家万户。

有感而发写一点不那么务实的东东。

 

 

谈谈Zopfli

image01

最近 Google 出了一个新的开源项目 Zopfli。Zopfli是什么呢?简单说是一个 Deflate 压缩算法的另一种实现。推出之后国内国外媒体纷纷报道转载。昨天看到国内媒体的报道 (搜狐IT)中说道:“据悉,Zopfli的压缩率比现有的Zlib高3-8倍。”当时看到了就吓了一大跳,3-8倍这是要逆天啊!赶紧去Zopfli主页看一眼,原来只是3%-8%的提升。国内IT编辑真是吓死人不偿命。

Zopfli到底表现怎么样呢?先看看 Zopfli 自己提供的数据:

测试集 样本大小 gzip -9 7-zip kzip Zopfli
Alexa-top-10k 693,108,837 128,498,665 125,599,259 125,163,521 123,755,118
Calgary 3,141,622 1,017,624 980,674 978,993 974,579
Canterbury 2,818,976 730,732 675,163 674,321 669,933
enwik8 100,000,000 36,445,248 35,102,976 35,025,767 34,955,756

大概是比标准的gzip -9要小 3.7%-8.3% 的样子。但是压缩所需要的时间非常的惊人:

压缩算法 压缩时间
gzip -9 5.60 s
7-zip -mm=Defalte -mx=9 128 s
kzip 336 s
Zopfli 454 s

可以说如果用 gzip 压缩要喝口水的时间的话,用 Zopfli 就可以出去吃个便饭了。

我们再看看这些算法的出生年份:Deflate最早诞生于1994年。7-zip最早诞生于1999年,也是一个开源项目,虽然7-zip自己默认用的格式是LZMA和LZMA2算法,但是也支持对Deflate算法的更好的压缩。KZip 是 Pngout 作者写的一个小工具,诞生于2006年,是一个把现有Zip再压缩的工具。

这里不得不提几个Zopfli文档里没有提到的其它 Deflate 兼容的压缩工具:DeflOpt,是2007年诞生的一个Zip再压缩工具。AdvZip,是一个利用7-zip Deflate的一个Zip再压缩工具。

可以从表中看出,Zopfli比1994年原版Deflate确实有3%-8%的提升,但是对比比较新的Deflate实现,提升实在是很有限,比如比KZip只提升了大概1%不到。压缩时间对比KZip也增加了相当多。

发布没多久,就有人发现,利用 KZip+DeflOpt,压缩的结果可以比Zopfli压缩的更小,甚至Zopfli的几个样本的压缩结果,依然可以用 DeflOpt 再压缩一点(1%左右)。所以说Zopfli其实并不是他在文档里所说的,“所有已知Deflate算法实现里压缩比最高的”。

当然,Zopfli的意义在于它是开源算法,而KZip+DeflOpt这俩都不开源。关于KZip,DeflOpt是如何实现的,之前还有很多人在猜测。Zopfli的出现给大家提供了很好的解答。

另一点值得探讨的是,在今天研究Deflate算法更好实现是否还有价值。Zlib的作者本人Mark Adler在听说Zopfli之后说:“这很酷,不过看上去是一个付出了很多努力,但只取得了很小提升的一个糟糕结果。也许到了给HTTP的accept-encoding加上更好算法的时候了”。是的,诞生于1994年的Deflate确实太老了。现有的解压更快、压缩比更高的开源算法有很多很多,比如 bzip2, LZMA/XZ等等。LZMA/XZ在解压速度上,以及压缩比上,都完胜Deflate。Deflate对于很多 UTF-8 3 bytes的网页压缩效果也很不理想。直到今天,支持bzip2, LZMA的浏览器还寥寥无几。也许更有前途值得关注的是HTTP/2.0协议(一部分基于Google的SPDY协议)。

重新回到Deflate算法。为何Deflate有如此多的压缩实现呢?我们得详细的看看Deflate算法的具体内容。Deflate算法其实就是LZ77算法加Huffman算法。先经过LZ77的字典找重,然后用Huffman树进行降比特。不同的Deflate压缩的实现其关键在于LZ77的搜索重复单词,以及选择分块来进行Huffman。早期算法例如7-zip对分块都不是很重视,更多的考虑的是LZ77算法的优化。而KZip另辟蹊径对分块也进行了优化,使得最终比特流长度变得更短。

LZ77算法优化是一个有向图上的最短路径的搜索问题。对于字节流每个字节建立单边节点,重复单词序列建立更短的边,形成一个有向图。LZ77算法的目的就是如何找到有向图从起点到终点的最短路径。对于边的长度确定的情况下,用动态规划找最优解是很简单的。然而LZ77在搜索时,如果要考虑下一步Huffman过滤之后的长度,则边长度就是不固定的。Zopfli采用迭代的办法,先用一次贪心法拿到第一个次好的结果,然后通过使用结果字节的熵值(就是出现频率的N-log2n)来给出下一次迭代的每条边的边长,也就是每个字母的比特长度。通过反复迭代,来逐步逼近最好结果。当然,理论上也可能跌入一个次好结果的低谷。

Huffman_tree_2.svg然后是最关键的分块问题。分块为何会影响Huffman的压缩结果?其主要问题还是因为动态Huffman算法的随机性。如果都采用对字节使用频率统计完毕之后的静态Huffman,那么不管如何分块都不会对结果有影响,反而因为分块产生额外的比特,使得结果变大。动态Huffman的树是在字节流的处理过程中动态创建的,因此其字节流的开始片段不规律性往往使得结果不优。如何分块才能更优?因为随机性太大,也很难进行判断。所以KZip和Zopfli采用的都是尽可能的穷举。KZip就号称用了“重复单词的穷举(LZ77)”和“更高效率的分块(Huffman)”来实现,可以增加分块的个数进行进一步优化。而Zopfli,是不停的在一个最大块内找9个点,穷举判断哪一个最优,然后进行反复切割的办法。

Deflate压缩算法有没有最优解?这其实是个NP问题。对于短短32字节大小的数据,都有2**31 = 2147483648 种不同的分块方案。当然绝大多数分块都没有意义而产生更差结果。分块之后依然还有需要进行迭代的边长会变化的最短路径问题需要解决。

最后,尽管 Zopfli 的结果不是很令人满意,不过确实给众多不开源的 Deflate 压缩工具树立了标杆。那些想靠着 Deflate 算法做收费 PNG 压缩的软件可以洗洗睡了。