За счет чего обеспечивается уникальность GUID?

Question

[Надим]

Встретил такой код:

Развернуть пример

/**
 * Создает новый GUID в соответствии с RFC4122
 * https://www.ietf.org/rfc/rfc4122.txt.
 * @returns {string} - GUID. 
 */
function newGuid() {
	return "xxxxxxxx-xxxx-4xxx-yxxx-xxxxxxxxxxxx".replace(/[xy]/g, function(c) {
		var r = Math.random() * 16 | 0, 
			v = (c === "x") ? r : (r & 0x3 | 0x8);
		return v.toString(16);
	});
}

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

Comments

[Lynn «Кофеман»]

Нет там никакого «гарантированно». Есть «с очень маленькой вероятностью которой можно пренебречь».

[Надим]

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

[Andrew]

Надим Закиров, мб есть какой-то второй критерий, из-за которого вероятность этого пересечения еще
меньше(0.000001 ~ 0 )

[Lynn «Кофеман»]

Надим Закиров, если вероятность меньше чем шанс что прямо сейчас вселенная схлопнется, то не вижу никаких проблем.

[Надим]

Lynn «Кофеман», тем не менее люди как-то умудряются выигрывать безвыиграшные лотереи.
Andrew, да, возможно на сервере все же есть какая-то доп. проверка, мы просто не знаем.

[CityCat4]

Надим Закиров, Хм. Я уверен, что если бы все люди, связанные с этим "выигрышем" сказали бы правду, то выяснилось бы, что никакого выигрыша, ну то есть события, основанного на случайности - не было. Кто-то что-то где-то узнал, кто-то кому-то что-то сказал, кто-то что-то как-то подстроил... Проблема только в том, что такого рода правду люди обычно не говорят даже перед смертью.

[Aetae]

Надим Закиров, мы живём в недетерминированном мире, всегда есть маленькая вероятность всего.)
С этим можно только смириться. Шанс на коллизию uuid не больше чем шанс что космический луч испортит состояние у вас в оперативной памяти.

Ну и на сервере конечно есть ограничение на уникальность ключа в столбце, чтоб неслучайно никто ничего не поломал.

[Vitsliputsli]

Создается впечатление, что когда произошла коллизия, все падает с ошибкой, транзакция теряется и все разводят руками со словами "ну, бывает".
На самом деле, зная, что возможна коллизия, проверяйте на дубли, и в случае обнаружения, просто просите повторить с другим guid. Т.е. хотя шанс не большой, он все равно должен отрабатывать корректно.
Ну и guid бывают разные, например, для разных ДЦ правильно выбранный тип guid не будет пересекаться никогда.

[Надим]

Всем спасибо за ответы. Изучил иностранные форумы, нашел такие расчеты:

Развернуть цитату

кажется, никто не упоминает фактическую математику вероятности ее возникновения.

во-первых, предположим, что мы можем использовать все 128-битное пространство (Guid v4 использует только 122 бита).

мы знаем, что общая вероятность не получить дубликат в n выборка-это:

(1-1/2128)(1-2/2128)...(1-(n-1) / 2128)

потому что 2128 намного больше, чем n, мы можем приблизительно это:

(1-1/2128)n (n-1)/2

и потому что мы можем предположить n намного больше 0, мы можем приблизить это к:

(1-1/2128)n^2/2

теперь мы можем приравнять это к" приемлемой " вероятности, скажем, 1%:

(1-1/2128)n^2/2 = 0,01

который мы решаем для n и

n = sqrt(2 * log 0.01 / log (1-1 / 2128))

какой Вольфрам Альфа становится 5.598318 × 1019

чтобы поместить это число в перспективу, давайте возьмем 10000 машин, каждая из которых имеет 4-ядерный процессор, делает 4 ГГц и тратит 10000 циклов на создание Guid и ничего больше не делает. Это займет ~111 лет, прежде чем они создайте дубликат.

В общем, вероятность поймать дубль действительно мала, но она все же есть, если брать в расчет все компы мира, а не только 10 000 машин.

Answer 1

[Илья Салигжанов]

За счёт честного слова. Гарантии, как таковой 100%й нет, есть только крайне маленькая вероятность пересечения. Мой коллега такую вероятность словил однажды, когда не смог с ходу понять, чем вызван баг - оказалось, одинаковыми GUIDами