Saturday, 29 May 2021

Prepare for Facebook System Design Interview [Pirate Round]

What is the System Design Interview Round at Facebook?

System Design Interview Round is also known as the Pirate Interview round at Facebook.
In this round, you will be asked to show off your design skills. The system design questions asked are typically more open-ended and feel more like a discussion.
The design interview is 45 minutes long. It rarely involves coding. You will spend most of the time talking and drawing on the whiteboard.
The purpose of the interview is to assess the candidate's ability to solve a non-trivial engineering design problem. The interviewer will ask you a very broad design problem and evaluate your solution.

Now let us review the top system design questions which are usually asked at Facebook.

Question 1: Design Facebook News Feed

In the Design Facebook News Feed question, design the following key features and their APIs.

Facebook users should see the news feed containing posts and statuses from their friends and pages that they have followed.
They can post and like statuses that may contain text, images, and videos.
They can send friend requests to other users and follow other pages.

Design Goals

Minimum latency
High Availability
Eventual Consistency (Due to CAP Theorem)
Read-Heavy Service

Scale Estimations

One billion daily active users (DAUs)
Ten billion news feed requests daily
On average:
- Each user posts twice a day
- Each post is liked five times
- Each user has 200 friends
- Each user follows 100 pages

Question 2: Design Facebook Status Search

Facebook provides a search bar at the top of its page to enable its users to search posts, statuses, videos, and other forms of content posted by their friends and the pages they follow. In this question,

Develop a service to enable the users to search the statuses posted on Facebook by their friends and followed pages.
Consider that these statuses will only contain text for this particular question.

Design Goals

We should ensure that the final system has minimum latency, and users should not experience any significant lag while searching for the statuses.
The system should be highly available.
Due to the CAP theorem, we will aim for an eventually consistent system.
Our system will be read-heavy as more users will be searching on Facebook rather than posting statuses. Thus, the number of read requests will be far greater than write requests.

Scale Estimations

For an efficient system, we will have to consider the following scale estimations.

On average, the system will have one billion daily active users
Receive around five billion search requests daily
About one billion statuses will be generated by the users per day.

Question 3: Design Live Commenting

This question is not related to Live Videos. This question is related to the active real-time feed of comments at the bottom of each post. Thus, in this question,

Design the backend of a system that can enable real-time commenting on Facebook posts.
The users should be able to see the new comments in real-time for the posts visible in front of their screen.

This problem is quite challenging, as users are continuously scrolling the news feed, and thus the posts that are visible in their view can change very frequently.

Scale Estimations

To design an efficient system in the interview, we will have to consider the following scale estimations. These estimations will help us in explaining the scale of the system to the interviewer.

Every minute, Facebook serves over 100 million pieces of content that may receive comments.
In that same minute, users submit around a million comments that need to get routed to the correct viewers.

Question 4: Design Facebook Messenger or WhatsApp

Develop the backend of a messenger system that can,

Support 1:1 conversations between two users.
Track the online or offline status of the users.

If time remains, discuss more complex features like Group conversations and Push notifications.

Question 5: Design Instagram

Design a simpler version of Instagram.

Users can upload and share photos.
They can follow other users.
Like the photos posted on Instagram.
Instagram users should get a scrollable feed of photos that are posted by the users they follow.

Question 6: Design Typeahead Suggestions

Google predicts and suggests a list of autocomplete queries based on the characters that we have already typed in the search box.

Suggest the top ten search queries based on the characters already typed by the user in the search box.
Assume query's popularity can be determined by the frequency of the query being searched in the past.

Question 7: Design Privacy Settings at Facebook

We can set different privacy levels for the Facebook posts we publish to be only visible to a specific set of users like public, friends, friends of friends, etc.

Enable a user to specify the different levels of privacy for a post so that it is only visible to a particular set of users.
Implement two levels of privacy, Public and Friends.
Optional Complex Levels: friends of friends, custom groups

Question 8: Design Proximity Server

Proximity servers are used to discover nearby attractions such as places and events, which are then recommended to Facebook users.

Users can add, update, and delete places.
Given a location expressed as latitude and longitude, users can query all the nearby places within a given distance.
Optional Follow-up: Query events near a given place around a particular time. This adds the third dimension of time to the problem.

Question 9: Design Top N Songs

This question is very similar to designing the system for Top N Trending topics.

Get the top N songs for a user over the past X days.
Assume popularity of a song can be determined by the frequency of the song being listened to in the past.

Question 10: Design Web Crawler

Web Crawler scans the world wide web to download and index all the web pages to be made available for the search queries submitted by the users.

Given a list of seed web pages, it should download all the web pages and index them for future retrieval.
The service should handle duplicate web pages so that unique URLs are stored.

Design Goals

We should ensure that our service is highly scalable, as it needs to crawl the entire Web and fetch billions of web pages.
It should implement the Robot Exclusion protocol, allowing web admins to declare parts of their websites off-limits to crawlers.
For the simplicity of the interview, we can consider that we will crawl only HTML pages.

Scale Estimations

Our System will be crawling about 25 billion web pages every two weeks.
On average, each URL will be 512 bytes in size,
And each page will be about 100 KB in size.

Designing Distributed File Storage Systems - Explained with Google File System(GFS)

A distributed file system(DFS) is a file system that allows you to access files stored in multiple hosts distributed across them.

In contrast to other data stores like MySQL or NoSQL which can also be made distributed, the data is DFS is stored in raw form and as files instead of a table or a fixed-document format.

The use cases where DFS is used are very vast. From storing media content like Youtube videos to Instagram images to blogs like these, anything that can be stored as a file, is big and is not suitable to store in other data stores, DFS is generally a preferred choice for everyone.

Key points to consider while designing a DFS:

Understanding from the perspective of using a distributed file system, there are some characteristics that need to be considered while choosing the data store and tweaked according to the business requirements of the project.

Consistency - Strong consistency for a user means the system should behave as if the user is talking to a single server in spite of behind the scene they are in 1000s. If a user chooses to build a distributed system that is also consistent in nature, performance should be traded off for this, which is mostly the write performance. The general case is a write is acknowledged successful if and only if the writes to all the replicas are done, and the write performance takes a hit with this. Most of the systems are made eventual consistent due to this reason if it can be afforded for the busses use case. If we want strong consistency, it will trade-off performance, as it cannot send an acknowledgment until all replicas are updated.
Parallel performance(through sharding and replication) - As most of the data is independent, we can split up the data(shard) to store in multiple machines to scale horizontally with an increased amount of data as well as traffic load. This will surely increase the query and maintenance complexity of storing data, as we have to manage the metadata at the application layer as well, but a good way to store if the data is very huge, like for a typical file data store. We can achieve increase query performance as most of the queries can be done parallelly, even for the same file if we split the file as well(we'll talk about chunking)
Fault-tolerant (through replication) - As we want the system to be highly available, i.e. even if a few servers fail, it should continue working without any change for the end-user. This can be achieved with replication, i.e. duplicating and storing the same data across multiple machines. Though replication can be very tricky to achieve, and we have to trade off consistency to achieve this, this can certainly be very useful if losing a file, even a chunk of it can be very costly for the business. Ex: if we are trusting google drive to keep all our data for a lifetime, we don't want them to lose any of it, and losing even a little data can be very harmful for their reputation.
Automatic failure recovery - As we will be dealing with 1000s of servers storing and maintaining the data, any failure if fixed manually can take some amount of time and human hours, which also cost the company. And if the servers are in 1000s, the chances of any kind of failure is very high. We can achieve this by persisting some metadata so that after any failure or restart, the node can backup the state from where it was before the failure.

Architecture

Metadata service(servers)

Metadata service(servers) is responsible for keeping track of all the metadata like where a file is stored, how it is chunked, how it is replicated, update pattern(versions).

Considering the above points, we will be using a master-slave architecture means there will be a single node that will take care of the update to files and there will be replicas that will be used for reading the files, and in the case of the master failure, coordinate between them to select a new master among them.

Responsibilities of the master node:

master keeps mapping from filename to chunks
we query the master to ask for servers where the file is stored
the master contains two main tables

map of the file name to an array of chunk ids or chunks handles
maps chunk handle to

a list of chunk servers
the version number of the chunk
which chunk servers are primary

all the tabular data should be kept in memory in master for faster reads and writes

periodically syncs all data to non-volatile memory(disks) in case of failure, the newly elected master will load these data from disk

Responsibilities of slave node(s):

keep all data in sync with the master
in case of failure, elect a new master among the remaining nodes to act as the primary server for redirection

Chunking service(servers)

The chunking service(servers) is responsible for chunking the file and storing it on disk(non-volatile). Files are chunked in smaller parts, as the files can be very big, and to update, we may not require the whole file to be loaded again and again. It will also be easier to replicate and synchronize small files across secondary servers and clients if multiple clients are connected at the same time.

How reads and writes happen?

Both metadata service and chunking service are involved in any kind of reads or write.

Reads:

API: read(file_name, offset)

file_name: will be a unique identifier for the file
offset: will be the starting point in the whole file, from where it will start reading

the read request from the client will first go to metadata service, which will return

chunk handle for the file and offset
list of chunk servers, including the primary and secondary(replicas) servers

the above information will also be cached, as the same call will be very frequent
then the read request will go to the chunk server as read(chunk_handle, offset) where chunk_handle will have the information about the chunk version

this will return the chunk of the file from one of the secondary chunk servers

Writes:

API: write(data, file_name)

data: is the data that will be appended to the end of the file
file_name: will be a unique identifier of file to be written

the request will go to metadata service, which will create a new chunk identifier for new data and

will store chunk handle, version
find up to data replicas(chunk servers)

elect one of them to be primary, others to be secondary

master of metadata server will increment the version number and writes it to disk
sends primary and secondary a message for the updated version number, elected primary server, and list of secondary servers for the given chunk handle
the primary server picks and sets the offset for the data
send all replicas a request to write at the offset

if all replicas respond with "success", returns "success" to the client
if any secondary server responds with "fail" or doesn't respond within a given time, returns "failed" to the client

WHAT IF the metadata service thinks the primary chunk server is dead?

This may be due to various scenarios such as network failure, packet loss, etc due to which the metadata service thinks the primary chunk server is dead, so it will elect and assign a new primary server and update its database.

But if in actuality, it's not dead, it can be the case that the primary server is even responding to the client and to other secondary servers as well, but disconnected from metadata service.

In this case, it will elect a new primary server, and we will be having two primary servers, which is a big problem.

This problem is called a "split-brain" problem which mainly occurs due to network partition.

To solve this, the master can assign a TTL to primary, i.e. for how much time it will be primary, and stop taking any requests after the TTL ends.

After TTL ends, it will check for available nodes and chooses one of them to be primary for a given lease again making the remaining secondary, and updates its database accordingly.

The value of TTL can be chosen as per the consistency and availability requirements, as it will not be updating it's primary even if the primary dies until the TTL ends.

Thursday, 20 May 2021

System Design Interview Prep Material

All system design youtube channels

https://www.youtube.com/user/dimakorolev/videos

2. https://www.youtube.com/c/ByteByByte/videos

3. https://www.youtube.com/channel/UC_n-A84J0UcU5uq4sEh2CnQ

4. https://www.youtube.com/c/DefogTech/videos

5. https://www.youtube.com/c/HusseinNasser-software-engineering/videos

6. https://www.youtube.com/c/SystemDesignInterview/videos

7. https://www.youtube.com/c/sudoCODE/videos

8. https://www.youtube.com/c/codeKarle/videos

9. https://www.youtube.com/c/CMUDatabaseGroup/videos

10. https://www.youtube.com/c/interviewingio/videos

11. https://www.youtube.com/c/GauravSensei/videos

12. https://www.youtube.com/c/EngineeringwithUtsav/videos

13. https://www.youtube.com/channel/UClB4KPy5LkJj1t3SgYVtMOQ/videos

14. https://www.youtube.com/c/ExponentTV/videos

15. https://www.youtube.com/watch?v=cQP8WApzIQQ&list=PLrw6a1wE39_tb2fErI4-WkMbsvGQk9_UB

16. https://www.youtube.com/c/TheInterviewSage/videos

17. https://www.youtube.com/c/ThinkSoftware/videos

18. https://www.youtube.com/c/SuccessinTech/videos

19. https://www.youtube.com/c/TechDummiesNarendraL/videos

20. https://www.youtube.com/c/OktaDev/videos

Important Books :

Imp keywords

1. Write ahead logging

2. SSL passthrough / termination on load balancers

3. Clock vectors

4. Hinted handoff

5. Bloom filters

6. Gossip protocols

7. Merkle trees

8. Paxos algorithm

9. Two phase commit

10. Two phase locking

11. Consistent hashing

12. Data replication

13. Total order broadcast

14. Write ahead logging

15. Isolation levels (read uncomitted, read comitted, repeatable read, serializable)

16. Quad trees (GeoHashin)

17. Inverse indexing - Google search/any search indexing

18. Gaming ranking - rank players based on score and faster.

19. Word search in trie - auto suggestions system design

20. Sort 5gb data in 1gb memory - merge sort

21. Paxos algo

22. Merkle Tree

23. Backpressure

24. Circuit breaker

25. Raft

26. Service discovery

27. Saga

28. Hyperloglog

Important algorithms

https://github.com/resumejob/system-design-algorithms

● Frugal Streaming

● Geohash / S2 Geometry

● Leaky bucket / Token bucket

● Loosy Counting

● Operational transformation

● Quadtree / Rtree

● Ray casting

● Reverse index

● Rsync algorithm

● Trie algorithm

● Consistent Hashing

● Count-Min Sketch

● Bloom Filters

● HyperLogLog

● Skip Lists

● LRU

● B tree

● Hierarchical Timing Wheels https://blog.acolyer.org/2015/11/23/hashed-and-hierarchical-timing-wheels/

● Merkle trees

● Fenwick Tree - http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=2FDD6F53D3DC3BB91FA42E7277B6765B?doi=10.1.1.14.8917&rep=rep1&type=pdf

● AMS (Alon Matias Szegedy) algorithm

Cloud design patterns

https://docs.microsoft.com/en-us/azure/architecture/patterns/index-patterns

Cloud arch pattern

Ambassador	Create helper services that send network requests on behalf of a consumer service or application.	Design and Implementation, Operational Excellence
Anti-Corruption Layer	Implement a façade or adapter layer between a modern application and a legacy system.	Design and Implementation, Operational Excellence
Asynchronous Request-Reply	Decouple backend processing from a frontend host, where backend processing needs to be asynchronous, but the frontend still needs a clear response.	Messaging
Backends for Frontends	Create separate backend services to be consumed by specific frontend applications or interfaces.	Design and Implementation
Bulkhead	Isolate elements of an application into pools so that if one fails, the others will continue to function.	Reliability
Cache-Aside	Load data on demand into a cache from a data store	Data Management, Performance Efficiency
Choreography	Let each service decide when and how a business operation is processed, instead of depending on a central orchestrator.	Messaging, Performance Efficiency
Circuit Breaker	Handle faults that might take a variable amount of time to fix when connecting to a remote service or resource.	Reliability
Claim Check	Split a large message into a claim check and a payload to avoid overwhelming a message bus.	Messaging
Compensating Transaction	Undo the work performed by a series of steps, which together define an eventually consistent operation.	Reliability
Competing Consumers	Enable multiple concurrent consumers to process messages received on the same messaging channel.	Messaging
Compute Resource Consolidation	Consolidate multiple tasks or operations into a single computational unit	Design and Implementation
CQRS	Segregate operations that read data from operations that update data by using separate interfaces.	Data Management, Design and Implementation, Performance Efficiency
Deployment Stamps	Deploy multiple independent copies of application components, including data stores.	Reliability, Performance Efficiency
Event Sourcing	Use an append-only store to record the full series of events that describe actions taken on data in a domain.	Data Management, Performance Efficiency
External Configuration Store	Move configuration information out of the application deployment package to a centralized location.	Design and Implementation, Operational Excellence
Federated Identity	Delegate authentication to an external identity provider.	Security
Gatekeeper	Protect applications and services by using a dedicated host instance that acts as a broker between clients and the application or service, validates and sanitizes requests, and passes requests and data between them.	Security
Gateway Aggregation	Use a gateway to aggregate multiple individual requests into a single request.	Design and Implementation, Operational Excellence
Gateway Offloading	Offload shared or specialized service functionality to a gateway proxy.	Design and Implementation, Operational Excellence
Gateway Routing	Route requests to multiple services using a single endpoint.	Design and Implementation, Operational Excellence
Geodes	Deploy backend services into a set of geographical nodes, each of which can service any client request in any region.	Reliability, Operational Excellence
Health Endpoint Monitoring	Implement functional checks in an application that external tools can access through exposed endpoints at regular intervals.	Reliability, Operational Excellence
Index Table	Create indexes over the fields in data stores that are frequently referenced by queries.	Data Management, Performance Efficiency
Leader Election	Coordinate the actions performed by a collection of collaborating task instances in a distributed application by electing one instance as the leader that assumes responsibility for managing the other instances.	Design and Implementation, Reliability
Materialized View	Generate prepopulated views over the data in one or more data stores when the data isn't ideally formatted for required query operations.	Data Management, Operational Excellence
Pipes and Filters	Break down a task that performs complex processing into a series of separate elements that can be reused.	Design and Implementation, Messaging
Priority Queue	Prioritize requests sent to services so that requests with a higher priority are received and processed more quickly than those with a lower priority.	Messaging, Performance Efficiency
Publisher/Subscriber	Enable an application to announce events to multiple interested consumers asynchronously, without coupling the senders to the receivers.	Messaging
Queue-Based Load Leveling	Use a queue that acts as a buffer between a task and a service that it invokes in order to smooth intermittent heavy loads.	Reliability, Messaging, Resiliency, Performance Efficiency
Retry	Enable an application to handle anticipated, temporary failures when it tries to connect to a service or network resource by transparently retrying an operation that's previously failed.	Reliability
Scheduler Agent Supervisor	Coordinate a set of actions across a distributed set of services and other remote resources.	Messaging, Reliability
Sequential Convoy	Process a set of related messages in a defined order, without blocking processing of other groups of messages.	Messaging
Sharding	Divide a data store into a set of horizontal partitions or shards.	Data Management, Performance Efficiency
Sidecar	Deploy components of an application into a separate process or container to provide isolation and encapsulation.	Design and Implementation, Operational Excellence
Static Content Hosting	Deploy static content to a cloud-based storage service that can deliver them directly to the client.	Design and Implementation, Data Management, Performance Efficiency
Strangler Fig	Incrementally migrate a legacy system by gradually replacing specific pieces of functionality with new applications and services.	Design and Implementation, Operational Excellence
Throttling	Control the consumption of resources used by an instance of an application, an individual tenant, or an entire service.	Reliability, Performance Efficiency
Valet Key	Use a token or key that provides clients with restricted direct access to a specific resource or service.	Data Management, Security

Data Management patterns

● 06/23/2017

● +3

Data management is the key element of cloud applications, and influences most of the quality attributes. Data is typically hosted in different locations and across multiple servers for reasons such as performance, scalability or availability, and this can present a range of challenges. For example, data consistency must be maintained, and data will typically need to be synchronized across different locations.

Additionally data should be protected at rest, in transit, and via authorized access mechanisms to maintain security assurances of confidentiality, integrity, and availability. Refer to the Azure Security Benchmark Data Protection Control for more information.

Pattern	Summary
Cache-Aside	Load data on demand into a cache from a data store
CQRS	Segregate operations that read data from operations that update data by using separate interfaces.
Event Sourcing	Use an append-only store to record the full series of events that describe actions taken on data in a domain.
Index Table	Create indexes over the fields in data stores that are frequently referenced by queries.
Materialized View	Generate prepopulated views over the data in one or more data stores when the data isn't ideally formatted for required query operations.
Sharding	Divide a data store into a set of horizontal partitions or shards.
Static Content Hosting	Deploy static content to a cloud-based storage service that can deliver them directly to the client.
Valet Key	Use a token or key that provides clients with restricted direct access to a specific resource or service.

DATA MANAGEMENT PATTERNS

Design and Implementation patterns

● 06/23/2017

● 2 minutes to read

Good design encompasses factors such as consistency and coherence in component design and deployment, maintainability to simplify administration and development, and reusability to allow components and subsystems to be used in other applications and in other scenarios. Decisions made during the design and implementation phase have a huge impact on the quality and the total cost of ownership of cloud hosted applications and services.

Pattern	Summary
Ambassador	Create helper services that send network requests on behalf of a consumer service or application.
Anti-Corruption Layer	Implement a façade or adapter layer between a modern application and a legacy system.
Backends for Frontends	Create separate backend services to be consumed by specific frontend applications or interfaces.
CQRS	Segregate operations that read data from operations that update data by using separate interfaces.
Compute Resource Consolidation	Consolidate multiple tasks or operations into a single computational unit
External Configuration Store	Move configuration information out of the application deployment package to a centralized location.
Gateway Aggregation	Use a gateway to aggregate multiple individual requests into a single request.
Gateway Offloading	Offload shared or specialized service functionality to a gateway proxy.
Gateway Routing	Route requests to multiple services using a single endpoint.
Leader Election	Coordinate the actions performed by a collection of collaborating task instances in a distributed application by electing one instance as the leader that assumes responsibility for managing the other instances.
Pipes and Filters	Break down a task that performs complex processing into a series of separate elements that can be reused.
Sidecar	Deploy components of an application into a separate process or container to provide isolation and encapsulation.
Static Content Hosting	Deploy static content to a cloud-based storage service that can deliver them directly to the client.
Strangler Fig	Incrementally migrate a legacy system by gradually replacing specific pieces of functionality with new applications and services.

DESIGN AND IMPLEMENTATION PATTERNS

Messaging patterns

The distributed nature of cloud applications requires a messaging infrastructure that connects the components and services, ideally in a loosely coupled manner in order to maximize scalability. Asynchronous messaging is widely used, and provides many benefits, but also brings challenges such as the ordering of messages, poison message management, idempotency, and more.

Pattern	Summary
Asynchronous Request-Reply	Decouple backend processing from a frontend host, where backend processing needs to be asynchronous, but the frontend still needs a clear response.
Claim Check	Split a large message into a claim check and a payload to avoid overwhelming a message bus.
Choreography	Have each component of the system participate in the decision-making process about the workflow of a business transaction, instead of relying on a central point of control.
Competing Consumers	Enable multiple concurrent consumers to process messages received on the same messaging channel.
Pipes and Filters	Break down a task that performs complex processing into a series of separate elements that can be reused.
Priority Queue	Prioritize requests sent to services so that requests with a higher priority are received and processed more quickly than those with a lower priority.
Publisher-Subscriber	Enable an application to announce events to multiple interested consumers asynchronously, without coupling the senders to the receivers.
Queue-Based Load Leveling	Use a queue that acts as a buffer between a task and a service that it invokes in order to smooth intermittent heavy loads.
Scheduler Agent Supervisor	Coordinate a set of actions across a distributed set of services and other remote resources.
Sequential Convoy	Process a set of related messages in a defined order, without blocking processing of other groups of messages.