Приемлемо ли полагаться на уникальность случайных целых?

42

Я внедряю сетевой протокол, и мне требуется, чтобы пакеты имели уникальные идентификаторы. До сих пор я только что генерировал случайные 32-разрядные целые числа и предполагал, что астрономически маловероятно, что в течение срока службы программы / соединения произойдет столкновение. Это вообще считается приемлемой практикой в ​​рабочем коде, или следует разработать более сложную систему для предотвращения коллизий?

Феникс
источник
47
Почему использование последовательного целого числа не приведет к его сокращению?
whatsisname
20
Почему бы вам просто не использовать инкремент int? Идентификаторы GUID , разработанные с учетом описанных вами свойств уникальности, имеют размер 128 бит, а не 32.
Роберт Харви,
21
В качестве альтернативы, назначьте номер канала каждому подключенному компьютеру и используйте увеличивающийся идентификатор последовательности. Объединение двух чисел (с номером канала, занимающим старшие биты) становится вашим новым уникальным идентификатором.
Роберт Харви
27
Если ваш «генератор случайных чисел» гарантирует, что определенное число не будет повторяться до тех пор, пока не будет сгенерировано любое другое число, это очень плохой генератор случайных чисел! По той же логике, единственно возможная «случайная» последовательность бросков монет будет HTHTHTHTHT…
alephzero
17
«Я требую, чтобы пакеты имели уникальные идентификаторы». Каковы последствия нарушения этого требования? Если вам требуются уникальные идентификаторы, при самом строгом прочтении этого слова у вас должна быть централизованная система распределения идентификаторов (например, как MAC назначаются отдельным компаниям сетевых карт). Скорее всего, у вас есть более мягкое определение «требовать». Понимание этого уровня мягкости кардинально изменит ответы, которые вы получите.
Cort Ammon

Ответы:

142

Остерегайтесь парадокса дня рождения .

Предположим, вы генерируете последовательность случайных значений (равномерно, независимо) из набора размера N (N = 2 ^ 32 в вашем случае).

Затем практическое правило для парадокса дня рождения гласит, что после того, как вы сгенерировали значения sqrt (N), существует как минимум 50% вероятность того, что произошло столкновение, то есть, что в сгенерированная последовательность.

Для N = 2 ^ 32, sqrt (N) = 2 ^ 16 = 65536. Таким образом, после того, как вы сгенерировали около 65 000 идентификаторов, более вероятно, что два из них столкнутся, чем нет! Если вы генерируете идентификатор в секунду, это произойдет менее чем за день; Излишне говорить, что многие сетевые протоколы работают намного быстрее, чем это.

nomadictype
источник
11
+1. В моей последней работе один из наших партнеров фактически использовал этот подход для генерации случайных идентификаторов (не для сетевых пакетов, а для общего бизнес-объекта, в конечном итоге созданного конечными клиентами). Когда я запросил данные, взглянув на это, я обнаружил, что в среднем было две-три пары дубликатов каждый день. (К счастью, это сломало вещи только в том случае, если дубликаты были созданы в течение четырех часов друг от друга, что происходило немного реже. Но все же.)
ruakh
6
(нажмите здесь, чтобы отобразить математику). Приближение $ \ sqrt {N} $ стоит с точностью до постоянного множителя; для $ N = 2 ^ {32} $ фактический порог составляет 77164, так как это наименьшее значение $ n $, такое, что $ \ prod_ {k = 1} ^ {n-1} (1 - k / N) <1 / 2. $
wchargin
4
@wchargin: Нет ничего особенного в вероятности достижения 0,5; Примечательно, что вероятность увеличивается относительно быстро с увеличением N. Если бы 32-битные идентификаторы имели бы небольшую, но нетривиальную вероятность случайного столкновения, то 40-битный идентификатор почти не имел бы их.
суперкат
3
@supercat: Это все правда. Я просто подумал, что если предоставить такую ​​константу, то можно также дать точное значение :-)
wchargin
2
@wchargin: Я предпочитаю думать о том, где нужно начинать беспокоиться о дубликатах. Если человек значительно опускается ниже sqrt (N), вероятности столкновений быстро уменьшаются до такой степени, что можно смело утверждать, что они не произойдут, если в генераторе случайных чисел не будет серьезного дефекта.
суперкат
12

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

Один из алгоритмов для генерации UUID будет эффективно генерировать ID, состоящий из 122 случайных битов, и предполагать, что он будет уникальным. И два других алгоритма основаны на уникальном хэш-значении, усеченном до 122 битов, что имеет примерно такой же риск коллизий.

Таким образом, существуют стандарты, основанные на том, что 122 битов достаточно для того, чтобы случайный идентификатор был уникальным, но 32 битов явно недостаточно. С 32-битными идентификаторами требуется только около 2¹⁶ идентификаторов, прежде чем риск коллизии достигнет 50%, потому что с 2¹⁶ идентификаторами будет близко к 2¹3 парам, каждая из которых может быть коллизией.

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

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

kasperd
источник
12
SHA-1 считается небезопасным, потому что существуют определенные атаки (то есть неслучайные) против самого алгоритма, которые могут находить столкновения быстрее, чем грубая сила, а не потому, что существует высокая вероятность случайного столкновения. По приблизительным оценкам , при 122 битах и ​​скорости генерации 1 млрд. (10 ^ 9) идентификаторов в секунду потребуется 73 года, прежде чем вероятность столкновения составит 50%.
8bittree
sqrt(2^122)= 2,3 квадриллиона квадриллиона UUID
noɥʇʎԀʎzɐɹƆ
2
@ 8bittree Сеть биткойнов вычисляет 2 хэша SHA2 каждые 10 минут. Если бы это были SHA1-хэши, для создания коллизии потребовалась бы всего неделя. Если бы UUID создавались с той же скоростью, что и биткойн, вычисляет хэши, создание коллизии займет менее 2 секунд.
kasperd
Биткойн - это попытка найти коллизии, он очень популярен и имеет специальное оборудование, разработанное специально для поиска хешей. Теперь, конечно, если ОП планирует создать чрезвычайно популярную криптовалюту или что-то подобное, тогда им может потребоваться сотни или тысячи битов на идентификатор. Но сразу предположить, что это требования, может стимулировать гораздо больше работы, чем необходимо, если стандартной библиотеки UUID достаточно.
8bittree
@ 8bittree Если использование стандартных библиотек является каким-либо преимуществом, то обязательно используйте UUID. Но вытащить несколько случайных байтов urandomне сложнее, чем использовать библиотеку UUID. Я просто реализовал оба в Python для сравнения, и каждый метод был ровно 25 символов исходного кода.
kasperd
3

Я бы назвал это плохой практикой. Генераторы случайных чисел просто не создают уникальные числа, они просто создают случайные числа. Случайное распределение может включать несколько дубликатов. Вы можете сделать это обстоятельство неприемлемо маловероятным, добавив элемент времени. Если вы получите текущее время из системных часов в миллисекундах. Что-то вроде этого:

parseToInt(toString(System.currentTimeMillis()) + toString(Random.makeInt()))

Пройдет долгий путь. Очевидно, чтобы действительно гарантировать уникальность, вам нужно использовать UUID / GUID. Но они могут быть дорогими для генерации, вышеупомянутого, вероятно, достаточно, так как единственная возможность перекрытия, если случайная генерация имела дубликат в ту же миллисекунду.

Fresheyeball
источник
9
1 мс может быть долгое время в некоторых системах.
Quant_dev
7
На самом деле это вовсе не уменьшает вероятность столкновения. Вероятность столкновения после N чисел точно равна вероятности исходного решения ОП. Хитрость использования текущего времени в качестве начального числа обычно используется при последовательном назначении клавиш.
Корт Аммон
2
@Fresheyeball Я уверен, что это не имеет никакого эффекта, если Random.makeInt () фактически не генерирует равномерное распределение от минимального значения целого числа до максимального значения целого числа. Для каждого прошлого значения, сгенерированного этой функцией, есть случайное значение из makeInt, которое для этого точного временного шага генерирует это значение, создавая столкновение. Поскольку все значения из makeInt равновероятны, вероятность столкновения точно равна вероятности столкновения без добавления времени.
Cort Ammon
2
@CortAmmon это не использует текущее время в качестве начального числа , и это определенно имеет значение, если эти N чисел не были сгенерированы в течение одной миллисекунды, потому что два числа с разными частями метки времени никогда не сталкиваются. Если вы представите пример другого ответа, в котором один пакет в секунду имеет 50% -ную вероятность коллизии менее чем за один день, у этого есть 0% -ная вероятность коллизии при одном пакете в секунду, по крайней мере, до тех пор, пока не currentTimeMillisнаступит время.
Хоббс
3
@hobbs Вы забыли о целочисленном переполнении. Теперь, если ключ, используемый ОП, представлял собой структуру, содержащую 2 целых числа, одно из которых содержит, System.currentTimeMillisа другое содержит Random.makeInt(), тогда вероятность столкновения существенно снижается. Однако это не то, что делает код в этом примере. Учитывая любое предыдущее время и случайное значение, а также любое текущее время, вероятность столкновения идентична вероятности столкновения двух случайных чисел в первую очередь.
Cort Ammon
3

Это зависит как от вероятности отказа, так и от последствий отказа.

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

Майкл Кей
источник
1

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

Шон Максомт
источник
0

Можно предположить, что случайные числа будут уникальными, но вы должны быть осторожны.

Предполагая, что ваши случайные числа распределены поровну, вероятность столкновения примерно равна (n 2/2 ) / k, где n - количество генерируемых вами случайных чисел, а k - количество возможных значений, которые может принять «случайное» число.

Вы не ставите число на астрономически маловероятное, поэтому давайте возьмем его как 1 к 2 30 (примерно на миллиард). Допустим также, что вы генерируете 2 30 пакетов (если каждый пакет представляет около килобайта данных, то это означает терабайт общих данных, большой, но невообразимо большой). Мы находим, что нам нужно случайное число с по крайней мере 2 89 возможных значений.

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

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

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

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

Питер Грин
источник
0

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

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

Тем не менее, существует много систем, которые зависят от этой схемы, обычно с UUID. Например, каждый объект и ресурс в Second Life имеет 128-битный UUID, генерируемый случайным образом, и они редко сталкиваются.

Anniepoo
источник
0

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

Еще один момент: случайность не так проста, чтобы генерировать и определять, как люди могут себе представить. (На самом деле, существуют статистические тесты на случайность ).

С учетом сказанного важно осознавать заблуждение игрока , которое является статистической ошибкой, когда люди предполагают, что независимые события как-то влияют друг на друга. Случайные события, как правило, статистически независимы друг от друга, т. Е. Если вы случайным образом сгенерируете «10», это не изменит вашу будущую вероятность генерировать больше «10» в наименьшей степени. (Возможно, кто-то может придумать исключение из этого правила, но я ожидаю, что это будет иметь место практически для всех генераторов случайных чисел).

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

Еще один момент, на который следует обратить внимание: шанс выиграть Powerball от участия в одной игре, насколько я понимаю, составляет примерно 1 на 175 миллионов. Однако шансы на победу у кого-то значительно выше. Вас больше интересуют шансы того, что кто-то "выиграет" (т.е. будет дубликатом), чем шансы того или иного конкретного числа "выиграть" / быть дубликатом.

EJoshuaS - Восстановить Монику
источник
Если один генерирует 4096-битные идентификаторы таким образом, что каждый бит с одинаковой вероятностью будет равен 0 или 1 независимо от любого другого бита, который был сгенерирован в том же или любом другом идентификаторе, вероятность того, что любые два идентификатора когда-либо совпадут, будет быть исчезающе маленьким, даже если бы кто-то случайно генерировал разные идентификаторы для каждого из примерно 4.0E81 атомов в наблюдаемой вселенной. Тот факт, что такие идентификаторы почти наверняка будут уникальными, никоим образом не сделает их «неслучайными»
суперкат
@supercat Это правда - учитывая достаточно большое количество, очень маловероятно, что будут дубликаты, но это не невозможно. Это действительно зависит от того, насколько плохи последствия неединственности, является ли то, что описывает ОП, хорошей идеей.
EJoshuaS - Восстановить Монику
Если вероятность случайного столкновения меньше, чем вероятность удара метеора, уничтожающего устройства, которые полагаются на уникальные идентификаторы, с технической точки зрения нет необходимости беспокоиться о первом. Будет большая необходимость беспокоиться обо всем, что может привести к тому, что случайные числа не будут независимыми, но случайные столкновения не будут проблемой.
Суперкат
@supercat Я думаю, что вы неправильно это читаете, посмотрите другой ответ о парадоксе дня рождения, я думаю, что коллизия гораздо более вероятна, чем вы рассчитываете - ОП просто использует 32-битное число, поэтому я не уверен, где вы Мы получили 4096 от, и, как показал кочевой тип, вероятность возможного столкновения с числом этой длины на самом деле удивительно высока.
EJoshuaS - Восстановить Монику
Вы правы в том, что 32-разрядное число слишком короткое даже для небольших групп населения, если столкновения совершенно неприемлемы. Если использовать достаточно большое число, можно уменьшить вероятность случайных столкновений до точки, в которой можно смело предположить, что они просто не произойдут, и во многих случаях использование большего числа может оказаться лучше, чем попытка использовать другие средства обеспечение уникальности, поскольку для последнего обычно требуется доступ к переходам состояний, которые нельзя отменить или откатить, даже если часы системы сброшены или система перезагружена из резервной копии.
суперкат
0

Неважно, сколько битов вы используете - вы НЕ МОЖЕТЕ гарантировать, что два «случайных» числа будут разными. Вместо этого я предлагаю вам использовать что-то вроде IP-адреса или другого сетевого адреса компьютера и порядковый номер, предпочтительно БОЛЬШОЙ последовательный номер HONKIN '- 128 бит (очевидно, без знака) звучат как хорошее начало, но 256 будет лучше.

Боб Джарвис
источник
-1

Нет, конечно нет. Если только вы не используете сэмплы без замены, есть шанс - хотя и малый - дублирования.

Доктор Дрю
источник