Universally Unique Identifier

A Universally Unique Identifier (UUID) is an identifier standard used in software construction, standardized by the Open Software Foundation (OSF) as part of the Distributed Computing Environment (DCE). The intent of UUIDs is to enable distributed systems to uniquely identify information without significant central coordination. Thus, anyone can create a UUID and use it to identify something with reasonable confidence that the identifier will never be unintentionally used by anyone for anything else. Information labeled with UUIDs can therefore be later combined into a single database without needing to resolve name conflicts. The most widespread use of this standard is in Microsoft's Globally Unique Identifiers (GUIDs). Other significant users include Linux's ext2/ext3 filesystem, LUKS encrypted partitions, GNOME, KDE, and Mac OS X, all of which use implementations derived from the uuid library found in the e2fsprogs package.

UUIDs are documented as part of ISO/IEC 11578:1996 "Information technology -- Open Systems Interconnection -- Remote Procedure Call (RPC)" and more recently in ITU-T Rec. X.667 | ISO/IEC 9834-8:2005 ( [http://www.itu.int/ITU-T/studygroups/com17/oid.html freely available] ). The IETF has published Proposed Standard RFC 4122 that is technically equivalent with ITU-T Rec. X.667 | ISO/IEC 9834-8.

Definition

A UUID is a 16-byte (128-bit) number. The number of theoretically possible UUIDs is therefore 2^16*8 = 2¹²⁸ = 256¹⁶ or about 3.4 × 10³⁸. This means that 1 trillion UUIDs would have to be created every nanosecond for 10 billion years to exhaust the number of UUIDs.

In its canonical form, a UUID consists of 32 hexadecimal digits, displayed in 5 groups separated by hyphens, in the form 8-4-4-4-12 for a total of 36 characters. For example:

:550e8400-e29b-41d4-a716-446655440000

A UUID may also be used with a specific identifier "intentionally" used repeatedly to identify the same thing in different contexts. For example, in Microsoft's Component Object Model, every component must implement the IUnknown interface, which is done by creating a UUID representing IUnknown. In all cases wherever IUnknown is used, whether it is being used by a process trying to access the IUnknown interface in a component, or by a component implementing the IUnknown interface, it is always referenced by the same identifier: 00000000-0000-0000-C000-000000000046.

Version 1 (MAC address)

Conceptually, the original (version 1) generation scheme for UUIDs was to concatenate the UUID version with the MAC address of the computer that is generating the UUID, and with the number of 100-nanosecond intervals since the adoption of the Gregorian calendar. In practice, the actual algorithm is more complicated. This scheme has been criticized in that it is not sufficiently 'opaque'; it reveals both the identity of the computer that generated the UUID and the time at which it did so.

Version 2 (DCE Security)

Version 2 UUIDs are similar to Version 1 UUIDs, with the upper byte of the clock sequence replaced by the identifier for a "local domain" (typically either the "POSIX UID domain" or the "POSIX GID domain") and the first 4 bytes of the timestamp replaced by the user's POSIX UID or GID (with the "local domain" identifier indicating which it is). [cite web
author = The Open Group
year = 1997
title = CDE 1.1: Remote Procedure Call
url = http://www.opengroup.org/onlinepubs/9629399/apdxa.htm] [cite web
author = The Open Group
year = 1997
title = DCE 1.1: Authentication and Security Services
url = http://www.opengroup.org/onlinepubs/9696989899/chap5.htm#tagcjh_08_02_01_01]

Version 3 (MD5 hash)

Version 3 UUIDs use a scheme deriving a UUID via MD5 from a URL, a
fully qualified domain name, an Object identifier, a distinguished name (DN as used in Lightweight Directory Access Protocol), or on names inunspecified namespaces. Version 3 UUIDs have the form xxxxxxxx-xxxx-3xxx-xxxx-xxxxxxxxxxxx with hexadecimal digits x.

To determine the version 3 UUID of a given name the UUID of the namespace, e.g. 6ba7b810-9dad-11d1-80b4-00c04fd430c8 for a domain, is transformed to a string of bytes corresponding to its hexadecimal digits, concatenated with the input name, hashed with MD5 yielding 128 bits. Six bits are replaced by fixed values, four of these bits indicate the version, 0011 for version 3. Finally the fixed hash is transformed back into the hexadecimal form with hyphens separating the parts relevant in other UUID versions.

Version 4 (random)

Version 4 UUIDs use a scheme relying only on random numbers. This algorithm sets the version number, as well as two reserved bits. All other bits are set using a random or pseudorandom data source.

Version 5 (SHA-1 hash)

Version 5 UUIDs use a scheme with SHA-1 hashing, otherwise it is the same idea as in version 3. RFC 4122 states that version 5 is preferred over version 3 name based UUIDs.

Implementations

Borland Developer Studio

A new GUID can be generated by pressing Ctrl-Shift-G.

C

libuuid is part of the e2fsprogs package and is available from http://e2fsprogs.sourceforge.net/.

The OSSP project provides a UUID library. [cite web | url = http://www.ossp.org/pkg/lib/uuid/ | title = Universally Unique Identifier (UUID) | author = Open Source Software Project]

Cocoa/Carbon

The Core Foundation class CFUUIDRef is used to produce and store UUIDs, as well as to convert them to and from CFString/NSString representations. [cite web | url = http://developer.apple.com/documentation/CoreFoundation/Reference/CFUUIDRef/Reference/reference.html | author = Apple Computer, Inc. | title = CFUUID Reference]

ColdFusion

The createUUID() function provides a UUID in all versions, however the format generated is in 4 segments instead of 5 xxxxxxxx-xxxx-xxxx-xxxxxxxxxxxxxxxx (8-4-4-16). [cite web | url = http://livedocs.adobe.com/coldfusion/8/htmldocs/functions_c-d_24.html | author = Adobe Systems Inc. | title = ColdFusion Functions:CreateUUID]

Common Lisp

A library is available to create UUIDs (v1, v3, v4 and v5) according to RFC 4122. [cite web | url = http://www.dardoria.net/software/uuid.html | title = UUID | author = Boian Tzonev]

Eiffel

A library is available to create UUIDs Generates uuids according to RFC 4122, Variant 1 0, Version 4. Source available at [https://svn.origo.ethz.ch/eiffelstudio/trunk/Src/library/uuid/ Eiffel UUID library]

Free Pascal & Lazarus IDE

In Free Pascal there is a class called TGUID that holds the structure of a UUID. Also in the SysUtils.pas unit there are methods to create, compare and convert UUID's. They are CreateGUID(), GUIDToString() and IsEqualGUID(). [cite web | url = http://www.freepascal.org/docs-html/rtl/sysutils/index-5.html | title = Reference for 'sysutils' unit | author = Free Pascal Documentation] In the Lazarus IDE you can also generate a UUID by pressing Ctrl+Shift+G.

Haskell

The package uuid [cite web | url = http://hackage.haskell.org/cgi-bin/hackage-scripts/package/uuid | title = uuid | author = Antoine Latter] provides a binding to library libuuid, which is part of e2fsprogs. [cite web | url = http://e2fsprogs.sourceforge.net/ e2fsprogs | title = esfsprogs | author = Theodore Ts'o] The package can be used to create, parse, and print UUIDs.

Java

The J2SE 5.0 release of Java provides a class that will produce 128-bit UUIDs, although it only implements version 3 and 4 generation methods, not the original method (due to lack of means to access MAC addresses using pure Java). The API documentation for the Javadoc:SE|package=java.util|java/util|UUID class refers to ISO/IEC 11578:1996.

Open source implementations supporting MAC addresses on several common operating systems are [http://johannburkard.de/software/uuid/ UUID – generate UUIDs (or GUIDs) in Java] , [http://jug.safehaus.org/ Java Uuid Generator (JUG)] and ActiveScript [http://www.activescript.co.uk/] .

Javascript

AF Design provide a [http://www.af-design.com/services/javascript/uuid/ javascript class] based on random number instead of MAC address.

MySQL

MySQL provides a UUID() function. [cite web | url = http://dev.mysql.com/doc/refman/5.0/en/miscellaneous-functions.html#function_uuid | title = MySQL 5.0 Reference Manual | author = MySQL AB]

.NET Framework

The .NET Framework also provides a class called System.Guid to generate and manipulate 128-bit UUIDs. [http://msdn2.microsoft.com/en-us/library/system.guid.aspx]

ORACLE Database

The Oracle SQL provides a function called SYS_GUID() to generate unique identifiers ( [http://download-east.oracle.com/docs/cd/B12037_01/server.101/b10759/functions153.htm] ).

Perl

The Data::GUID [cite web | url = http://search.cpan.org/dist/Data-GUID/ | title = Data-GUID | author = Ricardo Signes] module from CPAN can be used to create UUIDs

PHP

In PHP there are several modules for creating UUIDs. [http://pecl.php.net/package/uuid]

PostgreSQL

PostgreSQL contains a uuid data type. Also various generation functions as part of the uuid-ossp contrib module. [cite web | url = http://www.postgresql.org/docs/8.3/static/datatype-uuid.html | title = PostgreSQL 8.3.x Documentation: UUID Type | author = PostgreSQL Global Development Group]

Progress OpenEdge ABL

The GENERATE-UUID function in OpenEdge 10 provides a UUID which can be made printable using the GUID() or BASE64-ENCODE() functions. [http://www.psdn.com/library/servlet/KbServlet/download/1927-102-2537/dvref.pdf]

Python

The uuid module [cite web | url = http://docs.python.org/lib/module-uuid.html | title = Python Library Reference: uuid] (included in the standard library since Python 2.5) creates UUIDs to RFC 4122.

Ruby

There are several RFC4122 implementations for Ruby, the most updated ones being [http://raa.ruby-lang.org/project/ruby-uuid/ Ruby-UUID] , [http://raa.ruby-lang.org/project/uuid/ UUID] and [http://sporkmonger.com/projects/uuidtools/ UUIDTools]

QL Server Data Base

Transact-SQL ( [http://msdn2.microsoft.com/en-us/library/aa276822(SQL.80).aspx 2000] and [http://msdn2.microsoft.com/en-us/library/ms187942.aspx 2005] ) provides a function called NEWID() to generate uniqueidentifiers. SQL Server 2005 provides an additional function called [http://msdn.microsoft.com/en-us/library/ms189786.aspx NEWSEQUENTIALID()] which generates a new GUID that is greater than any GUID previously created by the [http://msdn.microsoft.com/en-us/library/ms189786.aspx NEWSEQUENTIALID()] function on a given computer.

Tcl

A Tcl implementation is provided in the TclLib package. [cite web | url = http://tcllib.sourceforge.net/doc/uuid.html | title = Tcl Standard Library: uuid]

Random UUID probability of duplicates

Randomly generated UUIDs like those generated by the Javadoc:SE|package=java.util|java/util|UUID class have 122 random bits. There are 128 bits altogether with 4 bits being used for the version ('Randomly generated UUID'), and 2 bits for the variant ('Leach-Salz'). With random UUIDs, the chance of two having the same value can be calculated using probability theory (Birthday paradox). Using the approximation:$p(n)approx\; 1-e^\{-n^2/\{2\; cdot\; x$these are the probabilities of an accidental clash after calculating "n" UUIDs, with "x"=2¹²²:

n	probability
68,719,476,736 = 236	0.0000000000000004 (4 × 10−16)
2,199,023,255,552 = 241	0.0000000000004 (4 × 10−13)
70,368,744,177,664 = 246	0.0000000004 (4 × 10−10)

To put these numbers into perspective, one's annual risk of being hit by a meteorite is estimated to be one chance in 17 billion [ [http://www.dartmouth.edu/~chance/chance_news/recent_news/chance_news_2.21.html Old Farmer's Almanac 1994, 220-222, Taking your Chances: An Explanation of Risk] ] , that means the probability is about 0.00000000006 (6 × 10⁻¹¹), equivalent to the odds of creating a few tens of trillions of UUIDs in a year and having one duplicate. In other words, only after generating 1 billion UUIDs "every second" for the next 100 years, the probability of creating "just one" duplicate would be about 50%. The probability of one duplicate would be about 50% if every person on earth owns 600 million UUIDs.

The odds of a properly generated duplicate UUID being used in error in any practical circumstance is so low that any other work to improve software reliability would clearly be a much higher priority.

The probability also depends on the quality of the random number generator. A cryptographically secure pseudorandom number generator must be used to generate the values, otherwise the probability of duplicates may be significantly higher.

History

The initial design of DCE UUIDs was based on UUIDs as defined in the Network Computing System [cite book
last = Zahn
first = Lisa
title = Network Computing Architecture
pages = 10
publisher = Prentice Hall
year = 1990
isbn = 0136116744 ] , whose design was in turn inspired by the (64-bit) unique identifiers defined and used pervasively in Domain/OS, the operating system designed by Apollo Computer, Inc.

References

ee also

*Globally Unique Identifier
*LABEL

External links

* [http://www.itu.int/ITU-T/studygroups/com17/oid.html International Standard "Generation and registration of Universally Unique Identifiers (UUIDs) and their use as ASN.1 Object Identifier components"] (ITU-T Rec. X.667 | ISO/IEC 9834-8, freely available)
* [http://www.ietf.org/rfc/rfc4122.txt A Universally Unique IDentifier (UUID) URN Namespace] (IETF RFC 4122)
* [http://www.famkruithof.net/uuid/uuidgen?typeReq=-1 Extract the time from a version 1 UUID / GUID]
* [http://www.itu.int/ITU-T/asn1/uuid.html Global UUID registration function at ITU-T]
* [http://jakarta.apache.org/commons/sandbox/id/uuid.html Commons Id]
* [http://www.iso.ch/cate/d2229.html ISO/IEC 11578:1996]
* [http://www.infonuovo.com/dma/csdocs/sketch/instidid.htm DmaId for InstanceId Values (DCE Universally Unique IDentifiers, UUIDs)]
* [http://www.opengroup.org/onlinepubs/9629399/apdxa.htm Syntax and semantics of the DCE variant of Universal Unique Identifiers (UUIDs)]
* [http://www.h2database.com/html/advanced.html#uuid Random UUID Probability of Duplicates]
* [http://www.opengroup.org/dce/info/draft-leach-uuids-guids-01.txt IETF UUID draft specification]