Gitのコミット時に付けられるhashって衝突するんじゃね、と思って確認したことをメモしておく。
まず、ごくごく低確率ではあるけど衝突することはあるようだ。
How would git handle a SHA-1 collision on a blob?
So what happens is that if we ever see a collision, the "earlier" object in any particular repository will always end up overriding.
もし衝突が起きたら、そのレポジトリにおける過去のコミットは上書きされるよ。
あまりよろしくない挙動になっているようだ。
とはいえ衝突が起こる確率は天文学的な数字だし、偶然それが起こったとしてもちょっと過去のログが欠けるだけだから別にいいよね、ということになっている。
過去においてはHEXで7桁という割と少なめのhashで運用していので、衝突もそこそこに起こっていたという話もある。
The default of 7 comes from fairly early in git development, when seven hex digits was a lot (it covers about 250+ million hash values). Back then I thought that 65k revisions was a lot (it was what we were about to hit in BK), and each revision tends to be about 5-10 new objects or so, so a million objects was a big number.
gitの開発段階においては7桁のhex（2億5千万以上のパターンが持てる）で十分だろうということで、デフォルト値を設定してたんだ。6万5千件のリビジョンが、それぞれ5〜10の新しいオブジェクトを持つくらいだろうと考えて。100万オブジェクトって十分大きいサイズだよね。
These days, the kernel isn't even the largest git project, and even the kernel has about 220k revisions (_much_ bigger than the BK tree ever was) and we are approaching two million objects.
ところが最近はLinuxカーネルを超える規模のgitプロジェクトも出現するようになってきたし、カーネル自身のレポジトリも22万リビジョン、200万オブジェクトに達しようとしている。
といった経緯を経て、現在では40桁にまで拡張されている。
16の40乗は10進数だと下記のような数字になる。
1461501637330902918203684832716283019655932542976
まあ、とりあえずとても大きい数字だ。
これが衝突する確率について、下記の記事に書かれている。
How hard is it to get a git hash collision?
a large project might have 1000 active developers who commit 10 commits per day. In these circumstances, it would take approximately 4×10^17 years for a collision to happen with 50% probability.
非常に大きなプロジェクトで、1000人のアクティブな開発者が、日に10回のコミットをしたとする。この場合、4×10の17乗年間活動を続けると、50%の確率で衝突が発生する。
いわゆる誕生日のパラドックスが起こる問題だけど、これだけの桁数を衝突させるには宇宙の年齢をはるかに超える天文学的な時間がかかるそうだ。
システム開発においては懸念する必要のない可能性と思って良い。
この手のシステムを仮に法律の管理や、裁判所の判例管理なんかを行うようになった場合は、問題として捉えられたりするのだろうか。天文学的な確率は無視するか、事前にチェックを入れるか。
いや、そうした例では分散型である必要はないから、subversion的なもので連番のrevisionが振られるのが正解なんだろうな。