cockroach's distribute strategy

gistfile1.txt

cockroach's stragegy: 
rangeはsplitでしか増えない
splitの時、新しくできたrangeのreplicaは同じ(raftで元々のrangeのレプリカ全部に対してsplitが実行されるので、自然な挙動)

splitされたrangeはrebalanceされる
それ以外に、zone config(複数データセンターに配置する設定)に違反しているrangeがrebalanceされる

rebalanceの結果は全ノードにpropagateしないとリクエストをどこにroutingしていいかわからないのできついが、cockroachはどうするつもりか
=>
key - rangeの対応関係を保存するためのrangeが２段階あり、それは通常のrangeのように幾つかのレプリカに保存されている。
key='hoge'を含むrangeがどこのレプリカにあるか、はkey='\0meta2hoge'を含むrangeが存在するノードに記録されている。そのrangeがどのレプリカに保存されているかもわからないが、それはfirst rangeという、gossipで全ノードに通知される特別なrangeの中に含まれていることが保証されている。そのレプリカのアドレスは当然わかるため、'\0meta1hoge'を含むrangeの場所をfirst rangeをもつノードに問い合わせて、判明したノードに'\0meta2hoge'を含むrangeの場所を問い合わせることで'hoge'を含むrangeの場所を知ることができる。一度問い合わせたrangeとkeyの範囲はキャッシュされるため次回以降の問い合わせは高速化される。

rangeのsplitされる閾値をXbyte, １つのrangeを表すrangedescriptorのサイズをYbyteとすると、meta1はmath.floor(X / Y)個のrangeを持つことができる。
meta2のrangeそれぞれもmath.floor(X / Y)個のrangeを持てるため、最大データ量はX * (math.floor(X / Y) ^ 2) byteとなるだろう。
階層構造を増やすことによって^2の部分は増えていくため、保存できる最大データ量を指数関数的に増やすことができるのはうまいやり方だと思う。

従って、rebalanceのときは
1. rangeをsplitして、meta2の対応するrangeをもつノードのデータを書き換える。１つのkey-value pairがなくなって新しいkey-value pairが２つできるだろう。
2. rebalanceが完了した後、rebalanceされたrangeのノード情報を書き換える。
一つのrangeだけを書き換えることでrebalanceの際のマッピングされているノード情報の更新が完了する。

rebalanceするとmetadataが変わるためrange cacheをinvalidateしなくてはいけないだろう.
lookupが失敗したか、gossipで通知されたとかをトリガーにするのがいいのだろうか