일치성hash 알고리즘의java 구현

일치성hash 알고리즘의java 구현

분포식 장면에서 데이터의 균일한 분포는 일치성hash링을 통해 해결할 수 있다. 일치성hash링에 대한 구체적인 소개는 인터넷에 많은 블로그가 상세하게 썼다. 여기서 주로 코드 실현을 말한다. 노드 데이터를 노드 클래스로 추상화하고 일치성hash링을 HashCircle 클래스로 추상화한다. 구체적인 코드는 다음과 같다.

Node.java

import java.util.ArrayList;
import java.util.List;


public class Node {
    private List<Integer> partition;
    private String name;

    Node(String name)
    {
        setPartition(new ArrayList());
        this.setName(name);
    }

    public void addPartition(int p)
    {
        partition.add(p);
    }

    public void showNode()
    {
        System.out.println("name:      "+name);
        System.out.println("partition: "+partition.toString());
    }

    public List<Integer> getPartition() {
        return partition;
    }

    public void setPartition(List partition) {
        this.partition = partition;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }
}

HashCircle.java

import java.io.UnsupportedEncodingException;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.util.ArrayList;
import java.util.List;
import java.util.SortedMap;
import java.util.TreeMap;


public class HashCircle {

    public static void main(String[] args) throws NoSuchAlgorithmException {
        List<Node> nodes = new ArrayList<Node>();
        TreeMap<Long, Node> dht = new TreeMap<Long, Node>();
        int virsulNode = 150;
        //   10 Node  
        for (int i=0; i<10; i++)
        {
            nodes.add(new Node("node"+i));
        }

        // Node         hash 
        for (int i=0; i(); i++)
        {
            Node node = nodes.get(i);
            for (int j=0; j
            {
                dht.put(hash(computeMd5("node"+i+j), 2), node);
            }
        }

        // 200     hash 
        for (int i=0; i<200; i++)
        {
            Integer partition = i;
            Node node;
            SortedMap<Long, Node> map = dht.tailMap(hash(computeMd5("partition"+i), 2));
            if (map.isEmpty())
                node = nodes.get(0);
            else
                node = dht.get(map.firstKey());
            node.addPartition(partition);
        }

        for (int i=0; i(); i++)
        {
            nodes.get(i).showNode();
        }
    }

    /**
     *   MD5 
     */
    public static byte[] computeMd5(String k) {
        MessageDigest md5;
        try {
            md5 = MessageDigest.getInstance("MD5");
        } catch (NoSuchAlgorithmException e) {
            throw new RuntimeException("MD5 not supported", e);
        }
        md5.reset();
        byte[] keyBytes = null;
        try {
            keyBytes = k.getBytes("UTF-8");
        } catch (UnsupportedEncodingException e) {
            throw new RuntimeException("Unknown string :" + k, e);
        }

        md5.update(keyBytes);
        return md5.digest();
    }

    /**
     *   2^32         
     *
     * @param digest
     * @param nTime
     * @return
     */
    public static long hash(byte[] digest, int nTime) {
        long rv = ((long) (digest[3 + nTime * 4] & 0xFF) << 24)
                | ((long) (digest[2 + nTime * 4] & 0xFF) << 16)
                | ((long) (digest[1 + nTime * 4] & 0xFF) << 8)
                | (digest[0 + nTime * 4] & 0xFF);

        return rv & 0xffffffffL; /* Truncate to 32-bits */
    }
}