Building a thread-safe GUID increment'er

Question

In my below code, I'm locking the guid, to try and make it thread safe. With my example application, I will get a "duplicate key" about every 10 times I run the program. Aka, I get a duplicate, which is not what I need.

Is there anyway to make the ".NextGuid" thread safe?

using System;    
namespace MyConsoleOne.BAL
{
    public class GuidStore
    {
        private static object objectlock = new object();    
        private Guid StartingGuid { get; set; }    
        private Guid? LastGuidHolder { get; set; }    
        public GuidStore(Guid startingGuid)
        {
            this.StartingGuid = startingGuid;
        }

        public Guid? GetNextGuid()
        {
            lock (objectlock)
            {
                if (this.LastGuidHolder.HasValue)
                {
                    this.LastGuidHolder = Increment(this.LastGuidHolder.Value);
                }
                else
                {
                    this.LastGuidHolder = Increment(this.StartingGuid);
                }
            }    
            return this.LastGuidHolder;
        }

        private Guid Increment(Guid guid)
        {    
            byte[] bytes = guid.ToByteArray();    
            byte[] order = { 15, 14, 13, 12, 11, 10, 9, 8, 6, 7, 4, 5, 0, 1, 2, 3 };    
            for (int i = 0; i < 16; i++)
            {
                if (bytes[order[i]] == byte.MaxValue)
                {
                    bytes[order[i]] = 0;
                }
                else
                {
                    bytes[order[i]]++;
                    return new Guid(bytes);
                }
            }    
            throw new OverflowException("Guid.Increment failed.");
        }
    }
}

using MyConsoleOne.BAL;
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace MyConsoleOne
{
    class Program
    {
        static void Main(string[] args)
        {
            GuidStore gs = new GuidStore(Guid.NewGuid());

            for (int i = 0; i < 1000; i++)
            {
                Console.WriteLine(i);
                Dictionary<Guid, int> guids = new Dictionary<Guid, int>();
                Parallel.For(0, 1000, j =>
                {
                    Guid? currentGuid = gs.GetNextGuid();
                    guids.Add(currentGuid.Value, j);
                    Console.WriteLine(currentGuid);
                }); // Parallel.For
            }    
            Console.WriteLine("Press ENTER to Exit");
            Console.ReadLine();
        }
    }
}

My code is a combination of:

• Making Guid properties threadsafe
• Increment Guid in C#

Since I'm getting "Why not use Guid.NewGuid" questions, I'll provide the reason here:

I have a parent process that has a uniqueidentifier which is created by Guid.NewGuid(). I'll refer to this as the "parent guid". That parent process will create N number of files. If I were writing from scratch, I would just append the "N" at the end of the filename. So if the parent Guid was "11111111-1111-1111-1111-111111111111" for example, I would write files

"11111111-1111-1111-1111-111111111111_1.txt"
"11111111-1111-1111-1111-111111111111_2.txt"
"11111111-1111-1111-1111-111111111111_3.txt"

, etc, etc. However, via the existing "contract" with the client ::: the filename must have a (unique) Guid in it and not have that "N" (1,2,etc,etc) value in the filename (this "contract" has been in existence for years, so its set in stone pretty much). With the functionality laid out here, I'll be able to keep the "contract", but have file names that are loosely tied to the "parent" Guid (which again the parent is generated by Guid.NewGuid()). Collision is NOT an issue with the filenames (they are put under a distinct folder for the 'process' execution). Collision is an issue with the "parent" Guid. But again, that is already handled with Guid.NewGuid.

So with a starting Guid of "11111111-1111-1111-1111-111111111111", I'll be able to write filenames like:

OTHERSTUFF_111111111-1111-1111-1111-111111111112_MORESTUFF.txt
OTHERSTUFF_111111111-1111-1111-1111-111111111113_MORESTUFF.txt
OTHERSTUFF_111111111-1111-1111-1111-111111111114_MORESTUFF.txt
OTHERSTUFF_111111111-1111-1111-1111-111111111115_MORESTUFF.txt
OTHERSTUFF_111111111-1111-1111-1111-111111111116_MORESTUFF.txt
OTHERSTUFF_111111111-1111-1111-1111-111111111117_MORESTUFF.txt
OTHERSTUFF_111111111-1111-1111-1111-111111111118_MORESTUFF.txt
OTHERSTUFF_111111111-1111-1111-1111-111111111119_MORESTUFF.txt
OTHERSTUFF_111111111-1111-1111-1111-11111111111a_MORESTUFF.txt
OTHERSTUFF_111111111-1111-1111-1111-11111111111b_MORESTUFF.txt

So in my example above, the "parent guid" is represented by "this.StartingGuid"....and then I get "incremented" guid's off of that.

And also. I can write better unit-tests, because now I will know the filenames ahead of time.

APPEND:

Final Code Version:

public class GuidStore
{
    private static object objectlock = new object();

    private static int[] byteOrder = { 15, 14, 13, 12, 11, 10, 9, 8, 6, 7, 4, 5, 0, 1, 2, 3 };

    private Guid StartingGuid { get; set; }

    private Guid? LastGuidHolder { get; set; }

    public GuidStore(Guid startingGuid)
    {
        this.StartingGuid = startingGuid;
    }

    public Guid GetNextGuid()
    {
        return this.GetNextGuid(0);
    }

    public Guid GetNextGuid(int firstGuidOffSet)
    {
        lock (objectlock)
        {
            if (this.LastGuidHolder.HasValue)
            {
                this.LastGuidHolder = Increment(this.LastGuidHolder.Value);
            }
            else
            {
                this.LastGuidHolder = Increment(this.StartingGuid);
                for (int i = 0; i < firstGuidOffSet; i++)
                {
                    this.LastGuidHolder = Increment(this.LastGuidHolder.Value);
                }
            }

            return this.LastGuidHolder.Value;
        }
    }

    private static Guid Increment(Guid guid)
    {
        var bytes = guid.ToByteArray();
        var canIncrement = byteOrder.Any(i => ++bytes[i] != 0);
        return new Guid(canIncrement ? bytes : new byte[16]);
    }
}

and UnitTests:

public class GuidStoreUnitTests
{
    [TestMethod]
    public void GetNextGuidSimpleTest()
    {
        Guid startingGuid = new Guid("11111111-1111-1111-1111-111111111111");
        GuidStore gs = new GuidStore(startingGuid);


        List<Guid> guids = new List<Guid>();

        const int GuidCount = 10;

        for (int i = 0; i < GuidCount; i++)
        {
            guids.Add(gs.GetNextGuid());
        }

        Assert.IsNotNull(guids);
        Assert.AreEqual(GuidCount, guids.Count);
        Assert.IsNotNull(guids.FirstOrDefault(g => g == new Guid("11111111-1111-1111-1111-111111111112")));
        Assert.IsNotNull(guids.FirstOrDefault(g => g == new Guid("11111111-1111-1111-1111-111111111113")));
        Assert.IsNotNull(guids.FirstOrDefault(g => g == new Guid("11111111-1111-1111-1111-111111111114")));
        Assert.IsNotNull(guids.FirstOrDefault(g => g == new Guid("11111111-1111-1111-1111-111111111115")));
        Assert.IsNotNull(guids.FirstOrDefault(g => g == new Guid("11111111-1111-1111-1111-111111111116")));
        Assert.IsNotNull(guids.FirstOrDefault(g => g == new Guid("11111111-1111-1111-1111-111111111117")));
        Assert.IsNotNull(guids.FirstOrDefault(g => g == new Guid("11111111-1111-1111-1111-111111111118")));
        Assert.IsNotNull(guids.FirstOrDefault(g => g == new Guid("11111111-1111-1111-1111-111111111119")));
        Assert.IsNotNull(guids.FirstOrDefault(g => g == new Guid("11111111-1111-1111-1111-11111111111a")));
        Assert.IsNotNull(guids.FirstOrDefault(g => g == new Guid("11111111-1111-1111-1111-11111111111b")));
    }

    [TestMethod]
    public void GetNextGuidWithOffsetSimpleTest()
    {
        Guid startingGuid = new Guid("11111111-1111-1111-1111-111111111111");
        GuidStore gs = new GuidStore(startingGuid);

        List<Guid> guids = new List<Guid>();

        const int OffSet = 10;

        guids.Add(gs.GetNextGuid(OffSet));

        Assert.IsNotNull(guids);
        Assert.AreEqual(1, guids.Count);

        Assert.IsNotNull(guids.FirstOrDefault(g => g == new Guid("11111111-1111-1111-1111-11111111111c")));
    }

    [TestMethod]
    public void GetNextGuidMaxRolloverTest()
    {
        Guid startingGuid = new Guid("ffffffff-ffff-ffff-ffff-ffffffffffff");
        GuidStore gs = new GuidStore(startingGuid);

        List<Guid> guids = new List<Guid>();

        const int OffSet = 10;

        guids.Add(gs.GetNextGuid(OffSet));

        Assert.IsNotNull(guids);
        Assert.AreEqual(1, guids.Count);

        Assert.IsNotNull(guids.FirstOrDefault(g => g == Guid.Empty));
    }

    [TestMethod]
    public void GetNextGuidThreadSafeTest()
    {
        Guid startingGuid = Guid.NewGuid();
        GuidStore gs = new GuidStore(startingGuid);

        /* The "key" of the ConcurrentDictionary must be unique, so this will catch any duplicates */
        ConcurrentDictionary<Guid, int> guids = new ConcurrentDictionary<Guid, int>();
        Parallel.For(
            0,
            1000,
            j =>
            {
                Guid currentGuid = gs.GetNextGuid();
                if (!guids.TryAdd(currentGuid, j))
                {
                    throw new ArgumentOutOfRangeException("GuidStore.GetNextGuid ThreadSafe Test Failed");
                }
            }); // Parallel.For
    }

    [TestMethod]
    public void GetNextGuidTwoRunsProduceSameResultsTest()
    {
        Guid startingGuid = Guid.NewGuid();

        GuidStore gsOne = new GuidStore(startingGuid);

        /* The "key" of the ConcurrentDictionary must be unique, so this will catch any duplicates */
        ConcurrentDictionary<Guid, int> setOneGuids = new ConcurrentDictionary<Guid, int>();
        Parallel.For(
            0,
            1000,
            j =>
            {
                Guid currentGuid = gsOne.GetNextGuid();
                if (!setOneGuids.TryAdd(currentGuid, j))
                {
                    throw new ArgumentOutOfRangeException("GuidStore.GetNextGuid ThreadSafe Test Failed");
                }
            }); // Parallel.For

        gsOne = null;

        GuidStore gsTwo = new GuidStore(startingGuid);

        /* The "key" of the ConcurrentDictionary must be unique, so this will catch any duplicates */
        ConcurrentDictionary<Guid, int> setTwoGuids = new ConcurrentDictionary<Guid, int>();
        Parallel.For(
                0,
                1000,
                j =>
                {
                    Guid currentGuid = gsTwo.GetNextGuid();
                    if (!setTwoGuids.TryAdd(currentGuid, j))
                    {
                        throw new ArgumentOutOfRangeException("GuidStore.GetNextGuid ThreadSafe Test Failed");
                    }
                }); // Parallel.For

        bool equal = setOneGuids.Select(g => g.Key).OrderBy(i => i).SequenceEqual(
                         setTwoGuids.Select(g => g.Key).OrderBy(i => i), new GuidComparer<Guid>());

        Assert.IsTrue(equal);
    }
}

internal class GuidComparer<Guid> : IEqualityComparer<Guid>
{
    public bool Equals(Guid x, Guid y)
    {
        return x.Equals(y);
    }

    public int GetHashCode(Guid obj)
    {
        return 0;
    }
}

Answer 1

You have two problems here:

1. Dictionary.Add() is NOT threadsafe. Use ConcurrentDictionary.TryAdd() instead.
2. Your implementation of GetNextGuid() has a race condition because your are returning this.LastGuidHolder outside the lock, so it could be modified by another thread just before it is returned.

An obvious solution is to move the return inside the lock:

public Guid? GetNextGuid()
{
    lock (objectlock)
    {
        if (this.LastGuidHolder.HasValue)
        {
            this.LastGuidHolder = Increment(this.LastGuidHolder.Value);
        }
        else
        {
            this.LastGuidHolder = Increment(this.StartingGuid);
        }

        return this.LastGuidHolder;
    }
}

However, I would change the return type to Guid - it doesn't seem to serve any purpose to return a Guid? - that's something that should be hidden away inside the class:

public Guid GetNextGuid()
{
    lock (objectlock)
    {
        if (this.LastGuidHolder.HasValue)
        {
            this.LastGuidHolder = Increment(this.LastGuidHolder.Value);
        }
        else
        {
            this.LastGuidHolder = Increment(this.StartingGuid);
        }

        return this.LastGuidHolder.Value;
    }
}

Here's a version of your test method using ConcurrentDictionary:

static void Main(string[] args)
{
    GuidStore gs = new GuidStore(Guid.NewGuid());

    for (int i = 0; i < 1000; i++)
    {
        Console.WriteLine(i);
        ConcurrentDictionary<Guid, int> guids = new ConcurrentDictionary<Guid, int>();
        Parallel.For(0, 1000, j =>
        {
            Guid currentGuid = gs.GetNextGuid();
            if (!guids.TryAdd(currentGuid, j))
            {
                Console.WriteLine("Duplicate found!");
            }
        }); // Parallel.For
    }

    Console.WriteLine("Press ENTER to Exit");
    Console.ReadLine();
}

Having said all that, I cannot understand why you aren't just using Guid.NewGuid()...