小对象压缩存储
ziplist、intset
- hash：hashtable，小对象压缩用ziplist
- set：值为NULL的hashtable，小整数对象压缩用intset
- zset：skiplist，小对象压缩用ziplist
应用篇
分布式锁
如果setnx和expire分开设置，程序在设置expire之前挂掉，锁无法del或过期。 redis支持整合setnx和expire到一条指令：
set lock:codehole true ex 5 nx // ex 5：过期时间5s，nx：键不存在时才设置
... critical
del lock:codehole再安全点，保证锁只能由自己释放：
tag = random.nextint()
if redis.set(key, tag, nx=True, ex=5):
do_something()
redis.delIfEquals(key, tag) # 假想的delIfEquals指令，由脚本实现保证原子性无法解决超时问题。如果在临界区的执行时间太长，超时导致锁释放，临界区就有并发问题。使用redission框架可以在锁快过期时续期。
延时队列
用zset实现延时队列，把消息的序列化串作为value，把消息的到期处理时间作为score。用一个进程定时查询zset的score最小的元素，可用ZRANGEBYSCORE key -inf +inf limit 0 1 withscores。如果最小score<当前时间戳，就将消息取出来执行。
近似计数
HyperLogLog，基数估计（count distinct），空间复杂度O(lglgn)
布隆过滤器
说集合不含某元素时肯定不含，说集合含某未知元素时可能不含
可用在推荐新闻的去重，爬虫URL的去重（会比精确结果多去掉一些）
简单限流
限制某行为在一定时间内的发生次数
每个行为一个zset，用score记录行为发生时间（value保持唯一即可），查询[now - period, now]范围内的发生次数。
漏桶限流
漏桶的剩余容量leftQuota、漏水速率leakingRate、上次漏水时间leakingTime
先漏这一次水 leftQuota += (currentTime-leakingTime)*leakingRate，再看剩余容量够不够 leftQuota≥needed
Redis-Cell模块支持漏桶限流 #？ ，用两个数字ops、seconds表示漏水速率
查找附近
GeoHash算法将地图区域不断切分为小方块并编码，切分次数越多精度越高、编码越长。
scan指令
redis的所有key都存储在一个dict中（一维数组+冲突链表），scan返回的游标是一维数组的槽位。scan遍历采用高位进位加法（在最高位加1然后往左进位），这样在扩容或缩容rehash后的槽位是相邻的，可以避免对之前槽位的重复遍历。在扩容或缩容后对当前槽位的遍历可能返回重复元素，所以scan返回的结果需要客户端去重。
原理篇
线程IO模型
redis是单线程
事件驱动IO（IO多路复用）
read_events, write_events = select(read_fds, write_fds, timeout)
for event in read_events:
handle_read(event.fd)
for event in write_event:
handle_write(event.fd)
handle_others() # 处理其他事情，比如定时任务等持久化
快照
fork出子进程序列化内存数据，父进程写时复制共享页面
通常在从节点进行，不在主节点进行
日志
记录对内存数据的修改指令
内存数据库对日志的处理与其他数据库不同：
- 先修改内存再写日志。其他数据库是先写日志再修改内存。
- 日志瘦身和快照类似，fork出子进程将内存数据转成修改指令写入日志，完成后再将操作期间父进程发生的增量修改追加进去。其他数据库是压缩日志中的相同键只保留最新值。
一般有个独立的异步线程每秒fsync()一次，将所写日志强制从内核缓存刷到磁盘
混合持久化
快照和（从快照持久化开始到结束这段时间的）增量日志一起，重启时先加载快照、再重放增量日志
事务（不具备原子性）
multi服务端队列开启、exec执行服务端队列中的指令、discard抛弃队列。exec即使指令执行失败，也会执行队列中的后续指令，redis事务不具备原子性（可中断性）
乐观锁watch+multi
在事务开始前监控某些键，先watch某些键再multi，然后在exec时如果发现这些键的值已被更改，就事务失败返回NULL。exec返回后自动取消所有的watch。
集群篇
主从复制
主节点将改变状态的指令存在本地缓存中（定长的环形数组），然后异步地将指令复制到从节点。如果太久没复制，本地缓存中的旧指令会被覆盖，这时需要先快照复制、再增量指令复制。
Sentinel
主节点故障自动转移到从节点
Stream
类似Kafka
拓展篇
Redlock算法
在分布式锁的基础上，向所有节点发送set(key, value, nx=True, ex=xxx)指令，只要过半set成功就认为加锁成功。锁的有效时间要减去获取过半数锁的过程耗费的时间。释放锁要向所有节点发送del指令。
过期策略
将所有设置了过期时间的key放入一个独立的dict
- 定时抽样删除：每0.1s抽样从字典中随机选20个key，删除其中过期的key，如果过期比例超过1/4就如此重复
- 惰性删除：客户端访问这个key时检查过期时间，如果过期就立即删除
如果大批量key要过期，要给过期时间加一个随机时间（比如一天内的随机秒数），防止同时过期导致缓存雪崩
近似LRU算法
抽样删除：如果内存超出限制，就随机选5个key，淘汰掉最旧的，如此重复
异步删除
unlink会用后台线程异步删除大对象回收内存
源码篇
字符串
- 正常结构含成员capacity、len、content
- ≤44字节用embstr结构。因为RedisObject头16字节、字符串头3字节、NULL尾1字节，jemalloc分配64字节的话64-16-3-1=44字节。
字典dict
struct dict {
...
dictht ht[2]; // 内含两个哈希表
}渐进式rehash：
在后续的定时任务或hash操作指令中，将ht[0]的内容一点点地迁移到ht[1]
压缩列表ziplist
紧凑存储，通过offset值支持正反向遍历
quicklist是ziplist的双向链表。压缩深度k表示首尾各k个ziplist不压缩，其余ziplist用LZF算法压缩。
新引入的listpack是ziplist的改进版，且解决了ziplist的级联更新问题。
跳跃表
struct zset {
dict *dict; // all values value=>score
zskiplist *zsl;
}基数树rax
类似压缩过的Trie树
参考
《Redis深度历险——核心原理与应用实践》