High-Performance Server Architecture
高性能服务器架构
来源：http://pl.atyp.us/content/tech/servers.html
译文来源：http://www.lupaworld.com/home/space-341888-do-blog-id-136718.html
（map注：本人看了一遍，“于我心有戚戚焉”，翻译得也很好，于是整理了一下，重新发布，备忘）
引言
本文将与你分享我多年来在服务器开发方面的一些经验。对于这里所说的服务器，更精确的定义应该是每秒处理大量离散消息或者请求的服务程序，网络服务器更符合这种情况，但并非所有的网络程序都是严格意义上的服务器。使用“高性能请求处理程序”是一个很糟糕的标题，为了叙述起来简单，下面将简称为“服务器”。
本文不会涉及到多任务应用程序，在单个程序里同时处理多个任务现在已经很常见。比如你的浏览器可能就在做一些并行处理，但是这类并行程序设计没有多大挑战性。真正的挑战出现在服务器的架构设计对性能产生制约时，如何通过改善架构来提升系统性能。对于在拥有上G内存和G赫兹CPU上运行的浏览器来说，通过DSL进行多个并发下载任务不会有如此的挑战性。这里，应用的焦点不在于通过吸管小口吮吸，而是如何通过水龙头大口畅饮，这里麻烦是如何解决在硬件性能的制约.(作者的意思应该是怎么通过网络硬件的改善来增大流量)
一些人可能会对我的某些观点和建议发出置疑，或者自认为有更好的方法, 这是无法避免的。在本文中我不想扮演上帝的角色；这里所谈论的是我自己的一些经验，这些经验对我来说, 不仅在提高服务器性能上有效，而且在降低调试困难度和增加系统的可扩展性上也有作用。但是对某些人的系统可能会有所不同。如果有其它更适合于你的方法，那实在是很不错. 但是值得注意的是，对本文中所提出的每一条建议的其它一些可替代方案，我经过实验得出的结论都是悲观的。你自己的小聪明在这些实验中或许有更好的表现，但是如果因此怂恿我在这里建议读者这么做，可能会引起无辜读者的反感。你并不想惹怒读者，对吧？
本文的其余部分将主要说明影响服务器性能的四大杀手:
1) 数据拷贝（Data Copies）
2) 环境切换（Context Switches）
3) 内存分配（Memory allocation）
4) 锁竞争（Lock contention）
在文章结尾部分还会提出其它一些比较重要的因素，但是上面的四点是主要因素。如果服务器在处理大部分请求时能够做到没有数据拷贝，没有环境切换，没有内存分配，没有锁竞争，那么我敢保证你的服务器的性能一定很出色。
数据拷贝（Data Copies）
本节会有点短，因为大多数人在数据拷贝上吸取过教训。几乎每个人都知道产生数据拷贝是不对的，这点是显而易见的，在你的职业生涯中, 你很早就会见识过它；而且遇到过这个问题，因为10年前就有人开始说这个词。对我来说确实如此。现今，几乎每个大学课程和几乎所有how-to文档中都提到了它。甚至在某些商业宣传册中，"零拷贝" 都是个流行用语。
尽管数据拷贝的坏处显而易见，但是还是会有人忽视它。因为产生数据拷贝的代码常常隐藏很深且带有伪装，你知道你所调用的库或驱动的代码会进行数据拷贝吗？答案往往超出想象。猜猜“程序I/O”在计算机上到底指什么？哈希函数是伪装的数据拷贝的例子，它有带拷贝的内存访问消耗和更多的计算。曾经指出哈希算法是一种有效的“拷贝+”似乎能够被避免，但据我所知，有一些非常聪明的人说过要做到这一点是相当困难的。如果想真正去除数据拷贝，不管是因为影响了服务器性能，还是想在黑客大会上展示"零复制”技术，你必须自己跟踪可能发生数据拷贝的所有地方，而不是轻信宣传。
有一种可以避免数据拷贝的方法是使用buffer的描述符（或者buffer chains的描述符）来取代直接使用buffer指针，每个buffer描述符应该由以下元素组成：
l 一个指向buffer的指针和整个buffer的长度
l 一个指向buffer中真实数据的指针和真实数据的长度，或者长度的偏移
l 以双向链表的形式提供指向其它buffer的指针
l 一个引用计数
现在，代码可以简单的在相应的描述符上增加引用计数来代替内存中数据的拷贝。这种做法在某些条件下表现的相当好，包括在典型的网络协议栈的操作上，但有些情况下这做法也令人很头大。一般来说，在buffer chains的开头和结尾增加buffer很容易，对整个buffer增加引用计数，以及对buffer chains的即刻释放也很容易。在chains的中间增加buffer，一块一块的释放buffer，或者对部分buffer增加引用技术则比较困难。而分割，组合chains会让人立马崩溃。
我不建议在任何情况下都使用这种技术，因为当你想在链上搜索你想要的一个块时，就不得不遍历一遍描述符链，这甚至比数据拷贝更糟糕。最适用这种技术地方是在程序中大的数据块上，这些大数据块应该按照上面所说的那样独立的分配描述符，以避免发生拷贝，也能避免影响服务器其它部分的工作.(大数据块拷贝很消耗CPU,会影响其它并发线程的运行)。
关于数据拷贝最后要指出的是：在避免数据拷贝时不要走极端。我看到过太多的代码为了避免数据拷贝，最后结果反而比拷贝数据更糟糕，比如产生环境切换或者一个大的I/O请求被分解了。数据拷贝是昂贵的，但是在避免它时，是收益递减的(意思是做过头了，效果反而不好)。为了除去最后少量的数据拷贝而改变代码，继而让代码复杂度翻番，不如把时间花在其它方面。
上下文切换（Context Switches）
相对于数据拷贝影响的明显，非常多的人会忽视了上下文切换对性能的影响。在我的经验里，比起数据拷贝，上下文切换是让高负载应用彻底完蛋的真正杀手。系统更多的时间都花费在线程切换上，而不是花在真正做有用工作的线程上。令人惊奇的是，（和数据拷贝相比）在同一个水平上，导致上下文切换原因总是更常见。引起环境切换的第一个原因往往是活跃线程数比CPU个数多。随着活跃线程数相对于CPU个数的增加，上下文切换的次数也在增加，如果你够幸运，这种增长是线性的，但更常见是指数增长。这个简单的事实解释了为什么每个连接一个线程的多线程设计的可伸缩性更差。对于一个可伸缩性的系统来说，限制活跃线程数少于或等于CPU个数是更有实际意义的方案。曾经这种方案的一个变种是只使用一个活跃线程，虽然这种方案避免了环境争用，同时也避免了锁，但它不能有效利用多CPU在增加总吞吐量上的价值，因此除非程序无CPU限制（non-CPU-bound），(通常是网络I/O限制 network-I/O-bound)，应该继续使用更实际的方案。
一个有适量线程的程序首先要考虑的事情是规划出如何创建一个线程去管理多连接。这通常意味着前置一个select/poll, 异步I/O，信号或者完成端口，而后台使用一个事件驱动的程序框架。关于哪种前置API是最好的有很多争论。 Dan Kegel的C10K在这个领域是一篇不错的论文。个人认为，select/poll和信号通常是一种丑陋的方案，因此我更倾向于使用AIO或者完成端口，但是实际上它并不会好太多。也许除了select()，它们都还不错。所以不要花太多精力去探索前置系统最外层内部到底发生了什么。
对于最简单的多线程事件驱动服务器的概念模型, 其内部有一个请求缓存队列，客户端请求被一个或者多个监听线程获取后放到队列里，然后一个或者多个工作线程从队列里面取出请求并处理。从概念上来说，这是一个很好的模型，有很多用这种方式来实现他们的代码。这会产生什么问题吗？引起环境切换的第二个原因是把对请求的处理从一个线程转移到另一个线程。有些人甚至把对请求的回应又切换回最初的线程去做，这真是雪上加霜，因为每一个请求至少引起了2次环境切换。把一个请求从监听线程转换到成工作线程，又转换回监听线程的过程中，使用一种“平滑”的方法来避免环境切换是非常重要的。此时，是否把连接请求分配到多个线程，或者让所有线程依次作为监听线程来服务每个连接请求，反而不重要了。
即使在将来,也不可能有办法知道在服务器中同一时刻会有多少激活线程.毕竟，每时每刻都可能有请求从任意连接发送过来，一些进行特殊任务的“后台”线程也会在任意时刻被唤醒。那么如果你不知道当前有多少线程是激活的，又怎么能够限制激活线程的数量呢？根据我的经验，最简单同时也是最有效的方法之一是：用一个老式的带计数的信号量，每一个线程执行的时候就先持有信号量。如果信号量已经到了最大值，那些处于监听模式的线程被唤醒的时候可能会有一次额外的环境切换,(监听线程被唤醒是因为有连接请求到来, 此时监听线程持有信号量时发现信号量已满,所以即刻休眠), 接着它就会被阻塞在这个信号量上，一旦所有监听模式的线程都这样阻塞住了，那么它们就不会再竞争资源了，直到其中一个线程释放信号量，这样环境切换对系统的影响就可以忽略不计。更主要的是，这种方法使大部分时间处于休眠状态的线程避免在激活线程数中占用一个位置，这种方式比其它的替代方案更优雅。
一旦处理请求的过程被分成两个阶段(监听和工作)，那么更进一步，这些处理过程在将来被分成更多的阶段(更多的线程)就是很自然的事了。最简单的情况是一个完整的请求先完成第一步,然后是第二步(比如回应)。然而实际会更复杂：一个阶段可能产生出两个不同执行路径，也可能只是简单的生成一个应答(例如返回一个缓存的值)。由此每个阶段都需要知道下一步该如何做，根据阶段分发函数的返回值有三种可能的做法：
l 请求需要被传递到另外一个阶段（返回一个描述符或者指针）
l 请求已经完成（返回ok）
l 请求被阻塞(返回"请求阻塞")。这和前面的情况一样，阻塞到直到别的线程释放资源
应该注意到在这种模式下，对阶段的排队是在一个线程内完成的，而不是经由两个线程中完成。这样避免不断把请求放在下一阶段的队列里，紧接着又从该队列取出这个请求来执行。这种经由很多活动队列和锁的阶段很没必要。
这种把一个复杂的任务分解成多个较小的互相协作的部分的方式，看起来很熟悉，这是因为这种做法确实很老了。我的方法，源于CAR在1978年发明的"通信序列化进程"(Communicating Sequential Processes CSP)，它的基础可以上溯到1963时的Per Brinch Hansen and Matthew Conway--在我出生之前！然而，当Hoare创造出CSP这个术语的时候，“进程”是从抽象的数学角度而言的，而且，这个CSP术语中的进程和操作系统中同名的那个进程并没有关系。依我看来，这种在操作系统提供的单个线程之内，实现类似多线程一样协同并发工作的CSP的方法，在可扩展性方面让很多人头疼。
一个实际的例子是，Matt Welsh的SEDA，这个例子表明分段执行的(stage-execution)思想朝着一个比较合理的方向发展。SEDA是一个很好的“server Aarchitecture done right”的例子，值得把它的特性评论一下：
1. SEDA的批处理倾向于强调一个阶段处理多个请求，而我的方式倾向于强调一个请求分成多个阶段处理。
2. 在我看来SEDA的一个重大缺陷是给每个阶段申请一个独立的在加载响应阶段中线程“后台”重分配的线程池。结果，原因1和原因2引起的环境切换仍然很多。
3. 在纯技术的研究项目中，在Java中使用SEDA是有用的，然而在实际应用场合，我觉得这种方法很少被选择。
内存分配（Memory Allocator）
申请和释放内存是应用程序中最常见的操作, 因此发明了许多聪明的技巧使得内存的申请效率更高。然而再聪明的方法也不能弥补这种事实:在很多场合中，一般的内存分配方法非常没有效率。所以为了减少向系统申请内存，我有三个建议。
建议一是使用预分配。我们都知道由于使用静态分配而对程序的功能加上人为限制是一种糟糕的设计。但是还是有许多其它很不错的预分配方案。通常认为，通过系统一次性分配内存要比分开几次分配要好，即使这样做在程序中浪费了某些内存。如果能够确定在程序中会有几项内存使用，在程序启动时预分配就是一个合理的选择。即使不能确定，在开始时为请求句柄预分配可能需要的所有内存也比在每次需要一点的时候才分配要好。通过系统一次性连续分配多项内存还能极大减少错误处理代码。在内存比较紧张时，预分配可能不是一个好的选择，但是除非面对最极端的系统环境，否则预分配都是一个稳赚不赔的选择。
建议二是使用一个内存释放分配的lookaside list(监视列表或者后备列表)。基本的概念是把最近释放的对象放到链表里而不是真的释放它，当不久再次需要该对象时，直接从链表上取下来用，不用通过系统来分配。使用lookaside list的一个额外好处是可以避免复杂对象的初始化和清理.
通常，让lookaside list不受限制的增长，即使在程序空闲时也不释放占用的对象是个糟糕的想法。在避免引入复杂的锁或竞争情况下，不定期的“清扫"非活跃对象是很有必要的。一个比较妥当的办法是,让lookaside list由两个可以独立锁定的链表组成：一个"新链"和一个"旧链".使用时优先从"新"链分配，然后最后才依靠"旧"链。对象总是被释放的"新"链上。清除线程则按如下规则运行：
1. 锁住两个链
2. 保存旧链的头结点
3. 把前一个新链挂到旧链的前头
4. 解锁
5. 在空闲时通过第二步保存的头结点开始释放旧链的所有对象。
使用了这种方式的系统中，对象只有在真的没用时才会释放，释放至少延时一个清除间隔期(指清除线程的运行间隔)，但同常不会超过两个间隔期。清除线程不会和普通线程发生锁竞争。理论上来说，同样的方法也可以应用到请求的多个阶段，但目前我还没有发现有这么用的。
使用lookaside lists有一个问题是，保持分配对象需要一个链表指针(链表结点)，这可能会增加内存的使用。但是即使有这种情况，使用它带来的好处也能够远远弥补这些额外内存的花销。
第三条建议与我们还没有讨论的锁有关系。先抛开它不说。即使使用lookaside list,内存分配时的锁竞争也常常是最大的开销。解决方法是使用线程私有的lookasid list, 这样就可以避免多个线程之间的竞争。更进一步，每个处理器一个链会更好，但这样只有在非抢先式线程环境下才有用。基于极端考虑，私有lookaside list甚至可以和一个共用的链工作结合起来使用。
锁竞争（Lock Contention）
高效率的锁是非常难规划的, 以至于我把它称作卡律布狄斯和斯库拉(参见附录)。一方面, 锁的简单化(粗粒度锁)会导致并行处理的串行化,因而降低了并发的效率和系统可伸缩性; 另一方面, 锁的复杂化(细粒度锁)在空间占用上和操作时的时间消耗上都可能产生对性能的侵蚀。偏向于粗粒度锁会有死锁发生，而偏向于细粒度锁则会产生竞争。在这两者之间，有一个狭小的路径通向正确性和高效率，但是路在哪里？
由于锁倾向于对程序逻辑产生束缚，所以如果要在不影响程序正常工作的基础上规划出锁方案基本是不可能的。这也就是人们为什么憎恨锁，并且为自己设计的不可扩展的单线程方案找借口了。
几乎我们每个系统中锁的设计都始于一个"锁住一切的超级大锁"，并寄希望于它不会影响性能，当希望落空时(几乎是必然), 大锁被分成多个小锁，然后我们继续祷告(性能不会受影响)，接着，是重复上面的整个过程(许多小锁被分成更小的锁), 直到性能达到可接受的程度。通常，上面过程的每次重复都回增加大于20%-50%的复杂性和锁负荷，并减少5%-10%的锁竞争。最终结果是取得了适中的效率，但是实际效率的降低是不可避免的。设计者开始抓狂:"我已经按照书上的指导设计了细粒度锁，为什么系统性能还是很糟糕?"
在我的经验里，上面的方法从基础上来说就不正确。设想把解决方案当成一座山，优秀的方案表示山顶，糟糕的方案表示山谷。上面始于"超级锁"的解决方案就好像被形形色色的山谷，凹沟，小山头和死胡同挡在了山峰之外的登山者一样，是一个典型的糟糕爬山法；从这样一个地方开始登顶，还不如下山更容易一些。那么登顶正确的方法是什么？
首要的事情是为你程序中的锁形成一张图表，有两个轴：
l 图表的纵轴表示代码。如果你正在应用剔出了分支的阶段架构(指前面说的为请求划分阶段)，你可能已经有这样一张划分图了，就像很多人见过的OSI七层网络协议架构图一样。
l 图表的水平轴表示数据集。在请求的每个阶段都应该有属于该阶段需要的数据集。
现在，你有了一张网格图，图上每个单元格表示一个特定阶段需要的特定数据集。下面是应该遵守的最重要的规则：两个请求不应该产生竞争，除非它们在同一个阶段需要同样的数据集。如果你严格遵守这个规则，那么你已经成功了一半。
一旦你定义出了上面那个网格图，在你的系统中的每种类型的锁就都可以被标识出来了。你的下一个目标是确保这些标识出来的锁尽可能在两个轴之间均匀的分布, 这部分工作是和具体应用相关的。你得像个钻石切割工一样，根据你对程序的了解，找出请求阶段和数据集之间的自然“纹理线”。有时候它们很容易发现，有时候又很难找出来，此时需要不断回顾来发现它。在程序设计时，把代码分隔成不同阶段是很复杂的事情，我也没有好的建议，但是对于数据集的定义，有一些建议给你：
l 如果你能对请求按顺序编号，或者能对请求进行哈希，或者能把请求和事物ID关联起来，那么根据这些编号或者ID就能对数据更好的进行分隔。
l 有时，基于数据集的资源最大化利用，把请求动态的分配给数据，相对于依据请求的固有属性来分配会更有优势。就好像现代CPU的多个整数运算单元知道把请求分离一样。
l 确定每个阶段指定的数据集是不一样的是非常有用的，以便保证一个阶段争夺的数据在另外阶段不会争夺。
如果你在纵向和横向上把“锁空间(这里实际指锁的分布)" 分隔了，并且确保了锁均匀分布在网格上，那么恭喜你获得了一个好方案。现在你处在了一个好的登山点，打个比喻，你面有了一条通向顶峰的缓坡，但你还没有到山顶。现在是时候对锁竞争进行统计，看看该如何改进了。以不同的方式分隔阶段和数据集，然后统计锁竞争，直到获得一个满意的分隔。当你做到这个程度的时候，那么无限风景将呈现在你脚下。
其他方面
我已经阐述完了影响性能的四个主要方面。然而还有一些比较重要的方面需要说一说，大所属都可归结于你的平台或系统环境：
l 你的存储子系统在大数据读写和小数据读写，随即读写和顺序读写方面是如何进行？在预读和延迟写入方面做得怎样？
l 你使用的网络协议效率如何？是否可以通过修改参数改善性能？是否有类似于TCP_CORK, MSG_PUSH,Nagle-toggling算法的手段来避免小消息产生？
l 你的系统是否支持Scatter-Gather I/O(例如readv/writev)? 使用这些能够改善性能，也能避免使用缓冲链(见第一节数据拷贝的相关叙述)带来的麻烦。(说明：在dma传输数据的过程中，要求源物理地址和目标物理地址必须是连续的。但在有的计算机体系中，如IA，连续的存储器地址在物理上不一定是连续的，则dma传输要分成多次完成。如果传输完一块物理连续的数据后发起一次中断，同时主机进行下一块物理连续的传输，则这种方式即为block dma方式。scatter/gather方式则不同，它是用一个链表描述物理不连续的存储器，然后把链表首地址告诉dma master。dma master传输完一块物理连续的数据后，就不用再发中断了，而是根据链表传输下一块物理连续的数据，最后发起一次中断。很显然 scatter/gather方式比block dma方式效率高)
l 你的系统的页大小是多少？高速缓存大小是多少？向这些大小边界进行对起是否有用？系统调用和上下文切换花的代价是多少？
l 你是否知道锁原语的饥饿现象？你的事件机制有没有"惊群"问题?你的唤醒/睡眠机制是否有这样糟糕的行为: 当X唤醒了Y, 环境立刻切换到了Y,但是X还有没完成的工作?
我在这里考虑的了很多方面，相信你也考虑过。在特定情况下，应用这里提到的某些方面可能没有价值，但能考虑这些因素的影响还是有用的。如果在系统手册中，你没有找到这些方面的说明，那么就去努力找出答案。写一个测试程序来找出答案；不管怎样，写这样的测试代码都是很好的技巧锻炼。如果你写的代码在多个平台上都运行过，那么把这些相关的代码抽象为一个平台相关的库，将来在某个支持这里提到的某些功能的平台上，你就赢得了先机。
对你的代码,“知其所以然”, 弄明白其中高级的操作, 以及在不同条件下的花销.这不同于传统的性能分析, 不是关于具体的实现,而是关乎设计. 低级别的优化永远是蹩脚设计的最后救命稻草.
（map注：下面这段文字原文没有，这是译者对于翻译的理）
[附录：奥德修斯（Odysseus，又译“奥德赛”），神话中伊塔刻岛国王，《伊利亚特》和《奥德赛》两大史诗中的主人公（公元前11世纪到公元前9世纪的希腊史称作“荷马时代”。包括《伊利亚特》和《奥德赛》两部分的《荷马史诗》，是古代世界一部著名的杰作）。奥德修斯曾参加过著名的特洛伊战争，在战争中他以英勇善战、足智多谋而著称，为赢得战争的胜利，他设计制造了著名的“特洛伊木马”（后来在西方成了“为毁灭敌人而送的礼物”的代名词）。特洛伊城毁灭后，他在回国途中又经历了许多风险，荷马的《奥德赛》就是奥德修斯历险的记述。“斯库拉和卡律布狄斯”的故事是其中最惊险、最恐怖的一幕。
相传，斯库拉和卡律布狄斯是古希腊神话中的女妖和魔怪，女妖斯库拉住在意大利和西西里岛之间海峡中的一个洞穴里，她的对面住着另一个妖怪卡律布狄斯。它们为害所有过往航海的人。据荷马说，女妖斯库拉长着12只不规则的脚，有6个蛇一样的脖子，每个脖子上各有一颗可怕的头，张着血盆大口，每张嘴有3 排毒牙，随时准备把猎物咬碎。它们每天在意大利和西西里岛之间海峡中兴风作浪，航海者在两个妖怪之间通过是异常危险的，它们时刻在等待着穿过西西里海峡的船舶。在海峡中间，卡律布狄斯化成一个大旋涡，波涛汹涌、水花飞溅，每天3次从悬崖上奔涌而出，在退落时将通过此处的船只全部淹没。当奥德修斯的船接近卡律布狄斯大旋涡时，它像火炉上的一锅沸水，波涛滔天，激起漫天雪白的水花。当潮退时，海水混浊，涛声如雷，惊天动地。这时，黑暗泥泞的岩穴一见到底。正当他们惊恐地注视着这一可怕的景象时，正当舵手小心翼翼地驾驶着船只从左绕过旋涡时，突然海怪斯库拉出现在他们面前，她一口叼住了6个同伴。奥德修斯亲眼看见自己的同伴在妖怪的牙齿中间扭动着双手和双脚，挣扎了一会儿，他们便被嚼碎，成了血肉模糊的一团。其余的人侥幸通过了卡律布狄斯大旋涡和海怪斯库拉之间的危险的隘口。后来又历经种种灾难，最后终于回到了故乡——伊塔刻岛。
这个故事在语言学界和翻译界被广为流传。前苏联著名翻译家巴尔胡达罗夫就曾把 “斯库拉和卡律布狄斯”比作翻译中“直译和意译”。他说：“形象地说，译者总是不得不在直译和意译之间迂回应变，犹如在斯库拉和卡律布狄斯之间曲折前行，以求在这海峡两岸之间找到一条狭窄然而却足够深邃的航道，以便达到理想的目的地——最大限度的等值翻译。”
德国著名语言学家洪堡特也说过类似的话：“我确信任何翻译无疑地都是企图解决不可能解决的任务。因为任何一个翻译家都会碰到一个暗礁而遭到失败，他们不是由于十分准确地遵守了原文的形式而破坏了译文语言的特点，就是为了照顾译文语言的特点而损坏了原文。介于两者之间的做法不仅难于办到，而且简直是不可能办到。”
历史上长久以来都认为，翻译只能选择两个极端的一种：或者这种——逐字翻译（直译）；或者那种——自由翻译（意译）。就好像翻译中的斯库拉和卡律布狄斯”一样。如今 “斯库拉和卡律布狄斯”已成为表示双重危险——海怪和旋涡的代名词，人们常说“介于斯库拉和卡律布狄斯之间”，这就是说：处于两面受敌的险境，比喻“危机四伏”，用来喻指译者在直译和意译之间反复作出抉择之艰难。]
