Redis笔记_4

简单动态字符串SDS

传统的C语言字符串存在问题:
1. 获取字符串长度需要通过运算
2. 非二进制安全，如果中间有一个\0则字符串直接结束了
3. 不可修改

set name sangs: 这条命令会在底层创建两个SDS，分别是name 和 sangs的SDS

struct __attribute__ ((__packed__)) sdshdr8{
    uint8_t len;            // buf已保存的字符串字节数，不包含结束标识
    uint8_t alloc;          // buf申请的总字节数，不包含结束标识，第一次触发时，申请内存一般和len一样
    unsigned char flags;    // 不同的SDS头类型，用来控制SDS的头大小
    char buf[];
};

len: 4

alloc: 4

flags: 1

n

a

m

e

\0

• 由于通过len判断需要读取多少位，所以是二进制安全的，不会读取到一半终止
• 之所以叫动态字符串，是因为具备动态扩容的能力。如果要给SDS追加一段字符串，就会申请新的内存空间，即为内存预分配
  • 如果新字符串长度小于1M，则新空间为扩展后字符串长度的两倍+1
  • 如果新字符串长度大于1M，则新空间为扩展后字符串长度+1M+1

举例

len: 2

alloc: 2

flags: 1

h

i

\0

len: 6

alloc: 12

flags: 1

h

i

,

A

m

y

\0

优点

1. 获取字符串长度的时间复杂度为O(1)
2. 支持动态扩容
3. 减少内存分配次数
4. 二进制安全

IntSet

• 是set集合的一种实现方式，基于整数数组实现。
• 长度可变
• 有序

typeder struct intset{
    uint32_t encoding;  // 编码方式，支持16位，32位，64位整数
    uint32_t length;    // 元素个数
    int8_t contents[];  // 整数数组，保存集合数据，指针，指向数组第一个地址
} intset;

IntSet升级

假设有一个IntSet，元素为5, 10 ,20。则采用的编码为INTSET_ENC_INT16，每个整数占用2B，如果此时添加了一个数字50000，超过了int16_t的范围，则会自动升级编码方式到合适的大小

• 升级编码为INTSET_ENC_INT32，每个整数占用4B，并按照新的编码方式以及元素个数扩容数组
• 倒序依次将数组中的元素拷贝到扩容后的正确位置(因为正序拷贝会导致后面的数字被覆盖)
• 将待添加的元素放入数组末尾
• 将IntSet的encoding属性改为INTSET_ENC_INT32，修改length:4

特点

1. Redis确保IntSet元素唯一有序
2. 具备升级机制，可以节省内存空间
3. 底层采用二分查找方式查询

• 因为需要连续的内存空间，所以适合少量的数据，且IntSet只能存储整数

Dict

• 三个部分组成:
  1. 哈希表(DickHashTable)
  2. 哈希节点(DictEntry)
  3. 字典(Dict)

typedef struct dictht{
    dictEntry **table；     // Entry指针数组，数组中保存的是指向Entry的指针
    unsigned long size;     // 哈希表大小
    unsigned long sizemask; // 哈希表大小的掩码，总等于size - 1
    unsigned long used;     // Entry个数
} dictht;

typedef struct dictEntry{
    void *key;  // 键
    union{
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;        // 值
    struct dictEntry *next;
} dcitEntry;

typedef struct dict {
    dictType *type;         // dict类型，内置不同的hash函数
    void *privdata;         // 私有数据，在做特殊hash运算时使用
    dictht ht[2];           // 一个Dict包含两个哈希表，其中一个是当前数据，另一个一般为空，rehash时使用
    long rehashidx;         // rehash进度，-1表示未进行
    int16_t pauserehash;    // rehash是否暂停，1表示暂停，0表示继续
}dict;

Dict扩容

当我们向Dict添加键值对时，Redis首先根据key计算出hash值h，然后利用h & sizemask来计算元素应该存储得到数组中的哪个索引位置。

• 因为sizemask的大小恰好是size - 1，所以h & sizemask这个与运算的结果恰好等于对h求余(其实就是除留余数法)

• 如果有同义词，则将新插入的元素接在前面，后面跟上原来的数据(这就是使用拉链法解决哈希冲突)
• 但是如果元素较多，冲突增多，链表过长，则查询效率会大大降低
  • 因此每次新增键值对会检查负载因子(使用的位置个数和总空间个数的比值)
  • 哈希扩容:
    1. 负载因子 >= 1，并且服务器没有执行BGSAVE或者BGREWRITEAOF等后台进程
    2. 负载因子 > 5

static int _dictExpandIfNeeded (dict *d){
    // 如果正在rehash 返回OK
    if (dictIsRehashing(d)) return DICT_OK;
    // 如果哈希表为空，则初始化哈希表默认大小为4
    if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);
    // 当负载因子(used / size)达到1以上，并且当前没有进行bgrewrite等子进程操作
    // 或者当负载因子超过5，则进行地图Expand，也就是扩容
    if (d->ht[0].used >= d->ht[0].size && 
        (dict_can_resize || d->ht[0].used / d->ht[0].size > dict_force_resize_ratio)){
            // 扩容大小为used + 1，底层对扩容大小判断，实际上找的是第一个大于等于used + 1的2^n
            return dictExpand(d, d->ht[0].used + 1);
    }
    return DICT_OK;
}

Dict收缩

• 当负载因子小于0.1的时候，就会做哈希表收缩

// t_hash.c hashTypeDeleted()
if (dictDelete((dict*)o->ptr, field) == c_OK){
    deleted = 1
    // 删除成功后，需要检查是否重置Dict大小，如果需要则调用dictResize重置
    if(htNeedsResize(o->ptr)) dictResize(o->ptr);
}

// server.c 
int htNeedsResize(dict *dict){
    long long size, used;
    // 哈希表大小
    size = dictSlots(dict);
    // entry数量
    used = dictSize(dict);
    // size > 4(初始大小)并且负载因此低于0.1
    return (size>DICT_HT_INITIAL_SIZE && (used*100 / size < HASHTABLE_MIN_FILL));
}

int dictResize(dict *d){
    unsigned long minimal;
    // 如果正在做bgsave或者bgrewriteof或者rehash，返回错误
    if(!dict_can_resize || dictIsRehashing(d)) return DICT_ERR;
    // 获取used，也就是entry个数
    minimal = d->ht[0].used;
    // 如果used小于4，则重置为4
    if(minimal < DICT_HT_INITIAL_SIZE) minimal = DICT_HT_INITIAL_SIZE;
    // 重置大小为minimal，其实是第一个大于等于minimal的2^n
    return dictExpand(d, minimal);
}

rehash

无论是收缩还是扩容，都会创建新的哈希表，导致哈希表的size和sizemask变化，而key的查询与sizemask有关，因此必须对哈希表中的每一个key重新计算索引，插入新的哈希表，这个过程称为rehash

1. 计算新的哈希表的realeSize，取决于当前做的是扩容还是收缩
   • 扩容，则新的size为第一个大于等于dict.ht[0].used + 1的$2^n$
   • 收缩，则新的size为第一个大于等于dict.ht[0].used的$2^n$(不得小于4)
2. 按照新的realeSize申请内存空间，创建dictht，并赋值给dict.ht[1]
3. 设置dict.rehashidx=0表示开始rehash
4. 将dict.ht[0]中的每一个dictEntry都rehash到dict.ht[1]
5. 将dict.ht[1]赋值给dict.ht[0]，给dict.ht[1]初始化为空哈希表，释放原来的dict.ht[0]内存

渐进式rehash

但是这样做，一次完成rehash，则很有可能导致主线程阻塞，所以实际上是分多次进行rehash，称为渐进式rehash

1. 计算新的哈希表的realeSize，取决于当前做的是扩容还是收缩
   • 扩容，则新的size为第一个大于等于dict.ht[0].used + 1的$2^n$
   • 收缩，则新的size为第一个大于等于dict.ht[0].used的$2^n$(不得小于4)
2. 按照新的realeSize申请内存空间，创建dictht，并赋值给dict.ht[1]
3. 设置dict.rehashidx=0表示开始rehash
   4. 将dict.ht[0]中的每一个dictEntry都rehash到dict.ht[1]
4. 每次执行增删改查操作时，检查一下dict.rehashidx是否大于-1，如果是则将dict.ht[0].table[rehashidx]的entry链表rehash到dict.ht[1]，并且将rehashidx ++，直到dict.ht[0]的所有数据都rehash到dict.ht[1]
5. 将dict.ht[1]赋值给dict.ht[0]，给dict.ht[1]初始化为空哈希表，释放原来的dict.ht[0]内存.
6. 将rehashidx赋值为-1，表示rehash结束
7. 在rehash过程中，新增操作直接写入ht[1]，查询修改和删除则会在dict.ht[0], dict.ht[1]依次查找并执行，可以确保ht[0]中的数据只减不增，随着rehash最终为空

ZipList

• 节省内存
• 一种特殊的"双端链表"，实际上并不是链表，只是一系列特殊编码的连续内存组成的，可以在任意一端进行压入、弹出操作，并且时间复杂度为O(1)的数据结构

属性	类型	长度	用途
zlbytes	uint32_t	4B	记录整个压缩列表占用的内存字节数
zltail	uint32_t	4B	记录压缩列表表尾节点距离压缩列表的起始地址有多少字节，通过这个偏移量，可以确定尾节点的位置
zllen	uint16_t	2B	记录压缩列表包含的节点数量，最大值为UINT16_MAX(65534)，超过这个值会记录为65535，但是节点的真实数量需要遍历整个压缩列表才能计算得出
entry	列表节点	不定	压缩列表包含的各个节点，节点长度由节点保存的内容决定
zlend	uint8_t	1B	特殊值0xff，用于标记压缩列表的末端

ZipListEntry

• 每一个Entry内部又包含了三个部分，分别为

  previous_entry_length

  encoding

  content

• previous_entry_length: 前一个节点的长度，占1 or 5字节
  • 如果前一个节点的长度小于254，则采用1B来保存这个长度
  • 如果前一个字节的长度大于254，则采用5B来保存这个长度，其中第一个字节为0xfe,后面四个字节才是真实长度数据(所以字节的长度不能太大)
• encoding: 编码属性，记录content的数据类型(字符串还是整数)以及长度，占用1，2，或者5个字节
• contents: 负责保存节点的数据，可以是字符串或者整数
• 这样可以避免使用两个指针记录前后节点，这样需要消耗16个字节，浪费内存。
• 小端存储

Encoding编码

字符串编码: 以00, 01, 10开头则content为字符串

编码	编码长度	字符串大小
|00pppppp|	1B	<= 63B
|01pppppp|qqqqqqqq|	2B	<= 16383 B
|10000000|qqqqqqqq|rrrrrrrr|ssssssss|tttttttt|	5B	<= 4294967295B

• 例如保存’ab’, ‘bc’:
  

整数编码: 以11开头，则content为整数，并且encoding固定占用一个字节

编码	编码长度	字符串大小
11000000	1	int16_t(2B)
11010000	1	int32_t(4B)
11100000	1	int64_t(8B)
11110000	1	24位有符号整数(3B)
11111110	1	8位有符号整数(1B)
1111xxxx	1	直接在xxxx位置保存数值，范围从0001~1101，减一后结果为实际值，实际上保存了(0~12)

• 例如保存2, 5:
  

连锁更新问题

• 每个entry都包含previous_entry_length来记录上一个节点大小，长度是1 or 5字节
  • 假设有N个连续的，长度为250~253字节之间的entry，只需要使用1B即可
  • 如果在第一个节点插入一个大小为254B的entry，就需要占用5B，此时导致后面的每一个entry大小都恰好达到了254B，导致了每个元素都需要改变
    最终产生了连续多次空间扩展操作，就是连锁更新。新增，删除都有可能导致连锁更新
• 因为概率很低，所以暂时还没有完全解决。目前有新的listpack可以在一定程度上解决ZipList的连锁更新问题，但是还没有完全引入