Sequential Guid Generator

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

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

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

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

Tags:

C#

Guid

Sequence

Recent Posts