ハクソク

世界を動かす技術を、日本語で。

HNに聞いてみる: 実際にUUID v4の衝突が発生しました…

18時間前

概要

  • UUID v4の重複発生という極めて稀な現象
  • npmパッケージ「uuid」を利用した純粋なUUID生成
  • 15,000件中1件の衝突という統計的にほぼ不可能な事象
  • 原因の推測と一般的な再現性の有無
  • 対策や今後の注意点

UUID v4重複の事例とその不可解さ

  • UUID v4 は理論上、 重複の確率が極めて低い 識別子生成手法
  • 利用している npmパッケージ「uuid」 は広く使われる標準的実装
  • 15,000件程度のデータベース で1件のUUID重複が発生
  • 生成方法は import { v4 as uuidv4 } from "uuid"; const document_id = uuidv4(); のシンプルな呼び出し
  • UUIDの手動編集や加工は一切なし

UUID v4の重複確率と理論

  • UUID v4は 128ビット（約3.4×10^38通り） のランダム値
  • 15,000件程度での衝突確率 はほぼゼロ（誤差レベル）
  • 「誕生日のパラドックス」でも 10億件超で初めて現実的な衝突確率
  • 理論上、 この規模での衝突は「ありえない」 とされる

可能性のある原因

  • バグや実装ミス （パッケージ側、依存モジュール、乱数生成器の不具合）
  • 環境依存の問題 （OSレベルの乱数ソース不具合、仮想化・コンテナ環境のエントロピー不足）
  • キャッシュやプロセス間の状態共有 によるUUIDの再利用
  • 運用・デプロイ時の何らかの副作用 （例：UUID生成をラップしている自作コードのバグ）
  • npmパッケージのバージョン不整合 や古いバージョン利用

実際に同様の事例はあるのか

  • 世界的にも極めて稀な報告
    • GitHub issueやStack Overflowでも ほぼ前例なし
    • 一部、 乱数ソースの初期化失敗 や Dockerコンテナの複製 で似た現象の報告あり
  • npm「uuid」パッケージのissue で過去に乱数生成関連のバグ報告が存在

今後の対応・確認事項

  • uuidパッケージのバージョン確認 と最新版へのアップデート
  • 乱数ソースのエントロピー や システム依存性 の確認
  • UUID生成直後に重複チェック を一時的に導入
  • 同一タイムスタンプ/プロセス/初期化条件 での再現テスト
  • 同様の事象が継続する場合は、OSやNode.jsの乱数生成器の不具合も疑う

まとめ・今後の注意点

  • UUID v4の重複は理論上ほぼ不可能 だが、現実には「絶対」は存在しない
  • 乱数生成の信頼性 や パッケージの健全性 を常に監視
  • 再発時はシステム全体の乱数初期化や依存環境の見直し が必要
  • 万一の衝突検出ロジック を設けることで、予期せぬ事態への備えが可能

Hackerたちの意見

完全に同意だわ。意味が分からない。でも…考えられるのは、元々ユーザーのスマホでUUIDv4を生成してからデータベースに送ってたってことかな。今朝衝突したUUIDはUbuntuサーバーで作られたみたいだし。UUIDv4がどうやって生成されるのか、生成される機械の何がアルゴリズムに関係してるのかはよくわからないけど、思いつくのはそれだけだな。以前はユーザーのデバイスで生成してたのが、ここ数ヶ月でサーバーで生成するようになったってこと。

└

UUIDv4の衝突は統計的に見て非常にありえないことだよね。もっとありそうなのは、両方のシステムが同じシードを使ってたってこと。これがほんの数バイトの差で、衝突の確率が数十億分の1、あるいは数百万分の1に増えることもある。

└

ユーザーにUUIDを生成させてるの？正直言って、変なことやってる可能性の方が、実際にUUIDの衝突を経験する可能性より高いと思うよ。データベースはその衝突をどうやって「フラグ」立てたの？

└

あなたの具体的なセットアップでcrypto.jsが実際に何をしてるか、ちゃんと確認した方がいいよ。弱いポリフィルが存在するから…。

└

もし二つのデバイス上で生成されたUUIDだったら、衝突が起こるのも理解できる。安いエンドデバイスがランダム数生成器を正しくシードしてないことがあって、衝突する「ランダム」な値が出ることもあるし、適切な暗号学的RNGの代わりに安いRNGを使ってるライブラリもあって、さらに悪化することもある。でもサーバー上ではそんなことは起こるべきじゃない、特に2026年にはね（過去にはVMのRNGをシードするのがちょっと問題だったけど）。たとえ一つのUUIDが悪く生成されても、本当にランダムなUUIDがそれと衝突することは統計的にありえないよ。両方の生成器に問題がないと。

あなたが話してることは極めて稀なことだから、今すぐ地球が小惑星で壊滅する可能性の方が高いよ…。

└

小惑星が省略記号を打ってコメント追加ボタンをクリックするくらい稀だね。

└

UUIDの衝突が起きて、地球が小惑星に壊されるなんて、統計的に見てもさらに珍しいことだよね。

└

単一のデータベースでUUIDを使う場合は、確かに天文学的に稀だよ。でも、地球上のどのコンピュータシステムもUUIDの衝突を経験したことがないって言うのは全然違う話だよ。システムの数も天文学的だからね。

└

そんなに珍しいわけじゃないよ。計算したところ、隕石に当たるよりも少ない確率だってわかったし、UUIDに関するWikipediaの記事にそのことやバースデーパラドックスについてのセクションも追加したんだけど、数年前に削除されたり置き換えられちゃった。 （もし私の情報が正しければ、実際に隕石に当たった女性がいて、彼女は生き残ったけど、足に怪我をしたらしい。）UUIDの衝突が起きた場合、ほぼ確実にソフトウェアのバグかコンピュータのグリッチが原因だよ。宇宙線の影響かもしれないし、宇宙線がコンピュータのメモリやCPUに干渉するのは意外とよくあることなんだ。

└

スレッドで他の人が言ってたように、適切にシードしないとすごく一般的だよ！君の言い方だと、SFの密度の小惑星帯に囲まれている地球が衝突するくらい珍しいってことかな。

誰も信じないだろうけど、面白い話があるんだ。10年前、友達がスタートアップのCTOに就任したんだけど、その会社は急成長中で、開発者が200人くらいいたんだ。彼の初週に、新しいUUIDを生成するためのマイクロサービスがあることを発見したんだ。一つのエンドポイントに専任のエンジニアが3人いて、データベース担当もいた（話がややこしくなるね）。他のチームは「安全な」UUIDが必要なときはこのサービスを呼ぶように指示されてた。友達は「なんで？」って思ったら、このサービスには以前発行されたUUIDを保存するためのDBがあったんだ。リクエストはこう処理されてた：UUIDを生成して、自分のデータベースをチェックして新しく生成したUUIDが以前のUUIDと重複しないか「検証」してから、挿入してクライアントに返すって感じ。安心感があるのかな。チームは自分たちのカンバンボードとスプリントも持ってた。

└

いつの間にか、誰かがシステムをグローバル企業全体で使える128ビットのインクリメントカウンターに最適化したんだよね。成長するデータベースに対して高コストなデータベース検索をする代わりに、マイクロサービスは現在のカウンターを取得して、1を加算して新しい値を渡すだけ。これって簡単で速いO(1)の操作だよね。これにより、サービスをシャーディングして高可用性を提供したり、レイテンシを減らすためにサービスをグローバルに分散させたりできる。各インスタンスに専用のID範囲を与えればいいんだ。データセンターのIDを示すために高位ビットをいくつか予約して、さらにそのデータセンター内のIDジェネレーターインスタンス用にもう少しビットを使うことを提案するよ。ちょっと待って、これってどこかで見たことあるような…Twitterってまだこれやってるのかな、それとも最終的に切り替えたのかな？

└

似たようなことを、ある大手SVテック企業の中で見たことがあるよ。彼らのプロセスはもう少し複雑で、使用中のUUIDのマスターリストが別の部署が運営する外部CMDBサービスに保存されてたんだ。毎日そのデータベースのダンプを受け取ってたから、「仮」のIDを生成する際にチェックできたんだよね。「仮」のIDがCMDBに正しく提出されて初めて「確定」される仕組みだった。生産環境で「仮」のIDが使われないようにガードレールも設けてあったし、未使用の「確定」IDを再利用するプロセスもあった。あ、定期的に監査も行っていて、経営陣も真剣に受け止めてたよ。最後に聞いたときは、ローカルデータベースキャッシュをZookeeperに移すための6ヶ月プロジェクトに18ヶ月もかかってたみたい。

└

ふふ、UUID全体を保存する必要なんてないじゃん、ハッシュだけで十分だよ。バカだね。

└

信じられるよ。よく「UUIDの不運くじに当たることはあるのかな？」って考えてたし、これがMicrosoftのバージョン、つまりGUIDでも同じくらい一般的なのか気になるな。

└

2つの数字を足すサービスを持ってたんだ。これが現実的じゃないと思う理由は何なの？ :-)

└

信じられるな。でも、もっと信じがたいのは、「割り当てられたUUIDのリスト」だけの情報しかないテーブルじゃないってことだ。それだけだったら、かなり驚く（いい意味でね）。ほとんどのスタートアップは、そのテーブルが顧客情報にリンクしてることを確認すると思う。そうすれば、特定のUUIDを持つ顧客が誰か簡単に検索したり、メインDBと照合したりできるから。

└

マイクロサービスでそれを確保するのは分かるけど、3人も専任でいるの？彼らはダンジョンを探索したり、CoDや卓球をして過ごしてたに違いないよ。

└

前の職場では、createEntityWithRandomUUIDという関数があって、基本的にはデータベースへの挿入を軽くラップするだけのものだった。もし衝突が起きたら、新しいIDを生成して再試行するんだけど、確か5回までだったかな。衝突が実際に起きたかどうかを示すログはなかったよ。

└

自分専用の3人のエンジニアがいるエンドポイント > チームは自分たちのカンバンボードとスプリントを持ってた。私の初期の仕事はリソースが限られたスタートアップだったから、何かを作るとか誰かを雇うっていう決断は、慎重に考えた上で行われてた。この話は当時の私にはフィクションに思えた。キャリアの後半で、こういうスタートアップに参加したけど、誰かが思いつく新しい懸念がすぐに新しいマイクロサービスになって、新しいチームを作るために新しい人を雇うことになってた。どんなに小さなことでも、新しい人を雇って新しいチームを作る理由になってた。四半期の目標がエンジニアリングチームを成長させることだって会議で伝えられたこともあった。変な時代だったよ。3〜4人のチームがそれぞれスプリントや計画セッションを持って、自分たちの仕事を増やす方法を考えてた。中には、スプリント全体を小さな変更に費やすほど遅いチームもいたし、些細な問題に対して過剰に設計された解決策を作ってるチームもあった。ある会議では、安定したプロジェクトにいる人たちを急ぎの仕事に再配置することを提案したけど、却下された。それは新しい人を雇う理由を減らすことになるから、誰かのKPIと衝突することになってたんだ。

└

彼らがDBに一定数のUUIDを「事前生成」して、メモリに保存してDBの遅延を減らし、割り当てが行われたらDBに記録することで、全プロセスを自動化できると思うんだけどね。そして、マイクロサービスは他の既知のエンドポイントからの割り当てリクエストだけを受け付けるように簡単に作れるはずだよ。

RNGの初期化に何か問題があるのかな？エントロピーが足りない？カスタマイズされていないRNGはこうなるよ: const rnds8 = new Uint8Array(16); export default function rng() { return crypto.getRandomValues(rnds8); } getRandomValuesはエントロピーの最小量を指定してないからね。

└

RNGに何か大きな問題があるのはほぼ確実だし、そう、種の生成方法に問題があるんだろうね。暗号にも影響が出てるかも。

これは意外とよくあることなんだ。UUIDv4のセキュリティは、高品質なエントロピーソースがあるという前提に基づいているんだけど、この前提はハードウェアの欠陥や普通のソフトウェアバグ、開発者が「高品質なエントロピー」の意味を理解していないことによって無効化されるんだ。UUIDv4が広告通りに機能するためにはそれが必要なんだけど、エントロピーソースが壊れていることを検出するのは比較的高コストだから、ほとんど誰もやらないんだよね。衝突が起きたときに初めて気づくってわけ。だから、UUIDv4は多くの高信頼性・高保証のソフトウェアシステムでは明示的に禁止されているんだ。

└

視点を教えてくれてありがとう！UUIDv4の代わりに高信頼性システムで使われている代替案について詳しく教えてくれない？

└

UUIDv4がエントロピーの壊れたソースのせいだってどういうこと？それとも私があなたの言葉を誤解してる？

└

これがCloudFlareがラバランプの壁を作った理由なんだ。壁自体がエントロピーの素晴らしいソースってわけじゃないけど、他にもソースがあるはずだし、エントロピーのソースは多ければ多いほどいいからね。RNGの概念やエントロピーの役割を完全には理解していない人にも目に見える形で示すことができるんだ。エントロピーのソースが多いほど、「完璧な」ランダム化に近づくよ。そして、そのエントロピーのソースの大部分は非決定論的である必要がある。ローカルシステムで動くローカルアプリケーション、例えばゲームなんかでも、マウスの座標やボタンを押す間のタイミング、プレイヤーがスタートを押す前のゲーム開始からの正確なフレーム数などを使って、PRNGの裏側を使いながらランダム性を大きく高めることができるんだ。そう、後者は技術的には決定論的なんだけど（古いゲームほど決定論的になるし、古いゲームのTASプレイが「RNG」を打ち砕くのを見てみて）。でも、初期シードに50個の異なるパラメータが入っているとしたら、攻撃者はその50個を完璧に予測したり再生したりしなきゃいけない（再生攻撃を避けるための他の方法も重ねて使えるし）。CloudFlareが100個未満の異なるエントロピーソースしか持っていなかったら、ちょっとがっかりするだろうね。それは、彼らのエントロピーソースを一つのシード値にブレンドするアルゴリズムが良いと仮定した場合だけど。

└

超簡単に検出できるし、やり直すだけだよ。

└

[遅延]

この面白い記事を再読するのにいいタイミングだね: https://jasonfantl.com/posts/Universal-Unique-IDs/ もし宇宙全体が巨大なコンピュータに変わって、熱的死を迎えるまでUUIDを生成し続けたら、IDスペースには何ビット必要になるんだろう？

└

そこまで行くなら、これが必須だよね。https://www.decisionproblem.com/paperclips/

ここでちょっと議論があるよ: https://github.com/uuidjs/uuid/issues/546 例: > ちなみに、googlebotでcrypto.getRandomValues()の挙動をテストしたけど、これも決定論的だったよ！

UUIDはクライアント側で生成してるの、それともサーバー側？もしクライアント側なら、クローリングボットのせいかもね。例えば、Googlebotは決定論的な「ランダム性」を使ってJavaScriptを実行するから。

これは通常、十分にシードされていないPRNGが原因だよ。UUIDはバックエンドで生成してるの、それともフロントエンド？フロントエンドは多くの理由から根本的に信頼性が低いし、意図的な衝突もあるからね。だから、その場合は衝突を何とか処理する必要があるよ。一般的な衝突の原因を回避することはできるけど、具体的な内容は環境による。一方、バックエンドを信頼性のあるものにするのは可能だよ。君のコードはどんな環境で動いてるの？歴史的には、VMがこの問題に悩まされることもあったけど、今は解決されてるはず。厳重にサンドボックスされたプロセスでも、RNGライブラリが安全でないフォールバックを使っていると、まだこの問題に直面することがあるかも。プロセスやVMをフォークすると、状態の重複が起こって衝突が発生することもある。

これ、"Pro Git"って本の一節を思い出すな。 「SHA-1の衝突を得るために何が必要かを示す例を挙げるね。地球上の65億人全員がプログラミングをしていて、毎秒それぞれがLinuxカーネルの歴史に相当するコード（650万のGitオブジェクト）を生成して、巨大なGitリポジトリにプッシュしていたとしたら、そのリポジトリに50%の確率で1つのSHA-1オブジェクトの衝突が発生するまでに約2年かかる。だから、オーガニックなSHA-1の衝突は、プログラミングチームのメンバー全員が同じ夜に無関係な事件でオオカミに襲われて殺されるよりも可能性が低いんだ。」意図的な衝突については次の段落で触れられているよ。SHA-1ハッシュはランダムじゃないから、uuidv4のように擬似乱数生成の問題は当てはまらないし、SHA-1ハッシュは160ビットで、uuidv4は128ビットなんだ。でも、無関係なオオカミの襲撃ってアイデアは好きだな。