Redis 数据结构
概览
数据类型和数据结构
键和值用什么组织
哈希桶中的元素保存的并不是值本身，而是指向具体值的指针。
字符串
struct SDS<T> {
T capacity; // 数组容量
T len; // 数组长度
byte flags; // 特殊标识位，不理睬它
byte[] content; // 数组内容
}
当字符串比较短时，len 和 capacity 可以使用 byte 和 short 来表示，Redis 为了对内存做极致的优化，不同长度的字符串使用不同的结构体来表示。当字符串长度小于 1M 时，扩容都是加倍现有的空间，如果超过 1M，扩容时一次只会多扩 1M 的空间。需要注意的是字符串最大长度为 512M。
哈希
存储形式：压缩列表 ziplist 和哈希表 hash
struct RedisDb {
dict* dict; // all keys key=>value
dict* expires; // all expired keys key=>long(timestamp)
...
}
struct zset {
dict *dict; // all values value=>score
zskiplist *zsl;
}
dict 结构内部包含两个 hashtable，通常情况下只有一个 hashtable 是有值的。但是在 dict 扩容缩容时，需要分配新的 hashtable，然后进行渐进式搬迁，这时候两个 hashtable 存储的分别是旧的 hashtable 和新的 hashtable。待搬迁结束后，旧的 hashtable 被删除，新的 hashtable 取而代之。
struct dict {
...
dictht ht[2];
}
渐进式 rehash
什么是渐进哈希？字典有一个字段 rehashidx，设置为 0 表示正式开始，每当添加/删除/查找/更新时，都会把在 rehashidx 索引上的所有键值对迁移到 ht[1]，当完成之后，rehashidx 加 1。添加的时候，只会添加到 ht[1]，查找则会 ht[0] 和 ht[1] 都找。
大字典的扩容是比较耗时间的，需要重新申请新的数组，然后将旧字典所有链表中的元素重新挂接到新的数组下面，这是一个O(n)级别的操作，作为单线程的Redis表示很难承受这样耗时的过程。步子迈大了会扯着蛋，所以 Redis 使用渐进式 rehash 小步搬迁。虽然慢一点，但是肯定可以搬完。
搬迁操作埋伏在当前字典的后续指令中(来自客户端的hset/hdel指令等)，但是有可能客户端闲下来了，没有了后续指令来触发这个搬迁，那么Redis就置之不理了么？当然不会，优雅的Redis怎么可能设计的这样潦草。Redis 还会在定时任务中对字典进行主动搬迁。
扩容/缩容
正常情况下，当 hash 表中元素的个数等于第一维数组的长度时，就会开始扩容，扩容的新数组是原数组大小的 2 倍。不过如果 Redis 正在做 bgsave，为了减少内存页的过多分离 (Copy On Write)，Redis 尽量不去扩容 (dict_can_resize)，但是如果 hash 表已经非常满了，元素的个数已经达到了第一维数组长度的 5 倍 (dict_force_resize_ratio)，说明 hash 表已经过于拥挤了，这个时候就会强制扩容。
load_factor = ht[0].used / ht[1].size;
什么时候缩容，负载因子小于 0.1。
有序集合
压缩列表
Redis 为了节约内存空间使用，zset 和 hash 容器对象在元素个数较少的时候，采用压缩列表 (ziplist) 进行存储。压缩列表是一块连续的内存空间，元素之间紧挨着存储，没有任何冗余空隙。
跳跃列表
如果数据存储在链表中，就真的没法用二分查找算法了吗？只需要对链表稍加改造，就可以支持类似“二分”的查找算法。这种链表加多级索引的结构，就是跳表。
Redis 中的有序集合支持的核心操作主要有下面这几个：
- 插入一个数据；
- 删除一个数据；
- 查找一个数据；
- 按照区间查找数据（比如查找值在
[100, 356]之间的数据）； - 迭代输出有序序列。
插入、删除、查找以及迭代输出有序序列这几个操作，红黑树也可以完成，时间复杂度跟跳表是一样的。但是，按照区间来查找数据这个操作，红黑树的效率没有跳表高。
对于按照区间查找数据这个操作，跳表可以做到 O(logn) 的时间复杂度定位区间的起点，然后在原始链表中顺序往后遍历就可以了。
对于每一个新插入的节点，都需要调用一个随机算法给它分配一个合理的层数。直观上期望的目标是 50% 的 Level1，25% 的 Level2，12.5% 的 Level3，一直到最顶层2^-63，因为这里每一层的晋升概率是 50%。
/* Returns a random level for the new skiplist node we are going to create.
* The return value of this function is between 1 and ZSKIPLIST_MAXLEVEL
* (both inclusive), with a powerlaw-alike distribution where higher
* levels are less likely to be returned. */
int zslRandomLevel(void) {
int level = 1;
while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
level += 1;
return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}
延时队列
延时队列可以通过 Redis 的 zset(有序列表) 来实现。我们将消息序列化成一个字符串作为 zset 的value，这个消息的到期处理时间作为score，然后用多个线程轮询 zset 获取到期的任务进行处理，多个线程是为了保障可用性，万一挂了一个线程还有其它线程可以继续处理。因为有多个线程，所以需要考虑并发争抢任务，确保任务不能被多次执行。
Redis 的 zrem 方法是多线程多进程争抢任务的关键，它的返回值决定了当前实例有没有抢到任务，因为 loop 方法可能会被多个线程、多个进程调用，同一个任务可能会被多个进程线程抢到，通过 zrem 来决定唯一的属主。
同时，我们要注意一定要对 handle_msg 进行异常捕获，避免因为个别任务处理问题导致循环异常退出。以下是 Java 版本的延时队列实现，因为要使用到 Json 序列化，所以还需要 fastjson 库的支持。
import java.lang.reflect.Type;
import java.util.Set;
import java.util.UUID;
import com.alibaba.fastjson.JSON;
import com.alibaba.fastjson.TypeReference;
import redis.clients.jedis.Jedis;
public class RedisDelayingQueue<T> {
static class TaskItem<T> {
public String id;
public T msg;
}
// fastjson 序列化对象中存在 generic 类型时，需要使用 TypeReference
private Type TaskType = new TypeReference<TaskItem<T>>() {
}.getType();
private Jedis jedis;
private String queueKey;
public RedisDelayingQueue(Jedis jedis, String queueKey) {
this.jedis = jedis;
this.queueKey = queueKey;
}
public void delay(T msg) {
TaskItem<T> task = new TaskItem<T>();
task.id = UUID.randomUUID().toString(); // 分配唯一的 uuid
task.msg = msg;
String s = JSON.toJSONString(task); // fastjson 序列化
jedis.zadd(queueKey, System.currentTimeMillis() + 5000, s); // 塞入延时队列 ,5s 后再试
}
public void loop() {
while (!Thread.interrupted()) {
// 只取一条
Set<String> values = jedis.zrangeByScore(queueKey, 0, System.currentTimeMillis(), 0, 1);
if (values.isEmpty()) {
try {
Thread.sleep(500); // 歇会继续
} catch (InterruptedException e) {
break;
}
continue;
}
String s = values.iterator().next();
if (jedis.zrem(queueKey, s) > 0) { // 抢到了
TaskItem<T> task = JSON.parseObject(s, TaskType); // fastjson 反序列化
this.handleMsg(task.msg);
}
}
}
public void handleMsg(T msg) {
System.out.println(msg);
}
public static void main(String[] args) {
Jedis jedis = new Jedis();
RedisDelayingQueue<String> queue = new RedisDelayingQueue<>(jedis, "q-demo");
Thread producer = new Thread() {
public void run() {
for (int i = 0; i < 10; i++) {
queue.delay("codehole" + i);
}
}
};
Thread consumer = new Thread() {
public void run() {
queue.loop();
}
};
producer.start();
consumer.start();
try {
producer.join();
Thread.sleep(6000);
consumer.interrupt();
consumer.join();
} catch (InterruptedException e) {
}
}
}
上面的算法中同一个任务可能会被多个进程取到之后再使用 zrem 进行争抢，那些没抢到的进程都是白取了一次任务，这是浪费。可以考虑使用 lua scripting 来优化一下这个逻辑，将 zrangebyscore 和 zrem 一同挪到服务器端进行原子化操作，这样多个进程之间争抢任务时就不会出现这种浪费了。
位图
在我们平时开发过程中，会有一些 bool 型数据需要存取，比如用户一年的签到记录，签了是 1，没签是 0，要记录 365 天。如果使用普通的 key/value，每个用户要记录 365 个，当用户上亿的时候，需要的存储空间是惊人的。
为了解决这个问题，Redis 提供了位图数据结构，这样每天的签到记录只占据一个位，365 天就是 365 个位，46 个字节 (一个稍长一点的字符串) 就可以完全容纳下，这就大大节约了存储空间。
Redis 的位数组是自动扩展，如果设置了某个偏移位置超出了现有的内容范围，就会自动将位数组进行零扩充。
HyperLogLog
统计网站的 UV (同一个用户一天之内的多次访问请求只能计数一次，这就要求每一个网页请求都需要带上用户的 ID，无论是登陆用户还是未登陆用户都需要一个唯一 ID 来标识)，如果使用 Set 会占据太多空间，Redis 提供了 HyperLogLog 数据结构就是用来解决这种统计问题的。HyperLogLog 提供不精确的去重计数方案，虽然不精确但是也不是非常不精确，标准误差是 0.81%，这样的精确度已经可以满足上面的 UV 统计需求了。
127.0.0.1:6379> pfadd codehole user1
127.0.0.1:6379> pfadd codehole user2
127.0.0.1:6379> pfcount codehole
(integer) 2
如果使用 Bitmap 统计一亿用户，那么这个 Bitmap 需要 1 亿位。统计一天占用的空间为：1 亿 / 8 = 12.5 MB，不管多少个用户登录，占用的空间都是 12.5 MB。
Redis 4.0 布隆过滤器
新闻客户端推荐系统如何实现推送去重的？当用户量很大，每个用户看过的新闻又很多的情况下，从每个用户的历史记录里进行筛选，过滤掉那些已经存在的记录，推荐系统的去重工作在性能上跟的上么？
当布隆过滤器说某个值存在时，这个值可能不存在；当它说不存在时，那就肯定不存在。
127.0.0.1:6379> bf.add codehole user1
127.0.0.1:6379> bf.add codehole user2
127.0.0.1:6379> bf.exists codehole user1
1
Redis 4.0 redis-cell 漏斗限流模块
> cl.throttle zk:reply 15 30 60 1
▲ ▲ ▲ ▲ ▲
| | | | └───── need 1 quota (可选参数，默认值也是1)
| | └──┴─────── 30 operations / 60 seconds 这是漏水速率
| └───────────── 15 capacity 这是漏斗容量
└─────────────────── key
Redis 3.2 GeoHash 地理位置
如何快速查询附近的人 ?
业界比较通用的地理位置距离排序算法是 GeoHash 算法，Redis 也使用 GeoHash 算法。GeoHash 算法将二维的经纬度数据映射到一维的整数，这样所有的元素都将在挂载到一条线上，距离靠近的二维坐标映射到一维后的点之间距离也会很接近。当我们想要计算「附近的人时」，首先将目标位置映射到这条线上，然后在这个一维的线上获取附近的点就行了。
BigKey
如何发现
redis-cli --bigkeys，这个命令建议在从节点执行，因为是使用 scan 完成的，没有从节点，就是用 --i 0.1 代表每 100 ms 执行一次。计算每种数据结构的 top1。
找到大于 10KB 的所有 key:
127.0.0.1:6379> memory usage big:hash 这个是 redis 4.0 提供的，然后结合 scan 就能找到所有的。
如何防止
string 控制在 10KB 以内，hash、list、set、zset 元素个数不要超过 5000。非字符串的 bigkey，不要使用 del 删除，使用 hscan、sscan、zscan 渐进删除，同时也要防止 bigkey 过期时间自动删除的问题。
Redis 4.0 过期异步删除: lazyfree-lazy-expire yes
如何优化
big list: list1、list2、list3 ... listN
big hash: hash % 100 二次 hash