• Sentinel checks master/slave liveness, and will perform the switch.
    • Sentinel itself is at least one master one slave (outside redis master-slaves). Client connects to the sentinel instead of main nodes directly
  • Cluster is for sharding
  • How is master elected?
  • How does redis cluster know which shard to use? why 16k slots?
    • Every node maintains slot and it corresponding key ranges by a bitmap. More slots means better compression
    • However, more slots means bigger heartbeat messages

Skip list

  • Redis uses skiplist instead of RBT to implemnt sorted list
  • Need to support interval search and scan. Hard to do so in RBT
  • Easier to implement than RBT
  • Each item has probability p to exist in the next level of the linked list. Therefore, We need to scan at most 1/p items at each level to detect the segment that contains the item
  • Each level is p smaller than the previous level, so the number of linked list is log (1/p)(n). Total search cost is number of linked list * expected items to scan in each linked list

Eviction

  • 3.0 maintain a candidate pool of size 16, a top K least recent visited entries. When eviction is needed, just purge from the candidate pool
  • Strict LRU nees a LL which introduces concurrency and size issue. That is why redis uses a 24 bit TS to implement near LRU
  • The eviction process continous if expiration ratio > 1/4

Defend against a single, super hot key’s expiry

  • If we want to update from the client side, i.e., don’t want a separate process to update cache entries, options:
    • Set a mutex key (SETNX), load db, and set the cache. Otherwise, retry the whole get cache method
    • Alternatively, inside value itself set a timeout value to1, when we read the cache and find it already expired, we extend timeout1, and reset it on cache. This way, others still think it is safe to use the cache.
    • Do not set expiring time, but store the logical value inside the value, if we find it is about to expire, use a background thread to update construct the value asyncly
  • Still need to combine with rate-limiting + active standby to defend in depth.

HA

  • Sentinel is for HA with master-slave replication. Note redis cluster is for sharding + replication, which also supports master-slave failover.
    • Sentinel and redis cluster should not be mixed
  • RDB
    • BGSAVE: fork a child process to create the file. This forked process uses CoW, i.e., it shares code and data with the parent process unless copied
    • This is mainly use for hourly backup/restore
  • AOF
    • forks a chile process to rewrite old AOF
    • write commands to appendonly.aof
    • Replays AOF when the server reboots
  • RDB file goes to the replica, and then replay the AOF log