EBOOK – REDIS IN ACTION

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

  • Foreword
  • Preface
  • Acknowledgments
  • About this Book
  • About the Cover Illustration
  • Part 1: Getting Started
  • Part 2: Core concepts
  • Part 3: Next steps
  • Appendix A
  • Appendix B
  • Buy the paperback

    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: WATCH, MULTI, 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.