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

Question

Мне нужно сгенерировать 10-значный уникальный идентификатор (люди SIP/VOIP должны знать, что это значение параметра в заголовке P-Charging-Vector). Каждый символ должен быть одним из 26 букв ASCII (с учетом регистра), одной из десяти цифр ASCII или дефиса-минуса.

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

Вот мой пример. Я ПЕРВАЯ кодировка «ДОЛЖЕН» быть закодированным глобально уникальным локальным IP-адресом в base-63 (его беззнаковый длинный int, который будет занимать 1-6 символов после кодирования), а затем насколько это возможно для текущей метки времени (ее long_t/long long int, который будет занимать 9-4 символа после кодирования в зависимости от того, сколько места занимает зашифрованный ip-адрес).

Я также добавил число циклов 'i' к отметке времени, чтобы сохранить уникальность в случае, если функция вызывается более одного раза в секунду.

Достаточно ли этого, чтобы быть глобально и локально уникальным или есть другой лучший подход?

Gaurav

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

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

// 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; 

    //printf("index=%d,longlong=%lld,longlong%63=%lld\n",index,longlong,longlong%63); 
    if(longlong < 63){ 
     x[index] = set[longlong]; 
     return index+1; 
    } 

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

int main(){ 
    char x[11],y[11] = {0}; /* '\0' is taken care of here */ 

    //let's generate 10 million ids 
    for(int i=0; i<10000000; i++){ 

     /* add i to timestamp to take care of sub-second function calls, 
      3770168404(is a sample ip address in n/w byte order) =    84.52.184.224 */ 
     b63((long long)time(NULL)+i,x,b63((long long)3770168404,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); 
    } 

    return 0; 
} 

Answer 1

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

Answer 2

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

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

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

Answer 3

Он должен быть «глобально уникальным (за пределами машины, генерирующего идентификатор)» и достаточно «локально уникальным (в пределах машины генерации идентификатора) ', и все, что нужно упаковать в 10 персонажей, фу!

Вы управляете всеми идентификаторами программного обеспечения? Вы разыскиваете иды? Если нет ...

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

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

Answer 4

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

Answer 5

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

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

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

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

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

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

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

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

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

Answer 6

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

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

Answer 7

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

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

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

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

Gaurav

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

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

// 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; 
}