處理大規(guī)模日志計(jì)算任務(wù)是運(yùn)維團(tuán)隊(duì)經(jīng)常遇到的問題。為保證任務(wù)分配均勻性和穩(wěn)定性，百度云智能運(yùn)維架構(gòu)團(tuán)隊(duì)對(duì)原始一致性哈希算法進(jìn)行改進(jìn)。新算法在保持原始一致性哈希算法穩(wěn)定性的同時(shí)，通過設(shè)置不均衡因子來控制分配的不均勻范圍，達(dá)到負(fù)載分配均勻性與穩(wěn)定性有效兼容。

　　業(yè)務(wù)場(chǎng)景

　　分布式系統(tǒng)在應(yīng)用中經(jīng)常會(huì)面對(duì)如下業(yè)務(wù)場(chǎng)景：

　　計(jì)算系統(tǒng)每分鐘有大量的定時(shí)任務(wù)需要及時(shí)調(diào)度并按時(shí)完成，單機(jī)在處理能力和時(shí)效性上都無法滿足要求，需要將任務(wù)分配到大量Work節(jié)點(diǎn)上進(jìn)行并行計(jì)算，如何均勻分配這些任務(wù)，并且在任務(wù)增減，Work節(jié)點(diǎn)退出/加入(伸縮能力)時(shí)保持任務(wù)分配的穩(wěn)定性(不會(huì)引起大量任務(wù)遷移)。

　　分布式存儲(chǔ)系統(tǒng)，海量數(shù)據(jù)被分片存儲(chǔ)，那么如何讓每個(gè)Data節(jié)點(diǎn)上分片更加均勻，并且在Data節(jié)點(diǎn)退出/加入時(shí)保持?jǐn)?shù)據(jù)分片的穩(wěn)定性。

　　高并發(fā)Web系統(tǒng)中，架構(gòu)上幾乎都是一個(gè)或多個(gè)反向代理服務(wù)器(如Nginx)來做七層負(fù)載均衡，后端使用應(yīng)用服務(wù)器集群(如Tomcat)提供服務(wù)，這種架構(gòu)具備水平伸縮能力，那么反向代理如何均勻分配請(qǐng)求，并且盡量保證請(qǐng)求Session粘性。

　　問題分析

　　上述問題可以抽象為對(duì)分配算法如下幾個(gè)方面的要求：

　　公平性：即算法的結(jié)果要盡可能地公平，不能造成分配不均問題，這點(diǎn)在分布式系統(tǒng)中尤其重要，公平性就是要盡可能避免由于負(fù)載過重/過輕導(dǎo)致系統(tǒng)出現(xiàn)慢節(jié)點(diǎn)/饑餓節(jié)點(diǎn)影響系統(tǒng)整體性能和資源利用率。

　　穩(wěn)定性：分布式系統(tǒng)中，集群節(jié)點(diǎn)維護(hù)、故障、宕機(jī)、重啟、擴(kuò)縮容是非常常見的，穩(wěn)定性就是要保證計(jì)算任務(wù)、數(shù)據(jù)、請(qǐng)求在節(jié)點(diǎn)加入/退出時(shí)盡可能保持穩(wěn)定，不引起大量計(jì)算任務(wù)重分配、數(shù)據(jù)遷移、請(qǐng)求轉(zhuǎn)移，這對(duì)系統(tǒng)整體可靠性、穩(wěn)定性、高性能至關(guān)重要。

　　可行性：算法在工程實(shí)踐上一定是可行的，具體體現(xiàn)在這兩個(gè)方面：時(shí)間復(fù)雜度、空間復(fù)雜度，時(shí)間復(fù)雜度要求一定要快，滿足業(yè)務(wù)場(chǎng)景對(duì)響應(yīng)時(shí)間的要求，空間復(fù)雜度要求占用資源少，滿足業(yè)務(wù)在資源投入和收益上的平衡。

　　常見算法

　　面對(duì)這些問題有很多常見的處理方法，例如輪詢(Round-Robin)、取模哈希、一致性哈希、按ID范圍分段、自定義分段策略，下面我們選擇幾種常見分配算法，分析它們?cè)诠叫?，穩(wěn)定性及可用性方面的能力：

　　從上面表格對(duì)比可知這幾種常見算法都無法兼具三種特性，那么有沒有一個(gè)算法，能同時(shí)具備公平性、穩(wěn)定性以及可行性?接下來介紹的這個(gè)算法能在保持原始一致性哈希穩(wěn)定性的同時(shí)還具備可控的均勻性，已經(jīng)實(shí)際應(yīng)用于我們的分布式近線計(jì)算系統(tǒng)中用于分配定時(shí)計(jì)算任務(wù)，目前來看效果還不錯(cuò)。

　　有界負(fù)載一致性哈希

　　有界負(fù)載一致性哈希(Bounded-Load Consistent Hash)算法是對(duì)原始一致性哈希算法的改進(jìn)，相對(duì)于原始一致性哈希算法的不均勻問題，新算法能通過設(shè)置一個(gè)不均衡因子，來控制整個(gè)分配的不均衡范圍。

　　算法描述

　　1. 假設(shè)計(jì)算節(jié)點(diǎn)數(shù)為n，任務(wù)數(shù)為m，則每個(gè)計(jì)算節(jié)點(diǎn)的平均任務(wù)數(shù)t=⌈m/n⌉(取上界是為了保證t*n >= m，保證所有任務(wù)都能被分配執(zhí)行)。

　　2. 設(shè)置不均衡因子c(取值范圍為1 < c < ∞)用于控制最大不均勻范圍，則每個(gè)節(jié)點(diǎn)分配的最大任務(wù)數(shù)為c*t。

　　3. 使用一致性哈希算法為任務(wù)尋找計(jì)算節(jié)點(diǎn)，當(dāng)所選節(jié)點(diǎn)已有任務(wù)數(shù)大于tc時(shí)，順序?qū)ふ蚁乱粋€(gè)已有任務(wù)數(shù)不大于tc的節(jié)點(diǎn)，直到找到并將任務(wù)分配給該節(jié)點(diǎn)。

　　4. 重復(fù)步驟3直到所有任務(wù)分配完成。

　　不均衡因子c越接近1整個(gè)分配越均衡(整個(gè)分配過程耗時(shí)會(huì)變長(zhǎng))，跟輪詢算法效果一樣了，c無窮大時(shí)跟原始一致性哈希效果一樣了。

　　實(shí)現(xiàn)

　　下面通過Java偽代碼對(duì)該算法進(jìn)行實(shí)現(xiàn)：

　　因?yàn)檫@一行代碼maxAssignedSize*totalOfNode>=totalOfSlice，所以上面的算法不會(huì)導(dǎo)致死循環(huán)，每次分配必然有一個(gè)計(jì)算節(jié)點(diǎn)能接受這個(gè)任務(wù);最終結(jié)果就是每個(gè)節(jié)點(diǎn)分配的任務(wù)數(shù)都不會(huì)超過maxAssignedSize，不均勻問題通過imbalanceFactor參數(shù)來控制;當(dāng)計(jì)算節(jié)點(diǎn)退出時(shí)，其上面的任務(wù)遷移也只限于跟它相鄰的一個(gè)或多個(gè)節(jié)點(diǎn)，并不會(huì)導(dǎo)致大范圍重分配。

　　效果

　　下面通過對(duì)比近線計(jì)算分配算法分別選擇輪詢、一致性哈希、有界負(fù)載一致性哈希時(shí)的業(yè)務(wù)指標(biāo)，從分配均衡性，計(jì)算節(jié)點(diǎn)加入/退出的穩(wěn)定性兩個(gè)方面來衡量這三種算法的效果：

　　圖1 單個(gè)計(jì)算節(jié)點(diǎn)分配任務(wù)數(shù)(輪詢、一致性哈希、有界負(fù)載一致性哈希(c=1.1))

　　圖2 節(jié)點(diǎn)加入/退出時(shí)遷移任務(wù)數(shù)(輪詢、一致性哈希、有界負(fù)載一致性哈希(c=1.1))

　　很明顯可以看到，輪詢?cè)谌蝿?wù)分配上非常均勻，但是當(dāng)計(jì)算節(jié)點(diǎn)變動(dòng)時(shí)，導(dǎo)致大量任務(wù)重分配，而一致性哈希解決了任務(wù)大量重分配問題，但任務(wù)分配不均勻而且無法控制這種均勻性，而有界一致性哈希在任務(wù)分配均勻性和重分配都表現(xiàn)非常好，通過不均衡因子來限制不均勻范圍，本身一致性哈希又有效避免了大量任務(wù)重分配。

　　總結(jié)

　　分布式近線計(jì)算系統(tǒng)的任務(wù)分配算法在業(yè)務(wù)需求驅(qū)動(dòng)下，經(jīng)歷了從最初的均勻輪詢(防止分配不均導(dǎo)致慢節(jié)點(diǎn))，到使用一致性哈希(防止任務(wù)因?yàn)橛?jì)算節(jié)點(diǎn)加入/退出導(dǎo)致重分配，為了達(dá)到盡可能均勻優(yōu)化虛擬節(jié)點(diǎn)個(gè)數(shù))，再到有界負(fù)載一致性哈希通過參數(shù)控制解決原始一致性哈希分布不均勻問題，每次分配算法改進(jìn)都極大提高了系統(tǒng)整體穩(wěn)定性;有界負(fù)載一致性哈希算法具有通用性，可以有效解決任務(wù)分配，數(shù)據(jù)分片，請(qǐng)求分發(fā)等業(yè)務(wù)場(chǎng)景中分配均勻性與穩(wěn)定性問題。