6.2.1 Why locks are important

  • Redis in Action – Home
  • Foreword
  • Preface
  • Part 1: Getting Started
  • 1.1.1 Redis compared to other databases and software
  • 1.1.3 Why Redis?
  • 1.3.2 Posting and fetching articles
  • 1.3.3 Grouping articles
  • 2.1 Login and cookie caching
  • 2.2 Shopping carts in Redis
  • 2.3 Web page caching
  • 2.5 Web page analytics
  • 3.1 Strings
  • 3.2 Lists
  • 3.4 Hashes
  • 3.5 Sorted sets
  • 3.7.1 Sorting
  • 3.7.2 Basic Redis transactions
  • 3.7.3 Expiring keys
  • 4.4 Redis transactions
  • 4.7 Summary
  • 5.1 Logging to Redis
  • 5.2 Counters and statistics
  • 5.2.2 Storing statistics in Redis
  • 5.4.1 Using Redis to store configuration information
  • 5.4.2 One Redis server per application component
  • 5.4.3 Automatic Redis connection management
  • 6.1 Autocomplete
  • 6.2 Distributed locking
  • 6.3 Counting semaphores
  • 6.6 Distributing files with Redis
  • 6.2.1 Why locks are important
  • 6.2.2 Simple locks
  • 6.2.3 Building a lock in Redis
  • 6.2.5 Locks with timeouts
  • 6.3.2 Fair semaphores
  • 6.3.4 Preventing race conditions
  • 6.5.1 Single-recipient publish/subscribe replacement
  • 6.5.2 Multiple-recipient publish/subscribe replacement
  • 6.6.2 Sending files
  • 7.1 Searching in Redis
  • 7.2 Sorted Indexes
  • 7.5 Summary
  • 7.1.2 Sorting search results
  • 8.1.1 User information
  • 8.5.1 Data to be streamed
  • 9.2.2 SETs
  • 9.4 Summary
  • Chapter 11: Scripting Redis with Lua
  • 11.1.1 Loading Lua scripts into Redis
  • 11.2 Rewriting locks and semaphores with Lua
  • 11.5 Summary
  • 11.2.1 Why locks in Lua?
  • 11.2.2 Rewriting our lock
  • B.1 Forums for help
  • Buy the paperback
  • Redis in Action – Home
  • Foreword
  • Preface
  • Part 1: Getting Started
  • 1.1.1 Redis compared to other databases and software
  • 1.1.3 Why Redis?
  • 1.3.2 Posting and fetching articles
  • 1.3.3 Grouping articles
  • 2.1 Login and cookie caching
  • 2.2 Shopping carts in Redis
  • 2.3 Web page caching
  • 2.5 Web page analytics
  • 3.1 Strings
  • 3.2 Lists
  • 3.4 Hashes
  • 3.5 Sorted sets
  • 3.7.1 Sorting
  • 3.7.2 Basic Redis transactions
  • 3.7.3 Expiring keys
  • 4.4 Redis transactions
  • 4.7 Summary
  • 5.1 Logging to Redis
  • 5.2 Counters and statistics
  • 5.2.2 Storing statistics in Redis
  • 5.4.1 Using Redis to store configuration information
  • 5.4.2 One Redis server per application component
  • 5.4.3 Automatic Redis connection management
  • 6.1 Autocomplete
  • 6.2 Distributed locking
  • 6.3 Counting semaphores
  • 6.6 Distributing files with Redis
  • 6.2.1 Why locks are important
  • 6.2.2 Simple locks
  • 6.2.3 Building a lock in Redis
  • 6.2.5 Locks with timeouts
  • 6.3.2 Fair semaphores
  • 6.3.4 Preventing race conditions
  • 6.5.1 Single-recipient publish/subscribe replacement
  • 6.5.2 Multiple-recipient publish/subscribe replacement
  • 6.6.2 Sending files
  • 7.1 Searching in Redis
  • 7.2 Sorted Indexes
  • 7.5 Summary
  • 7.1.2 Sorting search results
  • 8.1.1 User information
  • 8.5.1 Data to be streamed
  • 9.2.2 SETs
  • 9.4 Summary
  • Chapter 11: Scripting Redis with Lua
  • 11.1.1 Loading Lua scripts into Redis
  • 11.2 Rewriting locks and semaphores with Lua
  • 11.5 Summary
  • 11.2.1 Why locks in Lua?
  • 11.2.2 Rewriting our lock
  • B.1 Forums for help
  • Buy the paperback

    6.2.1 Why locks are important

    In the first version of our autocomplete, we added and removed items from a LIST. We did so by wrapping our multiple calls with a MULTI/EXEC pair. Looking all the way back to section 4.6, we first introduced WATCH/MULTI/EXEC transactions in the context of an in-game item marketplace. If you remember, the market is structured as a single ZSET, with members being an object and owner ID concatenated, along with the item price as the score. Each user has their own HASH, with columns for user name, currently available funds, and other associated information. Figure 6.2 shows an example of the marketplace, user inventories, and user information.

    You remember that to add an item to the marketplace, we WATCH the seller’s inventory to make sure the item is still available, add the item to the market ZSET, and remove it from the user’s inventory. The core of our earlier list_item() function from section 4.4.2 is shown next.

    Figure 6.2 The structure of our marketplace from section 4.6. There are four items in the market on the left—ItemA, ItemC, ItemE, and ItemG—with prices 35, 48, 60, and 73, and seller IDs of 4, 7, 2, and 3, respectively. In the middle we have two users, Frank and Bill, and their current funds, with their inventories on the right.
    Listing 6.6 The list_item() function from section 4.4.2
    def list_item(conn, itemid, sellerid, price):
       #... 
    
     
                pipe.watch(inv)
    

    Watch for changes to the user’s inventory.

                if not pipe.sismember(inv, itemid):
                   pipe.unwatch()
    

    Verify that the user still has the item to be listed.

                   return None
    
    
     
                pipe.multi()
                pipe.zadd("market:", item, price)
                pipe.srem(inv, itemid)
                pipe.execute()
    

    Actually list the item.

                return True
       #...
    
     

    The short comments in this code just hide a lot of the setup and WATCH/MULTI/EXEC handling that hide the core of what we’re doing, which is why I omitted it here. If you feel like you need to see that code again, feel free to jump back to section 4.4.2 to refresh your memory.

    Now, to review our purchasing of an item, we WATCH the market and the buyer’s HASH. After fetching the buyer’s total funds and the price of the item, we verify that the buyer has enough money. If the buyer has enough money, we transfer money between the accounts, add the item to the buyer’s inventory, and remove the item from the market. If the buyer doesn’t have enough money, we cancel the transaction. If a WATCH error is caused by someone else writing to the market ZSET or the buyer HASH changing, we retry. The following listing shows the core of our earlier purchase_item() function from section 4.4.3.

    Listing 6.7 The purchase_item() function from section 4.4.3
    def purchase_item(conn, buyerid, itemid, sellerid, lprice):
       #...
    
     
                pipe.watch("market:", buyer)
    
    

    Watch for changes to the market and the buyer’s account information.

                price = pipe.zscore("market:", item)
                funds = int(pipe.hget(buyer, 'funds'))
                if price != lprice or price > funds:
                   pipe.unwatch()
    

    Check for a sold/repriced item or insufficient funds.

                   return None
    
    
     
                pipe.multi()
                pipe.hincrby(seller, 'funds', int(price))
                pipe.hincrby(buyerid, 'funds', int(-price))
                pipe.sadd(inventory, itemid)
                pipe.zrem("market:", item)
                pipe.execute()
    

    Transfer funds from the buyer to the seller, and transfer the item to the buyer.

                return True
    
       #...         
    
     

     

    As before, we omit the setup and WATCH/MULTI/EXEC handling to focus on the core of what we’re doing.

    To see the necessity of locks at scale, let’s take a moment to simulate the marketplace in a few different loaded scenarios. We’ll have three different runs: one listing and one buying process, then five listing processes and one buying process, and finally five listing and five buying processes. Table 6.1 shows the result of running this simulation.

    Table 6.1 Performance of a heavily loaded marketplace over 60 seconds
     

    Listed items

    Bought items

    Purchase retries

    Average wait per purchase

    1 lister, 1 buyer

    145,000

    27,000

    80,000

    14ms

    5 listers, 1 buyer

    331,000

    <200

    50,000

    150ms

    5 listers, 5 buyers

    206,000

    <600

    161,000

    498ms

    As our overloaded system pushes its limits, we go from roughly a 3-to-1 ratio of retries per completed sale with one listing and buying process, all the way up to 250 retries for every completed sale. As a result, the latency to complete a sale increases from under 10 milliseconds in the moderately loaded system, all the way up to nearly 500 milliseconds in the overloaded system. This is a perfect example of why WATCH/MULTI/EXEC transactions sometimes don’t scale at load, and it’s caused by the fact that while trying to complete a transaction, we fail and have to retry over and over. Keeping our data correct is important, but so is actually getting work done. To get past this limitation and actually start performing sales at scale, we must make sure that we only list or sell one item in the marketplace at any one time. We do this by using a lock.