1台に入らないデータを分ける
データ分割（パーティショニング、シャーディングとも呼びます）とは、大量のデータを、キーを使って複数の機械に振り分けることです。1台に入らないデータも、機械ごとに一部ずつ持てば扱えます。
会員が3000万人いる通販サイトで、「ケンさんの会員情報はどの機械にあるか」を、どう素早く見つけるのでしょうか。
このレッスンのゴール
メモ
キーを使って、データを複数の機械に振り分けられます。
キーワード
| ことば | いみ | れい |
|---|---|---|
| シャード | 分けたデータの一片と、それを持つ機械 | |
| ハッシュ関数 | キーを、決まった数に変える手順 | |
| 剰余 | 割り算の余り | 823 % 3 は 1 |
| コンシステントハッシュ | 輪の上で持ち主を決め、台数が変わっても動きを少なくする方法 | |
| ホットスポット | 一部の機械にだけ仕事が集まること |
学生が入力するセルは、このプレビューでは空白です。
キーを数に変え、余りで機械を決める
ハッシュ関数は、キーを決まった数に変えます。同じキーはいつも同じ数になります。
機械が3台なら、その数を3で割った剰余（余り）が、0、1、2のどれかになります。余りが、キーを置く機械の番号です。これで、探すときも同じ計算をするだけで、置き場所が分かります。
キーの置き場所を計算する
# 教材用のハッシュ: キーの文字コードを足した数です。
def simple_hash(key):
total = 0
for ch in key:
total = total + ord(ch)
return total
for key in ["user:ami", "user:ken", "user:rei", "user:sho"]:
number = simple_hash(key)
print(key, number, "3台なら", number % 3, "4台なら", number % 4)
# 4台目を足すと、何個のキーの置き場所が変わるでしょうか。
例: 4台目を足すと動くキー
| キー | 数 | 3台のとき | 4台のとき | 動いたか |
|---|---|---|---|---|
| user:ami | 816 | 0 | 0 | 動かない |
| user:ken | 823 | 1 | 3 | 動いた |
| user:rei | 825 | 0 | 1 | 動いた |
| user:sho | 835 | 1 | 3 | 動いた |
学生が入力するセルは、このプレビューでは空白です。
823を3で割った余りを計算する
echo $((823 % 3))ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
台数が4台のときの余りを計算する
echo $((823 % 4))ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
コンシステントハッシュは、輪で持ち主を決める
台数が変わるたびに多くのキーが動くのは、困ります。そこで、0から99までの数を輪にして、機械の位置を輪の上に置きます。
キーの位置から時計回りに進み、最初に出会った機械が持ち主です。機械を1台足しても、動くのは、その前の機械から新しい機械までの間にあるキーだけです。
例: 輪の上の持ち主
| キーの位置 | 時計回りで最初の機械 | 機械Dを65に足したあと |
|---|---|---|
| 35 | B（位置50） | B |
| 51 | C（位置80） | D（位置65） |
| 60 | C（位置80） | D（位置65） |
| 90 | A（輪を一周して位置20） | A |
学生が入力するセルは、このプレビューでは空白です。
輪の上でキーの持ち主を探す
# 輪の上に、機械の位置を並べます。キーは、時計回りで最初に出会う機械のものです。
ring = [[20, "A"], [50, "B"], [80, "C"]]
def owner(ring, position):
for entry in ring:
if entry[0] >= position:
return entry[1]
return ring[0][1]
for position in [35, 50, 90]:
print("位置", position, "の持ち主:", owner(ring, position))
# ring に [65, "D"] を足して、位置 60 の持ち主を調べてみましょう。
小さなクライアント v を作る
v() ( printf '%s\r\n' "$*" | nc -w 1 valkey 6379 )ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
ケンさんを機械1の持ち物として入れる
v SET shard1:user:ken 823ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
持ち主の機械1に、あるか尋ねる
v EXISTS shard1:user:kenここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
違う機械3に、あるか尋ねる
v EXISTS shard3:user:kenここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
ラボでは、名前の先頭で3台に分ける
ラボのValkeyは1台です。そこで、キーの先頭に shard1: のような名前をつけて、3台に分けたつもりで試します。持ち主の機械にだけ、キーがあります。
本物のValkeyのクラスタは、キーを16384個のスロットに分けて、スロットごとに持ち主の機械を決めています。
よくある間違い
注意
分割と複製は同じものだと考えがちです。複製は同じデータの写しを増やし、分割は別々のデータを別々の機械に置きます。実際のシステムは、分けたうえで、それぞれに写しを持たせます。
偏りがあると、1台だけが忙しくなる
キーが偏ると、一部の機械にだけ仕事が集まります。これをホットスポットと呼びます。人気商品のキーだけが、何万回も読まれる場合などです。
偏りを減らすには、キーを散らす、ホットなキーの写しを増やす、といった工夫を重ねます。