Context Navigation

Consistent Hasing を Ruby で試す

Consistent Hashing は、複数のコンピュータ(ノード)にレコードを分散するのに使われるアルゴリズムです。

Consistent Hashing を試すではプログラムサンプルが Perl で書かれていますが、それを Ruby に書き直してみました。それだけではなんなので、二分探索を用いてキーの検索の高速化も試みています。

プログラムの説明については、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)

Download in other formats:

Plain Text