# 機能設計書 94-Sketch Data Structures

## 概要

本ドキュメントは、Apache Sparkの確率的データ構造（Sketch Data Structures）の設計について記述する。CountMinSketchとBloomFilterの2つの確率的データ構造を提供し、近似的な頻度推定と所属テストを効率的に行う。

### 本機能の処理概要

**業務上の目的・背景**：大規模データセットに対する正確な集計やルックアップは膨大なメモリと計算コストを必要とする。確率的データ構造は、一定の誤差を許容することで、サブリニアなメモリ使用量で近似的な回答を提供する。SparkのSQL最適化（統計情報収集）や、ユーザーが利用可能なAPIとして活用される。

**機能の利用シーン**：
- CountMinSketch: データストリーム中の要素の出現回数の近似推定（カーディナリティ推定）
- BloomFilter: 要素の集合への所属テスト（偽陽性を許容する高速なフィルタリング）

**主要な処理内容**：
1. CountMinSketch: 2次元long配列によるハッシュベースの頻度カウント
2. BloomFilter: ビット配列とハッシュ関数による空間効率の良い集合所属テスト
3. 両構造のマージ（mergeInPlace）によるパーティション間の結合
4. バイナリシリアライゼーション/デシリアライゼーション

**関連システム・外部連携**：Spark SQLの統計情報収集、DataFrameのbloomFilter/countMinSketch API、join最適化で利用される。

**権限による制御**：特になし。

## 関連画面

| 画面No | 画面名 | 関連種別 | 関連する操作・処理 |
|--------|--------|----------|------------------|
| - | - | - | 画面機能マッピングに本機能に対応する画面定義なし |

## 機能種別

基盤 / 確率的データ構造

## 入力仕様

### 入力パラメータ

#### CountMinSketch

| パラメータ名 | 型 | 必須 | 説明 | バリデーション |
|-------------|-----|-----|------|---------------|
| depth | int | Yes（パターン1） | スケッチの深さ | 正の整数 |
| width | int | Yes（パターン1） | スケッチの幅 | 正の整数 |
| eps | double | Yes（パターン2） | 相対誤差 | 正の値 |
| confidence | double | Yes（パターン2） | 信頼度 | (0.0, 1.0)の範囲 |
| seed | int | Yes | ランダムシード | - |

#### BloomFilter

| パラメータ名 | 型 | 必須 | 説明 | バリデーション |
|-------------|-----|-----|------|---------------|
| expectedNumItems | long | Yes | 期待挿入要素数 | 正の値 |
| fpp | double | No | 偽陽性確率（デフォルト0.03） | (0.0, 1.0)の範囲 |
| numBits | long | No | ビット配列サイズ | 正の値 |
| seed | int | No | ランダムシード（V2のみ） | - |

## 出力仕様

### 出力データ

| 項目名 | 型 | 説明 |
|--------|-----|------|
| CountMinSketch | CountMinSketch | 頻度推定用スケッチインスタンス |
| BloomFilter | BloomFilter | 所属テスト用フィルターインスタンス |
| 推定頻度 | long | estimateCount()の戻り値 |
| 所属判定 | boolean | mightContain()の戻り値 |

## 処理フロー

### 処理シーケンス

#### CountMinSketch

```
1. 生成
   a. create(depth, width, seed) → CountMinSketchImpl(depth, width, seed)
   b. create(eps, confidence, seed) → CountMinSketchImpl(eps, confidence, seed)
      - width = ceil(2/eps)
      - depth = ceil(-log2(1-confidence))
   c. initTablesWith(depth, width, seed): 2次元配列とハッシュ関数の初期化

2. 要素追加
   a. add(item): hashの計算 → 各行のカウンタをインクリメント
   b. addLong/addString/addBinary: 型別最適化

3. 頻度推定
   a. estimateCount(item): 各行のカウンタの最小値を返す

4. マージ
   a. mergeInPlace(other): 同一depth/width/seedの場合、各セルを加算

5. シリアライゼーション
   a. writeTo(out): V1形式でバイナリ出力
   b. readFrom(in): V1形式からデシリアライズ
```

#### BloomFilter

```
1. 生成
   a. create(expectedNumItems) → デフォルトFPP(0.03)で生成
   b. create(expectedNumItems, fpp) → 最適ビット数を計算
      - numBits = -n * log(p) / (log(2))^2
   c. create(expectedNumItems, numBits) → 最適ハッシュ関数数を計算
      - numHashFunctions = max(1, round(m/n * log(2)))
   d. V1/V2版のインスタンスを生成

2. 要素追加
   a. put(item): ハッシュ値計算 → ビット設定
   b. putLong/putString/putBinary: 型別最適化

3. 所属テスト
   a. mightContain(item): 全ハッシュ位置のビットがセットされているか判定
   b. 偽陽性あり、偽陰性なしの片側誤差

4. マージ
   a. mergeInPlace(other): ビット配列のOR演算
   b. intersectInPlace(other): ビット配列のAND演算

5. シリアライゼーション
   a. writeTo(out): V1/V2形式でバイナリ出力
   b. readFrom(in): バージョン検出して適切な実装でデシリアライズ
```

## ビジネスルール

### 業務ルール

| ルールNo | ルール名 | 内容 | 適用条件 |
|---------|---------|------|---------|
| BR-94-01 | CMS誤差保証 | 確率deltaで、推定値は真の値+eps*N以下 | estimateCount使用時 |
| BR-94-02 | BF片側誤差 | 偽陽性はあるが偽陰性はない | mightContain使用時 |
| BR-94-03 | マージ互換性 | CMS: 同一depth/width/seedのみ。BF: 同一bitSizeのみ | mergeInPlace使用時 |
| BR-94-04 | V2デフォルト | BloomFilterはデフォルトでV2版を生成 | create()呼び出し時 |
| BR-94-05 | デフォルトFPP | BloomFilterのデフォルト偽陽性確率は3%（0.03） | fpp未指定時 |

### 計算ロジック

- **CMS幅**: `width = ceil(2 / eps)`
- **CMS深さ**: `depth = ceil(-log(1 - confidence) / log(2))`
- **BF最適ビット数**: `numBits = -n * log(p) / (log(2))^2`
- **BF最適ハッシュ関数数**: `numHashFunctions = max(1, round(m / n * log(2)))`
- **BF可変FPP**: `fpp = min(expectedNumItems / (maxNumItems / DEFAULT_FPP), DEFAULT_FPP)`

## データベース操作仕様

本機能はデータベースを直接操作しない。

## エラー処理

### エラーケース一覧

| エラーコード | エラー種別 | 発生条件 | 対処方法 |
|------------|----------|---------|---------|
| IllegalArgumentException | パラメータエラー | depth/widthが正でない | 正の値を指定 |
| IllegalArgumentException | パラメータエラー | confidence範囲外 | (0.0, 1.0)の範囲を指定 |
| IncompatibleMergeException | マージエラー | 非互換スケッチのマージ | 同一パラメータのスケッチを使用 |
| IllegalArgumentException | バージョンエラー | 未知のBloomFilterバージョン | サポートされたバージョン（1,2）を使用 |

## トランザクション仕様

本機能はトランザクション管理対象外。個々のスケッチインスタンスはスレッドセーフではない。

## パフォーマンス要件

- CountMinSketch: O(depth)の時間計算量で追加・推定を実行
- BloomFilter: O(k)の時間計算量で追加・テストを実行（k=ハッシュ関数数）
- メモリ使用量はパラメータに比例（CMS: depth*width*8バイト、BF: numBits/8バイト）

## セキュリティ考慮事項

特になし。

## 備考

`common/sketch/` パッケージ配下に実装。CountMinSketchはstream-libの実装に基づき、BloomFilterはGuavaの実装に基づく。

---

## コードリーディングガイド

### 推奨読解順序

#### Step 1: 抽象クラスを理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 1-1 | CountMinSketch.java | `common/sketch/src/main/java/org/apache/spark/util/sketch/CountMinSketch.java` | **54-222行目**: 抽象クラス。Version enum（V1）、create()ファクトリメソッド、readFrom()デシリアライゼーション |
| 1-2 | BloomFilter.java | `common/sketch/src/main/java/org/apache/spark/util/sketch/BloomFilter.java` | **45-317行目**: 抽象クラス。Version enum（V1, V2）、create()ファクトリメソッド、最適パラメータ計算、readFrom()バージョン自動検出 |

**読解のコツ**: まず抽象クラスのAPIを把握し、次に具体実装のアルゴリズムを読む。BloomFilterのreadFrom()（195-207行目）ではバージョン検出のためにBufferedInputStreamでpeekしている点に注目。

#### Step 2: 具体実装を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 2-1 | CountMinSketchImpl.java | `common/sketch/src/main/java/org/apache/spark/util/sketch/CountMinSketchImpl.java` | **24-80行目**: depth/width/table/hashA/epsのフィールド定義。コンストラクタでのパラメータ計算。PRIME_MODULUS = 2^31 - 1 |
| 2-2 | BloomFilterImpl.java | `common/sketch/src/main/java/org/apache/spark/util/sketch/BloomFilterImpl.java` | V1版BloomFilter実装。BitArrayによるビット管理 |
| 2-3 | BloomFilterImplV2.java | `common/sketch/src/main/java/org/apache/spark/util/sketch/BloomFilterImplV2.java` | V2版BloomFilter実装。int32切り捨て問題の修正 |

### プログラム呼び出し階層図

```
CountMinSketch (抽象クラス)
    |
    +-- create(depth, width, seed) --> CountMinSketchImpl
    +-- create(eps, confidence, seed) --> CountMinSketchImpl
    +-- readFrom(InputStream) --> CountMinSketchImpl.readFrom()
    |
    CountMinSketchImpl
        +-- add(item) --> hashLong/hashString --> テーブル更新
        +-- estimateCount(item) --> 各行最小値
        +-- mergeInPlace(other) --> テーブル加算

BloomFilter (抽象クラス)
    |
    +-- create(expectedNumItems) --> create(n, DEFAULT_FPP)
    +-- create(n, fpp) --> create(n, optimalNumOfBits)
    +-- create(n, numBits) --> create(V2, n, numBits, DEFAULT_SEED)
    +-- create(version, n, numBits, seed) --> BloomFilterImpl / BloomFilterImplV2
    +-- readFrom(InputStream) --> [バージョン検出] --> BloomFilterImpl.readFrom / V2.readFrom
    |
    BloomFilterImpl / BloomFilterImplV2
        +-- put(item) --> ハッシュ計算 --> BitArray.set()
        +-- mightContain(item) --> ハッシュ計算 --> BitArray.get()
        +-- mergeInPlace(other) --> BitArray.putAll() [OR]
        +-- intersectInPlace(other) --> BitArray.intersect() [AND]
```

### データフロー図

```
[入力パラメータ]         [スケッチ生成]           [操作]            [出力]

eps, confidence   -->  CountMinSketch       add(item)         estimateCount --> long
seed                   .create()            addLong()
                                            mergeInPlace()

expectedNumItems  -->  BloomFilter          put(item)         mightContain --> boolean
fpp                    .create()            putLong()
                                            mergeInPlace()
                                            intersectInPlace()
```

### 関連ファイル一覧

| ファイル | パス | 種別 | 役割 |
|---------|------|------|------|
| CountMinSketch.java | `common/sketch/src/main/java/org/apache/spark/util/sketch/CountMinSketch.java` | ソース | CMS抽象クラス・API |
| CountMinSketchImpl.java | `common/sketch/src/main/java/org/apache/spark/util/sketch/CountMinSketchImpl.java` | ソース | CMS具体実装 |
| BloomFilter.java | `common/sketch/src/main/java/org/apache/spark/util/sketch/BloomFilter.java` | ソース | BF抽象クラス・API |
| BloomFilterImpl.java | `common/sketch/src/main/java/org/apache/spark/util/sketch/BloomFilterImpl.java` | ソース | BF V1実装 |
| BloomFilterImplV2.java | `common/sketch/src/main/java/org/apache/spark/util/sketch/BloomFilterImplV2.java` | ソース | BF V2実装 |
| IncompatibleMergeException.java | `common/sketch/src/main/java/org/apache/spark/util/sketch/IncompatibleMergeException.java` | ソース | マージ非互換例外 |
