Локально уникальный идентификатор

Вопрос: Если у вас есть .NET GUID для вставки в базу данных, это структура, как это:Локально уникальный идентификатор

60 bits of timestamp, 
48 bits of computer identifier, 
14 bits of uniquifier, and 
6 bits are fixed, 
---- 
128 bits total

Теперь у меня есть проблема с GUID, потому что это 128 битное число, и некоторые из БД, которые я использую, поддерживают только 64-разрядные номера.

Теперь я не хочу решать эту проблему, используя значение autointrement bigint, так как я хочу иметь возможность выполнять автономную репликацию.

Итак, у меня возникла идея создания локально уникального класса идентификатора, который в основном представляет собой идентификатор GUID, уменьшенный до 64-битного значения.

Я пришел с этим:

day 9 bit (12*31=372 d) 
year 8 bit (2266-2010 = 256 y) 
seconds 17 bit (24*60*60=86400 s) 
hostname 12 bit (2^12=4096) 
random 18 bit (2^18=262144) 
------------------------ 
      64 bits total

Мой вопрос теперь: Отметка в значительной степени фиксируется на 34 бита, оставив меня с 64-34 = 30 битов для имени хоста + случайное число.

Теперь мой вопрос: 1) Вы предпочли бы увеличить бит-имя-хэш-биты и уменьшить случайную битрейзеру, или увеличить случайную битовку и уменьшить биты имени хоста-хэша.

2) Существует ли хеш-алгоритм, который сокращает каждую строку до n-битов? n идеально = 12 или как можно ближе.

источник

2010-08-14 Stefan Steiger

На самом деле .NET-идентификаторы GUID - это 6 фиксированных бит и 122 бит случайности.

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

источник

2010-08-14 22:34:42

Существуют различные подходы; Мне также нравится идея «id узла» с меткой времени (без случайности). Вы можете легко создать идентификатор узла с любым количеством бит посредством XOR'ing криптографического хэша (например, SHA1). Чем меньше бит, тем выше вероятность столкновения с идентификатором узла, конечно. Указанный вами «uniquifier» фактически используется другими алгоритмами Guid для обработки системных часов, идущих назад, чтобы сохранить метки времени уникальными для каждого идентификатора узла. Но в конце концов вам будет трудно найти решение, которое гарантирует меньшее количество столкновений, чем чисто случайность. Помните, что это все .NET Guids do ... –

Хотя вероятность 1/2^64 все еще очень маленькая, мне не нравится мысль о чисто случайном числе. Но я подумал о том, чтобы полностью исключить хэш хоста и просто увеличить случайное число до 30 бит. Но это не очень хорошая идея, потому что для n оффлайновых клиентов это создало бы вероятность столкновения на 2^30 * n. Для 100 клиентов это всего лишь одна на 10 миллионов. С большим количеством неудач, можно просто попасть в джек-пот там ... –

1/2^64 == один из 18 септилий (один септик = один триллион один триллион, или один миллион миллионов миллионов). Если вы идете полностью случайным образом ... –

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

источник

2010-08-14 22:34:43

Тогда мне придется сравнивать два числа для каждого соединения. Разве это не слишком сильно снижает производительность? –

Хорошо, что вы будете задействовать дополнительный столбец в своем ключе [im, предполагая, что guid является ключом], поэтому вы будете иметь небольшое изменение, но таким образом вы не потеряете Руководство по системам, которые могут его поддерживать, и у вас есть обходной путь для тех, кто этого не делает. –

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

См. here для получения информации о RAND() по сравнению с NEWID() в SQL Server, что на самом деле является обвинительным заключением GUID и генераторов случайных чисел. Кроме того, см. here, если вам нужно что-то более случайное, чем System.Random.

источник

2010-08-15 02:19:21 mattmc3

Полностью случайные числа - не очень хорошая идея, ИМХО. Я не хочу беспокоиться о дубликатах и странных ошибках, поскольку база данных становится все больше и больше. По крайней мере, временная метка должна быть каким-то образом интегрирована. Хотя думать об этом, было бы разумнее оставить секунды и просто увеличить размер случайного целого. Таким образом, я могу иметь довольно длинный хэш хоста и довольно длинное случайное число. –

Локально уникальный идентификатор

ответ

Смежные вопросы