Redis五种基本数据结构的实现

String

SDS

SDS(simple dynamic string，SDS),简单动态字符串

redis是用C写的，但是字符串没有使用C语言的字符串进行表示，而是自己实现了一个，C的字符串只是被使用于一个字符串常量，而要可以修改的话，则是使用SDS表示字符串值

C
struct sdshr {
    // 记录buf数组中已使用字节的数量
    // 等于 SDS 所保存字符串的长度
    int len;
    
    // 记录 buf 数组中未使用字节的数量
    int free;
    
    // 字节数组，用于保存字符串
    char buf[];
}

主要好像是多了未使用空间和已使用长度这两部分，那这两部分的作用是什么？

已使用长度倒是比较明确，可以以常数复杂度获取字符串长度，因为C字符串并不记录自身的长度信息，而是遍历整个字符串，为遇到的每个字符进行计数，直到遇到代表字符串结尾的空字符为止，确保获取字符串长度不会成为性能瓶颈

而free部分，则可以避免缓冲区溢出，C语言如果直接拼接两个字符串，若分配的空间不够，且它对应存储的空间有另外一个字符串连续，则可能会直接修改下一个字符串的内容，而Redis的SDS API则不会，可以先检查是否有足够的剩余空间，再进行下一步的拼接

空间预分配

是为了减少C语言进行内存重分配扩展s空间的次数，因为内存重分配设计复杂算法，可能需要执行系统
调用，所以Redis采取了两种空间预分配策略

- 当len<1MB时，那么会给分配和len属性同样大小的未使用空间
- 当len>1MB时，那么会给分配1MB未使用空间

惰性空间释放

 用于优化SDS的字符串缩短操作：当SDS的API需要缩短SDS保存的字符串时，程序并不立即使用内存重
 分配来回收缩短后多出来的字节，而是使用free属性将这些字节的数量记录起来，并等待将来使用
 

二进制安全

还有另外一个优点是二进制安全，C语言是通过空字符判断字符串结束的，但是redis如果存储二进制数据的话，其中也有可能存在空字符，所以redis直接把所有数据当作二进制来存储，然后取值是通过len属性判断实际内容长度的

二进制安全简单来说，就是只关心二进制话的字符串，不关心具体形式

使用场景

1. 缓存对象

   • 直接缓存整个对象的JASON
   • 将key进行分离采用MSET存储，用MGET获取各属性值

2. 常规计数器

   • 比如IP限流，点赞，转发，库存数量等等

3. 分布式锁

   • SETNX，实现key不存在才会插入，可以用来实现分布式锁：
     • 如果key不存在，则显示插入成功，表示加锁
     • key存在，插入失败，加锁失败

   对锁还会加上过期时间，避免死锁或者程序宕机不释放锁
   SET lock_key unique_value NX PX 10000

   解锁过程则需要区判断是否执行操作的客户端是加锁的客户端，是的话才允许将其删除

   可以看出解锁有两个操作，1是判断，2才是删除，所以需要保证原子操作，这时候就需要lua脚本来保证解锁的原子性

   lua
   if redis.call("get",KEYS[1]) == ARGV[1] then
       return redis.call("del",KEYS[1])
   else
       return 0
   end

4. 共享Session

   单系统应用中常直接将Session信息保存在服务器端，而分布式则不能这样操作

   例如用户一建立会话，Session信息存储到了服务器一中，但第二次访问时被分配到了服务器二上，这时候服务器二上没有用户一的Session信息，即认为他没有登录，就需要他重新登录了，因为分布式系统每次都会将请求随机分配到不同的服务器上

   所以需要用一个能将Session信息存储起来且可以被所有服务器访问到的方法，即可以用Redis对这些信息进行统一的存储和管理

List

底层数据结构是由双向链表或压缩列表实现
- 如果列表元素个数小于512，列表每个元素值小于64字节，则会用压缩列表作为底层数据结构
- 否则使用双向链表

不过在3.2版本之后，List数据类型底层数据结构就只由quicklist实现了

使用场景

• 消息队列
  消息队列在存取消息时，必须要满足三个需求，分别是消息保序、处理重复的消息和保证消息可靠性
  Redis的List和Stream两种数据结构，可以满足上面三个需求

1. 如何满足消息保序

List本身是按照先进先出的顺序对数据存取的，所以已经满足保序的需求了，例如用LPUSH+RPOP实现消息队列，选择一个方向即可满足

不过这样存在的问题是，生产者写入数据时，生产者不会主动去通知消费者，所以消费者需要开启一个协程不断的调用RPOP命令，等有消息写入时，立刻返回结果，否则返回空值则继续循环，所以会使得消费者程序的CPU一直消耗在执行RPOP命令上，带来不必要的性能损失

所以可以使用Redis的BRPOP命令,称为阻塞式读取，客户端在没有读到队列数据时，自动阻塞直到有新数据写入再读取新数据，相比前一种方法这样更节省CPU性能

2. 处理重复的消息

消费者要实现重复消息的判断，需要两个方面的要求：

• 每个消息都要有一个全局ID
• 消费者要记录已经处理的消息ID

不过LIST的缺点就是不会为每个消息生成ID，所以我们需要自行为每个消息生成一个全局唯一ID，生成之后，再用LPUSH命令把消息插入List时，在消息中包含这个全局唯一ID

3. 如何保证消息可靠性？

当消费者从List读取一条，则该消息就不存在了，所以如果消费者处理一半时出现了宕机，则该消息就无效了且无法找回

为了留下这个消息，使用List的BRPOPLPUSH命令，读取出来，并且存到一个备份的List留存

缺点

读取完就被删除了，只支持单个消费者读取

Hash

底层数据结构是由压缩列表或哈希表实现

• 如果哈希类型元素个数小于512个，所有值小于64字节，Redis会使用压缩列表作为Hash类型的底层数据结构
• 如果哈希类型元素不满足上面条件，Redis会使用哈希表作为Hash类型的底层数据结构

使用场景

• 购物车

  • 添加商品 HSET cart:{用户id} {商品id} 1
  • 添加数量 HINCRBY cart:{用户id} {商品id} 1
  • 商品总数 HLEN cart:{用户id}
  • 删除商品 HDEL cart:{用户id} {商品id}
  • 获取购物车所有商品 HGETALL cart:{用户id}

• 令牌桶限流

Set

无序并唯一的键值集合，存储顺序不会按照插入的先后顺序进行存储

一个集合最多可以存储2^32-1个元素，概念和数学中的集合基本类似，可以交集，并集，差集等，所以Set类型除了支持集合内的增删改查，同时还支持多个集合取交，并，差

内部实现

Set类型的底层数据结构是哈希表或整数集合实现

• 如果集合元素都是整数且个数小于512，则使用整数集合作为Set类型的底层数据结构
• 如果集合中的元素不满足上面条件，则使用哈希表作为Set类型的底层数据结构

使用场景

• 点赞
  保证一个用户只能点一个赞，添加到集合中
• 共同关注
• 抽奖活动
  允许重复中奖，则使用SRANDMEMBER，如果不允许重复中奖，可以使用SPOP命令

Zset

在Set的基础上多了一个排序属性score

内部实现

底层数据结构是由压缩列表或跳表实现

• 如果有序集合的元素个数小于128个，并且每个元素的值小于64字节，Redis会使用压缩列表作为Zset类型的底层数据结构
• 如果有序集合的元素不满足上面条件，会使用跳表

Redis7.0中，压缩列表换为了listpack数据结构了

应用场景

• 排行榜

  golang
  ZADD user:xiaolin:ranking 200 article:1
  ZADD user:xiaolin:ranking 40 article:2
  ZADD user:xiaolin:ranking 70 article:3
  ZADD user:xiaolin:ranking 31 article:4
  
  // 点赞
  ZINCRBY user:xiaolin:ranking 1 article:3
  
  //查看某篇文章的点赞数量
  ZSCORE user:xiaolin:ranking article:3
  
  //倒序获取有序集合key才start下标到stop下标的元素
  ZREVRANGE user:xiaolin:ranking 0 2 WITHSCORES
  1) "article:1"
  2) "200"
  3) "article:3"
  4) "70"
  5) "article:2"
  6) "40"
  
  //获取区间
  ZRANGEBYSCORE user:xiaolin:ranking 100 200 WITHSCORES

• 手机号、姓名
  这里的分数需要一致，主要是对key进行排序

golang
ZADD phone 0 13100111100 0 13110114300 0 13132110901
ZADD phone 0 13200111100 0 13210114300 0 13252110901

// 获取所有号码
ZRANGEBYLEX phone - +

// 获取132号段的号码
ZRANGEBYLEX phone [132 (133

// 姓名排序
ZADD names 0 Toumas 0 Jake 0 Bluetuo 0 Gaodeng 0 Aimini 0 Aidehua

// 获取所有人
ZRANGEBYLEX names - +

// 获取名字中大写字母A开头的所有人
ZRANGEBYLEX names [A (B

// 获取名字中大写字母C到Z的所有人
ZRANGEBYLEX names [C [Z

Bitmap

位图，一连串的0|1构成的，通过offset偏移量来查找定位元素

使用场景

• 签到统计
  一个bit代表一天，一个用户只需要31个bit即可，一年也只需要365个bit

golang
// 统计id为100的用户在22年6月的签到情况

// 三号签到
SETBIT uid:sign:100:202206 2 1

// 检验三号签到
GETBIT uid:sign:100:202206 2

// 统计6月签到
BITCOUNT uid:sign:100:202206

// 找到6月第一次打卡时间
BITPOS key bitValue [start] [end]
BITPOS uid:sign:100:202206 1

• 判断用户登录状态
• 连续签到用户数
  多个bitmap，记录每天的签到人员，然后进行与操作

HyperLogLog

用于基数统计的数据集合，即统计一个集合中不重复的元素个数，不过HyperLogLog是基于概率完成的，标准误算率为0.81%

优点是在数量很大时，计算基数所需的内存空间总是固定的且很小

每个HyperLogLog只需要12KB内存，就可以计算接近2^64个不同元素的基数

命令

shell
PFADD key element [element ...]
PFCOUNT key [key ...]
PFMERGE destkey sourcekey [sourcekey ...]

使用场景

• 百万级网页UV计数

GEO

主要是地理位置的存储，内部是Sorted Set类型，即Zset

使用GeoHash编码方法实现了经纬度到Sorted Set中元素权重分数的转换，关键机制是[对二维地图做区间划分]和[对区间进行编码],一组经纬度落在某个区间后，就用区间的编码值来表示，并把编码值作为Sorted Set元素的权重分数，就可以根据这个权重实现搜索附近的需求

Stream

专门为消息队列设计的数据类型
在之前使用的方法都有缺陷

• 发布订阅模式：
  不能持久化可靠的保存消息，并且对于离线重连的客户端不能读取历史消息
• List
  不能重复消费，需要实现全局唯一ID

相比前面两种方法，Stream实现了消费组

golang
// 0-0表示从第一条消息开始读取
XGROUP CREATE mymq group1 0-0
XGROUP CREATE mymq group2 0-0

// 消费组group1内消费者从mymq消息队列

具体使用会比前面难一点，这个在之后进行补充

缺点

使用Redis作为消息队列有一些缺点：

1. Redis作为中间件本身会使得数据丢失
2. 面对消息挤压，内存资源会紧张，因为Redis会将消息存于内存当中，当然可以设置队列最大长度，当队列最大长度超出上限，旧消息会被删除，只保留固定长度的新消息，但这样又可能会使得消息丢失了

发布订阅的缺点

1. 没有基于任何数据类型实现，所以不具备[数据持久化]的能力，所以宕机后所有数据都会丢失
2. 发布订阅模式是【发后即忘】的工作模式，如果有订阅者重连则不能消费之前的历史信息
3. 当消费端有一定的消息积压时，即消费者消费不过来生产者的消息，消费端会被强行断开

所有只适合即时通讯的场景，比如构建哨兵集群的场景采用了发布/订阅机制