Linux集群之负载平衡原理和实现算法

　2008-11-26 10:59:37　来源：WEB开发网　闂傚倸鍊搁崐鎼佸磹閹间礁纾瑰瀣椤愯姤鎱ㄥ鍡楀幊缂傚倹姘ㄩ幉绋款吋閸澀缃曢梻鍌欑濠€閬嶆惞鎼淬劌绐楅柡宥庡亞娑撳秵銇勯弽顐沪闁绘挶鍎甸弻锝夊即閻愭祴鍋撻崷顓涘亾濮樼偓瀚�

闂傚倸鍊搁崐鎼佸磹閹间礁纾瑰瀣捣閻棗銆掑锝呬壕濡ょ姷鍋涢ˇ鐢稿极閹剧粯鍋愰柟缁樺笧閳ь剦鍙冨鍝勑ч崶褏浠奸梺璇茬箲閼归箖鎮鹃悜钘夎摕闁靛濡囬崢鐢告⒑鐟欏嫷鍟忛柛鐘崇墵閵嗗倹绺介崨濠勫幈闁硅壈鎻槐鏇熺墡闂備線娼уú銈団偓姘嵆閻涱噣骞掑Δ鈧粻锝嗙節闂堟稑鏆欏ù婊堢畺閺岋綁濮€閳惰泛婀辨竟鏇熺節濮橆厾鍘甸梺缁樺姦閸撴岸鎮樻潏銊ょ箚闁圭粯甯炴晶娑氱磼缂佹ḿ娲寸€规洖宕灃闁告劕鍟犻崜婵堟崲濞戞ḿ鏆嗗┑鐘辫兌閺佹牜绱撴担浠嬪摵闁圭懓娲ら悾鐑藉箳閹搭厽鍍甸梺鐟板悁閻掞箓鎮楅幖浣光拻濞达絿鍎ら崵鈧梺鎼炲€栭悧鐘荤嵁韫囨稒鏅搁柨鐕傛嫹

婵犵數濮烽弫鍛婃叏閻戣棄鏋侀柛娑橈攻閸欏繑銇勯幘鍗炵仼缂佺媭鍨堕弻娑㈠箛闂堟稒鐏堥悗鐟版啞缁诲啴濡甸崟顖氱閻庨潧鎽滈悾濂告⒑绾拋娼愭繛鑼枎椤繒绱掑Ο鑲╂嚌闂侀€炲苯澧畝锝堝劵椤︽煡鎮￠妶澶嬬厪闁割偅绻冮崑顏呯箾瀹割喕绨婚幆鐔兼⒑鐎圭姵銆冮柤鍐茬埣瀹曟繈鏁冮埀顒勨€旈崘顔嘉ч柛鈩冾殘閻熸劙姊洪悡搴℃毐闁绘牕銈稿畷鐑樼節閸パ冨祮闂侀潧楠忕槐鏇㈠储椤忓牊鈷戦柟鑲╁仜閸旀鏌￠崨顔锯姇缂佸倹甯熼ˇ瀵哥磼鏉堛劌绗氭繛鐓庣箻閸┾剝鎷呴柨瀣垫綗闂傚倷娴囧銊╂倿閿曞倸绠查柛銉墮閺嬩線鏌熼崜褏甯涢柡鍛倐閺屻劑鎮ら崒娑橆伓闂傚倸鍊搁崐鎼佸磹閹间礁纾瑰瀣椤愯姤鎱ㄥ鍡楀幊缂傚倹姘ㄩ幉绋款吋閸澀缃曢梻鍌欑濠€閬嶆惞鎼淬劌绐楅柡宥庡亞娑撳秵銇勯弽顐沪闁绘挶鍎甸弻锝夊即閻愭祴鍋撻崷顓涘亾濮樼偓瀚�　　闂傚倸鍊搁崐鎼佸磹閹间礁纾归柣鎴ｅГ閸ゅ嫰鏌ら崫銉︽毄濞寸姵姘ㄧ槐鎾诲磼濞嗘帒鍘＄紓渚囧櫘閸ㄥ爼濡撮崘顔煎窛闁哄鍨归崢娲倵楠炲灝鍔氭い锔诲灦瀹曪繝骞庨懞銉у帾闂婎偄娲﹀ú鏍ㄧ墡闂備浇顕х€垫帡宕滈悢濂夋綎闁惧繐婀辩壕鍏间繆椤栨碍鎯堟い顐㈢Т椤啴濡堕崱妤€顫庨梺鍛婎焼閸パ呭弨婵犮垼娉涜癌闁绘柨鍚嬮悡銉╂倵閿濆骸鍘撮柛瀣尰缁绘繂顫濋娑欏闁荤喐绮庢晶妤冩暜閹烘挾顩插ù鐓庣摠閻撴洟鏌熼幆褜鍤熼柍钘夘樀閺屽秶绱掑Ο鑽ゅ弳濡炪値鍋呯换鍫ュ箠濠婂懎鏋堟俊顖濐嚙椤忓綊姊婚崒娆戭槮闁硅绱曠划娆撳箣閿斿搫浜奸梺鍝勵槹閸ㄧ喖寮搁弮鍫熺厸闁告劧绲芥禍鍓х磽娴ｈ櫣甯涚紒瀣尰缁傛帡鏁冮崒姘憋紲濠殿喗锕╅崜锕傛倵閹惰姤鈷掑ù锝呮憸閿涘秶绱掗鍛仸妤犵偞鍨垮畷鍫曨敆閸屾氨銈﹂梺璇插嚱缂嶅棙绂嶉弽顓炵哗濞寸姴顑嗛悡娆撴⒑椤撱劎鐣卞褜鍨遍妵鍕棘閸喒鍋撶憴鍕攳濠电姴娲﹂崐閿嬨亜韫囨挸顏ら柛瀣崌瀵€燁檨婵炲吋鐗曢埞鎴︽偐鐎圭姴顥濋梺绋胯閸斿酣骞夊宀€鐤€婵炴垶岣块悿鍛存⒑閸︻叀妾搁柛鐘愁殜瀵煡骞栨担鍦弳闂佺粯娲栭崐鍦偓姘炬嫹

核心提示： 梯度模型策略在中心任务调度策略中，计算节点越多，Linux集群之负载平衡原理和实现算法(5)，冲突就越多，为了减少冲突，但随着时间的推移，轻负载节点实际上不久就可以接受被它拒绝接受的任务了，适应大量处理节点的需要，梯度模型策略、发送者启动策略和接收者启动策略都不设置专用的调度节点

梯度模型策略

在中心任务调度策略中，计算节点越多，冲突就越多。为了减少冲突，适应大量处理节点的需要。梯度模型策略、发送者启动策略和接收者启动策略都不设置专用的调度节点，而且每个节点只与一部分节点进行交互，以减少由负载平衡导致的冲突。

在梯度模型策略中，所有处理节点仅与直接相邻的节点进行交互，并引入两个阀值：M 1 和Mh。在运行过程中，我们将所在节点划分成三类：设一个节点的剩余任务量为t，如果t < M 1则称之为轻负载节点；如果M 1< t < M h则称之为中负载节点；如果t > M h则称之为重负载节点。另外，把从一个节点到与之最接近的轻负载节点的最短距离定义为这个节点的梯度。

在启动时，每个节点都是重负载节点，梯度都是无穷大。在计算过程中，周期性地检查其剩余负载是否大于M1。当某一节点发现自身剩余的负载小于M1时就把它的梯度设为零，随后把自身当前的梯度与相邻节点间的距离之和发送给相邻的节点。相邻的节点接收到这个新梯度，就与自身当前梯度进行比较。如果自身梯度小于等于新梯度，则不做任何事；如果自身梯度大于新梯度，则将自身梯度设置为新梯度，并向发送给它新梯度信息的节点一样传播新梯度。这样，梯度信息（实际上就是计算任务完成的情况）就会被传播开来，重负载节点就可以把它多余的负载发送给向临界点中梯度最小的节点。于是，计算任务就在梯度的引导之下从重负载节点流向轻负载节点。

可是，按照这种方式，有可能导致过多的计算任务涌向一个轻负载节点。如果轻负载节点接收了过多的新任务，就有可能重新变成中负载甚至重负载节点。一旦出现这种情况，梯度信息就不再能够正确地引导计算任务了。为此，必须使轻负载节点察看要接受的计算任务，如果接收计算任务使本节点脱离轻节点状态，就拒绝接受它。这虽然延迟了任务的接收，但随着时间的推移，轻负载节点实际上不久就可以接受被它拒绝接受的任务了，同时还可以保持节点的梯度的有效性。