DeadLock and Redis queues

See full PPT presentation

Flow Map

Before explaining the content of the presentation, this post is a summary of only part of the presentation, and I thought it might be difficult to convey the flow through a post alone. So, I would like to first talk about how I organized the content and the overall sequence through the flow map I created while preparing for the actual presentation. The main content is about deadlock issues that have been experienced in practice and what methods exist to solve them. Afterwards, we explained the process of enabling sequential access using redis queues and distributed locks. Before explaining the core solution process, I added an explanation about redis for better understanding. And finally, we talked about comparing the performance of redis queue and distributed lock jmeter and ways to withstand more traffic.

About Deadlock

DeadLock is a deadlock in which two transactions occupy different resources and are waiting to gain possession of the other resource. This refers to a situation in which Transaction 1``` cannot access resource B occupied by Transaction 2, and conversely, Transaction2```` cannot access resource A, resulting in an infinite wait. When deadlock actually occurred, the following error occurred. Looking at the error, you can see that PID 61 ended up as the victim. In other words, it was not reflected properly and ended without the actual reservation being registered.

2023-02-06 11:57:33.526 WARN 3028 --- [o-8080-exec-431] o.h.engine.jdbc.spi.SqlExceptionHelper : SQL Error: 1205, SQLState: 40001
2023-02-06 11:57:33.526 ERROR 3028 --- [o-8080-exec-431] o.h.engine.jdbc.spi.SqlExceptionHelper: Transaction (Process ID 61) was deadlocked on lock | communication buffer resources with another process and has been chosen as the deadlock victim. Rerun the transaction.
2023-02-06 11:57:33.527 ERROR 3028 --- [o-8080-exec-431] h.hsas.service.Exception Controller: ErrorResponse(location=[CannotAcquireLockException]

How to solve deadlock

At the time, I thought a lot about how to solve it, and since I worked for a large company and it was not something I could freely manage with large costs and resources, the solutions were limited. At this point, I started thinking about what I could do. In fact, they are basic but important alternatives that should be considered because they are solutions that can be solved without incurring large costs and learning curves.

Let's look at the basics first.

The implementation logic of the code or the design aspect of the table. Taking a reservation program as an example, there may be domains such as member/administrator, reservation request, review, registration, and other services. Assuming that reservation application is the most core function and can attract a lot of traffic, how is this part implemented when reading or saving from the database? And we need to reexamine how the table is designed. Then you should also double-check database index settings. As a non-clustered index, several columns are grouped together to form one index. In this case, when a lock is simply taken, there is a high possibility that a page lock will be taken rather than a row-by-row lock, which ultimately increases the possibility of deadlock. In Java, there are functions provided for concurrency control, such as synchronized. In other languages, it is a mutex or lock function. Allows methods to be processed one by one sequentially when there are multiple requests. But this synchronization is not enough. This is no problem in a single application environment, but it is difficult to guarantee data consistency in a distributed system environment.

What are some things to consider in terms of transactions?

First, the part applied to solve the deadlock issue above was to match the transaction size and direction. It is necessary to adjust the size unit so that methods with multiple functions are not included in one transaction. By making the transaction unit small, you can reduce the time it takes to lock. And if methods for retrieving data in multiple transactions proceed in the opposite order, deadlocks may occur as they occupy different resources. However, in reality, it is often difficult to solve such a simple problem in complex projects with multiple services. There is also a way to set Lock or isolation level . Simply put, a lock prevents simultaneous access when multiple transactions exist, and the transaction isolation level controls which transaction's changes are visible to other transactions. Spirng JPA provides useful annotations to set locks and isolation levels, and you can also set retries using @Retryable. It is necessary to check how transaction-level query is actually performed. If there are too many joins or too many conditions, the scope of the lock becomes large, which can lead to a deadlock.

What are some things to consider in terms of transactions?

In reality, the parts discussed above can be resolved to some extent in the process of writing and refactoring code, but when considering greater traffic and scalability, it is necessary to think about it in terms of system design. Separation of read/write servers . Since most applications have a high read ratio, you can have a master server like this and have subordinate replica servers handle read requests. This way, you can distribute the load on the database when there is a lot of traffic. There is also a method of caching using in-memory data, which has faster performance. If you look at the look aside method in the Redis caching strategy by having a cache server, it first checks whether there is data in the cache server, and when a cache miss occurs, it looks it up on the disk, updates it on the cache server, and returns it. In other words, there is a performance advantage because data is not retrieved from disk every time. Lastly, there are queues and distributed locks. Queuing is a method of putting work units in a list or queue so that they can proceed sequentially. Distributed locking is a method that allows access to data or resources when a lock is acquired for concurrency control in a distributed system, as shown in the figure.

About Redis

This is information organized by version after looking at Redis Github new features. As of version 7.0, the most notable new spec features include Redis functions, ACLv2, command introspection, and Sharded Pub/Sub.

Redis is a NoSQL, in-memory database. That is why it is important to monitor memory management. Memory is allocated using Jmalloc, and storing data of the same size helps reduce memory fragmentation. Redis supports various data structures such as sorted sets, sets, and hyperloglogs. Because it is an in-memory database, it is volatile. Therefore, Redis provides a replication function to complement this, and can be used in structures such as clusters and sentinels. Additionally, there is a failover function that detects failed nodes and promotes them to master nodes. There is RDB, which provides backup snapshots for data persistence, and AOF function, , which saves Redis commands as log files. Both require disk space, so you'll need to adjust accordingly. Redis is a representative cache server that can be used in distributed systems, and TTL needs to be set efficiently to ensure data freshness and resource saving. It is also used to create queues and distributed locks, using Lua scripts. Instead of sending multiple individual Redis commands over the network, you can run multiple commands at once with a single Lua script. This can reduce network overhead and improve performance.

Redis queue

How to manage sorted sets in redis? In the configuration file, if there are less than 128 entries and the total of all entries is less than 64 bytes, it is saved in a ziplist structure. Even if only one of the two conditions is exceeded, it is saved in a skiplist structure.

First, if you look at the ziplist structure, you can see that entries are stored in a linear structure because they are relatively small. An entry represents a value and score pair.

The skiplist contains header```` and tail, which indicate the beginning and end of the node, and allows you to know the number of nodes and the number of level```` within the node. Each node can know the value and score, and the next node forward within the level within the node. For example, if you are looking for the value of the fourth node, ``element, you can search faster because you jump in large increments at a high level and then find the next node. As a result, when comparing ziplist and skiplist, skiplist is better in terms of time complexity as log n```, but in situations where the entries are small or few and memory management is important, it is better to use ziplist.

Redis spinlocks and distributed locks

Spinlock

Since spinlocks increase the load by continuously looping and attempting to obtain locks, it is recommended to use the sleep function in the loop to provide a period of time. Also, it is recommended to use it in a multi-threaded environment where the lock occupation time is small. In Spring, you can conveniently use lettuce, one of the Redis client libraries, by adding dependencies. If you implement a spin lock with Lettuce, it does not provide a function to repeat over a certain period of time in the process of acquiring the lock, so you must implement a part that loops and checks whether the lock can be acquired.

public boolean acquireLettuceSpinLock(String lockKey, long timeout, long startTime) throws InterruptedException {
boolean locked = redisTemplate.opsForValue().setIfAbsent(lockKey, "locked", timeout, TimeUnit.MILLISECONDS);
while (!locked && System.currentTimeMillis() - startTime < timeout) {
Thread.sleep(50);
}
if (!locked && System.currentTimeMillis() - startTime >= timeout) {
return false;
}
return locked;
}
public void releaseLock(String lockKey) {
redisTemplate.delete(lockKey);
}

On the other hand, in redisson spinlock, an RLock object can be obtained with getSpinLock, and the difference is that a spinlock can be implemented with only timeout and unit settings without separately implementing a repetition statement with tryLock.

redisson.getSpinLock(lockKey).tryLock(timeout, timeUnit);
/**
* Returns Spin lock instance by name.
* <p>
* Implements a <b>non-fair</b> locking so doesn't guarantees an acquire order by threads.
* <p>
* Lock doesn't use a pub/sub mechanism
*
* @param name - name of object
* @return Lock object
*/
RLock getSpinLock(String name);

Distributed lock

Distributed locks When multiple users or threads access shared data or resources in a distributed environment, a lock must be acquired to access the database. The difference is that pessimistic locks are used to control the concurrency of data within a single server or process, while distributed locks are used to control the concurrency of shared resources among multiple servers or processes.

redisson.getLock(lockKey).tryLock(timeout, timeUnit);
<T> RFuture<T> tryLockInnerAsync(long waitTime, long leaseTime, TimeUnit unit, long threadId, RedisStrictCommand<T> command) {
return evalWriteAsync(getRawName(), LongCodec.INSTANCE, command,
"if (redis.call('exists', KEYS[1]) == 0) then " +
"redis.call('hincrby', KEYS[1], ARGV[2], 1); " +
"redis.call('pexpire', KEYS[1], ARGV[1]); " +
"return nil; " +
"end; " +
"if (redis.call('hexists', KEYS[1], ARGV[2]) == 1) then " +
"redis.call('hincrby', KEYS[1], ARGV[2], 1); " +
"redis.call('pexpire', KEYS[1], ARGV[1]); " +
"return nil; " +
"end; " +
"return redis.call('pttl', KEYS[1]);",
Collections.singletonList(getRawName()), unit.toMillis(leaseTime), getLockName(threadId));
}

When implementing distributed locking with redission, you can implement it using the getLock() method. If you use the tryLock() method instead of simply using the lock() method to acquire a lock, instead of throwing an error when you fail to acquire the lock, you will retry. In fact, this Lua script is received as a class called redis excutor and processed in redis.

Performance testing and consideration of measures to resolve large volume traffic

We conducted a performance test with Jmeter, and when we assumed that the number of concurrent users was 10 times the event target, we confirmed that 100 pieces of data were received according to the limit in redis lettuce spin lock, redisson spin lock, and redisson distributed lock. However, it was found that general pessimistic and optimistic locking alone was insufficient for concurrency control.

When the number of concurrent users is 100,000, you can see that a thread bottleneck occurs. Still, we were able to confirm that consistency was maintained with only 100 pieces of data coming in. But as traffic increased, issues with distributed locks also arose. When pinging to check the connection to the Redis server, a pong response should have been received, but the problem occurred because the server did not operate properly. This is because all traffic was focused on a single point: Redis.

org.apache.http.conn.HttpHostConnectException: Connect to localhost:8080 [localhost/127.0.0.1, localhost/0:0:0:0:0:0:0:1] failed: Connection refused: connect at org.apache.http.impl.conn.DefaultHttpClientConnectionOperator.connect(DefaultHttpClientConnectionOperator.java:156) at org.apache.jmeter.protocol.http.sampler.HTTPHC4Impl$JMeterDefaultHttpClientConnectionOperator.connect(HTTPHC4Impl.java:409) at org.apache.http.impl.conn.PoolingHttpClientConnectionManager.connect(PoolingHttpClientConnectionManager.java:376) at
org.redisson.client.RedisTimeoutException: Command execution timeout for command: (PING), params: [], Redis client: [addr=redis://localhost:6379]
at org.redisson.client.RedisConnection.lambda$async$0(RedisConnection.java:244) ~[redisson-3.18.0.jar:3.18.0]
at io.netty.util.HashedWheelTimer$HashedWheelTimeout.run(HashedWheelTimer.java:715) ~[netty-common-4.1.94.Final.jar:4.1.94.Final]
at io.netty.util.concurrent.ImmediateExecutor.execute(ImmediateExecutor.java:34) ~[netty-common-4.1.94.Final.jar:4.1.94.Final]

So how can we solve the limitations of distributed locks?

The Redis structure, which has become a single point of failure, can be handled by changing it to a cluster or sentinel. Management is required by checking in advance through memory monitoring, log levels, etc. and receiving notifications of issues to be aware of. You might consider setting a timeout to reduce the waiting time to obtain a distributed lock. If service size or cost support is available, using an event broker may be an alternative.