đŸȘŽ Quartz 4.0

Distributed Cache

Jan 12, 20255 min read

Read Strategies

Read-Through

  • Application first makes a read request to the cache
  • On a cache hit, the cached data is returned
  • On a cache miss, the cache makes a read request to the database and stores the data in the cache. Subsequent requests for this data will be cache hits

Advantages:

  • The cache contains only requested data, which helps keep the cache size small
  • As the application does not contact the database, the implementation burden of database requests is shifted to the cache

Disadvantages:

  • The cached data may become stale, especially if writes are made directly to the database. To reduce stale data, we can set a TTL

Cache-Aside

  • Application first makes a read request to the cache
  • On a cache hit, the cached data is returned
  • On a cache miss, the application makes a read request to the database. The cache is then populated with the data from the database, so subsequent requests for this data will be cache hits

Advantages:

  • The cache contains only requested data, which helps keep the cache size small

Disadvantages:

  • Each cache miss results in three roundtrips
  • The cached data may become stale, especially if writes are made directly to the database. To reduce stale data, we can set a TTL
  • Thundering herd problem on cache misses when accessing the database

Write Strategies

Write-Through

  • Application first writes data to the cache
  • Cache synchronously writes data to the database

Advantages:

Disadvantages:

  • Slower writes since every write is done to both the cache and DB
  • Most data is never read, so we incur unnecessary cost. We can configure a TTL to reduce wasted space

Write-Back (Write-Behind)

  • Application first writes data to the cache
  • Cache asynchronously writes data to the database

Advantages:

  • Faster writes on average than write-through. Writes to the DB are not blocking

Disadvantages:

  • Most data is never read, so we incur unnecessary cost. We can configure a TTL to reduce wasted space
  • Complex design because our cache must have high availability, so we cannot make tradeoffs against availability to improve performance or latency

Write-Around

  • Application writes data directly to the database
  • Cache is populated on cache misses using Read-Through or Cache-Aside strategies

Caching Pitfalls

Cache Stampede and Cache Avalanche

Cache stampede, also known as thundering herd, is a type of failure that occurs when a large number of read requests result in cache misses, causing a massive influx of traffic to the storage system. This surge of requests can overload the backend system or database, causing slowdowns or outages

Cache avalanche is a type of failure that happens when multiple or all cache entries expire simultaneously or within a short time window, leading to a sudden surge in requests to the underlying data store

Locking

To prevent multiple simultaneous processes from querying the storage system, a process will attempt to acquire a distributed lock for the cache key upon a cache miss. Only the process holding the lock will access the storage

There are different options for the case when the lock is not acquired:

  • Wait until the value is recomputed
  • Return a “not-found” and have the client handle the absence of the value properly
  • Keep a stale item in the cache to be used while the new value is recomputed

Probabilistic Early Expiration

In this approach, each process may decide to proactively refresh the cache based on a probability that increases as the value nears expiration. Since the probabilistic decision is made independently by each process, the effect of the stampede is mitigated as fewer processes will expire at the same time

See Optimal Probabilistic Cache Stampede Prevention for an algorithm specification

Staggered Expiration

For cache avalanche prevention, use staggered expiration by combining a base time-to-live (TTL) value with a random delta

Consistent Hashing

Consistent hashing can be used to distribute cache entries across multiple cache servers evenly. It reduces the impact of cache avalanche and cache stampede by sharing the load among the servers

Circuit Breakers and Rate Limiting

Implementing circuit breakers and rate limiting in the system can help prevent cache avalanche and cache stampede from escalating into more severe issues

Cache Penetration

Cache penetration happens when requested data is missing in both the cache and database, causing requests to skip the cache and hit the database. Repeated requests for nonexistent keys can lead to cache misses and overload the database

Null Values

Store a placeholder value, such as null, in the cache to represent nonexistent data. Subsequent requests for the same data will result in a cache hit, and the application can handle null values. Set an appropriate TTL for these placeholder entries to prevent them from occupying cache space indefinitely

Bloom Filter

When a record is added to storage, its key is also stored in a Bloom filter. When fetching a record, the application first checks the Bloom filter. If the key is not found, it doesn’t exist in the cache or storage either, and the application returns a null value. If the key is found, the application checks the cache and storage. Since a Bloom filter can have false positives, some cache reads may still result in a miss

References

Graph View

Backlinks

  • No backlinks found