小さなランダムに見えるID生成
https://stackoverflow.com/questions/815622
-
03-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
Google App Engineアプリケーションで使用する一意のIDを生成しようとしていますが、使用を検討しているアプローチの実行可能性に関するフィードバックをお願いします（最後に質問）。このトピックに関するいくつかの質問を読みましたが、この特定のアプローチに出くわしたことは覚えていません。
ランダムに見えるID、例えばMD5ハッシュが欲しいのですが、小さくしたいです。 tinyurlの行に沿った4〜6文字が理想的です。 IDは、ユーザーが作成するテスト質問など、アプリケーションのコンテキストでのユーザー生成コンテンツ用です。 IDがランダムに見える必要はありません（シリアルIDのように見える場合は問題ありません）が、私が使用することを考えているアプローチはこれに適しているため、実際には問題ではありません。
Google App Engineに精通している人々は、データストアへの書き込みが特に高価であり、同じエンティティグループに対してそれらが多すぎるとタイムアウトになる可能性があることを知っています。シャードカウンターは、単一のグローバルカウンターでの書き込み競合と、それに伴う失敗したトランザクションを回避するためによく使用されるアプローチです。
短いIDを取得し、書き込みの競合を回避するとともに、誕生日のパラドックスを回避しようとしています。たとえ数百万のIDが存在する可能性に備えたいと思います。たとえそれが少し船外に出ていても。
次の行に沿ってシャードカウンターを使用することを考えていました。
- カウンターはユーザーごとに分割されるため、ユーザーごとに分割があります。各カウンタオブジェクトには、特定のユーザーに固有の独自のカウントがあり、そのユーザーが新しいアイテムを作成すると増分されます。アイテムが正常に作成されたかどうかに関係なく、カウントは増加します。
- IDの基礎は、次の文字列のMD5ハッシュです：<！> quot; <！> lt; user-email-address <！> gt; | <！> lt; late-counter-value <！ > gt; <！> quot;。
- 結果のMD5ハッシュは、最初は4文字に切り捨てられます。
- 単一のグローバル<！> quot; length <！> quot;値は維持されます。前の手順で重複キーが発生するたびに（最初はこれがかなり速く発生すると想像する人はいつでも）、長さの値は1ずつ増加します。新しいIDのMD5ハッシュは、<！> quot; length <！> quotで切り捨てられます。 4文字ではなく、文字。
- ユーザーのメールアドレスを公開したくありません。これは、ある種のハッシュが良い方法であることを示唆しています。
私の質問は次のとおりです。これにより、重複キーの結果としての書き込み競合が大幅に回避され、長さフィールドへの書き込み競合はおそらく問題になりません。誰もがここで関係する数学を説明できますか？長さはMD5ハッシュの長さ近くまで急速に増加し、アプローチ全体の価値を疑問視しますか？物事を維持しやすくするために、完全な（より長い）MD5ハッシュを使用する方が良いでしょうか？見落としているものはありますか？
解決
このアルゴリズムは賢く、書き込み操作を最小限に抑えます。したがって、長さの値は、最短の長さと衝突の不在の間のバランスに収束します。
ハッシュテーブルで使用される戦略を使用することにより、衝突がないという制約を緩和できます。長さの増分に戻る前に、他のいくつかの一意のIDを試してください。
したがって、0に初期化されたハッシュ文字列の最後にテストカウンターを追加することをお勧めします。生成されたIDが既に使用されている場合は、カウンターをインクリメントし、長さを増やした後に最大カウンター値に達するまで再試行します。
IDアドレス空間をより効率的に使用し、長さの増分を大幅に少なくすることになります。
MD5の長さ制限に関する質問については、MD5の選択はやり過ぎだと思います。暗号化（擬似）セキュアハッシュは本当に必要ありません。必要なのは、crc32（またはより高速なadler）を使用できるランダムビットジェネレータです。特に、コードを携帯電話で実行する場合。 crc32でランダムビットジェネレーターを実装するには、32ビット値を文字列に追加してハッシュし、選択した定数値（シード）で初期化します。次に、この文字列でcrc32を計算します。さらにバイトが必要な場合は、取得したcrc32値を文字列の前の32ビットに書き込み、crc32を再計算します。十分なビットが得られるまで繰り返します。 crc32を選択したアルゴリズムに置き換えることができます。これにより、初期定数がシードである安価で高速なランダムビットジェネレータが生成されます。
このアルゴリズムを使用すると、生成されるランダムビットの数を最小限に抑え、長さの上限もありません。
エンコーディングについては、制約を指定しませんでした。数字に大文字と小文字を使用できますか？この例では、36種類のASCII値のアルファベットを使用しています。 必要なバイト数を生成できる上記の擬似乱数ジェネレーターを作成したら、IDの文字数に長さを定義し、次のランダムバイトのモジュロで次の文字を選択します。一度に生成するバイト数が正確にわかり、IDの生成は簡単です。
他のヒント
このようなものはどうですか：
-
a-zA-Z0-9を使用して4文字のキーが必要な場合は、次のようになります。 62 ^ 4 = <！> gt; 1400万の可能な値。
-
これをN個のパーティションに分割します。 0000 ... 1000、1001 ... 2000、...、ZZAA ... ZZZZ
各パーティションは、次のエンティティで表されます。 開始ID 終了ID 現在のID
今、IDを生成するには：
- パーティションをランダムに選択します。各パーティションの開始キーをキーとして使用します。 トランザクションを開始：
- get_or_create（）そのパーティションエンティティ。
- 現在のID ==終了IDの場合、ステップ1に進みます
- 現在のIDを保存
- 現在のIDを1つ増やす トランザクションの終了
IDとして保存された現在のIDを使用します。
Nを140として選択した場合、各パーティションには100,000個の値があります。これにより、<！> quot; empty <！> quot;の選択による再試行の回数を制限しながら、かなりの数の同時挿入が可能になります。パーティション。
これについてもっと考える必要があるかもしれません。特に、5桁または6桁のキーに移動する必要がある場合、どのようにケースを処理しますか？
-Dave
上記の質問にいくつかのハードナンバーを追加するために、質問に記載されている行に沿ってIDを生成する小さなプログラムを実装しました。これらは試用の1つの結果です：
Length Count MD5 Base 62
4 400 3d0e 446
5 925 4fc04 1Myi
6 2434 0e9368 40V6
7 29155 e406d96 GBFiA
8 130615 7ba787c8 2GOiCm
9 403040 75525d163 YNKjL9
10 1302992 e1b3581f52 H47JAIs
Total: 1869561
ハッシュの長さが増加するたびに、これは衝突によるものだったため、このインスタンスでは6つの衝突がありました。カウントは、衝突の前に生成された特定の長さのキーの数です。 MD5列には、キーの重複エラーが発生する前に正常に追加された最後の切り捨てられたキーが表示されます。一番右の列は、ベース62のキーを示しています（正しく変換を行った場合）。
文字が追加されるたびに、より多くのキーが生成されているように見えます。このアプローチがユーザー生成コンテンツに合わせて拡張されることを期待しています。
興味のある方のために、最後の列のベース62表現を取得した方法を次に示します。
def base_62_encode(input):
"Inspired by code at http://en.wikipedia.org/wiki/Base_36."
CLIST="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"
rv = ""
while input != 0:
rv = CLIST[input % 62] + str(rv)
input /= 62
return rv
base62_id = base_62_encode(long(truncated_hash, 16))
（後で追加：）
これは、Google App EngineのコンテキストでこれらのIDの生成に関連するいくつかのことを処理するクラスです。デフォルトでは、このクラスによって生成されるキーは純粋にベース62ではありません。GAEキー名の最初の文字はアルファベットである必要があるためです。この要件は、最初の文字にベース52を使用することで対処されています。
<！> quot; clist <！> quot;を変更することにより、プライマリベースを62以外に変更できます。コンストラクターに渡された（またはコンストラクターから省略された）値。 <！> quot; 1 <！> quot;、<！> quot; l <！> quot;、<！> quot; i <！>など、混同されやすい文字を削除したい場合があります。 quot;など。
使用法：
keygen = LengthBackoffIdGenerator(SomeClass, initial_length=5)
small_id, modified = keygen.small_id(seed_value_from_sharded_counter)
クラスは次のとおりです。
class LengthBackoffIdGenerator(object):
"""Class to generate ids along the lines of tinyurl.
By default, ids begin with a alphabetic character. Each id that is created is checked against previous ones
to ensure uniqueness. When a duplicate is generated, the length of the seed value used is increased by one
character.
Ids become gradually longer over time while remaining relatively short, and there are very few retries in
relation to the number of keys generated.
"""
ids = set()
def __init__(self, cls, clist='0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ', alpha_first=False,
initial_length=5, check_db=False):
self.clist = clist
self.alpha_first = alpha_first
if self.alpha_first:
import re
alpha_list = re.sub(r'\d', '', clist)
if len(alpha_list) < 1:
raise Exception, 'At least one non-numeric character is required.'
self.alpha_list = alpha_list
self.cls = cls
self.length = initial_length
self.check_db = check_db
def divide_long_and_convert(self, radix, clist, input, rv):
"Inspired by code at http://en.wikipedia.org/wiki/Base_36."
rv += clist[input % radix]
input /= radix
return (input, rv)
def convert_long(self, input):
rv = ""
if self.alpha_first:
input, rv = self.divide_long_and_convert(len(self.alpha_list), self.alpha_list, input, rv)
while input != 0:
input, rv = self.divide_long_and_convert(len(self.clist), self.clist, input, rv)
return rv
def hash_truncate_and_binify(self, input, length):
"""Compute the MD5 hash of an input string, truncate it and convert it to a long.
input - A seed value.
length - The length to truncate the MD5 hash to.
"""
from assessment.core.functions import md5_hash
input = md5_hash(input)[0:length]
return long(input, 16)
def _small_id(self, input):
"""Create an ID that looks similar to a tinyurl ID.
The first letter of the ID will be non-numeric by default.
"""
return self.convert_long(self.hash_truncate_and_binify(input, self.length))
def small_id(self, seed):
key_name = self._small_id(seed)
increased_length = False
if self.check_db and not self.cls.get_by_key_name(key_name) is None:
self.ids.add(key_name)
if key_name in self.ids:
self.length += 1
increased_length = True
key_name = self._small_id(seed)
self.ids.add(key_name)
return (key_name, increased_length)
