e-Book - 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

    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.

    Figure 6.1A recent contacts autocomplete
    showing users with names starting with je

    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:

    1. Remove the contact from the list if it exists.
    2. Add the contact to the beginning of the list.
    3. 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.

    Listing 6.1The add_update_contact() function
    def add_update_contact(conn, user, contact):
       ac_list = 'recent:' + user
    
       pipeline = conn.pipeline(True)
    

    Set up the atomic operation.

       pipeline.lrem(ac_list, contact)  
    

    Remove the contact from the list if it exists.

       pipeline.lpush(ac_list, contact)
    

    Push the item onto the front of the list.

       pipeline.ltrim(ac_list, 0, 99)
    

    Remove anything beyond the 100th item.

       pipeline.execute()
    

    Actually execute everything.

    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
    follows:

    def remove_contact(conn, user, contact):
       conn.lrem('recent:' + user, contact)
    

    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.

    Listing 6.2The fetch_autocomplete_list() function
    def fetch_autocomplete_list(conn, user, prefix):
    
       candidates = conn.lrange('recent:' + user, 0, -1)
    

    Fetch the autocomplete list.

       matches = []
    
       for candidate in candidates:
          if candidate.lower().startswith(prefix):
    

    Check each candidate.

             matches.append(candidate)
    

    We found a match.

       return matches
    

    Return all of the matches.

    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.