短い固有ID

私はHTTPサービスを設計しています。これは、1日に最大5億リクエスト（複数の独立したマシンによって提供される）の能力を備えています。短い固有ID

リクエストごとに一意のIDを生成してユーザーに返す必要があります。 IDは、10分のウィンドウ内で一意の100％でなければなりません。（1日が望ましい、グローバルにユニークなIDが理想的です）。そのIDを生成するためにサーバーとサーバー間の通信は必要ありません。

愚か疑似セッションの例：私はUUIDを使用するこのHTTPサービスの前の世代で

 
Client: GET /foo 

Server: Content-Type: text/xml 

     <root> 
      <id>ab9d1972-2844-11e0-86b2-000c29544403</id> 
      <other_data/> 
     </root>

。

私はUUIDに満足していますが、問題が1つあります。長すぎます。その数の要求では、この余分なサイズが目に見えてディスク容量が浪費され、ログファイルが無駄になります。

短いがユニークな識別子を作成する最も良い方法は何ですか？物事を価値あるものにするために、アルゴリズムはUUIDの長さの半分を生成しなければならず、一日中ユニークである必要があります（10分はさらに短くする必要があります）。

は理想的には、アルゴリズムは、プレーンCで正気、軽量な生産品質の実装を持っているでしょう示唆し

更新：GETリクエストに渡された時に生成されたIDは、URIエンコーディングを必要とすべきではありません。

出典

2011-01-29 Alexander Gladysh

レイジー質問（申し訳ありませんが、夜間に数学をするには遅すぎます）：バイナリからascii85でエンコードされたUUIDはどれくらいですか？ –

@Alexander：桁数は 'ceil（log（max_val）/ log（num_different_chars））'です。 –

ASCII85は4バイトを5文字でエンコードします。しかし、それは*本当に* URIや人間に優しいものではありません。（UUIDは128ビットで16バイトはASCII85の20文字です）。 –

各マシンに固有のプレフィックスを付けます。各マシンにカウンタを与えます。 IDを生成するには、カウンタをインクリメントし、その値を接頭辞に追加します。

IDを難読化したい場合は暗号化します。暗号は可逆変換であるため、一意の値に適用すると一意の値が生成されます。

出典

2011-01-29 00:21:08

また、IDの予測攻撃を排除するために、各IDをmachineid-counter-randomkeyの3つの部分にすることもできます。 –

良いアイデア。あなたは本当に速い暗号を提案できますか？ –

また、IDがあなたの方法で生成された場合、そのIDはどれくらい短いと思いますか？ –

いくつかの考え：

5億要求する日。本当に？
UUIDを使用します。
必要に応じて、HTTPを使用しないでください（より重要なオーバーヘッドなので）。また、UUIDをバイナリ形式で転送してください。
サーバーが本当にユニーク IDを返すようにするには、一定のバイト数が必要です。
UDPの使用はどうですか？

とにかく、あなたは何をしようとしていますか？

出典

2011-01-29 00:20:58 BastiBen

500M、実際には（それは目標トップキャパシティで、実際の推定負荷は100Mに似ています）。残念なことにHTTPとTCP/IPは必須です。 –

また、500M /日はc10kの制限内にあるはずですが、それについて何が驚くべきですか？ –

答えて

関連する問題