Design Distributed Cache
Design Distributed Cache
Ref: original video
Problem statement
Issues with this setup
calls to the data store may take a long time to execute or may utilize a lot of system resources. Some data should be stored in memory and return faster to client.
if the datastore is down or slow, it would be good to serve requests as normal
Why it is called "distributed" cache?
Because the data is large and needs to be stored across several machines.
Single server case
Cache eviction strategy - LRU
Refer to LC LRU cache implementation
Stepping into the distributed world
Dedicated cache cluster
Isolation of resources between service and cache. Both the cache and the service do not share memory and CPU any more.
Can be used by multiple services. e.g. utilize the same cluster across several microservices our team owns
Flexibility in choosing hardware
Co-located cache
No extra hardware and operation cost
Scale together with the service
Choose a cache host to call (naive approach)
Mod hashing is a poor choice
Choose a cache host to call (consistent hashing)
minimize a number of keys we need to re-hash(only new added host, on the clockwise range that need to re-hash)
Who is route these cache to the cache server? - Cache Client
Maintaining a list of cache servers
Option 1: Use configuration management tools
every time need to deploy modified files to every service host
Option 2: Use external storage (e.g. S3)
put the file to the shared storage
service hosts poll for the file periodically
each service host needs a deamon process to poll data periodically
drawback is that we still need to maintain the file manually; also don't know the health of the cache services
Option 3: Configuration service (e.g. Zookeeper)
discover cache hosts and monitor their health
each cache server register itself with configuration service and send heartbeats to it periodically
as long as heartbeats come, server keeps being registered in the system; if heartbeats stop coming, the configuration service unregisters a cache server that is no longer alive or inaccessible
every cache client grabs the list of registered cache servers from the configuration service
Achieving high availability
availability 一般讨论的就是 replication！
Protocol Option 1: probabilistic protocols (e.g. gossip, epidemic broadcast trees, bimodal multicast)
favor eventual consistency
Protocol Option 2: consensus protocols (e.g. 2 or 3 phase commit, paxos, raft chain replication)
favor strong consistency
Master-slave(leader-follower) replication
replica copy across all shards, easy to deal with hot shards - scale out by adding more read replica
for leader election: we can use a configuration service(like, zookeeper). It's the source of truth about whether the service is alive or not. If the leader is down, it will promote another leader.
Redis also implemented Redis Sentinel for this purpose.
What else is important?
Consistency
Several reasons cause inconsistency:
replicate data asynchronously
clients have different lists of cache servers (cache servers may go up and go down again, and a server has values that no other clients can read)
Data expiration
We use LRU cache eviction. If cache is not full, some items may sit there for a long time and such item may become stale.
To fix it: we could introduce some metadata for a cache entry and include
time-to-liveattribute.Option 1 (passively expire an item): when some client tries to access it, and the item is found to be expired.
Option 2 (actively expire an item): create a maintenance thread that runs at regular intervals and remove expired items
Local and remote cache
implement a support for the local cache inside the cache client
use LRU cache or use 3rd party Guava cache.
Security
use a firewall(have some open ports) to ensure only approved clients can access the cache.
clients may also encrypt data before storing in cache and decrypt it on the way out.
Monitoring and logging
number of faults while calling the cache, latency, number of hits and misses, CPU and memory utilization on cache hosts, network I/O
logging should be small but useful: capture the details of every request to the cache.
e.g.: who and when accessed the cache; what was the key and return status code
Cache client
responsibilities of a cache client:
maintain a list of cache servers
pick a shard to route a request to
handle a remote call and any potential failures
emit metrics
make it simpler:
option 1: introduce a proxy, that will sit between cache clients and cache servers and will be responsible for picking a cache shard. e.g. twemporxy project created by Twitter.
option 2: make cache servers responsible for picking a shard. Client sends request to a random cache server and cache server applies consistent hashing and redirects request to the shard that stores the data. This idea is utilized by Redis cluster.
Consistent hashing
major flaws:
domino effect: cache server do not split the circle evenly. If happens when one server dies and transfer all loads to the next one, then the next cannot handle this and dies. Thus it might cause chain reaction of failures.
some servers reside closer and some may be far apart, causing uneven distribution of keys among the cache servers.
To fix them:
add each server on the circle multiple times. Ref Jump Hash Algorithm. or Proportional hashing(algorithm used by Yahoo!).
Summary
Last updated
