- キー・バリュー型データ構造はデータ駆動システムの中核構成要素であり、ワークロードやハードウェア条件によって性能差が大きく開くことがある
- 物理構造は、データ配置、探索用メタデータ、保存・検索のアルゴリズムに分けられ、アクセスメソッド、データコンテナ、検索構造とも呼ばれる
- ワークロードはポイントクエリ、範囲クエリ、挿入、削除、更新の組み合わせで表され、メモリや永続ストレージの容量とコストも設計要件となる
- B+-treeは読み取りと範囲クエリに強い一方、挿入・更新が増えるとリーフノードの再構成が負担になり、LSM-treeはバッファリングとマージによって大量の挿入を処理する
- データ移動がボトルネックになる環境では、新しいアプリケーション、ハードウェアの変化、データ増加に合わせて既存の構造を選ぶか、新しい構造を設計する必要がある
キー・バリュー型データ構造が解決する問題
- キー・バリュー型データ構造はデータ集約型アプリケーションで広く使われており、キー・バリューモデルの汎用性から多くのシステムの基盤になっている
- 1つのキーは1つの値にマッピングされるが、同じ値が複数のキーに関連付けられることはある
- 値の意味はアプリケーションによって異なる
- リレーショナルデータベースのレコードである場合がある
- Pandas DataFrameである場合がある
- NoSQLシステムでアプリケーションがパースして利用するフィールド集合である場合がある
- ソーシャルネットワークデータを扱うシステムでは、画像や動画のような大きなオブジェクトへの参照を含む場合がある
物理構成と適用範囲
- 物理的には、キー・バリュー型データ構造は3つの要素で構成される
- 特定のレイアウトで保存されたデータ
- データ探索を支援する任意のメタデータ
- 保存と検索の操作を支えるアルゴリズム
- データ構造は、データシステム、オペレーティングシステム、ファイルシステム、コンパイラ、ネットワークシステムでさまざまな形で使われる
- 本書の例は主に大規模データシステムと補助記憶装置を中心にしているが、分析と設計の方法はインメモリシステムにも適用される
- この分析は、メモリ・ストレージ階層が2段階以上ある環境に合わせたものになっている
ワークロードとコストが設計を左右する
- アプリケーションやワークロードは、キー・バリュー操作の組み合わせとして表せる
-
ポイントクエリ
-
範囲クエリ
- 挿入
- 削除
- 更新
- メモリと永続ストレージに必要な容量およびコストも、アプリケーション要件を構成する
- システムの種類によって、最適化すべきデータ構造は異なる
- ファイルシステムは、頻繁な更新に最適化されたデータ構造でファイルのメタデータと内容を管理する
- コンパイラは変数のライフサイクルの間、hash mapで変数を管理し、プログラム全体の形をabstract syntax treeで表現する
- ネットワーク機器では、ルーティングテーブルを効率的に保存しアクセスするために特化したデータ構造が必要になる
B+-treeとLSM-treeの対照的な選択
- B+-treeは、挿入や更新が少なくポイントクエリ・範囲クエリが多いワークロードで、読み取りコストと書き込みコストのバランスを取るためによく使われる
- 高いノードファンアウトは、ルートからリーフへ移動する際に必要な補助メモリアクセスを減らし、上位レベルはより高速なメモリ階層にキャッシュされる
- すべてのキーをリーフノードにソートして保持し、リーフノードを連結リストでつないで範囲クエリを支える
- 挿入や更新が増えると、リーフノードの再構成や分割が必要になり、性能上のボトルネックになり得る
- LSM-treeは、多数の挿入があるワークロードのために別のアプローチを用いる
- すべての更新を共通のメモリバッファに入れる
- バッファがいっぱいになるとディスクへフラッシュする
- バッファが積み上がると、より大きなソート済みデータコレクションへマージする
- 更新はout-of-placeポリシーで処理され、同じキーを持つキー・バリューペアが構造内に複数存在することがある
- 特定キーの現在値は、最も新しく挿入されたキー・バリューペアが持つ
適応型データ構造
- ワークロードを事前に予測してデータ構造を設計する方法だけでなく、実行中に段階的に理想的な形へ近づいていくデータ構造も扱う
- 元来の設計におけるB+-treeとLSM-treeは、すべてのポイントクエリまたは範囲クエリに答えるため、ディスク常駐ノード内にソート順を強制する
- 適応型データ構造は、1つ以上の未ソートノードから始め、機会が生じたときに段階的にソートできる
- database crackingは、到着するクエリのアクセスパターンを使い、基盤データを継続的かつ増分的に物理再構成する
- 目的は将来のクエリ性能を改善することにある
ハードウェア階層とメモリウォール
- ハードウェアの発展は、データ構造設計に新たな課題と機会を生み出す
- ストレージ階層では、下位段階ほど低価格でより多くの保存領域を提供するがアクセス遅延は大きく、プロセッサに近い上位段階ほど高速だが小さく、バイト当たりのコストが高い
- 特定アプリケーションのボトルネックとなる階層は、アプリケーションデータのサイズと各階層の記憶容量によって異なる
- B+-treeはもともとファンアウトを最大化してディスクアクセスを減らそうとしたが、メモリ容量が大きくなり、データがRAMや不揮発性補助メモリに収まるようになると、トレードオフは大きく変化する
- インメモリB+-treeは、小さなファンアウトで最もよい性能を示す
- **メモリウォール（memory wall）**は、プロセッサ速度とオフチップメモリ速度の間の差が広がっていく傾向を指す
- 2000年代初頭以降、オペレーティングシステムとデータ管理システムは、キャッシュメモリの利用を最適化するよう再設計されてきた
設計空間とガイドライン
- データ構造設計の選択肢の空間を整理し、アプリケーションの目標とワークロードに合う構造を選ぶ方法を扱う
- ハードウェアとデータの性質は変化し続けるため、データ構造設計にも継続的な革新が必要である
- 整理された設計空間とガイドラインは、既存のデータ構造から最も適したものを選ぶ、または特定ワークロードに合う新しいデータ構造を設計するために使われる
1件のコメント
Hacker News のコメント
まだざっと目を通した程度だが、これは巨大な領域を扱った非常に優れた調査資料だ
単にデータ構造を列挙するだけでなく、アプリケーションでデータ構造を作ったり使ったりする際に考慮すべき要素を頭の中で体系化する助けになる
この本の著者の一人は、この分野の研究室を運営している
最適なデータ構造設計を支援するすばらしいツールもある: http://daslab.seas.harvard.edu/datacalculator/
このテーマについて、さらにおすすめの資料が知りたい
論文はすばらしいし、Martin Klepmann の Designing Data-Intensive Applications も知っているが、その本はデータ構造というよりデータベース寄りだ
ある種の分析用データを格納する構造を設計するなら非常に重要な、構造体の配列と配列の構造体の対比が抜けている
つまり議論はしているが、構造体の配列／配列の構造体という用語では説明していないということだ
1冊買いたいが、Amazon では100ドルする
著者も損をし、読者も損をする壊れた構造だ
目次が必要だ
ページのヘッダーとフッターを無視するよう言っても同じで、最近の水準はずっと良くなっていると思っていた