Dive into Redis — the optimal solution for high-performance data retrieval

Published in

SFU Professional Computer Science

14 min readFeb 11, 2022

Haoming Pan, Yukang Liu, Yewin Shu, Zheng Wu, Jie Min

This blog is written and maintained by students in the Master of Science in Professional Computer Science Program at Simon Fraser University as part of their course credit. To learn more about this unique program, please visit {sfu.ca/computing/mpcs}.

1. Introduction

As a developer team, I believe many of our fellow professionals may encounter a situation where we sit in our chairs for an eternity to wait for a response from the database triggered by one of the API requests at the application server with a severely complex calculating process. Indeed, as such situations stack up across the development process, it would eventually tear apart our patience and undermine our working experience. As a result, it is when Redis plays the role of saviour. There are many mechanisms and techniques to resolve this issue. However, before we dive into the solution, we first need to have a big picture of Redis and the database in general.

Redis is considered as a NoSQL database, but it shares no similar points with other major NoSQL databases such as MongoDB and has a completely different structure compared to SQL databases like MySQL, PostgreSQL. MongoDB and other major NoSQL databases are stored in a form of documents, and the SQL database depends heavily on the relational schema, where both structures need to have predefined fields before storing the actual data to the database. In contrast to that, Redis stores everything in the form of a { Key: Value } pairs.

As a result of the special storing feature, it is not so capable of storing large chunks of structured data. Unlike other databases that run on the disk and store everything on the disk, Redis actually runs inside the working memory of RAM(Cache), and the data stored in the cache is usually the information that is retrieved frequently or involves complex computation. Therefore, instead of using Redis as the main storage for the application, most developers tend to classify it as sub storage for the main database.

Facts: According to Stackoverflow.com is considered as 5th most beloved database environment

Left to right Figure 1(document), Figure 2(Key: Value pair), Figure 3(table)

To better understand how Redis optimizes the data retrieval process, consider the below use cases in figure four. Imagine a user made a request for a resource from service on his computer, and the service would retrieve the information from the database. However, the query may take maybe 60 seconds to process, which means the user will wait for at least 60 seconds to receive it. It is obvious that the waiting time is not so user friendly. So, we need to utilize Redis for this scenario.

Observing figure five, instead of directly querying a database, we append a Redis cache instance and make the retrieval process occur directly from the service to Redis. Redis will first check if the desired data exist in the cache. If there is a matching content (Cache hit), then Redis will send it back to the service

All the concise information regarding Redis syntax and Redis data manipulation is stated in their documentation. From the next section, we will start to dive deeper into Redis regarding how they maintain their high performance.

2. Keep Redis high performance

Redis has the ability to reach large number of queries in a small amount of time. However, to further enhance its performance we need to eliminate any potential steps and avoid operation delay to continuously keep its high performance. In this section, we are going to talk about several ways to maintain Redis’s high performance.

A) Avoid storing Bigkeys

It will take a lot of time to allocate memory when we are using Bigkeys in program, because Redis usually processes the requests in a single thread. Similarly, deleting Bigkeys will also take some time to “free memory”.

Moreover, “network data transmission” may cost time when we are reading Bigkeys. The requests are put in a queue and waiting to be executed, which will lower the performance of Redis.

Therefore, the application should try not to store Bigkeys as much as possible to avoid operation delays. Bigkeys can split into multiple small keys for storage if necessary.

B) Enable lazy-free mechanism

Enable Redis’s lazy-free mechanism is another way to avoid storing Bigkeys. After it is enabled, when Redis deletes a Bigkey, releasing memory will be executed in the background thread, which can avoid the impact on the main thread.

C) Pay attention to the commands with the size of N

If too much data is queried at once, it will spend a long time on the network transmission stage, and the time delay will increase. Therefore, for each type of container which includes List, Hash, Set and ZSet, when the number of elements is unknown, we should not execute LRANGE key 0 -1 or HGETALL or SMEMBERS or ZRANGE key 0 –1 directly.

Instead, we should follow these steps: First, query the number of data elements (LLEN/HLEN/SCARD/ZCARD). Then a full load of data can be queried synchronously if the number of elements is small. Otherwise, data should be queried in batches if the number of elements is very large.

D) Using batch commands instead of multiple single commands

When you need to operate on multiple keys at once, you should use batch commands to handle them. The advantage of batch operation is that it can significantly reduce the number of round-trip of networks IOs between the client-side and the server-side when compared to multiple single operations.

Thus, we’d better use MGET/MSET instead of GET/SET in String or Hash, use HMGET and HMSET instead of HGET and HSET, or use Pipeline to send multiple commands to the server for execution at once.

Even though we try to eliminate as many threats as possible that may burden the performance of Redis, there may still be many issues that can be unexpected both internally and externally.

3. Three must known problems in Redis

3.1 Redis cache avalanche problem

Redis cache avalanche is a situation when a significant amount of keys in Redis expires at the same time. In the meanwhile, numerous users are searching the data that have just expired in Redis; In other words, a huge amount of requests hit the database directly and concurrently, which overload the database.

How to solve the Redis cache avalanche problem?

Key pairs setting: Most of the cases for cache avalanche could happen when many key pairs have similar expirations time: In an E-commerce website, limited-time shopping activities start at 11 pm. Accidently, most of the key pairs in Redis would expire at that time. In that case, all the requests would turn to the database for requests. Suppose the application has a high volume of concurrent requests. In that case, the database will be under a lot of pressure, further affecting other normal business request processing in the database. To address this scenario, we should map the expiration to different times to make them evenly distributed. For instance, add random values to the default expiration time when storing some hit data.
Add Latency and Fault Tolerance mechanisms for resilience:
When an estimable Redis cache avalanche is inevitable, we should introduce latency and fault tolerance mechanisms to improve the resilience of the system. This includes service down gradation, rate limitation and circuit-breaker.
Rate Limitation: Rate limitation means that we control the number of requests entering the system at the front end of the request portal of the business system to avoid too many requests being sent to the database. By using request flow limiting, a large number of concurrent requests to the database could be alleviated.
Circuit-Breaker: Circuit-breaker suspends the business application’s interface access to the caching system. To be more specific, when the business application invokes the cache interface, the cache client does not send the request to the Redis cache instance, but returns it directly and waits until the Redis cache instance is back in service before allowing the application request to be sent to the cache system.
Service DownGradation: Service downgrade means that we could simplify some of the microservice requests. The ultimate goal of degradation is to ensure that core services are available.

3.2 Redis cache breakdown

Redis cache breakdown is a situation when the server receives a tremendous amount of requests to the same key. Unfortunately, this key has just expired in Redis. As a consequence, all of the requests hit the database at the same time, which causes the database to break down. The cache breakdown and cache avalanche are similar because they are both caused by the expired key in Redis. However, the most important difference between them is that cache breakdown happens when a key is heavily accessed, and it expires in Redis; on the other hand, cache avalanche happens when lots of keys expire in Redis.

How to solve the Redis cache breakdown problem?

Never expired: The most straightforward solution is to set the heavily-used key never expires in Redis. There are two methods to make the key ‘never expire’. The first method is to set the key to never expire when we created it. The second method is that we build caching by an asynchronous thread at the backend when the key is going to expire. The drawback of this method is that it is hard for developers to find which data will be heavily-accessed in the future.
Mutex lock: The second solution is to add a mutex key to only allow 1 request to come into the database as demonstrated in figure 8. In this case, we can prevent a huge amount of requests from hitting the database. Although this solution solves the problem of the first solution. The drawback of this method is that it is possible to cause a deadlock when the thread that gets the lock dies suddenly. We need to further investigate it to find a better solution.

3.3 Redis cache penetration

Redis cache penetration is a situation when an attacker continuously makes requests to the data that does not exist in the database. For example, the attacker continuously searches the item that ID equals -1 in our database. The database returned empty. Redis would not cache it since the return value from the database is empty. As a result, every search to the item that ID equals -1 hits our database directly, making our database heavy-load or even break down.

How to solve the Redis cache penetration problem?

Cache default value
Once cache penetration has occurred, we can cache a null value or a default value in Redis for the query data. Subsequent requests from the application can then be read directly from Redis and returned to the business application, avoiding the need to send many requests to the database for processing and keeping the database up and running. However, one thing to be noted is that the caching expiration cannot be too long, which could lead to the poor effectiveness of data.
Authentication check
One of the important reasons for cache penetration is that there are a large number of malicious requests accessing non-existent data. Hence, an effective countermeasure is to check the legitimacy of the requests received by the business system at the front end of the request portal and filter out malicious requests (e.g., unreasonable request parameters, illegal request parameters, Non-exist request fields) directly from accessing the back-end cache and database.
Integrate high-performance probabilistic data structure. E.g. BloomFilter, Cuckoo Filter. Bloom filter is an effective probabilistic data structure and it is usually used to examine the existence of a certain element. It is widely used and has an important role in this distributed system era. We would explore more content related to this data structure in the following part.

4. All you need to know for BloomFilter.

4.1 Basics for BloomFilter

In general, BloomFilter can be used to retrieve whether an element is in a collection or not, with better space efficiency and query time compared with the general algorithm. This is because the BloomFilter consists of a bit array with all initial values of 0 and N hash functions that can be used to quickly determine whether a certain data exists. When we want to mark the existence of a certain data (e.g. the data has been written to the database), the BloomFilter will complete the checking by three steps.

First, using N hash functions, we calculate the hash value of this data separately to get N hash values.
Then, we take these N hash values and modulo the length of the bit array to get the corresponding position of each hash value in the array.
Finally, we set the bit of the corresponding position to 1, which completes the operation of marking data in the BloomFilter.

The most important conclusion for BloomFilter is that it can be used to determine that a certain data does not exist in a given set, but cannot be used to determine that a certain data exists in a given set. In other words, when any checked bit is not set, the entry is definitely not in the filter, but when all checked bits are set, the entry might be in the filter. Thus it contains certain false positive probability(FPP)

4.2 Ways to implement the bloom filter

As BloomFilter gains more and more popularity in the real industry, there are different methods to implement the BloomFilter, and in this section, we will introduce two ways to use the BloomFilter.

Implementing the BloomFilter using Guava Library supported by Google Open Source.

2. Implementing the BloomFilter using the RedisBloom.

Starting from Redis v4.0, Redis contains the new functions for using Modules, and BloomFilter is one of the Modules. Source code for RedisBloom: https://github.com/RedisBloom/RedisBloom

To use this redis module, we could directly use Docker to install this extension module for redis.

All the commands could be found here:https://oss.redis.com/redisbloom/Bloom_Commands/

4.3 Typical Scenarios for using the bloom filter:

As mentioned above, in this modern big data era, Bloom Filter is becoming more and more useful in many different scenarios. In this section, we would list several scenarios in that we could use the BloomFilter.

Many databases including Google Bigtable, Apache HBase, Apache Cassandra, and PostgreSQL implement the BloomFilters to check the non-existence row or column to speed up the searching process, since using BloomFilter could ideally decrease the numbers of Disk IO operations.
The BloomFilter is also used in Bitcoin. In the Bitcoin network, there are some lightweight Bitcoin nodes that do not need to save all blocks and transactions, but only the transactions they are interested in. In this way, when a light node synchronizes data to a full node, it does not send a list of all the transactions, but it only sends a BloomFilter calculated through the list of transactions. Further mechanisms could be found in this link. https://eprint.iacr.org/2014/763.pdf
Squid web proxy cache server also implements Bloom filters in its cache digests function. https://wiki.squid-cache.org/SquidFaq/CacheDigests
BloomFilter could be used to check the Daily Active User(DAU) for a system. (the same person logs in multiple times should be counted only ones)
BloomFilter could be used to effectively deduplicate in the scenarios of web-crawling and spam email detection.

4.4 Some improved versions for bloom filter:

Even though BloomFilter holds certain advantages, the drawbacks are also quite obvious. The lack of deletion is one of the most vital problems that would affect the usage of the BloomFilter. Furthermore, as the elements increase, the False Positive also tends to increase correspondingly.

For example, suppose we have an email A, whose results of hashing are in 1, 3, 7, and an email B whose results are 2, 6, 7. Then if we remove the result of email A, then email B would be considered as not existing.

Thus, there are several improved versions for BloomFilter that aim to facilitate the usage of BloomFilter in different scenarios, including the Counting Bloom Filters, Inverse Bloom Filters, and the most widely known improved version — the Cuckoo Filters.

All the improved versions of the bloom filters could be found in this link: https://github.com/tylertreat/BoomFilters

4.5 Cuckoo Filter:

Cuckoos, the birds, like to lay their eggs in other birds’ nests. After the cuckoo chicks are born, they kick out other eggs and “borrow” other bird’s nests to grow up.

a) Cuckoo Hashing:

First, we use two hash functions h1(x), h2(x) and two hash buckets T1, T2.
Insert element x: there are three cases: If one of the hash results in the corresponding two buckets is empty, then just insert; if two buckets are all empty then we could insert in either one; if two of the hash results in the corresponding two buckets are all full, then we could just “kick out” one of the elements(named y) in the bucket and then insert x. Recursively implement the previous job for element y; If there are too many kicks when inserting, then that means the hash bucket is full, and thus we need to rehash the buckets and insert again.
search element x: Directly read the T1[h1(x)], T2[h2(x)] and compare with x.

Cuckoo was initially proposed by Rasmus Pagh and Flemming Friche Rodler, and the basic idea contains three steps;

b) Cuckoo Filter:

In 2014, a paper proposed by researchers in CMU, Harvard and Intel Labs implemented the Cuckoo hashing in a revised Bloom Filter, and named it Cuckoo Filter.

Check the link below:

https://www.eecs.harvard.edu/~michaelm/postscripts/cuckoo-conext2014.pdf

Compared with the traditional Bloom Filter, it contains several advantages:

It supports removing elements.
It maintains a higher query efficiency, especially under high loading factors.
Easier to implement compared with other improved BloomFilters.

To realized the above goal, Cuckoo Filter made several changes to the original Cuckoo Hash:

It increases the number of Hash buckets
It only saves the fingerprint for the key.
It uses the XOR operation in determining the new position of a kicked element.

Conclusion

Redis provides a highly available in-memory storage that tremendously optimizes the overall performance of a service. Since it is an add-on sub storage in most scenarios, it also has the scalability to grow with the service. Moreover, it also implements some of the most advanced algorithms to reinforce the effectiveness of the optimization process. Time is precious for both data engineers and the users, the emergence of Redis would benefit both parties.