صغيرة عشوائي يبحث ID الجيل

Question

أحاول إنشاء معرفات فريدة للاستخدام في Google App Engine وأود ردود الفعل بشأن جدوى النهج أنا أفكر في استخدام (الأسئلة في النهاية).لقد قرأت عدد غير قليل من الأسئلة في هذا الموضوع, لكني لا أتذكر القادمة عبر هذا نهج معين.

أود عشوائي يبحث معرفات مثل التجزئة MD5, ولكن أنا أيضا أريد لها أن تكون صغيرة.أربعة إلى ستة أحرف ، على غرار tinyurl ، من شأنه أن يكون مثاليا.معرفات سوف يكون المحتوى المقدم من المستخدمين ، في سياق تطبيق مثل أسئلة الاختبار أن الناس سوف تكون الكتابة.فإنه ليس من الضروري أن تكون معرفات عشوائي المظهر (لا بأس إذا كانت تبدو مثل المسلسل IDs) ، ولكن النهج أنا أفكر في استخدام يفسح المجال هذا, حتى انها ليست حقا مشكلة.

الناس على دراية مع محرك جوجل التطبيق سوف تعرف أن يكتب إلى مخزن البيانات خاصة مكلفة ويمكن أن يؤدي مهلة إذا كان هناك الكثير منهم إلى نفسه كيان الفريق.Sharded عدادات النهج التي تستخدم في كثير من الأحيان تجنب كتابة الخلاف على عالمية واحدة العداد فشل المعاملات التي تذهب معها.

جنبا إلى جنب مع الحصول على القصير معرفات و تجنب كتابة الخلاف ، أنا أحاول تجنب عيد ميلاد المفارقة.أود أن تستعد لاحتمال أن يكون هناك الملايين من معرفات ، حتى لو كان هذا هو المبالغة قليلا.

كنت أفكر في استخدام sharded العداد على النحو التالي:

• العداد sharded على المستخدمين ، حتى أن هناك قشرة لكل مستخدم.كل كائن عداد لديها الاعتماد الخاصة مستخدم معين ، والتي يتزايد عند إنشاء عنصر جديد من قبل المستخدم.العدد يتزايد بغض النظر عما إذا كان هذا البند هو خلق بنجاح.
• أساس الهوية تم تجزئة MD5 من السلسلة التالية:"<user-email-address>|<latest-counter-value>".
• مما أدى تجزئة MD5 ثم يتم اقتطاع في البداية إلى أربعة أحرف.
• عالمية واحدة "طول" قيمة الحفاظ عليها.كلما الخطوات السابقة يؤدي إلى مفتاح مكرر (واحد يتخيل هذا سيحدث بسرعة إلى حد ما في البداية) ، قيمة سيتم زيادة طول جانب واحد.التجزئة MD5 عن الهويات الجديدة سوف تكون الآن في اقتطاع "طول" أحرف بدلا من أربعة أحرف.
• أنا لا أريد أن يعرض المستخدم وعنوان البريد الإلكتروني ، مما يوحي بأن تجزئة من نوع ما من شأنه أن يكون وسيلة جيدة للذهاب.

أسئلتي هي:هل أنا على حق في التفكير في أن هذا إلى حد كبير تجنب كتابة الخلاف نتيجة مفاتيح مكررة و أن يكتب الخلاف على طول الحقل قد لا يكون مشكلة ، خاصة في أطوال أطول?يمكن لأي شخص أن تصف الرياضيات المعنية هنا ؟ أن مدة زيادة بسرعة إلى قرب طول تجزئة MD5, التشكيك في قيمة كل النهج ؟ سيكون من الأفضل أن تذهب مع كامل (أطول) تجزئة MD5 من أجل إبقاء الأمور أسهل الحفاظ ؟ هل هناك أي شيء أنا يطل ؟

Answer 1

هذه الخوارزمية ذكية ومن شأنها بالفعل تقليل عمليات الكتابة.وبالتالي فإن قيمة الطول سوف تتقارب إلى التوازن بين أقصر طول و غياب من الاصطدامات.

يمكنك تخفيف قيود غياب الاصطدام باستخدام الاستراتيجيات المستخدمة في جداول التجزئة.جرب بعض المعرفات الفريدة الأخرى قبل العودة إلى زيادة الطول.

وبالتالي أقترح عليك إضافة عداد اختبار إلى نهاية السلسلة المجزأة التي تمت تهيئتها إلى 0.إذا كان المعرف الذي تم إنشاؤه مستخدمًا بالفعل، فقم بزيادة العداد وأعد المحاولة حتى يتم الوصول إلى الحد الأقصى لقيمة العداد بعد زيادة الطول.

سينتهي بك الأمر باستخدام أكثر كفاءة لمساحة عنوان المعرف الخاص بك وزيادات أقل تكرارًا في الطول.

فيما يتعلق بسؤالك حول الحد الأقصى لطول MD5، أعتقد أن اختيار MD5 يعد مبالغة.لا تحتاج حقًا إلى تجزئة آمنة مشفرة (زائفة).ما تحتاجه هو مولد بت عشوائي يمكنك من خلاله استخدام crc32 (أو Adler وهو الأسرع).خاصة إذا كان سيتم تشغيل الكود على الهاتف المحمول.لتنفيذ مولد بت عشوائي باستخدام crc32، قم بإضافة قيمة 32 بت إلى السلسلة المراد تجزئتها وتهيئتها بقيمة ثابتة من اختيارك (البذرة).ثم قم بحساب crc32 على هذه السلسلة.إذا كنت بحاجة إلى المزيد من البايتات، فاكتب قيمة crc32 التي تم الحصول عليها في 32 بت أمام السلسلة وأعد حساب crc32.كرر حتى يكون لديك ما يكفي من البتات.يمكنك استبدال crc32 بالخوارزمية التي تختارها.ينتج عن هذا مولد بت عشوائي رخيص وسريع حيث يكون الثابت الأولي هو البذرة.

باستخدام هذه الخوارزمية يمكنك تقليل عدد البتات العشوائية التي تم إنشاؤها وليس لها حد أعلى للطول.

فيما يتعلق بالتشفير، لم تحدد القيود.هل يمكنك استخدام الحروف الكبيرة والصغيرة مع الأرقام؟يستخدم المثال الخاص بك أبجدية مكونة من 36 قيمة ASCII مختلفة.بمجرد حصولك على مولد الأرقام العشوائية الزائفة الموصوف أعلاه والذي يمكنه إنشاء أكبر عدد ممكن من البايتات، ما عليك سوى تحديد الطول ليكون عدد أحرف المعرف الخاص بك واختيار الحرف التالي مع وحدة البايت العشوائي التالي.ستعرف بعد ذلك بالضبط عدد وحدات البايت التي سيتم إنشاؤها دفعة واحدة، وسيكون إنشاء المعرف أمرًا تافهًا.

Answer 2

ماذا عن شيء مثل هذا:

1. إذا كنت تريد 4 حرف باستخدام مفاتيح a-zA-Z0-9 ثم عليك:62^4 = > 14 مليون القيم الممكنة.

2. كسر هذا إلى N أقسام:0000 ...1000, 1001 ...2000 , ..., ZZAA ...ZZZZ

   كل قسم يمثل كيان:تبدأ id نهاية الهوية الهوية الحالية

الآن لإنشاء معرف:

1. أختاري القسم.استخدام مفتاح البداية لكل قسم رئيسي.تبدأ الصفقة:
2. get_or_create() هذا التقسيم الكيان.
3. إذا الحالية id == نهاية id, انتقل إلى الخطوة 1
4. حفظ الهوية الحالية
5. الزيادة الحالية معرف واحد نهاية الصفقة

استخدام الهوية الحالية التي تم حفظها في بطاقة الهوية.

إذا اخترت ن 140 لكم كل قسم قد 100,000 القيم.هذا من شأنه أن يسمح عدد غير قليل من إدراج المتزامنة مع الحد من عدد مرات إعادة المحاولة بسبب قطف "فارغة" التقسيم.

قد تحتاج إلى التفكير في هذا أكثر.خصوصا كيف سيتم التعامل مع هذه القضية عندما تحتاج إلى نقل إلى 5 أو 6 أرقام المفاتيح ؟

-ديف

Answer 3

فقط لإضافة بعض الأرقام الصعبة إلى السؤال أعلاه، قمت بتنفيذ برنامج صغير لإنشاء معرفات على غرار ما ذكر في السؤال، وكانت هذه نتائج إحدى التجارب:

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

في كل مرة زاد طول التجزئة، كان ذلك بسبب الاصطدام، لذلك كان هناك ستة تصادمات في هذه الحالة.العدد هو عدد المفاتيح ذات الطول المحدد التي تم إنشاؤها قبل الاصطدام.يعرض عمود 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.افتراضيًا، المفاتيح التي يتم إنشاؤها بواسطة هذه الفئة ليست ذات أساس 62 تمامًا، حيث يجب أن يكون الحرف الأول من اسم مفتاح GAE أبجديًا.تمت معالجة هذا المطلب هنا باستخدام الأساس 52 للحرف الأول.

يمكن تغيير القاعدة الأساسية إلى شيء آخر غير 62 عن طريق تغيير قيمة "clist" التي تم تمريرها إلى (أو حذفها) المُنشئ.قد يرغب المرء في إزالة الأحرف التي يسهل الخلط بينها، على سبيل المثال، "1"، "l"، "i"، وما إلى ذلك.

الاستخدام:

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)