欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

redis的五种基本数据类型及其内部实现

程序员文章站 2022-06-12 19:35:25
...

一、redis的五种数据类型

redis作为目前最流行的Key-Value类型的内存数据库,对于数据库的操作都在内存中进行,并可定期的将数据异步的持久化到磁盘之上。由于是纯内存的操作,因此它的性能比普通的关系型数据库高出很多,同时由于是单线程串行的执行指令,因此也避免了加锁和释放锁的开销。相比于memcache,redis的每个value值最大可存储1GB,而memcache只有10MB,同时redis在速度上也快于memcache,还可以持久化。redis最大的特点则是,它可以支持五种基本数据类型,分别是字符串(string),列表(list),集合(set),有序集合(zset)以及哈希(hash),下面具体介绍下它们的特点以及内部实现。

二、redisObject

在redis中每个value都是以一个redisObject结构来表示,如下:

typedef struct redisObject{
//类型
unsigned type:4;
//编码
unsigned encoding:4;
//指向底层数据结构的指针
void *ptr;
//引用计数器
int refCount;
//最后一次的访问时间
unsigned lru:
}
  • type:
    type就是指这个对象的数据类型,即我们平常所认知的redis的五种数据类型,可以通过TYPE命令查看一个对象的数据类型:
127.0.0.1:6379> set a 123
OK
127.0.0.1:6379> type a
string
127.0.0.1:6379> hmset b name jack age 12
OK
127.0.0.1:6379> type b
hash
127.0.0.1:6379> lpush c 1 2 3
(integer) 3
127.0.0.1:6379> type c
list
127.0.0.1:6379> sadd d 1 2 3
(integer) 3
127.0.0.1:6379> type d
set
127.0.0.1:6379> zadd e 2 a 3 b
(integer) 2
127.0.0.1:6379> type e
zset
127.0.0.1:6379> 
  • encoding:
    表示redisObject对象的底层编码实现,主要有简单动态字符串,链表,字典,跳跃表,整数集合以及压缩列表,每一个value都是由两种及以上的上述编码所构成,后面详细展出
  • *ptr
    用于指向底层实现数据结构的指针
  • lru:
    最后一次访问该对象的时间,可以通过Object idletime查看当前时间距离该键的lru的时间,即空转时间如下:
127.0.0.1:6379> set cbd 123
OK
127.0.0.1:6379> object idletime cbd
(integer) 90
127.0.0.1:6379> object idletime cbd
(integer) 95
127.0.0.1:6379> object idletime cbd
(integer) 98
127.0.0.1:6379> get cbd //访问了该键,因此lru重置
"123"
127.0.0.1:6379> object idletime cbd
(integer) 3
127.0.0.1:6379> 
  • refCount
    引用计数器,当创建一个对象的时间便将它的值初始化为1,当它被其它程序引用之时则加1,不再被引用则减1,当它的引用计数值变为0时,对象所占用的内存就会被释放。因此它主要有两个用途,内存回收的标志以及用于对象共享。
    对象共享:当新建的两个或多个键都是整数值并且相同时,则它们的键会共享这一个值对象,这样可以减少内存的分配和回收,可以用OBJECT REFCOUNT查看引用情况,如下:
127.0.0.1:6379> set first 123
OK
127.0.0.1:6379> OBJECT refcount first
(integer) 1
127.0.0.1:6379> set second 123
OK
127.0.0.1:6379> OBJECT refcount second
(integer) 2
127.0.0.1:6379> OBJECT refcount first
(integer) 2
127.0.0.1:6379> 

redis在初始化服务器之时,会默认创建包含了值为0-9999的对象,当新建的键的值处于这个范围之时,则直接添加引用即可。

三、字符串对象

简单动态字符串(SDS):
字符串作为redis中最常见的数据结构,所有键值对的键,字符串对象的值底层都是由简单动态字符串实现的。在redis中,它并未使用C语言中的字符串,而是自己实现了一种叫做SDS的数据结构,它的结构表示如下:

struct sdshdr{
//记录buf数组中已使用字节的长度
int len;
//记录buf数组中剩余空间的长度
int free;
//字节数组,用于存储字符串
char buf[];
};

一个SDS示例如下:
redis的五种基本数据类型及其内部实现
当free为0时表示没有任何未使用的空间,len表示字符串的长度,buf中存储每一个字节以及空字符,由于SDS遵循了C字符串以为’\0’结尾的特点,因此它也可以直接重用部分C函数库里的函数。
相比于C字符串,SDS具有以下特点:获取长度的时间复杂度为O(1),因为len直接保存了当前字符串的长度;避免缓存区溢出,当C字符串进行拼接之时,如果未事先对当前字符串的空间进行调整,则可能会导致当前字符串的数据溢出,导致拼接过来的字符串内容被意外的修改,而SDS在拼接之前会进行自动的调整和扩展;减少内存分配次数,在SDS拼接发生以后,如果此时的len小于1MB则它会多分配和len大小相同的未使用空间,用free表示,如果大于1MB,则会分配1MB的为使用空间;惰性空间释放,当字符串进行缩短的时候,程序并不会立即回收空间(也可以调用API立即释放),而是记录到free之中,以便于后序拼接的使用。

编码:
字符串对象的编码可以是int、raw或者embstr。其中int表示整型的值,embstr表示小于等于39字节的字符串值,剩余的均用raw表示,并且int和embstr都是只读的,一旦发生了append操作,即会转换为raw。如下:

127.0.0.1:6379> set age 12
OK
127.0.0.1:6379> Object encoding age
"int"
127.0.0.1:6379> APPEND age 3
(integer) 3
127.0.0.1:6379> Object encoding age
"raw"
127.0.0.1:6379> set name jack
OK
127.0.0.1:6379> Object encoding name
"embstr"
127.0.0.1:6379> APPEND name ja
(integer) 6
127.0.0.1:6379> Object encoding name
"raw"

四、列表对象

链表提供了节点重排以及节点顺序访问的能力,redis中的列表对象主要是由压缩列表和双端链表实现。
双端链表(linkedlist)结构如下:

type struct list{
//表头节点
listNode *head;
//表尾节点
listNode *tail;
//包含的节点总数
unsigned long len;
//一些操作函数 dup free match...
};

一个链表示例:
redis的五种基本数据类型及其内部实现
其中每个节点都有一个prev指针和一个next指针,而节点中的value则是列表对象具体的值。
压缩列表(ziplist)结构如下:

type struct ziplist{
//整个压缩列表的字节数
uint32_t zlbytes;
//记录压缩列表尾节点到头结点的字节数,直接可以求节点的地址
uint32_t zltail_offset;
//记录了节点数,有多种类型,默认如下
uint16_t zllength;
//节点
列表节点 entryX;

一个压缩列表示例:
redis的五种基本数据类型及其内部实现
而每个列表节点中主要包括以下几项:previous_entry_length,记录了压缩列表中前一节点的字节长度,当小于254字节时,它的长度为1字节,当大于254字节时,长度为5字节且后4字节保存真正的长度,用于表尾向表头遍历;content,节点所存储的内容,可以是一个字节数组或者整数;encoding,记录content属性中所保存的数据类型以及长度。

编码:
当列表对象所存储的字符串元素长度小于64字节并且元素数量小于512个时,使用ziplist编码,否则使用linkedlist编码,如下:

127.0.0.1:6379> rpush zip "hello" "world"
(integer) 2
127.0.0.1:6379> OBJECT encoding zip
"ziplist"
127.0.0.1:6379> rpush zip "fffffffffffffffffffffzzzzzzzzzzzzzzzzzzzzzzzzzzzzzkkkkkkkkkkkkkkkkkkkkkkkkkcccccccccc"
(integer) 3
127.0.0.1:6379> OBJECT encoding zip
"linkedlist"
127.0.0.1:6379> 

五、集合对象

整数集合与字典:
集合对象的编码可以是整数集合(intset)或者字典(hashtable)。
整数集合结构如下:

typedef struct intset{
//编码方式
uint32_t encoding;
//元素数量
uint32_t length;
//存储元素的数组
int8_t contents[];
}

整数集合的每个元素都是contents数组的一个数组项,各个项在数组中按值得大小从小到大有序排列,并且不包含重复的项。contents数组中元素的类型由encoding决定,当新加入元素之时,如果元素的编码大于contents是数组的编码,则会将所有元素的编码升级为新加入元素的编码,然后再插入。编码不会发生降级。
字典的结构如下:

typedef struct dict{
//类型特定函数
dictType *type;
//哈希表 两个,一个用于实时存储,一个用于rehash
dictht ht[2];
//rehash索引 数据迁移时使用
unsigned rehashidx;
}

而哈希表的结构如下:

typedef struct dictht{
//哈希表数组
dictEntry **table;
//哈希表大小
unsigned long size;
//哈希表掩码,总是等于size-1,存储时计算索引值
unsigned long sizemask;
//已有元素数量
unsigned long used;
}

一个字典示例如下:
redis的五种基本数据类型及其内部实现

其中键值对都保存在节点dictEntry之中,并且通过拉链法解决哈希冲突,存储时通过MurmurHash算法来计算键的哈希值,能够更好的提供随机分布性且速度也快。扩容时时采用渐进式的rehash,采用分而治之的方法,通过改变rehashidx的值,来一个个将元素移动到ht[1]中,完成以后将ht[1]变为ht[0],原先的ht[0]变为ht[1],同时将redhashidx置为-1。

编码:
当集合对象所保存的元素都是整数值且元素数量不超过512个时,使用intset编码,否则使用hashtable编码,如下:

127.0.0.1:6379> sadd cloud 1 2 3 4 5
(integer) 5
127.0.0.1:6379> object encoding cloud
"intset"
127.0.0.1:6379> sadd cloud a b c
(integer) 3
127.0.0.1:6379> object encoding cloud
"hashtable"

六、有序集合

跳跃表
有序集合的编码可以是压缩列表(ziplist)或者跳跃表(skiplist)。
跳跃表的结构如下:

typedef struct zskiplist{
//跳跃表的头结点
zskiplistNode header;
//尾节点
zskiplistNode tail;
//跳跃表中层数最大的节点的层数(不包括头结点)
unsigned long level;
//跳跃表长度(不包括头节点)
unsigned int length;

其中的跳跃表节点结构如下:

typedef struct zskiplistNode{
//后退指针
struct zskiplistNode *backward;
//分值
double score;
//成员对象
robj *obj;
//层
struct zskiplistLevel{
//前进指针
struct zskiplistNode *forward;
//跨度
unsigned int span;
}level[];
};

每个level数组可以包含多个元素,里面存储有指向其他节点(不是下一个)的指针,可以加快访问速度;跨度用于表示两个节点之间的距离,排位时使用;后退指针依次的从后向前访问;分值用于排序;成员是一个指向字符串对象的指针。

编码:
当元素数量小于128个并且所有元素成员的长度都小于64字节之时使用ziplist编码,否则使用skiplist编码,如下:

127.0.0.1:6379> zadd test 2 a 3 b
(integer) 2
127.0.0.1:6379> OBJECT encoding test
"ziplist"
127.0.0.1:6379> zadd test 4 ffffffffffffffffffffffffffffffffffffffffffffffffffffffffqwqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq
(integer) 1
127.0.0.1:6379> OBJECT encoding test
"skiplist"

七、哈希

哈希对象的编码可以是压缩列表(ziplist)或者字典(hashtable),当哈希对象保存的所有键值对的键和值得长度都小于64字节并且元素数量小于512个时使用ziplist,否则使用hashtable。使用ziplist时,是依次将键和值压入链表之中,两者相邻。使用hashtable是是将键值对存于dictEntry之中。

参考-《Redis设计与实现》