Documentation - Redise Pack

A guide to Redise Pack installation, operation and administration

open all | close all

11.4.3 Popping items from the sharded LIST

When popping items from a sharded LIST, we technically don’t need to use Lua. Redis already has everything we need to pop items: WATCHMULTI, and EXEC. But like we’ve seen in other situations, when there’s high contention (which could definitely be the case for a LIST that grows long enough to need sharding), WATCH/MULTI/EXEC transactions may be slow.

To pop items in a nonblocking manner from a sharded LIST in Lua, we only need to find the endmost shard, pop an item (if one is available), and if the resulting LIST shard is empty, adjust the end shard information, as demonstrated in the next listing.

Listing 11.15The Lua script for pushing items onto a sharded LIST
def sharded_lpop(conn, key):
   return sharded_list_pop_lua(
      conn, [key+':', key+':first', key+':last'], ['lpop'])

def sharded_rpop(conn, key):
   return sharded_list_pop_lua(
      conn, [key+':', key+':first', key+':last'], ['rpop'])

sharded_list_pop_lua = script_load('''
local skey = ARGV[1] == 'lpop' and KEYS[2] or KEYS[3]

Get the key for the end we’ll be popping from.

local okey = ARGV[1] ~= 'lpop' and KEYS[2] or KEYS[3]

Get the key for the end we won’t be popping from.

local shard = redis.call('get', skey) or '0'

Get the shard ID that we’ll be popping from.

local ret = redis.call(ARGV[1], KEYS[1]..shard)

Pop from the shard.

if not ret or redis.call('llen', KEYS[1]..shard) == '0' then

If we didn’t get anything because the shard was empty, or we have just made the shard empty, we should clean up our shard endpoint.

   local oshard = redis.call('get', okey) or '0'

Get the shard ID for the end we didn’t pop from.

   if shard == oshard then
      return ret

If both ends of the sharded LIST are the same, then the list is now empty and we’re done.

   end
   local cmd = ARGV[1] == 'lpop' and 'incr' or 'decr'

Determine whether to increment or decrement the shard ID, based on whether we were popping off the left end or right end.

   shard = redis.call(cmd, skey)

Adjust our shard endpoint.

   if not ret then
      ret = redis.call(ARGV[1], KEYS[1]..shard)

If we didn’t get a value before, try again on the new shard.

   end
end
return ret
''')

When popping items from a sharded LIST, we need to remember that if we pop from an empty shard, we don’t know if it’s because the whole sharded LIST is empty or just the shard itself. In this situation, we need to verify that we still have space between the endpoints, in order to know if we can adjust one end or the other. In the situation where just this one shard is empty, we have an opportunity to pop an item from the proper shard, which we do.

The only remaining piece for our promised API is blocking pop operations.