Linux集群之负载平衡原理和实现算法
2008-11-26 10:59:37 来源:WEB开发网 闂傚倸鍊搁崐鎼佸磹閹间礁纾归柟闂寸绾惧綊鏌熼梻瀵割槮缁炬儳缍婇弻鐔兼⒒鐎靛壊妲紒鐐劤缂嶅﹪寮婚悢鍏尖拻閻庨潧澹婂Σ顔剧磼閹冣挃闁硅櫕鎹囬垾鏃堝礃椤忎礁浜鹃柨婵嗙凹缁ㄧ粯銇勯幒瀣仾闁靛洤瀚伴獮鍥敍濮f寧鎹囬弻鐔哥瑹閸喖顬堝銈庡亝缁挸鐣烽崡鐐嶆棃鍩€椤掑嫮宓佸┑鐘插绾句粙鏌涚仦鎹愬闁逞屽墰閹虫捇锝炲┑瀣╅柍杞拌兌閻ゅ懐绱撴担鍓插剱妞ゆ垶鐟╁畷銉р偓锝庡枟閻撴洘銇勯幇闈涗簼缂佽埖姘ㄧ槐鎾诲礃閳哄倻顦板┑顔硷工椤嘲鐣烽幒鎴旀瀻闁规惌鍘借ⅵ濠电姷鏁告慨顓㈠磻閹剧粯鈷戞い鎺嗗亾缂佸鏁婚獮鍡涙倷閸濆嫮顔愬┑鐑囩秵閸撴瑦淇婇懖鈺冪<闁归偊鍙庡▓婊堟煛鐏炵硶鍋撻幇浣告倯闁硅偐琛ラ埀顒冨皺閺佹牕鈹戦悙鏉戠仸闁圭ǹ鎽滅划鏃堟偨缁嬭锕傛煕閺囥劌鐏犻柛鎰ㄥ亾婵$偑鍊栭崝锕€顭块埀顒佺箾瀹€濠侀偗婵﹨娅g槐鎺懳熺拠鑼舵暱闂備胶枪濞寸兘寮拠宸殨濠电姵纰嶉弲鎻掝熆鐠虹尨宸ョ€规挸妫濆铏圭磼濡搫顫嶇紓浣风劍閹稿啿鐣烽幋锕€绠婚悹鍥у级瀹撳秴顪冮妶鍡樺鞍缂佸鍨剁粋宥夋倷椤掍礁寮垮┑鈽嗗灣閸樠勭妤e啯鍊垫慨妯煎亾鐎氾拷

发送者启动策略
发送者启动策略也引入了一个阀值M来把所有的处理节点划分成轻负载节点和重负载节点,所有当前剩余负载t > M的节点都被称为重负载节点,t < M的节点被称为轻负载节点。发送者启动策略还需要为每个节点定义一个相关域,节点只与它的相关域中的节点进行交互和任务传递。一个直观的相关域的定义是把所有与之相邻的节点作为相关域。
在启动时,所有节点开始执行计算任务。在执行一段时间之后,节点就开始检查其自身是否是重负载节点。如果是重负载节点,则它就试图在相关域中均匀地分布任务。具体地:设该重负载节点的负载为l p,相关域中有K个节点,其负载分别为l 1,……., l k,则平均负载L avg为:
为了达到均匀分布,应求得重负载节点应该传递给每个相关域中节点的负载量m k。我们首先引入h k以避免负载被迁移到相关域中负载最重的重负载节点。如果L avg> l k,则 ,否则h k= 0。那么m k为
随后该节点就可以按照m k向各个相关节点发送任务了。
接收者启动策略
接收者启动策略与发送者启动策略除了是由轻负载节点启动,要求其它节点把任务发送给它之外,其它基本相同。
接收者启动策略同样引入M以区分轻、重负载节点,引入相关域以确定交互范围。
在启动时,所有节点开始执行计算任务,经过一段时间之后,一旦某个节点发现自身成为轻负载节点,就试图在它的相关域中均匀地分布负载。具体地:设该轻负载节点的负载为l p ,相关域中有K个节点,其负载分别为l 1 ,……., l k,则平均负载L avg为:
为了达到均匀分布,应求得相关域中节点应该传递给轻负载节点的负载量m k。我们首先引入权h k以避免负载从负载更轻的相关域中的节点被迁移到该节点。如果L avg< l k, 则 ,否则h k=0。那么m k为:
随后该节点就可以按照m k发出接受任务的请求了。
更多精彩
赞助商链接