Jargons

CAP theorem

Pick two. In a distributed system, one has to choose between AP v.s. CP.

https://medium.com/system-design-blog/cap-theorem-1455ce5fc0a0

Consistent hashing

Vector clock

Resolve data conflict of different nodes.

Leader election

Bully
Raft
Paxos

Load balancer

Gossip protocol

Service discovery

Client-side discovery
Server-side discovery

Rate limiting

  • Fixed window

    • userId:{count, startTime}

    • Pros: less storage required

    • Cons:

      • inaccurate throttling, end of window1+start of window2 can allow more requests than limitation.

      • Read-then-write pattern lead to race condition.

        • Locking

  • Sliding window

    • userId:SortedSet<Time>

    • pros: accurate throttling

    • cons: more storage needed.

  • Sliding window + fixed window

    • Option1: Break into smaller granularity: 3600 requests per hour -> 60 requests per minute, have a counter for every minute.

    • Option2: Break into every minutes as well. calculate request in current window + request in previous window * overlap percentage

    • userId:SortedList<Pair<time_minute, count>>

    • Cons: false negative, if user send all requests within show time window.

    • Pros: less storage. Balance of two approach.

  • Token bucket

    • Check token bucket for every request

    • 2 parameters: bucket size, refill rate

    • pros: allow burst request

  • Leaking bucket

    • Put request in a queue, process queue in a fixed rate.

    • 2 parameters: queue size, process rate.

    • Pros: stable rate.

  • Race condition

Token bucket
Leaky bucket

Bloom filter

  • Build bit-array: hash(element) -> add to bit-array

  • Query: hash(element) -> check bit-array -> result: 1) equal -> Maybe exists; 2) missing bits -> definitely not exists.

Unique ID generator

Twitter Snowflake

Message Queue

7 Layers OSI model

System latency(access speed)

Bigtable

Last updated

Was this helpful?