Redis distributed increment with locking

Question

I have a requirement for generating an counter which will be send to some api calls. My application is running on multiple node so some how I wanted to generate unique counter. I have tried following code

public static long GetTransactionCountForUser(int telcoId)
{
    long valreturn = 0;
    string key = "TelcoId:" + telcoId + ":Sequence";
    if (Muxer != null && Muxer.IsConnected && (Muxer.GetDatabase()) != null)
    {
        IDatabase db = Muxer.GetDatabase();
        var val = db.StringGet(key);
        int maxVal = 999;
        if (Convert.ToInt32(val) < maxVal)
        {
            valreturn = db.StringIncrement(key);
        }
        else
        {
            bool isdone = db.StringSet(key, valreturn);
            //db.SetAdd(key,new RedisValue) .StringIncrement(key, Convert.ToDouble(val))
        }
    }
    return valreturn;
}

And run tested it via Task Parallel libray. When I have boundary values what i see is that multiple time 0 entry is set

Please let me know what correction i needed to do

Update: My final logic is as following

public static long GetSequenceNumberForTelcoApiCallViaLuaScript(int telcoId)
{
    long valreturn = 0;
    long maxIncrement = 9999;//todo via configuration
    if (true)//todo via configuration
    {
        IDatabase db;
        string key = "TelcoId:" + telcoId + ":SequenceNumber";
        if (Muxer != null && Muxer.IsConnected && (db = Muxer.GetDatabase()) != null)
        {
            valreturn = (long)db.ScriptEvaluate(@"
                local result = redis.call('incr', KEYS[1])
                if result > tonumber(ARGV[1]) then
                result = 1
                redis.call('set', KEYS[1], result)
                end
                return result", new RedisKey[] { key }, flags: CommandFlags.HighPriority, values: new RedisValue[] { maxIncrement });
        }
    }
    return valreturn;
}

Okinawa

Why don't you use a simple table with just an identity column, do an insert and use the returned SCOPE_IDENTITY() - that should return something unique all the time. – Hexahydrate

I wanted to avoid db insertion/db round trip. I have a support for Cache Via Redis which i wanted to fully untilize – Okinawa

@KamranShahid please do not use string.Format to parameterize that; I'll edit my example to show the preferred way – Perquisite

btw; I might be wrong, but I don't think GetDatabase will ever return 0, so that check might be redundant – Perquisite

Have updated my answer with argument value usage. So you think there isn't any scenario when Muxer is connected but it doesn't have database? – Okinawa

Answer 1

Indeed, your code is not safe around the rollover boundary, because you are doing a "get", (latency and thinking), "set" - without checking that the conditions in your "get" still apply. If the server is busy around item 1000 it would be possible to get all sorts of crazy outputs, including things like:

1
2
...
999
1000 // when "get" returns 998, so you do an incr
1001 // ditto
1002 // ditto
0 // when "get" returns 999 or above, so you do a set
0 // ditto
0 // ditto
1

Options:

1. use the transaction and constraint APIs to make your logic concurrency-safe
2. rewrite your logic as a Lua script via ScriptEvaluate

Now, redis transactions (per option 1) are hard. Personally, I'd use "2" - in addition to being simpler to code and debug, it means you only have 1 round-trip and operation, as opposed to "get, watch, get, multi, incr/set, exec/discard", and a "retry from start" loop to account for the abort scenario. I can try to write it as Lua for you if you like - it should be about 4 lines.

---

Here's the Lua implementation:

string key = ...
for(int i = 0; i < 2000; i++) // just a test loop for me; you'd only do it once etc
{
    int result = (int) db.ScriptEvaluate(@"
local result = redis.call('incr', KEYS[1])
if result > 999 then
    result = 0
    redis.call('set', KEYS[1], result)
end
return result", new RedisKey[] { key });
    Console.WriteLine(result);
}

Note: if you need to parameterize the max, you would use:

if result > tonumber(ARGV[1]) then

and:

int result = (int)db.ScriptEvaluate(...,
    new RedisKey[] { key }, new RedisValue[] { max });

(so ARGV[1] takes the value from max)

It is necessary to understand that eval/evalsha (which is what ScriptEvaluate calls) are not competing with other server requests, so nothing changes between the incr and the possible set. This means we don't need complex watch etc logic.

Here's the same (I think!) via the transaction / constraint API:

static int IncrementAndLoopToZero(IDatabase db, RedisKey key, int max)
{
    int result;
    bool success;
    do
    {
        RedisValue current = db.StringGet(key);
        var tran = db.CreateTransaction();
        // assert hasn't changed - note this handles "not exists" correctly
        tran.AddCondition(Condition.StringEqual(key, current));
        if(((int)current) > max)
        {
            result = 0;
            tran.StringSetAsync(key, result, flags: CommandFlags.FireAndForget);
        }
        else
        {
            result = ((int)current) + 1;
            tran.StringIncrementAsync(key, flags: CommandFlags.FireAndForget);
        }
        success = tran.Execute(); // if assertion fails, returns false and aborts
    } while (!success); // and if it aborts, we need to redo
    return result;
}

Complicated, eh? The simple success case here is then:

GET {key}    # get the current value
WATCH {key}  # assertion stating that {key} should be guarded
GET {key}    # used by the assertion to check the value
MULTI        # begin a block
INCR {key}   # increment {key}
EXEC         # execute the block *if WATCH is happy*

which is... quite a bit of work, and involves a pipeline stall on the multiplexer. The more complicated cases (assertion failures, watch failures, wrap-arounds) would have slightly different output, but should work.

Perquisite

Can you help me in transaction within stackexchange.redis ? By the way i have seen same values in output window :) – Okinawa

@KamranShahid added a working Lua example; let me know if it doesn't help – Perquisite

I am at very beginner level in redis.It's the first instance I have heard about this lua script. Let me google a bit to see how I can map my logic to this Lua scriptevaluate – Okinawa

I have now tried with both implementation. I have almost same time to test 10000 iteration with both logic. (Transaction stat:05:44:18:2144 end:05:44:30:4357 start:05:44:55:1087 end:05:45:04:7907) LuaScript ( start:05:45:39:9117 end:05:45:51:2947 start:05:46:17:0707 end:05:46:26:5237) Not that complicated other then !success while loop retry – Okinawa

Now I will check if i have call from two application(different redis connection to same server) will there be any duplicate or not – Okinawa

@KamranShahid the code as shown should be safe from any number of connections - that is the entire point. By duplications, I'm assuming you're talking about just the unexpected ones around the time of wrap-around. Obviously, you'll still get duplications every 1000 cycles... i.e. if you issue 1, 2, 3, ... 999, 0, 1, 2, 3, 4, ... 998, 999, 0, 1, 2 - we've seen 1 three times. I'm assuming you're ok with that ;p – Perquisite

I have verified the case during my unit testing.Actually it is STAN implementation for iso messaging where STAN is reset after certain number [999999]Thanks – Okinawa

@MarcGravell +1 for suggesting lua. I just rewrote transaction code to use lua instead. Had too many issues in worst case scenarios, like fail-over where the transactional code simply stops working properly – Meliorism

Thanks, very nice and simple implemenation, and even better explanation. – Ardenardency

@MarcGravell one more question. if i have a Redis cluster then is it still safe to use this technique? – Okinawa

@KamranShahid yes; both Lua and multi/exec are fine on cluster as long as a: they only impact a single hash-slot (which must be the case if they have a single key), and b: (in the case of Lua specifically) you're using KEYS to pass the keys, not ARGV (it uses KEYS to do the hash-slot routing) – Perquisite

You can check my final logic mentioned in the question for b case – Okinawa

Answer 2

You can use WATCH command - this way, if the value changes, you'll get notified

Ollieollis

Any idea how can i get it's advantage in stackexchange.redis api? – Okinawa

@KamranShahid try smth like github.com/StackExchange/StackExchange.Redis/blob/master/Docs/… – Ollieollis

Thanks Chester. I will try it – Okinawa

Note: this would not be my recommendation; the redis transaction API is hard to get right - Lua would be much simpler in this case (/cc @KamranShahid) – Perquisite

Marc what's mean's by the redis transaction API is hard to get right? Is it buggy or may be problem in cluster aware Redis implementation? (At the moment our implementation is not cluster base) – Okinawa

@KamranShahid neither of those; it is just hard - give me a few minutes and I'll try to write the equivalent code via the transaction / constraint API in my answer – Perquisite

Thanks Marc i will surely try with that one as well and analyze which is more efficient – Okinawa

@KamranShahid added to my answer – Perquisite