摘要
maglev是谷歌的一個(gè)網(wǎng)絡(luò)負(fù)載均衡器。它是一個(gè)運(yùn)行在linux服務(wù)器上的大型的分布式的軟件。不同于傳統(tǒng)的硬件負(fù)載均衡設(shè)備，它不需要特殊的物理設(shè)備，并且可以很方便的通過(guò)增加或者減少服務(wù)來(lái)進(jìn)行擴(kuò)縮容。核心路由通過(guò)ECMP協(xié)議來(lái)將網(wǎng)絡(luò)包均勻的發(fā)送給maglev節(jié)點(diǎn)。maglev再將這些網(wǎng)絡(luò)包均勻的分發(fā)給后端實(shí)際服務(wù)節(jié)點(diǎn)。為了容納不斷增長(zhǎng)的流量,maglev針對(duì)包處理做了特別的優(yōu)化。一個(gè)maglev節(jié)點(diǎn)可以處理10Gbps的小包。為了最小化面向連接協(xié)議在發(fā)生預(yù)期外錯(cuò)誤和失敗時(shí)產(chǎn)生的負(fù)面影響，maglev支持了一致性hash以及連接跟蹤(connection tracking)的特性。2008年起 maglev承載了谷歌的大部分流量，同時(shí)也為谷歌云提供服務(wù)。
介紹
谷歌承載了非常大的全球化的流量，提供了數(shù)以百計(jì)的面向用戶的產(chǎn)品。同時(shí)，越來(lái)越多的服務(wù)遷移到了谷歌云上。一些谷歌的重要服務(wù)如谷歌搜索，谷歌郵箱每秒要處理上百萬(wàn)次請(qǐng)求,這對(duì)基礎(chǔ)設(shè)施提出了巨大的需求。
為了能夠低延遲的處理海量請(qǐng)求，一個(gè)谷歌服務(wù)部署在世界各地不同區(qū)域的服務(wù)器上。在每個(gè)區(qū)域內(nèi)，需要將流量均勻的分發(fā)給所有服務(wù)器以高效的利用資源并且保證不超過(guò)單個(gè)服務(wù)器的負(fù)載上限。所以，網(wǎng)絡(luò)負(fù)載均衡是谷歌非常重要的一個(gè)基礎(chǔ)設(shè)施。
如圖一所示，一個(gè)負(fù)載均衡器是由多個(gè)邏輯上部署在核心路由與服務(wù)節(jié)點(diǎn)(通常是tcp或者udp服務(wù)器)間的設(shè)備組成的。
傳統(tǒng)意義上，負(fù)載均衡器被理解成一種專用的硬件設(shè)備,這種設(shè)備有很多的局限性。
首先，這種設(shè)備的擴(kuò)展性受限于單個(gè)設(shè)備的最大承受上限，無(wú)法承載谷歌日益增長(zhǎng)的流量。其次，這種設(shè)備無(wú)法滿足谷歌對(duì)高可用性的要求，它們通常是成對(duì)部署來(lái)避免單點(diǎn)故障，這只能提供 1+1的冗余。第三，很難做到甚至無(wú)法做到修改一個(gè)專用的硬件設(shè)備，這就無(wú)法在日新月異的今天提供靈活性和可編碼性。第四，在升級(jí)時(shí)非常的貴,想要提升硬件設(shè)備的性能通常只能購(gòu)買新款并重新部署?；谝陨系木窒扌?，我們決定尋求替代方案。
我們可以通過(guò)一個(gè)分布式的軟件系統(tǒng)來(lái)構(gòu)建一個(gè)負(fù)載均衡器。軟件負(fù)載均衡器(以下簡(jiǎn)稱為slb)相對(duì)于硬件擁有很多優(yōu)點(diǎn)。首先，我們能夠非常方便的進(jìn)行擴(kuò)縮容:我們簡(jiǎn)單的添加maglev節(jié)點(diǎn)后，核心路由通過(guò)ECMP協(xié)議將流量均勻的轉(zhuǎn)發(fā)給所有maglev節(jié)點(diǎn)。同時(shí)，可用性和可靠性也被提升了 因?yàn)閟lb擁有N+1的冗余。這個(gè)系統(tǒng)對(duì)我們都是可控的，我們可以更方便的添加，測(cè)試以及發(fā)布新的特性。同時(shí)，發(fā)布新版的slb是非常簡(jiǎn)單的。因?yàn)閟lb只使用同區(qū)域的機(jī)器,我們可以將服務(wù)分給多個(gè)同區(qū)域的slb來(lái)實(shí)現(xiàn)隔離。
設(shè)計(jì)和實(shí)現(xiàn)一個(gè)slb是有很高復(fù)雜度和挑戰(zhàn)性的。首先，每臺(tái)機(jī)器都必須能夠提供高吞吐量。設(shè)N為機(jī)器數(shù)，T為每臺(tái)機(jī)器的最大吞吐量。則這個(gè)slb的容量為N * T 。 如果T不夠高，那就需要更多的機(jī)器，slb就不具有性價(jià)比了.其次 slb必須提供連接持久化的能力，同一個(gè)連接的數(shù)據(jù)包必須分發(fā)給同一臺(tái)后端機(jī)器。這樣才能確保服務(wù)質(zhì)量，因?yàn)榉?wù)是動(dòng)態(tài)的，而且故障是非常常見(jiàn)的。
這篇文章介紹了maglev，一個(gè)快速可信賴的slb系統(tǒng)。08年以來(lái)，maglev已經(jīng)成為了谷歌前臺(tái)服務(wù)的重要組件，并且為谷歌幾乎所有流量提供服務(wù)。使用最新的高速網(wǎng)絡(luò)技術(shù)，maglev節(jié)點(diǎn)可以達(dá)到線性的吞吐量。通過(guò)一致性hash以及連接跟蹤技術(shù)，maglev能夠在服務(wù)發(fā)生快速變化或者產(chǎn)生異常錯(cuò)誤時(shí)提供可信賴的服務(wù)。本文中有些技術(shù)已經(jīng)誕生很多年了，下文將會(huì)展示如何使用這些技術(shù)來(lái)構(gòu)建一個(gè)slb。
本文的主要內(nèi)容為
- 展示maglev的設(shè)計(jì)與實(shí)現(xiàn)
- 分享maglev在全球范圍使用的經(jīng)驗(yàn)
- 展示maglev的性能
2.系統(tǒng)概述
本節(jié)主要闡述了maglev是如何工作的。在介紹maglev是如何工作之前我們將會(huì)介紹谷歌前臺(tái)業(yè)務(wù)的架構(gòu)。
2.1 前臺(tái)服務(wù)架構(gòu)
圖二展示了一個(gè)小集群下谷歌服務(wù)的架構(gòu)。
每一個(gè)谷歌服務(wù)擁有一個(gè)或者多個(gè)虛擬ip(以下簡(jiǎn)稱vip). vip不同于物理ip，并不分配給一個(gè)特定的網(wǎng)卡，而是由maglev之后的多個(gè)服務(wù)節(jié)點(diǎn)來(lái)提供服務(wù)。maglev將vip與一批服務(wù)節(jié)點(diǎn)關(guān)聯(lián)，并且通過(guò)BGP協(xié)議通知給核心路由。路由將這個(gè)ip發(fā)布到谷歌骨干網(wǎng)，最終，所有的vip都會(huì)全球可用。maglev同時(shí)支持ipv4和ipv6的流量，以下討論的內(nèi)容對(duì)這兩者都是一致的。
當(dāng)一個(gè)用戶嘗試去請(qǐng)求一個(gè)谷歌服務(wù)www.google.com.瀏覽器首先發(fā)送了一次DNS請(qǐng)求，谷歌DNS服務(wù)器會(huì)挑選離用戶最近的區(qū)域，并且返回一個(gè)該區(qū)域的vip。瀏覽器則會(huì)嘗試與vip建立一個(gè)新連接。
當(dāng)核心路由收到VIP的包時(shí)，通過(guò)ECMP協(xié)議分發(fā)給本區(qū)域內(nèi)的maglev節(jié)點(diǎn)（因?yàn)樗衜aglev的鏈路cost都是一致的）。 當(dāng)maglev接受到一個(gè)包，它會(huì)從VIP對(duì)應(yīng)的服務(wù)節(jié)點(diǎn)列表中選擇一個(gè)節(jié)點(diǎn),將目標(biāo)ip改為節(jié)點(diǎn)ip后使用GRE協(xié)議
封裝數(shù)據(jù)包。
當(dāng)包到達(dá)實(shí)際節(jié)點(diǎn)時(shí)，需要解包。當(dāng)響應(yīng)就緒時(shí)，會(huì)將ip來(lái)源設(shè)置為vip，而目標(biāo)ip為用戶ip。我們使用DSR來(lái)繞過(guò)maglev節(jié)點(diǎn)來(lái)發(fā)送相應(yīng)給核心路由以免maglev需要處理通常更大的返回包。DSR的實(shí)現(xiàn)則超出了本文的范圍。
在大型集群中則更加復(fù)雜，我們需要避免將maglev節(jié)點(diǎn)和核心路由部署在同一個(gè)2層網(wǎng)內(nèi)，所以需要一個(gè)封裝器部署在核心路由之后來(lái)將核心路由的包通過(guò)隧道發(fā)送給maglev節(jié)點(diǎn)。
2.2 Maglev 配置
如前文所述，maglev接受來(lái)自核心路由的已聲明的vip包然后轉(zhuǎn)發(fā)給服務(wù)節(jié)點(diǎn)。如圖三所示，每個(gè)maglev節(jié)點(diǎn)包含一個(gè)controller和一個(gè)forwarder,controller和forwarder從圖中的configuration objects獲取vip。configuration objects可以從文件中讀取也可以接受外部系統(tǒng)的rpc請(qǐng)求。
maglev節(jié)點(diǎn)上，controller會(huì)定時(shí)檢查forwarder的健康狀態(tài)。根據(jù)檢查結(jié)果，controller決定是否通過(guò)BGP協(xié)議向核心路由注冊(cè)VIP，這就保證核心路由僅會(huì)向健康的maglev節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)(controller掛了怎么辦？)
maglev節(jié)點(diǎn)接受到的所有vip的數(shù)據(jù)都會(huì)由forwarder來(lái)處理。每個(gè)vip都會(huì)包含一個(gè)或者多個(gè)bp(backend pool) 。除非特別說(shuō)明，否則maglev的backend是服務(wù)節(jié)點(diǎn)。
一個(gè)bp可能包含服務(wù)節(jié)點(diǎn)的真實(shí)ip，也有可能包含其他的bp，這樣就能夠重利用已聲明的bp而不用重復(fù)聲明。每個(gè)bp，根據(jù)實(shí)際需要，都會(huì)擁有一個(gè)或者更多的健康檢查方法來(lái)保證數(shù)據(jù)包只會(huì)轉(zhuǎn)發(fā)給健康的服務(wù)節(jié)點(diǎn)。由于一個(gè)服務(wù)節(jié)點(diǎn)可能存在于多個(gè)bp中，健康檢查需要根據(jù)ip去重來(lái)避免重復(fù)檢查。
forwarder有一個(gè)config manager，負(fù)責(zé)解析和檢查config object。所有配置更新都具有原子性。在推送配置或者健康檢查時(shí)，maglev節(jié)點(diǎn)間可能會(huì)出現(xiàn)不同步，然而，一致性hash能夠保證連接在短窗口期內(nèi)也能大多數(shù)成功(疑)。
我們可以在一個(gè)區(qū)域內(nèi)發(fā)布多組maglev。不同組的maglev使用不同的配置，服務(wù)不同的vip。這種方式可以提供一種隔離性，并且保證服務(wù)的質(zhì)量。也是一種非常適合嘗試新特性的方式，它不會(huì)干擾正常的流量。下文中，每個(gè)區(qū)域僅包含一組maglev。
3. Forwarder的設(shè)計(jì)與實(shí)現(xiàn)
forwarder是maglev的一個(gè)重要組件，它需要快速可信賴的處理非常大的數(shù)據(jù)包。本節(jié)闡述了設(shè)計(jì)理念和forwarder一些核心模塊的實(shí)現(xiàn)以及設(shè)計(jì)理念背后的原理。
3.1 整體架構(gòu)
圖四展示了forwarder的整體架構(gòu)。forwarder從NIC中接受數(shù)據(jù)，將數(shù)據(jù)包的GRE/IP重寫為合適的值后發(fā)回NIC，而不需要經(jīng)過(guò)linux內(nèi)核態(tài)。
從NIC獲取的數(shù)據(jù)包首先由steering module處理，計(jì)算五元組的hash值來(lái)將數(shù)據(jù)包投放到不同的receiving queues中，每個(gè)receiving queues有一個(gè)數(shù)據(jù)包重寫線程處理。處理線程首先嘗試為數(shù)據(jù)包匹配一個(gè)vip，會(huì)將沒(méi)有匹配到vip的數(shù)據(jù)包拋棄。
然后計(jì)算五元組hash，根據(jù)hash從connection tracking table（以下簡(jiǎn)稱連接表）中獲取服務(wù)節(jié)點(diǎn)。為了避免線程間同步，我們不使用steering module中計(jì)算的hash值
連接表保存了連接所對(duì)應(yīng)的服務(wù)節(jié)點(diǎn)、如果連接表中存在該hash的數(shù)據(jù)，并且服務(wù)節(jié)點(diǎn)還是健康的，仍將數(shù)據(jù)轉(zhuǎn)發(fā)給該服務(wù)節(jié)點(diǎn)。否則將調(diào)用一致性hash模塊選取為該數(shù)據(jù)包選擇一個(gè)新的服務(wù)節(jié)點(diǎn)，并將該結(jié)果寫連接表。如果沒(méi)有可用的服務(wù)節(jié)點(diǎn)，數(shù)據(jù)包將被拋棄。每個(gè)處理線程都有一張連接表來(lái)避免多線程讀寫。當(dāng)服務(wù)節(jié)點(diǎn)選擇完成后。處理線程將為數(shù)據(jù)包添加GRE/IP頭，然后發(fā)送到對(duì)應(yīng)的transmission queues 。muxing module來(lái)從transmission queues中獲取數(shù)據(jù)發(fā)送到NIC。
steering module使用五元組hash來(lái)替代輪詢有兩個(gè)原因。第一，避免由于不同線程處理速度差異導(dǎo)致的同一連接的數(shù)據(jù)包順序錯(cuò)亂。第二, forwarder只需要為每個(gè)連接計(jì)算一次hash，節(jié)省時(shí)間并且消除由于服務(wù)節(jié)點(diǎn)更新的競(jìng)態(tài)條件導(dǎo)致的選取不同服務(wù)節(jié)點(diǎn)。在少數(shù)情況下，如果選中的receiving queues已經(jīng)滿了，會(huì)使用輪詢算法來(lái)作為補(bǔ)充，這種fallback機(jī)制可以很好的解決針對(duì)同一五元組的syn flood攻擊。
3.2 高速處理數(shù)據(jù)包
maglev forwarder需要盡可能快的處理數(shù)據(jù)包來(lái)節(jié)約所需要的節(jié)點(diǎn)數(shù)。forwarder能夠達(dá)到線性速率，精確的說(shuō)10Gbps(8c機(jī)器)。可以每秒處理813k的1500byte大小的ip包。然而，我們的要求更加嚴(yán)格，我們必須能夠處理非常小的數(shù)據(jù)包。假定每個(gè)數(shù)據(jù)包平均大小為100byte，forwarder必須能夠每秒處理9.06百萬(wàn)個(gè)數(shù)據(jù)包。本節(jié)將會(huì)描述一些核心技術(shù)來(lái)達(dá)到這個(gè)目標(biāo)。
maglev是一個(gè)運(yùn)行在商用linux服務(wù)器上的用戶態(tài)應(yīng)用。因?yàn)閘inux內(nèi)核網(wǎng)絡(luò)棧處理代價(jià)非常高昂，maglev不使用任何linux網(wǎng)絡(luò)棧的功能。這就需要maglev能夠繞過(guò)內(nèi)核來(lái)處理數(shù)據(jù)。如圖五所示，在NIC硬件的支持下，我們開(kāi)發(fā)了一套方法在NIC和forwarder中傳輸數(shù)據(jù)而不需要任何內(nèi)核介入。當(dāng)maglev啟動(dòng)后，提前申請(qǐng)了一塊packet pool在NIC和forwarder中共享。steering模塊和muxing模塊都有一個(gè)環(huán)形隊(duì)列，隊(duì)列中是packet pool的指針。
steering和muxing模塊都持有了環(huán)形隊(duì)列的三個(gè)指針。在接受側(cè)，NIC將新的數(shù)據(jù)包放在receivied指針處然后將指針向前推。steering模塊分發(fā)數(shù)據(jù)包給處理線程然后推動(dòng)processed指針。因?yàn)閟teeing模塊和muxing模塊共用一個(gè)packet pool 所以還需要一個(gè)reserved指針，當(dāng)packet pool有可用unused塊時(shí)，加入環(huán)形隊(duì)列并推動(dòng)reserved指針。在發(fā)送端，當(dāng)NIC發(fā)送了一個(gè)包時(shí)，會(huì)推動(dòng)send指針。當(dāng)處理線程將數(shù)據(jù)包重寫完成時(shí) 會(huì)推動(dòng)ready指針。當(dāng)NIC發(fā)送完成后會(huì)推動(dòng)recycled指針釋放packet。注意，在所有環(huán)節(jié)都沒(méi)有packet 拷貝操作。
為了減少昂貴的越界操作，我們盡可能的成批的處理數(shù)據(jù)包。此外，處理線程所有數(shù)據(jù)都是獨(dú)享的，來(lái)避免線程安全問(wèn)題以及鎖損耗。我們會(huì)將每個(gè)線程與cpu進(jìn)行綁定，來(lái)避免上下文切換來(lái)帶的損耗以獲得最佳的性能?；谶@些優(yōu)化，maglev可以做到小包下的線性速率，如圖5.2所示(并沒(méi)有這張圖)。
進(jìn)一步，maglev處理每個(gè)數(shù)據(jù)包的延遲是非常短的，一個(gè)標(biāo)準(zhǔn)服務(wù)器上通常只需要350ns。有兩種特殊情況下可能會(huì)需要更長(zhǎng)時(shí)間。第一，因?yàn)閒orwarder是以批處理的方式轉(zhuǎn)發(fā)數(shù)據(jù)包，每一批數(shù)據(jù)包會(huì)在達(dá)到批大小或者超時(shí)時(shí)被處理，在實(shí)踐中我們采取了一個(gè)50us的定時(shí)器。因此，如果maglev處于低負(fù)載時(shí)，最壞情況下數(shù)據(jù)包會(huì)有50us的延遲。動(dòng)態(tài)調(diào)整批大小是一個(gè)可行的改進(jìn)策略。第二，當(dāng)maglev處于過(guò)載情況下，每個(gè)數(shù)據(jù)包可能會(huì)有額外的延遲，maglev能夠緩存的數(shù)據(jù)包最大數(shù)量就是packet pool的大小。超出的部分?jǐn)?shù)據(jù)包將會(huì)被NIC所拋棄。假定packet pool的大小為3000，forwarder每秒能處理一千萬(wàn)個(gè)包，那處理所有緩存包將需要300us。包將獲得一個(gè)最大300us的延遲。幸運(yùn)的，這種情況可以通過(guò)合理的容量規(guī)劃和添加maglev節(jié)點(diǎn)來(lái)解決。
3.3 服務(wù)節(jié)點(diǎn)選擇
當(dāng)一個(gè)數(shù)據(jù)包匹配到一個(gè)VIP后，我們需要從該VIP的BP中選擇一個(gè)服務(wù)節(jié)點(diǎn)。對(duì)于面向連接的協(xié)議如TCP，我們必須要把同一個(gè)連接的數(shù)據(jù)發(fā)送給同一個(gè)服務(wù)節(jié)點(diǎn)。首先我們通過(guò)一致性hash算法來(lái)選擇一個(gè)服務(wù)節(jié)點(diǎn)，這種算法能夠非常均勻的分配流量。然后我們將這個(gè)連接和服務(wù)節(jié)點(diǎn)的對(duì)應(yīng)關(guān)系記錄在本地的連接跟蹤表中。
maglev的連接跟蹤表采用一個(gè)固定大小的hash表，key為五元組的hash值，value為對(duì)應(yīng)的服務(wù)節(jié)點(diǎn)。如果表中沒(méi)有對(duì)應(yīng)的hash值，maglev將會(huì)選取一個(gè)服務(wù)節(jié)點(diǎn)，并且保存到表中。如果存在就直接復(fù)用之前的節(jié)點(diǎn)選擇。只要服務(wù)節(jié)點(diǎn)存活，這能夠保證同一個(gè)連接的包被發(fā)送到同一個(gè)服務(wù)節(jié)點(diǎn)。在BP發(fā)生變化時(shí)，連接追蹤就能夠排上用場(chǎng)了。
然而，在分布式情況下，獨(dú)立的maglev節(jié)點(diǎn)連接追蹤是不夠的。首先，這需要所有相同五元組的數(shù)據(jù)包發(fā)送到同一個(gè)maglev節(jié)點(diǎn)。因?yàn)楹诵穆酚赏ǔ２惶峁┻B接親和的功能，當(dāng)maglev節(jié)點(diǎn)組變化時(shí)這個(gè)就無(wú)法做到了。不幸的是，這種變化是非常常見(jiàn)的。例如，當(dāng)升級(jí)maglev時(shí)，我們需要逐個(gè)重啟maglev節(jié)點(diǎn)，這個(gè)過(guò)程通常需要持續(xù)最少一個(gè)小時(shí)的時(shí)間。有時(shí)我們也會(huì)添加移除替換maglev節(jié)點(diǎn)。當(dāng)新的maglev節(jié)點(diǎn)啟動(dòng)時(shí)，沒(méi)有正確的連接追蹤表，舊連接就會(huì)中斷(疑)。
第二個(gè)理論上的限制是連接追蹤表空間有限，當(dāng)發(fā)生syn flood攻擊時(shí)，這個(gè)表可能會(huì)被填滿。因?yàn)閙aglev只會(huì)在記錄超時(shí)時(shí)移除，一旦表被填滿，我們需要選擇一個(gè)為在表中沒(méi)有記錄的數(shù)據(jù)包選擇服務(wù)節(jié)點(diǎn)。雖然服務(wù)器通常具有較大的內(nèi)存，但是我們通常會(huì)將maglev和其他服務(wù)混布，所以我們需要限制追蹤表的大小。
一旦以上任何一個(gè)情況發(fā)生，我們不再能夠再支持鏈接追蹤功能。因此，maglev提供了一致性hash算法來(lái)保證這種情況下也可以可信賴的分發(fā)數(shù)據(jù)。
3.4 一致性hash
一種可能的解決方式是在所有maglev機(jī)器間共享追蹤表，例如一張分布式的hash table。然而，這會(huì)影響轉(zhuǎn)發(fā)的性能表現(xiàn)，要知道m(xù)aglev節(jié)點(diǎn)上的處理線程都不共享數(shù)據(jù)。
一個(gè)更佳的解決方式是使用本地一致性hash算法。一致性hash的概念第一次出現(xiàn)于二十世紀(jì)九十年代。它能夠生成一張大的查找表。這種方式提供了兩個(gè)maglev需要的特性。
- 負(fù)載均衡: 每個(gè)服務(wù)節(jié)點(diǎn)會(huì)收到幾乎一樣的連接。
- 最小影響: 當(dāng)服務(wù)節(jié)點(diǎn)集變化時(shí)，連接絕大多數(shù)情況下仍然會(huì)被發(fā)送到原來(lái)的服務(wù)節(jié)點(diǎn)上。
現(xiàn)有的hash算法都將最小影響的優(yōu)先級(jí)放在了負(fù)載均衡之上，因?yàn)樗鼈冊(cè)O(shè)計(jì)出來(lái)是為了解決小規(guī)模服務(wù)下的緩存問(wèn)題。然而,maglev更重視負(fù)載均衡。首先，將所有流量盡可能均勻的打到服務(wù)節(jié)點(diǎn)上對(duì)maglev是非常重要的，否則服務(wù)節(jié)點(diǎn)就需要更高的性能來(lái)處理高峰期的流量。對(duì)于一個(gè)VIP，maglev可能有數(shù)百個(gè)服務(wù)節(jié)點(diǎn)。我們的經(jīng)驗(yàn)顯示，這種情況下現(xiàn)有的hash算法需要一個(gè)巨大的hash表來(lái)達(dá)到我們需要的負(fù)載均衡程度。其次，雖然最小影響是非常重要的，但是小概率的影響對(duì)于maglev是可容忍的。大部分情況下，hash表的改變不會(huì)導(dǎo)致連接重置，因?yàn)檫B接追蹤表中原有數(shù)據(jù)。而當(dāng)兩者同時(shí)發(fā)生時(shí)，連接重置的數(shù)量與表中影響記錄數(shù)成正比。
基于以上考慮，我們實(shí)現(xiàn)了一套新的一致性hash，稱作maglev hashing。首先，為每個(gè)服務(wù)節(jié)點(diǎn)生成一個(gè)偏好數(shù)組，接下來(lái)每個(gè)節(jié)點(diǎn)輪流填充他們的偏好位置，知道表被填滿。這樣，maglev hashing為每個(gè)服務(wù)節(jié)點(diǎn)提供了幾乎一樣的機(jī)會(huì)。節(jié)點(diǎn)權(quán)重的區(qū)別可以通過(guò)填充頻率來(lái)實(shí)現(xiàn)。這個(gè)實(shí)現(xiàn)細(xì)節(jié)本文不描述。
設(shè)M為表的大小，每個(gè)服務(wù)節(jié)點(diǎn)的偏好列表被保存在permutation[i]中，偏好列表是一個(gè)隨機(jī)的序列，取值為[0,m-1]。為了生成這個(gè)序列，我們首先為每個(gè)服務(wù)節(jié)點(diǎn)起一個(gè)unique的名字。然后用兩種不同的hash算法計(jì)算名字的hash值，分別作為offset和skip。最后用這兩個(gè)值來(lái)生成序列，如下
offset ← h1(name[i]) mod M
skip ← h2(name[i]) mod (M ?1) +1
permutation[i][ j] ← (offset+ j ×skip) mod M
M必須是一個(gè)素?cái)?shù)以保證skip的值是和M互質(zhì)的。設(shè)N為一個(gè)VIP的BP的節(jié)點(diǎn)數(shù)。
我們使用偽碼1來(lái)生成表
# 偽碼1
01: function POPULATE
02: for each i < N do next[i] ← 0 end for
03: for each j < M do entry[ j] ← ?1 end for
04: n ← 0
05: while true do
06: for each i < N do
07: c ← permutation[i][next[i]]
08: while entry[c] ≥ 0 do
09: next[i] ← next[i] +1
10: c ← permutation[i][next[i]]
11: end while
12: entry[c] ← i
13: next[i] ← next[i] +1
14: n ← n+1
15: if n = M then return end if
16: end for
17: end while
18: end function
我們用next[i]來(lái)記錄i節(jié)點(diǎn)的偏好序列下一個(gè)值，最后表被存在entry數(shù)組中。然后我們依個(gè)用偏好序列填充entry數(shù)組直到填充滿為止
這個(gè)算法必然會(huì)結(jié)束。最差情況下性能為O(m2)，這僅當(dāng)所有服務(wù)節(jié)點(diǎn)的偏好序列全部一致時(shí)發(fā)生。為了避免這種情況，我們通常選取M值需要保證M>>N。這種情況下性能為O(MlogM) 。第n步時(shí)我們需要消耗 M/(M-n)次來(lái)找到一個(gè)空的位置。所以總的嘗試次數(shù)為M/n 從n=1到M的和。每個(gè)服務(wù)節(jié)點(diǎn)占據(jù)表中M/N個(gè)條目。因此 不同服務(wù)節(jié)點(diǎn)占據(jù)的條目數(shù)最多相差1。實(shí)踐中，我們選取的M要大于100*N來(lái)保證不超過(guò)1%的服務(wù)節(jié)點(diǎn)間的差異。Fisher-Yates Shuffle這種序列生成算法可以生成更好的隨機(jī)序列。
我們使用表1來(lái)展示maglev是如何工作的。假設(shè)存在三個(gè)服務(wù)節(jié)點(diǎn)，表的大小為7，offset和skip的值分別為(3,4),(0,2)和(3,1)。最終生成的偏好序列如左列所示。
B1節(jié)點(diǎn)移除之前，整個(gè)表如右列所示。當(dāng)B1移除后，B1占據(jù)的條目將會(huì)均分給其他節(jié)點(diǎn)。同時(shí)只有第六行收到了影響。而實(shí)踐中，當(dāng)我們使用更大的表時(shí)，影響會(huì)更小，會(huì)在5.3節(jié)做詳細(xì)論述。
