ConsistentHash – JAVA編程語言程序開發技術文章

server點分佈在很大的一個circle上,circle的點數量可以是int.MAX個。

每個key同樣hash後,落到int.MAX個點的大circle上,尋找最近的server點。

加server時,或者移去server時,其它server落在circle上的位置不會變,所以最大限度避免瞭數據抖動。 如果是傳統方法的hash算法,任何一個server節點的增加或者刪除,都會導致整個系統的所有cache落點改變。

圖1, A、B、C為三個緩存Server所在的點。 1-4是cache item key的hash值。

 

圖2,移去C緩存、加入D緩存,1,2兩個點不會受到任何幹擾。

 

[java] 
/**
 * Consistent Hash Algorithm, see:
 * https://weblogs.java.net/blog/2007/11/27/consistent-hashing
 */ 
public class ConsistentHash<T> { 
 
    private SortedMap<Integer, T> circle; 
 
    public ConsistentHash(SortedMap<Integer, T> serverMap) { 
        this.circle = serverMap; 
    } 
 
    public T get(String key) { 
 
        int hash = hash32(key); 
        if (!circle.containsKey(hash)) { 
            SortedMap<Integer, T> tailMap = circle.tailMap(hash); 
            if (tailMap.isEmpty()) { 
                hash = circle.firstKey(); 
            } else { 
                hash = tailMap.firstKey(); 
            } 
        } 
        return circle.get(hash); 
    } 
     
    private static final int FNV_32_INIT = 0x711c9dc5; 
    private static final int FNV_32_PRIME = 0x01000193; 
    public static int hash32(final String k) { 
        int rv = FNV_32_INIT; 
        for(byte b : k.getBytes()) { 
            rv ^= b; 
            rv *= FNV_32_PRIME; 
        } 
        return rv; 
    } 
 

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *