Tạo ID ngẫu nhiên nhỏ

Question

Tôi đang cố gắng tạo ID duy nhất để sử dụng trong ứng dụng Google App Engine và muốn phản hồi về tính khả thi của cách tiếp cận mà tôi đang nghĩ đến khi sử dụng (câu hỏi ở cuối). Tôi đã đọc khá nhiều câu hỏi về chủ đề này, nhưng tôi không nhớ đã đi qua cách tiếp cận đặc biệt này.

Tôi muốn ID trông ngẫu nhiên, ví dụ: băm MD5, nhưng tôi cũng muốn chúng nhỏ. Bốn đến sáu ký tự, dọc theo dòng tinyurl, sẽ là lý tưởng. Các ID sẽ dành cho nội dung do người dùng tạo, trong ngữ cảnh của ứng dụng của tôi, những thứ như câu hỏi kiểm tra mà mọi người sẽ viết. Nó không cần thiết rằng các ID được tìm kiếm ngẫu nhiên (nó là tốt nếu họ trông giống như ID nối tiếp), nhưng cách tiếp cận tôi đang nghĩ đến việc sử dụng cho vay chính nó, do đó, nó không thực sự là một vấn đề.

Những người quen thuộc với Google App Engine sẽ biết rằng ghi vào kho dữ liệu đặc biệt tốn kém và có thể dẫn đến hết thời gian chờ nếu có quá nhiều người trong số họ vào cùng một nhóm tổ chức. Các bộ đếm phân tầng là một cách tiếp cận thường được sử dụng để tránh tranh chấp viết trên một bộ đếm toàn cục đơn lẻ và các giao dịch không thành công đi kèm với nó.

Cùng với việc nhận các ID ngắn và tránh tranh cãi, tôi đang cố gắng tránh nghịch lý sinh nhật. Tôi muốn chuẩn bị cho khả năng có hàng triệu ID, ngay cả khi điều này xảy ra một chút.

Tôi đã nghĩ đến việc sử dụng một bộ đếm sharded dọc theo dòng sau đây:

• Bộ đếm là sharded trên người dùng, do đó có một mảnh cho mỗi người dùng. Mỗi đối tượng truy cập có số đếm riêng cho từng người dùng cụ thể, được tăng lên khi một mục mới được tạo bởi người dùng đó. Số đếm được tăng lên bất kể một mục được tạo thành công hay không.
• Cơ sở của ID là mã băm MD5 của chuỗi sau: "< địa chỉ email người dùng > | < giá trị cập nhật mới nhất >".
• Băm MD5 kết quả sau đó được cắt ngắn, ban đầu thành bốn ký tự.
• Giá trị "chiều dài" toàn cầu duy nhất được duy trì. Bất cứ khi nào các bước trước đó dẫn đến một khóa trùng lặp (một trong những tưởng tượng điều này sẽ xảy ra khá nhanh lúc đầu), giá trị của độ dài sẽ được tăng lên một. Băm MD5 cho ID mới giờ đây sẽ bị cắt ngắn ở các ký tự "độ dài", thay vì bốn ký tự.
• Tôi không muốn để lộ địa chỉ email của người dùng, điều này gợi ý rằng một loại băm nào đó sẽ là một cách hay.

Câu hỏi của tôi là: Tôi có nghĩ rằng điều này phần lớn sẽ tránh viết tranh chấp do các khóa trùng lặp và viết tranh chấp trên trường độ dài có thể không phải là vấn đề, đặc biệt là ở độ dài dài hơn? Bất cứ ai có thể mô tả toán học có liên quan ở đây? Liệu độ dài có tăng nhanh đến gần độ dài của một mã băm MD5, gọi vào câu hỏi giá trị của toàn bộ cách tiếp cận? Nó sẽ được tốt hơn chỉ để đi với đầy đủ (còn) MD5 băm để giữ cho mọi thứ dễ dàng hơn để duy trì? Có cái gì tôi nhìn?

Answer 1

thuật toán này là thông minh và thực sự sẽ hạn chế tối đa các hoạt động ghi. Vì vậy, giá trị độ dài sẽ hội tụ đến một sự cân bằng giữa chiều dài ngắn nhất và vắng mặt va chạm.

Bạn có thể thư giãn hạn chế không có va chạm bằng cách sử dụng các chiến lược được sử dụng trong bảng băm. Hãy thử một số ID duy nhất khác trước khi quay trở lại để tăng độ dài. Do đó, tôi đề xuất bạn thêm bộ đếm thử vào cuối chuỗi băm được khởi tạo thành 0. Nếu ID đã tạo đã được sử dụng, hãy tăng bộ đếm và thử lại cho đến khi đạt được giá trị bộ đếm tối đa sau khi bạn tăng chiều dài .

Bạn sẽ kết thúc bằng việc sử dụng không gian địa chỉ ID hiệu quả hơn và số gia hạn độ dài ít hơn nhiều.

Về câu hỏi của bạn về giới hạn độ dài MD5, tôi nghĩ rằng lựa chọn MD5 là quá mức cần thiết. Bạn không thực sự cần một băm mật mã (giả) an toàn. Những gì bạn cần là một máy phát bit ngẫu nhiên mà bạn có thể sử dụng crc32 (hoặc adler nhanh hơn). Đặc biệt là nếu mã được chạy trên điện thoại di động. Để thực hiện một trình tạo bit ngẫu nhiên với crc32, hãy thêm một giá trị 32 bit vào chuỗi để băm và khởi tạo nó với một giá trị không đổi của sự lựa chọn của bạn (hạt giống). Sau đó tính crc32 trên chuỗi này. Nếu bạn cần nhiều byte hơn, hãy ghi giá trị crc32 thu được trong 32bits ở phía trước của chuỗi và tính toán lại crc32. Lặp lại cho đến khi bạn có đủ bit. Bạn có thể thay thế crc32 bằng thuật toán bạn chọn. Điều này mang lại một bộ tạo bit ngẫu nhiên rẻ và nhanh, trong đó hằng số ban đầu là hạt giống.

Với thuật toán này, bạn giảm thiểu số lượng các bit ngẫu nhiên được tạo ra và cũng không có giới hạn chiều dài trên.

Về mã hóa, bạn không chỉ định các ràng buộc. Bạn có thể sử dụng chữ hoa và chữ thường với các chữ số không? Ví dụ của bạn sử dụng bảng chữ cái 36 giá trị ASCII khác nhau. Khi bạn có trình tạo số ngẫu nhiên giả được mô tả ở trên có thể tạo nhiều byte như mong muốn, chỉ cần xác định độ dài là số chữ cái của ID và chọn chữ cái tiếp theo với một modulo của byte ngẫu nhiên tiếp theo. Bạn sẽ biết chính xác có bao nhiêu byte để tạo ra trong một lần và tạo ID là tầm thường.

Answer 2

Làm thế nào về một cái gì đó như thế này:

1. Nếu bạn muốn 4 phím ký tự sử dụng a-zA-Z0-9, sau đó bạn sẽ phải: 62^4 => 14 triệu giá trị có thể.

2. Chia nhỏ thành N phân vùng: 0000 ... 1000, 1001 ... 2000, ..., ZZAA ...ZZZZ

   Mỗi phân vùng được đại diện bởi một thực thể có: bắt đầu id cuối id id hiện

Bây giờ, để tạo ra một ID:

1. chọn ngẫu nhiên một phân vùng. Sử dụng phím khởi động cho từng phân vùng làm khóa. Bắt đầu giao dịch:
2. get_or_create() thực thể phân đoạn đó.
3. nếu id hiện tại == cuối id, đi lại bước 1
4. tiết kiệm id hiện
5. increment hiện id bởi một End giao dịch

sử dụng id hiện tại đã được lưu lại dưới dạng id của bạn.

Nếu bạn chọn N là 140, mỗi phân vùng sẽ có 100.000 giá trị. Điều này sẽ cho phép khá một vài chèn đồng thời trong khi hạn chế số lần thử lại do chọn phân vùng "trống".

Bạn có thể cần phải suy nghĩ về điều này nhiều hơn. Đặc biệt, làm thế nào bạn sẽ xử lý các trường hợp khi bạn cần phải di chuyển đến 5 hoặc 6 chữ số?

-Dave

Answer 3

Chỉ cần thêm một số con số khó khăn cho câu hỏi trên, tôi đã thực hiện một chương trình nhỏ để tạo id dọc theo dòng đề cập trong câu hỏi, và đây là những kết quả của một trong những lần chạy thử nghiệm :

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 

Mỗi lần chiều dài băm tăng lên, điều này là do va chạm, do đó có sáu va chạm trong trường hợp này. Số đếm là số lượng khóa của một độ dài đã cho trước khi va chạm. Cột MD5 hiển thị khóa cắt ngắn cuối cùng đã được thêm thành công trước khi có lỗi khóa trùng lặp. Cột ở phía xa bên phải hiển thị khóa trong cơ sở 62 (nếu tôi đã thực hiện chuyển đổi chính xác).

Dường như ngày càng có nhiều khóa được tạo với mỗi ký tự bổ sung, đó là những gì bạn sẽ tưởng tượng. Tôi hy vọng rằng cách tiếp cận này sẽ mở rộng cho nội dung do người dùng tạo.

Đối với bất cứ ai quan tâm, đây là làm thế nào tôi có các đại diện cơ sở 62 cho cột cuối cùng:

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)) 

---

(Added sau này :)

Dưới đây là một lớp học mà sẽ chăm sóc của một số điều liên quan đến việc tạo các ID này trong ngữ cảnh của Google App Engine. Theo mặc định, các khóa được tạo bởi lớp này không hoàn toàn là cơ sở 62, vì ký tự đầu tiên của tên khóa GAE phải là chữ cái. Yêu cầu đó đã được giải quyết ở đây bằng cách sử dụng cơ số 52 cho ký tự đầu tiên.

Cơ sở chính có thể được thay đổi thành thứ gì đó khác hơn 62 bằng cách thay đổi giá trị "clist" đã được chuyển vào (hoặc bị bỏ qua) của hàm tạo. Người ta có thể muốn xóa các ký tự dễ bị nhầm lẫn, ví dụ: "1", "l", "i", v.v.

Cách sử dụng:

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

Đây là lớp:

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)