EBOOK – REDIS IN ACTION

This book covers the use of Redis, an in-memory database/data structure server.

open all | close all

11.4.2 Pushing items onto the sharded LIST

It turns out that one of the simplest operations that we’ll perform will be pushing
items onto either end of the sharded LIST. Because of some small semantic changes to
the way that blocking pop operations work in Redis 2.6, we have to do some work to
ensure that we don’t accidentally overflow a shard. I’ll explain when we talk more
about the code.

In order to push items onto either end of a sharded LIST, we must first prepare the
data for sending by breaking it up into chunks. This is because if we’re sending to a
sharded LIST, we may know the total capacity, but we won’t know if any clients are
waiting on a blocking pop from that LIST,1 so we may need to take multiple passes for
large LIST pushes.

After we’ve prepared our data, we pass it on to the underlying Lua script. And in
Lua, we only need to find the first/last shards, and then push the item(s) onto that
LIST until it’s full, returning the number of items that were pushed. The Python and
Lua code to push items onto either end of a sharded LIST is shown in the following
listing.

Listing 11.14Functions for pushing items onto a sharded LIST
def sharded_push_helper(conn, key, *items, **kwargs):
   items = list(items)

Convert our sequence of items into a list.

   total = 0
   while items:

While we still have items to push…

      pushed = sharded_push_lua(conn,
         [key+':', key+':first', key+':last'],

…push items onto the sharded list by calling the Lua script.

         [kwargs['cmd']] + items[:64])

Note that we only push up to 64 items at a time here; you may want to adjust this up or down, depending on your maximum ziplist size.

      total += pushed

Count the number of items that we pushed.

      del items[:pushed]

Remove the items that we’ve already pushed.

   return total

Return the total number of items pushed.

def sharded_lpush(conn, key, *items):
   return sharded_push_helper(conn, key, *items, cmd='lpush')

def sharded_rpush(conn, key, *items):
   return sharded_push_helper(conn, key, *items, cmd='rpush')

Make a call to the sharded_push_helper function with a special argument that tells it to use lpush or rpush.

sharded_push_lua = script_load('''
local max = tonumber(redis.call(
   'config', 'get', 'list-max-ziplist-entries')[2])

Determine the maximum size of a LIST shard.

if #ARGV < 2 or max < 2 then return 0 end

If there’s nothing to push, or if our max ziplist LIST entries is too small, return 0.

local skey = ARGV[1] == 'lpush' and KEYS[2] or KEYS[3]
local shard = redis.call('get', skey) or '0'

Find out whether we’re pushing onto the left or right end of the LIST, and get the correct end shard.

while 1 do
   local current = tonumber(redis.call('llen', KEYS[1]..shard))

Get the current length of that shard.

   local topush = math.min(#ARGV - 1, max - current - 1)

Calculate how many of our current items we can push onto the current LIST shard without going over the limit, saving one entry for later blocking pop purposes.

   if topush > 0 then
      redis.call(ARGV[1], KEYS[1]..shard, unpack(ARGV, 2, topush+1))
      return topush

If we can push some items, then push as many items as we can.

   end
   shard = redis.call(ARGV[1] == 'lpush' and 'decr' or 'incr', skey)

Otherwise, generate a new shard, and try again.

end
''')

As I mentioned before, because we don’t know about whether clients are blocking on
pops, we can’t push all items in a single call, so we choose a modestly sized block of 64
at a time, though you should feel free to adjust it up or down depending on the size of
your maximum ziplist-encoded LIST configuration.

LIMITATIONS TO THIS SHARDED LISTEarlier in this chapter, I mentioned that
in order to properly check keys for sharded databases (like in the future Redis
cluster), we’re supposed to pass all of the keys that will be modified as part of
the KEYS argument to the Redis script. But since the shards we’re supposed to
write to aren’t necessarily known in advance, we can’t do that here. As a
result, this sharded LIST is only able to be contained on a single actual Redis
server, not sharded onto multiple servers.

You’ll notice that for our sharded push, we may loop in order to go to another shard
when the first is full. Because no other commands can execute while the script is executing,
the loop should take at most two passes: one to notice that the initial shard is
full, the second to push items onto the empty shard.

Exercise: Finding the length of a sharded LIST

Now that you can create a sharded LIST, knowing how long your LIST has grown can
be useful, especially if you’re using sharded LISTs for very long task queues. Can
you write a function (with or without Lua) that can return the size of a sharded LIST?

Let’s work on popping items from the LIST next.

1 In earlier versions of Redis, pushing to a LIST with blocking clients waiting on them would cause the item to
be pushed immediately, and subsequent calls to LLEN would tell the length of the LIST after those items had
been sent to the blocking clients. In Redis 2.6, this is no longer the case—the blocking pops are handled after
the current command has completed. In this context, that means that blocking pops are handled after the
current Lua call has finished.