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并没有直接只用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命令来查看数据库键的值对象编码。
可以看到“zhangsan”的编码是embstr.
字符串对象的编码可以是int ,raw 或者embstr.如果一个字符串对象保存的是整数值,并且这个整数值可以用long类型标识,那么字符串对象将以整数值保存在ptr属性里面,并将字符串对象的编码设置为INT。
如果对"zhang_san"字符串进行修改,类型会变成raw。
为什么对字符串进行更改时,会变成raw类型呢,emptr类型与raw类型有什么区别呢,接下类针对这两个具体类型进行详细描述。
embstr编码是为专门保存短字符串的一种编码方式,这种编码和raw编码一样,都使用redisObject结构和sdshdr结构来标识字符串对象,但raw编码会调用两次内存分配函数来创建redisObject结构和sdshdr结构,而embstr编码则通过调用一次内存分配函数来分配一块连续的空间,空间中一次包含redisObject和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是数据空间,如下图所示。
free属性值为0,表示这个SDS没有分配任何未使用空间,len为5表示这个SDS保存了一个五个字节的字符串,buf为一个char类型的数组,数组的前五个字节分别保存了'H','E','L','L','O'五个字符,最后一个字节则保存了空字符串\0.
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; }
总结:
C字符串 | SDS |
获取字符串长度复杂度为O(n) | 获取字符串长度复杂度为O(1) |
API是不安全的,可能造成缓冲区溢出 | API是安全的,可能造成缓冲区溢出 |
修改N次字符串必然进行N次内存分配 | 修改N次字符串最多进行N次内存分配 |
只能保存文本数据 | 可以保存文本数据和二进制数据 |
对SET key HELLO 命令执行后,内部储存结构示意图。