> For the complete documentation index, see [llms.txt](https://jaywin.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jaywin.gitbook.io/leetcode/system-design/jargons.md).

# 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>

![](https://3398971849-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-M9HSM8Jn9nrPTh34ajG%2Fuploads%2Fgit-blob-bb1b50a1fd7ac3a08593a079f333abbc408db84e%2Fimage%20\(6\)%20\(1\).png?alt=media)

## 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>

![](https://3398971849-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-M9HSM8Jn9nrPTh34ajG%2Fuploads%2Fgit-blob-3d825ed1a46e554b95ba345c6d27437e3471abe4%2Fimage%20\(7\)%20\(1\)%20\(1\).png?alt=media)

## 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>

![](https://3398971849-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-M9HSM8Jn9nrPTh34ajG%2Fuploads%2Fgit-blob-9962d797045c012ca0ed6068aef6ff426d5f22b5%2Fimage%20\(17\)%20\(1\)%20\(1\).png?alt=media)

## 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](https://medium.com/coinmonks/chubby-a-centralized-lock-service-for-distributed-applications-390571273052): lock file records leader info, e.g. url:port
  * [Zookeeper sequential nodes](https://www.tutorialspoint.com/zookeeper/zookeeper_leader_election.htm)
  * <https://docs.microsoft.com/en-us/azure/architecture/patterns/leader-election>

![Bully](https://3398971849-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-M9HSM8Jn9nrPTh34ajG%2Fuploads%2Fgit-blob-545b85e3a956d1d0ec59557cd39097e8612b5746%2Fimage.png?alt=media)

![Raft](https://3398971849-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-M9HSM8Jn9nrPTh34ajG%2Fuploads%2Fgit-blob-934ec67924e782ebdf4acefb0b297c1748f179c8%2Fimage.png?alt=media)

![Paxos](https://3398971849-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-M9HSM8Jn9nrPTh34ajG%2Fuploads%2Fgit-blob-2a6610e9cc86da779eda0c254b08bd8de0c268ce%2Fimage.png?alt=media)

## 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>

![](https://3398971849-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-M9HSM8Jn9nrPTh34ajG%2Fuploads%2Fgit-blob-b95898a03f95ea87d64949e5e6c6e368a6c2ca07%2Fimage.png?alt=media)

## Gossip protocol

![](https://3398971849-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-M9HSM8Jn9nrPTh34ajG%2Fuploads%2Fgit-blob-84f24df4eea3f02a8641ea2f6670bc11dc5646d0%2Fimage.png?alt=media)

![](https://3398971849-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-M9HSM8Jn9nrPTh34ajG%2Fuploads%2Fgit-blob-0c3c83772bda6614f60080f2dd98c762bf8767a8%2Fimage.png?alt=media)

## 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](https://eng.uber.com/ringpop-open-source-nodejs-library/): sharding, leader election, ectc.

![Client-side discovery](https://3398971849-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-M9HSM8Jn9nrPTh34ajG%2Fuploads%2Fgit-blob-ef0e8e0ae92b2c68b05698f1e4a08c42e6dfaab0%2Fimage.png?alt=media)

![Server-side discovery](https://3398971849-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-M9HSM8Jn9nrPTh34ajG%2Fuploads%2Fgit-blob-a6313af7965778ce6443f3c6c7faf2836a426717%2Fimage.png?alt=media)

![](https://3398971849-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-M9HSM8Jn9nrPTh34ajG%2Fuploads%2Fgit-blob-d359f13753ff4d2fcaed8d4d59f25357a5dba45b%2Fimage.png?alt=media)

![](https://3398971849-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-M9HSM8Jn9nrPTh34ajG%2Fuploads%2Fgit-blob-bc5f13480140bff702632e302a0ed5366d5b0291%2Fimage.png?alt=media)

## 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](https://3398971849-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-M9HSM8Jn9nrPTh34ajG%2Fuploads%2Fgit-blob-4db553868bca7737827f911b7a6262cda10e9f67%2Fimage.png?alt=media)

![Leaky bucket](https://3398971849-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-M9HSM8Jn9nrPTh34ajG%2Fuploads%2Fgit-blob-c86964790c4d5aa022aa2c69705e55c72dfcd36d%2Fimage.png?alt=media)

## 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.

![](https://3398971849-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-M9HSM8Jn9nrPTh34ajG%2Fuploads%2Fgit-blob-3027bf35de2b582d704cbf3a4549a51fceaa640a%2Fimage.png?alt=media)

## Unique ID generator

![Twitter Snowflake](https://3398971849-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-M9HSM8Jn9nrPTh34ajG%2Fuploads%2Fgit-blob-6aa0d8917c08e84ac78ce9f528c3d8eb0bc3dffa%2Fimage.png?alt=media)

## Message Queue

![](https://3398971849-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-M9HSM8Jn9nrPTh34ajG%2Fuploads%2Fgit-blob-1fa4fff86ec5c44c3da073df831204099cbfacff%2Fimage.png?alt=media)

## 7 Layers OSI model

![](https://3398971849-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-M9HSM8Jn9nrPTh34ajG%2Fuploads%2Fgit-blob-98e11853a139359c084e5c179e29a403844e840d%2Fimage.png?alt=media)

## System latency(access speed)

![](https://3398971849-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-M9HSM8Jn9nrPTh34ajG%2Fuploads%2Fgit-blob-b0e69e58b64ba68ed59f397ddf5f5522fbb3ec36%2Fimage.png?alt=media)

## Bigtable

![](https://3398971849-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-M9HSM8Jn9nrPTh34ajG%2Fuploads%2Fgit-blob-63963f1632fc0e95f982606ea89b9e3a14b754d1%2Fimage.png?alt=media)

![](https://3398971849-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-M9HSM8Jn9nrPTh34ajG%2Fuploads%2Fgit-blob-36a4353aca7170e8dc72962af4bd06d3027a5e6b%2Fimage.png?alt=media)