负载平衡算法比较与改进 宋东风

       在学习分布式系统的过程中对负载平衡技术产生浓厚兴趣，读了几篇这方面的学术论文以及几本专著中的相关专题。这样对负载平衡技术有了初步了解并略有心得，下面就谈谈自己的学习体会并尝试对已有的算法作改进。

目前在分布式系统中，对于服务器端的平衡技术已经比较成熟，各商用的应用服务器基本上都具有此功能，而且做得很不错。我们这里要探讨的不是服务器端的负载平衡，而是网络上的负载平衡。Internet上的平衡算法研究借鉴了服务器端的现有成果，并针对网络的特殊性作了合理的取舍改进。例如，服务器端的负载平衡有时候要求能实现二次分配功能，我们这里就不需要了。在Internet上，对于容错的要求也没有那么苛刻。

常用的负载平衡算法主要有轮转法、直接hashing、最少任务优先。其中，各类基于Hashing (Hashing-Based)的由于具有下面所述的优点而值得特别注意：各源地址或者目标地址经hashing后，同一个属于Session的包会经过同一条链路。因此，我们下面只讨论Hashing-based的算法。我们先比较现有的各种常用的Direct-Hashing算法，分析其效率，再根据其不足处提出改进意见。

常用的Direct-Hashing如下：

1)Hashing of Destination Address

H(.)= DestIP mod N

这里的DestIP表示目标主机的IP地址（Destination IP）。N是分支出口的数目，下同。

2)Hashing Using XOR Folding of Destination Address

H(.)= (D1⊕D2⊕D3⊕D4) mod N

这里的D1、D2、D3、D4分别表示Destination IP的4个域，下同。

3)Hashing Using XOR Folding of Source and Destination Address

H(.)=(S1⊕S2⊕S3⊕S4⊕D1⊕D2⊕D3⊕D4) mod N

这里的S1、S2、S3、S4分别表示Source IP的4个域。

4)Internet Checksum

H(.)=Checksum(5-tuple) mod N

这里的五元组(5-tuple)的格式是这样的（Source IP, Destination IP, Source Port, Destination Port, Protocol ID）, 下同。

5)CRC16(循环冗余校验)

H(.)=CRC16(5-tuple) mod N

 

下面我们简单讨论一下这五个算法的复杂度和平衡效果。在参考文献1中给出了各个算法效果的实验数据。限于篇幅，我们这里不列出具体数据了。我们把实验数据绘成曲线图，可以直观地看出各算法的平衡效果，具体的图在本文的最后。

算法1计算简单。但是只利用了目标地址一个信息，而且只利用了目标地址的低位。例如，当N=4，那么就只利用了最右边的2位（二进制）。所以其平衡效果不佳。

算法2充分利用了目标地址的信息，所以平衡效果要比算法1有所改善，但总体表现仍不能令人满意。

算法3利用了目标地址和源地址信息，要过进一步得到改善。

算法4利用了各个数据包中的更多信息，计算也复杂很多，所以效果有很大改善。

算法5的计算复杂性最高，代价高，平衡效果非常出色。

 

我们注意到，上面的5种方法都没有利用反馈信息，即只考虑了转发并没有考虑各分支出口的实际负载现状，这样为了达到理想的效果只能通过增加计算复杂度来实现，但是有没有其他办法能降低复杂度来达到相对理想的效果呢？如果我们能够很好地利用各分支出口的负载信息，引入一个权值来标示负载信息，动态调节各分支的负载分配，这肯定可以在较低的计算复杂度下达到预想的平衡效果。实际上，很多服务器端的负载平衡算法就参考了反馈信息，它们收集各个处理机的各类负载指标信息，然后调整分配策略。但是，我们这里的执行主体是路由器，其计算能力不能与应用服务器相比，所以我们只能收集少量的信息，并且收集信息的频度要低。按照这个思路，我们提出了改进意见。

我们在路由器中维护一个历史信息表，记录各个分支的流量。企图根据该信息来调整各个分支的“配额”J。为了实现这点，必须改变原来那种直接对N取余的做法。我们引入整数型参数M，用来作为hashing函数结果与具体的分支出口的中介。Hashing函数中将采用对M取余来代替对N取余。我们可以将其看成M个虚拟出口。我们再通过索引将这M个虚拟分支和N个实际分支建立映射，请参考下边的示意图。这样我们可以通过调整这种映射关系来达到调整对各个真实分支的“配额”。

    这样改进后，我们就可以根据历史信息来动态调整各个分支的负载，而且有一个额外的好处---那就是，能适应分支带宽不同的网络!具体的效果我们需要通过实验来验证，这需要在下一步工作做。本文不作证明。

附录：

各个算法的平衡效果图

 

算法1                                 算法2
 

算法3                                 算法4

            算法5

参考文献

1)      Zhiruo Cao, Zheng Wang, and Ellen Zegura “Performance of Hashing-Based Schemes for Internet Load Balancing”, Infocom, 2000

2)      Mon-Yen Luo and Chu-Sing Yang, “Constructing Zero-loss Web Services”, Infocom, 2001.

3)      范国闯 朱寰，Web应用服务器自适应负载平衡服务,软件学报 2003 Vol. 14 No.6

4)      《分布式系统设计》（Distributed System Design）Jie Wu 著，高传善 译，机械工业出版社，2001-2-1

5)      《高性能集群计算：结构与系统》(High Performance Cluster Computing Architectures and Systems，Volume 1) （美）Rajkumar Buyya 著，郑纬民 石威 汪东升 等 译，电子工业出版社，2001-6-1

     北大天网作为中国最早的搜索引擎在搜索引擎行业影响深远。其背后的北大计算机系网络与分布式系统实验室培养了一批杰出的人才。

     从刘建国，到雷鸣、陈华、周利民、段晖，他们曾经是百度早期的核心员工，现在都已经自立门户了。

     刘建国，原是北大计算机的副教授。号称百度的第一员工，曾经担任百度的副总裁、CTO。2007年创建爱帮网（www.aibang.com）。

     周利民，1992年本科毕业于武汉大学计算机系。1995年北大计算机系硕士，后留校任教，参与设计研发“北大天网”的最初版本。2000年放弃UCLA的博士学业，退学加入百度，曾任首席架构师。

     雷鸣，北大93级计算机系，算是实验室中的大师兄。曾编写了百度第一代程序的大量代码，并被李彦宏称为“中国最好的工程师之一”，曾担任百度的首席架构师，口碑非常好。在百度上市之前离开百度去斯坦福读MBA.毕业后，他与怀奇开始打造一款将歌曲、歌词、歌星新闻相结合的音乐识别软件“酷我”，并依此寻找解决音乐版权问题的方法。

     陈华，北大97级计算机系。研究生毕业后加入msn search，后离职创建酷讯（www.kooxoo.com）。

     段晖，北大97级计算机系。2003年他离开百度时，已经是公司技术委员会五人组之一。如今，他和林应民（百度、迅雷）创立了一见互动（取义“百闻不如一见”），试图打造一个Youtube+ MySpace的社区。

     2005年，网络与分布式系统实验室的老师们把这些人当年的论文收集起来编著成书---《搜索引擎---原理、技术与系统》。凭着内容和作者的名头，该书当仁不让地成为搜索引擎方面的扛鼎之作！比起其它那些抄抄开源框架就敢卖弄的书，这本书的理论深度高出太多！

    前日媒体报导，Google与金山合作，采用金山的词霸和快译。这下Google除了可以获得词霸系列现有的用户群，还可以获得金山的中文处理技术。Google现在有了这么一个强援，以后百度还敢自诩更懂中文么？
    我们更进一步的说,难道百度的技术真的比google强? 恐怕不是吧. 真实原因应该还是靠中国特殊的国情,使得打擦边球迎合市场\紧跟政府,听话有关系.

     新近买了一本自然语言处理方面的书---《中文文本信息处理的原理与应用》（清华大学出版社）。我之前读过一些NLP经典教材和论文，也使用过一些开源的资源（分词、命名实体识别、分类、聚类，等等），算是有点基础吧。这本书是同济的XXX教授主编的，他好像还是学院的领导。我曾经听过他的课，所以就支持了一把，买了这本书。

     书拿到手后挑最感兴趣的章节看看，翻了几页就觉得不对劲，很多语句似曾相识。回家后翻出几年前读过的一本《中文信息处理技术教程》（清华大学出版社，朱巧明主编）。这下发现，大段大段的文字都是重样的。当然了，也不全是一模一样。有一段在举例的时候，朱书用的是“通用电气公司 苏州大学 关心下一代工作委员会”，苗书用的是“通用电气公司 同济大学 关心下一代工作委员会”:P

     尽管我对于国人编著的书本质量本身并不抱很大的期望，但是这回还是很郁闷。如果是其它通用的领域的话倒是可以看引进版，但是中文处理总要看本土的作品吧。谁知这种有点名头的人物也乱抄一通---还把朱巧明的书列在参考文献的最后一项:P

(转载)
    上周末，我去一间熟悉的西餐厅吃晚饭，发现餐厅内部刚装修过，餐厅服务生的装束也有所改变。 
    我发现服务生们上衣夹克的口袋里都多放了一把勺子。于是我叫来相熟的亨利，向他打听最近的变化。 
    亨利告诉我，餐厅老板最近请了埃森哲公司作业务流程重组的咨询，以改进餐厅的工作效率和服务质量。 
    埃森哲的咨询顾问经过两个礼拜的现场工作，发现33.333％的餐桌在就餐过程中都会发生一次勺子掉在地上的情况。而以往服务生需要单跑去厨房一次给客人换干净勺子。如果在服务生的夹克口袋里放一把备用勺，则他们不必单独跑一次厨房，可以在下次上菜时顺路换掉勺子，这样可以将服务生的劳动生产率提高 17.365％。 
     正说着，我旁边的桌子响起叮当一声：他们勺子掉地上了。只见亨利从容地从口袋里拿出备用勺，及时给客人换上
    看到这个场景，我对埃森哲公司的咨询建议相当佩服。
    这时，我又留意到所有服务生西裤的拉链外有一根很细的绳子，其质地和隐性胸罩带一样，所以较难发现。 
    于是，我又向亨利提出这个新问题：“你们这根细绳儿是干嘛用的？”
    亨利环顾了一下，将身子倾斜过来，小声说道：“好眼力！不是每个人都象您这样观察入的！” 
    亨利接着说：“埃森哲公司通过对餐厅工作流程的现场观察和数据分析，发现服务生每班次平均要小便5.125次，而每次小便完平均要花 1.306分钟洗手和烘干手。埃森哲的顾问建议我们在那儿上面系上这根绳子，以后每次小便直接把自己那活儿拉出来，可以避免手接触到，这样就可以省去洗手和烘干的麻烦，既提高服务生的劳动生产率，又节约餐厅的水费和电费。。。” 
    听完亨利的介绍，我对埃森哲公司更敬佩了。
   不过，我还有一点小小的疑问：“亨利啊，你们可以用绳子把自己那活儿拉出来，但是怎么能不用手把它给放回去呢？” 
    亨利又一次谨慎地环顾左右，将身子倾得更低，用更小的声音对我说：“我不知道其他人是怎么解决的，但我是用的那把勺子。。。”

爱国也好，抵制家乐福也好，都要冷静。巴金老人家教导过我们，别被人当枪使---这话主要是反思文革的，对现在也适用。

娃哈哈的宗庆后老板说要反抗达能，保护民族产业。大家会相信么？眼下也是。海峡那边的阿扁总统号召大家“爱台湾”，又有几个人人会当真？

周星驰演过一部电影《鹿鼎记》里有一段经典台词，颇有点意思---金庸写《鹿鼎记》原著的时候正值内地文革，这段台词深得金庸的精髓。

-------------------------------------

陈近南：不要乱说话，起来！青木堂堂主惨死在敖拜爪牙的手上，我们一定要贯彻他的遗志，诛杀敖拜这个奸贼！同时，将满清皇帝跟清狗赶出关外，复我大明江山！
众 人：反清复明！反清复明！反清复明！
韦小宝：反清复明！反清复明！
陈近南：现在我有一个极为危险的任务，希望能有兄弟自愿担任。
众 人：有任务，有任务！
陈近南：我查到清宫里面有四本《四十二章经》，里面记载了清廷在关外收藏一个大宝藏的秘密。如果我们能够知道这个大宝藏的秘密，我们就可以取回清朝在大明江山所搜刮的民脂民膏，而且还可以切断他们的龙脉！
众 人：有道理！
陈近南：龙脉一断，那清狗的气数就已尽！而我们大明江山就只日可复！所以我想派人入宫去愉这几本经书！但是我知道这个任务非常的危险，可以说是九死一生，有谁不想去的就坐下！
众 人：（纷纷拼死占座，韦小宝只因要坐的椅子上被陈近南钉了钉子而站了起来）
.........
陈近南：小宝，你是个聪明人，我可以用聪明的方法跟人说话。外面的人就不行！
韦小宝：不解！
陈近南：读过书明事理的人，大多数已经在清廷里面当宫了。所以我们要对抗清廷，就要用一些蠢一点的人。对付那些蠢人，就绝对不可以跟他们说真话，必需要用宗教形式来催眠他们，使他们觉得所做的事都是对的，所以“反清复明”只不过是个口号，跟“阿弥陀佛”其实是一样的。清朝一直欺压我们汉人，抢走我们的银两跟女人，所以我们要反清。
韦小宝：要反清抢回我们的钱跟女人，是不是，复不复明根本就是脱了裤子放屁，关人鸟事呀！行了，大家聪明人，了解！继续！
陈近南：总之，如果成功的话，就有无数的银两跟女人，你愿不愿意去呀？
韦小宝：愿意！只不过你刚才那句“九死一生”太吓人了！

     中山大学的袁伟时教授是我很敬佩的历史学家，老先生是一位独立思考的学者。前两年的时候，他发表了一篇反响很大的文章---《现代化与历史教科书》，惹来众多卫道者拍砖。这本《帝国落日》是袁先生的旧作，当初也颇有一些争议。

     该书为解读晚清那段充满屈辱与抗争的历史提供了一个不同于教科书的视角，正应了那句老话“兼听则明”:)

      前几天我的msn签名档改为"从来不曾远离,如今离你更近".这本来是花旗银行的一个广告词.花旗在上个世纪早期就来到中国,1949年撤出大陆.如今允许外资银行落地,它们又回来了---你就把他当作银行版的胡汉三.这句广告词说的就是这么一个事.

     我把它引用过来只是用来描绘自己换个新环境的心情.却被同事误会是感情故事,狂晕:P

     身边的很多朋友都是ddmap的活跃用户,我自己也是.下周就要去丁丁报到了，充满期待.

     丁丁以前是专门做电子地图的，现在还将加入生活搜索。以后如果大家想找上海吃喝玩乐生活信息，请多多支持丁丁网，呵呵。

     上海的IT圈子真的很小，同行之间很容易就会遇到熟人。有人说两个陌生人之间最多通过6个人就可以拉上关系。这个规律放到本地的同行中那就更适用了，大概2到3个人就可以串上。

     最近去本地一个知名的互联网公司串门，见识了一下那种别具一格的文化---当然我个人很难欣赏那种bt文化，我还是比较严肃的。跟那边有过一面之缘的朋友聊了聊，发现彼此的交集中的人就有3个。

     看来以后做人要低调，要修炼个人口碑:)

对于Python、Per、Rubyl之类的动态语言，但是工作生活中很少用。最近一时兴起，想熟悉一下。

     前段时间清明的时候，国内很多地方都搞祭典。女娲、炎帝、黄帝、大禹，等等，这些传说中中华民族的祖先们都被请出来。我很怀疑这些始祖的真实性，连夏商都不可考，何况之前的三皇五帝。我们的邻居朝鲜半岛上那两个国家，也自称有五千年的文明史，其中真实性更是可疑。

     有很多学者称，这种祭祀活动能增强民族认同或者国家认同，要求国家领导人出面。这种说法也是值得商榷的。传统上这种祭祖活动更多地展示王权的一种仪式，还是为了增强自己的政权的合法性---表明自己“受命于天”。再说了，像美国那种移民国家，没得祖先可以祭奠也不影响人家的国家认同嘛

     一直对信息检索技术比较有兴趣，但是由于种种原因脱离了一线一年多。期间自己仍然对搜索引擎行业保持关注。我们常说知之者不如乐之者，乐之者不如好之者。现今有机会重回自己喜欢的行业，学以致用，这真是心情大好。相比之下，其它如待遇或者title之类因素都不是最重要的。

     曾经“狠傻很天真”，好高鹜远，空想能如何如何。期间却忽视了自身的积累，没有找到自己真正的核心竞争力。接下来相当长的一段时间内我会给自己补课，弥补自己技术上的短板---从自然语言处理到系统分析与设计，等等。每个阶段有自己更适合做的事情。

     回头看看这一年半的经历，见过各色人物，见证一家公司从筹建到发展过程中的酸甜苦辣，体验确实丰富。

     丁丁网(丁丁地图)是一家靠上海地图起家的公司，目前正转型，提供全面的生活信息服务。我很喜欢生活搜索这个行业:)

----------------------------------------------------------------------------------------------------------------------------

     使人成熟的不是时间而是经历:)