छोटे यादृच्छिक दिखने वाली आईडी पीढ़ी

Question

मैं Google ऐप इंजन एप्लिकेशन में उपयोग के लिए अद्वितीय आईडी उत्पन्न करने की कोशिश कर रहा हूं और उस दृष्टिकोण की व्यवहार्यता पर फीडबैक चाहूंगा जिसे मैं उपयोग करने के बारे में सोच रहा हूं (अंत में प्रश्न)। मैंने इस विषय पर काफी कुछ प्रश्न पढ़े हैं, लेकिन मुझे इस विशेष दृष्टिकोण में आने की याद नहीं है।

मुझे यादृच्छिक दिखने वाली आईडी, उदाहरण के लिए, एमडी 5 हैश, लेकिन मैं भी उन्हें छोटा होना चाहता हूं। टिन्यूरल की तर्ज पर चार से छह वर्ण आदर्श होंगे। आईडी उपयोगकर्ता द्वारा जेनरेट की गई सामग्री के लिए होगी, मेरे आवेदन के संदर्भ में, परीक्षण प्रश्नों जैसी चीजें जो लोग लिखेंगे। यह आवश्यक नहीं है कि आईडी यादृच्छिक दिख रहे हों (यह ठीक है अगर वे धारावाहिक आईडी की तरह दिखते हैं), लेकिन जिस दृष्टिकोण का मैं उपयोग करने के बारे में सोच रहा हूं वह स्वयं को उधार देता है, इसलिए यह वास्तव में कोई मुद्दा नहीं है।

Google ऐप इंजन से परिचित लोगों को पता चलेगा कि डेटा स्टोर में लिखना विशेष रूप से महंगा है और परिणामस्वरूप समय-समय पर एक ही इकाई समूह में बहुत से लोग हो सकते हैं। शर्डेड काउंटर एक ऐसा दृष्टिकोण है जिसका प्रयोग अक्सर एक वैश्विक काउंटर पर लिखने वाली विवाद से बचने के लिए किया जाता है और इसके साथ चलने वाले असफल लेनदेन।

छोटी आईडी प्राप्त करने और लिखने की विवाद से बचने के साथ, मैं जन्मदिन के विरोधाभास से बचने की कोशिश कर रहा हूं। मैं लाखों आईडी होने की संभावना के लिए तैयार करना चाहता हूं, भले ही यह थोड़ा सा हो रहा हो।

मैं निम्नलिखित लाइनों के साथ एक sharded काउंटर का उपयोग करने का सोच रहा था:

• काउंटर उन पर sharded है, ताकि प्रत्येक उपयोगकर्ता के लिए एक ठीकरा है। प्रत्येक काउंटर ऑब्जेक्ट की अपनी गिनती होती है जो किसी दिए गए उपयोगकर्ता के लिए विशिष्ट होती है, जो उस उपयोगकर्ता द्वारा बनाई गई नई वस्तु के दौरान बढ़ी जाती है। किसी आइटम को सफलतापूर्वक बनाया गया है या नहीं, इस पर ध्यान दिए बिना गिनती बढ़ी है।
• आईडी का आधार निम्न स्ट्रिंग का MD5 हैश है: "< उपयोगकर्ता-ईमेल-पता > | < नवीनतम-काउंटर-मान >"।
• परिणामी एमडी 5 हैश को फिर से चार वर्णों में छोटा कर दिया गया है।
• एक वैश्विक "लंबाई" मान बनाए रखा जाता है। जब भी पिछले चरणों में डुप्लिकेट कुंजी होती है (एक कल्पना करता है कि यह पहले से काफी जल्दी होगा), लंबाई का मूल्य एक से बढ़ाया जाएगा। नए आईडी के लिए एमडी 5 हैश अब चार अक्षरों के बजाय "लंबाई" अक्षरों पर छोटा कर दिया जाएगा।
• मैं उपयोगकर्ता ईमेल पता का पर्दाफाश नहीं करना चाहता, जो बताता है कि किसी प्रकार का हैश जाने का एक अच्छा तरीका होगा।

मेरे सवाल कर रहे हैं: मैं यह सोच कर कि यह काफी हद तक डुप्लिकेट चाबी का एक परिणाम और लंबाई मैदान पर कि विवाद लिखने शायद एक मुद्दा है, विशेष रूप से अब लंबाई पर नहीं होगा के रूप में लिखने के विवाद से बचने जाएगा में हूं? क्या कोई यहां शामिल गणित का वर्णन कर सकता है? क्या लंबाई एमडी 5 हैश की लंबाई के करीब तेजी से बढ़ेगी, जो पूरे दृष्टिकोण के मूल्य पर सवाल उठाती है? क्या चीजों को बनाए रखने में आसान रखने के लिए पूर्ण (लंबा) MD5 हैश के साथ जाना बेहतर होगा? क्या मैं कुछ भी देख रहा हूं?

Answer 1

इस एल्गोरिथ्म चालाक है और वास्तव में लिखने के संचालन को कम से कम होगा:

keygen = LengthBackoffIdGenerator(SomeClass, initial_length=5) 
small_id, modified = keygen.small_id(seed_value_from_sharded_counter) 

यहाँ वर्ग है। इसलिए लंबाई मूल्य कम से कम लंबाई और टकराव के के बीच संतुलन में एकत्रित होगा।

हैश टेबल में उपयोग की जाने वाली रणनीतियों का उपयोग करके आप टक्कर की अनुपस्थिति की बाधा को दूर कर सकते हैं। लंबाई बढ़ाने के लिए वापस गिरने से पहले कुछ अन्य अद्वितीय आईडी आज़माएं।

मैं करूंगा इस प्रकार आप उत्पन्न ID पहले से ही प्रयोग किया जाता है टुकड़ों में बंटी स्ट्रिंग को 0 पर प्रारंभ के अंत के लिए एक परीक्षण काउंटर जोड़ने के लिए, काउंटर बढ़ाने के और पुन: प्रयास जब तक एक अधिकतम काउंटर मूल्य क्या आप लंबाई में वृद्धि के बाद तक पहुँच जाता है का सुझाव ।

आप अपने आईडी पता स्थान के अधिक कुशल उपयोग के साथ समाप्त हो जाएंगे और बहुत कम लंबाई में वृद्धि होगी।

एमडी 5 की लंबाई सीमा के बारे में आपके प्रश्न के बारे में मुझे लगता है कि एमडी 5 की पसंद एक ओवरकिल है। आपको वास्तव में एक क्रिप्टोग्राफिक (छद्म) सुरक्षित हैश की आवश्यकता नहीं है। आपको जो चाहिए वह एक यादृच्छिक बिट जनरेटर है जिसके लिए आप crc32 (या एडलर जो तेज़ है) का उपयोग कर सकते हैं। विशेष रूप से यदि कोड मोबाइल फोन पर चलाना है। Crc32 के साथ एक यादृच्छिक बिट जनरेटर को कार्यान्वित करने के लिए, हैश को स्ट्रिंग में 32 बिट मान को प्रीपेड करें और इसे अपनी पसंद (बीज) के निरंतर मान के साथ प्रारंभ करें। फिर इस स्ट्रिंग पर crc32 की गणना करें। यदि आपको अधिक बाइट्स की आवश्यकता है, तो स्ट्रिंग के सामने 32 बिट्स में प्राप्त crc32 मान लिखें और crc32 को पुन: सम्मिलित करें। जब तक आपके पास पर्याप्त बिट्स न हो जाएं Iterate। आप अपनी पसंद के एल्गोरिदम के साथ crc32 को प्रतिस्थापित कर सकते हैं। यह एक सस्ता और तेज़ यादृच्छिक बिट जनरेटर उत्पन्न करता है जहां प्रारंभिक स्थिर बीज होता है।

इस एल्गोरिदम के साथ आप उत्पन्न यादृच्छिक बिट्स की संख्या को कम करते हैं और लंबाई में कोई ऊपरी सीमा भी नहीं है।

एन्कोडिंग के संबंध में, आपने बाधाओं को निर्दिष्ट नहीं किया है। क्या आप अंकों के साथ ऊपरी और निचले केस अक्षरों का उपयोग कर सकते हैं? आपका उदाहरण 36 विभिन्न ASCII मानों के वर्णमाला का उपयोग करता है। एक बार जब आपके ऊपर वर्णित छद्म यादृच्छिक संख्या जेनरेटर होता है जो वांछित के रूप में कई बाइट उत्पन्न कर सकता है, तो बस अपनी आईडी के अक्षरों की संख्या होने के लिए लंबाई निर्धारित करें और अगले यादृच्छिक बाइट के मॉड्यूल के साथ अगला अक्षर चुनें। आपको पता चलेगा कि एक बार में कितने बाइट उत्पन्न होते हैं और आईडी उत्पन्न करना तुच्छ है।

Answer 2

कुछ इस तरह के बारे में कैसे:

1. आप एक-zA-Z0-9 का उपयोग कर 4 चरित्र कुंजी चाहते हैं, तो आप होगा: 62^4 => 14 लाख संभावित मान।

2. इसे एन विभाजन में विभाजित करें: 0000 ... 1000, 1001 ... 2000, ..., ZZAA ...ZZZZ

   प्रत्येक विभाजन के साथ एक इकाई का प्रतिनिधित्व करती है: आईडी अंत आईडी वर्तमान आईडी

अब शुरू , एक आईडी उत्पन्न करने के लिए:

1. बेतरतीब ढंग से एक विभाजन लेने। एक कुंजी के रूप में प्रत्येक विभाजन के लिए प्रारंभ कुंजी का प्रयोग करें। प्रारंभ लेनदेन:
2. get_or_create() विभाजन इकाई।
3. यदि वर्तमान आईडी == अंत आईडी, वर्तमान आईडी
4. वेतन वृद्धि वर्तमान आईडी बचाने के लिए चरण 1
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 में कुंजी दिखाता है (यदि मैंने सही ढंग से रूपांतरण किया है)।

ऐसा लगता है कि अधिक से अधिक कुंजी प्रत्येक अतिरिक्त चरित्र है, जो है कि तुम क्या कल्पना कर सकते हैं के साथ उत्पन्न किया जा रहा है। मुझे आशा है कि यह दृष्टिकोण उपयोगकर्ता द्वारा जेनरेट की गई सामग्री के लिए स्केल करेगा।

def base_62_encode(input): 
    "Inspired by code at http://en.wikipedia.org/wiki/Base_36." 
    CLIST="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz" 
    rv = "" 
    while input != 0: 
     rv = CLIST[input % 62] + str(rv) 
     input /= 62 
    return rv 

base62_id = base_62_encode(long(truncated_hash, 16)) 

---

(बाद में :)

यहाँ पर जोड़ा एक वर्ग इस बात का ध्यान रखता है:

जो कोई रुचि है, यहाँ के लिए मैं कैसे अंतिम स्तंभ के लिए आधार 62 प्रतिनिधित्व मिल गया है Google ऐप इंजन के संदर्भ में इन आईडी की पीढ़ी से संबंधित कई चीजें। डिफ़ॉल्ट रूप से, कुंजी है कि इस वर्ग के द्वारा उत्पन्न कर रहे, विशुद्ध रूप से आधार 62 नहीं कर रहे हैं के बाद से एक GAE कुंजी नाम के पहले अक्षर वर्णमाला होना चाहिए। पहले चरित्र के लिए बेस 52 का उपयोग करके उस आवश्यकता को यहां संबोधित किया गया है।

प्राथमिक आधार "clist" मान में पारित कर दिया गया है (या में शामिल करना ज़रूरी) निर्माता बदलकर 62 के अलावा कुछ करने के लिए बदला जा सकता है। एक, अक्षर हैं जो मिश्रित करने के लिए उदाहरण के लिए, आसान कर रहे हैं दूर करने के लिए "1", "एल", "मैं", आदि चाहते हो सकता है

उपयोग:

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='abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ', 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)