redisdistributed-computingdistributeddistributed-system

List increment for redis


Say that I have a list in redis, and a distributed service on top, the idea is for the distributed system to write data into this list, which can then be queried by other hosts.

Given a list like so:

1,2,3,4,1

I want to be able to do operations like increment the first element by 5 and increment the second element by 2 to get the end resulting list of:

6,4,3,4,1

Since the service is distributed, I cannot just grab the list, and then do the computation by the service and then set, as two machines may try to add 1 to the list, but due to them grabbing the same list we will have a race condition.

I also cannot enforce consistent hashing by the upstream, as hotkeys may have high load and lead to data skew, so I need a solution that can be load balanced by round-robin or some other non hash based algorithm by the upstream.

How can I accomplish this with redis?


Solution

  • You can use the following two commands to achieve your goal:

    1. LINDEX: get the value of at the given index.
    2. LSET: set the value at the given index with an increased value.

    In order to make these two commands atomic, so that it works in a distributed env. You can wrap these two commands into a Lua script:

    local key = KEYS[1]
    local index = ARGV[1]
    local incr = ARGV[2]
    
    local val = redis.call('lindex', key, index)
    if not val then return nil end
    
    val = tostring(tonumber(val) + tonumber(incr))
    redis.call('lset', key, index, tonumber(val) + incr)
    
    return val
    

    However, both LINDEX and LSET are slow commands (especially with a long list), i.e. O(N) operation. You might need to redesign your code with a more efficient data structure.