Globally Unique Identifier - Sequential Algorithms

Sequential Algorithms

GUIDs are commonly used as the primary key of database tables, and with that, often the table has a clustered index on that attribute. This presents a performance issue when inserting records because a fully random GUID means the record may need to be inserted anywhere within the table rather than merely appended near the end of it.

As a way of mitigating this issue while still providing enough randomness to effectively prevent duplicate number collisions, several algorithms have been used to generate sequential GUIDs.

The oldest technique, present as a feature in early version of Microsoft's GUIDGEN SDK tool, works by simply outputting the set of MAC-based version 1 GUIDs corresponding to a time interval, taking advantage of the fact that the time field in v1 GUIDs has a resolution of 100ns, which allows a million sequential GUIDs to be generated by simply locking out other GUID generators on the computer for a tenth of a second (or 10000 GUIDs in a millisecond). These sequential GUIDs are unique, but the increment happens in the Data1 field, not at the end of the GUID.

The second technique, described by Jimmy Nilsson in August 2002 and referred to as a "COMB" ("combined guid/timestamp"), replaces the last 6 bytes of Data4 in a random (version 4) GUID with the least-significant 6 bytes of the current system date/time. While this can result in GUIDs that are generated out of order within the same fraction of a second, his tests showed this had little real-world impact on insertion. One side effect of this approach is that the date and time of insertion can be easily extracted from the value later, if desired. The COMB technique tries to compensate for the reduced clustering in database indexes caused by switching to an OS version that uses random GUIDs rather than MAC-based GUIDs, and is useful only when it is not possible to revert to version 1 GUIDs.

Starting with Microsoft SQL Server version 2005, Microsoft added a function to the Transact-SQL language called NEWSEQUENTIALID, which essentially provides access to the traditional version 1 GUIDs (or something so close it fits the same description), with all their advantages and disadvantages.

In 2006, a programmer found that the SYS_GUID function provided by Oracle was returning sequential GUIDs on some platforms, but this appears to be a bug rather than a feature.

Read more about this topic:  Globally Unique Identifier