加畑さんインタビュー：衝突しない文字列を作るお話 JAWS DAYS 2013 Araki room

http://debiancdn.wordpress.com/2013/04/07/%E5%8A%A0%E7%95%91%E3%81%95%E3%82%93%E3%82%A4%E3%83%B3%E3%82%BF%E3%83%93%E3%83%A5%E3%83%BC%EF%BC%9A%E8%A1%9D%E7%AA%81%E3%81%97%E3%81%AA%E3%81%84%E6%96%87%E5%AD%97%E5%88%97%E3%82%92%E4%BD%9C%E3%82%8B/

2兆個、だいたい英数8桁の衝突しない文字列をつくるお話。

素数は3793、3797、3803、3821、3823、3833、3847。。というあたりで存在しています。ここから4つ(p1,p2,p3,p4)選んだ積は2兆くらいになる。そこで3800×4個のファイルをS3につくっておく。それぞれのファイルは2桁の文字（Ad, s6, xJとか。。）を入れた1.txtとかのファイル。

あとはシーケンシャルに作った数Nを N mod p1, N mod p2, N mod p3, N mod p4のファイルから取り出すとぶつかることがない8桁の文字列がコスト低く取り出せる、という話でした。ユニークなIDを連番でなく使いたいときに使えます。実際5000req/secをt1.microで作れているそうです。Nを作るためにMySQLを使っている。