原作者：CCP Prism X
原文：http://community.eveonline.com/news/dev-blogs/building-a-balanced-universe/

?

??? 大家好，我是CCP Prism X，天秤座。

?

?? 《奧德賽》版本上線后許多新玩家涌入了EVE宇宙追尋夢(mèng)想，這其實(shí)是一件很值得高興的事，我們理應(yīng)大肆慶祝才對(duì)。不過(guò)呢，這次新玩家的流入如此迅猛，幾乎塞爆了整個(gè)帝國(guó)領(lǐng)地，讓我們開始有點(diǎn)擔(dān)心起來(lái)。新伊甸中的居民如此之多，每時(shí)每刻都在做著許許多多不同的事情，讓我們的CPU核心（下文會(huì)稱為“節(jié)點(diǎn)”）壓力山大，帝國(guó)的多個(gè)星系中都出現(xiàn)了時(shí)間膨脹現(xiàn)象。如果你在0.0地區(qū)生活那時(shí)間膨脹沒什么要緊，但如果你獨(dú)自一人在某個(gè)星系做任務(wù)時(shí)突然發(fā)現(xiàn)周圍的一切都像進(jìn)入了子彈時(shí)間一般慢吞吞，那你不會(huì)高興的。

?

??? 帝國(guó)星系按理說(shuō)應(yīng)該對(duì)高負(fù)載事先留有余地，不應(yīng)該出現(xiàn)時(shí)間膨脹才是，一旦發(fā)生了膨脹，我們的靜態(tài)服務(wù)器集群重構(gòu)機(jī)制最起碼應(yīng)該阻止問(wèn)題再次發(fā)生。我們會(huì)按照預(yù)估的負(fù)載情況在服務(wù)器啟動(dòng)時(shí)將星系分配到不同節(jié)點(diǎn)，如果預(yù)估正確的話重構(gòu)機(jī)制應(yīng)該會(huì)正常發(fā)揮作用。但如果同一星系反復(fù)被分配到一個(gè)承載了太多星系的節(jié)點(diǎn)上，它的運(yùn)作就開始不正常了，具體原因我們也不十分清楚。

?

????第一步：找出問(wèn)題所在

??? 剛才我沒有提到星系重構(gòu)機(jī)制的一個(gè)重要特征：同一星座內(nèi)的星系往往被分配到同一節(jié)點(diǎn)上，完全不顧這是否是目前最佳的負(fù)載分配方式，這導(dǎo)致了不同節(jié)點(diǎn)間負(fù)載差異巨大，而重構(gòu)機(jī)制應(yīng)該是盡可能均分負(fù)載才對(duì)。另外，這一行為并不會(huì)超出星座范疇，所以一個(gè)節(jié)點(diǎn)可以承載兩個(gè)完整的星座，但很可能一個(gè)在最南邊一個(gè)在最北邊。所以在南邊那個(gè)星座發(fā)生的大規(guī)模會(huì)戰(zhàn)也會(huì)讓北邊那個(gè)星座遭遇嚴(yán)重的時(shí)間膨脹，生活在當(dāng)?shù)氐耐婕乙欢ê懿桓吲d。

?

??? 這是一幅舊系統(tǒng)中星系節(jié)點(diǎn)分布的虛擬化視圖（這是3D轉(zhuǎn)印2D圖像所以有點(diǎn)歪歪扭扭的就不要在意啦），同一顏色的星系位于同一節(jié)點(diǎn)上。你一定會(huì)發(fā)現(xiàn)這和一塊擦顏料的破布差不多，各種顏色之間基本沒什么關(guān)聯(lián)。我標(biāo)出的兩個(gè)紅圈中的星系其實(shí)位于同一節(jié)點(diǎn)上，你看看這有多遠(yuǎn)：

?

?

??? 下圖進(jìn)一步說(shuō)明了過(guò)去這種負(fù)載分配有多糟糕，節(jié)點(diǎn)之間的負(fù)載差異令人驚訝，你可以看看圖中的差異值有多大：

?

?

?

??? 那么我們?yōu)槭裁串?dāng)初以星座為劃分節(jié)點(diǎn)的基礎(chǔ)單位呢？那是因?yàn)楹芫靡郧拔覀冾A(yù)計(jì)由于網(wǎng)絡(luò)延遲的存在，跨節(jié)點(diǎn)的星門跳躍要比節(jié)點(diǎn)內(nèi)的占用更多資源?，F(xiàn)在我們發(fā)現(xiàn)這種假設(shè)完全不對(duì)，跨節(jié)點(diǎn)跳躍其實(shí)比節(jié)點(diǎn)內(nèi)跳躍還省資源。星門跳躍這一過(guò)程需要將玩家從一個(gè)星系中移除，然后再放到另一個(gè)星系中，而將這一過(guò)程均分給兩個(gè)節(jié)點(diǎn)要比在同一節(jié)點(diǎn)內(nèi)發(fā)生負(fù)載低。

?

??? 認(rèn)識(shí)到這一點(diǎn)之后，我們決定首先要打破星系抱團(tuán)分布的現(xiàn)狀，星系應(yīng)該只按照節(jié)點(diǎn)的負(fù)載情況來(lái)分布，這會(huì)使服務(wù)器負(fù)載均衡許多。不過(guò)盡管我們重新分布了服務(wù)器，時(shí)間膨脹情況卻比之前更嚴(yán)重了。這些星系基本處于半隨機(jī)分布狀態(tài)，全不顧地緣因素，所以還是會(huì)出現(xiàn)“南方打仗，北方遭殃”的情況。所以我們還得從頭再來(lái)！

?

????第二步：解決問(wèn)題

??? 我們得想個(gè)辦法既能均衡節(jié)點(diǎn)負(fù)載，又能保證同一節(jié)點(diǎn)上的星系彼此臨近。我們不想因?yàn)楹笠稽c(diǎn)原因使得服務(wù)器重構(gòu)的時(shí)間延長(zhǎng)，所以干脆趁此機(jī)會(huì)將舊的T-SQL代碼用Python重新編寫。而這一舉動(dòng)意外地成為了整個(gè)工作的關(guān)鍵點(diǎn)，因?yàn)檫@樣一種擁有眾多支持工具的程序化語(yǔ)言非常適合解決這種程序化的問(wèn)題，比之前那種限制繁多的關(guān)系式語(yǔ)言強(qiáng)得多。

?

??? Python的使用讓解決問(wèn)題變得容易起來(lái)。我們嘗試將一片星系按照設(shè)定好的坐標(biāo)來(lái)劃分，這樣分成的部分比重相似，而且互相臨近。如果你將任意坐標(biāo)星系一分為二，兩部分將會(huì)緊密相連，這就解決了上面說(shuō)過(guò)的地緣性問(wèn)題。這也同時(shí)保證了兩部分的負(fù)載基本相當(dāng)，所以剩下的問(wèn)題就只是如何調(diào)整這條分割線在哪里了。這并不困難，只需要將分割線向負(fù)載較重的那一半移動(dòng)一定距離，然后下一次移動(dòng)距離減半，以此類推。理論上我們會(huì)在最佳分割處左右搖擺直到最終找到確切地點(diǎn)。當(dāng)然這只是理論上，我們也并沒有想找出最最準(zhǔn)確的解決方案，只要在最短時(shí)間內(nèi)找到足夠好的方案就可以了。

?

??? 下圖可以幫你理解這個(gè)過(guò)程。圓圈代表了一大片星系，我并沒有將它們一個(gè)個(gè)標(biāo)出來(lái)，只要最后的劃分使負(fù)載盡可能均衡就行了。

?

?

?

??? 我們首先要將整個(gè)宇宙劃分為兩大塊，然后挑負(fù)載高的那個(gè)再分一次，然后在三個(gè)中選負(fù)載高的再來(lái)一次，這樣一次次重復(fù)，直到數(shù)量與我們現(xiàn)有的服務(wù)器節(jié)點(diǎn)數(shù)量相等，然后就可以向數(shù)據(jù)庫(kù)中寫入節(jié)點(diǎn)分布并啟動(dòng)服務(wù)器了。

?

??? 為了便于理解我準(zhǔn)備了幾張圖，不過(guò)頭三步只是對(duì)帝國(guó)領(lǐng)地的劃分，是用來(lái)幫助你理解概念的，不要在意細(xì)節(jié)。最后一幅圖是最終的宇宙節(jié)點(diǎn)劃分，你可以和之前那幅圖比較一下。

?

??? 帝國(guó)初始狀態(tài)：

?

?

?

??? 第一次劃分后，兩部分不一樣大小是因?yàn)閷?shí)際上并不是所有的服務(wù)器都負(fù)載平均的：

?

?

?

??? 第七次劃分后：

?

?

?

??? 最終結(jié)果，看看現(xiàn)在顏色統(tǒng)一多了吧：

?

?

?

????第三步：最終解決問(wèn)題

??? 這就是我們?cè)?jì)劃在《絕地反擊》更新前幾周對(duì)服務(wù)器集群進(jìn)行的重構(gòu)。如果你對(duì)計(jì)算機(jī)知識(shí)有一定了解就應(yīng)該能看出來(lái)，要想讓服務(wù)器負(fù)載均衡，節(jié)點(diǎn)的數(shù)量必須是偶數(shù)，否則就會(huì)不平衡。要想達(dá)到完美平衡就需要足夠多的節(jié)點(diǎn)，不然上一層的節(jié)點(diǎn)負(fù)載就會(huì)是下一層節(jié)點(diǎn)負(fù)載的兩倍。

?

??? 這幅圖直觀地說(shuō)明了4個(gè)節(jié)點(diǎn)比3個(gè)節(jié)點(diǎn)好在哪里。當(dāng)然這只是理想狀況，我們并不指望所有節(jié)點(diǎn)負(fù)載達(dá)到完美平衡。

?

?

?

??? 這樣做的結(jié)果是劃分更不均衡了。下圖中0.0地區(qū)的數(shù)據(jù)看起來(lái)好些了，但是帝國(guó)節(jié)點(diǎn)的差異仍然很大。不過(guò)至少CPU最低使用率不是0了。內(nèi)存占用的數(shù)據(jù)比之前更糟，不過(guò)CPU使用確實(shí)已做到了均衡。

?

?

?

??? 很明顯看起來(lái)這里的最佳分配方式應(yīng)該是每個(gè)節(jié)點(diǎn)負(fù)載的33%，但是你也看到了上面所說(shuō)的漂亮算法在這里完全不起效。不過(guò)既然知道了只要節(jié)點(diǎn)數(shù)量是偶數(shù)就沒錯(cuò)，那就堅(jiān)持推行下去！我們當(dāng)然可以強(qiáng)制星系節(jié)點(diǎn)的數(shù)量為偶數(shù)，但這是人為限制，尤其是任何十進(jìn)制數(shù)字都可以用二進(jìn)制數(shù)字來(lái)表示，那就把上面的二進(jìn)制樹換為偶數(shù)節(jié)點(diǎn)然后再次計(jì)算。

?

??? 下圖是一種比三個(gè)節(jié)點(diǎn)更復(fù)雜些的例子：

?

?

?

??? 這個(gè)方法足夠簡(jiǎn)單，可以盡量少修改初始方案的代碼。那個(gè)方案已經(jīng)使用了將坐標(biāo)星系劃分為兩個(gè)負(fù)載均衡部分的方法，那讓它劃分為兩個(gè)X/Y部分也不是什么大問(wèn)題。

?

??? 用這種新方法重新劃分前面使用的數(shù)據(jù)，我們得到了下面的結(jié)果，看起來(lái)相當(dāng)均衡了：

?

?

?

??? CPU占用的差異也有極大改觀！我們會(huì)馬上實(shí)施這一計(jì)劃。

?

?

?

????第四步：寫篇日志

??? 一個(gè)更加均衡的宇宙就這樣誕生了。

?

??? 就這么多了，感謝收看！