房产发布网站建设,如何查企业的工商信息,德邦公司网站建设特点,建设银行行号网站查询是什么意思一、Redis数据结构-动态字符串
我们都知道Redis中保存的Key是字符串#xff0c;value往往是字符串或者字符串的集合。可见字符串是Redis中最常用的一种数据结构。
不过Redis没有直接使用C语言中的字符串#xff0c;因为C语言字符串存在很多问题#xff1a;
获取字符串长度…一、Redis数据结构-动态字符串
我们都知道Redis中保存的Key是字符串value往往是字符串或者字符串的集合。可见字符串是Redis中最常用的一种数据结构。
不过Redis没有直接使用C语言中的字符串因为C语言字符串存在很多问题
获取字符串长度的需要通过运算。非二进制安全。不可修改。
Redis构建了一种新的字符串结构称为简单动态字符串Simple Dynamic String简称SDS。 例如我们执行命令 那么Redis将在底层创建两个SDS其中一个是包含“name”的SDS另一个是包含“KEKE”的SDS。
Redis是C语言实现的其中SDS是一个结构体源码如下 例如一个包含字符串“name”的sds结构如下
SDS之所以叫做动态字符串是因为它具备动态扩容的能力例如一个内容为“hi”的SDS
假如我们要给SDS追加一段字符串“,Amy”这里首先会申请新内存空间
如果新字符串小于1M则新空间为扩展后字符串长度的两倍1
如果新字符串大于1M则新空间为扩展后字符串长度1M1。称为内存预分配。
优点
获取字符串长度的时间复杂度为O(1)。支持动态扩容。减少内存分配次数。二进制安全。
Redis数据结构-intset
IntSet是Redis中set集合的一种实现方式基于整数数组来实现并且具备长度可变、有序等特征。 结构如下 其中的encoding包含三种模式表示存储的整数大小不同 现在数组中每个数字都在int16_t的范围内因此采用的编码方式是INTSET_ENC_INT16每部分占用的字节大小为 encoding4字节 length4字节 contents2字节 * 3 6字节 我们向该其中添加一个数字50000这个数字超出了int16_t的范围intset会自动升级编码方式到合适的大小。 以当前案例来说流程如下
升级编码为INTSET_ENC_INT32, 每个整数占4字节并按照新的编码方式及元素个数扩容数组。倒序依次将数组中的元素拷贝到扩容后的正确位置。将待添加的元素放入数组末尾。最后将inset的encoding属性改为INTSET_ENC_INT32将length属性改为4。 源码如下
intset *intsetAdd(intset *is, int64_t value, uint8_t *success){uint8_t valenc _intsetValueEncoding(value);//获取当前值编码uint32_t pos;//要插入的位置if (success) *success 1;//判断编码是不是超过了当前intset的编码if (valenc intrev32ifbe(is-encoding)){//超出编码需要升级return intsetUpgradeAndAdd(is,value);} else {//在当前intset中查找值与value—样的元素的角标posif (intsetSearch(is,value,pos)) {if (success)*success O;//如果找到了则无需插入直接结束并返回失败return is;}//数组扩容is intsetResize(is,intrev32ifbe(is-length)1);//移动数组中pos之后的元素到pos1给新元素腾出空间if (pos intrev32ifbe(is-length)) intsetMoveTail(is,pos,pos1);}//插入新元素_intsetSet(is,pos,value);/重置元素长度is-length intrev32ifbe(intrev32ifbe(is-length) 1);return is;
}static intset *intsetUpgradeAndAdd(intset *is, int64_t value){//获取当前intset编码uint8_t curenc intrev32ifbe(is-encoding);//获取新编码uint8_t newenc _intsetValueEncoding(value);//获取元素个数int length intrev32ifbe(is-length);//判断新元素是大于0还是小于0小于0插入队首、大于0插入队尾int prepend value 0 ? 1 : 0;//重置编码为新编码is-encoding intrev32ifbe(newenc);//重置数组大小is intsetResize(is,intrev32ifbe(is-length)1);//倒序遍历逐个搬运元素到新的位置,_intsetGetEncoded按照旧编码方式查找旧元素while(length--) // _intsetSet按照新编码方式插入新元素intsetSet(is,lengthprepend, _intsetGetEncoded(is,length,curenc));//插入新元素prepend决定是队首还是队尾if (prepend)_intsetSet(is,0,value);else_intsetSet(is,intrev32ifbe(is-length),value);//修改数组长度is- length intrev32ifbe(intrev32ifbe(is-length) 1);return is;
}
小总结
Intset可以看做是特殊的整数数组具备一些特点
Redis会确保Intset中的元素唯一、有序。具备类型升级机制可以节省内存空间。底层采用二分查找方式来查询。
二、 Redis数据结构-Dict
我们知道Redis是一个键值型Key-Value Pair的数据库我们可以根据键实现快速的增删改查。而键与值的映射关系正是通过Dict来实现的。 Dict由三部分组成分别是哈希表DictHashTable、哈希节点DictEntry、字典Dict。
typedef struct dictht {// entry数组//数组中保存的是指向entry的指针dictEntry **table;//哈希表大小unsigned long size;//哈希表大小的掩码总等于size - 1unsigned long sizemask;// entry个数unsigned long used;
} dictht;typedef struct dictEntry {void *key;//键union {void *val;uint64_t u64;int64_t s64;double d;} v;//值//下一个Entry的指针struct dictEntry *next;
} dictEntry;
当我们向Dict添加键值对时Redis首先根据key计算出hash值h然后利用 h sizemask来计算元素应该存储到数组中的哪个索引位置。我们存储k1v1假设k1的哈希值h 1则13 1因此k1v1要存储到数组角标1位置。
Dict由三部分组成分别是哈希表DictHashTable、哈希节点DictEntry、字典Dict。
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;typedef struct dictht {// entry数组//数组中保存的是指向entry的指针dictEntry **table;//哈希表大小unsigned long size;//哈希表大小的掩码总等于size - 1unsigned long sizemask;// entry个数unsigned long used;
}dictht;typedef struct dictEntry {void *key;//键union {void *val;uint64_t u64;int64_t s64;double d;} v;//值//下一个Entry的指针struct dictEntry *next;
}dictEntry;typedef struct dict {dictType *type; // dict类型内置不同的hash函数void *privdata;//私有数据在做特殊hash运算时用dictht ht[2];//一个Dict包含两个哈希表其中一个是当前数据另一个一般是空rehash时使用long rehashidx; // rehash的进度-1表示未进行int16_t pauserehash; // rehash是否暂停1则暂停O则继续
} dict; Dict的扩容
Dict中的HashTable就是数组结合单向链表的实现当集合中元素较多时必然导致哈希冲突增多链表过长则查询效率会大大降低。 Dict在每次新增键值对时都会检查负载因子LoadFactor used/size 满足以下两种情况时会触发哈希表扩容 哈希表的 LoadFactor 1并且服务器没有执行 BGSAVE 或者 BGREWRITEAOF 等后台进程 哈希表的 LoadFactor 5
static int dictExpandlfNeeded(dict*d){//如果正在rehash则返回okif (dictlsRehashing(d)) return DICT_OK;//如果哈希表为空则初始化哈希表为默认大小:4if (d-ht[0].size 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);//当负载因子(used/size)达到1以上并且当前没有进行bgrewrite等子进程操作//或者负载因子超过5则进行dictExpand 也就是扩容if (d-ht[0].used d-ht[0].size i(dict_can_resize || d-ht[0].used/d-ht[0].size dict_force_resize_ratio){//扩容大小为used 1底层会对扩容大小做判断实际上找的是第一个大于等于used1的2^nreturn dictExpand(d, d-ht[0].used 1);}return DICT_OK;
}// t_hash.c # hashTypeDeleted()
//……
if (dictDelete((dict*)o-ptr, field) C_OK){deleted 1;//删除成功后检查是否需要重置Dict大小如果需要则调用dictResize重置/*Always check if the dictionary needs a resize after a delete.*/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.1return (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 |l dictlsRehashing(d))return DICT_ERR;//获取used也就是entry个数minimal d-ht[0].used;//如果used小于4则重置为4if (minimal DICT_HT_INITIAL_SIZE)minimal DICT_HT_INITIAL_SIZE;//重置大小为minimal其实是第一个大于等于minimal的2^nreturn dictExpand(d, minimal);
}
Dict的rehash
不管是扩容还是收缩必定会创建新的哈希表导致哈希表的size和sizemask变化而key的查询与sizemask有关。因此必须对哈希表中的每一个key重新计算索引插入新的哈希表这个过程称为rehash。过程是这样的 计算新hash表的realeSize值取决于当前要做的是扩容还是收缩 如果是扩容则新size为第一个大于等于dict.ht[0].used 1的2^n。如果是收缩则新size为第一个大于等于dict.ht[0].used的2^n 不得小于4。 按照新的realeSize申请内存空间创建dictht并赋值给dict.ht[1]。 设置dict.rehashidx 0标示开始rehash。 将dict.ht[0]中的每一个dictEntry都rehash到dict.ht[1]。 将dict.ht[1]赋值给dict.ht[0]给dict.ht[1]初始化为空哈希表释放原来的dict.ht[0]的内存。 将rehashidx赋值为-1代表rehash结束。 在rehash过程中新增操作则直接写入ht[1]查询、修改和删除则会在dict.ht[0]和dict.ht[1]依次查找并执行。这样可以确保ht[0]的数据只减不增随着rehash最终为空。
整个过程可以描述成 小总结
Dict的结构
类似java的HashTable底层是数组加链表来解决哈希冲突。Dict包含两个哈希表ht[0]平常用ht[1]用来rehash。
Dict的伸缩
当LoadFactor大于5或者LoadFactor大于1并且没有子进程任务时Dict扩容。当LoadFactor小于0.1时Dict收缩。扩容大小为第一个大于等于used 1的2^n。收缩大小为第一个大于等于used 的2^n。Dict采用渐进式rehash每次访问Dict时执行一次rehash。rehash时ht[0]只减不增新增操作只在ht[1]执行其它操作在两个哈希表。
三、 Redis数据结构-ZipList
ZipList 是一种特殊的“双端链表” 由一系列特殊编码的连续内存块组成。可以在任意一端进行压入/弹出操作, 并且该操作的时间复杂度为 O(1)。 属性类型长度用途zlbytesuint32_t4 字节记录整个压缩列表占用的内存字节数zltailuint32_t4 字节记录压缩列表表尾节点距离压缩列表的起始地址有多少字节通过这个偏移量可以确定表尾节点的地址。zllenuint16_t2 字节记录了压缩列表包含的节点数量。 最大值为UINT16_MAX 65534如果超过这个值此处会记录为65535但节点的真实数量需要遍历整个压缩列表才能计算得出。entry列表节点不定压缩列表包含的各个节点节点的长度由节点保存的内容决定。zlenduint8_t1 字节特殊值 0xFF 十进制 255 用于标记压缩列表的末端。
ZipListEntry
ZipList 中的Entry并不像普通链表那样记录前后节点的指针因为记录两个指针要占用16个字节浪费内存。而是采用了下面的结构 previous_entry_length前一节点的长度占1个或5个字节。 如果前一节点的长度小于254字节则采用1个字节来保存这个长度值。如果前一节点的长度大于254字节则采用5个字节来保存这个长度值第一个字节为0xfe后四个字节才是真实长度数据。 encoding编码属性记录content的数据类型字符串还是整数以及长度占用1个、2个或5个字节。 contents负责保存节点的数据可以是字符串或整数。
ZipList中所有存储长度的数值均采用小端字节序即低位字节在前高位字节在后。例如数值0x1234采用小端字节序后实际存储值为0x3412。
Encoding编码
ZipListEntry中的encoding编码分为字符串和整数两种 字符串如果encoding是以“00”、“01”或者“10”开头则证明content是字符串。
编码编码长度字符串大小|00pppppp|1 bytes 63 bytes|01pppppp|qqqqqqqq|2 bytes 16383 bytes|10000000|qqqqqqqq|rrrrrrrr|ssssssss|tttttttt|5 bytes 4294967295 bytes
例如我们要保存字符串“ab”和 “bc”。 ZipListEntry中的encoding编码分为字符串和整数两种
整数如果encoding是以“11”开始则证明content是整数且encoding固定只占用1个字节。
编码编码长度整数类型110000001int16_t2 bytes110100001int32_t4 bytes111000001int64_t8 bytes11110000124位有符整数(3 bytes)1111111018位有符整数(1 bytes)1111xxxx1直接在xxxx位置保存数值范围从0001~1101减1后结果为实际值 Redis数据结构-ZipList的连锁更新问题
ZipList的每个Entry都包含previous_entry_length来记录上一个节点的大小长度是1个或5个字节
如果前一节点的长度小于254字节则采用1个字节来保存这个长度值。如果前一节点的长度大于等于254字节则采用5个字节来保存这个长度值第一个字节为0xfe后四个字节才是真实长度数据。
现在假设我们有N个连续的、长度为250~253字节之间的entry因此entry的previous_entry_length属性用1个字节即可表示如图所示 ZipList这种特殊情况下产生的连续多次空间扩展操作称之为连锁更新Cascade Update。新增、删除都可能导致连锁更新的发生。
小总结
ZipList特性
压缩列表的可以看做一种连续内存空间的双向链表。列表的节点之间不是通过指针连接而是记录上一节点和本节点长度来寻址内存占用较低。如果列表数据过多导致链表过长可能影响查询性能。增或删较大数据时有可能发生连续更新问题。
