Consistent Hashing を試す

Consistent Hashing は、 複数のノードにレコードを分散させる方法として、 Amazon Dynamo や Cache::Memcached::Fast などで使われているアルゴリズムです。

この文章では、Perl で実際に Consistent Hashing を実装し、 その特徴を理解することを目的とします。

更新履歴

サーバー台数で割った余り (mod) を使用する

まず Consistent Hashing と比較するために、レコードに対して整数のハッシュ値を求め、 ハッシュ値をノード数で割った余り (mod) で、ノードを選択するという方法を書いてみます。

ここでは、ハッシュ値の算出に CRC (Cyclic Redundancy Check) を使用しています。 

use strict;
use String::CRC;
use Perl6::Say;

my @nodes = map { [$_] } @ARGV;

foreach my $key (('A'...'Z')) {
    my $index = crc($key, 32) % scalar @nodes;
    push @{ $nodes[$index] }, $key;
}

say join "\n", map { join ' ', @{ $_ }; } @nodes;

以上のプログラムの引数にノード (n1, n2, ..., n4) を与えて実行すると、 レコード (A, B, ..., Z) がそれぞれどのノードに配置されるかが表示されます。 

% perl mod.pl n1 n2 n3 n4
n1 D H L P T X
n2 A E I M Q U Y
n3 B F J N R V Z
n4 C G K O S W
%

このように、すべてのノードに一様にレコードが分散しているのがわかります。

余り (mod) を使用した方法の問題点

しかし、余り (mod) を使用した方法には、ノードの増減に弱いという問題があります。

ノード n4 を減らしてみます。 

% perl mod.pl n1 n2 n3
n1 B D G I N Q V X
n2 C E J L O R T W Y
n3 A F H K M P S U Z
%

本来であれば n4 にあったレコードが n1, n2, n3 へと移動すればすむはずですが、 B が n3 から n1 に、M が n2 から n3 へ移動するなど、 ノード間に必要の無いレコードの移動が発生していることがわかります。

たとえばノードが memcached のようなキャッシュサーバー、 レコードがキャッシュという場合、 このレコードの移動は、キャッシュのヒットミスにつながります。

Consistent Hashing

そこで Consistent Hashing の登場です。

Consistent Hashing ではレコードと同様にノードに対してもハッシュ値を計算します。 各レコードは、そのハッシュ値と近い値を持つノードに格納されます。

ここではリスト @circle に個々のノードを 

{ key => ハッシュ値, name => ノード名 }

という形で保持し、key の値で整列してます。 なおハッシュ値の算出には MD5 を使用しました。 

use strict;
use Digest::MD5 qw(md5_hex);
use Perl6::Say;

sub search {
    my ($list_ref, $key) = @_;

    my $max = scalar @{ $list_ref };
    foreach my $i (1...$max) {
        if ($list_ref->[$i-1]->{key} le $key && $key lt $list_ref->[$i]->{key}) {
            return $list_ref->[$i]->{name};
        }
    }
    return $list_ref->[0]->{name};
}

my %nodes = map { ($_ => [$_]) } @ARGV;

my @circle = sort {
    $a->{key} cmp $b->{key};
} map {
    my $name = $_;

    { key => md5_hex($name), name => $name };
} keys %nodes;

foreach my $rec (('A'...'Z')) {
    my $name = search([ @circle ], md5_hex($rec));
    push @{ $nodes{$name} }, $rec;
}

say join "\n", map { join ' ', @{ $nodes{$_} }; } sort keys %nodes;

以上のプログラムを、先程のものと同様の引数で実行してみます。 

% perl ch1.pl 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
%

n1 がほとんど使われていないなど、レコードが一様に分散していないのが気になりますが、 とりあえずノード n4 を減らしてみます。 

% perl ch1.pl 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 にあった G, I, L, R が n3 に移動し、 n1, n2 は前回とかわらない、ということが確認できます。

仮想ノード

レコードの分散にかたよりがあったのは、ハッシュ値がランダムだからです。 4 つのノードのハッシュ値を順に並べた際に、 となりあうハッシュ値同士の差が一定であることなんて保証できません。

そこで仮想ノードを導入します。 あるノードに対応するハッシュ値を複数算出し、 それを @circle 上に配置することで、レコードの分散を改善できます。

たとえランダムな値でも、十分にたくさんあれば、 となりあう値同士の差が一定に近づくはずです。 

use strict;
use Digest::MD5 qw(md5_hex);
use Perl6::Say;

sub search {
    my ($list_ref, $key) = @_;

    my $max = scalar @{ $list_ref };
    foreach my $i (1...$max) {
        if ($list_ref->[$i-1]->{key} le $key && $key lt $list_ref->[$i]->{key}) {
            return $list_ref->[$i]->{name};
        }
    }
    return $list_ref->[0]->{name};
}

my $number_of_replicants = shift;
my %nodes = map { ($_ => [$_]) } @ARGV;

my @circle = sort {
    $a->{key} cmp $b->{key};
} map {
    my $name = $_;

    map {
        my $suffix = $_ ? "_$_" : '';
        { key => md5_hex($name . $suffix), name => $name };
    } (0...$number_of_replicants);
} keys %nodes;

foreach my $rec (('A'...'Z')) {
    my $name = search([ @circle ], md5_hex($rec));
    push @{ $nodes{$name} }, $rec;
}

say join "\n", map { join ' ', @{ $nodes{$_} }; } sort keys %nodes;

実行時の最初の引数を $number_of_replicants とし、その数だけ 

{ key => md5_hex(n1),   name => n1 },
{ key => md5_hex(n1_1), name => n1 },
{ key => md5_hex(n1_2), name => n1 }, ...

というハッシュ値とノードのペアを @circle に追加します。

まず、仮想ノード数 0 で実行してみます。 結果は先程の ch1.pl と同じです。 

% perl ch2.pl 0 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
%

100 個ほど仮想ノードを追加してみます。 

% perl ch2.pl 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
%

ずいぶん分散が一様になっているのがわかります。 またノードをひとつ減らしてみます。 

% perl ch2.pl 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 の D が n1 へ移動し I, W が n2 へ移動、 G, J, R, X が n3 へと移動していることがわかります。 それ以外の必要の無い移動は発生していません。

参考