Design a modern
Memory Cache
Joway Wang
iftech 2019.11
Why we need a local cache?
Definition of “Modern”
Concurrent 💥
High throughput 🌊
High cache hit ratio 🎳
Memory Limit 🔒
Definition
Concurrent 💥
High throughput 🌊
High cache hit ratio 🎳
Memory Limit 🔒
Simplest Map
Golang
cache := map[string]string{}
cache["a"] = "b"
Problem
Thread Safe Map
Problem
Golang
type SafeMap struct {
lock sync.Mutex
store map[string]string
}
Segmented Safe Map
Problem
Question
Golang
type SafeMap struct {
locks []*sync.Mutex
store []map[string]string
}
Golang: sync.Map
Definition
Concurrent 💥
High throughput 🌊
High cache hit ratio 🎳
Memory Limit 🔒
Eviction strategy
Eviction strategy: LRU
What’s the problem?
Eviction strategy: LFU
What’s the problem?
Eviction strategy: TinyLFU
What’s the problem?
Eviction strategy: W-TinyLFU
Why it called 「TinyLFU」?
Data Structure: Count-Min Sketch
💥 Question:
How to push access log into TinyLFU？
Problem:
Roadmap
RingBuffer
Roadmap
💥 Question:
Could we use segmented buffer?
Why?
Goroutine Model
Thread
M : Machine | Physical Processor
P : Logic Processor
G : Goroutine
Physical CPU
G
P
M
G
G
G
G-P-M Model
CPU
Thread
OS
Golang
Golang: sync.Pool
RingBuffer with sync.Pool
Golang
type ringBuffer struct {
stripes []*ringStripe
pool *sync.Pool
}
Architecture
Q&A