なるべく短くてユニークなIDを作りたかった

日々

ふと思い立って、頑張って考えてみた。

基本的には 元になる値 と 変換ルール を決めればよくて、後は好みの問題だと思う。


元になる値を選定について

  • 時間を使う(連番方式)
    • メリット
      • 重複せず常に増え続けるのでそのままIDとして使える。
      • 歯抜けになるが、比較的短く作れる
        • ある時間内で作られなければそのIDは記録されないため
    • デメリット
      • 次を予測しやすい
        • 変換ルールで少しは対策できる？
      • 1秒あたりに1個しか作れない。
      • タイマーの精度を上げると1秒間に作れる個数は増えるが、値が大きくなってしまう(ユニークIDが長くなる可能性がある)
      • 並列環境では衝突する可能性がある(要排他制御)
  • ファイルやDBを使い連番を記録する(連番方式)
    • メリット
      • 重複せず常に増え続けるのでそのままIDとして使える。
      • 無駄なく短く作れる
    • デメリット
      • 次を予測しやすい
        • 変換ルールで少しは対策できる？
      • 並列環境では衝突する可能性がある(要排他制御)
  • 乱数を使う(乱数)
    • メリット
      • 次を予測しにくい
    • デメリット
      • 同一の値が得られる可能性がある
        • 回避するには、過去に作ったかどうか判定する必要があるが、ある程度埋まってくると衝突が頻発してしまう
  • 時間と乱数を合わせる
    • 時間が"100"、乱数が"123"だったときに、連結して"100123"を値とする
    • メリット
      • 乱数により単純な連番ではなくなる
    • デメリット
      • 値が大きくなりがち(ユニークIDが長くなる可能性がある)

変換ルールを決める

  • 情報を落とさない変換ルールを作る
    • そのまま使う、Base64変換や、A-Z,a-z,0-9の62文字を使って62進数変換するなど
    • メリット
      • 値さえ一意であれば衝突することはない
    • デメリット
      • 変換ルールがばれやすく、ばれると元になった値も芋づる式にばれる可能性がある
        • ある程度複雑にはできる？

複雑にできるかどうかはわからないが、思いついたのは以下。

  • S1=['a','b','c']
  • S2=['A','d','e','C','0','1']
  • S3=['f','G','2','3']
  • ....

といった可変長な変換テーブルを用意して、1文字目はS1から、2文字目はS2から...という感じで順番に文字を変換する。

攻撃するには変換テーブルの存在を知っていないといけないのと、入力値によって次を推測しやすい形にはならないので、複雑になる・・・ような気がする。

  • ハッシュ関数(md5/sha1...)を使う
    • メリット
      • 次を予測しにくいIDになる
      • 元になった値を予測する事は非常に難しい(もし変換ルールがばれても元の値の選定の仕方はバレることはほぼない)
      • 実装しなくていいので楽
      • 固定長出力のハッシュ関数でも一応短くできる
        • gitのようにほぼ衝突しないとタカを括って、先頭の数文字で一意に識別するとか
        • 具体的にはSHA1を16進数変換すると40文字なので、先頭2文字で登録、登録済みであれば次は先頭3文字で登録...と繰り返してなるべく短くなるように登録する。あ、めんどい。
    • デメリット
      • ハッシュ関数は衝突するつくりになってるものがほとんどなので、何かしらの衝突対策が必要。乱数のときみたいに。

おわり。

どれだけ短く作るかによるけども、単純に短く作るだけなら、連番+情報を落とさない変換ルールが最も短くつくれるはず。
0〜18446744073709551615(20文字。64bitの符号なし最大値)までなら、62進数変換で1文字〜10文字で収まる。
つまり、18446744073709551615個は10文字以下でユニークIDを表現できる。もちろん多少長くなってもよければさらにたくさんのユニークIDを扱える。

後はそこまで必要なのか、もしバレたらまずいのか、などで組み合わせる感じかなぁ。

あと、どの変換ルールを採用しても考えうる限りの文字を総当りでやられたらお終いだが、それはどの手法もそうなので、相手に変換ルールとかがばれないことが重要だと思う。

何かしらOSS化しなきゃならないときは、適当にsaltを設定できるようにしたりしてアルゴリズムを知ってても推測しにくい形に変換できるといいかもしれない。

そもそも短いユニークIDは他人にバレても良いような使い方しかダメでしょう・・・。

どうせ使い道は短いURLの生成ぐらいしかないんじゃｒｙ