Loading...
墨滴

金亚大王

2021/03/25  阅读:75  主题:默认主题

快速掌握 Redis 五种基本数据类型的原理

快速掌握 Redis 五种基本数据类型的原理

目录

正文

使用 Redis ,离不开这五种基本的数据对象类型——字符串、列表、哈希、集合、有序集合。通常在程序设计中,我们会按图索骥,各取所需。但是每个数据类型他们的底层是怎样的呢?Redis 又对这些数据类型做了哪些优化呢?接下来让我们一起寻求这一答案。

Redis 对象数据结构

typedef struct redisObject{

// 类型
unsigned type: 4;

// 编码
unsigned encoding: 4;

// 指向底层实现数据结构的指针
void *ptr;

//...

}

类型与编码

类型

类型 对象
STRING 字符串对象
LIST 列表对象
HASH 哈希对象
SET 集合对象
ZSET 有序集合对象

编码

编码 编码对应的底层数据结构
INT long 类型的整数
EMBSTR embstr 编码的简单动态字符串
RAW 简单动态字符串
HT 字典 HASH_TABLE
LINKEDLIST 双端链表
ZIPLIST 压缩列表
INTSET 整数集合
SKIPLIST 跳跃表和字典

类型与编码映射

类型 编码 编码对应的底层数据结构
STRING INT long 类型的整数
STRING EMBSTR embstr 编码的简单动态字符串
STRING RAW 简单动态字符串
LIST ZIPLIST 压缩列表
LIST QUICKLIST 快速列表
LIST LINKEDLIST 双端链表
HASH ZIPLIST 压缩列表
HASH HT 字典
SET INTSET 整数集合
SET HT 字典
ZSET ZIPLIST 压缩列表
ZSET SKIPLIST 跳跃表和字典

⚠️ 每种类型对象都至少使用了两种不同的编码

字符串 STRING

1. int

如果一个字符串对象保存的是整数值并且可用long类型来表示

  • long 整数

2. raw

如果一个字符串对象保存的是字符串值,并且这个字符串值的长度大于 32 字节

两次内存分配 分别创建 redisObject 和 SDSHdr(Redis 自己实现的字符串结构 Simple Dynamic String Header)

  • 大于 32 字符

3. embstr

如果一个字符串对象保存的是字符串值,并且这个字符串值的长度小于 32 字节

通过一次内存分配,同时分配 redisObject 和 SDSHdr

  • 小于 32 字节
  • 只分配 1 次内存

⚠️ 浮点数也是用字符串来存储,取出时再从字符串转为浮点数

转换

单向转换

  • int -> raw 字符串操作导致值不再满足 long 类型整数条件
  • embstr -> raw 字符串操作导致不再满足 字符串 小于 32 字节条件

对象共享

Redis 初始化时会创建好 0 到 9999 的整数字符串。所有 0 - 9999 的整数值内容都直接共享对象(包括 LIST、HASH、SET 中的整数值)而不单独存储整数字符串。

【问题】为什么不共享字符串值的字符串对象?(点击展开答案)

- 整数值的字符串对象验证操作复杂度 O(1)

- 字符串 验证复杂度 O(N)

列表对象 LIST

1. ziplist

  • 元素数量小于 512 个
  • 每个元素的长度都小于 64 字节

2. linkedlist

3. quicklist (Redis 3.2)

  • Redis 3.2 引入 quicklist 代替 ziplist 和 linkedlist 作为 LIST 底层实现
  • 由节点 ziplist 组成的双向链表
  • 解决了 ziplist 的连锁更新问题

哈希对象 HASH

1. ziplist

同一个键值对的两个节点紧挨在一起,键在前,值在后。

  • 键值对小于 512 个
  • 键和值的字符串长度都要小于 64 字节

2. hashtable

键值都是字符串对象

集合 SET

1. intset

  • 所有元素都是整数
  • 元素数量不超过 512 个

2. hashtable

  • value 是 Null

有序集合 ZSET

1. ziplist

  • 集合所有元素数量小于 128 个
  • 每个成员对象小于 64 字节

2. skiplist

typedef struct zset {
  // 跳跃表结构
  zskiplist *zsl;
  
  // 字典
  dict *dict
}

zsl 数据包含成员(字符串对象)和分数(Double 浮点数)

dict 包括成员和分数

【问题】会不会有数据不同步的问题?(点击展开答案)

他们通过指针共享成员和分数值,从而避免数据不同步的情况。

  • zset
    • dict 字典
    • zsl (skiplist) 跳跃表
  • 通过指针共享数据,不产生两份数据
  • 成员 STRING 字符串对象
  • 分值 Double 浮点数类型

字符串类型

Redis 自己实现的「简单动态字符串」 simple dynamic string 简称 SDS

struct sdshdr {
// 记录 buf 已使用字节长度,也就是字符串长度
int len;
// 记录 buf 未使用字节的数量
int free;
char buf[];
}

简单的字符串结构

free: 5
len: 5
buf: R e d i s \0 _ _ _ _ _

⚠️ \0 不计入 len 属性里面

【问题】为什么不直接用 C 字符串?(点击展开答案)

不能保证字符串的安全性。通过 len 来判断有效字符串长度,而不是通过 `\0`。

【问题】但是为什么要加入 `\0` 的设计?(点击展开答案)

兼容 C 的一些字符串现有函数

内存空间预分配

  • 小于 1MB 扩张二倍
  • 大于等于 1MB 扩张 1MB

注意,还需要外加 1 byte 的 \0 的位置

惰性空间释放

减少字符串数量,并不会导致空间被收回。 可通过 sdsfree 释放空间。

其他数据类型

除了最基础的这五种数据类型,Redis 还提供如下四种针对特殊场景的四种特殊的数据结构

  • bitmap 提供位与或非操作
  • hyperLogLog 提供不精确的去重计数方案
  • bloomFilter 布隆过滤器
  • GeoHash 附近的人

金亚大王

2021/03/25  阅读:75  主题:默认主题

作者介绍

金亚大王