System Design Interview

Non-relational databases might be the right choice if: •Your application requires super-low latency. •Your data are unstructured, or you do not have any relational data. •You only need to serialize and deserialize data (JSON, XML, YAML, etc.). •You need to store a massive amount of data.

Horizontal scaling is more desirable for large scale applications due to the limitations of vertical scaling.

A master database generally only supports write operations. A slave database gets copies of the data from the master database and only supports read operations. All the data-modifying commands like insert, delete, or update must be sent to the master database. Most applications require a much higher ratio of reads to writes; thus, the number of slave databases in a system is usually larger than the number of master databases.

Consider using cache when data is read frequently but modified infrequently. Since cached data is stored in volatile memory, a cache server is not ideal for persisting data. For instance, if a cache server restarts, all the data in memory is lost. Thus, important data should be saved in persistent data stores.

Decoupling makes the message queue a preferred architecture for building a scalable and reliable application. With the message queue, the producer can post a message to the queue when the consumer is unavailable to process it. The consumer can read messages from the queue even when the producer is unavailable.

Some of the following metrics are useful: •Host level metrics: CPU, Memory, disk I/ O, etc. •Aggregated level metrics: for example, the performance of the entire database tier, cache tier, etc. •Key business metrics: daily active users, retention, revenue, etc.

For example, stackoverflow.com in 2013 had over 10 million monthly unique visitors, but it only had 1 master database

•The overall cost of vertical scaling is high. Powerful servers are much more expensive.

You need to have a good sense of scalability basics to effectively carry out back-of-the-envelope estimation. The following concepts should be well understood: power of two [2], latency numbers every programmer should know, and availability numbers.

To obtain correct calculations, it is critical to know the data volume unit using the power of 2. A byte is a sequence of 8 bits. An ASCII character uses one byte of memory (8 bits). Below is a table explaining the data volume unit (Table 2-1).

•Memory is fast but the disk is slow. •Avoid disk seeks if possible. •Simple compression algorithms are fast. •Compress data before sending it over the internet if possible. •Data centers are usually in different regions, and it takes time to send data between them.

The system design interview simulates real-life problem solving where two co-workers collaborate on an ambiguous problem and come up with a solution that meets their goals. The problem is open-ended, and there is no perfect answer. The final design is less important compared to the work you put in the design process. This allows you to demonstrate your design skill, defend your design choices, and respond to feedback in a constructive manner.

Many think that system design interview is all about a person's technical design skills. It is much more than that. An effective system design interview gives strong signals about a person's ability to collaborate, to work under pressure, and to resolve ambiguity constructively. The ability to ask good questions is also an essential skill, and many interviewers specifically look for this skill. A good interviewer also looks for red flags. Over-engineering is a real disease of many engineers as they delight in design purity and ignore tradeoffs. They are often unaware of the compounding costs of over-engineered systems, and many companies pay a high price for that ignorance. You certainly do not want to demonstrate this tendency in a system design interview.

Step 1-Understand the problem and establish design scope

Ask questions to understand the exact requirements. Here is a list of questions to help you get started: •What specific features are we going to build? •How many users does the product have? •How fast does the company anticipate to scale up? What are the anticipated scales in 3 months, 6 months, and a year? •What is the company’s technology stack? What existing services you might leverage to simplify the design?

Step 2-Propose high-level design and get buy-in

Step 3-Design deep dive

Step 1 Understand the problem and establish design scope: 3-10 minutes Step 2 Propose high-level design and get buy-in: 10-15 minutes Step 3 Design deep dive: 10-25 minutes Step 4 Wrap: 3-5 minutes

rate limiting is usually implemented within a component called API gateway. API gateway is a fully managed service that supports rate limiting, SSL termination, authentication, IP whitelisting, servicing static content, etc.

CAP (Consistency, Availability, Partition Tolerance) theorem. CAP theorem CAP theorem states it is impossible for a distributed system to simultaneously provide more than two of these three guarantees: consistency, availability, and partition tolerance. Let us establish a few definitions. Consistency: consistency means all clients see the same data at the same time no matter which node they connect to. Availability: availability means any client which requests data gets a response even if some of the nodes are down. Partition Tolerance: a partition indicates a communication break between two nodes. Partition tolerance means the system continues to operate despite network partitions.

Nowadays, key-value stores are classified based on the two CAP characteristics they support: CP (consistency and partition tolerance) systems: a CP key-value store supports consistency and partition tolerance while sacrificing availability. AP (availability and partition tolerance) systems: an AP key-value store supports availability and partition tolerance while sacrificing consistency. CA (consistency and availability) systems: a CA key-value store supports consistency and availability while sacrificing partition tolerance. Since network failure is unavoidable, a distributed system must tolerate network partition. Thus, a CA system cannot exist in real-world applications.

If we choose consistency over availability (CP system), we must block all write operations to n1 and n2 to avoid data inconsistency among these three servers, which makes the system unavailable. Bank systems usually have extremely high consistent requirements. For example, it is crucial for a bank system to display the most up-to-date balance info. If inconsistency occurs due to a network partition, the bank system returns an error before the inconsistency is resolved. However, if we choose availability over consistency (AP system), the system keeps accepting reads, even though it might return stale data. For writes, n1 and n2 will keep accepting writes, and data will be synced to n3 when the network partition is resolved. Choosing the right CAP guarantees that fit your use case is an important step in building a distributed key-value store.

•Strong consistency: any read operation returns a value corresponding to the result of the most updated write data item. A client never sees out-of-date data. •Weak consistency: subsequent read operations may not see the most updated value. •Eventual consistency: this is a specific form of weak consistency. Given enough time, all updates are propagated, and all replicas are consistent. Strong consistency is usually achieved by forcing a replica not to accept new reads/ writes until every replica has agreed on current write. This approach is not ideal for highly available systems because it could block new operations. Dynamo and Cassandra adopt eventual consistency, which is our recommended consistency model for our key-value store. From concurrent writes, eventual consistency allows inconsistent values to enter the system and force the client to read the values to reconcile.

“A hash tree or Merkle tree is a tree in which every non-leaf node is labeled with the hash of the labels or values (in case of leaves) of its child nodes. Hash trees allow efficient and secure verification of the contents of large data structures”.

UUID has a very low probability of getting collusion. Quoted from Wikipedia, “after generating 1 billion UUIDs every second for approximately 100 years would the probability of creating a single duplicate reach 50%”

The hashValue consists of characters from [0-9, a-z, A-Z], containing 10 + 26 + 26 = 62 possible characters. To figure out the length of hashValue, find the smallest n such that 62 ^ n ≥ 365 billion. The system must support up to 365 billion URLs based on the back of the envelope estimation.

Fanout is the process of delivering a post to all friends. Two types of fanout models are: fanout on write (also called push model) and fanout on read (also called pull model). Both models have pros and cons. We explain their workflows and explore the best approach to support our system. Fanout on write. With this approach, news feed is pre-computed during write time. A new post is delivered to friends’ cache immediately after it is published. Pros: •The news feed is generated in real-time and can be pushed to friends immediately. •Fetching news feed is fast because the news feed is pre-computed during write time. Cons: •If a user has many friends, fetching the friend list and generating news feeds for all of them are slow and time consuming. It is called hotkey problem. •For inactive users or those rarely log in, pre-computing news feeds waste computing resources. Fanout on read. The news feed is generated during read time. This is an on-demand model. Recent posts are pulled when a user loads her home page. Pros: •For inactive users or those who rarely log in, fanout on read works better because it will not waste computing resources on them. •Data is not pushed to friends so there is no hotkey problem. Cons: •Fetching the news feed is slow as the news feed is not pre-computed. We adopt a hybrid approach to get benefits of both approaches and avoid pitfalls in them. Since fetching the news feed fast is crucial, we use a push model for the majority of users. For celebrities or users who have many friends/ followers, we let followers pull news content on-demand to avoid system overload. Consistent hashing is a useful technique to mitigate the hotkey problem as it helps to distribute requests/ data more evenly.

The keep-alive is efficient for this because the keep-alive header allows a client to maintain a persistent connection with the chat service. It also reduces the number of TCP handshakes. HTTP is a fine option on the sender side, and many popular chat applications such as Facebook [1] used HTTP initially to send messages. However, the receiver side is a bit more complicated. Since HTTP is client-initiated, it is not trivial to send messages from the server. Over the years, many techniques are used to simulate a server-initiated connection: polling, long polling, and WebSocket. Those are important techniques widely used in system design interviews so let us examine each of them.

Depending on polling frequency, polling could be costly. It could consume precious server resources to answer a question that offers no as an answer most of the time.

In long polling, a client holds the connection open until there are actually new messages available or a timeout threshold has been reached. Once the client receives new messages, it immediately sends another request to the server, restarting the process. Long polling has a few drawbacks: •Sender and receiver may not connect to the same chat server. HTTP based servers are usually stateless. If you use round robin for load balancing, the server that receives the message might not have a long-polling connection with the client who receives the message. •A server has no good way to tell if a client is disconnected. •It is inefficient. If a user does not chat much, long polling still makes periodic connections after timeouts.

WebSocket is the most common solution for sending asynchronous updates from server to client.

WebSocket connection is initiated by the client. It is bi-directional and persistent. It starts its life as a HTTP connection and could be “upgraded” via some well-defined handshake to a WebSocket connection. Through this persistent connection, a server could send updates to a client.

The number of concurrent connections that a server can handle will most likely be the limiting factor. In our scenario, at 1M concurrent users, assuming each user connection needs 10K of memory on the server (this is a very rough figure and very dependent on the language choice), it only needs about 10GB of memory to hold all the connections on one box. If we propose a design where everything fits in one server, this may raise a big red flag in the interviewer’s mind. No technologist would design such a scale in a single server. Single server design is a deal breaker due to many factors. The single point of failure is the biggest among them. However, it is perfectly fine to start with a single server design. Just make sure the interviewer knows this is a starting point.

Two types of data exist in a typical chat system. The first is generic data, such as user profile, setting, user friends list. These data are stored in robust and reliable relational databases. Replication and sharding are common techniques to satisfy availability and scalability requirements. The second is unique to chat systems: chat history data. It is important to understand the read/ write pattern. •The amount of data is enormous for chat systems. A previous study [2] reveals that Facebook messenger and Whatsapp process 60 billion messages a day. •Only recent chats are accessed frequently. Users do not usually look up for old chats. •Although very recent chat history is viewed in most cases, users might use features that require random access of data, such as search, view your mentions, jump to specific messages, etc. These cases should be supported by the data access layer. •The read to write ratio is about 1: 1 for 1 on 1 chat apps. Selecting the correct storage system that supports all of our use cases is crucial. We recommend key-value stores for the following reasons: •Key-value stores allow easy horizontal scaling. •Key-value stores provide very low latency to access data. •Relational databases do not handle long tail [3] of data well. When the indexes grow large, random access is expensive. •Key-value stores are adopted by other proven reliable chat applications.

Updating online status on every disconnect/ reconnect would make the presence indicator change too often, resulting in poor user experience. We introduce a heartbeat mechanism to solve this problem. Periodically, an online client sends a heartbeat event to presence servers. If presence servers receive a heartbeat event within a certain time, say x seconds from the client, a user is considered as online. Otherwise, it is offline.