Module 14 Review & Cheat Sheet
For full definitions, check the System Design Glossary.
1. Key Concepts Flashcards
Test your knowledge before moving on. Click a card to flip it.
QuadTree
A tree data structure where each node has exactly 4 children. Used for spatial indexing by recursively dividing a 2D region into quadrants. Good for adaptive density.
Google S2
A spatial indexing library that maps the sphere to a cube, then uses a Hilbert Curve to map 2D cells to 1D integers. Used by Uber for uniform cell sizes and better locality than Geohash.
gVisor
A container sandbox by Google that intercepts syscalls in user space. It provides a security boundary between the application and the host kernel, unlike standard Docker.
Firecracker
A virtualization technology by AWS that creates lightweight MicroVMs. It combines the security of traditional VMs with the speed of containers (<125ms boot).
Double-Entry Ledger
A distinctive accounting method where every transaction has equal and opposite entries (Debit and Credit). Ensures the sum of all entries is always zero. Essential for consistency.
Idempotency Key
A unique token sent by the client (e.g., UUID) to ensure that retrying a request (like a payment) does not result in duplicate operations.
Pessimistic Locking
A database locking strategy (`SELECT FOR UPDATE`) that prevents other transactions from modifying data until the lock is released. Critical for preventing Double Spending.
Interval Tree
An augmented Binary Search Tree (BST) used to store time intervals. Allows efficient query of overlapping intervals in O(log N). Critical for Calendar apps.
Seccomp
Secure Computing Mode. A Linux kernel feature that restricts the system calls a process can make (e.g., allow read/write, block socket/fork). Essential for sandboxing.
RRULE
Recurrence Rule (RFC 5545). A standard string format (e.g., `FREQ=DAILY`) used to define repeating events without storing infinite database rows.
Reconciliation
The process of verifying records by comparing internal data (Ledger) with external data (Bank Statements). It is the ultimate safety net for distributed financial systems.
RFQ (Request for Quote)
A trading model where the system provides a fixed price valid for a short window (e.g., 7s). Requires managing race conditions and market risk, unlike an Order Book.
2. System Design Cheat Sheet
| System | Core Problem | Key Technology / Pattern | Why? |
|---|---|---|---|
| Uber / Yelp | Proximity Search (2D) | Google S2 (Hilbert Curve) | Handles 2D locality better than B-Trees. Uniform cell sizes. |
| LeetCode | Arbitrary Code Execution | gVisor / Firecracker | Docker is not secure (Shared Kernel). MicroVMs provide true isolation. |
| Payment System | Consistency / Double Spend | Double-Entry Ledger & Idempotency | Ledger ensures history (Audit). Idempotency handles retries safely. |
| Google Calendar | Overlap Detection | Interval Tree | Efficiently finds intersecting time slots in $O(\log N)$. |
| Trading Order System | Time-Sensitive Consistency | Redis TTL & Pessimistic Locking | Redis TTL handles quote expiry (7s). DB Locking prevents Double Spend. |
3. Quick Revision Points
- Geospatial:
- Geohash: Base-32 string. Suffers from boundary issues.
- QuadTree: Adaptive (deep in cities, shallow in oceans).
- S2: Best for global scale. Maps sphere to 1D ID.
- Security (RCE):
- Defense in Depth: Read-Only FS -> cgroups -> Seccomp -> Network Namespace -> MicroVM.
- Payments:
- ACID: Use SQL (Postgres/MySQL) with Row Locking (
SELECT FOR UPDATE) to prevent race conditions. - Reconciliation: The ultimate safety net for distributed systems.
- ACID: Use SQL (Postgres/MySQL) with Row Locking (
- Scheduling:
- Recurring Events: Store rule (
RRULE), not rows. Expand on read. - Conflict:
Max(StartA, StartB) < Min(EndA, EndB). - Interval Tree: In-memory optimization for overlap checks.
- Recurring Events: Store rule (
- Trading (RFQ):
- Expiry: Use Redis TTL to auto-expire quotes.
- Latency: Client clock is untrusted. Use Grace Periods.
- Wallets: Must use Pessimistic Locking (
SELECT FOR UPDATE) to ensure ACID compliance.
[!TIP] Interview Tip: If asked “How to scale Uber?”, start with QuadTree vs Geohash. If asked “How to scale Payments?”, start with Idempotency and ACID.