# 機能設計書 69-負荷分散

## 概要

本ドキュメントは、Jenkins におけるビルドタスクの Executor 割り当て制御（負荷分散）機能の設計について記述する。

### 本機能の処理概要

負荷分散機能は、キューに入ったビルドタスクをどの Executor で実行するかを決定するスケジューリング機能である。デフォルトでは Consistent Hash アルゴリズムを使用して効率的な割り当てを行う。

**業務上の目的・背景**：大規模な CI/CD 環境では、多数のビルドタスクを複数のノード/Executor に効率的に分散させる必要がある。負荷分散機能は、ビルドの実行効率を最大化し、特定のノードへの偏りを防ぎ、ビルド時間の短縮とリソースの有効活用を実現する。また、Consistent Hash を使用することで、同じジョブが同じノードで実行されやすくなり、ワークスペースキャッシュの効率的な利用も可能になる。

**機能の利用シーン**：
- キューからのビルドタスク割り当て
- 複数 Executor への作業分散
- エージェントノードの負荷均等化
- アフィニティ（親和性）を考慮した割り当て

**主要な処理内容**：
1. キューイングされたタスクの取得
2. 利用可能な Executor の収集
3. Consistent Hash による Executor 選択
4. 貪欲法による割り当て最適化
5. シャットダウン中のブロッキング
6. カスタム LoadBalancer への置き換え対応

**関連システム・外部連携**：
- Queue: ジョブキュー
- Executor: タスク実行単位
- MappingWorksheet: 割り当て計算用ワークシート
- ConsistentHash: ハッシュベースの割り当てアルゴリズム

**権限による制御**：負荷分散機能自体には特別な権限制御はない。Queue の操作権限に依存。

## 関連画面

| 画面No | 画面名 | 関連種別 | 関連する操作・処理 |
|--------|--------|----------|------------------|
| 4 | ビルドキュー | 補助機能 | キュー内タスクの表示 |
| 10 | ビルド実行中情報 | 結果表示画面 | 実行中タスクの表示 |

## 機能種別

スケジューリング / リソース管理

## 入力仕様

### 入力パラメータ

| パラメータ名 | 型 | 必須 | 説明 | バリデーション |
|-------------|-----|-----|------|---------------|
| task | Task | Yes | 割り当て対象のタスク | null でないこと |
| worksheet | MappingWorksheet | Yes | 割り当て計算用ワークシート | null でないこと |

### 入力データソース

- Queue からのタスク情報
- Executor の状態情報

## 出力仕様

### 出力データ

| 項目名 | 型 | 説明 |
|--------|-----|------|
| Mapping | Mapping | タスクと Executor の割り当て結果、割り当て不可の場合は null |

### 出力先

- Queue: 割り当て結果に基づいてタスクを Executor に渡す

## 処理フロー

### 処理シーケンス

```
1. map() メソッドの呼び出し
   └─ Queue からタスクとワークシートを受け取る

2. シャットダウンチェック
   └─ sanitize() でシャットダウン中は null を返す

3. Consistent Hash の構築
   └─ 各ワークチャンクに対して利用可能な ExecutorChunk を収集
   └─ ConsistentHash を構築

4. 貪欲割り当て
   └─ assignGreedily() でアフィニティキーに基づいて割り当て
   └─ 部分的な有効性をチェックしながら再帰的に割り当て

5. 割り当て結果の返却
   └─ 完全に有効な Mapping を返す、または null（割り当て不可）
```

### フローチャート

```mermaid
flowchart TD
    A[map 呼び出し] --> B{シャットダウン中?}
    B -->|Yes| C[null 返却]
    B -->|No| D[ConsistentHash 構築]
    D --> E[ワークチャンクごとにハッシュ構築]
    E --> F[Mapping 生成]
    F --> G[assignGreedily 開始]
    G --> H{全チャンク割り当て済み?}
    H -->|Yes| I[Mapping 返却]
    H -->|No| J[アフィニティキー取得]
    J --> K[ConsistentHash.list でチャンク候補取得]
    K --> L{候補チャンク選択}
    L --> M[assign]
    M --> N{部分的に有効?}
    N -->|Yes| O[再帰呼び出し]
    N -->|No| P[次の候補を試行]
    O --> Q{再帰成功?}
    Q -->|Yes| I
    Q -->|No| P
    P --> R{候補なし?}
    R -->|Yes| S[null 返却]
```

## ビジネスルール

### 業務ルール

| ルールNo | ルール名 | 内容 | 適用条件 |
|---------|---------|------|---------|
| BR-69-01 | シャットダウンブロック | シャットダウン中は新規タスクを割り当てない | Queue.isBlockedByShutdown() が true |
| BR-69-02 | アフィニティ | 同じジョブは同じノードで実行されやすい | デフォルト動作 |
| BR-69-03 | 貪欲割り当て | 先に見つかった有効な割り当てを採用 | 常時 |
| BR-69-04 | 重み付け | Executor 数に比例した重みで ConsistentHash を構築 | 常時 |

### 計算ロジック

**Consistent Hash の重み計算**:
- 各 ExecutorChunk の重み = ec.size() * 100
- サイズ（Executor 数）に比例した確率で選択される

**アフィニティキー**:
- task.getAffinityKey() で取得
- デフォルトはジョブのフル表示名
- 複数ワークチャンクの場合はインデックスを付加

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

### 操作別データベース影響一覧

該当なし（負荷分散はメモリ上で動作）

## エラー処理

### エラーケース一覧

| エラーコード | エラー種別 | 発生条件 | 対処方法 |
|------------|----------|---------|---------|
| RuntimeException | 実行時エラー | task.getAffinityKey() での例外 | デフォルトのキー（フル表示名）を使用 |

### リトライ仕様

割り当て失敗時は null を返し、後で再度呼び出される。

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

該当なし

## パフォーマンス要件

- 割り当て計算は高頻度で行われるため高速である必要がある
- ConsistentHash による O(log n) の検索
- 貪欲法による効率的な割り当て

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

- LoadBalancer のカスタム実装は慎重に設計する必要がある
- 特定のノードへの偏りを避ける

## 備考

- LoadBalancer は ExtensionPoint だが、@Extension ではなく Queue.setLoadBalancer() で設定
- CONSISTENT_HASH がデフォルト実装
- DEFAULT は CONSISTENT_HASH のエイリアス（非推奨）
- sanitize() でシャットダウンチェックを追加するラッパーを生成可能

---

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

本機能を理解するために参照すべきファイルと、推奨する読み解き順序を以下に示す。

### 推奨読解順序

#### Step 1: データ構造を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 1-1 | LoadBalancer.java | `core/src/main/java/hudson/model/LoadBalancer.java` | LoadBalancer 抽象クラスの構造（54-181行目） |

**読解のコツ**: LoadBalancer は ExtensionPoint を実装する抽象クラス。map() メソッドが唯一の抽象メソッドで、実装クラスでオーバーライドする。

#### Step 2: map() メソッドを理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 2-1 | LoadBalancer.java | `core/src/main/java/hudson/model/LoadBalancer.java` | map() 抽象メソッド（76-77行目） |

**主要処理フロー**:
- **76-77行目**: map() - タスクとワークシートを受け取り、Mapping を返す

#### Step 3: CONSISTENT_HASH 実装を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 3-1 | LoadBalancer.java | `core/src/main/java/hudson/model/LoadBalancer.java` | CONSISTENT_HASH 定数（82-140行目） |

**主要処理フロー**:
- **87-100行目**: ワークチャンクごとに ConsistentHash を構築
- **103-110行目**: Mapping を生成し、assignGreedily() を呼び出し
- **113-139行目**: assignGreedily() - 再帰的な貪欲割り当て

#### Step 4: sanitize() を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 4-1 | LoadBalancer.java | `core/src/main/java/hudson/model/LoadBalancer.java` | sanitize() メソッド（156-178行目） |

**主要処理フロー**:
- **157行目**: 元の LoadBalancer を base として保持
- **161-163行目**: シャットダウンチェック
- **167行目**: base.map() を呼び出し
- **173-176行目**: 二重サニタイズ防止

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

```
LoadBalancer.map(task, worksheet)
    │
    └─ CONSISTENT_HASH.map()
           │
           ├─ ConsistentHash 構築 (88-100行目)
           │      ├─ ws.works(i).applicableExecutorChunks() (92行目)
           │      └─ hash.addAll(toAdd) (97行目)
           │
           ├─ Mapping 生成 (103行目)
           │
           └─ assignGreedily() (106行目)
                  │
                  ├─ task.getAffinityKey() (117-122行目)
                  │
                  ├─ hashes.get(i).list(key) (126行目)
                  │
                  ├─ m.assign(i, ec) (128行目)
                  │
                  ├─ m.isPartiallyValid() チェック (130行目)
                  │
                  └─ 再帰呼び出し (130行目)
```

### データフロー図

```
[入力]                      [処理]                           [出力]

Task ─────────────────▶ LoadBalancer.map()
                              │
                              ▼
MappingWorksheet ────▶ ConsistentHash 構築
                              │
                              ▼
ExecutorChunk 一覧 ───▶ 重み付きハッシュ追加
                              │
                              ▼
アフィニティキー ────▶ ConsistentHash.list()
                              │
                              ▼
                       assignGreedily() ────────▶ Mapping
                              │
                              ▼
                       isCompletelyValid() ────▶ 結果返却
```

### 関連ファイル一覧

| ファイル | パス | 種別 | 役割 |
|---------|------|------|------|
| LoadBalancer.java | `core/src/main/java/hudson/model/LoadBalancer.java` | ソース | 負荷分散の主要クラス |
| MappingWorksheet.java | `core/src/main/java/hudson/model/queue/MappingWorksheet.java` | ソース | 割り当て計算用ワークシート |
| ExecutorChunk.java | `core/src/main/java/hudson/model/queue/MappingWorksheet.java` | ソース | Executor のグループ |
| Queue.java | `core/src/main/java/hudson/model/Queue.java` | ソース | ジョブキュー |
| ConsistentHash.java | `core/src/main/java/hudson/util/ConsistentHash.java` | ソース | Consistent Hash 実装 |
