Является ли распределение UUID равномерным? А вернее, меня интересует реализация от Microsoft — GUID.

Здравствуйте, Ka3a4oK, Вы писали:

KK>Является ли распределение UUID равномерным? А вернее, меня интересует реализация от Microsoft — GUID.

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

Здравствуйте, adontz, Вы писали:

A>Здравствуйте, Ka3a4oK, Вы писали:

KK>>Является ли распределение UUID равномерным? А вернее, меня интересует реализация от Microsoft — GUID.

A>Не совсем. UUID генерируется в том числе и на основе времени, а значит в каждый конкретный момент распределение UUID не равномерно, так как может быть сгенерированно лишь некоторое подмножемтво 128битных чисел.


В виндах начиная с 2k все уже совсем не так, буквально несколько месяцев назад дизасемблил код генерации UUID'а. Теперь там используется RC4, в качестве seed'а используется RC4(прошлый UUID) где для второго RC4 в качетсве seed'а используется псевдо-случайная последовательность от Kerberos'овского драйвера. Эта последовательность изменяется либо после определенного количества генераций UUID'ов, либо просто через некоторый промежуток времени. Какой алгоритм генерации псевдослучайной последовательности в драйвере изучать не стал, думаю что MS там много чего накрутила.

Здравствуйте, Kapany3, Вы писали:

K>В виндах начиная с 2k все уже совсем не так, буквально несколько месяцев назад дизасемблил код генерации UUID'а. Теперь там используется RC4, в качестве seed'а используется RC4(прошлый UUID) где для второго RC4 в качетсве seed'а используется псевдо-случайная последовательность от Kerberos'овского драйвера. Эта последовательность изменяется либо после определенного количества генераций UUID'ов, либо просто через некоторый промежуток времени. Какой алгоритм генерации псевдослучайной последовательности в драйвере изучать не стал, думаю что MS там много чего накрутила.


Все равно равномерность совсем дохлая.

KK>>>Является ли распределение UUID равномерным?

A>>Не совсем. UUID генерируется в том числе и на основе времени, а значит в каждый конкретный момент распределение UUID не равномерно, так как может быть сгенерированно лишь некоторое подмножемтво 128битных чисел.

K>В виндах начиная с 2k все уже совсем не так, буквально несколько месяцев назад дизасемблил код генерации UUID'а. Теперь там используется RC4, в качестве seed'а используется RC4(прошлый UUID) где для второго RC4 в качетсве seed'а используется псевдо-случайная последовательность от Kerberos'овского драйвера. Эта последовательность изменяется либо после определенного количества генераций UUID'ов, либо просто через некоторый промежуток времени. Какой алгоритм генерации псевдослучайной последовательности в драйвере изучать не стал, думаю что MS там много чего накрутила.

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

А>Насколько я знаю, в GUID (через kerberos) зашивается серийный номер сетевой карты (или ещё какого-то уникально-номерного оборудования). В любом случае, если некоторое значение может появиться на моем компьютере, вашему оно уже не светит.

Вполне возможно что этот номер как то учавствует в генерации псевдослучайноого seed'а. Но явно номер сетевухи нигде не появляется при шифровании.

Напсал простейшую программку. Программа подряд генерит 1000000 раз новый UUID и для каждого байта (если представить UUID как последовательность 128/8=16 байт) накапливает сумму на каждой итерации. В конце делим накопленную сумму на количество итераций и смотрим на результат:

[0] 0
[1] 127
[2] 127
[3] 127
[4] 127
[5] 127
[6] 127
[7] 71
[8] 159
[9] 127
[10] 127
[11] 127
[12] 127
[13] 127
[14] 127
[15] 127

Видно, что для байтов под номерами 0,7,8 распределение значений неравномерное.

Здравствуйте, Ka3a4oK, Вы писали:

KK>Видно, что для байтов под номерами 0,7,8 распределение значений неравномерное.

Это на конкретно твой версии (включая сервис паки и прочие обновления) Windows. Алгоритмы генерации UUID меняются (корректируются) от весии к версии.

KK>Напсал простейшую программку. Программа подряд генерит 1000000 раз новый UUID и для каждого байта (если представить UUID как последовательность 128/8=16 байт) накапливает сумму на каждой итерации. В конце делим накопленную сумму на количество итераций и смотрим на результат:

KK> [0] 0
KK> [1] 127
KK> [2] 127
KK> [3] 127
KK> [4] 127
KK> [5] 127
KK> [6] 127
KK> [7] 71
KK> [8] 159
KK> [9] 127
KK> [10] 127
KK> [11] 127
KK> [12] 127
KK> [13] 127
KK> [14] 127
KK> [15] 127

KK>Видно, что для байтов под номерами 0,7,8 распределение значений неравномерное.

Задача в том, чтобы генерить уникальные числа. Представим, что наш UUID — это такое огромное 128-битное целое. Вроде все ништяк, до 3400 года можно спать спокойно. Но эффективная работа с нашими структурами данных требует равномерности распределения СВ.

Идея состоит в том, чтобы эти "нервномерные" байтики сдвинуть в самое начало 128-битного числа(ноль ваще можно выкинуть). При этом мы более или мене выровняем распределение. Как вам идея ?

KK>Идея состоит в том, чтобы эти "нервномерные" байтики сдвинуть в самое начало 128-битного числа(ноль ваще можно выкинуть). При этом мы более или мене выровняем распределение. Как вам идея ?

Так может сверху еще hash-функцию какую навернуть, у которой распределение равномерное. Например MD5 (про равномерность не в курсе, надо изучать).

Здравствуйте, Kapany3, Вы писали:


KK>>Идея состоит в том, чтобы эти "нервномерные" байтики сдвинуть в самое начало 128-битного числа(ноль ваще можно выкинуть). При этом мы более или мене выровняем распределение. Как вам идея ?

K>Так может сверху еще hash-функцию какую навернуть, у которой распределение равномерное. Например MD5 (про равномерность не в курсе, надо изучать).

Алгоритм генерации UUID гарантирует (в обозримом будющем) уникальность значений. Если мы перетасуем несколько байт, то для множества UUID подвергнутых этой операции(одинакового двигания байтов) условие уникальности будет сохранятся. Hash-функция этого не гарантирует.