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

　　業務場景

　　分布式系統在應用中經常會面對如下業務場景：

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

　　分布式存儲系統，海量數據被分片存儲，那么如何讓每個Data節點上分片更加均勻，并且在Data節點退出/加入時保持數據分片的穩定性。

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

　　問題分析

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

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

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

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

　　常見算法

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

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

　　有界負載一致性哈希

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

　　算法描述

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

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

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

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

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

　　實現

　　下面通過Java偽代碼對該算法進行實現：

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

　　效果

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

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

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

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

　　總結

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