content

Question 1

code-deployment Build System – General Overview

Answer 1

we can design our build system as a queue of jobs. each job has a commit identifier (the commit SHA) for what version of the code it should build and the name of the resulting binary that will be created.
A pool of servers (workers) handles these jobs. Each worker takes jobs off the q and writes the resulting binaries to blob storage.

Question 2

code-deployment Build System – how should we NOT design our job q?

Answer 2

A naive design of the job queue is implementing it in memory, but if there’s a failure in the servers that hold this queue, we lose the entire state of our jobs: queued jobs and past jobs.

We’d be unnecessarily complicating matters by trying to optimize around this in-memory type of storage – better off implementing the queue using a SQL db.

Question 3

code-deployment Build System – how should we design our job q?

Answer 3

jobs table in sql db. We can implement the dequeuing mechanism by looking at the oldest created_at timestamp with a QUEUED status. This means that we want to index our table on created_at AND status.

Question 4

code-deployment concurrency

Answer 4

ACID transactions will make it safe for potentially hundreds of workers to grab jobs off the queue without unintentionally running the same job twice

Question 5

code-deployment Build System – how do we handle lost jobs?

Answer 5

Since builds last 15m, it’s likely that a worker dies mid-build and that job remains ‘RUNNING’ forever.

We could have an extra col in our jobs table called last_heartbeat. The worker running that job will update the relevant row every 3-5m to just let us know that it’s still running the job.

We can then have a separate service that polls the table every so often (say, every 5m), checks all of the RUNNING jobs, and if their last_heartbeat was last modified longer than 2 heartbeats ago (need margin of error), then something’s likely wrong, and this service can reset the status of the relevant jobs to QUEUED, which would effectively bring them back to the front of the queue.

Question 6

code-deployment Build System – how do we handle storage?

Answer 6

When a worker completes a build, it can store the binary in GCS before updating the jobs table. This ensures that a binary has been stored before it’s marked as SUCCEEDED.

Since we’ll deploy our binaries to machines spread across the world, we should have regional storage rather than just a single global blob store.

We can design our system based on clusters around the world (in 5-10 global regions). Each region has a blob store (a regional GCS bucket). Once a worker successfully stores a binary in our main blob store, the worker is released and can run another job, while the main blob store performs some asynchronous replication to store the binary in all of the regional GCS buckets.

Question 7

code-deployment Deployment System – General Overview

Answer 7

our deployment system must allow for the very fast distribution of 10GB binaries to hundreds of thousands of machines across the world. We want:
- a service that tells us when a binary has been replicated in all regions
- a service that serves as the source of truth for what binary should currently be run on all machines
- a peer-to-peer-network design for our machines across the world

Question 8

deployment system – Replication-Status Service

Answer 8

We can have a global service that continuously checks that a given binary in the main blob store has been replicated across all regional GCS buckets. Once a binary has been replicated, this service updates a separate SQL db with rows containing the name of a binary and a replication_status. Once a binary has a “complete” replication_status, it’s officially deployable.

Question 9

Deployment System – how do we distribute binaries to machines across the world quickly?

Answer 9

Having each machine download a 10GB file one after the other from a regional blob store is extremely slow. A peer-to-peer-network approach will be much faster and will allow us to hit our 30-minute time frame for deployments.

Question 10

what happens when an engineer hits a button that says “Deploy build/binary B1 to every machine globally”?

Answer 10

We’ll have a K-V store like Etcd or ZooKeeper storing our goal-state, which is the desired build version at that point in time and will look something like: “current_build: B1”. We’ll have a global K-V store and regional K-V stores.

Regional K-V stores will poll the global K-V store (say, every 10s) for updates and will update themselves accordingly.

Machines in each global region will poll the regional K-V store, and when the build_version changes, they’ll try to fetch that build from the P2P network and run the binary.

Question 11

AlgoExpert access control

Answer 11

users who haven’t purchased AlgoExpert can’t access individual questions. We can implement this fairly easily by just making some internal API call whenever a user requests our static API content to figure out if the user owns the product before returning the full content for questions.

Question 12

AlgoExpert – replication

Answer 12

we do need to keep our databases up to date with each other, since users might travel around the world and hit a different database server than their typical one.

For this, we can have some async replication between our database servers.

Question 13

AlgoExpert – code execution

Answer 13

• rate limiting using a K-V Store like Redis to easily prevent DoS attacks
• Since we want 1-3s of latency for running code, we need to keep a set of special servers–our “workers”– ready to run code at all times. They each clean up after running code. Our backend servers can contact a worker and get a response from that worker when it’s done running code (or if the code timed out), and our servers can return that to the UI in the same request.
• logging and monitoring for run-code events to help us scale

This design scales horizontally with our number of users, and it can scale vertically to make running code even faster (more CPU == faster runs).

Question 14

Stockbroker – what happens after a PlaceTrade call is placed?

Answer 14

Once API servers receive a PlaceTrade call, they’ll store the trade in a SQL table. This table needs to be in the same SQL database as the one that the balances table is in, because we’ll need to use ACID transactions to alter both tables in an atomic way.

Question 15

Stockbroker – Trade-Execution Queue

Answer 15

• we use a message queue like Apache Kafka or Google Cloud Pub/Sub
• there is a set of topics that customer IDs map to. When a user makes a trade, the API server writes a row to the database and also creates a message that gets routed to that user’s topic. (this guarantees: 1. at-least-once delivery semantics (trades are never missed) 2. only 1 worker trying to execute a trade
• each topic’s subscriber is a cluster of worker servers. we use leader election for high availability. the leader executes the trade by contacting the exchange.

Question 16

Stockbroker – Trade-Execution Logic

Answer 16

worker server queries db and then talks to the exchange. the exchange issues a callback to a separate server that writes updates the trades and balances tables

Question 17

FB news feed – what happens when a CreatePost API call is placed?

Answer 17

the API call goes through some load balancing before landing on 1 of many API servers (which are stateless, meaning they don’t keep track of which clients access them). Those API servers then create a message on a Pub/Sub topic. Each shard – that stores the pre-generated feeds – subs to its own topic.

When a subber gets a msg about a new post, it searches the main db for all of the post creator’s friends.

When celeb users post, we can cap the number of topics that get messaged. For those users, we can let the post appear in feeds of users when the feeds get refreshed manually.

Question 18

FB news feed – feed creation

Answer 18

we can store news feeds separately from our main db, across many shards. We can have a separate cluster of machines in charge of aggregating posts, ranking them via some ranking algo, generating news feeds, and sending them to our shards every so often (every 5, 10, 60m?).

Question 19

FB news feed – cross-region strategy

Answer 19

When CreatePost gets called and reaches our Pub/Sub subbers, they’ll send a msg to another Pub/Sub topic that some Forwarder Service in between regions subs to. Once the Forwarder receives the msg, it’ll fwd the msg to other regions, which starts the feed-update logic in those regions. We can have some additional logic passed to the forwarder to prevent the other regions from notifying other regions about the CreatePost call in question, which would lead to an infinite chain of replications; in other words, we can make it such that only the region where the post originated from is in charge of notifying other regions.

Question 20

G Drive – storing file data

Answer 20

When uploading a file, the request will be load balanced across multiple “blob splitter” servers, and these blob splitters have the job of splitting files into blobs and storing these blobs in GCS.
- we need a lot of redundancy to prevent data loss – push to 3 different GCS buckets (each in a diff region) and consider a write successful only if it went through in at least 2 buckets.

Question 21

Content-Addressable Storage

Answer 21

• a way to store info so it can be retrieved based on its content, not its name or location.

In order to avoid having multiple identical blobs stored in our blob stores, we’ll name the blobs after a hash of their content. This technique is called CAS; by using it, we make all blobs immutable in storage.

Question 22

G Drive Garbage Collection

Answer 22

Any change to a file will create a whole new blob and de-reference the old one. Any deleted file will also de-reference the file’s blobs. So we’ll end up with a lot of unused, orphaned blobs taking up storage for no reason.

Our GC service watches the entity-metadata K-V stores and keeps counts of the number of times every blob is referenced by files; these counts go in a SQL table.

Reference counts get updated whenever files are uploaded / deleted. When the reference count for a particular blob reaches 0, GC marks the blob as orphaned in the relevant blob stores, and the blob will be safely deleted after some time.

Question 23

how do we deliver Netflix’s video content across the globe with little latency?

Answer 23

50 TB/s of bandwidth consumption means we can’t serve content out of a single data center or even dozens of data centers. We need many 1000s of locations around the world. Use CDNs: they have many 1000s of Points of Presence around the world. We can use a CDN like Cloudflare and serve our video content out of the CDN’s PoPs.
- Since the PoPs can’t keep ALL content in cache, we can have an external service that periodically repopulates CDN PoPs with the movies and shows most likely to be watched.

Question 24

Netflix’s recommendation engine

Answer 24

we must process vast amounts of user-activity data to feed into this engine. user-activity data will be gathered in the form of logs.

We can store the logs in a distributed file system like HDFS and run MapReduce jobs to process these logs in parallel. The results of these jobs can be fed into ML pipelines or stored in a db.

Question 25

Tinder pics

Answer 25

pics are at most 2MB ea. We’ll want to reduce the dimensions of pictures, since they’ll only be viewable on small mobile screens. We’ll perform lossy compression on them - we can afford to lose a bit of quality. this brings pics down to ~50KB ea

Question 26

Tinder deck generation

Answer 26

a smart deck-gen algo continuously generates decks of 200 profiles for each user every day, stored in SQL table. This ensures that decks are as relevant as possible when users interact with them.
smart:
- doesn’t generate decks for users inactive for more than a day
- re-generates decks for users who’ve just changed location

• On app load, the app requests the 40 profiles at the top of the deck and locally stores them.
• To ensure users never feel like they’ve run out of ppl, the app fetches 20 more profiles when the user has 20 locally stored profiles left.

Question 27

Tinder swiping

Answer 27

On app load, the app fetches all rows in the swipes table where swipeeId == userId. Then, every 30s, it’ll fetch new swipes.

The app keeps all swipes in memory, in a HT-like structure, meaning that for any profile, the app can know right away if they’ve already swiped on it.

When a user swipes, the app writes the swipe to the swipes table. If the swipe is a LIKE, the backend will check for a matching swipe, and if there is one, it’ll write a match to the matches table.

Question 28

Tinder undo

Answer 28

The Undo feature can be implemented by simply delaying the API calls that occur on a left swipe until the next swipe. This avoids doing multiple writes to the swipes table.

Question 29

Slack – how do we support real-time behavior?

Answer 29

2 “types”:
1. sending, receiving msgs in real time
2. cross-device sync (marking channels as read)

Each org is assigned to a Kafka topic. When user sends a msg or reads a channel, our API servers, which handle speaking to our db, will also send a Pub/Sub msg (containing “type”) to the right topic.

1 API server cluster (diff set) subs to each topic. Clients (Slack users) establish long-lived TCP connections w/ these API server clusters to receive msgs from them.

Question 30

Airbnb – how does our quadtree solution work?

Answer 30

“Geo index” machines refer to the machines that store the quadtree in memory.

When our system boots up, the GI machines create the quadtree by querying the SQL listings table. When listings are created or deleted, changes are first written to the SQL table, and then the leader GI machine gets the update. Then, every 10m, the geo-index leader and followers all recreate the quadtree from the SQL table, which allows them to stay up to date with new listings.

Question 31

Airbnb Display Listings

Answer 31

DisplayListings api call searches thru geo-index leader’s quadtree for relevant listings based on the location that the renter passes.
- each listing in the quadtree contains a list of unavailable date ranges; we perform binary search on this list to see if the listing is available during the renter’s date range.
- pagination using an offset

Question 32

Airbnb get a specific listing

Answer 32

This API call is simple. We can have listing IDs from the list of listings that a renter is browsing through, and we can simply query our SQL table of listings for the given ID.

Question 33

Airbnb making a reservation

Answer 33

Reserved listings must be reflected both in our quadtree and in our SQL tables. They must be excluded from the list of browsable listings.

When a renter tries to start the booking process, the rsrvation table will first be checked to see if there’s currently a res for the listing during the renter’s date range; if there is, an error is returned; if not, a res is made with an exp timestamp 15m into the future.

Following the write to the res table, we update the geo-index leader’s quadtree with the new res (adding the res dates to the list of unavailabilities).