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

• https://www.educative.io/courses/grokking-the-system-design-interview/B81vnyp0GpY
• https://docs.datastax.com/en/dse/6.7/dse-arch/datastax_enterprise/dbArch/archDataDistributeVnodesUsing.html#Distributingdatausingvnodes

Vector clock

Resolve data conflict of different nodes.

• https://riak.com/why-vector-clocks-are-easy/index.html
• http://guyharrison.squarespace.com/blog/2015/10/12/vector-clocks.html

Leader election

• Algorithm

  • https://www.cnblogs.com/moonyaoo/p/12952580.html
  • Bully

    • https://www.cs.colostate.edu/~cs551/CourseNotes/Synchronization/BullyExample.html
  • Paxos

    • http://harry.me/blog/2014/12/27/neat-algorithms-paxos/
    • https://www.cnblogs.com/linbingdong/p/6253479.html
    • Used in: Casandra, Spanner, Chubby

    • Multi-paxos: leader proposer.

  • Raft

    • Similar with Paxos, especially multi-poxos.

    • https://raft.github.io/
    • http://thesecretlivesofdata.com/raft/
    • Used in: etcd

  • ZAB

    • Similar to Raft, but the server that is most up to date wins.

    • Used in: Zookeeper

• Lease(lock, distributed mutex):

  • Chubby: lock file records leader info, e.g. url:port
  • Zookeeper sequential nodes
  • https://docs.microsoft.com/en-us/azure/architecture/patterns/leader-election

Bully

Raft

Paxos

Load balancer

• 5 Load balancing methods

  • Round Robin

    • Weighted Round Robin. Similar to virtual nodes -> physical nodes mapping.

  • IP hash

  • Least connection

  • Least Response Time

  • Least Bandwidth

  • https://www.educative.io/courses/grokking-the-system-design-interview/3jEwl04BL7Q

Gossip protocol

Service discovery

• https://www.nginx.com/blog/service-discovery-in-a-microservices-architecture/
• Client-side

• Server-side

  • Routing tier. Use Zookeeper.

  • Gossip protocol. Handle-or-forward pattern.

    • Uber Ringpop: sharding, leader election, ectc.

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

  • Option 1: lock

    • cons: latency, performance bottleneck

  • Option 2: rely on atomic operation of third-party implementation, e.g. Redis

    • https://engineering.classdojo.com/blog/2015/02/06/rolling-rate-limiter/
    • detailed code: https://gist.github.com/ptarjan/e38f45f2dfe601419ca3af937fff574d

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