Ask HN: 実際に UUID v4 の衝突を経験しました…

 (news.ycombinator.com)
1 ポイント 投稿者 GN⁺ 2 시간 전 | 1件のコメント | WhatsAppで共有
  • データベースが今日、重複した UUID v4 を検出し、既存の値は2025年に追加されたレコードの b6133fd6-70fe-4fe3-bed6-8ca8fc9386cd と完全に同一だったとのこと
  • 使用しているパッケージは npm の uuid で、import { v4 as uuidv4 } from "uuid"; の後に const document_id = uuidv4(); で生成してデータベースに保存する方式だという
  • データベースには約 15,000件のレコード しかなく、統計的にはあり得ないように見えるが、同じことを経験した人がいるか尋ねている

関連記事

1件のコメント

 
GN⁺ 2 시간 전
Hacker Newsのコメント

  • jandrewrogers: これは意外とよくある。UUIDv4の安全性は高品質なエントロピー源があるという前提に依存しているが、ハードウェア障害、ありふれたソフトウェアバグ、開発者のエントロピー理解不足によって、この前提は簡単に崩れる。
    エントロピー源が壊れていることを検知するのはかなりコストが高いので、ほとんど誰もやらず、結局は衝突が起きてから初めて気づく。だから高信頼・高保証のシステムではUUIDv4が明示的に禁止されていることも多い

    • LocalH: だからCloudFlareはラバランプの壁みたいなものを作ったわけだ。それ自体がものすごいエントロピー源というより、乱数生成やエントロピーの概念をよく知らない人にも、目に見える形で理解させる効果がある。
      エントロピー源は多ければ多いほどよく、そのかなりの部分は非決定的であるべきだ。小規模なゲームでも、マウス座標、ボタン入力間隔、開始ボタンを押す前のフレーム数のような値を初期シードに混ぜれば、内部で疑似乱数生成器を使っていても予測はかなり難しくなる。CloudFlareがエントロピー源を100個未満しか使っていないなら失望すると思う
    • Groxx: 不良ハードウェアでそれらしい重複を見たことがある。それに一部のUUIDライブラリでは、後ろ側が0で大量に埋まる重複パターンも非常によくあった。
      昔のGo界隈みたいに「Nバイト要求したが3バイトしか返らなかったので、N-3バイトを再要求しなければならない」という戻り値を検証しないと起きる。ほとんどのハードウェアやOSでは問題にならないので、みんな確認せず、ある日になって本番環境で数万件の衝突として表面化する
    • thecloud: 高信頼システムではUUIDv4の代わりに何を使っているのか気になる

  • throwaway_19sz: 信じがたい笑い話みたいだが本当の話。10年前、友人が急成長中のスタートアップのCTOとして加わったのだが、開発者が200人ほどいる会社で、最初の週にUUID生成専用マイクロサービスがあることを発見した。
    単一のエンドポイントに専任エンジニア3人、しかもDB担当までいた。新しい「安全な」UUIDが必要になると、全チームがこのサービスを呼び出さなければならず、このサービスはUUIDを生成したあと、自前のDBに既発行UUIDがあるか確認し、なければ挿入して返していた。安心感のためだったのか、そのチームは専用のカンバンボードとスプリントまで回していた

    • Aurornis: 初期の頃はリソースが限られたスタートアップで働いていて、何かを作るにしても人を採るにしても慎重に決めていた。当時ならこの話は作り話に見えただろう。
      その後に入ったスタートアップでは、誰かが新しい心配事を思いつくたびに新しいマイクロサービスと新しいチームが生まれていた。四半期目標にエンジニアリングチームの規模拡大が明示されており、3〜4人のチームが自分たちのスプリントと計画会議の中で自分たちの仕事を作り出していた。安定しているプロジェクトの人員を急ぎの案件に回そうと提案したが、エンジニア数を特定の数字まで増やすKPIに反するとして止められた
    • wongarsu: そのうち全社共通の128ビット増分カウンタに最適化する人が現れそうだ。肥大化するDBを引かずに現在のカウンタを取得して1増やして配るだけならO(1)で速い。
      高可用性とグローバル展開のために各インスタンスへ専用のID範囲を割り当てればシャーディングもできる。上位ビットの一部をデータセンターIDに、さらに数ビットをその中のID生成インスタンスに予約すればいい。あれ、これどこかで見た気がする……。Twitterがまだこの方式を使っているのか、結局変えたのか気になる
    • roryirvine: 大手シリコンバレーの技術企業の奥深くで似たようなものを見たことがある。ただ、使用中のUUIDのマスターリストが別部署の運用する外部CMDBサービスにあって、手順はもっと複雑だった。
      毎日DBダンプを受け取って「暫定」ID生成時に確認し、CMDBへ正しく提出されて初めて「確定」状態になった。暫定IDが本番で使われないようなガードレールもあり、未使用の確定IDを再利用する手順まであった。最後に聞いた時点では、ローカルDBキャッシュをZookeeperへ移す6か月計画のプロジェクトを18か月目にやっていた

  • CodesInChaos: たいていはシード不足の疑似乱数生成器が原因。UUIDをバックエンドで作ったのかフロントエンドで作ったのかが重要だ。
    フロントエンドは意図的な衝突も含め、さまざまな理由で根本的に信頼しづらいので衝突処理が必要になる。バックエンドなら安定して作れる。昔はVMでこういう問題があったが、今どきは解決されているはずで、強くサンドボックス化されたプロセスが安全でない代替乱数経路を使うと今でも起こりうる。プロセスやVMのforkも状態複製による衝突を生むことがある

    • danpalmer: Segmentという分析会社が、Webブラウザで生成されたUUIDに製品全体を依存させていたという話を聞いたことがある。あちこちでブラウザUUID衝突が起きていて、製品が根本的に有用なデータを作れない状態だったようだ。今は直っていることを願う

  • kst: “Pro Git”の一節を思い出した。 <https://git-scm.com/book/en/v2>
    地球上の65億人全員が毎秒Linuxカーネル全履歴規模のコードを作って巨大なGitリポジトリ1つにpushしたとしても、SHA-1オブジェクト衝突の確率が50%になるまでにはおよそ2年かかる、という例だった。だから自然発生のSHA-1衝突は、チーム全員が同じ夜に互いに無関係なオオカミの襲撃で死ぬ確率より低い、という表現が気に入っていた。SHA-1ハッシュは乱数ではなく160ビットなのでUUIDv4とは違うが、無関係なオオカミの襲撃というたとえは好きだ

    • mega_dean: トランプ1組のシャッフル順列がどれだけ巨大かを説明するこのページを思い出した: https://czep.net/weblog/52cards.html
      赤道上を10億年に1歩で地球一周し、1周ごとに太平洋から水滴を1滴抜き、海が空いたら紙を1枚積み、その過程を太陽に届くまで繰り返しても、52!秒タイマーの先頭3桁は変わらない、というたとえだ
    • swiftcoder: 一方で辞書攻撃はかなり現実的で、そのテストケース用ファイルを何も考えずにGitへコミットした人たちが証言する通り、かなり面倒だ
    • TacticalCoder: GitチームはSHA-1に加えてSHA256のような別ハッシュをオプションで提供しようと懸命に作業していなかったっけ？

  • e12e: 関連する議論がここにある: https://github.com/uuidjs/uuid/issues/546
    たとえば crypto.getRandomValues() をgooglebotでテストしたところ、決定的だったという話がある

    • D2OQZG8l5BI1S06: それはありえる。ただ、そもそもなぜブラウザでUUIDを生成するのか分からない。目的そのものを損なっているように見える

  • adyavanapalli: 今話していることはあまりに稀で、この瞬間に地球全体が小惑星で破壊される可能性のほうが高いくらいだ

    • thomasmg: そこまで稀ではない。計算してみたら隕石に当たるよりは珍しかったので、その話と誕生日問題をWikipediaのUUID記事に追加したことがある。数年前に削除・差し替えられたが。
      実際に隕石に当たりながら脚の怪我だけで生き延びた女性がいたと聞いた。UUID衝突が起きたなら、ソフトウェアバグかコンピュータ異常である可能性が圧倒的に高く、宇宙線かもしれない。宇宙線がメモリやCPUに影響するのは思ったよりよくある
    • delichon: 小惑星が三点リーダを打ってコメント追加ボタンを押すくらいの確率だ
    • spindump8930: 他の人も言っているように、シードを誤るとかなりよく起こる。たとえるなら、地球がSFに出てくるような高密度小惑星帯に囲まれているときに当たる確率くらいだ

  • juancn: 乱数生成器の初期化がおかしいか、エントロピー不足ではないか？ カスタマイズしていないなら crypto.getRandomValues(rnds8) を使っているはずだが、getRandomValues は最小エントロピー量を明示していない

    • Hizonner: 乱数生成器がひどく壊れていた可能性がほぼ確実で、おそらくシード処理の問題だろう。暗号化も一緒に壊している可能性が高い

  • Geee: 量子力学の多世界解釈によれば、すべてのUUIDが同じ宇宙分岐が1つくらいあってもおかしくない。その世界の人たちが何を考えているのか想像してしまう

    • suprjami: たぶん「そのUUID」を作ったあと、末尾に増分する数字を付けて一意にするだろう。問題解決
    • BobaFloutist: それだけでなく、UUIDが1つを除いてすべて同じ宇宙のほうがずっと多いはずだ。ただその1つまで使えなかっただけかもしれない。あるいは最初の2つだけが一意で、その後の全UUIDがその2つのどちらかになる宇宙もある
    • nyantaro1: だからEverett流のアプローチはあまり好きではない

  • mittermayr: ありえないという意見には完全に同意する。それでも推測するなら、以前はユーザーの携帯電話でUUIDv4を生成してDBへ送っていて、今朝衝突したUUIDはUbuntuサーバーで生成された、という違いがある。
    UUIDv4がどう生成されるのか、生成マシンの特性がアルゴリズムに入るのかは分からないが、唯一思い当たる変化は、以前は端末で作っていたのを数か月前からサーバーで作るようになったことだ

    • AntiUSAbah: ユーザーにUUIDを生成させていたのか？ 正直、本物のUUID衝突よりも何か妙な実装をしていた可能性のほうが高そうだ。DBがその衝突をどう示したのか気になる
    • wongarsu: 両方とも端末で生成したUUIDなら衝突の可能性は理解できる。低価格端末では乱数生成器のシードが正しく取れず、「ランダム」値が衝突した例があったし、ライブラリが適切な暗号学的乱数生成器の代わりに安価な乱数生成器を使っていればさらに悪化する。
      ただしサーバー側で、特に2026年にそれはあってはならない。昔はVMの乱数シードが問題だったが、今はもっと少ないはずだ。片方のUUIDが悪く生成されたとしても、本当にランダムなUUIDがそれと衝突する確率は非常に低いので、両方の生成器に問題がある必要がある
    • stubish: UUIDv4衝突は統計的に極端に稀だ。もっとありそうなのは、2つのシステムが同じシードを使っていたことだ。シードが数バイトしかなければ、衝突確率は数十億分の1や数百万分の1まで上がる

  • dweez: この面白い記事をまた読む時だ: https://jasonfantl.com/posts/Universal-Unique-IDs/
    宇宙全体を巨大なコンピュータに変えて熱的死までUUIDだけを生成するとしたら、ID空間には何ビット必要か？

    • CodeWriter23: そこまで行くなら、これも必須だ: https://www.decisionproblem.com/paperclips/
    • ipaddr: 「今、地球上のすべての人間が隕石に当たる心配をするか？」という例えはあまりよくないかもしれない。隕石1つで世界が終わる可能性もあるし、十分な時間があればその可能性は高くなる

  • beejiu: UUIDをクライアント側で生成しているのかサーバー側で生成しているのか気になる。クライアント側ならクローラーボットが原因かもしれない。たとえばGooglebotは決定的な「ランダム性」でJavaScriptを実行する

    • adzm: そのパッケージの以前の事故でも、Googlebotの乱数不足が結論だった: https://github.com/uuidjs/uuid/issues/546
    • AgentME: ほぼ確実にこのケースか、システム乱数生成器を正しく使えないパッケージの古い版を使っていたか、JS crypto APIを再実装した古くて壊れたポリフィルを読み込んでいたか、同一のVMスナップショットを複数サーバーで再開して乱数状態が複製されるような奇妙なホスティング構成だった可能性が高い。
      こういう説明のほうが、本当にランダムな衝突より何桁ももっとありそうだ

  • merlindru: シード問題の可能性が高い。そうでないと証明できたら、少し有名になれるかもしれない

  • erlkonig: データが十分多ければランダム値はいずれ衝突しうるし、そのときにソフトウェアがどれだけ堅牢かが分かる、とずっとチームに言ってきた。
    それでも、経験豊富な開発者、チームリード、CIOの中にも不可能だと信じて、その状況を処理するコードをまったく書かない人が多い。すると質の悪い乱数生成器が、いつでも想定よりはるかに早くシステムを壊せるし、検知や再生成なしで同時破損も起こりうる。malloc() の成功確認をしない類と同じに見える。「不可能なら、そんなに多くのビットを使う必要はないのでは？」とよく聞く

  • leni536: 偶然に起きたのではなく、どこかにバグがある。ざっと見た限り、パッケージはJSランタイムの crypto.randomUUID() を呼んでいるようで、これは常に適切にシードされているべきだ。
    ランタイムにバグがある可能性は極めて低そうだが、絶対ではない。どのJSランタイムを使っているのか気になる

  • jbverschoor: もっともありそうな原因は、uuid パッケージが依存する乱数生成パッケージが最近侵害されて、「ランダム」な数字を予測可能にされたことだ。その結果、サプライチェーン攻撃によって多くの暗号化、SSL、通貨関連プロジェクトが危険にさらされているかもしれない

    • jbverschoor: 3週間前に変わった uuid/src/rng.ts では、乱数配列が const になっていた。すべての呼び出しが同じ乱数配列を共有するようになる。
      その後の呼び出しが以前の乱数コードを更新するので、重要なものを生成していたなら無事を祈るしかない。以前のコードは slice() で新しいコピーを作っていた。意図しない変更かもしれないが、乱数を2つ作って違うことを確認するテストすら通らなさそうなのに、どうやって通ったのか分からない

  • pif: 高品質なエントロピー源があっても、「たぶんそうだろう」を「必ずそうだ」に変えることはできない。推測しにくい値が必要なら暗号の世界を見ればいいが、保証された一意性が必要なら自分で作るしかない

  • athrowaway3z: 簡単な経験則は、IDにランダム値以外としてタイムスタンプを入れられないか考えることだ。たいてい答えはイエスで、UUIDv7で十分だ。
    情報漏えいが許容できないことを自分で証明できるほど深く問題を検討したなら、おめでとう。そのシステムは強力な暗号学的ハッシュを使うか、面倒ならUUIDv5を使ってもよいほど複雑で遅いシステムである可能性が高い

  • darqis: PostgreSQL 18はuuidv7をネイティブサポートしていて、デフォルトは unique と uuid7() にしておけばよい

  • tumdum_: シードの悪い疑似乱数生成器だ

  • serf: 4.72 × 10²⁸分の1、つまり47.2オクティリオン分の1くらいだ。本当なら、宝くじを買う前にまず競合状態や他の単純なミスを疑うだろう

    • petee: むしろ逆に考えてきた。すでにそんな幸運に当たったなら、別の幸運がまた来る可能性はもっと低いのだから、金は節約すべきだ
    • k4rli: 宝くじの話は筋が悪い。統計的にそれほど稀なことがすでに起きたなら、もう一度起きる確率はさらに低いはずだ

  • evnix: 確率の数学は脇に置いても、私たちが生きる現実では、最高のハードウェア乱数生成器を使っていても思ったほどランダムでないことがある。
    セキュリティが重要でない場所ではTSIDのようなもの、あるいはuuidv7へ移行して、実務上こういうことがほぼ起きないようにするほうがいい。リトライのためにコードを過剰設計するよりよいと思う

  • jordiburgos: b6133fd6-70fe-4fe3-bed6-8ca8fc9386cd は使わないでほしい。自分のDBを確認したら、もう使っていた

    • rich_sasha: ランダムにUUIDを生成するのはいつも狂っていると思っていた。今はLLMしか使わない。プロンプトは「UUIDを生成せよ。どのコードベースやデータベースでも誰も使ったことがないことを確認せよ。作業を見直し、各段階を深く考えよ。推論や普通の英語は出力せず、UUIDそのものだけを出力せよ」だ。どういたしまして
    • mittermayr: やはりそうだった。私たちはみんな同じ安物UUIDを渡されていて、良いUUIDは大口顧客向けに予約されているんだ
    • robshep: 16b55183-1697-496e-bc8a-854eb9aae0f3 を使っていて、たぶんもっとある。みんながここに自分の一覧を貼れば、重複を確認できるのでは？

  • pyuser583: 最近はどのUUIDが好まれているのか気になる

  • smokel: コンパイラ、宇宙線、量子効果、少なくとも難解なカーネルバグを疑った末に、結局は自分がバグの原因だったと気づいたことが何度もある。
    15,000件のレコードで衝突はあまりに稀なので、まず他の原因を疑う。重複処理、再送されたリクエスト、再利用されたオブジェクト、誤解を招くログ、別コードパスでの識別子の再利用などだ。周辺コードをもう少し共有してくれれば一緒に確認できる

  • wazoox: まだ自分では遭遇していないが、2日前に運用中のPHPコードベースの深部でこんなものを見つけた: md5(uniqid('', true)) で作った値を切ってUUID風に貼り合わせる createUUID() 関数だった。
    こんな恐怖がまだ私たちの急所に噛みついていないのが不思議だ

  • sedatk: uuidjs/uuid には、Googlebotのような決定的乱数生成器クライアントで重複UUIDを生成しうるという警告がある。
    クライアント生成UUIDが常に一意だと期待するアプリでは問題になりうるので、重複を確認して適切に失敗させるか、Googlebotクライアントからの書き込み操作を無効化する戦略が必要だと書かれている: https://github.com/uuidjs/uuid/commit/91805f665c38b691ac2cbd...

  • xyzzy123: Linuxベースの分散システムで、長時間の負荷テストが重複UUIDのせいで失敗したことがある。
    長く調べた結果、カーネルバグ、正確には競合状態が原因だった。マルチプロセッサ環境で2つのプロセスが同時に /dev/random を読むと、ごく稀に、およそ100万分の1程度で同じバイトを受け取ることがあった。まず乱数生成器の初期化を見ると思う

  • baq: 実行中のVMがエントロピーをすべて仮想化で吹き飛ばしたように思える

  • glaslong: ラバランプを何個か買わないといけない

  • 0xfffafaCrash: UUIDがフロントエンドで生成されたのかバックエンドで生成されたのか気になる。フロントエンドなら、エントロピー問題よりもクライアントコードやリクエストが改ざんされて既知のUUIDが注入された可能性に賭ける

  • latentframe: エンジニアリングで最も危険な言葉の1つが統計的に不可能だ。規模が十分大きくなれば、極端な事例は理論ではなく運用イベントになる

  • 8organicbits: 去年、実際の衝突とそのライブラリまで含めて記事を書いたことがある: https://alexsci.com/blog/uuid-oops/
    UUIDが衝突耐性を持つためには厳密に守るべき制約が多く、今回の件は乱数生成器に問題がある可能性が高そうだ

  • nu11ptr: 結局はエントロピー源の問題だ。だから私はいつもループ内で生成して挿入する。衝突したら適切に処理できる

  • sbuttgereit: 「技術的に不可能」ではない。むしろ非常に技術的に可能だ。良いランダム性があれば極めて、極めて稀というだけで、UUIDv4が重複値を生成することを技術的に防ぐものはない

  • beardyw: 間抜けな質問かもしれないが、日付を16進数の秒単位でも付けられないのか？ 数バイト追加するだけで、今うまくいっているものを将来も大丈夫だと保証できそうに思えるのだが

    • flohofwoe: タイムスタンプデータを含む別のUUIDバリアントを使えばいい。たとえばv1やv7があり、MACアドレスを含むバリアントもある
    • itsyonas: ただuuidv7を使えばいい
    • mittermayr: その通りで、何らかの追加の準ランダムデータでもこういう事態を防ぐ助けになったはずだ。ただ、それがUUIDv4の発想でもある。すでに十分なランダム性と時間が入っていると思っていた

  • mdavid626: 別の説明もありうる。たとえば誰かがリクエストを手動でいじったとか、DBをいじったとかだ

  • radial_symmetry: 私も一度こういうことを経験して、自分が気が狂い始めたのかと思ったが、ここのコメントを読んで安心した

  • NKosmatos: 「技術的に不可能」ではない。不可能なのではなく、非常に、非常に稀なだけだ。宝くじやPowerballを買ってみるべきかもしれない。
    “improbable” という言葉を見るたびに https://hitchhikers.fandom.com/wiki/Infinite_Improbability_D... を思い出す

    • sebazzz: 実際には宝くじは買うべきではない。その衝突と宝くじ当選の両方が起きるのはさらに珍しい
    • rithdmc: 想像もつかない話だ

  • sudb: 自分のプロジェクトの1つでCUID2を選んだのは、実際に良い判断だったのだと初めて実感した: https://github.com/paralleldrive/cuid2