крошечное случайно выглядящее идентификационное поколение

How about something like this:

1. If you want 4 character keys using a-zA-Z0-9, then you'd have: 62^4 = > 14 million possible values.

2. Break this up into N partitions: 0000 ... 1000, 1001 ... 2000 , ... , ZZAA ... ZZZZ

   Each partition is represented by an entity with: start id end id current id

Now, to generate an ID:

1. randomly pick a partition. Use the start key for each partition as a key. Начать транзакцию:
2. get_or_create () этой сущности раздела.
3. если текущий идентификатор == конечный идентификатор, перейти к шагу 1
4. сохранить текущий идентификатор
5. увеличить текущий идентификатор на единицу Завершить транзакцию

использовать текущий идентификатор, который был сохранен в качестве вашего идентификатора.

Если вы выберете N равным 140, у каждого раздела будет 100 000 значений. Это позволило бы довольно много одновременных вставок при ограничении количества повторных попыток из-за выбора «пустого» раздела.

Возможно, вам нужно подумать об этом больше. Особенно, как вы справитесь со случаем, когда вам нужно перейти на 5 или 6-значные клавиши?

-Dave

Просто для того, чтобы добавить некоторые жесткие числа к вопросу выше, я реализовал небольшую программу для генерации идентификаторов в соответствии с линиями, упомянутыми в вопросе, и это были результаты одного из пробных прогонов :

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 (если я правильно сделал преобразование).

Похоже, что с каждым дополнительным символом генерируется все больше и больше ключей, что вы и представляете. Я надеюсь, что этот подход будет масштабироваться для пользовательского контента.

Для всех, кто интересуется, вот как я получил представление base 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)