Случайный код из 8 символов

Question

Я получил ответы на несколько похожих вопросов, заданных на SO, но не смог найти то, что искал.

Существует ли более эффективный способ генерирования 8-значных уникальных идентификаторов, основание 36 (0-9A-Z), чем генерация уникального идентификатора и запрос к базе данных, чтобы узнать, существует ли он, и повторяется, пока вы не получите уникальный идентификатор, который не был использован?

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

Answer 1

Один из вариантов - сделать это наоборот: генерировать огромное количество из них в базе данных всякий раз, когда вам нужно, а затем либо извлекать один из БД, когда вам это нужно, либо резервировать целую кучу из них дляваш конкретный процесс (т. е. пометить их как «потенциально используемые» в базе данных), а затем выдать их из памяти.

Answer 2

Я сомневаюсь, что ваш "неэффективный" подход на самом деле неэффективен. Учтите это:

• Существует 36 ^ 8 == 2 821 109 907 456 (2,8 триллиона) возможных идентификаторов.
• Если у вас есть N существующих идентификаторов, вероятность столкновения нового случайно сгенерированного идентификатора N составляет ~ 2,8 трлн.
• Если N не исчисляется сотнями миллиардов, вы «генерируете уникальный идентификатор и запрашиваете БД, чтобы узнать, существует ли он», алгоритм почти всегда завершается за один цикл.

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

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

Но если у вас не более 150 000 идентификаторов (я полагаю, они были сгенерированы в течение длительного периода времени), то создание идентификаторов в пакетах не стоит усилий ... если только вы не выполняете операцию массовой загрузки.

Answer 3

К сожалению, 8 базовых 36 цифр немного малы.Это всего 2 миллиона миллионов возможных идентификаторов, поэтому, если вы генерируете 1,4 миллиона случайно, вероятность столкновения составляет примерно половину.

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

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

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

Answer 4

Должен ли он быть криптографически защищенным?

Если нет, pc (n) = a + bn, где b - простое число относительно 36 ^ 8.Использовать массив байтов.

foo(int n, byte[] a, byte[] b) {
  byte[] r = new byte[8];
  int carry=0;
  for(int i = 0; i<8;i++) {
    int x = carry + a[i] + n*b[i];
    r[i] = x % 36;
    carry = x / 36;      
  }
}

Answer 5

Я делаю что-то похожее для генерации кодов активации: 8-строчные строчные буквы одноразового использования.Они предназначены для использования в течение короткого времени после создания (обычно в течение нескольких минут, но, возможно, не в течение недели), но должны быть уникальными.Когда они используются, они удаляются из базы данных.

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

def _generate_code(self, length):
    random.seed()
    candidates = string.lowercase[:26]
    result = ""
    for i in range(length):
        result += random.choice(candidates)
    return result

Answer 6

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

Чтобы минимизировать требования к ОЗУ, я сохранил растровое изображение в необработанном двоичном файле и использовал ввод-вывод файла произвольного доступа для поиска байта с соответствующим битом, который мне нужно было проверить и / или установить.

Ваше намного большее пространство идентификатора потребовало бы растровое изображение 328 ГБ, что, вероятно, не может быть и речи. С другой стороны, Python set используемых идентификаторов может быть приемлемым, в зависимости от того, сколько идентификаторов, по вашему мнению, может в действительности использоваться. Другими альтернативами могут быть какой-то разреженный файл или метод разреженной матрицы, например, в scipy.sparse .

Надеюсь, это поможет.

Answer 7

Вот некоторый код на Python для генерации случайных идентификаторов base36.

import random

def base36encode(number, alphabet='0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'):
    '''
    Convert positive integer to a base36 string.

    Source: http://en.wikipedia.org/wiki/Base_36#Python_Conversion_Code
    '''
    if not isinstance(number, (int, long)):
        raise TypeError('number must be an integer')

    # Special case for zero
    if number == 0:
        return '0'

    base36 = ''

    sign   = ""
    if number < 0:
        sign  ='-'
        number=-number

    while number != 0:
        number, i = divmod(number, len(alphabet))
        base36 = alphabet[i] + base36

    return sign + base36

def generateID(length=8):
    '''Generates a base36 ID.'''

    random.seed()
    id = base36encode(random.randint(0, (36**length)-1))

    # append 0s to ensure desired length
    while len(id) < length:
        id = '0' + id

    return id

def generateMultipleIDs(n):
    '''Generate n number of unique, base36 IDs.'''

    output = set()

    while len(output) < n:
        output.add(generateID())

    return output

Answer 8

Если есть только один источник идентификаторов (то есть: вам не нужно координировать несколько независимых источников на разных машинах), вы можете сделать следующее:

• Рассчитать максимальноеколичество битов, которое может иметь число, чтобы оно не превышало информацию, содержащуюся в 8-символьной строке 0-9A-Z.Это будет floor(log2(36^8)) = 41 бит.

• иметь счетчик (с 41 битом), начинающийся с нуля

• Return transform(counter++) для каждого запроса идентификатора

Функция transform должна быть биективной и может быть произвольно длинной последовательностью следующих операций (которые сами по себе являются биективными при вычислении по модулю 2^41):

• xor с фиксированным значением
• поворот влево или вправо на фиксированное значение
• переупорядочить биты с помощью фиксированного отображения (обобщение поворота выше)
• добавить или вычесть фиксированное значение

Когда вы закончите с этим, вам понадобится только другая функция encode(number) для преобразования числа в base36.