Requirement

• Functional (put, get)
• non-functional (high scalability, high availability, high performance)

Simple solution

• client -> local cache -> Data storage
• LRU

Scale to multiple machine

• local cache is not enough -> distributed system
• separate service / cache server
• sharding cache server (Consistent Hashing)
• Cache client call config service(ZooKeeper) to discover all cashe servers
• master / slave for cache server
  • put: master
  • get: slave

Resource

• original video
• zookeeper
• ref2

TODO

cache miss, search from disk? Bloom filter? SStable?

Powers of two table

1
2
3
4
5
6
7
8
9
10

Power           Exact Value         Approx Value        Bytes
---------------------------------------------------------------
7                             128
8                             256
10                           1024   1 thousand           1 KB
16                         65,536                       64 KB
20                      1,048,576   1 million            1 MB
30                  1,073,741,824   1 billion            1 GB
32                  4,294,967,296                        4 GB
40              1,099,511,627,776   1 trillion           1 TB

Resource

• Latency number

Used for re-sized hash table without moving most of data

Resource

• ref

Rate limiter could implmented by each API/ each IP/ total region Might save the rule in DB / config file

Where to implement

1. server side
   • Fully control
2. middleware
   • API gateway
   • Might be 3rd party

Algorithm

• Token bucket
• Leaking bucket
• Fixed window counter
• sliding window log
• Sliding window counter

Resource

• Good video
  • Need to review again to get deeper
• Code for TokenBucket
• 九章算法