CODEWITHSUNDEEP
c#guidsequence
Chris Marisic
Chris Marisic

Reputation: 33098

Sequential Guid Generator

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

Upvotes: 56

Views: 57011

Answers (10)

Schwarzie2478
Schwarzie2478

Reputation: 2276

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.

Upvotes: 6

Michael Seifert
Michael Seifert

Reputation: 182

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;
    }
}
}

Upvotes: 1

Moslem Ben Dhaou
Moslem Ben Dhaou

Reputation: 7005

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);
}

Upvotes: 21

Ian Boyd
Ian Boyd

Reputation: 256571

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://stackoverflow.com/a/47682820/12597
   //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

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
    • 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

Upvotes: 78

toddmo
toddmo

Reputation: 22396

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);
    }
  }
}

Upvotes: 3

Chris Marisic
Chris Marisic

Reputation: 33098

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

Upvotes: 2

John Boker
John Boker

Reputation: 83699

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;
        }
    }
}

Upvotes: 28

Ronny Heuschkel
Ronny Heuschkel

Reputation: 558

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

Upvotes: 3

Charles
Charles

Reputation: 51

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;

    }

}

}

Upvotes: 4

Mike Chaliy
Mike Chaliy

Reputation: 26648

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

Upvotes: 2

Related Questions