Wednesday, March 9, 2011

The First Cut…

 

The first, naïve implementation of NewSequentialGuid() was:

public static Guid NewSequentialGuid()
{
lock (LockObject)
{
var ticks = DateTime.Now.Ticks;
return new Guid(_a, _b, _c, BitConverter.GetBytes(ticks));
}
}

Exercising this code to print out 10 Guids in a tight loop yielded the following results:


FirstImplementation


Two points leap to our notice:



  1. Several of the Guids are identical – the red circled records are identical.
  2. When the Guids increase, they seem to be increasing at the most significant end of the last two segments of the Guid – the orange circled column is increasing downwards.

Let’s fix the first problem first by introducing a forced delay before creating the Guid, ensuring that the tick count of DateTime has a chance to increment itself.


Fixing the second one requires us to reverse the bytes of the 64-bit integer passed to the last argument to the Guid constructor.


The modified code looks thusly:

public static Guid NewSequentialGuid()
{
lock (LockObject)
{
Thread.Sleep(1);

var ticks = DateTime.Now.Ticks;
var rgb = BitConverter.GetBytes(ticks);
Array.Reverse(rgb);
return new Guid(_a, _b, _c, rgb);
}
}


which generates the following result:


FirstImplementationFixed


Now we’re generating Guids that grow in a reasonable order, and they’re unique.


To further verify that the Guids are unique, we can write a quick test to generate a million or so Guids, put them in a list, sort the list, and ensure that no two Guids are the same.

[TestMethod]
public void TestGuidsAreUnique()
{
var _guids = new List<Guid>(C_MAX_GUIDS);

for (var i = 0; i < C_MAX_GUIDS; i++)
{
_guids.Add(OrderedGuid.NewSequentialGuid());
}

VerifyItemsAreUnique(from _g in _guids orderby _g.ToString() select _g);
}

or even better, with a multi core machine where there can be truly concurrent creation of Guids, we could write this, which creates a million Guids using Parallel.For() into a ConcurrentBag<T>:

[TestMethod]
public void TestGuidsAreUniqueMT()
{
var _guids = new ConcurrentBag<Guid>();

Parallel.For(0,
C_MAX_GUIDS,
() => 0,
(_, __, ___) =>
{
_guids.Add(OrderedGuid.NewSequentialGuid());
return _guids.Count;
},
_ => { });

Assert.AreEqual(C_MAX_GUIDS, _guids.Count);

VerifyItemsAreUnique(from _g in _guids orderby _g.ToString() select _g);
}

We are relieved to notice that both our tests pass. So we can now use this OrderedGuid class in our database-based applications.


FirstImplementationFixedTestsPassed