Increment method is not atomic?
From what I understood, the Increment method should be atomic. In other words, the method should lock the current value, increment it, unlock and return the incremented value. If this is wrong, I'm unsure how increment would be used effectively. Please let me know if it is [I]not[/I] supposed to be atomic.
We have a large distributed system that processes and saves hundreds of incoming items per-second across multiple servers. Each item is to be assigned a system-wide sequential ID. Ideally, MemCached would be used to store the sequential id and Increment would be called to both retrieve and increment id from wherever it is needed.
We are using enyim 2.3 with Membase.Store 2.4, Windows 7 (x64). What I have found when testing our system using the Increment approach is that I'll frequently get 2 items with the same Id in the system which I assumed would be impossible, however, to test the Increment method I wrote the following c# program:
[FONT="Courier New"]class Program
{
static void Main(string[] args)
{
try
{
MemcachedClient client = new MemcachedClient();
ulong id = 0;
ulong previousId = ulong.MaxValue;
DateTime now = DateTime.Now;
Console.WriteLine("Starting.");
for (int i = 0; i < 10000; i++)
{
id = client.Increment("NextItemId", 0, 1);
if (id == previousId)
Console.WriteLine("Duplicate ID: {0}", id);
previousId = id;
}
Console.WriteLine("Done.");
Console.WriteLine("Duration: {0}ms", DateTime.Now.Subtract(now).TotalMilliseconds);
Console.ReadLine();
}
catch(Exception ex)
{
Console.WriteLine(ex.ToString());
}
}
}[/FONT]
This program works great, increment is called 10000 times in a row without returning any duplicate values.
However, in order to closer replicate the way our system works, I modified the program so that multiple threads were calling the Increment method like so:
[FONT="Courier New"]class Program
{
static MemcachedClient client = new MemcachedClient();
static Dictionary _ids = new Dictionary();
static void Main(string[] args)
{
try
{
DateTime now = DateTime.Now;
Console.WriteLine("Starting.");
for (int i = 0; i < 10000; i++)
{
System.Threading.ThreadPool.QueueUserWorkItem(new System.Threading.WaitCallback(DoWork));
}
Console.WriteLine("Done.");
Console.WriteLine("Duration: {0}ms", DateTime.Now.Subtract(now).TotalMilliseconds);
Console.ReadLine();
}
catch(Exception ex)
{
Console.WriteLine(ex.ToString());
}
}
static void DoWork(object state)
{
ulong id = client.Increment("NextItemId", 0, 1);
try
{
_ids.Add(id, null);
}
catch
{
Console.WriteLine("Duplicate Id: {0}", id);
}
}
}[/FONT]
If atomic, increment should always return an incremented id as in the first program, however, if you test this program it will report that a few duplicate ids were returned from Increment.
The simple answer is to add a Lock{} around the Increment statement, and that does solve the issue for a single program using multiple threads. However, technically, Lock should not be required, and our system will have dozens to hundreds of programs that will be running concurrently over many servers, all of them frequently calling Increment on this MemCached value. My fear is that id duplication will appear unless Increment is truly atomic. Is this a bug?
Thanks for your help.
Slegay, thanks for the reply.
Yes, I was aware of the missing lock around _ids.Add() however, even with the lock around _ids.Add(), if I run the program, most of the time I'll get a handful of "An item with the same key has already been added." exceptions. This should not be happening, and Increment should not have to be executed within a lock. Again, I don't mind doing that since it solves the problem in an individual process, however with multiple processes spread out across dozens of servers, calling Increment must be in itself atomic for the solution to work. Any suggestions?
We're using Memcached as a distributed counter, so you problem intrigued me.
Here's a non-blocking test running 10 threads with 1000 increments each. It populates 10 lists of values, merges those when it's done, sorts and compares.
The test passes. There are no duplicate values.
The test runs on a Northscale cluster with 2 nodes.
Also, I haven't found one Memcached-related post mentioning problems with Increment / Decrement atomicity. I'm afraid either your updated test is wrong, or you're having some configuration issues.
[TestMethod()]
public void ConcurrentCounterTest(){
var uid = Guid.NewGuid().ToString();
var tLists = new Dictionary>();
// set up the job
Action doWork = () => {
for(var i=0; i<1000; i++){
tLists[Thread.CurrentThread].Add(Client.Increment(uid, 0, 1));
}
};
// create 10 threads
var tStart = new ThreadStart(doWork);
for(var i=0; i<10; i++){
var t = new Thread(tStart);
tLists.Add(t, new List());
t.Start();
}
// loop until we're done
var isFinished = false;
while(!isFinished){
Thread.Sleep(10);
isFinished = true;
foreach(var t in tLists.Keys){
if (t.ThreadState == ThreadState.Running)
{
isFinished = false;
break;
}
}
}
// merge the values
var fullList = new List();
foreach (var list in tLists.Values)
fullList.AddRange(list);
// put a debug point after this and inspect the list so you can see all values are there
fullList.Sort();
// Compare the full list of values with a list of distinct values
Assert.AreEqual(fullList.Count, fullList.Distinct().Count());
}
Just to check, is there perhaps a difference between proxy port and direct port? I would think if you're using the Enyim client, the Direct Port is probably the default and we'd be less likely to have an issue there, but thought I should double check that both tests are using the same configuration.
I forgot to mention I'm using the latest Enyim NorthScale client.
Slegay,
Thanks again for your reply and sample code of a multithreaded use of Increment that does not produce duplicates. Unfortunately, that does not explain why the example I provided [I]does[/I] produce duplicates. Like I mentioned, even adding a lock {} around _ids.Add() continues to show that duplicate keys are trying to be added to the dictionary. This makes no sense if Interval is truly atomic as multiple threads running the DoWork() method will all call Increment individually before attempting to add an id to _ids.
Have you tried to reproduce this using the same or similar code? We are using the latest enyim client, and no proxy.
Thanks!
Have you tried to reproduce this using the same or similar code? We are using the latest enyim client, and no proxy.
Can you confirm, this means it's configured with the "direct port", not the proxy port? Thanks.
You're right, Memcached Increment / Decrement is supposed to be atomic.
A major problem I'm noticing in your code is the way you're modifying the dictionary is not thread safe. My guess is your exception has nothing to do with Memcached, but with data corruption due to unsafe collection manipulation.
I'd suggest using a lock around "_ids.Add(id, null);" and run the test again (in the try/catch block of the DoWork method).
Or an even better test would be to use non-blocking code and 1 collection/dictionary per thread. Once your test is complete, compare or merge the collections and look for identical ids.