The previous chapters have described the underlying technologies such as consistent hashing, ID generator, and now using these techniques we can develop a URL shortener that can generate 100 million URLs per day. Design consists of the following elements: API endpoints URL redirecting URL shortening Data model Hash functions: Hash + collision resolution vs Base-62 conversion Additional topics to consider: Rate limiter Web server scaling Database scaling Analytics Availability, consistency, and reliability These items are disclosed in a very interesting Chapter 8 of the book:
Generating unique ID seems to be a simple task, but it is not in a high-load distributed systems! This topic consists of: Understanding the requirements and why it is a complicated task Possible solutions: Multi-master replication Universally unique identifier (UUID) Ticket server Twitter SNOWFLAKE approach (seems to be the best one!) Details: Timestamp Sequence number Other issues Clock synchronization Section length tuning High availability These items are disclosed in a very interesting Chapter 7 of the book:
Key-Value stores are the most basic but widely used data storages. Design of key-value store consists of understanding the following topics: What do we want from key-value store? Single server key-value store DISTRIBUTED key-value store: CAP theorem Real-world trade-offs for distributed systems System components: Data partition Data replication Consistency Inconsistency resolution: Versioning Handling all types of failures: Failure detection, Handling TEMPORARY failures, Handling PERMANENT failures, Handling data center outage System architecture diagram Write path Read path These items are disclosed in a very interesting Chapter 6 of the book:
Consistent Hashing is a cornerstone technology for distributed systems. Many of software developers don’t realize it, but Consistent Hashing is needed in many places: load balancers, caches, CDNs, id generators, databases, chats / social networks, and many other systems. This topic consists of: Problem with rehashing and why we need hashing to be CONSISTENT Hash space and hash ring BASIC approach (introduced by Karger et al. at MIT) Advanced approach with VIRTUAL NODES These items are disclosed in a very interesting Chapter 5 of the book:
Every popular software should have a Rate Limiter. It prevents DDOS attack, reduces cost and prevents servers from being overloaded. There are some tricky questions to be considered during implementation of Rate Limiter: Where to put Rate Limiter: client-side, server-side, gateway? Algorithms for rate limiting. There are many algorithms with pros and cons: Token bucket, Leaking bucket, Fixed window counter, Sliding window log, Sliding window counter. Your business needs will define the right algorithm.
Four standard steps for system design interview. However, I would think about them wider: as about four initial steps to design the software. Step 1. Understand the problem and establish design scope Step 2. Propose high-level design and get buy-in Step 3. Design deep dive Step 4. Wrap up The chapter 3 of the book discovers details about each step, good questions to ask (to think about), DO’s and DONT’s.
A very short Chapter 2 is about how to make rough estimates to start from the most important parts when designing the software. Some concepts that EVERY software developer should know: “Power of two” Standard latency numbers! How fast is memory, how slow is disk, etc… Availability numbers What are key metrics you should think about These concepts and numbers are disclosed in chapter two of the book:
A great generic plan for scaling any app from zero to millions of users. Single server setup Selection and usage of database Vertical scaling vs horizontal scaling approaches. And why you should prefer horizontal Adding load balancer for horizontal scaling Adding database replication for horizontal scaling Adding cache Adding CDN Stateless vs Stateful architecture and using external state storage Adding extra Data Centers Adding Message queue Adding Logging, Metrics, and Automation Scaling database (sharding) and futher steps… All of these is carefully but briefly disclosed in the Chapter 1 of the book: