Vector Clocks

大雑把な意訳、訳しにくい箇所は英文のまま転載します。
http://docs.basho.com/riak/1.3.2/references/appendices/concepts/Vector-Clocks/

Overview

どのノードでもあらゆるリクエストを受け入れることができ、各リクエストに全てのノードが参加する必要とするわけではないということは、values のバージョンが最新かをたどる方法が必要となります。これには Vector Clock が役割を持ちます。

新しい value が Riak に格納されると、その最初のバージョンを確立して Vector Clock でタグ付けされます。それぞれの更新時においては、下記に記載する条件で object の 2 つのバージョンを比較して、Vector Clock を拡張します。

オブジェクトは他方の直接の子孫であるかどうか
オブジェクトは共通の親の子孫であるかどうか
Whether the objects are unrelated in recent heritage.

この識別を使用すると、Riak は同期していないデータを自動的に修復するか、クライアントにアプリケーションで指定した方法で修正させる機会を提供します。

Siblings

Riak が格納されている Object の正規のバージョンを解決できないときに Siblings が生成されます。bucket's properties 上の "allow_mult" に "true " を設定した場合は、下記に記載する 3 つのシナリオによって単一の Object に siblings を生成するでしょう。

同時書き込み: クライアントからの同時に生じた 2 つの書き込みが同じ Vector Clock を持っていると、Riak は格納する Object を決めることができず、Object に 2 つの sibling を与えます。これらの書き込みは、同じノードあるいは異なるノードで発生するかもしれません。
古い VectorClock: いくつかのクライアントが古い Vector Clock を使用して書き込む場合があります。これはクライアントが書き込む前に対象 object の最新 Vector Clock を読み込むシナリオです。読み込み書き込みサイクルの間に異なるクライアントが書き込むことによって、この状況が生じるかもしれません。古い Vector Clock で書き込むことによって sibling が生成されるでしょう。もし古い Vector Clock で書き込みを習慣的に行なうと、絶えず sibling を生成するでしょう。
Missing Vector Clock: 存在している Object に Vector Clock を指定せずに書き込む場合があります。これは "curl" のようなクライアントを使用して "X-Riak-Vclock" ヘッダーを指定するのを忘れた場合に発生します。

Riak uses siblings because it is impossible to order events with respect to time in a distributed system, this means they must be ordered causally. "allow_mult" が true の場合は、Riak は発生した conflict を解決しないでしょう。発生した sibling から 1 つの選択するか、違う Object に置き換える必要があります。

# allow_mult を true に設定した bucket を作成します
$ curl -v -XPUT -H "Content-Type: application/json" -d '{"props":{"allow_mult":true}}' http://127.0.0.1:8098/riak/kitchen
> PUT /riak/kitchen HTTP/1.1
> User-Agent: curl/7.19.7 (x86_64-redhat-linux-gnu) libcurl/7.19.7 NSS/3.14.0.0 zlib/1.2.3 libidn/1.18 libssh2/1.4.2
> Host: 127.0.0.1:8098
> Accept: */*
> Content-Type: application/json
> Content-Length: 29
>
< HTTP/1.1 204 No Content
< Vary: Accept-Encoding
< Server: MochiWeb/1.1 WebMachine/1.10.0 (never breaks eye contact)
< Date: Thu, 04 Jul 2013 09:44:11 GMT
< Content-Type: application/json
< Content-Length: 0
<

# object を作成します
$ curl -v -X POST -H "Content-Type: application/json" -d '{"dishes":11}' http://127.0.0.1:8098/riak/kitchen/sink?returnbody=true
> POST /riak/kitchen/sink?returnbody=true HTTP/1.1
> User-Agent: curl/7.19.7 (x86_64-redhat-linux-gnu) libcurl/7.19.7 NSS/3.14.0.0 zlib/1.2.3 libidn/1.18 libssh2/1.4.2
> Host: 127.0.0.1:8098
> Accept: */*
> Content-Type: application/json
> Content-Length: 13
>
< HTTP/1.1 200 OK
< X-Riak-Vclock: a85hYGBgzGDKBVIc1ze/yQg8qH40gymRMY+VgfGA52m+LAA=
< Vary: Accept-Encoding
< Server: MochiWeb/1.1 WebMachine/1.10.0 (never breaks eye contact)
< Link: </riak/kitchen>; rel="up"
< Last-Modified: Thu, 04 Jul 2013 09:44:33 GMT
< ETag: "6FTuzD45wjEgvNOpKMlT8w"
< Date: Thu, 04 Jul 2013 09:44:33 GMT
< Content-Type: application/json
< Content-Length: 13
<
* Connection #0 to host 127.0.0.1 left intact
* Closing connection #0
{"dishes":11}

# Vector Clock を指定せずに object を更新することで sibling  を作成します
$ curl -v -XPUT -H "Content-Type: application/json" -d '{"dishes":9}' http://127.0.0.1:8098/riak/kitchen/sink?returnbody=true
> PUT /riak/kitchen/sink?returnbody=true HTTP/1.1
> User-Agent: curl/7.19.7 (x86_64-redhat-linux-gnu) libcurl/7.19.7 NSS/3.14.0.0 zlib/1.2.3 libidn/1.18 libssh2/1.4.2
> Host: 127.0.0.1:8098
> Accept: */*
> Content-Type: application/json
> Content-Length: 12
>
< HTTP/1.1 300 Multiple Choices
< X-Riak-Vclock: a85hYGBgzGDKBVIc1ze/yQg8qH40gymRKY+VQeCA52m+LAA=
< Vary: Accept-Encoding
< Server: MochiWeb/1.1 WebMachine/1.10.0 (never breaks eye contact)
< Last-Modified: Thu, 04 Jul 2013 09:44:48 GMT
< ETag: "5nhfALuggOCcAHlLH60m6B"
< Date: Thu, 04 Jul 2013 09:44:48 GMT
< Content-Type: multipart/mixed; boundary=EJcMmbfshYJ04SJH7YVgfdjE2h9
< Content-Length: 412
<

--EJcMmbfshYJ04SJH7YVgfdjE2h9
Content-Type: application/json
Link: </riak/kitchen>; rel="up"
Etag: 3gMc93QhPKRSRtuLwcGeBz
Last-Modified: Thu, 04 Jul 2013 09:44:48 GMT

{"dishes":9}
--EJcMmbfshYJ04SJH7YVgfdjE2h9
Content-Type: application/json
Link: </riak/kitchen>; rel="up"
Etag: 6FTuzD45wjEgvNOpKMlT8w
Last-Modified: Thu, 04 Jul 2013 09:44:33 GMT

{"dishes":11}
--EJcMmbfshYJ04SJH7YVgfdjE2h9--

V-Tag

このポイントは複数のレスポンスが返ることです。sibling を持っている Object を取得すると、2 つの選択をすることができます。sibling のリストを取得する方法を記載します。このレスポンスは、フォーマットは同じですが出力内容は異なるはずです。

# 全ての siblings の vtag リストを取得する
$ curl http://127.0.0.1:8098/riak/kitchen/sink
Siblings:
3gMc93QhPKRSRtuLwcGeBz
6FTuzD45wjEgvNOpKMlT8w

複数の values を持った Object を読み込むと、"300 Multiple Choices" レスポンスと、全ての sibling の "vtag" リストが出力されます。"vtag" は Object の 1 つの sibling を参照することができます。Object の URL に "vtag" パラメータを付けることによって、指定した sibling を取得できます。

# vtag=6FTuzD45wjEgvNOpKMlT8w の sibling を取得する
$ curl http://127.0.0.1:8098/riak/kitchen/sink?vtag=6FTuzD45wjEgvNOpKMlT8w
{"dishes":9}

"multipart/mixed" ヘッダーを Accept すると、全ての siblings を 1 回のリクエストで取得できます。

# 全ての siblings を取得する
$ curl http://127.0.0.1:8098/riak/kitchen/sink -H "Accept: multipart/mixed"

--7id5AcJe2ChS6GptGQ2G6x59PcW
Content-Type: application/json
Link: </riak/kitchen>; rel="up"
Etag: 3gMc93QhPKRSRtuLwcGeBz
Last-Modified: Thu, 04 Jul 2013 09:44:48 GMT

{"dishes":9}
--7id5AcJe2ChS6GptGQ2G6x59PcW
Content-Type: application/json
Link: </riak/kitchen>; rel="up"
Etag: 6FTuzD45wjEgvNOpKMlT8w
Last-Modified: Thu, 04 Jul 2013 09:44:33 GMT

{"dishes":11}
--7id5AcJe2ChS6GptGQ2G6x59PcW--

Conflict Resolution

"allow_mult" を true にすると、conflict が生じた場合に正しい value を決めなければいけません。アプリケーションでは、自動的に修復するか、ユーザーに conflict した Object を提示します。Riak で適切な value に更新するためには、最新の Vector Clock が必要になるでしょう。"{'dishes':11}" が正しい value だと仮定すると、次のように更新します。

# 最新の Vector Clock のために Object を読み込みます
$ curl -v http://127.0.0.1:8098/riak/kitchen/sink
> GET /riak/kitchen/sink HTTP/1.1
> User-Agent: curl/7.19.7 (x86_64-redhat-linux-gnu) libcurl/7.19.7 NSS/3.14.0.0 zlib/1.2.3 libidn/1.18 libssh2/1.4.2
> Host: 127.0.0.1:8098
> Accept: */*
>
< HTTP/1.1 300 Multiple Choices
< X-Riak-Vclock: a85hYGBgzGDKBVIc1ze/yQg8qH40gymRKY+VQeCA52m+LAA=
< Vary: Accept, Accept-Encoding
< Server: MochiWeb/1.1 WebMachine/1.10.0 (never breaks eye contact)
< Last-Modified: Thu, 04 Jul 2013 09:44:48 GMT
< ETag: "5nhfALuggOCcAHlLH60m6B"
< Date: Thu, 04 Jul 2013 11:21:55 GMT
< Content-Type: text/plain
< Content-Length: 56
<
Siblings:
3gMc93QhPKRSRtuLwcGeBz
6FTuzD45wjEgvNOpKMlT8w

# Vector Clock を指定して正しい value に更新します
$ curl -v -XPUT -H "Content-Type: application/json" -d '{"dishes":11}' -H "X-Riak-Vclock: a85hYGBgzGDKBVIc1ze/yQg8qH40gymRKY+VQeCA52m+LAA=" http://127.0.0.1:8098/riak/kitchen/sink?returnbody=true
> PUT /riak/kitchen/sink?returnbody=true HTTP/1.1
> User-Agent: curl/7.19.7 (x86_64-redhat-linux-gnu) libcurl/7.19.7 NSS/3.14.0.0 zlib/1.2.3 libidn/1.18 libssh2/1.4.2
> Host: 127.0.0.1:8098
> Accept: */*
> Content-Type: application/json
> X-Riak-Vclock: a85hYGBgzGDKBVIc1ze/yQg8qH40gymRKY+VQeCA52m+LAA=
> Content-Length: 13
>
< HTTP/1.1 200 OK
< X-Riak-Vclock: a85hYGBgzGDKBVIc1ze/yQg8qH40gymROY+VoeK652m+LAA=
< Vary: Accept-Encoding
< Server: MochiWeb/1.1 WebMachine/1.10.0 (never breaks eye contact)
< Link: </riak/kitchen>; rel="up"
< Last-Modified: Thu, 04 Jul 2013 11:24:40 GMT
< ETag: "2FSsoEDUHPt67UbcjnNwBr"
< Date: Thu, 04 Jul 2013 11:24:40 GMT
< Content-Type: application/json
< Content-Length: 13
<
{"dishes":11}

Concurrent conflict resolution

conflicts を自動的に解決しようとしたら、2 つのクライアントが同時に解決することで新しい conflicts を生成して終わる可能性に注意するべきです。To avoid a pathological divergence you should be sure to limit the number of reconciliations and fail once that limit has been exceeded.

Sibling Explosion

Sibling explosion occurs when an object rapidly collects siblings without being reconciled. これは無数の問題をもたらします。Having an enormous object in your node can cause reads of that object to crash the entire node. Other issues are increased cluster latency as the object is replicated and out of memory errors.

Vector Clock Explosion

sibling explosion の他にも、短い期間で 1 つの Object に対して大量の更新を行なうと、Vector Clock は過度に大きく成長します。1 つの Object に対して大量に更新を行なうことは推奨できません。Vector Clock が過度に大きく成長するのを防ぐために、Vector Clock の切り込みレベルを調整できます。

How does last_write_wins affect resolution?

"allow_mult" を "false" に設定することと "last_write_wins" を "true" に設定することは同じ振る舞いをするように見えますが、そこには微妙な違いがあります。

たとえ両方の設定は 1 つの value をクライアントに戻すとしても、"allow_mult=false" は解決するために Vector Clock を使用しますが、"last_write_wins=true" は最新バージョンを決めるために timestamp を読むだけです。システム内部では、"allow_mult=false" は同時書き込みやネットワーク分断によって siblings が存在することを許しますが、"last_write_wins=true" は後の timestamp を持っている value で上書きするだけです。

あなたが sibling の作成を好まない場合は、"allow_mult=false" があなたに最新の value を取得させ、ネットワーク分断時も優雅に処理を行ないます。しかしながら、頻繁に keys が再書き込みされる場合や、新しい value が古い value と依存していないケースにおいては、"last_write_wins=true" はより良いパフォーマンスを提供します。あたなが "last_write_wins=true" を使いたいかもしれないケースは、セッションストレージや、更新がなく挿入のみを行なう場合です。

注意: bucket の properties に "allow_mult=true" と "last_write_wins=true" を併用することは、未定義な振る舞いをするので使用してはいけません。

Vector Clock Pruning

Riak は bucket ごとに設定できる 4 つのパラメータに基づいて、過度な成長を防ぐために Vector Clock の切り詰めを定期的に行ないます。

small_vclock
big_vclock
young_vclock
old_vclock

"small_vclock" と "big_vclock" パラメータは Vector Clock リストの長さに言及します。もしリストの長さが "small_vclock" より小さい場合は、切り詰められません。もしリストの長さが "big_clock" より大きい場合は、切り詰められます。

"young_vclock" と "old_vclock" パラメータは各 Vector Clock に格納されている timestamp に言及します。リストの長さが "small_vclock" と "big_vclock" の間にある場合に timestamp を確認します。timestamp が "young_vclock" より若い場合は、切り詰められません。timestamp が "old_vclock" より古い場合は、切り詰められます。

Client vs Vnode Vector Clocks

Riak 1.0 より前のバージョンでは、全ての PUT リクエストはクライアント ID とともに投稿されなければいけませんでした。The jobs of coordinating a put request and incrementing the associated vector clock were handled by the vnode which received the request. クライアント ID が投稿されなかった場合は、Vector Clock をインクリメントするためにランダムに生成したクライアント ID を使用していました。This resulted in potentially unbounded vector clock growth with poorly-behaved clients.

Riak 1.0 の時点で、Vector Clock は vnodes が内部のカウンターと識別子を使用することによって直接管理されます。これは Vector Clock の成長を抑制させますが、書き込みに若干の遅延を追加されます。

More Information

Vector Clock に関する情報:

Vector Clocks on Wikipedia
Why Vector Clocks are Easy
Why Vector Clocks are Hard
The vector clocks used in Riak are based on the work of Leslie Lamport.

End

基本的には Vector Clock を使用した方が良いけど、ログを格納するだけの用途だったら "last_write_wins=true" で高速化をはかるってのも良いね。