Cache - Cache Design Patterns

I read a blog a couple months ago talking about four most common cache design patterns, and want to summarize that post and add my understandings here.

Naive Approach

The naive approach is, when update data in cache service, first remove cached data, update data source, and then reload data from data source to cache.

However, the logic is wrong!

For example, there are two concurrent operation, one being update operation and the other being query operation. After update operation removed cached data, query operation doesn’t hit the target and triggers a reload of outdated data from data store, and then the update operation modifies data store. Thus, the cache now contains dirty/expired data, and will continue to hold such dirty data.

I’m gonna discuss four caching strategies/design patterns today.

  • Read Through
  • Write Through
  • Cache Aside
  • Write Behind Caching

Note that they’re design patterns, neither mechanisms of databases like MySQL or Postgres, nor how Memcache or Redis works.

Read / Write Through

This is where the application treats cache as the main data store and reads data from it and writes data to it. The cache is responsible for reading and writing this data to the database, thereby relieving the application of this responsibility.

1. Read Through

Read Through is used in querying operations to update cached data.

When cached data is evicted (due to expiration or LRU eviction), it’s the application’s responsibility to load new data into cache in Cache Aside strategy , while it’s cache service’s responsibility in Read Through strategy. This function brings transparency of caching to application.

2. Write Through

Write Through is used in data updating operations to update cached data.

Whenever application updates a piece of data

  • if data is not in cache, cache service directly update data store
  • if data is in cache, cache service will first update itself, and then update database. A write is done synchronously both to the cache and to the backing store, conforming a single transaction.

3. Cache Aside

This article explains Cache Aside strategy very well. I’ll grab some content from there.

For caches that do not provide read/write-through functionality, it is the responsibility of the applications that use the cache to maintain the data in the cache. An application can emulate the functionality of read-through caching by implementing the cache-aside strategy. This strategy effectively loads data into the cache on demand. The following figure summarizes the steps in this process.

If an application updates information, it can emulate the write-through strategy as follows:

  • Make the modification to the data store
  • Invalidate the corresponding item in the cache.

When the item is next required, using the cache-aside strategy will cause the updated data to be retrieved from the data store and added back into the cache.

Issues and Considerations

Consider the following points when deciding how to implement this pattern:

  • Lifetime of Cached Data. Many caches implement an expiration policy that causes data to be invalidated and removed from the cache if it is not accessed for a specified period. For cache-aside to be effective, ensure that the expiration policy matches the pattern of access for applications that use the data. Do not make the expiration period too short because this can cause applications to continually retrieve data from the data store and add it to the cache. Similarly, do not make the expiration period so long that the cached data is likely to become stale. Remember that caching is most effective for relatively static data, or data that is read frequently.

  • Evicting Data. Most caches have only a limited size compared to the data store from where the data originates, and they will evict data if necessary. Most caches adopt a least-recently-used policy for selecting items to evict, but this may be customizable. Configure the global expiration property and other properties of the cache, and the expiration property of each cached item, to help ensure that the cache is cost effective. It may not always be appropriate to apply a global eviction policy to every item in the cache. For example, if a cached item is very expensive to retrieve from the data store, it may be beneficial to retain this item in cache at the expense of more frequently accessed but less costly items.

  • Priming the Cache. Many solutions prepopulate the cache with the data that an application is likely to need as part of the startup processing. The Cache-Aside pattern may still be useful if some of this data expires or is evicted.

  • Consistency. Implementing the Cache-Aside pattern does not guarantee consistency between the data store and the cache. An item in the data store may be changed at any time by an external process, and this change might not be reflected in the cache until the next time the item is loaded into the cache. In a system that replicates data across data stores, this problem may become especially acute if synchronization occurs very frequently.

  • Local (In-Memory) Caching. A cache could be local to an application instance and stored in-memory. Cache-aside can be useful in this environment if an application repeatedly accesses the same data. However, a local cache is private and so different application instances could each have a copy of the same cached data. This data could quickly become inconsistent between caches, so it may be necessary to expire data held in a private cache and refresh it more frequently. In these scenarios it may be appropriate to investigate the use of a shared or a distributed caching mechanism.

When to Use this Pattern

Use this pattern when:

  • A cache does not provide native read-through and write-through operations.

  • Resource demand is unpredictable. This pattern enables applications to load data on demand. It makes no assumptions about which data an application will require in advance.

This pattern might not be suitable:

  • When the cached data set is static. If the data will fit into the available cache space, prime the cache with the data on startup and apply a policy that prevents the data from expiring.
  • For caching session state information in a web application hosted in a web farm. In this environment, you should avoid introducing dependencies based on client-server affinity.

4. Write Behind

In the Write-Behind scenario, modified cache entries are written to cache, not data source. Updates in cache are asynchronously written to the data source after a configured delay, whether after 10 seconds, 20 minutes, a day, a week or even longer. Note that this only applies to cache inserts and updates - cache entries are removed synchronously from the data source.

For Write-Behind caching, cache service maintains a write-behind queue of the data that must be updated in the data source. When the application updates X in the cache, X is added to the write-behind queue (if it isn’t there already; otherwise, it is replaced), and after the specified write-behind delay, cache service will update the underlying data source with the latest state of X. Note that the write-behind delay is relative to the first of a series of modifications—in other words, the data in the data source will never lag behind the cache by more than the write-behind delay.

The result is a read-once and write at a configured interval (that is, much less often) scenario. There are four main benefits to this type of architecture:

  • The application improves in performance, because the user does not have to wait for data to be written to the underlying data source. (The data is written later, and by a different execution thread.)

  • The application experiences drastically reduced database load: Since the amount of both read and write operations is reduced, so is the database load. The reads are reduced by caching, as with any other caching approach. The writes, which are typically much more expensive operations, are often reduced because multiple changes to the same object within the write-behind interval are coalesced and only written once to the underlying data source (write-coalescing). Additionally, writes to multiple cache entries may be combined into a single database transaction (write-combining) .

  • The application is somewhat insulated from database failures: the Write-Behind feature can be configured in such a way that a write failure will result in the object being re-queued for write. If the data that the application is using is in the cache, the application can continue operation without the database being up.

  • Linear Scalability: For an application to handle more concurrent users you need only increase the number of nodes in the cluster; the effect on the database in terms of load can be tuned by increasing the write-behind interval.

Write-behind strategy is actually Linux file system’s Page Cache. Because all updates are written asynchronously with a delay, Linux will lose some data updates when exit unexpectedly, e.g. machine being shut down.

Application

Developers can leverage all the strategies demonstrated above, and combine some of them together in when designing caching strategies. For example, you can have a Read-Through Write-Behind cache layer.


References:


Here’s the original post


看来,有很多人是不知道缓存同步的几个Design Pattern的,如:Cache aside, Read through, Write through, Write behind caching

看到好些人在写更新缓存数据代码时,先删除缓存,然后再更新数据库,而后续的操作会把数据再装载的缓存中。然而,这个是逻辑是错误的。试想,两个并发操作,一个是更新操作,另一个是查询操作,更新操作删除缓存后,查询操作没有命中缓存,先把老数据读出来后放到缓存中,然后更新操作更新了数据库。于是,在缓存中的数据还是老的数据,导致缓存中的数据是脏的,而且还一直这样脏下去了。

我不知道为什么这么多人用的都是这个逻辑,当我在微博上发了这个贴以后,我发现好些人给了好多非常复杂和诡异的方案,所以,我想写这篇文章说一下几个缓存更新的Design Pattern(让我们多一些套路吧)。

这里,我们先不讨论更新缓存和更新数据这两个事是一个事务的事,或是会有失败的可能,我们先假设更新数据库更新缓存都可以成功的情况(我们先把成功的代码逻辑先写对)。

更新缓存的的Design Pattern有四种:Cache aside, Read through, Write through, Write behind caching,我们下面一一来看一下这四种Pattern。

1. Cache Aside Pattern

这是最常用最常用的pattern了。其具体逻辑如下:

  • 失效:应用程序先从cache取数据,没有得到,则从数据库中取数据,成功后,放到缓存中。
  • 命中:应用程序从cache中取数据,取到后返回。
  • 更新:先把数据存到数据库中,成功后,再让缓存失效。

注意,我们的更新是先更新数据库,成功后,让缓存失效。

那么,这种方式是否可以没有文章前面提到过的那个问题呢?我们可以脑补一下。

一个是查询操作,一个是更新操作的并发,首先,没有了删除cache数据的操作了,而是先更新了数据库中的数据,此时,缓存依然有效,所以,并发的查询操作拿的是没有更新的数据,但是,更新操作马上让缓存的失效了,后续的查询操作再把数据从数据库中拉出来。而不会像文章开头的那个逻辑产生的问题,后续的查询操作一直都在取老的数据。

2. Read through / 3. Write Through Pattern

我们可以看到,在上面的 Cache Aside 套路中,我们的应用代码需要维护两个数据存储,一个是缓存(Cache),一个是数据库(Repository)。所以,应用程序比较啰嗦。而 Read/Write Through 套路是把更新数据库(Repository)的操作由缓存自己代理了,所以,对于应用层来说,就简单很多了。可以理解为,应用认为后端就是一个单一的存储,而存储自己维护自己的Cache。

Read Through

Read Through 套路就是在查询操作中更新缓存,也就是说,当缓存失效的时候(过期或LRU换出),Cache Aside 是由调用方负责把数据加载入缓存,而 Read Through 则用缓存服务自己来加载,从而对应用方是透明的。

Write Through

Write Through 套路和 Read Through 相仿,不过是在更新数据时发生。当有数据更新的时候,如果没有命中缓存,直接更新数据库,然后返回。如果命中了缓存,则更新缓存,然后再由 Cache 自己更新数据库(这是一个同步操作)

下图自来Wikipedia的Cache词条。其中的Memory你可以理解为就是我们例子里的数据库。

4. Write Behind Caching Pattern

Write Behind 又叫 Write Back。一些了解 Linux 操作系统内核的同学对 write back 应该非常熟悉,这不就是 Linux 文件系统的 Page Cache 的算法吗?是的,你看基础这玩意全都是相通的。所以,基础很重要,我已经不是一次说过基础很重要这事了。

Write Back 套路,一句说就是,在更新数据的时候,只更新缓存,不更新数据库,而我们的缓存会异步地批量更新数据库。这个设计的好处就是让数据的 I/O 操作飞快无比(因为直接操作内存嘛). 因为异步,write back 还可以合并对同一个数据的多次操作,所以性能的提高是相当可观的。

但是,其带来的问题是,数据不是强一致性的,而且可能会丢失(我们知道 Unix/Linux 非正常关机会导致数据丢失,就是因为这个事)。在软件设计上,我们基本上不可能做出一个没有缺陷的设计,就像算法设计中的时间换空间,空间换时间一个道理,有时候,强一致性和高性能,高可用和高性性是有冲突的。软件设计从来都是取舍 Trade-Off。

另外,Write Back 实现逻辑比较复杂, 因为他需要 track 有哪数据是被更新了的,需要刷到持久层上。操作系统的 write back 会在仅当这个cache需要失效的时候,才会被真正持久起来,比如,内存不够了,或是进程退出了等情况,这又叫 lazy write。

在 wikipedia 上有一张 write back 的流程图,基本逻辑如下:

Write-back_with_write-allocation

再多唠叨一些

  1. 上面讲的这些 Design Pattern,其实并不是软件架构里的 mysql 数据库和 memcache/redis 的更新策略,这些东西都是计算机体系结构里的设计,比如CPU的缓存,硬盘文件系统中的缓存,硬盘上的缓存,数据库中的缓存。基本上来说,这些缓存更新的设计模式都是非常老古董的,而且历经长时间考验的策略,所以这也就是,工程学上所谓的Best Practice,遵从就好了。

  2. 有时候,我们觉得能做宏观的系统架构的人一定是很有经验的,其实,宏观系统架构中的很多设计都来源于这些微观的东西。比如,云计算中的很多虚拟化技术的原理,和传统的虚拟内存不是很像么?Unix 下的那些 I/O 模型,也放大到了架构里的同步异步的模型,还有 Unix 发明的管道不就是数据流式计算架构吗?TCP 的好些设计也用在不同系统间的通讯中,仔细看看这些微观层面,你会发现有很多设计都非常精妙……所以,请允许我在这里放句观点鲜明的话——如果你要做好架构,首先你得把计算机体系结构以及很多老古董的基础技术吃透了。

  3. 在软件开发或设计中,我非常建议在之前先去参考一下已有的设计和思路,看看相应的 guideline,best practice 或 design pattern,吃透了已有的这些东西,再决定是否要重新发明轮子。千万不要似是而非地,想当然的做软件设计。

  4. 上面,我们没有考虑缓存(Cache)和持久层(Repository)的整体事务的问题。比如,更新 Cache 成功,更新数据库失败了怎么吗?或是反过来。关于这个事,如果你需要强一致性,你需要使用“两阶段提交协议”——prepare, commit/rollback,比如 Java 7 的 XAResource,还有 MySQL 5.7 的 XA Transaction,有些cache也支持XA,比如EhCache。当然,XA这样的强一致性的玩法会导致性能下降,关于分布式的事务的相关话题,你可以看看《分布式系统的事务处理》一文。