UUID

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

UUID (англ. universally unique identifier "универсальный уникальный идентификатор") — это стандарт идентификации, используемый в создании программного обеспечения, стандартизированный Open Software Foundation (OSF) как часть DCE — среды распределённых вычислений (Distributed Computing Environment (англ.)). Основное назначение UUID — это позволить распределённым системам уникально идентифицировать информацию без центра координации. Таким образом, любой может создать UUID и использовать его для идентификации чего-либо с приемлемым уровнем уверенности, что данный идентификатор непреднамеренно никогда не будет использован для чего-то ещё. Поэтому информация, помеченная с помощью UUID, может быть помещена позже в общую базу данных, без необходимости разрешения конфликта имен. Наиболее распространённым использованием данного стандарта является Globally Unique Identifier (GUID) фирмы Microsoft. Другими значительными пользователями являются Linux (файловая система ext2/ext3, LUKS шифрованные разделы, GNOME, KDE) и Mac OS X — все они применяют реализацию, полученную из библиотеки uuid, находящейся в пакете e2fsprogs.

Стандарты[править | править код]

UUID задокументирован как часть ISO/IEC 11578:1996 «Information technologyOpen Systems InterconnectionRemote Procedure Call (RPC)» и позже в ITU-T Rec. X.667 | ISO/IEC 9834-8:2008. IETF опубликовала предлагаемый стандарт RFC 4122, который технически идентичен ITU-T Rec. X.667 | ISO/IEC 9834-8.

Формат[править | править код]

UUID представляет собой 16-байтный (128-битный) номер. В каноническом представлении UUID изображают в виде числа в шестнадцатеричной системе счисления, разделённого дефисами на пять групп в формате 8-4-4-4-12. Такое представление занимает 36 символов:

123e4567-e89b-12d3-a456-426655440000
xxxxxxxx-xxxx-Mxxx-Nxxx-xxxxxxxxxxxx

4 бита M обозначают версию ("version") UUID, а 1-3 старших бита N обозначают вариант ("variant") UUID.

Такое разделение на группы основано на структуре UUID:

Структура UUID
Название поля Длина (в байтах) Длина (число 16-ричных цифр) Содержимое
time_low 4 8 целое число, обозначающее младшие 32 бита времени
time_mid 2 4 целое число, обозначающее средние 32 бита времени
time_hi_and_version 2 4 4 старших бита обозначают версию UUID, младшие биты обозначают старшие 12 бит времени
clock_seq_hi_and_res clock_seq_low 2 4 1-3 старших бита обозначают вариант UUID, остальные 13-15 бит обозначают clock sequence
node 6 12 48-битный идентификатор узла

Эти поля соответствуют версиям UUID 1 и 2, которые генерируются на базе времени, но представление 8-4-4-4-12 используется для любых версий UUID.

RFC 4122 также определяет пространство имён URN для UUID:

urn:uuid:123e4567-e89b-12d3-a456-426655440000

Microsoft GUID иногда используется с фигурными скобками:

{123e4567-e89b-12d3-a456-426655440000}

Общее количество уникальных ключей UUID (без учёта версий) составляет 2128 = 25616 или около 3,4 × 1038. Это означает, что генерируя 1 триллион ключей каждую наносекунду, перебрать все возможные значения удастся лишь за 10 миллиардов лет.

UUID со специальным идентификатором может быть преднамеренно использован повторно, для идентификации той же самой сущности в различных контекстах. Например, в Microsoft Component Object Model каждый компонент должен поддерживать стандартный интерфейс «IUnknown». Для этого создан UUID, представляющий «IUnknown». Во всех случаях, когда используется «IUnknown» — при доступе процессов к интерфейсу «IUnknown» в компоненте, или же для реализации поддержки интерфейса «IUnknown» самим компонентом, — всегда происходит отсылка к одному и тому же идентификатору: 00000000-0000-0000-C000-000000000046.

Кодирование[править | править код]

Бинарное представление UUID различается на разных системах.

Большинство систем кодируют UUID полностью в big-endian. Например, 00112233-4455-6677-8899-aabbccddeeff кодируется в байты 00 11 22 33 44 55 66 77 88 99 aa bb cc dd ee ff.

Некоторые системы, например маршалинг в Microsoft COM/OLE libraries, используют mixed-endian, где первые три компонента UUID закодированы как little-endian, а последние два как big-endian. Например, 00112233-4455-6677-8899-aabbccddeeff в таком случае кодируется как 33 22 11 00 55 44 77 66 88 99 aa bb cc dd ee ff.

Варианты[править | править код]

По историческим причинам UUID имеет несколько вариантов, обозначаемых одним, двумя или тремя битами.

Вариант 0[править | править код]

Один из вариантов, определенных в RFC 4122, вариант 0 (обозначается одним битом 0xxx2, N = 0..7), присутствует ради обратной совместимости с устаревшим форматом UUID Apollo Network Computing System 1.5, разработанным примерно в 1988 году. В этом формате первые 6 октетов UUID представляют собой 48-битную метку времени (количество единиц времени в 4 микросекунды, прошедших с 1 января 1980 года UTC); следующие 2 октета зарезервированы; следующий октет - это «address family»; последние 7 октетов являются 56-битным идентификатором хоста в форме, определенной address family. Несмотря на различие в деталях, можно видеть сходство с современным UUID версии 1. Биты варианта в текущей спецификации UUID совпадают с старшими битами октета семейства адресов в UUID NCS. Хотя семейство адресов может содержать значения в диапазоне 0..255, были определены только значения 0..13. Таким образом, обозначение варианта 0 как 0xxx позволяет избежать конфликтов с историческими UUID NCS, если они всё ещё существуют в базах данных.

Варианты 1 и 2[править | править код]

Эти варианты используются в текущих спецификациях UUID. Вариант 1 (обозначается двумя битами 10xx2 N = 8..b) является основным и описан в RFC 4122. Вариант 2 (обозначается тремя битами 110x2 N = c..d) описан в RFC как зарезервированный для обратной совместимости с ранними GUID из Microsoft Windows.

Помимо битов, обозначающих вариант, во всём остальном эти два варианта UUID одинаковы, за исключением того, что при кодировании в бинарную форму для хранения или передачи UUID варианта 1 используют сетевой порядок байтов (big-endian), а GUID варианта 2 используют «нативный» (little-endian) порядок байтов. В каноническом текстовом представлении варианты 1 и 2 одинаковы, за исключением битов вариантов.

Хотя некоторые важные идентификаторы GUID, такие как идентификатор интерфейса IUnknown для COM, являются UUID варианта 2, многие идентификаторы, созданные и используемые в ПО Microsoft Windows и называемые «GUID», по факту являются стандартными UUID варианта 1 с сетевым порядком байтов. Текущая версия утилиты Microsoft guidgen создает стандартные UUID варианта 1. В некоторой документации Microsoft говорится, что «GUID» является синонимом «UUID»,[1] как это стандартизировано в RFC 4122. Сам RFC 4122 утверждает, что UUID также известны как GUID ("are also known as GUIDs"). Все это говорит о том, что «GUID», хоть и был изначально отдельным вариантом UUID, используемым в Microsoft, сейчас стал просто альтернативным названием для стандартного UUID.

Вариант 3[править | править код]

В RFC 4122 вариант 111x2 (N = e..f) зарезервирован для использования в будущем.

Версии[править | править код]

В стандарте определены пять версий ("version") UUID, каждая из которых может подходить лучше или хуже в определённых ситуациях.

Nil UUID[править | править код]

Особый случай, в котором все биты UUID выставлены в ноль: 00000000-0000-0000-0000-000000000000.

Версия 1 (время и MAC-адрес)[править | править код]

Версия 1 включает в себя 48-битный MAC-адрес узла ("node"), на котором сгенерирован UUID, и 60-битную метку времени (timestamp), которая обозначает число 100-наносекундных интервалов, прошедших с полуночи 15 октября 1582 года по UTC — даты начала применения григорианского календаря. RFC 4122 указывает максимально возможное время около 3400 года н.э., и это означает, что 60-битная метка времени является знаковой. Однако некоторые программы, например библиотека libuuid, считают timestamp беззнаковым[2], и для них максимальным временем является примерно 5236 год н.э.

13- или 14-битный clock sequence дополняет метку времени в случаях, когда системные часы обновляются недостаточно быстро, или на многопроцессорных системах. В таких случаях метка времени у разных UUID может оказаться одинаковой. Чтобы избежать генерации одинаковых UUID, используют clock sequence, который обновляется каждый раз при создании нового UUID и который будет разным у разных UUID даже при совпадении меток времени. Поскольку UUID версии 1 соответствует одной точке в пространстве (узел) и времени (метка времени и clock sequence), вероятность совпадения двух правильно сгенерированных UUID практически равна нулю. Поскольку метка времени и clock sequence вместе составляют 74 бита, всего может быть сгенерировано 274 (1.8⋅1022, или 18 секстиллионов) уникальных UUID версии 1 на одном узле с максимальной средней скоростью 163 миллиарда UUID в секунду.

В отличие от других версий UUID, уникальность UUID версий 1 и 2, основанных на MAC-адресах сетевых карт, частично зависит от идентификатора, выданного центральным регистрирующим органом, а именно от части уникального идентификатора организации (OUI) MAC-адреса, который выдаётся в IEEE производителям сетевого оборудования.[3] Уникальность также зависит от правильного назначения уникальных MAC-адресов сетевых карт производителями, что, как и другие производственные процессы, подвержено ошибкам.

Использование MAC-адреса означает, что всегда можно отследить компьютер, который создал UUID. Иногда возможно найти компьютер, на котором был создан или отредактирован какой-либо документ, если используемый текстовый процессор встроил UUID в файл. Эта дыра в конфиденциальности использовалась для поиска автора вируса Melissa (англ.).[4]

Версия 2 (время, MAC-адрес и DCE security version)[править | править код]

RFC 4122 резервирует версию 2 "DCE security", но не предоставляет никаких подробностей о ней. По этой причине во многих реализациях UUID версия 2 отсутствует. Однако описание UUID версии 2 есть в спецификации DCE 1.1 Authentication and Security Services.[5]

Версия 2 похожа на версию 1, но младшие 8 бит clock sequence заменены на номер «локального домена» ("local domain" number), а младшие 32 бита метки времени (timestamp) заменены целочисленным идентификатором, значимым в пределах указанного локального домена.

Возможность включить 40-битный домен/идентификатор является компромиссом. С одной стороны, 40 битов допускают около 1 триллиона значений доменов/идентификаторов для одного узла. С другой стороны, с урезанным значением метки времени до 28 старших значащих бит по сравнению с 60 битами в версии 1 время в UUID версии 2 будет «тикать» лишь раз в 429,49 секунды (чуть больше 7 минут) в отличие от 100 наносекунд в версии 1. И с шестибитным clock sequence, в отличие от 14 бит в версии 1, могут быть сгенерированы лишь 64 уникальных UUID для одного узла/домена/идентификатора в течение этих 7 минут. Таким образом UUID версии 2 не подходит, если требуется генерировать UUID чаще чем раз в 7 секунд.

Версии 3 и 5[править | править код]

UUID версий 3 и 5 образуются путём хеширования идентификатора пространства имён и имени. Версия 3 использует алгоритм хеширования MD5, версия 5 — SHA-1.

Идентификатор пространства имён сам по себе является UUID. Спецификация предоставляет UUID для представления пространств имён URL, FQDN, OID и отличительных имён X.500, но любой желаемый UUID может использоваться в качестве идентификатора пространства имен.

Для вычисления UUID версии 3, соответствующего данному пространству имен и имени, UUID пространства имен преобразуется в байтовую, конкатенируется с именем и хешируется алгоритмом MD5, что дает 128 битов. Затем 6 или 7 битов заменяются фиксированными значениями: 4-битной версией (например, 00112 для версии 3) и 2- или 3-битным вариантом ("variant") UUID (например, 102, обозначающим RFC 4122 UUID, или 1102, обозначающим legacy Microsoft GUID). Поскольку 6 или 7 битов таким образом предопределены, лишь 121 или 122 бита вносят вклад в уникальность UUID.

UUID версии 5 похож, но использует SHA-1 вместо MD5. Так как SHA-1 даёт 160-битный хеш, он предварительно обрезается до 128 бит.

Суть UUID версий 3 и 5 в том, что одна и та же пара из пространства имён и имени будет отображаться в один и тот же UUID. При этом ни пространство имён, ни имя не могут быть обратно получены из UUID, кроме как методом перебора.

RFC 4122 рекомендует использовать версию 5 вместо версии 3 и не рекомендует использовать ни одну из этих версий в качестве учетных данных для безопасности.

Версия 4 (случайный)[править | править код]

UUID версии 4 генерируется случайным образом. Как и в других версиях UUID, 4 бита используются для указания версии, 2 или 3 бита указывают на вариант. Так что для варианта 1 (который используется большинством UUID) на случайно сгенерированную часть приходится 122 бита, что даёт 2122, или 5.3⋅1036 (5.3 ундециллиона) возможных вариантов UUID версии 4 варианта 1. UUID версии 4 варианта 2 имеет вдвое меньше возможных вариантов, так как ещё один бит используется для обозначения варианта.

Вероятность совпадения UUID[править | править код]

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


Исходя из того, что при больших значениях N, получаем:


Где N — количество возможных вариантов (2128); n — число сгенерированных ключей.

p(250) 1,87×10−9

p(259) 0.000489

p(264) 0.4

p(266) 0.999665

Можно с уверенностью сказать, что первый квадриллион ключей (1015) будут уникальными.


Программа для расчета вероятности на языке программирования Java:

public void probabilityCoincidenceGUID() {
    MathContext mc = new MathContext(1000, RoundingMode.HALF_UP);
    BigDecimal N = BigDecimal.valueOf(2).pow(128, mc);
    BigDecimal n = BigDecimal.valueOf(2).pow(50, mc);
    BigDecimal result_ = calcProbabilityCoincidenceGUID(N, n, mc);
    double result = result_.doubleValue();
} 
    
private BigDecimal calcProbabilityCoincidenceGUID(BigDecimal N, BigDecimal n, MathContext mc) {
    // = N  \cdot (LN(N-1)-LN(N-n))  +  n \cdot (LN(N-n)-LN(N)-1)  -  (LN(N-1)-LN(N)-1)		
    BigDecimal N_1 = N.subtract(BigDecimal.valueOf(1), mc);
    BigDecimal N_n = N.subtract(n, mc);
    BigDecimal ln_N = BigDecimalUtils.ln(N, 400);
    BigDecimal ln_N_1 = BigDecimalUtils.ln(N_1, 400);
    BigDecimal ln_N_n = BigDecimalUtils.ln(N_n, 400);
    BigDecimal v1 = N.multiply(ln_N_1.subtract(ln_N_n, mc), mc);
    BigDecimal v2 = n.multiply(ln_N_n.subtract(ln_N, mc).subtract(BigDecimal.valueOf(1), mc), mc);
    BigDecimal v3 = ln_N_1.subtract(ln_N, mc).subtract(BigDecimal.valueOf(1), mc);
    BigDecimal exp = v1.add(v2, mc).subtract(v3, mc);
    BigDecimal result = BigDecimal.valueOf(1).subtract(BigDecimalUtils.exp(exp, 400));
    return result;
}

См. также[править | править код]

Ссылки[править | править код]

Примечания[править | править код]

  1. Globally Unique Identifiers. Microsoft Developer Network. Microsoft.
  2. ext2/e2fsprogs.git - Ext2/3/4 filesystem userspace utilities. Kernel.org. Дата обращения 9 января 2017. (недоступная ссылка)
  3. The Institute of Electrical and Electronics Engineers, Incorporated (IEEE). Registration authority. — 1963-01-01.
  4. Reiter, Luke Tracking Melissa's Alter Egos. ZDNet. CBS Interactive (2 апреля 1999). Дата обращения 16 января 2017.
  5. DCE 1.1: Authentication and Security Services. The Open Group.