System Architecture Flashcards
(46 cards)
1
Q
Load Balancing
A
Static:
- Round robin
- Weighted round robin
- IP hash
Dynamic:
- Least connections
- Weighted least connections (assign different weights to each server)
- Weighted response time
- Resource-based (CPU, memory)
Global server load balancing (CDN)
2
Q
Estimate set membership
A
Bloom filter
- Elements are added to the filter by hashing them multiple times and setting the bits at the resulting indices in a bit array.
- To check if an element is present, it’s hashed in the same way, and all corresponding bits in the array are checked.
- If all the checked bits are set, the element might be in the set (potential false positive); if any bit is not set, the element is definitely not in the set (no false negatives).
3
Q
Estimate set cardinality
A
HyperLogLog
- HyperLogLog estimates the number of unique elements in a dataset by observing the longest run of leading zeros in the binary representation of hashed elements.
- It uses multiple independent hash functions and divides the hashed values into streams to reduce variance and improve accuracy.
- The final cardinality estimate is obtained by combining the estimates from each stream using a harmonic mean, with bias correction applied for small and large cardinalities.
4
Q
Estimate counters
A
Count-min sketch
- It uses multiple hash functions to map each item to a set of counters in a 2D array. When an item’s count is incremented, the corresponding counters in each row are increased.
- To estimate the count of an item, the sketch hashes the item using the same functions and retrieves the values of the corresponding counters.
- The minimum of these retrieved counter values provides an estimate of the item’s frequency. This estimate is guaranteed to be greater than or equal to the true frequency (no underestimation), but may overestimate it.
5
Q
Consistent hashing
A
- Distributes data across a dynamic number of servers (nodes) with minimal disruption. Unlike traditional hashing, when a node is added or removed, only a small fraction of the keys need to be remapped.
- Uses a hash ring. Both the keys and the servers are hashed onto a circular space (the “ring”). Each key is assigned to the next server in the ring in a clockwise direction.
- Improves scalability and fault tolerance. By minimizing data movement during scaling events and node failures, consistent hashing reduces the load on the system and improves its resilience.
6
Q
Design bit.ly
A
- Read / write patterns strongly favor reads. Highly cacheable.
- Expiration time on URLs
- Validate URL is valid on creation (using a library like is-url)
- base62 encoding (not 64)
- 302 (temporary redirect) to enable analytics and give us more control. 301s cache in browsers and bypass the server.
- Redis caching for heavy reads (1,000x faster than SSD reads, millions of reads per second) – cache invalidation can be complex
- CDN / edge computing: Points of Presence (PoPs). Can avoid having to back to origin server. Cache invalidation is still a problem. Potentially higher costs. Debugging becomes more challenging.
- Break out service to reads and writes to scale separately.
- Redis for incrementing ID, could use counter batching to reduce overhead if needed.
7
Q
Common functional requirements
A
- Authentication / authorization
- Observability and alerting
- The system should be well-tested and easy to deploy (CI/CD pipelines).
- The system should be fault-tolerant.
- The system should have regular backups.
8
Q
Hash indexing
A
Useful of exact match queries. O(1) average case lookup. Supported in PostgreSQL.
9
Q
Data access times
A
- Memory: 100 nanoseconds (0.0001 ms)
- SSD: 0.1 ms
- HDD: 10 ms
10
Q
CDN
A
Content delivery network
- Points of Presence (PoPs) geographically distributed around the world
- Can avoid having to back to origin server.
Potential problems:
- Cache invalidation is still a problem.
- Potentially higher costs.
- Debugging becomes more challenging.
11
Q
DB resilience (psotgres)
A
- Replicas (hot backup, synchronous in same region, async across regions)
- DB backups
12
Q
Design LeetCode
A
- Monaco online editor library for syntax highlighting / autocomplete
- Security and isolation when running user code (containers vs serverless). Containers, need to manage these explicitly. Not as secure as VMs. Need to take care to configure and secure the containers to prevent users from breaking out and accessing the host system. Enforce resource limits.
- Read Only Filesystem
- CPU and Memory Bounds
- Explicit Timeout
- Limit Network Access
- No System Calls (Seccomp)
- Serverless: cold start times are a problem, may have resource limits that can negatively impact performance.
- Live leaderboards / competetions!
- Only 4k problems, very small scale
- Leaderboard: redis sorted set, client polls every 5 seconds for updates (likely don’t need Websockets)
- Auto scaling (ECS: elastic container service)
- Horizontal scaling with queues: buffer submissions during peak times. Enables retries if a container fails.
13
Q
REST API returning a list
A
Make sure you paginate! ?page=1&size=100
14
Q
Secure running user code
A
- Read-only filesystem: write output to a temp dir
- CPU and memory bounds
- Explicit timeout: kill process if it exceeds timeout
- Limit network access: disable it completely from the container
- No system calls (seccomp - secure computing) - a mode of the kernel
15
Q
Design a leaderboard:
- global top 10
- friends top 10
- relative position global
- relative position friends
A
16
Q
Auto scaling containers
A
ECS Elastic Container Service
17
Q
Video / audio concepts
A
- Codecs: encoders and decoders. Compress images, audio and video.
- Video container: MPEG, etc. A video container is a file format that stores video data (frames, audio) and metadata. A container might house information like video transcripts as well.
- Bitrate: The bitrate of a video is the number of bits transmitted over a period of time, typically measured in kilobytes per second (kbps) or megabytes per second (mbps).
- Manifest files: Manifest files are text-based documents that give details about video streams. There’s typically 2 types of manifest files: primary and media files.
18
Q
Design Youtube
A
- Presigned URLs -> AWS S3
- Store different video formats as segments. Segments must be playable on their own. They are created at i-frame (key frame) boundaries.
- Users watch videos using adaptive bitrate streaming. Client does more work to determine the bitrate it can handle.
- Tools like ffmpeg are used to segment and encode
- A data pipeline DAG is used to process videos efficiently (highly parallel). Can use something like Temporal here for orchestration. Can use S3 to pass temporary data between stages of the pipeline.
- Resumable uploads: split video into chunks on the client side. Store metadata and track status of uploads per chunk. Use S3 event notifications to track chunk upload completions.
- CDN: for video files and manifests
- Speed up uploads: “pipeline” the process by uploading segments of the video and start processing them immediately while other segments are still uploading.
19
Q
Design Ticketmaster
A
- Availability for viewing. Consistency for booking.
- Entities: Event, User, Performer, Venue, Ticket, Booking
- Booking endpoints: 2 endpoints, (1) reserve tickets, (2) book tickets. ACID properties necessary.
- Booking service: uses Stripe for payment processing
- Reservations: don’t lock in DB, status with expiration is okay, distributed locking with Redis is better
- High demand events?: SSE for real-time seat updates help. Virtual waiting queue is best.
- Search indexing: Index + SQL query optimization «_space;Full-text indexes (via extensions) in the DB == Elasticsearch
- Search caching: Redis (keys based on search queries) «_space;Query result caching and edge caching (CDNs)
20
Q
Circuit Breaker implementations
A
Hystrix is a circuit breaker that stops cascading failures, realtime monitoring for configuration changes, concurrency aware request caching and automated batching through request collapsing. If microservice failed to return the default response, wait until it’s recovered.
21
Q
Row-level locking vs Optimistic Concurrency Control (OCC)
A
22
Q
Redis Sentinel Architecture
A
23
Q
Redis distributed lock
A
- SETNX (set if not exists) with TTL
- Redlock algo (set lock on multiple nodes with quorum)
- Libraries: Redsync (Redlock impl in golang), Redisson
24
Q
Lucene architecture
A
25
Inverted index
An inverted index is a data structure that maps from words to the documents that contain them. This allows you to quickly find documents that contain a given word.
- Used for full-text search
- Used by lucene
26
Lemmatization
Lemmatization is a process of changing a word to a dictionary form of the word
27
Stemming
Stemming is a process of transforming a word into root form by cutting the ending of the word. This is similar to Lemmatization, but can not handle cases with irregular verbs, but can handle words which are not in the dictionary.
28
Stop words
Stop words are the most popular words in the language or in your dataset, which don’t have any semantic weight.
29
Design an Ad Click Aggregator
- Users can click on an ad and be redirected to the advertiser's website
- Advertisers can query ad click metrics over time with a minimum granularity of 1 minute
- Track click via redirect. If we allow redirects to happen client-side we risk not knowing about it.
- Analytics: separate DB + batch processing << stream processing
- cassandra for raw click data
- spark for batch processing, run every minute
- streaming (flink), keep counts in memory and periodically flush to OLAP DB
- scaling streams: shard by AdId, but can further bucket by appending random number to the end of the AdId to spread out the load
- Durability: kafka is durable. Flink COULD use checkpointing, but not particularly relevant when processing 1-minute intervals. RECONCILIATION is a good way to double check as well.
- Prevent abuse: generate unique impression ID, check impression ID in cache early in the stream (before aggregating). Sign the impression ID to avoid falsified IDs.
- Aggregate data at coarse granularity (daily, weekly) via nightly cron job.
30
OLAP DBs
- Druid
- Redshift
- Snowflake
- Bigquery
31
Facebook news feed (Twitter)
Users should be able to create posts.
Users should be able to friend/follow people.
Users should be able to view a feed of posts from people they follow, in chronological order.
Users should be able to page through their feed.
- use simple table for follower -> followed
- lots of users results in a fan-out problems. Lots of reads, will be brittle and slow. (long tail problem)
- use something like Snowflake IDs to make sure post IDs are chronologically sortable.
- Precompute feeds table in DynamoDB. We'll use a partition key of the userId of the feed and its value will be a list of post IDs in order.
- Async workers to process posts and write to feeds of their followers.
- Don't fan-out writes for users with many followers (celebrities, > 100k). Fan out reads and merge with precomputed feeds at read time.
- Hot keys: redundant caches (do not distribute data across nodes, they can operate independently), this spreads the load evenly across the cluster.
32
Triple stores
https://en.wikipedia.org/wiki/Triplestore
- A triplestore or RDF store is a purpose-built database for the storage and retrieval of triples[1] through semantic queries. A triple is a data entity composed of subject–predicate–object, like "Bob is 35".
33
Job scheduler (similar to schedule Twitter posts):
- Users should be able to schedule jobs to be executed immediately, at a future date, or on a recurring schedule (ie. "every day at 10:00 AM").
- Users should be able monitor the status of their jobs.
- The system should execute jobs within 2s of their scheduled time.
- Users, jobs, tasks, schedule, executions (we need to separate the definition of a job from its execution instances)
- By using a time bucket (Unix timestamp rounded down to the nearest hour) as our partition key, we achieve efficient querying while avoiding hot partition issues.
- when a recurring job completes, we can easily schedule its next occurrence by calculating the next execution time and creating a new entry in the Executions table
- GSI (Global secondary index) for UserID to get all jobs for a user
- two-layered scheduler architecture:
1) query the DB every 5 minutes
2) publish messages to a queue in order of execution_time with delayed delivery (SQS Delivery Delay)
3) "just in time" jobs: publish directly to queue
- AWS default limit is 3,000 messages per second for SQS
- ECS or Kubernetes for autoscaling
- At least once execution: SQS visibility timeout + heartbeats
- we need to ensure our task code is idempotent: Design jobs to be naturally idempotent by using idempotency keys and conditional operations. For example, instead of "increment counter", the job would be "set counter to X". Instead of "send welcome email", we'd first check if the welcome email flag is already set in the user's profile. Each job execution includes a unique identifier that downstream services can use to deduplicate requests.
34
SSTables
Sorted String Tables
- Used in Cassandra
35
Instagram
Users should be able to create posts featuring photos, videos, and a simple caption.
Users should be able to follow other users.
Users should be able to see a chronological feed of posts from the users they follow.
- hybrid to compute feed: fan out write + real-time
- upload media: S3, multi-part upload, S3 notification to track status
- CDN + dynamic media optimization
36
Online auction
- Users should be able to post an item for auction with a starting price and end date.
- Users should be able to bid on an item. Where bids are accepted if they are higher than the current highest bid.
- Users should be able to view an auction, including the current highest bid.
The system should maintain strong consistency for bids to ensure all users see the same highest bid.
- Use optimistic concurrency control (OCC) to update max_bid on auction row. 1. read max bid from row 2. conditionally update max bid if value has not changed.
- message queue to process bids. 1. durable storage 2. buffer against load spikes 3. guaranteed ordering
- SSE for real-time client updates. More efficient than polling / long polling.
- Pub/Sub (Redis) to broadcast max bid updates to clients that are watching the auction.
- Dynamic auction end times: update end time with each bid + cron job. Or use an SQS queue with a delayed delivery. Check if the winner has changed, if not, end the auction.
37
Dropbox
Users should be able to upload a file from any device
Users should be able to download a file from any device
Users should be able to share a file with other users and view the files shared with them
Users can automatically sync files across devices
- availability >> consistency (not intuitive here potentially)
- presigned URLs to upload
- CDN: We can use a cache control header to specify how long the file should be cached in the CDN.
- Sharing with users: join table mapping user -> fileId that they have access to. Can use transaction to make sure it is consistent with the share list in the file metadata.
- Monitor files: FileSystemWatcher or FSEvents
- Conflicts are resolved using a "last write wins" strategy
- Classify files: fresh vs stale. Can use SSE for real-time updates for fresh. Can do periodic polling for stale files.
- Large files: 1. progress indicator 2. resumable uploads
- Fingerprint: SHA-256
- Compression to speed up uploads and downloads: don't try to compress already compressed files
- Encrypt in transit HTTPS, encrypt at rest in S3, access control
- Generate a download signed URL with a TTL
38
Presigned URLs
Presigned URLs are a feature provided by cloud storage services, such as Amazon S3, that allow temporary access to private resources. These URLs are generated with a specific expiration time, after which they become invalid, offering a secure way to share files without altering permissions. When a presigned URL is created, it includes authentication information as part of the query string, enabling controlled access to otherwise private objects.
39
Compression
There are a number of compression algorithms that you can use to compress files. The most common are Gzip, Brotli, and Zstandard. Each of these algorithms has its own tradeoffs in terms of compression ratio and speed. Gzip is the most widely used and is supported by all modern web browsers. Brotli is newer and has a higher compression ratio than Gzip, but it's not supported by all web browsers. Zstandard is the newest and has the highest compression ratio and speed, but it's not supported by all web browsers. You'll need to decide which algorithm to use based on your specific use case.
One important fact about compression is that you should always compress before you encrypt in cases where encryption is necessary. This is because encryption naturally introduces randomness into the file, which makes it difficult to compress. By compressing before encrypting, you will achieve a much higher compression ratio.
40
Saga pattern
The saga pattern is a way to manage data consistency across multiple microservices without using distributed transactions, which can be complex and unreliable. Instead, it breaks down a single business transaction into a sequence of local transactions. Each local transaction updates the database within its own service and then publishes an event to trigger the next local transaction in the saga.
There are two main ways to coordinate these sagas:
Choreography: Each service listens for events from other services and reacts accordingly. There's no central orchestrator; services communicate directly through events. This can be simpler to implement initially but can become harder to manage as the saga grows more complex, leading to potential cyclic dependencies.
Orchestration: A central orchestrator service manages the entire saga. It tells each service when to execute its local transaction and what to do based on the outcomes. This provides better control and visibility but introduces an additional service dependency.
If a local transaction fails at any point in the saga, the pattern also requires implementing compensating transactions. These are transactions that undo the changes made by the preceding successful transactions. Imagine if one runner in the relay race drops the baton; you need a way to go back and correct the steps taken by the previous runners.
41
Distributed Cache Like Redis
Users should be able to set, get, and delete key-value pairs.
Users should be able to configure the expiration time for key-value pairs.
Data should be evicted according to Least Recently Used (LRU) policy.
- background process to clean up TTL'ed items
- LRU: hash table + doubly linked list to track access order
- async repliaction / peer-to-peer replication (gossip protocols)
- sharding: 32 GB machines, 24 GB of usable memory, consistent hashing
- hot keys: dedicated hot key cache == read replicas << copies of hot keys
- heavy writes to hot key: write batching or sharding hot key with suffixes
- connection pooling
42
Gossip protocols
https://en.wikipedia.org/wiki/Gossip_protocol
43
Consistent hashing
Hash Ring & Assignment: Keys and servers are mapped to a circular space. Keys are assigned to the first server encountered clockwise on the ring.
Minimal Redistribution: Adding or removing servers only requires remapping a small fraction of keys, unlike traditional hashing.
Scalability & Stability: This approach improves scalability and stability in distributed systems by limiting the impact of node changes.
44
Cassandra
- last write wins
- partition key, clustering key (optional, like sort key)
- Cassandra Query Language (CQL) dialect
- partitions of data are replicated to nodes on the ring, enabling it to skew extremely available (configurable)
-
45
Geospatial
- Geohashing
- Quadtree (in-memory) - A quadtree is a hierarchical data structure used for spatial partitioning of two-dimensional space. It recursively subdivides space into quadrants, allowing efficient storage and retrieval of spatial data.
- R-tree - It organizes spatial objects into a tree hierarchy, allowing efficient queries for nearest neighbors, range searches, and spatial joins.
- Redis geohashing
- PostGIS (postgres extension)
- ElasticSearch, native support
46
System architecture principles
- Individual parts are coherent, cohesive and aligned both to the domain and to business value
- individual parts are decoupled in the right way so that independent teams can work on the overall system together and in parallel
- half an eye on future evolutions, creating overall architectures that are sufficiently adaptable to change
