原 荐 redis数据结构分析-redisObject-SDS

栏目: 数据库 · 发布时间: 5年前

内容简介:redis是一个key-value储存系统。和Memcached类似,它支持存储的value类型相对更多,包括string(字符串)、list(链表)、set(集合)、zset(sorted set --有序集合)和hash(哈希类型)redis字符串:在redis-Client中执行以下命令: SET USER_NAME zhangsan   会创建一个key为USER_NAME,value为zhangsan 的键值对。那么,那么这个字符串的值 "zhangsan" 在数据库中是以哪种数据结构储存的呢?

redis是一个key-value储存系统。和 Memcached 类似,它支持存储的value类型相对更多,包括string(字符串)、list(链表)、set(集合)、zset(sorted set --有序集合)和hash(哈希类型)

redis字符串:在redis-Client中执行以下命令: SET USER_NAME zhangsan   会创建一个key为USER_NAME,value为zhangsan 的键值对。那么,那么这个字符串的值 "zhangsan" 在数据库中是以哪种数据结构储存的呢?

Redis对象

redis并没有直接只用string list set等来直接实现键值对数据库,而是根据这些数据结构创建了一个对象系统,这个系统包含了 redis 中五种数据结构。并且redis对象中记录最后一次访问时间,服务器会根据这个时间删除对象,从而释放内存(如果启用了maxmemory功能的情况下).

redisObject数据结构分析:

typedef struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    unsigned lru:REDIS_LRU_BITS; /* lru time (relative to server.lruclock) */
    int refcount;
    void *ptr;
} robj;

type占用4个bit位,记录了对象的类型 REDIS_STRING 0,REDIS_LIST 1,REDIS_SET 2,REDIS_ZSET 3,REDIS_HASH 4

ptr:该指针执行对象底层实现数据结构,这些数据结构对象由encoding属性决定。

encoding属性记录了对象所使用的编码,也就是说对象使用了什么数据结构作为对象底层实现。

可以这样理解:type记录的数据结构是针对redis使用者来说的。encoding记录的数据结构是redis底层的具体实现。并且每种类型的对象redis至少两种不同的编码,也就是两种不同的实现方式。使用 OBJECT ENCODING命令来查看数据库键的值对象编码。

原 荐 redis数据结构分析-redisObject-SDS

可以看到“zhangsan”的编码是embstr.

字符串对象:

字符串对象的编码可以是int ,raw 或者embstr.如果一个字符串对象保存的是整数值,并且这个整数值可以用long类型标识,那么字符串对象将以整数值保存在ptr属性里面,并将字符串对象的编码设置为INT。

原 荐 redis数据结构分析-redisObject-SDS

如果对"zhang_san"字符串进行修改,类型会变成raw

原 荐 redis数据结构分析-redisObject-SDS

为什么对字符串进行更改时,会变成raw类型呢,emptr类型与raw类型有什么区别呢,接下类针对这两个具体类型进行详细描述。

embstr编码是为专门保存短字符串的一种编码方式,这种编码和raw编码一样,都使用redisObject结构和sdshdr结构来标识字符串对象,但raw编码会调用两次内存分配函数来创建redisObject结构和sdshdr结构,而embstr编码则通过调用一次内存分配函数来分配一块连续的空间,空间中一次包含redisObject和sdshdr两个结构。

原 荐 redis数据结构分析-redisObject-SDS

接下来介绍sdshdr数据结构。

c语言 中,传统的字符串以空字符结尾的字符数组来表示,redis并没有直接使用这种传统的字符串标识,而是自己构建了一种名为(simple dynamid string ,SDS)的抽象类型,并将SDS用作Redis默认字符串表示。在redis中c字符串只会用在一些无需对字符串值修改的地方。

typedef char *sds;
struct sdshdr {
    int len;
    int free;
    char buf[];
};

其中len表示buf中已占用空间的长度,free中表示buf中可剩余空间的长度,buf是数据空间,如下图所示。

原 荐 redis数据结构分析-redisObject-SDS

free属性值为0,表示这个SDS没有分配任何未使用空间,len为5表示这个SDS保存了一个五个字节的字符串,buf为一个char类型的数组,数组的前五个字节分别保存了'H','E','L','L','O'五个字符,最后一个字节则保存了空字符串\0.

SDS字符串与C字符串的区别。

C语言使用长度为N+1的字符数组来表示长度为N的字符串,并且字符数组的最后一个元素总是空字符'\0'.(java也是用的char[])

获取字符串的长度 ,对c语言字符串来说,c字符串并不记录自身的长度,获取一个c字符串的长度必须遍历整个字符串,这个操作的复杂度为O(n)的。而redis的STRLEN命令的复杂度仅为O(1).

减少内存分配的次数 ,c字符串并不记录自身长度,因此每次增长或者缩短一个字符串时,都需要对内存进行一次内存重新分配的操作。

对于redis中sds来说会进行空间预分配:(可以参考 JAVA 中 ArrayList这种数据结构的扩容,他们是类似的。ArrayList没记错的话是每次扩1.5倍)

sds sdsMakeRoomFor(sds s, size_t addlen) {

    struct sdshdr *sh, *newsh;

    // 获取sds目前空闲的长度
    size_t free = sdsavail(s);

    size_t len, newlen;

    // 空间足够,则直接返回,不重新分配
    if (free >= addlen) return s;

    // 获取 s 目前已占用空间的长度
    len = sdslen(s);
    sh = (void*) (s-(sizeof(struct sdshdr)));

    // s 最少需要的长度
    newlen = (len+addlen);

    // 根据新长度,为 s 分配新空间所需的大小
    if (newlen < SDS_MAX_PREALLOC)
        // 如果新长度小于 SDS_MAX_PREALLOC 
        // 那么为它分配两倍于所需长度的空间
        newlen *= 2;
    else
        // 否则,分配长度为目前长度加上 SDS_MAX_PREALLOC
        newlen += SDS_MAX_PREALLOC;
    // T = O(N)
    newsh = zrealloc(sh, sizeof(struct sdshdr)+newlen+1);

    // 内存不足,分配失败,返回
    if (newsh == NULL) return NULL;

    // 更新 sds 的空余长度
    newsh->free = newlen - len;

    // 返回 sds
    return newsh->buf;
}

同时sds是 惰性空间释放 ,当sds字符串缩短操作时不会立即free()空间,而是使用free属性将这些字节的数量记录起来,并等待将来使用。

C字符串中的字符必须符合某种编码,比如(ASCII),并且出了字符串末尾之外,字符串里不能包含空字符,否则会认为已经到结尾,因此c字符串只能保存文本数据,而不能保存图片,音频,视频等二进制数据。

同时c字符串提供的api是不安全的,比如在修改内容时忘记分配空间。

总结:

C字符串 SDS
获取字符串长度复杂度为O(n) 获取字符串长度复杂度为O(1)
API是不安全的,可能造成缓冲区溢出 API是安全的,可能造成缓冲区溢出
修改N次字符串必然进行N次内存分配 修改N次字符串最多进行N次内存分配
只能保存文本数据 可以保存文本数据和二进制数据

对SET key HELLO 命令执行后,内部储存结构示意图。

原 荐 redis数据结构分析-redisObject-SDS

参考资料:

<C语言程序设计>

<Redis设计与实现>

Redis源码:https://github.com/antirez/redis/tree/unstable/src

--------------------------- 分割线 ----------------------------

看了redis源码才知道,原来c语言还能这样封装!

原 荐 redis数据结构分析-redisObject-SDS

以上所述就是小编给大家介绍的《原 荐 redis数据结构分析-redisObject-SDS》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

程序员面试宝典(第5版)

程序员面试宝典(第5版)

欧立奇、刘洋、段韬 / 电子工业出版社 / 2015-10 / 55.00

容提要 《程序员面试宝典(第5版)》是《程序员面试宝典》的第5 版,在保留第4 版的数据结构、面向对象、程序设计等主干的基础上,修正了前4 版近40 处错误,解释清楚一些读者提出的问题,并使用各大IT 公司及相关企业最新面试题(2014-2015)替换和补充原内容,以反映自第4 版以来两年多的时间内所发生的变化。 《程序员面试宝典(第5版)》取材于各大公司面试真题(笔试、口试、电话面试......一起来看看 《程序员面试宝典(第5版)》 这本书的介绍吧!

图片转BASE64编码
图片转BASE64编码

在线图片转Base64编码工具

Base64 编码/解码
Base64 编码/解码

Base64 编码/解码

UNIX 时间戳转换
UNIX 时间戳转换

UNIX 时间戳转换