System Desing Primer

Question 1

Performance vs scalability

Answer 1

A service is scalable if it results in increased performance in a manner proportional to resources added. Generally, increasing performance means serving more units of work, but it can also be to handle larger units of work, such as when datasets grow.1

Another way to look at performance vs scalability:

If you have a performance problem, your system is slow for a single user.
If you have a scalability problem, your system is fast for a single user but slow under heavy load.

Question 2

Latency vs throughput

Answer 2

Latency is the time to perform some action or to produce some result.

Throughput is the number of such actions or results per unit of time.

Generally, you should aim for maximal throughput with acceptable latency.

Question 3

Define Elements of CAP

Briefly explain it

Discuss dimensions

Answer 3

In a distributed computer system, you can only support two of the following guarantees:

Consistency - Every read receives the most recent write or an error
Availability - Every request receives a response, without guarantee that it contains the most recent version of the information
Partition Tolerance - The system continues to operate despite arbitrary partitioning due to network failures
Networks aren’t reliable, so you’ll need to support partition tolerance. You’ll need to make a software tradeoff between consistency and availability.

CP - consistency and partition tolerance
Waiting for a response from the partitioned node might result in a timeout error. CP is a good choice if your business needs require atomic reads and writes.

AP - availability and partition tolerance
Responses return the most readily available version of the data available on any node, which might not be the latest. Writes might take some time to propagate when the partition is resolved.

AP is a good choice if the business needs to allow for eventual consistency or when the system needs to continue working despite external errors.

Question 4

Consistency Patterns

Answer 4

Recall the definition of consistency from the CAP theorem - Every read receives the most recent write or an error.

Weak consistency
After a write, reads may or may not see it. A best effort approach is taken.

This approach is seen in systems such as memcached. Weak consistency works well in real time use cases such as VoIP, video chat, and realtime multiplayer games. For example, if you are on a phone call and lose reception for a few seconds, when you regain connection you do not hear what was spoken during connection loss.

Eventual consistency
After a write, reads will eventually see it (typically within milliseconds). Data is replicated asynchronously.

This approach is seen in systems such as DNS and email. Eventual consistency works well in highly available systems.

Strong consistency
After a write, reads will see it. Data is replicated synchronously.

This approach is seen in file systems and RDBMSes. Strong consistency works well in systems that need transactions.

Question 5

Discuss Availability Patterns with Disadvantages

Answer 5

Fail-over
Active-passive
With active-passive fail-over, heartbeats are sent between the active and the passive server on standby. If the heartbeat is interrupted, the passive server takes over the active’s IP address and resumes service.

The length of downtime is determined by whether the passive server is already running in ‘hot’ standby or whether it needs to start up from ‘cold’ standby. Only the active server handles traffic.

Active-passive failover can also be referred to as master-slave failover.

Active-active
In active-active, both servers are managing traffic, spreading the load between them.

If the servers are public-facing, the DNS would need to know about the public IPs of both servers. If the servers are internal-facing, application logic would need to know about both servers.

Active-active failover can also be referred to as master-master failover.

Disadvantage(s): failover
Fail-over adds more hardware and additional complexity.
There is a potential for loss of data if the active system fails before any newly written data can be replicated to the passive.

Question 6

What is DNS?

Answer 6

A Domain Name System (DNS) translates a domain name such as www.example.com to an IP address.

DNS is hierarchical, with a few authoritative servers at the top level. Your router or ISP provides information about which DNS server(s) to contact when doing a lookup. Lower level DNS servers cache mappings, which could become stale due to DNS propagation delays. DNS results can also be cached by your browser or OS for a certain period of time, determined by the time to live (TTL).

Question 7

What are different types of DNS records?

Answer 7

NS record (name server) - Specifies the DNS servers for your domain/subdomain.

MX record (mail exchange) - Specifies the mail servers for accepting messages.

A record (address) - Points a name to an IP address.

CNAME (canonical) - Points a name to another name or CNAME (example.com to www.example.com) or to an A record.

Question 8

Name a few patterns for DNS routing

Answer 8

Weighted round robin
Prevent traffic from going to servers under maintenance
Balance between varying cluster sizes
A/B testing

Latency-based

Geolocation-based

Question 9

DNS disadvantages

Answer 9

Accessing a DNS server introduces a slight delay, although mitigated by caching described above.

DNS server management could be complex and is generally managed by governments, ISPs, and large companies.

DNS services have recently come under DDoS attack, preventing users from accessing websites such as Twitter without knowing Twitter’s IP address(es).

Question 10

What is CDN?

Answer 10

A content delivery network (CDN) is a globally distributed network of proxy servers, serving content from locations closer to the user. Generally, static files such as HTML/CSS/JS, photos, and videos are served from CDN, although some CDNs such as Amazon’s CloudFront support dynamic content. The site’s DNS resolution will tell clients which server to contact.

Question 11

How does CDN improves performance?

Answer 11

Serving content from CDNs can significantly improve performance in two ways:

Users receive content from data centers close to them
Your servers do not have to serve requests that the CDN fulfills

Question 12

What are the CDN types? Explain

Answer 12

Push CDNs
Push CDNs receive new content whenever changes occur on your server. You take full responsibility for providing content, uploading directly to the CDN and rewriting URLs to point to the CDN. You can configure when content expires and when it is updated. Content is uploaded only when it is new or changed, minimizing traffic, but maximizing storage.

Sites with a small amount of traffic or sites with content that isn’t often updated work well with push CDNs. Content is placed on the CDNs once, instead of being re-pulled at regular intervals.

Pull CDNs
Pull CDNs grab new content from your server when the first user requests the content. You leave the content on your server and rewrite URLs to point to the CDN. This results in a slower request until the content is cached on the CDN.

A time-to-live (TTL) determines how long content is cached. Pull CDNs minimize storage space on the CDN, but can create redundant traffic if files expire and are pulled before they have actually changed.

Sites with heavy traffic work well with pull CDNs, as traffic is spread out more evenly with only recently-requested content remaining on the CDN.

Question 13

CDN disadvantages?

Answer 13

CDN costs could be significant depending on traffic, although this should be weighed with additional costs you would incur not using a CDN.

Content might be stale if it is updated before the TTL expires it.

CDNs require changing URLs for static content to point to the CDN.

Question 14

What is load balancer?

Answer 14

Load balancers distribute incoming client requests to computing resources such as application servers and databases. In each case, the load balancer returns the response from the computing resource to the appropriate client.

Load balancers can be implemented with hardware (expensive) or with software such as HAProxy.

Question 15

What are the benefits of load balancer?

Answer 15

Load balancers are effective at:

Preventing requests from going to unhealthy servers

Preventing overloading resources

Helping to eliminate a single point of failure

Additional benefits include:

SSL termination - Decrypt incoming requests and encrypt server responses so backend servers do not have to perform these potentially expensive operations

Removes the need to install X.509 certificates on each server

Session persistence - Issue cookies and route a specific client’s requests to same instance if the web apps do not keep track of sessions

Question 16

How to protect load balancers against failures?

Answer 16

To protect against failures, it’s common to set up multiple load balancers, either in active-passive or active-active mode.

Question 17

Load Balancer traffic routing patterns?

Answer 17

Load balancers can route traffic based on various metrics, including:

Random
Least loaded
Session/cookies
Round robin or weighted round robin
Layer 4
Layer 7

Question 18

Layer 4 Load Balancing

Answer 18

Operates at: Transport layer (OSI model)

Decisions based on: Source/destination IP addresses and ports (TCP/UDP segment headers)
Analogy: Mailroom sorting packages by address

Characteristics:
Fast and efficient
Simple to configure
Limited functionality (no content awareness)

Use Cases:
Balancing traffic for TCP/UDP applications (web, email, database servers)
Improving performance and availability
Providing failover

Benefits:
Improved performance
Increased availability
Enhanced scalability
Simplified management

Limitations:
No content awareness
Limited traffic management features

Question 19

Layer 7 Load Balancing

Answer 19

Operates at: Application layer (OSI model)

Decisions based on: HTTP headers, URLs, cookies, application-specific data

Analogy: Intelligent receptionist directing visitors based on their purpose and appointment details

Characteristics:
Advanced traffic management
Content-aware
More resource-intensive

Use Cases:
Routing traffic based on user location, type of content, or application
Implementing security policies (e.g., web application firewall)
Optimizing content delivery (e.g., caching)

Benefits:
Increased flexibility and control
Improved security
Optimized performance
Enhanced user experience

Limitations:
Increased complexity
Higher resource consumption

Question 20

Load Balancer Disadvantages

Answer 20

The load balancer can become a performance bottleneck if it does not have enough resources or if it is not configured properly.

Introducing a load balancer to help eliminate a single point of failure results in increased complexity.

A single load balancer is a single point of failure, configuring multiple load balancers further increases complexity.

Question 21

Disadvantages of horizontal scaling

Answer 21

Scaling horizontally introduces complexity and involves cloning servers
Servers should be stateless: they should not contain any user-related data like sessions or profile pictures
Sessions can be stored in a centralized data store such as a database (SQL, NoSQL) or a persistent cache (Redis,
Memcached)

Downstream servers such as caches and databases need to handle more simultaneous connections as upstream servers scale out

Question 22

Reverse Proxy + Benefits

Answer 22

A reverse proxy is a web server that centralizes internal services and provides unified interfaces to the public. Requests from clients are forwarded to a server that can fulfill it before the reverse proxy returns the server’s response to the client.

Additional benefits include:

Increased security - Hide information about backend servers, blacklist IPs, limit number of connections per client

Increased scalability and flexibility - Clients only see the reverse proxy’s IP, allowing you to scale servers or change their configuration

SSL termination - Decrypt incoming requests and encrypt server responses so backend servers do not have to perform these potentially expensive operations
Removes the need to install X.509 certificates on each server

Compression - Compress server responses

Caching - Return the response for cached requests

Static content - Serve static content directly
HTML/CSS/JS
Photos
Videos
Etc

How to remmember:

S.C.O.R.F.S

Security - Hide information about backend servers, blacklist IPs, limit number of connections per client
Compression - Compress server responses to improve load times.
Offloading - This now represents SSL termination, emphasizing that the reverse proxy handles the encryption/decryption workload.
Resilience - Increased scalability and flexibility; clients only see the reverse proxy’s IP, allowing you to scale servers or change their configuration without affecting them.
Fast Content - Caching (Return the response for cached requests)
Static Content - Serve static content directly (HTML/CSS/JS, Photos, Videos, etc.)

Question 23

Load balancer vs reverse proxy

Answer 23

Deploying a load balancer is useful when you have multiple servers. Often, load balancers route traffic to a set of servers serving the same function.

Reverse proxies can be useful even with just one web server or application server, opening up the benefits described in the previous section.

Solutions such as NGINX and HAProxy can support both layer 7 reverse proxying and load balancing.

Question 24

Reverse Proxy Disadvantages

Answer 24

Introducing a reverse proxy results in increased complexity.

A single reverse proxy is a single point of failure, configuring multiple reverse proxies (ie a failover) further increases complexity.

Question 25

What is ACID?

Answer 25

ACID is a set of properties of relational database transactions.

Atomicity - Each transaction is all or nothing
Consistency - Any transaction will bring the database from one valid state to another
Isolation - Executing transactions concurrently has the same results as if the transactions were executed serially
Durability - Once a transaction has been committed, it will remain so

Question 26

Techniques to scale relational databases

Answer 26

master-slave replication, master-master replication, federation, sharding, denormalization, and SQL tuning

Question 27

Explain Master-Slave replication

Answer 27

The master serves reads and writes, replicating writes to one or more slaves, which serve only reads. Slaves can also replicate to additional slaves in a tree-like fashion. If the master goes offline, the system can continue to operate in read-only mode until a slave is promoted to a master or a new master is provisioned.

Source: Scalability, availability, stability, patterns

Disadvantage(s): master-slave replication
Additional logic is needed to promote a slave to a master.
See Disadvantage(s): replication for points related to both master-slave and master-master.

Note: in the read-only mode, we can queue up write operation and process them once master is online
If there is no queue, then we lose writes.
if there is queue, we can process them later and offer a good balance of availability and eventual consistency

The alternative is having a leader election process and promote one slave to be master.
This can lead to poor availability during election process. We can mitigate the availability with a write queue and guarantee eventual consistency.

we can combine master-master and master-slave techniques for more resiliency in read and writes. Though, syncronization between read replicas during times of failure is complex

Question 28

Explain Master-Master replication

Answer 28

Master-master replication
Both masters serve reads and writes and coordinate with each other on writes. If either master goes down, the system can continue to operate with both reads and writes.

Disadvantage(s): master-master replication
You’ll need a load balancer or you’ll need to make changes to your application logic to determine where to write.

Most master-master systems are either loosely consistent (violating ACID) or have increased write latency due to synchronization.

Conflict resolution comes more into play as more write nodes are added and as latency increases.

Question 29

Disadvantages of replication in generall

Answer 29

There is a potential for loss of data if the master fails before any newly written data can be replicated to other nodes.

Writes are replayed to the read replicas. If there are a lot of writes, the read replicas can get bogged down with replaying writes and can’t do as many reads.

The more read slaves, the more you have to replicate, which leads to greater replication lag.

On some systems, writing to the master can spawn multiple threads to write in parallel, whereas read replicas only support writing sequentially with a single thread.

Replication adds more hardware and additional complexity.

Question 30

Explain Database Federation

Answer 30

Federation (or functional partitioning) splits up databases by function. For example, instead of a single, monolithic database, you could have three databases: forums, users, and products, resulting in less read and write traffic to each database and therefore less replication lag. Smaller databases result in more data that can fit in memory, which in turn results in more cache hits due to improved cache locality. With no single central master serializing writes you can write in parallel, increasing throughput.

Disadvantage(s): federation
Federation is not effective if your schema requires huge functions or tables.

You’ll need to update your application logic to determine which database to read and write.

Joining data from two databases is more complex with a server link.

Federation adds more hardware and additional complexity.

Question 31

Explain Sharding

Answer 31

Sharding distributes data across different databases such that each database can only manage a subset of the data. Taking a users database as an example, as the number of users increases, more shards are added to the cluster.

Similar to the advantages of federation, sharding results in less read and write traffic, less replication, and more cache hits. Index size is also reduced, which generally improves performance with faster queries. If one shard goes down, the other shards are still operational, although you’ll want to add some form of replication to avoid data loss. Like federation, there is no single central master serializing writes, allowing you to write in parallel with increased throughput.

Common ways to shard a table of users is either through the user’s last name initial or the user’s geographic location.

Disadvantage(s): sharding
You’ll need to update your application logic to work with shards, which could result in complex SQL queries.
Data distribution can become lopsided in a shard. For example, a set of power users on a shard could result in increased load to that shard compared to others.
Rebalancing adds additional complexity. A sharding function based on consistent hashing can reduce the amount of transferred data.
Joining data from multiple shards is more complex.
Sharding adds more hardware and additional complexity.

Question 32

Token Bucket Algorithm

Answer 32

• Bucket Size: Max tokens allowed in the bucket.
• Refill Rate: Tokens added per second.
• How it works:
1. Tokens added to bucket periodically until full.
2. Each request uses 1 token.
3. If enough tokens → request goes through; otherwise, dropped.
4. Allows traffic bursts if tokens available.
• Examples:
• Different APIs or IP addresses need separate buckets.
• Global bucket for shared requests (e.g., max 10,000/sec).

Pros: Easy to implement, memory efficient, supports bursts.
Cons: Tuning bucket size and refill rate can be tricky.

Question 33

Leaky Bucket Algorithm

Answer 33

Definition:
The leaking bucket algorithm processes requests at a fixed rate, usually implemented with a first-in-first-out (FIFO) queue.

How it works:

1.	A request arrives.
2.	If the queue is not full, the request is added.
3.	If the queue is full, the request is dropped.
4.	Requests are processed from the queue at regular intervals.

Key Parameters:

•	Bucket size: Equal to the queue size (limits how many requests can be held).
•	Outflow rate: Defines how many requests can be processed per second.

Pros:

•	Memory-efficient (limited queue size).
•	Provides a stable outflow rate.

Cons:

•	Burst traffic can fill the queue, causing recent requests to be dropped.
•	Requires careful tuning of parameters.

Example:
Used by Shopify for rate-limiting.

Question 34

Fixed Window Counter Algorithm

Answer 34

Definition:
The fixed window counter algorithm divides the timeline into fixed-size windows, using a counter for each window to track requests.

How it works:

1.	The timeline is divided into time windows (e.g., 1 second, 1 minute).
2.	Each request increments the counter by one.
3.	Once the counter hits a pre-defined threshold, new requests are dropped until the next window starts.

Key Problem:
A traffic burst near the edges of windows can allow more requests than the set limit.

Example:
If the system allows 3 requests per second, any additional requests beyond 3 in a second are dropped.

Pros:

•	Memory-efficient.
•	Easy to implement.
•	Works well for use cases with natural time windows.

Cons:

•	Traffic spikes at window edges can exceed the allowed quota, letting more requests through.

Question 35

Denormalization: advantages & disadvantages

Answer 35

Denormalization
Denormalization attempts to improve read performance at the expense of some write performance. Redundant copies of the data are written in multiple tables to avoid expensive joins. Some RDBMS such as PostgreSQL and Oracle support materialized views which handle the work of storing redundant information and keeping redundant copies consistent.

Once data becomes distributed with techniques such as federation and sharding, managing joins across data centers further increases complexity. Denormalization might circumvent the need for such complex joins.

In most systems, reads can heavily outnumber writes 100:1 or even 1000:1. A read resulting in a complex database join can be very expensive, spending a significant amount of time on disk operations.

Disadvantage(s): denormalization
Data is duplicated.
Constraints can help redundant copies of information stay in sync, which increases complexity of the database design.
A denormalized database under heavy write load might perform worse than its normalized counterpart.

Question 36

What is NoSQL?
Explain BASE

Answer 36

NoSQL is a collection of data items represented in a key-value store, document store, wide column store, or a graph database. Data is denormalized, and joins are generally done in the application code. Most NoSQL stores lack true ACID transactions and favor eventual consistency.

BASE is often used to describe the properties of NoSQL databases. In comparison with the CAP Theorem, BASE chooses availability over consistency.

Basically available - the system guarantees availability.
Soft state - the state of the system may change over time, even without input.
Eventual consistency - the system will become consistent over a period of time, given that the system doesn’t receive input during that period.

Question 37

Explain Key-Value store in NoSQL databases

Answer 37

Abstraction: hash table

A key-value store generally allows for O(1) reads and writes and is often backed by memory or SSD. Data stores can maintain keys in lexicographic order, allowing efficient retrieval of key ranges. Key-value stores can allow for storing of metadata with a value.

Key-value stores provide high performance and are often used for simple data models or for rapidly-changing data, such as an in-memory cache layer. Since they offer only a limited set of operations, complexity is shifted to the application layer if additional operations are needed.

Example: DynamoDB, Memcached, Reddis

Question 38

What is Document Store?

Answer 38

Abstraction: A key-value store where the values are documents.
Data Storage: Stores data in documents (e.g., JSON, XML, binary). Each document contains all the information for a single object.
Organization: Documents can be organized using collections, tags, metadata, or directories.
Flexibility: Documents within a store can have different structures.
Querying: Offers APIs or query languages to search based on the document’s internal structure.
Examples: MongoDB, CouchDB, DynamoDB (supports both key-values and documents)
Key Features to Remember:

Focuses on storing complete information about an object in a single document.
Provides flexible schema design.
Often uses APIs or query languages for efficient retrieval of information within documents.

Question 39

What is a wide column store?

Answer 39

Abstraction: ColumnFamily<RowKey, Columns<ColKey, Value, Timestamp» (Think of it as a nested map or a table with rows and columns).
Basic Unit: Column (name/value pair)
Organization:
Columns grouped into column families (similar to SQL tables).
Column families can be further grouped into super column families.
Access:
Access individual columns with a row key.
Columns with the same row key form a row.
Versioning: Each value has a timestamp for versioning and conflict resolution.
Key Features: High availability, high scalability, efficient retrieval of key ranges.
Examples: Bigtable, HBase, Cassandra
Common Use Cases: Storing and managing very large datasets.
Key Concepts to Remember:

Data is organized into columns and column families.
Row keys are used to access data.
Timestamps are crucial for versioning and data consistency.
Designed for scalability and availability.

Note that this database is good for doing a range of analysis in a column (data scientists analyzing XXX)

Question 40

What is a graph database?

Answer 40

Abstraction: Graph (nodes and edges)
Components:
Nodes: Represent entities (e.g., people, products, places).
Arcs/Edges: Represent relationships between nodes (e.g., “friends with,” “purchased,” “located in”).
Strengths:
Optimized for complex relationships (many-to-many, intricate connections).
High performance for data with interconnected relationships.
Use Cases: Social networks
Challenges:
Relatively new technology.
Limited development tools and resources compared to other databases.
Many rely on REST APIs for access.

Key Concepts to Remember:

Focuses on relationships between data.
Excellent for highly interconnected data.
Provides efficient traversal and querying of relationships.
Still maturing in terms of tooling and widespread adoption.

Other notes:
In this database, we have two tables: Nodes and edges
Nodes table has information about a node with a reference to physical address of a corresponding edge

The edge table has physical address of itself, physicall adress of the node it points to, and a pointer (physicall address) to the next edge.

The edge can also store some information.

More information: https://www.youtube.com/watch?v=Sdw_D-Gllac

Question 41

What are some key reasons to choose SQL vs. NoSQL?

Answer 41

SQL

Strengths:
Structured data with a strict schema
Relational data with complex joins
Transactions for data consistency
Established ecosystem (developers, tools, etc.)
Fast lookups by index
Clear scaling patterns

NoSQL

Strengths:
Semi-structured data with flexible schema
Non-relational data
High scalability for large datasets
Very high throughput for I/O operations
Good for:
Rapid ingest of clickstream/log data
Leaderboard/scoring data
Temporary data (e.g., shopping carts)
Frequently accessed (“hot”) tables
Metadata/lookup tables

Question 42

Consisten Hashing Implementation in Python

Answer 42

import hashlib
import bisect

class ConsistentHashing:
def __init__(self, num_replicas=3):
# Number of virtual nodes per real node
self.num_replicas = num_replicas
self.ring = {} # This is where we store the hash value for each node
self.sorted_keys = [] # Sorted list of hash values (keys in the ring)

def _hash_function(self, key):
    # Use MD5 hash function to generate a hash value for the key
    m = hashlib.md5()
    m.update(key.encode('utf-8'))
    return int(m.hexdigest(), 16)

def add_node(self, node):
    # Add node along with its replicas to the ring
    for i in range(self.num_replicas):
        virtual_node = f"{node}#{i}"
        hashed_key = self._hash_function(virtual_node)
        self.ring[hashed_key] = node
        bisect.insort(self.sorted_keys, hashed_key)

def remove_node(self, node):
    # Remove node along with its replicas from the ring
    for i in range(self.num_replicas):
        virtual_node = f"{node}#{i}"
        hashed_key = self._hash_function(virtual_node)
        if hashed_key in self.ring:
            del self.ring[hashed_key]
            index = bisect.bisect_left(self.sorted_keys, hashed_key)
            self.sorted_keys.pop(index)

def get_node(self, key):
    # Get the node responsible for the given key
    if not self.ring:
        return None
    
    hashed_key = self._hash_function(key)
    index = bisect.bisect(self.sorted_keys, hashed_key) % len(self.sorted_keys)
    return self.ring[self.sorted_keys[index]]

Example usage
if __name__ == “__main__”:
# Initialize consistent hashing with 3 virtual nodes per real node
ch = ConsistentHashing(num_replicas=3)

# Add some nodes
ch.add_node("Node1")
ch.add_node("Node2")
ch.add_node("Node3")

# Find which node a key maps to
print("Key1 is mapped to:", ch.get_node("Key1"))
print("Key2 is mapped to:", ch.get_node("Key2"))
print("Key3 is mapped to:", ch.get_node("Key3"))

# Remove a node
ch.remove_node("Node2")
print("After removing Node2...")

# Find which node a key maps to after removing a node
print("Key1 is mapped to:", ch.get_node("Key1"))
print("Key2 is mapped to:", ch.get_node("Key2"))
print("Key3 is mapped to:", ch.get_node("Key3"))

Question 43

What is the Cache-Aside strategy?

Answer 43

Definition: Data is loaded into the cache only when it’s requested by the application.

Process:
Application checks cache for data.
If data is present (cache hit), return it.
If data is missing (cache miss), fetch from database, store in cache, and return it.

Advantages:
Cost-effective cache size (only stores requested data).
Simple implementation with immediate performance gains.

Disadvantages:
Initial requests for new data are slower due to extra database and cache roundtrips.
Example: A web server caching frequently accessed web pages.

Note: Often combined with Write-Through caching for optimal performance. If not, data can become stale

If we use only cache-aside strategy (FASTER WRITES) for both read/write, then we might end up with stale entries after an update happens to the database(race condition between concurrent requests).
One solution:
Updates go only to the database
cache receives a signal from database that an entry is invalidated.
Another read requests will update the entry in cache

This is complex. See Facebook memcache paper for more info.

Question 44

What is the Write-Through caching strategy?

Note (this can be extended to read through as well)

Answer 44

Definition: Data is written to the cache first and then to the database. The cache acts as an intermediary between the application and the database. Every time an application writes data to the cachethe thread waits in this pattern until the write to the database is also completed.

Process:
1. The application reads and writes data to cache.
2. Cache syncs any changed data to the database synchronously/immediately.
For Reddis, the Redis server is blocked until a response from the main database is received.

Advantages:
Ensures strong consistency between cache and database.
Reduces database write load as all writes go through the cache.

Disadvantages:
Write latency can be higher as each write involves updating both the cache and the database.
Example: A financial application where data consistency is crucial.

Usecases:

• E-commerce application: In an e-commerce application, write-through caching can be used to ensure consistency of product inventory. Whenever a customer purchases a product, the inventory count should be updated immediately to avoid overselling. Redis can be used to cache the inventory count, and every update to the count can be written through to the database. This ensures that the inventory count in the cache is always up-to-date, and customers are not able to purchase items that are out of stock.
• Banking application: In a banking application, write-through caching can be used to ensure consistency of account balances. Whenever a transaction is made, the account balance should be updated immediately to avoid overdrafts or other issues. Redis can be used to cache the account balances, and every transaction can be written through to the database. This ensures that the balance in the cache is always up-to-date, and transactions can be processed with strong consistency.
• Online gaming platform: Suppose you have an online gaming platform where users can play games against each other. With write-through caching, any changes made to a user’s score or game state would be saved to the database and also cached in Redis. This ensures that any subsequent reads for that user’s score or game state would hit the cache first. This helps to reduce the load on the database and ensures that the game state displayed to users is always up-to-date.
• Claims Processing System: In an insurance claims processing system, claims data needs to be consistent and up-to-date across different systems and applications. With write-through caching in Redis, new claims data can be written to both the database and Redis cache. This ensures that different applications always have the most up-to-date information about the claims, making it easier for claims adjusters to access the information they need to process claims more quickly and efficiently.
• Healthcare Applications: In healthcare applications, patient data needs to be consistent and up-to-date across different systems and applications. With write-through caching in Redis, updated patient data can be written to both the database and Redis cache, ensuring that different applications always have the latest patient information. This can help improve patient care by providing accurate and timely information to healthcare providers.
• Social media application: In a social media application, write-through caching can be used to ensure consistency of user profiles. Whenever a user updates their profile, the changes should be reflected immediately to avoid showing outdated information to other users. Redis can be used to cache the user profiles, and every update can be written through to the database. This ensures that the profile information in the cache is always up-to-date, and users can see accurate information about each other.

Note: we should ensure atomicity in this, otherwise, we would end up with inconsistent data
Note: Reddis allows setting events on commands (SET, GET, etc.) to run a python script that includes the logic

Question 45

Compare cache aside read and read through

Answer 45

cache-miss:
cache-aside has 3 hops (more latency)
read through has two hops (faster)

data in cache:
same behaviour

cache size:
N/A in read scenarios as behave the same

Question 46

Compare cache aside write and write through

Answer 46

write:
cache-aside:
has the chance of stale data when having concurrent updates. Fixing the issue is complex and requires extra infra and database signals to invalidate stale data in cache

write-through:
easy write compared to cache-aside
higher latency as write to both cache and database is sequential and synchronous

Cache Size:

cache-aside: more compact. We only have the data that is being frequently read. Writes that are not read often are not in the cache.

write-through: we need more cache. Data that may not be frequently read will be present in the cache. We need strong cache eviction policies as a remedy to save storage.

Question 47

What is the Write Behind caching strategy?

Answer 47

In write-behind, the application does the following:

Add/update entry in cache
Asynchronously write entry to the data store, improving write performance

Advantages:
- High throughput writes
- It’s resilient to database failures and can tolerate some database downtime
- If batching or coalescing is supported, it can reduce overall writes to the database, which decreases the load and reduces costs

Disadvantage(s): write-behind

There could be data loss if the cache goes down prior to its contents hitting the data store.

It is more complex to implement write-behind than it is to implement cache-aside or write-through.

There is a period that the data in cache is inconsistent with database

Question 48

What is the Refresh Ahead caching strategy?

Answer 48

How it works: Asynchronously refreshes data from the database before its cache expiration time, often using a background job or thread. This can be based on a fixed interval or a “refresh factor” (percentage of TTL).

Benefits:
- Ensures frequently accessed data is up-to-date.
- Reduces read latency by avoiding database trips.
- Prevents latency spikes caused by cache expirations.
- Can help mitigate the “thundering herd” problem.

Drawbacks:
- Can increase complexity in application code.
- May put extra load on the cache and database.
- Requires accurate prediction of future data needs.
- May not be suitable for all access patterns (e.g., write-
heavy workloads).

Comparison to Read-Through Cache:
- Refresh-ahead: Proactive, predictive, lower latency for
frequent data.
- Read-through: On-demand, reactive, higher initial
latency.

Key Considerations:
- Refresh frequency to balance data freshness and
database load.
- Monitoring cache effectiveness and adjusting refresh
strategies.
- Potential for batch refreshing frequently updated data.

Link: https://www.enjoyalgorithms.com/blog/refresh-ahead-caching-pattern

Question 49

What is thundering herd problem in cache?

Answer 49

The “thundering herd” problem occurs in a highly concurrent environment (typically, many users). When many users make a request to the same piece of data at the same time, and there is a cache miss (the data for the cached element is not present in the cache) the thundering herd problem is triggered.

Question 50

What is Request Coalescing?

Reddit Eng blog: https://www.reddit.com/r/RedditEng/comments/obqtfm/solving_the_three_stooges_problem/

Answer 50

Request coalescing combines multiple simultaneous requests to the same resource into a single request going to the origin. If multiple requests come in at the same time, they will be automatically merged. Once the request from the origin completes, the response will be streamed in real-time to all waiting connections for that request path.

Request Coalescing works by using a special lock mechanism when sending requests to the origin. Upon receiving a request, Request Coalescing opens a mutex lock. Then, the Request Coalescing system will send a single request to the origin. As soon as the origin responds, the mutex is released and all the waiting connections are automatically connected to the origin response.

Question 51

What is the idempotency status for HTTP verbs?

Answer 51

GET, PUT, and DELETE -> Idempotent

PATCH and POST -> not idempotent

PUT: Idempotent, as it replaces the resource, resulting in the same state if repeated.
POST: Not idempotent, as it creates a new resource each time, leading to multiple instances.
PATCH: Not idempotent (in many cases), as it modifies the resource partially, with the possibility of cumulative changes when repeated.

Question 52

When to use UDP over TCP?

Answer 52

Use UDP over TCP when:

You need the lowest latency
Late data is worse than loss of data
You want to implement your own error correction

example: facebook memcache work

Question 53

When to use TCP over UDP?

Answer 53

Use TCP instead of UDP when:

You need reliable, complete data delivery
You want the protocol to optimize data transmission based on network conditions

Question 54

How is read and write operation for Facebook Memcache?

Answer 54

READ:(with lease extension)

v=get(k)
If v is nil
V = fetch from DB
Set (k, v)

WRITE (k,v):

Send k,v to db
delete(k) in the local cache (to provide read-after-write consistency)

Question 55

In facebook memcache for write operation, why do we delete key in cache instead of update?

Answer 55

Setting the key during WRITE instead of delete can lead to having stale data (race condition and concurrent writes)

Question 56

What is lease mechanism in Facebook memcache?

Answer 56

Thundering Herd problem -> concurrent requests will go to database when a key is not in the cache
First FE that reaches the MC gets a lease token.
Other FEs are asked to retry in XXX with the lease
Once the FE brings back the data, the lease is fulfilled. If FE fails to do so, lease will get expired (timeout), and a new lease will be generated for the next FE asking for the data
Handling Race Condition in read and update.
In this case if the database gets updated while another client is going to populate the cache, the lease will get invalidated when delete signal is received to ensure not storing stale data.

Question 57

How does facebook memcache guarantee read-after-write consistency for writes in the replica region?

Answer 57

If write request is issued in a replica region:

Send write to primary db in primary region
To guarantee read-after-write, set a remote marker when doing the write (an indicator that this is prone to race)

Once db replica sends invalidation signal, the marker gets deleted

If in the meantime there is a read request and marker is present, we read the data from the primary db that we wrote on.

If the marker is not present, it means replication is finished and we can read from the replica similar as before.

Question 58

How does facebook memcache invalidates stale data in caches?

Answer 58

McSequel sends invalidate signals to invalidate stale data across cache replicas (guarantee that upon cache miss you will see fresh data)

To control the number of packets being sent around by McSequel, invalidation requests are batched and sent to McRouter

McRouter fans out the requests to the proper FE cluster.
Each cluster has its own McRouters which broadcasts the invalidations to individual memcache servers
If a downstream path is down, each stage can buffer the invalidation requests and send them a bit later