Создание v5 UUID. Что такое имя и пространство имен?

125

Я прочитал эту manстраницу, но не понимаю, что nameи namespaceдля чего.

Для UUID версий 3 и 5 необходимо указать пространство имен и имя дополнительных аргументов командной строки. Пространство имен является либо UUID в строковом представлении, либо идентификатором для внутренних предопределенных UUID пространства имен (в настоящее время известны «ns: DNS», «ns: URL», «ns: OID» и «ns: X500»). Имя представляет собой строку произвольной длины.

Пространство имен:

Пространство имен представляет собой либо UUID в строковом представлении, либо

Означает ли это, что мне нужно сохранить его (UUID v4) где-нибудь в связи со сгенерированным UUID v5? В любом случае, почему это не делается автоматически?

Имя представляет собой строку произвольной длины.

nameполностью случайная строка? В чем тогда его цель? Можно ли его декодировать из UUID v5?

uuid Gajus
источник

Ответы:

106

Имя и пространство имен могут использоваться для создания иерархии (очень вероятно) уникальных UUID.

Грубо говоря, UUID типа 3 или 5 генерируется путем хеширования идентификатора пространства имен с именем. UUID типа 3 используют MD5, а UUID типа 5 используют SHA1. Доступны только 128-битные, и 5-битные используются для указания типа, поэтому все хеш-биты не попадают в UUID. (Также MD5 считается криптографически сломанным, а SHA1 находится на последнем издыхании, поэтому не используйте его для проверки данных, которые должны быть «очень безопасными»). Тем не менее, это дает вам способ создания повторяемой / проверяемой «хеш-функции», отображающей возможное иерархическое имя на вероятностно уникальное 128-битное значение, потенциально действующее как иерархический хэш или MAC.

Предположим, у вас есть хранилище (ключ, значение), но оно поддерживает только одно пространство имен. Вы можете сгенерировать большое количество различных логических пространств имен, используя UUID типа 3 или 5. Сначала создайте корневой UUID для каждого пространства имен. Это может быть UUID типа 1 (хост + временная метка) или типа 4 (случайный), если вы его где-то спрятали. В качестве альтернативы вы можете создать один случайный UUID для вашего корня (или использовать nullUUID: в 00000000-0000-0000-0000-000000000000качестве root), а затем создать воспроизводимый UUID для каждого пространства имен с помощью " uuid -v5 $ROOTUUID $NAMESPACENAME". Теперь вы можете создавать уникальные UUID для ключей в пространстве имен, используя "uuid -v5 $NAMESPACEUUID $KEY". Эти UUID могут быть помещены в одно хранилище" ключ-значение "с высокой вероятностью избежания коллизии. Этот процесс можно повторять рекурсивно, так что если, например," значение ", связанное с ключом UUID, в свою очередь, представляет своего рода логическое" пространство имен " "как корзина, контейнер или каталог, то его UUID можно использовать, в свою очередь, для генерации более иерархических UUID.

Сгенерированный UUID типа 3 или 5 содержит (частичный) хэш идентификатора пространства имен и имени в пространстве имен (ключа). Он не больше содержит UUID пространства имен, чем MAC сообщения содержит содержимое сообщения, из которого он закодирован. Имя представляет собой «произвольную» (октетную) строку с точки зрения алгоритма uuid. Однако его значение зависит от вашего приложения. Это может быть имя файла в логическом каталоге, идентификатор объекта в хранилище объектов и т. Д.

Хотя это хорошо работает для умеренно большого количества пространств имен и ключей, в конечном итоге он выдыхается, если вы стремитесь к очень большому количеству уникальных ключей с очень высокой вероятностью. Запись в Википедии о проблеме дня рождения (также известная как парадокс дня рождения) включает таблицу, которая дает вероятности хотя бы одного столкновения для различного количества ключей и размеров таблиц. Для 128-битного хэширования 26 миллиардов ключей таким образом имеет вероятность коллизии p=10^-18(ничтожно мала), но 26 триллионов ключей увеличивают вероятность хотя бы одного коллизии до p=10^-12(одного на триллион), а хеширование 26*10^15ключей увеличивает вероятность хотя бы одно столкновение сp=10^-6(один из миллиона). С поправкой на 5 бит, которые кодируют тип UUID, он будет работать несколько быстрее, поэтому триллион ключей имеет примерно 1-триллионный шанс столкнуться с одним конфликтом.

См. Http://en.wikipedia.org/wiki/Birthday_problem#Probability_table для таблицы вероятностей.

См. Http://www.ietf.org/rfc/rfc4122.txt для получения дополнительной информации о кодировках UUID.

Джефф Андерсон-Ли
источник
2
Могу ли я на определенном уровне ниже по иерархии использовать UUIDv5 в качестве пространства имен и UUIDv4 в качестве случайного ключа, чтобы гарантировать, что конфликты в самих данных (которые идентифицируются этим GUID) не увеличивают шансы столкновения UUID? Какие-либо проблемы с производительностью, о которых мне следует знать?
ermik
Я новичок в этой концепции и был озадачен тем, что это за иерархия, о которой вы говорите. Где я могу это увидеть и т. Д. Некоторая ясность пришла, когда я застрял в объяснении, это может быть использовано для создания воспроизводимого UUID для пространства имен . Мне интересно, есть ли способ проверить, что данный UUID (типа 3 или 5) был сгенерирован с использованием определенного пространства имен (его UUID)?
msciwoj
213

UUID типов 3 и 5 - это просто метод вставки хэша в UUID.

Хэш SHA1 выводит 160 бит (20 байтов); результат хеширования преобразуется в UUID.

С 20-байтовым хешем из SHA1:

SHA1 Digest:   74738ff5 5367 e958 9aee 98fffdcd1876 94028007
UUID (v5):     74738ff5-5367-5958-9aee-98fffdcd1876
                             ^_low nibble is set to 5, to indicate type 5
                                  ^_first two bits set to 1 and 0, respectively

(Обратите внимание, что первые два бита «9» уже равны 1 и 0 соответственно, поэтому это не имеет никакого эффекта).

Что мне хэшировать?

Вам, наверное, интересно, что я должен хешировать. В основном вы хешируете конкатенацию:

sha1([NamespaceUUID]+[AnyString]);

Вы префикс своей строки так называемым пространством имен, чтобы предотвратить конфликты имен .

В UUID RFC предварительно определены четыре пространства имен:

  • NameSpace_DNS: {6ba7b810-9dad-11d1-80b4-00c04fd430c8}
  • NameSpace_URL: {6ba7b811-9dad-11d1-80b4-00c04fd430c8}
  • NameSpace_OID: {6ba7b812-9dad-11d1-80b4-00c04fd430c8}
  • NameSpace_X500: {6ba7b814-9dad-11d1-80b4-00c04fd430c8}

Итак, вы можете хешировать:

StackOverflowDnsUUID = sha1(Namespace_DNS + "stackoverflow.com");
StackOverflowUrlUUID = sha1(Namespace_URL + "stackoverflow.com");

Затем RFC определяет, как:

  • взять 160 бит из SHA1
  • и преобразовать его в 128 бит UUID

Основная суть состоит в том, чтобы взять только первые 128 бит, вставить 5в запись типа , а затем установить первые два бита clock_seq_hi_and_reservedраздела на 1 и 0 соответственно.

Еще примеры

Теперь, когда у вас есть функция, которая генерирует так называемое имя , вы можете иметь функцию (в псевдокоде):

UUID NameToUUID(UUID NamespaceUUID, String Name)
{
    byte[] hash = sha1(NamespaceUUID.ToBytes() + Name.ToBytes());
    UUID result;
    Copy(hash, result, 16);
    result[6] &= 0x0F; 
    result[6] |= 0x50;
    result[8] &= 0x3F; 
    result[8] |= 0x80;
    return result;
}

(Обратите внимание, что порядок байтов вашей системы может повлиять на индексы вышеуказанных байтов)

Вы можете звонить:

uuid = NameToUUID(Namespace_DNS, 'www.stackoverflow.com');
uuid = NameToUUID(Namespace_DNS, 'www.google.com');
uuid = NameToUUID(Namespace_URL, 'http://www.stackoverflow.com');
uuid = NameToUUID(Namespace_URL, 'http://www.google.com/search&q=rfc+4112');
uuid = NameToUUID(Namespace_URL, 'http://stackoverflow.com/questions/5515880/test-vectors-for-uuid-version-5-converting-hash-into-guid-algorithm');

Теперь вернемся к вашему вопросу

Для UUID версий 3 и 5 необходимо указать пространство имен и имя дополнительных аргументов командной строки. Пространство имен является либо UUID в строковом представлении, либо идентификатором для внутренних предопределенных UUID пространства имен (в настоящее время известны «ns: DNS», «ns: URL», «ns: OID» и «ns: X500»). Имя представляет собой строку произвольной длины.

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

UUID Namespace_RectalForeignExtractedObject = '8e884ace-bee4-11e4-8dfc-aa07a5b093db'

Имя представляет собой строку произвольной длины.

Имя - это просто текст, который вы хотите добавить в пространство имен, затем хэшировать и вставить в UUID:

uuid = NameToUUID('8e884ace-bee4-11e4-8dfc-aa07a5b093db', 'screwdriver');
uuid = NameToUUID('8e884ace-bee4-11e4-8dfc-aa07a5b093db', 'toothbrush');
uuid = NameToUUID('8e884ace-bee4-11e4-8dfc-aa07a5b093db', 'broomstick');
uuid = NameToUUID('8e884ace-bee4-11e4-8dfc-aa07a5b093db', 'orange');
uuid = NameToUUID('8e884ace-bee4-11e4-8dfc-aa07a5b093db', 'axe handle');
uuid = NameToUUID('8e884ace-bee4-11e4-8dfc-aa07a5b093db', 'impulse body spray');
uuid = NameToUUID('8e884ace-bee4-11e4-8dfc-aa07a5b093db', 'iPod Touch');

Примечание : любой код, выпущенный в общественное достояние. Ссылка на авторство не требуется.

Ян Бойд
источник
45
Спасибо за подробное объяснение. Если бы я мог дать за это бонусные баллы, Namespace_RectalForeignExtractedObjectя бы сделал это.
boodle
Можно ли декодировать имя или пространство имен, декодированное из UUID?
Сатеш
4
@Sathesh Нет, расшифровать хэш невозможно; хэши - это односторонние функции. Например, вся коллекция Star Trek TNG Blu-Ray занимает 81 ГБ и имеет хэш C5740BBBF2429115276D4AB60A020ED3ADE01192 . Невозможно декодировать этот 20-байтовый хэш обратно в 81 ГБ. Если вам это действительно нужно, вы можете попробовать хешировать все возможные идентификаторы GUID и возможные строки, пока не найдете комбинацию, дающую тот же результат. С любым лучом вы найдете его где-то между вечностью и вечностью.
Ян Бойд
22

Имя - это не что иное, как идентификатор, уникальный в некотором пространстве имен. Проблема в том, что пространства имен часто довольно малы, и имена в одном часто конфликтуют с именами в других. Например, номерной знак (имя) моей машины уникален в пространстве имен DMV моего штата, но, вероятно, не является уникальным в мире; DMV других состояний могли использовать то же имя в своих пространствах имен. Черт возьми, у кого-то еще может быть номер телефона (имя), которое также совпадает, потому что это еще одно пространство имен и т. Д.

Можно рассматривать UUID как населяющие единое пространство имен, настолько обширное, что оно может предоставить уникальное имя для всего ; вот что означает «универсальный». Но как сопоставить существующие имена в других пространствах имен с UUID?

Одним из очевидных решений является создание UUID (V1 или V4) для каждого элемента, чтобы заменить старые имена в их непересекающихся пространствах имен. Обратной стороной является то, что они намного больше, вам нужно сообщить все новые имена всем, у кого есть копия вашего набора данных, обновить все ваши API и т. Д. Скорее всего, вы не можете полностью избавиться от старых имен. в любом случае, это означает, что теперь у каждого предмета есть два имени, так что вы сделали лучше или хуже?

Вот тут-то и пригодится V3 / V5. UUID выглядят так же случайно, как и V4, но на самом деле детерминированы; любой, у кого есть правильный UUID для пространства имен, может затем независимо сгенерировать тот же UUID для любого заданного имени в этом пространстве имен. Вам не нужно ни публиковать их, ни даже предварительно создавать, поскольку любой может создавать их на лету по мере необходимости!

DNS-имена и URL-адреса - очень часто используемые пространства имен, поэтому для них были опубликованы стандартные UUID; OID ASN.1 и имена X.500 встречаются не так часто, но органы по стандартизации любят их, поэтому они опубликовали стандартные UUID пространства имен.

Для всех других пространств имен вы должны создать свой собственный UUID пространства имен (V1 или V4) и передать его всем, кто в нем нуждается. Если у вас несколько пространств имен, публикация UUID для каждого из них явно не идеальна.

Здесь и появляется иерархия: вы создаете один «базовый» UUID (любого типа), а затем используете его как пространство имен для именования других пространств имен! Таким образом, вам нужно только опубликовать базовый UUID (или использовать очевидный), а все остальные смогут вычислить.

Например, давайте останемся, мы хотели создать несколько UUID для StackOverflow; который имеет очевидное имя в пространстве имен DNS, поэтому основа очевидна:

uuid ns_dns = '6ba7b810-9dad-11d1-80b4-00c04fd430c8';
uuid ns_base = uuidv5(ns_dns, 'stackoverflow.com');

Сам StackOverflow имеет отдельные пространства имен для пользователей, вопросов, ответов, комментариев и т.д., но они также довольно очевидны:

uuid ns_user = uuidv5(ns_base, 'user');
uuid ns_question = uuidv5(ns_base, 'question');
uuid ns_answer = uuidv5(ns_base, 'answer');
uuid ns_comment = uuidv5(ns_base, 'comment');

Это конкретный вопрос # 10867405, поэтому его UUID будет:

uuid here = uuidv5(ns_question, '10867405');

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

Stephens
источник
Мне интересно, почему stackoverflow должен сопоставлять однозначно сгенерированное большое целое число с UUID, учитывая, что его API-интерфейсы, по-видимому, возвращают только большое целое число в виде строки. Где бы использовался UUID, если бы не в API. Кажется, мы должны выбрать либо UUID, либо BIGINT? Зачем нужна эта гибридная стратегия. Еще +1 за четкое объяснение в вашем ответе.
nishant
4
UUID V3 / V5 были разработаны для случаев, когда вам необходимо детерминированно преобразовать существующие (и, вероятно, конфликтующие) пространства имен в одно пространство имен UUID, что часто бывает полезно при объединении наборов данных. Если это не относится к тому, что вы делаете, выберите V1 / V4.
StephenS