07 Strong Consistency Lock How to Solve the Contention Issues in High Concurrency Systems

07 Strong Consistency Lock How to Solve the Contention Issues in High Concurrency Systems #

Hello, I am Xu Changlong.

In this lesson, I will give you a detailed explanation of the case of inventory contention in high concurrency. I believe many people have seen relevant materials, but in the practical process, there are still situations where specific implementations cannot meet the requirements, such as some implementations not being able to handle multiple inventory purchases within a second, slow performance in adding inventory operations, or slow performance when inventory is depleted, and so on.

This is because different requirements have different specific implementations for inventory contention. We need to dig deeper and understand the characteristics and applicable scenarios of various locks in order to make flexible adjustments based on different business needs.

Since the scenario of inventory contention in a flash sale is a very classic application scenario, I will now show you how to achieve inventory contention in high concurrency by combining it with the flash sale requirement. I believe that through this process, you will have a deeper understanding of locks.

Mistakes in Lock Contention #

Before introducing the specific solution for inventory contention, let’s first understand a little knowledge - concurrent inventory locks. I remember when I was studying computer science, my teacher demonstrated a piece of code:

public class ThreadCounter {
    private static int count = 0;
    
    public static void main(String[] args) throws Exception {
        Runnable task = new Runnable() {
            public void run() {
                for (int i = 0; i < 1000; ++i) {
                    count += 1;
                }
            }
        };
        
        Thread t1 = new Thread(task);
        t1.start();
        
        Thread t2 = new Thread(task);
        t2.start();
        
        t1.join();
        t2.join();
        
        cout << "count = " << count << endl;
    }
}

Based on the code, we expect the result to be 2000 when executed, but it is not the case. Why is that?

When multiple threads concurrently read and write to the same public variable without mutual exclusion, the sets from multiple threads may overlap or read operations might read data that other threads have only written halfway, leading to data corruption. In other words, in order to ensure the accuracy of a variable in a multi-threaded concurrent situation, the variable should not be modified or read by other threads during the modification process.

For this situation, we generally use locks or atomic operations to protect the inventory variable:

If it is a simple int type data, we can use atomic operations to ensure data accuracy.
If it is a complex data structure or involves multiple steps, we can use locks to ensure data integrity.

Here, I have attached a reference material about several types of locks. If you are interested, you can delve deeper into it.

Considering our previous habits, to help you better understand contention, here is another example of a common mistake we often make. Because the inventory deduction operation requires attention to atomicity, we often encounter the following approach in practice:

redis> get prod_1475_stock_1
15
redis> set prod_1475_stock_1 14
OK

That is, first retrieve the variable from the cache, perform the -1 operation on it, and then put it back into the cache. This is a wrong approach.

As shown in the figure above, the reason is, when multiple threads read at the same time, they all read 5, so when setting it back, they all become 6. In practice, each thread has obtained the inventory, but the actual value of the inventory has not changed cumulatively, resulting in overselling of inventory. If you need to use this approach, it is generally recommended to add a spin mutex lock to exclude other threads from doing similar operations.

However, lock operations greatly affect performance, so before discussing lock methods, let me introduce you to a few relatively lightweight approaches.

Atomic Operations #

In scenarios where high-concurrency modifications are required, using a mutex lock to prevent variables from being incorrectly overwritten is very inefficient. Letting ten thousand users compete for a lock and queue up to modify a variable stored in a process of a single server is a very bad design.

This is because locks require spinning and waiting during acquisition, which requires multiple attempts before successfully acquiring the lock. Moreover, the more threads involved in contention, the worse the situation becomes. The communication process and spinning waiting during this period can easily cause system instability due to resource consumption. In this case, I will store the inventory in a separate and high-performance memory caching service called Redis. This centralized management of inventory can reduce the competition between users for inventory, which can cause other services to become unstable. Additionally, it improves response speed, which is a common practice for protecting inventory in the internet industry.

At the same time, I do not recommend using row locks in the database to ensure inventory modifications. Database resources are precious, and using row locks to manage inventory would result in poor and unstable performance.

As mentioned earlier, when a large number of users concurrently modify a variable, only locks can ensure the correctness of the modifications. However, lock contention has poor performance. So how can we reduce the lock granularity and minimize lock contention?

As shown in the above image, we can actually split the inventory of a popular product and store it in multiple keys. This can greatly reduce lock contention.

For example, if the current product inventory is 100, we can split it into 10 keys and store them in different Redis instances. Each key can store 10 product inventory counts. When a user places an order, one key can be randomly selected to decrement the inventory. If there is no inventory, the current key can be recorded, and the remaining 9 keys can be randomly chosen until 1 inventory count is successfully decremented.

Apart from this method, I personally recommend using Redis atomic operations. Atomic operations have a smaller granularity and are implemented as high-performance single-threaded operations, allowing for globally unique decision-making. Many atomic operations are implemented at the hardware level with excellent performance, such as the example below:

redis> decr prod_1475_stock_1
14

Operations like incr and decr are atomic. We can determine whether inventory has been successfully decremented by checking whether the return value is greater than 0. However, you should note that if the current value has already become negative, we need to consider compensating for the previously decremented inventory. To minimize modification operations, we can perform a value check before decrementing. The overall operation is as follows:

// Read current inventory and check if it is greater than 0
// If greater than 0, continue the operation; otherwise, reject subsequent operations
redis> get prod_1475_stock_1
1

// Begin decrementing inventory. If the return value is greater than or equal to 0, it means the decrement was successful; if it is less than 0, it means there is no inventory
// In this example, we can see that it returns -2. This can be understood as two threads simultaneously attempting to decrement the inventory and neither of them obtaining it
redis> decr prod_1475_stock_1
-2

// Decrement failed. Compensate for the over-decremented inventory
// This returns 0 because both threads are compensating, resulting in a final restoration of 0 inventory
redis> incr prod_1475_stock
0

This seems like a good inventory protection plan, but it also has its drawbacks, as you may have guessed. The accuracy of the inventory depends on whether our business can return the deducted values before the operation is interrupted. If the “return” operation is interrupted during service runtime, manual repair would be difficult because we wouldn’t know how much inventory is still in transit. We would have to wait for all the processes to end after the event to see the remaining inventory.

If we want to completely guarantee no loss of inventory, we usually use transactions and rollbacks for protection. However, the external inventory service Redis falls outside the scope of database caching, and all of this needs to be ensured through manual code. This requires us to handle inventory issues every time we encounter a failure in our business.

Therefore, in many common flash sale systems, the inventory is not returned when a failure occurs, not because we don’t want to, but because many unexpected scenarios cannot be handled.

Speaking of locks, you might think of using the Setnx command or database CAS to implement mutual-exclusive locks and solve the inventory problem. However, this lock involves spinning and blocking while waiting, and when there is high concurrency, the user service needs to try multiple times in a loop to successfully obtain the lock. This wastes system resources and puts heavy pressure on data services. It is not recommended to do it this way (here is a reference for lock performance comparison).

Token Inventory #

In addition to using numerical values to record inventory, there is also a more scientific way called the “token” method, which can avoid negative inventory caused by inventory grabbing.

Specifically, we use a list in Redis to save multiple tokens to represent the inventory. Each token represents one inventory, and the user who grabs the inventory and gets a token can continue with the payment:

// Put in three inventories
redis> lpush prod_1475_stock_queue_1 stock_1
redis> lpush prod_1475_stock_queue_1 stock_2
redis> lpush prod_1475_stock_queue_1 stock_3

// Take out one, if it doesn't return after 0.5 seconds, then grabbing the inventory fails
redis> brpop prod_1475_stock_queue_1 0.5

When there is no inventory left, the user will only get nil. Of course, this implementation only solves the problem of not compensating for inventory after a failed inventory grab. If our error handling in the business code is not perfect, we may still lose inventory.

At the same time, we should note that brpop can take out a token from the “right side” of the list queue. If we don’t need to block and wait, using rpop will have better performance.

However, when we have thousands of inventories, it may not be suitable to use the token method because we need to push 10,000 tokens into the list to work properly and represent the inventory. If there are 100,000 inventories, we would need to continuously insert 100,000 strings into the list, which can cause Redis to experience a large amount of lag during the insertion process.

So far, the inventory design seems perfect, but please consider this: if the product side requests “grabbing multiple inventories for one product”, meaning multiple units of the same product (such as grabbing two bags of rice) in one flash sale, can we still satisfy this requirement using multiple locks to reduce lock contention?

Multiple Inventory Flash Sale #

In fact, this situation often occurs and gives us more ideas for optimization. For grabbing multiple inventories in one flash sale, we need to make some adjustments to our design.

Previously, in order to reduce lock conflicts, we divided the inventory into 10 random keys. Let’s imagine a scenario where there are only a few items left in the inventory. In an extreme case, if we want to buy three items (as shown above), we would need to try all the inventory keys. After trying 10 keys, we finally managed to get only two items in stock. Now, the question is whether we should reject the user’s order or return the stock.

This actually depends on the product design. We also need to add a check: if the product is sold out, there is no need to try 10 inventory keys anymore, as making 10 requests to Redis in one go would put a lot of pressure on Redis’s service (Redis’s O(1) command performance can theoretically reach 100,000 OPS. If we make 10 requests in one go, then ideally the performance of the stock purchase interface would be 10,000 QPS. After load testing, it is suggested to apply 70% funnel-based rate limiting based on the actual performance).

By now, you probably noticed that in the scenario where “one product can be purchased multiple times”, dividing the inventory did not reduce the number of lock conflicts and actually increased the difficulty of maintenance. As the stock becomes less and less, the performance of the later stage of the purchase process becomes poorer. This design no longer meets our original intention (in many cases, our underlying design may not be suitable due to business requirements, so we need to dig deeper into the specific product requirements at the beginning of the design).

So what should we do? We can combine the 10 keys into 1 key and use rpop to deduct multiple stocks. However, if the stock is not enough for three items, we still need the product team to provide advice on whether to continue the transaction. At the beginning, we can use the LLEN (O(1)) command to check if we have enough stock in our list to be popped using rpop. The following is the final design discussed this time:

// Check if the stock is empty before taking it (llen O(1))
redis> llen prod_1475_stock_queue
3

// Take out 3 stocks, but only managed to get 2
redis> rpop prod_1475_stock_queue 3
"stock_1"
"stock_2"

// The product team says the quantity is not enough and does not allow the transaction to continue,
// so we put the stocks back
redis> lpush prod_1475_stock_queue stock_1
redis> lpush prod_1475_stock_queue stock_2

With this design, we have greatly reduced the lock conflict pressure on the ordering system. Redis is known for being a high-performance caching service, and with long connections and multi-threaded load testing, Redis 5.0 can achieve 100,000 OPS, and the network performance of Redis 6.0 is even better.

This method of using Redis atomic operations to reduce lock conflicts is universal and simple for various programming languages. However, be careful not to mix Redis service with complex business logic, as it will affect the efficiency of our stock interface.

Spin Mutual Timeout Lock #

If we need to operate multiple decision keys to complete the stock competition, the atomic method mentioned above is not suitable. This is because the atomic operation is too fine-grained to achieve transactional ACID for multiple data.

For this type of multi-step operation, it is suitable to use spin mutual lock. However, this method is not recommended when there is high traffic, because it relies on the logic code to loop multiple times until the lock is obtained in order to ensure a good user experience. Here is an example:

// The business logic needs to loop and try to acquire the lock, for example, loop 10 times, sleep for 10ms each time,
// and return failure to the user after 10 failed attempts
// After acquiring the lock, set a timeout to prevent issues caused by process crashes and not releasing the lock
// If the lock acquisition fails, it will return nil
redis> set prod_1475_stock_lock EX 60 NX
OK

// Successfully acquired the lock, deduct the stock
redis> rpop prod_1475_stock_queue 1
"stock_1"

// Deduct the numeric stock for display purposes
redis> decr prod_1475_stock_1
3

// Release the lock
redis> del prod_1475_stock_lock

The drawback of this method is that if there are more threads competing for the lock, the waiting time will be longer. Furthermore, due to multiple threads checking in a loop during high concurrency, Redis will be under a lot of pressure. If there are 100 customers placing orders, there will be 100 threads checking every 10ms, resulting in 10,000 operations on Redis.

CAS Optimistic Lock: Lock Operation Postponed #

In addition to the methods mentioned above, let me recommend another implementation: CAS optimistic lock. Compared to spin mutual locks, this method is more efficient when there are fewer concurrent threads competing for stocks. Usually, the way we use locks is to acquire the lock first and then perform operations on the data. This method requires acquiring the lock before proceeding, and acquiring the lock incurs performance overhead, even if there are no other threads competing for the lock.

The core implementation of CAS optimistic lock is to record or monitor the current inventory information or version number and perform pre-operations on the data.

As shown in the image above, if the monitored value changes during the operation, we roll back the previous operations. If there are no changes during the operation, we commit the completion of the transaction. All actions during the operation are treated as a transaction.

// Start the transaction
redis> multi
OK

// Watch the modified value
// If any other thread modifies it during the `exec` phase, it will automatically fail and roll back if necessary

I hope the provided drafts are helpful. Let me know if you need any further assistance.

redis> watch prod_1475_stock_queue prod_1475_stock_1
    
// Perform operations on data within a transaction
redis> rpop prod_1475_stock_queue 1
QUEUED
    
// Step 2
redis> decr prod_1475_stock_1
QUEUED
    
// Execute all previous operations
// If the value of 'watch' changes during 'multi', it will be rolled back
redis> exec
3

As you can see, with this method, we can quickly reduce inventory in batches and greatly reduce the time spent on lock contention. As we mentioned earlier, this method is very efficient when there are few competing threads, but when there are many competing threads, a large number of retries may be required. Nonetheless, even in such cases, the CAS optimistic lock will still perform better than locks implemented with spinning.

When using this method, I recommend keeping the number of operations within the transaction as small as possible. Also, please note that **when Redis is in Cluster mode, 'multi' must be executed within a single slot in order to ensure atomicity**.

### Redis Lua Implementation for Redis Locks

Another way to implement multiple-step inventory operations is by using Redis Lua scripts. Since **all operations within a Lua script are sequential**, they are not interrupted by other operations, so there is no lock contention.

Additionally, Lua scripts can be customized for different scenarios, and the application only needs to execute the specified Lua script with the necessary parameters to achieve high-performance inventory reduction. This can greatly reduce the waiting time for multiple requests from the application.

To demonstrate how to execute a Lua script, I will use PHP:

```php
<?php
$script = <<<EOF
// Get the current inventory count
local stock=tonumber(redis.call('GET',KEYS[1])); 
// Return -1 if not found
if stock==nil 
then 
    return -1; 
end 
// Reduce the inventory count
local result=stock-ARGV[1]; 
// Return 0 if the count falls below the specified value
if result<0 
then 
    return 0; 
else 
    // If the count remains above 0 after reduction, update the result in Redis and return 1
    redis.call('SET',KEYS[1],result); 
    return 1; 
end
EOF;

$redis = new \Redis();
$redis->connect('127.0.0.1', 6379);
$result = $redis->eval($script, array("prod_stock", 3), 1);
echo $result;

With this method, we can perform various sequential operations remotely and implement actions such as replenishing stock.

### Summary

In this lesson, we explored six different approaches using Redis features to solve the problem of lock contention for inventory. Each approach has its own advantages and drawbacks.

![](../images/118be054c09f4c45b2cc384ee004c6ba.jpg)- These methods can be combined and used based on the requirements of the application.

While it is possible to implement locking and inventory reduction using code, such as through local CAS optimistic locks, in general, code developed by ourselves tends to become complex and hard to control due to the mix of business logic and other factors. In contrast, Redis, being a standalone deployment, has better system resources to quickly solve lock contention issues.

You may have noticed that most of the solutions discussed in this lesson involve only one level of "locking", despite the fact that many real-world scenarios involve multiple levels of locks. This is not because I want to neglect the topic, but rather because I strongly discourage multiple layers of locks and lock re-entry due to the difficulty of maintaining such a system. A fine-grained lock can address the majority of problems, so why complicate matters unnecessarily?

### Questions for Consideration

1. Please think about how to reduce the issue of slow response times after reducing inventory to 0 by using atomic operations and splitting inventory.

2. This lesson covers not only inventory management, but also a variety of lock usage scenarios. Please share some clever designs you have come across in practice that are not easily noticed.

Feel free to discuss and exchange ideas in the comments section. See you in the next lesson!