Генерация уникального ссылочного номера стратегии

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

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

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

Какие стратегии я могу использовать?

10.12.2008 17:16:00
Почему последовательные числа представляют угрозу безопасности?
Juliet 10.12.2008 17:26:57
Потому что вы можете догадаться, каким будет следующий номер. Представьте себе, если ваш банк назначил номера счетов по порядку ... вы могли бы легко найти диапазоны номеров счетов.
JoshBerke 10.12.2008 17:38:50
7 ОТВЕТОВ

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

2
10.12.2008 17:18:25

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

Каков наилучший формат для номера клиента, номера заказа?

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

Например, если все клиенты будут в известной сети, вы можете завершить каждое число в блоке D ip-адреса каждого клиента.

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

2
23.05.2017 12:08:35

Обрежьте GUID до нужного вам размера.

Если вы генерируете числа, если они не случайные и не огромные, вам лучше проверить, использовались ли они в любом случае.

-1
10.12.2008 17:33:02
Я не рекомендую такой подход, если вы не добавите код для обработки коллизий.
Michael Haren 10.12.2008 17:34:07
Усечение требует мира боли - см. Этот пост stackoverflow.com/questions/352674/…
Gavin Miller 10.12.2008 17:44:40

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

Используйте GUID, но закодируйте его base64 выглядит как 7QDBkvCA1 + B9K / U0vrQx1A, который составляет 22 байта, который все еще длиннее, чем собственный Guid ... но короче, чем типичное строковое представление.

См. Текстовое кодирование здесь: http://en.wikipedia.org/wiki/Globally_Unique_Identifier

Другим вариантом будет хэширование Guid, но вы потеряете часть уникальности, так каков ваш уровень допуска для неуникальных предметов?

==========

Предполагая, что у вас есть один процесс вставки в таблицу, вы можете использовать алгоритм HiLo и быть уверенным, что вам не нужно каждый раз обращаться к БД. Вы просто сохраняете в памяти последнее высокое значение ... когда запускается процесс, вы нажимаете на БД, чтобы узнать, где вы остановились: что такое алгоритм Hi / Lo?

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

1
23.05.2017 10:27:52

Одним из способов может быть генерирование чисел на основе меньшего подмножества чисел. Например, вы можете использовать двоичную последовательность для генерации на основе нумерации Годеля. Например, отображение 000 на 111 на 5z, 3y, 2x дает 0, 2, 3, 6, 5, 10, 15, 30.

Конечно, это слишком упрощенно. Но, перебирая «соленые» числа для генерации ссылочных номеров, вам не нужно было бы вообще отслеживать ссылочные номера. При условии или, конечно, вы были достаточно уверены, что вам не нужно учитывать столкновения.

0
11.12.2008 09:14:48

Если это возможно в вашем приложении / среде, вы решили добавить время как часть к псевдослучайному числу?

т.е. microtime () + rand (10000,99999)

0
11.12.2008 09:41:35

Я делал это в производственной системе с успехом:

  • Возьмите текущее время (UTC, с точностью до микросекунды)
  • Ваш идентификатор процесса, идентификатор потока
  • Имя вашего компьютера
  • Значение соли (в основном просто строка, уникальная для вашей программы)
  • Случайное значение (предпочтительно криптографический PRNG)

Поместите это в память, либо в виде строки, либо XOR значений вместе или что-то подобное. Затем:

  • Хеш это с, например, SHA-1
  • Сделайте мод N на полученном числе, чтобы уменьшить вывод до N байтов
  • Преобразование в шестнадцатеричное или что-то для печати, если вам это нужно.

Просто помните, что сокращение UID до N байтов увеличит шансы UID-коллизий.

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

0
11.12.2008 09:50:07