test随笔

数据结构与对象

数据结构

1.简单动态字符串

C语言使用长度为N+1长度的字符数组来存放长度为N的字符串，且在字符数组的最后一个元素总是空字符"\0"。而在Redis中C字符串自会作为字符串字面量用在一些无需对字符串值进行修改的地方，例如打印日志：redislog(REDIS_WARNING, "redis is now reday to exit, bye bye ");。在Redis中自定义了一种名为简单动态字符串（Simple Dynamic String，SDS）的抽象类型，并将SDS作为Redis的默认字符串表示。例如执行一下命令：

redis> RPUSH fruits "apple" "banana" "cherry"
(integer) 3

那么Redis将在数据库中创建一个新的键值对，其中：

键值对的键是一个字符串对象，对象的底层实现是一个保存了字符串"fruits"的SDS
键值对的值是一个列表对象，列表对象包含了三个字符串对象，这三个字符串对象分别是由SDS实现的"apple""banana""cherry"

SDS的定义

SDS是由sds.h/sdshdr结构定义的，具体如下：

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

上图为一个SDS实例的示意图，我们从图上可以得知：

len的属性值为5，表明这个SDS保存了五个字节长度的字符串
free的属性值为5，表明这个SDS中有5个字节空间没有被使用
buf属性是一个字节数组，数组的前五个字节分别保存了'R''e''d''i''s'五个字符，而最后一个字节则保存了空字符'/0'

SDS遵循C字符串以空字符结尾的惯例，保存空字符的一字节空间不计算在SDS的len属性里面，并且为空字符分配额外的一字节空间，以及添加空字符到字符串末尾等操作都是由SDS函数自动完成的。所以这个空字符串对于SDS使用者来说是完全透明的，SDS遵循C字符串中空字符结尾的惯例的好处是SDS可以直接重用一部分C字符串函数库的函数。

SDS获取字符串长度复杂度

由于C字符串不记录自身的长度信息，所以获取C字符串的长度需遍历整个字符串，对每个字符进行计数，直到遇到代表C字符串结尾的空字符'/0'为止，所以获取C字符串长度的时间复杂度为O(N)。而SDS在属性len中记录了字符串长度信息，所以获取SDS字符串长长度的时间复杂度为O(1)。这确保了获取字符串长度的工作不会成为Redis的性能瓶颈，例如多次对一个长字符串使用STRLEN命令也不会影响Redis的性能

杜绝缓冲区溢出

C字符串另一个问题是容易造成缓冲区溢出（buffer overflow），例如<string.h>/strcat函数可以将一个字符串的内容拼接到目标字符串的末尾，但是如果目标字符串分配的内存空间不足就会产生缓冲区溢出，可能会覆盖掉别的内容。

与C字符串不同的是，SDS在进行修改之前，APS会先检查SDS的空间是否满足修改所需的要求，如果不满足的话，API会自动将SDS的空间扩展到执行修改所需的大小，然后再执行修改操作。所以SDS的空间分配策略完全杜绝了发生缓冲区溢出的可能。

SDS空间分配策略

C字符串的底层实现总是为N+1长度的字符数组，所以对字符串进行修改长度操作，例如增加或缩短一个C字符串，程序总要对保存C字符串的数组进行一次内存重分配操作：

如果是增长字符串操作，那么执行这个操作之前程序要先通过内存重分配来扩展底层字符数组的空间大小，如果忘记这一步骤就会造成缓冲区溢出
如果是缩短字符串操作，那么执行这个操作之后程序要通过内存重分配来释放掉字符数组未被使用的空间，如果忘记这一步骤就会产生内存泄漏

因为内存重分配涉及到非常复杂的算法，并且可能执行系统调用，所以通常是一个比较耗时的操作。在一般的程序中如果修改字符串的情况不经常出现，那么每次修改字符串进行一次内存重分配还是可以接受的。但是Redis作为以性能著称的数据库，经常被用于速度要求高，修改次数多的场景，如果每次修改都进行一次内存重分配那肯定是不合适的。

所以为了避免这种情况出现，SDS通过未使用空间这一特性解除了字符串长度和字符数组长度之间的关联。而针对未使用空间这一特性，SDS实现了空间预分配和惰性空间释放两种优化策略：

空间预分配：空间预分配用于优化SDS的字符串增长操作，当SDS的需要进行空间扩展时，API不仅会为SDS分配修改所需要的内存空间，还会为SDS分配额外的未使用空间

额外分配的未使用空间分配策略如下：

修改之后SDS中len的属性值小于1MB，那么程序分配和len属性同样大小的未使用空间；修改之后SDS中len的属性值大于等于1MB，那么程序会分配1MB的未使用空间

通过空间预分配策略，Redis可以减少连续执行字符串增长操作时所需的内存重分配次数，在扩展SDS内存空间之前，API会先检查未使用空间是否足够，如果足够的话API就会使用未分配空间，而无需进行内存重分配。

惰性空间释放：惰性空间释放用于优化缩短SDS字符串操作，当SDS字符串执行缩短操作后，程序并不立即使用内存重分配来回收缩短后多出来的字节空间，而是使用free属性将这些字节空间记录起来，等待将来使用

通过惰性空间释放策略，SDS避免了缩短字符串时所需的内存重分配操作，并为以后可能发生的增长字符串操作提供了优化。SDS也提供了手动释放未使用空间的API。

二进制安全

C字符串中的字符必须符合某种编码（例如ASCII），并且除了字符串末尾以外不能包含空字符，否则空字符将会被认定为字符串结尾。这些限制使得C字符串只能保存文本数据而不能保存图片，视频等二进制数据。而SDS的API都是二进制安全的，API会以处理二进制的方式来处理SDS中的字符数组里的数据，这也是我们将SDS中的数组成为字节数组的原因

例如SDS中保存了带空字符的字符串也是能够读取成功的，因为SDS使用len属性值而不是空字符来判断字符串是否结束

兼容部分C字符串函数

虽然SDS是二进制安全的，但是它们和C字符串一样遵循这空字符结尾的惯例，这样SDS就可以重用C字符串中的部分函数

2.链表

链表提供高效的节点重排能力，以及顺序性的节点访问方式，并且可以灵活的增删节点来调节链表的长度。链表在Redis中的应用非常广泛，比如列表的底层实现之一就是链表，当一个链表包含了数量较多的元素或链表中包含了较长的字符串时，列表就会使用链表作为底层实现

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

链表及链表节点的定义

每个链表节点使用adlist.h/listNode结构表示：

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

多个链表节点通过prev和next指针连接成双端链表，链表使用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 *value);
}list;

list结构为链表提供了表头指针head、表尾指针tail、以及链表长度计数器len，而dup、free和match则是用于实现多态链表所需的类型特定函数：

dup函数用于复制链表节点所保存的值
free函数用于释放链表节点所保存的值
match函数则用于对比链表节点值和参数值是否相等

总结

链表被广泛用于Redis的各个功能，如列表、发布与订阅、慢查询、监视器等
每个链表节点使用listNode结构来表示，每个listNode都有指向前置节点和后置节点的指针，所以链表是双端链表
每个链表使用list结构来表示，每个list结构都有链表头节点、链表尾节点和链表长度等信息
因为链表的头节点的前置节点和尾节点的后置节点都指向null，所以链表是无环链表
通过为链表设置不同的类型特定函数，链表可以保存不同类型的值

3.字典

字典又称符号表（symbol table）、关联数组（associative array）或映射（map），是一种用于保存键值对的抽象数据结构。字典在Redis中的应用相当广泛，比如Redis的数据库就是使用字典来作为底层实现的，对数据库的增删改查操作也是构建在对字典的操作之上

除了用来表示数据库以外，字典还是哈希值的底层实现之一，当一个哈希值包含的键值对比较多或者键值对中的元素都是比较长的字符串时，哈希值会使用字段作为其底层实现

字典的定义

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

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

typedef  struct dictEntry{
    // 键
    void *key;
    
    // 值
    union{
        void *val;
        uint64_t u64;
        int64_t s64;
    }v;
    
    // 指向下一节点的指针，在发生哈希冲突时形成链表
    struct dictEntry *next;
}dictEntry;

dictEntry结构中key属性保存键值对中的键，而v属性则保存键值对中的值，其中键值对中的值可以是一个指针，也可以是一个uint64_t整数，又或者是一个int64_t整数，next属性是指向另一个哈希表节点的指针，这个指针可以将多个哈希值相等的键值对连接在一起组成链表，已解决哈希冲突问题。

Redis中哈希表是由dict.h/dictht结构定义：

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

table属性是一个数组，数组中的每一个元素都是指向dictEntry结构的指针；size属性记录了哈希表的大小，也就是table数组的大小；used记录了哈希表目前已有的节点数量；sizemask属性和哈希值一起决定键值对在table数组中的索引

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

typedef struct dict{
    // 类型特定函数
    dictType *type;
    
    // 私有数据
    void *privdata;
    
    // 哈希表
    dictht ht[2];
    
    // rehash索引，不在rehash阶段时值为-1
    int rehashidx;
}dict;

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

type属性是一个指向dictType结构的指针，每个dictType结构保存了一簇用于操作特定类型键值对的函数，Redis会为用途不同的字典设置不同的类型特定函数

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;

privdata属性保存了需要传给类型特定函数的可选参数

ht属性是一个包含两个项的数组，数组中的每一个项都是一个dictht哈希表，一般情况下，字典只使用ht[0]哈希表，ht[1]哈希表在对ht[0]进行rehash的时候使用；rehashinx属性记录了rehash的进度，如果没有正在进行的rehash那么rehashidx的值为-1。

哈希算法

当要将一个新的键值对添加到字典中时，程序会先计算出键值对中键的哈希值，然后根据哈希值和哈希表大小掩码sizemask进行与运算来计算出该键值对在哈希表数组的索引：

# 使用字典设置的哈希函数来计算key的哈希值
hash = dict -> typr -> hashFunction(key);
# 使用哈希表的sizemask属性和哈希值进行与运算计算出索引
# 根据情况不同，ht[x]可能是ht[0]也可能是ht[1]
index = hash & dict -> ht[x].sizemask;

当有两个或以上的键值对分配到同一个索引上时，我们称这些键发生了冲突，即哈希冲突；Redis的哈希表使用链表法来解决哈希冲突，每个哈希表节点都有一个next指针，发生哈希冲突的键值对通过next指针构成一个单向链表，由于dictEntry组成的链表没有指向表头表尾的指针，所以为了速度考虑，程序总是将新节点添加到链表的头位置（复杂度为0(1)），如果放在表尾则需要通过哈希表数组索引上的dictEntry遍历整个链表，复杂度为O(N)

rehash

随着操作的不断执行，哈希表保存的键值对会逐渐的增多或减少，为了让哈希表的加载因子（load factor）保持在一个合理的范围之内，当哈希表中的键值对数量太多或太少时，程序需要对哈希表的大小进行相应的扩展和伸缩

当以下条件任意一个被满足时，程序将会自动对哈希表进行扩展操作：

服务器没有在执行BGSAVE和BGREWRITEAOF命令且哈希表的加载因子大于等于1
服务器正在执行BGSAVE和BGREWRITEAOF命令且哈希表的加载因子大于等于5

哈希表的加载因子计算方法：

# 加载因子 = 哈希表已保存节点数量 / 哈希表数组大小
load_factor = ht[0].used / ht[0].size

而判断程序是否在执行BGSAVE和BGREWRITEAOF命令是因为执行这两个命令的过程中Redis需要创建当前服务器进程的子进程，而大多数操作系统都采用写时复制（copy-on-write）技术来优化子进程的使用效率，所以在子进程存在期间，服务器会提高执行扩展操作所需的加载因子大小，从而尽可能避免在子进程存在期间进行哈希表的扩展操作，这可以避免不必要的内存写入操作，最大限度的节约内存

而当哈希表的加载因子小于0.1时，程序开始自动执行哈希表的收缩操作

哈希表的扩展和收缩工作可以通过rehash来完成，Redis对字典的哈希表执行rehash操作步骤如下：

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

渐进式rehash

为了避免哈希表数组中键值对数量过多导致rehash对服务器性能造成影响，服务器不是一次性将ht[0]中的元素全部rehash到ht[1]中的，而是多次的、渐进式的将ht[0]里面的键值对rehash到ht[1]中的，以下为哈希表渐进式rehash的步骤：

为ht[1]分配空间，此时字典同时拥有ht[0]和ht[1]两个哈希表
在字典中维持一个索引计数器变量rehashidx，并将它的值设为0，表示rehash工作正式开始
在rehash工作进行期间，每次对字典执行增删改查操作时，程序除了执行指定的操作外，还会顺便将ht[0]哈希表上rehashidx索引位置上的所有键值对rehash到ht[1]中，当rehash工作完成后将索引计数器变量rehashidx+1
当ht[0]上的所有键值对都rehash到ht[1]上之后，程序会将rehashidx设为-1，表示rehash操作已完成

渐进式rehash的好处是它采取分而治之的方式，将rehash键值对所需的计算工作均摊到对字典的每个增删改查操作上，从而避免了集中式rehash带来的巨大计算量对服务的影响

在渐进式rehash操作执行期间，对字典进行删除、更新、查询操作会在两个哈希表上进行，例如查找会先在ht[0]查找，如果没有找到再到ht[1]上进行查找。而在渐进式rehash执行期间对字典进行增加操作则只会在ht[1]上进行，这一措施保证了ht[0]中的键值对只增不减，并随着rehash的操作最终变成空表

总结

字典被广泛用于实现Redis的各种功能，包括数据库和哈希值
Redis中的字典使用哈希表作为底层实现，每个字典中有两个哈希表，一个用于保存数据，一个在rehash时使用
当字典被用作数据库的底层实现或哈希值的底层实现时，Redis使用MurmurHash2算法来计算键的哈希值
哈希表使用链地址法解决哈希冲突，被分配到同一索引的多个键值对会连接成一个单向链表
在对哈希表进行扩展或者收缩操作时，程序需要将现有哈希表包含的所有键值对rehash到新哈希表里面，并且这个rehash过程并不是一次性地完成的，而是渐进式地完成的。

标签：SDS,ht,链表,字符串,键值,哈希,test,随笔
From： https://www.cnblogs.com/edws/p/17153266.html