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

550e8400-e29b-41d4-a716-446655440000

Общее количество уникальных ключей UUID составляет 2128 = 25616 или около 3,4 × 1038. Это означает, что генерируя 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[править | править вики-текст]

Расчет вероятности совпадения хотя бы двух ключей из множества ключей, сгенерированных случайным образом вычисляется по формуле: 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 )


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


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 — количество возможных вариантов (2128); n — число сгенерированных ключей.

p(250) \approx 1,87×10−9

p(259) \approx 0.000489

p(264) \approx 0.4

p(266) \approx 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;
}

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

Ссылки[править | править вики-текст]