「Consistent Hashingをためす」の編集履歴（バックアップ）一覧はこちら

「Consistent Hashingをためす」(2010/05/26 (水) 02:32:22) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

　だいぶ前にかった[[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で作成してみました。

**Consistent Hashing
　Perl版、Ruby版と同じく、まずは引数で指定されたノード名（複数）のハッシュ値をmd5で求めます。次に'A'〜'Z'のハッシュ値をmd5で求め、それと等しいか、それより大きいがもっとも近いハッシュ値をもつノードを処理させるノードに決定します。
'A'〜'Z'の値は、クライアントが利用するサーバを決定するための情報の例として使っています。実際のシステムでは、ユーザ毎に利用するサーバを振り分けるなら、ログインIDなどが該当すると思います。

 public class Main {
    private static String search( NavigableMap<BigInteger, String> circle, BigInteger rec ){
        // circleをNavigableMapを使用し、ceilingKeyによりもっとも近いkeyを取得
        BigInteger key = circle.ceilingKey(rec);
        if( key == null ){
            // 指定されたレコードがkeyの最大値を越える場合は最小ノードに入れる
            return (String)circle.get(circle.firstKey());
        }else{
            // ノードの最大値を越える場合は最小ノードに入れる
            return (String)circle.get(key);
        }
    }
 
    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 = 0;
        NavigableMap<BigInteger, String> circle = new TreeMap<BigInteger, String>();
        SortedMap<String, List> nodesmap = new TreeMap<String, List>();
        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");
 
        for( int i = 0; i < args.length; i++ ){
            nodesmap.put( args[i], new LinkedList<String>());
        }
 
        for( String node : nodesmap.keySet() ){
            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");
        }
    }
 }

***実行結果
 $ java Main n1 n2 n3 n4   <-- 引数はノード名です。
 n1 H T 
 n2 A B F K M N P S U V W Y 
 n3 C D E J O Q X Z 
 n4 G I L R 

ここでノードn4を減らしてみる。（実システムではサーバ故障したような場合ですね）
 $ java Main n1 n2 n3
 n1 H T 
 n2 A B F K M N P S U V W Y 
 n3 C D E G I J L O Q R X Z 

この結果からわかるとおり、n4にあったものは全てn3に移動しています。これは、このアルゴリズムだと自分の値以上でもっとも近いハッシュ値のノードに決定するため、あるノードがなくなると、そのノードのハッシュより大きい次のノードに属すことになります。
これだと、ノードの増減による偏りが大きいため、次に示す仮想ノードをもちいて偏りを少なくします。

**仮想ノードノードを用いたConsistent Hshing
　上記のConsistent Hashingの考え方は、ノードを円周上にハッシュ値の順に配置して、ひとつ前のノードと当該ノードまでの間にある情報（上記での'A'〜'Z'の値）を、当該ノードの情報として決定します。ここで、ひとつのノードを複数の仮想ノードにして、それぞれのハッシュ値を求め円周上に配置します。すると１つのノードの仮想ノードが円周上にまばらに分散されるため、そのノードに属す情報も円周上に分散されます。そこからノードをひとつ減らすと、減る仮想ノードの情報は、その次の仮想ノードに属すことになります。各ノードの仮想ノードが不規則に並んでいれば、減った仮想ノード情報は、他の複数のノードに分散されます。（わかりにくかったら、上記のコンシステントハッシングのリンク先を見てください。）

 public class Main_Vnode {
    private static String search( NavigableMap<BigInteger, String> circle, BigInteger rec ){
        // circleをNavigableMapに変更し、ceilingKeyにより、もっとも近いkeyを取得
        BigInteger key = circle.ceilingKey(rec);
        if( key == null ){
            // 指定されたレコードがkeyの最大値を越える場合は最小ノードに入れる
            return (String)circle.get(circle.firstKey());
        }else{
            // ノードの最大値を越える場合は最小ノードに入れる
            return (String)circle.get(key);
        }
    }
    
    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 = 0;
        NavigableMap<BigInteger, String> circle = new TreeMap<BigInteger, String>();
        SortedMap<String, List> nodesmap = new TreeMap<String, List>();
        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");
        
        for( int i = 0; i < args.length; i++ ){
            if( i == 0){
                numOfReplicants = Integer.valueOf(args[0]);
            } else {
                nodesmap.put( args[i], new LinkedList<String>());
            }
        }
              
        for( String node : nodesmap.keySet() ){
            circle.put( getHash(node), node );
            for(int i=1; i <= numOfReplicants; i++){
                circle.put( getHash(node + '_' + i), 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");
        }       
    }
 }

***実行結果
 $ java Main_Vnode 100 n1 n2 n3 n4　　<---第一引数が１ノードあたりの仮想ノード数で、その後ろの引数はノード名です。
 n1 A E F O P Q U V 
 n2 B H S T Y 
 n3 C K L M N Z 
 n4 D G I J R W X 

仮想ノードが円周上に分散したために、仮想ノードを使わないものより、ノード間の偏りが減っています。
さきほど同様ひとつノードを減らして実行します。
 $ java Main_Vnode 100 n1 n2 n3
 n1 A D E F O P Q U V 
 n2 B H I S T W Y 
 n3 C G J K L M N R X Z 

n4にあったデータが、さきほどはn3にだけ移動したものが、n1、n2、n3の全ノードに移っています。

perlやrubyと比べると、やはりJavaはコード量が大いですね。

----
#comment
----

　だいぶ前にかった[[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で作成してみました。

**Consistent Hashing
　Perl版、Ruby版と同じく、まずは引数で指定されたノード名（複数）のハッシュ値をmd5で求めます。次に'A'〜'Z'のハッシュ値をmd5で求め、それと等しいか、それより大きいがもっとも近いハッシュ値をもつノードを処理させるノードに決定します。
'A'〜'Z'の値は、クライアントが利用するサーバを決定するための情報の例として使っています。実際のシステムでは、ユーザ毎に利用するサーバを振り分けるなら、ログインIDなどが該当すると思います。

 public class Main {
    private static String search( NavigableMap<BigInteger, String> circle, BigInteger rec ){
        // circleをNavigableMapを使用し、ceilingKeyによりもっとも近いkeyを取得
        BigInteger key = circle.ceilingKey(rec);
        if( key == null ){
            // 指定されたレコードがkeyの最大値を越える場合は最小ノードに入れる
            return (String)circle.get(circle.firstKey());
        }else{
            // ノードの最大値を越える場合は最小ノードに入れる
            return (String)circle.get(key);
        }
    }
 
    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 = 0;
        NavigableMap<BigInteger, String> circle = new TreeMap<BigInteger, String>();
        SortedMap<String, List> nodesmap = new TreeMap<String, List>();
        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");
 
        for( int i = 0; i < args.length; i++ ){
            nodesmap.put( args[i], new LinkedList<String>());
        }
 
        for( String node : nodesmap.keySet() ){
            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");
        }
    }
 }

***実行結果
 $ java Main n1 n2 n3 n4   <-- 引数はノード名です。
 n1 H T 
 n2 A B F K M N P S U V W Y 
 n3 C D E J O Q X Z 
 n4 G I L R 

ここでノードn4を減らしてみる。（実システムではサーバ故障したような場合ですね）
 $ java Main n1 n2 n3
 n1 H T 
 n2 A B F K M N P S U V W Y 
 n3 C D E G I J L O Q R X Z 

この結果からわかるとおり、n4にあったものは全てn3に移動しています。これは、このアルゴリズムだと自分の値以上でもっとも近いハッシュ値のノードに決定するため、あるノードがなくなると、そのノードのハッシュより大きい次のノードに属すことになります。
これだと、ノードの増減による偏りが大きいため、次に示す仮想ノードをもちいて偏りを少なくします。

**仮想ノードノードを用いたConsistent Hshing
　上記のConsistent Hashingの考え方は、ノードを円周上にハッシュ値の順に配置して、ひとつ前のノードと当該ノードまでの間にある情報（上記での'A'〜'Z'の値）を、当該ノードの情報として決定します。ここで、ひとつのノードを複数の仮想ノードにして、それぞれのハッシュ値を求め円周上に配置します。すると１つのノードの仮想ノードが円周上にまばらに分散されるため、そのノードに属す情報も円周上に分散されます。そこからノードをひとつ減らすと、減る仮想ノードの情報は、その次の仮想ノードに属すことになります。各ノードの仮想ノードが不規則に並んでいれば、減った仮想ノード情報は、他の複数のノードに分散されます。（わかりにくかったら、上記のコンシステントハッシングのリンク先を見てください。）

 public class Main_Vnode {
    private static String search( NavigableMap<BigInteger, String> circle, BigInteger rec ){
        // circleをNavigableMapに変更し、ceilingKeyにより、もっとも近いkeyを取得
        BigInteger key = circle.ceilingKey(rec);
        if( key == null ){
            // 指定されたレコードがkeyの最大値を越える場合は最小ノードに入れる
            return (String)circle.get(circle.firstKey());
        }else{
            // ノードの最大値を越える場合は最小ノードに入れる
            return (String)circle.get(key);
        }
    }
    
    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 = 0;
        NavigableMap<BigInteger, String> circle = new TreeMap<BigInteger, String>();
        SortedMap<String, List> nodesmap = new TreeMap<String, List>();
        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");
        
        for( int i = 0; i < args.length; i++ ){
            if( i == 0){
                numOfReplicants = Integer.valueOf(args[0]);
            } else {
                nodesmap.put( args[i], new LinkedList<String>());
            }
        }
              
        for( String node : nodesmap.keySet() ){
            circle.put( getHash(node), node );
            for(int i=1; i <= numOfReplicants; i++){
                circle.put( getHash(node + '_' + i), 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");
        }       
    }
 }

***実行結果
 $ java Main_Vnode 100 n1 n2 n3 n4　　<---第一引数が１ノードあたりの仮想ノード数で、その後ろの引数はノード名です。
 n1 A E F O P Q U V 
 n2 B H S T Y 
 n3 C K L M N Z 
 n4 D G I J R W X 

仮想ノードが円周上に分散したために、仮想ノードを使わないものより、ノード間の偏りが減っています。
さきほど同様ひとつノードを減らして実行します。
 $ java Main_Vnode 100 n1 n2 n3
 n1 A D E F O P Q U V 
 n2 B H I S T W Y 
 n3 C G J K L M N R X Z 

n4にあったデータが、さきほどはn3にだけ移動したものが、n1、n2、n3の全ノードに移っています。

perlやrubyと比べると、Javaはコード量が多いですね。

----
#comment
----