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]

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

← →
Ega23 © (2008-02-27 14:22) [29]

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

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

← →
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

← →
Jeer © (2008-02-27 15:48) [32]

> 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) можно было определить компьютер на
> котором он был создан

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

← →
Jeer © (2008-02-27 16:15) [34]

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

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

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

> Jeer © (27.02.08 16:15) [34]

это не проянило ситуации
алгоритм реверсивен?

← →
Jeer © (2008-02-27 17:21) [36]

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

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

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

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

?

← →
Jeer © (2008-02-27 17:53) [38]

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

← →
Anatoly Podgoretsky © (2008-02-27 22:43) [39]

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

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

← →
Anatoly Podgoretsky © (2008-02-27 22:44) [40]

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

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

← →
Anatoly Podgoretsky © (2008-02-27 22:50) [41]

> Jeer (27.02.2008 17:53:38) [38]

Не уловимый Джо.
Кроме того меры приняты, и не за счет выкидывания МАС, а за счет шифрования.

← →
Иксик © (2008-02-27 23:37) [42]

> Jeer © (27.02.08 15:48) [32]
>
>
> > Ega23 © (27.02.08 10:53)
>
>
> Я, вот, одного понять не могу - почему не понятен простой
> факт из комбинаторики ?
> "Число кортежей длины элементов n символов при алфавите
> объемом m символов конечно и составляет m^n"
>

> Jeer © (27.02.08 17:53) [38]
>
> Последний блок в GUID был прямо посвящен MAC.
> Т.е. был всегда одинаков для одного и того же интерфейса
> и, как бы, выдавал с головой компьютер, на котором он был
> создан.
>

Ну вот m и уменьшилось.

← →
Petr V. Abramov © (2008-02-28 00:41) [43]

знание MAC-адреса есть большой удар по privacy личных данных. особенно для пользователей популярных сайтов
:)

← →
Denis__ © (2008-02-28 11:40) [44]

А как узнать MAC-адрес? Есть для этого функции в Делфе?

← →
DVM © (2008-02-28 12:15) [45]

> Есть для этого функции в Делфе?

нет

Что-то вы много хотите в 16 байт запихнуть, уже чего только тут не упомянули. А подумать? Чтобы туда не запихнули всё равно всё сводится к 128 битам.
И не забывайте о законах Мерфи. Если что-то маловероятно, но теоретически может случиться, то оно обязательно случиться, причём так, что нанесёт наибольший возможный ущерб.

Я бы не стал забиваться на уникальность чего-то потенциально неуникального. Чего и вам желаю. Просто придумай алгоритм генерации гарантированно уникального значения, если уж ты не ограничен в ширине ключа (в разумных пределах). Вот елси бы тебе нужно было обязательно поместиться в 32 или 64 бита, тогда да, есть проблема, а так... Зачем без оглядки полагаться не нечто ненадёжное, которое теоретически может подвести, когда можно придумать надёжное?

> DVM © (27.02.08 11:49) [14]
> GUID уникален статистически, как говорится. Т.е. повторения
> возможны, но настолько редко, что ими можно пренебречь.

Присоединяюсь

> Просто придумай алгоритм генерации гарантированно уникального
> значения

Такого алгоритма не бывает.

> Jeer © (28.02.08 14:18) [49]
>
>
> > DVM © (28.02.08 12:28) [48]
>
>
> Есть статистически уникальные значения и алгоритмы для их
> генерации:))

Например GUID :))

> Такого алгоритма не бывает

При неограниченном ключе?
Бывает.
Пускай он состоит из трех частей.
В первой хранится текущее время вселенной с точностью до секунду
Во второй - текущий тик в текущей секунде(мы же знаем, сколько тиков дает проц, значит хнаем количество тиков в секунду)
В третьей - номер процессора(делаем счетчик, и каждому процессору присваиваем номер текущего счетчика, после чего счетчик инкрементируем)

Можно пример, когда такой ключ будет не уникальным?

> Можно пример, когда такой ключ будет не уникальным?

Можно. Тики и время запросто могут совпасть при генерации на разных компьютерах (по крайней мере ничего этому не мешает теоретически).

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

У процессора есть уникальный ID? Я знаю были попытки его ввести, вроде кончилось тем, что никому это не понравилось и затея умерла.
К тому же где гарантия, что в некий момент времени, некая компания "Вася Пупкин и Co" не станет выпускать свои совместимые процессоры совершенно игнорируя нумерацию Intel?

> @!!ex © (28.02.08 20:34) [51]

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

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

Всякими хитрыми манипуляциями со временем и генераторами случайных чисел мы можем получить ключи, вероятность совпадения которых будет ничтожно мала, но не 100%. НО НЕТ ГАРАНТИИ, ЧТО ВОТ ЭТИ 0.000000000000000000000000000000000000001 процента не выпадут прямо сейчас.

> НО НЕТ ГАРАНТИИ, ЧТО ВОТ ЭТИ 0.000000000000000000000000000000000000001
> процента не выпадут прямо сейчас.

Законы Мэрфи имеют приоритет над законами больших чисел
electronically tested

> DVM © (28.02.08 20:57) [52]
> > Можно пример, когда такой ключ будет не уникальным?Можно.
> Тики и время запросто могут совпасть при генерации на разных
> компьютерах (по крайней мере ничего этому не мешает теоретически).

Мы же решаем конкретную задачу? А тут, как я понял, дело происходит на одном компьютере. А в таком случае комбинации времени, номера процессора/ядра и performance counter будет более чем достаточно и, к тому же, меньше 128 бит.

Комбинация время/perfcounter решит проблему перевода времени назад. Номер ядра нужен, если дело происходит в мультитред программе или возможен запуск нескольких процессов.

Если же дело происходит на нескольких компьютерах в локальной сети, то достаточно добавить MAC адрес.

> Alex Konshin © (29.02.08 09:57) [55]
>
> > DVM © (28.02.08 20:57) [52]
> > > Можно пример, когда такой ключ будет не уникальным?Можно.
>
> > Тики и время запросто могут совпасть при генерации на
> разных
> > компьютерах (по крайней мере ничего этому не мешает теоретически).
>
>
> Мы же решаем конкретную задачу? А тут, как я понял, дело
> происходит на одном компьютере.

> Ega23 © (27.02.08 14:22) [29]
> Но тут система сильно распределённая получается.

> Вот насколько уникален?

Генерируя 1 триллион ключей каждую наносекунду, перебрать все возможные значения удастся лишь за 10 миллиардов лет

> [57] Kolan © (01.03.08 10:40)
> > Вот насколько уникален?
>
> Генерируя 1 триллион ключей каждую наносекунду, перебрать
> все возможные значения удастся лишь за 10 миллиардов лет

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

> Kolan © (01.03.08 10:40) [57]
> > Вот насколько уникален?Генерируя 1 триллион ключей каждую
> наносекунду, перебрать все возможные значения удастся лишь
> за 10 миллиардов лет

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

Кстати, даже один генератор может выдавать одинаковые ключи гораздо чаще, чем вы думаете. Чтобы они не повторялись нужно принимать особые, нетривиальные меры. Почитайте хотя бы Кнута на досуге. Учиться никогда не поздно, может ещё не все потеряно.

Еще кстати, хотел бы заметить, что именно то обстоятельство, что при генерации UUID принимает участие так много разных данных, даёт мне основание утверждать, что UUID"ы повторяются намного порядков чаще, чем могло бы быть в идеальном случае для 128 битного числа. Так что в данном случае это скорее недостаток.

> Иксик © (29.02.08 16:33) [56]
Ega23 © (27.02.08 14:22) [29]> Но тут система сильно распределённая получается.

Ну и что? Если в данном конкретном случае можно как-то различать компьютеры (для локальных сетей, например, использовать MAC), то задача решена, не так ли? Пусть ключ 64+32+48+8 и длиннее 128 бит, но зато он гарантировано уникальный для этой конкретной задачи. При других условиях можно найти и гораздо более короткий ключ.

> Alex Konshin © (02.03.08 05:08) [60]
>
> > Иксик © (29.02.08 16:33) [56]
> Ega23 © (27.02.08 14:22) [29]> Но тут система сильно распределённая
> получается.
>
> Ну и что? Если в данном конкретном случае можно как-то различать
> компьютеры (для локальных сетей, например, использовать
> MAC)

Лично мне неизвестно, что можно... Может и можно, а может и нет. Если это заставы по периметру границы, ни в какую сеть не объединенные или еще что-нибудь подобное.

>
> > Есть для этого функции в Делфе?
>
> нет

А как всё-таки узнать МАС? Неужели никто не знает?

> Denis__ © (02.03.08 14:52) [62]

Я пользовал функцию
GetAdaptersInfo(...): DWORD; stdcall; external IPHelper;
Только надо учесть, что интерфейсов может быть больше, чем один.

Да, IPHelper = "IPHlpAPI.dll";

> korneley

Сэнкс

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