跨平台网络库Cyclone发布

      我在畅游工作时,曾经维护一个名为Cyclone的基础库,包括天龙八部在内的大部分端游产品都是使用的这个库,主要是网络通讯、消息包管理,加密等功能,但这个库本身的技术含量很低,网络部分只支持select,没有考虑多线程,代码也很丑陋。由于是关系现金流的核心产品,本着稳定压倒一切的原则,一直不敢动,所以至今畅游仍然还在用着这份十多年前的代码。2015年初的时候,我曾经有一段时间没什么事情,于是打算重新写一个全新的网络库,参考了NginxSkynetMuduolwanlibevent的设计之后,有了一些心得,于是开始写新版的cyclone。在离开畅游之前,cyclone已经完成了第一版,并且应用在一个在研的手游项目上,但这个版本并不完善,后来我一直想找时间把cyclone再完善一下,但对于创业狗来说,坐下来写代码简直就是大逆不道的事情,于是一直断断续续的写。直到最近,cyclone终于完成一个比较满意的版本,也算完成了一个心愿 🙂

      这个工程我放在了Github上,cyclone的设计从一开始就是比较清晰的,主要是以下几个特性

非阻塞+多路复用

      这应该是使用最为广泛的一种网络模型,适合大多数应用场景,multiplexing支持select、epoll、kqueue三种api

多线程+event loop机制

      cyclone是按照one loop per thread的思想设计的,线程通过event唤醒,线程之间的通讯通过pipe进行,这种模式可以最大程度上减少线程的空转以及线程之间的临界区。对于网游服务器来说,一种很不好的设计就是不考虑线程的空转成本,大量使用sleep+busy loop,这也是为什么很多情况下,一台网游服务器明明cpu占用很低,但玩家仍然觉得“卡”的原因,因为大量的空转逻辑,导致服务器线程的fps降低,对玩家的消息包的相应时间加长导致的。线程之间的通讯使用无锁队列+pipe机制,也就是把要传输的数据放在无锁队列中,然后通过pipe唤醒相应的目标线程。对于c++多线程程序来说,对象的生命周期管理是一个非常重要的问题,一不小心就会陷入泥潭,所以采用线程之间的消息通讯机制,再配合std::shared_ptr,可以大大降低问题的复杂度。

跨平台

      目前支持Windows、Linux、MacOSX、Android,后面会考虑支持iOS,因为用了很多c++11特性,所以跨平台并不是什么太麻烦的事情,主要的跨平台的差异还是在于EventLoop中针对不同平台的实现,cyclone的EventLoop支持socket,timer,pipe三种唤醒机制,其中pipe的实现在linux和mac上都有原生的支持,在windows上虽然也有pipe,但无法用在select上,所以我用了一对socket来模拟pipe,这个消耗会有些高,所以在windows的生产环境里尽量慎用pipe。timer在mac上使用了kqueue原生机制,linux和Android使用了timerfd,windows上使用了timer-queue + pipe的方式。
      cyclone使用CMake作为编译脚本,以及单元测试程序,如果需要编译单元测试的话,需要安装google test

工具函数

      cyclone的设计思想是宁缺毋滥,尽量保证库的简单,比如消息包的封装,加解密这样的代码是以工具的形式放在库里,我已经把dh-exchange密钥交换和aes加密放在库里,可以实现通讯双方的安全协议,另外adler32可以做简单的crc校验算法,xorshift128做异或加密。

范例

      我提供了几个类似于helloworld的范例,比如echo和chat,另外samples里还有两个很有用的程序,socks5和relay。把这两个程序写出来的目的其实大家都懂得,socks5这个程序实现了简单的Socks5协议代理服务器,配合海外的vps,可以实现科学上网,但在我大天朝,仅仅靠sockes5还不行,因为这个协议本身并不支持消息加密,很容易就会莫名其妙的挂掉,所以我又实现了加密用的relay。原理可以参照云风的这篇文章。其中relay_local是一个n:1的工具,把多个链接收到一个链接中,relay_server是1:n的工具,把链接恢复出来去和真正的目标程序通讯,而relay_local和relay_server之间的协议是通过密钥交换和aes算法加密的,所以非常安全。
      具体操作是,在海外的vps上,运行socks5和relay_server,如下:

      在本地机器上运行relay_local

Continue reading

Tagged , | 5 Comments | 1,074 views

完全使用HTTPS了

      以前用过CloudFlare免费SSL证书来实现这个网站的https访问,不过CloudFlare是利用dns解析,把浏览器和服务器之间的数据通过中间服务器加密来实现,速度很慢而且只能使用固定的dns,所以不久我就把这个功能关掉了。最近偶然发现了一家可以提供免费SSL证书的机构Let’s Encrypt
letsencrypt-logo-horizontal
      简单了解了一下,Let’s Encrypt是国外一个公共的免费SSL项目,由 Linux 基金会托管,它的来头不小,由Mozilla、思科、Akamai、IdenTrust和EFF等组织发起,目的就是向网站自动签发和管理免费证书,以便加速互联网由HTTP过渡到HTTPS,目前Facebook等大公司开始加入赞助行列。目前Let’s Encrypt的证书已经被Mozilla、Google、Microsoft和Apple等主流的浏览器所信任,所以使用起来完全没有问题。证书的申请也很简单,官方有一套自动化的脚本(https://github.com/certbot/certbot)可以完成所有工作
      首先把脚本clone到本地

      生成证书(注意,生成证书时,需要临时关闭nginx服务)

      生成的证书放在/etc/letsencrypt/live/目录下,可以通过tree命令查看

      在nginx的配置文件中加入ssl服务器定义

      再把原先的http部分重定向到https

      重新启动服务器之后,即可看到所有链接已经变成绿色的https链接了。需要注意的是,Let’s Encrypt的证书的有效期只有三个月,所以需要设置一个定时任务,定期更新证书

      另外推荐一个检测网站ssl链接安全性的网站:https://www.ssllabs.com/ssltest/index.html

Tagged | 1 Comment | 1,457 views

在UnrealEngine4中使用Google Protobuf

       最近项目中需要把Google protobuf加入到UnrealEngine4游戏工程中,积累下一些有用的经验分享下。
       UE有一套自己的编译规则,如何在游戏中添加第三方库官方有一篇很详细的文档(Linking Static Libraries Using The Build System)。
       简单来说,第三方库一般放在’Source/ThirdParty’目录下,建一个目录,把需要包含的头文件以及编译好的库都放在这里,然后写一个对应的[LIBNAME].Build.cs文件,在这个文件里需要告诉编译器需要修改的设置,例如添加那些包含目录以及链接库。在游戏工程使用时,需要在本工程文件的[APPNAME].Build.cs中添加对该库的引用,就像下面这样

       对第三方库的使用,可以参照UnrealEngine的源码,在它的源码目录’Source/ThirdParty’里,有一大堆第三方库,不过这些库都是预先编译好的.lib和.a,如何编译出这些库官方并没有提供详细的文档说明。对于Windows环境来说比较简单,首先是使用和UE编辑器同样的VisualStudio版本,例如目前最新的4.14使用的是VS2015,并且在编译中使用/MD选项。google protobuf本身提供了一套cmake编译脚本,可以很方便的编译出所需要的lib文件。
       比较麻烦的是Linux平台,UE提供了专门的clang工具链来作为Linux和Android平台的编译工具,可以参照官方的这篇文档下载安装(Compiling For Linux),不过这套工具链中并没有对应的make工具,所以我从UE源码中的UnrealBuildTool工具中把编译参数还原出来,手动写了一套python脚本来完成probobuf的编译。
       为了适应UE4的环境,需要做一些改动,首先是protobuf中使用了类似于UINT这样的数据类型,而这种数据类型在UE4的源码中已经被屏蔽,具体可以参考UE源码中DisableOldUETypes.h文件的说明,为了使两者兼容,需要在protoc产生的.pb.h文件中添加#include “AllowWindowsPlatformTypes.h”和#include “HideWindowsPlatformTypes.h”两行代码。

       另外protobuf源码中有一个文件使用了byteswap.h这个头文件,不幸的是,UE4源码中有一个ByteSwap.h文件,在clang编译器中产生编译错误,需要做一定的修改。

       我把最终编译好的库以及所使用的的编译脚本放到了github上,所需环境如下

软件 版本 备注
Google Protobuf 3.1.0
Visual Studio 2015
clang 3.9.0 EPIC提供改造过的工具链,需要参照这篇官方文档下载安装
CMake 2.8以上 需要把cmake.exe所在路径加入到PATH路径中
Unreal Engine Source 4.14.3 参照官方文档下载并编译源码
Python 3.x or 2.x
Tagged | 2 Comments | 2,014 views

星辰大海

离开畅游快一年了,这期间我组建了一个VR游戏公司,天镜科技,聚集了一帮牛人,所开发的VR游戏近期即将在VivePort上线。
技术、科幻、产品,有这些东西在,我很喜欢现在的状态。
stardust_1
来吧,我们的征途是星辰大海!

Tagged | 1 Comment | 1,097 views

赌博中的数学:Martingle策略

      前段时间在Las Vegas待了一个星期左右,以前虽然也来过赌城,但不像这次这么长时间,趁机好好体验了一把赌徒的生活。

      来赌场的华人最爱玩的是一种叫做“百家乐”(Baccarat)的游戏,这个游戏的规则并不复杂,节奏也很快,简单来说,就是类似于最简单的猜大小的游戏,每局产生的结果有三种可能性,要么是“庄”,要么是“闲”,或者是“和”,每个结果的概率和赔率大概分布如下:

结果 概率 赔率
45.86% 0.95
44.62% 1
9.52% 8

      举个例子,假如押10块钱到“庄”上,如果牌局结果是“庄”,那么不仅可以把本金10块拿回来,还可以再获得9.5元,但如果结果是“闲”,那么这10块钱本金就赔进去了。很多赌徒之所以痴迷百家乐,除了节奏明快,百家乐的发牌方式设计的也很独特,先发两张牌,然后再通过一定的规则“补牌”,在补牌的过程中结果可能完全反转,整个过程很“刺激”,另外一个原因来自于百家乐的“路单”。所谓路单就是用来记录赌局已经产生的结果的图案,除了直接记录每一局是“庄”、“闲”还是“和”,百家乐的路单中还有“大路”、“大眼仔”、“小路”、“曱甴路”这些古怪的额外数据,用来记录诸如结果是否“齐整”等信息。
      作为一个死理性派,我自然一开始就明白“赌徒谬论”(Gambler’s fallacy)这个道理,所有赌局在概率上都是互相独立的,即便连续开出十几次“庄”,下一次是庄的概率仍然是45.86%,那些花花绿绿的路单纯粹就是给人心理安慰罢了,所以我始终没有去费力气分析什么路单,但我一直在尝试另一个和赌博相关的问题,就是“Martingle策略”(Martingale)。
      Maringle是一种投资策略,在赌徒中间流传甚广,这种策略可以简单描述为“输钱后加倍下注,直到赢钱”。比如在百家乐游戏中,我一开始押10元到“闲”上,如果押对,那么下次仍然继续押10元,如果押错,相当于我赔掉了10元,那么第二局就押20元,这样如果第二局赢得话,我就可以获得40元,刨除两局投入的30元,仍然盈利10元,如果继续输,那么就加倍到40、80、160…元,这样一旦赢钱,就可以把连续输掉的钱都翻本回来。

      理论上讲,如果本金足够,并且赌局没有押注上限的话,这种方法是可以绝对盈利的,事实上也的确如此,Martingle策略最早在18世纪就在法国的赌场上流行,我在拉斯维加斯用这个策略,用5美金做最小赌注押“闲”,一度把1000美元本金翻到3000美元,当时心情激动,认为找到了发财的好方法。不过好景不长,很快我遇到连续的“庄”,几乎在瞬间,我几天辛辛苦苦赢来的钱就全赔了进去,最终兴趣索然,就再也不玩了。
      为了真实重现这种状况,我用Mathematic模拟了一下Martingle策略:

      其实这就是Martingle策略的真相,在运气比较好的情况下,通过输和赢交替进行,资产会小量的逐渐提升,不过一旦遇到连续输的结果,押注翻倍上升,而获利仍然是最小押注,风险就会急剧升高,最终无一例外出现破产出局的情况,所以使用这种策略的最终要的事情就是“见好就收”,一旦赢到一定程度就赶紧收手,所谓久赌必输就是这个道理。

Tagged , | Leave a comment | 2,111 views

开源一个调试工具


        AxTrace是我的个人开发的一个调试工具,已经伴随我很多年了,在很多我参与的项目中发挥了重大作用,最近我花了不少时间把这个工具重新整理了一下,在这里正式公开。
        简单来说,AxTrace是给程序员在开发期间使用的一个日志工具,类似于DebugView,比如在程序中添加下面的语句:

        那么在AxTrace程序中就会显示出这条日志和变量值。
Continue reading

1 Comment | 1,778 views

畅游十一年

      2016年1月8日,我的离职清单上正式签上所有应该签的名字,这也就意味着我在的搜狐畅游生涯结束了,距离我入职的日期2005年1月19日,整整十一年。
      从刚入职时的毛头小子,到如今的人到中年,人生中最美好的十一年留给了畅游。

      这是走的时候在大厅拍的,其实在我心中已经鞠了一躬了,谢谢你…
      正式进入创业状态,方向是VR游戏,坐标北京,有对这个方向感兴趣的,请和我联系: thejinchao@gmail.com

1 Comment | 1,688 views

如何生成一个随机的圆形

        最近在工作中遇到这么一个问题:
        在游戏场景中有一个怪物生成点,这个生长点产生的怪物均匀分布在半径为R的圆形内,这个随机算法应该如何生成?看起来很简单,随手写了一个:

#define RAND  ((float)rand()/RAND_MAX)
 
void get_random_pos(float center_x, float center_y, float radius, float&x, float& y)
{
    
float u = RAND*radius;
    
float v = RAND*2*PI;
    
    
x = center_x + u*cos(v);
    
y = center_y + u*sin(v);
}

        但写的过程中,直觉告诉我,这么写肯定是有问题的,试想,如果以北京为例,如果所有居住在北京的人都报出自己家和天安门的距离,那么这些数据肯定不是均匀分布的,因为居住在五环附近的人数肯定要大于居住在二环附近的人数,于是用Mathamatica实验一下:

        果然,这么写是不对的,网上查了一下,这个问题还真是有人研究过,说应该把所获得的随机数开平方一下,实验一下:

        但是,这个开平方背后的数学原理究竟是什么呢?抽空翻了下概率书,原来,其中的道理并不复杂,这里涉及到概率里的一个基本概念,累计分布函数(Cumulative distribution function),简称CFD,它的定义如下:
        设有一个随机变量\(X\),它的取值范围是从负无穷到正无穷,如果把它的值小于\(x\)的概率表达为一个函数\(F(x)\),那么这个函数就称为\(X\)的累计分布函数
\begin{equation}
F(x)=P(X\leq x)
\end{equation}
Continue reading

Tagged , , | 4 Comments | 5,360 views

一个简单的DH密钥协商算法的实现

        密码的管理可以说是加密体系中最为性命攸关的问题,在计算机发明之前,加密方法只能使用简单的移位、查表等简单的方法,这种级别的加密算法,基本上都无法逃脱被破解的命运,比如二战中德国发明的“英格玛”可以说是前计算机时代人类所发明的最为复杂的加密方法了,但以图灵为首的盟军科学家们,仍然可以用粗暴的暴力破解法硬生生从密文中破解出原文出来。
        进入计算机时代后,加密算法的复杂度有了质的飞跃,相对应的破解难度也不断加大,到了如今,像AES这样变态的加密算法,已经比英格玛不知复杂了多少个数量级,在没有密码的情况下,想直接从密文中破解出明文,即使图灵重生也全无可能了。于是,密钥本身的管理变成了加密环节中最脆弱的环节,“如何安全的把密码告诉别人”成了一个难题,比如,如果你需要发给同事一封包含加密附件的邮件,一般都会把密码放在另外一封邮件中发送,或者用其他方式告诉他,尽管这样做也并不安全,但总比那种傻乎乎的把密码和加密附件直接放在一起强多了。
        1976年,美国的两位数学家Whitfield DiffieMartin Hellman率先发表了一种解决该密钥传输的方法,因此这种方法被大家称为Diffie–Hellman key exchange算法,这种算法提出这么一个做法:“在加密通讯之前双方各自生成密码的一部分,然后互换后合成起来,作为最终的密码”。这就是密钥协商,维基百科上使用了一个很有趣的比喻,就是颜料的混合:
        设想这样一个场景,Alice(A)和Bob(B),他们想在不见面的情况下秘密约定出一种颜色,但他们互相沟通的信息都会被公开,应该怎么办呢?

Alice Bob
私密信息 公开信息 公开信息 私密信息
A和B首先约定好公开的一种颜色,比如黄色
A,B各自挑选出一种私密的颜色,比如橙色和兰色
A,B各自将两种颜色混合起来
双方交换混合后的颜色
A,B各自将自己的私密颜色再次混入得到的颜色中
现在A,B得到了一种相同的颜色,这种颜色是由一份黄色、一份橙色、一份兰色混合而来,但外界无法得知

        秘密在于,颜色混合是一种“不可逆”的操作,当双方交换颜色时,尽管我们知道他们交换的颜色都是由一份黄色和另一份其他颜色混合得到的,但我们还是无法或者很难得到他们的私密颜色。而DH秘钥交换的原理非常相似,也是利用了数学上的一个“不可逆”的运算,就是离散对数(Discrete logarithm
Continue reading

Tagged , , | 3 Comments | 4,316 views

如何计算线段和圆的交点

这是我以前写的一篇博文,因为有朋友需要,重新贴出来

        一个程序里用到了计算线段和圆相交情况的算法,在这里记下来备忘

        设线段的两个端点分别是P1(x1,y1)和P2(x2,y2),圆的圆心在P3(x3,y3),半径为r,那么如果有交点P(x,y)的话
\begin{equation}
\overrightarrow{P}=\vec{P_1}+u(\vec{P_2}-\vec{P_1})\tag1
\end{equation}
        其中,u在0到1之间,转换成各个坐标
\begin{equation}
\begin{cases}
x=&x_1+u(x_2-x_1)\\
y=&y_1+u(y_2-y_1)
\end{cases}\tag2
\end{equation}
        由于P也在圆上,所以
\begin{equation}
(x-x_3)^2+(y-y_3)^2=r^2\tag3
\end{equation}
        联立上面的公式,可以得到
\begin{equation}
Au^2+Bu+C=0\tag4
\end{equation}
        其中
\begin{equation}
\begin{cases}
A=&(x_2-x_1)^2+(y_2-y_1)^2\\
B=&2((x_2-x_1)(x_1-x_3)+(y_2-y_1)(y_1-y_3))\\
C=&x_3^2+y_3^2+x_1^2+y_1^2-2(x_3x_1+y_3y_1)-r^2
\end{cases}\tag5
\end{equation}
        解一元二次方程,可以得到
\begin{equation}
u=\frac{-B\pm\sqrt{B^2-4AC}}{2A}\tag6
\end{equation}
        根据B2-4AC的结果,可以判断线段所在直线和圆的相交情况

  • 如果小于0,表示没有交点
  • 如果等于0,表示相切,只有一个交点
  • 如果大于0,表示有两个交点

        针对P1和P2之间的线段,根据计算出的u值,有5种结果

  • 如果线段和圆没有交点,而且都在圆的外面的话,则u的两个解都是小于0或者大于1的
  • 如果线段和圆没有交点,而且都在圆的里面的话,u的两个解符号相反,一个小于0,一个大于1
  • 如果线段和圆只有一个交点,则u值中有一个是在0和1之间,另一个不是
  • 如果线段和圆有两个交点,则u值得两个解都在0和1之间
  • 如果线段和圆相切,则u值只有1个解,且在0和1之间
Tagged , | 2 Comments | 5,130 views