redis-rb で ConsistentHashing の仮想ノード数を指定する

redis-rb では Sharding のアルゴリズムとしてコンシステント・ハッシュ法が使われています。
コンシステント・ハッシュ法でサーバごとのキーの偏りを減らす為の仮想ノードという仕組みがあるのですが、redis-rb を使う場合に仮想ノードの数をどうやって指定するのか調べてみました。

コンシステント・ハッシュ法や、仮想ノードについては以下の記事がとてもわかりやすかったです。

ConsistentHashing - コンシステント・ハッシュ法
http://www.hyuki.com/yukiwiki/wiki.cgi?ConsistentHashing

1時間でわからせたコンシステントハッシュで仮想ノードが必要な理由 - 西尾泰和のはてなダイアリー
 http://d.hatena.ne.jp/nishiohirokazu/20090430/1241075459

redis-rb での仮想ノード数

まずは redis-rb で仮想ノード数を指定している箇所を見てみます。

redis-rb(3.0.4) では Redis::HashRing クラスの @replicas という変数が仮想ノード数を保持しています。
この変数の値は、コンストラクタの第二引数 replicas で指定できるようです。

class Redis
  class HashRing

    POINTS_PER_SERVER = 160 # this is the default in libmemcached

    attr_reader :ring, :sorted_keys, :replicas, :nodes

    # nodes is a list of objects that have a proper to_s representation.
    # replicas indicates how many virtual points should be used pr. node,
    # replicas are required to improve the distribution.
    def initialize(nodes=[], replicas=POINTS_PER_SERVER)
      @replicas = replicas
      @ring = {}
      @nodes = []
      @sorted_keys = []
      nodes.each do |node|
        add_node(node)
      end
    end
・
・
・

デフォルトでは同クラスで定義されている定数 POINTS_PER_SERVER の値である 160 が使用されるようになっています。

同じく Redis::HashRing クラスの add_node メソッドを見ると、ノード追加時に @replicas の数だけ仮想ノードを作成し追加しています。

    # Adds a `node` to the hash ring (including a number of replicas).
    def add_node(node)
      @nodes << node
      @replicas.times do |i|
        key = Zlib.crc32("#{node.id}:#{i}")
        @ring[key] = node
        @sorted_keys << key
      end
      @sorted_keys.sort!
    end

仮想ノード数を確認してみる

以下のようなコードを書いて、本当に上記の数だけ仮想ノードが作成されているのかを確認してみます。

# -*- coding: utf-8 -*-

require 'redis'
require 'redis/distributed'

REDIS_HOSTS = [
  {url: "redis://192.0.2.1:6379/0", id: "redis-node1"},
  {url: "redis://192.0.2.1:6380/0", id: "redis-node2"},
  {url: "redis://192.0.2.1:6381/0", id: "redis-node3"},
]

redis = Redis::Distributed.new(REDIS_HOSTS)

p "node size:#{redis.nodes.size}"
p "replicas:#{redis.ring.replicas}"
p "sorted_keys size:#{redis.ring.sorted_keys.size}"

実行すると以下のように出力されました。

"node size:3"
"replicas:160"
"sorted_keys size:480"

先ほどコードを読んだ通り、ノード数に対して、@replicas の数だけ仮想ノードが作成されているようです。

仮想ノード数を変更する

それでは仮想ノード数を変更してみます。

Redis::HashRing クラスを使っているのは Redis::Distributed クラスです。
Redis::Distributed クラスでは、以下のようにコンストラクタで Redis::HashRing のインスタンスを生成していました。

class Redis
  class Distributed
・
・
・
    attr_reader :ring

    def initialize(node_configs, options = {})
      @tag = options.delete(:tag) || /^\{(.+?)\}/
      @default_options = options
      @ring = HashRing.new
      node_configs.each { |node_config| add_node(node_config) }
      @subscribed_node = nil
    end

これでは HashRing の第二引数を指定することができません。
アクセサも attr_reader で定義されているため、Distributed のインスタンス生成後に外部から HashRing インスタンスを設定することも出来ないようです。

どうしたものか、と思っていたところ、最近以下のようなコードがコミットされていました。

allow using a custom HashRing · 54f9084 · redis/redis-rb
https://github.com/redis/redis-rb/commit/54f9084c8dd8fbd7fa1a742be1b9a2fa849ded6d

コンストラクタ内で HashRing を生成している部分が以下のように変更されています。

@ring = options.delete(:ring) || HashRing.new

これで Distributed クラスのコンストラクタの引数に、仮想ノード数を変更した HashRing インスタンスを渡す事ができます。
3.0.4 では上記の変更は含まれていなかったので、以下のようにモンキーパッチとして適用して使ってみました。

# -*- coding: utf-8 -*-

require 'redis'
require 'redis/distributed'

class Redis
  class Distributed
    def initialize(node_configs, options = {})
      @tag = options.delete(:tag) || /^\{(.+?)\}/
      @ring = options.delete(:ring) || HashRing.new
      @default_options = options
      node_configs.each { |node_config| add_node(node_config) }
      @subscribed_node = nil
    end
  end
end

REDIS_HOSTS = [
  {url: "redis://192.0.2.1:6379/0", id: "redis-node1"},
  {url: "redis://192.0.2.1:6380/0", id: "redis-node2"},
  {url: "redis://192.0.2.1:6381/0", id: "redis-node3"},
]

redis = Redis::Distributed.new(REDIS_HOSTS, ring: Redis::HashRing.new([], 360))

p "node size:#{redis.nodes.size}"
p "replicas:#{redis.ring.replicas}"
p "sorted_keys size:#{redis.ring.sorted_keys.size}"

実行結果を見ると以下のように仮想ノード数が変更されていることが確認できます。

"node size:3"
"replicas:360"
"sorted_keys size:1080"

既に master ブランチには変更が反映されているので、次のバージョンでは上のようなモンキーパッチは不要になりそうです。

試してみる

実際にデフォルトである 160 と、360(適当)を指定した場合とで、キーの分散状況が変わるかどうかを試してみました。
上で使用していたコードに、以下のようなテストデータを投入する処理を追記してそれぞれ実行しています。

KEYS = ('a'..'z').map {|c| c * 3}

# ランダムな値を Redis に設定する
KEYS.each { |key|
  redis.set(key, "key:#{key}")
}

実行後にキーの数を調べてみたところ、以下のようになっていました。
当然ですがそれぞれのスクリプトの実行前には Redis サーバ上の全てのキーを一旦消去しています。

デフォルト(160)の場合

$ redis-cli -p 6379 KEYS '*'
1) "mmm"
2) "ccc"
3) "yyy"
4) "www"
5) "fff"
6) "vvv"
$ redis-cli -p 6380 KEYS '*'
 1) "nnn"
 2) "kkk"
 3) "zzz"
 4) "rrr"
 5) "ggg"
 6) "bbb"
 7) "aaa"
 8) "xxx"
 9) "ooo"
10) "ttt"
11) "uuu"
12) "jjj"
13) "iii"
$ redis-cli -p 6381 KEYS '*'
1) "qqq"
2) "sss"
3) "lll"
4) "ppp"
5) "hhh"
6) "ddd"
7) "eee"

360 に変更した場合

$ redis-cli -p 6379 KEYS '*'
1) "mmm"
2) "ooo"
3) "ccc"
4) "yyy"
5) "qqq"
6) "iii"
7) "www"
8) "uuu"
9) "ggg"
$ redis-cli -p 6380 KEYS '*'
1) "rrr"
2) "aaa"
3) "fff"
4) "eee"
5) "zzz"
6) "xxx"
7) "ttt"
8) "jjj"
$ redis-cli -p 6381 KEYS '*'
1) "bbb"
2) "nnn"
3) "sss"
4) "vvv"
5) "kkk"
6) "lll"
7) "ppp"
8) "hhh"
9) "ddd"