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

https://stackoverflow.com/questions/815622

03-07-2019
|

Вопрос

Я пытаюсь создать уникальные идентификаторы для использования в приложении Google App Engine и хотел бы получить отзывы о возможности подхода, который я собираюсь использовать (вопросы в конце).Я прочитал довольно много вопросов на эту тему, но не помню, чтобы сталкивался с этим конкретным подходом.

Мне нужны случайные идентификаторы, например хеши MD5, но я также хочу, чтобы они были небольшими.Идеально было бы от четырех до шести символов, таких как tinyurl.Идентификаторы будут относиться к контенту, созданному пользователями, в контексте моего приложения, например, к тестовым вопросам, которые люди будут писать.Не обязательно, чтобы идентификаторы выглядели случайным образом (хорошо, если они выглядят как серийные идентификаторы), но подход, который я собираюсь использовать, позволяет это сделать, так что это не проблема.

Люди, знакомые с Google App Engine, знают, что записи в хранилище данных особенно дороги и могут привести к тайм-аутам, если их слишком много в одной группе сущностей.Сегментированные счетчики — это подход, который часто используется, чтобы избежать конфликтов при записи на один глобальный счетчик и связанных с ним неудачных транзакций.

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

Я думал об использовании сегментированного счетчика следующим образом:

Счетчик сегментирован по пользователям, так что для каждого пользователя имеется свой сегмент.Каждый объект-счетчик имеет свой собственный счетчик, специфичный для данного пользователя, который увеличивается при создании этим пользователем нового элемента.Счетчик увеличивается независимо от того, успешно ли создан элемент.
Основой идентификатора является MD5-хеш следующей строки:«<адрес-электронной почты-пользователя>|<последнее значение-счетчика>».
Полученный хэш MD5 затем усекается первоначально до четырех символов.
Поддерживается одно глобальное значение длины.Всякий раз, когда предыдущие шаги приводят к дублированию ключа (поначалу можно предположить, что это произойдет довольно быстро), значение длины будет увеличено на единицу.Хэши MD5 для новых идентификаторов теперь будут усекаться до символов «длины», а не до четырех символов.
Я не хочу раскрывать адрес электронной почты пользователя, а это говорит о том, что какой-то хеш будет хорошим способом.

Мои вопросы:Прав ли я, полагая, что это в значительной степени позволит избежать конфликтов при записи из-за дублирования ключей и что конфликты при записи в поле длины, вероятно, не будут проблемой, особенно при большей длине?Может ли кто-нибудь описать математику, задействованную здесь?Будет ли длина быстро увеличиваться почти до длины хеша MD5, ставя под сомнение ценность всего подхода?Было бы лучше просто использовать полный (более длинный) хэш MD5, чтобы упростить обслуживание?Есть ли что-то, что я упускаю из виду?

Решение

Этот алгоритм умен и действительно минимизирует операции записи.Таким образом, значение длины будет сходиться к балансу между самой короткой длиной и отсутствие столкновений.

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

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

В конечном итоге вы получите более эффективное использование адресного пространства вашего идентификатора и гораздо менее частое увеличение длины.

Что касается вашего вопроса об ограничении длины MD5, я думаю, что выбор MD5 является излишним.Вам действительно не нужен криптографический (псевдо)безопасный хэш.Что вам нужно, так это генератор случайных битов, для которого вы можете использовать crc32 (или adler, что быстрее).Особенно если код будет запускаться на мобильном телефоне.Чтобы реализовать генератор случайных битов с помощью crc32, добавьте 32-битное значение к строке для хеширования и инициализируйте ее постоянным значением по вашему выбору (начальным числом).Затем вычислите crc32 для этой строки.Если вам нужно больше байтов, запишите полученное значение crc32 в 32 бита перед строкой и пересчитайте crc32.Повторяйте, пока у вас не будет достаточно битов.Вы можете заменить crc32 алгоритмом по вашему выбору.Это дает дешевый и быстрый генератор случайных битов, в котором начальная константа является начальным числом.

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

Что касается кодирования, вы не указали ограничения.Можете ли вы использовать заглавные и строчные буквы вместе с цифрами?В вашем примере используется алфавит из 36 различных значений ASCII.Если у вас есть описанный выше генератор псевдослучайных чисел, который может генерировать столько байтов, сколько необходимо, просто определите длину как количество букв вашего идентификатора и выберите следующую букву по модулю следующего случайного байта.Тогда вы точно будете знать, сколько байт нужно сгенерировать за один раз, а генерация идентификатора не составит труда.

Другие советы

Как насчет чего-то вроде этого:

Если вам нужны 4-символьные клавиши с использованием a-zA-Z0-9, вам нужно:62^4 = > 14 миллионов возможных значений.
Разбейте это на N разделов:0000...1000, 1001...2000, ..., ЗЗАА...ЗЗЗЗ

Каждый раздел представлен сущностью с:Идентификатор начала идентификатора текущего идентификатора

Теперь, чтобы сгенерировать идентификатор:

случайным образом выберите раздел.Используйте стартовый ключ для каждого раздела в качестве ключа.Начать транзакцию:
get_or_create() этот объект раздела.
если текущий идентификатор == конечный идентификатор, перейдите к шагу 1
сохранить текущий идентификатор
Идентификатор тока увеличения на одну конечную транзакцию

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

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

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

-Дэйв

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

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)

Лицензировано под: CC-BY-SA с атрибуция

Не связан с StackOverflow