A bottom-up look at cache consistency

The speed gap between two "devices" is an eternal topic in computers. It is nothing more than adding cache! The locality principle is the greatest theorem in computer science. In order to gain a deeper understanding of cache issues in various places inside the computer, here we compare and analyze three different cases from a bottom-up perspective.

1. CPU level: CPU —> Level 3 cache (L1~3) —> Memory;

2. Database internal level: memory —> buffer pool —> disk;

3. Database external level: user —> redis —> database;

Cache between CPU and memory: Level 3 cache

The CPU uses L1, L2, and L3 three-level cache to solve the problem of slow memory speed. The CPU can write to memory in two ways: write-back and write-through.

• Write direct: As the name suggests, it writes to the cache and then writes to the memory. It is simple and direct, but the efficiency is low.

• Write back: The CPU writes to the cache, but does not write it to the memory, and marks the data as Dirty, indicating that the cache and memory data are inconsistent at this time. Only when the cache is replaced, the data in the cache is written to the memory. This greatly reduces the number of writes to memory and improves efficiency.

In multi-core CPUs, the above cache consistency issues will become more complicated. in multi-core CPUs. Each core has its own unique L1 and L2 cache, and only the L3 cache is shared by all cores. Therefore, the consistency of L1 and L2 caches between different cores cannot be guaranteed. In order to solve this problem, the CPU uses two mechanisms to synchronize the L1 and L2 caches of different cores: write propagation and transaction serialization

• Write propagation: Propagate the data write operation results to the caches of other cores

• Transaction serialization: When core 1 modifies variable i to 100, it will notify core 3 and core 4 through propagation. If core 2 modifies i to 200 at the same time, it will also be propagated to core 3 and core 4. At this time, the value of variable i obtained by core 3 and core 4 will be uncertain (it may be 100 or 200). Therefore, it is necessary to realize the serialization of transactions. When both cores need to modify a variable, they must be implemented in a certain order. To this end, the concept of lock can be introduced. Only the core that has obtained the lock is qualified to modify the variable, and the core that does not have the lock can only wait.

The specific implementation mechanism of the write propagation idea is bus sniffing, where each core monitors all activities on the bus. Core 1 modifies variable i to 100 and sends a propagation to the bus. If other cores (2~3) find that the value of variable i is also stored in their L1 cache, they will immediately modify their L1 cache. It can be seen that each write operation needs to be propagated, which unintentionally increases the burden on the CPU. In addition, write propagation does not guarantee transaction serialization.

The serialization of transactions needs to be implemented through the MESI protocol. The so-called MSEI, namely Modified (modified), Exclusive (exclusive), Shared (shared), Invalidated (invalidated), uses these four states to mark a Cache line.

For specific state transfer, please refer to Xiaolin Coding. I will not continue to describe it here. The whole process is still very interesting and can be described by a finite state machine.

Cache inside the database: Buffer Pool

Within MySQL, due to the slow disk IO speed, the InnoDB engine copies the L1~3 cache and introduces a Buffer Pool. If the read data already exists in the Buffer Pool, then the cache hits and returns directly. When writing data, it is first written into the Buffer Pool and marked as dirty data.

The Buffer Pool is slightly inconsistent with the L13 cache. The L13 cache is written into the memory when the data page is replaced. In order to ensure data security, MySQL uses a background thread to write dirty data pages to the disk at a certain opportunity. In addition, if mysql crashes before the background thread is flushed to the disk, wouldn't it be a shame to lose data at this time? The so-called slow speed is nothing more than adding cache, and the so-called downtime is nothing more than writing to disk. Therefore, MySQL adds a layer of writing mechanism (matryoshka) to the disk. Each update operation of MySQL is first written to the redo log, and then written to the buffer pool. Since redo log reads and writes sequentially, the writing speed is very fast.

What? You said that if the redo log is written, the data is still in the Page Cache of the memory and is not written to the disk at this time. If a failure occurs and the data in the memory is lost, data security cannot be guaranteed. In fact, if this kind of power outage occurs, it is an operating system level failure. There is no solution. You can directly go to the finance department to pay your salary and leave.

Cache outside the database: Redis

Redis is often used as a cache for MySQL to store hot data and prevent MySQL from collapsing due to excessive pressure. Similar to the CPU situation, Redis and databases will also face cache inconsistency issues.

But what is different from the internal cache of the CPU and MySQL is that when modifying data, the former uses a delayed write-back strategy (the CPU writes dirty pages to memory only after they are replaced, and MySQL has a background thread to control the timing to write to the disk). Although Redis serves as the cache of MySQL, it uses a write-through strategy when modifying. It is necessary to modify Redis and MySQL at the same time. Will the order of the two operations cause problems?

• Update the database first, then update Redis

• Update Redis first, then update the database

In a concurrency environment, both operations may cause cache and database inconsistencies. For detailed analysis of the two situations, please refer to [Xiao Lin Coding](https://xiaolincoding.com/redis/architecture/mysql_redis_consistency .html#%E5%85%88%E6%9B%B4%E6%96%B0%E6%95%B0%E6%8D%AE%E5%BA%93-%E 8%BF%98%E6%98%AF%E5%85%88%E6%9B%B4%E6%96%B0%E7%BC%93%E5%AD%98).

Think about it for a moment, if the CPU also adopts the write-through strategy, it will also encounter the above cache and memory inconsistency problem.

If you change to delete Redis and update the database:

• Delete Redis first, then update the database

• Update the database first, then delete Redis

For the specific analysis process, please refer to [Xiaolin Coding](https://xiaolincoding.com/redis/architecture/mysql_redis_consistency.html#%E5%85%88%E6%9B%B4%E6%96% B0%E6%95%B0%E6%8D%AE%E5%BA%93-%E8%BF%98%E6%98%AF%E5%85%88%E5%88%A0%E9%99%A4%E7%BC%93%E5%AD%98), it is a bit troublesome to write it out. In short, the result is, **"Update the database first + and then delete the cache" is the solution that can ensure data consistency.

If you delete the cache first and then update the database, the industry solution is: Delayed double deletion strategy

redis.delKey(X)





db.update(X)





Thread.sleep(N)





redis.delKey(X)

Anyway, no matter which method is used, redis has an expiration policy to cover it up. After a long enough time, it will always be updated, and at least weak consistency is maintained with the database