Core Concept

Network

• Default HTTP over TCP, handle 90% of use cases
• Need real time update? use WebSocket or Server-Sent Events (SSE)
  • Prioritise Server-Sent Events (SSE) and HTTP Long polling. Only fall back WebSocket when need bi-directional
  • Since this is stateful, we cant simply throw it under a load balancer
• For internal to internal services, use gRPC if performance is critical.
  • Don't use for public facing since it's not natively support in browser yet
• For low latency globally, do regional deployment with data replicated or partitioned by geography, for this case, use CDNs

API Design

• 90% of the time default to REST.
• Do not spend too much time, only 4-5 key endpoints in couple minutes
• If you're returning large result sets, need pagination.
  • Real-time: using cursor base pagination so we know where we are at
    • i.e: ?cursor=post_123
  • Non-real-time: offset base pagination to fetch n amount of item for each page
    • i.e ?offset=20&limit=10
• Authentication, use:
  • User session: JWT token
  • Service to service: API key

Data Modeling

• There are 2 main choices, either NoSQL or SQL
• SQL works great for structured data, when there is a clear relationship and need strong consistency:
  • i.e user account links to order, links to product
  • In SQL, we need to consider Database Denormalisation and Database Normalisation
    • Normalisation: great for consistency but need to do join to complete the data
    • Denormalisation: bad for write but good for read
  • NOTE: always start with Database Normalisation in the interview and Database Denormalisation the specific hot part. Don't propose Database Denormalisation upfront unless you have the clear reasons
• NoSQL allows you to have flexible schemas (data structure changes frequently), or you need to scale horizontally across many servers without complex joins
  • For NoSQL, queries like "get all posts that mentions hashtag Y" require scanning entire table.
  • Therefore you need to design the table right upfront which requires you to know your query upfront
  • NOTE: for NoSQL you cannot add Dynamo Local Secondary Index (LSI) after the table is created but for SQL you can using CREATE INDEX.
    • Therefore changing the structure of the table is often more difficult for NoSQL

Database indexing

• Most relational database create B-tree index B Tree and B+ Tree
  • Hash index is fast for exact match but it doesn't support range, so they're less common
• If you need specialised index for example, full-text search and location queries, you will need external system:
  • Full text search: ElasticSearch
  • Geospatial: PostGIS
• These external system often sync from your primary database using CDC, therefore there will be an acceptable slight lag behind. The trade-off is often worth it since it lets you search in a way your database cannot handle

Caching

• A cache on redis take a round 1ms compare to 20-50ms for a database query, that's already 20-50x speedup
• Normally, 90% of the time we use Cache aside: if the data is there, return, if not, query database, store the result in the cache with TTL and returns. Works for most heavy-read system
• To Invalidate the cache, there are a few strategy
  1. Write through > Write through with invalidation: invalidate entry after write
  2. Use short TTL and accept some staleness
  3. Combination of these 2
• For cache stampedes (when popular cache entry expires, many concurrent requests miss at same time and hits db), we can do
  • Locking: if one requests detect a cache miss, it will claim a lock to generate the cache entry for it. Other requests wait for this cache entry to generate instead of hitting the database
  • Early cache recomputation: recompute the cache before it expires
  • Random TTLs so they dont expire the same time
• if Redis goes down, we can have
  • Circuit breaker to stop affecting other dependencies
  • Small in-process cache fall back Local cache eventually-consistent Redis

Sharding

• When 1 single database is not enough and you need to split your data across multiple server
• Main thing is shard key
  • Example, for instagram, we can shard by user_id which all user's posts, likes comments are in one shard. However global query like "trending post across all users" will be impacted and expensive
• Most system use hard-based sharding where you use % to pick a shard
• Range based sharding can work if your access pattern is naturally fall into partition. However it will create hotspot if one range get more traffic
• Directory-based sharding is flexible but adds dependency and latency to every request, normally not worth it.

[!danger]
The big mistake is to shard early, a well-tuned database with read replicas can handle way more than you think. If you're at 10K writes per second and 100GB of data you don't need sharding yet.

Problem with sharding

• Cross-shard transactions become nearly impossible
• Hotspot problem

Consistent Hashing

See Design Consistent Hashing.

This pattern showed up in different practice like distributed emmcached, redis cluster, Cassandra and Dynamodb also use it for sharding

[!NOTE]
In the interview, you rarely need to explain how consistent hashing work unless specifically asked. I't enough to say we'll use consistent hashing as mechanism to make the hash without massive data movement.

CAP Theorem

CAP theorem

If you choose consistency, when network partition happens:

• System will refuse to serve stale data, only serve when the whole system is up to guarantee correctness

If you choose availability:

• Every node keeps serving requests during network partition. User always have response but nodes might bet temporarily have different data until the parition heals

For most system, availability is the right default with eventually consistency. User can tolerate seeing sighly stale data.

Strong consistency matters when stale data caused actual business problems For example: Inventory system, banking, booking system.

[!NOTE]
It's common to have different consistency requirements for different parts of the same application. I.e e-commerce system, product description and review can be eventually consistent. Order processing and inventory processing need strong consistency.

CAP theorem only describe behavior during network partition, it's important to know PACELC theorem. In practice, even when network is healthy, strong consistency will add latency.

In interview, when you mention replication or distributed data, interviewer may ask about consistency. The safe answer is eventual consistency unless problem involves money, inventory or booking etc.

Number to know