Redis 数据类型及适用场景

Redis 数据类型及适用场景

Redis 核心对象

在 Redis 中有一个 核心对象叫做 Redisobject，是用来表示所有的 key 和 value ，redis 常见的数据类型有五种，包括string（字符串）、hash（哈希）、list（列表）、set（集合）、zset（有序集合）

还有一些使用频率不高的数据结构，包括 hyperloglog、bitmap（位图）、geohash（地图）

image-20201112093801027

​ redis 基本数据结构

image-20201112175201239

String（字符串）

string 的 三种内部编码分别是：int，embstr，raw。

int 类型，当一个 key 的 value 是整数型时，redis 就将其编码为 int 类型（条件就是把这个 value当做字符串看待，他的长度不能超过 20）。这种编码类型是为了节省内存，redis 默认会缓存 10000个整型值，这就意味着，如果有 10 个不同的 key，但是其 value 都是 10000 以内的值，事实上全部都是共享同一个对象

1
2
3
4
127.0.0.1:6379> set test 1234
OK
127.0.0.1:6379> object encoding test
"int"

embstr 条件是编码的长度不能超过 44，embstr 编码创建字符串对象所需的空间分配次数为一次，并且 embstr 编码的字符串对象的所以数据都保存在一块连续的内存中，所以可以更好地利用缓存带来的优势，并且释放 embstr 编码的字符串对象只需要调用一次内存释放函数

1
2
3
4
127.0.0.1:6379> set test a1234567890123456789012345678901234567890123
OK
127.0.0.1:6379> object encoding test
"embstr"

raw 条件是编码长度超过 44，raw 编码创建字符串对象所需的空间分配次数为两次， raw 编码的字符串对象的数据可能保存在一块不连续的内存中，并且释放 raw 编码的字符串对象需要调用两次内存释放函数

1
2
3
4
127.0.0.1:6379> set test a1234567890123456789012345678901234567890123456
OK
127.0.0.1:6379> object encoding test
"raw"

redis 是使用 C 语言开发的，但是 redis 字符串中，并没有使用 C 语言中的字符串，而是使用一种被称为 SDS（simple dynamic string）的结构体来保存字符串

image-20201112094301192 
1
2
3
4
5
struct sdshdr {
	int len;
	int free;
	char buf[]
}

SDS 结构如上图：

  • len：用于记录 buf 中已使用的空间的长度
  • free：buf 中空闲空间的长度
  • **buf[]**：实际存储的内容

exp：执行命令 set key value，key 和 value 都是一个 SDS 类型的结构存储在内存中

SDS 与 C 字符串的区别

  1. 常数时间内获得字符串的长度

    C 字符串本身不记录长度信息，每次获取长度信息都是需要遍历整个字符串，复杂度为**O(n)**；C 字符串遍历时遇到 ’\0’ 即结束遍历

    SDS 中 len字段保存着字符串的长度，所以每次都能在常数时间内获取字符串的长度，复杂度为 O(1)

  2. 避免缓冲区溢出

    假设在内存中有两个紧挨着的字符串，分别为 s1=“123” 和 s2=“678”

    由于在内存上紧紧相连，当我们对s1 进行扩充的时候，将 s1=“123”变为s1=“1234”的时候，由于没有进行相应的内存重新分配，导致s2 会被 s1 莫名其妙的修改，会造成缓冲区溢出的问题

    但是 SDS 的 API 对 zfc 修改时首先会检查空间是否足够，如果不充足会分配新的空间，避免缓冲区溢出的问题

  3. 减少字符串修改时带来的内存重新分配的次数

    在 C 语言中，当我们频繁的对一个字符串进行修改操作的时候，需要频繁的进行内存重新分配，十分影响性能。如果不小心忘记，就可能导致内存溢出或者内存泄漏，对于 redis 来说，本来就会很频繁的进行数据的修改，所以使用 C 字符串并不合适。而 SDS 实现了空间的预分配和惰性空间释放两种优化策略：

    • 空间预分配 当 SDS 的 API 对一个 SDS 修改以后，并且对 SDS的空间进行扩充，程序不仅会为 SDS 分配所需要的必须的空间，还会额外分配未使用的空闲空间

      分配规则如下：如果对 SDS 修改后，len的长度小于 1M，那么程序将分配和 len相同长度的未使用空间。举个例子，如果 len=10，重新分配后，buf 的实际长度就是 10（已使用空间）+ 10（空闲空间）+ 1（空字符）=21（实际分配空间），如果对 SDS 修改后 len长度大于 1M，那么程序将分配 1M 的未使用空间

    • 惰性空间释放 当对 SDS 进行缩短操作的时候，程序并不会回收多余的不再被使用的内存空间，而是使用 free 字段将这些字节数量记录下来，后边如果需要进行 append 操作，则直接使用 free 字段中未使用的空间，减少内存再分配的次数

  4. 二进制安全

    在 redis 中不仅可以存储 string 类型的数据，也可以存储一些二进制数据。二进制数据并不是规则的字符串格式，其中就可能会包含以下特殊的字符，比如 “\0”。在 C 中遇到 “\0” 表示的是字符串的结束，但是在 SDS中，标志字符串结束的 len 属性

应用场景

  1. 存储图片
  2. 常规计数，比如统计微博粉丝数等
  3. 共享 session
  4. 限速（例如单位时间内不能获取 N次验证码）

Hash（字典）

Hash对象的实现方式有两种分别是ziplist、hashtable，其中hashtable的存储方式key是String类型的，value也是以key value的形式进行存储。

字典类型的底层就是hashtable实现的，明白了字典的底层实现原理也就是明白了hashtable的实现原理

我们知道hash表最大的问题就是hash冲突，为了解决hash冲突，假如hashtable中不同的key通过计算得到同一个index，就会形成单向链表（「链地址法」），如下图所示：

image-20201112175627751

字典的数据结构如下所示

1
2
3
4
5
6
typedef struct dict{
	dictTypr *type;
	void *privdata;
	dictht ht[2]
	int trehashidx
}
1
2
3
4
5
6
7
8
9
tyepedef struct dicth{
	// 	哈希表数组
	dectEntrt **table;
	// 哈希表大小
	unsigned Long size;
	unsigned long size;
	// 哈希表已有节点数量
	unsigned long used;
}

rehash

由上段代码，我们可知 dict 中存储了一个 dictht 的数组，长度为 2，表明这个数据结构中实际存储着两个哈希表 ht[0] 和 ht[1]，为什么要存储两张 hash 表呢？

当然是为了 Rehash，Rehash 的过程如下：

  • 为 ht[1] 分配空间。如果是扩容操作，ht[1] 的大小为第一个大于等于 ht[0].used*2 的 2^n；如果是缩容操作，ht[1] 的大小为第一个大于等于 ht[0].used 的 2^n。
  • 将 ht[0] 中的键值 Rehash 到 ht[1] 中。
  • 当 ht[0] 全部迁移到 ht[1] 中后，释放 ht[0]，将 ht[1] 置为 ht[0]，并为 ht[1] 创建一张新表，为下次 Rehash 做准备

渐进式 Rehash

由于 Redis 的 Rehash 操作是将 ht[0] 中的键值全部迁移到 ht[1]，如果数据量小，则迁移过程很快。但如果数据量很大，一个 Hash 表中存储了几万甚至几百万几千万的键值时，迁移过程很慢并会影响到其他用户的使用

为了避免 Rehash 对服务器性能造成影响，Redis 采用了一种渐进式 Rehash 的策略，分多次、渐进的将 ht[0] 中的数据迁移到 ht[1] 中

前一过程如下：

  • 为 ht[1] 分配空间，让字典同时拥有 ht[0] 和 ht[1] 两个哈希表
  • 字典中维护一个 rehashidx，并将它置为 0，表示 Rehash 开始
  • 在 Rehash 期间，每次对字典操作时，程序还顺便将 ht[0] 在 rehashidx 索引上的所有键值对 rehash 到 ht[1] 中，当 Rehash 完成后，将 rehashidx 属性+1。当全部 rehash 完成后，将 rehashidx 置为 -1，表示 rehash 完成

注意，由于维护了两张 Hash 表，所以在 Rehash 的过程中内存会增长。另外，在 Rehash 过程中，字典会同时使用 ht[0] 和 ht[1]

所以在删除、查找、更新时会在两张表中操作，在查询时会现在第一张表中查询，如果第一张表中没有，则会在第二张表中查询。但新增时一律会在 ht[1] 中进行，确保 ht[0] 中的数据只会减少不会增加

hashtable

当 哈希类型 无法满足 ziplist 的条件时，Redis 会使用 hashtable 作为 哈希 的 内部实现，因为此时 ziplist 的 读写效率 会下降，而 hashtable 的读写 时间复杂度 为 O（1）

1
2
3
4
127.0.0.1:6379> hmset hashkey f1 v1 f2 v2
OK
127.0.0.1:6379> object encoding hashkey
"ziplist"
  • 当有 value 大于 64 字节时，内部编码 会由 ziplist 变为 hashtable：
1
2
3
4
127.0.0.1:6379> hset hashkey f3 "one string is bigger than 64 byte...忽略..."
OK
127.0.0.1:6379> object encoding hashkey
"hashtable"
  • 当 field 个数 超过 512，内部编码 也会由 ziplist 变为 hashtable：
1
2
3
4
127.0.0.1:6379> hmset hashkey f1 v1 f2 v2 f3 v3 ... f513 v513
OK
127.0.0.1:6379> object encoding hashkey
"hashtable"

ziplist

压缩列表（ziplist）是一组连续内存块组成的顺序的数据结构，压缩列表能够节省空间，压缩列表中使用多个节点来存储数据

压缩列表是列表键和哈希键底层实现的原理之一，压缩列表并不是以某种压缩算法进行压缩存储数据，而是它表示一组连续的内存空间的使用，节省空间，压缩列表的内存结构图如下：

image-20201112175908202

压缩列表中每一个节点表示的含义如下所示：

zlbytes：4个字节的大小，记录压缩列表占用内存的字节数

  1. zltail：4个字节大小，记录表尾节点距离起始地址的偏移量，用于快速定位到尾节点的地址
  2. zllen：2个字节的大小，记录压缩列表中的节点数
  3. entry：表示列表中的每一个节点
  4. zlend：表示压缩列表的特殊结束符号’0xFF’

再压缩列表中每一个entry节点又有三部分组成，包括previous_entry_ength、encoding、content

  1. previous_entry_ength表示前一个节点entry的长度，可用于计算前一个节点的其实地址，因为他们的地址是连续的
  2. encoding：这里保存的是content的内容类型和长度
  3. content：content保存的是每一个节点的内容
image-20201112175945189

应用场景

哈希表相对于 string 类型存储信息更加的直观，操作也更加的方便，经常会用来做为用户数据的管理，存储用户的信息

hash 也可以用作高并发场景下使用 redis 生成唯一的 id

  1. 存储用户数据

    当我们要存储用户数据的时候，肯定是会为用户生成一个唯一标识 id，保持唯一性，用户的其他信息比如生日，年龄，身高、体重等就可以作为 value 值存储

    若是传统的实现，就是简单地将用户的全部信息封装成一个对象，然后通过序列化存储数据，当需要获取用户信息的时候再反序列化去拿到用户信息，这样其实也可以，但是如果仅仅是修改了用户的某个信息，就需要将整套数据重新进行序列化存储，对于机器的性能消耗十分巨大

    image-20201112180709684

若是使用 Redis 的 hash 来存储用户数据，可以将原来的 value 即用户的详细信息也存储成key、value 的形式，这样就不会带来序列化和反序列化造成的性能开销的问题

image-20201112180855998

hash 结构与关系型表

需要注意的是哈希结构和关系型表有不同之处：

  1. 哈希类型 是 稀疏的，而 关系型数据库 是 完全结构化的，例如 哈希类型 每个 键 可以有不同的 field，而 关系型数据库 一旦添加新的 列，所有行 都要为其 设置值（即使为 NULL）
  2. 关系型数据库 可以做复杂的 关系查询，而使用 Redis 去模拟关系型复杂查询 开发困难，维护成本高

List（列表）

Redis中的列表在3.2之前的版本是使用ziplist和linkedlist进行实现的。在3.2之后的版本就是引入了quicklist

ziplist 压缩列表上面已经讲过了，我们来看看linkedlist和quicklist的结构是怎么样的

linkedlist是一个双向链表，他和普通的链表一样都是由指向前后节点的指针。插入、修改、更新的时间复杂度尾O(1)，但是查询的时间复杂度确实O(n)

linkedlist和quicklist的底层实现是采用链表进行实现，在c语言中并没有内置的链表这种数据结构，Redis实现了自己的链表结构

image-20201112181040809

Redis中链表的特性：

  1. 每一个节点都有指向前一个节点和后一个节点的指针
  2. 头节点和尾节点的prev和next指针指向为null，所以链表是无环的
  3. 链表有自己长度的信息，获取长度的时间复杂度为O(1)
  • 当元素 个数较少 且 没有大元素 时，内部编码 为 ziplist：
1
2
3
4
127.0.0.1:6379> rpush listkey e1 e2 e3
(integer) 3
127.0.0.1:6379> object encoding listkey
"ziplist"
  • 当元素个数超过 512 个，内部编码 变为 linkedlist：
1
2
3
4
127.0.0.1:6379> rpush listkey e4 e5 ... e512 e513
(integer) 513
127.0.0.1:6379> object encoding listkey
"linkedlist"
  • 当某个元素超过 64 字节，内部编码 也会变为 linkedlist：
1
2
3
4
127.0.0.1:6379> rpush listkey "one string is bigger than 64 byte..."
(integer) 4
127.0.0.1:6379> object encoding listkey
"linkedlist"

应用场景

  1. 微博列表
  2. 热门文章列表
  3. 微博热门
  4. 消息队列

Set（集合）

Redis中列表和集合都可以用来存储字符串，但是Set是不可重复的集合，而List列表可以存储相同的字符串，Set集合是无序的这个和后面讲的ZSet有序集合相对

Set的底层实现是hashtable和intset

inset 也叫做整数集合，用于保存整数值的数据结构类型，它可以保存int16_t、int32_t 或者int64_t 的整数值

在整数集合中，有三个属性值 encoding、length、**contents[]**，分别表示编码方式、整数集合的长度、以及元素内容，length就是记录contents里面的大小

在整数集合新增元素的时候，若是超出了原集合的长度大小，就会对集合进行升级，具体的升级过程如下：

  1. 首先扩展底层数组的大小，并且数组的类型为新元素的类型
  2. 然后将原来的数组中的元素转为新元素的类型，并放到扩展后数组对应的位置
  3. 整数集合升级后就不会再降级，编码会一直保持升级后的状态

内部编码为整数集合

当元素个数 较少 且都为 整数 时，内部编码 为 intset

1
2
3
4
127.0.0.1:6379> sadd setkey 1 2 3 4
(integer) 4
127.0.0.1:6379> object encoding setkey
"intset"

内部编码为哈希

当 元素个数 超过 512 个，内部编码 变为 hashtable

1
2
3
4
5
6
127.0.0.1:6379> sadd setkey 1 2 3 4 5 6 ... 512 513
(integer) 513
127.0.0.1:6379> scard setkey
(integer) 513
127.0.0.1:6379> object encoding listkey
"hashtable"

当某个元素 不为整数 时，内部编码 也会变为 hashtable

1
2
3
4
127.0.0.1:6379> sadd setkey a
(integer) 1
127.0.0.1:6379> object encoding setkey
"hashtable"

应用场景

  1. 共同好友
  2. 二度好友
  3. 抽奖

ZSet（有序集合）

ZSet是有序集合，从上面的图中可以看到ZSet的底层实现是ziplist和skiplist实现的

skiplist 也叫做跳跃表，跳跃表是一种有序的数据结构，它通过每一个节点维持多个指向其它节点的指针，从而达到快速访问的目的

skiplist由如下几个特点：

  1. 有很多层组成，由上到下节点数逐渐密集，最上层的节点最稀疏，跨度也最大
  2. 每一层都是一个有序链表，只扫包含两个节点，头节点和尾节点
  3. 每一层的每一个每一个节点都含有指向同一层下一个节点和下一层同一个位置节点的指针
  4. 如果一个节点在某一层出现，那么该以下的所有链表同一个位置都会出现该节点
image-20201112181732228

在跳跃表的结构中有head和tail表示指向头节点和尾节点的指针，能后快速的实现定位。level表示层数，len表示跳跃表的长度，BW表示后退指针，在从尾向前遍历的时候使用

BW下面还有两个值分别表示分值（score）和成员对象（各个节点保存的成员对象）

跳跃表的实现中，除了最底层的一层保存的是原始链表的完整数据，上层的节点数会越来越少，并且跨度会越来越大

跳跃表的上面层就相当于索引层，都是为了找到最后的数据而服务的，数据量越大，条表所体现的查询的效率就越高，和平衡树的查询效率相差无几

应用场景

  1. 微博热搜，首页按照阅读量高低推荐
  2. 各种排行榜

BitMap（位图）

这个就是Redis实现的BloomFilter，BloomFilter非常简单，如下图所示，假设已经有3个元素a、b和c，分别通过3个hash算法h1()、h2()和h2()计算然后对一个bit进行赋值，接下来假设需要判断d是否已经存在，那么也需要使用3个hash算法h1()、h2()和h2()对d进行计算，然后得到3个bit的值，恰好这3个bit的值为1，这就能够说明：d可能存在集合中。再判断e，由于h1(e)算出来的bit之前的值是0，那么说明：e一定不存在集合中：

image-20201112182807211

需要说明的是，bitmap并不是一种真实的数据结构，它本质上是String数据结构，只不过操作的粒度变成了位，即bit。因为String类型最大长度为512MB，所以bitmap最多可以存储2^32个bit

GEO（位置）

GEO数据结构可以在Redis中存储地理坐标，并且坐标有限制，由EPSG:900913 / EPSG:3785 / OSGEO:41001 规定如下：

  • 有效的经度从-180度到180度
  • 有效的纬度从-85.05112878度到85.05112878度

但是，需要说明的是，Geo本身不是一种数据结构，它本质上还是借助于Sorted Set（ZSET），并且使用GeoHash技术进行填充。Redis中将经纬度使用52位的整数进行编码，放进zset中，score就是GeoHash的52位整数值。在使用Redis进行Geo查询时，其内部对应的操作其实就是zset(skiplist)的操作。通过zset的score进行排序就可以得到坐标附近的其它元素，通过将score还原成坐标值就可以得到元素的原始坐标。

总之，Redis中处理这些地理位置坐标点的思想是：二维平面坐标点 –> 一维整数编码值 –> zset(score为编码值) –> zrangebyrank(获取score相近的元素)、zrangebyscore –> 通过score(整数编码值)反解坐标点 –> 附近点的地理位置坐标。

GEOHASH 原理

使用wiki上的例子，纬度为42.6，经度为-5.6的点，转化为base32的话要如何转呢？首先拿纬度来进行说明，纬度的范围为-90到90，将这个范围划为两段，则为[-90,0]、[0,90]，然后看给定的纬度在哪个范围，在前面的范围的话，就设当前位为0，后面的话值便为1.然后继续将确定的范围1分为2，继续以确定值在前段还是后段来确定bit的值。就这样慢慢的缩小范围，一般最多缩小13次就可以了(经纬度的二进制位相加最多25位，经度13位，纬度12位)。这时的中间值，将跟给定的值最相近。如下图所示：

image-20201112182945940

第1行，纬度42.6位于[0, 90]之间，所以bit=1；第2行，纬度42.6位于[0, 45]之间，所以bit=0；第3行，纬度42.6位于[22.5, 45]之间，所以bit=1，以此类推。这样，取出图中的bit位：1011 1100 1001，同样的方法，将经度(范围-180到180)算出来为 ：0111 1100 0000 0。结果对其如下：

  1. # 经度0111 1100 0000 0
  2. # 纬度1011 1100 1001

得到了经纬度的二进制位后，下面需要将两者进行结合：从经度、纬度的循环，每次取其二进制的一位(不足位取0)，合并为新的二进制数：01101111 11110000 01000001 0。每5位为一个十进制数，结合base32对应表映射为base32值为：ezs42。这样就完成了encode的过程。

Streams

这是Redis5.0引入的全新数据结构，用一句话概括Streams就是Redis实现的内存版kafka。而且，Streams也有Consumer Groups的概念。通过Redis源码中对stream的定义我们可知，streams底层的数据结构是radix tree

Hyperloglog

HyperLoglog是redis新支持的两种类型中的另外一种(上一种是位图类型Bitmaps)。主要适用场景是海量数据的计算。特点是速度快。占用空间小。

同样是用于计算，HyperLoglog在适用场景方面与Bitmaps方面有什么不同呢。我个人的理解是，Bitmaps更适合用于验证的大数据，比如签到，

记录某用户是不是当天进行了签到，签到了多少天的时候。也就是说，你不光需要记录数据，还需要对数据进行验证的时候使用Bitmaps。

HyperLoglog则用于只记录的时候，比如访问的uv统计。

Redis HyperLogLog 是用来做基数统计的算法，HyperLogLog 的优点是，在输入元素的数量或者体积非常非常大时，计算基数所需的空间总是固定 的、并且是很小的。

在 Redis 里面，每个 HyperLogLog 键只需要花费 12 KB 内存，就可以计算接近 2^64 个不同元素的基 数。这和计算基数时，元素越多耗费内存就越多的集合形成鲜明对比。

但是，因为 HyperLogLog 只会根据输入元素来计算基数，而不会储存输入元素本身，所以 HyperLogLog 不能像集合那样，返回输入的各个元素。

基数 比如数据集 {1, 3, 5, 7, 5, 7, 8}， 那么这个数据集的基数集为 {1, 3, 5 ,7, 8}, 基数(不重复元素)为5。 基数估计就是在误差可接受的范围内，快速计算基数。