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

　　業(yè)務場景

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

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

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

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

　　問題分析

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

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

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

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

　　常見算法

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

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

　　有界負載一致性哈希

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

　　算法描述

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

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

　　3. 使用一致性哈希算法為任務尋找計算節(jié)點，當所選節(jié)點已有任務數(shù)大于tc時，順序尋找下一個已有任務數(shù)不大于tc的節(jié)點，直到找到并將任務分配給該節(jié)點。

　　4. 重復步驟3直到所有任務分配完成。

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

　　實現(xiàn)

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

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

　　效果

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

　　圖1 單個計算節(jié)點分配任務數(shù)(輪詢、一致性哈希、有界負載一致性哈希(c=1.1))

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

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

　　總結

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