concept LIST in category redis
This is an excerpt from Manning's book Redis in Action.
In the world of key-value stores, Redis is unique in that it supports a linked-list structure. LISTs in Redis store an ordered sequence of strings, and like STRINGs, I represent figures of LISTs as a labeled box with list items inside. An example of a LIST can be seen in figure 1.2.
Figure 1.2. An example of a LIST with three items under the key, list-key. Note that item can be in the list more than once.
The operations that can be performed on LISTs are typical of what we find in almost any programming language. We can push items to the front and the back of the LIST with LPUSH/RPUSH; we can pop items from the front and back of the list with LPOP/RPOP; we can fetch an item at a given position with LINDEX; and we can fetch a range of items with LRANGE. Let’s continue our Redis client interactions by following along with interactions on LISTs, as shown in listing 1.2. Table 1.4 gives a brief description of the commands we can use on lists.
Table 1.4. Commands used on LIST values
Command
What it does
RPUSH Pushes the value onto the right end of the list LRANGE Fetches a range of values from the list LINDEX Fetches an item at a given position in the list LPOP Pops the value from the left end of the list and returns it Even if that was all that we could do with LISTs, Redis would already be a useful platform for solving a variety of problems. But we can also remove items, insert items in the middle, trim the list to be a particular size (discarding items from one or both ends), and more. We’ll talk about many of those commands in chapter 3, but for now let’s keep going to see what SETs can offer us.
In this chapter, we’ll start by discussing some of the advantages of Lua over performing operations on the client, showing an example from the social network in chapter 8. We’ll then go through two problems from chapters 4 and 6 to show examples where using Lua can remove the need for WATCH/MULTI/EXEC transactions. Later, we’ll revisit our locks and semaphores from chapter 6 to show how they can be implemented using Lua for fair multiple client access and higher performance. Finally, we’ll build a sharded LIST using Lua that supports many (but not all) standard LIST command equivalents.
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.
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.
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.
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 LIST
Earlier 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.
