WikiSort.ru - Не сортированное

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 представляет собой 16-байтный (128-битный) номер. В шестнадцатеричной системе счисления UUID выглядит как:

550e8400-e29b-41d4-a716-446655440000

Общее количество уникальных ключей UUID составляет 2¹²⁸ = 256¹⁶ или около 3,4 × 10³⁸. Это означает, что генерируя 1 триллион ключей каждую наносекунду, перебрать все возможные значения удастся лишь за 10 миллиардов лет.

UUID задокументирован как часть ISO/IEC 11578:1996 «Information technology — Open Systems Interconnection — Remote 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 со специальным идентификатором может быть преднамеренно использован повторно, для идентификации той же самой сущности в различных контекстах. Например, в Microsoft Component Object Model каждый компонент должен поддерживать стандартный интерфейс «IUnknown». Для этого создан UUID, представляющий «IUnknown». Во всех случаях, когда используется «IUnknown» — при доступе процессов к интерфейсу «IUnknown» в компоненте, или же для реализации поддержки интерфейса «IUnknown» самим компонентом, — всегда происходит отсылка к одному и тому же идентификатору: 00000000-0000-0000-C000-000000000046.

Вероятность совпадения UUID

Возможно, этот раздел содержит оригинальное исследование. Добавьте ссылки на источники, в противном случае он может быть удалён. Дополнительные сведения могут быть на странице обсуждения. (13 декабря 2013)

Расчет вероятности совпадения хотя бы двух ключей из множества ключей, сгенерированных случайным образом вычисляется по формуле: ${\displaystyle p(n)=1-{\frac {(N-1)!}{(N-n)!\cdot N^{n-1}}}\Longleftrightarrow p(n)=1-\exp \left(\ln \left({\frac {(N-1)!}{(N-n)!\cdot N^{n-1}}}\right)\right)}$

Исходя из того, что ${\displaystyle \ln(N!)\approx N\cdot \ln(N)-N}$ при больших значениях N, получаем:

${\displaystyle p(n)\approx 1-\exp \left(N\cdot (\ln(N-1)-\ln(N-n))+n\cdot (\ln(N-n)-\ln(N)-1)-(\ln(N-1)-\ln(N)-1)\right)}$

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

p(2⁵⁰) ${\displaystyle \approx }$ 1,87×10⁻⁹

p(2⁵⁹) ${\displaystyle \approx }$ 0.000489

p(2⁶⁴) ${\displaystyle \approx }$ 0.4

p(2⁶⁶) ${\displaystyle \approx }$ 0.999665

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

Программа для расчета вероятности на языке программирования 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;
}

См. также

• GUID

Ссылки

• RFC 4122 — A Universally Unique IDentifier (UUID) URN Namespace
• Global UUID registration function at ITU-T
• Устройство и криптоанализ UUID-генератора в ОС Windows
• UUID онлайн генератор