「Consistent Hashingをためす」の編集履歴（バックアップ）一覧に戻る

Consistent Hashingをためす - (2010/05/26 (水) 01:24:36) のソース

　だいぶ前にかった[[UNIX magazine 2009年04月号>http://www.amazon.co.jp/gp/product/B001U52MP0?ie=UTF8&tag=muranagasview-22&linkCode=as2&camp=247&creative=1211&creativeASIN=B001U52MP0]]でクラウドを特集していた。
　この中で、サーバ台数を増やしてスケールアウトする場合に、クライアントがどのサーバに処理させるかを決めるためにコンシステントハッシング（Consistent Hashing）が紹介されていた。
　なお、コンシステントハッシングについては、以下のリンクを見てください。
-[[Tom White's Blog: Consistent Hashing>http://weblogs.java.net/blog/tomwhite/archive/2007/11/consistent_hash.html]]
-[[コンシステント・ハッシュ法 (Tom White's Blog の日本語訳)>http://www.hyuki.com/yukiwiki/wiki.cgi?ConsistentHashing]]

　最近ネットをみていたら、[[「Consistent Hasing を Ruby で試す」>http://tam.qmix.org/dist/wiki/ConsistentHashingRuby]]にて、rubyを使ってConsistent Hashingをためしていた。そのプログラムは、もともと[[「Consistent Hashing を試す」>http://8-p.info/consistent-hashing/]]にあるperlのプログラムをrubyにしたそうで、私もJavaで作成してみました。

上記のサイトでは、
 import java.math.BigInteger;
 import java.security.MessageDigest;
 import java.security.NoSuchAlgorithmException;
 import java.util.Arrays;
 import java.util.Collection;
 import java.util.LinkedList;
 import java.util.List;
 import java.util.SortedMap;
 import java.util.TreeMap;
 
 public class Main {
    //private static final SortedMap<byte[], String> circle = new TreeMap<byte[], String>();
    private static final SortedMap<BigInteger, String> circle = new TreeMap<BigInteger, String>();
    private static final SortedMap<String, List> nodesmap = new TreeMap<String, List>();
    private static final List<String> alphalist = Arrays.asList(
            "A","B","C","D","E","F","G","H","I","J","K","L","M",
            "N","O","P","Q","R","S","T","U","V","W","X","Y","Z");
 
    private static String search( SortedMap circle, BigInteger rec ){
        // circleはSortedMapなので、Keyが小さい方から取得される前提
        for( Object circleKey : circle.keySet()){
            if( rec.compareTo((BigInteger)circleKey) != 1 ){
                return (String)circle.get(circleKey);
            }
        }
 
        // ノードの最大値を越える場合は最小ノードに入れる
        return (String)circle.get(circle.firstKey());
    }
    
    private static BigInteger getHash( String value ) throws NoSuchAlgorithmException{
        int ret = 0;
        MessageDigest digest = MessageDigest.getInstance( "md5" );
        byte[] byteHash = digest.digest(value.getBytes());
        return new BigInteger(byteHash);
    }
    
    public static void main(String[] args) throws NoSuchAlgorithmException {
        int numOfReplicants = args.length;
        Collection<String> nodes = Arrays.asList(args);
              
        for( String node : nodes ){
            circle.put( getHash(node), node );
        }
        
        for( String str : alphalist ){
            String node = search(circle, getHash(str));
            if( !nodesmap.containsKey(node)){
                List<String> asciiList = new LinkedList<String>();
                asciiList.add(str);
                nodesmap.put(node, asciiList);
            }else{
                nodesmap.get(node).add(str);
            }
        }
        
        for( String node : nodesmap.keySet()){
            System.out.print(node + " ");
            List<String> asciiList = nodesmap.get(node);
            for( String strascii : asciiList ){
                System.out.print(strascii + " ");
            }
            System.out.print("\n");
        }       
    }
 }