今天继续学习 Redis 相关的知识，Redis 的五种基础数据结构。虽然在之前的博客中也有提到过这五种数据结构，当时赶着背东西，基本上就是从别人的八股文里抄的，所以还是重新学一下，重新记录加深记忆，正文开始。

在数据的江湖里，Redis无疑是那位神秘莫测、武功高强的武林盟主。今天，我们要介绍的就是Redis的五个顶级弟子（Redis 到现在已经有 9 种数据结构了），他们各怀绝技，行走江湖无往不利。话不多说，让我们一睹这五兄弟的风采！

前言

我知道现在你已经迫不及待的想要了解这五个大侠了，但是在正式学习这些之前，我们先来了解一下 Redis 武林中的一些“潜规则”。

Redis的两层数据结构简介

Redis 为什么会有如此高的性能？这也是一个老生常谈的问题了，其中之一的原因就是它的每种数据结构都是经过专门设计的，并都有一种或多种数据结构来支持，依赖这些灵活的数据结构，来提升读取和写入的性能。

想要了解Redis的数据结构，可以从两个不同的层面来讨论它：

  1. 第一个层面，是从使用者的角度，这一层面也是Redis暴露给外部的调用接口，比如：
    • string
    • list
    • hash
    • set
    • sorted set
  2. 第二个层面，是从内部实现的角度，属于更底层的实现，比如：
    • dict
    • sds
    • ziplist
    • quicklist
    • skiplist
    • intset

本文会先从第一个层面来了解 Redis 的基础操作，再深入学习其底层原理。

redisObject：两层数据结构的桥梁

什么是redisObject？

从Redis的使用者的角度来看，一个Redis节点包含多个database（非cluster模式下默认是16个，cluster模式下只能是1个），而一个database维护了从key space到object space的映射关系，这个映射关系的key是string类型，而value可以是多种数据类型，比如：string, list, hash, set, sorted set等。
而从 Redis 内部实现的角度来看，database 内的这个映射关系是用一个 dict 来维护的。dict 的 key固定用一种数据结构来表达就够了，这就是动态字符串 sds；而value则比较复杂，为了在同一个dict内能够存储不同类型的value，这就需要一个通用的数据结构，这个通用的数据结构就是 robj，全名是redisObject。

举个例子：

  • 如果value是list类型，那么它的内部存储结构是一个quicklist或者是一个ziplist

  • 如果value是string类型，那么它的内部存储结构一般情况下是一个sds。但如果string类型的value的值是一个数字，那么Redis内部还会把它转成long型来存储，从而减小内存使用。

所以，一个robj既能表示一个sds，也能表示一个quicklist，甚至还能表示一个long型。

Redis 的数据结构定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/* Object types */
#define OBJ_STRING 0
#define OBJ_LIST 1
#define OBJ_SET 2
#define OBJ_ZSET 3
#define OBJ_HASH 4
 
/* Objects encoding. Some kind of objects like Strings and Hashes can be
 * internally represented in multiple ways. The 'encoding' field of the object
 * is set to one of this fields for this object. */
#define OBJ_ENCODING_RAW 0     /* Raw representation */
#define OBJ_ENCODING_INT 1     /* Encoded as integer */
#define OBJ_ENCODING_HT 2      /* Encoded as hash table */
#define OBJ_ENCODING_ZIPMAP 3  /* Encoded as zipmap */
#define OBJ_ENCODING_LINKEDLIST 4 /* Encoded as regular linked list */
#define OBJ_ENCODING_ZIPLIST 5 /* Encoded as ziplist */
#define OBJ_ENCODING_INTSET 6  /* Encoded as intset */
#define OBJ_ENCODING_SKIPLIST 7  /* Encoded as skiplist */
#define OBJ_ENCODING_EMBSTR 8  /* Embedded sds string encoding */
#define OBJ_ENCODING_QUICKLIST 9 /* Encoded as linked list of ziplists */
 
#define LRU_BITS 24
typedef struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    unsigned lru:LRU_BITS; /* lru time (relative to server.lruclock) */
    int refcount;
    void *ptr;
} robj;

一个 robj 包含如下 5 个字段

  • type: 对象的数据类型。占4个bit。可能的取值有5种：OBJ_STRING, OBJ_LIST, OBJ_SET, OBJ_ZSET, OBJ_HASH，分别对应Redis对外暴露的5种数据结构

  • encoding: 对象的内部表示方式（也可以称为编码）。占4个 bit。可能的取值有10种，即前面代码中的10个OBJ_ENCODING_XXX常量。

  • lru: 做LRU替换算法用，占24个bit。这个不是我们这里讨论的重点，暂时忽略。
  • refcount: 引用计数。它允许robj对象在某些情况下被共享。
  • ptr: 数据指针。指向真正的数据。比如，一个代表string的 robj，它的 ptr 可能指向一个 sds 结构；一个代表 list 的 robj，它的 ptr 可能指向一个 quicklist。

encoding字段的说明

这里特别需要仔细察看的是encoding字段。对于同一个type，还可能对应不同的encoding，这说明同样的一个数据类型，可能存在不同的内部表示方式。而不同的内部表示，在内存占用和查找性能上会有所不同。

当type = OBJ_STRING的时候，表示这个robj存储的是一个string，这时encoding可以是下面3种中的一种：

  • OBJ_ENCODING_RAW: string采用原生的表示方式，即用sds来表示。

  • OBJ_ENCODING_INT: string采用数字的表示方式，实际上是一个long型。

  • OBJ_ENCODING_EMBSTR: string采用一种特殊的嵌入式的sds来表示。

当type = OBJ_HASH的时候，表示这个robj存储的是一个hash，这时encoding可以是下面2种中的一种：

  • OBJ_ENCODING_HT: hash采用一个dict来表示
  • OBJ_ENCODING_ZIPLIST: hash采用一个ziplist来表示

10种encoding的取值说明

  • OBJ_ENCODING_RAW: 最原生的表示方式。其实只有string类型才会用这个encoding值（表示成sds）。

  • OBJ_ENCODING_INT: 表示成数字。实际用long表示。

  • OBJ_ENCODING_HT: 表示成dict。
  • OBJ_ENCODING_ZIPMAP: 是个旧的表示方式，已不再用。在小于Redis 2.6的版本中才有。
  • OBJ_ENCODING_LINKEDLIST: 也是个旧的表示方式，已不再用。
  • OBJ_ENCODING_ZIPLIST: 表示成ziplist。
  • OBJ_ENCODING_INTSET: 表示成intset。用于set数据结构。
  • OBJ_ENCODING_SKIPLIST: 表示成skiplist。用于sorted set数据结构。
  • OBJ_ENCODING_EMBSTR: 表示成一种特殊的嵌入式的sds。
  • OBJ_ENCODING_QUICKLIST: 表示成quicklist。用于list数据结构。

robj 的作用

  • redisObject就是Redis对外暴露的第一层面的数据结构：string, list, hash, set, sorted set，而每一种数据结构的底层实现所对应的是哪些第二层面的数据结构（dict, sds, ziplist, quicklist, skiplist等），则通过不同的encoding来区分。可以说，robj是联结两个层面的数据结构的桥梁。
  • 为多种数据类型提供一种统一的表示方式。
  • 允许同一类型的数据采用不同的内部表示，从而在某些情况下尽量节省内存。
  • 支持对象共享和引用计数。当对象被共享的时候，只占用一份内存拷贝，进一步节省内存。

img

好了，在了解完武林江湖的一些潜规则后，我们就可以正式进入这个江湖了，可以避免露头秒了。

字符串（String）：一招制敌的快剑手

首先登场的是字符串，这位老大哥简直是个“快剑手”，动作迅捷、干脆利落。他就像是江湖上的独行侠，擅长简单直接的攻击方式。字符串可以存储任何类型的数据：文本、数字甚至二进制数据，只要你给的，他都能快速接住。

img

如何使用？

通常我们会使用两种方式来操作 Redis：第一种是使用命令行来操作，例如 redis-cli；另一种是使用代码的方式来操作，下面我们分别来看，后面其他数据结构也都会按照这样的顺序讲解。

命令行操作方式

命令 介绍
SET key value 设置指定 key 的值
SETNX key value 只有在 key 不存在时设置 key 的值
GET key 获取指定 key 的值
MSET key1 value1 key2 value2 … 设置一个或多个指定 key 的值
MGET key1 key2 … 获取一个或多个指定 key 的值
STRLEN key 返回 key 所储存的字符串值的长度
INCR key 将 key 中储存的数字值(整型和浮点型)增一
DECR key 将 key 中储存的数字值(整型和浮点型)减一
INCRBY/DECRBY key increment 将 key 中储存的数字值(整型和浮点型)加/减 increment
EXISTS key 判断指定 key 是否存在
DEL key（通用） 删除指定的 key
EXPIRE key seconds（通用） 给指定 key 设置过期时间
APPEND key value 给指定 key 后面追加值 value

更多 Redis String 命令以及详细使用指南，请查看 Redis 官网 对应的介绍。

代码操作方式（采用Go-Redis V8 版本）

常用方法:

  • Keys():根据正则获取keys
  • Type():获取key对应值得类型
  • Del():删除缓存项
  • Exists():检测缓存项是否存在
  • Expire(),ExpireAt():设置有效期
  • TTL(),PTTL():获取有效期
  • DBSize():查看当前数据库key的数量
  • FlushDB():清空当前数据
  • FlushAll():清空所有数据库
  • Set():设置键缓存
  • SetEX():设置并指定过期时间
  • SetNX():设置并指定过期时间,仅当key不存在的时候才设置。
  • Get():获取键值
  • GetRange():字符串截取
  • Incr():增加+1
  • IncrBy():按指定步长增加
  • Decr():减少-1
  • DecrBy():按指定步长减少
  • Append():追加
  • StrLen():获取长度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
// Redis String Set/Get 示例
func setGetExample(rdb *redis.Client, ctx context.Context) {
	// 1.Set 设置 key 如果设置为-1则表示永不过期
	err := rdb.Set(ctx, "score", 100, 60*time.Second).Err()
	if err != nil {
		fmt.Printf("set score failed, err:%v\n", err)
		panic(err)
	}

	// 2.Get 获取已存在的Key其存储的值
	val1, err := rdb.Get(ctx, "score").Result() // 获取其值
	if err != nil {
		fmt.Printf("get score failed, err:%v\n", err)
		panic(err)
	}
	fmt.Printf("val1 -> score ：%v\n", val1)

	// Get 获取一个不存在的值返回redis.Nil 则说明不存在
	val2, err := rdb.Get(ctx, "name").Result()
	if err == redis.Nil {
		fmt.Println("[ERROR] - Key [name] not exist")
	} else if err != nil {
		fmt.Printf("get name failed, err:%v\n", err)
		panic(err)
	}
	// Exists() 方法用于检测某个key是否存在
	n, _ := rdb.Exists(ctx, "name").Result()
	if n > 0 {
		fmt.Println("name key 存在!")
	} else {
		fmt.Println("name key 不存在!")
		rdb.Set(ctx, "name", "weiyi", 60*time.Second)
	}
	val2, _ = rdb.Get(ctx, "name").Result()
	fmt.Println("val2 -> name : ", val2)

	// 3.SetNX 当不存在key时将进行设置该可以并设置其过期时间
	val3, err := rdb.SetNX(ctx, "username", "weiyigeek", 0).Result()
	if err != nil {
		fmt.Printf("set username failed, err:%v\n", err)
		panic(err)
	}
	fmt.Printf("val3 -> username: %v\n", val3)

	// 4.Keys() 根据正则获取keys, DBSize() 查看当前数据库key的数量.
	keys, _ := rdb.Keys(ctx, "*").Result()
	num, err := rdb.DBSize(ctx).Result()
	if err != nil {
		panic(err)
	}
	fmt.Printf("All Keys : %v, Keys number : %v \n", keys, num)

  // 根据前缀获取Key
  vals, _ := rdb.Keys(ctx, "user*").Result()


	// 5.Type() 方法用户获取一个key对应值的类型
	vType, err := rdb.Type(ctx, "username").Result()
	if err != nil {
		panic(err)
	}
	fmt.Printf("username key type : %v\n", vType)

	// 6.Expire()方法是设置某个时间段(time.Duration)后过期，ExpireAt()方法是在某个时间点(time.Time)过期失效.
	val4, _ := rdb.Expire(ctx, "name", time.Minute*2).Result()
	if val4 {
		fmt.Println("name 过期时间设置成功", val4)
	} else {
		fmt.Println("name 过期时间设置失败", val4)
	}
	val5, _ := rdb.ExpireAt(ctx, "username", time.Now().Add(time.Minute*2)).Result()
	if val5 {
		fmt.Println("username 过期时间设置成功", val5)
	} else {
		fmt.Println("username 过期时间设置失败", val5)
	}

	// 7.TTL()与PTTL()方法可以获取某个键的剩余有效期
	userTTL, _ := rdb.TTL(ctx, "user").Result() // 获取其key的过期时间
	usernameTTL, _ := rdb.PTTL(ctx, "username").Result()
	fmt.Printf("user TTL : %v, username TTL : %v\n", userTTL, usernameTTL)

	// 8.Del():删除缓存项与FlushDB():清空当前数据
  // 当通配符匹配的key的数量不多时，可以使用Keys()得到所有的key在使用Del命令删除。
	num, err = rdb.Del(ctx, "user", "username").Result()
	if err != nil {
		panic(err)
	}
	fmt.Println("Del() : ", num)
  // 如果key的数量非常多的时候，我们可以搭配使用Scan命令和Del命令完成删除。
  iter := rdb.Scan(ctx, 0, "user*", 0).Iterator()
  for iter.Next(ctx) {
    err := rdb.Del(ctx, iter.Val()).Err()
    if err != nil {
      panic(err)
    }
  }
  if err := iter.Err(); err != nil {
    panic(err)
  }

	// 9.清空当前数据库，因为连接的是索引为0的数据库，所以清空的就是0号数据库
	flag, err := rdb.FlushDB(ctx).Result()
	if err != nil {
		panic(err)
	}
	fmt.Println("FlushDB() : ", flag)
}

redis数据库中字符串与整型操作实践

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
// stringIntExample 数据类型演示
func stringIntExample(rdb *redis.Client, ctx context.Context) {
	// 设置字符串类型的key
	err := rdb.Set(ctx, "hello", "Hello World!", 0).Err()
	if err != nil {
		panic(err)
	}
	// GetRange ：字符串截取
	// 注：即使key不存在，调用GetRange()也不会报错，只是返回的截取结果是空"",可以使用fmt.Printf("%q\n", val)来打印测试
	val1, _ := rdb.GetRange(ctx, "hello", 1, 4).Result()
	fmt.Printf("key: hello, value: %v\n", val1) //截取到的内容为: ello

	// Append()表示往字符串后面追加元素，返回值是字符串的总长度
	length1, _ := rdb.Append(ctx, "hello", " Go Programer").Result()
	val2, _ := rdb.Get(ctx, "hello").Result()
	fmt.Printf("当前缓存key的长度为: %v，值: %v \n", length1, val2)

	// 设置整形的key
	err = rdb.SetNX(ctx, "number", 1, 0).Err()
	if err != nil {
		panic(err)
	}
	// Incr()、IncrBy()都是操作数字，对数字进行增加的操作
	// Decr()、DecrBy()方法是对数字进行减的操作，和Incr正好相反
	// incr是执行原子加1操作
	val3, _ := rdb.Incr(ctx, "number").Result()
	fmt.Printf("Incr -> key当前的值为: %v\n", val3) // 2
	// incrBy是增加指定的数
	val4, _ := rdb.IncrBy(ctx, "number", 6).Result()
	fmt.Printf("IncrBy -> key当前的值为: %v\n", val4) // 8

	// StrLen 也可以返回缓存key的长度
	length2, _ := rdb.StrLen(ctx, "number").Result()
	fmt.Printf("number 值长度: %v\n", length2)
}

内部实现

字符串总结图.png

源码分析

Redis 3.2 之前 SDS 源码如下：

1
2
3
4
5
6
7
8
9
10
11
struct sds{
    // 记录 buf 数组中已使用字节的数量
    // 等于 SDS 所保存字符串的长度
    int len; 
    
    // 记录 buf 数组中未使用字节的数量
    int free; 
    
    // 字节数组，用于保存字符串
    char buf[]; 
}

可以看出 Redis 3.2 之前 SDS 内部是一个带有长度信息的字节数组，存储结构如下图所示：

字符串存储结构图.png

为了更加有效的利用内存，Redis 3.2 优化了 SDS 的存储结构，源码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
typedef char *sds;

struct __attribute__ ((__packed__)) sdshdr5 { // 对应的字符串长度小于 1<<5
    unsigned char flags;
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 { // 对应的字符串长度小于 1<<8
    uint8_t len; /* 已使用长度，1 字节存储 */
    uint8_t alloc; /* 总长度 */
    unsigned char flags; 
    char buf[]; // 真正存储字符串的数据空间
};
struct __attribute__ ((__packed__)) sdshdr16 { // 对应的字符串长度小于 1<<16
    uint16_t len; /* 已使用长度，2 字节存储 */
    uint16_t alloc; 
    unsigned char flags; 
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 { // 对应的字符串长度小于 1<<32
    uint32_t len; /* 已使用长度，4 字节存储 */
    uint32_t alloc; 
    unsigned char flags; 
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 { // 对应的字符串长度小于 1<<64
    uint64_t len; /* 已使用长度，8 字节存储 */
    uint64_t alloc; 
    unsigned char flags; 
    char buf[];
};

这样就可以针对不同长度的字符串申请相应的存储类型，从而有效的节约了内存使用。

数据类型

SDS

我们可以使用 object encoding key 命令来查看对象(键值对)存储的数据类型，当我们使用此命令来查询 SDS 对象时，发现 SDS 对象竟然包含了三种不同的数据类型：int、embstr 和 raw。

确切地说，String在Redis中是用一个robj来表示的。

用来表示String的robj可能编码成3种内部表示：OBJ_ENCODING_RAW，OBJ_ENCODING_EMBSTR，OBJ_ENCODING_INT。其中前两种编码使用的是sds来存储，最后一种OBJ_ENCODING_INT编码直接把 string 存成了 int 型。

  • 在对string进行incr, decr等操作的时候，如果它内部是OBJ_ENCODING_INT编码，那么可以直接进行加减操作；
  • 如果它内部是OBJ_ENCODING_RAW或OBJ_ENCODING_EMBSTR编码，那么Redis会先试图把sds存储的字符串转成long型，如果能转成功，再进行加减操作。

int 类型很好理解，整数类型对应的就是 int 类型，而字符串则对应是 embstr 类型，当字符串长度大于 44 字节时，会变为 raw 类型存储。

为什么是 44 字节？

在 Redis 中，如果 SDS 的存储值大于 64 字节时，Redis 的内存分配器会认为此对象为大字符串，并使用 raw 类型来存储，当数据小于 64 字节时(字符串类型)，会使用 embstr 类型存储。既然内存分配器的判断标准是 64 字节，那为什么 embstr 类型和 raw 类型的存储判断值是 44 字节？

这是因为 Redis 在存储对象时，会创建此对象的关联信息，redisObject 对象头和 SDS 自身属性信息，这些信息都会占用一定的存储空间，因此长度判断标准就从 64 字节变成了 44 字节。

在前言部分就已经提到过 redisObject 了，其中的五个字段一共占据了 16 字节。

SDS 自身的数据结构，从 SDS 的源码可以看出，SDS 的存储类型一共有 5 种：SDS TYPE 5、SDS TYPE 8、SDS TYPE 16、SDS TYPE 32、SDS TYPE 64，在这些类型中最小的存储类型为 SDS TYPE ５，但 SDS TYPE ５ 类型会默认转成 SDS TYPE 8，以下源码可以证明，如下图所示：SDS-0116-1.png

为什么转换？

img

可以看出，SDS TYPE 5类型根本就无法使用。

那我们直接来看 SDS TYPE 8 的源码：

1
2
3
4
5
6
struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; // 1 byte
    uint8_t alloc; // 1 byte
    unsigned char flags; // 1 byte
    char buf[];
};

可以看出除了内容数组(buf)之外，其他三个属性分别占用了 1 个字节，最终分隔字符等于 64 字节，减去 redisObject 的 16 个字节，再减去 SDS 自身的 3 个字节，再减去结束符 \0 结束符占用 1 个字节，最终的结果是 44 字节(64-16-3-1=44)，内存占用如下图所示：

44字节说明图.png

性能优势

SDS 与 C 语言字符串比较相近，但拥有更过的优势：

  • SDS 获取字符串长度时间复杂度 O(1)：因为 SDS 通过 len 字段来存储长度，使用时直接读取就可以；C 语言要想获取字符串长度需要遍历整个字符串，时间复杂度 O(N)。
  • SDS 能杜绝缓冲区的溢出：因为当 SDS API 要对 SDS 进行修改时，会先检查 SDS 的空间是否足够，如果不够的话 SDS 会自动扩容，So，不会造成缓冲区溢出。而 C 语言则不具备这个功能。
  • SDS 能减少修改字符串时带来的内存重分配次数：
    • 空间预分配：当 SDS 扩容时不只是会增加需要的空间大小，还会额外的分配一些未使用的空间。分配的规则是：如果分配后 SDS 的长度小于 1MB，那么会分配等于分配后 SDS 的大小的未使用空间，简单说就是，SDS 动态分配后是 16KB，那么就会多分配 16KB 的未使用空间；如果 小于 1MB，那么久分配 1MB 的未使用空间。
    • 惰性空间释放： 惰性空间释放用于优化 SDS 的字符串缩短操作：当 SDS 的 API 需要缩短 SDS 保存的字符串时，并不会立即内存重分配来回收多出来的字节，而是用 free 来记录未使用空间。

空间预分配补进一步理解

当执行追加操作时，比如现在给key=‘Hello World’的字符串后追加‘ again!’则这时的len=18，free由0变成了18，此时的buf='Hello World again!\0....................'(.表示空格)，也就是buf的内存空间是18+18+1=37个字节，其中‘\0’占1个字节redis给字符串多分配了18个字节的预分配空间，所以下次还有append追加的时候，如果预分配空间足够，就无须在进行空间分配了。在当前版本中，当新字符串的长度小于1M时，redis会分配他们所需大小一倍的空间，当大于1M的时候，就为他们额外多分配1M的空间。

思考：这种分配策略会浪费内存资源吗？

答：执行过APPEND 命令的字符串会带有额外的预分配空间，这些预分配空间不会被释放，除非该字符串所对应的键被删除，或者等到关闭Redis 之后，再次启动时重新载入的字符串对象将不会有预分配空间。因为执行APPEND 命令的字符串键数量通常并不多，占用内存的体积通常也不大，所以这一般并不算什么问题。另一方面，如果执行APPEND 操作的键很多，而字符串的体积又很大的话，那可能就需要修改Redis 服务器，让它定时释放一些字符串键的预分配空间，从而更有效地使用内存。

哈希（Hash）：万花筒般的博学者

接下来出场的是哈希，哈希就像是一个学识渊博的百科全书，里面装着各种各样的知识点。你问他什么，他都能迅速找到并回答你。哈希非常适合存储对象类型的数据，每个字段都能独立操作，让你在管理数据时游刃有余。

哈希表存储结构.png

如何使用？

命令行操作方式

命令 介绍
HSET key field value 设置指定哈希表中指定字段的值
HSETNX key field value 只有指定字段不存在时设置指定字段的值
HMSET key field1 value1 field2 value2 … 同时将一个或多个 field-value (域-值)对设置到指定哈希表中
HGET key field 获取指定哈希表中指定字段的值
HMGET key field1 field2 … 获取指定哈希表中一个或者多个指定字段的值
HGETALL key 获取指定哈希表中所有的键值对
HEXISTS key field 查看指定哈希表中指定的字段是否存在
HDEL key field1 field2 … 删除一个或多个哈希表字段
HLEN key 获取指定哈希表中字段的数量

更多 Redis Hash 命令以及详细使用指南，请查看 Redis 官网对应的介绍。

代码操作方式（采用Go-Redis V8 版本）

常用方法:

  • HSet():设置
  • HMset():批量设置
  • HGet():获取某个元素
  • HGetAll():获取全部元素
  • HDel():删除某个元素
  • HExists():判断元素是否存在
  • HLen():获取长度

简单示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// hash 是一个 string 类型的 field（字段） 和 value（值） 的映射表，hash 特别适合用于存储对象。
func hashExample(rdb *redis.Client, ctx context.Context) {
	// (1) HSet() 设置字段和值
	rdb.HSet(ctx, "huser", "key1", "value1", "key2", "value2")
	rdb.HSet(ctx, "huser", []string{"key3", "value3", "key4", "value4"})
	rdb.HSet(ctx, "huser", map[string]interface{}{"key5": "value5", "key6": "value6"})

	// (2) HMset():批量设置
	rdb.HMSet(ctx, "hmuser", map[string]interface{}{"name": "WeiyiGeek", "age": 88, "address": "重庆"})

	// (3) HGet() 获取某个元素
	address, _ := rdb.HGet(ctx, "hmuser", "address").Result()
	fmt.Println("hmuser.address -> ", address)

	// (4) HGetAll() 获取全部元素
	hmuser, _ := rdb.HGetAll(ctx, "hmuser").Result()
	fmt.Println("hmuser :=> ", hmuser)

	// (5) HExists 判断元素是否存在
	flag, _ := rdb.HExists(ctx, "hmuser", "address").Result()
	fmt.Println("address 是否存在 hmuser 中: ", flag)

	// (6) HLen() 获取长度
	length, _ := rdb.HLen(ctx, "hmuser").Result()
	fmt.Println("hmuser hash 键长度: ", length)

	// (7) HDel() 支持一次删除多个元素
	count, _ := rdb.HDel(ctx, "huser", "key3", "key4").Result()
	fmt.Println("删除元素的个数: ", count)
}

内部实现

Redis 的字典使用哈希表作为底层实现， 一个哈希表里面可以有多个哈希表节点， 而每个哈希表节点就保存了字典中的一个键值对。

源码分析

接下来的三个小节将分别介绍 Redis 的哈希表、哈希表节点、以及字典的实现。

哈希表

Redis 字典所使用的哈希表由 dict.h/dictht 结构定义：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
typedef struct dictht {
    // 哈希表数组    
    dictEntry **table;
    
    // 哈希表大小    
    unsigned long size;
    
    // 哈希表大小掩码，用于计算索引值    
    // 总是等于 size - 1    
    unsigned long sizemask;
    
    // 该哈希表已有节点的数量    
    unsigned long used;
} dictht;

  • table 属性是一个数组， 数组中的每个元素都是一个指向 dict.h/dictEntry 结构的指针， 每个 dictEntry 结构保存着一个键值对。

  • size 属性记录了哈希表的大小， 也即是 table 数组的大小， 而 used 属性则记录了哈希表目前已有节点（键值对）的数量。

  • sizemask 属性的值总是等于 size - 1 ， 这个属性和哈希值一起决定一个键应该被放到 table 数组的哪个索引上面。

下图 展示了一个大小为 4 的空哈希表 （没有包含任何键值对）。

img

哈希节点

哈希表节点使用 dictEntry 结构表示， 每个 dictEntry 结构都保存着一个键值对：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
typedef struct dictEntry {

    // 键
    void *key;

    // 值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;

    // 指向下个哈希表节点，形成链表
    struct dictEntry *next;

} dictEntry;
  • key 属性保存着键值对中的键， 而 v 属性则保存着键值对中的值， 其中键值对的值可以是一个指针， 或者是一个 uint64_t 整数， 又或者是一个 int64_t 整数。
  • next 属性是指向另一个哈希表节点的指针， 这个指针可以将多个哈希值相同的键值对连接在一次， 以此来解决键冲突（collision）的问题。

举个例子， 下图就展示了如何通过 next 指针， 将两个索引值相同的键 k1 和 k0 连接在一起。

img

字典

Redis 中的字典由 dict.h/dict 结构表示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
typedef struct dict {

    // 类型特定函数
    dictType *type;

    // 私有数据
    void *privdata;

    // 哈希表
    dictht ht[2];

    // rehash 索引
    // 当 rehash 不在进行时，值为 -1
    int rehashidx; /* rehashing not in progress if rehashidx == -1 */

} dict;

type 属性和 privdata 属性是针对不同类型的键值对， 为创建多态字典而设置的：

  • type 属性是一个指向 dictType 结构的指针， 每个 dictType 结构保存了一簇用于操作特定类型键值对的函数， Redis 会为用途不同的字典设置不同的类型特定函数。
  • 而 privdata 属性则保存了需要传给那些类型特定函数的可选参数。

ht 属性是一个包含两个项的数组， 数组中的每个项都是一个 dictht 哈希表， 一般情况下， 字典只使用 ht[0] 哈希表， ht[1] 哈希表只会在对 ht[0] 哈希表进行 rehash 时使用。

除了 ht[1] 之外， 另一个和 rehash 有关的属性就是 rehashidx ： 它记录了 rehash 目前的进度， 如果目前没有在进行 rehash ， 那么它的值为 -1 。

下图 展示了一个普通状态下（没有进行 rehash）的字典：

img

数据类型

字典类型本质上是由数组和链表结构组成的，通常情况下字典类型会使用数组的方式来存储相关的数据，但发生哈希冲突时才会使用链表的结构来存储数据。

Redis 计算索引值的方法是：

1
2
3
4
5
6
# 使用字典设置的哈希函数，计算键 key 的哈希值
hash = dict->type->hashFunction(key);

# 使用哈希表的 sizemask 属性和哈希值，计算出索引值
# 根据情况不同， ht[x] 可以是 ht[0] 或者 ht[1]
index = hash & dict->ht[x].sizemask;

类似 Java 的 HashMap，计算 key 的 hash 值，然后 hash & (len - 1), 而 Redis 的 sizemask 就是 size - 1。

什么是哈希冲突？发生哈希冲突怎么办？

字典类型的存储流程是先将键值进行 Hash 计算，得到存储键值对应的数组索引，再根据数组索引进行数据存储，但在小概率事件下可能会出完全不相同的键值进行 Hash 计算之后，得到相同的 Hash 值，这种情况我们称之为哈希冲突。

哈希冲突一般通过链表的形式解决，相同的哈希值会对应一个链表结构，每次有哈希冲突时，就把新的元素插入到链表的尾部，请参考上面数据结构的那张图。

键值查询的流程如下：

  • 通过算法 (Hash，计算和取余等) 操作获得数组的索引值，根据索引值找到对应的元素；
  • 判断元素和查找的键值是否相等，相等则成功返回数据，否则需要查看 next 指针是否还有对应其他元素，如果没有，则返回 null，如果有的话，重复此步骤。

键值查询流程，如下图所示：

Redis-HashType-03.png

性能优势

dict本质上是为了解决算法中的查找问题，是一个基于哈希表的算法，在不要求数据有序存储，且能保持较低的哈希值冲突概率的前提下，查询的时间复杂度接近O(1)。它采用某个哈希函数并通过计算key从而找到在哈希表中的位置，采用拉链法解决冲突，并在装载因子（load factor）超过预定值时自动扩展内存，引发重哈希（rehash），为了避免扩容时一次性对所有key进行重哈希，Redis采用了一种称为渐进式重哈希（incremental rehash）的方法，将重哈希的操作分散到对于dict的各个增删改查的操作中去。这种方法能做到每次只对一小部分key进行重哈希，而每次重哈希之间不影响dict的操作。dict之所以这样设计，是为了避免重哈希期间单个请求的响应时间剧烈增加，这与前面提到的“快速响应时间”的设计原则是相符的。

rehash

随着不断的操作，hash 表中的键值对可能会增多或减少，为了让哈希表的负载因子保持在一个范围内，需要对 hash 表进行扩容或收缩，收缩和扩容的过程就叫 rehash。rehash 过程如下：

  1. 为字典的 ht[1] 哈希表分配空间， 这个哈希表的空间大小取决于要执行的操作， 以及 ht[0] 当前包含的键值对数量 （也即是 ht[0].used 属性的值）(ht 是字典中的 hash 表，上文有介绍)：
  2. 如果执行的是扩展操作， 那么 ht[1] 的大小为第一个大于等于 ht[0].used * 2 的 2^n （2 的 n 次方幂）；
  3. 如果执行的是收缩操作， 那么 ht[1] 的大小为第一个大于等于 ht[0].used 的 2^n 。
  4. 将保存在 ht[0] 中的所有键值对 rehash 到 ht[1] 上面： rehash 指的是重新计算键的哈希值和索引值， 然后将键值对放置到 ht[1] 哈希表的指定位置上。
  5. 当 ht[0] 包含的所有键值对都迁移到了 ht[1] 之后 （ht[0] 变为空表）， 释放 ht[0] ， 将 ht[1] 设置为 ht[0] ， 并在 ht[1] 新创建一个空白哈希表， 为下一次 rehash 做准备

触发扩容的条件：

1、服务器目前没有执行 BGSAVE 命令或者 BGREWRITEAOF 命令，并且负载因子大于等于1。

2、服务器目前正在执行 BGSAVE 命令或者 BGREWRITEAOF 命令，并且负载因子大于等于5。

ps：负载因子 = 哈希表已保存节点数量 / 哈希表大小。

渐进式 rehash

rehash 时会将 ht[0] 所有的键值对迁移到 ht[1] 中，但这个动作不是一次性的，而是分多次、渐进式地完成。这样的所得原因时：当数据量大的时候一次性迁移会造成服务器在一段时间内定制服务。为了避免发生这样的事就出现了 渐进式 rehash。

主要的执行流程如下：

  • 扩容或者缩容时把字典中的字段 rehashidx 标识为 0；
  • 在执行定时任务或者执行客户端的 hset、hdel 等操作指令时，判断是否需要触发 rehash 操作（通过 rehashidx 标识判断），如果需要触发 rehash 操作，也就是调用 dictRehash 函数，dictRehash 函数会把 ht[0] 中的元素依次添加到新的 Hash 表 ht[1] 中；
  • rehash 操作完成之后，清空 Hash 表 ht[0]，然后对调 ht[1] 和 ht[0] 的值，把新的数据表 ht[1] 更改为 ht[0]，然后把字典中的 rehashidx 标识为 -1，表示不需要执行 rehash 操作。

列表（List）：风驰电掣的快马

第三位登场的是列表，这位兄弟简直就是江湖上的快马，擅长在前后两个方向上迅速移动。无论是队列还是栈，列表都能应付自如。最适合需要顺序操作的场景，比如任务队列或者消息队列。

列表类型 (List) 是一个使用链表结构存储的有序结构，它的元素插入会按照先后顺序存储到链表结构中，因此它的元素操作 (插入\删除) 时间复杂度为 O(1)，所以相对来说速度还是比较快的，但它的查询时间复杂度为 O(n)，因此查询可能会比较慢。

列表类型使用-列表结构图.png

如何使用？

命令行操作方式

命令 介绍
LPUSH key value1 value2 .. 在指定列表的头部（左边）添加一个或多个元素
RPUSH key value1 value2 … 在指定列表的尾部（右边）添加一个或多个元素
LSET key index value 将指定列表索引 index 位置的值设置为 value
LPOP key 移除并获取指定列表的第一个元素(最左边)
RPOP key 移除并获取指定列表的最后一个元素(最右边)
LLEN key 获取列表元素数量
LRANGE key start end 获取列表 start 和 end 之间 的元素

img

更多 Redis List 命令以及详细使用指南，请查看 Redis 官网对应的介绍。

代码操作方式（采用Go-Redis V8 版本）

常用方法:

  • LPush():将元素压入链表
  • LInsert():在某个位置插入新元素
  • LSet():设置某个元素的值
  • LLen():获取链表元素个数
  • LIndex():获取链表下标对应的元素
  • LRange():获取某个选定范围的元素集
  • LPop()从链表左侧弹出数据
  • LRem():根据值移除元素

简单示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
func listExample(rdb *redis.Client, ctx context.Context) {
	// 插入指定值到list列表中，返回值是当前列表元素的数量
	// 使用LPush()方法将数据从左侧压入链表（后进先出）,也可以从右侧压如链表对应的方法是RPush()
	count, _ := rdb.LPush(ctx, "list", 1, 2, 3).Result()
	fmt.Println("插入到list集合中元素的数量: ", count)

	// LInsert() 在某个位置插入新元素
	// 在名为key的缓存项值为2的元素前面插入一个值，值为123 ， 注意只会执行一次
	_ = rdb.LInsert(ctx, "list", "before", "2", 123).Err()
	// 在名为key的缓存项值为2的元素后面插入一个值，值为321
	_ = rdb.LInsert(ctx, "list", "after", "2", 321).Err()

	// LSet() 设置某个元素的值
	//下标是从0开始的
	val1, _ := rdb.LSet(ctx, "list", 2, 256).Result()
	fmt.Println("是否成功将下标为2的元素值改成256: ", val1)

	// LLen() 获取链表元素个数
	length, _ := rdb.LLen(ctx, "list").Result()
	fmt.Printf("当前链表的长度为: %v\n", length)

	// LIndex() 获取链表下标对应的元素
	val2, _ := rdb.LIndex(ctx, "list", 2).Result()
	fmt.Printf("下标为2的值为: %v\n", val2)

	// 从链表左侧弹出数据
	val3, _ := rdb.LPop(ctx, "list").Result()
	fmt.Printf("弹出下标为0的值为: %v\n", val3)

	// LRem() 根据值移除元素 lrem key count value
	n, _ := rdb.LRem(ctx, "list", 2, "256").Result()
	fmt.Printf("移除了: %v 个\n", n)
}

内部实现

我们先用 debug encoding key 来查看列表类型的内部存储类型，如下所示：

1
2
127.0.0.1:6379> object encoding list
"quicklist"

从结果可以看出，列表类型的底层数据类型是 quicklist。

  1. Redis3.2之前的底层实现方式：压缩列表ziplist 或者 双向循环链表linkedlist

    当list存储的数据量较少时，会使用ziplist存储数据，也就是同时满足下面两个条件：

    • 列表中数据个数少于512个
    • list中保存的每个元素的长度小于 64 字节
    • 当不能同时满足上面两个条件的时候，list就通过双向循环链表linkedlist来实现了

  2. Redis3.2及之后的底层实现方式：quicklist

    quicklist是一个双向链表，而且是一个基于ziplist的双向链表，quicklist的每个节点都是一个ziplist，结合了双向链表和ziplist的优点。

数据类型

quicklist

我们来看下 quicklist 的实现源码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
/* Node, quicklist, and Iterator are the only data structures used currently. */

/* quicklistNode is a 32 byte struct describing a ziplist for a quicklist.
 * We use bit fields keep the quicklistNode at 32 bytes.
 * count: 16 bits, max 65536 (max zl bytes is 65k, so max count actually < 32k).
 * encoding: 2 bits, RAW=1, LZF=2.
 * container: 2 bits, NONE=1, ZIPLIST=2.
 * recompress: 1 bit, bool, true if node is temporarry decompressed for usage.
 * attempted_compress: 1 bit, boolean, used for verifying during testing.
 * extra: 10 bits, free for future use; pads out the remainder of 32 bits */
typedef struct quicklistNode {
    struct quicklistNode *prev;
    struct quicklistNode *next;
    unsigned char *zl;
    unsigned int sz;             /* ziplist size in bytes */
    unsigned int count : 16;     /* count of items in ziplist */
    unsigned int encoding : 2;   /* RAW==1 or LZF==2 */
    unsigned int container : 2;  /* NONE==1 or ZIPLIST==2 */
    unsigned int recompress : 1; /* was this node previous compressed? */
    unsigned int attempted_compress : 1; /* node can't compress; too small */
    unsigned int extra : 10; /* more bits to steal for future usage */
} quicklistNode;

/* quicklistLZF is a 4+N byte struct holding 'sz' followed by 'compressed'.
 * 'sz' is byte length of 'compressed' field.
 * 'compressed' is LZF data with total (compressed) length 'sz'
 * NOTE: uncompressed length is stored in quicklistNode->sz.
 * When quicklistNode->zl is compressed, node->zl points to a quicklistLZF */
typedef struct quicklistLZF {
    unsigned int sz; /* LZF size in bytes*/
    char compressed[];
} quicklistLZF;

/* Bookmarks are padded with realloc at the end of of the quicklist struct.
 * They should only be used for very big lists if thousands of nodes were the
 * excess memory usage is negligible, and there's a real need to iterate on them
 * in portions.
 * When not used, they don't add any memory overhead, but when used and then
 * deleted, some overhead remains (to avoid resonance).
 * The number of bookmarks used should be kept to minimum since it also adds
 * overhead on node deletion (searching for a bookmark to update). */
typedef struct quicklistBookmark {
    quicklistNode *node;
    char *name;
} quicklistBookmark;


/* quicklist is a 40 byte struct (on 64-bit systems) describing a quicklist.
 * 'count' is the number of total entries.
 * 'len' is the number of quicklist nodes.
 * 'compress' is: -1 if compression disabled, otherwise it's the number
 *                of quicklistNodes to leave uncompressed at ends of quicklist.
 * 'fill' is the user-requested (or default) fill factor.
 * 'bookmakrs are an optional feature that is used by realloc this struct,
 *      so that they don't consume memory when not used. */
typedef struct quicklist {
    quicklistNode *head;
    quicklistNode *tail;
    unsigned long count;        /* total count of all entries in all ziplists */
    unsigned long len;          /* number of quicklistNodes */
    int fill : QL_FILL_BITS;              /* fill factor for individual nodes */
    unsigned int compress : QL_COMP_BITS; /* depth of end nodes not to compress;0=off */
    unsigned int bookmark_count: QL_BM_BITS;
    quicklistBookmark bookmarks[];
} quicklist;

typedef struct quicklistIter {
    const quicklist *quicklist;
    quicklistNode *current;
    unsigned char *zi;
    long offset; /* offset in current ziplist */
    int direction;
} quicklistIter;

typedef struct quicklistEntry {
    const quicklist *quicklist;
    quicklistNode *node;
    unsigned char *zi;
    unsigned char *value;
    long long longval;
    unsigned int sz;
    int offset;
} quicklistEntry;

这里定义了6个结构体:

  • quicklistNode：宏观上, quicklist是一个链表, 这个结构描述的就是链表中的结点. 它通过zl字段持有底层的ziplist. 简单来讲, 它描述了一个ziplist实例。
  • quicklistLZF：ziplist是一段连续的内存, 用LZ4算法压缩后, 就可以包装成一个quicklistLZF结构. 是否压缩quicklist中的每个ziplist实例是一个可配置项. 若这个配置项是开启的, 那么quicklistNode.zl字段指向的就不是一个ziplist实例, 而是一个压缩后的quicklistLZF实例。
  • quicklistBookmark：在quicklist尾部增加的一个书签，它只有在大量节点的多余内存使用量可以忽略不计的情况且确实需要分批迭代它们，才会被使用。当不使用它们时，它们不会增加任何内存开销。
  • quicklist：这就是一个双链表的定义. head, tail分别指向头尾指针. len代表链表中的结点. count指的是整个quicklist中的所有ziplist中的entry的数目. fill字段影响着每个链表结点中ziplist的最大占用空间, compress影响着是否要对每个ziplist以LZ4算法进行进一步压缩以更节省内存空间。
  • quicklistIter是一个迭代器。
  • quicklistEntry是对ziplist中的entry概念的封装. quicklist作为一个封装良好的数据结构, 不希望使用者感知到其内部的实现, 所以需要把ziplist.entry的概念重新包装一下。

从以上源码可以看出 quicklist 是一个双向链表，链表中的每个节点实际上是一个 ziplist，它们的结构如下图所示：

列表类型使用-quicklist结构图.png

quicklist更多额外信息：

下面是有关quicklist的更多额外信息:

  • quicklist.fill的值影响着每个链表结点中, ziplist的长度.
    1. 当数值为负数时, 代表以字节数限制单个ziplist的最大长度. 具体为:
    2. -1 不超过4kb
    3. -2 不超过 8kb
    4. -3 不超过 16kb
    5. -4 不超过 32kb
    6. -5 不超过 64kb
    7. 当数值为正数时, 代表以entry数目限制单个ziplist的长度. 值即为数目. 由于该字段仅占16位, 所以以entry数目限制ziplist的容量时, 最大值为2^15个
  • quicklist.compress的值影响着quicklistNode.zl字段指向的是原生的ziplist, 还是经过压缩包装后的quicklistLZF
    1. 0 表示不压缩, zl字段直接指向ziplist
    2. 1 表示quicklist的链表头尾结点不压缩, 其余结点的zl字段指向的是经过压缩后的quicklistLZF
    3. 2 表示quicklist的链表头两个, 与末两个结点不压缩, 其余结点的zl字段指向的是经过压缩后的quicklistLZF
    4. 以此类推, 最大值为2^16
  • quicklistNode.encoding字段, 以指示本链表结点所持有的ziplist是否经过了压缩. 1代表未压缩, 持有的是原生的ziplist, 2代表压缩过
  • quicklistNode.container字段指示的是每个链表结点所持有的数据类型是什么. 默认的实现是ziplist, 对应的该字段的值是2, 目前Redis没有提供其它实现. 所以实际上, 该字段的值恒为2
  • quicklistNode.recompress字段指示的是当前结点所持有的ziplist是否经过了解压. 如果该字段为1即代表之前被解压过, 且需要在下一次操作时重新压缩.

zaplist

ziplist 作为 quicklist 的实际存储结构，它本质是一个字节数组，ziplist 数据结构如下图所示：

img

其中的字段含义如下：

  • zlbytes字段的类型是uint32_t, 这个字段中存储的是整个ziplist所占用的内存的字节数。
  • zltail字段的类型是uint32_t, 它指的是ziplist中最后一个entry的偏移量. 用于快速定位最后一个entry, 以快速完成pop等操作。
  • zllen字段的类型是uint16_t, 它指的是整个ziplit中entry的数量. 这个值只占2bytes（16位）: 如果ziplist中entry的数目小于65535(2的16次方), 那么该字段中存储的就是实际entry的值. 若等于或超过65535, 那么该字段的值固定为65535, 但实际数量需要一个个entry的去遍历所有entry才能得到。
  • zlend是一个终止字节, 其值为全F, 即0xff. ziplist保证任何情况下, 一个entry的首字节都不会是255。

Entry 结构

  • 先看下源码中相关介绍

img

第一种情况：一般结构 <prevlen> <encoding> <entry-data>

  • prevlen：前一个entry的大小，编码方式见下文；
  • encoding：不同的情况下值不同，用于表示当前entry的类型和长度；
  • entry-data：真是用于存储entry表示的数据；

第二种情况：在entry中存储的是int类型时，encoding 和entry-data会合并在encoding中表示，此时没有entry-data字段；

redis中，在存储数据时，会先尝试将string转换成int存储，节省空间；

此时entry结构：<prevlen> <encoding>

  • prevlen编码

当前一个元素长度小于254（255用于zlend）的时候，prevlen长度为1个字节，值即为前一个entry的长度，如果长度大于等于254的时候，prevlen用5个字节表示，第一字节设置为254，后面4个字节存储一个小端的无符号整型，表示前一个entry的长度；

1
2
<prevlen from 0 to 253> <encoding> <entry>      //长度小于254结构
0xFE <4 bytes unsigned little endian prevlen> <encoding> <entry>   //长度大于等于254
  • encoding编码

encoding的长度和值根据保存的是int还是string，还有数据的长度而定；

前两位用来表示类型，当为“11”时，表示entry存储的是int类型，其它表示存储的是string；

存储string时：

|00pppppp| ：此时encoding长度为1个字节，该字节的后六位表示entry中存储的string长度，因为是6位，所以entry中存储的string长度不能超过63；

|01pppppp|qqqqqqqq| 此时encoding长度为两个字节；此时encoding的后14位用来存储string长度，长度不能超过16383；

|10000000|qqqqqqqq|rrrrrrrr|ssssssss|ttttttt| 此时encoding长度为5个字节，后面的4个字节用来表示encoding中存储的字符串长度，长度不能超过2^32 - 1;

存储int时：

|11000000| encoding为3个字节，后2个字节表示一个int16；

|11010000| encoding为5个字节，后4个字节表示一个int32;

|11100000| encoding 为9个字节，后8字节表示一个int64;

|11110000| encoding为4个字节，后3个字节表示一个有符号整型；

|11111110| encoding为2字节，后1个字节表示一个有符号整型；

|1111xxxx| encoding长度就只有1个字节，xxxx表示一个0 - 12的整数值；

|11111111| 还记得zlend么？

  • 源码中数据结构支撑

你可以看到为了操作上的简易实际还增加了几个属性

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/* We use this function to receive information about a ziplist entry.
 * Note that this is not how the data is actually encoded, is just what we
 * get filled by a function in order to operate more easily. */
typedef struct zlentry {
    unsigned int prevrawlensize; /* Bytes used to encode the previous entry len*/
    unsigned int prevrawlen;     /* Previous entry len. */
    unsigned int lensize;        /* Bytes used to encode this entry type/len.
                                    For example strings have a 1, 2 or 5 bytes
                                    header. Integers always use a single byte.*/
    unsigned int len;            /* Bytes used to represent the actual entry.
                                    For strings this is just the string length
                                    while for integers it is 1, 2, 3, 4, 8 or
                                    0 (for 4 bit immediate) depending on the
                                    number range. */
    unsigned int headersize;     /* prevrawlensize + lensize. */
    unsigned char encoding;      /* Set to ZIP_STR_* or ZIP_INT_* depending on
                                    the entry encoding. However for 4 bits
                                    immediate integers this can assume a range
                                    of values and must be range-checked. */
    unsigned char *p;            /* Pointer to the very start of the entry, that
                                    is, this points to prev-entry-len field. */
} zlentry;
  • prevrawlensize表示 previous_entry_length字段的长度
  • prevrawlen表示 previous_entry_length字段存储的内容
  • lensize表示 encoding字段的长度
  • len表示数据内容长度
  • headersize 表示当前元素的首部长度，即previous_entry_length字段长度与encoding字段长度之和
  • encoding表示数据类型
  • p表示当前元素首地址

看个例子：

Redis Ziplist Sample

上图是一份真实的ziplist数据。我们逐项解读一下：

  • 这个ziplist一共包含33个字节。字节编号从byte[0]到byte[32]。图中每个字节的值使用16进制表示。
  • 头4个字节（0x21000000）是按小端（little endian）模式存储的<zlbytes>字段。因此，这里<zlbytes>的值应该解析成0x00000021，用十进制表示正好就是33。
  • 接下来4个字节（byte[4..7]）是<zltail>，用小端存储模式来解释，它的值是0x0000001D（值为29），表示最后一个数据项在byte[29]的位置（那个数据项为0x05FE14）。
  • 再接下来2个字节（byte[8..9]），值为0x0004，表示这个ziplist里一共存有4项数据。
  • 接下来6个字节（byte[10..15]）是第1个数据项。其中，prevrawlen=0，因为它前面没有数据项；len=4，相当于前面定义的9种情况中的第1种，表示后面4个字节按字符串存储数据，数据的值为”name”。
  • 接下来8个字节（byte[16..23]）是第2个数据项，与前面数据项存储格式类似，存储1个字符串”tielei”。
  • 接下来5个字节（byte[24..28]）是第3个数据项，与前面数据项存储格式类似，存储1个字符串”age”。
  • 接下来3个字节（byte[29..31]）是最后一个数据项，它的格式与前面的数据项存储格式不太一样。其中，第1个字节prevrawlen=5，表示前一个数据项占用5个字节；第2个字节=FE，相当于前面定义的9种情况中的第8种，所以后面还有1个字节用来表示真正的数据，并且以整数表示。它的值是20（0x14）。
  • 最后1个字节（byte[32]）表示<zlend>，是固定的值255（0xFF）。

总结一下，这个ziplist里存了4个数据项，分别为：

  • 字符串: “name”
  • 字符串: “tielei”
  • 字符串: “age”
  • 整数: 20

源码分析

添加功能源码分析

quicklist 添加操作对应函数是 quicklistPush，源码如下：

1
2
3
4
5
6
7
8
9
10
void quicklistPush(quicklist *quicklist, void *value, const size_t sz,
                   int where) {
    if (where == QUICKLIST_HEAD) {
        // 在列表头部添加元素
        quicklistPushHead(quicklist, value, sz);
    } else if (where == QUICKLIST_TAIL) {
        // 在列表尾部添加元素
        quicklistPushTail(quicklist, value, sz);
    }
}

以 quicklistPushHead 为例，源码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int quicklistPushHead(quicklist *quicklist, void *value, size_t sz) {
    quicklistNode *orig_head = quicklist->head;
    if (likely(
            _quicklistNodeAllowInsert(quicklist->head, quicklist->fill, sz))) {
        // 在头部节点插入元素
        quicklist->head->zl =
            ziplistPush(quicklist->head->zl, value, sz, ZIPLIST_HEAD);
        quicklistNodeUpdateSz(quicklist->head);
    } else {
        // 头部节点不能继续插入，需要新建 quicklistNode、ziplist 进行插入
        quicklistNode *node = quicklistCreateNode();
        node->zl = ziplistPush(ziplistNew(), value, sz, ZIPLIST_HEAD);
        quicklistNodeUpdateSz(node);
        // 将新建的 quicklistNode 插入到 quicklist 结构中
        _quicklistInsertNodeBefore(quicklist, quicklist->head, node);
    }
    quicklist->count++;
    quicklist->head->count++;
    return (orig_head != quicklist->head);
}

quicklistPushHead 函数的执行流程，先判断 quicklist 的 head 节点是否可以插入数据，如果可以插入则使用 ziplist 的接口进行插入，否则就新建 quicklistNode 节点进行插入。

函数的入参是待插入的 quicklist，还有需要插入的值 value 以及他的大小 sz。

函数的返回值为 int，0 表示没有新建 head，1 表示新建了 head。 quicklistPushHead 执行流程，如下图所示：

列表类型使用-插入流程图.png

删除功能源码分析

quicklist 元素删除分为两种情况：单一元素删除和区间元素删除，它们都位于 src/quicklist.c 文件中。

单一元素删除

单一元素的删除函数是 quicklistDelEntry，源码如下：

1
2
3
4
5
6
7
8
void quicklistDelEntry(quicklistIter *iter, quicklistEntry *entry) {
    quicklistNode *prev = entry->node->prev;
    quicklistNode *next = entry->node->next;
    // 删除指定位置的元素
    int deleted_node = quicklistDelIndex((quicklist *)entry->quicklist,
                                         entry->node, &entry->zi);
    //...
}

可以看出 quicklistDelEntry 函数的底层，依赖 quicklistDelIndex 函数进行元素删除。

区间元素删除

区间元素删除的函数是 quicklistDelRange，源码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
// start 表示开始删除的下标，count 表示要删除的个数
int quicklistDelRange(quicklist *quicklist, const long start,
                      const long count) {
    if (count <= 0)
        return 0;
    unsigned long extent = count; 
    if (start >= 0 && extent > (quicklist->count - start)) {
        // 删除的元素个数大于已有元素
        extent = quicklist->count - start;
    } else if (start < 0 && extent > (unsigned long)(-start)) {
        // 删除指定的元素个数
        extent = -start; /* c.f. LREM -29 29; just delete until end. */
    }
    //...
    // extent 为剩余需要删除的元素个数，
    while (extent) {
        // 保存下个 quicklistNode，因为本节点可能会被删除
        quicklistNode *next = node->next;
        unsigned long del;
        int delete_entire_node = 0;
        if (entry.offset == 0 && extent >= node->count) {
            // 删除整个 quicklistNode
            delete_entire_node = 1;
            del = node->count;
        } else if (entry.offset >= 0 && extent >= node->count) {
           // 删除本节点的所有元素
            del = node->count - entry.offset;
        } else if (entry.offset < 0) {
            // entry.offset<0 表示从后向前，相反则表示从前向后剩余的元素个数
            del = -entry.offset;
            if (del > extent)
                del = extent;
        } else {
            // 删除本节点部分元素
            del = extent;
        }
        D("[%ld]: asking to del: %ld because offset: %d; (ENTIRE NODE: %d), "
          "node count: %u",
          extent, del, entry.offset, delete_entire_node, node->count);
        if (delete_entire_node) {
            __quicklistDelNode(quicklist, node);
        } else {
            quicklistDecompressNodeForUse(node);
            node->zl = ziplistDeleteRange(node->zl, entry.offset, del);
            quicklistNodeUpdateSz(node);
            node->count -= del;
            quicklist->count -= del;
            quicklistDeleteIfEmpty(quicklist, node);
            if (node)
                quicklistRecompressOnly(quicklist, node);
        }
        // 剩余待删除元素的个数
        extent -= del;
        // 下个 quicklistNode
        node = next;
        // 从下个 quicklistNode 起始位置开始删除
        entry.offset = 0;
    }
    return 1;
}

从上面代码可以看出，quicklist 在区间删除时，会先找到 start 所在的 quicklistNode，计算删除的元素是否小于要删除的 count，如果不满足删除的个数，则会移动至下一个 quicklistNode 继续删除，依次循环直到删除完成为止。

quicklistDelRange 函数的返回值为 int 类型，当返回 1 时表示成功的删除了指定区间的元素，返回 0 时表示没有删除任何元素。

更多源码

除了上面介绍的几个常用函数之外，还有一些更多的函数，例如：

  • quicklistCreate：创建 quicklist；
  • quicklistInsertAfter：在某个元素的后面添加数据；
  • quicklistInsertBefore：在某个元素的前面添加数据；
  • quicklistPop：取出并删除列表的第一个或最后一个元素；
  • quicklistReplaceAtIndex：替换某个元素。

性能优势

quicklist有自己的优点， 也有缺点， 对于使用者来说， 其使用体验类似于线性数据结构， list作为最传统的双链表， 结点通过指针持有数据， 指针字段会耗费大量内存。 ziplist解决了耗费内存这个问题。 但引入了新的问题: 每次写操作整个ziplist的内存都需要重分配。 quicklist在两者之间做了一个平衡。 并且使用者可以通过自定义quicklist.fill， 根据实际业务情况， 经验主义调参。

为什么 ziplist 特别省内存

只有理解上面的Entry结构，我们才会真正理解ZipList为什么是特别节省内存的数据结构。

ziplist节省内存是相对于普通的list来说的，如果是普通的数组，那么它每个元素占用的内存是一样的且取决于最大的那个元素（很明显它是需要预留空间的）；

所以ziplist在设计时就很容易想到要尽量让每个元素按照实际的内容大小存储，所以增加encoding字段，针对不同的encoding来细化存储大小；

这时候还需要解决的一个问题是遍历元素时如何定位下一个元素呢？在普通数组中每个元素定长，所以不需要考虑这个问题；但是ziplist中每个data占据的内存不一样，所以为了解决遍历，需要增加记录上一个元素的length，所以增加了prelen字段。

结合了双向链表和ziplist的优点，quicklist就应运而生了。

集合（Set）：独步天下的独行侠

然后，我们的集合大师登场了！集合就像是江湖中的独行侠，天生不爱重复。他擅长处理那些独一无二的数据，无论是要去重还是计算交集并集，集合都能完美胜任。正是他那种独特的个性，让他在数据江湖中独步天下。

集合类型 (Set) 是一个无序并唯一的键值集合。之所以说集合类型是一个无序集合，是因为它的存储顺序不会按照插入的先后顺序进行存储。

集合类型和列表类型的区别如下：

  • 列表可以存储重复元素，集合只能存储非重复元素；
  • 列表是按照元素的先后顺序存储元素的，而集合则是无序方式存储元素的。

img

如何使用？

命令行操作方式

命令 介绍
SADD key member1 member2 … 向指定集合添加一个或多个元素
SMEMBERS key 获取指定集合中的所有元素
SCARD key 获取指定集合的元素数量
SISMEMBER key member 判断指定元素是否在指定集合中
SINTER key1 key2 … 获取给定所有集合的交集
SINTERSTORE destination key1 key2 … 将给定所有集合的交集存储在 destination 中
SUNION key1 key2 … 获取给定所有集合的并集
SUNIONSTORE destination key1 key2 … 将给定所有集合的并集存储在 destination 中
SDIFF key1 key2 … 获取给定所有集合的差集
SDIFFSTORE destination key1 key2 … 将给定所有集合的差集存储在 destination 中
SPOP key count 随机移除并获取指定集合中一个或多个元素
SRANDMEMBER key count 随机获取指定集合中指定数量的元素

更多 Redis Set 命令以及详细使用指南，请查看 Redis 官网对应的介绍。

代码操作方式（采用Go-Redis V8 版本）

常用方法:

  • SAdd():添加元素
  • SPop():随机获取一个元素
  • SRem():删除集合里指定的值
  • SSMembers():获取所有成员
  • SIsMember():判断元素是否在集合中
  • SCard():获取集合元素个数
  • SUnion():并集,SDiff():差集,SInter():交集

Tips：集合数据的特征，元素不能重复保持唯一性, 元素无序不能使用索引(下标)操作

简单示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
func setExample(rdb *redis.Client, ctx context.Context) {
	// 集合元素缓存设置
	keyname := "Program"
	mem := []string{"C", "Golang", "C++", "C#", "Java", "Delphi", "Python", "Golang"}
	// //由于Golang已经被添加到Program集合中，所以重复添加时无效的
	for _, v := range mem {
		rdb.SAdd(ctx, keyname, v)
	}

	// SCard() 获取集合元素个数
	total, _ := rdb.SCard(ctx, keyname).Result()
	fmt.Println("golang集合成员个数: ", total)

	// SPop() 随机获取一个元素 （无序性，是随机的）
	val1, _ := rdb.SPop(ctx, keyname).Result()
	// SPopN()  随机获取多个元素.
	val2, _ := rdb.SPopN(ctx, keyname, 2).Result()

	// SSMembers() 获取所有成员
	val3, _ := rdb.SMembers(ctx, keyname).Result()
	fmt.Printf("随机获取一个元素: %v , 随机获取多个元素: %v \n所有成员: %v\n", val1, val2, val3)

	// SIsMember() 判断元素是否在集合中
	exists, _ := rdb.SIsMember(ctx, keyname, "golang").Result()
	if exists {
		fmt.Println("golang 存在 Program 集合中.") // 注意:我们存入的是Golang而非golang
	} else {
		fmt.Println("golang 不存在 Program 集合中.")
	}

	// SUnion():并集, SDiff():差集, SInter():交集
	rdb.SAdd(ctx, "setA", "a", "b", "c", "d")
	rdb.SAdd(ctx, "setB", "a", "d", "e", "f")

	//并集
	union, _ := rdb.SUnion(ctx, "setA", "setB").Result()
	fmt.Println("并集", union)

	//差集
	diff, _ := rdb.SDiff(ctx, "setA", "setB").Result()
	fmt.Println("差集", diff)

	//交集
	inter, _ := rdb.SInter(ctx, "setA", "setB").Result()
	fmt.Println("交集", inter)

  // 删除集合中指定元素(返回成功)
  n, _ := rdb.SRem(ctx, "setB", "a", "f").Result()
  fmt.Println("已成功删除元素的个数: ",n)
}

内部实现

集合类型是由 intset (整数集合) 或 hashtable (普通哈希表) 组成的。当集合类型以 hashtable 存储时，哈希表的 key 为要插入的元素值，而哈希表的 value 则为 Null，如下图所示：

集合Set-hashtable.png

当集合中所有的值都为整数时，Redis 会使用 intset 结构来存储。

当发生以下两种情况时，会导致集合类型使用 hashtable 而非 intset 存储：

  1. 当元素的个数超过一定数量时，默认是 512 个，该值可通过命令 set-max-intset-entries xxx 来配置。
  2. 当元素为非整数时，集合将会使用 hashtable 来存储。

数据类型

整数集合（intset）是集合键的底层实现之一： 当一个集合只包含整数值元素， 并且这个集合的元素数量不多时， Redis 就会使用整数集合作为集合键的底层实现。

intset

先看源码结构：

1
2
3
4
5
6
7
8
9
10
11
12
typedef struct intset {

    // 编码方式
    uint32_t encoding;

    // 集合包含的元素数量
    uint32_t length;

    // 保存元素的数组
    int8_t contents[];

} intset;
  • encoding 表示编码方式，的取值有三个：INTSET_ENC_INT16, INTSET_ENC_INT32, INTSET_ENC_INT64
  • length 代表其中存储的整数的个数
  • contents 指向实际存储数值的连续内存区域, 就是一个数组；整数集合的每个元素都是 contents 数组的一个数组项（item），各个项在数组中按值得大小从小到大有序排序，且数组中不包含任何重复项。

虽然 intset 结构将 contents 属性声明为 int8_t 类型的数组，但实际上 contents 数组并不保存任何 int8_t 类型的值，contents 数组的真正类型取决于 encoding 属性的值：如果 encoding 属性的值为 INTSET_ENC_INT16 ， 那么 contents 就是一个 int16_t 类型的数组， 数组里的每个项都是一个 int16_t 类型的整数值 （最小值为 -32,768 ，最大值为 32,767 ）。下图是一个包含五个 int16_t 类型整数值的整数集合。

img

img

可以看到，content数组里面每个元素的数据类型是由encoding来决定的，那么如果原来的数据类型是int16, 当我们再插入一个int32类型的数据时怎么办呢？

每当我们要将一个新元素添加到整数集合里面， 并且新元素的类型比整数集合现有所有元素的类型都要长时， 整数集合需要先进行升级（upgrade）， 然后才能将新元素添加到整数集合里面。

升级整数集合并添加新元素共分为三步进行：

  • 根据新元素的类型， 扩展整数集合底层数组的空间大小， 并为新元素分配空间。
  • 将底层数组现有的所有元素都转换成与新元素相同的类型， 并将类型转换后的元素放置到正确的位上， 而且在放置元素的过程中， 需要继续维持底层数组的有序性质不变。
  • 将新元素添加到底层数组里面。

整数集合不支持降级操作， 一旦对数组进行了升级， 编码就会一直保持升级后的状态。

源码分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/* 
 * 添加元素到集合
 * 如果当前值已经存在，则返回 0 不作任何处理，否则就添加该元素，并返回 1。
 */
int setTypeAdd(robj *subject, sds value) {
    long long llval;
    if (subject->encoding == OBJ_ENCODING_HT) { // 字典类型
        dict *ht = subject->ptr;
        dictEntry *de = dictAddRaw(ht,value,NULL);
        if (de) {
            // 把 value 作为字典到 key，将 Null 作为字典到 value，将元素存入到字典
            dictSetKey(ht,de,sdsdup(value));
            dictSetVal(ht,de,NULL);
            return 1;
        }
    } else if (subject->encoding == OBJ_ENCODING_INTSET) { // inset 数据类型
        if (isSdsRepresentableAsLongLong(value,&llval) == C_OK) {
            uint8_t success = 0;
            subject->ptr = intsetAdd(subject->ptr,llval,&success);
            if (success) {
                // 超过 inset 的最大存储数量，则使用字典类型存储
                if (intsetLen(subject->ptr) > server.set_max_intset_entries)
                    setTypeConvert(subject,OBJ_ENCODING_HT);
                return 1;
            }
        } else {
            // 转化为整数类型失败，使用字典类型存储
            setTypeConvert(subject,OBJ_ENCODING_HT);

            serverAssert(dictAdd(subject->ptr,sdsdup(value),NULL) == DICT_OK);
            return 1;
        }
    } else {
        // 未知编码(类型)
        serverPanic("Unknown set encoding");
    }
    return 0;
}

以上这些代码验证了，我们上面所说的内容，当元素都为整数并且元素的个数没有到达设置的最大值时，键值的存储使用的是 intset 的数据结构，反之到元素超过了一定的范围，又或者是存储的元素为非整数时，集合会选择使用 hashtable 的数据结构进行存储。

性能优势

对于小集合使用intset来存储，主要的原因是节省内存。特别是当存储的元素个数较少的时候，dict所带来的内存开销要大得多（包含两个哈希表、链表指针以及大量的其它元数据）。所以，当存储大量的小集合而且集合元素都是数字的时候，用intset能节省下一笔可观的内存空间。

实际上，从时间复杂度上比较，intset的平均情况是没有dict性能高的。以查找为例，intset是O(log n)的，而dict可以认为是O(1)的。但是，由于使用intset的时候集合元素个数比较少，所以这个影响不大。

有序集合（Sorted Set）：运筹帷幄的智者

最后一位出场的是有序集合，这位兄弟简直是个运筹帷幄的智者。他不仅有集合哥的特质，还多了一项绝技：排序。每个成员都有一个分数，他可以根据分数将成员排序，非常适合排行榜、评分系统等场景。

有序集合类型 (Sorted Set) 相比于集合类型多了一个排序属性 score（分值），对于有序集合 ZSet 来说，每个存储元素相当于有两个值组成的，一个是有序结合的元素值，一个是排序值。有序集合的存储元素值也是不能重复的，但分值是可以重复的。

当我们把学生的成绩存储在有序集合中时，它的存储结构如下图所示：

学生存储值.png

如何使用？

命令行操作方式

命令 介绍
ZADD key score1 member1 score2 member2 … 向指定有序集合添加一个或多个元素
ZCARD KEY 获取指定有序集合的元素数量
ZSCORE key member 获取指定有序集合中指定元素的 score 值
ZINTERSTORE destination numkeys key1 key2 … 将给定所有有序集合的交集存储在 destination 中，对相同元素对应的 score 值进行 SUM 聚合操作，numkeys 为集合数量
ZUNIONSTORE destination numkeys key1 key2 … 求并集，其它和 ZINTERSTORE 类似
ZDIFF destination numkeys key1 key2 … 求差集，其它和 ZINTERSTORE 类似
ZRANGE key start end 获取指定有序集合 start 和 end 之间的元素（score 从低到高）
ZREVRANGE key start end 获取指定有序集合 start 和 end 之间的元素（score 从高到底）
ZREVRANK key member 获取指定有序集合中指定元素的排名(score 从大到小排序)

更多 Redis Sorted Set 命令以及详细使用指南，请查看 Redis 官网对应的介绍。

代码操作方式（采用Go-Redis V8 版本）

常用方法:

  • ZAdd():添加元素
  • ZIncrBy():增加元素分值
  • ZRange()、ZRevRange():获取根据score排序后的数据段
  • ZRangeByScore()、ZRevRangeByScore():获取score过滤后排序的数据段
  • ZCard():获取元素个数
  • ZCount():获取区间内元素个数
  • ZScore():获取元素的score
  • ZRank()、ZRevRank():获取某个元素在集合中的排名
  • ZRem():删除元素
  • ZRemRangeByRank():根据排名来删除
  • ZRemRangeByScore():根据分值区间来删除

简单示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
func zsetExample(rdb *redis.Client, ctx context.Context) {
	// 有序集合成员与分数设置
	// zSet类型需要使用特定的类型值*redis.Z，以便作为排序使用
	lang := []*redis.Z{
		&redis.Z{Score: 90.0, Member: "Golang"},
		&redis.Z{Score: 98.0, Member: "Java"},
		&redis.Z{Score: 95.0, Member: "Python"},
		&redis.Z{Score: 97.0, Member: "JavaScript"},
		&redis.Z{Score: 99.0, Member: "C/C++"},
	}
	//插入ZSet类型
	num, err := rdb.ZAdd(ctx, "language_rank", lang...).Result()
	if err != nil {
		fmt.Printf("zadd failed, err:%v\n", err)
		return
	}
	fmt.Printf("zadd %d succ.\n", num)

	// 将ZSet中的某一个元素顺序值增加: 把Golang的分数加10
	newScore, err := rdb.ZIncrBy(ctx, "language_rank", 10.0, "Golang").Result()
	if err != nil {
		fmt.Printf("zincrby failed, err:%v\n", err)
		return
	}
	fmt.Printf("Golang's score is %f now.\n", newScore)

	// 根据分数排名取出元素:取分数最高的3个
	ret, err := rdb.ZRevRangeWithScores(ctx, "language_rank", 0, 2).Result()
	if err != nil {
		fmt.Printf("zrevrange failed, err:%v\n", err)
		return
	}
	fmt.Printf("zsetKey前3名热度的是: %v\n,Top 3 的 Memeber 与 Score 是:\n", ret)
	for _, z := range ret {
		fmt.Println(z.Member, z.Score)
	}

	// ZRangeByScore()、ZRevRangeByScore():获取score过滤后排序的数据段
	// 此处表示取95~100分的
	op := redis.ZRangeBy{
		Min: "95",
		Max: "100",
	}
	ret, err = rdb.ZRangeByScoreWithScores(ctx, "language_rank", &op).Result()
	if err != nil {
		fmt.Printf("zrangebyscore failed, err:%v\n", err)
		return
	}
	// 输出全部成员及其score分数
	fmt.Println("language_rank 键存储的全部元素:")
	for _, z := range ret {
		fmt.Println(z.Member, z.Score)
	}
}

内部实现

有序集合是由 ziplist (压缩列表) 或 skiplist (跳跃表) 组成的。

数据类型

zskiplist

跳跃表（zskiplist）是一种有序数据结构， 它通过在每个节点中维持多个指向其他节点的指针， 从而达到快速访问节点的目的。

跳跃表支持平均 O(\log N) 最坏 O(N) 复杂度的节点查找， 还可以通过顺序性操作来批量处理节点。

Redis 使用跳跃表作为有序集合键的底层实现之一： 如果一个有序集合包含的元素数量比较多，又或者有序集合中元素的成员（member）是比较长的字符串时，Redis 就会使用跳跃表来作为有序集合键的底层实现。

跳跃表的实现原理：

对于于一个单链表来讲，即便链表中存储的数据是有序的，如果我们要想在其中查找某个数据，也只能从头到尾遍历链表。这样查找效率就会很低，时间复杂度会很高，是 O(n)。比如查找12，需要7次查找

img

如果我们增加如下两级索引，那么它搜索次数就变成了3次

img

源码分析

跳跃表节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
typedef struct zskiplistNode {

    // 后退指针
    struct zskiplistNode *backward;

    // 分值
    double score;

    // 成员对象
    robj *obj;

    // 层
    struct zskiplistLevel {

        // 前进指针
        struct zskiplistNode *forward;

        // 跨度
        unsigned int span;

    } level[];

} zskiplistNode;

层

跳跃表节点的 level 数组可以包含多个元素， 每个元素都包含一个指向其他节点的指针， 程序可以通过这些层来加快访问其他节点的速度， 一般来说， 层的数量越多， 访问其他节点的速度就越快。

每次创建一个新跳跃表节点的时候， 程序都根据幂次定律 （power law，越大的数出现的概率越小） 随机生成一个介于 1 和 32 之间的值作为 level 数组的大小， 这个大小就是层的“高度”。

下图分别展示了三个高度为 1 层、 3 层和 5 层的节点， 因为 C 语言的数组索引总是从 0 开始的， 所以节点的第一层是 level[0] ， 而第二层是 level[1] ，以此类推。

img

跨度

层的跨度（level[i].span 属性）用于记录两个节点之间的距离：两个节点之间的跨度越大， 它们相距得就越远。指向 NULL 的所有前进指针的跨度都为 0 ， 因为它们没有连向任何节点。

初看上去， 很容易以为跨度和遍历操作有关， 但实际上并不是这样 —— 遍历操作只使用前进指针就可以完成了， 跨度实际上是用来计算排位（rank）的： 在查找某个节点的过程中， 将沿途访问过的所有层的跨度累计起来， 得到的结果就是目标节点在跳跃表中的排位。

举个例子， 下图用虚线标记了在跳跃表中查找分值为 3.0 、 成员对象为 o3 的节点时， 沿途经历的层： 查找的过程只经过了一个层， 并且层的跨度为 3 ， 所以目标节点在跳跃表中的排位为 3 。

后退指针

节点的后退指针（backward 属性）用于从表尾向表头方向访问节点： 跟可以一次跳过多个节点的前进指针不同， 因为每个节点只有一个后退指针， 所以每次只能后退至前一个节点。

下图用虚线展示了如果从表尾向表头遍历跳跃表中的所有节点： 程序首先通过跳跃表的 tail 指针访问表尾节点， 然后通过后退指针访问倒数第二个节点， 之后再沿着后退指针访问倒数第三个节点， 再之后遇到指向 NULL 的后退指针， 于是访问结束。

img

分值和成员

节点的分值（score 属性）是一个 double 类型的浮点数， 跳跃表中的所有节点都按分值从小到大来排序。

节点的成员对象（obj 属性）是一个指针， 它指向一个字符串对象， 而字符串对象则保存着一个 SDS 值。

在同一个跳跃表中， 各个节点保存的成员对象必须是唯一的， 但是多个节点保存的分值却可以是相同的： 分值相同的节点将按照成员对象在字典序中的大小来进行排序， 成员对象较小的节点会排在前面（靠近表头的方向）， 而成员对象较大的节点则会排在后面（靠近表尾的方向）。

举个例子， 在下图所示的跳跃表中， 三个跳跃表节点都保存了相同的分值 10086.0 ， 但保存成员对象 o1 的节点却排在保存成员对象 o2 和 o3 的节点之前， 而保存成员对象 o2 的节点又排在保存成员对象 o3 的节点之前， 由此可见， o1 、 o2 、 o3 三个成员对象在字典中的排序为 o1 <= o2 <= o3 。

img

跳跃表

虽然仅靠多个跳跃表节点就可以组成一个跳跃表， 如下图所示。

img

但通过使用一个 zskiplist 结构来持有这些节点， 程序可以更方便地对整个跳跃表进行处理， 比如快速访问跳跃表的表头节点和表尾节点， 又或者快速地获取跳跃表节点的数量（也即是跳跃表的长度）等信息， 如下图所示。

img

zskiplist 结构的定义如下：

1
2
3
4
5
6
7
8
9
10
11
typedef struct zskiplist {
    // 表头节点和表尾节点    
    struct zskiplistNode *header, *tail;
    
    // 表中节点的数量    
    unsigned long length;
    
    // 表中层数最大的节点的层数    
    int level;
    
} zskiplist;
  • header 和 tail 指针分别指向跳跃表的表头和表尾节点， 通过这两个指针， 程序定位表头节点和表尾节点的复杂度为 O(1) 。
  • 通过使用 length 属性来记录节点的数量， 程序可以在 O(1) 复杂度内返回跳跃表的长度。
  • level 属性则用于在 O(1) 复杂度内获取跳跃表中层高最大的那个节点的层数量， 注意表头节点的层高并不计算在内。

性能优势

为什么是跳跃表？而非红黑树？

因为跳跃表的性能和红黑树基本相近，但却比红黑树更好实现，所有 Redis 的有序集合会选用跳跃表来实现存储。

kiplist与平衡树、哈希表的比较

来源于：https://www.jianshu.com/p/8ac45fd01548

skiplist和各种平衡树（如AVL、红黑树等）的元素是有序排列的，而哈希表不是有序的。因此，在哈希表上只能做单个key的查找，不适宜做范围查找。所谓范围查找，指的是查找那些大小在指定的两个值之间的所有节点。

在做范围查找的时候，平衡树比skiplist操作要复杂。在平衡树上，我们找到指定范围的小值之后，还需要以中序遍历的顺序继续寻找其它不超过大值的节点。如果不对平衡树进行一定的改造，这里的中序遍历并不容易实现。而在skiplist上进行范围查找就非常简单，只需要在找到小值之后，对第1层链表进行若干步的遍历就可以实现。

平衡树的插入和删除操作可能引发子树的调整，逻辑复杂，而skiplist的插入和删除只需要修改相邻节点的指针，操作简单又快速。

从内存占用上来说，skiplist比平衡树更灵活一些。一般来说，平衡树每个节点包含2个指针（分别指向左右子树），而skiplist每个节点包含的指针数目平均为1/(1-p)，具体取决于参数p的大小。如果像Redis里的实现一样，取p=1/4，那么平均每个节点包含1.33个指针，比平衡树更有优势。

查找单个key，skiplist和平衡树的时间复杂度都为O(log n)，大体相当；而哈希表在保持较低的哈希值冲突概率的前提下，查找时间复杂度接近O(1)，性能更高一些。所以我们平常使用的各种Map或dictionary结构，大都是基于哈希表实现的。

从算法实现难度上来比较，skiplist比平衡树要简单得多。

应用场景

通过学习上面的内容，我们已经非常了解这五种数据结构的基本使用和内部原理了，那么在实际生产中到底要怎么用，每种数据结构的使用场景是什么，我们来看一下。

当然！下面是关于Redis五种基础数据结构的应用场景的详细介绍：

字符串（String）

应用场景：

  • 缓存数据：字符串是缓存数据的最常用数据结构，比如缓存用户信息、产品详情等。
  • 计数器：使用INCR、DECR等命令，可以轻松实现各种计数功能，如网站访问量、点赞数等。
  • 会话存储：将用户会话信息存储在字符串中，便于快速读取和更新。

示例：

1
2
3
4
5
6
7
8
9
# 缓存用户信息
SET user:1001 "John Doe"

# 计数器：增加网站访问量
INCR site:views

# 会话存储：设置和获取用户会话
SET session:12345 "user_id:1001"
GET session:12345

哈希（Hash）

应用场景：

  • 存储对象：哈希非常适合存储具有多个字段的对象，如用户信息、商品信息等。
  • 轻量级的数据存储：可以存储相对较小的数据，如配置项、状态信息等。
  • 减少内存消耗：对于多字段数据，使用哈希可以比字符串节省内存。

示例：

1
2
3
4
5
6
7
8
# 存储用户信息
HSET user:1001 name "John Doe" age 30 email "john@example.com"

# 获取用户的某个字段
HGET user:1001 name

# 获取用户的所有字段
HGETALL user:1001

列表（List）

应用场景：

  • 任务队列：列表可以用作任务队列，支持从两端插入和删除元素。
  • 消息队列：可以用列表来实现简单的消息队列，保证消息的顺序性。
  • 日志存储：将日志条目存储在列表中，便于按时间顺序追加和读取。

示例：

1
2
3
4
5
6
7
8
9
10
# 添加任务到队列
LPUSH task_queue "Task1"
RPUSH task_queue "Task2"

# 从队列获取任务
LPOP task_queue

# 存储日志条目
RPUSH logs "Log entry 1"
RPUSH logs "Log entry 2"

集合（Set）

应用场景：

  • 去重：集合天生不允许重复元素，非常适合用于去重场景。
  • 标签管理：适合存储用户标签、商品标签等。
  • 社交网络：可以用来管理好友关系、共同兴趣等。

示例：

1
2
3
4
5
6
7
8
# 存储用户标签
SADD user:1001:tags "redis" "database" "nosql"

# 判断是否存在某标签
SISMEMBER user:1001:tags "redis"

# 获取所有标签
SMEMBERS user:1001:tags

有序集合（Sorted Set）

应用场景：

  • 排行榜：有序集合非常适合实现排行榜，按分数排序展示前N名用户。
  • 带权重的数据存储：适用于需要按权重排序的数据，如评分系统。
  • 延迟队列：可以根据分数（时间戳）实现延迟任务队列。

示例：

1
2
3
4
5
6
7
8
# 添加用户到排行榜
ZADD leaderboard 100 "Alice" 200 "Bob"

# 获取排行榜前N名
ZRANGE leaderboard 0 1 WITHSCORES

# 获取某用户的排名
ZRANK leaderboard "Alice"

通过这些应用场景的介绍，相信你对Redis五种基础数据结构的使用有了更深入的了解。每种数据结构都有其独特的优势和适用场景，根据具体需求选择合适的数据结构可以大大提升系统的性能和效率。

总结

Redis数据结构五兄弟，各个身怀绝技，各有千秋。无论是字符串的快剑手、哈希的万花筒、列表的快马、集合的独行侠，还是有序集合的智者，他们都在数据江湖中扮演着不可或缺的角色。希望这篇介绍能让你对Redis的五种基础数据结构有一个更生动形象的了解。让我们一起在Redis的世界中，成为数据江湖的侠客吧！

哈哈，抽象的标题、抽象的开头和抽象的结尾，笔者实在是懒得去想这些东西要怎么写了，但是又想搞一篇有趣的文章，于是去请教了万能的人工智能 ChatGPt，还可以吧，描述很传神。

这篇博客真是史诗级的长度，光是看标题就看的眼花缭乱，本来只看了技术摘抄里的文章，觉得好像没有多少内容，还在感慨昨天没学什么东西。结果在搜索更多的资料时发现看的全是概述，重要的内容还没学，于是边学边写，太夸张了，不过还是学到了不少东西的。

在正式学习 Redis 底层之前，一直觉得 Redis 快就是因为它被存放在内存里，现在发现其实它每一处的设计都有考虑性能和效率。

什么？你问为什么今天没有记录什么有趣的东西。

实在是因为最近一直都在闷着头学东西，也就没怎么去关心实习方面的事，不找实习，连烦恼都消失不见了。

终于知道为什么大家都讨厌HR了，老小子耍我，说要让技术经理加我的微信跟我面试，结果到现在都没有，骗子不得好死。还好我本来就没有抱希望。

不过昨天我的好舍友说把我的简历发给他的Leader看了，说不定能帮我找一个实习，不过以我的狗运气，应该不太可能。还是沉下心来学习吧。

参考

Redis数据结构的基本使用和内部原理

数据结构的命令行用法

数据结构的Go 语言操作

Redis 底层数据结构的概述

Redis 底层数据结构的详解

Redis 底层数据结构的详解 2

dict详解

SDS详解

robj详解

ziplist详解

quicklist详解

skiplist详解

intset详解