GUID - насколько уникален?

← →
Ega23 © (2008-02-27 10:53) [0]

На одном и том же компьютере поток событий ~ 1000 в секунду. Для каждого генерится GUID. Будет ли он уникальным, или нет?

З.Ы. Только не надо сейчас разговоров начинать: "А почему не воспользоваться обычныч счётчиком? А ты уверен, что у тебя всё нормально с архитектурой? " и т.п. :)

← →
Kerk © (2008-02-27 10:54) [1]

Будет уникальным. Ибо кроме привязки к железу там и текущее время задействовано.

ты уверен, что у тебя всё нормально с архитектурой?

← →
Ega23 © (2008-02-27 10:55) [2]

> ты уверен, что у тебя всё нормально с архитектурой?

Не уверен. :)
Но пока не от меня зависит... :)

← →
www (2008-02-27 10:56) [3]

> поток событий ~ 1000 в секунду. Для каждого генерится GUID

а успеет?

← →
Reindeer Moss Eater © (2008-02-27 10:59) [4]

На одном и том же компьютере .....

Вообще не вопрос.

← →
@!!ex © (2008-02-27 10:59) [5]

Честно говоря не ожидал такого вопроса...
Вроде этож прописные истины.
GUID уникален. Проблемы могут быть только, если он генерится на левом железе.

← →
Ega23 © (2008-02-27 11:01) [6]

> GUID уникален

Вот насколько уникален? С каким допуском берётся текущее время? Просто в MSSQL, например, хоть убейся - дискрет 3 миллисекунды.

← →
isasa © (2008-02-27 11:04) [7]

Единственная проблема заздача GUID-ов может кончится :)

← →
Григорьев Антон © (2008-02-27 11:15) [8]

Там ещё MAC-адрес сетевой карты берётся. И что-то краем уха я слышал, что MS наезжал на китайских производителей сетевух, что те, мол, не следят за уникальностью своих MAC"ов, из-за этого GUID"ы могут получаться одинаковыми.

← →
Dimka Maslov © (2008-02-27 11:16) [9]

GUID включает в себя МАС-адрес сетевого адаптера, текущее время и некое число, зависящее от количества переводов системных часов назад. Начиная с Windows2000 от этого дела вычисляется ещё и MD5. Так что GUID - действительно уникален.

← →
isasa © (2008-02-27 11:18) [10]

Ega23 © (27.02.08 11:01) [6]
Просто в MSSQL, например, хоть убейся - дискрет 3 миллисекунды.

:)
Уроды. И при этом они ухитряются проиндексировать уникальными ключами реплицируемые таблицы ...

← →
Rouse_ © (2008-02-27 11:19) [11]

Все еще зависит от операционки. В свое время под 98-ым мы натыкались на коллизию двух парных гуидов...

← →
Григорьев Антон © (2008-02-27 11:20) [12]

Вообще, алгоритм генерации GUID"а надо искать не в MS"овской документации, а в первоисточнике, стандартах OSF (конкретно - DCE RPC). Что-нибудь типа этого: http://www.opengroup.org/onlinepubs/9629399/apdxa.htm#tagcjh_20

← →
Григорьев Антон © (2008-02-27 11:25) [13]

Вот что нашёл в стандарте:

Clock Overrun

The 100 nanosecond granularity of time should prove sufficient even for bursts of UUID creation in the next generation of high-performance multiprocessors. If a system overruns the clock adjustment by requesting too many UUIDs within a single system clock tick, the UUID service may raise an exception, handled in a system or process-dependent manner either by:

- terminating the requester

- reissuing the request until it succeeds

- stalling the UUID generator until the system clock catches up.

← →
DVM © (2008-02-27 11:49) [14]

GUID уникален статистически, как говорится. Т.е. повторения возможны, но настолько редко, что ими можно пренебречь.

← →
Eraser © (2008-02-27 12:34) [15]

> Ega23 © (27.02.08 10:53)

> Будет ли он уникальным, или нет?

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

← →
@!!ex © (2008-02-27 12:38) [16]

> при условии что 1000 в секунду

Что за бред???

← →
@!!ex © (2008-02-27 12:42) [17]

Может я скажу новость, но уникальность GUID"a никак от частоты генерации не зависит.
Да и вообще, GUID НЕ МОГУ закончится... вернее могут... к 3400 году... если это кого-то волнует...

← →
@!!ex © (2008-02-27 12:44) [18]

Юмор в тему:
http://blogs.byte-force.com/xor/archive/2004/11/15/352.aspx

← →
Eraser © (2008-02-27 12:53) [19]

))

← →
isasa © (2008-02-27 13:09) [20]

Юмор в тему.
А что быстрее, сгенерировать GUID, или создать поток?

← →
TUser © (2008-02-27 13:12) [21]

Если все компьютеры мира будут генерить GUID с какой-то бешенойскоростью, то вероятность повторения за черти-какое время (то ли за год, толи за вресмя существования Вселенной) не превышает пяти процентов. Уникальным он будет.

← →
Иксик © (2008-02-27 13:33) [22]

Ну если 1000 в секунду, то имхо, если у меня голова с утра варит, вероятность повторения будет 1000*количество секунд/2^128 или же примерно количество секунд/2^118. То есть вероятность повторения в сутки - где-то 1/2^100, в год - где-то 1/2^90 ~= 1/10^26. Я очень сильно округлял, чтобы просто показать порядки.

Вероятность 1/10^26 в год - это очень маленькая вероятность. Может я неправильно считаю...

Черт, я же зарекся сюда писать... Надеюсь это будет мой последний пост :)

← →
Правильный_Вася (2008-02-27 13:39) [23]

> вероятность повторения за черти-какое время (то ли за год,
> толи за вресмя существования Вселенной) не превышает пяти
> процентов. Уникальным он будет.

если вероятность > 0, значит, гарантий уникальности быть не может
может быть только ощущение уникальности
а при возможной смене железа - так и вообще

← →
Ega23 © (2008-02-27 13:42) [24]

> Иксик © (27.02.08 13:33) [22]

Дань, ты не прав. Тут надо рассматривать не всё возможное множество GUIDов, а именно сгенерённое на данной машине. Вот если представить, что GUID генерится каждые 10 наносекунд (100 миллионов в секунду), то тут вероятность повторения будет очень высокая, т.к. в алгоритме кроме всяких MAC-адресов (который для даннолй машины - один и тот же) используется текущее время. Причём время в дискретной системе не есть вещь абсолютная.
Собственно, меня интересовал тот минимальный временной интервал, для которого гарантируется уникальность GUID на уровне алгоритма генерации.

← →
@!!ex © (2008-02-27 13:48) [25]

> [24] Ega23 © (27.02.08 13:42)

Там кроме времени еще и случайные числа используются.
Кстати, если при генерации используется QueryPerformanceCounter то частота генерации неважна, все равно уникально будет.

← →
DiamondShark © (2008-02-27 13:48) [26]

> Вот если представить, что GUID генерится каждые 10 наносекунд
> (100 миллионов в секунду), то тут вероятность повторения
> будет очень высокая, т.к. в алгоритме кроме всяких MAC-адресов
> (который для даннолй машины - один и тот же) используется
> текущее время

Ну так генератор тебе просто не даст сгенерировать гуиды с частотой, превышающей дискретность таймера. Делов-то.

> Собственно, меня интересовал тот минимальный временной интервал,
> для которого гарантируется уникальность GUID на уровне
> алгоритма генерации.

Нижняя оценка -- дискретность системного таймера. В реальности может и хуже.

← →
Иксик © (2008-02-27 13:59) [27]

> Ega23 © (27.02.08 13:42) [24]
>
>
> > Иксик © (27.02.08 13:33) [22]
>
>
> Дань, ты не прав. Тут надо рассматривать не всё возможное
> множество GUIDов, а именно сгенерённое на данной машине.

Разумеется, просто не зная точного алгоритма генерации невозможно сказать какое подмножество значений 2^128 возможно на этой машине, а следовательно невозможно точно определить вероятность. Я брал максимум.

> Вот если представить, что GUID генерится каждые 10 наносекунд
> (100 миллионов в секунду), то тут вероятность повторения
> будет очень высокая, т.к. в алгоритме кроме всяких MAC-адресов
> (который для даннолй машины - один и тот же) используется
> текущее время.

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

← →
ANB (2008-02-27 14:12) [28]

При достаточно высокой скорости закачки данных скорее всего тормоза возникнут именно из-за генерации гуидов. Счетчик таки крутить быстрее.

> Счетчик таки крутить быстрее.

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

← →
Dust (2008-02-27 14:59) [30]

Удалено модератором

← →
Strate (2008-02-27 15:22) [31]

"Алгоритм, который Microsoft использовала для генерации GUID, был широко раскритикован. В частности, в качестве основы для генерации части цифр GUID использовался MAC-адрес сетевого адаптера, что означало, например, что по данному документу MS Word (также получающему при создании свой уникальный GUID) можно было определить компьютер на котором он был создан. Позже Microsoft изменила алгоритм таким образом, что теперь он не включает в себя MAC-адрес."

(c) Wiki

> Ega23 © (27.02.08 10:53)

Я, вот, одного понять не могу - почему не понятен простой факт из комбинаторики ?
"Число кортежей длины элементов n символов при алфавите объемом m символов конечно и составляет m^n"

И при чем тут MAC, system time, system slice и прочая требуха ?
Как бы они не имплантировались в алгоритм.

С равным успехом можно пользоваться RND-генератором желаемой длины.
Не достаточно 2^128 - используешь 2^1024 и т.п.

← →
Правильный_Вася (2008-02-27 15:49) [33]

> по данному документу MS Word (также получающему при создании
> свой уникальный GUID) можно было определить компьютер на
> котором он был создан

а что, алгоритм реверсивен?

> Правильный_Вася (27.02.08 15:49) [33]
>
>

Эта история насчет Office 97. Затем MS ушла от встраивания MAC.

← →
Правильный_Вася (2008-02-27 17:16) [35]

Нет.
Равно как и нормальный хэш.
Для быстро следущих запросов дополнительно используется инкремент.

← →
Правильный_Вася (2008-02-27 17:43) [37]

> Нет.Равно как и нормальный хэш.

так в чем тогда был страх
> по GUID определить компьютер на котором он был создан

?

Последний блок в GUID был прямо посвящен MAC.
Т.е. был всегда одинаков для одного и того же интерфейса и, как бы, выдавал с головой компьютер, на котором он был создан.

> isasa (27.02.2008 11:04:07) [7]

Обязательно кончится, через 2^118 секунд

> Григорьев Антон (27.02.2008 11:15:08) [8]

Наезжали не из-за этого, локальная сеть с одинаковыми МАС адресами принципиально работать не может

GUID - насколько уникален? Найти похожие ветки