System design notes
The notes for 229 lessons of System Design for Interviews and System Design Advanced, by Gaurav Sen, in the order the courses teach them. Lessons marked free can be watched without an account.
System Design for Interviews
How do I use this course?
- What do we offer?
Have you ever started a system design course and wondered which videos actually matter for your interview? This course answers that with one path of videos, which takes less than six hours. Most of your interview preparation should come from this path. The path starts with Building an Ecommerce App. In eleven episodes, we take a small online shop and scale it, adding servers, caches, rate limits and microservices as the traffic grows. The first four videos are free. After that, we go deeper into networks, databases, consistency, messaging and the tradeoffs you make in every design. Then we use these ideas to design WhatsApp, Instagram, Uber's ride matching and a distributed rate limiter. The path ends with interview tips, so that you know how the interview runs. Most chapters have quizzes, PDF summaries and book readings beside the videos, and some designs end with an exercise where you complete the design yourself. Each lesson also shows what it covers, and has your notes and a discussion with other learners. Everything else is under Additional Resources, at the bottom of the course. This has more lessons on each subject, API design, caches, Tinder, Hotstar, Gmail and recordings of past classes. These are not counted in your progress, so you can pick them up when you want to learn more. I hope you enjoy the course. Cheers.
Building an Ecommerce App: 1 to 1M
- #4.1: Tech Decisions and Cost Estimation
Estimation is a back of the envelope calculation of how much data is stored, how much memory is consumed, and how much bandwidth and how many servers a design needs. The founder asks subjective questions, each answered with numbers: Microservices. A small company without a team greater than 10 or 15 people has no need for them. A slow language. Node.js may be two or four times slower than optimized languages, so the serverless compute costs more. Cheaper hiring and training offset that cost. The cost of a feature, such as users seeing themselves wear the t-shirt on camera. It is the cost of each API call, into 1000 calls a day, into 30 days. The cost of storage. A thousand video files of 1 MB each are 1 GB per day in S3. The order is to meet all requirements, keep the design simple, and then optimize the cost. The externally visible code matters most: API contracts and service level agreements. A complex API contract takes developers a long time to understand.
- Capacity Planning and Estimation: How much data does YouTube store daily?
Back-of-the-envelope calculations are often expected in system design questions. They help logically state the parameters influencing a result, and estimating the capacity requires multiple estimations on the way. Also lets us individually state our assumptions. Eg: Estimate the hardware requirements to set up a system like YouTube. Eg: Estimate the number of petrol pumps in the city of Mumbai. Chapters 00:06 Storage Requirements 01:20 Supplementary storage requirements 03:54 Back of Envelope calculations 05:38 Youtube caching estimation 08:58 Youtube video processing estimation 12:14 Conclusion ------STORAGE Let's start with storage requirements: About 1 billion active users. I assume 1/1000 produces a video a day. Which means 1 million new videos a day. What's the size of each video? Assume the average length of a video to be 10 minutes. Assume a 10 minute video to be of size 1 GB. Or... A video is a bunch of images. 10 minutes is 600 seconds. Each second has 24 frames. So a video has 25*600 = 150,000 frames. Each frame is of size 1 MB. Which means (1.5 10^5) (10^6) bytes = 150 GB. This estimate is very inaccurate, and hence we must either revise our estimate or hope the interviewer corrects us. Normal video of 10 minutes is about 700 MB. As each video is of about 1GB, we assume the storage requirement per day is 1GB * 1 million = 1 PB. This is the bare minimum storage requirement to store the original videos. If we want to have redundancy for fault tolerance and performance, we have to store copies. I'll choose 3 copies. That's 3 petabytes of raw data storage. What about video formats and encoding? Let's assume a single type of encoding, mp4, and the formats will take a 720p video and store it in 480, 360, 240 and 144p respectively. That means approximately half the video size per codec. If X is the original storage requirement = 1 PB, We have X + X/2 + X/4 + X/8 == 2*X. With redundancy, that's 2X 3 = 6 X. That's 6 PB(processed) + 3PB (raw) == 10 PB of data. About 100 hard drives. The cost of this system is about 1 million per day. For a 3 year plan, we can expect a 1 billion dollar storage price. Now let's look at the real numbers: Video upload speed = 3 * 10^4 minutes per minute. That's 3 * 10^4 * 1440 video footage per day = 4.5 * 10^7 minutes. Video encoding can reduce a 1-hour film to 1 GB. So 1 million GB is the requirement. That's 1 PB. So the original cost is similar to what the real numbers say. If we are off by order of magnitude, it's good. However, being off by 3 or more orders of magnitude is too much. We can then highlight the following: Where our assumption was wrong, or Which factor we didn't take into account.
- #5: Scaling Servers and Load Balancing
Horizontal scaling serves more requests with more machines, and vertical scaling with bigger machines. The app grows and the AWS bill becomes quite expensive. Serverless charges a premium because AWS manages the servers end to end. Each fix creates the next problem: A reserved instance. The server is rented from AWS for a year at a discount. A bigger instance. Memory runs out, so large becomes extra large. The single server is underutilized at night and has no backup when it crashes. It gives 32 virtual computers where 32 small computers give 64 for the same money. Multiple smaller instances. A crashed server's requests have to be redirected, and requests have to be sent roughly evenly. A load balancer. AWS Elastic Load Balancer routes the requests across the EC2 instances. Round robin is a stateless algorithm: requests go to servers 1, 2, 3 and 4 in a cyclic fashion. Least connections is stateful: with 20, 30 and 40 requests on three servers, the new request goes to the server with 20.
- Load Balancer Summary PDFPDF
- #6: Caching and Consistent Hashing
Caching is taking a temporary copy of the data and storing it close to what needs it, for low latency. The call to the server for the list of t-shirts is slow. Each fix creates the next problem: An in-memory cache, a map of product ID to product data inside each server. It is fast and simple, but a restart loses it, and coordination between the caches is complex. A single global cache such as Redis. It holds one copy of the data and scales independently of the application servers. As the system scales, one cache server is not enough. Sharding. The hash of the t-shirt ID modulo the number of servers gives the cache. Going from 3 servers to 4 leaves 1 by 12 of the keys where they are. Consistent hashing. Server IDs are hashed onto a ring, and a request goes to the next clockwise server. Removing a server impacts only one server. With few servers the chance of a skew is high. Plotting 20 virtual points for each server reduces it.
- #7: Cache Write and Eviction Policies
Four factors decide how well a cache performs: its placement, data distribution, write policy and eviction policy. The founder needs three large Redis instances for the t-shirts data. The code shows what is wrong: The most popular t-shirts are queried from the database every time, because the cache can become stale. Popularity does not need the latest data, so the cache expires after one hour or six hours. A user's recently viewed t-shirts are stored as heavy objects. Storing only the t-shirt IDs removes the duplicate information. A write policy keeps the cache consistent. Write-through updates the database first and then the cache. Write-behind updates the cache and writes to the database when the entry is evicted. That reduces the database load, but a Redis crash loses the updates. One entry per user grows with the users. The cache is fixed at a thousand entries, and an eviction policy decides which entry is evicted: least recently used or least frequently used. Under least frequently used, hot data takes a long time to reach the cache.
- #8: Traffic Spikes and Rate Limiting
A flash sale sells the t-shirts at a 50% discount for two hours, and the system survives the spike by dropping the requests it cannot process. The founder expects 10x the daily sales. The preparation has three steps: estimate the number of requests, preemptively scale the servers, and cache along the access patterns. Load testing finds how many requests one server can serve. The sale starts with 1 million concurrent users and the system collapses. The logs show the same user IDs making thousands of requests in seconds: a distributed denial of service attack. The fixes for the second sale, a week later: A web application firewall blocks bots at the CDN and the gateway. Graceful degradation. Payments, customer support and order status get the highest request priority. Short circuit fails requests in the upstream service, and backpressure drops them on arrival downstream. Concurrency with multiple threads, and gRPC, remove head of line blocking. At extreme scale the answer is rate limiting: a server that can manage 100 requests and gets 1000 drops 900.
- #9: Microservices and API Contracts
A microservice is a service owned by one team, with its own deployment cycle and its own setup. The team grows from 5 engineers to 15. Stand-ups carry non-overlapping updates, features take longer to ship, new engineers need hand-holding, and nobody is an expert at payments. The root cause is a single server's code with too many people changing it. The team is split into three: orders and payments, inventory, and communications. Each team deploys independently, scales its own service and is reached through API calls. Three drawbacks: Other teams know only the API signatures. Logging and caching are set up by every team, so effort is duplicated. A function call becomes a network call, which is less efficient. Teams split too quickly devolve into nano services: more projects than people. Every team publishes its API contract to one repository and ships a client library. A change from t-shirt ID to item ID and item type is a breaking change. A null item type treated as t-shirts keeps the API backward compatible.
- #10: Analytics and Data Pipelines
A data warehouse is a single copy of the data in every production database, kept for the business teams to query. The team scales from 15 engineers to 70, across 12 teams. The business teams report that engineers take a lot of time to run their queries, and that one business query needs data from the profile, orders and delivery teams. The core problem is that the business teams are coupled with the tech team for data insights. The fix: The data in the 12 Postgres databases is collected into a single data source. Business teams fire read queries on the copy, so a heavy analytics query does not overload a production database. A server exposes APIs for the dashboards and a SQL query interface for custom queries. Amazon Kinesis streams the data and Amazon Athena queries it. The product management team asks for open source: Apache Kafka for streaming, the Hadoop file system or CSV files on Amazon S3 for the store, and Apache Spark for queries. The microservices publish events to Kafka.
Networks Deep Dive
- HTTP, WebSockets, TCP and UDP
HTTP, WebSockets, TCP and UDP This video is everything you need to know about Hypertext Transfer Protocols. Let me ask you something. Can a server send a client request to the client by itself? Do you know about the web sockets? Wanna know about Transmission Control Protocol(TCP)? Get diving straight into the video folks.
- Summary PDF NetworksPDF
Databases Deep Dive
- SQL vs. NoSQL and Sharding
Difference between SQL and NoSQL A SQL database stores a record as rows across tables mapped by foreign keys, and a NoSQL database stores it as one blob of JSON. In SQL a person's address sits in a separate table, and address ID 23 maps to the row for Munich, Germany. In NoSQL the address is an object nested inside the person's object. The advantages of NoSQL: Insertions and retrievals need the whole blob, so the relevant data is kept together and no join is needed. The schema is flexible. A new attribute such as salary is added straight away, where SQL adds a column under locks on the table. Horizontal partitioning is built in, with a focus on availability. It is built for aggregations. The disadvantages: Not many updates are supported. ACID is not guaranteed, so financial systems do not use it for transactions. Relations are not implicit: there is no foreign key constraint. Joins are hard and manual. NoSQL fits data that is a block, with many writes and few updates. Sharding Sharding is horizontal partitioning: one attribute of the data is the key that breaks the data into pieces, and each database server gets one chunk. The range of user IDs is cut like a pizza, so that each slice is served by one database server. Tinder shards on location, so a query for the users in one city reads a single shard. The problems, and what answers each: Joins across shards. The query goes to two shards and joins the data across the network, which is extremely expensive. The shards are inflexible in number. Hierarchical sharding breaks a shard with too much data into smaller pieces, and a manager for the shard maps each request to the right piece. A shard fails. In a master-slave architecture writes go to the master and reads are distributed across the slaves. If the master fails, the slaves choose a master among themselves. An index on a shard can be on a different attribute, such as age within New York.
- Summary - Database ShardingPDF
- NoSQL databases SummaryPDF
Consistency in Distributed Systems
- Data Consistency
What is Data Consistency? Consistency is a measure of how up to date a piece of data in a distributed system is. A read that reflects all of the updates on a piece of data comes from a highly consistent system. A read that returns stale data, old data without the recent updates, comes from an inconsistent or weakly consistent system. Consistency matters for two reasons: A highly consistent system is easier to reason about, because every update is reflected in all of the data in the system. Users appreciate their changes being reflected. A user likes a post and refreshes the page. The like is still on the post, and the user is happy. A like that has not been registered after the refresh is not appealing. It is the engineer's responsibility to make a system as consistent as possible. The chapter covers the different levels of consistency a system can provide to its users, who are end users of the application or other engineers hitting the service APIs. Linearizable Consistency Linearizable consistency is the highest level of consistency: every update is reflected in every read request. The system is a single room with a single door, and each person is a request. A request enters the room, is processed and leaves. All other requests wait in a queue. With ordering forced in the queue, every request is processed in sequence, as if there is only one computer. The guarantee has two costs: High latency. A request that takes a long time inside the room makes everybody wait. This is head of line blocking. Low availability. A request that cannot be processed stops the system from responding, so the room is a single point of failure. Users get a highly consistent view of the world, and they rarely see it. A single thread implements this in a server, because all instructions inside it are executed in order. The thread is the queue and the processor is the room. Protocols like Raft maintain the ordering across distributed systems. Eventual Consistency Eventual consistency is the polar opposite of linearizable consistency: the server does not look at the ordering of the requests. A write request sets key 1 to 31, and a read request for key 1 follows it. The server sends both requests on in parallel. Three things make that possible: Different servers get different requests. The requests run concurrently on different threads. The database runs the queries in parallel. The responses can then come out of order. The read is executed first and the write second, so the read returns 21. A customer who changes the age on a profile from 21 to 31 and reads the page still sees 21. The customer retries the request and gets worried. A stale read like this is a problem for some applications. For others it is fine. An email goes to the outbox, and after some time, when the request succeeds, it goes to the sent box. A refresh that still shows the email in the outbox is not scary, because eventually it is going to be sent.
- PDF summaryPDF
- Consistency vs. Availability
Distributed data consistency Consistency means that multiple copies of the same data match each other. It is the C in the CAP theorem and the C in database transactions. The example is Facebook in its initial days: a single server at Harvard with a single copy of data. User A creates a profile, user B asks for it, and the server returns it from its database. The answer is always right. A single server has three problems: It is a single point of failure. A network outage or a power loss takes the system down. Vertical scaling costs a lot and hits a limit. Latency. A student at Oxford connects across a continent, about 100 milliseconds away. A second server at Oxford, with no communication between the two, serves each campus its own data. No data is shared. Sending a Harvard student to the Oxford server for Oxford data shares it, and keeps one copy. Vertical scaling is no longer a concern. The Oxford server is still a single point of failure, and the latency between continents is still high. Tradeoffs - 2 phase commit protocol Two phase commit is a protocol in which a leader asks its followers to prepare a transaction and then to commit it. The leader gets an update and sends a prepare request to its followers. Each follower begins a transaction, writes the statements, keeps the row locked and sends an acknowledgement. Only the commit is remaining. The leader commits to its own database and sends a commit message to everyone. Each follower commits and acknowledges. If the leader does not get all the acknowledgements for the prepare, it fails the transaction and tells the followers to roll back. A follower cannot roll back by itself on a timeout. If a commit message fails and the follower rolls back, a get returns C on the follower and C++ on the leader. So the leader keeps retrying the commit until it is acknowledged, and the transaction ID makes the retry idempotent. Until then, read and write operations on the row are blocked. The system is totally consistent, and the cost is that it is not available.
Messaging and Event Handling
- Messaging and Event Handling
The Message Queue: Problem Statement Asynchronous processing gives a client a confirmation at once and the result later, and it needs a list of pending orders that survives a failure. A pizza shop keeps taking orders while pizzas are being made. The client gets a confirmation that the order has been placed, not the pizza. The shop keeps a list: order 1, order 2 and so on. A new order is added to the queue, and a finished pizza is removed from it, after which the client pays. Two things follow from not making the client wait: The client does other tasks during that time. The pizza maker orders the tasks in the queue by priority. Then the shop becomes a chain: pizza shop 1, 2 and 3. If pizza shop 3 goes down in a power outage, its takeaway orders are dumped and its delivery orders are sent to the other shops. A list in memory does not allow this, because the computer shuts down with the shop. The list needs persistence, so it is stored in a database. Asynchronous processing: benefits A message queue takes tasks, persists them, assigns them to a server, and reassigns them when the server does not acknowledge in time. The setup is four servers, S0 to S3, and a database that stores every order: the order ID, the contents and whether it is done. S3 is serving orders 9 and 11 when it crashes. A notifier checks each server for a heartbeat every 10 or 15 seconds, and assumes a server that does not respond is dead. It queries the database for the orders that are not done and distributes them to the remaining servers. The query also picks up order 3, which another server is already processing, so two servers make the same pizza. Load balancing with consistent hashing removes the duplicates. Each server handles a set of buckets, and on a crash the remaining servers only get new buckets added, so order 3 stays where it was. A message queue, here a task queue, encapsulates the assignment, load balancing, heartbeat and persistence in one thing. RabbitMQ is an example. Publisher Subscriber Models In a publisher subscriber model a service publishes a message to a message broker, and the broker sends it to the subscribers. With requests and responses, S1 calls S0 and S2, and S2 calls S3 and S4. If S4 fails, S2 waits for a timeout and passes it to S1 and the client. S1 has already changed its database, and a retry changes it again. With a message broker, S1 publishes and sends a success to the client. The broker persists the message and replays it when S2 is back up. The services are decoupled, delivery is guaranteed at least once, and a new service S6 only registers with the broker. Two disadvantages: No atomicity. Account A has 1000. A transfer of 950 deducts a commission of 50 while the fund transfer service is down. A second transfer of 800 deducts another 50, leaving 900. When the service runs, the 950 fails and the 800 succeeds, leaving 100 where 0 was expected. No idempotency. A replayed message debits 50 again unless it carries a request ID.
System Design Tradeoffs
- System Design Tradeoffs
Pull vs. Push Architectures In a push architecture the service that owns an event sends it to everyone interested, and in a pull architecture the users query the service for it. Cristiano Ronaldo uploads an image on Instagram. Sending it to millions of followers in one shot overloads the server. The followers are of three types: big fans who want the notification immediately, 1 million Indian followers who want the image without a notification, and 10 million passive followers. Push, for the big fans. The notification service broadcasts on upload. Ten batches, six minutes apart, lower the peak load and reach every big fan in one hour. Pull, for the followers. They open the app at random times and query the notification service, so the load is much less spiky. Hybrid. The notification service pushes events to a message queue, which decouples the ingestion rate from the exit rate. Push has very low latency and leaves no stale notifications. Pull has lesser peak load, but a notification stays in the cache for 24 or 48 hours. Consistency vs. Availability Consistency versus availability is the trade-off between returning the latest data and returning a response at all. A consistent system gives the latest data in its response. If x is 10 and a write sets it to 20, a read after that returns 20. An available system gives a response within the time guaranteed in its service level agreement. A system that promised three hours and took six has timed out. The two fight wherever there is parallel processing or concurrency: A server answers a request for Brad Pitt's profile from its cache while his profile update runs in parallel. The read is processed at timestamp 5, the cache is updated at 6, and the response is the old profile. The update goes to the US database, and readers in India query the India database before the two are consistent. If the US database crashes, the India system still responds with old data: consistency sacrificed for availability. With a single source of truth the profile returned is the latest, and any failure stops the responses.
WhatsApp System Design
- WhatsApp System Design
System Requirements The system is WhatsApp, a chat-based application, and the requirements are the features chosen to fit an interview of one hour. The special things about WhatsApp are group messaging and read receipts. The candidate features: Group messaging. A WhatsApp group holds at most 200 people. Image sharing, and video sharing. Sent, delivered and read receipts: the tick marks that show the stage a message is on. Whether the person is online, and the last time they were seen on the chat. Whether chats are temporary or permanent. Temporary chats give the user privacy and power, and save storage space because the chats are stored only in the users' applications. Snapchat and WhatsApp are far more temporary than office messaging applications. If a user and the friend both delete the app, those chat messages are lost forever. Compliance and official communication need the message stored forever. Image sharing is left out, which leaves four features. Group messaging is the first. One to one messaging One to one messaging is one person sending a message to another, with sent, delivered and read receipts going back to the sender. A user to box mapping stored in the gateway takes memory away from TCP connections and is duplicated on every box. So the connection is kept dumb, and a sessions microservice stores who is connected to which box. A sends the message for B to gateway 1, which passes it to the sessions service. The message is stored in a database and retried till B gets it. A gets the sent receipt. The sessions service finds B's box and routes the message to gateway 2, which sends it to B. B acknowledges to gateway 2. The sessions service finds A's box, and A gets the delivery receipt. When B opens the chat, the same flow carries the read receipt. HTTP is a client to server protocol, so the server cannot send a message to B. Long polling is not real-time. WebSockets over TCP let the server send to the client. Last Seen Timestamps The last seen timestamp is the time of a user's latest activity, stored on the server as a key value pair of user to timestamp. B wants to know when A was last online. B asks the server, and A is not in the picture. Every activity of A, such as sending or reading a message, is a request to the server, and the current timestamp is persisted in the table. If A was online three seconds ago, B is shown online. The threshold is 10 or 15 seconds. A last seen microservice behind the gateway does the user activity tracking. Some requests are sent by the application itself, such as polling for messages or a delivery receipt. The client flags each request as a user activity or an app request. Only user activities go to the last seen service, which updates the timestamp for that user. B queries this service and is told that the user is online, or was last seen at the timestamp. Group Messaging Group messaging sends one user's message to every other member of the group. Who is in which group is decoupled from the session service into a group service. A user sends a group message to a gateway, which forwards it unparsed. A parser microservice converts it to an object in the internal protocol, such as Thrift. The session service asks the group service for the other members of the group, and gets their user IDs. The session service finds the gateway each user is connected to, and routes the message to each one. A group is limited in size, 200 on WhatsApp, because a larger group fans out the request too much. Requests to the group service are routed on the group ID with consistent hashing. A message queue retries a failed request, and after five retries the failure is propagated to the client. Delivered and seen receipts for a group are expensive. Under heavy load such as New Year's, unimportant messages like last seen are deprioritized.
- Architecture DiagramPDF
- Summary - PDFPDF
Instagram Design
- Instagram Design
Requirements The system is Instagram, and the requirements are four key features agreed with the interviewer. Storing and getting images is the only feature that is obvious in an Instagram interview. Every other feature is asked for, because the time constraints do not allow a deep design of all of them. Store and get images. Like and comment on posts. Follow someone. Every Instagram account is a user. Facebook is more complicated, because pages are followed too. Publish a news feed. An image is a post. The questions on a post are whether a comment takes a comment, which makes it recursive, and whether a comment takes a like. Instagram allows a like on a comment. It allows a reply to a comment but no reply to a reply, so there is one level of comment and then reply. That keeps the complexity constrained. Here the design is simpler still: a post takes a single comment, a comment takes a like, and a comment takes no reply. Designing the Data Schema The data schema for liking and commenting on Instagram is an ER diagram of likes, comments, posts and an activity table. The likes table holds a like ID, the user ID, the timestamp and whether the like is active. A like is on a post or on a comment, so the table holds a parent ID and a type field, comment or post. The type tells where to query. The number of likes on a post has three designs: A select count from likes where the post ID matches. A news feed with many posts fires many of these, and it is slow. A likes column on the post and on the comment, incremented on each like. It is aggregation information, and it does not belong in the original table. An activity table that stores the number of likes for each parent ID. It needs no type. The comment has an ID, the text and a timestamp. The post has a user ID, which answers a query for all the posts of a user. Following Users Following is one user following another user, and it is stored in a single table. The table has three columns: the follower user ID, the followee user ID and the time at which the following started. The follower is the person who is following someone. The followee is the person who is being followed. Gaurav follows Stephen Hawking, and the row holds the two user IDs and today's timestamp. The table answers two questions: Who follows me. An equals condition on the followee column with Hawking's user ID gives all his followers as a list. Who are the people I follow. A single equals on the follower column with Gaurav's user ID gives their user IDs, Bill Gates among them. In an interview, an answer that is known and given directly saves time for the interviewer and the candidate, and shows preparation. The interviewer expects to ask more questions, and a quick answer to a simple one leaves time for the advanced topics. User Feed Service The user feed service returns the user feed: the top 20 posts a user needs to look at. A cell phone reaches the server side through a gateway. The gateway is the reverse proxy. It holds security mechanisms such as authentication tokens, and converts external protocols such as HTTP into an internal protocol. The service runs on multiple servers. A load balancer keeps the state of the entire system and sends it to the gateway as a snapshot, updated every 10 seconds. The gateway hashes the user ID to find the box. The feed is computed in a chain: The follow service returns the users followed by that user. The posts service returns the posts of each of them, so 10 followed users mean 10 requests. One call that takes a set of user IDs returns all the posts in one go. A limit on the number of posts reduces the load on the database and the network. This does not scale. Every feed request recomputes all the posts, and the posts service gets bombarded. Scaling the Instagram news feed A precomputed user feed is a list of posts kept ready for each user, so a feed request is answered in one shot. The feed is updated when a followed user posts: The post request goes to the posts service and is persisted in the database. The posts service notifies the user feed service. The user feed service gets the followers of the poster and adds the post to each one's queue. A queue holds at most 20 posts. The queues live in a cache. Lost data is recomputed with the brute force formula, and the feed of a user who logs in infrequently is dropped and recomputed at login. The user feed service notifies the followers. Polling every ten seconds costs the cell phone bandwidth and battery. A push over WebSockets is seamless. A celebrity has millions of followers, and a million notifications at once crash the system. Batch processing rate limits them. In the pull model the followers ask the server. The answer is a hybrid: pull for a celebrity, push for a normal user.
- Summary - PDFPDF
Design a Cab Aggregator App like Uber
- Uber: Ride Matching
Requirements of a cab aggregator A cab aggregator takes a person in a cab from a pickup point to a destination. Uber, Ola and Lyft are examples. A person books a cab on the phone and sees a price. On accepting it, the request goes out to nearby cabs, from a smaller radius to a larger one, and one of them accepts. The cab moves from its location A to the pickup B, and then to the destination C. Food delivery picks up only from restaurants and drops at addresses already in the profile. A cab picks up and drops anywhere on the map, so it is the most complex case. The core requirements: Pricing, calculated in real time from who the customer is, the pickup and the drop. Surge pricing. When demand is more than supply the price goes up, dynamically. Ride matching with a nearby driver. Driver location updates, which feed the ride matching. Estimated time of arrival, which decides the next ride a driver picks up. Profile creation, driver insurance and reviews are not core. Ride Matching Ride matching finds a nearby driver for a user who wants a ride from a source to a destination. The world map is split into squares with a side of one kilometer, because a person does not walk more than one kilometer. Each region holds its demand: the number of interested customers divided by the number of drivers. The supply for a square is an educated guess: all the drivers in the three by three block around it, which is nine squares. A smarter guess takes more time, and the customer drops off. The higher the demand, the higher the price. Ride matching optimizes several factors: the driver wants to keep driving and earn, and the customer wants to reach quickly. Proximity is defined in terms of time, not distance, because a river or a road block sends a nearby driver all the way around. A driver 15 minutes away is likely to be cancelled. Calling Google Maps for every request costs a lot, so the estimated time of arrival is built in-house. Matching Drivers with Live Rides A driver on a live ride is matched to a new pickup when the time to finish the current ride and then reach the pickup is within the threshold. Ride matching for available drivers: The drivers in the nine squares around the pickup are queried. Each driver whose estimated time of arrival is within a threshold, such as five minutes, is sent the request. If none accepts, the size of the square is increased. A driver accepts, or the ETA is too high and the ride is cancelled. A driver on a ride is a candidate when the ETA from current location to destination, plus the ETA from destination to pickup, is less than or equal to the threshold. The first ETA is constantly calculated and stored for every driver, so it is an order one computation. The second is calculated on the fly, and running it for 500 drivers is expensive. Two filters apply: the driver's time to reach the destination is within the threshold, and the destination is in the squares near the pickup.
Distributed Rate Limiting
- Distributed Rate Limiting
The Oracle and the Timer Wheel Rate limiting is taking in requests in proportion to how many the server can serve. Without it, one crash collapses the system. Four servers serve 300 requests each. S2 dies and its requests are distributed, so S3 serves 400 against a capacity of 350 and crashes. S4 gets 600 and crashes. S1 gets 1200 against a capacity of 1000 and crashes too. The gateway asks an oracle whether to process a request. Each service registers its capacity with the oracle on startup. On a no, the gateway drops the request and sends a 503. A sliding window. The oracle keeps each request ID and timestamp and allows three requests per minute. It is simple and correct, but the memory footprint is high and expired requests have to be found on every request. A timer wheel. The wheel's size is the request timeout, six seconds. A request goes to the slot at time mod wheel size. When the pointer reaches a slot, every request in it has expired and is kicked out. The memory footprint is small. Partitioning and Real-life Optimisations A service that gets requests from internal services limits their rate itself, because asking the oracle for every internal message is a big deal. Three metrics show a service under load: the average response time, the age of messages in the queue, and the count of the dead letter queue. A bad actor S2 fills the queue. The queue is partitioned: the hash of the request ID, mod the number of queues, gives the queue ID. S2's requests all hash to one queue, and the others are fine. With five queues, 20 percent of the users are still affected. More queues, larger queues, or a hierarchical split with a second hash function mitigate this. Request collapsing. On a cache miss the request is stored against a future object. Clients asking for the same expensive computation wait on the same future, so the database gets one request. Client side rate limiting. A permanent error is not retried. A temporary error is retried with exponential backoff: a wait of one second, then two, then four, up to 10 seconds.
- Architecture DiagramPDF
- Capacity EstimationsPDF
- Summary PDF - Rate LimitingPDF
- API ContractsPDF
- FAQsPDF
Interview Tips
- System Design Tips
Here are 5 Tips for System Design interviews. They are helpful when preparing for a System Design interview. 1. Don't get into details prematurely 2. Avoid fitting requirements to a set architecture in mind 3. Keep it simple, stupid! Remember to look at the big picture and avoid too many hacks when solving. 4. Have justifications for the points you make. Don't use buzz words or half hearted thoughts in your design. 5. Be aware of the current solutions and tech practices. A lot of solutions can be purchased off the shelf which simplify implementation. You should be able to argue for a custom implementation with it's pros and cons. Have these on the back of your mind during you interview, and all the best! Here are three major points evaluated during the interview: 1. Clarity of Thought a. Express your thoughts in a clear manner. b. Justify your decisions. Critical reasoning and argument are key to a successful software design. c. When faced with a problem, use standard approaches to mitigate it. For example, say you are faced with an availability problem. State that replication and partitioning help increase availability in general, and move on to offer a solution. d. Don’t make points without thinking them through. Half-hearted attempts at solving problems are frowned upon heavily. 2. Know about existing solutions a. Stay up to date with the current solutions in the market. This includes products and design practices. If NoSQL is being adopted left right and center, you need to be aware of it. b. Know when to pick a solution vs. building something custom. If you name a product, you should be (generally) aware of the features it provides. c. Design practices enable you to meet custom requirements. Examples are decoupling systems, load balancing, sticky sessions, etc… 3. Flexibility a. Switch your targets as the requirements shift. If the interviewer wants to know about one particular part of the system, do it first. b. Never have a set architecture in mind. We all try to fit requirements to a system, but only after it has been shaped by the initial ones. A rigid attitude creates a brittle architecture. It will break before you do. c. Take a step back at times to make adjustments to the general architecture. Being focused on one part can narrow our vision and bloat those areas. There will be components which can be extracted out and extended to the rest of the system.
Zoom Meets
- October - Kafka Internals
What was cooking up interesting in the zoom class?? What's life without exploring? In this zoom class let us explore Kafka! How many of us know about the Kafka internals? Kafka is ubiquitous. The questions that come up to our mind when we want to dig deep into Kafka are: How is Kafka Internally built? It's a log. A log is a file where u write one line and when there is a new event you write another line. Every line will have a delimiter. Every line is appended after the delimiter. Why Kafka doesn't work on queues(priority)? Queues are implemented using linked lists or an array. The mechanism of Kafka doesn't give any priority. Kafka is fast, scalable, and distributed in nature by its design, partitioned and replicated commit log service. So there is no priority on topic or message. All events belonging to a topic need to be ordered. For example, Let's say we have topics A B C and P Q R. For instance, if all this is jumbled like P Q A B C R Rules: P comes before Q And Q comes before R The original order need not be maintained. We need to care about ordering between inside the topics not in between topics. Wherein C will be consumed by the consumer only after B gets consumed. What is Causal ordering? As long as relevant messages are sent to the same partition, message (causal) ordering is still guaranteed. In Kafka, this is achieved using keyed messages. Kafka partitioners would hash keys and ensure a key always goes to the same partition given the number of partitions is not changed. How do u search in a log? A log has a key and value. The log is already sorted by key. How we usually query is based on timestamp or the machine id. Instead of taking any random key, we take the 128 bits key and use 64 bits to store the timestamp. For Example: 18th August_123 Where ‘_’ is used as a delimiter. Elastic search The basic idea is it is a no-sequel database. It has key-value pairs. It is good at text search and aggregations. You can add tags to it. An Elasticsearch index is a collection of documents that are related to each other. Benefits of using Kafka Limited persistence Fast in terms of writing(if u want to read fast use another database). Used for debugging Finally, If a very popular search text exists how do u find the document that it exists in and store it efficiently? I leave it here for you to discover. Let me give out a little secret! This zoom class has the answer to this question!
- October 2022 - Implementing a File System
In this zoom video, get ready to start with interview-ready tips. Let's say there are 5-6 servers and there is a load balancer... How are the requests monitored? If we have authentication in the load balancer it becomes a gateway that checks whether a request is valid or not. If we need extra authentication needed( for example, only admins can send requests to a particular server), the question arises of where we should have the authentication logic. If you are up for scaling then you must be opting Load Balancer Authentication. The drawback of this method is that you will have to deploy a load balancer every time a request is sent. Another drawback is that it is a single point of failure. Who will handle authentication when the Load balancer is gotten rid of? AuthService We have an Auth service which takes in request from load balance them validates and send them back. What if I tell you we have a video to explain this? Go ahead and watch the video on Authentication and Global caching under the High-Level Design. Service Registry If we are going to have a sidecar to take care of invalidation, how do you maintain the states? The consistency becomes a question. The state here is the cache that we use. What is a sticky session? Dive into the video on time stamp 23: 50 to know more. Authentication for multiple systems works in different ways. The architecture-wise where you give the authentication matters in terms of performance. You have a bunch of externally exposed services one of the things you can do is if it is coming from the service which is sending the request can say whether it needs to be authenticated or not. If internal services are not talking to each other and the sidecar feels that the request need not be authenticated, the authentication can be bypassed. Benefits Of Compression: Lower bandwidth usage Faster to send Lesser memory being used Why shouldn't we compress messages? Computational overhead Time-taking latency. To know how to implement a file system in an interview dive into the time stamp- 1:19:00 and keep your knowledge caps open. For this problem, we need to be creating : 1. Create(file_id, content) 2. Read(file_id) 3. Update(file_id, content) 4. Delete(file_id) It's time for discovery. Go ahead, explorer. The zoom class answers this question!
- Pessimistic and Optimistic Locking
How to count the frequency of words from 1TB of file in 2 GB RAM consistency having only a single machine? There are 2 things that could be done in this case. To split the whole file into contents of 2 GB. The other approach would be to stream the file while tokenizing it and counting the number of words until it reaches the required size. Data Structures that can be used: Hash Maps The entire words of the file will be converted into a key set of 1 Terabyte long if there are distinct words in the file. The edge would be storing 1 next to all the hashed words of the file which will be altered with changing frequencies of the words. We might need concurrent hashmaps to deal with this problem The scatter-and-gather approach can be used to sort out the data. Have a look at the external Merge Sort algorithm (Which can also be used to solve this problem) Splitting the file into pieces is the complexity. Multi-threading can be used to solve this problem. Let's say we have a fileSplitter(n), There are 1,2,3 threads that are being passed. The splitter will split the file into pieces based on the number of words such that the limit memory is reached. We will have to stream through these chunks of threads. We will need to have seek() and parse() functions to go ahead with this method. Finally, we store all of this in hashmaps. Quick Fact!! BookMyShow makes use of Optimistic locks !! There are 2 copies to make sure your booking doesn't clash with already booked seats. While pessimistic locks won't create copies. The timestamps will help you to reach the point in the video where you can see a full video explanation of the same. Why not solve your doubts? When you are connecting to a server you are connecting to a port where multiple people connect. The server can identify who is connected to it. Let's go back to TCP connections, We take a message and route it through multiple routers and send it to a person. It is more of a logical concept rather than a physical one. Let's Move on to a system design problem: There is an e-commerce app which has a lot of price fluctuations for its products. They have a catalogue of schools that is already in the ERP systems. They want to add a new component to the e-commerce platform. Get to know the tips on how to solve this!! Come lets clear a user's doubt on over-utilizations of resources.
- Producers and Consumers: November Meet
This zoom meeting can never get interesting enough!! Get to know the resources on where to apply for SD roles from this zoom meet intro part.. Some websites that were discussed: Instahyre Cutshort Geektrust Angel.co Along with that why not hustle with a few more resolving doubts and general discussions? How do we handle 5000 transactions(writes) per second on a relational database with a max latency of 50 milliseconds? Moving ahead with the learning spree.. The first thing to note here is what type are consistency are looking at and what type of translation isolation level is needed? Choosing the translation isolation level in a wise manner will help increase concurrency. The requirements for the questions are below: The user should get appropriate tasks to work on based on skill language. Example: A user who only knows Hindi should be assigned Hindi tasks where these tasks should be served in order of priority and first come first serve basis. By default, users should get English tasks as well. The system management should also be able to view the life cycle of a job and we expect the people to be working in parallel. The system must be able to respond to the task within 15 milliseconds if the user is waiting for the job or not( If he is free). Let's take a queue and enter the tasks. This means that we have a priority queue which is implemented by a heap-based on which the tasks are served. Let's say we have multiple queues. The problem to address here is the priority and skill level of the worker and the language might be different. We will have a head-of-line blocking problem when we have the tasks blocking the assigning of work to the users based on priority when using only one queue. We can have a list of queues for the languages task and the queue is following FIFO(as we know) if the task on the front doesn't get assigned to any worker we upload that task to a separate log queue. We use the approach of using a sorted tree instead of a priority queue which makes the problem complexity O(log(n)). This is very similar to the Operating System Resources problem. Now, what happens when we use a hash map(brute force algorithm)? Depending on the language we have a worker. Then we see the skill level of the worker. To remove the problem where 2 workers pull the same task we shall assign locks. Acknowledgements for the acceptance or assignments of the tasks need to be mentioned. Some sort of expiry algorithm would do. Question: There are 2 services A and B deployed using EKS. What is the best way to communicate with each service? Also, where do we need to keep the URL? Go ahead and watch the video to know what is Gaurav’s take on this!!
- IRCTC Algorithm: December
We discuss how the IRCTC algorithm possibly works. It's a complex algorithm, but worth understanding! Irctc Algorithm Train ticketing system How do we efficiently book tickets in the ticket booking system so the seats don't remain vacant? It's a High-level design question. Example: There are 10 stations and some person X books seats from 1 to 5 and some other person wants to book from 6 to 8. How do we handle that? How do we know who booked prior? Here the exciting part is that we not only have to consider the allocations, but also we will have to search for trains. We draw the UML diagram by considering the following: •There is a Client who wants to book a seat through their web browser. •The clients say that they want to book a journey with the specifications • This is the case when the client wants to book a specific train. • The other option is when the client searches for all trains available to reach the particular destination with the number of seats, and start date. • The train should have information about the estimated time of arrival, estimated departure time, source, destinations, category and seats. Multiple perspectives and multiple calculations..let's head to see the exact answer. How do you book the seats? The other interesting fact is that the centre of gravity has to be taken into account or the train will be heavier on one side alone. If a single woman is travelling she needs to be placed with other women travelling on the same train. All these are the considerations that need to be considered. However, the brute force approach would be: Book from A - B ( 2 seats) The algorithm is like a rule engine. It goes through the preferences and chooses the best option for the client. The time the rule engine runs to check all the preferences will become a matter of consideration here. The duplication is good because it will make the search faster. Instead of a beat matrix, we can flatten it by making it an array. So how do we approach this? Let's head to the video!
- Google Docs and Chess Design Queries
Google Docs and Chess Design Queries When we use Google docs when we are sharing a document with someone else. Both will be able to edit the content of the docs. This makes it difficult to design the algorithm as we will have to lock based on the ranges. A specific algorithm is used for these kinds of test collaborations. The Operational Transform The algorithm is very complex. There is a video available in the System Design course for your reference. Let's move to the Chess design: The Chess design is going to have a gateway. The gateway speaks to another service that stores session data which does a protocol translation. In a chess design, the app should make regular changes. Different clients speak to the app to hit the services. The problem: If the API has a breaking change then all the clients need to be updated and restarted. When changing a version of the library you need to update and restart the services. The key here is to keep the gateway dumb as possible so that you do need not to restart the gateway. •Minor changes are not relevant • Services are not relevant • Breaking changes are not relevant The service registry needs to be dumb as possible. Apart from a reverse proxy it also acts as a parser. Let's say you are in version 3 of Google Docs and google docs says that a person deleted a character from the doc that will be stored in a new version. What happens is that one keeps drifting away from the lattice point. Eventually, the events are mapped to the current state. The algorithm will tell you how to do that. Each operation is mapped which will end up in the final result. Further, let's see what exciting discussions we have and how to approach them. Head to watch the full video to learn more!
- Jan 2023: DNS, CDNs, and everything in between
The process of navigating to a website, specifically mentioning the role of DNS servers and Content Delivery Networks (CDNs) in the process. When a user types in a website address, such as amazon.com, the request first goes to a DNS server which then determines which CDN to direct the request. The CDN acts as a first line of defense against Distributed Denial of Service (DDOS) attacks, and then the request goes to the real server (content server), which delivers the content. Protection from malicious attacks can be done at the CDN or Gateway level. He gives the example of a website hosted on S3, with the CDN being backed by S3 and replicating static content all around the world for low latency. The DNS server can determine the closest location for the user to connect and provide the appropriate IP address.
- Jan 2023: API design and other discussions
Gaurav discusses using consistent hashing in sharding and how requests are mapped to specific buckets in some distributed systems like Redis. There is a potential for one bucket to become overloaded due to a lack of uniform distribution. What is the potential latency when consumers pull during a load rebalancing event? Graph API vs. Open API. There are various ways to overcome the problem of an increase in logs, including compressing and archiving logs, scaling the storage for logs, and identifying which service is causing the increase in logs. It is impossible to stop an increase in logs as user activity increases, but steps can be taken to manage them more efficiently. Additionally, discussing with teams why they are logging so much is a practical consideration. The use of APIs and understanding how they work are essential. GraphQL may not be as helpful as REST in certain situations and clients must understand the objects beforehand. When there is a large request load on the API gateway, it can be scaled horizontally to handle the load, but that code can also be made more efficient. YouTube handles a similar scenario, but when there is too much load, the cached content can be used. There is a need to change and degrade the service in the API gateway when there is too much load. Gaurav shares his experience preparing for technical interviews, specifically for DSA. It's difficult to find an equilibrium between system design and DSA prep. It's essential to speak with the interviewer about their thought process and approach to a problem. For DSA, execution is very important, and being able to understand and catch hints is also essential. In an interview, it's best to be prepared and not overlook the importance of paying attention to the current needs. One complex DB query as an API versus using three different simple queries as three APIs: depends on the requirement, but usually, three simple queries are better, but sometimes it may be necessary to use one complex query for an atomic operation. We found a solution for handling large requests and responses for an API. The idea of breaking down a large request into smaller fragments and returning responses is applicable here. The input and decision on how to break down the request can depend on the business use case and that there is a separation of ingestion rate and persistence rate. We may also use an asynchronous approach, where data is uploaded and inserted into a database after all files have been processed and cross-checks can be made on the records.
- Feb 2023: Permission Management System
The video by Gaurav Sen covers a range of topics. The discussion starts with Kafka and SCS, which are message queueing systems. Gaurav suggests some resources for learning about Kafka, including Confluent's documentation. The conversation then moves on to managing permissions and naming conventions for meetings. The video ends with a design problem that involves designing an authentication system for microservices with complex rules for user actions.
- March 2023: Eventual Consistency Levels
In the video, Gaurav Sen talks about the importance of consistency in distributed systems. He gives an example of how likes on a post in a social media platform may not be immediately consistent across all nodes in the system, but it is still acceptable because it does not affect the overall experience. He also explains how consistency can be ensured in financial systems through settlements and reconciliations, and how a sorted string table can be used to maintain a record of changes in the system. Sen emphasizes that the level of consistency required depends on the application and the user's needs.
- March 2023: Fetch top K hits in a distributed system
The video by Gaurav Sen shows a session in which he discusses system design, specifically the difference between machine coding and low level design. He also discusses the types of questions asked during SD interviews and gives an example of a recommendation system. In the latter part of the video, he demonstrates how to solve a system design problem using Redis and hash maps to return the most popular blog posts in the last five and 15 minutes.
- April 2023: Distributed Consensus and Load Balancing
The video discusses the issue of ordering events in a message queue or event bus with multiple topics, using examples of services posting response times and events like create, update, and delete. Enforcing order by timestamps or using distributed consensus algorithms like Paxos or Raft is mentioned as a solution. The use of logical clocks like hybrid logical clocks or Lamport clocks is also discussed as an alternative to the Spanner implementation, which requires Google-level hardware. We also discuss the importance of enforcing order in the queue to ensure the sequential execution of instructions in a multi-threaded environment. It explains how a thread pool can mimic a queue and how events can be sent to different threads depending on whether they need to be sequentially ordered. The video also addresses questions related to hashing, partitioning, and handling multiple events across different services. Finally, it suggests that ordering across services can be complex and require engineering coordination.
- September - Design Judge Launch
We attempt multiple questions of the system design judge!
- October - Live Watch Party Design
We discuss the architecture and tradeoffs that come up when designing a live watch party system.
Networks Deep Dive
- Connecting to the internet: ISPs, DNS and everything in between
Connecting to the internet: ISPs, DNS and everything in between At times do you wonder how your computer connects to the internet? Now that you know the basics of networking, have you ever thought about where you get data from a server? What is the role of an IP address? Wanna know about the Internet backbone? Dive into the video for we are about to learn about Domain Name Servers and Internet Service Providers.
- Communication Standards: REST, GraphQL and GRPC
Communication Standards: REST, GraphQL and GRPC In this video you will learn about the following: In a microservice architecture, services need to communicate with each other. How do servers communicate internally? How do you communicate between services? Different services are written in different languages. But why do we need one common language to define the objects? How do you query the microservices? REST GraphQL gRPC (google Remote Procedure Call) is generally used by microservices to communicate internally. It is written over HTTP 2.0
API Design
- API Design
API Design Goals An API is a documented way in which external consumers interact with code. It is the contract: what the code does, not how. WhatsApp exposes getAdmins to find all the admins of a group. It takes a group ID as a string and returns a list of admin objects named admins. It has two errors: the group does not exist, or the group is deleted. The design runs through a checklist: Where it is exposed. In a microservice architecture, getAdmins belongs to the group service. Naming. The action defines the name. An API that also returns the groups the admins belong to is no longer getAdmins. Parameters. No additional parameters, except to optimize: information that saves the service four or five IO calls to other microservices. Response. A response stuffed for extensibility gives the caller more than it needs, costs network, and is confusing. Errors. Defining every possible error and returning one generic error are both extremes. A group that does not exist is an expected error, and a generic 404 for it is wrong. API Design in Practice An API on an HTTP endpoint has a route that says where the function is, an action, and request and response objects. The route holds the address of the site, the model, the function and a version such as v1. A POST to getAdmins carries the group ID as a JSON object, and the response is a JSON array of admins. Four rules of a clean API: Routing is kept apart from the action. A request with only a group ID is ambiguous. HTTP already defines GET, so the function is named admins. No side effects. A setAdmins that also adds members or creates the group does more than its name says. A missing group returns 404, and the client calls create group. A huge response is broken into pieces. Pagination gives the client an offset: of 200 members, the first 10 and then the next 10. Fragmentation numbers the pieces between services. Perfect consistency is slow. A cached response is slightly older, and returning only the essentials under database load is service degradation.
Databases Deep Dive
- Databases Deep Dive
What are Databases? A database is a store where structured data is written, updated and retrieved. A website stores the email and name of each registered user in a database, fetches them to check whether a user has already registered, and makes an update when the user changes the profile picture. A database is not the application server. The business and application logic sits in a separate server, because a code change and a restart are easier there. A move from Postgres to MySQL then leaves the business logic unchanged. A database is an abstraction on top of the file system. A file holds unstructured data and is read entirely or block by block. A database has an ID and types such as integer, long and string, and each type occupies a certain amount of space. A database is expected to be durable. A tsunami or a hurricane can still destroy the hardware, but the chance of losing data is much lower than in memory. An in-memory database is faster than disk, costs more, and loses its updates in a crash. Storage and Retrieval A database stores rows of structured data in tables, builds indexes on them, and reads them back through SQL queries. The hardware is magnetic tape or solid state disk. One layer above it are the algorithms: B+ trees, which create the indexes in relational databases, log-structured merge trees, pages, hash tables and pointers. A table is a structured store with columns, and each column has a data type. A profile table has an ID as an integer, the names and email as strings, and the date of birth as a date. An SQL statement is broken down this way: From: the table being read. Where: the rows of interest, such as users from India. Group by: clusters, such as by date of birth. Having: an aggregation, such as clusters of more than 100 users. Order: ascending or descending. Limit: the top 5 results. The query optimizer finds the most optimal way to execute the query. It uses heuristics, and it knows where the hash tables and indexes exist. What is a NoSQL database? A NoSQL database is any database that does not support SQL or relational tables. It is a catch-all term. NoSQL databases usually mean key value stores or document-oriented databases: a key, and a document or value for that key. It is a persistent variation of a hash map. Whether a database holds the latest copy of the data depends on the application. Certain types of data are okay with being lost, such as the number of views on a post. A creator who sees the views go down from 1,000 to 990 has not suffered tremendous damage. Usually a database is the single source of truth for any data-related operation. It is expected to have data that is as consistent as possible, and to be available, which means it is responsive to requests. If the database is down, the whole application is down. A database management system decides what data is persisted where, and manages the read replicas and any coordination. The management system is the manager, and the database nodes are the employees that store the data. Types of Databases: Graph, TimeSeries and Object Graph, time series and object-oriented databases each store data in the shape of the operations run on it. A graph database stores its data internally as nodes and edges, so that graph queries such as an A* search or a breadth-first search are efficient. Relational databases with a layer written on top are also used as graph databases. They are not optimized for graph operations, so they are usually not as good as Neo4j. A time series database stores values such as the number of sales per day. It is good at aggregation operations and it compresses the time values. With a long timestamp of 64 bits, each subsequent value is off by only one second, so the database saves on timestamp storage. It suits metric data, instrumentation data and monitoring. An object-oriented database stores objects instead of tuples. It is usually implemented using a relational database. It helps programmers write and read data quicker, and the application layer does little transformation when storing object-oriented data. What database should you choose? The database for a project is chosen by the application being written and by the trade-offs each database gives. Postgres has high consistency and high durability. It provides nothing off the shelf for availability: when a Postgres instance goes down, a read replica has to be ready to take its place. Cassandra has a cluster architecture. If one of the nodes goes down, the rest of the nodes take up its responsibility, so fault tolerance is inbuilt. It is not highly consistent unless it is configured to be. Neo4j is a graph database and is excellent for graph queries. It is a poor counter for the likes on a Facebook post. A database is an abstraction that manages data reads and writes while the engineer focuses on the business logic. Elasticsearch does not support SQL, and a third-party library converts SQL queries to Elasticsearch queries. When the growth of the application is unknown, a familiar database is the choice. When it is known, the choice is the database with the best trade-offs.
- Cassandra Internals
The internal architecture of Cassandra helps us understand some design patterns of NoSQL key-value databases. Sharding Quorum Redundancy Client-side routing with keys
Consistency in Distributed Systems
- Causal Consistency
Causal Consistency Causal consistency orders the operations on the same key and leaves the operations on other keys alone. The name comes from cause and effect. A customer with ID 1 cares only about key 1. The requests for it are a read, a write of 31 and another read, and the expected responses are 21 and then 31. Under linearizability the last read is blocked on every request before it, including the reads and writes of key 2, which wastes resources. The fix is to extract the requests for the same key and order them sequentially: read 1, write 1 to 31, read 1. Key 2 gets its own order: write 7, two reads, write 17. A global lock on the key does not give this order. Three operations fighting for the lock on key 2 let the write of 17 win, and the two reads return 17 instead of 7. Causal consistency needs ordering, not locks. It is more consistent than eventual consistency and more efficient than linearizable consistency. Data Consistency Levels Tradeoffs Each of the four consistency levels trades consistency against efficiency. Linearizable has the highest consistency and the lowest efficiency, because of head of line blocking: a request waits on a lot of requests that are irrelevant to it. It also keeps aggregations consistent. Eventual has the lowest consistency and the highest efficiency. Data is read quickly from the database, with no order between reads and writes. Causal has high consistency, because the reads and writes for a particular key are ordered. Its efficiency is rather high in most cases, because the operations are point updates and point reads. Quorum has configurable consistency and configurable efficiency. The drawback of a quorum is cost: it needs multiple nodes. An even number of replicas risks the split-brain problem, and one replica is a single point of failure, so the count is three or five. Different parts of one system can run at different levels. A server or a cache can run at eventual consistency while the database runs at the highest level.
- Data Consistency across Continents
Data Consistency across Continents Consistency means that multiple copies of the same data are the same. A cache on the Harvard server reduces latency for Oxford profiles. The Harvard server checks its cache, fetches a missing profile from the Oxford server, stores it and returns it. A cache miss still goes to Oxford. The practical fix is multiple copies of the data, one in the US and one in Europe. No single point of failure. If one server crashes, the other serves the data. Network issues are solved. A user who belongs to Europe is read from the copy in the US. Latency is low. An update to C is made locally and the response is sent back. The update then has to propagate to the other copy. Done manually, it suits infrequent updates: a bank notes the change in a ledger, and it reflects on the statement in a few days. A real time system sends the update over TCP, which gives reliable and ordered delivery, and Europe applies it. The open problem is a failed transmission. Leader-follower architectures A leader-follower architecture lets only one server, the leader, commit writes. The followers receive its updates and serve reads. The chain that leads to it: The US server sends an update to the Europe server, and the transmission fails. The fix is an acknowledgement. The acknowledgement fails too. The US server retries, every five seconds forever, or five times before it gives up. A server that commits locally cannot depend on its peer to commit, because the network is unreliable. A server that waits hands the same problem to the peer, which never knows whether its acknowledgement arrived. An acknowledgement of the acknowledgement is an infinite process. This is the two generals problem. So the US server becomes the leader, the only one that writes to the database. The Europe server is a follower: it gets regular updates from the leader and serves reads. If an update does not go through, a follower that answers gives a dirty read, and a follower that waits is not available. Pure consistency costs availability, and availability brings inconsistencies.
Caches Deep Dive
- Caching: Basics
Benefits of a cache: Saves network calls Avoids repeated computations Reduces DB load Drawbacks of a cache: Can be expensive Potential thrashing Cache Policies: LRU LFU
- Write Policies
Write Policies: Write Back Policy A write policy decides what happens to the cache and the database when a write request arrives. It is different from a replacement policy, which runs only when the cache has no memory left for a new entry. In a write back policy the cache is updated and the database is not. Key 1 holds 20. A write sets it to 30 in the cache, and the database still holds 20. Reads are consistent as long as the cache is alive. If the cache crashes it is rebuilt from the database, and key 1 is 20 again. Three things write the value back to the database: A timeout. The entry has a time to live of 50. A read at 51 finds it stale, removes it and persists it. An event. After five updates the value is written. A replacement. Key 3 arrives with 70, key 1 is removed from the cache and written to the database. The database is eventually consistent. Comments on a post and aggregated counts of likes fit this policy. Write Through Policy In a write through policy a write removes the key from the cache and updates the database. Key 1 holds 10 in the cache and in the database. A write sets key 1 to 30. The cache drops its entry for key 1, and the database changes 10 to 30. The database's response changes nothing in the cache. The next read of key 1 finds no entry in the cache. The cache pulls 1 and 30 from the database and returns it. The two are consistent again. One case is tricky. A read of key 1 arrives after the cache has dropped the entry and before the database has finished the write. The cache has no entry, so it queries the database. If the write holds a lock on that row, things are fine. If the isolation level is read uncommitted, no lock is taken and the read returns 10. Write through gives high consistency and high persistence. It is not the most efficient policy. It fits transaction data. Write Around Policy In a write around policy a write goes around the cache and updates only the database. Key 1 holds 30 in the cache and in the database. A write sets key 1 to 50. The request is sent directly to the database, which now holds 50. The cache still holds 30, which is stale. A queue can sit between the request and the database. A read of key 1 returns 30, and keeps returning 30 until the entry is kicked out of the cache. The policy has three properties: Persistence. Every write reaches the database. Write back can lose data. Eventual consistency. The entry is kicked out at 12 o'clock and repopulated at 3 o'clock with 50. A replacement and a load have to happen before the cache is consistent. Efficiency. There is no contention on the cache and no ordering of writes in it. The cache only serves reads. Write through goes through the cache to the database. Write back updates the cache immediately and the database after some time.
- Replacement Policies: LRU, LFU and Segmented LRU
Replacement Policies In this video, we learn to determine which key needs to be evicted. This is based on the replacement policy LRU Policy (Least Recently Used) In this policy, we evict the entry that has not been used for the longest. To implement this policy, we need to add another data point i.e., Last Used. To understand this policy, watch the video where you can understand it with examples. Time interval in which Write-Around Policy Replacement Policies LRU Policy (Least Recently Used) an entry was not used = current_timestamp - LastUsed for that entry. LFU Policy (Least Frequently Used) In this policy, we evict the entry that is used least frequently. Don't forget to watch the video for a better explanation using examples!!
- PDF SummaryPDF
System Design Tradeoffs
- Throughput vs. Latency
Introduction to design tradeoffs A design trade-off is one non-functional requirement met at the expense of another. Uploading pictures on Instagram is one functional requirement with several non-functional requirements: Recovery from a failed upload. If the phone loses charge or internet with half the picture uploaded, the rest is uploaded later. Safety, or persistence. A tsunami that takes down a data center in Japan does not lose a creator's work. Quality. The image is understandable when it reaches the receiver. These are business requirements, driven by what the customer expects. Safety is at loggerheads with cost. Persisting the image in 300 places keeps it safe from disaster, and the cost and the time taken to upload become very high. Quality is also at loggerheads with cost, because a high definition image stores more data. Viewing images brings in response time and the ability to cache, and smaller images cache easily. One copy or three copies of the main image are stored, and 50 copies of the popular images are cached around the world. Throughput vs. Latency Latency is the time required to get a response from a server, and throughput is how much of the processing power is spent on the application's own tasks. A server runs at most 20 instructions per second. A profile service spends 10 waiting on the database and two on garbage collection. The 8 that remain give a throughput of 40 percent. How often the background task runs sets the trade-off: Background tasks kept for the end. The application runs for 97 seconds and the background task for 3. Throughput is 97 percent, and a request arriving in those 3 seconds is stuck, so worst case latency is more than three seconds. Background tasks in small parts. The task runs 90 times and takes 9 seconds in total. Throughput falls to 91%, and worst case latency falls with it. Thrashing makes both worse. With very small time slices, context switching eats into the application time. A cache with two entries and requests for A, B and C in a cycle misses on every read. SQL vs. NoSQL databases SQL and NoSQL databases differ in consistency, architecture, scalability, sharding and transaction support. Consistency. NoSQL usually has more relaxed consistency. SQL usually has high consistency. Architecture. SQL replicates data through a primary replica architecture: writes fall on the primary, reads on either. NoSQL is usually a cluster, where any node responds or a hash routes the request to a node. Failover. NoSQL has leader election or a consensus algorithm, such as quorum. SQL has an assigned primary, and when it fails the replica becomes the primary. Sharding. NoSQL usually comes with inbuilt sharding: requests from 0 to 100 are split into five ranges on different nodes. SQL usually does not. Transactions. SQL has ACID support. NoSQL usually has none. NoSQL is designed for high scalability, with fast reads and writes. In SQL the reads are fast and the writes are slower, because they are bottlenecked on one node. MySQL and Postgres suit relational or transaction support. Amazon DynamoDB, MongoDB and Cassandra suit extremely high scale with denormalized key value pairs.
Design a Cab Aggregator App like Uber
- Uber: Pricing and ETA
Static Pricing of Rides Static pricing gives a rider a price for a trip from a source to a destination, computed by a rule engine from stored weights. The app sends the server the user ID, the source, the destination and metadata such as the time of day. A rider who waits for a price drops off, so the price is needed fast as well as accurate. A machine learning algorithm on the request takes time. A cache of prices from region to region is fast. A region that is too big averages high demand with low demand, so the price is inaccurate. One change in a rule makes hundreds of updates in the cache. A rule engine runs through the request's parameters and sets the price. The initial price is the distance into a weight of distance, plus the time taken into a weight of time. The weights come from historical prices, the cost of fuel and the cost of a driver's time. Rules raise or lower the price against thresholds, such as the demand at the source. Calculating Estimated Time of Arrival The estimated time of arrival is the time taken to get from A to B along the roads. Quad trees and blocks of squares fail here, because what matters is whether there is a road from A to B. The map is stored as a graph: nodes as points and edges as roads. Breadth-first search minimizes the number of edges, and one edge is 10 minutes while another is three hours. A star search works on cost. For each reachable node it adds the real cost from the source to an approximate cost to the destination, given by a heuristic function. A priority queue expands the node with the lowest estimated cost next. The points, connections and weights go in a graph database. The points stored are the interesting points, where a turn is possible, each with its adjacent points. An edge's weight is the historical average: the total time taken by all riders divided by the number of rides. The driver sends the location by simple polling every three seconds.
Interview Tips
- Dos and Don'ts
System design interviews can be tricky. Here are 5 mistakes that you should avoid during an interview. The mistakes mentioned here are what I have seen and done in my experience as a software engineer and interviewer. Do not have a premeditated introduction Estimate Capacity Requirements only if required Expand on the network protocol choices (if required, like we do with database choices) Know the internal architecture of systems Highlight design tradeoffs
Tinder System Design
- Tinder System Design
Requirements of Tinder A design can start from either end. Starting from the ER diagram models the data first, then the services, then the clients. This order is too constrained and too abstract, because the data is modelled before anyone asks what users need. The second approach goes from front to back: the features users need, then the services that fulfil them, then the data each service requires. The system is more flexible and easier to start. Four features are picked for Tinder, each with one question: Storing profiles. A profile holds images, five images per user. Recommending matches. The question is the number of active users. Noting matches. The number of matches is taken as a share of active users. The assumption is that a swipe matches 0.1% of the time. Direct messaging, once two people have matched. Too many questions about one feature means too much detail too early. Four features are enough for an interview of at most an hour, since the interviewer steers toward the details that matter. Image Storage: Files vs. Database BLOB An image is stored either as a file or as a BLOB, a binary large object in a database. A database gives four extra guarantees, and an image needs none of them: Mutability. An update to an image is the entire image, so it is stored as a separate, immutable file. Transaction guarantees. There is no atomic operation on an image. Indexes. They improve search, and the content of an image is ones and zeros. Access control. A secure file system gives the same mechanisms and is almost as tedious to set up as a secure database. A file is cheaper. It is faster, because large objects are stored separately, which a database does only through vertical partitioning. It is not pulled in by a select star. It is static, so a CDN is built over it for fast access. The database stores the reference: the image ID, the image URL and the profile ID. The file itself sits in a distributed file system. Profile Creation and Authentication Profile creation registers a user with the profile service, and authentication checks that each later request comes from the user it claims. The client on the mobile sends a username and password to the profile service, which stores them in the database. An update profile request then has to be authenticated: The monolithic way: the profile service authenticates the username and password itself. This way is insecure, so the client sends a token. A new service has no information about tokens and usernames, so it talks to the profile service on every request, and that code is duplicated in each service that comes up. A gateway fixes this. Clients talk only to the gateway. It asks the profile service whether the request is authenticated, redirects it to the correct service on a yes, fails it on a no, and forwards the response. Images go to a separate image service. It stores them in a distributed file system, and keeps the profile ID, the image ID and the URL of each image in a database. One to One chat messaging One to one chat sends a direct message from one client to another through the gateway, over a connection the server pushes on. After a match, the client tells the gateway: message to user ID 1 from user ID 2. HTTP is a client server protocol. The client talks and the server responds, so the receiver has to poll the server every five seconds for messages, which is extremely inefficient. The fix is a peer-to-peer protocol, where both machines are equal and the server pushes messages to the client. XMPP is one. XMPP takes a WebSocket connection. A custom protocol over TCP also works, because the connection is made and maintained. Each user listens on one of the connections on the gateway service. To decouple the system, a sessions service stores which user ID is on which connection. To deliver a message, the sessions service finds the connection the other user is using, and the message is sent to that socket. Matching right-swiped users A match is noted on the server by a matcher service, and the swipes are kept on the client. The client is an app and stores information. If it stored the matches and the app was uninstalled, they would be lost, so the server is the source of truth. A match is sent to the server. A matcher service keeps a table of user ID to user ID, with an index on the user ID. The records are duplicated: A matched with B, and B matched with A. A direct message then takes a longer path: The message goes to the matcher, which confirms that the two users are matched. The matcher sends it to the sessions service, which finds the connection to use. The message is sent on that connection. When the app is reinstalled, it pulls the matches from the matcher. The only information lost is who was swiped left or right, which lives on the phone. The loss is not critical: the same people are recommended again. Serving recommendations to users A recommendation is a set of users chosen by age, gender and location, and the core of it is finding which users are close. The profile service stores the age, the gender and the location. Indexes on all three do not work: a table is sorted in one way, so a query uses only one of those indexes, and the query optimizer picks which. A distributed NoSQL database such as Cassandra or Amazon Dynamo, which replicates the data and builds a table for each query. Sharding on a relational database, also called horizontal partitioning. Ranges in one column direct the data to a node: names from A to J go to database node 36, and K to P to node 79. A master-slave architecture removes the single point of failure. The data is sharded by location, in chunks of a city. All the users within a chunk are pulled out of one node, queried on the sorted age, and filtered by gender. A recommendation service stores the user IDs and their current locations, updated every hour.
- Architecture DiagramPDF
- Summary - PDFPDF
Hotstar: Live Video Streaming Design
- Hotstar: Live Video Streaming Design
Live Streaming Requirement Breakdown A live streaming service transports high definition video from a sports or cultural event to millions of users who are interested in the stream. Hotstar and ESPN are examples. The constraint is that the video reaches the users within one minute. The challenges are compute, bandwidth and performance. The requirements: Transform the original video. The 8K video is converted into other resolutions, such as 4K, 1080p, 720p and 360p, and into different codecs for different operating systems. It is a 2D matrix of resolutions to codecs. Heterogeneous delivery, to the various devices of users at scale. Caching, because performance is tied to the bandwidth used. A fault tolerance guarantee, because users are paying. The first two are specific to this system: the data is video, and the users are heterogeneous. Caching, fault tolerance and performance are engineering guarantees that are default for any engineer. The most critical requirements are the first two. Video Ingestion and Transformation Video ingestion takes the live video in as a stream, and transformation converts it into the resolutions and formats the clients need. A live stream cannot wait for the whole video to end, as Netflix does with an upload. It is ingested over RTMP, which is written over TCP: acknowledgements and ordering, so no data loss. TCP is slower than UDP, but poor quality at the source only gets worse on the way to the user. The original video is backed up in multiple stores. Then: The transformation service has a job scheduler, with tasks such as converting 8K footage into 720p video or 360p HLS. It publishes the tasks to a message queue, and worker nodes subscribe and pick them up. A worker persists its result in distributed file storage, because a full video in a message queue is a very bad idea. The worker publishes an event that it is done. The transformation service publishes tasks at its own pace and the workers pull at theirs. Transferring processed videos to end users Processed video travels from the transformation service to servers around the world, then to a content delivery network, whose edge servers send it to the users. Last mile. Users connect over HTTP. An iPhone uses HLS (HTTP live streaming) and other operating systems use DASH. Both have adaptive bitrate: if a user on 480p is able to buffer a lot, the browser sets the video quality higher. Own servers. A service such as Hotstar keeps servers in India, the US and the UK, because the SLA of a content delivery network may not match live streaming guarantees. Video reaches them over RTMP, with no data loss. Routing. The original server redirects a user to a box by location, and the box gives an endpoint to pull the video from. If the Indian servers go down, requests are redirected to the US server. The content delivery network takes care of caching the video. The servers cache the endpoint, with the live stream ID and user ID as the key.
- FAQsPDF
- Capacity PlanningPDF
- Architecture DiagramPDF
Design an Emailing service like Gmail
- Scope and Requirement setting
We identify the key features of the system by noting down its: 1) Services 2) APIs 3) Database schemas
- Requirements ListPDF
- Gmail System Design
Chapter #1: Service Registration and Proxies A gateway is the known place where external requests connect to the system, and it routes each request to the right internal service. The domain name servers map gmail.com to the IP address of the gateway. Inside, the method auth in gmail.com/auth maps to the auth service. The gateway also blacklists IP addresses that exceed a rate limit, and translates HTTP requests into a more efficient protocol over TCP. The gateway now has a lot of responsibility, so the mapping moves to a service manager. Each service registers its method names and the IP addresses of its boxes, and a heartbeat tells the service manager which boxes are alive. The gateway caches the mapping. The auth service stores the user ID, the encrypted password and the phone number, with verified set to false. A code with a timestamp goes in a separate table, and the SMS service fills a template with it. The user sends the code to gmail.com/verify. The auth service checks the code and its expiry and sets verified to true. Chapter #2: Authentication & Global Caching A token is a secret that the auth service gives a user at login and that the user sends with every subsequent request. Every request to an internal service is authenticated. An unauthenticated request for the last day's emails could be sent by anyone who knows the user ID. The username and password in a browser cookie, appended to every request. The password is stored as plain text. A token in its place. Invalidating the token logs the user out. The gateway now asks the auth service on every request. A cache of tokens at the gateway, updated by the auth service through a message queue. The gateway is bloated with somebody else's data, and an update fans out to every gateway box: three boxes, or 500. A global cache, a map of key to value such as auth_userID to the secret. Services send updates to it, and the gateway makes a single API call to route and authenticate a request. The global cache costs an API call, and the service stays decoupled. Gmail Chapter #3: API contracts & Versioning An API contract is the definition a service publishes of the objects its methods accept. Creating a profile is a POST request that carries JSON. The gateway converts it into a programming object, which the service registered for that method name defines. Each fix creates the next problem: A contract. The service owns it and the gateway reads it to construct objects. Rules specific to the service stay out of the contract. Internal services need the contract too, and new services keep arriving. It is stored where they register. Pushing a contract change needs a restart of every box. Services pull the contract instead. Contracts live in a contract registry. A framework like Thrift keeps them language independent. A breaking change, an integer becoming a string, fails the parser. Contracts are versioned, and the sender chooses the version. The profile image is uploaded to the drive service first and the request carries its URL. The user preference store maps a user ID to a layout and to the email preferences, both as JSON. Chapter #4: Sending, Tagging & Searching Emails Sending an email stores it in the email store and publishes an event to which the spam detector, the preference store and the search engine subscribe. A send email request carries a JSON body to the email store. Its schema is an ID, to, from, subject and created timestamp. The content, with the text and the attachments, is kept separately as JSON. Virus checker. It checks the URLs and uploads, and belongs to the drive service. Spam detector. It reads the content and subject, and tags the email. 500 emails from the same sender with similar timestamps are spam. It runs as a cron job every hour, or as a stream service pulling email events from a message queue. Preference store. It keeps a table of email ID to tags, which makes a search by tag fast. Search engine. A join of the three tables on every search is slow, so Elasticsearch subscribes to the email event. The subscribers are eventually consistent: a tag or spam mark takes a few seconds. Gmail Chapter #5: Contacts & Groups The contacts manager records who has emailed whom, and maps a group address to its members. The email store publishes each email to a message queue such as Kafka. The spam detector, the preference store and the search engine subscribe, each at its own position. Each addition creates the next problem: Contacts. Sending an email makes the two users contacts, stored as a mapping of user ID from to user ID to. An email marked as spam creates no contact. A second queue. It carries only emails whose tags have been set. The contacts manager and the search engine pull from it. Groups. A group ID maps to user IDs, one row for each member of group 123. External emails. Mail for another provider goes out through an SMTP server, and mail from outside is forwarded to the email store. The final architecture is a gateway, an authentication service, a service registry, a preference store, the email store in three components, and these consumers.
- Architecture Diagram 1PDF
- Architecture Diagram 2PDF
- Architecture Diagram 3PDF
- Architecture Diagram 4PDF
- Architecture Diagram 5PDF
- Capacity EstimationsPDF
- FAQsPDF
- API ContractsPDF
- Summary - PDFPDF
Basics
- Horizontal vs Vertical Scaling
Systems design a procedure by which we define the architecture of a system to satisfy given requirements. It is a technique by which the required amounts of scalability, reliability, performance and consistency are satisfied in real world systems. We discuss how to start with system design and why it is required. The first concept in designing a system is scalability. We discuss the two main approaches to solve this problem: Horizontal scaling and vertical scaling. Horizontal scaling is adding more machines to deal with increasing requirements. These machines handle requests in parallel to improve user experience. Vertical scaling is replacing the current machines with more advanced machines to improve throughput and hence response time. The techniques are used in conjunction in real world systems.
- Monoliths vs Microservices
Microservices are a hot topic in system design interviews. It is important to know why we use them instead of monolithic systems. The short answer is: Scalability. The detailed one would be: Advantages: 1) The microservice architecture is easier to reason about/design for a complicated system. 2) They allow new members to train for shorter periods and have less context before touching a system. 3) Deployments are fluid and continuous for each service. 4) They allow decoupling service logic on the basis of business responsibility 5) They are more available as a single service having a bug does not bring down the entire system. This is called a single point of failure. 6) Individual services can be written in different languages. 7) The developer teams can talk to each other through API sheets instead of working on the same repository, which requires conflict resolution. 8) New services can be tested easily and individually. The testing structure is close to unit testing compared to a monolith. Microservices are at a disadvantage to Monoliths in some cases. Monoliths are favorable when: 1) The technical/developer team is very small 2) The service is simple to think of as a whole. 3) The service requires very high efficiency, where network calls are avoided as much as possible. 4) All developers must have context of all services.
- Load Balancing
Load balancing is distributing work evenly onto a set of resources. In this video, we explain the main reason for load balancing, along with some common algorithms: Round robin Geo-distributed Least Connection
- Single Point of Failure
A single point of failure(SPOF) in computing is a critical point in the system whose failure can take down the entire system. A lot of resources and time is spent on removing single points of failure in an architecture/design. Single points of failure often pop up when setting up coordinators and proxies. These services help distribute load and discover services as they come and leave the system. Because of the critical centralized tasks of these services, they are more prone to being SPOFs. One way to mitigate the problem is to use multiple instances of every component in the service. The graph of dependencies then becomes more flexible, allowing the system to resiliently switch to another service instead of failing requests. Another approach is to have backups that allow a quick switch over on failure. The backups are useful in components dealing with data, like databases. Allocating more resources, distributing the system and replication are some ways of mitigating the problem of SPOF. Hence designs include horizontal scaling capabilities and partitioning. It is important to note that the CAP theorem does not allow removing SPOFs if perfect consistency is required.
- Content Delivery Networks
Content Delivery Networks are a bunch of servers spread across the globe to serve information. These networks are available on rent to deliver static content quickly to nearby users. Some examples of CDNs are Amazon CloudFront and the Akamai CDN. They are (relatively) cheap to rent and have high availability. They also provide pluggable algorithms to invalidate and fetch data. We discuss why content delivery networks are useful, and how they serve data with examples.
System Design Advanced
How do I use this course?
- What do we offer?
Have you ever been asked in an interview how a system like Google Docs or Kafka works on the inside? This course is the next step after System Design for Interviews, for engineers who know the basics and want to understand how large systems are built in production. The course has three parts. The first part covers concepts, like networks, databases for heavy writes and for locations, transaction isolation, replication and migrations, consensus with Paxos, security and observability. And the first four videos, on networks, are free. The second part uses these concepts to design systems, like Google Docs, Google Maps, a chess website, WhatsApp calling, a recommendation engine, Netflix movie onboarding and an audio search engine like Shazam. Most designs come with quizzes and an exercise, where you complete the design yourself. The third part reads the research papers behind production systems, like Memcached and TAO at Facebook, DynamoDB, Kafka, Spark, Dremel, Zanzibar, Borg, Dapper, Gorilla and Monarch, and vector databases. Most papers open with my video on the paper, followed by short lessons cut from my class on it. At the end, there are book chapters to read, on payments, ticket booking, batch processing and more. I hope you enjoy the course. Cheers.
Networks Deep Dive
- Internal routing: MAC addresses and NATFree
Internal routing: MAC addresses and NAT How does an internal router know where to send an external response to? Do you really wanna find out? Dig into the video right now as in this video we are going to learn: Content Delivery Network(CDN) Problems we face if we do not use CDN Decoding the responses from CDNs
- Head of line blockingFree
Head-of-line blocking in HTTP Head-Of-Line blocking occurs when the message/data packet at the head of the queue cannot move forward due to congestion even if other messages/packets behind this could. HTTP 2.0 solves this problem using Multiplexing. So what is multiplexing? Why HTTP 3.0 uses UDP instead of TCP? The video above answers all your questions!!
- Video transmission: WebRTC and HTTP-DASHFree
Video transmission: WebRTC and HTTP-DASH What do servers do while handling video data? Video files are large and cannot be sent in a single response. They have to be broken into packets. Why HTTP is not good for video transmission? HTTP is stateless. The client has to specify which chunk it wants because the server does not know about the previous requests. Do you want to learn more that includes the working of Conference Video Protocol? Dig into the video right now!
Databases
- Write Heavy DB Design
Write Heavy DB Design A write heavy database is designed so that a write costs as little as possible. A traditional database keeps its data in a B+ tree, where insertion and search are both order log n. Every SQL command is one I/O call and gets its own acknowledgement. Two ideas make writes cheaper: Condense the data queries into a single query. The server gathers them into one block and sends it in one shot: one I/O call, one acknowledgement. The server gives up some memory to hold the block. Write to a log. A log follows the linked list: a write appends at the end, in constant time. The log has fast writes and slow reads, because a read searches it sequentially, in order n. A sorted array is searched in order log n. A linked list for the writes with a sorted array for the reads gives great write speeds and great read speeds. This is where the log structured merge tree comes from. Write Heavy DB Design - Merging Sorted String Tables A log is fast to write and slow to read, so the database persists the log's records in sorted order and reads them with a binary search. The server appends each new record to a log in memory. At a threshold the records are sent to the database in one shot and stored sorted. The database can treat the next batch in three ways: Merge it into the one sorted file. Six records and six records make a sorted file of 12. After 10,000 records, six more force 10,000 and six records to be sorted, at n log n. Keep every batch as its own sorted chunk. Writes stay fast. A read does a binary search on each chunk, and n insertions leave n divided by six chunks, so reads are order n. A hybrid. Chunks are merged as long as the sort time is not too high. A merge moves a pointer along each of two sorted arrays and keeps taking the smaller element. Write Heavy DB Design - Query optimisations A log structured merge tree speeds up reads by merging sorted chunks in the background into larger sorted arrays that can be binary searched. Three chunks of size 6 hold 18 records. A search in one chunk takes approximately 3 operations, so a search in all three takes around 9. Merging two chunks into a sorted array of size 12 brings that to 7. The merging is similar to merge sort: Two blocks of size 6 become a block of size 12. Two blocks of size 12 become a block of size 24, searched in approximately 5 operations instead of 12. The blocks are of varying size, and a read is spread across them. A Bloom filter on top of each chunk tells whether a record exists in it. It has false positives and no false negatives. A merged array gets a larger Bloom filter, which reduces the chance of a false positive. A sorted set of records is called a sorted string table. Merging sorted string tables into a single array is called compaction. Quorom Quorum is a way in which the nodes that hold a piece of data vote for a value, and the value a majority accepts is taken as the truth. The replication factor is three: nodes 5, 1 and 2 hold the profile. Node 5 crashes before a read. With a quorum of 2: Node 1 does not have the data and node 2 has it. The data with the latest timestamp is returned, and the user sees the profile. Both have it. The correct data is returned. Neither has the write replicated yet. Both agree that there is no profile, and the user gets a wrong error. The third case is rare, and it is the risk taken with a NoSQL database, which moves forward with availability instead of consistency. With a quorum of 3, the query fails, because node 5 does not return a value. Most of the time, when the nodes do not agree on a value, the database query fails and the user is told the system is unavailable.
- Location Based Databases
Location Representation A location is represented as two binary numbers, one for each axis, where every extra bit narrows the region the point lies in. Two PIN codes that seemed close were separated by a train line with the crossing 2 kilometers away, so a PIN code does not measure distance. A location-based database has two requirements: Measuring the distance between any two points, with uniform assignment and scalable granularity. Proximity: all the users within 10 kilometers of a point. Latitude and longitude satisfy the first, with the Euclidean distance. They fail proximity, because checking every point in the database is too expensive. A number with a fixed number of bits represents a range, and each bit is a step of a binary search. Of 64 bits, 32 go to the X axis and 32 to the Y axis. One bit from X and one from Y pick one of four quadrants. Two points whose first 13 bits are the same are close. Two points on either side of a quadrant boundary are close, and their prefixes mismatch. Data Structure - Quad Tree A quad tree is like a binary search tree that works on two dimensions, so each node has four branches. The root represents the whole world. Each child contains one-fourth of the region, a sub-region, and the tree is recursive. 20 points in a node are distributed among its children: 5 in the top right, 3 in the top left, 1 in the bottom left and 11 in the bottom right. The depth is as far as the application requires. If cities are enough, all the users in Mumbai sit in one node. If a square of side one kilometer is enough, that square is the leaf node. The more sensible way is to split only when required: a node is split into smaller pieces when the number of users in it exceeds a threshold, such as 10. The worst case is skew. Mumbai has a huge population and a city in Iceland has very few users, so the tree goes very deep in one branch while the other branches are light. Range Queries and Hilbert Curve A Hilbert curve is a line squeezed into a 2D plane so that every point on the plane has a mapping on the line. A range query on a 2D plane has no efficient algorithm. On a 1D line, segment trees and interval trees answer it in log n. So the plane is converted into a line that preserves the proximity information. The line is broken into four segments, 0, 1, 2 and 3, and each goes to one quadrant. Of the possible arrangements, the U shaped Hilbert curve loses the least proximity information. Each quadrant is recursively broken into four more, with the U shape rotated so that the line stays continuous. The recursion goes to any depth, so the curve fills the entire space. Proximity is a plus or minus threshold on the line: 6 around a customer at position 29. Setting the threshold is a problem. Position 18 is at a difference of 11 from 29 and is extremely close, and 40 is also 11 away and is very far.
- Database Replication
Primary Replica Architectures A primary replica architecture sends every write to one database, the primary, and copies each operation to a replica that takes over when the primary goes down. A server with a single database has a single point of failure. A restart leaves the clients without their data, so a replica, also known as a backup, is kept. Writes go to the primary and are copied to the replica. Reads go to both. In read-intensive applications the writes are infrequent, 1% or 5% of the SQL queries. When the primary goes down the replica is promoted to primary, and a new replica is added as a copy of it. Benefits: Fault tolerance. Improved read speeds, with reads distributed among two or more nodes. Simplicity. A cloud solution provider does it. Drawbacks: Consistency. An operation that adds 10 to a balance is in flight: it is in the primary and not yet in the replica, and concurrent reads see different views. Slower writes. Each write also goes to the replica. Latency is traded for fault tolerance. WAL and Change Data Capture A write-ahead log is the log of operations a primary applies, copied to a replica. Change data capture sends each change as an event that a subscriber transforms. Both databases start in the same state. A new write, x = x + 10, is applied in the primary and sent over the wire to the replica, which applies the operations one by one. The replica acknowledges operation 4 and asks for number 5. Because it is a log, the operations are executed sequentially and rolled back, as in transactions. Only operations are sent, which keeps the transfer small. Two drawbacks: A replica that does not catch up is a consistency issue. Context. An entry with the timestamp Friday 10 a.m. arrives three minutes later, and the replica has two timestamps to choose from. Change data capture handles operations with context. It works like a message queue: an event is published, and the subscriber decides what to do with it. It suits different types of databases, such as write-optimized Cassandra copied into an RDS for relational reads. Write Amplification and Split Brain Split brain is two primaries that both believe they are correct and hold different copies of the data. Write amplification is one write turning into a write on every replica. With two primaries, a network partition stops a write on one from being reflected in the other. One server sends x plus 10 to its primary, another sends x minus 10 to the other, and x has two values. Last writer wins overwrites somebody else's operation, so usually an admin reconciles manually. An odd number of primary nodes prevents it: when the cluster splits, the majority settles on one value. With many read replicas, x = x + 10 is copied into every copy. Waiting for all of them makes fault tolerance worse and latency very high. Not waiting still means four operations in place of one. That loads the primary's bandwidth and leads to inconsistencies. The fix is for a majority of nodes to agree on a value, or a peer-to-peer ring of three or five nodes that reaches consensus through Paxos or Raft.
- Database Migrations
Database Migrations A database migration takes data from a source to a destination. The obvious way is to stop the source, take a dump, upload it into the destination and start the new database. The data is perfectly consistent and the system is down while the dump moves. A table with billions of records that is read and written every second is copied while it runs: A copy. The Users table is copied to a New users table. This takes about an hour, and thousands of records arrive in that hour. A second copy, of every operation in the database log with a timestamp greater than X, the last record copied. It takes a few seconds, and fewer records arrive. A trigger. An insert and update trigger on the old table sends each new write to the new table. The missing records. The operations between two timestamps, Y and Z, are copied. A trigger that updates a record the new table does not have yet does an upsert, or fails. The clients are never stopped. Migrating the Database A view is an abstract table: an SQL query over one or more real tables. It lets the servers move to a new table without a code change. The brute force way points the servers at the new table one at a time. S3 adds a record to the new table while S1 still reads the old one. S1 runs a count, gets 2 where the answer is 3, and makes a wrong decision. The migration with a view: Create a view on the new table that behaves like the old table. The new table has columns A, B and C, the old one B and C, so the view selects B and C. Rename the view to the old table's name and the old table to obsolete, in a single command. Every server now goes through the view. Restart the servers with code that points to the new table. Drop the view. Validate the data, by hand or automatically. The downtime is in seconds. The brute force migration took a few minutes. Migration Across Regions A migration from one cloud provider to another, Azure to AWS, cannot use a database trigger or a view, because neither works across providers. A DB proxy replaces both. The copy still works. An SQL dump and a second query move most of the data, and the records missed between two timestamps are moved afterwards. The proxy: Every server sends its SQL commands to the DB proxy. A read goes to Azure. A write goes to both Azure and AWS, as the trigger did. The missing records are copied across. The proxy is pointed at the new tables. It behaves like the view, so no rename is needed. The servers are restarted to point at AWS directly, and the proxy can be dropped. A proxy that stays is a single point of failure. Each server needs two restarts: one to point at the proxy and one to point at the new databases. Where some downtime is acceptable, a copy followed by a restart of every server is simpler.
- Database Migration SummaryPDF
Consistency in Distributed Systems
- Transaction Isolation Levels
Transaction Isolation Levels: Read Uncommitted A transaction isolation level is the read guarantee a database gives when two transactions run in parallel. Data consistency covers a generic stream of operations. An isolation level is limited to the data inside transactions. A transaction starts with a begin statement and ends with a commit. The commit makes its operations stick, which makes the transaction durable. A transaction is also atomic: either all of its operations execute or none do, and they are rolled back. Read uncommitted is the loosest guarantee. The database keeps a single copy of the data, and every read takes the latest value. It is fast, because there is no read or write contention. The drawback shows up when a transaction fails: T1 writes 50 to key 2, which held 17. T2 reads key 2 and gets 50. T1 fails and is rolled back. A write reversal sets key 2 to 17. No later read of the database returns 50. T2 has seen a value that never happened. Transaction Isolation Levels: Read Committed Read committed lets a transaction read only the committed pieces of data in the database. The database does not keep a single copy of the data. Each transaction keeps its own copy of what it writes: T1 writes 50 to key 2. The value goes into T1's copy. The original table still holds 12 and 17. T2 writes 50 to key 1 in its own copy. T2 reads key 2 from the table and gets 17. T1 reads key 1 before T2 commits and gets 12. If T2 commits first, its copy goes through to the table and T1 reads 50. This is a higher level of isolation than read uncommitted. Higher isolation is usually slightly slower and more expensive. A movie hall with a capacity of 50 stops booking at 50 committed transactions. Counting uncommitted ones could leave 48 people and two vacant seats after a rollback. A count of likes on a post can return 55 and then 54. It trades isolation for efficiency. Transaction Isolation Levels: Repeatable Read Repeatable read guarantees that repeated reads of the same key inside one transaction return the same value. Read committed does not give that guarantee: T2 reads key 2 and gets 17. T1 writes 50 to key 2 and commits. T2 reads key 2 again and gets 50, the latest committed value. Two consecutive reads of one key gave different values. A transaction that makes decisions on a key it reads and then writes can be messed up by this. Under repeatable read the transaction behaves as if a snapshot of the entire database is taken when it begins. It works on that copy and changes the database on commit. The 17 in the snapshot is a committed value, though not the latest one. The implementation is called snapshot isolation. When two concurrent transactions write the same key, one with 25 and one with 50, the contention is resolved by rejecting the value that comes second, or by rolling back a transaction. This is optimistic concurrency control: the transaction is optimistic that the value will not change. Transaction Isolation Levels: Serializable Serializable is the highest transaction isolation level. Either all the operations run in a serial manner, or every operation is ensured not to meddle with another transaction's operation. A read of the sum of the values between 1 and 2 puts a lock on all the values between 1 and 2. It is inefficient. It is used when phantoms are not acceptable. A phantom appears like this: T1 reads the sum of the two values and gets 29. T2 writes 50 and then 25 for key 1 in its local copy, and commits. The value in the table changes from 12 to 25. T1 reads the sum again. It sees 25 plus 17, which is 42. Two reads of the same aggregation query in one transaction gave different results. An insert of a new key at the same time has the same effect: the key is a phantom to the query. It is as if an additional 13 seats were booked out of nowhere. Executing the transactions sequentially makes sure there are no phantoms. Transaction Level Implementations Each isolation level is implemented by a different way of storing a value. Read uncommitted needs a single entry in the database, which is overridden whenever there is an update. Read committed keeps a local copy of the changed values. The committed value stays in the database, and the newer value stays in the local copy till the commit goes through. There is one master copy and a copy of changed values for each transaction. Repeatable read keeps a version of the values a transaction reads and does not change. Every key stores all the values it has had across commits. A transaction keeps seeing the version from when it began, and a new transaction is given the next version. Serializable needs causal ordering. Transactions that have an entry in common are put in order in a queue, and each waits for the ones before it. A read with no relation to the others runs in a separate queue. Serializable is slow, and the data is very consistent. Transaction Isolation Levels: Conclusion A database offers four transaction isolation levels: read uncommitted, read committed, repeatable read and serializable. Down this order the isolation level increases, and as it increases the efficiency decreases. Serializable gives the highest level of isolation for the lowest level of efficiency. Read uncommitted is the highest level of efficiency. Efficiency goes up from 4 to 3 to 2 to 1. The choice depends on the application. Some applications go for serializable. Most applications run on repeatable read. Isolation levels are very similar to the consistency levels, but they are specific to transactions: how transactions behave, and how the data inside them behaves, when it is worked on simultaneously.
- Distributed Consensus with Paxos
The Problem of Distributed Consensus Paxos is an algorithm: a series of repeatable steps by which a distributed system reaches consensus. Consensus here is a majority. More than half the nodes agree on a particular value. Distributed means the components can fail individually and the messages between them can be dropped. Apache Zookeeper uses Paxos for distributed locking. So does Google Chubby. The problem shows up with five servers, S1 to S5, writing to three databases. S2 receives "add 10 to X" and tells all three databases to persist it. The log position is zero. Two other servers receive "subtract 10 from Y" and "add 10 to Y". These requests can arrive in any order. One database logs the subtraction first. Another logs the addition first. Y starts at 5. Where the subtraction comes first it fails for insufficient balance, and Y ends at 15. Where the addition comes first, Y goes to 15 and then to 5. The two databases hold inconsistent data. Two-phase commit and quorum are two answers. Paxos has advantages over both. Basic Algorithm Paxos writes to a log in two phases: first get the log line and lock it, then write to it. Three servers, S1, S2 and S3, broadcast every write to three databases, D1 to D3. A write is durable when at least two accept it. A plain broadcast can be overwritten by a concurrent request. The position of a write is as important as its data. So a server first asks for the log line. The databases answer log line zero, and the server writes at zero. This is the propose. S2 and S3 can both be told zero before either writes. S3 then overwrites S2: a stale read. So the database records the owner of the log line. When S3 asks after S2, the line is given to S3, because S2 might be dead. A write from S2 is now rejected. S2 asks again, becomes the owner, and its write executes. A server has to own the log line and execute the write consecutively for there to be consensus. Improving the algorithm A lock request that carries a timestamp instead of the name of its server can be compared with any other request. In the basic algorithm a request to acquire the lock is tied to the identity of the server that sends it. Another server cannot agree on the previous value, and errors across generations of elections are hard to debug. S2 sends a timestamp, T2, instead of its server ID. The latest operation is picked up. The databases store the timestamp beside the log line. A server sends the same timestamp to D1, D2 and D3. Timestamps are unique across the system. S1 takes T1 and T4, S2 takes T2 and T5, S3 takes T3 and T6: each server takes the numbers with one remainder when divided by 3. Two timestamps can now be compared, and the more recent request is known. Writing is isolated from acquiring the lock: another server can write without having made the initial claim. A server that asks again with a new timestamp runs a fresh election. Termination Conditions Paxos is a two-phase protocol: a server locks a log line with a timestamp, then writes to it, and a majority of the databases has to agree. Servers do not talk to each other, and databases do not talk to each other. A server reaches consensus by observing the values in the databases. S2 sends a log line request with its timestamp. The database answers with the log line and logs the row with that timestamp. S3 sends a request with a higher timestamp. The database overrides the row only because the timestamp is greater. S3 writes with its timestamp. It matches, and the write is accepted. S2 writes with its lower timestamp. The database rejects it. An accept without a prepare fails too. For the next write the database tells the server which log line comes next. If the databases answer with different log lines, there is no majority value and the server does nothing. The algorithm terminates when a majority of databases agree on the accept: the server alone knowing this is sufficient. Practical Considerations Paxos in the real world is optimized further: servers retry with jitter, and a leader is elected so that a write is no longer a log line request. Timing. S1 and S2 retrying a log line request after the same interval hit the server together. With jitter S1 sends every three seconds, S2 every one second and S3 every five seconds, so one of them wins. Speed. Running the algorithm for every read or write takes a lot of bandwidth. Instead of a log line, the servers select a leader. The one that gets a majority wins, and all write operations are directed to it. This is multi-Paxos. Catching up. A database far behind the others has to catch up. The Paxos algorithm does not define how. Google Chubby and Apache Zookeeper use Paxos for distributed locking. The lock is a small file in a file system: the owner that the majority of the servers accept has the permission to write to a node. The testing of the algorithm costs more than its implementation.
Security and Observability
- Security in Distributed Systems
Security aspects in distributed systems Security in a distributed system has several parts. Three of them need no design work from an engineer. Verification. It is the mechanism that tells whether a request comes from a human being. Models such as GPT-4 recognize characters and images, so captchas are broken regularly. SSL and TLS. They verify the web server that serves the page. HTTPS in the browser says the page is safe. The one choice an engineer makes here is the version, TLS 1.2 or 1.3, and it is made for performance. Encryption algorithms. ECC, RSA and Diffie-Hellman are pure math. They are open source and well used, and knowing their internals does not help an engineer design or build systems. Digital rights management is a fourth. It decides that a video for customers in India is not viewed in the US, and that only paid customers see it. Counting IP addresses and tracking local copies belong to it, and FairPlay is the system to read for that. Access Control Lists and Rule Engines Authorization decides whether an authenticated user or piece of code has the permission to do the action it asks for. It is done in three ways. Access control lists. An object, such as a file or a user, has a list of the actions allowed on it or by it. The lists of every object, grouped together, form the access control matrix of the system. Object based rules cover a single user or resource. Role based and group based rules cover many. The object based rule is more specific and takes precedence: all admins are allowed to delete files, except Gaurav. Rule engines. An ACL is a poor fit for a global rule. When a subscription ends, nobody goes to every resource to remove it. The rule bubbles up into a rule engine, a bunch of if statements. It suits a rule over multiple objects: 30 days for Indians, 15 days for Americans. Secret keys. A server tells the database a secret key, like a username and password. It is an additional layer of security. Attack Vectors - Hackers, Developers and Code A system is attacked by three kinds of attackers, some voluntary and some involuntary. Hackers. They flood the system with a huge number of requests, a DDoS attack. Rate limiting, a web application firewall and verifying that the user is not a bot stop the flood. They also look for a vulnerability: a response that gives away extra information. Careful API design takes care of that. Employees. Willingly or unwillingly, an employee could take down a system or make everyone's photos public. Access control lists stop that: the role does not give the permission. The scope of attack is reduced as well. A server opens the least number of entry points, and a database speaks only to the servers that need it. An employee working from home gets a VPN, a tunnel, because a request on a public network can be read. Malicious code. There is no way to stop it from executing, because code is the thing that makes changes on the database. Access to resources is restricted, and peer reviews and backups help. How videos are protected inside CDNs A CDN holds the video, and the CDN does not know whether a user is authorized to view it. There are three ways to protect the video. Token based auth on the server. The CDN takes each request to the server, and the server says yes or no. The auth is strong and the CDN needs no mechanism of its own. It is slow, because every request reaches the server, and the token is exposed to the CDN. Domain based auth. The CDN serves the video only when the HTTP headers show the request came from an allowed domain, such as interviewready.io. It is simple and fast. The domain is easy to spoof, and there is no user to user restriction. Server side auth. The user talks to the server directly and gets back a token for the CDN, signed by the server's private key. The CDN checks it with the public key. Tokens are timed, with a refresh interval of 60 seconds or one hour. Usually the choice is a mix of three and two.
- Token Based Auth, SSO and OAuth
Token Based Auth A token is a piece of text that states what a user can do, signed by the server with its private key. The user sends the username and password to the server, which checks them against its database. The server sends back a token: signed text showing all the permissions, such as Gaurav can create and delete documents. The user sends the token along with each request. The server decrypts it with its public key, which proves that the text came from the server, and does not take the password again. The private key is a number never shared with anyone, and the public key is a number everyone knows. The signed text is gibberish, and guessing the private key is computationally too difficult. A token does not protect against replay attacks: a person who steals it acts in the user's name. Logging out invalidates the token. The server stores the time of the last logout, so a token from 9 a.m. is no longer valid after a logout at 10:30 a.m. SSO and OAuth Single sign-on (SSO) moves authentication to an external service, and OAuth gets authorization on an external system. SSO comes from the SAML protocol. Gaurav has an account on Uber, so Uber checks his credentials and sends InterviewReady a token. On every request InterviewReady decrypts the token with Uber's public key and reads the permissions. Token generation has moved to an external system. After a layoff, Uber answers no for that user and the access ends. The benefit is for companies that want total control of their users. OAuth is the opposite of SSO: InterviewReady asks Google for permission to add, delete and modify events in Gaurav's calendar. Google asks the user on its sign-in screen. On a yes, Google gives InterviewReady a token to use on each change. When the user revokes access, Google invalidates the token and the requests fail. OAuth is an authorization system, but nearly everyone uses it for authentication. InterviewReady asks Google for the name and profile photo of a person, and treats the permission as authentication.
- Observability in Distributed Systems
Introduction to Observability Observability means an engineer or an operations person can look at a system and tell whether it is functioning as expected or something is wrong with it. Several topics come under it: logging, monitoring, anomaly detection and alerts, root cause analysis and incident reporting. Anomaly detection and alerts are close to each other. A system that is monitored effectively earns more trust: Errors are found quicker. Business problems are notified to the right people quicker. Some errors are resolved automatically. A robust and fault tolerant system needs excellent observability. The chapter covers each topic in detail, so that an engineer can name the parts that are missing in an organization and the parts that can be improved. Logging - Best Practices Logging is the simplest form of getting data from a system: a log line is written to a file whenever a request comes in or the system does something. A log line is like a println statement in Java or cout in C++. A typical line holds: The timestamp of the event. The level: I for information, W for warning, E for error. A system-breaking error at level one may create an incident report. The file and line that wrote it, such as content.go 264. The log line itself, such as user content progress created, with the ID of the content. Personal user details are a privacy decision. In financial systems, where engineers see transactions, the identity is hidden: only a user ID is printed and the email is protected, or the user ID is not printed at all. Passwords are blurred out. For debugging, the request ID is printed in every log line, and a grep for it returns the series of log lines related to that request. Monitoring Metrics Monitoring takes metrics, meaning numbers, from a system and tracks them across time. The numbers can be about the machines: the amount of memory used, the number of I/O operations. They can be about the business: the number of sales, the number of visitors on a page. Tracked across time, each number becomes a graph, a time series, that a human being can watch. An operations team looks at the numbers daily or hourly. Monitoring is usually manual, and it can be automated. The example is AWS CloudWatch tracking an elastic load balancer. If the number of requests spikes up, more load balancers are added. If it drops, a load balancer is removed to save cost. The decision is made by a person reading the dashboard. A data store powers the dashboard. It can be a time series store or plain Postgres. A small organization usually uses the data store it already has. A cloud provider such as AWS sells this ready built, with alerts and monitoring. Anomaly Detection: Holt-Winters Algorithm Anomaly detection finds a metric that has left its normal range, automatically, so that the response to a problem is quick. A business that makes 3,000 sales a day and drops to 200 wants to know the same day. The example is video retention: the percentage of users still watching at each second of a video. It declines smoothly, with a few spikes. Confidence intervals. Each point carries a range the next point is expected to fall in, and the range narrows as more of the graph is seen. A point outside it is an anomaly. This raises false alarms on known events such as a Black Friday sale. Differentiation. The rate of drop off is almost constant, so its derivative, the acceleration, is constant, and the next derivative, the jerk, is near zero. A large jerk is flagged. The Holt-Winters algorithm detects spikes even in seasonal metrics. Seasonal changes give small jerks and are ignored. A big spike is caught. Root Cause Analysis Root cause analysis finds what went wrong in a system when there was an anomaly or an incident: from the symptom, the cause. There are three ways to do it. Manual. A person looks into the log lines and the metrics and builds an incident report: when the problem occurred, what the root cause was, and the technique used to find it. One technique is the five whys. Memory consumption was high. Why? Many PDF files were generated together. Why? A cron job generated them hourly. Each answer goes a level deeper. With several contributing factors the line of whys becomes a tree. Automated. It is hard to do, error prone and fast. When sales and visitors both go down, sales depends on visitors, so the independent metric is the one to fix. Principal component analysis and the Spearman coefficient measure how correlated two metrics are. Outsourced. Amazon CloudWatch and Amazon SageMaker detect anomalies. One of SageMaker's algorithms is isolation trees: sparsely populated branches of a population are anomalies. Conclusion to Observability Observability in a distributed system grows with the organization that runs it. The chapter covered three parts: logging and monitoring, anomaly detection, and root cause analysis. Small and medium organizations collect data. The focus is on collecting the data and interpreting it manually. Medium to large organizations detect anomalies automatically, and may try to resolve some of them. Large organizations try to resolve quite a few anomalies and add root cause analysis, so that their teams function effectively. The problem of error handling is scaled out this way. Anomaly Detection Anomaly detection on the server side manages the health of a system: the servers publish their metrics to an engine, and the engine flags an anomaly and alerts an engineer. False positives are allowed far more than false negatives. An engineer investigating a false alert is much cheaper than a real alert being missed. Each service has its own metrics, so a service mesh with a sidecar gives uniformity. The sidecar is a library for common functionality, and it publishes the metrics of every application to the engine. Finding anomalies in the time series data: Fixed limits, from historical data. They ignore the trend: a metric that has gone down for months hits the low pass filter. Dynamic low pass and high pass filters that stick close to the graph. A sharp change is flagged. They ignore time: the spike on the 25th of December is normal. An isolation tree, which is a decision tree. It partitions the data by features, and a point set apart in very few partitions is an anomaly.
System Design Tradeoffs
- Memory vs. Latency
Memory vs. Latency A system can lower its latency by spending memory. The best example is a cache. Fetching a profile from the database takes time, say 100 milliseconds. The profiles of the people who are extremely active are kept in a cache in memory on the server. An active user keeps asking for his profile and his follower count. Both are kept in the cache, and each request is answered from it in 10 milliseconds instead of 100. The cost is memory. The profile is now stored twice, once in the database and once in the cache, and the cache costs money. The tradeoff runs the other way too. A smaller cache uses less memory, and more of the responses take 100 milliseconds. The medium approach has three parts: Keep the hot entries in the cache. Use a good replacement algorithm. Use a good write policy. Latency vs. Accuracy Latency is the time a system takes to respond to a request. A system can lower its latency by giving up some accuracy. Three ways: A cache. The system calls the database and the cache together. The cache answers 30 in one millisecond. The database holds 31 and takes 10 milliseconds. The system returns 30. An approximation. A request asks for the likes of a video. Counting them means reading a queue of database requests and then the database. Instead the system uses earlier data: the video had 10 likes at 1K views, and it has 100K views now, so it answers 1000. The assumption is that the ratio of likes stays the same. A sample. Google Maps knows a road's average speed is 20 kilometers per hour. Out of 500 drivers it reads 50, sees two kilometers per hour, and sends an alert that the road is broken. The answers are fast and can be wrong. A bank transaction or a balance cannot use them. Increasing accuracy increases latency. Relations Between Tradeoffs The parameters of a design trade-off relate to each other in pairs, and each relation is an up or a down arrow on either side. More memory, lower latency, because most things can be kept in memory. More memory, more cost. Lower latency, lower throughput. Throughput is how much of the running time is spent by the application, and it relates to latency alone. Greater cost, lower latency. It is a dotted line: more machines scale the system, but there is no guarantee. Lower consistency, lower latency. A system that is okay with inaccurate data gets very low latency. Lower consistency, higher availability. The two are inversely proportional. Memory has no real relation with consistency, availability or throughput. Those depend on the policies and the algorithms used. People using a system do not care whether it is a CA, CP or AP system. They care whether it is good enough for the SLAs. The trade-offs that bubble up are usually latency, consistency, availability and memory. Throughput and cost are rarer.
- Monoliths to Microservices Migration
Motivation A monolith keeps all the code of an application in a single repository, and a microservice architecture breaks it into services. Microservices have three advantages: Separation of concerns. Accepting PayPal payments is a change in the payment service only. Engineering is easier, because the expectations and responses of a service are well defined. Deployments are easier. The authentication service is deployed separately. Monoliths have two: They suit a small team. The move to microservices comes when the team has scaled, not the users. Communication is a function call with explicit parameters, and the compiler rejects a wrong call. In microservices, an ID that changes from an int to a string breaks every service that calls it: a breaking change. One way to move is to build the whole microservice architecture and redirect 10% of the users to it. The engineering effort is massive. The better approach starts with a new feature, such as analytics. It becomes a separate service, called over the network, with its own database and its own code repository. Infrastructure Requirements Adding microservices needs five infrastructure changes. Contracts. Each microservice defines how it is called, and ships a client: a library that other services download to make function calls such as get report. A library that is not up to date breaks the code. Routing. A load balancer or service registry routes requests from one service to another based on service capabilities. Deployments. Copying code to an AWS box with SCP and running a command does not hold as services increase. Jenkins deploys on every Git push to master, and containers replace boxes. Communication. The session service talks to analytics over a message queue, because a lost event only makes a report wrong. The profile service talks to payments with request response, for an immediate answer. Logging. A request crosses sessions, analytics, profiles and payments, so all logs go to a single repository. Kafka pushes them and the Elastic stack stores them. Every log for a request ID is then pulled out in one shot, which makes debugging and root cause analysis easier. Practical considerations A move from a monolith to microservices depends on three things: who owns the data, where the business responsibilities sit, and the cost of the infrastructure. Every microservice encapsulates the data it is responsible for. The profile service is the single source of truth for profiles, with a dedicated data store. The payment service asks it for profile information. Business responsibilities are condensed to a single place. An intermediary that condenses information from Google, Facebook and LinkedIn is used only by the profile service and changes with its requirements, so it is a component of the profile service. The initial infrastructure cost is high: logging, deployment infrastructure, documentation. A small team sacrifices features for it. The number of services per person: A startup: one person handles two services or fewer. A medium organization: one service or fewer, so two people handle a service and there is no single point of failure. A large organization: two to four people per service. Beyond four there is confusion, and the service is broken down. Containers: A friendly Introduction Capacity planning is a bunch of guesses about the compute, memory and storage an application needs, made before there is a computer for it. Earlier, a DevOps team or a finance team asked which box to buy for a piece of code. The answer came from capacity planning, and then a computer was bought from the shop. That computer is an investment. A small computer does not hold when the business scales, and the time and effort are spent all over again. A large computer is reasonably safe, but the initial hardware investment is very large. Horizontal scaling on the basis of hardware alone means getting as many computers as possible. One approach organizations took was to let their employees use a single computer. Multiple people using the same resource leads to contention, so resource usage is isolated as much as possible. Containers: Usecases A container is a lightweight form of virtualization that isolates one application from another. A program needs four resources: memory, I/O, processing and disk. The operating system is the sole manager of these resources, and a program asks for them through an interface. Programs that share one operating system can still starve each other. If one takes all the memory, everyone else is upset. A virtual machine is a strong boundary: an operating system running on top of an operating system. Virtual machines make cloud computing possible. Amazon and Google rent out spare hardware. The code becomes platform independent, and a machine is replaced by shutting one down and starting another. Starting an entire virtual machine takes a few seconds. A container gives app isolation without the full operating system, so it is faster to build and tear down. Docker lets the developer specify the operating system and the resources. Containers are still considered a little slow, and their management is not worth it for simple applications. Service discovery and Heartbeats A heartbeat is a regular message that tells a health service a server is alive, and service discovery is how the load balancer learns which boxes run a service. The health service asks S1 every five seconds whether it is alive, and S1 responds yes. If S1 misses one request it is marked critical. On the second miss it is assumed dead. The load balancer is told, and the service is run on another machine, S4. A machine sometimes responds yes while the application processes no requests. So the service itself sends a heartbeat every five seconds: a two-way heartbeat. A dead server with cron jobs still sends requests with stale data, a zombie. Once the health service marks it dead, it kills itself. A new profile service tells the load balancer its IP addresses and ports. The load balancer persists a snapshot of all the services, and other services ask it for an address. The health service reads the diff in the snapshot and opens connections to the new boxes.
- Summary - PDFPDF
Google Docs: Collaborative editor design
- Google Docs
Google Docs Requirements Google Docs is an app for creating and storing documents, and multiple people read and change a shared document in real time. The features: Creating, reading, updating and deleting documents: the CRUD model. Sharing, with permissions for reading and editing. A shared document sends a notification through email. Export as a PDF, which is not considered here. Version history, with a diff checker between two versions. Spell checking. The concern is the inputs a spell checker needs as a black box. Comment support for multiple collaborators. Offline support: changes made offline for a couple of days are sent in bulk. Storage and sharing are the core. Version history and offline support are solved with them, and notifications and comments are not core features. The core problems point to collaboration, which is a challenge in a distributed system for two reasons: Concurrency. Two people do operations without being aware of each other, and the conflict has to be resolved. Data consistency. Multi-region support keeps multiple copies of a document around the world. Document Schema A document is stored as an ID, an author and the data, with metadata such as a creation timestamp around it. The data holds all the characters and is of type text. The author is a varchar. The ID is randomly generated and is the primary key. One design splits this into two tables. Doc metadata holds the ID, the author, the timestamp and the other metadata in a relational database. Doc content holds the ID and the content in a NoSQL database. Relational queries run on the metadata table. The split turns into a mess: The metadata is hard to fix, so the table takes many alter queries. Finding the last 10 documents of an author reads IDs from one table and fetches them from the other. Such a join, across a NoSQL database and a relational database, takes forever. The design taken keeps one table of ID and data. The data is a JSON object whose key value pairs hold the author, the timestamp, the rest of the metadata and the contents. Storing Documents A document is stored with a limit on its size, because a document of arbitrary length is expensive to read and to update. A very large document could be stored as a linked list of pages: page 1, page 2, page 3. Each page ends with the ID of the next one. The file system picks up pages one after another until it reads an ID of zero. The problems: Arbitrary length. A person who does not want the system to succeed makes a document of 1 million pages. Additions. 10 more lines on page 3 push content to page 4, which may overflow too. Deletions. Deleted lines leave blank pointers and dead nodes. This is complex in a collaborative environment, so every application limits the size. In Google Docs the max document size is 50 MB, or 1 million characters. The limit is the max size that the text column allows. The database is most likely Cassandra, or Amazon DynamoDB, or a custom in-house key value database. Version History Version history stores each version of a document as its own row, keyed by the document ID and the version number. Document 1 holds ABC at version 1, AB at version 2 and ABD at version 3. The ID and the version number are merged into a single unique key. Most reads ask for the latest version, so the versions are kept in a separate table. The document table holds one entry for each ID, replaced on every update, so reads are quick. A request for a specific version goes to the version table. A version at every keystroke is wasteful. A cron job takes snapshots instead: The cron job reads the document. If the contents differ from the last version, it stores them under the next version number. If they match, nothing is stored. A cron job that checks all the documents every half an hour is a thundering herd. With a last modified timestamp on each document, the cron job runs every minute and picks up the documents modified in the last half an hour. Avoiding Thundering Herds in Crons A cron job run in a naive way performs no tasks until the cron time hits and then performs them all together: a thundering herd. With x tasks to be done in a time y, the aim is x by y tasks processed per second. The naive cron job instead puts a spike on the server, and other requests stop being served. The fix is inspired by hashing. Take 3000 documents and 30 minutes: A document's ID is divided by 30 and the remainder is its cron index. ID 37 gives 7 and ID 30 gives zero. The index is at most 29. At minute zero the cron job processes the documents with index zero: IDs zero, 30, 60. At minute one it processes 1, 31, 61. The documents are broken into 30 pieces, and each piece is picked up by one cron job that runs every 30 minutes. One big cron job becomes 30 small ones. The volume of tasks is the same and the peak is reduced, at the cost of some software complexity. Compression and Caching Storage cost is reduced by compressing documents, and compression has a processing cost. The compression is lossless, because lossy compression is devastating to people who work on the document professionally. Huffman codes are one choice, and there are better algorithms for text. Every write compresses the document before saving it to the database. Every read decompresses it before serving. A hybrid approach keeps the latest version, Vn, in its full form, because users are working on it. It is fast to access. The versions V1, V2 and V3 are compressed and kept in cold storage, which is cheap. Writes are sped up by storing operations as a log beside the copy of the latest version: The copy is ABC. Add XY and delete BC are stored as two operations. A get takes the copy, applies the changes yet to be made and serves AXY. Reads become compute intensive and many write operations are saved. The current document is eventually consistent. Going through the list of changes gives perfect consistency. Concurrent Writes with Locks A concurrent write is two people making changes to the same document at the same time. A document holds ABC. User A adds D to the end and expects ABCD. User B deletes B and expects AC. The operations can reach in any order, and both users are eventually served ACD. Pessimistic locking. Add D takes an exclusive lock on the document. Delete B fails to acquire the lock and waits till ABCD is written, then makes it ACD. Multiple writers cannot write at the same time, so it is too slow. Optimistic locking. Delete B does not wait. Each writer takes a copy of the document, giving ABCD and AC, and both try to write. One wins, and the other cancels its operation and retries or fails. Copying the entire document is expensive. Locks do not work, so the operations are merged instead of the state: ABC with add D and ABC with delete B merge into ACD. Two problems remain: how the operations are ordered, and who defines a complex operation such as bolding. Operational Transform Overview Operational transform is an algorithm that reconciles two copies of a document by shifting the index of each operation for the operations the other copy has already applied. A document is ABCD. One copy deletes at index 1 and becomes ACD. The other adds E at index 2 and becomes ABECD. An operation is defined by its index, not its character. The naive way performs each operation on the opposing copy: Adding E at index 2 of ACD gives ACED. Deleting at index 1 of ABECD gives AECD. The copies do not match. The delete pulled every index after it back by one. So the add is applied at index 1, and both copies are AECD. Google Docs most likely runs operational transform, which makes more sense with a server. A CRDT, a conflict-free replicated data type, is peer-to-peer: the copies share their data and are eventually consistent, with no central authority. The differences between two versions of a document come from the Myers algorithm, which Git uses. The longest common subsequence is a simpler idea. Permission Management Permissions on a document are held by a separate service, the permission manager, and not in the document's own table. The permission manager looks at every user request and decides whether it is valid. For each document ID it stores key value pairs of a user ID and an access: A private document has one pair: user 123 is the owner. Any other user gets an error. To share with user 124, a request to update the permission goes through the gateway to the permission manager, which appends 124 with read access. A write from 124 then fails. Link sharing for reads is a pair where star, meaning anybody, has read access. If any pair satisfies the permission the operation requires, the permission manager returns yes. Creating a document also goes through it, and the document is then added to the document service's database. With the permission manager in between, the gateway is decoupled from the document service. Each service scales independently.
Design a Location Based Service like Google Maps
- Google Maps
Requirements of a Map application A map application tracks where a user is and gives the best route from a source to a destination. The features taken up: Location tracking along whatever route the user chooses. A route from source to destination, updated along the way. Adding new locations, such as a restaurant or a house. Finding nearby stores, such as gas stations within a radius of one or two kilometers. The search is by Cartesian distance, not along the route. Traffic updates. Estimated time of arrival, built into the routing algorithm. The features left out are public transport, a custom time to leave, ratings and reviews, live sharing, and location history. Public transport is regular, has start and end times, and has a limited number of routes. The best route is a straight line, which most of the time does not exist. A route can minimize distance, tolls, turns or the chance of route changes: a highway is chosen over a thin road for the same 30 minutes. This design minimizes one thing, time. Routing Challenges in Maps Routing on a map means finding the minimum path from a source to a destination, where one number defines a road: the time taken to move from one end to the other. Running a graph algorithm looks simple, and the scale of the problem is massive. There are two challenges. Locations in the middle of the road. A source or a destination is more likely to be between the ends of a road than at an end. Too many paths. From Mumbai to Pune the highway takes around three hours, and the other paths also arrive. The thousands of ways are inside each city, from a place such as Powai or Andheri to the highway and from the highway to the destination. The one option is approximation. A location in the middle of a road is converted to a nearby corner point. Points on a road that have turns are marked as limiters, and the source and the destination each use a nearby limiter. Partitioning Algorithm: Splitting the graph into regions Partitioning splits the graph of roads into regions with a hub each, so that fewer routes are computed between a source and a destination. There are too many paths from a source to a destination, and two approaches: reduce the number of routes, or compute the result faster with some approximation. On a small graph every route is calculated: one takes 8 minutes and the other takes 10. From Powai to Andheri, around 10 or 15 kilometers, calculating all the possible routes every time is too much. Reducing the routes: The two locations are split into regions. Each region gets a hub, a common point where most routes start. It might be connected to a highway. Every point in a region connects to its hub. The best route between the hubs is pre-computed. The path may not be optimal: a point closer to the destination than the hub still travels to the hub. The trade-off is a quick suggestion to the user, not the best possible one. Graph partitioning algorithms find the hubs. Finding the shortest path - A* search A* search finds a route by approximation: at each point it picks the next point with the lowest sum of the time to reach it and the estimated time from it to the destination. There are too many routes to cache. From the source x, the possible next points are y, p and q. The cost of going to the destination d through y is the time from x to y plus the estimated time from y to d. The minimum of the three costs gives the route. The points and edges are stored in a graph database, which has the graph algorithms inbuilt. Edges are roads with the time required to travel on them. Accurate edge times come from live data. A person broadcasts the location at A at time T1 and at B at T2, and the average of T2 minus T1 is the expected time from A to B. The estimated time is a heuristic: the Cartesian distance at the current speed. 3 kilometers at 40 kilometers an hour is around 5 minutes. GeoHash and other proximity filters GeoHash assigns a hash to a location from its latitude and longitude, and locations that share a prefix are near each other. Location tracking is push updates to the server: the GPS location is sent every five seconds. It needs no WebSocket, because the communication is not bi-directional. In a tunnel without internet, the client uses the cached route and the accelerometer. Finding a nearby store takes three filters: Relevance. A keyword search on title and description, so that a search for a pharmacy finds a medicine shop. Ratings and reviews screen out closed stores and scams. Proximity. A square around the source, sized by the maximum distance a person walks, such as five kilometers. Walking time. Stores with an estimated time of arrival greater than 20 minutes are filtered out. GeoHash does the proximity filter. It splits the world into four pieces, each with its own bits, and splits each piece recursively, adding to the same prefix. It is inaccurate: it misses some nearby destinations and picks up some far ones. Detecting traffic jams and broadcasting updates A traffic update changes the estimated time of arrival for every user whose route uses a road that has become faster or slower. Three signals mark a stretch from X to Y: Updates from users on the road about congestion, a breakdown or construction. The average time to finish the stretch: an expected 2 minutes against an average of 15 minutes in the past 5 minutes. The number of users in the stretch. A dramatic increase suggests a traffic jam or a roadblock. The weight of X to Y in the graph database is updated from 2 minutes to 30 minutes. By proximity: user locations are stored in a quad tree or a Hilbert curve, and all users within 5 kilometers of X or Y get the update. Each client checks whether its active route uses X to Y, and if so requests a new route from its current position. By popular interconnections: a cache maps each highway to the users whose active routes use it, and a highway's update goes to those users. Calculating an accurate and efficient estimated time of arrival The estimated time of arrival is a function of the route: the sum of the time to travel every interconnection on it. The map is split into regions, and each region is recursively broken into sub-regions. A hub represents each region. Region R1 holds R2, R3, R4 and R5, and region R6 holds R7, R8 and R9. A route from a source in R3 to a destination in R7 moves up to the parent, R3 to R1. It crosses at the same level, R1 to R6. It moves down the sub-regions, R6 to R7. Only the fastest two or three connections between regions are kept, so Dijkstra's has few edges to look into. A new route that consistently takes three minutes where the normal one takes six replaces the slowest connection. The route may not be optimal: 10 minutes instead of 8 or 6. Users care about a small ETA and almost equally about a predictable one, and well-known routes vary less. The more historical data there is on an interconnection, the more accurate the prediction.
Chess Design: Building a highly scalable turn-based gaming website
- Chess Design
Requirements of a chess website A chess website matches players from around the world and carries their moves to each other with low latency. Three requirements: A matching engine. Players have ratings, and filters feed the matching so that games are between equally rated opponents. Latency. A move is accepted or rejected quickly, the opponent is notified, and the time a move spends on the server is minimized. An analysis engine, which sends players statistics on their games. It is done in batch. A player makes a game challenge request: the user ID, the type of game, the color, and preferences such as the opponent's maximum and minimum rating. The matching engine service converts the relative ratings to absolute values and checks whether any existing challenge matches the new one. The challenges live in a custom in-memory cache built on a sorted set, with a TTL of 30 seconds. A SQL database with range queries backs it up. When memory runs out the cache is sharded: multiple instances of the service, with users directed by user ID. Handling connections at scale A chess server notifies the opponent of every move, validates the move, and stays fair to players on slow connections. Users connect to gateways, reverse proxies that route a request by user ID. HTTP has a client to server relationship: a server cannot send a request to a client. WebSockets give bidirectional communication, and a gateway database records which user is connected to which box. A direct connection between two players over WebRTC saves bandwidth, but there is no mediator: a hacked client can cheat. A single source of truth needs the game engine. The game engine keeps a cache of game ID to game state, so a move is checked against the chessboard. The cache is sharded: the game ID modulo the number of servers picks the game engine. For fairness the server does not trust the client's timestamp beyond a maximum latency, 500 milliseconds. A claimed time within that limit is taken; an older claim is replaced by the time of receipt minus 500 milliseconds. Consistent Hashing vs. Sharding Consistent hashing reassigns buckets whenever a server is added or removed. With game state held in an in-memory cache on each server, that reassignment can produce an illegal state. Server 5 joins the ring and takes the buckets from 351 to 0 from server 4. A service with a cached routing table sends request 388 to server 4, which drops it or redirects it to server 5. The edge case is a slow hand-over: The load balancer tells server 5 to load buckets 351 to 0 from the database. The request asking server 4 to remove them is delayed, so 4 and 5 hold the same buckets. A black move goes to server 4 and is saved in the database. The next white move goes to server 5, which never saw the black move and rejects it. Asking the load balancer or the database on every request fixes this, and neither is performant. The chess design uses sharding instead: each server is the sole source of truth for a concrete range. Rebalancing means restarting the servers. Connection related thundering herds A thundering herd is a huge number of requests that arrive at the server suddenly. Millions of users hold connections to three gateway boxes. When user A sends a message to user B, A's gateway finds B's gateway. Querying every other gateway eats bandwidth and fills request queues, so a connections database stores which user is connected to which box. Adding a feature to the gateway service means a code change and a restart. In a parallel deployment all boxes restart at once: Every connection between the gateways and the users is lost. All the clients reconnect at the same time. The gateways are under tremendous load, and the system is down for a while. The fix is a separate connection service. The gateway is a dumb service: it creates TCP sockets and forwards the raw data. The connection service holds the logic and the versioned clients of the internal services, such as profile, game and matcher. A client update restarts only the connection service, and the gateway loses no connections. Request Batching and Conclusion The chess design has standard services, non real time services and a real time core. Profile, authentication and sessions are a standard set. Campaign announcements subscribe to events on message queues. Three services run as a stream or a batch. The cheating checker compares a day's games with a chess engine, on moves and on timing. The rating engine receives wins and losses as a stream and writes ratings to its own database. The game analyzer runs for premium users. All move requests go to the game engine, which shards its cache by game ID. The matching engine finds two requests that satisfy each other and creates a game. The spectacle service broadcasts moves to spectators, and two or three seconds of delay is fine. With 10,000 spectators, 5,000 in India and 5,000 in the US, it sends one request to each gateway with the list of user IDs, and the gateway duplicates it at the last mile. The design comes down to latency, bandwidth and the number of connections per box.
- Architecture DiagramPDF
- Capacity PlanningPDF
- API ContractsPDF
- Summary - PDFPDF
WhatsApp Calling App
- Requirements ListPDF
- WhatsApp Calling App
Calling App Design A calling app passes a signal from one phone to another to create a connection, carries the data, and ends on a signal for termination. A call goes over the internet with voice over IP, or over PSTN. PSTN blocks a portion of the bandwidth for the caller, so it is charged. A voice over IP call: C sends the call state manager a request with the sender and receiver user IDs. The call state manager validates it and asks the session service for each session. Each session maps to a connection on the switch: 113 on box A, 114 on box B. The switch bridges the two connections. The switch publishes every state change to a message queue, and the call state manager logs each with a timestamp. A call that started at timestamp 53 and terminated at 100 is charged to the caller as one minute. An invoice ID keeps the same call from being charged multiple times. For PSTN, a recommendation engine chooses the spectrum provider by call quality and fee. Concept #1: Breaking calls into dialogs A dialog is the connection between one participant of a call and the server, and it is treated as an independent component. On the internet, the signal hops through the routers of internet service providers to the server. A phone call goes through the PSTN, a network of phone service providers. If A is on Verizon and B is on AT&T, Verizon either drops the call or forwards it to AT&T, which sends it to B. The provider that terminates the call charges for it. Verizon's selling price is fixed, and its cost price depends on where the call terminates. Calls go through the application server, because only registered users make calls. The call is broken into dialog A and dialog B. A third user C adds dialog C, which gives conference calling. A dialog table maps a dialog ID to a call ID, with the provider, the cost price, the timestamp and the direction. Verizon at $1 per minute and AT&T at $3 per minute make the call's cost price the sum of its dialogs. Concept #2: The state machine Every dialog is a state machine: a set of actions that move it between states, from initiated to terminated. Initiated. The caller sends a call to the server, or the server makes a call to the callee. Ringing. A validated callee goes here, and the phone rings. Started. A validated caller goes here immediately. Terminated. Any state reaches it: validation fails, the balance is not enough, or a user cuts the call. Charging starts when both users have hit the started state and runs until terminated. The entire call needs a state machine too. Keeping that logic on the switch is a bad idea. A restart of a proxy, gateway or endpoint breaks every connection, and all the users reconnect to the box, which is the thundering herd problem. The state machine logic changes with the requirements, and a code change means a restart. So the boxes are kept as dumb as possible. The call state manager (CSM) stores the conditional logic and turns it into a simple request response. Concept #3: Charging Users Users are charged after the calls on a postpaid plan, and during the call on a prepaid plan. A prepaid user pays 500 rupees for 500 minutes. A user with one rupee left is allowed one minute, and without a constant check speaks for three hours. The switch polls the billing service every minute, and it answers yes or no. Or the billing service returns a max talk time, such as three minutes, and the switch cuts the call at the limit. That logic moves to the call state manager, which stores the max talk time per call ID. It costs two API calls and removes the logic from the switch. The max talk time is set at the start of the call. If 10 people join a conference call from different countries, the user exceeds the budget. A request response architecture is simpler. Every minute the switch asks to continue, and the call state manager asks the billing service whether the user has the three rupees for the next minute. Consistent Hashing for caching call state Consistent hashing maps call IDs to caches so that adding or losing a cache moves few entries. Three caches A, B and C hold the state of eight call IDs. The usual mapping is the hash of the call ID mod the number of servers. Adding a cache D changes the remainder to mod 4, and entries migrate from box to box. The churn is the number of entries a server has to get rid of. On a hash ring: The hash of each server ID mod a large prime number M places A, B and C on a ring from zero to M minus one. The same hash places each call ID on the ring. Each call ID is stored on the next clockwise server. When D arrives, only 8, 5, 7 and 6 move to it. When A crashes, 1 and 3 move to C. The ring suffers from skew: D takes four call IDs and B takes one. Mapping every server onto multiple points with different hash functions makes skew unlikely.
- Calling App ArchitecturePDF
- API ContractsPDF
- FAQsPDF
- Capacity EstimationPDF
- FAQs 2PDF
- Summary - PDFPDF
Recommendation Engine Design
- Recommendation Engine Design
Converting data sources to a lake A data warehouse is a place where the data generated by business services is collected and used later: analytics, alerts and monitoring, a query dashboard. In a food delivery system the profile, sessions, trips, restaurants and payments databases need not match. Reading from them for every insight puts load on databases the main services need, so a copy of all of them is made into a data lake. The lake is heterogeneous. Its records are linked by something common across the databases: the delivery ID. One ID links five types of data into a single row. A machine learning system fed with this data predicts outputs from inputs, such as the chance of a refund. If refunds are high for restaurant XYZ, the business promotes XYZ less. Three things hold for the lake: A cron job pulls the data from the databases periodically, every 30 minutes. The lake is immutable: entries are added, existing records are not updated. The lake is cheap, on a file storage system such as HDFS. The Map Reduce Architecture MapReduce spreads one job over layers of boxes that read from a data lake and produce a data set. The work is partitioned across different systems, and the hardware that runs it does not matter. If one box crashes, only the data relevant to it is affected: the data is sent again when the box recovers. There is no single point of failure. The task is broken into pieces: The filter layer. All of its boxes filter. More layers, which map or expand. A data set. Everything is collected into a single database, whose schema is defined by the people who want the data. The data set goes to the downstream systems, such as the machine learning system. Multiple processes run on the same data lake and the same hardware and give different outputs. One filter and reduction produce data set one for the operations team. Another produce data set two for the alerts and monitoring team. The process is also known as ETL: extract from the lake, transform in the boxes, load onto the downstream services. Fault tolerance and engineering optimizations A MapReduce job is fault tolerant because its boxes are stateless and its stages are decoupled. Whether a stage pulls its work or has it pushed is the wrong question. A data set sits between two stages: an intermediate table that stores intermediate results. Each stage reads from the table before it and writes to the table after it. The boxes hold no state. There is an input and there is an output, and what a box does is computation. The current state of the box does not define what the output will be. When a box crashes: Another box goes to the input intermediary table. It recomputes. The output is the same. It does not matter which box runs a task. Real time analytics Real-time analytics answers what a batch job answers too late, such as an alert when the number of trips goes down dramatically. The data lake pulls from the original sources periodically, and the jobs on it are cron jobs. Querying the lake always takes time. Instead, the services that own the data send events on an event bus, something like Kafka. The analytics engine is interested in the trips topic and the payments topic. A subscriber condenses two events into a single event on a separate queue, a topic of its own. The analytics engine pulls that data and finds trends. The decision goes to an engineer or to an operations executive. This is a streaming architecture. Its queues are temporary, simple operations are easier in a stream, and some loss of events is okay: availability matters more than consistency here. Complex operations, such as ordering all deliveries by price, are easier in the batch process, which loses nothing. The combination of streaming and batch processing is the Lambda architecture. Ranking restaurants in real time and batch A batch job answers a question that can wait: the number of deliveries that failed because the delivery time was too long. The payment service says the status is customer cancelled. The delivery service says the predicted delivery time was greater than X. The two databases go through a MapReduce job: A join of the two. A filter on the delivery time being greater than X. A filter on the status being cancelled. A reduce, which takes a count of the deliveries. The job takes up to one hour. The data set goes to the machine learning engine, which finds correlations: a delivery executive with less than two months in the company, or a gourmet restaurant that takes long to prepare. Correlation is not causation, so human beings look at the result. Sources of data split in two. Real-time data goes as events to the downstream systems, which react immediately. Data persisted in the data lake goes through the long MapReduce process, and its final result is used by the downstream systems to generate insights.
- Querying on top of Views over the DBPDF
- Data Lake InteractionsPDF
- Map Reduce ArchitecturePDF
- Job SchedulerPDF
- Example: Ranking RestaurantsPDF
- Final Architecture DiagramPDF
- Summary - PDFPDF
Netflix Movie Onboarding
- Netflix Movie Onboarding
Video Processing Netflix onboards new content by breaking each video into chunks and encoding every chunk in every format and resolution. A codec is a way to compress video, and lossy compression loses data to keep the file smaller. Formats differ by internet connection speed, and resolutions differ by device. The number of formats into the number of resolutions is the number of videos processed. One computer takes time and has a chance of failing, so the original video is broken into chunks. One resolution, one format, one chunk is one task. Chunks were first three minutes each. A chunk that ends in the middle of a car scene causes a lag. Chunks are now based on scenes. A shot is four seconds, and shots are collated into a scene that is fetched together. For a sparse movie, where viewers jump between points, Netflix sends only the data asked for. For a dense movie, watched continuously, it proactively fetches the future parts. The video is stored in Amazon S3, a cheap store for static data. ISP Synergy Open Connect is a cache that Netflix places with internet service providers, so that a request for a movie is answered near the user. An internet service provider (ISP) maps an address to an IP address, a computer somewhere on the internet. The Netflix servers are usually in the US. From India, a signal takes a lot of time to go there, and video is a lot of data. Netflix extended caching to ISPs: A request from India for a Bollywood movie does not hit the Netflix US servers. The ISP asks the Open Connect box, which holds many movies. If the movie is there, it is returned quickly. Bandwidth and time are saved, for Netflix and for the ISP. The box is localized: different movies for India, Britain and the US. Around 90% of Netflix traffic is taken care of by these boxes. New content is copied in around 4 a.m., when the load on the boxes is minimum. Netflix processes a movie into chunks and populates the box with them. Virtual Advertising for live sports events Virtual advertising replaces parts of a live sports video with an ad chosen for the user who is watching. A recommendation system groups each user, ranks the ads and takes the top one. The options for rendering: Render on the client's GPU. Cell phones have poor GPUs, and the ad stream has to be sent as a second video. Green screen the sidelines. People in the stadium then see no advertisements, and that revenue is lost. Use the fixed cameras. A football match has 20 cameras, each fixed at a position and angle, so the section of video that is the side stand is known and replaced with an ad. Players in front of the stand are the challenge. Key overlays. The colors of the stadium ad are replaced and the jersey color is kept. It is fast, and it fails on a jersey of the same color and on skin colors. AI. The players, the football and logos are identified as objects and kept, and everything else is replaced.
- Summary - Netflix Movie OnboardingPDF
Design an Audio Search Engine like Shazam
- Audio Search Engine and Coding Judge
Design an algorithm for an Audio Search Engine An audio search engine such as Shazam takes a 10 second clipping of a song and returns the original song. A clipping is taken in a noisy environment, so the whole sound wave is not compared. The song is represented concisely as a set of interesting points: points with a high variation in amplitude, which survive the noise. Each interesting point is stored as a frequency and a time. The amplitude value is dropped. The offset of the clipping is not known, so two points are defined by their frequencies and the difference in time: F1, F3 and delta time. All pairs of n points come to about n square pairs. The song is broken into chunks of points instead: eight interesting points in chunks of three give six chunks and 18 pairs. The points in a chunk are converted into a single combinatorial hash, a key in a dictionary. The client sends the clipping to the server as a set of hashes. The server returns the song with the maximum number of matches. Online Judge An online judge takes code from users across the world and tests whether it passes the test cases of a problem statement. Each fix creates the next problem: The server executes an uploaded file immediately, checks its output against the known output, and stores accepted or rejected in the database. Thousands of users submitting together in a contest are more than it can handle. Rate limiting drops or blocks requests, which is not fair in a contest. A message queue makes the system asynchronous. The file goes to a distributed file system such as S3, the upload is acknowledged immediately, and an event with the user and the code URL is published. The server processes the events one by one. Malicious code can still run on the server. Virtualization runs the code in a virtual operating system. In the worst case that operating system crashes. A container does the same without an entire virtual operating system for every execution. The core problem is a job scheduler, a container and security.
- Capacity EstimationPDF
- FAQsPDF
- Summary - PDFPDF
20 Whitepapers
- 20 Whitepapers that changed the world
A white paper shows the implementation details and the practical aspects of building a system. Most of the trade-offs in it come from the product requirements. Memcached at Facebook is the example. A request for a profile is an aggregate query that hits multiple shards, so splitting the key space makes things worse. Facebook chose replication. The papers run from number 20 to number one: Monolith, FlexiRaft, Spanner and Minesweeper: real-time recommendations at TikTok, quorums at Meta, a strongly consistent database at Google, and automated root cause analysis. Cassandra, FoundationDB from Apple and Amazon Aurora: three databases. Pregel, Dapper, Chubby, Megastore, Bigtable, MapReduce and the Google File System: graph processing, tracing, distributed locks, storage and data processing at Google. TAO, the graph store from Meta. Memcached, in the top five. Monarch and Gorilla, the time series databases of Google and Facebook. Gorilla is in the top three. Amazon DynamoDB, at number two. Zanzibar, a system by Google, is number one, for its practical optimizations around rate limiting and fault tolerance.
Scaling Memcached at Facebook
- Scaling Memcache at Facebook
Memcached at Facebook is a common cache that answers the hundreds of key value reads behind a single page. A home page is a tree of posts, comments and replies. A cache used by all engineers needs high adoption, so engineers import a client library, which compresses values and batches requests. It is a look-aside cache. A get that misses goes to MySQL and populates the cache. A set updates the database and deletes the key, because a delete is idempotent. The cache is scaled according to the access pattern: Protocols. Set requests use TCP, so they go in order. Get requests use UDP, which saves 20% in request latency. Replication. Sharding spreads the keys of a page over all nodes. With replication, one node answers the whole page. Rate limiting. Each client keeps a sliding window that is neither too large nor too small. The gutter. Spare instances, around 1% of all nodes, reduce client failures by 99%. Mcsqueal. The keys to delete are added to the MySQL binary log, which is propagated.
- Why Facebook keeps its social graph in memory
Facebook keeps its social graph in memory, as an adjacency list, so that lookups are fast. Memcached is a mature piece of technology at Facebook. Facebook was one of the first companies with a massive graph network, and graph databases are not common. A graph is represented as an adjacency matrix or an adjacency list. The number of users is very large and the matrix is very sparse, so the graph is kept as an adjacency list: A map. The key is a person and the value is the list of that person's friends. Get key Gaurav returns his friends. A map inside it. Checking whether Harsha and Gaurav are friends goes through the list. Stored as a map, the check is order one. A request for a news feed, or for friends having birthdays, goes through the friend list. These queries are made in memory. The objectives are low latency, high availability and ease of use. Very high consistency is not needed. A cache used by one or two teams limits its optimizations to one team.
- What one homepage load asks of the cache
One homepage load fetches hundreds of key value pairs at once. A homepage shows posts. The posts have comments and likes, the comments have replies, and people click to see who has liked a post. A popular video is cached with its top comments and their top replies. There is no clear structure, because nobody can guess what users will find popular. So the page is not cached as one piece. It is broken into levels: Level one. Notifications and popular posts, which everyone gets to see. Level two. The top 10 comments of a popular post, or the profile and mutual friends of a person to follow. It is cached too, and fetched only when the person clicks. One homepage request fans out into nested calls: 95 keys for most requests and 1,700 for some. Facebook constructs a directed graph of the data. Some fetches run in parallel and some depend on others. Updates follow read after write consistency. A like stays hit after a refresh, and an added comment shows on the post.
- A look-aside cache behind a client library
A look-aside cache is a cache deployed apart from the database and outside the web server, which calls it. Memcached is an in-memory distributed hash table, and a write to it is a deletion: A get for key 1 returns 10 from the cache. A set of key 1 to 30 removes the entry from the cache and writes 30 to the database. The next get for key 1 is a cache miss. The value 30 is fetched from the database and populated in the cache. So the cache takes two operations, an add and a delete. An engineer does not manage any of this. The code imports a client library, called mcrouter, and calls get, set and delete. The client does serialization, compression, request routing, error handling and request batching. It is deployed along with the code, as a Mailchimp or an AWS client is, and adoption across the organization is very high. Fetching 1,700 items is likely to hit a failure and a retry, so tail latencies are high.
- UDP for gets and TCP for sets
Memcached at Facebook sends a get request over UDP and a set or delete request over TCP. TCP is acknowledgement based, so all writes are ordered. UDP is best effort and connectionless: no connection is created, and TCP connections are limited for a box and cost something. Facebook noticed a 20% reduction in request latency for get requests. A write can then be processed after the read that follows it: Three requests are sent: get key 1, set the key to 30, get key 1. Handled in parallel, the two gets are processed before the set. Read after write consistency breaks. A user likes a post, refreshes the page, and the like is not there. A smart client avoids this with a version number. The home page is version 29 and the like is version 30. A reply from the cache at version 27 is treated as an error on the client, which does not try to recover from it. The client here is the one hosted on the web server, not the UI client.
- A sliding window on the client
A sliding window is a rate limit kept on the client: it moves forward as responses come back, which limits the number of requests in flight. The size of the window is a trade-off. A larger window causes more congestion, so the last request waits a long time. A smaller window causes more round trips, because the requests beyond it are rejected and tried again later. The size is therefore not fixed: The window grows. A system that handles 3000 requests per second is given a little more, and while requests succeed the window keeps increasing. The window shrinks. When requests start failing, the window size is reduced. With 200 requests, the 200th waits a long time. With a window of five, the sixth request is bounced back. A static limit of 200 does not adapt. When the hardware improves, the window sets itself with no code change. A very large window does not help either. A user who waits three seconds hits refresh, and memcached gets two requests on 95 keys.
- Leases against stale sets
A lease is an ID that Memcached hands out with every cache miss for a key, so that a late set carrying an old value fails. Memcached starts with zero data. Two web servers miss on the same key, A: The slow web server reads A from the database and gets 10. The fast web server sets A to 20 in the database. The fast web server reads A, gets 20 and sets it in the cache. The slow web server sets A to 10 in the cache. The cache holds 10 and the database holds 20. With leases, the fast web server picks up a new lease ID. The slow web server finds its lease ID is not valid, reads the value again and sets it. A lease ID is similar to a version number and to optimistic locking. Availability is the higher priority, so there is no strong consistency. Read after write is not strict. In rare cases a read does not show the reader's own update.
- Serving a slightly stale value
A slightly stale value is an old cache entry served to a reader who accepts it, so that a key written all the time is not loaded again for every read. A get that misses makes the application server go to the database, fetch the key and populate the cache. A post is liked constantly, so its key is updated constantly and kicked out of the cache. A reader does not care if the likes go from 3,507 to 3,508. So the client says how old a value it accepts. At 8:03 a like count from the last two minutes is fine. A profile picture is wanted within 30 seconds. A delete does not remove the entry: The application server updates the database and deletes the key from the cache. The cache marks the entry as old and keeps it. A reader who accepts data five minutes old is served the old entry. When the cache is out of space, stale entries are kicked out first. Nobody decides beforehand which data may be stale.
- Why short lived and evergreen keys are kept apart
An eviction policy decides which entry a cache kicks out when its memory is used up. A cache tries to answer all requests with the minimum number of database calls. It cannot predict what is asked next, so it picks an entry to kick out: the least recently used, the least frequently used, or FIFO. A single eviction policy does not work at Facebook, because the access patterns of its objects are different. Facebook saw two types of entries: Long lived, evergreen entries. People keep using them from time to time, maybe for a day. Logos, ads and profile pictures are like this. Short lived entries. They are popular for a short period and never used again, like a list of 50 entries run through once. Least recently used is good for the short lived entries and poor for the evergreen ones, which are used from time to time. Kept together, the short lived objects kick out the evergreen ones. So the cache is split into two, and each part gets its own policy.
- Why multi-key reads want replicas and not shards
A request that reads many keys at once is served better by replicas of a cache than by its shards. One home page request fans out into a get for keys 1 to 100. Three cache servers answer it slowly, and there are two ways to scale them: Sharding. The servers take keys 1 to 33, 34 to 66 and 67 to 100. The get is split into three pieces, then six when the shards are cut again. With a thousand users every shard still gets a thousand requests, so each has to scale from 100 to a thousand. The problem is not solved. Replication. Each server holds all keys from 1 to 100. One get goes to a single server, the next to another. Sharding is far better when there is no aggregation, because a request is routed to the right place. A cache that is out of memory evicts keys. A database cannot, so it has to shard or replicate. In the worst case a cache reads from the database, so durability does not matter.
- How one failed cache server takes down the rest
A cascading failure is a collapse in which the load of one failed server brings down the servers that remain. When a server collapsed at Facebook, it took time to find out, and then scripts had to be run to start it again. In 2011 FBAR took the common parts of the fixes engineers wrote for their failed scripts and made them an API. Even with this automation, a failure takes a few minutes to be detected and fixed. In those minutes the load on the other servers increases: Three servers, S1, S2 and S3, each run at 60% capacity behind a load balancer. S1 fails. Its 60 units of work are distributed equally, so S2 and S3 each carry 30 plus 60 out of 100. At 90% the chance of a server failing is high. When S2 fails, all the load hits S3. Facebook's answer is the gutter, a separate set of servers, S4. All of S1's requests are routed to the gutter before S2 can fail.
- The gutter pool
A gutter is a small set of servers that takes the requests of a failed cache server. With S1, S2 and S3, a collapse of any one redirects its requests to S4, the gutter. Once S1 is back, its requests go back. This one backup reduced client failures by 99%. The gutter is already working, so it is not autoscaling, and it is common to every server. It adds 1% more server capacity, where a backup for each doubles it. The client's part: A get times out once. The client assumes the server has failed and queries the gutter. On a cache miss in the gutter, the client sets the entry. On a cache hit, it does nothing. Entries in the gutter expire sooner, so a profile changed in the gutter and in S1 is not inconsistent for long. The load is not distributed over the other servers, because a single key can account for 20% of the requests to a server. A server that gets two or three of these keys is overloaded.
- Clusters and invalidation from the commit log
Mcsqueal reads the binary log of a MySQL database and broadcasts every committed update to the other databases and to the caches that use them. Adding servers the naive way lets every web server connect to every memcache server. Facebook broke its architecture into clusters instead. The web servers of a cluster talk only to its own memcache servers, and each cluster is responsible for the entire data set. Each cluster has its own database, so the databases are not consistent. A web server that broadcast every set operation to all databases would be too expensive. The log does the work: MySQL notes every operation down in its binary log, which it replays after a collapse. One of five databases commits an update to its log. After some time mcsqueal reads the log and broadcasts the update to the other four. One line before each update, mcsqueal has written a delete of that key from memcached. The relevant caches delete the key. A single update reaches every database and cache, which gives reasonably high consistency.
- Regional pools for large rarely read objects
A regional pool is a single cluster that holds a large object few people read, in place of a copy in every cluster. The group Powai chess players may hold ten thousand people, and few people in the US, China or Australia look at it. So the object is kept in one cluster, close to India. The other caches do not have it, and the pool is not replicated across regions. A read from the US is not answered by the US cache. Mcrouter looks at the key and routes the read to the Indian server. The cross continent call is rare, and the single copy saves a lot of memory. A cache failure impacts a small set of users. Three factors, measured against thresholds, decide that an object goes to a regional pool: It is accessed infrequently. It is large. It does not affect many users, so the blast radius is small. The object is then assigned to a single cluster, and mcrouter knows where to send a key by looking at a routing table.
- Why a cold cluster warms from a warm one
Cold cluster warmup fills a new cluster's cache from a warm cluster's memcached, which reduces the time to heat up from days to hours. A new cache cluster is completely empty. A get request misses, the value is set, and the next get request misses again, so the cache is useless until it is populated. On a miss the cold cluster does not hit the database. It hits a warm cluster's memcached, a cross region call, because something popular in one cluster is likely popular in another. Mcrouter does this based on a config flag, until the new cluster has normal hit rates. This creates a race condition: Initially K is 5. The cold cluster sets K to 10 in the database. A get for K misses in the cold cluster and hits the warm cluster, which returns 5. Mcsqueal invalidates K in the warm cluster. The cold cluster holds 5 and the database holds 10. The database never tells the cold cluster to reset the value, so it stays stale.
- One name change followed through a cold cluster
A cold cache is a cache whose hit rate is under the threshold at which it is called warm. A user changes his name at a Facebook web server that has a cold cache and a database. A warm cache stands in another cluster. The web server deletes the user's entry in its own cache and sets the new name in the database. The user refreshes the page. The web server goes to mcrouter, which hits the warm cache, because the probability of finding the entry there is high. The warm cache still holds the old name. Till now there is no problem. Deleting from the warm caches as well means deleting from all clusters in the world. One database update hits clusters in India, the US and the UK, and waits for the responses. So only one cluster is hit at a time, letting go of consistency for latency. Mcsqueal corrects the warm side. It broadcasts the update to all databases and to the caches that care about the value, and the entries become consistent again.
- Two seconds of probation
Two seconds of probation is a wait on a key that has just been set, so that the cold cache is not filled with its old value. The cold cache holds the old name because it was fetched from the warm cache. Mcsqueal kicks that entry out of the warm cache, but it does not broadcast the binary log to the source cluster. Invalidating everything is not an answer, because every update would then require an invalidation. So every key has a probation timestamp: A set marks the key and stores its timestamp. A get before that time fetches the value, and the mcrouter gives it to the web application server. The value is not stored in the cache while the key is in probation. Two seconds is a magic number. Facebook saw that most requests are managed within one second, and made it two to be doubly sure. The trade off is a cache that stays stale if the invalidate does not come through in two seconds. A key with no expiry time is never expired.
- How replication lag leaves a stale value in the cache
Cross-cluster consistency is keeping the cache of one region in step with a database that is written in another region. Facebook runs clusters of Memcached in several regions, and every region holds all the data. One region holds the master databases and the other regions hold read only replicas. All writes go to the master because the system is read heavy: read queries are 100 times the write queries. A write and a read in India race: A web server in India writes K = 10 to the US database. The same web server deletes K from the Indian cache. Another Indian web server gets a read for K and misses in the cache. It reads K = 5 from the Indian replica, which is the stale value. The MySQL binlog replicates K = 10 to the Indian database. The second web server sets K = 5 in the cache. Every later read finds K = 5 in the cache, so the value never changes.
- Remote markers against stale fills across regions
A remote marker is a Boolean flag that Memcached keeps on a deleted key. While it stands, Memcached does not apply a set for that key. A set updates the database and deletes the entry from the cache. A get that misses reads the database and sets the cache. Across regions this races: A write updates the US database and deletes the key. A reader misses, picks the old value up from its database and sets it in the cache. The cache is stale till the next update. With a remote marker, the delete tells Memcached that a remote update is coming. Memcached takes a set, gives a success and does not update the data. The system that reads the MySQL bin logs updates the Indian database and the cache. There is only one remote marker and no counter. After two writes, a reader that comes once the marker is removed can still leave stale data. The cache does not keep the updated value. It evicts it, which makes the rest of the system simpler.
- Memory slabs and a timer wheel inside one server
Adaptive memory slabs are the sizes of memory a memcached server stores its objects in, and the number of blocks it assigns to each size. Objects of one type are of similar size. Memory slabs are normally given as 1 KB, 2 KB, 4 KB, 8 KB, and those jumps are large. A small object in a large slab wastes the rest of it. Facebook defines its own slabs, starting from 64 KB: 72, 76, 80, 84, 92, up to 128 and on to 1 MB. The factor is one point zero seven instead of two. Memcached sees which objects are accessed. If profiles are accessed a lot and groups are not, it evicts the least recently used group and breaks that slab into pieces of 64 KB. The web server and mcrouter have no idea. A cache can always have a miss. Short lived items go in a circular buffer of linked lists. Every second the current position moves forward and that linked list is deleted.
- Lecture Notes PDFPDF
TAO
- TAO
TAO is Facebook's graph store, a wrapper of graph APIs over memcached, backed by MySQL. Objects are nodes and associations are edges. The store takes 1 billion reads per second on petabytes of data, and writes are few. The API adds an association, gets the associations of a source and a type, and counts them. Each cache shard holds a range of keys: Routing. The client hashes an object ID to find its shard. An edge goes by the hash of its source ID. The inverse edge. A like has an inverse, liked by, whose source is the post. One like hits two shards. The order. The two edges are written one after the other, so a failure can leave one hanging. A cron job finds the hanging edges. Writes and reads. The writes of a key range go to one place, and many replicas serve reads. Read after write. A write goes to the nearest replica, which forwards it.
- Why Facebook built TAO
TAO is Facebook's in-memory graph based cache with a minimal API. In 2009 Facebook was answering a lot of graph queries. A profile page fetches the friends, the liked posts and the places of one person. Another query asks whether Gaurav is a friend of Anubhav. MySQL and Memcached hold columns and key value pairs, while a graph is a set of objects linked to each other. So each team wrote its own objects and relations in code, and repeated the optimizations of the other teams. TAO rolls them into one library. TAO is a real time store. An analytical query, such as comparing the locations of two people, runs in batch on a data copy. The requirements: 1 billion reads per second. Of every thousand queries, 998 are reads. Multiple petabytes of data, in a graph that is hard to shard. A pull architecture in the clients, which can cause a thundering herd. A read hit rate of 95% and a read latency of 25 milliseconds. Cost is not discussed.
- Why a plain cache does not fit a graph
A simple cache like memcached is a key value store, and a graph kept in it loads whole lists and brings concepts irrelevant to graph operations. Edge lists. Every load operation fetches the entire list. Gaurav has almost 5 thousand friends, so showing them brings 5 thousand people into the cache. One edge. To know whether Pankaj liked a post, the post is the key and the whole array of likes is loaded into memory. Concurrent updates. Pankaj likes the post while Sanchit dislikes it, and one array has to allow both. A mismatch needs optimistic locking, pessimistic locking or a merge. Consistency. Memcached ensures it with leases and remote markers. An operation of one or two steps in a graph is three or four in a key value store. TAO is a library over memcached with its own data model of objects and interactions, and it takes care of the cache and the database in the background. There is no real efficiency gain. Engineers think in graph models and not in key value models.
- Objects and associations
TAO's data model has two records, an object and an association. An object has an ID, a type and a set of key value pairs. A profile with the name Gaurav is an object. An association links two objects. It has a source ID, a type, a destination ID, a timestamp and a map of key value pairs. Gaurav is linked to India by an association of type nationality. The timestamp is there for two reasons: Ordering. One request comes first, another later. Recent event sorting. Most objects that are accessed were created recently, and old posts are rarely seen. The source ID, type and destination ID are unique. A post is liked or not liked, so an association maps a one-time event well. A second check-in at the same hotel is not allowed. Objects map repeatable actions. Each comment on a post is an object, and so is a check-in. An inverse makes an association bidirectional. Gaurav is friends with Pankaj, so Pankaj is also friends with Gaurav. The API adds, deletes and updates an association.
- The four association queries
TAO offers four queries on a source and a type of association. Get. It returns the associations from the source to any destination in a set, between a start time and an end time. Count. It returns the count of all edges of the type from the source. Range. It takes a position and a limit, such as the first 50 after an offset of a hundred. This helps pagination. Time range. It takes a start time, an end time and a limit, such as the top 10 posts Gaurav has liked in the last three days. The 50 most recent comments on a post is a time range. The likes on a post are a count. A check-in can be stored in two ways. In the first, Gaurav has an edge to a check-in object, which has an edge to Taj. It is more flexible, but a query goes through two edges. In the second, each check-in object holds the place, so a count of places in the last three days is one query.
- A graph cache in front of MySQL
TAO is a cache tier in front of a database tier. Client requests are routed to the appropriate cache server, and the cache tier can manage any TAO request. The database tier handles multiple shards. The data has to be stored somewhere, and the database is MySQL, which Facebook has used for a long time. A request that the cache cannot serve moves on: A cache miss. The read goes to the next layer, which is another cache or the database. A write. It goes to the database, because a write needs high consistency. The cache contains commonly queried objects, the likes on each object, and how many people have liked it. Its replacement policy is least recently used, the same as memcached. The cache also gives smart responses. A cached count of zero answers a later get with the same parameters with an empty set. Brad Pitt has zero recent posts, so a get for his recent posts returns nothing. This reduces latency for a common query pattern, where get and count queries come together.
- Why an inverse edge can be left hanging
A hanging edge is an inverse edge that exists without its original edge. Objects are sharded by object ID, and edges by their source ID. Gaurav and every like he has made sit in one shard, so a query for his likes goes to one place. This is data locality. The number of logical shards is much larger than the number of databases, which keeps their load almost uniform. A like is two associations, and the problem starts there: User U1 likes post P1. The like goes to the shard that the hash of U1 gives. The inverse, liked by, has P1 as its source, so it goes to a different shard. The source cache calls the remote destination cache, which hits its database and responds. Only then does the source cache write to its database. A failure in between leaves liked by without the like. A two-phase commit is slow, and a quorum has to wait. TAO repairs these edges with a job that runs periodically, so the system is mostly consistent.
- Why the destination is written before the source
TAO writes the edge on the destination before the edge on the source, and fails the request if the destination fails. A like is written in India and in the US. If India persists first and calls the US asynchronously, a failed call leaves a hanging edge, and the remote call is more likely to fail. So the source checks with the destination first: The destination fails. The source fails the query and the client retries. The destination succeeds. The source writes and sends a successful response. The destination succeeds and the source fails. No success response is sent. This case is rare. The other option is to write the source and retry the destination. The client is told everything is okay while a dead database is retried. A cron job is simpler, because it executes once. A smiley changed to angry shows the difference. The source has no like, so the update fails. With retries the like is updated on the source, nothing is on the destination, and every later update is retried.
- Why every write goes to one region
TAO keeps a copy of its caches and databases in every region, and sends every write to one of them. One deployment in the US makes each like from India a call across continents, so the data is replicated around the globe. A social graph cannot be split by location, because a person in Hyderabad has relatives in the US. A write made in India has to reach the US too. The log. Every create, update and delete is a line in a log. Replaying the lines rebuilds the database, which makes a replica. The exchange. Regions that all take writes exchange logs and replay the lines each is missing. In MySQL this log is the bin log. The cost. When every region is a peer, each database spends its time on updates from the others, and throughput goes down. The leader. Of a thousand operations, two are writes. All writes go to one region and every region serves reads. Clients always connect with the closest follower, never directly with the leader.
- How a write goes through the follower to the leader
In TAO a client reads from a follower and writes through a follower. It never talks to the leader. The write takes one path: The client. It tells a follower it has a write operation. The follower. It talks to the leader. The leader. It does the write and comes back to the follower, which tells the client. That follower and the leader have the latest data. A client that goes to another follower sees stale data, until change data capture propagates the write from the leader to all followers. The leader has rate limiting, and the followers ensure it does not get overloaded. Across regions the follower sends the write to the leader region, which updates its database. The MySQL bin log propagates it to the database in another region. Inside a region the caches have one leader. The leader cache serializes the writes, and the database propagates its updates to that one cache alone. 99 point 8 percent of queries are reads, so one leader in each region is enough.
- How followers catch up after a write
TAO lets go of some consistency for availability and efficiency, and a follower catches up with a write through an invalidation or a refill. The CAP theorem rules out perfect consistency with perfect availability. TAO serves stale data rather than go to a remote database. A post has 300 likes, the latest count is 301, and TAO keeps 300 for now. Writes are sent to the master. The follower that got the original write request gets a response after success, so it is consistent. Other followers are sent invalidation messages on a queue. A follower with an equal or greater version number ignores the message, and one with older data accepts it. The leader serializes concurrent writes, so a larger version number is always newer. An invalidation deletes the entire key. A group of 20 thousand people gains a member and the list is fetched from the database again. A refill names the updated range. The cache keeps the list and fetches only the new users. Refills are idempotent and can be replayed using logs.
- What TAO keeps in the cache and in MySQL
TAO's cache uses the memory layout of memcache. A cache of 64 GB is cut into slabs by the size of the objects, with most of the memory, 32 GB, kept for small objects. Each slab behaves like an LRU cache. Counts are stored separately, in count caches. An entry holds a source, a type and the count in a single 32 bit integer. Negative entries are stored too. A count of zero for the likes on a post answers the query for the people who liked it, and the database is not queried. Empty arrays are no longer stored, which saved 20% of the cache space: three thousand servers became two thousand four hundred. In MySQL, objects are stored in a single table of a 64 bit ID and the object data. Edges are stored in one table: The source, the type and the timestamp sit in one column. That column is the only index. All the likes Pradeep made in the last three days are sorted together, and a single query fetches them.
- Hot shards and lists too long to cache
TAO uses consistent hashing within a tier, and a shard can still become a hot spot. Sharding is on the source ID. A user with too many followers, such as Brad Pitt or Mark Zuckerberg, brings all of that load to one shard. Shard cloning. A hot shard is cloned to rebalance load, so reads to it are served by multiple followers in the tier. Update messages are sent to all the followers hosting the shard. Client caching. A client of TAO is a service that uses it as a database, such as a friends service. The service talks to TAO through a library, and the library caches very hot data. Some lists are very long. Brad Pitt has liked a lot of posts and DiCaprio's post has a lot of likes, so the query is expensive from either side. When the edge and the inverse edge both cross a threshold, TAO queries MySQL. Such a list is not cached, because a few of them fill the cache.
- Where a request goes when a server fails
TAO keeps serving when a database or a cache fails, because a request has a second place to go. The leader DB is down. A follower is promoted to leader. A follower DB is down. Cache misses are sent to the leader DB. The leader fails. A read miss hits the DB. A write goes to a random leader in the leader tier, which writes to the DB, writes the inverse edge and sends invalidations to followers. A follower fails. Clients have two addresses for each shard, a primary follower and a backup follower. The Indians try Europe before the US. The DB is the source of truth. A write fails only when the DB fails. Refills and invalidations reach the followers through MySQL's binary log, which works like a message queue. When the acknowledgement is not received, the leader queues the event to disk and tries later. The same write may be sent multiple times, so idempotency is expected. The primary and the backup may not be perfectly consistent. Availability is more important.
- TAO Lecture NotesPDF
Amazon DynamoDB
- Amazon DynamoDB
A DynamoDB table is read through its keys: the partition key is hashed to find the partition the data belongs in, and an optional sort key keeps the data inside that partition sorted. The partition key plus the sort key is the primary key, one unique key. With the post ID as the partition key and the timestamp as the sort key, the posts of the last seven days come from querying all three partitions and aggregating the results. More access patterns are served from the same table: A composite key. User ID plus post ID returns the posts of user six between 60 and 90 quickly. A local secondary index. The same partition key is sorted by the like count, in the same partition, and the data stays strongly consistent. A global index. It has a different partition key and is an entire copy of the table. Amazon limits them to four. They are eventually consistent, changed by the logs streamed from the original partition. Duplication and denormalization are accepted, and joins are not encouraged.
Apache Kafka
- Apache Kafka
Kafka is a system from LinkedIn that takes messages from producers, stores them on its servers and lets consumers pull them. Producers publish messages to a topic, which is split into partitions. Messages within a partition are ordered. Partitions sit inside brokers, the Kafka servers. A consumer pulls using its offset. At 7 trillion messages per day, recovery has to be automated: Replicas. Every partition has replicas on other servers. Writes to different replicas leave the data inconsistent. A primary. One primary replica takes all writes, and the other replicas pull from it. When it fails, another replica takes its place. The high watermark. A consumer sees only messages that have been replicated. Batching. Producers send and consumers pull messages in batches. Incrementing the offset after processing gives at least once delivery. Incrementing it first gives at most once. In a consumer group, one consumer pulls each partition. Zero copy pushes a message from the file system to the socket, skipping the application cache.
- Why LinkedIn built Kafka
Kafka is a system that accepts events, stores them in a persistent store and distributes them to all interested parties. Around 2011, large scale internet systems like Google, Facebook and LinkedIn had problems consuming so much data and storing it. Kafka was developed by LinkedIn. A celebrity posts on LinkedIn. That single message has to reach many notification servers. Kafka sits in between: The producer sends the message. Kafka says it got the message and takes care of the delivery, at least once or at most once. Kafka keeps the message for a retention period of one or two weeks and retries it. A subscriber that does not accept it in that time loses it. Publishers only publish and consumers only consume. Kafka scales up as the message rates increase. The architecture becomes three parts: producers, distributors and consumers. Kafka was made for the producer consumer architecture, retention of messages on disk, scale (petabytes of data per day in 2015, recently something like 7 trillion messages per day), high performance, simplicity for its clients and reliability.
- Topics, partitions and the message key
A message is the unit of data in Kafka, like a row in a database, and the message key decides which partition holds it. A message carries a body, a partition ID and a topic. A topic is like a queue, and a very large topic is split into pieces called partitions. A message reaches its queue in two steps: The topic. The sender names it. The partition. The hash of the message key, modulo the number of partitions, gives the partition ID. The key can be the user ID of a profile, 356, or any data in the event. A custom router can replace this function. Messages are ordered by topic and partition. One partition is processed first in, first out, never in parallel. Debit 500 from user A and credit 500 to user B, sent to the same topic and partition, are processed in that order, so the final state of the consumers is correct. Partitions give scalability, reliability and ordering. A hot topic takes more partitions, and when one partition fails the others continue.
- Why producers and consumers batch messages
Kafka writes messages in batches: a producer sends up to 50 events in one call, in place of one call and one acknowledgement for each. A consumer batches too. It names its offset and asks for 50 messages. Kafka sends 50, or all it has when there are fewer. Batching trades latency for throughput. Messages wait in memory, so the system is no longer real time, and throughput increases. Three things follow for a batch: A batch goes to one topic and partition. A producer that writes to three queues holds a batch for each, which consumes memory. The client can force a send of fewer than 50. A batch is a single API call, and its messages are added to the queue in order. A client that collapses loses its batch, unless it stored the messages. The producer and the consumer batch at their own rates, because the messages are stored in between. A batch is compressed: the metadata of 50 messages is reduced. Messages can have schemas in Avro, a format like protobuf.
- Consumer groups and who moves the offset
A consumer group makes sure that all the messages of one topic and partition are consumed by the same member of that group. Without a group, two consumers take messages from the same queue. Debit 500 goes to consumer one, which takes 10 milliseconds, and credit 500 goes to consumer two, which takes one millisecond. The credit entry executes before the debit entry. With a very fast consumer, a transaction T2 executes before T1. Inside a group the messages are accepted in order, distributed in order and processed in order. More consumers than topic and partition pairs are of no use. Two consumers outside a group, C1 and C2, each have their own offset in Kafka, so both consume the same messages. Kafka deals only with the offset. The guarantee is managed by the consumer: At most once. The consumer pulls 50 messages and increments its offset before processing them. If it collapses, those 50 are never processed. At least once. The consumer increments its offset only after it has processed the 50 messages.
- Brokers, replicas and retention
A broker is a Kafka server. It receives messages from producers, assigns each one an offset and commits it to disk, like a log. A consumer mentions its offset and the broker reads from there. A single broker serves thousands of partitions. When one server goes down, only some partitions of a topic are affected, and the pieces of a queue are consumed in parallel. Each partition is replicated into multiple brokers for redundancy: One copy is the primary, the others are replicas. A replica can be one message behind, so consumers read only from the primary. If the primary fails, a replica that is in sync is promoted: one that pulled all the messages in the last 10 seconds. A replica that is out of sync cannot stand in the election, but it can vote. The replicas are not read. They are for fault tolerance. Retention is set per topic by time or by storage. When it runs out the oldest message is dropped, and only one member of a consumer group is affected.
- The controller and ZooKeeper
The controller is one broker of a Kafka cluster, elected as the overall leader, which assigns the primary of every partition. A single broker serves thousands of partitions, and Kafka has a set of brokers. One of them acts as the leader. ZooKeeper does the leader election for Kafka, through ZooKeeper atomic broadcast. The leader monitors the other brokers for failures. Kafka uses ZooKeeper for cluster management: Registration. A broker registers with a unique ID. Notifications. Subscribers for registration and deregistration listen to /brokers/id. Removal. ZooKeeper has a snapshot of which brokers are alive. A broker that crashes does not respond to health checks on time, so ZooKeeper removes it from the cluster and no new messages reach it. The controller chooses and reassigns the primary nodes for partitions. For partition P1 the leader is L1, and for partition P2 the leader is L2. A topic T1 with 1000 partitions and three replicas for each partition is 3000 pieces of queue. Every partition needs a primary, so the controller selects 1000 primaries for this topic.
- The high-water mark, tombstones and zero copy
Kafka sends a message to consumers only after every in-sync replica holds it. A replica is in sync when its copy of the data is no more than 10 seconds behind. With replicas R1, R2 and R3, and R3 out of sync, a message that R2 and R3 hold is not enough. It has to reach R1 and R2. If R2 fails, the consumer reads from R1. Events are immutable, so a message is deleted with a tombstone, a later message with a null in its value part. It marks a logical deletion for the key, and the previous values for that key go when log compaction runs. A like that is taken back is a null. Zero copy removes a step from sending a message to a consumer: The standard process. The broker loads the message from the file system into its application cache, then writes it to I/O. Those are two I/O calls. Zero copy. The file system cache writes directly to the network channel, without intermediate buffers, in a single I/O call.
Apache Spark
- Apache Spark
Apache Spark is a general purpose data analysis system that keeps intermediate results in memory. The paper is from Berkeley. Before it, each system was specialised: Dremel for aggregation queries, MapReduce for batch jobs, Pregel for graph algorithms. Spark puts them under a single umbrella. A MapReduce job runs on cheap commodity hardware that can crash: The restart. A crash restarts the entire process, which is slow. The disk. Intermediate results are stored and used during a failure. That takes disk space. The memory. Spark stores the results in memory. When a mapper fails, the output before it is resent from memory to a new mapper. The stages. No intermediate results are needed after every map job, so the functions run together in a single computer. Spark focuses only on computation, so the cluster manager is pluggable. An operation is assigned to the computer that has its data in memory.
- What a MapReduce job does
A MapReduce job takes a big data set through many operations, stage by stage, on cheap computers. Apache Spark is from 2009, Berkeley. Before it came MapReduce from Google: mapper jobs and reducer jobs. The example is a recommendation on Amazon from four tables: orders, profiles, products and views. A user saw P1 the day before yesterday and P2 three months ago, and today there is a sale. The job gives each product a probability of purchase. The tables are loaded into different computers. Each is filtered by user name, date and location. The tables are joined. An IP address is mapped into a country. The output is an item wise probability list. The recommendation system takes the top 10. A map operation converts one type of data into another. A reduce operation joins the tables and gets a single number. So much data means things can fail, so the process is managed, and it runs on commodity hardware to stay cheap. Apache Spark is like the open source, in memory version of MapReduce.
- Why MapReduce was slow and what Spark changed
Spark runs the operations of a job together in memory, where MapReduce ran them stage by stage with a store and a transfer after every stage. A common operation joins two tables on one key, such as a hundred GB of orders and 10 GB of profiles on the user profile key. In 2009 this was a big problem. The SQL query ran on the production DB for hours, or on a replica with instances spun up for it. Google built MapReduce, and Apache Hadoop is a MapReduce framework: A job is a pipeline of stages. After every stage the results are stored in an intermediate data store and sent to the next node. The transfers take time, and the chance of a job crashing is proportional to the time it takes. Spark puts operation one and operation two, a join and a filter on the same data, in one step. The engineer writes the steps as a script, and the framework finds the nodes. MapReduce runs with less instance memory. Spark trades memory for speed.
- Rebuilding lost work from memory and when to checkpoint
Spark recovers from a crashed node by asking the nodes it depended on for their results, which are kept in memory. MapReduce keeps intermediate results, so a failure in between is not a problem. Spark keeps most things in memory, and intermediate results would lose that purpose. The job is a directed acyclic graph of nodes: Node 6 crashes. It depended on nodes 1, 2 and 3. A new node 7 is spun up. Nodes 1, 2 and 3 give it their results from memory. The data node 6 held is lost forever, and node 7 computes it again. With multiple failures this becomes slow. A checkpoint pushes data to a disk, and one after every line of code takes a lot of bandwidth. One checkpoint at the end is a single movement to disk, but data lost at the last line means performing all the operations again. Hadoop made sense for jobs hours long, because its intermediate results save recomputing after machine failures. Spark has taken those benefits over.
- One engine in place of many
Spark is one general framework for running computations, with libraries in place of the specialised MapReduce, ML, graph and interactive query engines. A deployment scales to 10 thousand nodes. A SQL query is optimised before it runs: the filter is pushed down, so the filtering is done before the join. Data is shared across computations in memory, and disk is the last resort: Interactive queries. A changed query runs on the old result in memory, a 100x speedup. Fault tolerance. If node 6 fails, nodes 1, 2 and 3 bring it back as node 7 from memory, in parallel, a 40x speedup. Streaming. Events are collected for 200 milliseconds into a micro batch and sent through the same pipeline. Merging the new result with the older result is left to the engineers. An event pushed to Kafka goes through the pipeline already defined in Spark. The operations are reduce, collect and foreach. Foreach is a for loop, collect gathers into a list, and reduce takes an average. Checkpoints for sorting and reduce operations happen in memory.
- An LRU cache of data sets on each node
A Spark node keeps its data sets, the RDDs, in a least recently used cache in memory. A node, S1, has 10 GB of memory and 100 GB of data to bring in. The data is streamed, and the data set being worked on is kept in memory. S1 runs three jobs, J1, J2 and J3, and the memory cannot hold all their data: The disk. Data that does not fit moves to disk and can be pulled from disk. The order. First in, first out keeps J3, the latest job, and moves the RDDs of J1 to disk. Least recently used gives preference to a more active J1. The level. Data is evicted on the level of the data set, not the job. A cache holds DS1 to DS6, which belong to J1, J2 and J3. When DS7 arrives and the memory has run out, the least recently used data set is kicked out. It could be DS5, DS3 or DS2. Recently used data stays in memory the longest, which reduces the number of disk operations.
- Sending the next operation to where the data is
Spark sends the next operation to the node that already holds its data in memory. The cluster manager does not do the placing. It keeps nodes alive, adds nodes and removes nodes. Spark has a management library, which sends operations where they belong: A data set goes to node S1 and the computation completes. The result, RDD2, is in the memory of S1. RDD2 goes through operation 2. S1 has RDD2 in memory, so operation 2 goes to S1, and no bandwidth is used to send results to another server. An add operation on DS1 gives DS2. The next operation is mult on DS2. The map says DS2 exists in S1, so mult is assigned to S1. After a crash a new node is kept in the same rack, else the same availability zone, else the same region. An RDD is a read-only partitioned collection of records. Its preferred locations are a list of nodes, which are tagged. Kubernetes or Mesos is the cluster manager, and ZooKeeper is used for leader election.
Google Dremel
- Google Dremel
Dremel is the interactive analytics system Google built so that a product manager can query petabytes of data in SQL and get an answer in tens of seconds. Before Dremel a query was a MapReduce job, written as code by a software engineer. Every new question meant another job, so a decision waited on engineers. A query runs down a tree: The client fires a query at the query manager. The root sends it to the shards whose key range holds the keys, down through sub shards to the leaves. A leaf holds its data on local disk, with the distributed file store behind it. Each parent aggregates the results of its children, up to the root. Three optimizations keep the latency low: A prefetch cache with a 95% hit rate. Approximate answers, where an exact one is not needed. Columnar storage. The average age is a scan of 3 data points, not 9, and similar data stored together compresses.
- Why Google built Dremel and what it promised
Dremel is the system inside Google BigQuery that lets product managers and CXOs query petabytes of data interactively. Earlier, a query ran as MapReduce on the Google File System and took minutes, hours or days. A product manager asked an engineer to write the job, waited two or three hours for the answer, and waited one more hour to change a filter. Dremel was built to give five things: Interactive analytics. A filter is changed and the answer comes in tens of seconds. Short response times. Trillions of records are scanned in tens of seconds. SQL queries, in 2010, when NoSQL was at its height. Product managers and data analysts are comfortable with SQL. Columnar storage. A table is stored column after column, so a search on the city reads the city column alone. Fast aggregations, a sum or a count, with near linear scalability. More nodes take a higher load and latency stays flat. Borg inspired Kubernetes, the Google File System inspired Hadoop, and Dremel inspired Apache Impala and Apache Parquet.
- What Dremel leaves to MapReduce and what it stands on
Dremel is used by product managers, operations teams, engineers, support teams and analysts, who expect answers in tens of seconds. It is much faster than MapReduce, and the two differ in three more ways: The program. MapReduce runs any kind of program, and it is code. An engineer writes it. An analyst finds it difficult. The data. MapReduce parses unstructured data. Dremel needs structured columnar data. The work. MapReduce is good for joins across tables, such as Google Photos with Google Maps, and a join in code takes any arbitrary condition. Dremel is for aggregation over a column. Dremel depends on Colossus for storage, Jupiter for the network and Borg, the cluster manager. Dremel is not a database in itself. It is an analytics engine. Google keeps storage in Colossus, compute in Borg, configuration in Spanner and the network in Jupiter, and builds new systems on top of these systems. Monarch used Spanner for configuration and Colossus for storage.
- Scatter and gather through a tree of servers
Dremel answers a query by scattering it down a tree of servers and gathering the results back up. Dremel starts with Colossus, the storage, a file store. Clients fire queries as API calls to a query manager, which forwards the query to a root. The root sends the query to all relevant shards. A shard that cannot hold an answer is not picked up. Each shard is a parent node to the nodes under it, through many intermediate layers, down to the leaves. The leaves hold data on a local disk, with a copy in Colossus. Each node aggregates the results of its children and sends them back to its parent. A node that was not used returns zero, the identity of a sum. The local storage is three way replicated: the same data is stored in three nodes. If L3 does not respond, the parent fires the query again at another node with the same data, such as L6. The copies also distribute load. Monarch had something similar: a root node, zones and leaves.
- Slots as the budget of a query
A slot is one thread on one machine, and Dremel estimates the execution of every query in slots. The estimate is a guess: how many machines, into the number of threads those machines have, the query is going to use. A query that pulls 50 thousand data points on threads that each pull 1000 a second needs 50 slots. The client does not ask for slots. The load balancer makes the estimate: A pool. The system has 3000 slots. A query of 2000 slots. It goes ahead. Another query of 2000 slots. Only a thousand are sent, and the query waits. It is slow, or it fails and the client retries, and the system is not overloaded. A node holds several slots. A quad core processor has 4 threads and so 4 slots, an octa core has 8 and a single core has 1. Slots are also what the customer pays for. AWS states how many IO operations a database does per second and charges only for that, and Google charges only for slots.
- A prefetch cache and approximate answers
Dremel keeps a prefetch cache that takes 95% of the hits, and it gives an approximate answer when one is requested. A person's next query is not very different from the last one. It filters on the same data, with a little data added and a little removed. A least recently used cache holds that data, so the first query takes a lot of time and the subsequent queries are quick. An approximate answer is an option for count and top K queries: The top 100 of restaurants ranked 0 to 110. The top 10 and the top 20 are exact, and the tail is sampled from ranks 75 to 110. The top 10 queries of yesterday. The first 8 are accurate, and the others are sampled from ranks 8 to 12. The response is faster because it does not scan all table shards. A query that hits 100 shards has a high chance of a shard failing, and its latency spikes. The election commission asks every person, which takes time. The news channels sample.
- Why a column compresses and where it is decompressed
Dremel stores all values in columnar format, and a column compresses because its values repeat. A table of the numbers 1 to 20 is stored column after column: 1, 6, 11, 16, then 2, 7, 12, 17. A city column holds Mumbai, Mumbai, Delhi, Delhi. At Google scale a value is repeated millions of times across trillions of records. Age runs from 12 to 112, a hundred distinct values, so it is stored as an enum. Compression saves storage. More data is pulled into memory at a time, and it is pulled faster. This is what makes interactive analytics possible. It has costs: A mapping has to be kept. M M D D is stored as 0011. The data has to be ordered. Errors have to be corrected. Compression and decompression both use CPU. Decompression happens on the root. Columnar storage allows queries to be fired on compressed data, so nothing is decompressed before the queries are fired.
- Nested records and run length encoding
Dremel compresses its data, because compressed data gives faster querying and faster retrieval. The data is a JSON document. JSON is a set of key value pairs, and it also has objects. The schema is a document a search engine has picked up: A document has an ID, links and names. Each link is an object with a set of forward links and backward links. A name has a list of languages and a URL string. A language is an object with a string code and a country. These are classes, and inside them are classes, lists and values. Dremel stores this in columns, not as a row. The compression for a column is non zero run length encoding. Values that are the same are clustered together and replaced with a single value. A column of restaurants in Mumbai, Delhi and Chennai is sorted, so each city sits together. Each city gets a value and a frequency: 3 Mumbais, 2 Delhis, 1 Chennai. Six data points store many data points of a column.
- Google Dremel NotesPDF
Google's Authorization Service
- Zanzibar
Zanzibar is Google's authorization system, the one service that decides who can view, edit or own a document. It stores trillions of access control lists and answers millions of queries per second with five nines of availability. More than 99% of the queries are reads. A permission is a relation written in a single line, and a group can stand where a user does. The relations form a graph, and a check spreads out as a tree. It is built like a multilevel cache: The servers. ACL servers keep the most used lists in memory and answer the reads and the writes. The store. Spanner holds the namespace configurations, the relation tuples and a change log. The shards. The data is sharded by object ID, so every relation of a document sits in one shard. The background. A watch service streams the change log to clients, a job creates snapshots, and Leopard uses both to pre-compute user sets.
- What Google asked of one authorization service
Zanzibar is Google's authorization system, one service that decides who can see a photo, a drive link or a document. Hundreds of systems inside Google need authorization, and Google had five goals in mind when building it: A uniform data model and configuration language. If the data model changes, the older systems have to migrate and change their API connections. Causal ordering of actions. Gaurav adds 10 rupees to his account and Zoom deducts 10 rupees from it. The result of the second operation depends on the first one, so the two are ordered. Arpita's account is independent, and a total order would be wasteful. Massive scale. Trillions of access control lists, millions of requests per second and billions of end users. Very low latency. 10 milliseconds is the 95th percentile, so of a hundred people 95 are served within 10 milliseconds. Five nines of availability. The failure rate is the failures over the total, and it is subtracted from hundred percent. Most of the paper talks about the scale.
- Trade-offs come from the product, not from CAP
A trade-off in a real system is chosen from what the product accepts, not from the CAP theorem. Zanzibar cannot let go of consistency, because it needs causal ordering. It cannot let go of availability, because everybody is using it. It cannot let go of partition tolerance, because the system has to be distributed. CAP is for generic systems. What is acceptable in the domain defines how a system is built. A ledger for payments keeps latency, consistency and availability. A person's balance is the complex computation, and it is managed when the day ends. An authorization system may accept a delay in a write request, such as a password change that takes three minutes. Zanzibar is read heavy. Facebook's Memcache was built for 100 read requests to one write request, and Twitter's write heavy copy did not work out. Read heavy is said of the authorization list. A team can keep editing a document, while writes to its authorization list are much lower than the reads.
- Relation tuples, groups and usersets
Zanzibar uses a simple data model and a powerful query language. A relation is written as one line of text, called a tuple: doc:summary-pdf#owner@123. Doc is the namespace, and photo and drive are other namespaces. Summary-pdf is the object ID, owner is the relation and 123 is the user ID. The paper has three relations: owner, editor and viewer. The query language works on sets of users. Set operations. Union, intersection and exclusion. Exclusion removes a set: a photo is visible to the family, except the people who are currently in China. Computed sets. All admins of a group, or all viewers in the engineering group. User sets. The user ID of a tuple can be a group, written as org:engg#member. A new person is added to org engineering once. Every object that gives access to engineers is then accessible to that person. Tuple to userset expands a set into user IDs: 10, 20, 30, 40. These sets can be used in a union or an intersection.
- Why logical clocks fail at thousands of servers
A logical clock is a set of counters, one for each system, that orders related operations without reading the time. Google ensures causal consistency with globally ordered timestamps from Spanner. Local clocks cannot do it. One computer runs slower, another faster, and they fall out of sync. With three systems a logical clock works: System 1 has the first operation. It increments its counter and shares the clock with S2 and S3, which hold 1 0 0. S2 has an operation, and its clock becomes 1 1 0. S3 has an operation concurrently, and its clock becomes 1 0 1. The first operation is proven to happen before the other two, and those two are concurrent. With thousands of servers the array is huge, and every server maintains all of it. Many servers make operations at once, and all of them are concurrent. Only the next state is ordered after them. Most operations stay jumbled, so related operations are not ordered. Logical clocks are accurate with a small number of servers, as in database systems.
- One queue per object for causal order
A queue for each object keeps related operations in order and leaves unrelated ones in queues of their own. A blocking queue gives total ordering: the object behind cannot be accessed before the first object is completed. A priority queue does not give causal ordering. Gaurav adds 10 rupees, a get from a premium account is served first, and it returns the old balance. With total ordering only one server can pick at a time, the one which picked the head of the queue. So the queues are split: A queue for every object. Abhitej's operations go in one queue and Ash's in another, like topics in Kafka. One server for one document. The document ID is hashed and gives a server ID, so every operation on document 1 falls on S2 and is processed in order of arrival. A cost. If S2 goes down, D4 and D1 are not accessible. Google went for globally ordered timestamps from Spanner instead. An atomic clock is necessary only for external consistency. Locally the clocks are always ordered.
- A zookie makes a read fresh enough
A zookie is the timestamp a caller passes to Zanzibar with a read. Causal ordering means one action follows another. Gaurav adds Praveen to a document, and Praveen's access has to come after the add. In the opposite order Praveen gets a failure. Google Spanner orders actions in one line, using globally synchronized clocks. A caller asks it for the next number. Gaurav gets 30, Anubhav gets 31 and Adeeb gets 32. These are globally ordered timestamps. A read carries its timestamp to Zanzibar. Zanzibar holds user 10 for the users in Google, and its latest update is at 31: Gaurav sends 30. The data was updated at 31, so the data is good and Zanzibar returns 10. Anubhav sends 31. The two timestamps match, and Zanzibar returns the response it has. Adeeb sends 32. Zanzibar has older data than Adeeb is asking for, so the data may be stale for him. Zanzibar fetches the latest value for the key from its database.
- Concurrent writes with optimistic concurrency control
Optimistic concurrency control lets two writers change the same group in Zanzibar without a lock: each changes a copy, and the first commit wins. Tuhin adds a member with a zookie of a hundred while Pooja deletes one with a zookie of 50. Zanzibar does not use the zookie to order them. A copy. Each writer copies the user set at version V1 and changes the copy. A commit. Pooja commits first, and the group is at V2. A rejection. Tuhin's change has V1 as its base and V2 is the current version, so Zanzibar rejects it. A retry. Tuhin takes V2, adds member 555 again and commits V3. A lock is the pessimistic choice. An exclusive lock makes every read wait, and the holder can die with it. Zanzibar is highly available and read heavy, so it does not lock. A third writer can commit before the retry, and the retry is rejected again. A copy and a commit take milliseconds, so a change that takes long keeps failing.
- A zookie is a freshness bound, not a timestamp
A zookie is the minimum freshness of data that a caller accepts. It is not the timestamp of the query. Pooja holds a zookie of 50. Data at least as fresh as 50 is okay for her, and data before 50 is not. Tuhin holds a hundred. A zookie is not the time of the request, so the writes at 50 and a hundred cannot be ordered and executed one by one. Zanzibar keeps on every entry the time it was last updated. A table of four keys shows it: Anubhav comes with 10. Three entries are okay and one is too old. Pooja is okay with two entries. Tuhin is okay with one entry. Entries updated on or after the zookie are served. The stale entries are fetched from the database. In a cache, data updated three hours ago is good for a caller that accepts four hours and too old for one that wants two. A fifth row at timestamp 3 is not fetched, because the query touches only the first four rows.
- Watch, check and expand, and why nested groups need an index
Apart from read and write, Zanzibar has three calls, watch, check and expand, and it runs background jobs. Watch. Zanzibar publishes events to all subscribers for a namespace. A person who is out of a company loses all access immediately, because the change is an event. The response contains a zookie. Check. It asks whether a person has access to an object, such as edit access to a video on Drive. It contains a user set, and the set can be nested. Expand. It gives the list of user IDs in a set, such as all the engineers at Google. Three jobs run in the background: periodic snapshots in each namespace, periodic deletion of old snapshots, which is garbage collection, and indexing of large and deeply nested sets. A group may be defined by another group, so evaluating or expanding it takes time. A response is wanted in less than 10 milliseconds for 95% of the time, and a large set of 40 thousand engineers is hard to fetch one by one. Such sets are indexed.
- The serving architecture and why an old answer is acceptable
Zanzibar's architecture is caches, backups and subscribers around one database, Spanner. Clients send requests to the Zanzibar servers. These are access control list servers that expand, write and read, and they work as an in-memory cache of access control. Their database is Spanner. Three things run behind the servers: A data pipeline picks up events from Spanner, and a batch job makes snapshots. A snapshot is a copy of the database taken every hour, so a failure still leaves a backup. An indexing system, called Leopard, caches the sets that are commonly queried, whether deeply nested or large. It reads the snapshots, so indexing does not affect the production database. A watch service streams the changelog to clients that subscribe to events. Leopard subscribes too, and changes its index as data is updated. An index built on snapshots is acceptable because many requests carry no zookie. Zanzibar gives them the data it believes is fresh enough. A caller who wants the latest data sends a zookie.
- How relation tuples are stored and sharded in Spanner
Spanner holds the data Zanzibar needs to decide whether a person is allowed an action: the namespace configurations, the relation tuples and the changelog. A changelog row is keyed by a random shard ID, a timestamp and an update ID. A relation tuple is keyed by five parts: The shard ID. It is usually the object ID hashed into a bucket, and the bucket is a database, so everyone on one document is in one place. The object ID and the relation. This order keeps all the people with edit access on one document together. The user and the commit timestamp. For a very large group, such as a YouTube video that a million people can view, the shard ID is computed on object and user, because the read asks whether one user has access. A small object keeps the object ID, so one query goes to one shard. Inside a shard the rows are sorted on a composite key. Hashing reaches the shard in constant time, and a binary search finds the viewers in logarithmic time.
- Why writes go through Zanzibar
A write goes to Zanzibar and not straight to Spanner because a write here is specific to the application. Spanner is a database. It can manage writes and order them. It has no idea of auth, ACLs or groups, just as it has no idea of orders in an e-commerce system. Zanzibar has the idea. When Abhishek leaves a team, his access is removed in steps: The groups Abhishek is in are found. The documents which belong to those groups are found. These are read operations, an expand and a check. If the reads succeed, the write is done. This is a conditional write, like a mini transaction. If the balance was sufficient, then deduct the balance. The database is too generic for it, so the logic belongs to the server. Logic on the server brings back an old problem. One server deducts a balance and another adds to it, on the same DB. In Zanzibar, one person removes someone from a group and another makes them its chairman. Both cannot be accepted. One has to fail.
- What a write does to the serving cache
A Zanzibar server is a cache over Spanner, and a write to Spanner leaves the cached entry as it is. A middleware that stores its data only in the database is stateless. A Zanzibar server also stores data locally, in a cache, so it holds state. When a write arrives, Spanner is updated. The cache could evict the entry eagerly. The lesson assumes a simple way of operating in which it does not: The write. It flows through to the database. Spanner holds the new entry at 101 and the cache keeps the old entry. The read. A read operation sends a zookie, or names the previous write. The refresh. When a read asks for a value with a greater timestamp than the cached one, the cache updates itself. Write operations never update the cache. Only read operations fetch the latest value, and the freshness value is there for that. Zanzibar is a read heavy system. An order of magnitude is 10 times, and it has a hundred times as many read operations as writes.
- The changelog, snapshots and replicas in Spanner
A snapshot in Zanzibar is Spanner's changelog run again somewhere else, and replication is the work of Spanner, not of the Zanzibar servers. Snapshots are backups, and the backups are used to index the system. A database keeps a log of every change. An instance that crashes looks at its log, and a failed transaction is undone with more operations. The database can be thought of as its log. Keys 1 to 5 hold the values 10, 10, 10, 20, 20. There are two ways to copy them: Send every key value pair. Send the log (add 10 to 1, add 20 to 4, and so on) and repeat the operations in the same order. The result is the same database. The snapshot is made the second way, from the changelogs in Spanner. The five voting replicas are in the USA, in three regions, and use Paxos. The other replicas have no vote and still get the latest values. Replication happens in Spanner. The Zanzibar servers are caches, and a cache evicts old entries.
- Default staleness when no zookie is sent
The default staleness is the freshness Zanzibar picks for a request that carries no zookie. Replication happens in Spanner, and Paxos does not wait for all nodes. Of five servers, three persist a write and the write is safe. 2PC requires all nodes to agree. So the local Spanner can be behind. A request in US West asks for key 1 at a timestamp of a hundred, and the Spanner there holds only 98. Zanzibar reads from another zone, such as US East. An out of zone read takes time. Zanzibar counts these reads. 10% or 20% of all requests leaving the zone is too many. A key whose reads stay in zone is marked safe. Its average staleness, say 300, becomes the default freshness. A request without a zookie gets that default. A key three years old is too old, and Zanzibar fetches it from the database. Confidence intervals and z scores predict whether a read stays in zone. None of this impacts an operation with a zookie.
- A check as a boolean expression
A check is the core call of Zanzibar, and it is evaluated as a boolean expression. The set operations of a check are converted to boolean operations. A query for all users with access to a document breaks into three: the engineers of the company, the admins anywhere in the world, and the public who hold a particular key. The branches are computed in parallel. With AND on all three, one branch that fails means the entire expression fails, so the other branches are cancelled. This is a branch cancellation. The same ACL checks are grouped together. With replicas, a read for 1 can hit node X and a read for 13 can hit node Y, although either node holds both. One query for 1 and 13 hits one replica, so Zanzibar groups the checks to minimize the hits on Spanner. A wide group is expensive to expand. The admins may be the admins of operations, finance, engineering and HR. The expansion is cached in an indexing system called Leopard, which reads off snapshots.
- Sharding by object ID to cut RPC hops
Zanzibar is a distributed cache, and a request is served by making calls between servers and chasing pointers. Take one query: is Adeeb a member of Zoom? One Zanzibar node may not be able to answer it, so it hops from one node to another: The members. One node stores who the members in Zoom are, and they are fetched. The concentric relation. Admins are by default members, as editors of a Google doc already have view access, so the admins are added. The tuple set. All the members and admins are fetched and checked for Adeeb. To minimise RPC calls, the data is sharded by object ID. Zoom is the object and Adeeb is the user, so member, guest and admin in Zoom are kept in one shard. The query now costs one call to reach the shard, plus zero for the admins, plus zero for the tuple set. One user's permissions still hit multiple shards. The usual query asks whether a person has access to a document, so the access pattern matches the object ID.
- Hot keys and collapsed requests
Zanzibar caches the results of hot keys on both the caller and the callee, and collapses identical requests that are in flight into one. A check on the same group repeats its lookups, so the members, the admins and the tuple set are each cached. Cache keys have timestamps in them. The evaluation timestamp, or zookie, is rounded to the next near value, which lets most requests use a cached result. Request collapsing protects the database from a viral key: The first request for a key goes to the database, and the key is stored locally with a dummy value. A later request for that key finds the dummy value and waits. When the first query returns, every waiting caller is answered together. A caller cancels the branches that can no longer change the answer, and the servers delete them from their queues. A second caller collapsed onto a cancelled request is left hanging. So a server keeps a count of the callers interested in a request, and does not cancel while more than one is waiting.
- Request hedging for a slow or failed read
Request hedging sends the same request a second time, so that one slow or failed read does not hold up every caller waiting on it. Request collapsing takes many requests for the same key into a single one, with one future for the key. If that request fails, everyone gets the failure. A request that takes 10 seconds has wasted ten thousand seconds when a thousand requests were waiting on it. So requests are collapsed up to a threshold: Up to 10 users wait on one request. When the 11th user comes in, another entry is created for the same key with a new future. The same database gets two calls with the same key, and either response is accepted. It stays at two calls, because if both fail it is probably a database or a system error. Zanzibar uses request hedging for calls to Leopard and Spanner, not between its own servers. Every region has at least two replicas, so the second request stays in the region. The threshold of delay changes as per traffic patterns.
- Viral posts, rate limits and Zanzibar in numbers
A viral post is a single popular object that may have thousands of checks by different users. Zanzibar is indexed on object ID, so a viral post creates a hot spot. Zanzibar detects popular objects by tracking the reads on an object. If the reads are greater than a threshold, all the relations of this object are cached. When the next user comes, his relation is already cached. Rate limiting works in three places: Each client has a maximum of CPU seconds to be used per second. If the CPU seconds are greater than the threshold, as when Photos asks for a lot of relations, the client is rate limited. Each server has the same logic for outstanding RPCs. Requests to Spanner are rate limited for every client and every object and client pair. Different lock tables are used for different clients, so Spanner does not throttle them all. Zanzibar holds 2 trillion relation tuples in 30 regions and answers 10 million queries per second, 99% of them reads. Callee caches save 12% of the reads.
- Lectures Notes - ZanzibarPDF
Google Borg
- Google Borg
Borg is the system at Google that provides compute and memory for processes and manages each one's life cycle from start to finish. Borg finds the data centers, allocates resources and restarts a process that crashes. 98% of the servers at Google run because of it. A job's priority is monitoring, production, batch or free. A higher priority job preempts a lower one. Production jobs cannot be preempted, which avoids a cascade. A job runs in a Linux container, not a virtual machine. A chroot jail manages security and a cgroup manages resources. A cell is about ten thousand machines under one Borg master, which places a task by a hybrid of best fit and quick assignment. A running task gets a mapping in BNS, the Borg naming service. Chubby stores it in a file with its state and health. The Borg master has five in-memory replicas with re-election using Paxos. If it dies, the Borglets continue functioning. Sending a task where its libraries are installed reduces the start time from 25 seconds to five.
Google Dapper
- Google Dapper
Dapper is the request tracing system at Google: it records the path one request takes from the client to the server and every data store, and how much time it took. A tracing system that slows production is not adopted. Dapper has to be low latency and used by all services, so it is added to the generic client that makes every remote procedure call. A span. Each remote procedure call is a span with an ID, a parent ID and an array of events. A trace. All the spans of one request carry the same trace ID. Collection. Clients write log files to local storage. A background process buffers them. Collectors pull them, convert them into spans and store them in Bigtable, which has an index on the trace ID. Most requests reach Bigtable within 15 seconds. Sampling. IO calls are the bulk of the latency, so production samples one request in a thousand and twenty four. Adaptive sampling. A service with little volume asks for at least 10 samples per second.
Timeseries Databases: Gorilla and Monarch
- Monarch
Monarch is Google's in-memory time series data store for server side metrics. It takes in 6 million data points per second, holds petabytes of data and answers in less than a hundred milliseconds. It has no hard dependency: if Spanner or Colossus goes down, Monarch keeps running. It replaces Borgmon, which each team deployed on its own servers: Petabytes read at any time are kept in memory, which is very expensive. A histogram is stored for every time window, with an example request for each of its windows. Shared timestamps save 90% of timestamp storage, and differential encoding compresses every time series by around 90%. Leaves hold the data, under 30 or 40 zones and one root. A query goes root, zone, leaf, and results are aggregated on the way back. A field hints index of hashed trigrams skips leaves that cannot hold a key. Queries execute 1000 times faster. Data is stored in three leaves. A soft timeout and hedged requests keep a query from waiting on a slow zone or leaf.
- What a time series database needs and stores
What is a time series database? A time series database stores data useful for tracking metrics. Two papers describe such a database: Google Monarch, from 2020, and Facebook Gorilla, from 2015. Each made its own decisions and had its own outcomes. A time series database is used for five things: Metrics tracking. Anomaly detection: whether something is out of range or within range. Predictive analytics, such as how many machines are needed. Dashboards, because some analytics are too complex to predict. Debugging or tracing, a part of observability. Monarch shows that things are going wrong and then the pattern of a particular request. The design of the database is one subject and the features built on top of it are another. Metrics tracking depends on how data points are stored. Both papers mention anomaly detection. Predictive analytics, dashboards and tracing can live in a separate system. Requirements of a time series database Facebook and Google built their own time series databases instead of using OpenTSDB, InfluxDB or Prometheus. Scale is the reason that stands out, and the two share three requirements. Scale. Gorilla's 2015 paper claims tens of millions of data points per second. Run for a day, that goes into terabytes, and the scale had doubled by the time the paper was published. Google stores petabytes. The known solutions are databases on disk, which do not hold up here. Low latency. Metrics are tracked, anomalies detected and requests traced in real time, so queries have to return quickly. Databases on disk do not work out. High availability. A time series database tracks anomalies, and any system it depends on can pass its own anomalies into it. If Monarch depends on Colossus and Colossus goes down, Monarch cannot report the anomaly in Colossus. External dependencies are reduced as far as possible. Both databases take similar approaches and reach similar conclusions, with a few fundamental differences. Data schema of a time series database Both Monarch and Gorilla treat low latency as a very important factor. Three ideas lower latency: a customized data structure, a cache, and operating system hacks of the kind Kafka uses. The lesson takes the data structure. Both databases store a key with a time series as its value. The key reads like a path in a file system: a service, a metric, and more qualifiers for more detail. A time series is a set of timestamps, each with a value. The two differ in the timestamp: Monarch. A timestamp is a bucket, and the buckets are equidistant. Data points that arrive inside a window are rolled into one aggregated value. A key holds a histogram of values. Some value is lost. Gorilla. Every data point keeps its exact time and its exact value. Nothing is rolled up or aggregated. Monarch compresses better: 1000 points in one second become one value. Gorilla allows a deeper dive into the data.
- Persistence, time windows, load balancing and replication
Persistence in a time series database Monarch and Gorilla keep their time series in memory to be fast. To recover after a crash, both persist changes as logs. Each fix creates the next problem: An in-memory node that crashes loses its time series. The changes are persisted. A database suits a store that is queried. This store is only used to reconstruct the in-memory database, so logs are enough. The logs live in a distributed file store, replicated across zones. Monarch uses Colossus, the next generation of the Google file system. Gorilla uses GlusterFS with a replication factor of 3, and its paper says HDFS would have been fine. Logging every event flushes too many metrics to disk. Gorilla holds about 64 kilobytes, roughly one second of data, and then pushes it to the log. A crash in between loses that data. The logs are not perfectly consistent, by choice. Gorilla trades consistency for high throughput. Monarch trades it for availability: if Colossus does not respond, Monarch continues, because Monarch is what reports that Colossus is failing. Tradeoffs: choosing a time window Monarch and Gorilla diverge on one decision: how much data stays in memory. Facebook says its most important time series queries fall in the last 26 hours. Gorilla keeps only 26 hours of data in memory. Everything older goes to a persistent time series database, queried through Hive. That store has high latency and very low cost. Monarch makes no such mention. It stores aggregations, on the reasoning that a fault is usually visible even after data is rolled into a single bucket. The aggregated data is highly compressed and still costs petabytes of memory. Gorilla stays in terabytes. The two assumptions buy different things: Gorilla answers questions about recent data quickly and cannot run a very long time series analysis in memory. Monarch gives metrics and predictive analysis over a much larger series, such as yearly trends, and holds up better against future requirements. The cost of Monarch is about 1000 times the memory, and a much more complex architecture than Gorilla's. Load balancing in Gorilla Gorilla balances load through an external system called a shard manager, which maps ranges of keys to hosts. The key space is cut into ranges: 0 to 500, 500 to 1000, and so on. Range R1 is handled by host 1. A request for key 29 asks the shard manager where to go. Scaling out follows a chain: A new host, H5, enters and the shard manager assigns it a range, R5. Existing ranges shrink. A host that gives away part of its range drains out: data and load leave it. A host that takes a range drains in. H5 cannot serve at once, because its in-memory database is empty. The other hosts drain out only after H5 has drained in, which takes about 5 minutes. A crash is handled the same way. If H2 is lost, the shard manager reassigns R2 to the remaining nodes. They drain in by reading the logs stored in GlusterFS, and then serve requests. High availability needs fault tolerance: an answer for the range whose host has crashed. Replication and fault tolerance in Gorilla Gorilla stays available through a host crash by keeping two copies of everything, at two levels. Two hosts serve the same range. A cluster sits in one data center and holds two independent instances of each host. Every write goes to both, so the logs are duplicated too. No attempt is made to keep the two logs consistent, and the data may differ between them. Several data centers. If an entire cluster goes down, read queries are redirected to a different data center. The data is still served. It takes a little longer, and the data center that takes the load may run hot. These two characteristics make the system highly available. For a very consistent view there is a time series database that stores all the writes, queried through a Hive layer. Gorilla is for fast queries and anomaly detection in real time, with very low latency.
- Monarch's query tree, quotas and indexes
Monarch's architecture Monarch answers a query through a tree: a root mixer, zone mixers under it, and leaves under them. The instances that hold time series are called leaves. A range assigner maps ranges of the key space to leaves. Keys with the same prefix are stored close to each other, so the data for one query is likely to sit in one leaf. Clients do not connect to the range assigner. A query takes this path: It goes to the root mixer, which has a global view. The root mixer sends it to the zones best placed to answer. The other zones are not touched. Each zone mixer picks the leaves in its zone that answer best. The leaves evaluate the query and respond. The zone mixer merges their results, and the root mixer merges the results of the zones. The same range may be stored by several leaves, so the loss of one leaf does not stop a query. The root mixer looks like a single point of failure and a bottleneck. System features of Monarch Monarch protects its tree of mixers in two ways and offers a richer query language than Gorilla. Quota management. A really bad query could ask the root mixer to send back petabytes of data. Every node keeps an in-memory quota: the root mixer, the zone mixers and the leaves. One query cannot take all the resources. Replication. The root mixer is not a single point of failure. There are several root mixers, and several zone mixers that can answer a query. Gorilla's query language is very simple. Monarch supports a group by. One key is aggregated per hour and another per minute. When the result is asked for by the hour, the bucket is created on the fly, and both time series come back with the same one hour blocks: minute 60, minute 120, minute 180. Two series with different bucketing can then be compared. The interpolation hides a gap. A value missing at minute five does not show in the first hour. Query optimization in Monarch A field hints index tells a mixer whether a node can answer a query, as a Bloom filter does. The root mixer does not look at every range a zone handles. It holds an index that says whether a zone can or cannot handle a query. Each zone mixer holds one for its leaves. The index is built from trigrams. A query for the key GKCS is cut into its runs of three characters, with markers for the start and the end. A node that holds every one of those trigrams can potentially answer. Only potentially: a key that repeats three characters also passes. The two databases compared: Gorilla gives extremely fine grained time series, is real time, and has a simple architecture. Monarch aggregates, which shrinks the data and makes patterns easier to find. It runs about 120,000 machines. Storing only 26 hours of data removes the need for root mixers and zone mixers. Both agree on ranges assigned to hosts, an in-memory database backed by a file system, and delta of delta compression.
- Lecture Notes Facebook GorillaDBPDF
Vector Databases
- A hash that puts similar objects close together
A vector is a mathematical representation of an object, chosen so that similar objects get representations that are close to each other. A large language model gets documents, a query and a prompt. All three are context, and the context is converted to a mathematical representation that the model can use. A vector is on the input side of the model. The representation works like a hash: Each object gets a number. An apple is 36, a banana is 56 and a triangle is minus 3073. The fruits are closer to each other. A new object falls near similar ones. An orange is close to 36 and 56. The function is a neural net. The number does not say what is a fruit: a cat may be at 46. A vector has many dimensions. On an animal dimension the banana is at 37 and the cat is far away. The total distance between similar vectors is low, and between dissimilar vectors it is high.
- How a word becomes a token and then a vector
A vector is a 1D array of values for an object, such that similar objects have a low distance and dissimilar objects a high distance. A document was first represented by term frequency: the number of times each term occurs, as a 1D vector. Now a neural network gives the vector. It converts anything into a vector, gibberish included. A word reaches its vector in steps: The token. A word is split into tokens. Eating is split into eat and ing. The ID. Each token has an ID, such as 36 for cat. A number maps to a vector directly. The vector. Each ID is mapped to a 1D array. Its length is fixed for all the tokens, such as 7000 dimensions. Byte pair encoding finds the split. The text is split into characters, and pairs that occur together often are clubbed into one token. So ing and er become tokens. The LLM is a black box. Engineers often store these vectors in a DB.
- The second last layer of a classifier as the vector
The values at the second last layer of a classifier serve as the vector of the object. A classifier classifies an object. Millions of food images go in and four outputs come out: fruit, vegetable, cooked food or something else. Inside are layers of neurons, each connected to the next: The last layer. It gives the probabilities of the four classes and spikes the highest to one. The second last layer. The image has been compressed to its useful features, and the numbers here decide the classification. The values of these neurons, put in a one-dimensional array, are the vector. An image of 100 KB becomes an array of numbers. A cat and a dog share features, so their vectors are similar. A chimpanzee is not a pet, so its vector is not. A classifier of pet or wild keeps the vectors in a 1D space. All animals by type need n dimensions. This is the logic of why vectors work. Word2vec was inspired by it, and more efficient algorithms minimize loss in the representation directly.
- Why checking every vector is too slow
A vector search finds the vectors in a database that are closest to a search vector. Two vectors are compared by Euclidean distance, dot product or cosine distance. A website has a large number of products. A person describes a product in text: cold, sweet and delivered quickly. The text is converted into a single vector, the search query, and the database holds thousands or millions of vectors. A linear scan. The dot product of the search query with each vector is found, the results are sorted, and the lowest 10 distances give the products to recommend. Netflix does the same with the last 10 movies a person has seen. This brute force scan is slow. Ranges, one dimension at a time. A dessert query is asked how sweet it is, then how cold, down to the closest vector. This is the KD tree. A sort on one dimension. A binary search finds the vector closest in sweetness. Its distance in sweetness is zero and the remaining distances are very large, which always happens with multiple dimensions.
- Representatives for clusters of vectors
A clustered index groups the vectors into clusters beforehand, so that a search is compared with one representative of each cluster and not with every vector. The clusters are created before any search arrives, as an offline process, because the embedding space does not change. The example has 14 vectors, and a scan of all of them takes 14 comparisons. With clusters the search runs like this: One vector is picked at random from each cluster as the representative of the whole group. The search vector is compared with all the representatives, and the closest one is chosen. Inside that cluster the search vector is compared with the remaining three vectors. The search takes 5 plus 3, 8 comparisons against the original 14. The savings grow as the clusters grow, and K-means clustering makes the clusters. A cluster of 50 thousand points is split into 50 clusters of a thousand points each, and those into clusters of a hundred. This is similar to an address: country, state, pin code, landmark, and in the end the coordinates.
- When the nearest centroid hides the nearest point
A search that compares only with centroids can enter the wrong cluster while the closest point lies in another one. A cluster can be any shape, and its boundary is a demarcation in the ND space. The mistake happens in this order: An input is compared with the centroids of C1 and C2 only. Comparing with the entire cluster is an order N operation. C1's centroid is close and C2's is far, so the search goes to C1. The nearest point in C1 is 100 meters away. A point in C2 is just 50 meters away, because many points elsewhere in C2 affect its centroid. Vectors that come in later are assigned the same way. The clustered index is fast, and its only problem is accuracy. The vector database builds it in the background and uses it at search time. A relational database searches by sorting in log n. With K clusters there are K decisions at each level, K log n in all. One layer of many clusters avoids the hops at a small scale.
- Top ten results from a clustered index
A clustered index answers a search query with the closest 10 results, and it finds them by brute force inside one cluster. Netflix knows the last 10 movies a user saw and has to find the top 10 related movies. A food app has the last 10 meals. These are the search queries. One query is answered in two steps: The cluster. The DB is split into clusters, and the query goes into the nearest one, found through its representation. The brute force. Every point of the leaf cluster is compared with the query, and the closest 10 are the response. Ten queries become the input in two ways: One vector. The ten vectors are averaged, or one representation is chosen among their clusters. This is approximate. Ten parallel queries. They return a hundred results. The duplicates are removed and the top 10 with the lowest distance are kept. A horror movie and a romcom are not similar. Their average is neither, so running the queries in parallel helps.