Redis

1. sds 是对 C 语言字符串的扩展, 除了记录底层字符串，还缓存了当前长度

   // sds 的实现结构体不止一个，但是定义的方式类似，只是操作系统位数不一致
   // 下面以 sdshdr64 为例展示
   struct __attribute__ ((__packed__)) sdshdr64 {
     uint64_t len; /* used */
     uint64_t alloc; /* excluding the header and null terminator */
     unsigned char flags; /* 3 lsb of type, 5 unused bits */
     char buf[];
   };
   

2. Redis 的字符串是 二进制安全
3. 对比 C 语言字符串，提供了如下的特性
   • 高效计算字符串长度 strlen
   • 高效追加字符串 append
4. 代码实现在 sds.h 和 sds.c 两个文件中

1. 代码实现在 adlist.h 和 adlist.c 两个文件中

2. 该数据结构的定义如下

   typedef struct listNode { // 记录链表节点
     struct listNode *prev;
     struct listNode *next;
     void *value;
   } listNode;
   
   typedef struct listIter { // 记录链表的迭代器
     listNode *next;
     int direction;
   } listIter;
   
   typedef struct list { // 链表的数据结构
     listNode *head;
     listNode *tail;
     void *(*dup)(void *ptr);
     void (*free)(void *ptr); // 记录链表的空闲指针
     int (*match)(void *ptr, void *key); // 匹配的函数指针
     unsigned long len; // 缓存链表长度
   } list;
   

1. 代码实现在 dict.h 和 dict.c 两个文件中
2. 字典的实现在 Redis 中有两个作用
   • 实现数据库键空间 (Key Space), 例如: DBSIZE, FLUSHDB, RANDOMKEY
   • 用作 Hash 类型键的底层实现之一

3. 该数据结构的定义如下

   typedef struct dictEntry { // 字典项定义
     void *key;
     union {
       void *val;
       uint64_t u64;
       int64_t s64;
       double d;
     } v;
     struct dictEntry *next; // 指向相应数据项
   } dictEntry;
   
   typedef struct dictType {
     uint64_t (*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);
     int (*expandAllowed)(size_t moreMem, double usedRatio);
   } dictType;
   
   /* This is our hash table structure. Every dictionary has two of this as we
    * implement incremental rehashing, for the old to the new table. */
   // 每个字典的 entry 有两个 dictht, 主要目的是可以快速 rehash
   typedef struct dictht {
     dictEntry **table; // 哈希桶 bucket
     unsigned long size; // 指针数组大小 bucket size
     unsigned long sizemask; // 指针数组长度掩码，用于计算索引值
     unsigned long used; // 哈希表现有节点数量
   } dictht;
   
   typedef struct dict { // 字典数据类型的定义
     dictType *type;
     void *privdata;
     dictht ht[2];
     long rehashidx; /* rehashing not in progress if rehashidx == -1 */
     int16_t pauserehash; /* If >0 rehashing is paused (<0 indicates coding error) */
   } dict;
   
   /* If safe is set to 1 this is a safe iterator, that means, you can call
    * dictAdd, dictFind, and other functions against the dictionary even while
    * iterating. Otherwise it is a non safe iterator, and only dictNext()
    * should be called while iterating. */
   typedef struct dictIterator {
     dict *d;
     long index; // 正在迭代的数组索引
     int table, safe; // table 表示正在迭代的号码（0或1）, safe=1, 表示迭代过程中修改哈希表
     dictEntry *entry, *nextEntry;
     /* unsafe iterator fingerprint for misuse detection. */
     long long fingerprint;
   } dictIterator;
   
   typedef void (dictScanFunction)(void *privdata, const dictEntry *de);
   typedef void (dictScanBucketFunction)(void *privdata, dictEntry **bucketref);
   
   /* This is the initial size of every hash table */
   #define DICT_HT_INITIAL_SIZE     4
   

4. 字典的每个项记录两个 dictht
   • ht[0] 是字典主要使用的哈希表，
   • ht[1] 则只有在程序对 ht[0] 进行 rehash 时才使用
5. dictCreate() 创建新的字典
   • dictCreate() 创建了 dict 和两个 dictht
   • dictCreate() 并没有给 dictht 的 table 分配空间
6. dictAdd() 表示向字典中添加 dictEntry 数据
   • 该过程可能触发 rehash
     • rehash 可以是扩展数据，也可能是收缩数据 (shrink)
   • rehash 使用 ht[1] 作为中转节点
   • 为了 hash 效率, Redis 采用渐进式哈希
     • _dictRehashStep 用于对数据库字典、以及哈希键的字典进行被动 rehash
     • dictRehashMilliseconds 则由 Redis 服务器常规任务程序执行，用于对数据 库字典进行主动 rehash
7. 字典使用 链地址 解决哈希冲突

1. 跳跃表主要使用场景就是 有序集合 zset
   • 包含的元素数量比较多
   • 元素成员 (member) 是比较长的字符串
2. 跳跃表以有序的方式在 层次化 的链表中保存元素， 效率和平衡树媲美
3. 查找、删除、添加等操作都可以在 O(logN) 期望时间下完成
4. 比起平衡树来说， 跳跃表的实现要简单直观得多
5. 跳跃表的构成部分
   • 表头 (head): 负责维护跳跃表的节点指针
   • 跳跃表节点: 保存着元素值，以及多个层
   • 层: 保存着指向其他元素的指针
     • 高层的指针越过的元素数量大于等于低层的指针
     • 为了提高查找的效率，程序总是从高层先开始访问，然后随着元素值范围的缩小， 慢慢降低层次
   • 表尾: 全部由 NULL 组成，表示跳跃表的末尾

6. 跳跃表的定义位于 server.h 中

   /* ZSETs use a specialized version of Skiplists */
   typedef struct zskiplistNode {
       sds ele;
       double score;
       struct zskiplistNode *backward; // 后退指针
       struct zskiplistLevel { // 层
           struct zskiplistNode *forward; // 前进指针
           unsigned long span; // 该层跨域的节点数量
       } level[]; // level[] 在 Redis 中是 1 到 32 的随机数
   } zskiplistNode;
   
   typedef struct zskiplist {
       struct zskiplistNode *header, *tail; // 头节点和尾节点
       unsigned long length; // 节点数量
       int level; // 目前表内节点的最大层数
   } zskiplist;
   

7. Redis 在 William Pugh 关于 Skip List 的设计中进行修改，满足自身查询的需求
   • score 值可重复
   • 对比一个元素需要同时检查它的 score 和 member
   • 每个节点带有高度为 1 层的后退指针，用于从表尾方向向表头方向迭代

1. 用于有序、无重复地保存多个整数值，根据元素的值，自动选择该用什么长度的整数 类型来保存元素
2. intset 的应用范围如下
   • 只保存着整数元素
   • 元素的数量不多

3. intset 的实习见 intset.c 和 intset.h 中

   typedef struct intset {
     uint32_t encoding; // 保存所使用类型的长度
     uint32_t length; // 元素个数
     int8_t contents[]; // 元素
   } intset;
   

4. contents 数组中的整数位数提升时，需要对整数进行扩充操作，这个扩充过程叫 做 升级 (upgrade)
5. contents 数组不支持降级操作，一旦升级过后即使最大位数的数字被删除了，依 旧使用保持最大位数

1. ziplist 是由一系列特殊编码的内存块构成的列表
   • 一个 ziplist 可以包含多个节点 (entry)
   • 每个节点可以保存一个长度受限的字符数组 (不以 \0 结尾的 char 数组) 或者 整数
2. 哈希键、列表键和有序集合键初始化的底层实现皆采用 ziplist
3. 添加和删除 ziplist 节点有可能会引起连锁更新，因此，添加和删除操作的最坏复 杂度为 O(N^2)

4. ziplist 的典型结构如下，其中存储数据的是 entries

   area        |<---- ziplist header ---->|<----------- entries ------------->|<-end->|
   
   size          4 bytes  4 bytes  2 bytes    ?        ?        ?        ?     1 byte
               +---------+--------+-------+--------+--------+--------+--------+-------+
   component   | zlbytes | zltail | zllen | entry1 | entry2 |  ...   | entryN | zlend |
               +---------+--------+-------+--------+--------+--------+--------+-------+
                                          ^                          ^        ^
   address                                |                          |        |
                                   ZIPLIST_ENTRY_HEAD                |   ZIPLIST_ENTRY_END
                                                                     |
                                                            ZIPLIST_ENTRY_TAIL
   

5. ziplist 的 entry 如下

   area        |<------------------- entry -------------------->|
   
               +------------------+----------+--------+---------+
   component   | pre_entry_length | encoding | length | content |
               +------------------+----------+--------+---------+
   

1. 对象的类型定义位于 redisObject 结构体

   typedef struct redisObject {
     unsigned type:4; // 类型：字符串，哈希表，列表等等
     unsigned encoding:4; // 编码格式：sds, int, hashtable, zipmap, list, ziplist, skiplist
     unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or
                             * LFU data (least significant 8 bits frequency
                             * and most significant 16 bits access time). */
     int refcount; // 引用计数
     void *ptr;
   } robj;
   

2. 对象的内存释放方式是使用引用计数
   • 对象初始创建时 refcount 的值被设置成 1
   • 当 refcount 降至 0 后，该 redisObject 将会被释放

1. 字符串默认有如下两种类型
   • REDIS_ENCODING_INT 使用 long 类型来保存 long 类型值
   • REDIS_ENCODING_RAW 则使用 sdshdr 结构来如下类型的值
     • sds (也即是 char* )
     • long long
     • double
     • long double
2. 二进制安全, 可以存储图片和序列化对象, 最多可存储 512M 的数据
3. GET, SET, DEL, 操作单个字符串键的指令
4. MSET 同时设置多个键
5. INCR 和 DECR
6. STRLEN, APPEND

1. 哈希表使用如下两种编码格式
   • REDIS_ENCODING_ZIPLIST
     • 键和值一同推入压缩列表
     • 形成保存哈希表所需的键-值对结构
   • REDIS_ENCODING_HT 当出现如下条件时, ziplist 转 hashtable
     • 哈希表中某个键或某个值的长度大于 server.hash_max_ziplist_value, 默认 值为 64
     • 压缩列表中的节点数量大于 server.hash_max_ziplist_entries, 默认值为 512
2. 操作哈希表的指令 HMSET, HGET 和 HGETALL
3. 物理存储会在 ziplist 和 hashtable 两种类型中转换
4. ziplist 比 hashtable 节约空间，默认使用 ziplist
5. 当有需要时，Redis 会自动将 ziplist 转成 hashtable

1. 列表使用如下两种编码格式
   • REDIS_ENCODING_ZIPLIST
     • 将值添加到压缩列表中
   • REDIS_ENCODING_LINKEDLIST 当出现如下条件时, ziplist 转 linkedlist
     • 哈希表中某个键或某个值的长度大于 server.list_max_ziplist_value, 默认 值为 64
     • 压缩列表中的节点数量大于 server.list_max_ziplist_entries, 默认值为 512
2. 列表是一个双向链表, 最多存储 2^32-1 个元素
3. 常见列表操作 LPUSH, LPOP, RPUSH 和 RPOP
4. 范围查找 LRANGE key 0 10
5. 计算列表长度 LLEN
6. 列表可能会发生阻塞, BLPOP, BRPOP 和 BRPOPLPUSH

1. 集合使用如下两种编码格式
   • REDIS_ENCODING_INTSET
     • 如果集合的第一个元素是 long long 类型，则初始化成该类型
   • REDIS_ENCODING_HT 当出现如下条件时, intset 转 hashtable
     • 哈希表中某个键或某个值的长度大于 server.set_max_ziplist_value, 默认 值为 64
     • 压缩列表中的节点数量大于 server.set_max_ziplist_entries, 默认值为 512
     • 字典编码时，对应的 dictEntry 只保存 key, value 和 next 都为空
2. 集合数据操作 SADD, SREM 和 SMEMBERS
3. 随机获取成员 SRANDMEMBERS
4. 集合交集和并集操作 SINTER 和 SUNION
5. 求差集 SDIFF

1. 有序集合使用如下两种编码格式
   • REDIS_ENCODING_ZIPLIST
     • 每个有序集元素以两个相邻的 ziplist 节点表示
     • 第一个节点保存元素的 member 域
     • 第二个元素保存元素的 score 域
   • REDIS_ENCODING_SKIPLIST 当出现如下条件时, ziplist 转 skiplist
     • 服务器属性 server.zset_max_ziplist_entries 的值大于 0, 默认为 128
     • 元素的 member 长度小于服务器属性 server.zset_max_ziplist_value 的值, 默认为 64

     • zset 同时使用 字典 和 跳跃表 两个数据结构来保存有序集元素

       typedef struct zset {
         dict *dict;
         zskiplist *zsl;
       } zset;
       

     • 字典和跳跃表两个结构通过将指针共同指向这两个值来节约空间
2. 关于 zset 的两种定义的有序
   • 字典结构 dict
     • 检查给定 member 是否存在于有序集（被很多底层函数使用）
     • 取出 member 对应的 score 值 (实现 ZSCORE 命令)
   • 跳跃表结构 skiplist
     • O(logN) 时间复杂度内根据 score 对 member 进行定位（被很多底层函数使用）
     • 范围查找和处理操作，例如 ZRANGE, ZRANK 和 ZINTERSTORE
3. 有序的集合类型, 键是不可重复的
4. ZADD 和 ZCOUNT

Redis 的整数和字符串都是存在 string 类型中

127.0.0.1:6379> flushdb
OK
127.0.0.1:6379> set hello 'world'
OK
127.0.0.1:6379> keys *
1) "hello"
127.0.0.1:6379> get hello
"world"
127.0.0.1:6379> append hello '!'
(integer) 6
127.0.0.1:6379> get hello
"world!"

使用一个整数 string 类型的 count 变量值来计数

127.0.0.1:6379> set count 1
OK
127.0.0.1:6379> incr count
(integer) 2
127.0.0.1:6379> get count
"2"
127.0.0.1:6379> incr count
(integer) 3
127.0.0.1:6379>

常见哈希表的操作如下

127.0.0.1:6379> flushdb
OK
127.0.0.1:6379> hmset user name zhang age 12
OK
127.0.0.1:6379> hgetall user
1) "name"
2) "zhang"
3) "age"
4) "12"

集合的操作如下，包括对集合的基本操作

127.0.0.1:6379> sadd course math
(integer) 1
127.0.0.1:6379> sadd course chinese
(integer) 1
127.0.0.1:6379> object encoding course
"hashtable"
127.0.0.1:6379> smembers course
1) "math"
2) "chinese"

1. 使用 object encoding 查看对象的底层数据类型
2. 使用 type 来查看 key 对应的数据结构类型

127.0.0.1:6379> keys *
1) "a"
2) "str1"
127.0.0.1:6379> object encoding a
"quicklist"
127.0.0.1:6379> object encoding str1
"embstr"
127.0.0.1:6379> type str1
string