Learn the basics of large-scale system design through virtual interview examples
This is a post summarizing what was learned through discussion and study. github
Chapter 1. Scalability based on number of users
There were many similar parts to the recently organized post on Things to consider when designing back-end.
Single server
What happens if a user enters a domain address? It finds the corresponding IP address in DNS and sends an HTTP request to the web server corresponding to that address. At this time, the web server displays HTML or JSON data information according to the request to the user terminal.
database
The web server that receives the HTTP request obtains data through the database. Databases include MySQL and PostgreSQL, which are relational databases, and NoSQL, which are non-relational databases, include DynamoDB and Redis. NoSQL can be divided into key-value storage, graph storage, column storage, and document storage. Non-relational databases are suitable for situations where data is unstructured, data simply needs to be serialized or deserialized, or very low latency response times are required. Or, it is used when there is a need to store a very large amount of data. Isn’t storing a lot of data something that requires write operations? When I was previously studying NoSQL, I looked into ways to process caching using Redis instead of always querying data in RDBMS. At this time, it was a means for read operations, but I did not understand that it was used to store large amounts of data in non-volatile memory. Considering the author's intention, I understood that in the process of storing data, it is first stored in NoSQL, and data is updated in RDBMS at regular intervals. This is because, when a read operation is performed using an RDBMS, contention such as page locking for a significant period of time due to temporary storage of a large amount of data may not occur even in a situation where a row lock is required to read a specific row.
Vertical Scaling vs Horizontal Scaling
Server expansion methods can be divided into vertical scaling and horizontal scaling. Vertical scale expansion is
scale-up
Also called , it is a method of increasing the CPU or memory of the server itself. However, server expansion cannot be done indefinitely, and if only this server exists, it has limitations in that it cannot provide automatic recovery or multiplexing measures in the event of a failure. Horizontal expansion is
scale-out
Also called , it refers to a method of improving performance by having multiple servers. If you have multiple servers like this, you can improve performance and prevent overload by properly distributing server connections using a load balancer. The load balancer communicates between servers using private IP addresses for security purposes, and first receives requests and connects to the web server with the private IP address. So what about database multiplexing? The database is divided into a main database and a secondary database, so that read operations commonly used in applications are performed in several secondary databases, and write operations are handled in the primary database. In the event of a secondary database failure, read operations continue from the primary database or a new secondary database. In the event of a main database failure, the secondary database takes on the role of the main database. And if your archived data is out of date, you'll need additional troubleshooting with a recovery script. Is it possible to further solve the problem using a recovery script? In the process of promoting a secondary database to a primary database because the primary database has already failed, what is required is consistency with the data in the primary database where write operations are performed. Therefore, if you can retrieve data from the primary database, you should be able to retrieve the recovered data from just before the primary database failure to the secondary database. Multiple masters and circular multiplexing Multi-master refers to multiple master devices controlling one slave device, and circular multiplexing refers to multiple devices controlling each other.
Cache
Cache refers to storage that stores expensive calculation results or frequently referenced data in memory so that subsequent requests can be processed quickly. Data can be retrieved faster than database queries. When a user sends a request, if there is a value in the cache, the data is passed on. If not, the data is searched in the database, stored in the cache, and the request is processed. Cache is mainly used for reference data, and when it expires, the data must be read again from the database, so the expiration period should not be too short. Also, if the expiration period is too long, the consistency between the cache and the database decreases. In addition, cache servers must be distributed so that the cache does not become a single point of failure (SPOF). Cache Release Policy It is organized based on the contents of Caching Strategies and How to Choose the Right One. Which caching strategy you use will depend on what data access method you use. It depends on whether many write operations are performed at once, whether the frequency of write operations is high, and whether the data has unique values. In the Cache-Aside method, the application reads the cache first, and if there is no data (cache miss), it reads from the database and then puts the data into the cache. This method is all handled by the application and there is no separate connection between the cache and the database. In cases where there is a lot of content to look up, Memcached and Redis are most used. Cache-Aside approaches typically write data directly to the database, primarily on write operations, so they may not match the cache. Therefore, if you need to maintain proper data freshness, you will need to either invalidate cache entries or set an appropriate TTL. The Read-Through method is similar to the Cache-Aside method, but the difference is that the cache and database data models are not different. Instead, developers need to manually run queries to warm them up in advance, as unnecessary caching occurs when they are first loaded or cached. The Write-Through method refers to a case where a write operation is always written to the cache and then written to the database. This is consistent, but introduces latency because two writes are performed each time. The Write-Back method asynchronously updates data written to the cache to the underlying database. If there are many write operations, the cost is reduced because they are performed before the return operation rather than every time as in the Write-Through method. However, if a cache error occurs, your data may be permanently lost. Facebook paper on cache consistency
R. Nishtala, “Facebook, Scaling Memcache at,” 10th USENIX Symposium on NetworkedSystems Design and Implementation (NSDI ’13)
Content Delivery Network (CDN)
CDN is a network used to transmit static content. Static content is obtained through a nearby CDN server, and if there is no source in the CDN in that geographical location, the static content from the original server is stored in that CDN and then retrieved. When using a CDN, you need to consider cost, content expiration point, failure response plan, and content invalidation using version management.
Stateless web layer
If a user's state information is managed by a web server, and there are multiple web servers, the load balancer should connect the user only to the web server that has the state. Of course, to help with this, you can use sticky sessions, but this will put a burden on the load balancer. Therefore, it is necessary to create an architecture with a stateless web layer, so that users can receive a response no matter which web server they send a request to. In a stateless architecture, state information does not reside on the web server, freeing up scale in/out.
Data Center
data center
US-East
,
US-West
This is a service that connects to a nearby IP address through geoDNS according to geographic routing. When you want to use multiple data centers, you need to test whether the service operates well at each data center location and check whether data consistency for each data center is maintained.
Message queue
Message queue is a component that supports asynchronous communication that guarantees loss. The publisher creates a message queue in advance and performs the actions in the queue whenever the consumer consumes it. Producers can publish messages even if the consumer's process is not present, and consumers can also receive messages even if the producer is not available. Enables each component to be loosely coupled and increases fault tolerance. The book provides an example of a process in which photo retouching tasks are created in a message queue in advance and can be completed asynchronously. As the size of the queue increases, more work processes must be added to reduce processing time. However, if the queue is almost always empty, the number of working processes can be reduced.
When the size of the queue becomes large, more workers are added to reduce the processing time. However, if the queue is empty most of the time, the number of workers can be reduced. The language in this part was a bit awkward, so I looked up the original language version. Producers and consumers can scale independently, and as the queue size increases, more work processes can be added to the producer. If it's almost always empty, you can reduce the number of workers.
Logs, metrics and automation
Logs, metrics, and automation become important as your system grows. Here, metrics are an important tool to understand the current status of the business or system. For example, host-level metrics for CPU, memory, etc., aggregate metrics for database or cache performance, and key business metrics such as daily active users, returning visits, etc.
Scaling up your database
Database scale expansion includes vertical and horizontal scale expansion. It has almost similar drawbacks as vertical expansion in the case of servers. What you need to pay attention to here is the horizontal expansion of the database. Horizontal expansion of the database is called sharding, and it is divided into shards and managed to prevent duplication. Depending on the criteria for separating shards, the distribution may not be even, and hotspot keys may be concentrated in specific databases, resulting in server overload. Therefore, in this case, you should consider re-sharding or, rather, denormalization to prevent inefficiencies resulting from the process of joining across multiple shards.
1 million users and more
In order to manage a large-scale system, a design that favors scalability, such as optimization and division of services into small units, is required.
- The web layer is a stateless layer.
- Introducing multiplexing in all layers
- Cache as much data as possible
- Supports multiple data centers
- Static content will be served through CDN
- The data layer will expand its scale through sharding
- Each layer will be divided into independent services
- Continuously monitor the system and utilize automation tools
Chapter 2. rough estimate of size
Rough scale estimation is the act of calculating an estimate by conducting a thought experiment on universally accepted performance figures to see which design will meet the requirements. Jeff Dean, Lead of Google AI
Power of 2
Response delay value
- Memory is fast, but disk is still slow.
- Avoid disk seeking as much as possible.
- Simple compression algorithms are fast.
- Compress data whenever possible before transmitting it over the Internet.
- Data centers are usually distributed across multiple regions, and it takes time to send and receive data between centers.
High Availability
A term that refers to the ability of a system to operate continuously and without interruption for long periods of time. (mostly 99% to 100%)
Service Level Agreement (SLA)
Terms commonly used by service providers, agreements made between service providers and customers
429 Too many request
returns . In microservices, it is usually designed on a component called an API gateway, which is a fully entrusted management service that supports SSL termination, user authentication, and IP whitelist management.
Throughput Limiting Algorithm
Token bucket, leak bucket, fixed window counter, moving window log, moving window counter
Token Bucket
- It is a simple and commonly used algorithm by Internet companies and is used by Amazon and Stripe to control APIs.
- Tokens are populated periodically and one token is used each time a request is processed. If the token is missing, the request is discarded.
- Requires bucket size and token supply rate
- Although the implementation is efficient and memory efficient, it is difficult to properly tune the two argument values.
Leaking Bucket
+FIFO
- If there is space in the queue, add the request, otherwise discard the request.
- Bucket size, throughput rate
- The size of the queue is limited so it is efficient in terms of memory usage, but when there is a surge in requests, old requests pile up and newer requests are discarded. Like the token bucket algorithm, it is difficult to tune the parameter values correctly.
Fixed window counter
- Divide the timeline into windows at fixed intervals and add a counter to each window.
- When a request is received, the counter is incremented by 1, and when the counter exceeds the threshold, new requests are discarded until a new window is opened.
- If there is a sudden surge in traffic, more requests may be processed than the amount allocated to Windows.
Go to Windows Log
- This is a method that can solve the problem of processing more requests than allocated in case of a sudden influx of traffic in a fixed window counter.
- Store the request timestamp in the same cache as the Redis sorted set.
- Add new requests to log, remove expired timestamps.
- Uses a lot of memory because it stores timestamps of rejected requests.
Moving Window Counter
- Combining the fixed window counter and moving window log, the calculation of the request is as follows:
- Number of requests in the current 1 minute + Number of requests in the previous 1 minute * Rate of 1 minute directly overlapping with the moving window
- It is somewhat loose because the estimate is calculated assuming that requests arriving in the previous time window are evenly distributed.
Storage of counters
It is stored in a Redis memory-based storage device and increases the counter value by 1.
INCR
and determine the timeout value of the counter.
EXPIRE
There is.
Step 3 - Detailed Design
Throughput limit config file
domain: messaging
descriptors:
- key: message_type
Value: marketing
rate_limit:
unit: day
requests_per_unit: 5
Handling of traffic exceeding throughput limit
HTTP response headers allow the client to know how many requests there are, how many requests are left in the window, how many requests are possible per window, and how long afterward a request must be sent to avoid hitting the limit. +X-Ratelimit-Remaining +X-Ratelimit-Limit +X-Ratelimit-Retry-After
Implementation of a throughput limiter in a distributed environment
In cases of severe concurrency, race condition issues arise. Since locking significantly reduces system performance, one way to solve this problem is to use a Lua script or a Redis data structure called sorted set. For synchronization issues, it is recommended to use a centralized data store such as Redis instead of sticky sessions. In order to optimize performance, it is necessary to reduce latency by installing edge servers according to the geographical location of the data center. And, you must use the eventual consistency model when synchronizing data between restricted devices. It is appropriate to monitor throughput limiting devices and change algorithms to better handle traffic patterns.
Finish step 4
Additionally, you may want to consider the following:
- Limit hard or soft processing rates
- Limit processing rates at various layers
- How to design clients to avoid throughput limitations
Chapter 5. Stable Hash Design
In order to evenly distribute the server load, you can use a hash function to determine the distribution of key values placed on the server. However, if a specific server dies, a cache miss may occur where the cached client connects to a server with no data.
Stable Hash
If you bend the hash space into a hash ring, you can place a hash server and hash key on it. This method searches the ring located clockwise of the key and stores the key in the first server you encounter. Even if a server is added or deleted, it will be relocated to the next server. However, the size of the partitions cannot be maintained uniformly, so some large hash spaces may be allocated. To solve this, virtual node or replication method is used. This is a method that requires one server to manage multiple partitions by placing multiple servers in a ring rather than one server. The more nodes there are, the more even the distribution of keys becomes. As the number of virtual nodes increases, the standard deviation value will decrease further. However, more space will be needed to store virtual node data. Compromise decisions are required, so you need to adjust the number of virtual nodes appropriately to suit your system requirements.
- Minimizes the number of keys that are relocated when servers are added or deleted.
- Achieve horizontal scalability because data is evenly distributed
- Reduces hot spot key problems. If a specific shard is accessed frequently, server overload problems may occur.
Chapter 6. Key-value store design
A key-value store is a non-relational database called a key-value database. There are databases such as Amazon Dynamo, memcached, and Redis.
Understand the problem and confirm the design scope
What can you consider when designing a key-value store?
- Size of key-value pairs
- Size of data
- Availability
- Scalability
- Consistency of data
- Response delay time
Single server key-value store
Storing all key-value pairs in a hash table can provide fast searches, but it may be difficult to keep all the data in memory. To solve this, you can compress data or save only frequently used data to disk.
Distributed key-value store
A distributed hash table distributes the key-value pairs themselves across multiple tables, and according to the CAP theorem, data consistency, availability, and partition tolerance must be considered. (Refer to Chapter 1 CAP) In a real distributed system environment, there is no 100% guarantee that partition problems will not occur, so you must choose between consistency and availability. Therefore, you should design an appropriate system after consulting with the interviewer. (i.e. CP or AP)
Core components and technologies to be used in implementation
- data partition
- For data partitioning, it is necessary to consider whether data can be evenly distributed across multiple servers and whether data movement can be minimized when adding/deleting notes. Stable Hash allows you to automate scaling and adjust the number of virtual nodes to match your server capacity. (Refer to Chapter 5. Stable Hash)
- Data multiplexing
- To ensure high availability and stability, data needs to be multiplexed asynchronously across N servers.
- When using virtual nodes, the number of actual physical servers to which the selected N nodes will correspond may be less than N.
- Supplementation is required, such as preventing duplication of physical server selection and storing data copies on other servers.
- Data consistency
- Data multiplexed across multiple nodes must be properly synchronized. Using a quorum consensus protocol, we can ensure consistency for both read and write operations.
- N = Number of copies
- W = Quorum for write operation. For a write operation to be considered successful, it must receive responses from at least W servers indicating that the write operation was successful.
- R = Quorum for read operations. For a read operation to be considered successful, a response indicating that the write operation was successful must be received from at least R servers.
- If W+R>N, strong consistency is guaranteed. This is because there will be at least one overlapping node with the latest data to ensure consistency.
- R=1, W=N: System optimized for fast read operations
- W=1, R=N: System optimized for fast read operations
- W+R>N: Strong consistency is guaranteed
- W+R<=N: Strong consistency not guaranteed
- Consistency Model
- Strong consistency, weak consistency, eventual consistency
- Eventual consistency is a form of weak consistency, a model in which updates are eventually reflected in all copies.
- Data Versioning
- Multiplexing data increases availability, but increases the potential for loss of consistency between copies.
- Versioning: Creating a new version of the data whenever the data changes.
- Vector Clock:
[서버, 버전]
Attaching ordered pairs of to data
- Let's assume that data is updated on two servers and the data values are different.
- Using a vector clock, you can determine which version is leading and the possibility of conflict with another version.
- Disadvantages include that client implementation can become complicated,
[서버, 버전]
The point is that the number of ordered pairs can increase rapidly.
- Fault detection
- When there are many servers, it is better to adopt a distributed failure detection solution such as gossip protocol rather than building multicasting channels on all nodes.
- Gossip Protocol
- Each node periodically increases its beat counter
- Periodically send a list of self-beating counters to randomly selected nodes
- If the beat counter value of a member is not updated for a specified period of time, it is considered to be in a fault state
- Resolve obstacles
- Temporary failure handling
- Following a loose quorum approach, healthy servers are selected and requests to a failed server are temporarily handled by other servers.
- Using hinted handoff technique
- Permanent failure handling
- Sync to latest version using anti-entropy protocol
- Merkle Tree
해시 크리
A Merkle tree, also called, is a tree in which each node is labeled with a hash of the value stored in its child nodes or a hash value calculated from the label of the child node.
- If the hash values of the root node are different, you can compare the hash values of the child nodes from left to right and synchronize other data by finding the same bucket.
- With Merkle trees, the amount of data that needs to be synchronized is only proportional to the size of the differences that actually exist, and is independent of the total amount of data held on the two servers.
System architecture diagram
- The mediator is a node that acts as a proxy for the key-value store to the client.
- Nodes are distributed in a hash ring of stable hashes
- System is fully decentralized so nodes can be added or deleted automatically
- All nodes have the same responsibility
Write path
- When a write request comes in, it is written to the memory cache
- When the memory cache reaches its threshold, data is written to the SSTable (Sorted-String Table) on disk.
- SSTable: A table that manages ordered pairs of <키, 값> in the form of a sorted list.
Reading path
- If there is no data in the memory cache, data is retrieved from the SSTable on disk using a bloom filter.
Principle of Bloom filter The Bloom filter uses multiple hash functions to create multiple hash values for data and changes all corresponding bit values to 1, helping to determine whether there is or can be a data value through the state of the bit array. Therefore, since there is no need to identify all disk data, the data space that needs to be searched is reduced. Example of Bloom Filter Principle
- For example, hash function 1 might map 'apple' to 3, 'banana' to 7, and 'orange' to 2. Hash function 2 can map 'apple' to 4, 'banana' to 2, and 'orange' to 6. Finally, hash function 3 can map 'apple' to 1, 'banana' to 5, and 'orange' to 4.
- If the bits corresponding to the various hash values of each fruit mapped through the hash function are changed to 1, the state of the bit array becomes as follows.
Index: 1 2 3 4 5 6 7 8 Value: 1 1 1 1 0 1 1 0
Goal/Problem Technology Large-scale data storage Distribution across servers using stable hash Ensure high availability for read operations Multiplexing data across multiple data centers Ensuring high availability of writing speakers Conflict resolution using versioning and vector clocks data partition stable hash Gradual scale-up stable hash Diversity stable hash Adjustable data consistency Quorum agreement Temporary failure handling Temporary consignment after loose quorum protocols and provisos Handling permanent failures Merkle tree Data Center Failure Response Data multiplexing across multiple data centers
Chapter 7. Design of a unique ID generator for distributed systems
What should I do when creating an ID? While working on a project, I easily created IDs using UUID and auto_increment, and I was able to learn how to create IDs when certain conditions exist.
Step 1: Understand the problem and confirm the design scope
What should we check when asked to create a unique ID generator?
- Characteristics of ID
- Increased when creating a new ID
- Constituent characters - Is it a number, a letter, or a mixture?
- System scale (requires 10,000 IDs generated per second)
Step 2 Present a schematic design and obtain consent
- multi-master replication
- Utilizes the database's auto-increment function, which increases the ID value by the number of database servers currently in use.
- However, there are several disadvantages.
- Difficult to scale across multiple data centers.
- The uniqueness of the ID is guaranteed, but its value cannot be guaranteed to grow over time.
- It is difficult to get it to work properly when adding or deleting servers.
- UUID (Universally Unique Identifier)
- 128-bit digits to uniquely identify information stored in a computer system
- It is said that in order to create one duplicate UUID, 1 billion UUIDs per second must be created continuously for 100 years.
- No synchronization issues, easy to scale.
- Instead, the ID is 128 bits long and cannot be sorted chronologically or created using only numbers.
- Ticket Server
- Flickr used this technology to create distributed primary keys.
- This is a centralized method of using a database server with an auto-increment function.
- However, if you do this, there is a problem that the ticket server becomes SPOF (Single-Point-of-Failure), and if you create multiple servers, data synchronization issues also occur.
- Twitter Snowflake Approach
- Split the ID structure that needs to be created into multiple clauses (split 64-bit IDs)
- Sign bit: 1 bit to check whether the employee is an employee or not
- Timestamp: A value indicating how many milliseconds have elapsed since the origin time.
- Data Center ID
- Server ID
- Serial number
- Scalable in a distributed environment
Step 3 Detailed Design
This is a detailed design process for the snowflake approach described in step 2. First of all, the data center ID and server ID are determined when the system starts.
- timestamp
- This is a part that occupies 41 bits, which enables sorting by time. If you decimalize this part and add the Twitter origin time (epoch), the millisecond value is calculated, and the value can be obtained by converting it to UTC time.
- Since there are 41 bits, the maximum representable value is approximately 69 years (219902325551 milliseconds).
- Serial number
- Since it is 12 bits, it can have 4096 values.
- Will have a value greater than 0 only if a server generated more than one ID in the same millisecond.
Finish step 4
Is there anything that can be discussed further?
- Clock synchronization
- ID generation servers may not all use the same clock
- This can be resolved with NTP(Network Time Protocol).
- Optimize the length of each verse
- Applications with low concurrency and long lifetimes may benefit from reducing the length of the serial number and increasing the length of the timestamp clause.
- High availability
Chapter 8. URL shortcut design
Step 1: Understand the problem and confirm the design scope
- A URL shortcut key must provide a shortened URL when a long URL is entered, and return to the original URL when accessed with a shortened URL.
- Traffic volume
- Length of shortened URL
- Characters to be included in shortened URLs
- Whether to delete or renew
Step 2: Present rough design and seek consent
- API endpoint
- Endpoint for URL shortening, endpoint for URL redirection
- 301 Permanently Moved
- A response indicating that responsibility for processing HTTP requests for a URL has been permanently transferred to the URL returned in the Location header. The browser will cache this response and send it to the original URL in future requests.
- This is a great way to reduce server load.
- 302 Found
- The response that it must be temporarily processed by the URL specified by the Location header always goes through the shortened URL server.
- It is important to find an appropriate hash function for URL shortening.
Step 3 Detailed Design
Store ordered pairs of shortened URLs and original URLs in a relational database rather than in memory. To shorten, a hash function is used, and the length and character type of the desired shortened value must be considered. The book introduces post-hash collision resolution strategies and Base-62 conversion.
- Post-hash collision resolution strategy
- If only part of the hash value is used to further reduce the shortened URL length, conflicts may occur.
- To resolve this, there is also a way to use a hash function by adding a predetermined string to resolve collisions.
- However, in the end, there is a problem that the overhead is large because it has to be repeatedly queried through the database.
- CRC32, MD5, SHA-1
- base-62 conversion
- The reason for using base 62 is because there are 62 characters that can be used in hashValue, and it is expressed in base 62 according to the remainder of base 62.
- In this case, collision is not possible because it is a strategy that can be applied after ID uniqueness is guaranteed.
- Instead, the problem is that it's easy to figure out what the next shortened URL will be.
Finish step 4
Additional points to discuss
- Throughput limiter
- Scaling up web servers
- Since the web layer is designed as a stateless layer, it can be added or deleted freely.
- Scale up your database
- Data analysis solution
- By integrating a data analysis solution, you can find out which links are accessed most often by users and when they are clicked.
- Availability, data consistency, reliability
Comments
No comments yet. Be the first!
164 posts in 테크
- 2233D Gaussian Splatting vs Unreal Engine: Two Ways to Build a 3D World — and Where Each One Ships
- 222LLMs Inside Unreal Engine: The New Skills Game Developers Need in 2026
- 220Living With Claude Fable 5: How the Most Capable Model Changes the Way You Actually Work
- 219Luma's Bet: From Video Generator to a Single Model That Thinks in Pixels
- 215The Best AI Video Models in 2026: Types, Differences, and Where This Is All Going