Designing a Distributed Cache

In this lesson, we will learn to design a distributed cache. We will also understand the tradeoffs and design choices that can occur while we progress in our journey towards developing a solution.

Design Requirements

Let us start by understanding the requirements of our solution.

Functional

Following are the functional requirements:

• Insert data: The user of distributed cache system must be able to insert an entry to the cache.
• Retrieve data: The user should be able to retrieve data corresponding to a specific key.

Non-functional requirements

We will consider the following non-functional requirements:

• High performance: The primary reason for the cache is to enable fast retrieval of data. Therefore, both the Insert and Retrieve operations must be fast.

• Scalable: The cache system should scale horizontally with no bottlenecks on an increasing number of requests.

• Highly available: The unavailability of the cache will put an extra burden on the database servers, which can also go down at peak load intervals. We also require our system to survive occasional failures of components/network/power outages.

• Consistency: Data stored on the cache servers should be consistent, i.e., different cache clients retrieving the same data from different cache servers (primary/secondary) should be up to date.

• Affordability: Ideally, the caching system should be designed from commodity hardware instead of spending a fortune over a supporting component within the design of a system.

API Design

The API design for this problem is sufficiently easy since there are only two basic operations.

The API call to perform insertion should look like this:

insert(key, value)

Where the value is the data stored against a unique key. We assume that the key is a string and the value is an object. This function will return an acknowledgment or an error depicting the problem at the server end.

The API call to retrieve data from the cache should look like this:

retrieve(key)

The key is used for finding the location of the value stored in a cache server. This call will return an object to the caller.

Design considerations

Before designing the distributed cache system, it is important to consider some design choices. Each of these choices will be purely based on our application requirements. However, we can highlight some key differences here:

• Storage hardware: Assuming our data is large, we may require sharding and hence use shard servers for cache partitions. A question arises: should these shard servers be specialized or commodity hardware? Specialized hardware will have good performance and storage capacity but it will cost higher. We can build a large cache from commodity serversFacebook has built a 28 TeraByte of cache using commodity machines in 2013.. In general, the number of shard servers will depend on the cache’s size and access frequency. Furthermore, we can consider storing our data on the secondary storage of these servers for persistence while we still serve data from RAM. Secondary storage may be used in cases where a reboot happens, and cache rebuilding takes a long time. Persistence, however, may not be a requirement in a cache system if there is a dedicated persistence layer (i.e. database).
• Data structures: A vital part of the design has to be the speed of accessing data. Hash tables are data structures that take a constant time on average to store and retrieve data. Furthermore, we need another data structure to enforce an eviction algorithm on the cached data. In particular, linked lists are a good option as discussed in the previous lesson. Also, we need to understand what kind of data structures a cache can store. Even though we discussed for simplicity sake in the API design section that we will use strings, it is possible to store different data structures/formats like Hashmaps, Arrays, Sets etc. within the cache. In the next lesson, we will see a practical example of such a cache.
• Cache Client: It is the client process/library that places the insert and retrieve calls. The location of the client process is a design issue. For example, it is possible to place the client process within a serving host if the cache is for internal use only. Otherwise, in the case where the caching system is provided as a service for external use, a dedicated cache client can send users’ requests to the cache servers.
• Writing policy: The writing strategy over the cache and database has consistency implications. In general, there is no optimal choice, but depending on your application, the preference of writing policy is significantly important.
• Eviction policy: By design cache provides low-latency reads (and writes). To achieve it, data is often served from RAM memory. Usually, we can’t put all the data in the cache due to the limited size of the cache as compared to the full dataset. So we need to carefully decide what stays in the cache and how to make room for new entries. With the addition of new data, some of the existing data may have to be evicted from the cache. However, choosing a victim entry depends on the eviction policy. Numerous eviction policies exist, but the choice again depends on the application using it. For instance, Least Recently Used (LRU) can be a good choice for social media services where recently uploaded content will likely get the most views.

Apart from the details above, optimizing the Time To Live (TTL) value can play an essential role in reducing the number of cache misses.

High-level design

The following depicts our high-level design:

The main components in this high-level design are:

1. The cache client library resides in the service application servers. It holds all the information regarding cache servers. The cache

...