# データパーティショニング ## 定義 データパーティショニング（Data Partitioning）とは、リレーショナル・データベースのリレーション（テーブル）のタプルを複数のディスク・ノードに分散配置する手法の総称である。[[David DeWitt]] と [[Jim Gray]] が [[@1992__CACM__Parallel Database Systems The Future of High Performance Database Systems]]（CACM 1992）において、並列データベースにおけるパーティション並列化の基盤として体系化した。3 つの基本手法——ラウンドロビン・ハッシュ・レンジ——を定義し、各手法がスキャン性能・連想アクセス性能・データ歪み耐性のトレードオフにおいて異なる特性を持つことを示した。 ## 3 手法の比較 | 手法 | 原理 | 最適アクセスパターン | 弱点 | |---|---|---|---| | **ラウンドロビン** | タプルを順番に各ディスクへ均等配分 | 全スキャン（I/O 帯域最大化） | 連想アクセス（特定値の検索）で全ディスクを走査 | | **ハッシュ** | 属性のハッシュ値でディスクを決定 | 連想アクセス（等値結合・ポイントルックアップ） | データをランダム化し範囲検索に不向き | | **レンジ** | 属性値の連続範囲を各ディスクに割当 | 範囲クエリ・連想アクセス・クラスタリング | データ歪み（一部パーティションに集中）リスク | ハッシュとラウンドロビンは歪みに強いが、レンジパーティショニングではデータ分布が偏ると特定ノードが高負荷になる（**data skew**）。Bubba はアクセス頻度（temperature）を重みとするハイブリッドレンジパーティショニングで歪みを軽減した [6]。 ## 横断的知見 - **ハッシュパーティショニングは分散 KVS・NoSQL の普遍的手法に収斂した**: DeWitt/Gray が 1992 年に「ハッシュは連想アクセスに最適」と定式化した原則は、Amazon Dynamo（2007）の一貫性ハッシュリング・Cassandra（2010）のパーティショナー・Google Bigtable の tablet 範囲分割の設計原則と直接対応する。Dynamo は「データをランダム化する」というハッシュの性質を意図的に利用し、特定キーへの集中アクセスを防止した。(Source: [[@1992__CACM__Parallel Database Systems The Future of High Performance Database Systems]], [[@2007__SOSP__Dynamo - Amazon's Highly Available Key-value Store]], [[@2010__SIGOPS_OSR__Cassandra - A Decentralized Structured Storage System]]) - **[[一貫性ハッシュ法]]はラウンドロビン/ハッシュ/レンジのどれに当たるか**: 一貫性ハッシュ（consistent hashing）はハッシュリング上で各ノードが担当範囲を持つため、**ハッシュとレンジの融合**に位置づけられる。ノード追加・削除時に再配置が最小化される点は DeWitt/Gray の分類には含まれていなかった（1992 年時点ではノードの動的追加を考慮した設計手法が未成熟）。(Source: [[@1992__CACM__Parallel Database Systems The Future of High Performance Database Systems]]) - **パーティション数の最適化は現代クラウド DB でも継続課題**: DeWitt/Gray は「パーティション数が増えるとスキャンは改善するが、連想スキャンは起動コストとのクロスオーバーで悪化しうる [6, 11]」と述べた。Snowflake のマイクロパーティション・BigQuery のクラスタリングも同様のトレードオフを内包しており、自動最適化の研究が続く。(Source: [[@1992__CACM__Parallel Database Systems The Future of High Performance Database Systems]]) ## 未解決の問い - **多次元パーティショニング**: DeWitt/Gray は緯度・経度の 2 次元パーティショニングの例を挙げ「追加研究が必要」と述べた。現代の地理空間 DB・ベクトル DB はどのパーティション手法を採用しているか - **オンラインデータ再編成**: DeWitt/Gray が未解決課題とした「テラバイト DB のパーティション変更をオンラインで実行する」は現代の分散 DB でどう解決されているか - **スキューに対する自動対処**: Bubba の temperature-based パーティショニングの後継として、ML ベースの動的リパーティショニングはどこまで実用化されているか ## 関連 - ソース: [[@1992__CACM__Parallel Database Systems The Future of High Performance Database Systems]] - 概念: [[並列データベース]] / [[シェアードナッシング]] / [[一貫性ハッシュ法]] / [[分散ストレージ]] / [[専用データベースシステム]] - エンティティ: [[David DeWitt]] / [[Jim Gray]] / [[Teradata]] / [[University of Wisconsin]] ## 出典 - [[@1992__CACM__Parallel Database Systems The Future of High Performance Database Systems]]（ラウンドロビン・ハッシュ・レンジの 3 手法を並列 DB のコア技術として体系化）