Redis基本数据类型以及String（一）

kingforce

　　前言：
　　Redis也有自己的数据类型，包含string,list,hash,set,sorted set。下面就对每种数据类型原理以及操作做一个详细的介绍。
　　Redis是面向编程的语言，除了字符串，其他类型怎么表示呢？
　　Redis中定义了一个对象的结构体：
　　

/*　　* Redis 对象
*/　　
typedef struct redisObject {
　　

// 类型　　unsigned type:4;        
　　

　　// 不使用(对齐位)
　　unsigned notused:2;
　　

　　// 编码方式
　　unsigned encoding:4;
　　

　　// LRU 时间（相对于 server.lruclock）
　　unsigned lru:22;
　　

　　// 引用计数
　　int refcount;
　　

　　// 指向对象的值
　　void *ptr;
　　

　　
} robj;
　　

　　type表示了该对象的对象类型，即上面五个中的一个。但为了提高存储效率与程序执行效率，每种对象的底层数据结构实现都可能不止一种。encoding就表示了对象底层所使用的编码。下面先介绍每种底层数据结构的实现，再介绍每种对象类型都用了什么底层结构并分析他们之间的关系。
　　Redis对象底层数据结构共八种：
　　编码常量 编码所对应的底层数据结构
　　REDIS_ENCODING_INT（long 类型的整数）
　　REDIS_ENCODING_EMBSTR embstr （编码的简单动态字符串）
　　REDIS_ENCODING_RAW （简单动态字符串）
　　REDIS_ENCODING_HT （字典）
　　REDIS_ENCODING_LINKEDLIST （双端链表）
　　REDIS_ENCODING_ZIPLIST （压缩列表）
　　REDIS_ENCODING_INTSET （整数集合）
　　REDIS_ENCODING_SKIPLIST （跳跃表和字典）
　　string      
　　Redis的字符串也是字符序列，一个Key对应一个Value，它是Redis里面最为基础的数据存储类型。字符串类型是二进制安全（字符串不是根据某种特殊的标志来解析的，无论输入是什么，总能保证输出是处理的原始输入而不是根据某种特殊格式来处理）的，可以包含任何数据等等。
　　一：实现原理：
　　在C语言中，字符串可以用'\0'结尾的char数组标示。这种简单的字符串表示，在大多数情况下都能满足要求，但是不能高效的计算length和append数据。所以Redis自己实现了SDS（简单动态字符串）的抽象类型。
　　字符串的编码可以是int，raw或者embstr。如果一个字符串内容可转为long，那么该字符串会被转化为long类型，对象ptr指向该long，并且对象类型也用int类型表示。普通的字符串有两种，embstr和raw。如果字符串对象的长度小于44字节，就用embstr对象。否则用的raw对象。代码如下：                 
　　

robj *createObject(int type, void *ptr) {　　robj
*o = zmalloc(sizeof(*o));　　

    o->type = type;　　o
->encoding = OBJ_ENCODING_RAW;　　o
->ptr = ptr;　　o
->refcount = 1;　　

/* Set the LRU to the current lruclock (minutes resolution). */　　o
->lru = LRU_CLOCK();return o;　　
}
　　

　　

/* Create a string object with encoding OBJ_ENCODING_RAW, that is a plain　　* string object where o->ptr points to a proper sds string.
*/　　
robj
*createRawStringObject(const char *ptr,>return createObject(OBJ_STRING,sdsnewlen(ptr,len));　　
}
　　

　　

/* Create a string object with encoding OBJ_ENCODING_EMBSTR, that is　　* an object where the sds string is actually an unmodifiable string
　　* allocated in the same chunk as the object itself.
*/　　
robj
*createEmbeddedStringObject(const char *ptr,>robj *o = zmalloc(sizeof(robj)+sizeof(struct sdshdr8)+len+1);struct sdshdr8 *sh = (void*)(o+1);　　

　　o
->type = OBJ_STRING;　　o
->encoding = OBJ_ENCODING_EMBSTR;　　o
->ptr = sh+1;　　o
->refcount = 1;　　o
->lru = LRU_CLOCK();　　

　　sh
->len = len;　　sh
->alloc = len;　　sh
->flags = SDS_TYPE_8;if (ptr) {　　memcpy(sh
->buf,ptr,len);　　sh
->buf[len] = '\0';　　}
else {　　memset(sh
->buf,0,len+1);　　}
return o;　　
}
　　

　　

/* Create a string object with EMBSTR encoding if it is smaller than　　* REIDS_ENCODING_EMBSTR_SIZE_LIMIT, otherwise the RAW encoding is
　　* used.
　　*
　　* The current limit of 39 is chosen so that the biggest string object
　　* we allocate as EMBSTR will still fit into the 64 byte arena of jemalloc.
*/　　
#define OBJ_ENCODING_EMBSTR_SIZE_LIMIT 44
　　
robj *createStringObject(const char *ptr,>　　if (len <= OBJ_ENCODING_EMBSTR_SIZE_LIMIT)
　　return createEmbeddedStringObject(ptr,len);
　　else
　　return createRawStringObject(ptr,len);
　　
}
　　

　　优点：
　　（1）embstr的创建只需分配一次内存，而raw为两次（一次为sds分配对象，另一次为redisObject分配对象，embstr省去了第一次）。
　　（2）相对地，释放内存的次数也由两次变为一次。
　　（3）embstr的redisObject和sds放在一起，更好地利用缓存带来的优势
　　缺点：redis并未提供任何修改embstr的方式，即embstr是只读的形式。对embstr的修改实际上是先转换为raw再进行修改。
　　sds数据结构定义如下：     
　　

typedef char *sds;struct sdshdr {// 记录buf数据中已使用的字节数目　　int len;
　　

　　// 记录buf 剩余的字符长度
　　int free;
　　

　　// 字符数据，用于存储字符串  大小等于len+free+1，其中多余的1个字节是用来存储'\0'的。
　　char buf[];
　　};
　　

　　最新版本的数据结构定义如下：从下面代码可以看出，除了sdshdr5之外，其它4个header的结构都包含3个字段：len: 表示字符串的真正长度（不包含NULL结束符在内）。 alloc: 表示字符串的最大容量（不包含最后多余的那个字节）。 flags: 总是占用一个 字节。其中的最低3个bit用来表示header的类型。header的类型共有5种，在sds.h中有常量定义。
　　

typedef char *sds;　　

　　

/* Note: sdshdr5 is never used, we just access the flags byte directly.　　* However is here to document the layout of type 5 SDS strings.
*/　　
struct __attribute__ ((__packed__)) sdshdr5 {
　　unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
　　char buf[];
　　
};
　　
struct __attribute__ ((__packed__)) sdshdr8 {
　　uint8_t len; /* used */
　　uint8_t alloc; /* excluding the header and null terminator */
　　unsigned char flags; /* 3 lsb of type, 5 unused bits */
　　char buf[];
　　
};
　　
struct __attribute__ ((__packed__)) sdshdr16 {
　　uint16_t len; /* used */
　　uint16_t alloc; /* excluding the header and null terminator */
　　unsigned char flags; /* 3 lsb of type, 5 unused bits */
　　char buf[];
　　
};
　　
struct __attribute__ ((__packed__)) sdshdr32 {
　　uint32_t len; /* used */
　　uint32_t alloc; /* excluding the header and null terminator */
　　unsigned char flags; /* 3 lsb of type, 5 unused bits */
　　char buf[];
　　
};
　　
struct __attribute__ ((__packed__)) sdshdr64 {
　　uint64_t len; /* used */
　　uint64_t alloc; /* excluding the header and null terminator */
　　unsigned char flags; /* 3 lsb of type, 5 unused bits */
　　char buf[];
　　
};
　　

　　
#define SDS_TYPE_5  0
　　
#define SDS_TYPE_8  1
　　
#define SDS_TYPE_16 2
　　
#define SDS_TYPE_32 3
　　
#define SDS_TYPE_64 4
　　
#define SDS_TYPE_MASK 7
　　
#define SDS_TYPE_BITS 3
　　
#define SDS_HDR_VAR(T,s) struct sdshdr##T *sh = (void*)((s)-(sizeof(struct sdshdr##T)));
　　
#define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T))))
　　
#define SDS_TYPE_5_LEN(f) ((f)>>SDS_TYPE_BITS)
　　

　　其中SDS_HDR用来从sds字符串获得header起始位置的指针，比如SDS_HDR(8, s1)表示s1的header指针，SDS_HDR(16, s2)表示s2的header指针。使用SDS_HDR之前我们必须先知道到底是哪一种header，这样我们才知道SDS_HDR第1个参数应该传什么。由sds字符指针获得header类型的方法是，先向低地址方向偏移1个字节的位置，得到flags字段。比如，s1[-1]和s2[-1]分别获得了s1和s2的flags的值。然后取flags的最低3个bit得到header的类型。由于s1[-1] == 0x01 == SDS_TYPE_8，因此s1的header类型是sdshdr8。 由于s2[-1] == 0x02 == SDS_TYPE_16，因此s2的header类型是sdshdr16。有了header指针，就能很快定位到它的len和alloc字段：s1的header中，len的值为0x06，表示字符串数据长度为6；alloc的值为0x80，表示字符数组最大容量为128。 s2的header中，len的值为0x0006，表示字符串数据长度为6；alloc的值为0x03E8，表示字符数组最大容量为1000。
　　注： __attrubte__ ((packed)) 的作用就是告诉编译器取消结构在编译过程中的优化对齐,按照实际占用字节数进行分配。
　　通过sds.c中的sdsReqType可以清楚的明白要选用的header，长度在0和2^5-1之间，选用SDS_TYPE_5类型的header。 长度在2^5和2^8-1之间，选用SDS_TYPE_8类型的header。 长度在2^8和2^16-1之间，选用SDS_TYPE_16类型的header。 长度在2^16和2^32-1之间，选用SDS_TYPE_32类型的header。 长度大于2^32的，选用SDS_TYPE_64类型的header。能表示的最大长度为2^64-1。
　　

static inline char sdsReqType(size_t string_size) {if (string_size < 1<<5)return SDS_TYPE_5;if (string_size < 1<<8)return SDS_TYPE_8;if (string_size < 1<<16)return SDS_TYPE_16;if (string_size < 1ll<<32)return SDS_TYPE_32;return SDS_TYPE_64;　　
}
　　

　　从数据结构定义，可以看出Redis的sds和C语言区别就是，sds是通过buf以及len来判断字符串内容的，而不是通过'\0'来判断。      
　　（1）计算字符串的长度复杂度为0(1)   
　　（2）操作字符串时，内存的分配复杂度最多为O(N)        
　　C语言中对于一个N长的字符串底层是一个N+1长的字符数组（有一个字节存放空字符）。C字符串的长度和底层数组之间的长度存在着这样的关系，因此当进行字符串的操作而导致字符串长度发生变化的时候，需要对内存进行重新分配。如果操作会增长字符串，那么在执行之前，就需要进行内存分配扩充底层数组的大小。如果是缩短字符串的操作，则需要释放额外的内存。      如果字符串的操作不是很频繁，每次修改都重新分配一下内存是可以接受的。但是Redis作为一个数据库，其读写速度，数据修改频率都被要求达到很高的效率。因此这种低效的方式并不适合Redis。     
　　Redis采用两种方式处理内存问题：     
　　(1) 空间预分配    这种方式用于处理字符串长度增加的问题。如果对字符串的修改使得字符串的长度增加，API首先会判断buf的空间大小是否满足，如果满足则直接操作，如果不满足，则进行如下操作：如果对SDS进行修改之后的，SDS的长度（即len的值）小于1MB。程序将额外分配和len一样大小的未使用空间。以上面的”hello” + ” world”的操作为例。在这个例子中”hello”的len是5（不考虑’\0′)，修改之后的字符串”hello world”长度为11，那么新的SDS的buf的容量就是11*2+1。其中len和free都是11，多余的1字节用来存储'\0'。 如果对SDS修改之后的长度大于1MB，那么程序会分配1MB的未使用空间（没有分配等同大小的空间，避免资源浪费）。比如原数据是5MB，修改之后需要6MB的空间，进行修改的操作后，buf的实际空间应该是7MB，其中len为6MB，free为1MB。通过该策略实现了最多分配N次。      
　　

sds sdsMakeRoomFor(sds s,>
void *sh, *newsh;　　size_t avail
= sdsavail(s);　　size_t len, newlen;
char type, oldtype = s[-1] & SDS_TYPE_MASK;int hdrlen;　　

/* Return ASAP if there is enough space left. */　　if (avail >= addlen) return s;
　　

　　len = sdslen(s);
　　sh = (char*)s-sdsHdrSize(oldtype);
　　newlen = (len+addlen);
　　//内存大小分配
　　if (newlen < SDS_MAX_PREALLOC)
　　newlen *= 2;
　　else
　　newlen += SDS_MAX_PREALLOC;
　　

　　type = sdsReqType(newlen);
　　

　　/* Don't use type 5: the user is appending to the string and type 5 is
　　* not able to remember empty space, so sdsMakeRoomFor() must be called
　　* at every appending operation. */
　　if (type == SDS_TYPE_5) type = SDS_TYPE_8;
　　

　　hdrlen = sdsHdrSize(type);
　　if (oldtype==type) {
　　newsh = s_realloc(sh, hdrlen+newlen+1);
　　if (newsh == NULL) return NULL;
　　s = (char*)newsh+hdrlen;
　　} else {

　　/* Since the header>　　* and can't use realloc */
　　newsh = s_malloc(hdrlen+newlen+1);
　　if (newsh == NULL) return NULL;
　　memcpy((char*)newsh+hdrlen, s, len+1);
　　s_free(sh);
　　s = (char*)newsh+hdrlen;
　　s[-1] = type;
　　sdssetlen(s, len);
　　}
　　sdssetalloc(s, newlen);
　　return s;
　　
}
　　

　　（2）惰性空间释放   当执行字符串长度缩短的操作的时候，SDS并不直接重新分配多出来的字节，而是修改len和free的值（len相应减小，free相应增大，buf的空间大小不变化）。通过惰性空间释放，可以很好的避免缩短字符串需要的内存重分配的情况。而且多余的空间也可以为将来可能有的字符串增长的操作做优化。      
　　（3）防止内存溢出            
　　char a[10] = "hello";               
　　strcat(a, " world");               
　　strcpy(a, "hello world");      
　　上面的三句代码，就是C语言的字符串拼接和复制的使用，但是明显出现了缓冲区溢出的问题。字符数组a的长度是10，而”hello world”字符串的长度为11，则需要12个字节的空间来存储（不要忘记了’\0’）。Redis的SDS是怎么处理字符串修改的这种情况。当使用SDS的API对字符串进行修改的时候，API内部第一步会检测字符串的大小是否满足。如果空间已经满足要求，那么就像C语言一样操作即可。如果不满足，则拓展buf的空间，使得满足操作的需求，之后再进行操作。每次操作之后，len和free的值会做相应的修改。   
　　总结： SDS 具有以下优点      
　　（1） 常数复杂度获取字符串长度。      
　　（2）杜绝缓冲区溢出。      
　　（3）减少修改字符串长度时所需的内存重分配次数。      
　　（4）二进制安全。      
　　（5）兼容部分 C 字符串函数。   
　　二、命令操作        
　　1. SET SETEX PSETEX SETNX          
　　SET key value [EX][PX][NX][XX]         
　　EX second：设置键的过期时间，单位为秒。（SET key value EX second等同于SETEX key second value)。   
　　PX millisecond：设置键的过期时间，单位为毫秒。（SET key value PX millisecond等同于PSETEX key millisecond value）。   
　　NX：当建不存在时，才对键进行设置操作。（SET key value NX等同于SETNX key value）。   
　　XX：只有键已经存在时，才对键进行设置操作。   
　　（1）对不存在的键进行设置               
　　

   127.0.0.1:6379> set key "value"　　

　　OK         
　　

127.0.0.1:6379> get key　　

"value"    　　

　　（2）对已存在的键进行设置   
　　

  127.0.0.1:6379> set key "newvalue"　　

　　OK         
127.0.0.1:6379> get key　　

"newvalue"    　　

　　（3）使用EX选项     
　　

127.0.0.1:6379> set key-with-EX "hello" EX 10　　

　　OK               
　　

127.0.0.1:6379> get key-with-EX　　

"hello"　　

　　127.0.0.1:6379> get key-with-EX                 
　　

　　(nil)  
　　

　　（4）使用PX选项                    
　　

  127.0.0.1:6379> set key-with-PX "hello" PX 10000　　

　　OK                 
　　

127.0.0.1:6379> get key-with-PX　　

"hello"　　

　　127.0.0.1:6379> get key-with-PX                 
　　

　　(nil)  
　　

　　（5）使用NX|XX选项         
　　

  127.0.0.1:6379> set key-with-NX "hello" NX　　

　　OK               
　　

127.0.0.1:6379> set key-with-NX "hello" NX　　

　　(nil)      
　　

127.0.0.1:6379> set key-with-XX "hello"　　

　　OK               
　　

127.0.0.1:6379> del key-with-XX　　

　　(integer)
1　　

　　127.0.0.1:6379> set key-with-XX "hello" XX      
　　

　　(nil)   
　　

　　2. APPEND
　　APPEND key value              
　　如果key已存在并且是一个字符串，APPEND命令将value追加到key原来的位置。            
　　如果key不存在，APPEND简单的将给定的key设为value。   
　　

   127.0.0.1:6379> APPEND test "value"　　

　　(integer)
5　　

　　127.0.0.1:6379> get test            
　　

　　"value"            
　　

　　127.0.0.1:6379> APPEND test "1"           
　　

　　(integer) 6           
　　

　　127.0.0.1:6379> get test           
　　

　　"value1"           
　　

　　3. GET     
　　返回key所关联的字符串值   如果 key 不存在那么返回特殊值 nil 。假如 key 储存的值不是字符串类型，返回一个错误，因为 GET 只能用于处理字符串值。   
　　4. INCR INCRBY INCRBYFLOAT DECR DECRBY            
　　INCR将key中的数字值加1。如果KEY不存在，那么KEY的值初始化为0，然后执行INCR操作。如果类型错误，返回一个错误。   
　　INCR key   
　　INCRBY    将 key 所储存的值加上增量 increment。   
　　INCRBY key increment   
　　INCRBYFLOAT    将key 中所储存的值加上浮点数增量 increment，无论加法计算所得的浮点数的实际精度有多长， INCRBYFLOAT 的计算结果也最多只能表示小数点的后十七位   
　　INCRBYFLOAT key increment    DECR DECRBY操作与其相反。   
　　5. MSET MSETNX      
　　MSET key value [key value ...]            
　　如果某个给定 key 已经存在，那么 MSET 会用新值覆盖原来的旧值，如果这不是你所希望的效果，请考虑使用 MSETNX 命令：它只会在所有给定 key 都不存在的情况下进行设置操作。MSET 是一个原子性(atomic)操作，所有给定 key 都会在同一时间内被设置，某些给定 key 被更新而另一些给定 key 没有改变的情况，不可能发生。      
　　6. GETRANGE      
　　GETRANGE key start end   
　　返回 key 中字符串值的子字符串，字符串的截取范围由 start 和 end 两个偏移量决定(包括 start 和 end 在内)。             负数偏移量表示从字符串最后开始计数， -1 表示最后一个字符， -2 表示倒数第二个，以此类推。 GETRANGE 通过保证子字符串的值域(range)不超过实际字符串的值域来处理超出范围的值域请求。   
　　注：GETRANGE不支持回绕操作   
　　例：
　　

  127.0.0.1:6379> set test2 "aaaaaaa"　　

　　OK            
　　

127.0.0.1:6379> getrange test2 -1 -5 //回绕操作　　

　　""            
　　

　　127.0.0.1:6379> getrange test2 -3 -1            
　　

　　"aaa"
　　

　　7. MGET      
　　MGET key [key ...]            
　　返回所有(一个或多个)给定 key 的值。如果给定的 key 里面，有某个 key 不存在，那么这个 key 返回特殊值 nil 。因此，该命令永不失败     
　　8. STRLEN      
　　返回 key 所储存的字符串值的长度。key不存在时返回0,。当 key 储存的不是字符串值时，返回一个错误。     
　　9. SETRANGE      
　　SETRANGE key offset value            
　　用 value 参数覆写(overwrite)给定 key 所储存的字符串值，从偏移量 offset 开始。不存在的 key 当作空白字符串处理。SETRANGE 命令会确保字符串足够长以便将 value 设置在指定的偏移量上，如果给定 key 原来储存的字符串长度比偏移量小(比如字符串只有 5 个字符长，但你设置的 offset 是 10 )，那么原字符和偏移量之间的空白将用零字节(zerobytes, "\x00" )来填充。              注：能使用的最大偏移量是 2^29-1(536870911) ，因为 Redis 字符串的大小被限制在 512 兆(megabytes)以内。如果你需要使用比这更大的空间，你可以使用多个 key 。     
　　10. GETSET       
　　GETSET key value            
　　将给定 key 的值设为 value ，并返回 key 的旧值(old value)。当 key 存在但不是字符串类型时，返回一个错误。