Идентификатор из 10 символов, уникальный глобально и локально

Он ДОЛЖЕН быть «глобально уникальным (за пределами машины, генерирующей идентификатор)» и достаточно «локально уникальным (внутри машины, генерирующей идентификатор)», и все это должно быть упаковано в 10 символов, уф!

Вы контролируете все программы, генерирующие идентификаторы? Вы раздаете идентификаторы? Если не...

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

Я бы вернулся к документации SIP, посмотрел, есть ли приложение с алгоритмом генерации этих идентификаторов. Или, может быть, более умный пользователь SO, чем я, может ответить, что такое алгоритм SIP для генерации этих идентификаторов.

Я бы серьезно посмотрел на RFC 4122, в котором описывается создание 128-битных идентификаторов GUID. Существует несколько различных алгоритмов генерации, некоторые из которых могут подойти (на ум приходит алгоритм на основе MAC-адреса). Это большее числовое пространство, чем ваше 2 ^ 128 = 3,4 * 10 ^ 38 по сравнению с 63 ^ 10 = 9,8 * 10 ^ 17, поэтому вам, возможно, придется пойти на некоторые компромиссы в отношении уникальности. Учитывайте такие факторы, как частота генерации идентификаторов.

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

Разве вы не можете просто иметь распределенную таблицу идентификаторов?

Машины в локальных сетях с NAT часто будут иметь IP-адрес из небольшого диапазона, и не все 32-битные значения будут действительными (например, многоадресная рассылка и т. д.). Машины также могут получать одну и ту же метку времени, особенно если степень детализации велика (например, секунды); имейте в виду, что год очень часто будет одним и тем же, поэтому именно младшие биты дадут вам наибольшую «уникальность».

Вы можете взять различные значения, хэшировать их с помощью криптографического хэша и преобразовать в символы, которые вам разрешено использовать, усекая до 10 символов.

Но вы имеете дело со значением менее 60 бит; вам нужно тщательно подумать о последствиях столкновения. Возможно, вы неправильно подходите к проблеме...

Что ж, если я отброшу тот факт, что считаю это плохой идеей, и сконцентрируюсь на решении вашей проблемы, вот что я бы сделал:

У вас есть диапазон идентификаторов 10 ^ 63, что соответствует примерно 60 битам. Вы хотите, чтобы он был как «глобально», так и «локально» уникальным. Давайте сгенерируем первые N битов, чтобы они были глобально уникальными, а остальные — локально уникальными. Конкатенация двух будет иметь свойства, которые вы ищете.

Во-первых, глобальная уникальность: IP не подойдут, особенно локальные, они держат очень мало энтропии. Я бы выбрал MAC-адреса, они были созданы для того, чтобы быть глобально уникальными. Они охватывают диапазон 256 ^ 6, поэтому использование 6 * 8 = 48 бит.

Теперь о локальном уникальном: почему бы не использовать идентификатор процесса? Я делаю предположение, что уникальность для каждого процесса, если это не так, вам придется думать о чем-то другом. В Linux идентификатор процесса составляет 32 бита. Если бы мы хотели придраться, 2 самых значащих байта, вероятно, содержали бы очень небольшую энтропию, поскольку на большинстве машин они были бы равны 0. Так что откажитесь от них, если вы знаете, что делаете.

Итак, теперь вы увидите, что у вас есть проблема, поскольку для создания приличного (но не пуленепробиваемого) глобального и локального уникального идентификатора потребуется до 70 бит (в любом случае с использованием моей техники). А так как я бы еще посоветовал на всякий случай подставить случайное число (длиной не менее 8 бит), то оно точно не подойдет. Так что на вашем месте я бы хешировал ~78 сгенерированных битов в SHA1 (например) и преобразовывал первые 60 бит полученного хэша в формат вашего идентификатора. Для этого обратите внимание, что у вас есть диапазон из 63 символов, то есть почти полный диапазон из 6 бит. Итак, разделите хэш на 6-битные части и используйте первые 10 частей, чтобы выбрать 10 символов вашего идентификатора из 63-символьного диапазона. Очевидно, диапазон 6 битов составляет 64 возможных значения (вам нужно только 63), поэтому, если у вас есть 6-битная часть, равная 63, либо уменьшите ее до 62, либо примите по модулю 63 и выберите 0. Это немного сместит распределение, но это не так уж плохо.

Итак, это должно дать вам приличный глобально и локально псевдоуникальный идентификатор.

Несколько последних замечаний: согласно парадоксу дня рождения, вы получите ~ 1 % шанс коллизий после генерации ~ 142 миллионов идентификаторов и вероятность 99% после генерации 3 миллиардов идентификаторов. Поэтому, если вы добились большого коммерческого успеха и создали миллионы идентификаторов, приобретите идентификатор большего размера.

Наконец, я думаю, что предоставил решение вашей проблемы «лучшее, чем худшее», но я не могу не думать, что вы решаете эту проблему неправильным образом и, возможно, как уже упоминалось, неправильно читаете спецификации. Так что используйте это, если нет других способов, которые были бы более «пуленепробиваемыми» (централизованный провайдер ID, гораздо более длинный ID...).

Редактировать: я перечитал ваш вопрос, и вы говорите, что вызываете эту функцию, возможно, много раз в секунду. Я предполагал, что это должно было служить своего рода идентификатором приложения, сгенерированным один раз в начале вашего приложения и никогда не изменявшимся впоследствии, пока оно не завершилось. Поскольку это не так, вам определенно следует добавить случайное число, и если вы генерируете много идентификаторов, сделайте это как минимум 32-битным числом. И читайте и перечитывайте «Парадокс дня рождения», на который я ссылался выше. И задайте генератору чисел высокоэнтропийное значение, например, значение usec текущей метки времени. Или даже зайти так далеко, чтобы получить ваши случайные значения из /dev/urandom . Честно говоря, я считаю, что 60 бит, вероятно, недостаточно...

Хм, использование системных часов может быть слабостью... что, если кто-то переведет часы назад? Вы можете снова сгенерировать тот же идентификатор. Но если вы собираетесь использовать часы, вы можете вызвать gettimeofday() вместо time(); по крайней мере, таким образом вы получите лучшее разрешение, чем одна секунда.

@ Дуг Т. Нет, я не контролирую все программное обеспечение, генерирующее идентификаторы. Согласен без стандартизированного алгоритма возможны коллизии, я поднимал этот вопрос в соответствующих списках рассылки.

@Florian Принимая во внимание ваш ответ. Я решил использовать /dev/urandom PRNG для 32-битного случайного числа в качестве пространственного уникального компонента идентификатора. Я предполагаю, что каждая машина будет иметь свою собственную шумовую сигнатуру, и можно предположить, что она безопасно глобально уникальна в пространстве в данный момент времени. Уникальный компонент времени, который я использовал ранее, остается прежним.

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

Вот обновленный код ниже:

Гаурав

 #include <stdio.h>
 #include <string.h>
 #include <time.h>

 //base-63 character set
 static char set[]="abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789-";

 // b63() returns the next vacant location in char array x
 int b63(long long longlong, char *x, int index){
     if(index > 9)
         return index+1;

     if(longlong < 63){
         x[index] = set[longlong];
         return index+1;
     }  

     x[index] = set[longlong%63];
     return b63(longlong/63, x, index+1);
 }

 int main(){
     unsigned int number;
     char x[11], y[11] = {0};

     FILE *urandom = fopen("/dev/urandom", "r");
     if(!urandom)
         return -1;

     //let's generate a 1 billion ids
     for(int i=0; i<1000000000; i++){

         fread(&number, 1, sizeof(number), urandom);

         // add i to timestamp to take care of sub-second function calls, 
         b63((long long)time(NULL)+i, x, b63((long long)number, x, 0));

         // reverse the char array to get proper base-63 output
         for(int j=0, k=9; j<10; j++, k--)
             y[j] = x[k];

         printf("%s\n", y);
     }

     if(urandom)
     fclose(urandom);

     return 0;
 }