ライブ配信プロトコル NDGR の Message ID 単位重複除去
― 分散システム原則の Chrome 拡張への適用

1.解決したい課題

NDGR（niconico data graph relay）は、ニコ生の現行コメント配信プロトコル。length-delimited な Protocol Buffers フレームを HTTP long-polling 経由で配信する。Chrome 拡張がコメントを独自集計する場合、NDGR フレームを decode して順次受信するが、以下 3 つの経路で同じ message が複数回届く:

• (a) ネットワーク再送: HTTP long-polling の TCP 層 / アプリ層リトライで同一 segment が再配信される。
• (b) reconnect / backward fetch: 配信中の通信断後の再接続時、サーバが直近 N 秒分を再配信する（一般的な at-least-once 設計）。
• (c) relay overlap: 配信切替（同一視聴者が別 live に移動）で、前 live の tail と新 live の head が一時的に同じ segment URI を踏むことがある。

NdgrClientSharp（niconico 系 OSS の C# 実装）は Dictionary<string, HashSet<string>> 型で segment URI を主キーに重複排除しているが、これは (c) に弱い（同じ segment URI が別 live で再利用されると false dedupe）。

本手法は、分散システムで確立された原則に従って NDGR Message ID 単位の dedupe を行い、3 つの重複源を統一的に処理する。

2.手法の概要

受信パイプラインの構造:

NDGR HTTP frame
   ↓
length-delimited decode
   ↓
protobuf parse → { messageId, commentNo, chat, ... }
   ↓
★ dedupe（本手法）: canonical key = liveId + ":" + messageId
   ↓
post to aggregator

dedupe レイヤーの内部状態:

• currentLiveId: 現在の live ID（null 許容）
• buckets: Map<liveId, { ids: Set<string>, fifo: string[] }>
• perLiveMax: 1 live あたりの上限件数（既定 4096）
• stats: accepted / droppedDuplicate / evictedIds / resets 等の運用メトリクス

3.アルゴリズム詳細

3-1. canonical key 構築

liveId + ":" + messageId を主キーとする。liveId を含めることで、(c) relay overlap で同じ messageId が別 live に偶然衝突するケースを安全側に倒す（別 live なら別 message として通す）。

3-2. dedupe 判定

1. messageId が空文字 / null なら no-id として通す（dedupe しない、上流で空 ID 設計が変わった場合の fail-soft）。
2. liveId が空なら invalid-key として通す（バグ検知のシグナルとして通すが、観測層に記録）。
3. 該当 live の bucket に key が存在すれば duplicate。droppedDuplicate++。
4. 無ければ first-seen。bucket に追加。accepted++。

3-3. FIFO eviction

bucket の ids（Set）と fifo（array）を並行管理する。新規 ID は ids.add(key) + fifo.push(key)。fifo.length > perLiveMax になったら fifo.shift() で古い ID を取り出し、ids.delete(oldKey) で除外する。

3-4. live 切替時の reset

setCurrentLiveId(newLiveId) が呼ばれ、currentLiveId !== newLiveId なら全 bucket を clear（メモリ解放）。relay overlap のフェーズが終わった後の不要な保持を防ぐ。観測層に resets++ を記録。

3-5. メモリ予算

1 live 平均数千〜数万 message を想定すると、Set + FIFO で 1 live あたり 200-400 KB 程度（key 平均 50 byte × 4096 件）。同時保持 live 数は実質 1（切替で reset するため）なので、常時 1 MB 以下。Bloom filter（10 万件 1% FP で 117 KiB）を使う必要はない。

4.参考実装（JavaScript / 純粋関数ファクトリ）

export function createNdgrMessageDedupe(opts = {}) {
  const perLiveMax = Number.isFinite(opts.perLiveMax) && opts.perLiveMax > 0
    ? Math.floor(opts.perLiveMax) : 4096;

  let currentLiveId = null;
  const buckets = new Map();
  const stats = {
    accepted: 0, droppedDuplicate: 0, evictedIds: 0,
    bucketsCreated: 0, bucketsCleared: 0,
    resets: 0, lastResetLiveId: null
  };

  function getOrCreateBucket(liveId) {
    let b = buckets.get(liveId);
    if (!b) {
      b = { ids: new Set(), fifo: [] };
      buckets.set(liveId, b);
      stats.bucketsCreated += 1;
    }
    return b;
  }

  function observe({ liveId, messageId }) {
    if (!messageId) return { accepted: true, reason: 'no-id' };
    if (!liveId)    return { accepted: true, reason: 'invalid-key' };

    const key = `${liveId}:${messageId}`;
    const b = getOrCreateBucket(liveId);

    if (b.ids.has(key)) {
      stats.droppedDuplicate += 1;
      return { accepted: false, reason: 'duplicate' };
    }

    b.ids.add(key);
    b.fifo.push(key);
    stats.accepted += 1;

    while (b.fifo.length > perLiveMax) {
      const oldKey = b.fifo.shift();
      b.ids.delete(oldKey);
      stats.evictedIds += 1;
    }
    return { accepted: true, reason: 'first-seen' };
  }

  function setCurrentLiveId(newLiveId) {
    if (currentLiveId !== null && currentLiveId !== newLiveId) {
      stats.bucketsCleared += buckets.size;
      buckets.clear();
      stats.resets += 1;
      stats.lastResetLiveId = currentLiveId;
    }
    currentLiveId = newLiveId;
  }

  function snapshot() {
    return { currentLiveId, currentBuckets: buckets.size, ...stats };
  }

  return { observe, setCurrentLiveId, snapshot };
}

完全実装: src/lib/ndgrMessageDedupe.js（vitest 10 件で first-seen / duplicate / no-id / invalid-key / FIFO eviction / live 切替 reset を網羅検証）

5.なぜこの設計なのか（7 原則）

本手法は、独立に行った 4 軸の調査（niconico 系 OSS 深読み・分散システム semantics・Bilibili scale + 中華圏 OSS・cross-platform 横断）が完全に同じ結論を出した 7 つの原則に従う:

1. ordering（順序保証）と dedupe（重複排除）の役割分離 ― 順序は commentNo、重複判定は messageId。Kafka / Kinesis / MQTT / gRPC で確立された原則。
2. dedupe は decode 直後 ― 上流に渡す前に弾く。Slack の「3 秒以内に同一 event_id が来たら無視せよ」、Discord の queue migration、Bilibili の ACK fast pattern すべてが同じ位置を指定。
3. canonical key = liveId + ":" + messageId ― C# 実装の segmentUri 単独では backward fetch / relay overlap に弱い。liveId 含めることで安全側に倒す。
4. bounded window ― FIFO perLiveMax = 4096 + 配信切替時 reset。TTL は保険、主制御は size cap。
5. replay は contract ― Kinesis 公式が「duplicate は発生する、consumer 側で dedupe せよ」、gRPC が「reconnect = 新しい購読」と明記しているとおり、replay は仕様であり例外ではない。
6. at-least-once + idempotency と明示 ― exactly-once は MQTT QoS 2 / Kafka transaction の state machine が無い限り主張できない。本手法は idempotency-by-key で実現する。
7. dedupe を運用メトリクス subsystem として扱う ― droppedDuplicate / evictedIds / resets 等を必ず観測層に出す。盲信せず、運用中に dedupe が「効きすぎ」「効かなさすぎ」を即検知できるようにする。

5-1. なぜ Bloom filter ではなく Set を使うのか

1 live あたり数千〜数万 message なら、Set ベースで perLiveMax = 4096 でメモリ余裕。Bloom filter は数十万〜数百万件のスケールで意味を持つ最適化で、本ケースでは false positive のリスクのほうがコスト。

5-2. なぜ Bilibili の fuzzy merge（類似コメント統合）を採用しないか

blivechat の mergeSimilarDanmaku は UI 機能としては有効だが、「保存層 dedupe の主方式」には不向き。Issue #143「合并相似弹幕導致卡住的問題」のように、merge ロジックが原因で UI が hang する事例が報告されている。「正確性 dedupe」（messageId）と「UX merge」（類似性）は別レイヤーで分離するのが堅実。

6.既知の限界と拡張可能性

• 主敵は dedupe 精度ではなく再接続境界 ― 中国系 OSS の運用 Issue では「reconnect ループ」「auth drift」「platform change」が圧倒的多数。dedupe 自体より再接続境界を堅くする方が ROI 高い。本手法は dedupe を完璧化する代わりに、replay を contract として受け入れる方針で再接続境界の単純化に貢献する。
• messageId が無いメッセージ ― no-id として通す fail-soft 設計。上流の messageId 設計が変わった場合に dedupe が完全停止しないよう、観測層に signal が出る。
• 同一 live 内で messageId が衝突する場合 ― 仕様上はあり得ないが、サーバ側のバグ等で衝突した場合は正しい message も drop する。観測層の droppedDuplicate の異常上昇で検知可能。
• 拡張: TTL ベースの window（Telegram MTProto の 300 秒上限と一致）を追加して、size cap と二重防衛にする。
• 拡張: checkpoint 永続化（chrome.storage.local に snapshot）。タブ再起動時の重複も防げる。
• 拡張: 類似コメ折りたたみ（blivechat の fuzzy merge 相当）を別レイヤーの popup UI 機能として実装。dedupe 主方式とは混ぜない。

7.関連する既知技術（先行技術）

7-1. Kafka KIP-98（exactly-once semantics）

producer 側 sequence number + transaction でグローバル exactly-once を実現。NDGR には producer 側仕様が無いため、本手法は consumer-side dedupe で at-least-once + idempotency に倒す。

7-2. Amazon Kinesis（duplicates ドキュメント）

「duplicate は発生する、consumer は dedupe を実装せよ」と明記。本手法と同じ at-least-once 仮定。

7-3. MQTT 5.0 QoS 2

4-way handshake で exactly-once を実現するが、broker / client 両側に state machine が必要で重い。NDGR は HTTP long-polling ベースなので採用不可。

7-4. Telegram MTProto

msg_id は 64-bit session 内一意・単調増加。300 秒より古い / 30 秒より未来は reject。本手法の bounded window 値（FIFO 4096）は実装上 5-15 分相当でこの慣行と一致。

7-5. Bilibili blivedm / blivechat

中国最大規模のライブ配信プロトコル（同時接続 100 万人級）。protocol ID 主キー + retry 窓のみ seen-set 保持。mergeSimilarDanmaku による fuzzy merge は別レイヤー（UI 統合）として実装され、保存層 dedupe とは混在させない設計。

7-6. NdgrClientSharp（niconico C# 実装）

本プロトコルの C# 系実装で、segment URI 単独を主キーに Dictionary<string, HashSet<string>> で dedupe する。backward fetch / relay overlap には弱い（segment URI が live を跨ぐと false dedupe）。本手法は liveId + ":" + messageId 化で改善。

8.本記事の位置づけ・ライセンス

本記事は、Chrome 拡張機能『君斗りんくの追憶のきらめき』内で 2026 年 5 月 10 日（バージョン 0.1.238 / 0.1.239）に投入された ndgrMessageDedupe.js モジュールの設計思想と実装を、2026 年 5 月 11 日付で公開するものである。

設計は 4 軸独立調査（Codex による niconico 系 OSS 深読み・分散システム semantics 全面調査・Bilibili scale + 中華圏 OSS 調査・cross-platform 横断調査）が完全一致した 7 原則ベース。先行技術として Kafka / Kinesis / MQTT / Telegram MTProto / Bilibili blivedm / Slack Events API 等を参照した。

参考実装は MIT、本記事文章は CC BY 4.0 のもとで自由に複製・引用可。