System Design — Caching from Scratch (Part 1)
“There are only two hard things in Computer Science: cache invalidation and naming things.” — Phil Karlton
Introduction
In the world of system design, optimizing the performance of applications is a critical aspect. Caching plays a pivotal role in enhancing the speed and efficiency of systems by storing frequently accessed data in a location that allows for quicker retrieval. In this story, we will explore caching from the ground up, covering fundamental concepts.
What is Caching?
At its core, caching involves storing copies of frequently accessed data in a location that allows for quicker retrieval. This can significantly reduce the time it takes to fetch information, enhancing the overall performance of a system. Caches take advantage of the locality of reference principle “recently requested data is likely to be requested again”.
Basic Concepts of Caching
1. Cache
A cache is a high-speed data storage layer that stores a subset of data, typically transient in nature, to serve future requests more quickly. Caches can exist at various levels in a system, including hardware, software, and even within applications. In most simplified words — “A cache is like a short-term memory which has a limited amount of space.”
2. Cache Hit and Cache Miss
- Cache Hit: When the requested data is found in the cache, it’s termed a “cache hit.” This results in faster retrieval since the data is readily available.
- Cache Miss: If the requested data is not found in the cache, it’s a “cache miss.” In this case, the system needs to retrieve the data from the original source, potentially causing a delay.
3. Cache eviction policies
Following are some of the most common cache eviction policies:
- First In First Out (FIFO): The cache evicts the first block accessed first without any regard to how often or how many times it was accessed before.
- Last In First Out (LIFO): The cache evicts the block accessed most recently first without any regard to how often or how many times it was accessed before.
- Least Recently Used (LRU): Discards the least recently used items first.
- Most Recently Used (MRU): Discards, in contrast to LRU, the most recently used items first.
- Least Frequently Used (LFU): Counts how often an item is needed. Those that are used least often are discarded first.
- Random Replacement (RR): Randomly selects a candidate item and discards it to make space when necessary.
Caching Strategies
Now that we’ve laid the groundwork, let’s dive into various caching strategies and their applications.
1. Write-Through and Write-Behind Caching
1.1 Write-Through Caching
In a write-through caching strategy, every write operation to the system involves updating both the cache and the primary storage simultaneously. While this ensures data consistency, it might effect performance due to higher latency for write operations.
Example — Twitter, When a user posts a tweet, the tweet is immediately written to both the user’s timeline (cache) and it’s database. This ensures that the user’s timeline is always up-to-date, and any subsequent reads can quickly fetch the latest tweets directly from the cache. This approach prioritizes data consistency and minimizes the risk of displaying outdated information.
1.2 Write-Behind Caching
Write-behind caching involves updating the cache immediately upon a write request and then asynchronously updating the database. This can boost write performance but may introduce some level of data inconsistency between the cache and the underlying storage.
Example — Facebook, When a user makes a post, the post is first written to a cache. Meanwhile, in the background, the system asynchronously flushes batches of posts from the cache to the underlying database. This batching process allows the application to optimize the use of storage resources and reduce the impact of frequent, small writes to the database. It can improve overall system performance by aggregating multiple writes into larger, more efficient operations.
1.3 Write-around Caching
In this the write operations are bypassed from the cache and written directly to the database. In this approach, data is only cached on read requests, and write operations are sent directly to the storage, skipping the cache. This is done to avoid filling up the cache with write data that may not be frequently accessed.
Example — An application updates user profile information, which is infrequently accessed. The application writes the new data directly to the data store, avoiding unnecessary cache updates.
2. Cache Invalidation
Caches need to be kept in sync with the primary data source to avoid serving stale information. Cache invalidation strategies ensure that when data is updated or deleted in the primary storage, the corresponding data in the cache is invalidated or refreshed.
2.1 Time-Based Invalidation
In this approach, cached data is considered valid for a specific time duration. After this period elapses, the data is marked as stale, and the next access triggers a refresh from the primary storage.
2.2 Event-Based Invalidation
Event-based invalidation relies on notifications or events from the primary data source to signal changes. When data is updated or deleted, an event triggers the cache to update or remove the relevant entry.
3. Global vs Distributed Caching
Global Caching:
Global caching refers to caching data in a centralized location that is accessible globally. A single cache serves requests from users or applications regardless of their geographical location. This approach is often used in content delivery networks (CDNs) or global data centers.
Distributed Caching
As systems scale, caching at a single location may become insufficient. Distributed caching involves spreading the cache across multiple nodes or even geographically dispersed locations.
4. Real-world Examples
Let’s illustrate these concepts with real-world examples:
4.1 Content Delivery Networks (CDN)
CDNs leverage caching to distribute content geographically, reducing latency by serving content from servers closer to the end-users. This is a classic example of distributed caching.
4.2 Database Query Caching
In database systems, caching the results of frequently executed queries can significantly reduce response times. However, proper cache invalidation strategies must be in place to ensure data integrity.
5. Cache Compression
To maximize the efficiency of caching, some systems employ cache compression techniques. By reducing the size of cached data, compression minimizes storage requirements and can lead to faster data retrieval.
6 Cache Coherency
Maintaining cache coherency is crucial to prevent inconsistencies between multiple cache copies of the same data. Techniques such as write propagation and cache coherence protocols like MESI (Modified, Exclusive, Shared, Invalid) help ensure that all caches reflect the most recent data changes.
Case Study: Memcached
Introduction to Memcached
Memcached is a popular distributed memory caching system used to speed up dynamic web applications. It operates as an in-memory key-value store and is designed to be simple, fast, and scalable.
Key Features of Memcached
- Distributed Architecture: Memcached allows you to distribute the cache across multiple nodes, facilitating horizontal scalability.
- In-Memory Storage: Data is stored in RAM, providing ultra-fast access compared to traditional disk-based storage.
- Simple Key-Value Interface: Memcached follows a straightforward key-value storage model, making it easy to integrate into various applications.
Use Cases and Best Practices with Memcached
1. Session Storage
Memcached is often employed for session storage in web applications. By storing session data in-memory, it ensures quick access and seamless user experiences. (Note: that it is not persistent)
2. Full-Page Caching
In scenarios where entire pages can be cached, Memcached shines. This is particularly useful for reducing the load on backend servers in content-heavy websites.
Final Thoughts
In this story, I’ve covered the fundamentals of caching abd tried to explain a basic study of Memcached. Caching is powerful and is crucial for building high-performance scalable systems.
Clap & comment if you want more articles on system design topics. Share this article with your dev friends and those who want to learn system design!
