Вопрос по – Генерация v5 UUID. Что такое имя и пространство имен?

81

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

For version 3 and version 5 UUIDs the additional command line arguments namespace and name have to be given. The namespace is either a UUID in string representation or an identifier for internally pre-defined namespace UUIDs (currently known are "ns:DNS", "ns:URL", "ns:OID", and "ns:X500"). The name is a string of arbitrary length.

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

The namespace is either a UUID in string representation or an

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

The name is a string of arbitrary length.

name совершенно случайная строка? Какова цель этого тогда? Можно ли его декодировать с UUID v5?

Ваш Ответ

3   ответа
70

ь вероятно) уникальных UUID.

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

Предположим, у вас есть хранилище (ключ, значение), но оно поддерживает только одно пространство имен. Вы можете создать большое количество различных логических пространств имен, используя UUID типа 3 или 5. Сначала создайте корневой UUID для каждого пространства имен. Это может быть UUID типа 1 (host + timestamp) или типа 4 (random), если вы его где-то спрятали. В качестве альтернативы вы можете создатьone случайный UUID для вашего корня (или использоватьnull UUID:00000000-0000-0000-0000-000000000000 как root), а затем создайте воспроизводимый UUID для каждого пространства имен, используя & quot;uuid -v5 $ROOTUUID $NAMESPACENAME& Quot ;. Теперь вы можете создавать уникальные UUID для ключей в пространстве имен, используя & quot;uuid -v5 $NAMESPACEUUID $KEY& Quot ;. Эти 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, он будет работать несколько быстрее, поэтому триллионный ключ имеет примерно один шанс на триллион на одно столкновение.

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

Увидетьhttp://www.ietf.org/rfc/rfc4122.txt для более подробной информации о кодировке UUID.

На определенном уровне иерархии могу ли я использовать UUIDv5 в качестве пространства имен и UUIDv4 в качестве случайного ключа, чтобы гарантировать, что коллизии в самих данных (которые идентифицируются этим GUID) не увеличивают вероятность коллизии UUID? Любые проблемы с производительностью, о которых я должен знать?
Я новичок в концепции и был озадачен тем, что этоhierarchy Вы говорите о. Где я могу увидеть это и т.д.to create a reproducible UUID for namespace, Мне интересно, есть ли способ проверить, что данный UUID (типа 3 или 5) был создан с использованием определенного пространства имен (его UUID)?
6

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

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

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

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

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

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

Вот где возникает иерархия: вы создаете одну & quot; базу & quot; 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');

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

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

hash в UUID.

Type 1: stuffs MAC address, datetime into 128 bits Type 3: stuffs an MD5 hash into 128 bits Type 4: stuffs random data into 128 bits Type 5: stuffs an SHA1 hash into 128 bits

Хеш 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, соответственно, так что это не имеет никакого эффекта).

What do I hash?

Вы, вероятно, задаетесь вопросом, что я должен хэшировать. В основном вы хешируете объединение:

sha1([NamespaceUUID]+[AnyString]);

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

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 затем определяет, как:

take the 160 bits from SHA1 and convert it into 128 bits of a UUID

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

More examples

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

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');
Now back to your question

For version 3 and version 5 UUIDs the additional command line arguments namespace and name have to be given. The namespace is either a UUID in string representation or an identifier for internally pre-defined namespace UUIDs (currently known are "ns:DNS", "ns:URL", "ns:OID", and "ns:X500"). The name is a string of arbitrary length.

namespace это то, что вам нравится. Это может быть один из предопределенных или вы можете создать свой собственный, например:

UUID Namespace_RectalForeignExtractedObject = '4d79546f-6e67-7565-496e-486572417373'

The name is a string of arbitrary length.

Имя - это просто текст, который вы хотите добавить в пространство имен, затем хэшировать и вставить в 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');

Note: Any code released into public domain. No attribution required.

Спасибо за подробное объяснение. Если бы я мог дать бонусные баллы заNamespace_RectalForeignExtractedObject Я мог бы.

Похожие вопросы