请选择 进入手机版 | 继续访问电脑版

[Redis] Redis核心原理与实践之字符串实现原理

[复制链接]
查看124 | 回复30 | 2021-9-14 02:11:40 | 显示全部楼层 |阅读模式

本文分析Redis字符串的实现原理,内容摘自新书《Redis核心原理与实践》。这本书深入地分析了Redis常用特性的内部机制与实现方式,内容源自对Redis源码的分析,并从中总结出计划 思绪 、实现原理。通过阅读本书,读者可以快速、轻松地相识 Redis的内部运行机制。

Redis是一个键值对数据库(key-value DB),下面是一个简单的Redis的下令 :

  1. > SET msg "hello wolrd"
复制代码

该下令 将键“msg”、值“hello wolrd”这两个字符串保存到Redis数据库中。
本章分析Redis怎样 在内存中保存这些字符串。

redisObject

Redis中的数据对象server.h/redisObject是Redis对内部存储的数据定义的抽象范例 ,在深入分析Redis数据范例 前,我们先相识 redisObject,它的定义如下:

  1. typedef struct redisObject {
  2. unsigned type:4;
  3. unsigned encoding:4;
  4. unsigned lru:LRU_BITS;
  5. int refcount;
  6. void *ptr;
  7. } robj;
复制代码
  • type:数据范例 。
  • encoding:编码格式,即存储数据使用 的数据布局 。同一个范例 的数据,Redis会根据数据量、占用内存等环境 使用 不同的编码,最大限度地节省 内存。
  • refcount,引用计数,为了节省 内存,Redis会在多处引用同一个redisObject。
  • ptr:指向实际 的数据布局 ,如sds,真正的数据存储在该数据布局 中。
  • lru:24位,LRU时间戳或LFU计数。

redisObject负责装载Redis中的全部 键和值。redisObject.ptr指向真正存储数据的数据布局 ,redisObject .refcount、redisObject.lru等属性则用于管理数据(数据共享、数据过期等)。

  1. 提示:type、encoding、lru使用了C语言中的位段定义,这3个属性使用同一个unsigned int的不同bit位。这样可以最大限度地节省内存。
复制代码

Redis定义了以下数据范例 和编码,如表1-1所示。

Redis核心原理与实践之字符串实现原理

本书第1部分会对表1-1中前五种数据范例 举行 分析,末了 两种数据范例 会在第5部分举行 分析。假如 读者如今 对表1-1中内容感到迷惑 ,则可以先带着疑问继续阅读本书。

sds

我们知道,C语言中将空字符末了 的字符数组作为字符串,而Redis对此做了扩展,定义了字符串范例 sds(Simple Dynamic String)。
Redis键都是字符串范例 ,Redis中最简单的值范例 也是字符串范例 ,
字符串范例 的Redis值可用于很多场景,如缓存HTML片断 、记任命 户登录信息等。

定义

提示:本节代码如无特殊 阐明 ,均在sds.h/sds.c中。
对于不同长度的字符串,Redis定义了不同的sds布局 体:

  1. typedef char *sds;
  2. struct __attribute__ ((__packed__)) sdshdr5 {
  3. unsigned char flags;
  4. char buf[];
  5. };
  6. struct __attribute__ ((__packed__)) sdshdr8 {
  7. uint8_t len;
  8. uint8_t alloc;
  9. unsigned char flags;
  10. char buf[];
  11. };
  12. ...
复制代码

Redis还定义了sdshdr16、sdshdr32、sdshdr64布局 体。为了版面整齐 ,这里不展示sdshdr16、sdshdr32、sdshdr64 布局 体的代码,它们与sdshdr8布局 体基本雷同 ,只是len、alloc属性使用 了 uint16_t、uint32、uint64_t范例 。Redis定义不同sdshdr布局 体是为了针对不同长度的字符串,使用 合适的len、alloc属性范例 ,最大限度地节省 内存。

  • len:已使用 字节长度,即字符串长度。sdshdr5可存放的字符串长度小于32(25),sdshdr8可存放的字符串长度小于256(28),以此类推。由于该属性记录了字符串长度,以是 sds可以在常数时间内获取字符串长度。Redis限定 了字符串的最大长度不能超过512MB。
  • alloc:已申请字节长度,即sds总长度。alloc-len为sds中的可用(空闲)空间。
  • flag:低3位代表sdshdr的范例 ,高5位只在sdshdr5中使用 ,表示字符串的长度,以是 sdshdr5中没有len属性。别的 ,由于Redis对sdshdr5的定义是常量字符串,不支持扩容,以是 不存在alloc属性。
  • buf:字符串内容,sds遵照 C语言字符串的规范,保存一个空字符作为buf的末了 ,并且不计入len、alloc属性。如许 可以直接使用 C语言strcmp、strcpy等函数直接操作sds。

提示:sdshdr布局 体中的buf数组并没有指定数组长度,它是C99规范定义的柔性数组—布局 体中末了 一个属性可以被定义为一个大小可变的数组(该属性前必须有其他属性)。使用 sizeof函数计算包含柔性数组的布局 体大小,返回效果 不包括柔性数组占用的内存。
别的 ,attribute((packed))关键字可以取消布局 体内的字节对齐以节省 内存。

操作分析

接下来看一下sds构建函数:

  1. sds sdsnewlen(const void *init, size_t initlen) {
  2. void *sh;
  3. sds s;
  4. // [1]
  5. char type = sdsReqType(initlen);
  6. // [2]
  7. if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;
  8. // [3]
  9. int hdrlen = sdsHdrSize(type);
  10. unsigned char *fp; /* flags pointer. */
  11. sh = s_malloc(hdrlen+initlen+1);
  12. ...
  13. // [4]
  14. s = (char*)sh+hdrlen;
  15. fp = ((unsigned char*)s)-1;
  16. switch(type) {
  17. case SDS_TYPE_5: {
  18. *fp = type | (initlen << SDS_TYPE_BITS);
  19. break;
  20. }
  21. case SDS_TYPE_8: {
  22. SDS_HDR_VAR(8,s);
  23. sh->len = initlen;
  24. sh->alloc = initlen;
  25. *fp = type;
  26. break;
  27. }
  28. ...
  29. }
  30. if (initlen && init)
  31. memcpy(s, init, initlen);
  32. s[initlen] = '\0';
  33. // [5]
  34. return s;
  35. }
复制代码

参数阐明 :

  • init、initlen:字符串内容、长度。

【1】根据字符串长度,判定 对应的sdshdr范例 。
【2】长度为0的字符串后续通常必要 扩容,不应该使用 sdshdr5,以是 这里转换为sdshdr8。
【3】sdsHdrSize函数负责查询sdshdr布局 体的长度,s_malloc函数负责申请内存空间,申请的内存空间长度为hdrlen+initlen+1,此中 hdrlen为sdshdr布局 体长度(不包含buf属性),initlen为字符串内容长度,末了 一个字节用于存放空字符“\0”。s_malloc与C语言的malloc函数的作用雷同 ,负责分配指定大小的内存空间。
【4】给sdshdr属性赋值。
SDS_HDR_VAR是一个宏,负责将sh指针转化为对应的sdshdr布局 体指针。
【5】留意 ,sds实际 上就是char*的别名,这里返回的s指针指向sdshdr.buf属性,即字符串内容。Redis通过该指针可以直接读/写字符串数据。

构建一个内容为“hello wolrd”的sds,其布局 如图1-1所示。

Redis核心原理与实践之字符串实现原理

sds的扩容机制是一个很告急 的功能。

  1. sds sdsMakeRoomFor(sds s, size_t addlen) {
  2. void *sh, *newsh;
  3. // [1]
  4. size_t avail = sdsavail(s);
  5. size_t len, newlen;
  6. char type, oldtype = s[-1] & SDS_TYPE_MASK;
  7. int hdrlen;
  8. if (avail >= addlen) return s;
  9. // [2]
  10. len = sdslen(s);
  11. sh = (char*)s-sdsHdrSize(oldtype);
  12. newlen = (len+addlen);
  13. // [3]
  14. if (newlen < SDS_MAX_PREALLOC)
  15. newlen *= 2;
  16. else
  17. newlen += SDS_MAX_PREALLOC;
  18. // [4]
  19. type = sdsReqType(newlen);
  20. if (type == SDS_TYPE_5) type = SDS_TYPE_8;
  21. // [5]
  22. hdrlen = sdsHdrSize(type);
  23. if (oldtype==type) {
  24. newsh = s_realloc(sh, hdrlen+newlen+1);
  25. if (newsh == NULL) return NULL;
  26. s = (char*)newsh+hdrlen;
  27. } else {
  28. newsh = s_malloc(hdrlen+newlen+1);
  29. if (newsh == NULL) return NULL;
  30. memcpy((char*)newsh+hdrlen, s, len+1);
  31. s_free(sh);
  32. s = (char*)newsh+hdrlen;
  33. s[-1] = type;
  34. sdssetlen(s, len);
  35. }
  36. // [6]
  37. sdssetalloc(s, newlen);
  38. return s;
  39. }
复制代码

参数阐明 :
addlen:要求扩容后可用长度(alloc-len)大于该参数。
【1】获取当前可用空间长度。假如 当前可用空间长度满意 要求,则直接返回。
【2】sdslen负责获取字符串长度,由于sds.len中记录了字符串长度,该操作复杂度为O(1)。这里len变量为原sds字符串长度,newlen变量为新sds长度。sh指向原sds的sdshdr布局 体。
【3】预分配比参数要求多的内存空间,避免每次扩容都要举行 内存拷贝操作。新sds长度假如 小于SDS_MAX_PREALLOC(默以为 1024×1024,单位为字节),则新sds长度自动 扩容为2倍。否则,新sds长度自动 增长 SDS_MAX_PREALLOC。
【4】sdsReqType(newlen)负责计算新的sdshdr范例 。留意 ,扩容后的范例 不使用 sdshdr5,该范例 不支持扩容操作。
【5】假如 扩容后sds还是同一范例 ,则使用 s_realloc函数申请内存。否则,由于sds布局 已经变动,必须移动整个sds,直接分配新的内存空间,并将原来的字符串内容复制到新的内存空间。s_realloc与C语言realloc函数的作用雷同 ,负责为给定指针重新分配给定大小的内存空间。它会尝试在给定指针原地址空间上重新分配,如原地址空间无法满意 要求,则分配新内存空间并复制内容。
【6】更新sdshdr.alloc属性。

对上面“hello wolrd”的sds调用sdsMakeRoomFor(sds,64),则天生 的sds如图1-2所示。

Redis核心原理与实践之字符串实现原理

从图1-2中可以看到,使用 len记录字符串长度后,字符串中可以存放空字符。Redis字符串支持二进制安全,可以将用户的输入存储为没有任何特定格式意义的原始数据流,因此Redis字符串可以存储任何数据,比如图片数据流或序列化对象。C语言字符串将空字符作为字符串末了 的特定标记字符,它不是二进制安全的。
sds常用函数如表1-2所示。

函数 作用
sdsnew,sdsempty 创建sds
sdsfree,sdsclear,sdsRemoveFreeSpace 开释 sds,清空sds中的字符串内容,移除sds剩余的可用空间
sdslen 获取sds字符串长度
sdsdup 将给定字符串复制到sds中,覆盖原字符串
sdscat 将给定字符串拼接到sds字符串内容后
sdscmp 对比两个sds字符串是否雷同
sdsrange 获取子字符串,不在指定范围内的字符串将被扫除

编码

字符串范例 一共有3种编码:

  • OBJ_ENCODING_EMBSTR:长度小于或等于OBJ_ENCODING_EMBSTR_SIZE_LIMIT(44字节)的字符串。

在该编码中,redisObject、sds布局 存放在一块一连 内存块中,如图1-3所示。

Redis核心原理与实践之字符串实现原理

OBJ_ENCODING_EMBSTR编码是Redis针对短字符串的优化,有如下长处 :
(1)内存申请和开释 都只必要 调用一次内存操作函数。
(2)redisObject、sdshdr布局 保存在一块一连 的内存中,减少了内存碎片。

  • OBJ_ENCODING_RAW:长度大于OBJ_ENCODING_EMBSTR_SIZE_LIMIT的字符串,在该编码中,redisObject、sds布局 存放在两个不一连 的内存块中。
  • OBJ_ENCODING_INT:将数值型字符串转换为整型,可以大幅降低数据占用的内存空间,如字符串“123456789012”必要 占用12字节,在Redis中,会将它转化为long long范例 ,只占用8字节。

我们向Redis发送一个哀求 后,Redis会剖析 哀求 报文,并将下令 、参数转化为redisObjec。
object.c/createStringObject函数负责完成该操作:

  1. robj *createStringObject(const char *ptr, size_t len) {
  2. if (len <= OBJ_ENCODING_EMBSTR_SIZE_LIMIT)
  3. return createEmbeddedStringObject(ptr,len);
  4. else
  5. return createRawStringObject(ptr,len);
  6. }
复制代码

可以看到,这里根据字符串长度,将encoding转化为OBJ_ENCODING_RAW或OBJ_ENCODING_EMBSTR的redisObject。

将参数转换为redisObject后,Redis再将redisObject存入数据库,比方 :

  1. > SET Introduction "Redis is an open source (BSD licensed), in-memory data structure store, used as a database, cache and message broker. "
复制代码

Redis会将键“Introduction”、值“Redis...”转换为两个redisObject,再将redisObject存入数据库,效果 如图1-4所示。

Redis核心原理与实践之字符串实现原理

Redis中的键都是字符串范例 ,并使用 OBJ_ENCODING_RAW、OBJ_ENCODING_ EMBSTR编码,而Redis还会尝试将字符串范例 的值转换为OBJ_ENCODING_INT 编码。object.c/tryObjectEncoding函数完成该操作:

  1. robj *tryObjectEncoding(robj *o) {
  2. long value;
  3. sds s = o->ptr;
  4. size_t len;
  5. ...
  6. // [1]
  7. if (o->refcount > 1) return o;
  8. len = sdslen(s);
  9. // [2]
  10. if (len <= 20 && string2l(s,len,&value)) {
  11. // [3]
  12. if ((server.maxmemory == 0 ||
  13. !(server.maxmemory_policy & MAXMEMORY_FLAG_NO_SHARED_INTEGERS)) &&
  14. value >= 0 &&
  15. value < OBJ_SHARED_INTEGERS)
  16. {
  17. decrRefCount(o);
  18. incrRefCount(shared.integers[value]);
  19. return shared.integers[value];
  20. } else {
  21. // [4]
  22. if (o->encoding == OBJ_ENCODING_RAW) {
  23. sdsfree(o->ptr);
  24. o->encoding = OBJ_ENCODING_INT;
  25. o->ptr = (void*) value;
  26. return o;
  27. } else if (o->encoding == OBJ_ENCODING_EMBSTR) {
  28. // [5]
  29. decrRefCount(o);
  30. return createStringObjectFromLongLongForValue(value);
  31. }
  32. }
  33. }
  34. // [6]
  35. if (len <= OBJ_ENCODING_EMBSTR_SIZE_LIMIT) {
  36. robj *emb;
  37. if (o->encoding == OBJ_ENCODING_EMBSTR) return o;
  38. emb = createEmbeddedStringObject(s,sdslen(s));
  39. decrRefCount(o);
  40. return emb;
  41. }
  42. // [7]
  43. trimStringObjectIfNeeded(o);
  44. return o;
  45. }
复制代码

【1】该数据对象被多处引用,不能再举行 编码操作,否则会影响其他地方的正常运行。
【2】假如 字符串长度小于或等于20,则调用string2l函数尝试将其转换为long long范例 ,假如 成功则返回1。
在C语言中,long long占用8字节,取值范围是-9223372036854775808~9223372036854775807,因此最多能保存长度为19的字符串转换后的数值,加上负数的符号位,一共20位。
下面是字符串可以转换为OBJ_ENCODING_INT 编码的处理步骤。
【3】起首 尝试使用 shared.integers中的共享数据,避免重复创建雷同 数据对象而浪费内存。shared是Redis启动时创建的共享数据集,存放了Redis中常用的共享数据。shared.integers是一个整数数组,存放了小数字0~9999,共享于各个使用 场景。
留意 :假如 设置 了server.maxmemory,并使用 了不支持共享数据的镌汰 算法(LRU、LFU),那么这里不能使用 共享数据,由于 这时每个数据中都必须存在一个redisObjec.lru属性,这些算法才可以正常工作。
【4】假如 不能使用 共享数据并且原编码格式为OBJ_ENCODING_RAW,则将redisObject.ptr原来的sds范例 更换 为字符串转换后的数值。
【5】假如 不能使用 共享数据并且原编码格式为OBJ_ENCODING_EMBSTR,由于redisObject、sds存放在同一个内存块中,无法直接更换 redisObject.ptr,以是 调用createString- ObjectFromLongLongForValue函数创建一个新的redisObject,编码为OBJ_ENCODING_INT,redisObject.ptr指向long long范例 或long范例 。
【6】到这里,阐明 字符串不能转换为OBJ_ENCODING_INT 编码,尝试将其转换为OBJ_ENCODING_EMBSTR编码。
【7】到这里,阐明 字符串只能使用 OBJ_ENCODING_RAW编码,尝试开释 sds中剩余的可用空间。
字符串范例 的实当代 码在t_string.c中,读者可以查看源码相识 更多实现细节。

提示:server.c/redisCommandTable定义了每个Redis下令 与对应的处理函数,读者可以从这里查找感爱好 的下令 的处理函数。

  1. struct redisCommand redisCommandTable[] = {
  2. ...
  3. {"get",getCommand,2,
  4. "read-only fast @string",
  5. 0,NULL,1,1,1,0,0,0},
  6. {"set",setCommand,-3,
  7. "write use-memory @string",
  8. 0,NULL,1,1,1,0,0,0},
  9. ...
  10. }
复制代码

GET下令 的处理函数为getCommand,SET下令 的处理函数为setCommand,以此类推。

别的 ,我们可以通过TYPE下令 查看数据对象范例 ,通过OBJECT ENCODING下令 查看编码:

  1. > SET msg "hello world"
  2. OK
  3. > TYPE msg
  4. string
  5. > OBJECT ENCODING msg
  6. "embstr"
  7. > SET Introduction "Redis is an open source (BSD licensed), in-memory data structure store, used as a database, cache and message broker. "
  8. OK
  9. > TYPE Introduction
  10. string
  11. > OBJECT ENCODING info
  12. "raw"
  13. > SET page 1
  14. OK
  15. > TYPE page
  16. string
  17. > OBJECT ENCODING page
  18. "int"
复制代码

总结:

Redis中的全部 键和值都是redisObject变量。

  • sds是Redis定义的字符串范例 ,支持二进制安全、扩容。
  • sds可以在常数时间内获取字符串长度,并使用 预分配内存机制减少内存拷贝次数。
  • Redis对数据编码的告急 目标 是最大限度地节省 内存。字符串范例 可以使用 OBJ_ENCODING_ RAW、OBJ_ENCODING_EMBSTR、OBJ_ENCODING_INT编码格式。

本文内容摘自作者新书《Redis核心原理与实践》,这本书深入地分析了Redis常用特性的内部机制与实现方式,大部分内容源自对Redis源码的分析,并从中总结出计划 思绪 、实现原理。通过阅读本书,读者可以快速、轻松地相识 Redis的内部运行机制。

京东链接
豆瓣链接

到此这篇关于Redis核心原理与实践之字符串实现原理的文章就先容 到这了,更多相干 Redis字符串实现原理内容请搜索 脚本之家从前 的文章或继续欣赏 下面的相干 文章渴望 大家以后多多支持脚本之家!


免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
回复

使用道具 举报

avatar 真无牙泛 | 2021-9-14 04:33:39 | 显示全部楼层
admin楼主,我告诉你一个你不知道的的秘密,有一个牛逼的网站,运动刷步数还是免费刷的,QQ和微信都可以刷,特别好用。访问地址:http://yd.mxswl.com 猫先森网络
回复

使用道具 举报

好多兽医在广场上义诊,admin楼主去看看吧!
回复

使用道具 举报

avatar 爸证欢 | 2021-9-20 15:20:08 | 显示全部楼层
admin楼主的帖子越来越有深度了!
回复

使用道具 举报

avatar 阿源285 | 2021-9-21 00:23:30 | 显示全部楼层
你觉得该怎么做呢?
回复

使用道具 举报

avatar 加菲猫419 | 2021-9-26 23:34:33 | 显示全部楼层
怎么我回帖都没人理我呢?
回复

使用道具 举报

avatar 梦太晚616 | 2021-9-30 19:11:24 | 显示全部楼层
admin楼主最近很消极啊!
回复

使用道具 举报

avatar 玻璃杯儿敌 | 2021-10-4 10:03:02 | 显示全部楼层
admin楼主,我告诉你一个你不知道的的秘密,有一个牛逼的网站,影视频道的网站所有电影和连续剧都可以免费看的。访问地址:http://tv.mxswl.com
回复

使用道具 举报

avatar wzyu638116 | 2021-10-4 16:14:36 | 显示全部楼层
最近精神病院在打折,admin楼主去看看吧?
回复

使用道具 举报

avatar 大嘴997 | 2021-10-4 17:07:49 | 显示全部楼层
顶顶更健康!
回复

使用道具 举报

下一页 »
1234下一页
返回列表 发新帖
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则