做后期的网站有哪些,cms网站建设,南昌seo站内优化,百度投放广告一天多少钱Redis设计与实现读书笔记 Redis设计与实现[^1]简单动态字符串SDS的基础定义与C字符串的差别常数获取长度杜绝缓冲区溢出减少修改字符串时带来的内存重分配次数二进制安全函数兼容 链表链表和链表节点的实现 字典字典的实现哈希表定义哈希表节点定义字典定义 哈希算法解决键冲突… Redis设计与实现读书笔记 Redis设计与实现[^1]简单动态字符串SDS的基础定义与C字符串的差别常数获取长度杜绝缓冲区溢出减少修改字符串时带来的内存重分配次数二进制安全函数兼容 链表链表和链表节点的实现 字典字典的实现哈希表定义哈希表节点定义字典定义 哈希算法解决键冲突 Redis设计与实现1
简单动态字符串
SDS的基础定义
代码结构示例
struct sdshdr {//记录buf数组中已使用字节的数量//等于SDS所保存字符串的长度int len;//记录buf数组中未使用字节的数量int free;//字节数组用于保存字符串char buf[];
};free属性的值为0表示这个SDS没有分配任何未使用空间。len属性的值为5表示这个SDS保存了一个五字节长的字符串。buf属性是一个char类型的数组数组的前五个字节分别保存了’R’、‘e’、‘d’、‘i’、‘s’五个字符而最后一个字节则保存了空字符’\0’。 SDS遵循C字符串以空字符结尾的惯例保存空字符的1字节空间不计算在SDS的len属性里面并且为空字符分配额外的1字节空间以及添加空字符到字符串末尾等操作都是由SDS函数自动完成的所以这个空字符对于SDS的使用者来说是完全透明的。遵循空字符结尾这一惯例的好处是SDS可以直接重用一部分C字符串函数库里面的函数。 与C字符串的差别
C语言使用的这种简单的字符串表示方式并不能满足Redis对字符串在安全性、效率以及功能方面的要求所以Redis的作者开发了SDS这种字符串数据结构
常数获取长度
因为C字符串并不记录自身的长度信息所以为了获取一个C字符串的长度程序必须遍历整个字符串对遇到的每个字符进行计数直到遇到代表字符串结尾的空字符为止这个操作的复杂度为ON。 和C字符串不同因为SDS在len属性中记录了SDS本身的长度所以获取一个SDS长度的复杂度仅为O1。 这是属于功能和效率上的考虑使用更加简洁高效 杜绝缓冲区溢出
因为C字符串不记录自身的长度内存和长度担保需要手动控制否则不小心就会导致溢出覆盖掉其他内存中存储的字符串值安全性上是有隐患的。 与C字符串不同SDS的空间分配策略完全杜绝了发生缓冲区溢出的可能性当SDS API需要对SDS进行修改时API会先检查SDS的空间是否满足修改所需的要求如果不满足的话API会自动将SDS的空间扩展至执行修改所需的大小然后才执行实际的修改操作所以使用SDS既不需要手动修改SDS的空间大小也不会出现前面所说的缓冲区溢出问题。 这是属于安全性上的考虑 减少修改字符串时带来的内存重分配次数
为了避免c字符串的内存重新分配动态变化带来的性能损耗而设计这应该也是SDS设计的主要原因 SDS通过未使用空间解除了字符串长度和底层数组长度之间的关联在SDS中buf数组的长度不一定就是字符数量加一数组里面可以包含未使用的字节而这些字节的数量就由SDS的free属性记录。通过未使用空间SDS实现了空间预分配和惰性空间释放两种优化策略。
空间预分配用于优化SDS的字符串增长操作当SDS的API对一个SDS进行修改并且需要对SDS进行空间扩展的时候程序不仅会为SDS分配修改所必须要的空间还会为SDS分配额外的未使用空间。 如果对SDS进行修改之后SDS的长度也即是len属性的值将小于1MB那么程序分配和len属性同样大小的未使用空间这时SDS len属性的值将和free属性的值相同。举个例子如果进行修改之后SDS的len将变成13字节那么程序也会分配13字节的未使用空间SDS的buf数组的实际长度将变成1313127字节额外的一字节用于保存空字符。如果对SDS进行修改之后SDS的长度将大于等于1MB那么程序会分配1MB的未使用空间。举个例子如果进行修改之后SDS的len将变成30MB那么程序会分配1MB的未使用空间SDS的buf数组的实际长度将为30MB1MB1byte。 惰性空间释放用于优化SDS的字符串缩短操作当SDS的API需要缩短SDS保存的字符串时程序并不立即使用内存重分配来回收缩短后多出来的字节而是使用free属性将这些字节的数量记录起来并等待将来使用。
二进制安全
SDS的API都是二进制安全的binary-safe所有SDS API都会以处理二进制的方式来处理SDS存放在buf数组里的数据程序不会对其中的数据做任何限制、过滤、或者假设数据在写入时是什么样的它被读取时就是什么样。这也是我们将SDS的buf属性称为字节数组的原因——Redis不是用这个数组来保存字符而是用它来保存一系列二进制数据。 通过使用二进制安全的SDS而不是C字符串使得Redis不仅可以保存文本数据还可以保存任意格式的二进制数据。这是安全性和功能性上的胜利。 函数兼容
通过遵循C字符串以空字符即/0结尾的惯例SDS可以在有需要时重用string.h函数库从而避免了不必要的代码重复。
链表
链表和链表节点的实现
每个链表节点使用一个adlist.h/listNode结构来表示
typedef struct listNode {// 前置节点struct listNode * prev;// 后置节点struct listNode * next;//节点的值void * value;
}listNode;虽然仅仅使用多个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;如图所示 Redis的链表实现的特性可以总结如下
双端链表节点带有prev和next指针获取某个节点的前置节点和后置节点的复杂度都是O1。无环表头节点的prev指针和表尾节点的next指针都指向NULL对链表的访问以NULL为终点。带表头指针和表尾指针通过list结构的head指针和tail指针程序获取链表的表头节点和表尾节点的复杂度为O1。带链表长度计数器程序使用list结构的len属性来对list持有的链表节点进行计数程序获取链表中节点数量的复杂度为O1。多态链表节点使用void*指针来保存节点值并且可以通过list结构的dup、free、match三个属性为节点值设置类型特定函数所以链表可以用于保存各种不同类型的值。 链表被广泛用于实现Redis的各种功能比如列表键、发布与订阅、慢查询、监视器等。 字典
字典的实现
哈希表定义
Redis字典所使用的哈希表由dict.h/dictht结构定义
typedef struct dictht {//哈希表数组dictEntry **table;//哈希表大小unsigned long size;//哈希表大小掩码用于计算索引值//总是等于size-1unsigned long sizemask;//该哈希表已有节点的数量unsigned long used;
} dictht;table属性是一个数组数组中的每个元素都是一个指向dict.h/dictEntry结构的指针每个dictEntry结构保存着一个键值对。size属性记录了哈希表的大小也即是table数组的大小而used属性则记录了哈希表目前已有节点键值对的数量。sizemask属性的值总是等于size-1这个属性和哈希值一起决定一个键应该被放到table数组的哪个索引上面。
哈希表节点定义
哈希表节点使用dictEntry结构表示每个dictEntry结构都保存着一个键值对
typedef struct dictEntry {//键void *key;//值union{void *val;uint64_tu64;int64_ts64;} v;//指向下个哈希表节点形成链表struct dictEntry *next;
} dictEntry;key属性保存着键值对中的键而v属性则保存着键值对中的值其中键值对的值可以是一个指针或者是一个uint64_t整数又或者是一个int64_t整数。next属性是指向另一个哈希表节点的指针这个指针可以将多个哈希值相同的键值对连接在一次以此来解决键冲突collision的问题。
字典定义
Redis中的字典由dict.h/dict结构表示
typedef struct dict {//类型特定函数dictType *type;//私有数据void *privdata;//哈希表dictht ht[2];// rehash索引//当rehash不在进行时值为-1in trehashidx; /* rehashing not in progress if rehashidx -1 */
} dict;type属性和privdata属性是针对不同类型的键值对为创建多态字典而设置的
type属性是一个指向dictType结构的指针每个dictType结构保存了一簇用于操作特定类型键值对的函数Redis会为用途不同的字典设置不同的类型特定函数。而privdata属性则保存了需要传给那些类型特定函数的可选参数。
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;ht属性是一个包含两个项的数组数组中的每个项都是一个dictht哈希表一般情况下字典只使用ht[0]哈希表ht[1]哈希表只会在对ht[0]哈希表进行rehash时使用。除了ht[1]之外另一个和rehash有关的属性就是rehashidx它记录了rehash目前的进度如果目前没有在进行rehash那么它的值为-1。
哈希算法
Redis计算哈希值和索引值的方法如下
#使用字典设置的哈希函数计算键key的哈希值
hash dict-type-hashFunction(key);
#使用哈希表的sizemask属性和哈希值计算出索引值
#根据情况不同ht[x]可以是ht[0]或者ht[1]
index hash dict-ht[x].sizemask;当字典被用作数据库的底层实现或者哈希键的底层实现时Redis使用MurmurHash2算法来计算键的哈希值。2
解决键冲突
Redis的哈希表使用链地址法separate chaining来解决键冲突每个哈希表节点都有一个next指针多个哈希表节点可以用next指针构成一个单向链表被分配到同一个索引上的多个节点可以用这个单向链表连接起来这就解决了键冲突的问题。 这块没什么好说的jdk最早期的实现包括现在jdk初始的实现也都是用的这个办法缺点在于键冲突过多时链表寻找也会比较慢导致效率下降 作者是黄健宏2014-06出版redis的版本比较老基于Redis 3.0来写的不过基本的思路和大概的设计实现是可以参考借鉴的。 ↩︎ 现在用的什么算法没有考证留一个代办项吧 ↩︎
