初期バージョン から バージョン 1 における更新: ConsistentHashingRuby

更新日時:

2008/06/29 13:04:30 (2 年 前)

更新者:

tam

コメント:

--

ConsistentHashingRuby

@@ +1 @@
+= Consistent Hasing を Ruby で試す =
+
+Consistent Hashing は、複数のコンピュータ(ノード)にレコードを分散するのに使われるアルゴリズムです。
+
+[http://8-p.info/consistent-hashing/ Consistent Hashing を試す]ではプログラムサンプルが Perl で書かれていますが、それを Ruby に書き直してみました。それだけではなんなので、二分探索を用いてキーの検索の高速化も試みています。
+
+プログラムの説明については、[http://8-p.info/consistent-hashing/ Consistent Hashing を試す]も併せて参照してください。
+
+== サーバー台数で割った余り (mod) を使用する ==
+省略
+
+== Consistent Hashing ==
+Perl版と同じアルゴリズムで、キーとノードのハッシュ値を計算し、キーのハッシュ値に近い値を持つノードを選択します。このプログラムを ch1.rb とします。
+{{{
+require 'digest/md5'
+
+def search circle, key
+  for i in 1...circle.size
+    if circle[i-1][:key] < key and key < circle[i][:key]
+      return circle[i][:name]
+    end
+  end
+  return circle[0][:name]
+end
+
+nodes = {}
+ARGV.each {|arg| nodes[arg] = [arg]}
+
+circle = nodes.keys.map {|name|
+  {:key=>Digest::MD5.hexdigest(name), :name=>name}}.sort_by {|h| h[:key]}
+
+for rec in 'A'..'Z'
+  name = search circle, Digest::MD5.hexdigest(rec)
+  nodes[name].push rec
+end
+
+puts nodes.keys.sort.map {|key| nodes[key].join(' ')}.join("\n")
+}}}
+実行結果は、当然 Perl版と同じになります。この段階では、ノードによってレコードの数が偏っています。
+{{{
+$ ruby ch1.rb 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
+}}}
+ノードをひとつ減らしてみます。
+{{{
+$ ruby ch1.rb 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
+
+}}}
+
+== 仮想ノード ==
+ノードごとの偏りを少なくするため、仮想ノードの概念を取り入れてみます。このプログラムを ch2.rb とします。
+{{{
+require 'digest/md5'
+
+def search circle, key
+  for i in 1...circle.size
+    if circle[i-1][:key] < key and key < circle[i][:key]
+      return circle[i][:name]
+    end
+  end
+  return circle[0][:name]
+end
+
+number_of_replicants = ARGV.shift
+nodes = {}
+ARGV.each {|arg| nodes[arg] = [arg]}
+
+circle = nodes.keys.map {|name|
+  (0..number_of_replicants.to_i).map {|n|
+    suffix = n.zero? ? '' : "_#{n}"
+    {:key=>Digest::MD5.hexdigest(name+suffix), :name=>name}
+  }
+}.flatten.sort_by {|h| h[:key]}
+
+for rec in 'A'..'Z'
+  name = search circle, Digest::MD5.hexdigest(rec)
+  nodes[name].push rec
+end
+
+puts nodes.keys.sort.map {|key| nodes[key].join(' ')}.join("\n")
+}}}
+仮想ノードを100にした場合の実行結果は以下のようになります。先ほどよりはだいぶ偏りが少なくなりました。
+{{{
+$ ruby ch2.rb 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
+}}}
+ノードを一つ減らすと以下のようになります。
+{{{
+$ ruby ch2.rb 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
+}}}
+
+== 二分探索 ==
+これまでのプログラムでは、キーの値に近いノードを検索するのに線形探索を行っていました。これではノードの数が増えるにしたがって遅くなるので二分探索を用いるように変更します。このプログラムを ch3.rb とします。
+{{{
+require 'digest/md5'
+
+def search circle, key
+  left = 0
+  return circle[0][:name] if circle[-1][:key] < key or key <= circle[0][:key]
+  right = circle.size - 1
+  while left <= right do
+    mid = (left + right) / 2
+    return circle[mid][:name] if circle[mid-1][:key] < key and key <= circle[mid][:key]
+    if circle[mid][:key] < key
+      left = mid + 1
+    else
+      right = mid - 1
+    end
+  end
+  return nil
+end
+
+number_of_replicants = ARGV.shift
+nodes = {}
+ARGV.each {|arg| nodes[arg] = [arg]}
+
+circle = nodes.keys.map {|name|
+  (0..number_of_replicants.to_i).map {|n|
+    suffix = n.zero? ? '' : "_#{n}"
+    {:key=>Digest::MD5.hexdigest(name+suffix), :name=>name}
+  }
+}.flatten.sort_by {|h| h[:key]}
+
+for rec in 'A'..'Z'
+  name = search circle, Digest::MD5.hexdigest(rec)
+  nodes[name].push rec
+end
+
+puts nodes.keys.sort.map {|key| nodes[key].join(' ')}.join("\n")
+}}}
+実行結果は(あたりまえですが)線形探索版と同じです。
+{{{
+$ ruby ch3.rb 1000 n1 n2 n3 n4 
+n1 A F G K L N P Q Z
+n2 T U V X Y
+n3 C D M W
+n4 B E H I J O R S
+}}}
+線形探索版と二分探索版の速度を比較してみました。レコード A..Z に対する検索部分をそれぞれ1000回実行し、合計を求めました。二分探索のほうが圧倒的に速いですが、ノードの数が増えるほどその差は顕著になるのがわかります。
+{{{
+仮想ノードが100の場合
+             user     system      total        real
+ch2.rb:  4.203125   0.234375   4.437500 (  4.797802)
+ch3.rb:  0.242188   0.000000   0.242188 (  0.268957)
+
+仮想ノードが1000の場合
+             user     system      total        real
+ch2.rb: 44.007812   0.109375  44.117188 (105.273196)
+ch3.rb:  0.375000   0.015625   0.390625 (  0.408695)
+}}}