Cache Aside Pattern

When updating the cache, after updating the database, should we update the cache or delete the cache? Or should we delete the cache first, then update the database? In fact, all of these approaches have certain issues.

Cache Aside Pattern

This is the most commonly used caching approach. Its specific logic is as follows:

Miss: The application first fetches data from the cache. If it doesn't get it, it fetches data from the database, and upon success, puts it into the cache.
Hit: The application fetches data from the cache and returns it.
Update: First store the data in the database, and upon success, invalidate the cache.

When updating, we first update the database, and after the database update succeeds, we invalidate the cache. But is this approach really problem-free?

Let's consider the following concurrency scenario:

Cache key1 happens to expire.
Request A initiates a read request, misses the cache, and queries the database. At this point, the result is old data.
Request B initiates an update request, first updating the database.
Request B invalidates the cache.
At this point, Request A writes the old data read in step 2 into the cache.

The above concurrency scenario can theoretically occur and cause dirty data, but the probability of it happening in a real production environment is very low, because this condition requires the cache to expire during a read, and there must be a concurrent write operation. In practice, database write operations are much slower than read operations, and they also require table locks. The read operation must enter the database before the write operation, and it must update the cache after the write operation. The probability of all these conditions being met is quite low.

Delete Cache First, Then Update Database

The reasons this approach can cause data inconsistency are as follows:

Request A performs a write operation, deletes the cache (and updates the database, but hasn't done so yet).
Request B queries and finds the cache doesn't exist.
Request B queries the database and gets the old value.
Request B writes the old value into the cache.
At this point, Request A updates the new value into the database.

In this case, if the cache is not updated or evicted by the expiration policy, this data will always be dirty data.

Update Database First, Then Update Cache

Let's look at the following concurrency scenario:

Thread A and Thread B simultaneously update data key1.
Thread A updates the database data key1, now value1.
Thread A updates the database data key1, now value2 (the latest data).
Thread B updates the cache key1 to value2.
Thread A updates the cache key1 to value1.

Since Thread A's database update operation is earlier than Thread B's, Thread B's updated result value2 is the latest result, and ultimately value2 should be placed in the cache to meet actual requirements. However, due to network issues, B updates the cache earlier than A. This leads to dirty data, so this approach has thread safety issues.

Update Cache First, Then Update Database

This approach is not considered. If the cache is updated first and the cache update succeeds, but an exception occurs during the database update causing a rollback, the data in the cache cannot be rolled back, leading to data inconsistency.

Let me first explain that theoretically, setting an expiration time for the cache is a solution to ensure eventual consistency. With this approach, we can set an expiration time for the data stored in the cache. All write operations are based on the database, and cache operations are only best-effort. That is, if the database write succeeds but the cache update fails, then once the expiration time is reached, subsequent read requests will naturally read the new value from the database and backfill the cache. Therefore, the following discussion does not rely on setting expiration times for the cache.

Here, we discuss three update strategies:

(1) Update Database First, Then Update Cache

This approach is widely opposed. Why? There are two reasons.

Reason One (Thread Safety Perspective)

When Request A and Request B perform update operations simultaneously, the following can occur:

(1) Thread A updates the database. (2) Thread B updates the database. (3) Thread B updates the cache. (4) Thread A updates the cache.

This means Request A's cache update should happen before Request B's cache update, but due to network issues, B updates the cache earlier than A. This leads to dirty data, so this approach is not considered.

Reason Two (Business Scenario Perspective)

There are two points:

(1) If your business has more database write scenarios and fewer read scenarios, using this approach will cause the cache to be frequently updated even before the data is read, wasting performance.

(2) If the value you write to the database is not directly written to the cache but requires a series of complex calculations before being written to the cache, then recalculating the cache value after each database write is undoubtedly a waste of performance. Clearly, deleting the cache is more suitable.

Next, we discuss the most controversial issue: delete cache first, then update database, or update database first, then delete cache.

(2) Delete Cache First, Then Update Database

The reason this approach causes inconsistency is that there is a Request A performing an update operation and another Request B performing a query operation. The following situation can occur:

(1) Request A performs a write operation, deleting the cache. (2) Request B queries and finds the cache doesn't exist. (3) Request B queries the database and gets the old value. (4) Request B writes the old value into the cache. (5) Request A writes the new value into the database.

The above situation leads to inconsistency. Moreover, if the cache expiration time strategy is not used, this data will always be dirty data.

So, how to solve this? Use the delayed double-delete strategy.

Pseudo-code is as follows:

public void write(String key,Object data){

redis.delKey(key);

db.updateData(data);

Thread.sleep(1000);

redis.delKey(key);

}

Translated into Chinese description:

(1) First evict the cache. (2) Then write to the database (these two steps are the same as before). (3) Sleep for 1 second, then evict the cache again.

By doing this, the dirty cache data caused within 1 second can be deleted again.

So, how is this 1 second determined, and how long should the sleep actually be?

For the above situation, readers should evaluate the time consumption of their project's read data business logic. Then, the sleep time for write operations should be based on the read data business logic's time consumption, plus a few hundred milliseconds. The purpose of this is to ensure that after the read request completes, the write request can delete the dirty cache data caused by the read request.

What if you use MySQL's read-write separation architecture?

In this case, the reasons for data inconsistency are as follows. Again, there are two requests: Request A performs an update operation, and Request B performs a query operation.

(1) Request A performs a write operation, deleting the cache. (2) Request A writes the data to the database. (3) Request B queries the cache and finds no value. (4) Request B queries the slave database. At this point, master-slave synchronization hasn't completed, so it queries the old value. (5) Request B writes the old value into the cache. (6) The database completes master-slave synchronization, and the slave database becomes the new value.

The above situation is the cause of data inconsistency. Again, use the delayed double-delete strategy. Just change the sleep time to the master-slave synchronization delay time plus a few hundred milliseconds.

What if this synchronous eviction strategy reduces throughput?

OK, then make the second deletion asynchronous. Start a separate thread to delete asynchronously. This way, write requests don't need to sleep for a period before returning. This increases throughput.

What if the second deletion fails?

This is a very good question, because if the second deletion fails, the following situation can occur. Again, there are two requests: Request A performs an update operation, and Request B performs a query operation. For convenience, assume a single database:

OK, this means that if the second cache deletion fails, the cache and database inconsistency problem will reappear.

How to solve this?

For the specific solution, please see the blogger's analysis of the third update strategy.

(3) Update Database First, Then Delete Cache

First, let me mention that foreigners have proposed a cache update pattern called "Cache-Aside pattern." It states:

Miss: The application first fetches data from the cache. If it doesn't get it, it fetches data from the database, and upon success, puts it into the cache.
Hit: The application fetches data from the cache and returns it.
Update: First store the data in the database, and upon success, invalidate the cache.

Additionally, the well-known social networking site Facebook also proposed in their paper "Scaling Memcache at Facebook" that they use the strategy of updating the database first, then deleting the cache.

Does this approach have no concurrency issues?

No, it does. Suppose there are two requests: Request A performs a query operation, and Request B performs an update operation. The following situation can occur:

(1) The cache happens to expire. (2) Request A queries the database and gets an old value. (3) Request B writes the new value into the database. (4) Request B deletes the cache. (5) Request A writes the old value it queried into the cache.

OK, if the above situation occurs, dirty data will indeed be produced.

However, what is the probability of this happening?

There is a prerequisite for the above situation: the write database operation in step (3) must take less time than the read database operation in step (2), so that step (4) can occur before step (5). But think about it, the speed of database read operations is much faster than write operations (otherwise, why do read-write separation? The meaning of read-write separation is precisely because read operations are faster and consume fewer resources). Therefore, it's very difficult for step (3) to take less time than step (2).

How to solve the above concurrency issue?

First, setting an expiration time for the cache is one solution. Second, use the asynchronous delayed deletion strategy given in strategy (2) to ensure that the deletion operation is performed after the read request completes.

Are there other reasons for inconsistency?

Yes, there is a problem that exists in both cache update strategy (2) and cache update strategy (3): what if deleting the cache fails? Wouldn't inconsistency occur? For example, a write data request writes to the database, but deleting the cache fails, leading to inconsistency. This is also the last question left in cache update strategy (2).

How to solve it?

Just provide a guaranteed retry mechanism. Here are two solutions.

Solution One:

As shown in the figure below:

The flow is as follows:

(1) Update the database data. (2) The cache deletion fails due to various issues. (3) Send the key that needs to be deleted to a message queue. (4) Consume the message yourself and obtain the key that needs to be deleted. (5) Continue retrying the deletion operation until it succeeds.

However, this solution has a drawback: it causes significant intrusion into business code. Hence, Solution Two was created. In Solution Two, a subscription program is started to subscribe to the database's binlog and obtain the data that needs to be operated on. In the application, another program is started to receive the information from this subscription program and perform the cache deletion operation.

Solution Two:

The flow is as shown in the figure below:

(1) Update the database data. (2) The database writes the operation information into the binlog log. (3) The subscription program extracts the required data and key. (4) Start another piece of non-business code to obtain this information. (5) Attempt the cache deletion operation and find that the deletion fails. (6) Send this information to a message queue. (7) Re-obtain the data from the message queue and retry the operation.

Note: For the above binlog subscription program, there is a ready-made middleware in MySQL called canal that can fulfill the function of subscribing to binlog logs. As for Oracle, the blogger currently doesn't know if there is a ready-made middleware available. Additionally, for the retry mechanism, the blogger uses a message queue approach. If consistency requirements are not very high, you can simply start a separate thread in the program to retry at intervals. Everyone can be flexible and creative here; this is just providing an idea.

Granularity Control for Storage

Choosing full attributes provides better versatility and is easier to maintain. For tables like the user table, using full attributes is fine.

However, when choosing a cache, we need to consider performance and space issues. It's better to only save the attributes we need (but if the table structure changes later, maintainability is poor).

Cache Penetration: (Directly operating on the storage layer, losing the meaning of the cache layer)

Querying data that doesn't exist in the database, such as product details, querying a non-existent ID. Every time, it accesses the DB. If someone maliciously attacks, it could directly put excessive pressure on the DB.

Solutions:

When querying data by a certain key, if the corresponding data doesn't exist in the database, we set the value corresponding to this key to a default value, such as "NULL", and set a cache expiration time. At this point, before the cache expires, all accesses through this key are blocked by the cache. Later, if the data corresponding to this key exists in the DB, after the cache expires, accessing data through this key will retrieve the new value.
A common approach is to use a Bloom filter (which can retain a lot of data with very little memory). Hash all possible data into a sufficiently large bitmap. Data that definitely doesn't exist will be intercepted by this bitmap, thus avoiding query pressure on the underlying storage system. (Bloom filter: In fact, it's a very long binary vector and a series of random mapping functions. A Bloom filter can be used to check whether an element is in a set. Its advantages are that space efficiency and query time far exceed general algorithms. Its disadvantages are a certain false positive rate and difficulty in deletion.)

About the Bloom filter:

Cache Avalanche: (Cache Expiration)

A large area of the cache expires at the same time, so subsequent requests all fall to the database, causing the database to crash under a large number of requests in a short period.

Solutions:

Evenly stagger the cache expiration times of keys in the system to prevent a large number of keys' caches from expiring at the same time point.
Redesign the cache usage method. When we query data by key, first query the cache. If the cache doesn't have it, use a distributed lock to acquire a lock. The process that acquires the lock queries the DB and sets the cache, then unlocks. Other processes wait if they find a lock, and after unlocking, they return the cache data or query the DB again.
Try to ensure the high availability of the entire Redis cluster. If a machine goes down, replenish it as soon as possible.
Use local Ehcache cache + Hystrix rate limiting & degradation to prevent MySQL from crashing.

If it has already crashed: You can also use Redis's persistence mechanism to restore the saved data to the cache as quickly as possible.

Cache Thundering Herd (Cache "Bottomless Pit"):

Adding more nodes to meet business needs, but performance doesn't improve and instead declines.

When a client adds one cache, it only needs to do an mget once. But if it increases to three caches, it needs to do mget three times (network communication time increases). Each time a cache is added, the client needs to do a new mget, putting performance pressure on the server.

At the same time, mget needs to wait for the slowest machine to complete its operation before the mget operation is considered complete. This is still a parallel design; if it were a serial design, it would be even slower.

From the above example, we can conclude: More machines != Higher performance.

But it's not without solutions. Generally, when optimizing IO, the following methods can be used:

Command optimization. For example, slow queries like keys, hgetall bigkey.
We need to reduce the number of network communications. This optimization is the most frequently used in practical applications; we should minimize the number of communications.
Reduce access cost. For example, use client long connections or connection pools, NIO, etc.

Cache Aside Pattern