Designing a Cache System

This is a historical learning note and may contain outdated or incomplete understanding.

1. What Is a Cache?

The speed difference between CPU and disk is huge. Based on the principle of locality, frequently used data is generally loaded into memory to improve access speed.

2. Why Do We Need a Cache?

Improve performance.
Reduce downstream load.

3. Disadvantages of Caching

3.1. Cache Consistency

Under the CAP principle, consistency problems caused by delay cannot be fully eliminated; only eventual consistency can be guaranteed.
With read-through, eventual consistency can be guaranteed through expiration. With a full cache, the cache is read-only.
Monitoring and alerts + manual compensation, retry.
#133 Solutions for Cache and Database Consistency [Go Night Reading] - bilibili

3.2. Additional Storage Space

A typical trade of space for time.

4. Cache Layers

4.1. Client Cache

HTTP Cache

4.2. CDN Cache

4.3. Web Server Cache

Nginx

4.4. Business Server Cache

Local memory.

4.5. Cache Middleware Cache

Redis

4.6. Database Cache

MySQL’s built-in cache.

5. Using a Cache

5.1. Cache Size

The cache size can be set according to the average number of active users, so that the data will not be evicted from the cache.

5.2. Cache Duration

The cache duration can be set according to the average active duration, so that the data will not be evicted from the cache.

5.3. Cache Hit Rate

The quality of a cache depends on the hit rate. A high hit rate means the cache is effective. Generally, a hit rate above 80% is considered very high.

For non-hot data, consistent hashing can route requests to the same node, so the cache hit rate can be quite high. However, there can still be data hot spots. If traffic increases, even after scaling out, the characteristics of consistent hashing may keep existing requests on the original node, making the scaling ineffective. Virtual nodes can be used, but virtual nodes require data migration and cause cache misses, although this is still manageable.

5.4. Cache Warming

Count frequently accessed data and load it into the cache when the server starts.

5.5. Cache Eviction Strategy

Cache Replacement Strategies

5.6. Cache Architecture Patterns

5.6.1. cache-as-sor

Business code and cache are separated. It is generally used with read-through + write-back, read-through + write-through, or refresh-ahead.
Advantage: low coupling.
Disadvantage: low flexibility.

5.6.2. cache-aside

Business code and cache are together. It is generally used with read-through + write-invalid.
Advantage: high flexibility.
Disadvantage: high coupling.

5.7. Cache Updates

5.7.1. read-through + write-invalid

On read: if the cache has the value, return it directly; otherwise read from the database, put it into the cache, then return it.
On write: update the database first, then delete the cache.

5.7.1.1. Why Delete the Cache Instead of Updating It on Write?

This follows the idea of lazy computation: calculate only when the result is actually needed. Updating a cache can involve a series of complex and time-consuming operations, and the result may never be used afterward.

Essentially, it is a choice between heavier writes and lighter reads, or heavier reads and lighter writes.

5.7.1.2. Cache Consistency Problems

5.7.1.2.1. Concurrent Read/Write Problems

Whether the database is updated first or the cache is deleted first, cache inconsistency can occur.

Delete the cache first, then update the database. When reading and writing the same key concurrently, a cache consistency problem can occur:
- User 1 write: delete the Redis cache.
- User 2 read: read data from MySQL.
- User 2 read: write the data into Redis.
- User 1 write: write to the database.
Update the database first, then delete the cache. When reading and writing the same key concurrently, a cache consistency problem can also occur:
- User 1 read: read data from MySQL.
- User 2 write: update MySQL data.
- User 2 write: delete the Redis cache.
- User 1 read: write the data into Redis.

This happens when the read starts before the write commits, while the cache population happens after the write has deleted the cache. Compared with deleting the cache before updating the database, the probability of this kind of stale data is much lower.

How to solve it:
- Eventual consistency: add a cache expiration time.
- Strong consistency: add a lock.

5.7.1.2.2. Network Error Problems

The database update succeeds but deleting the cache fails. For network errors, the operation can only be retried:
- After updating the database, put the cache-deletion operation into a message queue and retry until it succeeds.
- Or, after updating the database, use Canal to subscribe to the binlog, put the cache-deletion operation into a message queue, and retry until it succeeds.

5.7.2. read-through + write-through

On read: if the cache has the value, return it directly; otherwise read from the database, put it into the cache, then return it.
On write: update the cache first, then update the database. That is, dual writes.

5.7.2.1. Cache Consistency Problems

Whether the database is updated first or the cache is updated first, cache inconsistency can occur.

5.7.2.1.1. Concurrent Write Problems

Update the database first, then update the cache. During concurrent writes, a cache consistency problem can occur:
- User 1 write: update the database.
- User 2 write: update the database.
- User 2 write: update the cache.
- User 1 write: update the cache. At this point, the cache contains old data.

In practice, concurrent writes are relatively uncommon, and the database locks the same record when it is written, so the probability is low.

Update the cache first, then update the database. During concurrent writes, a cache consistency problem can occur:
- User 1 write: update the cache.
- User 2 write: update the cache.
- User 2 write: update the database.
- User 1 write: update the database. At this point, the database contains old data.
How to solve it:
- Eventual consistency: add a cache expiration time.
- Strong consistency: add a lock.

5.7.2.1.2. Network Error Problems

The database update succeeds but the cache update fails. For network errors, the operation can only be retried:
- After updating the database, put the cache-update operation into a message queue and retry until it succeeds.
- Or, after updating the database, use Canal to subscribe to the binlog, put the cache-update operation into a message queue, and retry until it succeeds.

5.7.3. read-through + write-back

On read: if the cache has the value, return it directly; otherwise read from the database, put it into the cache, then return it.
On write: only update the cache, not the database. The cache asynchronously updates the database in batches.

5.7.3.1. Why Not Update the Database Directly?

Only memory is operated on, so I/O efficiency is very high.
Multiple operations on the same data can also be merged.

5.7.3.2. Cache Consistency Problems

5.7.3.2.1. Crash

If the system crashes before data in the cache has been flushed to the database, the data is lost.

5.7.4. refresh-ahead

On read: read only from the cache.
On write: write only to the database.
A scheduled task pulls all data from the database and updates the cache.

5.7.5. CDC

Change Data Capture system.
For example, LinkedIn’s Databus and Alibaba’s Canal.

5.7.6. Comparison of Approaches

refresh-ahead:
- Advantage: reads only access the cache, so efficiency is especially high.
- Disadvantages:
  - All data needs to be periodically pulled into the cache.
  - If the interval is too short and the data volume is too large, the operation may time out. If the interval is too long, the cache and database remain inconsistent for longer. This is similar to replication, where the replication delay is the scheduled pull interval.
- Suitable for scenarios with a small amount of data.
read-through + write-back:
- Advantages: compared with refresh-ahead, it does not need periodic full pulls; writing to the cache first and later batch-writing to the database is also very fast.
- Disadvantages:
  - If the system crashes before data in the cache has been flushed to the database, the data is lost.
  - Data is written to the cache whether it will be used or not, resulting in a low hit rate.
- Suitable for scenarios with a larger data volume, where data loss is acceptable and write performance requirements are especially high.
read-through + write-through:
- Advantage: compared with write-back, data is not lost.
- Disadvantages:
  - Data is written to the cache whether it will be used or not, resulting in a low hit rate.
  - ~~There is a concurrent read/write problem.~~
- Suitable for scenarios with a larger data volume, where data cannot be lost and write performance requirements are not as high.
read-through + write-invalid:
- Advantage: compared with write-through, the cache hit rate is higher and memory usage is lower.
- Disadvantages:
  - Compared with write-through, data is put into the cache only when a get request needs it, so efficiency is lower.
  - ~~There is a concurrent read/write problem.~~
- Suitable for scenarios with a very large data volume, where data cannot be lost and write performance requirements are not as high.

5.8. Cache Fallback to the Source

If data is not found in the cache and is then read from the database, this is called falling back to the source.
If the cache needs to fall back to the source, the following problems can occur.

5.8.1. Cache Penetration

5.8.1.1. What Is It?

The queried key does not exist, so neither the database nor the cache contains it. Query requests therefore fall through to the database. If request volume is too large, for example under an attack, the database can be overwhelmed.

5.8.1.2. How to Solve It

5.8.1.2.1. Cache Empty Values

Cache empty results as well. If data is later inserted, this empty cache entry needs to be cleared.
Disadvantages:
- The first query still has to query the database.
- The cache contains a large amount of empty data.

5.8.1.2.2. BloomFilter

Record all keys that exist in the database in a BloomFilter. When a request arrives, if the key exists in the BloomFilter, read it from the cache; if it does not exist in the BloomFilter, return empty directly.
Disadvantage:
- There is a certain false-positive rate. Because of hash collisions, BloomFilter may treat a nonexistent key as existing. The database will then be queried once and return no data, but the volume is small enough to be acceptable.

5.8.1.2.3. BloomFilter vs Cache Null

	BloomFilter	Cache Null
Advantage	Uses less space	No need for periodic rebuilds
Disadvantage	Needs periodic rebuilds	Uses more space

5.8.2. Cache Breakdown

5.8.2.1. What Is It?

A hot key expires in the cache. Query requests then fall through to the database. If request volume is too large, such as during a major promotion, the database can be overwhelmed.

5.8.2.2. How to Solve It

5.8.2.2.1. Do Not Expire Automatically

Set a logical expiration time and manually update the cache after it expires.
Periodically update the cache.

5.8.2.2.2. Use a Mutex and Queue Requests

Allow only one thread to rebuild the cache. Other threads wait for the rebuilding thread to finish and then fetch from the cache.
For example, Go’s sync.singleflight.

5.8.2.2.3. No Automatic Expiration vs Mutex

	No Automatic Expiration	Mutex
Advantage	No deadlock or blocking risk	Guarantees consistency
Disadvantage	Data inconsistency	Deadlock and blocking risk

5.8.3. Cache Avalanche

5.8.3.1. What Is It?

A large number of keys expire in the cache, unlike cache breakdown where one hot key expires. For example, the cache crashes, restarts, or many keys expire at the same time. Query requests then fall through to the database. If request volume is too large, such as during a major promotion, the database can be overwhelmed.

5.8.3.2. How to Solve It

5.8.3.2.1. Set Different Expiration Times

Add or subtract a value from a base expiration time.
Disadvantage:
- It cannot solve the case where a single key is hot.
- Solution: use a mutex and queue requests.

5.8.3.2.2. Improve Cache-System Availability

For example, enable Redis cluster mode and persistence.

5.8.3.2.3. Enable Transparent Multi-Level Caching

For example, a local cache.

6. How to Design Cache Middleware

Designing Cache Middleware