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

2013年春、東京ビッグサイトへ集結せよ！という掛け声で、3月の15日、16日の二日間アマゾンウェブサービスのユーザグループであるJAWS-US (Japan AWS User Group）が全国から一同に会してユーザカンファレンスを行いました。当日のタイムスケジュール、資料、動画はこちらから参照できます。

荒木が進行した「荒木の部屋・AWSサポート出張所（松井の部屋）」についてはUstream中継の記録がいつでもご覧いただけます。本記事はそこでの会話内容、プレゼンテーション内容を元にしています。一連の記事はこちらで順次追加公開していきます。

ユニークなIDをどうやってコスト安く＝O(log2)で作るかというマニアックなお話（Youtubeはこちら）。

乱数はかぶる、ハッシュは長いので。さて。



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

素数は3793、3797、3803、3821、3823、3833、3847。。というあたりで存在しています。ここから4つ(p1,p2,p3,p4)選んだ積は2兆くらいになる。そこで3800x4個のファイルを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を使っている。

AWSでオートナンバーだけ返すサービスがあればそのNを自分で作る必要がないので作って欲しい、という話でした。