23 Cache Design a Cache Can Either Add Luster or Bring Disaster

23 Cache Design A Cache Can Either Add Luster or Bring Disaster #

Today, I would like to discuss cache from a design perspective.

Usually, we use faster media (such as memory) as a cache to solve the problem of slow data retrieval from slower media (such as disks). Cache is an architectural design pattern that trades space for time to solve performance issues. More importantly, the data stored on disks is usually raw data, while the data saved in cache can be presentation-oriented. In this way, cache not only speeds up I/O but also reduces the computational work on raw data.

In addition, cache systems are generally designed to be simple and have relatively single functionality. Therefore, cache systems like Redis can achieve throughput several times or even dozens of times that of relational databases. Thus, cache is particularly suitable for high-concurrency scenarios in internet applications.

Although using Redis as a cache is simple and convenient, cache usage and design are not as simple as just setting it up. We need to pay attention to issues such as cache synchronization, cache avalanche, concurrency, and cache penetration. Today, let’s discuss these in detail.

Don’t Use Redis as a Database #

Usually, we use distributed caching databases such as Redis to cache data. However, it is important not to use Redis as a database. I have seen many cases where the data in Redis disappeared, causing errors in business logic, and because the original data was not retained, the business could not be recovered.

Redis does have data persistence capabilities, which can ensure that the data is not lost after service restart. This easily leads us to mistakenly believe that Redis can be used as a high-performance key-value database.

In fact, Redis (the free version) is essentially an in-memory database, where all data is stored in memory and handled directly by reading and writing data from memory. It also has data persistence capabilities. Therefore, Redis is characterized by fast request processing but cannot store data larger than the memory size.

Note: Although VM mode can store data larger than the memory size, it has been deprecated since version 2.6 due to performance reasons. In addition, Redis Enterprise edition provides Redis on Flash, which allows storing the key, dictionary, and hot data in memory while storing cold data on an SSD.

Therefore, when using Redis as a cache, we need to pay attention to two points.

First, from the client’s perspective, the characteristic of cached data must be that it has an original data source and is allowed to be lost. Even if the cache time is set to 1 minute, if the cache data disappears for some reason at 30 seconds, we should be able to accept it. After the data is lost, we need to reload the data from the original source. We cannot assume that the cache system is absolutely reliable, and we cannot assume that the cache system will not delete data that has not expired.

Second, from the perspective of the Redis server, the amount of data that the cache system can store must be smaller than the original data. First, we should limit the memory usage of Redis by setting the maxmemory parameter. Secondly, we should clearly determine which algorithm Redis should use to evict data based on the characteristics of the data.

From the Redis documentation, we can see that commonly used data eviction strategies include:

  • allkeys-lru: Delete the least recently used key among all keys.
  • volatile-lru: Delete the least recently used key among keys with an expiration time.
  • volatile-ttl: Delete the key that is about to expire first (based on the TTL value) among keys with an expiration time.
  • allkeys-lfu (Redis 4.0 and above): Delete the least frequently used key among all keys.
  • volatile-lfu (Redis 4.0 and above): Delete the least frequently used key among keys with an expiration time.

These algorithms are combinations of Key range and Key selection algorithms, where the range can be allkeys or volatile, and the algorithms can be LRU, TTL, or LFU. Next, I will explain how to choose the appropriate eviction algorithm from the perspectives of Key range and algorithm.

Firstly, from the algorithm perspective, LFU introduced in Redis 4.0 or later is more “practical” than LRU. Consider a scenario where a key is accessed once a day, but happened to be accessed a second ago. In this case, LRU may not choose to evict this key first, but may evict a key that is accessed every 5 seconds but has not been accessed in the past 2 seconds. LFU algorithm does not have this issue. TTL is simpler; it prioritizes deleting keys that are about to expire but may delete keys that are accessed frequently.

Secondly, from the Key range perspective, allkeys ensures that even keys without TTL can be freed. If the cache expiration time is always “forgotten” by the client when using Redis, then consider using this series of algorithms. volatile is more cautious. In case the client mistakenly uses Redis as a long-term cache, initializing the cache only once at startup, once this kind of data without TTL is deleted, the client may encounter errors.

Therefore, both users and administrators need to consider how Redis should be used. Users need to consider using Redis in a caching manner. Administrators should set memory limits for Redis and choose appropriate eviction strategies to avoid OOM errors.

Pay Attention to the Cache Avalanche Problem #

Because the IOPS (Input/Output Operations Per Second) of the cache system is much higher than that of the database, it is necessary to be cautious about the situation where a large number of caches expire within a short period of time. Once this happens, a large amount of data may need to be retrieved from the database, which puts tremendous pressure on the database and can even lead to a crash of the backend database. This is what we commonly refer to as cache invalidation or cache avalanche.

Broadly speaking, there are two reasons for cache avalanche:

The first reason is that the cache system itself is unavailable, resulting in a large number of requests being directly retrieved from the database.

The second reason is that a large number of keys expire at the same time due to the design of the application, resulting in a large amount of data retrieval from the database.

The first reason mainly involves the high availability configuration of the cache system itself, which is not a cache design issue. Therefore, today I will mainly talk about how to ensure that a large number of keys do not expire at the same time.

When the program is initialized, 1000 pieces of city data are put into the Redis cache with an expiration time of 30 seconds. After the data expires, it is retrieved from the database and written back into the cache. After each data retrieval from the database, the counter is incremented by 1. At the same time, a timer thread is started when the program starts, which outputs the value of the counter every second and resets the counter.

To test an interface that randomly queries city information and observe the QPS (Queries Per Second) of the database:

@Autowired

private StringRedisTemplate stringRedisTemplate;

private AtomicInteger atomicInteger = new AtomicInteger();

@PostConstruct

public void wrongInit() {

    // Initialize 1000 pieces of city data into Redis, with an expiration time of 30 seconds for all cached data

    IntStream.rangeClosed(1, 1000).forEach(i -> stringRedisTemplate.opsForValue().set("city" + i, getCityFromDb(i), 30, TimeUnit.SECONDS));

    log.info("Cache init finished");

    
    // Every second, output the QPS of database access
    
    Executors.newSingleThreadScheduledExecutor().scheduleAtFixedRate(() -> {

        log.info("DB QPS : {}", atomicInteger.getAndSet(0));

    }, 0, 1, TimeUnit.SECONDS);

}

@GetMapping("city")

public String city() {

    // Randomly query a city

    int id = ThreadLocalRandom.current().nextInt(1000) + 1;

    String key = "city" + id;

    String data = stringRedisTemplate.opsForValue().get(key);

    if (data == null) {

        // Retrieve from the database

        data = getCityFromDb(id);

        if (!StringUtils.isEmpty(data))

            // Cache expires in 30 seconds

            stringRedisTemplate.opsForValue().set(key, data, 30, TimeUnit.SECONDS);

    }

    return data;

}

private String getCityFromDb(int cityId) {

    // Simulate database query, increment counter by one for each query

    atomicInteger.incrementAndGet();

    return "citydata" + System.currentTimeMillis();

}

Use the “wrk” tool to test the “city” interface with 10 threads and 10 connections:

wrk -c10 -t10 -d 100s http://localhost:45678/cacheinvalid/city

After starting the program for 30 seconds, when the cache expires, the QPS of database retrievals reaches over 700:

img

There are two ways to solve the problem of cache keys expiring simultaneously and causing a significant increase in database pressure. Solution 1: Differentiated caching expiration time to avoid a large number of keys expiring at the same time. For example, when initializing the cache, set the expiration time of the cache to be within 30 seconds + a random delay of up to 10 seconds (perturbation value). This way, these keys will not expire at the same moment of 30 seconds, but will be spread out between 30 and 40 seconds:

@PostConstruct
public void rightInit1() {
    // Set the expiration time of the cache to be within 30 seconds + a random delay of up to 10 seconds
    IntStream.rangeClosed(1, 1000).forEach(i -> stringRedisTemplate.opsForValue().set("city" + i, getCityFromDb(i), 30 + ThreadLocalRandom.current().nextInt(10), TimeUnit.SECONDS));
    log.info("Cache init finished");
    
    // Output the database QPS once per second
    Executors.newSingleThreadScheduledExecutor().scheduleAtFixedRate(() -> {
        log.info("DB QPS : {}", atomicInteger.getAndSet(0));
    }, 0, 1, TimeUnit.SECONDS);
}

After the modification, the database QPS decreased from over 700 to around 100 at maximum.

Solution 2: Prevent the cache from expiring actively. Set the cache data to never expire during initialization, and then start a background thread that updates all data to the cache every 30 seconds. By controlling the frequency of updating data from the database through appropriate sleep, the database pressure is reduced:

@PostConstruct
public void rightInit2() throws InterruptedException {
    CountDownLatch countDownLatch = new CountDownLatch(1);
    
    // Update the cache every 30 seconds
    Executors.newSingleThreadScheduledExecutor().scheduleAtFixedRate(() -> {
        IntStream.rangeClosed(1, 1000).forEach(i -> {
            String data = getCityFromDb(i);
            
            // Simulate the time it takes to update the cache
            try {
                TimeUnit.MILLISECONDS.sleep(20);
            } catch (InterruptedException e) { }
            
            if (!StringUtils.isEmpty(data)) {
                // Cache never expires, passive update
                stringRedisTemplate.opsForValue().set("city" + i, data);
            }
        });
        
        log.info("Cache update finished");
        
        // Wait for the first cache update to complete when starting the program
        countDownLatch.countDown();
    }, 0, 30, TimeUnit.SECONDS);
    
    Executors.newSingleThreadScheduledExecutor().scheduleAtFixedRate(() -> {
        log.info("DB QPS : {}", atomicInteger.getAndSet(0));
    }, 0, 1, TimeUnit.SECONDS);
    
    countDownLatch.await();
}

After this modification, although the overall update time for the cache is around 21 seconds, the database pressure remains stable.

Regarding these two solutions, we need to pay special attention to the following three points:

  1. Solution 1 and Solution 2 are two completely different caching methods. If it is not possible to cache all data, then only Solution 1 can be used.

  2. Even with Solution 2, where the cache never expires, the logic for the query to the data source still needs to be ensured. As mentioned earlier, we cannot guarantee that the data in the cache system will never be lost.

  3. Whether it is Solution 1 or Solution 2, when adding data from the database to the cache, it is necessary to check if the data from the database is valid, such as performing basic null checks.

I have encountered a major incident before. A certain system would cache basic data for up to half a year. At one point, the DBA archived (essentially deleted) the original data in the database. Since the data in the cache was still there, there was no problem at first. However, when the data in the cache expired after half a year, empty data was queried from the database and added to the cache, causing a widespread incident.

This case illustrates that caches make it more difficult for us to discover problems with the original data. Therefore, data validation must be performed before adding data to the cache, and alarms should be promptly triggered if significant anomalies are detected.

Speaking of this, let’s take a closer look at the screenshot of the cache retrieval QPS exceeding 700. It can be seen that in concurrent situations, a total of 1000 data entries resulted in 1002 cache retrievals, indicating that some entries experienced concurrent retrievals. This is the cache concurrency issue that I will discuss further later.

Pay Attention to Cache Breakdown Issues #

In some cases where a key belongs to extremely hot data and there is a high level of concurrency, if this key expires, there may be a large number of concurrent requests to retrieve data from the source at the same time, which is equivalent to a large number of concurrent requests directly hitting the database. This situation is what we commonly refer to as cache breakdown or cache concurrency issues.

Let’s reproduce this problem. When the program starts, initialize a hot data in Redis with an expiration time of 5 seconds, and output the QPS of source retrieval every 1 second:

@PostConstruct
public void init() {
    // Initialize a hot data in Redis with an expiration time of 5 seconds
    stringRedisTemplate.opsForValue().set("hotsopt", getExpensiveData(), 5, TimeUnit.SECONDS);
    
    // Output the QPS of source retrieval every 1 second
    Executors.newSingleThreadScheduledExecutor().scheduleAtFixedRate(() -> {
        log.info("DB QPS: {}", atomicInteger.getAndSet(0));
    }, 0, 1, TimeUnit.SECONDS);
}

@GetMapping("wrong")
public String wrong() {
    String data = stringRedisTemplate.opsForValue().get("hotsopt");

    if (StringUtils.isEmpty(data)) {
        data = getExpensiveData();
        
        // Re-add the data to the cache with an expiration time of 5 seconds
        stringRedisTemplate.opsForValue().set("hotsopt", data, 5, TimeUnit.SECONDS);
    }

    return data;
}

As you can see, the database has about 20 QPS every 5 seconds:

img

If the source retrieval operation is particularly expensive, this concurrency cannot be ignored. In this case, we can consider using lock mechanisms to limit the concurrency of source retrieval. For example, in the following code example, we use Redisson to obtain a Redis-based distributed lock and attempt to acquire the lock before querying the database:

@Autowired
private RedissonClient redissonClient;

@GetMapping("right")
public String right() {
    String data = stringRedisTemplate.opsForValue().get("hotsopt");

    if (StringUtils.isEmpty(data)) {
        RLock locker = redissonClient.getLock("locker");
        
        // Acquire the distributed lock
        if (locker.tryLock()) {
            try {
                data = stringRedisTemplate.opsForValue().get("hotsopt");
                
                // Double check, because another thread might have passed the first check and is waiting for the lock, and the data has already been written into Redis by thread A.
                if (StringUtils.isEmpty(data)) {
                    // Retrieve data from the database
                    data = getExpensiveData();
                    stringRedisTemplate.opsForValue().set("hotsopt", data, 5, TimeUnit.SECONDS);
                }
            } finally {
                // Don't forget to release the lock, and pay attention to the usage of try-finally to ensure that unlock is always called
                locker.unlock();
            }
        }
    }

    return data;
}

This way, we can limit the concurrency of source retrieval to 1:

img

In a real business scenario, it is not necessary to use double-checking distributed locks with such strict global concurrency limitations, because although this can minimize the concurrency of database retrieval, it also limits the concurrency when the cache expires. Possible alternatives to consider are:

Option 1: Use locks within a process to limit concurrency, allowing each node to retrieve data concurrently.

Option 2: Instead of using locks for limitations, use tools like Semaphores to limit the concurrency to a certain number, such as 10. This way, you can limit the concurrency of source retrieval to a reasonable level while still allowing a certain number of threads to retrieve data at the same time.

Attention to Cache Penetration Issue #

In the previous examples, the logic of caching and sourcing is that when the required data is not found in the cache, it is sourced from the database. One vulnerability that can easily occur is that the absence of data in the cache does not necessarily mean that the data is not cached; it is also possible that the original data does not exist at all.

For example, consider the following scenario. The database only stores users with IDs ranging from 0 (exclusive) to 10000 (inclusive). If a user ID outside this range is queried from the database, an empty string will be returned, so the cached value will also be an empty string. If the ID=0 is used to query the API, it will retrieve an empty string from the cache, assume that there is no data in the cache, and source query again, which is equivalent to sourcing query every time:

@GetMapping("wrong")
public String wrong(@RequestParam("id") int id) {
    String key = "user" + id;
    String data = stringRedisTemplate.opsForValue().get(key);
    
    // Unable to distinguish whether it is an invalid user or cache expiration
    if (StringUtils.isEmpty(data)) {
        data = getCityFromDb(id);
        stringRedisTemplate.opsForValue().set(key, data, 30, TimeUnit.SECONDS);
    }
    
    return data;
}

private String getCityFromDb(int id) {
    atomicInteger.incrementAndGet();
    
    // Note that only users with IDs between 0 (exclusive) and 10000 (inclusive) are valid users for which user information can be retrieved
    if (id > 0 && id <= 10000) return "userdata";
    
    // Otherwise, return an empty string
    return "";
}

After load testing, the query per second (QPS) of the database reaches several thousand:

img

If this vulnerability is exploited maliciously, it will cause a huge performance pressure on the database. This is called cache penetration.

It is important to note the difference between cache penetration and cache breakdown:

  • Cache penetration refers to the situation where the cache does not play the role of buffering the load.
  • Cache breakdown refers to the instantaneous concurrent accesses to the database when the cache expires.

There are two solutions to address cache penetration.

Solution 1: For non-existing data, also set a special value in the cache. For example, when the user information retrieved from the database is empty, set a special meaning string “NODATA” in the cache. This allows the cache to be hit directly next time, thus returning the result from the cache without querying the database:

@GetMapping("right")
public String right(@RequestParam("id") int id) {
    String key = "user" + id;
    String data = stringRedisTemplate.opsForValue().get(key);
    
    if (StringUtils.isEmpty(data)) {
        data = getCityFromDb(id);
        
        // Verify if the data returned from the database is valid
        if (!StringUtils.isEmpty(data)) {
            stringRedisTemplate.opsForValue().set(key, data, 30, TimeUnit.SECONDS);
        } else {
            // If it's invalid, directly set "NODATA" in the cache, so that even for invalid users, the cache can still be hit next time
            stringRedisTemplate.opsForValue().set(key, "NODATA", 30, TimeUnit.SECONDS);
        }
    }
    
    return data;
}

However, using this approach may lead to a large number of invalid data being added to the cache. If you are concerned about the cache being filled with a large number of invalid data, you can consider Solution 2, which is to use a Bloom filter as a pre-filter.

A Bloom filter is a probabilistic data structure composed of a long binary vector and a series of random hash functions. When an element is added to the set, it is mapped to k points in the m-bit array using k hash functions, and these points are set to 1.

During retrieval, if any of these points is 0, then the element being checked definitely does not exist; if all points are 1, then the element being checked is very likely to exist.

The principle is illustrated in the following figure:

img

A Bloom filter does not store the original values, so it has a high space efficiency. On average, each element occupies only 2.4 bytes to achieve a false positive rate of one in ten thousand. Here, the false positive rate refers to the probability that the filter mistakenly determines an element to exist when it does not. We can increase the storage space of the Bloom filter to obtain a smaller false positive rate.

You can save all possible values in the Bloom filter and filter once before reading data from the cache:

  • If the Bloom filter indicates that the value does not exist, it means that the value definitely does not exist, so there is no need to query the cache or the database.
  • Only for extremely rare false positive requests, the illegal key requests will eventually go to the cache or the database.

To use the Bloom filter, we can use the BloomFilter class provided by Google Guava library to modify the program. During startup, initialize a BloomFilter with all valid user IDs and 10,000 elements, and call its mightContain method before querying the cache to check if the user ID is possible. If the Bloom filter indicates that the value may exist, proceed with the cache query. If the value is not found, query the database, and then set the data in the cache:

private BloomFilter<Integer> bloomFilter;

@PostConstruct
public void init() {
    // Create a Bloom filter with 10,000 elements and an expected false positive rate of 1%
    bloomFilter = BloomFilter.create(Funnels.integerFunnel(), 10000, 0.01);
    
    // Populate the Bloom filter
    IntStream.rangeClosed(1, 10000).forEach(bloomFilter::put);
}

@GetMapping("right2")
public String right2(@RequestParam("id") int id) {
    String data = "";
    
    // First check through the Bloom filter
    if (bloomFilter.mightContain(id)) {
        String key = "user" + id;
        
        // Query through the cache
        data = stringRedisTemplate.opsForValue().get(key);
        
        if (StringUtils.isEmpty(data)) {
            // Query through the database
            data = getCityFromDb(id);
            stringRedisTemplate.opsForValue().set(key, data, 30, TimeUnit.SECONDS);
        }
    }
    
    return data;
}

For Solution 2, we need to sync all possible values and add them to the Bloom filter, which is a tedious task. If the business rules are clear, you can also directly determine the existence of a value based on the business rules.

In fact, Solution 2 and Solution 1 can be used simultaneously. By placing the Bloom filter as a pre-filter, if there is a false positive case, then save the special value to the cache in order to avoid invalid data query requests to the database as a double guarantee.

Pay attention to cache data synchronization strategy #

The three cases mentioned earlier are actually passive deletion of expired cache data. In practice, when modifying the original data, considering the timeliness of cache data updates, we may adopt a proactive cache update strategy. These strategies may include:

  1. Updating the cache first, then updating the database;
  2. Updating the database first, then updating the cache;
  3. Deleting the cache first, then updating the database and loading data into the cache as needed when accessing;
  4. Updating the database first, then deleting the cache and loading data into the cache as needed when accessing.

So, which update strategy should we choose? Let me analyze these four strategies one by one:

The “update the cache first, then update the database” strategy is not feasible. The database design is complex and there is a high possibility that the database update operation will fail due to timeouts or other reasons. In addition, transactions are involved, and it is likely that the cache and database will be inconsistent if the database update fails.

The “update the database first, then update the cache” strategy is not feasible. First, if thread A and B complete the database update successively, but update the cache in the order of B and A, it is likely to update old data to the cache, causing data inconsistency. Second, we are not sure if the data in the cache will be accessed, so it is not necessary to update all data to the cache.

The “delete the cache first, then update the database and load data into the cache as needed when accessing” strategy is also not feasible. In the case of concurrency, it is likely that another thread will read the old value into the cache before the cache is deleted and the database is updated. If there is a large amount of concurrency, the probability of this happening will also be high.

The “update the database first, then delete the cache and load data into the cache as needed when accessing” strategy is the best. Although in extreme cases, this strategy may also result in data inconsistency, the probability is very low and can be ignored. Let’s take an example of an “extreme case”: the time point at which data is updated exactly coincides with the moment when the cache expires. At this time, A reads the old value first, and then B completes the database update and deletes the cache, after which A adds the old value to the cache.

It is worth noting that the operation of deleting the cache after updating the database may fail. If this happens, consider adding the task to a delayed queue for delayed retry to ensure that the data can be deleted and the cache can be updated in a timely manner. Because the delete operation is idempotent, even if duplicate deletion occurs, it is not a big problem, which is another reason why deletion is better than updating.

Therefore, for cache updates, it is recommended that the data in the cache not be triggered by data update operations, but be loaded on-demand when needed, and the cache should be promptly deleted after data updates.

Key Points Review #

Today, I mainly shared with you the three major issues of data caching from a design perspective.

Firstly, we cannot treat cache databases such as Redis as regular databases. We can’t assume that the cache is always reliable, nor can we assume that expired data can always be read. We need to handle the logic of cache fallback effectively. Besides, we should explicitly set the maximum memory usage and data eviction strategy of Redis to avoid OOM issues.

Secondly, caching performs much better than databases. We need to consider various situations where a large number of requests bypass the cache and directly hit the database, causing database failures. To solve the problem of cache avalanche, where the cache fails massively and momentarily, we can use differential cache expiration times. For the issue of high-concurrency cache key fallback, we can use locks to limit the concurrency. To solve the problem of cache penetration, where non-existent data directly goes through the cache, we can use Bloom filters to pre-judge the existence of data or set a value in the cache to solve it.

Thirdly, when there are updates to the data in the database, we need to consider how to ensure the consistency of the data in the cache. As we can see, the strategy of “updating the database first, then deleting the cache, and loading data to the cache on-demand when accessing” is the most appropriate. We should also set appropriate cache expiration times, so that even if inconsistencies occur, the data can be promptly synchronized after the cache expires.

Finally, I want to remind you that when using a caching system, it is important to monitor key metrics such as memory usage, hit rate, and average object expiration time of the cache system to evaluate its effectiveness and timely discover issues.

The code used today is uploaded to GitHub, and you can click on this link to view it.

Reflection and Discussion #

When discussing the issue of concurrent access to the cache, we mentioned that hot keys can impose pressure on the database when cache retrieval is required. If a key is particularly hot, the cache system may not be able to handle the load, as all accesses are concentrated on a single cache server. If we use Redis as the cache, can we distribute the cache retrieval pressure of a hot key to multiple Redis nodes?

Large keys can also be a problem when it comes to data caching. If a key’s value is very large, it can have a significant impact on the performance of Redis. Since Redis follows a single-threaded model, operations such as querying or deleting large keys can cause Redis to block or even experience high availability switches. Do you know how to query large keys in Redis and how to design the splitting of large keys?

Regarding cache design, what pitfalls have you encountered? I am Zhu Ye, and I welcome you to leave a comment in the comment section to share your thoughts. Feel free to share today’s content with your friends or colleagues for further discussion.