Riak Coreを読む、chash編

todo : あとで、モジュールの構成図でも作るか....

# Riak Coreを読む

Riak Coreを読んでいる。chash編である。

## chashを読む

https://github.com/basho/riak_core/blob/develop/src/chash.erl

Consistent Hashingだそうだ。一貫したハッシュということらしい。

## 型とレコード

```erlang
-type chash() :: {num_partitions(), [node_entry()]}.
```

さてこれが、chash型。パーティションの数と、node_entryのリストかな?

```erlang
%% A Node is the unique identifier for the owner of a given partition.
%% An Erlang Pid works well here, but the chash module allows it to
%% be any term.
-type chash_node() :: term().
```

パーティションのオーナーにとっての、識別子であるというわけね。pidは良いんだけど、型な何でもいいんよってことか。

```erlang
%% Indices into the ring, used as keys for object location, are binary
%% representations of 160-bit integers.
-type index() :: <<_:160>>.
-type index_as_int() :: integer().
```

リング内の、オブジェクトの位置のための、キーとして、型。

```erlang
-type node_entry() :: {index_as_int(), chash_node()}.
-type num_partitions() :: pos_integer().
```

node_entryは、インデックスと、chash_nodeの型。num_partitionsは正の整数なんだな。

## テストを読む

今回は、なんとなくテストから読んで行く。


### update_test()

```erlang
update_test() ->
    Node = 'old@host', NewNode = 'new@host',
    
    % Create a fresh ring...
    CHash = chash:fresh(5, Node),
    GetNthIndex = fun(N, {_, Nodes}) -> {Index, _} = lists:nth(N, Nodes), Index end,
    
    % Test update...
    FirstIndex = GetNthIndex(1, CHash),
    ThirdIndex = GetNthIndex(3, CHash),
    {5, [{_, NewNode}, {_, Node}, {_, Node}, {_, Node}, {_, Node}, {_, Node}]} = update(FirstIndex, NewNode, CHash),
    {5, [{_, Node}, {_, Node}, {_, NewNode}, {_, Node}, {_, Node}, {_, Node}]} = update(ThirdIndex, NewNode, CHash).
```


一応、ここで、使われている関数specとかを、調べておく

```erlang 
-spec fresh(NumPartitions :: num_partitions(), SeedNode :: chash_node()) -> chash().
```

freshは、フレッシュなchashを作るわけですねー。パーティションの数と、シードノードを取るんでつね。

```erlang
-spec update(IndexAsInt :: index_as_int(), Name :: chash_node(), CHash :: chash()) -> chash().
```

まぁ、updateするんですよ。

んで、テストは、chashのインデックスの位置にある、ノードが更新されているかどうかのテストなんでつな。

### max_n_test

```erlang 
-spec max_n(N :: integer(), CHash :: chash()) -> integer().

...

max_n_test() ->
    CHash = chash:fresh(8, the_node),
    ?assertEqual(1, max_n(1,CHash)),
    ?assertEqual(8, max_n(11,CHash)).
```

はい、まぁ、nがパーティションの数を超えないようにするやつでつね。

### simple_size_test

```erlang
simple_size_test() ->
    ?assertEqual(8, length(chash:nodes(chash:fresh(8,the_node)))).
```

とくに、コメントしなくても、分かるな。まぁ、nodeのリストを取っての、長さのテスト。

### successors_length_test

```erlang 
successors_length_test() ->
    ?assertEqual(8, length(chash:successors(chash:key_of(0),
                                            chash:fresh(8,the_node)))).
```

順列があってねってことかね。

### inverse_pred_test

```erlang
inverse_pred_test() ->
    CHash = chash:fresh(8,the_node),
    S = [I || {I,_} <- chash:successors(chash:key_of(4),CHash)],
    P = [I || {I,_} <- chash:predecessors(chash:key_of(4),CHash)],
    ?assertEqual(S,lists:reverse(P)).
````

まぁ、順列があって、successorsとpredecessorsは順方向か、逆方向ってことかね。

### merge_test

```erlang
merge_test() ->
    CHashA = chash:fresh(8,node_one),
    CHashB = chash:update(0,node_one,chash:fresh(8,node_two)),
    CHash = chash:merge_rings(CHashA,CHashB),
    ?assertEqual(node_one,chash:lookup(0,CHash)).
```

マージするんよ。

## 実装を読む

さて、実装を読んでいくよ。
### contains_name
```erlang
%% @doc Return true if named Node owns any partitions in the ring, else false.
-spec contains_name(Name :: chash_node(), CHash :: chash()) -> boolean().
contains_name(Name, CHash) ->
    {_NumPartitions, Nodes} = CHash,
    [X || {_,X} <- Nodes, X == Name] =/= [].
```

chashに、名前が含まれているかを調べるんよ。まぁ、リスト内包表記でやってる。

### freshとring_increment

```erlang
-define(RINGTOP, trunc(math:pow(2,160)-1)).  % SHA-1 space

...

%% @doc Create a brand new ring.  The size and seednode are specified;
%%      initially all partitions are owned by the seednode.  If NumPartitions
%%      is not much larger than the intended eventual number of
%%       participating nodes, then performance will suffer.
-spec fresh(NumPartitions :: num_partitions(), SeedNode :: chash_node()) -> chash().
fresh(NumPartitions, SeedNode) ->
    Inc = ring_increment(NumPartitions),
    {NumPartitions, [{IndexAsInt, SeedNode} ||
           IndexAsInt <- lists:seq(0,(?RINGTOP-1),Inc)]}.

...

%% @doc Return increment between ring indexes given
%% the number of ring partitions.
-spec ring_increment(NumPartitions :: pos_integer()) -> pos_integer().
ring_increment(NumPartitions) ->
    ?RINGTOP div NumPartitions.
```

なるほど。SHA1だから、160ビット。んで、2の160乗。それを、パーティションで分割して、それをインクリメントの値として、インデックスの値を決定しているのね。

### lookup

```erlang
%% @doc Find the Node that owns the partition identified by IndexAsInt.
-spec lookup(IndexAsInt :: index_as_int(), CHash :: chash()) -> chash_node().
lookup(IndexAsInt, CHash) ->
    {_NumPartitions, Nodes} = CHash,
    {IndexAsInt, X} = proplists:lookup(IndexAsInt, Nodes),
    X.
```

これも、簡単だな。インデックスから取ってくるだけでしょ?

### key_of

```erlang
-ifndef(old_hash).
sha(Bin) ->
    crypto:hash(sha, Bin).
-else.
sha(Bin) ->
    crypto:sha(Bin).
-endif.

...
 
%% @doc Given any term used to name an object, produce that object's key
%%      into the ring.  Two names with the same SHA-1 hash value are
%%      considered the same name.
-spec key_of(ObjectName :: term()) -> index().
key_of(ObjectName) ->    
    sha(term_to_binary(ObjectName)).
```

まぁ、ハッシュ関数読んでるだけだな。

### members

```erlang
%% @doc Return all Nodes that own any partitions in the ring.
-spec members(CHash :: chash()) -> [chash_node()].
members(CHash) ->
    {_NumPartitions, Nodes} = CHash,
    lists:usort([X || {_Idx,X} <- Nodes]).
```

ノードのメンバー全部のリストをつくる。

### merge_ring

```erlang
%% @doc Return a randomized merge of two rings.
%%      If multiple nodes are actively claiming nodes in the same
%%      time period, churn will occur.  Be prepared to live with it.
-spec merge_rings(CHashA :: chash(), CHashB :: chash()) -> chash().
merge_rings(CHashA,CHashB) ->
    {NumPartitions, NodesA} = CHashA,
    {NumPartitions, NodesB} = CHashB,
    {NumPartitions, [{I,random_node(A,B)} || 
           {{I,A},{I,B}} <- lists:zip(NodesA,NodesB)]}.
```

ringをマージする。前提としてパーティションの数が同じのchash同士をマージする。なんか、ランダムにnodeを選択する。

### next_index

```erlang
%% @doc Given the integer representation of a chash key,
%%      return the next ring index integer value.
-spec next_index(IntegerKey :: integer(), CHash :: chash()) -> index_as_int().
next_index(IntegerKey, {NumPartitions, _}) ->
        Inc = ring_increment(NumPartitions),
        (((IntegerKey div Inc) + 1) rem NumPartitions) * Inc.
```

次のインデックスを返す関数。

### nodes

```erlang
%% @doc Return the entire set of NodeEntries in the ring.
-spec nodes(CHash :: chash()) -> [node_entry()].
nodes(CHash) ->
    {_NumPartitions, Nodes} = CHash,
    Nodes.
```

簡単。

### ordered_from

```erlang
%% @doc Given an object key, return all NodeEntries in order starting at Index.
-spec ordered_from(Index :: index(), CHash :: chash()) -> [node_entry()].
ordered_from(Index, {NumPartitions, Nodes}) ->
    <<IndexAsInt:160/integer>> = Index,
    Inc = ring_increment(NumPartitions),
    {A, B} = lists:split((IndexAsInt div Inc)+1, Nodes),
    B ++ A.
```

ほぉー。ringだから、なんか、グルグル周るイメージがして良いな。

### predecessorsとsuccessors

```erlang
%% @doc Given an object key, return all NodeEntries in reverse order
%%      starting at Index.
-spec predecessors(Index :: index() | index_as_int(), CHash :: chash()) -> [node_entry()].
predecessors(Index, CHash) ->
    {NumPartitions, _Nodes} = CHash,
    predecessors(Index, CHash, NumPartitions).
%% @doc Given an object key, return the next N NodeEntries in reverse order
%%      starting at Index.
-spec predecessors(Index :: index() | index_as_int(), CHash :: chash(), N :: integer())
                  -> [node_entry()].
predecessors(Index, CHash, N) when is_integer(Index) ->
    predecessors(<<Index:160/integer>>, CHash, N);
predecessors(Index, CHash, N) ->
    Num = max_n(N, CHash),
    {Res, _} = lists:split(Num, lists:reverse(ordered_from(Index,CHash))),
    Res.

...


%% @doc Given an object key, return all NodeEntries in order starting at Index.
-spec successors(Index :: index(), CHash :: chash()) -> [node_entry()].
successors(Index, CHash) ->
    {NumPartitions, _Nodes} = CHash,
    successors(Index, CHash, NumPartitions).

%% @doc Given an object key, return the next N NodeEntries in order
%%      starting at Index.
-spec successors(Index :: index(), CHash :: chash(), N :: integer())
                -> [node_entry()].
successors(Index, CHash, N) ->
    Num = max_n(N, CHash),
    Ordered = ordered_from(Index, CHash),
    {NumPartitions, _Nodes} = CHash,
    if Num =:= NumPartitions ->
	    Ordered;
       true ->
	    {Res, _} = lists:split(Num, Ordered),
	    Res
    end.
```

### size

```erlang
%% @doc Return the number of partitions in the ring.
-spec size(CHash :: chash()) -> integer().
size(CHash) ->
    {_NumPartitions,Nodes} = CHash,
    length(Nodes).
```

実装は簡単。

### update

```erlang
%% @doc Make the partition beginning at IndexAsInt owned by Name'd node.
-spec update(IndexAsInt :: index_as_int(), Name :: chash_node(), CHash :: chash())
            -> chash().
update(IndexAsInt, Name, CHash) ->
    {NumPartitions, Nodes} = CHash,
    NewNodes = lists:keyreplace(IndexAsInt, 1, Nodes, {IndexAsInt, Name}),
    {NumPartitions, NewNodes}.
```

簡単でつね。