крошечное случайное генерирование ID

Question

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

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

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

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

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

• Счетчик sharded на пользователей, так что есть осколок для каждого пользователя. Каждый объект счетчика имеет свой собственный счет, который специфичен для данного пользователя, который увеличивается, когда новый элемент создается этим пользователем. Счет увеличивается, независимо от того, успешно ли создан элемент.
• Основой идентификатора является хеш MD5 следующей строки: «< user-email-address > | < последнее значение >».
• Получившийся хеш 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 торцевую ID текущий идентификатор

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

1. случайным образом выбрать раздел. Используйте ключ запуска для каждого раздела в качестве ключа. Start Сделка:
2. get_or_create(), что элемент раздела.
3. если текущий идентификатор == конечный идентификатор, перейдите к шагу 1
4. сохранить текущий идентификатор
5. приращение тока ид одним End Transaction

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

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

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

-Dave

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="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz" 
    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='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)