6.1.1 Autocomplete for recent contacts
The purpose of this autocomplete is to keep a list of the most recent users that each player has been in contact with. To increase the social aspect of the game and to allow people to quickly find and remember good players, Fake Game Company is looking to create a contact list for their client to remember the most recent 100 people that each user has chatted with. On the client side, when someone is trying to start a chat, they can start typing the name of the person they want to chat with, and autocomplete will show the list of users whose screen names start with the characters they’ve typed. Figure 6.1 shows an example of this kind of autocompletion.
Because each of the millions of users on the server will have their own list of their most recent 100 contacts, we need to try to minimize memory use, while still offering the ability to quickly add and remove users from the list. Because Redis LISTs keep the order of items consistent, and because LISTs use minimal memory compared to some other structures, we’ll use them to store our autocomplete lists. Unfortunately, LISTs don’t offer enough functionality to actually perform the autocompletion inside Redis, so we’ll perform the actual autocomplete outside of Redis, but inside of Python. This lets us use Redis to store and update these lists using a minimal amount of memory, leaving the relatively easy filtering to Python.
Generally, three operations need to be performed against Redis in order to deal with the recent contacts autocomplete lists. The first operation is to add or update a contact to make them the most recent user contacted. To perform this operation, we need to perform these steps:
- Remove the contact from the list if it exists.
- Add the contact to the beginning of the list.
- Trim the list if it now has more than 100 items.
We can perform these operations with LREM, LPUSH, and LTRIM, in that order. To make
sure that we don’t have any race conditions, we’ll use a MULTI/EXEC transaction
around our commands like I described in chapter 3. The complete function is shown
in this next listing.
As I mentioned, we removed the user from the LIST (if they were present), pushed
the user onto the left side of the LIST; then we trimmed the LIST to ensure that it
didn’t grow beyond our limit.
The second operation that we’ll perform is to remove a contact if the user doesn’t
want to be able to find them anymore. This is a quick LREM call, which can be seen as
The final operation that we need to perform is to fetch the autocomplete list itself to find
the matching users. Again, because we’ll perform the actual autocomplete processing
in Python, we’ll fetch the whole LIST, and then process it in Python, as shown next.
Again, we fetch the entire autocomplete LIST, filter it by whether the name starts with
the necessary prefix, and return the results. This particular operation is simple
enough that we could even push it off to the client if we find that our server is spending
too much time computing it, only requiring a refetch on update.
This autocomplete will work fine for our specific example. It won’t work as well if the
lists grow significantly larger, because to remove an item takes time proportional to the
length of the list. But because we were concerned about space, and have explicitly limited
our lists to 100 users, it’ll be fast enough. If you find yourself in need of much larger
most- or least-recently-used lists, you can use ZSETs with timestamps instead.