[訂正あり] 秒単位で衝突するファイル名をミリ秒単位に改善すると、1000倍安全になる

作成日: 2023-05-26

2023-05-29 訂正 どうやらルートぐらいしかよくならない

「リスクが1/Nになったら、N倍流せるようになる」が間違いです。√N倍しか流せない、という誕生日の直感が正しいです。

以下、誤りのある原文

topics.smt.docomo.ne.jp
https://topics.smt.docomo.ne.jp/article/itmedia_news/trend/itmedia_news-20230510_114?redirect=1
コンビニのプリントサービスのバグが有名になりました。秒単位で同時刻にサービスを2名以上に提供すると、秒で名付けられたファイル名の衝突が起こり、正しく処理がなされないというバグです。
今回はこの実装の是非ではなく、次の素朴な疑問に答えたいと思います。（私の先輩のツイートです）
秒単位のファイル名だから衝突しやすいのであって、ミリ秒単位なら多少マシなのではというアイデアについてです。衝突しにくくなることは事実でしょう。しかし、誕生日のパラドックスを知っていると32倍ぐらいの改善にしかならなそうな気もします。実際に計算してみましょう。

誕生日のパラドックスとは

「30人のクラスに同じ誕生日の2人がいる確率は？」が誕生日のパラドックスと言われる問題です。誕生日は365通りあるので、30人だと10%ぐらいかなという気がします。ところが、実際に計算すると約71%です。1人ずつ増えやしたときに、自分と同じ誕生日の人は365分の1ずつしか増えないのですが、誰かと誰かが同じ誕生日であるペアは急激に存在しやすくなります。
p(x)=1−∏k=1x−1365−k365p(x) = 1- \prod_{k=1}^{x-1}\frac{365-k}{365}

「何回起こるか」に答えてくれるポアソン分布

この誕生日の直感を今回の衝突のケースに適用できるのでしょうか。実は単純には適用できません。「N人のクラスに同じ秒の人が2人いる確率は？」のN人の部分がよくわかりません。
この問題を考えるには「単位時間に平均λ\lambda回起こる事象がこの単位時間にkk回起こる確率は？」というポワソン分布が役に立ちます。ポワソン分布は次の式で与えられます。
P(k)=λkk!e−λP(k) = \frac{\lambda^k}{k!}e^{-\lambda}

1秒間に衝突する確率の計算

1秒間に衝突する確率ppは1秒間に事象が0回か1回起こる確率の余事象です。
p=1−P(0)−P(1)=1−(1+λ)e−λ≃λ2   [∵e−λ≃1−λ]\begin{align*}p&=1-P(0)-P(1)\\&=1-(1+\lambda)e^{-\lambda}\\&\simeq\lambda^2 \ \ \ [\because e^{-\lambda} \simeq 1-\lambda]\end{align*}
途中でλ2≃0\lambda^2 \simeq 0としてe−λe^{-\lambda}をテイラー近似しています。1秒に3回以上事象が起こる確率を無視したとしても同じ式が得られます。

衝突を1/x秒間に改善したときの衝突する確率の計算

1秒間に1回までセーフが、1/x秒間に1回までセーフに改善したとします。単位時間が狭まったので、1/x秒間には平均λ/x回の事象が起こると考えます。1/x秒間に衝突する確率p0′p'_0を求めると、pのλがλ/xになるので次の式になります。
p0′≃λ2x2=px2p'_0\simeq\frac{\lambda^2}{x^2}=\frac{p}{x^2}
1秒間には1/x秒間の衝突可能性がx回あるので、1秒間に衝突する可能性は次式です。
p′=1−(1−p0′)x=1−(1−px2)x≃1−(1−px)=px\begin{align*}p'&=1-(1-p'_0)^x\\&=1-\left(1-\frac{p}{x^2}\right)^x\\&\simeq1-\left(1-\frac{p}{x}\right)\\&=\frac{p}{x}\end{align*}
途中でp2≃0p^2\simeq0としてテイラー近似しています。
以上より、1秒間をx分割したときに衝突するリスクはp/p′=xp/p'=xと、x倍改善されることがわかりました。実は誕生日のパラドックスは関係なく、素直に改善を受け入れることができてよかったです。

実際の排他制御の問題

分散処理における排他制御は厄介です。想像もつかない様々な事故が起こります。不自由な環境での苦肉の策の可能性もあります。衝突を検出できてリトライする仕様ならば問題なかったかもしれないと思います。ダーティーな解決策の上では、秒ではなくミリ秒にすれば誕生日の心配なく1000倍安全だよということを知っておきましょう。ミリ秒の精度ぐらいは流石に出る、出るよね…?