概要

cluster-specの内容のまとめ
随時追記していくと思います。
誤訳・認識ミスもあるかもしれません。
（）の部分は筆者のコメントです。
著作者から指摘があった場合は速やかに削除します。

Redis Cluster Specification

specへようこそ。ここではクラスタのアルゴリズムやデザイン情報を見れます。
このドキュメントはなるべく最新の実装に合わせています。

Main properties and rationales of the design

Redis Cluster goals

クラスタの達成したいことは以下です。（重要度順）

High performance and linear scalability up to 1000 nodes. プロキシなく非同期レプリケーション、マージ操作に性能的な負担がないこと。
可能な限り書き込みができること、多数派クラスタに接続されているクライアントに対しては出来る限り書き込みを許容する。少数派クラスタに接続してしまった場合は書き込みがロストするか書き込めないか。
可用性: 多数派クラスタは生き続ける。複数スレーブへの反映も可能。

このドキュメントはRedis 3.0以上に対応しています。

Implemented subset

クラスタも単一Keyに対するクエリは同じように使える。
複数Keyへのクエリは、全てが同じslotにいるなら操作可能
hash tagという機能を使うことで、むりやり同じNodeに押しこむことができる。
しかし、shardingなどの影響で、複数Keyの操作が常に成立するとは限らない。（同じslotに入れるからshardingしても問題ないのでは？）

クラスタの場合は複数DBをサポートしていない。そのため、スタンドアロン版のdatabase０のみ使える。

Clients and Servers roles in the Redis Cluster protocol

各ノードはデータの保持と各ノード間の状態確認を行う。
もしマスタが死んでたら自動で昇格する。
ノード間のやりとりはClusterBusと呼ばれるTCP BusでのBinaryProtocolで行われる。
各ノードは互いにやりとりしあう。
生存確認のpingを送りつつ、gossip protocolで共有する。
クラスタはManual failoverリクエストがユーザーから送られてきたら互いにやりとりして対応する。（adminでリクエストしろ）
ノードはproxyRequest形式でないので、ノードは -MOVEDや -ASKを返すため、クライアントはリダイレクトする。
なので、クライアントは各ノードの状態を知っていなくても大丈夫（ただしパフォーマンスを上げるため、ノードとslotを紐付けて管理するクライアントもある。）

Write safety

redisは非同期でノードへreplicationする。failoverしたノードの値が正になり、各ノードにコピーされる。
これは、マスタに書き込んだ後slaveに書き込まれる前にネットワーク障害などあるとデータが消えることを意味する。
しかし、もし分断された少数派の方であれば書き込みできなくなるので、問題はない。

redisはなるべく書き込みを許容する。大多数のマスタがある方は書き込みを許容する。
以下のシナリオは、書き込みロスの例

The following are examples of scenarios that lead to loss of acknowledged writes received in the majority partitions during failures:

書き込みがマスタに届き、replyを返す際にスレーブへの非同期コピーを行うので、届くことは保証されない。
もし書き込みがslaveにとどく前にマスタが死ぬとデータは失われる。
通常、クライアントにreplyを返すのと同時にslaveに複製するため、これはめったに起きないが、ありうる事象である。
以下のような場合。

（クラスタから）マスタが見つからない
あるスレーブがマスタに昇格する。
その後、（旧）マスタがクラスタに復帰する
（旧）マスタがslaveになる前に、クライアントが（旧）マスタに書き込みにいく。

旧マスタがslaveになるほんのわずかの間にの書き込みが、すぐにslaveとして新マスタのデータをコピーするためデータが消える。
これを満たすにはクライアントが旧マスタを見続けていることが必要。

NODE_TIMEOUTの間、多数のマスタから認識されなければそのマスタはフェイルオーバーの対象になるため、その時間までであればマスタは一つで書き込みはロストしない。
その時間を過ぎると、少数派のマスタへの書き込みはロストする。
しかし、少数派になった時点でredisは書き込みを拒否するため、ロストしうる時間はずっと短い。

Availability

クラスタは少数派と多数派に分けられるが、多数派とは、半数以上のマスタと、存在しないマスタのレプリカ全てを含む場合になる。分断が発生しても、NODE_TIMEOUTを過ぎると多数派はfailoverして書き込み可能になる。
これにより、いくつかのノードのcrashでも可用性を保てる設計になっている。

例えば、N個のマスタに一つずつslaveが付いている場合。
2つのノードが落ちた時のクラスタを維持できなくなる確率は1-(1/(N*2-1))になる。
5ノードであれば11.1%程度になる（1台死んで9台、そのうちスレーブがいないのは一台なので、1/9）

ちなみに、これらの障害に備えて、クラスタはスレーブ構成を最適化して冗長化に成功している。

Performance

redisは他ノードのデータを代わりに取得してくるようなproxyの役割はせず、正しいノードへのuriを返します。

このため、クライアントはどのノードがどのsubsetを持っているか把握し、正しいノードへ直接リクエストすることができるようになります。

非同期コピーのため、ノードは他のノードの返事をまたずに書き込みを完了します。（WAITを使わない限り。）

また、複数keyの操作は近くのKeyKeyのみなので、reshardingを行わない限りデータは動かない（ちょっと意味がわからない。。。同一slotでなければ拒否されるはずでは、、こんなふうに「CROSSSLOT Keys in request don't hash to the same slot」）

普通の操作は単一ノードのときと同等の性能です。リニアにスケールします。
ほんの少しの可用性と一貫性を犠牲にする代わりに、超ハイパフォーマンスを実現しているのです。

Why merge operations are avoided

クラスタは同じKeyのバージョンの衝突を避けている。それでは困る場合があることを知りつつ。
redisのデータはたいてい大きなものになる。数百の要素のlistなどもある。あるいはとても複雑な構成のものもある。merge作業は処理のボトルネックになるかもしれないし、多くのメモリを消費する。などなど。

クラスタはなるべく単一ノードのredisの挙動に近い形を維持している。

Overview of Redis Cluster main components

Keys distribution model

Key Spaceは16384 slotに分かれて保存されます。なので最大で16384ノードまで拡張できます。
（gossip Protocolの限界的に？）1000ノード以内が推奨ですが。

各ノードはslotのsubsetを持っています。
クラスタは、ノード間でslotの担当の移動がなければ安定している。（stableの意味によるが、reshardしている間も可用性はあったはず。。）
クラスタが安定しているとき、hash slotは一つのノードで管理される。（ただし、slaveに複製されるし、読み込みはslaveが許容すればスケールする）。

hash slotを決めるアルゴリズムはこんな形。

HASH_SLOT = CRC16(key) mod 16384

Keys hash tags

hash slotは一部例外があります。hash tagsです。
hashtagsは、複数のkeyを同じslotに入れるようになります。これによって、クラスタでも複数keyの操作ができます。

hashtagsの実装のため、hash slotは少し違う挙動をします。
もしkeyが"{...}"を含んでいたら、{から}までをhashtagとして、hashtagであれば同じslotに入れます。

例えば、

{user1000}.following と {user1000}.followers は、user1000でhashslot計算されるので、同じslotに入る。
foo{}{bar} だと、最初の{と}である空文字で計算される。
foo{{bar}}zap the substring {barとみなされる。
foo{bar}{zap} the substring bar とみなされる。
{}ではじまるKeyはbinaryを格納するときとかに重宝される（？）

rubyとCのサンプルコードはこんな感じ

Cluster nodes attributes

各ノードはda211946d0a440cf7921142108590cd07f9a0e1eのようなIDがふられる。
ノードはIDを設定ファイル（node.conf？）に保存し、adminがファイルを削除するか、CLUSTER RESETコマンドを用いない限り常にそのIDを利用する。

ノードIDはクラスタ内で一意になる。そのままのIDでIPの変更をしても、クラスタが勝手に調整してくれる。
ノードIDは互いの連携だけでなく、常にグローバルで一貫している。（？）
各ノードは以下の設定をもつ。まずはクラスタの設定で、ノード間で適宜調整する。
他には、サーバ同士の生存確認の状態とか。
各ノードは、互いのID、port、マスタ/スレーブのフラグ、最後のping到達時間、current configuration epoch of the node (後述)、hash slotの担当。
詳細はCLUSTER NODESに記載されています。
CLUSTER NODES commandはどのノードに投げても、クラスタの設定が取得できます。

以下は３つのマスタのクラスタに投げてみた例

The Cluster bus

各ノードは互いの通信用にもうひとつのTCPportを持っている。
これはクライアント用のport+10000で固定されている。
6379なら16379だ。
ノード間のやりとりはクラスタバスと呼ばれるbinary protocolで行われる。
詳細を知りたければコードを読むことです。

Cluster topology

各ノードは網目のように全てのノードで連絡している。
つまり、N-1のout/inのコネクションがある。
常に張りっぱなしだが、pingが長い間通らなければ一から貼り直す。

redisはgossip Protocolを使うため、メッセージ数が指数関数的に増えることにはならない。

まとめ

割とシンプルでわかりやすいですね。
ドキュメントは読みにくくないけど少し丁寧過ぎるように思いました。