大規模データセットのためのアルゴリズムとデータ構造

この記事の歩き方

本書はデータがRAMに収まらない大規模な世界でアルゴリズムをどう設計すべきかを3部構成で解説している。各部の位置づけは次の通り。

• 第0部 はじめに（1章）：なぜ大規模データが現代のコンピューターシステムで問題になるのかという前提を共有する。
• 第1部 ハッシュベースのスケッチ（2〜5章）：データそのものを保持せず、ハッシュ値を使った確率的データ構造で「存在判定・頻度・カーディナリティー」といったクエリに少ないメモリで答える方法を扱う。
• 第2部 リアルタイム分析（6〜8章）：絶え間なく到着するストリーミングデータに対し、第一部の道具をどう組み合わせて使うかを扱う。
• 第3部 データベースと外部記憶（9〜11章）：データをディスクに置く前提で、ディスクとRAMの間の転送コストを最小化するインデックス・ソート手法を扱う。

第1部と第2部はメモリに焦点があり「いかに小さく保つか」を追求する。第3部はディスクに焦点があり「いかに転送回数を減らすか」を追求する。読み進める際には、自分が今どの制約と向き合っているのかを意識すると整理しやすい。

第0部 はじめに

1章 イントロダクション

この章のポイント

• 現代のアプリケーションはデータがRAMに収まらなくなると、計算ではなく入出力がボトルネックになる。
• RAMに収まらないときには、スワップ・ディスクI/O待ち・OOMといった現象が典型的に発生する。
• メモリ階層のトレードオフは構造的なものであり、容易に解消しない。
• だからこそ、入出力コストを意識したアルゴリズムとデータ構造の重要性が今後も高まっていく。

RAMに収まらない場合に起きること

スワップが使われる

RAMに載せきれないデータは、OSによってSSDやHDDのスワップ領域に退避される。SSDでもRAMより数十〜数百倍遅く、HDDではさらに遅い。

頻繁にRAMとディスクの間でデータを入れ替える状態に陥ると、CPUは待ち時間ばかりとなり、アプリケーションはほぼ進まなくなる。これをスラッシングと呼ぶ。

スラッシングが起こる仕組みは次の通り。

1. 物理メモリが逼迫すると、OSはあまり使われていないページをスワップ領域に退避させる。
2. 退避させたページがすぐにまた必要になり読み戻されると、代わりに別のページが追い出される。
3. 「追い出す→すぐ呼び戻す」のサイクルが連鎖的に発生する。
4. CPUの大半の時間がページフォルトの処理とディスクI/Oの待機に費やされ、本来の処理がほぼ進まなくなる。

ディスクI/Oがボトルネックになる

ディスクへの読み書きが大量に発生すると、I/O待ち（I/O Wait）が増える。CPU使用率は低いのに処理が進まないという特徴的な状態になる。

OOM（Out Of Memory）になることもある

LinuxにはOOM Killerという機構があり、スワップが少ない場合や使い切った場合に、メモリを大量に消費しているプロセスを強制終了することがある。

macOSやWindowsにはOOM Killerそのものは存在しないが、jetsam（macOS）やLow Memory Notification（Windows）のように、別の仕組みでメモリ枯渇時のプロセス制御が行われる。

大規模データが問題になる構造的な理由

大規模なデータが現代のコンピューターシステムにとって大きな問題となる理由は主に2つある。

1. CPUとメモリの速度差：CPUやマルチプロセッサの速度はメモリの速度よりもはるかに速いペースで向上してきた。
   • マルチプロセッサ：1つのシステム内に複数のCPU（プロセッサ）を搭載する構成・アーキテクチャを指す。
2. メモリ階層のトレードオフ：上位ほど高速で容量が小さく、下位ほど容量は大きいが遅いという階層構造によって、データを処理する速度が計算する速度を律速する。
   • 現代のメモリ階層は、CPUレジスタやキャッシュ（L1／L2／L3）→ RAM → SSD → HDDの順に並ぶ。
   • 上位ほど高速・低レイテンシー・広帯域だが容量は小さい。下位ほど速度・レイテンシー・帯域はいずれも悪化するが容量は増える。
   • 容量を求めるとどうしても遅い記憶階層を使わざるを得ず、CPUは計算を高速にこなせてもデータの供給が追いつかない。

これらの傾向はすぐに変わるものではないため、入出力コストとメモリの問題に対処するアルゴリズム・データ構造の重要性は今後も高まる。

第1部 ハッシュベースのスケッチ

第1部では、データそのものを保持せず、ハッシュ値を使ってクエリに答える「確率的データ構造」を扱う。多少の誤差を許容する代わりにメモリ消費を劇的に減らせる点が共通の狙いとなる。

• 2章：基礎となるハッシュテーブルと現代のハッシング技術を概観する。
• 3章：要素の存在判定を行うブルームフィルターと商フィルターを扱う。
• 4章：要素の出現頻度を推定するカウントミンスケッチを扱う。
• 5章：重複を除いた要素数を推定するハイパーログログを扱う。

2章 ハッシュテーブルと現代のハッシングについての概説

この章のポイント

• ハッシュテーブルはネットワーク・データシステム・ストレージソリューション・テキスト処理など、現代のあらゆるシステムに欠かせない。
• 状況に応じて、速度と消費メモリのバランスや、単純性と最悪ケースへの対処のバランスを調整できる。

3章 近似的なデータの存在判定：ブルームフィルターと商フィルター

この章のポイント

• ブルームフィルターは、データが「集合の中に含まれているか」をわずかなメモリで高速に判定できる確率的データ構造である。
• 通常のハッシュテーブルでは消費メモリが非常に大きくなる分散データベースやネットワークなどの分野で広く応用されている。
• メモリ容量を節約するために正確性とのトレードオフがあり、メモリ容量・偽陽性率・要素数・ハッシュ関数の数の間に関係がある。
• 商フィルターは線形探索を用いたコンパクトなハッシュテーブルに基づいており、ブルームフィルターと機能的に同等だが、削除・マージ・リサイズを効率的に行える空間的局所性の利点がある。
• 商フィルターは一様ランダムな挿入や必ず成功する検索においてブルームフィルターよりも高性能である。一様ランダムで検索に失敗するケースではブルームフィルターのほうが高性能となる。
• 商フィルターのパフォーマンスは負荷係数（低いほうがよい）に依存する。ブルームフィルターのパフォーマンスはハッシュ関数の数（少ないほうがよい）に依存する。

ブルームフィルターの仕組み

ブルームフィルターはビット配列と複数のハッシュ関数を組み合わせて要素の存在を判定する。要素そのものは保存せず、ハッシュ結果から得られるインデックスだけを使うため、極めて少ないメモリで動作する。

データ構造

• ビット配列（初期値はすべて0）
• 複数の独立したハッシュ関数（要素を受け取り、ビット配列のインデックスを返す）

要素の追加

1. 追加する要素にすべてのハッシュ関数を適用し、複数のインデックスを得る。
2. 得たインデックス位置のビットをすべて1にする。

存在判定

1. 判定したい要素にすべてのハッシュ関数を適用し、複数のインデックスを得る。
2. すべてのビットが1なら「含まれているかもしれない」と判定する。
3. 1つでも0があれば「含まれていない」と確定する。

具体例

長さ10のビット配列と2個のハッシュ関数を用意し、すべてのビットを0で初期化する。

[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

「apple」を追加する。ハッシュ値が3、7だった場合、インデックス3、7のビットを1にする。

[0, 0, 0, 1, 0, 0, 0, 1, 0, 0]

続けて「banana」を追加する。ハッシュ値が1、7だった場合、インデックス1、7のビットを1にする（7はすでに1）。

[0, 1, 0, 1, 0, 0, 0, 1, 0, 0]

ここで未登録の「cherry」を検索する。ハッシュ値が1、3だった場合、両方のビットが1のため「含まれているかもしれない」と判定される。しかし「cherry」は実際には登録していない。この現象を偽陽性と呼ぶ。

偽陽性は発生するが偽陰性は発生しない理由

別々の要素のハッシュ結果が偶然同じインデックスに集中することがあるため、未登録の要素であっても、対応するすべてのビットが他の要素によって1にされている状況が起こりうる。このようにして偽陽性が生じる。

一方、登録済みの要素は追加時に必ずビットを1にしているため、ビットが0に戻ることはない。したがって登録済みの要素を「含まれていない」と誤判定すること（偽陰性）は起こらない。

商フィルターの仕組み

商フィルターは要素のハッシュ値を商と剰余に分け、商を配列のインデックスとして使い剰余だけをスロットに格納する。インデックスから商が復元できるため、ハッシュ値全体を保存せずに済み、コンパクトなハッシュテーブルとして機能する。

データ構造

• p ビットのハッシュ値を、上位 q ビットの商と下位 r ビット（p = q + r）の剰余に分割する。
• 大きさ 2^q のスロット配列を用意し、商をインデックスとして対応するスロットに剰余を格納する。
• 各スロットは剰余に加えて3つのメタデータビットを持つ。
  • is_occupied：このインデックスを商とする要素が存在するか
  • is_continuation：同じ商を持つグループ（run）の継続スロットか
  • is_shifted：本来の位置からずらされて配置されているか

要素の追加

1. 追加する要素にハッシュ関数を適用し、商と剰余を得る。
2. 商をインデックスとして対応するスロットに剰余を格納する。
3. すでに埋まっている場合は隣接スロットへ線形に押し出し、同じ商を持つ剰余を連続して並べる（runを形成する）。
4. 押し出しに合わせて3つのメタデータビットを更新する。

存在判定

1. 判定したい要素にハッシュ関数を適用し、商と剰余を得る。
2. 商の位置の is_occupied を確認する。
3. メタデータビットをたどって対応するrunを特定し、剰余が一致するスロットを線形に探す。
4. 一致するスロットがあれば「含まれているかもしれない」と判定する。
5. なければ「含まれていない」と確定する。

具体例

ハッシュ値を6ビットとし、その内訳を商3ビット・剰余3ビットとした場合を考える。スロット配列は長さ8で、すべてのスロットは空（剰余・メタデータビットの値はいずれも0）の状態から始める。

「apple」のハッシュ値が 010 110（商2、剰余6）だった場合、インデックス2のスロットに剰余6を格納し、そのスロットの is_occupied を1にする。

インデックス	0	1	2	3	4	5	6	7
剰余	-	-	6	-	-	-	-	-
is_occupied	0	0	1	0	0	0	0	0
is_continuation	0	0	0	0	0	0	0	0
is_shifted	0	0	0	0	0	0	0	0

続けて「banana」のハッシュ値が 010 011（商2、剰余3）で「apple」と商が衝突した場合、インデックス3のスロットに剰余3を押し出して格納し、そのスロットの is_continuation と is_shifted を1にする。インデックス2の is_occupied は1のまま保持する。

インデックス	0	1	2	3	4	5	6	7
剰余	-	-	6	3	-	-	-	-
is_occupied	0	0	1	0	0	0	0	0
is_continuation	0	0	0	1	0	0	0	0
is_shifted	0	0	0	1	0	0	0	0

ここで未登録の「cherry」を検索する。ハッシュ値が 010 110（商2、剰余6）だった場合、インデックス2のrunをたどると剰余6のスロットが見つかるため「含まれているかもしれない」と判定される。しかし「cherry」は実際には登録していない。ブルームフィルターと同様に、商フィルターでも偽陽性が生じる。

参考

• 初めて学ぶブルームフィルタ - yuyan / Zenn

4章 頻度推定とカウントミンスケッチ

この章のポイント

• 大量のデータを分析する際、特定の要素が非常に多く見られる一方で他の多くの要素はほとんど見られないという、頻度推定の問題がよく起こる。
• データを一度しか見られないストリーミングデータでは、データ全体を保存するスペースが限られているため、この問題を解決するのが難しくなる。
• カウントミンスケッチは頻繁に出現する要素を見つける問題の近似解を得るのに適しており、センサーや自然言語処理など、様々な分野で適用できる。
• カウントミンスケッチはメモリ容量の効率がよく、過大評価の範囲を制御する誤差パラメーターによって想定誤差の調整が可能である。

カウントミンスケッチの仕組み

カウントミンスケッチは複数の独立したハッシュ関数を使って各要素を複数のカウンターに分散して記録し、検索時にはそれらの最小値を取ることで頻度を推定する。

データ構造

• d 個の独立したハッシュ関数
• d 行 × w 列のカウンター配列（初期値はすべて0）

要素の追加

1. 追加する要素に d 個のハッシュ関数をそれぞれ適用し、各行で1つずつインデックスを得る。
2. 対応するカウンター（合計 d 個）をそれぞれ1ずつ増やす。

頻度の推定

1. 推定したい要素に同じ d 個のハッシュ関数を適用する。
2. 各行で対応するカウンター値を取り出し、その最小値を頻度の推定値とする。

過大評価しか起こらない理由

別の要素のハッシュ結果が衝突して同じカウンターを共有することはある。その場合カウンターは「実際の出現回数 + 他の要素による加算」となるため、必ず実際の頻度以上の値を返す。

複数のハッシュ関数すべてで衝突が起こるケースは確率的に小さい。最小値を取ることで過大評価を抑える設計になっている。

具体例

幅 w=4、行数 d=2 のカウントミンスケッチを考える。すべてのカウンターを0で初期化する。

行0: [0, 0, 0, 0]
行1: [0, 0, 0, 0]

「apple」を追加する。ハッシュ値が「行0:2、行1:0」だった場合、それぞれのカウンターを1にする。

行0: [0, 0, 1, 0]
行1: [1, 0, 0, 0]

「apple」をもう1回追加する。同じ位置のカウンターをさらに1増やす。

行0: [0, 0, 2, 0]
行1: [2, 0, 0, 0]

「banana」を追加する。ハッシュ値が「行0:2、行1:3」だった場合、行0の位置2は「apple」と衝突してカウンターが3になる。

行0: [0, 0, 3, 0]
行1: [2, 0, 0, 1]

ここで「apple」の頻度を推定する。「行0:2、行1:0」のカウンター値は (3, 2) で、その最小値2が推定値となる。実際の出現回数2と一致する。

「banana」の頻度を推定すると、「行0:2、行1:3」のカウンター値は (3, 1) で、最小値1が実際と一致する。

行0の位置2を直接見ると「banana」の頻度が3に過大評価されているが、行1が正しい値を保持しているため、最小値を取ることで実際の頻度に近づく。

5章 カーディナリティー推定とハイパーログログ

この章のポイント

• カーディナリティー推定は、データベースやネットワークトラフィック・電子商取引など、ソフトウェア開発のあらゆる領域で発生する問題である。
• データ量が非常に多いため、正確に計算する古典的な方法から、いくらかの誤差を許容してメモリ容量を大幅に削減する確率的な方法へと主流が変わってきている。
• ハイパーログログは、ハッシュ化とランダムビット文字列の確率的特性を利用してカーディナリティーを推定するアルゴリズム／データ構造である。
• 大規模なシステムを運用する多くの企業がハイパーログログを導入し、様々な側面を改善し現代化している。
• 最も力を発揮するのは、巨大な時系列データを個別のテーブルに集約する場面である。時間単位ごとのハイパーログログをテーブルとして保存し、必要な期間に対して該当するハイパーログログを集約できる。

カーディナリティー推定が難しい理由

カーディナリティーとは、ある集合に含まれる「重複を除いた要素の個数」を指す。たとえばあるサービスの1日のユニークユーザー数を求めたい場合、SQLなら次のように書ける。

SELECT COUNT(DISTINCT user_id) FROM access_log;

素朴な実装としては、すでに見たIDを集合に記録しておき、未登録なら追加してカウンターを増やすという方法がある。しかしユニーク要素が数億〜数十億規模になると、IDそのものを保持する集合がメモリに収まらなくなる。「過去に出現したかどうか」を厳密に判定し続けるには原理的にすべての要素を覚えておく必要があるため、正確な値を保つ限りメモリ消費を本質的に減らせない。

ハイパーログログはこの問題に対して、要素そのものを覚えるのをやめ、ハッシュ値の確率的な性質だけからカーディナリティーを推定するというアプローチを取る。

直感的なアイデア：コイントスからの類推

ハイパーログログの基本的な発想は、コイントスの例で理解しやすい。

ある集団の一人ひとりにコインを何度も投げてもらい、最初に裏が出るまで表が連続した回数を記録する。表が1回連続して出る確率は1/2なので、表が k 回連続して出るという事象の確率は (1/2)^k となる。逆に言えば、集団の中の誰か1人でも表を k 回連続で出したのなら、その集団の人数はおよそ 2^k 人程度だろうと推定できる。

ここで重要なのは「誰がもう数えられたか」を覚える必要がまったくないという点にある。残しておく情報は、これまでに観測された「連続して表が出た最大回数」というたった1つの整数だけでよい。

これをハイパーログログに置き換えると次のようになる。

• 1人のコイントス結果 → 1つの要素のハッシュ値
• 表が連続する回数 → ハッシュ値のビット列の先頭に並ぶ0の連続数
• 集団の人数 → カーディナリティー

アルゴリズムの流れ

実際のハイパーログログでは、推定精度を高めるために多数の独立した「推定器」を組み合わせる。コインの代わりにハッシュ関数を使うことで、決定論的かつ要素ごとに同じ結果が得られるようにしている。

データ構造

長さ m = 2^b のレジスタ配列を用意する。各レジスタは「これまでにそのレジスタに割り当てられた要素のハッシュ値で観測された、先頭0の連続数の最大値」を保持する小さな整数（典型的には数ビット）にあたる。

要素の追加

1. 要素にハッシュ関数を適用し、十分に長いビット列を得る。
2. ビット列の先頭 b ビットを使い、どのレジスタを更新するかを決める（要素を 2^b 個のレジスタへ振り分ける形になる）。
3. 残りのビット列で、先頭から0が連続する個数 ρ を数える。
4. 対応するレジスタの値を、ρ + 1 と現在値の大きい方で更新する。

カーディナリティーの推定

すべての要素を処理し終えたら、レジスタ群の値からカーディナリティーを推定する。各レジスタはハッシュ空間の 1/m を担当する小さな推定器とみなせるので、それらの値を集約してレジスタ数 m を掛けることで全体の推定値が得られる。少数のレジスタが極端な値を取っても全体推定が大きくぶれないように、調和平均と小さな補正項が使われる。

具体例

レジスタ数 m = 4（b = 2）のハイパーログログを考える。各レジスタを0で初期化する。

レジスタ: [0, 0, 0, 0]

「apple」を追加する。ハッシュ値の上位2ビットが 01、残りのビット列が 10110... だった場合を考える。上位2ビットからレジスタ1を選び、残りのビット列の先頭0連続数 ρ = 0 から ρ + 1 = 1 でレジスタ1を更新する。

レジスタ: [0, 1, 0, 0]

「banana」を追加する。ハッシュ値の上位2ビットが 11、残りのビット列が 00100... だった場合を考える。レジスタ3を選び、残りの先頭0連続数 ρ = 2 から ρ + 1 = 3 でレジスタ3を更新する。

レジスタ: [0, 1, 0, 3]

「cherry」を追加する。ハッシュ値の上位2ビットが 01、残りのビット列が 00001... だった場合を考える。レジスタ1を選び、残りの先頭0連続数 ρ = 4 から ρ + 1 = 5 でレジスタ1を更新する。現在値1より大きいため5に置き換わる。

レジスタ: [0, 5, 0, 3]

最終的にレジスタ群 [0, 5, 0, 3] から、調和平均と補正項を使ってカーディナリティーを推定する。実装では m が64〜数千程度に取られるため、レジスタの分布に基づいてより安定した推定値が得られる。

マージできるという強力な性質

ハイパーログログの各レジスタは「観測された先頭0の連続数の最大値」を保持しているだけなので、同じ m で構築された2つのハイパーログログは、レジスタごとに最大値を取るだけで1つに統合できる。これによって以下のような運用が容易になる。

• 時間単位（1分・1時間・1日など）ごとにハイパーログログを作って保存しておき、任意の期間のユニーク数は対応する範囲のレジスタをmaxでマージして推定する。
• 複数のサーバーやシャードで部分的に作ったハイパーログログを集約サーバーで1つにまとめる。

生のデータを保持し続けて毎回 COUNT(DISTINCT ...) を回すよりも、はるかに少ないストレージとレイテンシーで同じ問いに答えられる。ハイパーログログが大規模システムで広く採用されている大きな理由の1つは、並列・分散処理との相性の良さにある。

名前の由来

ハイパーログログでカーディナリティーを n とすると、各レジスタが保持する必要のある「先頭0の連続数」の大きさは概ね log₂ n のオーダーになる。さらにその値を表現するために必要なビット数は log₂ log₂ n で済む。この「ログログのサイズで十分」という性質が「LogLog」という名前の由来であり、ハイパーログログはその系列を改良したアルゴリズムにあたる。

実用例

ハイパーログログは多くのデータ基盤やデータベースに組み込まれている。

• Amazon Redshift（APPROXIMATE COUNT(DISTINCT ...) や hll_cardinality などのHLL関連関数）
• Presto / Trino（approx_distinct）
• Redis（PFADD / PFCOUNT / PFMERGE）
• Google BigQuery（APPROX_COUNT_DISTINCT）

利用者の側はアルゴリズムを実装する必要はなく、「ある程度の誤差を許容してよいか」「マージ可能であることが嬉しい局面か」を見極めて、適切な関数を選べばよい。

参考

• HyperLogLog について - masatana / Zenn

コラム：4つの確率的データ構造の比較

第1部で登場した4つのデータ構造を一覧で比較すると、それぞれの守備範囲が見えやすくなる。

構造	解く問題	誤差の種類	マージ	削除	主な用途
ブルームフィルター	存在判定	偽陽性のみ	可（同サイズ）	不可	キャッシュの存在確認、URLフィルター
商フィルター	存在判定	偽陽性のみ	可	可	LSM木のSSTable向けフィルター
カウントミンスケッチ	頻度推定	過大評価	可	加減算で可	ヘビーヒッター検出、トラフィック解析
ハイパーログログ	カーディナリティー推定	標準誤差（±数%）	可	不可	ユニークユーザー数（DAU／MAU）

「存在を確かめたいのか・回数を数えたいのか・種類数を数えたいのか」によって選ぶ道具が変わる。そう覚えておくと整理しやすい。

第2部 リアルタイム分析

第2部ではリアルタイムに次々と到着するデータを扱う。第一部のアルゴリズムは、大規模データベースに蓄積された過去のデータだけでなく、新たに連続して入ってくるデータにも適用できる。

このような流れるデータを効率的に扱うには、データが到着するたびに、その情報を迅速に組み込んでいく必要がある。そこでデータの流れの概要を捉える「スケッチ」を使う。ランダムサンプルのように汎用的なスケッチは、データに関する様々なクエリに答えられる。

第2部を読むうえでイメージしておくとよい状況は次の通り。

• 不規則なペースで大量のデータが到着する。
• データは一度処理されると本体は捨てられる。
• 蓄積するのはスケッチや要約だけになる。

6章 ストリーミングデータの統合と応用

この章のポイント

• 分散コンピューティングやストリーミングデータアプリケーションでのリアルタイム結果配信に対して、ハッシュ化・ブルームフィルター・カウントミンスケッチ・ハイパーログログを活用するとエンドツーエンドの遅延を短縮できる。
• 実例としては、異なるストレージシステムに保存された大規模なテーブルの結合・ストリーム内の重複排除・ネットワークトラフィックの監視・負荷分散などのタスクが挙げられる。
• サンプリングは、取り扱いが難しいデータセットに関するクエリに答えるための、強力で長い歴史を持つ技術である。
• データのサブセットを体系的に形成することで、サブセットへのクエリによってデータセット全体へのクエリと同じ精度の答えを得られる。
• 統計的推論の理論を用いることで、サンプルサイズの決定やクエリの回答に最適な推定器の選択が可能になり、結果の正確性と精度を保証できる。

確率的データ構造を組み合わせるシナリオ

実際のリアルタイム分析パイプラインでは、第一部の確率的データ構造を組み合わせて使う場面が多い。

• ストリーム内の重複排除：到着したデータをまずブルームフィルターに通し、「過去に見たかもしれない」要素だけを厳密なチェックに回すことで、I/Oを大幅に削減する。
• ヘビーヒッター検出：ネットワークトラフィックを監視する際、カウントミンスケッチで頻度を推定し、閾値を超えたフローだけを詳しく追跡する。
• ユニーク数の集約：複数のシャードから流れてくるイベントを各シャードでハイパーログログ化する。集約サーバーでまとめてマージすれば、低レイテンシーに全体のユニーク数を得られる。
• 分散ジョイン：異なるストレージ間のテーブルを結合する前にブルームフィルターを送って絞り込み、ネットワーク転送量を減らす（セミジョイン）。

これらの構造は独立して使うこともできるが、複数を組み合わせれば「メモリを小さく・遅延を短く・精度を十分に」というバランスを取れる。

7章 データストリームからのサンプリング

（省略）

8章 データストリーム上の近似分位数

（省略）

第3部 データベースと外部記憶アルゴリズムのためのデータ構造

第1部と第2部では、データを圧縮・サンプリングしてRAMへ収める工夫に焦点を当ててきた。第3部ではその成果を踏まえ、すべてのデータをディスク上に安心して置ける状態になったという前提のもとで、ディスク上の大量のデータをどう管理するかを学ぶ。

第3部の主要なテーマは次の通り。

• データの検索・追加・削除の方法。
• 大きなファイルをディスク上で効率的に整理する方法。
• 読み込みが多いデータベースと書き込みが多いデータベースで、インデックスの設計方法がどう異なるか。

これらを理解するための第一歩は、ディスクからメインメモリへのデータ転送コストがCPUでの処理コストよりも1000倍以上高いという事実を受け入れることだ。アルゴリズムの効率を考える際は、RAM内で起こることよりもディスクとRAMの間のデータ転送に注目する。この視点から分析する方法を学ぶことが第3部の主な目的となる。

9章 外部記憶モデルの紹介

この章のポイント

• データ集中型のアプリケーションはしばしば、ディスク上に大規模なデータセットを保有する。これらの大容量のファイルやDBを効率的に扱うには、特別なデータ構造やアルゴリズムの工夫が求められる。
• 外部記憶モデルは、主記憶に収めることができない大量のデータセットに対するアルゴリズムを分析する際に役立つ。このモデルでは、すべてのデータが無限に大きなディスク上に最初から存在しており、計算するためにデータのブロックを限定されたサイズの主記憶へ移動する必要があるとされる。
• 外部記憶モデルはアルゴリズムの計算コストを考慮せず、主記憶内の計算よりもはるかに高価なデータ転送のコストに焦点を当てる。
• シーケンシャルデータをスキャンする際、外部記憶アルゴリズムでは連続するブロックへ要素を効率的に配置するため、データセットをブロックサイズで分割する場合が多い。
• 内部記憶では二分探索が最適な検索手法だが、外部記憶では最適とは限らず、ブロックの入出力を最大限に活用することが求められる。ブロックを適切に再構成しB木というデータ構造を用いることで、より良い実行時間が達成可能となる。
• 大容量の主記憶を活用する最大の利点の1つは、どれだけ大きなファイルであっても、単一の線形スキャンで多数の整列されたリストやファイルを同時にマージできる点である。この手法は、後に解説する最適な外部記憶ソートアルゴリズムの基礎となる。

10章 データベースのためのデータ構造：B木・Bε木・LSM木

この章のポイント

• DBインデックスは、DBテーブルに追加される検索効率化のためのデータ構造で、大規模テーブルのクエリを高速化する目的で作られる。外部メモリにおける効率的な検索を実現するために、特定のデータ構造を用いてインデックスが構築される。
• MySQLなど広く採用されているストレージエンジンの中心となるのはB木で、ディスク上でのデータ検索における最適なデータ構造である。B木のノードはブロックサイズに準拠した大きさであり、すべての操作はBを底とする対数時間内に実行される。B木では、ノードが一定の閾値を超えると分割や統合が行われ、木は上方向へと成長する。
• B木は読み取りに特化しているが、書き込み処理が多い作業には別のデータ構造が適している。検索とは異なり、挿入や削除は遅延処理が可能で、バッチ処理によりまとめて処理できる。これを活用した書き込み最適化データ構造は、B木やBε木よりも高速な挿入処理を可能にする。
• Bε木は挿入と削除がB木に比べて漸近的に高速であり、検索処理はB木に比べてわずかに遅いデータ構造である。ノードに設けられたバッファを介して挿入と削除の指示が蓄えられ、適切なタイミングでバッチ処理される。εの値によって、データ構造が読み取りより書き込みをどれだけ優先するかが決まる。
• LSM木は、周期的に高速に統合されるソート済みのデータ列を持つ書き込み最適化データ構造である。LSM木はB木よりも検索が遅いが、書き込みは非常に高速である。

3つのインデックス構造の比較

ワークロード特性と採用例の観点から3つを並べると、それぞれの守備範囲が見えやすくなる。

構造	検索	書き込み	特性	代表的な採用例
B木	高速	標準	読み取り最適化。対数時間で安定したアクセスを提供する。	MySQL／InnoDB、PostgreSQL
Bε木	やや遅い	高速	内部ノードにバッファを持たせ、書き込みを遅延・バッチ化する。	TokuDB、PerconaFT
LSM木	遅い	非常に高速	ソート済みデータ列を周期的にマージして書き込みを最適化する。	LevelDB、RocksDB、Cassandra

読み込みが多いワークロードならB木、書き込みが多いワークロードならLSM木、その中間ならBε木、と大まかに覚えておくと選定の出発点になる。

11章 外部メモリによるソート

この章のポイント

• ソートはコンピューター科学における最もよく知られた問題の1つであり、様々な状況でのソートアルゴリズムの最適化に関する研究が多数存在する。
• データがRAMに収まらない場合、ソートアルゴリズムは小さなデータの断片をRAMに読み込んで、断片ごとにソートを行う必要がある。
• データがRAMに収まり切らない場合のアルゴリズムとしての選択肢はM/B方向外部マージソートである。このアルゴリズムは一度に多数のリストをマージし、大容量のメモリを有効に活用する。
• 同様に、クイックソートも外部メモリで最適に機能するように、より多くのピボットを選び、データを多くのパーティションに分割することにより適応させることが可能である。
• ソートのようなバッチ処理問題は、外部メモリでの検索よりも単位要素あたりのコストが安い。RAMと外部メモリの間の重要な違いは、RAMでは検索構造への挿入により最適にソートできるが、外部メモリでそれを行うと最適でないアルゴリズムとなる点である。

用語集

章をまたいで頻繁に登場する用語を簡潔にまとめておく。

• カーディナリティー：集合に含まれる重複を除いた要素の個数。例：ユニークユーザー数。
• スケッチ：データ全体を保持せず、ハッシュ値などを使って統計量を近似的に保持する小さなデータ構造。
• 偽陽性：実際には集合に含まれていない要素を「含まれている」と誤判定すること。
• 偽陰性：実際には集合に含まれている要素を「含まれていない」と誤判定すること。
• 負荷係数：ハッシュテーブルの使用率を示す指標で、要素数 / スロット数 で表される。値が大きいほど衝突が増える。
• 外部記憶モデル：主記憶に収まらないデータを扱う際の計算モデル。ディスクとRAMの間のブロック転送回数で計算量を測る。
• ブロック：ディスクと主記憶の間でデータを転送する最小単位。
• メモリ階層：CPUレジスタ→キャッシュ→RAM→SSD→HDDの順に並ぶ記憶装置の階層構造。上位ほど高速だが容量が小さい。
• マージ可能：複数のデータ構造を1つに統合できる性質。並列・分散処理と相性が良い。