Explore

Application Caching Strategies

Canh Nguyen Xuan

Overview

What is caching?

A cache: A high-speed data storage layer which stores a subset of data.

Caching allows efficiently reuse previously retrieved or computed data.

Caching types

Hardware caches

CPU caches: L1, L2, L3, TLB.

GPU caches

Hard drive caches

Software caches:

OS: Page caches

DNS

CDN

Database cache

HTTP cache

Server application cache

HTTP caching

⁠

https://developer.mozilla.org/en-US/docs/Web/HTTP/Caching⁠

⁠

https://www.freecodecamp.org/news/an-in-depth-introduction-to-http-caching-cache-control-vary/⁠

⁠

Usage

Use Cache-Control header:

No caching:

Cache-Control: no-store

Cache but revalidate:

Cache-Control: no-cache

Private cache:

Cache-Control: private

Public cache:

Cache-Control: public

Expiration:

Cache-Control: max-age=<seconds>

Must revalidate:

Cache-Control: must-revalidate

Cache validation:

ETag

Response header: ETag

ETag: "33a64df551425fcc55e4d42a148795d9f25f89d4" // Strong validator

ETag: W/"67ab43" // Week validator

Request header: If-None-Match

If-None-Match: "bfc13a64729c4290ef5b2c2730249c88ca92d82d"

If-None-Match: W/"67ab43", "54ed21", "7892dd"

If-None-Match: *

Last-Modified:

Response header: Last-Modified

Last-Modified: Wed, 21 Oct 2015 07:28:00 GMT

Request header:

If-Modified-Since: Wed, 21 Oct 2015 07:28:00 GMT

Strategies

Week validation vs strong validation:

Strong validation consists of guaranteeing that the resource is, byte to byte, identical to the one it is compared to.

Weak validation considers two versions of the document as identical if the content is equivalent. For example, a page that would differ from another only by a different date in its footer, would be considered identical to the other with weak validation.

⁠

Revved resources⁠

Infrequently updated files are named in a specific way: in their URL, usually in the filename, a revision (or version) number is added.

Varying responses:

⁠

https://www.smashingmagazine.com/2017/11/understanding-vary-header/⁠

Vary HTTP response header describes the parts of the request message aside from the method and URL that influenced the content of the response it occurs in

Vary: *

Vary: <header-name>, <header-name>, ...

Vary: Accept-Encoding

Normalization: Caching servers will by default match future requests only to requests with exactly the same headers and header values. To avoid unnecessary requests and duplicated cache entries, caching servers should use normalization to pre-process the request and cache only files that are needed.

Accept-Encoding: gzip,deflate,sdch

Accept-Encoding: gzip,deflate, Accept-Encoding: gzip

// Normalize Accept-Encoding

if (req.http.Accept-Encoding) {

if (req.http.Accept-Encoding ~ "gzip") {

set req.http.Accept-Encoding = "gzip";

}

// elseif other encoding types to check

else {

unset req.http.Accept-Encoding;

}

Database cache

Avoid using MySQL query cache (for version < 5.7.20):

Enabling the query cache adds some overhead for both reads and writes: (From High Performance MySQL v3):

Read queries must check the cache before beginning.

If the query is cacheable and isn’t in the cache yet, there’s some overhead due to storing the result after generating it.

There’s overhead for write queries, which must invalidate the cache entries for queries that use tables they change. Invalidation can be very costly if the cache is fragmented and/or large (has many cached queries, or is configured to use a large amount of memory).

Server application caching

Cache types

⁠

https://docs.microsoft.com/en-us/azure/architecture/best-practices/caching⁠

⁠

Local cache

⁠

Shared cache

⁠

Using a shared cache

Eviction Policies

Size-based Eviction

Random

LRU

LFU

FIFO

Frequency and recency (

Window⁠

⁠

Tiny LFU⁠

another resource⁠

)

Time-based Eviction

TTL after read/write.

After an exact time.

Caching strategies

⁠

https://github.com/donnemartin/system-design-primer#application-caching⁠

⁠

https://hazelcast.com/blog/a-hitchhikers-guide-to-caching-patterns/⁠

⁠

https://aws.amazon.com/caching/best-practices/⁠

⁠

https://twitter.com/alexxubyte/status/1499428315429412864age⁠

Cache-aside

⁠

Pros:

Only requested data is cached.

Node failures aren't fatal for your application.

Cons:

Cache stampede when cache miss.

Stale data.

Read through/Write-through

⁠

Pros:

Data in the cache is never stale.

It simplifies cache expiration.

Cons:

Cache can be filled with unnecessary objects.

When cache nodes fail, cached objects may no longer be in the cache.

Implementation:

In the application layer.

Use Hazelcast/Ignite

⁠

https://ignite.apache.org/docs/latest/persistence/external-storage#:~:text=Write%2Dthrough%20means%20that%20the,rolled%20back%20as%20a%20whole⁠

⁠

Write-behind (write-back)

⁠

Refresh-ahead

Use Change Data Capture (CDC) pattern, listen to changes from databases and refresh related cache data.

Use a cron job to periodically refresh cache data.

Cache data

⁠

https://guides.rubyonrails.org/caching_with_rails.html#basic-caching⁠

⁠

https://docs.microsoft.com/en-us/aspnet/core/performance/caching/overview?view=aspnetcore-6.0⁠

⁠

HTTP Response:

Page caching

Fragment Caching

Objects:

Query results.

Result of expensive calculation.

Should use binary format like msgpack, cbor, bson.

User sessions.

Concerns when using cache

Monitoring:

Cache hit/miss rates.

Cach eviction rates.

Replication lag.

Consistency vs Performance

Strong consistency vs Eventual consistency.

Consider read-after-write consistency.

Cache stampede

From

https://betterprogramming.pub/how-a-cache-stampede-caused-one-of-facebooks-biggest-outages-dbb964ffc8ed⁠

⁠

A substantial number of concurrent threads get a cache miss, leading to them all calling the database.

The database crashes due to an enormous CPU spike and leads to timeout errors.

Receiving the timeout, all the threads retry their requests — causing another stampede.

On and on the cycle continues.

Solutions:

Use multiple cache layers.

⁠

Locks & Promises⁠

Early recomputation.

Cache Scaling

Horizontal scaling

Sharding:

Proxies:

Codis⁠

Twemproxy⁠

mcrouter⁠

⁠

Distributed databases:

Redis cluster⁠

Apache Ignite⁠

Apache Hazelcast⁠

⁠

Case Studies

Facebook (2013)

⁠

https://www.usenix.org/system/files/conference/nsdi13/nsdi13-final170_update.pdf⁠

⁠

Overall Architecture:

⁠

In a region replication:

⁠

Cache Invalidation

Across region consistency:

Read-after-write consistency.

Use remote marker: (

Source⁠

)

Set a remote marker rk in the regional pool. Think of rk as a memcache record that represents extra information for key k.

Send the write to the primary region and include rk in the request, so that the primary knows to invalidate rk when it replicates the write.

Delete k in the local cluster.

Netflix (2016)

⁠

https://www.youtube.com/watch?v=Rzdxgx3RC0Q&⁠

⁠

Server application caching

Concerns when using cache

Case Studies

Facebook (2013)

Netflix (2016)

Want to print your doc?
This is not the way.

Try clicking the ⋯ next to your doc name or using a keyboard shortcut (

CtrlP

) instead.