If you are preparing for a software engineering interview, you might encounter some questions related to system design. System design is the process of designing the architecture, components, modules, interfaces, and data for a system to satisfy specified requirements. System design questions are usually open-ended and require you to think about how to design a system that meets certain goals and constraints.
In this blog post, I will introduce some of the common system design concepts that you should know before going into an interview. These concepts are not exhaustive, but they cover some of the fundamental aspects of designing scalable, reliable, and efficient systems.
Table of Contents
1. Networking 🌐
- TCP/IP Model
- IPv4 vs IPv6
- TCP vs UDP
- HTTP vs HTTP2 vs WebSocket
- DNS Lookup
- Public Key Infrastructure & Certificate Authority
- Symmetric vs Asymmetric Encryption
- Forward Proxy vs Reverse Proxy
- API Gateway
- CDNs and Edges
2. Database Management 🗄️
- RelationalDB vs NoSQL
- Types of NoSQL
- ACID vs BASE
- Partitioning/Sharding
- Consistent Hashing
- Database Replication
- Database Index
- Strong vs Eventual Consistency
3. Distributed Systems & Scalability 📈
- Vertical and Horizontal Scaling
- CAP Theorem
- Leader Election
- Paxos
- Microservices
- Distributed Messaging Systems
- Distributed File Systems
- MapReduce
4. Caching & Data Structures 🗃️
5. Concurrency & Synchronization 🔄
- Optimistic vs Pessimistic Locking
- Multithreading, Locks, Synchronization, CAS
- Barriers, Semaphores, Monitors
6. Infrastructure & Resource Management 🏢
- Data Center/Racks/Hosts
- Virtual Machines and Containers
- Random vs Sequential Disk Reads/Writes
- Load Balancer
7. Software Design Patterns 🧩
1) Networking 🌐
(i) TCP/IP model
The TCP/IP model is the foundational network protocol architecture for the internet. It consists of four layers:
- Application Layer (handles application-level protocols like HTTP, SMTP, FTP)
- Transport Layer (provides reliable transport, mainly via TCP, and fast but unreliable transport via UDP)
- Internet Layer (routes packets across networks using IP addresses)
- Network Access Layer (handles the physical transmission of data over network hardware)
The TCP/IP model is simpler than the OSI model (which has seven layers) and is widely used due to its reliability, scalability, and ease of implementation for real-world networking
(ii) ipv4 vs ipv6
IPv4 and IPv6 are two versions of the Internet Protocol (IP), which is responsible for assigning addresses to hosts and routing packets across networks.
IPv4 is the most widely used version of IP, but it has some limitations, such as:
- IPv4 has a limited address space of 32 bits, which can only support about 4.3 billion unique addresses. This is not enough to accommodate the growing number of devices connected to the Internet.
- IPv4 does not support end-to-end security or encryption by default. This makes it vulnerable to attacks and eavesdropping.
- IPv4 does not support quality of service (QoS) or traffic prioritization by default. This can affect the performance and reliability of real-time applications, such as voice or video.
IPv6 is the newer version of IP that aims to overcome these limitations by introducing some features, such as:
- IPv6 has a larger address space of 128 bits, which can support about 3.4 x 10^38 unique addresses. This is enough to assign a unique address to every atom on Earth.
- IPv6 supports end-to-end security and encryption by default using IPsec. This enhances the confidentiality and integrity of data transmitted over the Internet.
- IPv6 supports quality of service (QoS) and traffic prioritization by default using flow labels. This allows different types of traffic to be handled differently according to their needs.
IPv6 is gradually being adopted by more networks and devices, but it is not fully compatible with IPv4. Therefore, some transition mechanisms are needed to enable communication between IPv4 and IPv6 hosts.
(iii) TCP vs UDP
TCP and UDP are two protocols that operate at the transport layer of the TCP/IP model. They provide different types of data delivery between hosts.
- TCP (Transmission Control Protocol) provides reliable, ordered, and error-checked data delivery. TCP establishes a connection between two hosts before sending data and uses acknowledgments and retransmissions to ensure that no data is lost or corrupted. TCP also uses flow control and congestion control to regulate the speed and volume of data sent over the network. TCP is suitable for applications that require high reliability and consistency, such as web browsing, file transfer, email, etc.
- UDP (User Datagram Protocol) provides unreliable, unordered, and error-unchecked data delivery. UDP does not establish a connection between two hosts before sending data and does not use acknowledgments or retransmissions to ensure data delivery. UDP also does not use flow control or congestion control to regulate the speed and volume of data sent over the network. UDP is suitable for applications that require low latency and high performance, such as voice or video streaming, online gaming, etc.
TCP and UDP have different advantages and disadvantages depending on the application requirements. Therefore, choosing the right protocol for your system design is crucial.
(iv) HTTP vs http2 vs WebSocket
HTTP (Hypertext Transfer Protocol) is a protocol that defines how clients and servers communicate over the web. HTTP is based on a request-response model, where a client sends a request to a server and waits for a response. HTTP has some limitations, such as high latency, redundant headers, and lack of multiplexing.
HTTP/2 is an improved version of HTTP that addresses some of the limitations of HTTP. HTTP/2 supports features such as binary framing, header compression, server push, and multiplexing.
WebSocket is a protocol that enables bidirectional communication between clients and servers over a single TCP connection. WebSocket allows clients and servers to send and receive messages in real-time without polling or long-polling. WebSocket is useful for applications that require low latency and high interactivity.
(v) DNS lookup
DNS stands for Domain Name System, and it is a distributed system that maps human-readable domain names (such as www.google.com) to their corresponding IP addresses (such as 142.250.181.238). This allows users to access websites and services without having to memorize numerical addresses.
DNS lookup is the process of finding the IP address of a domain name by querying a series of DNS servers. The DNS servers are organized in a hierarchical structure, with the root servers at the top, followed by the top-level domain (TLD) servers, the authoritative servers, and the recursive servers.
The root servers are responsible for maintaining the information about the TLD servers, such as .com, .org, .net, etc. The TLD servers are responsible for maintaining the information about the authoritative servers for each domain name under their TLD. The authoritative servers are responsible for maintaining the information about the IP addresses of each domain name under their authority. The recursive servers are responsible for caching the information from other DNS servers and providing it to the clients.
When a client wants to resolve a domain name to an IP address, it first contacts a recursive server (usually provided by its ISP or operating system). The recursive server then checks its cache to see if it has the answer. If not, it contacts the root server to find out which TLD server is responsible for the domain name. Then it contacts the TLD server to find out which authoritative server is responsible for the domain name. Then it contacts the authoritative server to get the IP address of the domain name. Finally, it returns the IP address to the client and caches it for future use.
(vi) Public key infrastructure and Certificate Authority
Public key infrastructure (PKI) is a system that enables secure communication and authentication over the internet using public key cryptography. Public key cryptography involves using two keys: a public key and a private key. The public key can be shared with anyone, while the private key must be kept secret. The public key can be used to encrypt messages that can only be decrypted by the private key, or to verify signatures that can only be generated by the private key.
A certificate authority (CA) is a trusted entity that issues digital certificates that bind public keys to identities (such as domain names or organizations). A digital certificate contains information such as the public key, the identity of the owner, the validity period, and the signature of the CA. A digital certificate can be used to prove that a public key belongs to a certain identity, or that a message was signed by a certain identity.
One of the main applications of PKI and CA is securing web traffic using HTTPS (Hypertext Transfer Protocol Secure). HTTPS is an extension of HTTP (Hypertext Transfer Protocol) that encrypts and authenticates the communication between a web browser and a web server. HTTPS uses SSL (Secure Sockets Layer) or TLS (Transport Layer Security) protocols to establish a secure connection between the browser and the server.
When a browser requests an HTTPS website, it first performs an SSL/TLS handshake with the server. During this handshake, the server sends its digital certificate to the browser. The browser then verifies that the certificate is valid and issued by a trusted CA. If so, it extracts the public key from the certificate and uses it to encrypt a random session key that it sends back to the server. The server then decrypts the session key using its private key and uses it to encrypt and decrypt all subsequent messages with the browser.
(vii) Symmetric vs Asymmetric encryption
Symmetric encryption and asymmetric encryption are two types of encryption algorithms that are used to protect data from unauthorized access or modification.
Symmetric encryption uses the same key for both encryption and decryption. This means that both parties need to share and keep secret the same key in order to communicate securely. Symmetric encryption is fast and efficient, but it has some drawbacks. For example, it requires a secure way of distributing keys among parties, it does not provide authentication or non-repudiation (the ability to prove who sent or received a message), and it is vulnerable to brute-force attacks if the key is weak or compromised.
Asymmetric encryption uses different keys for encryption and decryption. This means that one party can encrypt a message using another party's public key, and only that party can decrypt it using its private key. Asymmetric encryption does not require sharing keys in advance, and it provides additional security features such as authentication and non-repudiation—since only the holder of the private key can decrypt messages encrypted with their public key or produce a valid digital signature.
However, asymmetric encryption tends to be computationally slower than symmetric encryption, which is why it is often used in combination with symmetric encryption in real-world systems. For example, in many secure communication protocols (like TLS/SSL), asymmetric encryption is used to securely exchange a symmetric session key, and then symmetric encryption is used for the actual data transfer.
Common algorithms for asymmetric encryption include RSA, DSA, and Elliptic Curve Cryptography (ECC). These are widely used for securing web traffic, digital signatures, and protecting data transmissions over public networks.
(viii) Forward Proxy vs Reverse Proxy
Forward Proxy:
A forward proxy sits between client devices and the internet. It acts on behalf of clients, forwarding their requests to external servers. This setup is commonly used for content filtering, network traffic monitoring, anonymous browsing, and bypassing geo-restrictions. In corporate environments, forward proxies prevent employees from accessing unauthorized sites and can cache content to optimize bandwidth usage.
Reverse Proxy:
A reverse proxy is positioned in front of web servers, handling requests from the internet and forwarding them to the appropriate backend server. Its primary use cases include load balancing, caching, SSL termination, and protecting backend servers from direct exposure. Services like Nginx and HAProxy often act as reverse proxies to improve scalability and security.
(ix) API Gateway
An API Gateway is an entry point for all client requests to a set of backend services (often microservices). It provides a unified interface and handles request routing, authentication, rate limiting, response transformation, and logging. By centralizing these cross-cutting concerns, an API gateway simplifies the client-side logic and increases backend security and maintainability. Common examples include Kong, Apigee, and AWS API Gateway.
(x) CDNs and Edges
A CDN (Content Delivery Network) is a network of geographically distributed servers that cache and deliver static or dynamic content to end users. The main purpose of a CDN is to reduce the latency and bandwidth consumption of delivering content from the origin server to the end user. A CDN can also provide other benefits such as security, scalability, reliability, and analytics.
An Edge is a server or a node in a CDN that is closest to the end user in terms of network distance. An edge can serve cached content from its local storage or fetch content from the origin server or another edge if it does not have the requested content. An edge can also perform other functions such as compression, encryption, authentication, etc.
Some common techniques that CDNs use to optimize content delivery are:
- GeoDNS: A technique that maps the end user's IP address to the nearest edge based on their geographic location.
- Anycast: A technique that routes packets to the nearest edge based on network distance using a single IP address for multiple edges.
- Cache invalidation: A technique that updates or removes stale or outdated content from the edges when the origin server changes or deletes it.
- Cache hierarchy: A technique that organizes edges into different levels of hierarchy based on their proximity to the origin server or the end user.
2) Database Management 🗄️
(i) RelationalDB vs NoSQL
Relational databases and NoSQL databases are two types of databases that store and manage data differently.
Relational databases store data in tables with predefined schemas and relationships. They support SQL queries and ACID transactions. Relational databases are good for applications that need structured and consistent data, complex queries, and data integrity.
NoSQL databases store data in various formats, such as key-value pairs, documents, columns, or graphs. They do not have fixed schemas or relationships. They support flexible queries and BASE transactions. NoSQL databases are good for applications that need unstructured and dynamic data, simple queries, and scalability.
(ii) Types of NoSQL
NoSQL databases can be categorized into four main types:
Key Value - These databases store data as key-value pairs, where the key acts as a unique identifier, and the value holds the associated data. Key-value databases are highly efficient for simple read and write operations, and they can be easily partitioned and scaled horizontally. Examples of key-value NoSQL databases include Redis and Amazon DynamoDB.
Wide column - These databases store data in column families, which are groups of related columns. They are designed to handle write-heavy workloads and are highly efficient for querying data with a known row and column keys. Examples of column-family NoSQL databases include Apache Cassandra and HBase.
Document based - These databases store data in document-like structures, such as JSON or BSON. Each document is self-contained and can have its own unique structure, making them suitable for handling heterogeneous data. Examples of document-based NoSQL databases include MongoDB and Couchbase.
Graph based - These databases are designed for storing and querying data that has complex relationships and interconnected structures, such as social networks or recommendation systems. Graph databases use nodes, edges, and properties to represent and store data, making it easier to perform complex traversals and relationship-based queries. Examples of graph-based NoSQL databases include Neo4j and Amazon Neptune.
(iii) ACID vs BASE
ACID and BASE are two sets of properties that describe how a database handles transactions.
ACID stands for Atomicity, Consistency, Isolation, and Durability. These properties ensure that transactions are processed reliably and in an all-or-nothing manner. A transaction is a logical unit of work that consists of one or more operations on the database. For example, transferring money from one account to another involves two operations: debiting one account and crediting another. An ACID transaction guarantees that either both operations succeed or both fail atomically (Atomicity), the database state remains valid and consistent after each transaction (Consistency), concurrent transactions do not interfere with each other (Isolation), and committed transactions are permanently recorded and not lost due to failures (Durability).
ACID properties are desirable for applications that require strong consistency and reliability, such as banking or e-commerce systems. However, ACID transactions also come with some drawbacks. They can be expensive in terms of performance and scalability, as they require locking resources and coordinating across multiple nodes. They can also limit availability in the face of network partitions or node failures.
BASE stands for Basically Available, Soft state, Eventual consistency. These properties relax some of the ACID constraints to achieve higher availability and scalability. A BASE transaction does not guarantee atomicity or isolation; instead, it allows partial failures or temporary inconsistencies in the database state. A BASE transaction also does not guarantee immediate consistency; instead, it ensures that the database state will eventually converge to a consistent state after some time (Eventual consistency).
BASE properties are suitable for applications that can tolerate some inconsistency and latency in exchange for higher availability and scalability, such as social media or online gaming systems. However,
BASE transactions also come with some trade-offs -
Consistency
BASE databases prioritize availability over consistency, which means that users may temporarily access inconsistent data.Replication
Asynchronous replication is faster than synchronous replication because it doesn't wait for all nodes to confirm an update before proceeding. However, this means that there can be a time lag where the replicas are out of sync with the master.Performance
Synchronous replication ensures strong data consistency, but it can be slow because it waits for all nodes to confirm an update.System choice
The choice of replication strategy depends on the system's needs and the trade-offs it can tolerate regarding performance, reliability, and consistency.
(iv) Partitioning/ Sharding
In a database, horizontal partitioning, often referred to as sharding, entails dividing the rows of a table into smaller tables and storing them on distinct servers or database instances. This method is employed to distribute the database load across multiple servers, thereby enhancing performance.
Conversely, vertical partitioning involves splitting the columns of a table into separate tables. This technique aims to reduce the column count in a table and boost the performance of queries that only access a limited number of columns.
(v) Consistent Hashing
Consistent hashing is a technique used in distributed systems to evenly distribute data across multiple servers or nodes and minimize the amount of data that needs to be moved when servers are added or removed. In a consistent hashing scheme, both the data and the nodes are assigned positions on a virtual circle (hash ring) by a hash function. Each piece of data is stored in the first node encountered while moving clockwise around the ring from the data's position. This design ensures that only a small portion of the data is remapped when the system scales up or down, making it ideal for building scalable and fault-tolerant distributed services (e.g., caching, databases)
(vi) Database Replication
Database replication is the process of copying and maintaining database objects, such as tables, in multiple database servers. This enhances data redundancy, availability, and disaster recovery.
Master-slave replication: One primary node handles writes; replicas synchronize with it and handle read requests, improving read scalability.
Master-master replication: Multiple nodes can accept reads and writes, with changes propagated between them. This boosts write scalability and fault tolerance but introduces challenges like conflict resolution.
Synchronous vs. Asynchronous replication: Synchronous ensures changes are immediately reflected across replicas (strong consistency), while asynchronous offers better performance at the risk of temporary inconsistencies.
(vii) Database Index
A database index is a data structure that improves the speed of data retrieval operations on a database table at the cost of additional writes and storage space.
Common types:
B-Tree: Used in relational databases to speed up equality and range queries.
Hash index: Effective for exact match searches.
Full-text index: Optimizes text search within large pieces of text.
Proper indexing is key to optimizing query performance but should be used judiciously to avoid extra overhead.
(viii) Strong vs Eventual Consistency
Consistency is a property that ensures that all nodes in a distributed system see the same view of the data at any given time. Consistency can be either strong or eventual, depending on how it handles updates.
Strong consistency guarantees that any update to the data is immediately visible to all nodes in the system. This means that all nodes always have the latest version of the data. Strong consistency is desirable for applications that require real-time data accuracy and synchronization.
Eventual consistency guarantees that any update to the data will eventually be visible to all nodes in the system. This means that some nodes may have stale or outdated versions of the data for some time. Eventual consistency is acceptable for applications that can tolerate some degree of inconsistency and latency.
3) Distributed Systems & Scalability 📈
(i) Vertical and Horizontal Scaling
Scaling is the ability of a system to handle increased load. There are two main ways to scale a system: Vertical Scaling and Horizontal Scaling.
Vertical scaling means increasing the capacity of a single server or component by adding more resources, such as CPU, memory, disk, or network. For example, you can upgrade your server from 8 GB RAM to 16 GB RAM to handle more requests. Vertical scaling is usually easier to implement and maintain, but it has some limitations. It can be expensive, as you need to buy more powerful hardware. It can also introduce a single point of failure, as your system depends on one server or component.
Horizontal scaling means increasing the number of servers or components in your system. For example, you can add more servers behind a load balancer to distribute the load among them. Horizontal scaling is usually more cost-effective and fault-tolerant, as you can use cheaper hardware and avoid single points of failure. However, it can also introduce more complexity and overhead, as you need to coordinate and synchronize data and state across multiple servers or components.
(ii) CAP theorem
CAP theorem is a fundamental concept in distributed systems. It states that it is impossible for a distributed system to simultaneously provide all three of the following guarantees:
- Consistency: Every read operation returns the most recent write or an error.
- Availability: Every request receives a response, without guaranteeing that it contains the most recent write.
- Partition tolerance: The system continues to operate despite arbitrary message loss or failure of part of the system.
According to the CAP theorem, a distributed system can only achieve two out of these three guarantees at any given time. For example, if you want your system to be consistent and available, you have to sacrifice partition tolerance. This means that if your system experiences a network partition (a situation where some nodes cannot communicate with others), it will stop serving requests or return inconsistent results. On the other hand, if you want your system to be available and partition tolerant, you have to sacrifice consistency. This means that your system will continue serving requests even if some nodes have stale or conflicting data.
The CAP theorem does not imply that you have to choose one guarantee over another permanently. You can also trade off between them dynamically depending on your use case and requirements. For example, you can use different consistency models for different types of data or operations in your system.
(iii) Leader election
Leader election is a process of choosing a single node among a group of nodes to perform some special tasks or coordinate the actions of other nodes. For example, in a distributed database system, there might be a leader node that is responsible for accepting write requests and replicating them to other nodes. In a consensus algorithm, such as Paxos or Raft, there might be a leader node that proposes values and collects votes from other nodes. In a distributed lock service, such as ZooKeeper or etcd, there might be a leader node that grants locks and maintains the state of the system.
Leader election can be useful for several reasons:
- It can simplify the design of the system by reducing the complexity and overhead of having multiple nodes perform the same tasks or communicate with each other.
- It can improve the performance and availability of the system by avoiding conflicts and contention among nodes and ensuring that there is always a node that can serve requests or make decisions.
- It can enhance the consistency and reliability of the system by ensuring that there is only one source of truth or authority for the system state or data.
There are different ways to implement leader election, depending on the requirements and assumptions of the system. Some common methods are:
- Static configuration: The leader node is predetermined and fixed by the system configuration. This method is simple and fast, but it does not handle failures or changes in the system well.
- Random selection: The leader node is chosen randomly by each node or by a central authority. This method is easy to implement and can handle failures or changes in the system, but it might result in frequent leader changes or conflicts among nodes.
- Round-robin: The leader node is rotated among all nodes in a fixed order. This method is fair and balanced, but it might not handle failures or changes in the system well.
- Bully algorithm: The leader node is the one with the highest identifier among all nodes. If a node detects that the current leader has failed or left the system, it initiates an election by sending messages to all nodes with higher identifiers than itself. If it does not receive any response, it becomes the new leader. Otherwise, it waits for a message from a higher identifier node that has become the new leader. This method can handle failures or changes in the system well, but it might incur high communication overhead and latency.
- Ring algorithm: The nodes are arranged in a logical ring and each node knows its successor in the ring. To elect a leader, a node initiates an election by sending a message containing its identifier to its successor. Each node that receives the message forwards it to its successor if its identifier is smaller than the one in the message, or discards it if its identifier is larger. The message eventually reaches the node that initiated the election, which becomes the new leader. This method can handle failures or changes in the system well, but it might incur high communication overhead and latency.
(iv) Paxos
Paxos is a consensus algorithm used in distributed systems to ensure that a group of nodes can agree on a single value, even in the presence of network failures or node crashes. It works by having proposers suggest values, acceptors vote on which value to accept, and learners learn the final decision. The process involves multiple phases (prepare, promise, accept, and learn), and a value is chosen only if a majority of acceptors agree. Paxos is crucial for achieving consistency and fault tolerance in replicated systems, such as distributed databases and coordination services
(v) Microservices
Microservices is an architectural style where complex applications are decomposed into smaller, independently deployable services that focus on single business capabilities. Each microservice has its own database and can be developed, deployed, and scaled independently.
Key benefits:
Improved scalability and fault isolation
Faster time to market via independent deployments
Technology diversity
Challenges:
Increased operational complexity
Need for robust inter-service communication (often via REST, gRPC or messaging systems)
Distributed data management and consistency
(vi) Distributed Messaging Systems
A distributed messaging system enables communication between distributed components of a system, allowing them to exchange messages reliably and asynchronously. These systems decouple senders and receivers, improving scalability and fault tolerance. Key features include message queues, topics, durability, and delivery guarantees.
Popular tools: Apache Kafka, RabbitMQ, and Amazon SQS.
Use cases: Event-driven architectures, task queues, real-time data pipelines, and microservices communication.
(vii) Distributed File Systems
A distributed file system (DFS) stores and manages files across multiple servers or locations, providing users with a single, unified view of the files.
Features:
Scalability for storing massive datasets
High availability through redundancy and replication
Fault tolerance via data sharding and recovery
Examples: Hadoop Distributed File System (HDFS), Google File System (GFS), NFS, and CephFS.
(viii) Map reduce
Map reduce is a programming model and an associated implementation for processing large-scale data sets in parallel and distributed environments. Map reduce consists of two phases: map and reduce. In the map phase, a set of input data is split into smaller chunks and processed by multiple map tasks that run on different machines. Each map task applies a user-defined function to its input chunk and produces a set of intermediate key-value pairs. In the reduce phase, the intermediate key-value pairs are shuffled and grouped by their keys and sent to multiple reduce tasks that run on different machines. Each reduce task applies another user-defined function to its input group of values and produces a set of output key-value pairs.
Map reduce provides several benefits for large-scale data processing, such as simplicity, scalability, fault tolerance, and flexibility. The user only needs to specify the map and reduce functions without worrying about the details of parallelization, distribution, synchronization, or failure handling. The map reduce framework handles these aspects automatically and efficiently. The user can also customize the map reduce pipeline by using different input formats, output formats, partitioners, combiners, etc.
Map reduce is widely used for various applications that involve processing large amounts of data in parallel and distributed environments. Some examples are web indexing, web analytics, machine learning, data mining, etc.
4) Caching & Data Structures 🗃️
(i) Caching
Caching is a technique of storing frequently accessed data in a fast and temporary storage layer, such as memory or disk, to reduce latency and improve performance. Caching can be implemented at different levels of a system, such as application, database, or network. Caching can improve the scalability and availability of a system by reducing the load on the backend servers and databases. However, caching also introduces challenges such as cache coherence, cache eviction, and cache invalidation.
(ii) Bloom Filters and Count-min sketch
A Bloom Filter is a probabilistic data structure that can efficiently test whether an element is a member of a set or not. The main advantage of a bloom filter is that it uses very little space compared to other data structures such as hash tables or sets. The main drawback of a bloom filter is that it can have false positives, meaning that it can incorrectly report that an element is in the set when it is not. However, it can never have false negatives, meaning that it can never report that an element is not in the set when it is.
A bloom filter consists of an array of m bits, initially all set to 0, and k independent hash functions that map each element to k different positions in the array. To add an element to the set, we compute its k hash values and set the corresponding bits in the array to 1. To check whether an element is in the set or not, we compute its k hash values and check if all the corresponding bits in the array are 1. If yes, we conclude that the element is probably in the set. If no, we conclude that the element is definitely not in the set.
A Count-Min Sketch is an extension of a bloom filter that can also estimate the frequency or count of an element in a multiset or a stream. The main advantage of a count-min sketch is that it uses very little space compared to other data structures such as hash tables or counters. The main drawback of a count-min sketch is that it can have overestimation errors, meaning that it can report a higher count than the actual one.
5) Concurrency & Synchronization 🔄
(i) Optimistic vs Pessimistic Locking
Locking is a mechanism that prevents concurrent access to shared resources, such as data or files. Locking can be either optimistic or pessimistic, depending on how it handles conflicts.
Optimistic locking assumes that conflicts are rare and allows multiple transactions to access the same resource without acquiring locks. However, if a conflict occurs, such as two transactions trying to update the same record, one of them will fail and have to retry. Optimistic locking is suitable for scenarios where read operations are more frequent than write operations, and where performance and scalability are important.
Pessimistic locking assumes that conflicts are common and requires transactions to acquire locks before accessing any shared resource. This ensures that only one transaction can modify a resource at a time, avoiding conflicts. However, pessimistic locking can also cause deadlock, where two transactions are waiting for each other to release their locks. Pessimistic locking is suitable for scenarios where write operations are more frequent than read operations, and where data integrity and consistency are important.
(ii) Multithreading, locks, synchronization, CAS (Compare and Set)
Multithreading is a technique that allows multiple threads of execution to run concurrently within a single process or application. Multithreading can improve the performance and responsiveness of an application by utilizing multiple CPU cores or by overlapping computation with I/O operations. However, multithreading also introduces challenges such as concurrency control, race conditions, deadlocks, and livelocks.
Concurrency control is the process of ensuring that multiple threads access shared data or resources in a consistent and correct manner. One common way of achieving concurrency control is using locks. A lock is a mechanism that allows only one thread to access a shared resource at a time while blocking other threads from accessing it until the lock is released. Locks can prevent race conditions, which occur when multiple threads access or modify shared data without proper synchronization
and cause incorrect or unpredictable results. However, locks can also cause problems such as deadlocks, which occur when two or more threads wait for each other to release locks that they hold and prevent each other from making progress, or livelocks, which occur when two or more threads repeatedly change their state in response to each other
and prevent each other from making progress.
Another way of achieving concurrency control is using synchronization primitives such as atomic operations, barriers,semaphores,or monitors.
These primitives provide different mechanisms to coordinate the actions of multiple threads:
Atomic Operations: These are operations that are performed as a single, indivisible step. An example is the Compare-and-Set (CAS) operation, which checks if a value has not changed before updating it. CAS is the foundation of many lock-free data structures and allows threads to update shared variables without explicit locks, reducing contention and improving performance in high-concurrency scenarios. If the value being checked does not match what a thread expects (because another thread changed it), the operation fails and is retried, ensuring consistency without blocking other threads.
Barriers: A barrier is a synchronization point where multiple threads must all arrive before any are allowed to continue. Barriers ensure that different parts of a program reach certain checkpoints together—common in parallel computing and tasks requiring coordinated progress.
Semaphores: A semaphore is an integer variable that controls access to shared resources by multiple threads. There are two main operations: wait (or acquire, P) and signal (or release, V). Semaphores can be used to restrict the number of threads that can access a resource simultaneously, making them useful for throttling or managing resource pools. Counting semaphores (which allow more than one thread) are useful for managing a pool of identical resources, while binary semaphores act like mutexes (mutual exclusion locks).
Monitors: A monitor is a high-level synchronization construct that allows only one thread to execute a critical section of code at a time, handling both mutual exclusion and the scheduling of waiting threads. Monitors typically encapsulate shared data and provide condition variables to wait for specific changes or notifications. Monitors make it simpler to avoid timing errors and encapsulate synchronization logic, while semaphores require explicit handling by the programmer.
In summary, multithreading can make systems highly concurrent and performant, but requires careful use of synchronization primitives to avoid common pitfalls like race conditions, deadlocks, and inconsistent state. Depending on the use case and performance requirements, you may choose between traditional locks, lock-free mechanisms like CAS, or higher-level constructs like semaphores and monitors to ensure safe and correct concurrent execution.
6) Infrastructure & Resource Management 🏢
(i) Data center/racks/hosts
A data center is a physical facility that houses multiple servers, storage devices, network equipment, and other hardware components that provide computing services to users. A data center can be organized into racks, which are metal frames that hold multiple servers and other devices. Each rack can have its own power supply, cooling system, and network switch. A host is a single server or device within a rack that runs one or more applications or services.
(ii) Virtual Machines and Containers
Virtual machines (VMs) and containers are two technologies that allow running multiple isolated applications on a single physical machine. They both provide benefits such as portability, scalability, security, and resource efficiency. However, they also have some differences in how they work and what they are best suited for.
A virtual machine is a software emulation of a physical computer that runs an operating system (OS) and applications. A VM has its own virtual hardware, such as CPU, memory, disk, network, etc., that are mapped to the physical resources of the host machine. A VM can run any OS and application that are compatible with the virtual hardware. A VM provides strong isolation and security, as it is completely separated from the host OS and other VMs. However, a VM also has some drawbacks, such as high overhead, slow startup time, and limited compatibility with the host OS.
A container is a lightweight software package that contains an application and its dependencies. A container runs on top of the host OS and shares the same kernel and libraries with other containers. A container does not have its own virtual hardware or OS; instead, it relies on the host OS to provide the necessary resources and services. A container provides fast startup time, low overhead, and high compatibility with the host OS. However, a container also has some drawbacks, such as weaker isolation and security, as it is more exposed to the host OS and other containers.
The choice between VMs and containers depends on the use case and the trade-offs involved. Generally speaking, VMs are more suitable for running heterogeneous applications that require strong isolation and security, while containers are more suitable for running homogeneous applications that require fast deployment and scalability.
(iii) Random vs Sequential read/writes to disk
Disk is a persistent storage medium that can store large amounts of data. Disk access can be classified into two types: random and sequential. Random access means that the data is read or written at random locations on the disk, while sequential access means that the data is read or written in a contiguous manner on the disk. Random access is typically slower than sequential access, as it involves more disk seek operations and fragmentation. Sequential access is typically faster than random access, as it involves less disk seek operations and better locality.
(iv) Load Balancer
A load balancer is a device or a software that distributes incoming requests or traffic across multiple servers or nodes in a cluster. The main purpose of a load balancer is to balance the load among the servers and prevent any single server from being overloaded or underutilized. Load balancers can also provide other benefits such as fault tolerance, high availability, security, and routing.
There are different types of load balancers based on the level of abstraction they operate on. For example, a layer 4 load balancer works at the transport layer and distributes requests based on the source and destination IP addresses and ports. A layer 7 load balancer works at the application layer and distributes requests based on the content of the request, such as the URL, headers, cookies, etc.
Some common algorithms that load balancers use to distribute requests are:
- Round robin: The simplest algorithm that assigns requests to servers in a circular order.
- Least connections: Assigns requests to the server with the least number of active connections.
- Least response time: Assigns requests to the server with the lowest average response time.
- Hashing: Assigns requests to servers based on a hash function of some attribute of the request, such as the IP address or the URL.
- Weighted: Assigns requests to servers based on some predefined weights that reflect their capacity or priority.
7) Software Design Patterns 🧩
(i) Design patterns and Object-oriented design
Design patterns are reusable solutions to common problems that arise in software design. They describe how to structure classes and objects to achieve certain goals or functionalities. They are not specific to any programming language or framework, but rather capture general principles and best practices that can be applied in different contexts.
Object-oriented design is a paradigm of software design that focuses on modeling real-world entities and concepts as classes and objects that have attributes and behaviors. It supports abstraction, encapsulation, inheritance, polymorphism, and modularity as key features.
Design patterns and object-oriented design can be useful for several reasons:
- They can improve the readability and maintainability of the code by following consistent and standardized conventions and structures.
- They can enhance the reusability and extensibility of the code by allowing components to be easily reused or modified without affecting other parts of the system.
- They can increase the robustness and reliability of the code by avoiding common pitfalls and errors that might occur in software design.
There are different types of design patterns, depending on their purpose and scope. Some common types are:
- Creational patterns: These patterns deal with how to create objects or classes in an efficient and flexible way. For example, singleton pattern ensures that only one instance of a class exists in the system; factory pattern allows creating objects without specifying their exact concrete class up front, and the builder pattern separates the construction of a complex object from its representation so the same construction process can create different results.
- Structural patterns: These patterns focus on how to organize classes and objects to form larger structures. Examples include the adapter pattern (which allows incompatible interfaces to work together), the decorator pattern (which dynamically adds new functionality to objects), and the facade pattern (which provides a simplified interface to a complex subsystem).
- Behavioral patterns: These patterns are concerned with how objects interact and communicate with each other. Some popular behavioral patterns include the observer pattern (where objects subscribe to receive updates from another object), the strategy pattern (which defines a family of interchangeable algorithms), and the command pattern (which encapsulates a request as an object, allowing for the parameterization and queuing of requests).
Applying the right design patterns helps improve code modularity, reuse, scalability, and maintainability, which are all essential qualities in robust system design.
System design is a vast and evolving field that bridges theory and practice to solve real-world challenges at scale. Mastering the core concepts—such as scalability techniques, consistency models, distributed architectures, replication strategies, and microservices—empowers you to create robust systems that can adapt to growth, recover from failures, and deliver high performance.
Remember, there’s no one-size-fits-all solution in system design. Each organization, application, and problem domain has unique requirements and constraints. By understanding the fundamental patterns and trade-offs discussed in this guide, you’ll be well-equipped to navigate design decisions confidently—whether in an interview or on the job.
Keep exploring, stay curious, and continue honing your skills—the landscape of system design has endless opportunities for learning and innovation.
If you are preparing for a software engineering interview, you might encounter some questions related to system design. System design is the process of designing the architecture, components, modules, interfaces, and data for a system to satisfy specified requirements. System design questions are usually open-ended and require you to think about how to design a system that meets certain goals and constraints.
In this blog post, I will introduce some of the common system design concepts that you should know before going into an interview. These concepts are not exhaustive, but they cover some of the fundamental aspects of designing scalable, reliable, and efficient systems.
Top comments (0)