Storage Partitioning
Shardingとも呼ばれ、それぞれのデータの断片(各record,row,document)が厳密に1Partitionに属するもので、目的としては大量のデータに対応できるようにScalabilityを強化するため.
データをPartition分割することにより、それぞれのNodeは自身のPartitionに対してqueryを実行できるため分散処理をさせることが可能になる.
PartitionとReplicationは併用される.
Types of partitioning
大量のデータが存在しており、Partitioningが均等になっていない場合、skew(一部のPartitionに多くのデータやQueryが集中している状態)が発生する.
この問題を解決するためにも均等にPartitioningされるように実装する必要がある.
不均等な高負荷が集中しているPartitionはHotSpotと呼ばれる.
Key-Value Partitioning
Primary-KeyによりPartitionを割り当てる方法
Key-Range Partitioning
連続的なKeyRangeを各Partitionに割り当てる方法
- Key-Rangeは必ずしも均等になっている必要はなく、データの分布が均等になるようにKey-Rangeを設定する
- ただ急激変化には弱くなる傾向にありそう
- Partitionの境界は管理者が選択することもできれば、Databaseに自動的に選択してもらうことも可能
- HBase, RethinkDB, MongoDB, Kafkaなどが採用している手法
Key-Hash Partitioning
skewやhotspotのリスクを避けるために、多くの分散データストアはキーに対するPartitionを決定する際にhash関数を用いる
- Partitioningの観点からすると、使用するHash関数は暗号として強力である必要はない
- Cassandra, MongoDB: MD5
- Voldemort: Fowler-Noll-Vo関数
- Keyに対するHash関数が決まれば、それぞれのPartitionにhash値の範囲を割り当て、それぞれのKeyを対応するHash値が範囲に入っているPartitionに保存されるようにする
Secondary indexでの partition
PartitioningされたDataSourceは、Primary-Keyのみを扱うのであれば、シンプルだがSecondary-Indexを扱う場合、複雑になる.
Document-Based Partitioning
Document-Based Partitioningでは、Secondary-Indexを各Partitionごとに構築する(ローカルインデックスとも呼ばれる).
- 各PartitionのSecondary-Indexは完全に分離されている
- 書き込みの際には、他のPartitionを気にしなくてよい
- Secondary-Indexにてレコードを検索したい場合、すべてのPartitionに対してQueryを実行する必要がある(スキャッタ/ギャザリング)
- Secondary-Indexに対する読み取り処理はscatter/gatheringによって高負荷になる可能性がある
- query実行を並列で実行した場合でも、scatter/gatheringはテイルレイテンシの増幅の影響を受けるため高負荷になる
語-Based Partitioning
こちらでは、各Partitionごとに個別のSecondary-Indexを持たせるのではなく、
すべてのPartitionのデータをカバーするグローバルインデックスを構築することも可能.
- 全てのPartitionの赤い車はIndexの
color:redは以下に存在する-
a ~ rまでの文字で始まる色: Partition0 -
s ~ zまでの文字で始まる色: Partition1
-
- 車の種類に対するIndex
-
a ~ f: Partition0 -
h ~ z: Partition1
-
- 読み込みについては全てのPartitionを参照する必要がないため高速になる
- 書き込みについては、低速で複雑になる
Re-Balancing
運用開始して時間が経つにつれて、databaseの中では以下のような変化が発生する.
以下のような変化に適応するために、負荷をクラスタ内にあるnodeから別のnodeへ移行するようにリバランスする必要がある.
- queryのthroughputが増大するため、CPUを追加して不可に対処する
- databaseのサイズが大きくなるため、保存のためにdiskやRAMを追加
- machineに障害が発生し、他のmachineがそのmachineが受け持っていた処理を肩代わりすることになる(F/O)
リバランシングは、以下のような最低限の要求を満たす必要が求められる
- リバランシングの終了後、負荷(Data Storage,読み書きのリクエスト)はクラスタ内のnode間で公平に分配されること
- リバランシングが行われている間、databaseは読み書きを受け付け続けなければならないこと
- node間を移動させるデータは必要最小限にとどめ、リバランシングが高速に行われ、networkやdiskのI/Oの負荷が最小になるようにすること
Re-Balancing戦略
Hashの余剰(Not Recommended)
余剰(mod N)による値でPartition分割することは可能だが、node数が変化するたびに割り当てnodeが変化するためリバランシングの負担が大きくなる.
そのため、この手法は避けるべき.
Partition数の固定
node数よりも多くのpartitionを作成し、1つのnodeに複数のpartitionを割り当てる手法
10個のnodeがcluster上で動作しているdatabaseがあるとする
- 最初の時点で1000 partitionsに分割する
- それぞれのnodeに100partitionsずつ分配する
- node0: partition0~99,
- node1: partition100~199
- node2: partition200~299
- ...
- node10: partition900~999
- 追加nodeがclusterに追加された場合、新しいnodeはpartitionの分散が均等になるまで既存の全てのnodeからpartitionを盗む
動的なPartitioning
key-rangeによるPartitioningは、partition数とpartitionの境界を固定するのは非常に不便になる可能性がある.
そのため、HBase, RethinkDBなどのkey-rangeによってPartitioningされたdatabaseは、Partitionを動的に作成する.
- Partitionサイズを最初に指定しておく
- 1つのpartitionのみ存在する場合に、partitionサイズを超えると2つのpartitionに分割される
- 分割後のpartitionのサイズはほぼ均等になる
- 2つのPartitionのみ存在する場合に、Partitionが何かしらの閾値より縮小するとそれを近接するpartitionにmergeされる
Node数に比例するPartitioning
Partition数をNode数に比例させる.つまり、nodeあたりのpartition数を固定する.
※これを利用するためには、partitionの境界をランダムに設定するためにhash-based partitioningが利用されている必要がある
Request Routing
適切なnodeへrequestをroutingするための方法
多くの分散データシステムは、このclusterのmetadataの追跡をZooKeeperのような独立した協調サービスに依存している.(Helix, Kafka, HBase, SolrCloud)
- 各nodeは自分自身をZooKeeperに登録
- ZooKeeperはPartitionからnodeへの信頼できるmappingを管理
- Routing LayerやPartitioningを認識するClientなどの他要素はZooKeeper内の情報を参照
- Partitionの所有者が変化したり、nodeの追加や削除が行われたりした場合には、ZooKeeperはRouting Layerに通知(Routing情報を最新に保つ)
Discussion