# 機能設計書 59-タイムスタンプ管理

## 概要

本ドキュメントは、Actual BudgetにおけるCRDTの論理時計によるタイムスタンプ管理機能の設計を記述する。この機能は、分散システムにおけるイベントの順序付けと一意性を保証するHybrid Unique Logical Clock（HULC）タイムスタンプを提供する。

### 本機能の処理概要

Actual Budgetの同期システムにおいて、Hybrid Unique Logical Clock（HULC）に基づくタイムスタンプ生成・管理機能を提供する。物理時計と論理時計を組み合わせることで、クロック誤差やネットワーク遅延がある環境でも、グローバルに一意で単調増加するタイムスタンプを生成する。

**業務上の目的・背景**：分散システムでは、複数のクライアントが独立して操作を行うため、操作の順序を正確に決定することが困難である。HULCタイムスタンプを使用することで、クライアント間のクロック同期が不完全な場合でも、すべての操作に対して一貫した順序付けが可能になり、CRDTベースの同期で競合を解決できる。

**機能の利用シーン**：
- 新しい同期メッセージの生成
- 受信メッセージの処理と時計の更新
- 差分同期の開始時点の指定

**主要な処理内容**：
1. HULCタイムスタンプの生成（send操作）
2. 受信タイムスタンプとの同期（recv操作）
3. タイムスタンプのパース・シリアライズ
4. クロックドリフト検出
5. カウンターオーバーフロー検出

**関連システム・外部連携**：システムクロック（Date.now()）

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

## 関連画面

| 画面No | 画面名 | 関連種別 | 関連する操作・処理 |
|--------|--------|----------|------------------|
| - | なし | - | バックエンド機能のため直接関連する画面なし |

## 機能種別

データ同期 / CRDT / 論理時計

## 入力仕様

### 入力パラメータ（タイムスタンプ生成）

| パラメータ名 | 型 | 必須 | 説明 | バリデーション |
|-------------|-----|-----|------|---------------|
| なし | - | - | send()は引数なし | - |

### 入力パラメータ（タイムスタンプ受信）

| パラメータ名 | 型 | 必須 | 説明 | バリデーション |
|-------------|-----|-----|------|---------------|
| msg | Timestamp | Yes | 受信したタイムスタンプ | フォーマット検証 |

### 入力データソース

- システムクロック（Date.now()）
- 受信メッセージのタイムスタンプ

## 出力仕様

### 出力データ

| 項目名 | 型 | 説明 |
|--------|-----|------|
| timestamp | Timestamp | 生成されたタイムスタンプオブジェクト |

### タイムスタンプ形式

```
2015-04-24T22:23:42.123Z-1000-0123456789ABCDEF
│                     │   │   │
│                     │   │   └─ ノードID（16文字の16進数）
│                     │   └─ カウンター（4桁の16進数）
└─────────────────────┴─ ISO 8601日時
```

### 出力先

呼び出し元への戻り値

## 処理フロー

### 処理シーケンス（send）

```
1. 現在のシステム時刻取得
   └─ Date.now()

2. 論理時刻の計算
   ├─ 現在の論理時刻と物理時刻の最大値
   └─ カウンターの更新

3. ドリフトチェック
   └─ 論理時刻と物理時刻の差が閾値以内か

4. タイムスタンプ生成
   └─ new Timestamp(millis, counter, node)
```

### 処理シーケンス（recv）

```
1. 現在のシステム時刻取得
   └─ Date.now()

2. 受信メッセージのドリフトチェック
   └─ 受信時刻と物理時刻の差が閾値以内か

3. 論理時刻の計算
   └─ ローカル/リモート/物理の最大値

4. カウンターの計算
   └─ 同一論理時刻の場合はカウンタインクリメント

5. 時計の更新
   └─ グローバル時計への反映
```

### フローチャート

```mermaid
flowchart TD
    subgraph send
        A1[send()呼び出し] --> B1[Date.now()取得]
        B1 --> C1[lNew = max(lOld, phys)]
        C1 --> D1{lOld == lNew?}
        D1 -->|Yes| E1[cNew = cOld + 1]
        D1 -->|No| F1[cNew = 0]
        E1 --> G1{ドリフト超過?}
        F1 --> G1
        G1 -->|Yes| H1[ClockDriftError]
        G1 -->|No| I1{カウンタ超過?}
        I1 -->|Yes| J1[OverflowError]
        I1 -->|No| K1[Timestamp生成]
    end

    subgraph recv
        A2[recv(msg)呼び出し] --> B2[Date.now()取得]
        B2 --> C2{msgドリフト超過?}
        C2 -->|Yes| D2[ClockDriftError]
        C2 -->|No| E2[lNew = max(lOld, phys, lMsg)]
        E2 --> F2[cNew計算]
        F2 --> G2[時計更新]
        G2 --> H2[Timestamp生成]
    end
```

## ビジネスルール

### 業務ルール

| ルールNo | ルール名 | 内容 | 適用条件 |
|---------|---------|------|---------|
| BR-59-1 | 最大ドリフト | 論理時刻と物理時刻の差は5分以内 | 常時 |
| BR-59-2 | カウンタ上限 | カウンタは0xFFFF（65535）まで | 常時 |
| BR-59-3 | ノードID長 | ノードIDは16文字の16進数 | 常時 |
| BR-59-4 | 単調増加 | 論理時刻は常に増加（後退しない） | 常時 |
| BR-59-5 | グローバル一意 | タイムスタンプはグローバルに一意 | 常時 |

### 計算ロジック

- **論理時刻（send）**: `lNew = Math.max(lOld, phys)`
- **カウンタ（send）**: `cNew = (lOld === lNew) ? cOld + 1 : 0`
- **論理時刻（recv）**: `lNew = Math.max(lOld, phys, lMsg)`
- **カウンタ（recv）**: 最大論理時刻のソースに応じて増分

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

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

この機能はデータベース操作を行わない。メモリ内のグローバル時計を管理。

## エラー処理

### エラーケース一覧

| エラーコード | エラー種別 | 発生条件 | 対処方法 |
|------------|----------|---------|---------|
| ClockDriftError | クロックドリフト | 論理時刻と物理時刻の差が5分超過 | システムクロック確認 |
| OverflowError | カウンタオーバーフロー | カウンタが0xFFFF超過 | 次のミリ秒を待機 |
| InvalidError | 不正タイムスタンプ | パース失敗 | 入力データ確認 |
| DuplicateNodeError | ノードID重複 | 同一ノードIDからのメッセージ | ノードID再生成 |

### リトライ仕様

エラー時はリトライせず、エラーを上位に伝播。

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

トランザクション処理なし（メモリ操作のみ）

## パフォーマンス要件

- タイムスタンプ生成：1μs以内
- パース処理：10μs以内

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

- ノードIDはUUIDから生成（予測困難）
- タイムスタンプの改ざん検知はMerkle Trieで実現

## 備考

- HLC仕様に基づく実装：http://www.cse.buffalo.edu/tech-reports/2014-04.pdf
- 46文字の文字列にシリアライズ

---

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

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

### 推奨読解順序

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

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 1-1 | timestamp.ts | `packages/crdt/src/crdt/timestamp.ts` | Timestampクラスと型定義 |

**読解のコツ**: HLC（Hybrid Logical Clock）の論文を参照すると、実装の意図が理解しやすい。

**主要処理フロー**:
- **29-32行目**: Clock型定義（timestamp + merkle）
- **94-103行目**: Timestampコンストラクタ（millis, counter, node）
- **109-114行目**: toString()シリアライズ

#### Step 2: タイムスタンプ生成（send）を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 2-1 | timestamp.ts | `packages/crdt/src/crdt/timestamp.ts` | send()静的メソッド |

**主要処理フロー**:
- **195-230行目**: Timestamp.send()
- **201行目**: Date.now()で物理時刻取得
- **204-205行目**: 現在の論理時刻とカウンタ取得
- **210-211行目**: 新論理時刻とカウンタ計算
- **214-215行目**: ドリフトチェック
- **217-218行目**: オーバーフローチェック
- **222-223行目**: グローバル時計更新

#### Step 3: タイムスタンプ受信（recv）を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 3-1 | timestamp.ts | `packages/crdt/src/crdt/timestamp.ts` | recv()静的メソッド |

**主要処理フロー**:
- **235-292行目**: Timestamp.recv()
- **241行目**: 物理時刻取得
- **244-245行目**: 受信メッセージの時刻取得
- **251-253行目**: 受信メッセージのドリフトチェック
- **265-273行目**: 論理時刻とカウンタ計算

#### Step 4: ユーティリティ関数を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 4-1 | timestamp.ts | `packages/crdt/src/crdt/timestamp.ts` | その他の関数 |

**主要処理フロー**:
- **79-81行目**: makeClientId()（UUID生成）
- **166-189行目**: Timestamp.parse()（文字列パース）
- **129-131行目**: hash()（MurmurHash計算）

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

```
Timestamp.send()
    │
    ├─ Date.now()
    │
    ├─ clock.timestamp.millis() / counter()
    │
    ├─ Math.max(lOld, phys)
    │
    ├─ [ドリフトチェック]
    │      └─ ClockDriftError
    │
    ├─ [オーバーフローチェック]
    │      └─ OverflowError
    │
    ├─ clock.timestamp.setMillis() / setCounter()
    │
    └─ new Timestamp(millis, counter, node)

Timestamp.recv(msg)
    │
    ├─ Date.now()
    │
    ├─ msg.millis() / counter()
    │
    ├─ [ドリフトチェック]
    │      └─ ClockDriftError
    │
    ├─ clock.timestamp.millis() / counter()
    │
    ├─ Math.max(lOld, phys, lMsg)
    │
    ├─ [カウンタ計算ロジック]
    │
    ├─ clock.timestamp.setMillis() / setCounter()
    │
    └─ new Timestamp(millis, counter, node)
```

### データフロー図

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

                    ┌─────────────────┐
Date.now() ────────▶│                 │
                    │  Timestamp.send │─────────▶ Timestamp
グローバル時計 ─────▶│                 │               │
                    └─────────────────┘               ▼
                                                "2015-04-24T22:23:42.123Z-1000-ABCDEF..."

                    ┌─────────────────┐
Date.now() ────────▶│                 │
                    │  Timestamp.recv │─────────▶ Timestamp
受信メッセージ ─────▶│                 │               │
グローバル時計 ─────▶│                 │               ▼
                    └─────────────────┘        グローバル時計更新
```

### 関連ファイル一覧

| ファイル | パス | 種別 | 役割 |
|---------|------|------|------|
| timestamp.ts | `packages/crdt/src/crdt/timestamp.ts` | ソース | HULCタイムスタンプ実装 |
| index.ts | `packages/crdt/src/crdt/index.ts` | ソース | CRDTモジュールエクスポート |
| merkle.ts | `packages/crdt/src/crdt/merkle.ts` | ソース | タイムスタンプを使用するMerkle Trie |
