ナノ秒タイムスタンプの衝突はよくある
(evanjones.ca)- 複数の物理コアが同時にクロックを読む最新システムでは、ナノ秒タイムスタンプでも簡単に重複し、4つの物理コアで同時測定した場合、全サンプルの約5%で衝突が発生
- 生のタイムスタンプを一意識別子のように使う設計は危険であり、衝突頻度はOSや実行方法によって変わる
- Goの
time.Now()は絶対時刻と単調クロック基準の相対時刻をあわせて記録するため、連続呼び出し間の差分と絶対タイムスタンプの重複を分けて確認できる - Linuxのシングルスレッドでは時間は常に増加し、最小増分は32nsだったが、スレッドが分かれると同じ絶対時刻が観測された
- Mac OS Xは絶対時刻がマイクロ秒解像度のため衝突がはるかに多く、シングルスレッドでも単調クロックが増加しないケースが頻繁に見られた
同時読み取りで明らかになった衝突頻度
- 核心となる問いは、最新システムでナノ秒タイムスタンプの衝突が実際にどれほど頻繁に起きるのかという点
- 4つの物理コアで同時にクロックを読むと、全サンプルの約**5%**で衝突が発生
- 4コアシステムでスレッドを2本だけ使っても、約**2%**のタイムスタンプが重複
- したがって、生のナノ秒タイムスタンプだけで一意IDを作れると仮定するのは安全ではない
テスト方法とOSごとの差
- テストプログラム はGoで書かれている
- Goの
time.Now()は呼び出しごとに絶対時刻と単調クロック基準の相対時刻を記録する- テストでは連続するタイムスタンプ間の相対差を比較
- 絶対タイムスタンプ自体の重複もあわせて確認
-
Linux
- シングルスレッドでは絶対時刻と単調時刻は常に増加
- 測定システムでの最小増分は32nsだった
- スレッド間では、絶対時刻が別スレッドと完全に同じになるケースが約**5%**発生
-
Mac OS X
- 絶対時刻はマイクロ秒解像度のため、同じテストでも衝突が非常に多く発生
- シングルスレッドでも単調クロックが増加しないケースが頻繁に観測された
1件のコメント
Hacker News のコメント
時間要素と連番を組み合わせた ID を使うのが、こうした問題を避ける方法です
たとえば UUIDv7 にはミリ秒単位の時間要素があり、同じミリ秒内のイベントごとに増加するフィールドがあり、異なるマシンで生成された ID 同士が衝突する確率を天文学的に低くするだけのランダムビットもあります
もちろんビット数は有限なので、同じ時間区間にイベントが多すぎると連番があふれることがあり、マシン間の衝突も実際に起こりえますし、インクリメント処理のために CPU の同期が必要になってイベント生成速度が制限される可能性もあります
それでも実務上の規模では UUIDv7 は非常によく機能します
UUIDv7 がどれくらい古いものなのか、ネットではうまく見つけられません
UUID 内のビットを消費するだけで、エントロピーにはあまり寄与しません
まだ本体には入っていませんが、アプリケーションレベルで直接使う以外にも uuidv7 を提供する優れた pg 拡張がいくつもあります
理解しにくいというレベルを超えて、目視で互いに区別することさえ非常に困難です
そのため、場合によっては必要最小限の情報以外に情報やノイズをまったく入れない 識別子 が有用です
何らかの形のオーバーフローするインクリメントカウンターと少しのランダムビットがあれば大抵は十分で、うまく実装すればどちらも分岐なしで可能です
関連して、以前 Windows の セキュリティイベントログ を担当するプログラムマネージャーでした
マルチコアシステムで物事が同時、または非常に近い時刻に起こると、スレッドスケジューリングが観測結果に大きく影響することがあります
たとえばタイムスタンプを取得するシステムコールに到達する前や、後でタイムスタンプを付けるためにイベントをキューに入れるバッファを渡す前に、スレッドクォンタムが終了することがあります
実際、2000年代の Windows のマルチプロセッサシステムでは、イベントログ項目が 順序入れ替わって 見えることは非常によくあり、ログのタイムスタンプ精度もあまり細かく信用できませんでした
安全な下限は事実上1秒で、一部のコンポーネントはタイムスタンプを切り捨てたり丸めたりしていたと記憶しています
一意な識別子が必要なら バージョン4 UUID、つまりランダム UUID を使えば十分です
衝突確率は、量子ゆらぎによって成長しきった恐竜が寝室に突然現れる確率と同じくらいです
もう少し真面目に言うと、使えるなら昔ながらの増加値がおそらく最善です
高速で安価ですし、特にデータベースではなおさらですが、ID 値から情報を推測できてしまう プライバシー・セキュリティ上の問題 があります
そういう場合や分散システムを扱う場合は UUID のほうが適しています
解像度がナノ秒だとしても、実際のコンピューターの時計の 精度 はどの程度なのか気になります
実際にナノ秒レベルだとは想像しにくく、物理実験の授業で、測定装置が表示する最小の数字と正確さは同じではないと学生に繰り返し強調していた頃を思い出します
ただし、そのレベルで 正確 だという意味ではなく、マルチコアシステムではコア間の時計がその程度のレベルで同期されていないこともあります
ARMv8 は時計が少なくとも 1GHz で増加することを保証していますが、Intel と以前の ARM はもっと複雑です
Erlang/Elixir の BEAM VM は、この違いを非常に明確に示している。単調増加と厳密な単調増加の区別である
https://www.erlang.org/doc/apps/erts/time_correction.html#mo...
「単調増加する値のシーケンスでは、先行する値があるすべての値は、その先行する値以上である」
これは https://www.erlang.org/doc/man/erlang.html#monotonic_time-0 関数で利用できる
https://www.erlang.org/doc/apps/erts/time_correction.html#st...
「厳密に単調増加する値のシーケンスでは、先行する値があるすべての値は、その先行する値より大きい」
厳密な単調値は何らかの同期や調整を意味し、同時プロセスが多い場合には性能コストを伴う
この機能は https://www.erlang.org/doc/man/erlang.html#unique_integer-1 関数で提供されており、ドキュメントでも、厳密に単調増加する値は本質的に生成コストが高くスケールしにくいので、本当に必要な場合にだけ
monotonic修飾子を渡すよう警告している言い換えると、UUIDv1 や https://en.wikipedia.org/wiki/Snowflake_ID に似ている
即時一貫性のある first/last write wins が必要な場合にだけ、厳密な単調グローバル識別子が本当に必要になる
代わりに結果整合的な first/last write wins を使えるなら、たとえば書き込みイベントが ID で線形化されるイベントストアやキューに入り、「同時」書き込みのうち ID 優先度が最も高いものだけを残して、処理中または読み取り時に捨てられるなら、まずは圧縮された
(nodeID, seq)ペアを検討するだろうグローバルなイベント順序付けが必要なら、特に Snowflake ID 形式の
(timestampMajor, nodeID, timestampMinor, seq)を検討する価値があるFreeBSD には
CLOCK_MONOTONIC_RAWがないのでコメントアウトしたところ、問題なさそうに見える衝突があるなら一部のタイムスタンプが繰り返されるはずだと理解していたが、衝突を作れない
clock_getres(CLOCK_REALTIME, ...)=1 ns、clock_getres(CLOCK_MONOTONIC, ...)=1 nsと出ており、30個のサンプルでも差分はおおむね 29〜71ns の範囲で増え続けた結局どこかの時点で 命令セットアーキテクチャ の問題に行き着くのではないかと思う
3GHz で動作する CPU は、1ナノ秒あたり3クロックサイクルを得る
コンパイラ最適化によって、クロックレジスタを読むアセンブリ呼び出しが連続して並ぶ可能性はかなりありそうだ
連続した
time.Now()呼び出しが3クロックサイクル以内に起きるなら、本当に一意なナノ秒精度を期待するのは妥当なのかと思う衝突が多少まれだとしても、1日に何度か発生するのは「ほぼ絶対に起きない」よりはるかに悪い
Lotus Notes に関する伝説を思い出す
昔は1秒解像度のタイムスタンプを一意な ID として使っていたという
衝突すると単に1秒を足しており、最終的に衝突が多すぎて項目が 未来時刻 を持つようになった
絶対的に正確な時刻は セキュリティ上の問題 である
CPU 設計者は完全な予測可能性を防ぐため、DEC の Alpha の時代のようなかなり昔から意図的にクロックジッターを入れていた
x86 でも3〜4回実行して値をレジスタに保存し、終わってから見れば、時間差が正確には同じでないことが分かると思う
検索してもうまく見つからないが、初期の x86 まで含めた話なら、正確なクロックのセキュリティ問題をそんなに早く認識していたという点が驚きだ
個人的には今世紀に入る前まではそのような問題を知らず、観測されるクロックジッターは割り込みなどで説明されるのだろうと推測していたと思う
間違っていると言いたいわけではなく、もっと知りたい
ミリ秒やマイクロ秒のタイムスタンプ衝突に驚く人をあまりにも多く見てきた
最も記憶に残っていて嫌だったタイプは、2回のシステムコールでタイムスタンプを組み立てる方式である
片方は上位桁用、もう片方は下位桁用として呼び出すが、プロセスのプリエンプションのせいで上位桁を読んだ後に下位桁が 99x から 00x に移ると、あるエンティティを生み出した原因よりも前の時刻のタイムスタンプを作れてしまう
こうなると一部のコードは非常に派手に壊れ、少なくとも2回は 無限ループ を見た
これを常に避けるべきものとして覚えておかないと、テストは99.5%は通ってしまい、パターン認識の感覚が非常に良い人が「同じテストが1カ月半の間、週1回赤くなっていた」ことを見つける必要がある
CI/CD コードの中で論理爆弾が修正される前に生き残るには長すぎる時間である