易栈网-膘叔

转自：http://www.blogjava.net/BlueDavy/archive/2008/09/03/226749.html

之前也有一些介绍大型网站架构演变的文章，例如LiveJournal的、ebay的，都是非常值得参考的，不过感觉他们讲的更多的是每次演变的结果，而没有很详细的讲为什么需要做这样的演变，再加上近来感觉有不少同学都很难明白为什么一个网站需要那么复杂的技术，于是有了写这篇文章的想法，在这篇文章中 将阐述一个普通的网站发展成大型网站过程中的一种较为典型的架构演变历程和所需掌握的知识体系，希望能给想从事互联网行业的同学一点初步的概念，文中的不对之处也请各位多给点建议，让本文真正起到抛砖引玉的效果。

架构演变第一步：物理分离webserver和数据库

最开始，由于某些想法，于是在互联网上搭建了一个网站，这个时候甚至有可能主机都是租借的，但由于这篇文章我们只关注架构的演变历程，因此就假设这个时候 已 经是托管了一台主机，并且有一定的带宽了，这个时候由于网站具备了一定的特色，吸引了 部分人访问，逐渐你发现系统的压力越来越高，响应速度越来越慢，而这个时候比较明显的是数据库和应用互相影响，应用出问题了，数据库也很容易出现问题，而 数据库出问题的时候，应用也容易出问题，于是进入了第一步演变阶段：将应用和数据库从物理上分离，变成了两台机器，这个时候技术上没有什么新的要求，但你 发现确实起到效果了，系统又恢复到以前的响应速度了，并且支撑住了更高的流量，并且不会因为数据库和应用形成互相的影响。

看看这一步完成后系统的图示：

这一步涉及到了这些知识体系：

这一步架构演变对技术上的知识体系基本没有要求。

架构演变第二步：增加页面缓存

好景不长，随着访问的人越来越多，你发现响应速度又开始变慢了，查找原因，发现是访问数据库的操作太多，导致数据连接竞争激烈，所以响应变慢，但数据库连 接又不能开太多，否则数据库机器压力会很高，因此考虑采用缓存机制来减少数据库连接资源的竞争和对数据库读的压力，这个时候首先也许会选择采用squid 等类似的机制来将系统中相对静态的页面（例如一两天才会有更新的页面）进行缓存（当然，也可以采用将页面静态化的方案），这样程序上可以不做修改，就能够 很好的减少对webserver的压力以及减少数据库连接资源的竞争，OK，于是开始采用squid来做相对静态的页面的缓存。

看看这一步完成后系统的图示：

这一步涉及到了这些知识体系：

前端页面缓存技术，例如squid，如想用好的话还得深入掌握下squid的实现方式以及缓存的失效算法等。

架构演变第三步：增加页面片段缓存

增加了squid做缓存后，整体系统的速度确实是提升了，webserver的压力也开始下降了，但随着访问量的增加，发现系统又开始变的有些慢了，在尝 到了squid之类的动态缓存带来的好处后，开始想能不能让现在那些动态页面里相对静态的部分也缓存起来呢，因此考虑采用类似ESI之类的页面片段缓存策略，OK，于是开始采用ESI来做动态页面中相对静态的片段部分的缓存。

看看这一步完成后系统的图示：

这一步涉及到了这些知识体系：

页面片段缓存技术，例如ESI等，想用好的话同样需要掌握ESI的实现方式等；

架构演变第四步：数据缓存

在采用ESI之类的技术再次提高了系统的缓存效果后，系统的压力确实进一步降低了，但同样，随着访问量的增加，系统还是开始变慢，经过查找，可能会发现系 统中存在一些重复获取数据信息的地方，像获取用户信息等，这个时候开始考虑是不是可以将这些数据信息也缓存起来呢，于是将这些数据缓存到本地内存，改变完毕后，完全符合预期，系统的响应速度又恢复了，数据库的压力也再度降低了不少。

看看这一步完成后系统的图示：

这一步涉及到了这些知识体系：

缓存技术，包括像Map数据结构、缓存算法、所选用的框架本身的实现机制等。

架构演变第五步： 增加webserver

好景不长，发现随着系统访问量的再度增加，webserver机器的压力在高峰期会上升到比较高，这个时候开始考虑增加一台webserver，这也是为了同时解决可用性的问题，避免单台的webserver down机的话就没法使用了，在做了这些考虑后，决定增加一台webserver，增加一台webserver时，会碰到一些问题，典型的有：
1、如何让访问分配到这两台机器上，这个时候通常会考虑的方案是Apache自带的负载均衡方案，或LVS这类的软件负载均衡方案；
2、如何保持状态信息的同步，例如用户session等，这个时候会考虑的方案有写入数据库、写入存储、cookie或同步session信息等机制等；
3、如何保持数据缓存信息的同步，例如之前缓存的用户数据等，这个时候通常会考虑的机制有缓存同步或分布式缓存；
4、如何让上传文件这些类似的功能继续正常，这个时候通常会考虑的机制是使用共享文件系统或存储等；
在解决了这些问题后，终于是把webserver增加为了两台，系统终于是又恢复到了以往的速度。

看看这一步完成后系统的图示：

这一步涉及到了这些知识体系：

负载均衡技术（包括但不限于硬件负载均衡、软件负载均衡、负载算法、linux转发协议、所选用的技术的实现细节等）、主备技术（包括但不限于ARP欺骗、linux heart-beat等）、状态信息或缓存同步技术（包括但不限于Cookie技术、UDP协议、状态信息广播、所选用的缓存同步技术的实现细节等）、共享文件技术（包括但不限于NFS等）、存储技术（包括但不限于存储设备等）。

架构演变第六步：分库

享受了一段时间的系统访问量高速增长的幸福后，发现系统又开始变慢了，这次又是什么状况呢，经过查找，发现数据库写入、更新的这些操作的部分数据库连接的 资 源竞争非常激烈，导致了系统变慢，这下怎么办呢，此时可选的方案有数据库集群和分库策 略，集群方面像有些数据库支持的并不是很好，因此分库会成为比较普遍的策略，分库也就意味着要对原有程序进行修改，一通修改实现分库后，不错，目标达到 了，系统恢复甚至速度比以前还快了。

看看这一步完成后系统的图示：

这一步涉及到了这些知识体系：

这一步更多的是需要从业务上做合理的划分，以实现分库，具体技术细节上没有其他的要求；

但同时随着数据量的增大和分库的进行，在数据库的设计、调优以及维护上需要做的更好，因此对这些方面的技术还是提出了很高的要求的。

架构演变第七步：分表、DAL和分布式缓存
随着系统的不断运行，数据量开始大幅度增长，这个时候发现分库后查询仍然会有些慢，于是按照分库的思想开始做分表的工作，当然，这不可避免的会需要对程序 进行一些修改，也许在这个时候就会发现应用自己要关心分库分表的规则等，还是有些复杂的，于是萌生能否增加一个通用的框架来实现分库分表的数据访问，这个在ebay的架构中对应的就是DAL，这个演变的过程相对而言需要花费较长的时间，当然，也有可能这个通用的框架会等到分表做完后才开始做，同时，在这个阶段可 能会发现之前的缓存同步方案出现问题，因为数据量太大，导致现在不太可能将缓存存在本地，然后同步的方式，需要采用分布式缓存方案了，于是，又是一通考察和折磨，终于是将大量的数据缓存转移到分布式缓存上了。

看看这一步完成后系统的图示：

这一步涉及到了这些知识体系：

分表更多的同样是业务上的划分，技术上涉及到的会有动态hash算法、consistent hash算法等；

DAL涉及到比较多的复杂技术，例如数据库连接的管理（超时、异常）、数据库操作的控制（超时、异常）、分库分表规则的封装等；

架构演变第八步：增加更多的webserver

在做完分库分表这些工作后，数据库上的压力已经降到比较低了，又开始过着每天看着访问量暴增的幸福生活了，突然有一天，发现系统的访问又开始有变慢的趋势 了，这个时候首先查看数据库，压力一切正常，之后查看webserver，发现apache阻塞了很多的请求，而应用服务器对每个请求也是比较快的，看来 是请求数太高导致需要排队等待，响应速度变慢，这还好办，一般来说，这个时候也会有些钱了，于是添加一些webserver服务器，在这个添加 webserver服务器的过程，有可能会出现几种挑战：
1、Apache的软负载或LVS软负载等无法承担巨大的web访问量（请求连接数、网络流量等）的调度了，这个时候如果经费允许的话，会采取的方案是购 买硬件负载，例如F5、Netsclar、Athelon之类的，如经费不允许的话，会采取的方案是将应用从逻辑上做一定的分类，然后分散到不同的软负载集群中；
2、原有的一些状态信息同步、文件共享等方案可能会出现瓶颈，需要进行改进，也许这个时候会根据情况编写符合网站业务需求的分布式文件系统等；
在做完这些工作后，开始进入一个看似完美的无限伸缩的时代，当网站流量增加时，应对的解决方案就是不断的添加webserver。

看看这一步完成后系统的图示：

这一步涉及到了这些知识体系：

到了这一步，随着机器数的不断增长、数据量的不断增长和对系统可用性的要求越来越高，这个时候要求对所采用的技术都要有更为深入的理解，并需要根据网站的需求来做更加定制性质的产品。

架构演变第九步：数据读写分离和廉价存储方案

突然有一天，发现这个完美的时代也要结束了，数据库的噩梦又一次出现在眼前了，由于添加的webserver太多了，导致数据库连接的资源还是不够用，而这个时候又已经分库分表了，开始分析数据库的压力状况，可能会发现数据库的读写比很高，这个时候通常会想到数据读写分离的方案，当然，这个方案要实现并不 容易，另外，可能会发现一些数据存储在数据库上有些浪费，或者说过于占用数据库资源，因此在这个阶段可能会形成的架构演变是实现数据读写分离，同时编写一些更为廉价的存储方案，例如BigTable这种。

看看这一步完成后系统的图示：

这一步涉及到了这些知识体系：

数据读写分离要求对数据库的复制、standby等策略有深入的掌握和理解，同时会要求具备自行实现的技术；

廉价存储方案要求对OS的文件存储有深入的掌握和理解，同时要求对采用的语言在文件这块的实现有深入的掌握。

架构演变第十步：进入大型分布式应用时代和廉价服务器群梦想时代

经过上面这个漫长而痛苦的过程，终于是再度迎来了完美的时代，不断的增加webserver就可以支撑越来越高的访问量了，对于大型网站而言，人气的重要毋 庸置疑，随着人气的越来越高，各种各样的功能需求也开始爆发性的增长，这个时候突然发现，原来部署在webserver上的那个web应用已经非常庞大 了，当多个团队都开始对其进行改动时，可真是相当的不方便，复用性也相当糟糕，基本是每个团队都做了或多或少重复的事情，而且部署和维护也是相当的麻烦， 因为庞大的应用包在N台机器上复制、启动都需要耗费不少的时间，出问题的时候也不是很好查，另外一个更糟糕的状况是很有可能会出现某个应用上的bug就导 致了全站都不可用，还有其他的像调优不好操作（因为机器上部署的应用什么都要做，根本就无法进行针对性的调优）等因素，根据这样的分析，开始痛下决心，将 系统根据职责进行拆分，于是一个大型的分布式应用就诞生了，通常，这个步骤需要耗费相当长的时间，因为会碰到很多的挑战：
1、拆成分布式后需要提供一个高性能、稳定的通信框架，并且需要支持多种不同的通信和远程调用方式；
2、将一个庞大的应用拆分需要耗费很长的时间，需要进行业务的整理和系统依赖关系的控制等；
3、如何运维（依赖管理、运行状况管理、错误追踪、调优、监控和报警等）好这个庞大的分布式应用。
经过这一步，差不多系统的架构进入相对稳定的阶段，同时也能开始采用大量的廉价机器来支撑着巨大的访问量和数据量，结合这套架构以及这么多次演变过程吸取的经验来采用其他各种各样的方法来支撑着越来越高的访问量。

看看这一步完成后系统的图示：

这一步涉及到了这些知识体系：

这一步涉及的知识体系非常的多，要求对通信、远程调用、消息机制等有深入的理解和掌握，要求的都是从理论、硬件级、操作系统级以及所采用的语言的实现都有清楚的理解。

运维这块涉及的知识体系也非常的多，多数情况下需要掌握分布式并行计算、报表、监控技术以及规则策略等等。

说起来确实不怎么费力，整个网站架构的经典演变过程都和上面比较的类似，当然，每步采取的方案，演变的步骤有可能有不同，另外，由于网站的业务不同，会有不同的专业技术的需求，这篇blog更多的是从架构的角度来讲解演变的过程，当然，其中还有很多的技术也未在此提及，像数据库集群、数据挖掘、搜索等，但在真实的演变过程中还会借助像提升硬件配置、网络环境、改造操作系统、CDN镜像等来支撑更大的流量，因此在真实的发展过程中还会有很多的不同，另外一个大型网站要做到的远远不仅仅上面这些，还有像安全、运维、运营、服务、存储等，要做好一个大型的网站真的很不容易，写这篇文章更多的是希望能够引出更多大型网站架构演变的介绍 。

ps:最后附上几篇LiveJournal架构演变的文章：
从LiveJournal后台发展看大规模网站性能优化方法
http://blog.zhangjianfeng.com/article/743
另外从这里：http://www.danga.com/words/大家可以找到更多关于现在LiveJournal网站架构的介绍。

情人节快乐


google的图标居然也随之变化，很吃惊
gXOgle? 你没看错. 酒红色的G__gle字母形状没有变化, 中间两个O消失了, 取而代之的是用口红画上去的"xo"两个字母. 以上就是Google 2009情人节的logo图案. 由于时差关系, 谷歌换用logo的时候, google.com还没有换. 其他同在亚洲时区的国家也相继换用了此logo. 第一眼看到X和O, 肯定会想到一个网络名词: "OOXX". 不过, 这可是纯正的中国特色词语, 难道老外也有这种用法吗? 还是, 另有所指? 下面还是请大家欣赏一下这个logo, 然后跟随我们的文章猜想一下为什么logo会是这个样子.
无论如何, 祝所有情侣和所有去死团团员们, 情人节快乐!

XE的说法1: 网络语言"OOXX"

“OOXX online”本来是一款极限单车游戏的名字。“OOXX”即“圈圈叉叉”，就是指单车的车圈和车叉。这款游戏惊险刺激深受年轻人喜爱，因而逐渐引申为“ 惊险刺激的PK”之义。 而后，由于“圈圈叉叉”会被误读或误写作其同音字(和谐)，从而“OOXX”就开始具备一些(和谐)的含义了，也就是(和谐)的意思。同时，因为(和谐) 在国人的传统观念中是见不得人的，所以“OOXX”在一些论坛中也指，因作坏事或说错话而被管理员封贴或封号。 有了(和谐)的意思之后，网路上众多具有高度语言天赋和智慧的达人，就真正开始YY和BT这个词了。用象形解释的话, “OO”和“XX”在(和谐)中就拥有了性别上的区分。从而，最终极最强的解释和引申就出现了：“OOXX”指“女上男下”，“XXOO”指 “男上女下”.

摘自百度知道(关键部分请脑内补完).

字面意思的说法2: "XO"

xo是指白兰地中的专用术语. 所有白兰地酒厂, 都用字母来分别品质, 例举如下:
E代表ESPECIAL (特别的)
F代表FINE (好)
V代表VERY (很好)
O代表OLD (老的)
S代表SUPERIOR (上好的)
P代表PALE (淡色而苍老)
X代表EXTRA (格外的)

对于干邑的级别, 法国政府有着极为严格的规则,酒商是不能随意自称的。总括而言,有下列之类别:

3-STAR三星干邑：蕴藏期不少于两年
V.S.O.P干邑：蕴藏期不少于四年
NAPOLEON干邑：蕴藏期不少于六年
X.O.干邑：蕴藏期多在八年以上

XO是白兰地的分级法中，算储存较久的一级。不过在法国的白兰地，除了法国政府所规定的事项外，各厂家为了凸显自己酒款的优势，常常做出比规定更严格条件，使的各家酒款都有自己的特色。而HENNESSY(轩尼诗)也是其中的一家。

摘自百度百科

有点儿靠谱的说法3: Hugs & Kisses

Inmedieval times, most people were unable to read or write. When it came time to sign a document, people who could not write usually made an "X" mark. Of course,an "X" is not much of a signature.To add a sense of commitment, it became customary to kiss the "X" after writing it.

在中世纪, 大多数人的文化水平都比较低. 在签署文件的时候, 中国人一般按手印, 西方人如果不知名字怎么写, 通常写一个"X"作为代替. 当然"X"本身不能作为签名, 为了添加个人信息, 通常会在那个"X"上亲吻一下.

Kissing the "X" was "performance law," a ritual act that bound thepartiesthe way legal documents bind us today. This act, witnessed by the person who wrote the text, represented asolemn guaranteeof the truthfulness of what was written, and an oath to carry out whatever obligations were stated in the document.

亲吻"X"是一项不成文的法则, 就象现在法律文档对我们的约束力一般. 这表明签字人对所写的东西保证其真实有效, 勇于对所写内容承担责任.

Over the years, the "X" and the kiss became interchangeable. Today, people who can read and write might still add one or more "X" marks to their letters, maybe with a couple of "O"s thrown in for hugs.

许多年过去了, "X"变成了和亲吻等价的符号. 人们在写信时加上"X"代表亲吻, 同时加上"O"则表示一个拥抱.

The Oxford English Dictionary states that X is "used to represent a kiss, esp. in the subscription to a letter.". There is no general consensus on the origins of the O as a hug. The O could relate to the shape formed when two hands are crossed in a hug, forming a type of O. The 'X' may also refer to the pursing of the lips when kissing.

牛津英语字典叙述 X 为“用于表达吻，尤其在书信的署名处”。但对于作为拥抱含义的 O 的起源并没有普遍共识。字母 O 可能与拥抱时两手交叠而成 O 的形状有关系。字母 X 可能也与接吻时噘起嘴唇而成的形状有关。

Google往年情人节logo

昨天上班、下班乘公车发现有趣的事情还是挺多。人生都这样吧，大概。

上班的时候，乘856，有位仁兄和电子报站器同步播音。开始的时候我被吓了一跳，电子报站器怎么破音了？后来才发现是这位仁兄在辛苦的为公车乘客们提供方便。

晚上下班的时候，看到两个黄皮肤，黑眼睛的人在聊天，聊什么我没听懂，他们很投入，我也不能打断别人是吧。这一男一女兴致极高，知道我听不懂他们说的洋文，然后就很投入的在说。
那位男青年，说的是很流畅，女青年则非常生疏，几乎就是一个单词一个单词的往外蹦。很是乐此不彼。

感慨不算多。

顺便，听说户籍制度要改革了，但好象我并在制度范围内，可怜的。。。

其实真的很吃惊，但后来想想，又觉得是可以接受的。试想Gphone连debian都能装上，这个iphone装一个web server又怎么样呢？
原文如下：http://apple4.us/2009/02/the-iphone-becomes-a-web-server.html

苹果经常在自己的广告里吹嘘，App Store 里的数万种应用几乎能让你的iPhone 无所不能，不过有时候他们的确不是在吹牛。

最新的一例就是，一款名叫 ServersMan@iPhone [App Store 链接] 的应用能够将你的 iPhone 变成一台功能成熟的 Web 服务器。该应用开发者是位于东京的 FreeBit 公司，该公司的主要业务是向其他虚拟网络运营商(VNO) 及互联网服务商(ISPs)提供网络平台。

当 iPhone 安装并启用这一应用后，普通的联网电脑能够像访问服务器一样通过网络浏览器访问该 iPhone 并上载或下载文件，甚至还可以使用 webDAV 协议。如果 PC 与 iPhone 处于同一个网络中，PC 可以直接连接到 iPhone ；如果 PC 与 iPhone 分别处于不同的网络中，FreeBit 的虚拟专用网络(VPN)软件能够帮助两者实现连接。

至于该应用的名字“ServersMan” 的来历，开发者称是源于索尼的 WalkMan，索尼公司前 CEO 出井伸之(Nobuyuki Idei) 目前是该公司的商业顾问。

ServersMan 应用目前仅限于日本的 App Store（日文版），开发者表示英文版将于 3 月份发布，此外针对 Windows Mobile 的另一个版本也在开发计划中。

看到这篇文章的时候，我觉得很惊讶，虽然我对这方面的了解并不多，但在自己的想像中，还是对网游这些东西稍有一点想法，因为曾经有朋友做过简单的外挂，比如，抓包发包然后尝试模拟包，来使网游达到你想实现的效果。
外挂这东西，在2003年左右应该是一个巅峰吧，那时候，奇迹外挂、传奇外挂，确实让一部分人先富起来，可是后来的零点行动，这些人都永远的消失在外挂长河中。
那时候我就在想，外挂是什么原理，为什么我这边的动作，可以让服务端产生那样的效果？其实，这就是一个同步的问题，我个人理解是服务器上有个触发器，这边发包后，然后那边判断包是否正常，然后就会有一个相应的动作。当然，动作程序还是在本机上，地图也在本机上，发出去的包，只是告诉服务器我是这样在动作的。于是就出现了瞬移，卡点这种情况，因为发出去的包，和坐标位置在服务器上都是正常的。（以上是我的猜测）

下面是文章：
不知道大家是否碰到过这种情况，当某个玩家发出一个火球，这个火球有自己的运动轨迹，那么如何来判断火球是否打中了人呢？大部分情况，当策划提出这个要求的时候，一般会被程序否认，原因是：太麻烦了，呵呵。复杂点的还有包括两个火球相撞之类的事情发生。

那么网络游戏中，是否真的无法模拟实现这种模拟呢？

首先我们来看看模拟此种操作会带来什么样的麻烦：

1，服务器必须trace火球的运行轨迹，乍一想，挺慢的。

2，网络延迟，传过来有延迟，传过去有延迟，延迟还不稳定，麻烦。

3，都有两点解决不了了，接下来不愿意再想了。

呵呵，实际上呢，对火球的模拟比对人物运动的模拟要轻松很多，原因很简单，火球的方向不会变。下面来看看具体用什么样的结构来实现：

不知道大家是否还记得我去年这个时候提到过的Dead Reckoning算法，我们要模拟火球运动的关键就在于一个叫Moving Objects Tracing Server的服务器程序，这个服务器是干什么的呢。这个服务器接收主游戏服务器发过来的注册事件的信息，比如有个玩家，开始移动了，那么主游戏服务器就 把该玩家的运动PDU，包括方向，速度，加速度，起点发给MOTS (Moving Objects Tracing Server)，然后MOTS自己开始对其运行进行模拟，当游戏服务器发来第二个PDU包的时候，则对各个物件的位置进行修正，并重新开始模拟。那么，我 们模拟的目的是什么呢？当然是发生某些事件，比如说碰撞，或者掉入地图的某个陷阱的时候，会将该事件回发给主逻辑服务器。然后逻辑服务器来处理该事件。

那么，对于火球的处理，也和处理其他玩家的同步一样，当接收到玩家的发火球的指令以后，产生一个火球，并指定其PDU信息，在MOTS上注册该个运 动物 体。当MOTS自行模拟到这个物体和其他玩家或者NPC物体产生碰撞，则通知主逻辑服务器，然后主逻辑服务器产生相应的动作。

那么关于延迟呢？有些人也许会说，比如说前面有个火球，我本地操纵的小人其实躲过去了，但是因为网络延迟，在服务器上我并没有躲过去，那么怎么算？ 呵呵， 不知道大家玩过星际没有，有没有发现在星际中玩多人连线模式的时候，有一点最特别的地方，就是控制一个小兵的时候，点了地图上的某个位置，但是小兵并不会 马上开始移动，而是有一定的延迟，但是这一小点延迟并不能掩盖星际的经典，同样的理论用到这里也成立。对于客户端的控制，当玩家操纵的主角改变PDU信息 的时候，确保信息发送到服务器之后，再开始处理本地的操作指令，这样就能保证本地的预测和服务器的预测几乎是没有什么误差的，即使有很小的误差产生，以服 务器为主，这样玩家也不会有太大的抱怨。

————————————————————————————————————————-

网络游戏同步详解之一

同步在网络游戏中是非常重要的，它保证了每个玩家在屏幕上看到的东西大体是一样的。其实呢，解决同步问题的最简单的方法就是把每个玩家的动作都向其 他玩家广播一遍，这里其实就存在两个问题：1，向哪些玩家广播，广播哪些消息。2，如果网络延迟怎么办。事实上呢，第一个问题是个非常简单的问题，不过之 所以我提出这个问题来，是提醒大家在设计自己的消息结构的时候，需要把这个因素考虑进去。而对于第二个问题，则是一个挺麻烦的问题，大家可以来看这么个例 子：
比如有一个玩家A向服务器发了条指令，说我现在在P1点，要去P2点。指令发出的时间是T0，服务器收到指令的时间是T1，然后向周围的玩家广播这条 消息，消息的内容是“玩家A从P1到P2”有一个在A附近的玩家B，收到服务器的这则广播的消息的时间是T2，然后开始在客户端上画图，A从P1到P2 点。这个时候就存在一个不同步的问题，玩家A和玩家B的屏幕上显示的画面相差了T2-T1的时间。这个时候怎么办呢？

有个解决方案，我给它取名叫预测拉扯，虽然有些怪异了点，不过基本上大家也能从字面上来理解它的意思。要解决这个问题，首先要定义一个值叫：预 测误差。然后需要在服务器端每个玩家连接的类里面加一项属性，叫TimeModified，然后在玩家登陆的时候，对客户端的时间和服务器的时间进行比 较，得出来的差值保存在TimeModified里面。还是上面的那个例子，服务器广播消息的时候，就根据要广播对象的TimeModified，计算出 一个客户端的CurrentTime，然后在消息头里面包含这个CurrentTime，然后再进行广播。并且同时在玩家A的客户端本地建立一个队列，保 存该条消息，只到获得服务器验证就从未被验证的消息队列里面将该消息删除，如果验证失败，则会被拉扯回P1点。然后当玩家B收到了服务器发过来的消息“玩 家A从P1到P2”这个时候就检查消息里面服务器发出的时间和本地时间做比较，如果大于定义的预测误差，就算出在T2这个时间，玩家A的屏幕上走到的地点 P3，然后把玩家B屏幕上的玩家A直接拉扯到P3，再继续走下去，这样就能保证同步。更进一步，为了保证客户端运行起来更加smooth，我并不推荐直接 把玩家拉扯过去，而是算出P3偏后的一点P4，然后用(P4-P1)/T(P4-P3)来算出一个很快的速度S，然后让玩家A用速度S快速移动到P4，这 样的处理方法是比较合理的，这种解决方案的原形在国际上被称为（Full plesiochronous），当然，该原形被我篡改了很多来适应网络游戏的同步，所以而变成所谓的：预测拉扯。

另外一个解决方案，我给它取名叫验证同步，听名字也知道，大体的意思就是每条指令在经过 服务器验证通过了以后再执行动作。具体的思路如下：首先 也需要在每个玩家连接类型里面定义一个 TimeModified，然后在客户端响应玩家鼠标行走的同时，客户端并不会先行走动，而是发一条走路的指令给服务器，然后等待服务器的验证。服务器接 受到这条消息以后，进行逻辑层的验证，然后计算出需要广播的范围，包括玩家A在内，根据各个客户端不同的TimeModified生成不同的消息头，开始 广播，这个时候这个玩家的走路信息就是完全同步的了。这个方法的优点是能保证各个客户端之间绝对的同步，缺点是当网络延迟比较大的时候，玩家的客户端的行 为会变得比较不流畅，给玩家带来很不爽的感觉。该种解决方案的原形在国际上被称为（Hierarchical master-slave synchronization），80年代以后被广泛应用于网络的各个领域。

最后一种解决方案是一种理想化的解决方案，在国际上被称为Mutual synchronization，是一种对未来网络的前景的良好预测出来的解决方案。这里之所以要提这个方案，并不是说我们已经完全的实现了这种方案，而 只是在网络游戏领域的某些方面应用到这种方案的某些思想。我对该种方案取名为：半服务器同步。大体的设计思路如下：

首先客户端需要在登陆世界的时候建立很多张广播列表，这些列表在客户端后台和服务器要进行不及时同步，之所以要建立多张列表，是因为要广播的类 型是不止一种的，比如说有local message,有remote message,还有global message 等等，这些列表都需要在客户端登陆的时候根据服务器发过来的消息建立好。在建立列表的同时，还需要获得每个列表中广播对象的TimeModified，并 且要维护一张完整的用户状态列表在后台，也是不及时的和服务器进行同步，根据本地的用户状态表，可以做到一部分决策由客户端自己来决定，当客户端发送这部 分决策的时候，则直接将最终决策发送到各个广播列表里面的客户端，并对其时间进行校对，保证每个客户端在收到的消息的时间是和根据本地时间进行校对过的。 那么再采用预测拉扯中提到过的计算提前量，提高速度行走过去的方法，将会使同步变得非常的smooth。该方案的优点是不通过服务器，客户端自己之间进行 同步，大大的降低了由于网络延迟而带来的误差，并且由于大部分决策都可以由客户端来做，也大大的降低了服务器的资源。由此带来的弊端就是由于消息和决策权 都放在客户端本地，所以给外挂提供了很大的可乘之机。

综合以上三种关于网络同步派系的优缺点，综合出一套关于网络游戏传输同步的较完整的解决方案，我称它为综合同步法（colligate synchronization）。大体设计思路如下：

首先将服务器需要同步的所有消息从划分一个优先等级，然后按照3/4的比例划分出重要消息和非重要消息，对于非重要消息，把决策权放在客户端，在客户端逻辑上建立相关的决策机构和各种消息缓存区，以及相关的消息缓存区管理机构，如下图所示：

上图简单说明了对于非重要消息，客户端的大体处理流程，其中有一个客户端被动行为值得大家注意，其中包括对服务器发过来的某些验证代码做返回， 来确保消息缓存中的消息和服务器端是一致的，从而有效的防止外挂来篡改本地消息缓存。其中的消息来源是包括本地的客户端响应玩家的消息以及远程服务器传递 过来的消息。

对于重要消息，比如说战斗或者是某些牵扯到玩家一些比较敏感数据的操作，则采用另外一套方案，该方案首先需要在服务器和客户端之间建立一套 Ping System，然后服务器保存和用户的及时的ping值，当ping比较小的时候，响应玩家消息的同时先不进行动作，而是先把该消息反馈给服务器，并且阻 塞，服务器收到该消息，进行逻辑验证之后向所有该详细广播的有效对象进行广播（包括消息发起者），然后客户端收到该消息的验证，才开始执行动作。而当 ping比较大的时候，客户端响应玩家消息的同时立刻进行动作，并且同时把该消息反馈给服务器，值得注意的是这个时候还需要在本地建立一个无验证消息的队 列，把该消息入队，执行动作的同时等待服务器的验证，还需要保存当前状态。服务器收到客户端的请求后，进行逻辑验证，并把消息反馈到各个客户端，带上各个 客户端校对过的本地时间。如果验证通过不过，则通知消息发起者，该消息验证失败，然后客户端自动把已经在进行中的动作取消，恢复原来状态。如果验证通过， 则广播到的各个客户端根据从服务器获得校对时间进行对其进行拉扯，保证在该行为完成之前完成同步。

至此，一个比较成熟的网络游戏的同步机制已经初步建立起来了，接下来的逻辑代码就根据各自不同的游戏风格以及侧重点来写了。

同步是网络游戏最重要的问题，如何同步也牵扯到各个方面的问题，比如说游戏的规模，游戏的类型以及各种各样的方面，对于规模比较大的游戏，在同 步方面可以下很多的工夫，把消息分得十分的细腻，对于不同的消息采用不同的同步机制，而对于规模比较小的游戏，则可以采用大体上一样的同步机制，究竟怎么 样同步，没有个定式，是需要根据自己的不同情况来做出不同的同步决策的网游同步算法之导航推测（Dead Reckoning）算法：

——————————————————————————————————————————

网络游戏同步详解之二

在了解该算法前，我们先来谈谈该算法的一些背景资料。大家都知道，在网络传输的时候，延迟现象是很普遍的，而在基于Server/Client结构 下的网络游戏的同步也就成了很头疼的问题，在保证客户端响应用户本地指令流畅的情况下，没法有效的保证的同步的及时性。同样，在军方也有类似的事情发生， 即使是同一LAN里面的机器，也会因为传输的延迟，导致一些运算的失误，介于此，美国国防部投入了大量的资金用于研究一种比较的好的方案来解决分布式系统 中的延迟问题，特别是一个叫分布式模拟运动（Distributed Interactive Simulation）的系统，这套系统呢，其中就提出了一套号称是Latency Hiding & Bandwidth Reduction的方案，命名为Dead Reckoning。呵呵，来头很大吧，恩，那么我们下面就来看看这套系统的一些观点，以及我们如何把它运用到我们的网络游戏的同步中。

首先，这套同步方案是基于我那篇《网络游戏的同步》一文中的Mutual Synchronization同步方案的，也就是说，它并不是Server/Client结构的，而是基于客户端之间的同步的。下面我们先来说一些本文中将用到的名词概念：
网状网络：客户端之间构成的网络
节点：网状网络中的每个客户端
极限误差：进行同步的时候可能产生的误差的极值

恩，在探讨其原理的之前，我们先来看看我们需要一个什么样的环境。首先，需要一个网状网络，网状网络如何构成呢？当有新节点进入的时候，通知该 网络里面的所有节点，各节点为该客户端在本地创建一个副本，登出的时候，则通知所有节点销毁本地关于该节点的副本。然后每个节点该保存一些什么数据呢？首 先有一个很重要的包需要保存，叫做协议数据包（PDU Protocol Data Unit），PDU包含节点的一些相关的运动信息，比如当前位置，速度，运动方向，或者还有加速度等一些信息。除PDU之外，还有其他信息需要保存，比如 说节点客户端人物的HP，MP之类的。然后，保证每个节点在最少8秒之内要向其它节点广播一次PDU信息。最后，设置一个极限误差值。到此，其环境就算搭 建完成了。下面，我们就来看看相关的具体算法：

假设在节点A有一个小人（路人甲），开始跑路了，这个时候，就像所有的节点广播一次他的PDU信息，包括：速度（S），方向（O），加速度 （A）。那么所有的节点就开始模拟路人甲的运动轨迹和路线，包括节点A本身（这点很重要），同时，路人甲在某某玩家的控制下，会不时的改变一下方向，让其 跑路的路线变得不是那么正规。在跑路的过程中，节点A有一个值在不停的记录着其真实坐标和在后台模拟运动的坐标的差值，当差值大于极限误差的时候，则计算 出当前的速度S，方向O和速度A（算法将在后面介绍），并广播给网络中其他所有节点。其他节点在收到这条消息之后呢，就可以用一些很平滑的移动把路人甲拉 扯过去，然后重新调整模拟跑路的数据，让其继续在后台模拟跑路。

很显然，如果极限误差定义得大了，其他节点看到的偏差就会过大，如果极限偏差定义得小了，网络带宽就会增大。如果定义这个极限误差，就该根据各 种数据的重要性来设计了。如果是回合制的网络游戏，那么在走路上把极限误差定义得大些无所谓，可以减少带宽。但是如果是及时打斗的网络游戏，那么就得把极 限误差定义得小一些，否则会出现某人看到某人老远把自己给砍死的情况。

Dead Reckoning的主要算法有9种，但是只有两种是解决主要问题的，其他的基本上只是针对不同的坐标系的一些不同的算法，这里就不一一介绍了。好，那么我们下面来看传说中的最主要的两种算法：
第一：目标点 = 原点 + 速度 * 时间差
第二：目标点 = 原点 + 速度 * 时间差 + 1/2 * 加速度 * 时间差
呵呵，传说中的算法都是很经典的，虽然我们早在初中物理的时候就学过。

该算法的好处呢，正如它开始所说的，Latency Hiding & Bandwidth Reduction，从原则上解决了网络延迟导致的不同步的问题，并且有效的减少了带宽，不好的地方就是该算法基本上只能使用于移动中的同步，当然，移动 的同步是网络游戏中同步的最大的问题。

该方法结合我在《网络游戏的同步》一文中提出的综合同步法的构架可以基本上解决掉网络游戏中走路同步的问题。相关问题欢迎大家一起讨论。

有关导航推测算法（Dead Reckoning）中的平滑处理：

根据我上篇文章所介绍的，在节点A收到节点B新的PDU包时，如果和A本地的关于B的模拟运动的坐标不一致时，怎么样在A的屏幕上把B拽到新的 PDU包所描叙的点上面去呢，上文中只提了用“很平滑的移动”把B“拉扯”过去，那么实际中应该怎么操作呢？这里介绍四种方法。

第一种方法，我取名叫直接拉扯法，大家听名字也知道，就是直接把B硬生生的拽到新的PDU包所描叙的坐标上去，该方法的好处是：简单。坏处是：看了以下三种方法之后你就不会用这种方法了。

第二种方法，叫直线行走（Linear），即让B从它的当前坐标走直线到新的PDU包所描叙的坐标，行走速度用上文中所介绍的经典算法：
目标点 = 原点 + 速度 * 时间差 + 1/2 * 加速度 * 时间差算出：
首先算出从当前坐标到PDU包中描叙的坐标所需要的时间：
T = Dest( TargetB – OriginB ) / Speed
然后根据新PDU包中所描叙的坐标信息模拟计算出在时间T之后，按照新的PDU包中的运动信息所应该达到的位置：
_TargetB = NewPDU.Speed * T
然后根据当前模拟行动中的B和_TargetB的距离配合时间T算出一个修正过的速度_S：
_S = Dest( _TargetB – OriginB ) / T
然后在画面上让B以速度_S走直线到Target_B，并且在走到之后调整其速度，方向，加速度等信息为新的PDU包中所描叙的。

这种方法呢，非常的土，会让物体在画面上移动起来变得非常的不现实，经常会出现很生硬的拐角，而且对于经常要修改的速度_S，在玩家A的画面上，玩家B的行动会变得非常的诡异。其好处是：比第一种方法要好。

第三种方法，叫二次方程行走（Quadratic），该方法的原理呢，就是在直线行走的过程中，加入二次方程来计算一条曲线路径，让Dest( _TargetB – OriginB )的过程是一条曲线，而不是一条直线，恩，具体的实现方法，就是在Linear方法的计算中，设定一个二次方程，在Dest函数计算距离的时候根据设定的 二次方程来计算，这样一来，可以使B在玩家A屏幕上的移动变得比较的有人性化一些。但是该方法的考虑也是不周全的，仅仅只考虑了TargetB到 _TargetB的方向，而没有考虑新的PDU包中的方向描叙，那么从_TargetB开始模拟行走的时候，仍然是会出现比较生硬的拐角，那么下面提出的 最终解决方案，将彻底解决这个问题。

——————————————————————————————————————————

网络游戏同步详解之三

最后一种方法叫：立方体抖动（Cubic Splines），这个东东比较复杂，它需要四个坐标信息作为它的参数来进行运算，第一个参数Pos1是OriginB，第二个参数Pos2是 OriginB在模拟运行一秒以后的位置，第三个参数Pos3是到达_TargetB前一秒的位置，第四个参数pos4是_TargetB的位置。

Struct pos {
Coordinate X;
Coordinate Y;
}
Pos1 = OriginB
Pos2 = OriginB + V
Pos3 = _TargetB – V
Pos4 = _TargetB
运动轨迹中(x, y)的坐标。
x = At^3 + Bt^2 + Ct + D
y = Et^3 + Ft^2 + Gt + H
（其中时间t的取值范围为0-1，在Pos1的时候为0，在Pos4的时候为1）
x(0-3)代表Pos1-Pos4中x的值，y(0-3)代表Pos1-Pos4中y的值
A = x3 – 3 * x2 +3 * x1 – x0
B = 3 * x2 – 6 * x1 + 3 * x0
C = 3 * x1 – 3 * x0
D = x0
E = y3 – 3 * y2 +3 * y1 – y0
F = 3 * y2 – 6 * y1 + 3 * y0
G = 3 * y1 – 3 * y0
H = y0

上面是公式，那么下面我们来看看如何获得Pos1-Pos4：首先，Pos1和 Pos2的取值会比较容易获得，根据OriginB配合当前的速度和方向可以获得，然而Pos3和Pos4呢，怎么获得呢？如果在从Pos1到Pos4的 过程中有新的PDU到达，那么我们定义它为NewPackage。

Pos3 = NewPackage.X + NewPackage.Y * t + 1/2 * NewPackage.a * t^2
Pos4 = Pos3 – (NewPackage.V + NewPackage.a * t)

如果没有NewPackage的情况下,则Pos3和Pos4按照开始所规定的方法获得。

至此，关于导航推测的算法大致介绍完毕。

原文来自：http://xinsync.xju.edu.cn/index.php/archives/4079