bases.md

Thinking Framework

1. User Journey
2. Systems Core Features (Functional Requirements)
3. Qualities of System (Non Functional Requirements): a. Expected Load b. Load change over time c. R/W Data Access Patterns, based off 2. c. CAP tradeoffs, everytime new functional req. e. Fault Tolerance, Idempotency, Replication, Sharding
4. Core Entities and Relationships (Rails ActiveRecord, nearest to uml)
5. API or Interface
6. High Level Design, to satisfy FR
7. Deep dives, to satisy non-FR

Tips

General Tips:

• Consider latency
• Reduce cardinality
• Always start from the simplest system, and then consider the non-FR at each component
• Know some real life numbers by head

General Numbers:

• 1K = 10 * 100 = 10^3 (ms)
• 1M = 10 * 100K = 1K * 1K = 10^6 (us)
• 1G/B = 10 * 100M = 1K * 1M = 10^9 (ns)
• 1T = 10 * 100G/B = 1K * 1B = 10^12 (ps)
• quadrillion = 10^15
• quintillion = 10^18

Powers of 2 (every 10 bits ≈ 1000, since 2^10 = 1024 ≈ 10^3):

• 2^10 ≈ thousand = 10^3
• 2^20 ≈ million = 10^6
• 2^30 ≈ billion = 10^9
• 2^40 ≈ trillion = 10^12
• 2^50 ≈ quadrillion = 10^15
• 2^60 ≈ quintillion = 10^18
• 2^64 ≈ 16 × 2^60 ≈ 16 quintillion

Formula:

2^P = 10^Q

P(i) = 10*X(i)
Q(i) = 3*Y(i)

X(i) = 0.3*Y(i)


Ex:

2^20
= 10^(0.3*20)
= 10^6


10^9
= 2^(9/0.3)
= 2^30

Metals:

• CPU Cache: 1ns
• L2 Cache: 4ns
• RAM: 100ns
• NvMe SSD: 100us
• Network flatency (same region): 0.3ms - 1ms
• Cross Region: 50ms - 150ms (100x slower than same)

Real life base metric:

• Single server
• App + DB
• 5 ms app processing
• 1 ms local DB query
• 0.5 ms network overhead

Total ≈ 6–10 ms P50

Mental Math

QPS -> Latency

Formula: Rps = Cores / Each action time

Example:

1 core cpu, 1 request takes 100ms

Rps = 1 / 0.1s = 10 rps

---

Bandwith Estimation:

Formula: Bandwith = Payload Size * QPS

1KB payload, 1K rps/qps, Bandwith = 1MB/s

---

Queue Throughputs

Formula is Little's Law

L = Rps * Avg Latency, where is total concurrent supported

1K Rps, 200ms Latency, L = 1K * 0.2s = 200 concurrent capacity

If you want to process 100K Rps, avg latency 2ms, needs 200cpu cores.

Examples

• url shortner

framework.svg

hld.svg

leetcode.md

Leetcode Competitons

Questions

• What kinds of competitions, which fields? (DSA, SQL?)
• Are these competitions long running?
• What are the business objectives? - only ranking? or companies can organise?
• How are the tie-breaks/performance measured? (features: time taken, attempts, partial correct?)
• How man competitions daily/monthly?
• Expected participation per competitions? Limits on seats available per competition?
• How will penalties work
• If competition is cross regional, how much would be the minumum time frame to start a competition? (depends on the lowest latency in different regions or replication lag)

FR

• Create competitions: set answers, test cases, features to track and score multipliers, penalties, start/end dates, rewards
• User registers
• Register for competitions, get notified
• Browse questions, submit solutions, execute (dry-run/test cases), view scores
• See rankings (live and final)
• Set rewards
• See submissions by participating people once competition is done
• Use as practice competition after competition is done (if organiser allows it)

Components:

• Metadata Service (for competition, and problems)

• User / Auth (competitors, organisers, admins)

• Infra Config / Policies

• Code Runners

• Timer Module

• Submissions and Plagarism, metadata valiadtions

• Scorer & Ranker

• Notification / Event Bus

• Blob Store (test cases)

Non FR

(Assuming that competitor organisers have been given a time frame, so anyone can start a competition at any time, and competition then can have a fixed duration)

Competition Metadata Service & Blob Store

handles:

• creating and scheduling competition

• rules, scorings, problems, test cases

• P: Ensure same rules and config for competitions (C > A)

• E: Ensure updated data, (C > L)

• Fairness

Submissions:

handles:

• receives submissions for problem.

• submitted versions

• config rules validations like expired or not (signals ranking is needed or not)

• logs

• Ties with code runner cluster, but prefer C > A

Code Runners:

handles:

• runing user code

• sandbox, time and memory limits and networking configs

• emit usage and success/failure metrics agains tes cases

• Prefer availaility to be able execute code, Availability can be ensured by having multi cluster and sandboxing competition cluster to reduce impact

• Could be multi cluster depending on type of competition and test case running we could set different set of policies

• Injects and Emits metrics for scoring (runtime, memory, submission, success/failure rate)

• Constrainted resources and sandboxing for execution

Failures:

• Client to Server connection lost:

  • Keep a local timer, and accumulate changes in the client. Sync to server

• Code runner cluster fails:

  • Region is failing: redirect to a different cluster in region
  • To ensure fairness: we need to reward with delta time, for the network trip required and re-scheduling.
  • Ensure a max cap on resources(cpu/memory/timeouts) to prevent resource hogging.

Su In order to compensate for time lost in

Scoring & Ranking:

handles:

• ingestion of code running events/metrics
• apply scoring based on rules set
• show the rank

Live vs Final Rankings:

• Live, prefer A > C .. if some node goes down, stops processing its okay. it can come back online when updated (convey this with colors)
  • SLO, SLA
• Final C > A .. even caches must be cleared on all cdns.
  • SLO, SLA:

local_delivery.md

Local Delivery Service

Deliver goods typically found in a convenience store via rapid delivery and 500+ micro distribution centers (DCs).

Questions

• specific to country/continent or worldwide?
• DC's managed by whom?
• SLA of delivery based on radius?
• Radius? static or area basis?
• operating times? what happens during large scale events/riots etc.
• User base, Items ? Region specific items?
• How do you confirm order delivered?
• Order completion: single order, club orders?
• How does payouts happen?
• Order cancellation time window, Returns
• Price of items, how numbers to round off?

FR

• User logs in, and see's items available in stores near 10km radiius

• Depending on weather delivery can be now or schedule for later

• Adds items to cart, wishlist(later or notify)

• Places order, amount, coupouns and discount

• Completes paynment, sees delivery time, order/driver status

• Driver registers, complete self and vehicle kyc. Gets accepted/rejected

• Driver can log-in, set active/inactive.

• Gets order requests broadcasted, accepts 1 or multiple

• Can move between locations

• Sees earnings, payouts, heatmaps for traffic congestions, weather alerts etc.

• Uploads photo or PIN to confirm delivery.

• Store Management tracks inventory

• Tracks order info (items, order, driver, status)

• Batch updates every X interval

• Recon Jobs validate earnings and inventory and delivery success/failures every Y intervals

• Payout service records transactions, money received, money to be sent to drivers, cancellations, returns, lost or failed orders.

• Adds new DC to network/mesh.

Non FR

• A:
  • Users should able to list items and place orders (99.99?) of the time.
  • Drivers should be able to move to locations if some area has problems
• C:
  • Inventory deduction must be atomic to prevent overselling
  • Inventory listing can have slight delays, No double chargi
  • Rider assignment must be atomic, but can be delayed within the order delivery SLA (15-30mints)
  • Order status tracking can be approximate but should never go back.
  • Order creation should be idempotent, no double ordering or double payments.
• L:
  • Browse Items (p95 < 200ms),
  • Order creation (p95 < 500ms),
  • Order Broadcast (p95 < 500ms),
  • Driver Assignment (2s-2mintues)
• S:
  • Should be able to handle adding DC,
  • Dyamically scale up and down based on spikes or long low demand.
  • 100K orders a day per region maybe a total of 1-10million globally,
  • 1-100 million users,
  • 100K-1million drivers
  • Notifications: 4xorders = 4-40M to users (for order states) + 100K orders per region * 1 million drivers ~ 100-200Billion
• Reliability:
  • Outages must be contained withing a region,
  • Item locks, orders should be recoverable,
  • Payments should have different modes and multiple gateways,
  • Orders once processed, must be delivered. If delvery fails must be refunded
  • Prevent over-selling and handle HOT items.
  • System performanc must be traceable and alertable, Handling hammering the system in case of failed systems.
• Safety:
  • Trace payments and orders for audits
  • Dont expose users card or addresses
  • Donot overcharge

Outline

Components:

• Registration/Login (User and Driver Management)
• Authentication, Blocking/BadUserDriver
• Catalogue/Inventory Management
• Order Mangement (Order auto delegation)
• Store Management
• Payments
• Discounting & Coupons
• Recon Jobs
• Notifications

thinking.md

Delivery Framework

(This is from hello interview,)

The best way to structure your system design interviews to structure your thoughts and focus on the most important aspects, built by FAANG managers and staff engineers.

---

The easiest way to sabotage your chances of getting an offer in your system design interview is to fail to deliver a working system. This is the most common reason that mid-level candidates fail these interviews and it often manifests as the opaque "time management". This issue isn't (always) that you need to work twice as fast — many times you just need to focus on the right things.

Overall Structure

Our delivery framework is a sequence of steps and timings we recommend for your interview. By structuring your interview in this way, you'll stay focused on the bits that are most important to your interviewer. An added benefit is that you'll have a clear path to fall back if you're overwhelmed. Many candidates are (understandably!) nervous in their interview. It's easy to get lost if you aren't building up a solution in a linear way.

While a firm structure to your approach is important and your interviewer is not trained specifically to assess you on your delivery (often this gets bucketed into "communication"), in practice we've seen many candidates that perform significantly better by following a structure which both keeps them from getting stuck and ensures they deliver a working system.

Here's the framework! ![[framework.svg]]

Recommended system design interview structure

Requirements (~5 minutes)

The goal of the requirements section is to get a clear understanding of the system that you are being asked to design. To do this, we suggest you break your requirements into two sections.

1) Functional Requirements

Functional requirements are your "Users/Clients should be able to..." statements. These are the core features of your system and should be the first thing you discuss with your interviewer. Oftentimes this is a back and forth with your interviewer. Ask targeted questions as if you were talking to a client, customer, or product manager ("does the system need to do X?", "what would happen if Y?") to arrive at a prioritized list of core features.

For example, if you were designing a system like Twitter, you might have the following functional requirements:

• Users should be able to post tweets
• Users should be able to follow other users
• Users should be able to see tweets from users they follow

A cache meanwhile might have requirements like:

• Clients should be able to insert items
• Clients should be able to set expirations
• Clients should be able to read items

Keep your requirements targeted! The main objective in the remaining part of the interview is to develop a system that meets the requirements you've identified -- so it's crucial to be strategic in your prioritization. Many of these systems have hundreds of features, but it's your job to identify and prioritize the top 3. Having a long list of requirements will hurt you more than it will help you and many top FAANGs directly evaluate you on your ability to focus on what matters.

2) Non-functional Requirements

Non-functional requirements are statements about the system qualities that are important to your users. These can be phrased as "The system should be able to..." or "The system should be..." statements.

For example, if you were designing a system like Twitter, you might have the following non-functional requirements:

• The system should be highly available, prioritizing availability over consistency
• The system should be able to scale to support 100M+ DAU (Daily Active Users)
• The system should be low latency, rendering feeds in under 200ms

It's important that non-functional requirements are put in the context of the system and, where possible, are quantified. For example, "the system should be low latency" is obvious and not very meaningful—nearly all systems should be low latency. "The system should have low latency search, < 500ms," is much more useful as it identifies the part of the system that most needs to be low latency and provides a target.

Coming up with non-functional requirements can be challenging, especially if you're not familiar with the domain. Here is a checklist of things to consider that might help you identify the most important non-functional requirements for your system. You'll want to identify the top 3-5 that are most relevant to your system.

1. CAP Theorem: Should your system prioritize consistency or availability? Note, partition tolerance is a given in distributed systems.
2. Environment Constraints: Are there any constraints on the environment in which your system will run? For example, are you running on a mobile device with limited battery life? Running on devices with limited memory or limited bandwidth (e.g. streaming video on 3G)?
3. Scalability: All systems need to scale, but does this system have unique scaling requirements? For example, does it have bursty traffic at a specific time of day? Are there events, like holidays, that will cause a significant increase in traffic? Also consider the read vs write ratio here. Does your system need to scale reads or writes more?
4. Latency: How quickly does the system need to respond to user requests? Specifically consider any requests that require meaningful computation. For example, low latency search when designing Yelp.
5. Durability: How important is it that the data in your system is not lost? For example, a social network might be able to tolerate some data loss, but a banking system cannot.
6. Security: How secure does the system need to be? Consider data protection, access control, and compliance with regulations.
7. Fault Tolerance: How well does the system need to handle failures? Consider redundancy, failover, and recovery mechanisms.
8. Compliance: Are there legal or regulatory requirements the system needs to meet? Consider industry standards, data protection laws, and other regulations.

3) Capacity Estimation

Many guides you've read will suggest doing back-of-the-envelope calculations at this stage. We believe this is often unnecessary. Instead, perform calculations only if they will directly influence your design. In most scenarios, you're dealing with a large, distributed system – and it's reasonable to assume as much. Many candidates will calculate storage, DAU, and QPS, only to conclude, "ok, so it's a lot. Got it." As interviewers, we gain nothing from this except that you can perform basic arithmetic.

Our suggestion is to explain to the interviewer that you would like to skip on estimations upfront and that you will do math while designing when/if necessary. When would it be necessary? Imagine you are designing a TopK system for trending topics in FB posts. You would want to estimate the number of topics you would expect to see, as this will influence whether you can use a single instance of a data structure like a min-heap or if you need to shard it across multiple instances, which will have a big impact on your design.

Regardless of how you end up using it in the interview, learning to estimate relevant quantities quickly will help you quickly reason through design trade-offs in your design. Don't worry if you're not good at mental arithmetic under pressure, most people aren't.

Core Entities (~2 minutes)

Next you should take a moment to identify and list the core entities of your system. This helps you to define terms, understand the data central to your design, and gives you a foundation to build on. These are the core entities that your API will exchange and that your system will persist in a Data Model. In the actual interview, this is as simple as jotting down a bulleted list and explaining this is your first draft to the interviewer.

Why not list the entire data model at this point? Because you don't know what you don't know. As you design your system, you'll discover new entities and relationships that you didn't anticipate. By starting with a small list, you can quickly iterate and add to it as you go. Once you get into the high level design and have a clearer sense of exactly what state needs to update upon each request you can start to build out the list of relevant columns/fields for each entity.

For our Twitter example, our core entities are rather simple:

• User
• Tweet
• Follow

A couple useful questions to ask yourself to help identify core entities:

• Who are the actors in the system? Are they overlapping?
• What are the nouns or resources necessary to satisfy the functional requirements?

Aim to choose good names for your entities. While most problems are small enough that you could probably sub in foo and bar for any entity in your system, some interviewers use this as an opportunity to see whether you're any good at one of the hardest problems in computer science.

API or System Interface (~5 minutes)

Before you get into the high-level design, you'll want to define the contract between your system and its users. Oftentimes, especially for full product style interviews, this maps directly to the functional requirements you've already identified (but not always!). You will use this contract to guide your high-level design and to ensure that you're meeting the requirements you've identified.

You have a quick decision to make here -- which API protocol should you use?

REST (Representational State Transfer): Uses HTTP verbs (GET, POST, PUT, DELETE) to perform CRUD operations on resources. This should be your default choice for most interviews.

GraphQL: Allows clients to specify exactly what data they want to receive, avoiding over-fetching and under-fetching. Choose this when you have diverse clients with different data needs.

RPC (Remote Procedure Call): Action-oriented protocol (like gRPC) that's faster than REST for service-to-service communication. Use for internal APIs when performance is critical.

Don't overthink this. Default to REST unless you have a specific reason not to. For real-time features, you'll also need WebSockets or Server-Sent Events, but design your core API first.

For Twitter, we would choose REST and design our endpoints using our core entities as resources. Resources should be plural nouns that represent things in your system:

POST /v1/tweets
body: {
  "text": string
}

GET /v1/tweets/{tweetId} -> Tweet

POST /v1/follows
body: {
  "followee_id": string
}

GET /v1/feed -> Tweet[]

Notice how we use plural resource names (tweets, not tweet). The current user is derived from the authentication token in the request header, not from request bodies or path parameters.

Never rely on sensitive information like user IDs from request bodies when they should come from authentication. Always authenticate requests and derive the current user from the auth token, not from user input.

[Optional] Data Flow (~5 minutes)

For some backend systems, especially data-processing systems, it can be helpful to describe the high level sequence of actions or processes that the system performs on the inputs to produce the desired outputs. If your system doesn't involve a long sequence of actions, skip this!

We usually define the data flow via a simple list. You'll use this flow to inform your high-level design in the next section.

For a web crawler, this might look like:

1. Fetch seed URLs
2. Parse HTML
3. Extract URLs
4. Store data
5. Repeat

High Level Design (~10-15 minutes)

Now that you have a clear understanding of the requirements, entities, and API of your system, you can start to design the high-level architecture. This consists of drawing boxes and arrows to represent the different components of your system and how they interact. Components are basic building blocks like servers, databases, caches, etc. This can be done either in person on a whiteboard or virtually using whiteboarding software like Excalidraw. The Key Technologies section will give you a good sense of the most common components you'll need to know.

Ask your recruiter what software you'll be using for your interview and practice with it ahead of time. You don't want to be fumbling with the software during your interview.

Don't over think this! Your primary goal is to design an architecture that satisfies the API you've designed and, thus, the requirements you've identified. In most cases, you can even go one-by-one through your API endpoints and build up your design sequentially to satisfy each one.

Stay focused! It's incredibly common for candidates to start layering on complexity too early, resulting in them never arriving at a complete solution. Focus on a relatively simple design that meets the core functional requirements, and then layer on complexity to satisfy the non-functional requirements in your deep dives section. It's natural to identify areas where you can add complexity, like caches or message queues, while in the high-level design. We encourage you to note these areas with a simple verbal callout and written note, and then move on.

As you're drawing your design, you should be talking through your thought process with your interviewer. Be explicit about how data flows through the system and what state (either in databases, caches, message queues, etc.) changes with each request, starting from API requests and ending with the response. When your request reaches your database or persistence layer, it's a great time to start documenting the relevant columns/fields for each entity. You can do this directly next to your database visually. This helps keep it close to the relevant components and makes it easy to evolve as you iterate on your design. No need to worry too much about types here, your interviewer can infer and they'll only slow you down.

Don't waste your time documenting every column/field in your schema. For example, your interviewer knows that a User table has a name, email, and password hash so you don't need to write these down. Instead, focus on the columns/fields that are particularly relevant to your design.

For our simple Twitter example, here is how you might build up your design, one endpoint at a time:

![[hld.svg]]

Deep Dives (~10 minutes)

Astute readers probably noticed that our simple, high-level design of Twitter is going to be woefully inefficient when it comes to fetching users' feeds. No problem! That's exactly the sort of thing you'll iterate on in the deep dives section. Now that you have a high-level design in place you're going to use the remaining 10 or so minutes of the interview to harden your design by:

• Ensuring it meets all of your non-functional requirements
• Addressing edge cases
• Identifying and addressing issues and bottlenecks
• Improving the design based on probes from your interviewer.

The degree to which you're proactive in leading deep dives is a function of your seniority. More junior candidates can expect the interviewer to jump in here and point out places where the design could be improved. More senior candidates should be able to identify these places themselves and lead the discussion.

So for example, one of our non-functional requirements for Twitter was that our system needs to scale to >100M DAU. We could then lead a discussion oriented around horizontal scaling, the introduction of caches, and database sharding -- updating our design as we go. Another was that feeds need to be fetched with low latency. In the case of Twitter, this is actually the most interesting problem. We'd lead a discussion about fanout-on-read vs fanout-on-write and the use of caches.

A common mistake candidates make is that they try to talk over their interviewer here. There is a lot to talk about, sure, and for senior candidates being proactive is important, however, it's a balance. Make sure you give your interviewer room to ask questions and probe your design. Chances are they have specific signals they want to get from you and you're going to miss it if you're too busy talking. Plus, you'll hurt your evaluation on communication and collaboration.

url_shortner.md

URL Shortner

questions

• how many read/writes?
• latency?

read: p50: 10ms p99: 50ms

write: p50: 50-80ms p99: 100-200ms

Function R

1. Create short url from long url
2. User visits a short url -> redirected to original url
3. Authenticated Users can have custom url, with saying custom meta:og urls
4. Expiriy
5. Check stats
6. Custom URL

Non-FR

1. User always see's their own result (SC)
2. Rest can be EC.
3. Hot short links (single flight and caching because of thundering heard)
4. dont reuse ids, because ids are cached so, propagating those changes might be a hassle we dont deal with rn.

Outline

• Resource (id, resource_type, email, hpass, created_at, blocked)
• URL (short_url, allocated, created_at, reserved_at)
• ResourceURL(resource_id, short_url, long_url, created_at, expires_at)

Flow

Write

flowchart LR
  Client -- Checks duplicates and domain exists, blacvklists --> API 
  API -- Generate unique short urls --> KeyGenerate
  KeyGenerate -- Return ID --> API
  API -- save to database --> DB

Loading

Read

flowchart LR
  Client -- Enters short URL --> API
  API -- Check in DB (maybe add cache) --> DB
  API -- 302 --> Redirect

Loading

Key Generation

1. readable
2. short (8-9)
3. url SAfe
4. collision rare

Writers

• TPS: 1M/sec

• Workers: 10, Growth 10x

• Worker/Shard Bits: log2(10) ~ log2(100) ~ 7bits

• 100k WPS Per worker = 100 wpms = log2(100) bits = 7bits

• Bust: 10x = 1000 wpms

• Seq Bits: log2(100) ~ log2(1000) ~ 10bits (3/0.3)

Using 64 bits we get 2^64 ~ 10^18 unique ids.

• Domain name, ping check.
• Malicious URLs:
  • Bloom Filters for knowns
  • Basic checks: ssl certs
  • Trustability of domains

Perf Analysis:

URL Record in DB: 200B 1M = 200MB/s Bandwidth

DB Write + index + wal = 5IOPS (assuming) 1M wps, 3shards = 333K writes per shard, 333*5 ~ 1.6M IOPS.

Write Pattern:

• append-only
• no updates
• no range scans needed

Discussions:

• Ebs: not possible.
• NVME: local attached storage to EC2 or something
• Postgres: Pros: Easy to maintain with strucutre, SC, Good for reads (range scans) because of b+ trees. Cons: VACCUM, single threaded bgwriter, Write and Updates/Deletes are costly because of tombstones and compaction seperately from WAL.
• RocksDB-esque: Pros: Faster writes, different flavours, like yugabytes, distributed natively by design, WAL and tombstones are compacted, sorted sets make write sequential, Bloom filters come in built. Cons: hash based keys bad for range queries, tuning compaction uintervals.

In either case, EBS wont support, this kind of scale, native local nvme's are better.

Another option is to use dynamodb, which promises ms latency on writes and reads, managed by AWS, causing vendor lock-in. Deletions and compaction intervals need to be managed.

Fault Tolerance:

• Database Crashes:

  • Have replication: out of 3, 1 master, 1 local sync replication, and 1 in different az
  • Shard the database, 10-100 nodes
  • Crash at WAL -> SST (recover uysing WAL)
  • SST -> Disk fail?
  • Leader election raft recovery stuff

• KeyGenerator Crashes:

  • We would loose a bunch of keys, for the timeperiod it was down
  • Respawn a new generator instance.
  • Have a backfill service, which can be used to create new ids until the thing catches up with present time.

• Compaction

Reader

• TPS: 10M/s