作为日常使用最为频繁的缓存系统redis , 而字符串又作为最为频繁使用的redis数据结构 , 可以说是我们的老朋友了 , 但是你真的熟悉他吗?
都说学习源码是最好的向大师学习的机会 , 那最为当下最优秀的缓存数据库,你真的不想看看他是怎么实现的吗?
那不管你是刚毕业的准备面试的新同学,还是已经工作很多年的老大哥,今天和小编一起,带着你的疑问,让我们从底层数据,重新认识下Redis字符串 。
首先本文的出现说明了一个问题 , 那就是Redis的字符串并没有使用C语言原生的字符串? 不然本文将以一句话结束 : 请参照C语言原生字符串实现 , END!
那回到正题 , Redis作者为啥抛弃原生而选择自定义呢 ? 我的理解是 : 就和平时为啥产品的同学提需求的初衷一样 , 本质原因还是因为当前系统不支持 ,所以需要开发的同学动手丰衣足食 , 同理 , 我们结合着Redis提供的功能 , 假想下如果使用C语言字符串进行实现会是怎样 , 相信就会得到答案 .
1.strlen命令 : 如果使用原生C语言 , 那这个操作就需要调用strlen方法 , O(n)级别的 , 若字符串太长 , 对于单线程的redis来说是真的等不起.2.append命令: 这个命令常用于位图的操作中 , 如果使用原生的C语言 , 由于C语言的字符串是常量字符串 , 所以每次操作都将进行一次拷贝 , 同样也是O(n)级别的 ,并且会引起频繁的CPU占用 , 对于性能著称的Redis同样是不可接受的.3.二进制安全 : 这个就很好理解了 , 学过C语言的同学肯定都知道 , C原生的字符串本质上就是字符数组是以0x\0
结尾 , 如果使用原生字符串 , 那么只要二进制流中出现0x\0
则会被截断 , 无法保证数据被正确储存.
理解了为什么要自定义字符串结构之后 , 让我们来认识下Redis的SDS字符串是什么样子的吧.
struct SDS<T> {
T capacity;//数组容量
T len; // 数组长度(实际占用)
byte flags;// 标志位
byte[] content;//实际内容 , 结尾1字节存储 0x\0 结束符标志位
}
对于SDS的数据结构 , 我们可以参照java中的ArrayList去理解 , 下面说下这个数据结构解决了那些问题
1.O(n)级别的lentgh获取: 上文说过了C语言中的获取长度是O(n)级别的 , 所以redis选择了用一个len变量动态的存储实际长度 , 将时间复杂度降至O(1)级别2.append频繁扩容: 采用冗余空间的策略, 减少了append带来的频繁扩容3.结束符标志位: 可以看到在上面我特意在content中标注了 , 结尾处有1字节用于存储结束符 , 和C语言字符串一样的结束符 , 为什么这么做呢? 因为这样redis处理字符串内部的 content数组时 , 就可以方便的复用C语言方法库中的字符串方法 , 减少开发成本.4.flags标志位: 对于工作在内存上的redis来说 , 对与内存的使用可谓细致到了极致 , 细心的同学可能观察到了 容量 和 长度使用了泛型存储 , redis会根据字符串的数据大小 , 动态分配泛型的类型 , flags就是标注这个类型信息的 , 下面我放出了部分源码 , 可以看到redis将字符串分为了4个级别, 分别使用8位、16位、32位、64位存储容量和长度 .
typedef char* sds;
struct __attribute__ ((__packed__)) sdshdr8 {
uint8_t len;
uint8_t alloc;
unsigned char flags;
char buf[]; // sds指向buf
};
struct __attribute__ ((__packed__)) sdshdr16 {
uint16_t len;
uint16_t alloc;
unsigned char flags;
char buf[]; // sds指向buf
};
struct __attribute__ ((__packed__)) sdshdr32 {
uint32_t len;
uint32_t alloc;
unsigned char flags;
char buf[]; // sds指向buf
};
struct __attribute__ ((__packed__)) sdshdr64 {
uint64_t len;
uint64_t alloc;
unsigned char flags;
char buf[]; // sds指向buf
};
#define SDS_TYPE_MASK 7
#define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T))))
// SDS_HDR指向sdshdr<T>
// sds指向sdshdr<T>.buf
static inline size_t sdslen(const sds s) {
unsigned char flags = s[-1]; // 注意负下标
switch(flags&SDS_TYPE_MASK) {
return SDS_HDR(8,s)->len;
case SDS_TYPE_16:
return SDS_HDR(16,s)->len;
case SDS_TYPE_32:
return SDS_HDR(32,s)->len;
case SDS_TYPE_64:
return SDS_HDR(64,s)->len;
}
return 0;
}
// 此源码摘自网络
上面我们看到了 , redis的字符串是有冗余空间的 , 那么当空间为零 , 自然就会引发扩容问题
1.初始状态无冗余: 当最开始创建SDS字符串时 , redis并没有创建冗余空间 , 因为大多数时候不会进行字符串变更操作 , 也就无需扩容 , 所以Redis的冗余空间 , 是当有了变更字符串操作时 , 触发扩容后 , 才存在的2.扩容规则: 当字符串小于1M时 , 每次扩容都翻倍 , 当字符串>1M时 , 为避免浪费 , 每次仅扩容1M , 下面我占出了字符串追加的代码 , 有兴趣的同学可以研究一番.
sds sdsMakeRoomFor(sds s, size_t addlen) {
void *sh, *newsh;
// 剩余容量
size_t avail = sdsavail(s);
size_t len, newlen;
char type, oldtype = s[-1] & SDS_TYPE_MASK;
int hdrlen;
// 如果当前容量足够,则不需要扩容
if (avail >= addlen) return s;
// 当前字符串的长度
len = sdslen(s);
sh = (char*)s-sdsHdrSize(oldtype);
// 扩容后的长度
newlen = (len+addlen);
// 如果扩容后的容量小于 1M 则扩大2倍,
if (newlen < SDS_MAX_PREALLOC) // #define SDS_MAX_PREALLOC (1024*1024)
newlen *= 2;
else
newlen += SDS_MAX_PREALLOC; // 否则等于当前容量 + 1M
// 获取新容量的结构体类型
type = sdsReqType(newlen);
if (type == SDS_TYPE_5) type = SDS_TYPE_8;
// 根据类型获取结构体大小
hdrlen = sdsHdrSize(type);
// 如果扩容后类型相等则,直接使用s_realloc扩容,内容不变
if (oldtype==type) {
newsh = s_realloc(sh, hdrlen+newlen+1);
if (newsh == NULL) return NULL;
s = (char*)newsh+hdrlen;
} else {
// 如果类型已经改变,就需要使用 s_malloc 申请内存,使用 memcpy 填充数据
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;
}
// 摘自互联网
在讲下面的编码优化前 , 我们先介绍下redis最外层的数据结构RedisObject , 如下所示.
typedef struct redisObject {
unsigned type:4; // 对象类型
unsigned encoding:4; // 对象编码
unsigned lru:24; // LRU时间戳
int refcount; // 引用计数
void *ptr; // 指向体结构的指针
} robj;
// 摘自网络
redisObject分为5个部分 , 共占用16字节
1.type: 标注的对象类型 , 可以理解为是redis暴露给使用方的数据结构
2.encoding: redis对上述数据结构 , 在底层实现上 , 采用了不同的编码实现策略 , 以达到性能空间的协调 , 下面我们要讲的编码优化 , 就是和字符串相关的逻辑 , 下面是完整的encoding列表
3.lru : 用于做键值回收策略4.refcount:因为c语言要手动管理内存回收 , 这个标志位就标记了当前对象的引用数量 , 类似于jvm的计数法gc.5.ptr: 实际数据对象引用
举个栗子
//int 编码
127.0.0.1:6379> SET keyInt 111111
OK
127.0.0.1:6379> DEBUG OBJECT keyInt
Value at:0x7f0869035dc0 refcount:1 encoding:int serializedlength:5 lru:485433 lru_seconds_idle:12
// embstr编码 : 字符串长度 < 39或44(3.2版本以后)
127.0.0.1:6379> SET keyEmbstr 01234567890123456789012345678901234567a
OK
127.0.0.1:6379> STRLEN keyEmbstr
(integer) 39
127.0.0.1:6379> DEBUG OBJECT keyEmbstr
Value at:0x7f0869014500 refcount:1 encoding:embstr serializedlength:21 lru:486066 lru_seconds_idle:7
// raw编码 : 字符串长度 > 39 或 44(3.2版本以后)
127.0.0.1:6379> SET keyRaw 01234567890123456789012345678901234567ab
OK
127.0.0.1:6379> STRLEN keyRaw
(integer) 40
127.0.0.1:6379> DEBUG OBJECT keyRaw
Value at:0x7f0869086300 refcount:1 encoding:raw serializedlength:21 lru:486755 lru_seconds_idle:29
从上面的例子我们可以看到 , 对于使用层面的 Redis字符串 来说在底层实现上有三种方式进行优化 , 下面为大家一一讲解.
首先我们讲讲最简单的int编码 , 这个很好理解 , 当我们输入的字符串是纯数字时 , redis就会使用整数的编码方式进行存储 , 这个整数的范围就时long类型能表示的最大数 , 当超出这个范围 , 就会进化为 SDS结构进行存储 .
// 特别注意: value at: 表明的是数据的引用地址
// 10000以内的整数存储
127.0.0.1:6379> SET keyIntA 9999
OK
127.0.0.1:6379> SET keyIntB 9999
OK
127.0.0.1:6379> DEBUG OBJECT keyIntA
Value at:0x7f0869085e00 refcount:3 encoding:int serializedlength:3 lru:478885 lru_seconds_idle:8458
127.0.0.1:6379> DEBUG OBJECT keyIntB
Value at:0x7f0869085e00 refcount:3 encoding:int serializedlength:3 lru:478885 lru_seconds_idle:8460
// 10000以外的整数存储
127.0.0.1:6379> SET keyIntC 10000
OK
127.0.0.1:6379> SET keyIntD 10000
OK
127.0.0.1:6379> DEBUG OBJECT keyIntC
Value at:0x7f0869035ea0 refcount:1 encoding:int serializedlength:3 lru:487337 lru_seconds_idle:11
127.0.0.1:6379> DEBUG OBJECT keyIntD
Value at:0x7f0869035f00 refcount:1 encoding:int serializedlength:3 lru:487377 lru_seconds_idle:11
我们可以看到10000以内的keyIntA
和 keyIntB
整数使用的是同一个引用0x7f0869085e00
, 而10000以外keyIntC
和 keyIntD
则使用的是不同的引用 , 这是为什么呢?
在redis 在初始化时建立了一个 小整数对象缓存 10000以内的小整数直接进行共享 , Java中的Integer也有相似的优化机制
在本小节最开始的例子中可以看到 字符串长度小于39时 , 会使用embstr编码 . 实际上此时redis创建字符串时 , 会一次性申请64字节内存 , 用于存放redisObject 和 sds 此时内存物理连续. 如下图所示
反之当字符串长度大于39时 , 会使用raw编码 , 这时redis创建字符串对象 , 会分两次申请内存 , 分别存储RedisObject
和 SDS
对象, 如下图所示.
相信不少小伙伴读到这里都会有这个疑问 , 为啥时39 , 为啥不是其他数 , 是随便定的吗?
实际上这个39就是通过计算出来的 , redis在申请内存时使用的是jemalloc内存分配器 , 这个分配器会分配8 , 16 ,32 ,64等字节的内存 . redisObject就占用了16字节 , SDS的头部最少占用8+1 = 9字节 , 所以此时redis一次要申请64字节内存 , 在扣除数据结尾的1字节标志位 , 那么剩余可存放的字符串长度为 : 64 - 16 -9 = 39字节 .
特别的是 3.2以后对SDS的头部进一步优化最小仅为3字节 , 相对于老版的8字节节省5字节 , 所以3.2版本后 , 界限变为 39+5 = 44字节
首先我们知道对于CPU和内存之间的IO性能 , 同样是有较大差异的 , 所以计算机底层在 CPU和内存之间建立了两级缓存 , CPU读取数据时 , 会从缓存中查找数据 , 没有找到才会从内存中寻找数据 , 那redis若都采用raw的形式进行字符串编码存储 , 则很有可能SDS和RedisObject在内存中间隔较远 , 导致没有被同时加载到缓存中 , 从而可能会导致缓存穿透的问题 , 而一般CPU的缓存是以64字节为一个缓存单位的 , 当Redis使用Emstr编码时 , 所有数据在内存中连续 , 大小刚好也是64字节 , 更容易被缓存命中 . 所以Redis字符串使用emstr 要比 raw编码性能更好 .
感谢大家能看到这 , 以上小编的逻辑难免会有些疏漏, 如果你有什么不理解的 , 或者发现了那些错误的地方, 请随时通过留言与小编交流,最后希望大家越来越好,技术精湛,牛气冲天,共勉!