程序员人生 网站导航

redis学习笔记1--底层数据结构与对象

栏目:综合技术时间:2016-11-09 16:51:46

1、数据结构与对象

(1)简单动态字符串
1、SDS的定义(简单动态字符串)
struct sdshdr{
int len;//记录buf所保存字符串的长度
int free;//记录buf中未使用的字符串的长度
char buf[]; //字节数组,用于保存字符串数据
};
2、redis为何选用SDS而不是c字符串来作为字符串存储方式:
①:常数复杂度查询字符串的长度
②:杜绝缓冲区的溢出
③:减少修改字符串带来的内存重分配次数:空间预分配和惰性空间释放
④:2进制安全——可以保存文本数据和2进制数据
⑤:兼容部份c字符串函数
3、SDS的API
sdsnew、sdsempty、sdsfree、sdslen、sdsavail、sdsdup、sdsclear等。

(2)链表(链表键、发布与定阅、慢查询、监视器、客户端状态信息、客户端输出缓存区等功能都用到)
1、redis链表的实现
链表结构: head、tail、len、dup()、free()、match()
2、redis链表特性
特性:双端无环链表、存储表头表尾和链表长度等信息、保存不同类型的值

(3)字典(被广泛用于实现redis的各种功能,包括数据库和哈希键)
1、字典的实现
哈希表(dictht)、哈希表节点(dictEntry)、字典结构(dict)、键值对操作函数(dictType)。
2、哈希算法
采取的是MurmurHash2(2008年由Austin Appleby发明,速度快,规律输入也能随机散布,目前最新版本是MurmurHash3)。
3、解决键冲突
链地址法(新节点添加到链表的表头位置)
4、rehash(重新散列)
哈希表的扩大和收缩的实现方法:为ht[1]分配空间(大小为第1个大于下面数的2的n次方幂:ht[0].used*2(扩大)、ht[0].used(收缩))、将ht[0]的键值对迁移到ht[1]上面、迁移完成以后把释放ht[0]将ht[1]置为ht[0]并在ht[1]创建1个空白的哈希表。
扩大和收缩的履行条件:扩大(服务器目前没有履行BGSAVE命令或是BGREWRITEAOF命令,并且哈希表的负载因子大于等于1;或是正在履行BGSAVE命令或是BGREWRITEAOF命令并且哈希表的负载因子大于等于5)、收缩(哈希表的的负载因子小于0.1)。
5、渐进式rehash
rehashidx表明rehash的进度
6、字典API
dictCreate、dictAdd、dictReplace、dictFetchValue、dictGetRandomkey、dictDelete、dictRelease。

(4)跳表(以空间换时间,1个用于实现有序集合,另外一个用于集群节点的内部数据结构)
跳表的原理介绍:http://www.cnblogs.com/xuqiang/archive/2011/05/22/2053516.html
1、跳表的实现
zskiplist、skiplistNode两种结构组成
2、跳表的API
zslCreate、zslFree、zslDelete、zslInsert等。

(5)整数集合(intset)
1、整数集合的实现
typedef struct intset{
uint32_t encoding;//编码方式
uint32_t length;//集合所包括的元素数量
int8_t contents[];//保存元素的数组
}intset;

2、升级(upgrade)
当添加的新元素的类型比集合中现有所有的元素的类型都要长时,整数集合需要进行升级。
步骤:分配底层数组空间、将现有的数组进行转换到新元素的相同类型、将新元素添加到底层数组中去。

3、升级的好处
①提升灵活性
②节俭内存

4、降级
整数集合不支持降级操作,1旦对数组进行了升级操作以后, 编码就会1直保持在升级的状态。

5、整数集合的API
intsetNew、intsetAdd、intsetRemove、intsetFind、intsetRandom、intsetGet、intsetLen、intsetBlobLen

(6)紧缩列表(ziplist)
紧缩列表是列表键和哈希键的底层实现之1。当1个列表建或哈希键值包括少许的列表项或键值对时,并且每一个列表项或键值对要末是小整数值,要末就是长度比较短的字符串,那末redis就会采取紧缩列表来做其底层实现。

1、紧缩列表的构成
紧缩列表是由1系列特殊编码的连续内存块组成的顺序型(sequential)的数据结构。zlbytes(所占内存字节数)、zltail(紧缩列表尾部距离起始地址多少字节)、zllen(字节的数量)、entryX(列表节点)、zlend(列表末真个特殊值标记)。

2、紧缩列表节点的构成
previous_entry_length(记录前1个节点的长度:小于254字节时,此值为1个字节并保存长度;当大于等于254字节时,此值为5个字节,第1字节为0xFE,而以后4个字节保存前1个节点的长度)、encoding(记录节点content属性所保存数据的类型和长度:分为字节数组(1字节00、2字节01和5字节01开头,节点的长度结尾)和整数数组(11开头,后面表示整数的类型))、content(保存节点的值)3个部份组成。

3、连锁更新
要多个连续的长度介于250字节和253字节之间的节点,才会产生连锁更新,这类情况很少见;及时出现连锁更新,但只要更新的节点不多,就不会对性能造成多大的影响。因此实际使用操作函数的时候,没必要担心连锁更新会影响紧缩列表的性能。

4、紧缩列表的API
ziplistNew、ziplistPush、ziplistInsert、ziplistIndex、ziplistFind、ziplistNext、ziplistPrev、ziplistGet、ziplistDelete、ziplistDeleteRange、ziplistBlobLen、ziplistLen。

(7)对象
redis在履行命令之前,会根据对象的类型来判断1个对象是不是可以履行给定的命令; 针对不同的使用处景,为对象设置多种不同的数据结构实现,从而优化对象在不同场景的使用效力;除此,对象系统还实现了基于援用计数技术的内存回收机制,当程序不再使用某个对象的时候,对应的内存自动释放;另外还实现了对象同享机制,在适当的条件下,通过量个数据库键同享同1个对象来节俭内存;对象还带有访问时间记录信息,该信息可以用于计算数据库键的空转时长,在服务器启动了maxmemory功能的情况下,空转时长较长的那个键可能会优先被服务器删除。

1、对象的类型和编码
redisObject(type(类型)、encoding(编码)、ptr(指向底层数据结构的指针))。
REDIS_ENCODING_INT(使用整数值实现的字符串对象)
REDIS_ENCODING_EMBSTR(使用embstr编码的简单动态字符串实现的字符串对象)
REDIS_ENCODING_RAW(使用简单动态字符串实现的字符串对象)
REDIS_ENCODING_ZIPLIST(使用紧缩列表实现的列表对象、哈希对象、有序集合对象)
REDIS_ENCODING_LINKEDLIST(使用双端链表实现的列表对象)
REDIS_ENCODING_HT(使用字典实现的哈希对象、集合对象)
REDIS_ENCODING_INTSET(使用整数集合实现的集合对象)
REDIS_ENCODING_SKIPLIST(使用跳跃表和字典实现的有序集合对象)

2、字符串对象(int、embstr、raw编码方式)
编码的转换:embstr没有相应的修改程序,因此履行修改命令的时候,embstr格式的字符串总是先转换成raw再履行修改命令。

字符串命令的实现:对应各自的字符串操作API

3、列表对象(ziplist和linkedlist)
条件:对象的编码可使用ziplist(列表对象保存的所以字符串的长度都小于64字节并且列表保存的元素个数小于512)或linkedlist(除以上条件以外)。

**列表命令的实现:**ziplist对应ziplist的API函数;linkedlist对应linkedlist的API函数。

关于现在新的redis使用quicklist,结合了ziplist和linkedlist的优点,详情请参考:http://blog.csdn.net/a809146548/article/details/52013225

4、哈希对象(ziplist和hashtable)
条件:哈希对象保存的所有键值对的键和值的字符串长度都小于64字节,并且哈希对象保存的键值对数量小于512个就使用ziplist编码,否则使用hashtable编码。(这两个上限值都可以修改,配置文件中的hash-max-ziplist-value和hash-max-ziplist-entries)。

ziplist:同1键值对的两个节点紧挨在1起,键在前值在后;先添加的键值对在表头,后添加的在列表的表尾。

hashtable:字典的每一个键和值都是1个字符串对象。

哈希命令的实现:ziplist和hashtable对应的API。

5、集合对象(intset和hashtable)
转换编码的条件:集合对象保存的所有元素都是整数值并且元素的数量不超过512个 ,使用intset编码,否则使用hashtable编码。(第2个条件可以修改,参考配置文件hash-max-intset-entries)

集合命令的实现:对应intset和hashtable的API。
6、有序集合对象(ziplist和skiplist)
ziplist:每一个集合元素使用两个紧挨在1起的紧缩列表节点来保存,第1个节点保存元素的成员,第2个元素保存元素的分值;紧缩列表内的集合元素依照分值的大小进行排序,分值小的排在靠近表头的位置,分值大的元素排在靠近表尾的位置。

skiplist:使用zset结构作为底层实现,zset包括1个字典和1个跳跃表。同时使用字典和跳跃表能够同时保存字典O(1)的查找成员复杂度,也能保存跳跃表范围型操作的优点。字典和跳跃表同享元素的成员和分值,所以不会造成任何的数据重复,也不会因此而浪费内存。

编码的转换条件:有序集合的元素个数小于128个并且保存的所有元素成员的长度都小于64个字节时采取ziplist编码;否则使用skiplist编码。(这两个上限值都可以修改,配置文件中的hash-max-ziplist-value和hash-max-ziplist-entries)

有序集合命令的实现:对应ziplist和zset(skiplist)API。

7、类型检查与命令多态
命令分类:1种是对任何类型的键履行(DEL、EXPIRE等);另外一类只能对特定的类型的键履行(SET、HDEL、SADD等)。

类型的检查(先检查key是不是是对应的类型),多态命令的履行(基于类型的多态(DEL),基于编码的多态(LLEN))。

8、内存回收
通过援用计数(refcount)进行对象的内存释放,为0时内存释放。

增加、减少和重置对象的援用计数的API:incrRefCount、decrRefCount、 resetRefCount。

0~9999在redis内部已创建同享字符串。

对象的生命周期:创建对象、操作对象、释放对象。

9、对象同享
键值相同的时候,同享1个字符串对象,相应的援用计数增加。(创建同享字符串对象的数量可以通过修改redis.h/REDIS_SHARED_INTEGERS常量来修改)

为何只同享字符串不同享其他对象:验证复杂度太高,CPU耗时多。
Object refcount key;
10、对象空转时长
Object idletime key;
配置文件的maxmemory选项和maxmemory-policy选项的说明有介绍对空转时间较长的那部份键进行优先释放。

------分隔线----------------------------
------分隔线----------------------------

最新技术推荐