不断的学习,我们才能不断的前进
一个好的程序员是那种过单行线马路都要往两边看的人

1. 简单动态字符串(SDS)

Redis 没有使用C语言的字符串,而是自己构建了一种名为简单动态字符串(simple dynamic string,SDS)的抽象类型, 并将 SDS 用作 Redis 的默认字符串表示。

在Redis里面C语言的字符串,只会用在不需要对字符串修改的地方,比如打印日志。

SDS 除了用来保存字符串的值外,还可以用做缓冲区:AOF 持久化模块中的 AOF 缓冲区, 以及客户端状态中的输入缓冲区, 都是由 SDS 实现的。

1.1 SDS 定义

SDS的值结构:

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

SDS 保存C语言字符串的风格,最后一个字符是空字符,不计算在len里面,所以SDS的长度为:len+free+1

1.2 SDS vs C字符串

C字符串用字符数组来存储,没有保存字符串的长度信息。

区别:

C 字符串 SDS
获取字符串长度的复杂度为 O(N) 。 获取字符串长度的复杂度为 O(1) 。
API 是不安全的,可能会造成缓冲区溢出。 API 是安全的,不会造成缓冲区溢出。
修改字符串长度 N 次必然需要执行 N 次内存重分配。 修改字符串长度 N 次最多需要执行 N 次内存重分配。
只能保存文本数据。 可以保存文本或者二进制数据。
可以使用所有 <string.h> 库中的函数。 可以使用一部分 <string.h> 库中的函数。

SDS 设计的原因:

1.2.1 常数时间复杂度

SDS存储来字符串的长度,所以只要O(1) 时间复杂度就可获得。设置和更新 SDS 长度的工作是由 SDS 的 API 在执行时自动完成的, 使用 SDS 无须进行任何手动修改长度的工作。

1.2.2 避免缓冲区溢出

使用C字符串的话会容易造成缓冲区溢出(buffer overflow)。

例如:假设程序里有两个在内存中紧邻着的 C 字符串 s1s2 , 其中 s1 保存了字符串 "Redis" , 而 s2 则保存了字符串 "MongoDB",如果将 s1 的内容修改为 "Redis Cluster" , 但粗心的他却忘了为 s1 分配足够的空间, 那么在执行之后, s1 的数据将溢出到 s2 所在的空间中, 导致 s2 保存的内容被意外地修改。

而SDS 的空间分配策略完全杜绝了发生缓冲区溢出的可能性: 当 SDS API 需要对 SDS 进行修改时, API 会先检查 SDS 的空间是否满足修改所需的要求, 如果不满足的话, API 会自动将 SDS 的空间扩展至执行修改所需的大小, 然后才执行实际的修改操作, 所以使用 SDS 既不需要手动修改 SDS 的空间大小, 也不会出现前面所说的缓冲区溢出问题。

1.2.3 减少字符串时带来的内存重分配次数

C 字符串并不记录自身的长度,所以每次增长或者缩短一个 C 字符串, 程序都总要对保存这个 C 字符串的数组进行一次内存重分配操作:

  • 增长字符串:在执行这个操作之前, 程序需要先通过内存重分配来扩展底层数组的空间大小 —— 如果忘了这一步就会产生缓冲区溢出。
  • 缩短字符串:在执行这个操作之后, 程序需要通过内存重分配来释放字符串不再使用的那部分空间 —— 如果忘了这一步就会产生内存泄漏。

内存重分配涉及复杂的算法, 并且可能需要执行系统调用, 所以它通常是一个比较耗时的操作。

1. 空间预分配

空间预分配用于优化 SDS 的字符串增长操作: 当 SDS 的 API 对一个 SDS 进行修改, 并且需要对 SDS 进行空间扩展的时候, 程序不仅会为 SDS 分配修改所必须要的空间, 还会为 SDS 分配额外的未使用空间。

分配规则:

  • 如果对 SDS 进行修改之后, SDS 的长度(也即是 len 属性的值)将小于 1 MB ,那么程序分配和 len 属性同样大小的未使用空间, 这时 SDS len 属性的值将和 free 属性的值相同。
  • 如果对 SDS 进行修改之后, SDS 的长度将大于等于 1 MB , 那么程序会分配 1 MB 的未使用空间。

在扩展 SDS 空间之前, SDS API 会先检查未使用空间是否足够, 如果足够的话, API 就会直接使用未使用空间, 而无须执行内存重分配。

通过空间预分配策略, Redis 可以减少连续执行字符串增长操作所需的内存重分配次数。

2. 惰性空间释放

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

1.2.4 二进制安全

C字符串除了末尾字符外,其他位置不能包含空字符。所以使得 C 字符串只能保存文本数据, 而不能保存像图片、音频、视频、压缩文件这样的二进制数据。

SDS 的 API 都是二进制安全的(binary-safe): 所有 SDS API 都会以处理二进制的方式来处理 SDS 存放在 buf 数组里的数据, 程序不会对其中的数据做任何限制、过滤、或者假设 。

SDS 通过len 属性的值而不是空字符来判断字符串是否结束。

1.2.5 兼容部分 C 字符串函数

虽然 SDS 的 API 都是二进制安全的, 但它们一样遵循 C 字符串以空字符结尾的惯例: 这些 API 总会将 SDS 保存的数据的末尾设置为空字符, 并且总会在为 buf 数组分配空间时多分配一个字节来容纳这个空字符, 这是为了让那些保存文本数据的 SDS 可以重用一部分 <string.h> 库定义的函数。

1. 3 SDS API

函数 作用 时间复杂度
sdsnew 创建一个包含给定 C 字符串的 SDS 。 O(N) , N 为给定 C 字符串的长度。
sdsempty 创建一个不包含任何内容的空 SDS 。 O(1)
sdsfree 释放给定的 SDS 。 O(1)
sdslen 返回 SDS 的已使用空间字节数。 这个值可以通过读取 SDS 的 len 属性来直接获得, 复杂度为 O(1) 。
sdsavail 返回 SDS 的未使用空间字节数。 这个值可以通过读取 SDS 的 free 属性来直接获得, 复杂度为 O(1) 。
sdsdup 创建一个给定 SDS 的副本(copy)。 O(N) , N 为给定 SDS 的长度。
sdsclear 清空 SDS 保存的字符串内容。 因为惰性空间释放策略,复杂度为 O(1) 。
sdscat 将给定 C 字符串拼接到 SDS 字符串的末尾。 O(N) , N 为被拼接 C 字符串的长度。
sdscatsds 将给定 SDS 字符串拼接到另一个 SDS 字符串的末尾。 O(N) , N 为被拼接 SDS 字符串的长度。
sdscpy 将给定的 C 字符串复制到 SDS 里面, 覆盖 SDS 原有的字符串。 O(N) , N 为被复制 C 字符串的长度。
sdsgrowzero 用空字符将 SDS 扩展至给定长度。 O(N) , N 为扩展新增的字节数。
sdsrange 保留 SDS 给定区间内的数据, 不在区间内的数据会被覆盖或清除。 O(N) , N 为被保留数据的字节数。
sdstrim 接受一个 SDS 和一个 C 字符串作为参数, 从 SDS 左右两端分别移除所有在 C 字符串中出现过的字符。 O(M*N) , M 为 SDS 的长度, N 为给定 C 字符串的长度。
sdscmp 对比两个 SDS 字符串是否相同。 O(N) , N 为两个 SDS 中较短的那个 SDS 的长度。

2. 链表

链表提供了高效的节点重排能力, 以及顺序性的节点访问方式, 并且可以通过增删节点来灵活地调整链表的长度。

integers 列表键的底层实现就是一个链表, 链表中的每个节点都保存了一个整数值。

除了链表键之外, 发布与订阅、慢查询、监视器等功能也用到了链表, Redis 服务器本身还使用链表来保存多个客户端的状态信息, 以及使用链表来构建客户端输出缓冲区(output buffer)。

2.1 结构定义

Redis 采用的是双向链表的结构,链表结点的结构:

typedef struct listNode {
    // 前置节点
    struct listNode *prev;
    // 后置节点
    struct listNode *next;
    // 节点的值
    void *value;
} listNode;

虽然多个链表结点可以够成一个结点,但是使用 adlist.h/list 来持有链表的话, 操作起来会更方便:

typedef struct list {
    // 表头节点
    listNode *head;
    // 表尾节点
    listNode *tail;
    // 链表所包含的节点数量
    unsigned long len;
    // 节点值复制函数,用于复制链表节点所保存的值
    void *(*dup)(void *ptr);
    // 节点值释放函数,用于释放链表节点所保存的值
    void (*free)(void *ptr);
    // 节点值对比函数 用于对比链表节点所保存的值和另一个输入值是否相等。
    int (*match)(void *ptr, void *key);
} list;

链表api方法

3. 字典

字典, 又称符号表(symbol table)、关联数组(associative array)或者映射(map), 是一种用于保存键值对(key-value pair)的抽象数据结构。

在字典中, 一个键(key)可以和一个值(value)进行关联(或者说将键映射为值),key 是独一无二的。

3.1 定义

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

// 哈希表
typedef struct dictht {
    // 哈希表数组
    dictEntry **table;
    // 哈希表大小
    unsigned long size;
    // 哈希表大小掩码,用于计算索引值
    // 总是等于 size - 1
    unsigned long sizemask;
    // 该哈希表已有节点的数量
    unsigned long used;
} dictht;

// 哈希表结点
typedef struct dictEntry {
    // 键
    void *key;
    // 值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;
    // 指向下个哈希表节点,形成链表,可以将多个哈希值相同的键值对连接在一次, 以此来解决键冲突(collision)的问题。
    struct dictEntry *next;
} dictEntry;

// 字典
typedef struct dict {
    // 类型特定函数,是一个指向 dictType 结构的指针
    dictType *type;
    // 私有数据,保存传给那些类型特定函数的可选参数
    void *privdata;
    // 哈希表 是一个包含两个项的数组,每一个项都是一个 dictht 哈希表,一般情况下只使用 ht[0],ht[1] 只会在对 ht[0] 进行 rehash 时使用.
    dictht ht[2];
    // rehash 索引
    // 当 rehash 不在进行时,值为 -1;当rehash为0时表示正在进行rehash。
    int rehashidx; /* rehashing not in progress if rehashidx == -1 */

} dict;

//每个 dictType 结构保存了一簇用于操作特定类型键值对的函数
typedef struct dictType {
    // 计算哈希值的函数
    unsigned int (*hashFunction)(const void *key);
    // 复制键的函数
    void *(*keyDup)(void *privdata, const void *key);
    // 复制值的函数
    void *(*valDup)(void *privdata, const void *obj);
    // 对比键的函数
    int (*keyCompare)(void *privdata, const void *key1, const void *key2);
    // 销毁键的函数
    void (*keyDestructor)(void *privdata, void *key);
    // 销毁值的函数
    void (*valDestructor)(void *privdata, void *obj);
} dictType;

3.2 哈希算法

当要将一个新的键值对添加到字典里面时, 程序需要先根据键值对的键计算出哈希值和索引值, 然后再根据索引值, 将包含新键值对的哈希表节点放到哈希表数组的指定索引上面。

# 使用字典设置的哈希函数,计算键 key 的哈希值
hash = dict->type->hashFunction(key);

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

键冲突解决办法:

当有两个或以上数量的键被分配到了哈希表数组的同一个索引上面时, 我们称这些键发生了冲突(collision)。

Redis 的哈希表使用链地址法(separate chaining)来解决键冲突: 每个哈希表节点都有一个 next 指针, 多个哈希表节点可以用 next 指针构成一个单向链表, 被分配到同一个索引上的多个节点可以用这个单向链表连接起来, 这就解决了键冲突的问题。

3.3 rehash

当哈希表保存的键值对数量太多或者太少时, 程序需要对哈希表的大小进行相应的扩展或者收缩。

步骤:

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

渐进式rehash

扩展或收缩哈希表将 ht[0] 里面的所有键值对 rehash 到 ht[1] 里面,不是一次性、集中式地完成的, 而是分多次、渐进式地完成的,是为了避免对服务器性能造成影响;步骤:

  1. ht[1] 分配空间, 让字典同时持有 ht[0]ht[1] 两个哈希表。
  2. 在字典中维持一个索引计数器变量 rehashidx , 并将它的值设置为 0 , 表示 rehash 工作正式开始。
  3. 在 rehash 进行期间, 每次对字典执行添加、删除、查找或者更新操作时, 程序除了执行指定的操作以外, 还会顺带将 ht[0] 哈希表在 rehashidx 索引上的所有键值对 rehash 到 ht[1] , 当 rehash 工作完成之后, 程序将 rehashidx 属性的值增一。
  4. 随着字典操作的不断执行, 最终在某个时间点上, ht[0] 的所有键值对都会被 rehash 至 ht[1] , 这时程序将 rehashidx 属性的值设为 -1 , 表示 rehash 操作已完成。

在渐进式 rehash 进行期间,两个hash表都在使用,所以增删查改会在两个表中进行。(第一个表没有,查找第二个表),另外在渐进式rehash执行期间,新添加到字典的键值对一律会被保存到ht[1]里面,而ht[0]不会进行任何添加操作。

哈希表的扩展与收缩

当以下条件中的任意一个被满足时, 程序会自动开始对哈希表执行扩展操作:

  1. 服务器目前没有在执行 BGSAVE 命令或者 BGREWRITEAOF 命令, 并且哈希表的负载因子大于等于 1
  2. 服务器目前正在执行 BGSAVE 命令或者 BGREWRITEAOF 命令, 并且哈希表的负载因子大于等于 5
# 负载因子 = 哈希表已保存节点数量 / 哈希表大小
load_factor = ht[0].used / ht[0].size

3.3 API

函数 作用 时间复杂度
dictCreate 创建一个新的字典。 O(1)
dictAdd 将给定的键值对添加到字典里面。 O(1)
dictReplace 将给定的键值对添加到字典里面, 如果键已经存在于字典,那么用新值取代原有的值。 O(1)
dictFetchValue 返回给定键的值。 O(1)
dictGetRandomKey 从字典中随机返回一个键值对。 O(1)
dictDelete 从字典中删除给定键所对应的键值对。 O(1)
dictRelease 释放给定字典,以及字典中包含的所有键值对。 O(N) , N 为字典包含的键值对数量。

4. 跳跃表

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

在大部分情况下, 跳跃表的效率可以和平衡树相媲美, 并且因为跳跃表的实现比平衡树要来得更为简单, 所以有不少程序都使用跳跃表来代替平衡树。

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

箭头上面的数字表示跨度,跨度用来计算目标结点在跳跃表中的排位。
每个跳跃表结点的层高都是1到32之间的随机数。
在同一个跳跃表中,多个节点可以包含相同的分数,但每个结点的成员对象必须是唯一的。首先按分值排序,分值相同在按成员对象大小排序。

4.1 实现

Redis 的跳跃表实现由 zskiplist(图片最左边的结构) 和 zskiplistNode 两个结构组成, 其中 zskiplist 用于保存跳跃表信息(比如表头节点、表尾节点、长度、level), 而 zskiplistNode 则用于表示跳跃表节点(level、backward回退指针、score、obj)。

level 是跳跃表内层数最大的那个结点的层数。

// 跳跃表结点
typedef struct zskiplistNode {
    // 后退指针 节点中用 BW 字样标记节点的后退指针,指向位于当前节点的前一个节点,后退指针在程序从表尾向表头遍历时使用。
    struct zskiplistNode *backward;
    // 分值 是一个 double 类型的浮点数, 跳跃表中的所有节点都按分值从小到大来排序。
    double score;
    // 成员对象 是一个指针, 它指向一个字符串对象, 而字符串对象则保存着一个 SDS 值。
    robj *obj;
    // 层
    struct zskiplistLevel {
        // 前进指针  用于从表头向表尾方向访问节点。
        struct zskiplistNode *forward;
        // 跨度 用于记录两个节点之间的距离
        unsigned int span;
    } level[];

} zskiplistNode;

// 跳跃表
typedef struct zskiplist {
    // 表头节点和表尾节点
    struct zskiplistNode *header, *tail;
    // 表中节点的数量
    unsigned long length;
    // 表中层数最大的节点的层数
    int level;
} zskiplist;

跳跃表API

5. 整数集合

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

// demo:创建一个只包含五个元素的集合键
redis> SADD numbers 1 3 5 7 9
(integer) 5
redis> OBJECT ENCODING numbers
"intset"

5.1 定义

整数集合(intset)是 Redis 用于保存整数值的集合抽象数据结构, 它可以保存类型为 int16_tint32_t 或者 int64_t 的整数值, 并且保证集合中不会出现重复元素

typedef struct intset {
    // 编码方式,int16_t、int32_t、int64_t
    uint32_t encoding;
    // 集合包含的元素数量
    uint32_t length;
    // 保存元素的数组,数组中按值的大小从小到大有序地排列, 并且数组中不包含任何重复项。
    int8_t contents[];
} intset;

5.2 升级

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

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

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

因为每次向整数集合添加新元素都可能会引起升级, 而每次升级都需要对底层数组中已有的所有元素进行类型转换, 所以向整数集合添加新元素的时间复杂度为 O(N) 。

升级的好处

一个是提升整数集合的灵活性, 另一个是尽可能地节约内存。

5.3 降级

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

举个例子, 即使我们将集合里唯一一个真正需要使用 int64_t 类型来保存的元素 4294967295 删除了, 整数集合的编码仍然会维持 INTSET_ENC_INT64 , 底层数组也仍然会是 int64_t 类型的。

6. 压缩列表

压缩列表(ziplist)是列表键和哈希键的底层实现之一。

当一个列表键只包含少量列表项, 并且每个列表项要么就是小整数值, 要么就是长度比较短的字符串, 那么 Redis 就会使用压缩列表来做列表键的底层实现

// demo:
redis> RPUSH lst 1 3 5 10086 "hello" "world"
(integer) 6
redis> OBJECT ENCODING lst
"ziplist"

6.1 定义

压缩列表是 Redis 为了节约内存而开发的, 由一系列特殊编码的连续内存块组成的顺序型(sequential)数据结构。

一个压缩列表可以包含任意多个节点(entry), 每个节点可以保存一个字节数组或者一个整数值。

graphviz-fe42f343a3f32f477efb5e895da547d476a7c97d

属性 类型 长度 用途
zlbytes uint32_t 4 字节 记录整个压缩列表占用的内存字节数:在对压缩列表进行内存重分配, 或者计算 zlend 的位置时使用。
zltail uint32_t 4 字节 记录压缩列表表尾节点距离压缩列表的起始地址有多少字节: 通过这个偏移量,程序无须遍历整个压缩列表就可以确定表尾节点的地址。
zllen uint16_t 2 字节 记录了压缩列表包含的节点数量: 当这个属性的值小于 UINT16_MAX65535)时, 这个属性的值就是压缩列表包含节点的数量; 当这个值等于 UINT16_MAX 时, 节点的真实数量需要遍历整个压缩列表才能计算得出。
entryX 列表节点 不定 压缩列表包含的各个节点,节点的长度由节点保存的内容决定。
zlend uint8_t 1 字节 特殊值 0xFF (十进制 255 ),用于标记压缩列表的末端。

每个压缩列表节点可以保存一个字节数组或者一个整数值, 其中, 字节数组可以是以下三种长度的其中一种:

  1. 长度小于等于 63 (2^{6}-1)字节的字节数组;
  2. 长度小于等于 16383 (2^{14}-1) 字节的字节数组;
  3. 长度小于等于 4294967295 (2^{32}-1)字节的字节数组;

而整数值则可以是以下六种长度的其中一种:

  1. 4 位长,介于 012 之间的无符号整数;
  2. 1 字节长的有符号整数;
  3. 3 字节长的有符号整数;
  4. int16_t 类型整数;
  5. int32_t 类型整数;
  6. int64_t 类型整数。

每个压缩列表节点都由 previous_entry_lengthencodingcontent 三个部分组成。

  • previous_entry_length:以字节为单位, 记录了压缩列表中前一个节点的长度;可以用来从表尾向表头遍历
  • encoding:记录了节点的 content 属性所保存数据的类型以及长度
  • content:负责保存节点的值

6.2 连锁更新

每个节点的 previous_entry_length 属性都记录了前一个节点的长度:

  • 如果前一节点的长度小于 254 字节, 那么 previous_entry_length 属性需要用 1 字节长的空间来保存这个长度值。
  • 如果前一节点的长度大于等于 254 字节, 那么 previous_entry_length 属性需要用 5 字节长的空间来保存这个长度值。

所以如果在一个压缩列表中, 有多个连续的、长度介于 250 字节到 253 字节之间的节点 e1eN ,然后将一个长度大于等于 254 字节的新节点 new 设置为压缩列表的表头节点,所以e1的previous_entry_length属性仅长 1 字节,它没办法保存新节点 new 的长度,所以需要程序将对压缩列表执行空间重分配操作,el得到previous_entry_length从原来的 1 字节长扩展为 5 字节长。 同样的e2——en都要执行这样的操作。

**总结 **

压缩列表里要恰好有多个连续的、长度介于 250 字节至 253 字节之间的节点, 连锁更新才有可能被引发, 在实际中, 这种情况并不多见;

其次, 即使出现连锁更新, 但只要被更新的节点数量不多, 就不会对性能造成任何影响: 比如说, 对三五个节点进行连锁更新是绝对不会影响性能的;

7. 对象

Redis 并没有直接使用这些数据结构来实现键值对数据库, 而是基于这些数据结构创建了一个对象系统, 这个系统包含字符串对象(string)、列表对象(list)、哈希对象(hash)、集合对象(set)和有序集合对象(zset)这五种类型的对象, 每种对象都用到了至少一种我们前面所介绍的数据结构。

Redis 的对象系统还实现了基于引用计数技术的内存回收机制: 当程序不再使用某个对象的时候, 这个对象所占用的内存就会被自动释放; 另外, Redis 还通过引用计数技术实现了对象共享机制, 这一机制可以在适当的条件下, 通过让多个数据库键共享同一个对象来节约内存。

7.1 定义

当我们创建一个键值对的时候,其实我们至少创建了两个对象:键对象和值对象。键对象其实就是字符串对象。而值对象是字符串、列表、哈希、集合、有序集合对象中的一个。

Redis中的每个对象都是由redisObject表示:

typedef struct redisObject {
    // 类型 字符串对象、列表对象、哈希对象、集合对象和有序集合对象
    unsigned type:4;
    // 编码,记录了值对象所使用的编码,也就是底层的数据结构:int、embstr编码的简单动态字符串、简单动态字符串、字典、双端链表、压缩列表、整数集合、跳跃表
    unsigned encoding:4;
    // 指向底层实现数据结构的指针,而这些数据结构由对象的 encoding 属性决定
    void *ptr;
  	// 对象的引用计数,用来进行垃圾回收。创建时为1,使用时加1,不使用减1,为0就会被释放。
  	int refcount;
		// 记录对象最后一次被命令程序访问的时间。
    unsigned lru:22;

} robj;

7.2 共享对象

对象的引用计数属性还带有对象共享的作用。

假设键 A 创建了一个包含整数值 100 的字符串对象作为值对象,如果这时键 B 也要创建一个同样保存了整数值 100 的字符串对象作为值对象,那么键A和键B会共享一个这个对象。

Redis 中, 让多个键共享同一个值对象需要执行以下两个步骤:

  1. 将数据库键的值指针指向一个现有的值对象;
  2. 将被共享的值对象的引用计数增一。

为什么 Redis 不共享包含字符串的对象?

当服务器考虑将一个共享对象设置为键的值对象时, 程序需要先检查给定的共享对象和键想创建的目标对象是否完全相同, 只有在共享对象和目标对象完全相同的情况下, 程序才会将共享对象用作键的值对象, 而一个共享对象保存的值越复杂, 验证共享对象和目标对象是否相同所需的复杂度就会越高, 消耗的 CPU 时间也会越多

  • 如果共享对象是保存整数值的字符串对象, 那么验证操作的复杂度为 O(1) ;
  • 如果共享对象是保存字符串值的字符串对象, 那么验证操作的复杂度为 O(N) ;
  • 如果共享对象是包含了多个值(或者对象的)对象, 比如列表对象或者哈希对象, 那么验证操作的复杂度将会是 O(N^2) 。

因此, 尽管共享更复杂的对象可以节约更多的内存, 但受到 CPU 时间的限制, Redis 只对包含整数值的字符串对象进行共享

不同类型和编码的对象

类型 编码 对象
REDIS_STRING REDIS_ENCODING_INT 使用整数值实现的字符串对象。
REDIS_STRING REDIS_ENCODING_EMBSTR 使用 embstr 编码的简单动态字符串实现的字符串对象。
REDIS_STRING REDIS_ENCODING_RAW 使用简单动态字符串实现的字符串对象。
REDIS_LIST REDIS_ENCODING_ZIPLIST 使用压缩列表实现的列表对象。
REDIS_LIST REDIS_ENCODING_LINKEDLIST 使用双端链表实现的列表对象。
REDIS_HASH REDIS_ENCODING_ZIPLIST 使用压缩列表实现的哈希对象。
REDIS_HASH REDIS_ENCODING_HT 使用字典实现的哈希对象。
REDIS_SET REDIS_ENCODING_INTSET 使用整数集合实现的集合对象。
REDIS_SET REDIS_ENCODING_HT 使用字典实现的集合对象。
REDIS_ZSET REDIS_ENCODING_ZIPLIST 使用压缩列表实现的有序集合对象。
REDIS_ZSET REDIS_ENCODING_SKIPLIST 使用跳跃表和字典实现的有序集合对象。

object encoding "key" 或者 type "key" 可以查看

字符串对象

字符串对象的编码有三种,int、raw、embstr。

  1. 保存的是long类型的整数值就用REDIS_ENCODING_INT编码来表示
  2. 保存的是字符串大于39字节的值,那就就用REDIS_ENCODING_RAW结构来表示
  3. 保存的是字符串大于39字节的值,那就就用REDIS_ENCODING_EMBSTR结构来表示
    可以用来做缓存,关键字
    字符串的命令
    set、get、append、incrbyfloat、incrby、decrby、strlen、setrange、getrange

列表对象

列表的编码可以是ziplist和linkedlist。
使用ziplist必须同时满足两个条件:

  1. 列表对象保存的字符串长度小于64字节。
  2. 数量小于512个。不能同时满足以上两个条件的都用linkedlist。

可以用来做消息队列、
列表的处理命令,其实就是一个双端链表,允许用户从序列的两端推入或者弹出元素。
列表的命令
lpush、rpush、lpop、rpop、lindex、llen、linsert、lrem、ltrim、lset、

哈希对象

哈希对象的编码可以是ziplist或者hashtable。
使用ziplist必须同时满足两个条件:

  1. 保存的所有键和值的字符串小于64字节。
  2. 数量小于512。
    不能同时满足则用hashtable
    哈希命令的实现
    hset、hget、hexists、hdel、hlen、hgetall、

集合对象

编码可以是intset和hashtable,是无序集合,会自动去重。
使用intset编码同时满足两个条件:

  1. 都是整数
  2. 数量不超过512.不能同时满足用hashtable。
    可以用来做交集、并集,比如两个用户的共同好友。
    集合命令实现
    sadd、scard、sismember、smembers、srandmember、spop、srem

有序集合对象

是排序的 Set,去重但可以排序,写进去的时候给一个分数,自动根据分数排序。
有序集合的编码可以是ziplist和skiplist。跳跃表按照分值大小保存了所有集合元素,而字典可以以O(1)的复杂度查找键值对。这也就是为什么使用字典+跳跃表实现来实现有序集合。
使用ziplist同时满足2个条件:

  1. 数量小于128、
  2. 元素成员小于64字节。
    不能满足以上两个用skiplist。
    可以用来做类似微博热搜榜排名、排行榜
    有序集合的命令实现
    zadd、zcard、zcount、zrange、zrevrange、zrank、zrevrank、zrem、zscore

Bitmap

就是通过一个bit位来表示某个元素对应的值或者状态,其中的key就是对应元素本身。8个bit可以组成一个Byte,所以bitmap本身会极大的节省储存空间。
使用场景:

  • 布隆过滤器:存在误判的情况;元素可以添加到集合但是无法进行删除
  • 统计活跃用户总数:通过在两个bitmap上面做and、or、not、xor运算
    • 使用时间作为缓存的key,然后用户id为offset,如果当日活跃过就设置为1。
    • 之后通过bitOp进行二进制计算两个日期之内用户的活跃情况。
  • 用户在线状态,只需要一个key,value为用户id。
    • 只需要一个key,然后用户id为偏移量offset,如果在线就设置为1,不在线就设置为0,

HyperLogLog

redis HyperLogLog 是用来做基数统计的算法,基数统计:统计一个集合中不重复元素的个数,常见于计算独立用户数(UV)。
HyperLogLog 的优点是,在输入元素的数量或者体积非常非常大时,计算基数所需的空间总是固定的、并且是很小的。通常是用来统计一个集合中不重复的元素个数。比如统计网站访问量(每人每天只算一次)。

简单的解决方案,为每一个页面设置一个独立的 set 集合 来存储所有当天访问过此页面的用户 ID,但是问题在于,存储空间巨大和统计复杂。

# 访问页面的用户添加到hyperlog
PFADD Redis主从同步原理:uv userID1 userID 2 useID3

PFCOUNT Redis主从同步原理:uv

# 合并多个hyperlog
PFMERGE destkey sourcekey [sourcekey ...]

Geo

Redis Geo 主要用于存储地理位置信息,可以用来查找附近的人。

Pub/Sub

Pub/Sub就是发布和订阅功能,

通用命令

del、expire、rename、type、object


目录