我还有机会吗?来自Redis字符串底层数据结构的灵魂发问
前言
作为日常使用最为频繁的缓存系统redis ， 而字符串又作为最为频繁使用的redis数据结构 ， 可以说是我们的老朋友了 ， 但是你真的熟悉他吗？
都说学习源码是最好的向大师学习的机会 ， 那最为当下最优秀的缓存数据库，你真的不想看看他是怎么实现的吗？
那不管你是刚毕业的准备面试的新同学，还是已经工作很多年的老大哥，今天和小编一起，带着你的疑问，让我们从底层数据，重新认识下Redis字符串 。
1、Redis为什么没有使用C语言原生的字符串?
首先本文的出现说明了一个问题 , 那就是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则会被截断 , 无法保证数据被正确储存.
综上所述: 无法使用C语言字符串较好的实现Redis字符串的相关功能并保证性能 , 所以Redis的作者别无选择只能重新设计
2、SDS字符串
理解了为什么要自定义字符串结构之后 , 让我们来认识下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>.bufstatic 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;}// 此源码摘自网络
3、扩容问题
上面我们看到了 , 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;elsenewlen += 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;}// 摘自互联网
4、RedisObject
在讲下面的编码优化前 , 我们先介绍下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: 实际数据对象引用
5、字符串的编码优化
举个栗子
//int 编码127.0.0.1:6379> SET keyInt 111111OK127.0.0.1:6379> DEBUG OBJECT keyIntValue 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 01234567890123456789012345678901234567aOK127.0.0.1:6379> STRLEN keyEmbstr(integer) 39127.0.0.1:6379> DEBUG OBJECT keyEmbstrValue 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 01234567890123456789012345678901234567abOK127.0.0.1:6379> STRLEN keyRaw(integer) 40127.0.0.1:6379> DEBUG OBJECT keyRawValue at:0x7f0869086300 refcount:1 encoding:raw serializedlength:21 lru:486755 lru_seconds_idle:29
从上面的例子我们可以看到 , 对于使用层面的 Redis字符串 来说在底层实现上有三种方式进行优化 , 下面为大家一一讲解.
5.1、Int编码
首先我们讲讲最简单的int编码 , 这个很好理解 , 当我们输入的字符串是纯数字时 , redis就会使用整数的编码方式进行存储 , 这个整数的范围就时long类型能表示的最大数 , 当超出这个范围 , 就会进化为 SDS结构进行存储 .
5.1.1、10000以内的整数优化
// 特别注意: value at: 表明的是数据的引用地址// 10000以内的整数存储127.0.0.1:6379> SET keyIntA 9999OK127.0.0.1:6379> SET keyIntB 9999OK127.0.0.1:6379> DEBUG OBJECT keyIntAValue at:0x7f0869085e00 refcount:3 encoding:int serializedlength:3 lru:478885 lru_seconds_idle:8458127.0.0.1:6379> DEBUG OBJECT keyIntBValue at:0x7f0869085e00 refcount:3 encoding:int serializedlength:3 lru:478885 lru_seconds_idle:8460// 10000以外的整数存储127.0.0.1:6379> SET keyIntC 10000OK127.0.0.1:6379> SET keyIntD 10000OK127.0.0.1:6379> DEBUG OBJECT keyIntCValue at:0x7f0869035ea0 refcount:1 encoding:int serializedlength:3 lru:487337 lru_seconds_idle:11127.0.0.1:6379> DEBUG OBJECT keyIntDValue 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也有相似的优化机制
embstr编码
在本小节最开始的例子中可以看到 字符串长度小于39时 , 会使用embstr编码 . 实际上此时redis创建字符串时 , 会一次性申请64字节内存 , 用于存放redisObject 和 sds 此时内存物理连续. 如下图所示
Raw编码
反之当字符串长度大于39时 , 会使用raw编码 , 这时redis创建字符串对象 , 会分两次申请内存 , 分别存储RedisObject 和 SDS对象, 如下图所示.
为什么39(44 3.2版本)是界限?
相信不少小伙伴读到这里都会有这个疑问 , 为啥时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字节
为什么要区分embstr和raw编码
首先我们知道对于CPU和内存之间的IO性能 , 同样是有较大差异的 , 所以计算机底层在 CPU和内存之间建立了两级缓存 , CPU读取数据时 , 会从缓存中查找数据 , 没有找到才会从内存中寻找数据 , 那redis若都采用raw的形式进行字符串编码存储 , 则很有可能SDS和RedisObject在内存中间隔较远 , 导致没有被同时加载到缓存中 , 从而可能会导致缓存穿透的问题 , 而一般CPU的缓存是以64字节为一个缓存单位的 , 当Redis使用Emstr编码时 , 所有数据在内存中连续 , 大小刚好也是64字节 , 更容易被缓存命中 . 所以Redis字符串使用emstr 要比 raw编码性能更好 .
End
感谢大家能看到这 ， 以上小编的逻辑难免会有些疏漏， 如果你有什么不理解的 ， 或者发现了那些错误的地方， 请随时通过留言与小编交流，最后希望大家越来越好，技术精湛，牛气冲天，共勉！