cockroach style range management

gistfile1.txt

-- contains all meta1 range data
root range
[
meta1_0000 : {meta1_0000..meta1_1000, 1.1.1.1, 1.1.1.2, 1.1.1.3}
meta1_1001 : {meta1_1001..meta1_2000, 1.1.2.1, 1.1.2.2, 1.1.2.3}
...
meta1_N001 : {meta1_N001..meta1_(N+1)000, 1.1.N.1, 1.1.N.2, 1.1.N.3}
]

-- constains partial meta2 range
meta1 range (key = meta1_0000)
[
meta2_0000 : {meta2_0000..meta2_0100,...}
meta2_0101 : {meta2_0101..meta2_0200,...}
...
meta2_1000 : {meta2_0901..meta2_1000,...}
]

-- contains partial key range
meta2 range (key = meta2_0101)
[
key_0101_0000 : {key_0101_0000..key_0101_1000,...}
...
key_0200_0000 : {key_0200_0000..key_0200_1000,...}
]

eg)
key_0103_0999を探す場合
"key_0103_0999"を含むrangeオブジェクトが、"key_0103_0999"に対応する値がどのノードにあるか、を保持しているため、そのrangeオブジェクトを見つける必要がある。
key名に一定のルールを設けることで、"key_0103_0999"というkeyからそのrangeオブジェクトを保持しているkeyは"key_0103_0000"である、というふうにわかる。
次に"key_0103_0000"に対応するrangeオブジェクトがどのノードにあるか、を保持しているmeta2 rangeを探す。同様にkey名の対応関係から対応するkey名は"meta2_0101"である、とわかる。
"meta2_0101"に対応するrangeオブジェクトがどこにあるかも同様に"meta1_0000"にあるとわかる。
meta1は必ずroot rangeに含まれており、root rangeはgossipに乗って通知されるため、"meta1_0000"に対応するrangeオブジェクトをroot rangeのノード情報を使って取ってくることができる。
次にmeta1_0000に含まれるノード情報から"meta2_0101"に対応するrangeオブジェクトを取ってくることで、"key_0103_0000"に対応するrangeオブジェクトを取ってくることができる。
同様にして、"key_0103_0999"に対応するデータが取得できるというわけ。

key_0103_0999 =(key変換)> key_0103_0000 =(key変換)> meta2_0101 =(key変換)> meta2_0101 =(key変換)> meta1_0000 =(key変換)> root

range１つが管理するkey-valueのバイト数の合計が一定を越えるとsplitされる。
splitされる際にはそれぞれ自分が含まれる親のrangeと自分自身を書き換えることになる。書き換えの結果、親のrangeがあふれた場合にはさらにsplitがさかのぼって適用されていく。