How to implement multi-user safe Linear Congruential Generator in Redis?

Question

I use Linear Congruential Generators (http://en.wikipedia.org/wiki/Linear_congruential_generator) to generate IDs exposed to users.

nextID = (a * LastID + c) % m

Now I want to implement LCGs in Redis. Here's the problem: Getting the current ID and generating the next ID outside Redis is not multi-user safe. Redis has 2 commands which can be used for simple counters: INCRBY and INCRBYFLOAT, but unfortunately Redis doesn't support modulo operation natively. At the moment the only way I see is using EVAL command and writing some lua script.

UPDATE1:

Some lua analog of

INCRBY LCG_Value ((LCG_Value*a+c)%m)-LCG_Value

seems to be a neat way to achieve this.

Answer 1

A server-side Lua script is probably the easiest and more efficient way to do it.

Now it can also be done using Redis primitive operations using a multi/exec block. Here it is in pseudo-code:

while not successful:
   WATCH LCG_Value
      $LastID = GET LCG_value
      $NextID = (a*$LastID+c)%m
   MULTI
      SET LCG_value $NextID
   EXEC

Of course, it is less efficient than the following Lua script:

# Set the initial value
SET LCG_value 1

# Execute Lua script with on LCG_value with a, c, and m parameters
EVAL "local last = tonumber(redis.call( 'GET', KEYS[1]));
      local ret = (last*ARGV[1] + ARGV[2])%ARGV[3];
      redis.call('SET',KEYS[1], ret);
      return ret;
" 1 LCG_value 1103515245 12345 2147483648

Note: the whole script execution is atomic. See the EVAL documentation.