Creating Client Side Sequential GUIDs

There are many databases where Guids (uniqueidentifiers) are used as the primary key for the tables. A Guid is a 128-bit (16-byte) value and is commonly displayed in hexadecimal digits with groups separated by hyphens, such as 1363B077-64DB-49B8-9884-000047475430. Guid primary keys are a natural fit for many development scenarios, such as replication, or when you need to generate primary keys outside the database. Guid primary keys have several benefits, such as:

Uniqueness across every table, every database and every server.
You can generate the values without having a roundtrip to the database.
Most replication scenarios require Guid columns.

One of the problems with Guid primary keys is that they are usually based on a random number generator and this could cause performance issues when a clustered index is defined on the primary key Guid column (default in SqlServer) or when a Guid column is indexed. When a large number of records are stored in a table, its PK index becomes very inefficient when the primary key is of type Guid. The reason for that is the fact that indexes need to have the records in a sort order by the index column. Sorting random Guids is not a very efficient operation. It takes much more computing cycles to find the correct place where a new guid should be stored among 100000000 Guids that are already sorted. For this reason, Microsoft offers the NEWSEQUENTIALID() function. The NEWSEQUENTIALID() function creates a Guid that is greater than any Guid previously generated by this function on a specified computer since Windows was started. After restarting Windows, the Guid can start again from a lower range. Using the NEWSEQUENTIALID() function can be faster than using the NEWID() function. This is because the NEWID() function causes random activity and uses fewer cached data pages. Using the NEWSEQUENTIALID() function also helps to completely fill the index and data pages. That way, each new Guid is put as the last in the sort order and there is almost no need to calculate its place in the index tree. The NEWSEQUENTIALID() function is a wrapper over the Windows UuidCreateSequential function.

However, not all backends offer such functionality. In fact, SQL Server is the only backend that provides sequential Guids out-of-the-box. On the other hand, the Guids generated with the Guid.NewGuid() method in .NET are always random and there is no .NET API for sequential Guids. That's why Telerik Data Access implements a sequential Guids generator, which generates sequential Guids on the client side. The specifics of the database used by the customer are also taken into account, i.e. the different databases store Guids differently. For example, some backends have a dedicated uniqueidentifier type, while other stores them as binary or Varchar.

In this topic:

Generating Client Side Sequential GUIDs

There are three methods for working with sequential Guids that are accessible through the KeyGenerators object exposed by the OpenAccessContext:

GetIncrementalGuid - returns the next Guid in incremental order for the current database. Telerik Data Access, grabs a number of incremental Guids (by default the grab size is 10) from the database and then returns them one by one when this method is called. After there are no more Guids to return, Telerik Data Access fetches a new portion of Guids from the database and so on.
GetIncrementalGuid(int grabSize) - allows you to control the grab size of the incremental Guid generator. For instance, if you have the knowledge that you will insert 50 objects as a batch, it is a nice option to specify 50 as the grab size when you request the first incremental Guid. In that way you will know that no additional round-trips will be done to the database while you request the additional 49 Guids.
GetIncrementalGuids(int count) - returns client side generated System.Guid values that are greater than any Guid previously generated for the connected database. The "count" parameter specifies the number of incremental Guid values that should be obtained.

The following code snippet demonstrates how to create sequential Guids on the client side:

using ( FluentModel context = new FluentModel() )
{
   Guid[] guids = new Guid[10];
   for ( int i = 0; i < 10; i++ )
   {
       guids[i] = context.KeyGenerators.GetIncrementalGuid();
   }
   context.SaveChanges();
   IList<EntityWithIncrementalGuid> result = context.GetAll<EntityWithIncrementalGuid>()
     .OrderBy( x => x.ID ).ToList();
   for ( int i = 0; i < result.Count; i++ )
   {
       Debug.Assert( result[i].ID.Equals( guids[i] ) );
   }
}

Using context As New FluentModel()
 Dim guids(9) As Guid
 For i As Integer = 0 To 9
  guids(i) = context.KeyGenerators.GetIncrementalGuid()
 Next i
 context.SaveChanges()
 Dim result As IList(Of EntityWithIncrementalGuid) = context _
    .GetAll(Of EntityWithIncrementalGuid)() _
    .OrderBy(Function(x) x.ID).ToList()
 For i As Integer = 0 To result.Count - 1
  Debug.Assert(result(i).ID.Equals(guids(i)))
 Next i
End Using

Understanding the Sequential GUIDs Generation Algorithm

Telerik Data Access uses internally the IncrementalGuidKeyGenerator class for sequential GUIDs generation. The voa_keygen table, which is also used by the HighLow key generator mechanism, is used as a repository to store the most recent Guid value. Telerik Data Access generates RFC 4122 complaint Guid values.

When an application connects to a database for the first time, Telerik Data Access initializes various internal metadata structures including the key generator table. If an incremental Guid has never been requested for the database, Telerik Data Access uses the Guid.NewGuid() method from .NET to obtain a random Guid value that is used as the start value.

Certain bytes (out of 16 bytes) that make up a Guid are used to store the version and variant of the Guid. Telerik Data Access sets the Guid version to its own Telerik Data Access version, thus preventing clashes with other Guid algorithms (random, sequential).

Every backend has its own way of sorting a Guid value so a Guid value that is considered to be greater than another Guid in MS SqlServer is treated as lesser in MySql. Keeping this in mind, the most significant byte of the start Guid is set to "0xff", i.e. to the highest possible byte value. This ensures that all incremental Guids generated by Telerik Data Access are inserted on the higher side of an index, if an index exists on the corresponding column. The resulting Guid (128 bits) is stored in the key generator table as 4 integer values.

The next time an incremental Guid is requested, Telerik Data Access reads these 4 integer values from the key generator table to reconstruct the Guid value. Based on the selected backend’s Guid sorting algorithm (each backend sorts Guid values in a defined way), the appropriate bytes within the Guid are incremented. The resulting Guid is then written back to the key generator table as 4 integers.

Telerik Data Access always reserves a minimum of 10 incremental Guid values and writes the resulting value to the key generator table. This is done to avoid accessing the key generator table for every request. In case the user requests more than the remaining reserved values, the requested values are obtained by incrementing the Guid stored in the key generator table. For example, if the IncrementalGuid key generator has 4 values remaining before it needs to access the key generator table and the user requests for 20 incremental Guids, these 4 values are discarded and a Guid value is constructed out of the 4 integer values from key generator table. The 20 Guids are incremented from this Guid onwards. This ensures that the multiple Guid values returned by the context are always incremental without any "holes".

Incremental Guid Range

Once the data is copied between these instances, new data can be added in them and it should be possible to easy synchronize these changes again later on. The problem is that the sequential Guid key generator will generate similar Guid values in these databases. Telerik Data Access allows you to avoid these issues by providing you with an API that can change the used number range for new Guid values per database. The number range uses one byte in the sequential Guid so that clashes are avoided. Additionally, a Guid with a higher number range is also a higher Guid from the server perspective. The number range of a database can be changed at any time. It is possible to compare the number ranges of two databases. To achieve this goal, Telerik Data Access offers two methods that are accessible through the KeyGenerators object exposed by the OpenAccessContext:

GetIncrementalGuidRange - retrieves the range of the last generated incremental Guid value.
SetIncrementalGuidRange(byte range) - sets the range of the next generated incremental Guid value.

Resetting Incremental GUIDs

Consider a model where some of the domain classes are using client-side sequential Guids. At some point, the application has to be deployed and/or needs to have its data synchronized. This can lead to Guid collision or you may want to reset the currently used Guid, which is stored in the database. To achieve this goal, Telerik Data Access offers the ResetIncrementalGuid method that is accessible through the KeyGenerators object exposed by the OpenAccessContext. The ResetIncrementalGuid method will reset the current unique identifier to a random value.