Sequential Guid Generator

Question

Is there any way to get the functionality of the Sql Server 2005+ Sequential Guid generator without inserting records to read it back on round trip or invoking a native win dll call? I saw someone answer with a way of using rpcrt4.dll but I'm not sure if that would be able to work from my hosted environment for production.

Edit: Working with @John Boker's answer I attempted to turn it into more of a GuidComb generator instead of being dependent on the last generated Guid other than starting over. That for the seed instead of starting with Guid.Empty that I use

public SequentialGuid()
{
    var tempGuid = Guid.NewGuid();
    var bytes = tempGuid.ToByteArray();
    var time = DateTime.Now;
    bytes[3] = (byte) time.Year;
    bytes[2] = (byte) time.Month;
    bytes[1] = (byte) time.Day;
    bytes[0] = (byte) time.Hour;
    bytes[5] = (byte) time.Minute;
    bytes[4] = (byte) time.Second;
    CurrentGuid = new Guid(bytes);
}

I based that off the comments on

// 3 - the least significant byte in Guid ByteArray 
        [for SQL Server ORDER BY clause]
// 10 - the most significant byte in Guid ByteArray 
        [for SQL Server ORDERY BY clause]
SqlOrderMap = new[] {3, 2, 1, 0, 5, 4, 7, 6, 9, 8, 15, 14, 13, 12, 11, 10};

Does this look like the way I'd want to seed a guid with the DateTime or does it look like I should do it in reverse and work backwards from the end of the SqlOrderMap indexes? I'm not too concerned about their being a paging break anytime an initial guid would be created since it would only occur during application recycles.

Edit: 2020+ update

At this point I strongly prefer Snowflake identifiers using something like https://github.com/RobThree/IdGen

Doodle

First of all - what is a purpose for this? I'm asking this because the whole purpose of Guid is to be random and unique. If you just need something incremental, you can use Int type field and set it to be AutoIncremental. – Stendhal

from yafla.com/dennisforbes/Sequential-GUIDs-in-SQL-Server/… : As discussed in the entry on using GUIDs in your database, GUIDs in SQL Server 2000 are, at least from the user's perspective, "random". This can lead to a fragmentation and splits in your data, and it's a common reason to avoid GUIDs in the first place. – Ellata

Well, that actually might help. I'd say that there's probably a misunderstanding of the whole purpose of GUIDs. If Chris just needs something incremental, there's another good solution called Int + AutoIncrement. There's no need for GUID in this case. Can someone explain me why someone would need to have incremental Guids?! – Stendhal

Vitaly, you are missing the point. SQL200x does have a Sequential Guid generator to optimize indexing based on Guids. Plenty terms to seearch on. – Teletypewriter

Henk, optimization has to be done only by results of speed tests. There're many examples when there were made wrong assumptions and "optimization" based on these assumptions didn't really work. I was wondering if there's any real purpose for sequential guids besides assumptions that this is the best way to go for any table structure and any queries by that table. Also check this article with speed tests on Guid which compares integer vs sequential guids: sql-server-performance.com/articles/per/… – Stendhal

The purpose of this to have a guid that will generate keys close to each other from my application to be sent to the database that i can have a clustered index on my primary key column (the guid). – Doodle

@Chris, I see what you mean, this is exactly what I was saying about. Guids have pros and cons. Pros of Guid is absolute uniqueness. So for example if you merge 2 databases, you don't need to create new ids (because they will never intersect). Cons are that Guid is more consuming than integer. You can use Sequential Guids and get a better performance than random ones, but you will lose the advantage: absolute uniqueness. And that could be ok: we don't merge databases too often, but you have another alternative - integer keys that support autoincrement, so please consider using them. – Stendhal

Depending on the database to generate my keys for me is not acceptable IMO. – Doodle

@Chris, we're talking about SQL Server 2005+ here. – Stendhal

In what way is your proposed solution 'sequential', given that it will call NewGuid() every time to construct the base? What are you actually trying to do? – Undersigned

Ah - just read @Sweepback Boker's linked article; now it all makes sense... however won't your code produce two possibly non-sequential GUIDs if run twice within 1 second? (Because the parts of NewGuid() that you don't change may not change sequentially). – Undersigned

I want IDs generated by my application, not the database. – Doodle

They would still be sequential, but one could possibly be lower than the other. The order doesn't matter because a clustered index will order them low to high (or something similarly) anyway. – Doodle

Possible duplicate of Is there a .NET equalent to SQL Servers newsequentialid() – Sweepback

@Sweepback they're not duplicated, that question was about how to do it while being dependent on SQL Server whereas mine was to do it without the dependency. I'm not attempting to reword a nearly decade old question if you have so little to do, please make an attempt. – Doodle

Adding a link to the article in the first comment, because it's not available anymore. web.archive.org/web/20110313145435/http://www.yafla.com:80/… – Pandowdy

Answer 1

this person came up with something to make sequential guids, here's a link

http://developmenttips.blogspot.com/2008/03/generate-sequential-guids-for-sql.html

relevant code:

public class SequentialGuid {
    Guid _CurrentGuid;
    public Guid CurrentGuid {
        get {
            return _CurrentGuid;
        }
    }

    public SequentialGuid() {
        _CurrentGuid = Guid.NewGuid();
    }

    public SequentialGuid(Guid previousGuid) {
        _CurrentGuid = previousGuid;
    }

    public static SequentialGuid operator++(SequentialGuid sequentialGuid) {
        byte[] bytes = sequentialGuid._CurrentGuid.ToByteArray();
        for (int mapIndex = 0; mapIndex < 16; mapIndex++) {
            int bytesIndex = SqlOrderMap[mapIndex];
            bytes[bytesIndex]++;
            if (bytes[bytesIndex] != 0) {
                break; // No need to increment more significant bytes
            }
        }
        sequentialGuid._CurrentGuid = new Guid(bytes);
        return sequentialGuid;
    }

    private static int[] _SqlOrderMap = null;
    private static int[] SqlOrderMap {
        get {
            if (_SqlOrderMap == null) {
                _SqlOrderMap = new int[16] {
                    3, 2, 1, 0, 5, 4, 7, 6, 9, 8, 15, 14, 13, 12, 11, 10
                };
                // 3 - the least significant byte in Guid ByteArray [for SQL Server ORDER BY clause]
                // 10 - the most significant byte in Guid ByteArray [for SQL Server ORDERY BY clause]
            }
            return _SqlOrderMap;
        }
    }
}

Ellata

People should be careful of using this code, as it generally fails at its #1 goal: being sortable. Yes it works if you +1 each time to an existing value. But it in no way matches a type 1 uuid (i.e. sortable guids), and doesn't match in any way what newsequentialid() does. This just creates a random guid, then lets you add to it. Subsequent calls will start with a different random guid - thus missing the entire point. A sequential guid needs to do what the RFC says - maintain a global state. – Injudicious

Answer 2

You could just use the same Win32 API function that SQL Server uses:

UuidCreateSequential

and apply some bit-shifting to put the values into big-endian order.

And since you want it in C#:

private class NativeMethods
{
   [DllImport("rpcrt4.dll", SetLastError=true)]
   public static extern int UuidCreateSequential(out Guid guid);
}

public static Guid NewSequentialID()
{
   //Code is released into the public domain; no attribution required
   const int RPC_S_OK = 0;

   Guid guid;
   int result = NativeMethods.UuidCreateSequential(out guid);
   if (result != RPC_S_OK)
      return Guid.NewGuid();

   //Endian swap the UInt32, UInt16, and UInt16 into the big-endian order (RFC specified order) that SQL Server expects
   //See https://mcmap.net/q/245439/-is-there-a-net-equivalent-to-sql-server-39-s-newsequentialid
   //Short version: UuidCreateSequential writes out three numbers in litte, rather than big, endian order
   var s = guid.ToByteArray();
   var t = new byte[16];

   //Endian swap UInt32
   t[3] = s[0];
   t[2] = s[1];
   t[1] = s[2];
   t[0] = s[3];
   //Endian swap UInt16
   t[5] = s[4];
   t[4] = s[5];
   //Endian swap UInt16
   t[7] = s[6];
   t[6] = s[7];
   //The rest are already in the proper order
   t[8] = s[8];
   t[9] = s[9];
   t[10] = s[10];
   t[11] = s[11];
   t[12] = s[12];
   t[13] = s[13];
   t[14] = s[14];
   t[15] = s[15];

   return new Guid(t);
}

See also

• Is there a .NET equalent to SQL Servers newsequentialid()

---

Microsoft's UuidCreateSequential is just an implementation of a type 1 uuid from RFC 4122.

A uuid has three important parts:

• node: (6 bytes) - the computer's MAC address
• timestamp: (7 bytes) - number of 100 ns intervals since 00:00:00.00, 15 October 1582 (the date of Gregorian reform to the Christian calendar)
• clockSequenceNumber (2 bytes) - counter in case you generate a guid faster than 100ns, or you change your mac address

The basic algorithm is:

1. obtain a system-wide lock
2. read the last node, timestamp and clockSequenceNumber from persistent storage (registry/file)
3. get the current node (i.e. MAC address)
4. get the current timestamp
5. • a) if the saved state was not available or corrupted, or the mac address has changed, generate a random clockSequenceNumber
   • b) if the state was available, but the current timestamp is the same or older than the saved timestamp, increment the clockSequenceNumber
6. save node, timestamp and clockSequenceNumber back to persistent storage
7. release the global lock
8. format the guid structure according to the rfc

There is a 4-bit version number, and 2 bit variant that also need to be ANDed into the data:

guid = new Guid(
      timestamp & 0xFFFFFFFF,  //timestamp low
      (timestamp >> 32) & 0xFFFF, //timestamp mid
      ((timestamp >> 40) & 0x0FFF), | (1 << 12) //timestamp high and version (version 1)
      (clockSequenceNumber & 0x3F) | (0x80), //clock sequence number and reserved
      node[0], node[1], node[2], node[3], node[4], node[5], node[6]);

Note: Completely untested; i just eyeballed it from the RFC.

• the byte order might have to be changed (Here is byte order for sql server)
• you might want to create your own version, e.g. Version 6 (version 1-5 are defined). That way you're guaranteed to be universally unique

Injudicious

This is useful for others, I had originally asked how to NOT do it with the DLL call. – Doodle

Oh, sorry, i completely missed that. Re-reading the question i...sorta see it. – Injudicious

the guids generated by UuidCreateSequential are not sortable using the default guid comparer, is there a way to do that? – Obsidian

@AhmedSaid I updated the answer so that the generated Guids are sortable by SQL Server (see my answer here. Short version: UuidCreateSequential writes out numbers in little endian order rather than big-endian. SQL Server assumes big-endian when sorting; so we can endian swap the values generated by UuidCreateSequential. – Injudicious

can u explain how to put in this array of bytes clockSequenceNumber value generated by code - supose I generated 64321 then what calculation should I execute to fill 2 bytes in output guid array ? – Palimpsest

Answer 3

Here is how NHibernate implements the Guid.Comb algorithm:

private Guid GenerateComb()
{
    byte[] guidArray = Guid.NewGuid().ToByteArray();

    DateTime baseDate = new DateTime(1900, 1, 1);
    DateTime now = DateTime.UtcNow;

    // Get the days and milliseconds which will be used to build the byte string 
    TimeSpan days = new TimeSpan(now.Ticks - baseDate.Ticks);
    TimeSpan msecs = now.TimeOfDay;

    // Convert to a byte array 
    // Note that SQL Server is accurate to 1/300th of a millisecond so we divide by 3.333333 
    byte[] daysArray = BitConverter.GetBytes(days.Days);
    byte[] msecsArray = BitConverter.GetBytes((long) (msecs.TotalMilliseconds / 3.333333));

    // Reverse the bytes to match SQL Servers ordering 
    Array.Reverse(daysArray);
    Array.Reverse(msecsArray);

    // Copy the bytes into the guid 
    Array.Copy(daysArray, daysArray.Length - 2, guidArray, guidArray.Length - 6, 2);
    Array.Copy(msecsArray, msecsArray.Length - 4, guidArray, guidArray.Length - 4, 4);

    return new Guid(guidArray);
}

Rienzi

Turned it into an extension here – Abrade

@Moslem Ben Dhaou:May I ask why you only changed the last section of the GUID? Isn't it better to change the first part? – Agon

@Moslem Ben Dhaou:How does Sql Server sort it? – Agon

An updated version in the master branch: github.com/nhibernate/nhibernate-core/blob/master/src/… – Denisse

Care: that algorithm uses DateTime.Now instead of DateTime.UtcNow, so for time zones with daylight saving, it will generates non sequential ids for an hour every year... Good luck finding what has happended. Use the last version provided by @SlimShaggy. – Autocade

Answer 4

Maybe interesting to compare with the other suggestions:

EntityFramework Core also implements a sequentialGuidValueGenerator. They generate randoms guids for each value and only change the most significant bytes based on a timestamp and thread-safe increments for sorting in SQL Server.

source link

This leads to values that are all very different but with a timestamp sortable.

Humanoid

You can find official microsoft docs about that: learn.microsoft.com/en-us/dotnet/api/… – Pained

Answer 5

C# Version

    public static Guid ToSeqGuid()
    {
        Int64 lastTicks = -1;
        long ticks = System.DateTime.UtcNow.Ticks;

        if (ticks <= lastTicks)
        {
            ticks = lastTicks + 1;
        }

        lastTicks = ticks;

        byte[] ticksBytes = BitConverter.GetBytes(ticks);

        Array.Reverse(ticksBytes);

        Guid myGuid = new Guid();
        byte[] guidBytes = myGuid.ToByteArray();

        Array.Copy(ticksBytes, 0, guidBytes, 10, 6);
        Array.Copy(ticksBytes, 6, guidBytes, 8, 2);

        Guid newGuid = new Guid(guidBytes);

        string filepath = @"C:\temp\TheNewGuids.txt";
        using (StreamWriter writer = new StreamWriter(filepath, true))
        {
            writer.WriteLine("GUID Created =  " + newGuid.ToString());
        }

        return newGuid;

    }

}

}

Coexecutor

Answer 6

My solution (in VB but easy to convert). It changes the most significant (for SQL Server sorting) first 8 bytes of the GUID to DateTime.UtcNow.Ticks and also has extra code to help the issue of getting the same Ticks multiple times if you call for a new GUID faster than the system clock updates.

Private ReadOnly _toSeqGuidLock As New Object()
''' <summary>
''' Replaces the most significant eight bytes of the GUID (according to SQL Server ordering) with the current UTC-timestamp.
''' </summary>
''' <remarks>Thread-Safe</remarks>
<System.Runtime.CompilerServices.Extension()> _
Public Function ToSeqGuid(ByVal guid As Guid) As Guid

    Static lastTicks As Int64 = -1

    Dim ticks = DateTime.UtcNow.Ticks

    SyncLock _toSeqGuidLock

        If ticks <= lastTicks Then
            ticks = lastTicks + 1
        End If

        lastTicks = ticks

    End SyncLock

    Dim ticksBytes = BitConverter.GetBytes(ticks)

    Array.Reverse(ticksBytes)

    Dim guidBytes = guid.ToByteArray()

    Array.Copy(ticksBytes, 0, guidBytes, 10, 6)
    Array.Copy(ticksBytes, 6, guidBytes, 8, 2)

    Return New Guid(guidBytes)

End Function

Gauntlett

Answer 7

I just took the NHibernate based answer by Moslem Ben Dhaou and made it an extension function:

using System;

namespace Atlas.Core.Kernel.Extensions
{
  public static class Guids
  {
    public static Guid Comb(this Guid source)
    {
      byte[] guidArray = source.ToByteArray();

      DateTime baseDate = new DateTime(1900, 1, 1);
      DateTime now = DateTime.Now;

      // Get the days and milliseconds which will be used to build the byte string 
      TimeSpan days = new TimeSpan(now.Ticks - baseDate.Ticks);
      TimeSpan msecs = now.TimeOfDay;

      // Convert to a byte array 
      // Note that SQL Server is accurate to 1/300th of a millisecond so we divide by 3.333333 
      byte[] daysArray = BitConverter.GetBytes(days.Days);
      byte[] msecsArray = BitConverter.GetBytes((long)(msecs.TotalMilliseconds / 3.333333));

      // Reverse the bytes to match SQL Servers ordering 
      Array.Reverse(daysArray);
      Array.Reverse(msecsArray);

      // Copy the bytes into the guid 
      Array.Copy(daysArray, daysArray.Length - 2, guidArray, guidArray.Length - 6, 2);
      Array.Copy(msecsArray, msecsArray.Length - 4, guidArray, guidArray.Length - 4, 4);

      return new Guid(guidArray);
    }
  }
}

Abrade

DateTime.Now must be changed to DateTime.UtcNow ... otherwise you will have nightmares. – Tashia

Answer 8

As far I know NHibernate have special generator, called GuidCombGenerator. You can look on it.

Burgos

Answer 9

Not specifically guid but I now normally use a Snowflake style sequential id generator. The same benefits of a guid while having even better clustered index compatibility than a sequential guid.

Flakey for .NET Core

IdGen for .NET Framework

Doodle

Answer 10

I ended up writing this C# class to achieve the following that I needed with SQLite (in which GUIDs are stored as BLOBs and sort order is determined by memcmp). I suppose it is not a real GUID but it's tested and it does it job on SQLite.

• Sortable (memcmp) sequential 16-byte array
• Using counter to guarantee correct ordering
• Thread safe

The time resolution seems to vary on OSes and on my Windows it's worse than 1ms. Therefore I chose to use a second bsed resolution where the first 34 bits represent the UnixTime (UTC), and then there is a 22 bit thread safe counter which increments for every request on the same second. If the counter reaches its max, the function sleeps for 500ms and tries again.

On my laptop I could generate and store ~3,2M 16 byte arrays per second.

The class returns a 16-byte array, not a GUID.

namespace SeqGuid
{
public static class SeqGuid
{
    static private Object _lock = new Object();
    static Random _rnd = new Random();
    static UInt64 _lastSecond = 0;
    static int _counter = 0;

    public static UInt64 UnixTime()
    {
        return (UInt64)DateTime.UtcNow.Subtract(DateTime.UnixEpoch).TotalSeconds;
    }

    public static byte[] CreateGuid()
    {
        // One year is 3600*24*365.25 = 31557600 seconds
        // With 34 bits we can hold ~544 years since 1970-01-01
        // 

        UInt64 seconds = UnixTime();

        lock (_lock)
        {
            if (seconds == _lastSecond)
            {
                // 22 bits counter, aka 11-1111-1111-1111-1111-1111 / 0x3F FFFF; 4.1M max / second, 1/4 ns
                _counter++;
                if (_counter >= 0x3F_FFFF)
                {
                    Thread.Sleep(500);
                    // http://msdn.microsoft.com/en-us/library/c5kehkcz.aspx
                    // A lock knows which thread locked it. If the same thread comes again it just increments a counter and does not block.
                    return CreateGuid();
                }
            }
            else
            {
                _lastSecond = seconds;
                _counter = 0;
            }
        }

        // Create 56 bits (7 bytes) {seconds (34bit), _counter(22bit)}
        UInt64 secondsctr = (seconds << 22) | (UInt64)_counter;

        byte[] byte16 = new byte[16] {
            (byte) ((secondsctr  >> 48) & 0xFF),
            (byte) ((secondsctr  >> 40) & 0xFF),
            (byte) ((secondsctr  >> 32) & 0xFF),
            (byte) ((secondsctr  >> 24) & 0xFF),
            (byte) ((secondsctr  >> 16) & 0xFF),
            (byte) ((secondsctr  >>  8) & 0xFF),
            (byte) ((secondsctr  >>  0) & 0xFF),
            (byte) _rnd.Next(0,255),
            (byte) _rnd.Next(0,255), (byte) _rnd.Next(0,255),
            (byte) _rnd.Next(0,255), (byte) _rnd.Next(0,255),
            (byte) _rnd.Next(0,255), (byte) _rnd.Next(0,255),
            (byte) _rnd.Next(0,255), (byte) _rnd.Next(0,255)};

        return byte16;
    }
}
}

Portsmouth