分散システムのパーティショニングを考察してみる

分散システムの良書が出てましたので、それの6章をベースにパーティショニングを考えてみます。
Designing Data-Intensive Applications

用語の意味

• パーティションとはデータを複数に分割すること
• シャーディングとも呼ばれる
  
• data(record, row or document)は必ず一つのパーティションに属する
  (技術的にはvertical partitioningというのもあるけど、そこはこの本では考慮していない模様)
  

主な目的はscalability  

• shared nothingの環境において、それぞれのノードにパーティションを分散配置することでscalabilityを確保
• 処理が特定のパーティションに閉じるクエリであればノードを追加すればするだけscalabilityは高まる
  
• ただlarge, comprexクエリ（特定のパーティションに閉じない処理という意味で良いと思う）は各ノードでパラレルに実行できる余地はあるが難しい
    (難しいというのは実装とかいろんな意味を含めてだと思う)

歴史

• 1980年代にTeradata(DWH用途), NonStopSQL(OLTP用途, HP社製)が出た。(Teradataは今も現役,NonStopSQLも現役と思うが使っている人は聞いたことない)
• そのあと(2010年頃)にNoSQL, Hadoopが出てきた
  

実装

• パーティショニングするモチベーションとして、パーティショニングすることでデータとクエリの負荷を各ノードに均等に分割したい
• 各ノードに均等に分割できていない状態(skewed)があるとスケーラビリティを確保できない
• skewedを回避するシンプルな方法として各ノードにランダムにデータを書くという戦略がある
   ただし、これだとどのノードにデータがあるのかわからないので、検索するときに全ノードを探索する必要があり、ありえない
   （実用ではNoSQLとか使うときに、どのカラムでパーティショニングする設計は依然として重要）
  

パーティショニングの行い方

• KeyRangeで行う方法とHashで行う方法がある
  

KeyRangeでパーティショニングする

• 特定のKey(RDBのカラムと同じ意味)のデータの範囲を元にパーティショニングする
  

Pros

• レンジスキャンができる
  

Cons

• データを均等に分割するのが難しい
   特にはじめにデータを入れるときにデータのレンジをデータベースとしてはわからないので分割のやりようがない
   そのために人間が事前にデータの範囲を定義して、この範囲であればこのノードにデータを配置するみたいなことをやったりする
  
• データを挿入するときにskewが発生する可能性がある timestampのように特定の順序でデータを挿入していくケース
  (このケースはRDBでもindexの特定のリーフに更新が集中して、ロック待ちで遅くなるケース)
  IoTみたいなユースケースだと[sensor id]+[timestamp]をkeyにして回避したりする
  

KeyRangeを使う製品

• BigTable
• HBase (BigTableのOSSクローン)
• RethinkDB
• MongoDB (MongoDBはhashパーティショニングも可能)

Hashでパーティショニングする

• Keyの値をhash関数にかけた結果を元にパーティショニングする
• 各パーティションはハッシュ値の範囲をもち、その範囲内のデータがそれぞれ格納される　

Pros

• データもクエリロードも均等に分割できる
  

Cons

• レンジスキャンが非効率 (そもそもレンジスキャンができない製品もたくさんある。voldemort, riak, couchbase ...)
  

Hashを使う製品

KeyRangeよりHashの方が多い
- Cassandra
- MongoDB
- Voldemort
- Riak
- Couchbase
- dynamodb

Hashでのパーティショニングの変形

• compound indexであり、１つ目のkeyをhashでパーティションにング、２つ目のkeyでソートをして並べる
• IoTでの[sensor id]+[timestamp]みたいなケースや[user_id]+[timestamp]みたいなケースで威力を発揮する
• Cassandraはこの形式を採用している #### 例外
• 同じkeyでread/writeしたらskewは発生する
  
• これはunusual caseではあるが、ありえない話でもない。SNSでfollowerをたくさん持つ有名人が何かしたときに有名人IDに対してread/writeが集中するとか。
  
• このようなskewを回避する方法はデータベースでは今はない。回避するとしたらアプリケーションで頑張る。例えばkeyにランダム値を付与するとかして。

セカンダリインデックス

• パーティションに使うKeyではなく別のカラムで検索をする方法
  
• そもそも実装していない製品(HBaseとか)も多い
• パーティショニングをするデータベースでセカンダリインデックスを使う方法としてdocument-based partitioningとterm-based partitioningがある

document-based partitioning

• 各パーティションでdocument -> primary key値というセカンダリインデックスを保持する形式
• このセカンダリインデックスは他のパーティションにどのようなデータが入っているかは関知しない
  

Pros

• writeが特定のパーティションに閉じる
  

Cons

• readは全てのパーティションのセカンダリインデックスを検索する必要がある
  

document-basedを使う製品

• ElasticSearch
• MongoDB
• Cassandra

term-based

• 全てのパーティションにまたがってglobalなセカンダリインデックスを保持する形式  
• 一方でdocument-basedのように各パーティションで作られるインデックスはlocal indexという
• globalなセカンダリインデックスを特定のホストにおくわけにはいかないので、このインデックス自体もKeyRangeやHashのパーティショニングで分散される
  

Pros

• readが特定のパーティションに閉じる
  

Cons

• セカンダリインデックス自体がKeyRangeやHashでパーティショニングされるので、KeyRange, HashのConsを引き継ぐ
• writeで別のパーティションに書き込む必要がある
   特に実データとセカンダリインデックスのデータを同期して書き込む場合はdistributed transactionをしないといけない
   で、distributed transactionをしている製品などこの世になく、asynchronousでセカンダリインデックスを更新している。
  

term-basedを使う製品

• dynamodb
• riak
• Oracle data warehouse

リバランシング

• 負荷をあるノードから別のノードに移すことをリバランシングという
  

リバランシングに期待すること

• リバランシング後に負荷が各ノードで均等になっている
• リバランシング中でもread/writeできる
• 動かす必要のないデータは動かさない。network, disk I/Oを少なくする目的で
  

実現方法

Fixed number of partitions

• パーティション数が固定の形式。つまり環境構築時にパーティション数を決めたら、それ以降変わることがない
• 固定のため一般的にはノード数よりも大分多い数をパーティション数として定義する
• ノードが追加されたらそれぞれの既存ノードからちょうど良い数のパーティションを移動する  
• パーティションの移動はすぐに終わるわけではないので、移動中でも移動元のパーティションはread/writeを受け付ける
  

Pros

• 動的なパーティションの分割やマージがないので性能は均一化しやすい
  

Cons

• 将来的な拡張も見越してパーティション数決めないといけないが、パーティション数多すぎると管理コストが増える
  (パーティション数多すぎて性能がすごい落ちるとかあまり経験ないけど)
  

Fixed number of partitionsを使う製品

• Riak
• ElasticSearch
• Couchbase
• Voldemort
  

Dynamic Partitioning

• 特定のデータ量を超えた場合にパーティションを分割する方式。また、特定のデータ量以下になった場合に２つのパーティションをマージする方式。
• KeyRangeでパーティションする製品にはよく使われる（事前にkeyの範囲がわからないのに固定のパーティションを決めるのは難しいため）
  

Pros

• 適切なパーティション数が維持できるため、余計な負荷がかからない
  

Cons

• データが少ない状態だと、パーティションが１つしかない状態も発生しうる
  KeyRangeパーティションのConsと一緒。事前にkeyの範囲を定義することで回避
  

Dynamic Partitioningを使う製品

• HBase
• RethinkDB
  

Partitioning proportionally to nodes

• パーティション数をノード数に応じて決める形式
• Fixed number of partitionsやDynamic Partitioningはノード数を考慮することはなかった

- ノードが追加されるとランダムに何個かのパーティションを選びスプリットして新ノードにスプリットした片割れを移動する

Pros

• 他の２方式のようなConsを持たない
  

Cons

• ランダムに何個かのパーティションを選んでスプリットするので各パーティションでデータが均等化しない
  

Partitioning proportionally to nodesを使う製品

• cassandra
• ketama
  

Automatic or Manual

• manualがおすすめ
• automaticの場合、勝手にrebalanceが起こり負荷が上昇してその結果負荷が上昇したノードを他のノードが故障ノードと誤検知することもある
  (負荷の調整も含めてautomaticにやってほしいが、そこまで賢い製品はないと思ってる)
  

Request Routing

• リバランスが起きてパーティションの配置が変わった場合にクライアントリクエストは正しいパーティションにどうやってアクセスするの？
• ３つの方式がある
• クライアントは任意のノードにアクセスして、そのノードがパーティションを持っているノードにアクセスする方式（各ノードがルーティング情報を持っている）
  Cassandraはこれ
• クライアントからのリクエストを受け付けるproxyがいて、そのproxyがパーティションを持っているノードにアクセスする方式（proxyがルーティング情報を持っている）
  MongoDBはこれ
• クライアントがパーティションを持っているノードに直接アクセスする方式(クライアントがルーティング情報を持っている)
  HBaseはこれ
• 実装としてはzookeeperに依存することが多い。zookeeperに各パーティションとノードのマッピング情報をもつ
• cassandraとかriakは違いgossipプロトコルでちょっとずつマッピング情報を各ノードに反映していく