写点什么

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

用户头像
binecy
关注
发布于: 3 小时前
Redis核心原理与实践--字符串实现原理

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

> SET msg "hello wolrd"
复制代码


该命令将键“msg”、值“hello wolrd”这两个字符串保存到 Redis 数据库中。

本章分析 Redis 如何在内存中保存这些字符串。

redisObject

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

typedef struct redisObject {    unsigned type:4;    unsigned encoding:4;    unsigned lru:LRU_BITS;    int refcount;    void *ptr;} robj;
复制代码


  • type:数据类型。

  • encoding:编码格式,即存储数据使用的数据结构。同一个类型的数据,Redis 会根据数据量、占用内存等情况使用不同的编码,最大限度地节省内存。

  • refcount,引用计数,为了节省内存,Redis 会在多处引用同一个 redisObject。

  • ptr:指向实际的数据结构,如 sds,真正的数据存储在该数据结构中。

  • lru:24 位,LRU 时间戳或 LFU 计数。


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

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


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


本书第 1 部分会对表 1-1 中前五种数据类型进行分析,最后两种数据类型会在第 5 部分进行分析。如果读者现在对表 1-1 中内容感到疑惑,则可以先带着疑问继续阅读本书。

sds

我们知道,C 语言中将空字符结尾的字符数组作为字符串,而 Redis 对此做了扩展,定义了字符串类型 sds(Simple Dynamic String)。

Redis 键都是字符串类型,Redis 中最简单的值类型也是字符串类型,

字符串类型的 Redis 值可用于很多场景,如缓存 HTML 片段、记录用户登录信息等。

定义

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

typedef char *sds;
struct __attribute__ ((__packed__)) sdshdr5 { unsigned char flags; char buf[];};struct __attribute__ ((__packed__)) sdshdr8 { uint8_t len; uint8_t alloc; unsigned char flags; char buf[];};...
复制代码


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 构建函数:

sds sdsnewlen(const void *init, size_t initlen) {    void *sh;    sds s;    // [1]    char type = sdsReqType(initlen);    // [2]    if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;    // [3]    int hdrlen = sdsHdrSize(type);    unsigned char *fp; /* flags pointer. */
sh = s_malloc(hdrlen+initlen+1); ... // [4] s = (char*)sh+hdrlen; fp = ((unsigned char*)s)-1; switch(type) { case SDS_TYPE_5: { *fp = type | (initlen << SDS_TYPE_BITS); break; } case SDS_TYPE_8: { SDS_HDR_VAR(8,s); sh->len = initlen; sh->alloc = initlen; *fp = type; break; } ... } if (initlen && init) memcpy(s, init, initlen); s[initlen] = '\0'; // [5] return s;}
复制代码


参数说明:

  • 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 所示。


sds 的扩容机制是一个很重要的功能。

sds sdsMakeRoomFor(sds s, size_t addlen) {    void *sh, *newsh;    // [1]    size_t avail = sdsavail(s);    size_t len, newlen;    char type, oldtype = s[-1] & SDS_TYPE_MASK;    int hdrlen;
if (avail >= addlen) return s; // [2] len = sdslen(s); sh = (char*)s-sdsHdrSize(oldtype); newlen = (len+addlen); // [3] if (newlen < SDS_MAX_PREALLOC) newlen *= 2; else newlen += SDS_MAX_PREALLOC;
// [4] type = sdsReqType(newlen); if (type == SDS_TYPE_5) type = SDS_TYPE_8; // [5] hdrlen = sdsHdrSize(type); if (oldtype==type) { newsh = s_realloc(sh, hdrlen+newlen+1); if (newsh == NULL) return NULL; s = (char*)newsh+hdrlen; } else { 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); } // [6] sdssetalloc(s, newlen); return s;}
复制代码


参数说明:

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 所示。



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

编码

字符串类型一共有 3 种编码:

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

  • 在该编码中,redisObject、sds 结构存放在一块连续内存块中,如图 1-3 所示。


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 函数负责完成该操作:


robj *createStringObject(const char *ptr, size_t len) {    if (len <= OBJ_ENCODING_EMBSTR_SIZE_LIMIT)        return createEmbeddedStringObject(ptr,len);    else        return createRawStringObject(ptr,len);}
复制代码


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


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

> 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 中的键都是字符串类型,并使用 OBJ_ENCODING_RAW、OBJ_ENCODING_ EMBSTR 编码,而 Redis 还会尝试将字符串类型的值转换为 OBJ_ENCODING_INT 编码。object.c/tryObjectEncoding 函数完成该操作:


robj *tryObjectEncoding(robj *o) {    long value;    sds s = o->ptr;    size_t len;    ...    // [1]     if (o->refcount > 1) return o;
len = sdslen(s); // [2] if (len <= 20 && string2l(s,len,&value)) { // [3] if ((server.maxmemory == 0 || !(server.maxmemory_policy & MAXMEMORY_FLAG_NO_SHARED_INTEGERS)) && value >= 0 && value < OBJ_SHARED_INTEGERS) { decrRefCount(o); incrRefCount(shared.integers[value]); return shared.integers[value]; } else { // [4] if (o->encoding == OBJ_ENCODING_RAW) { sdsfree(o->ptr); o->encoding = OBJ_ENCODING_INT; o->ptr = (void*) value; return o; } else if (o->encoding == OBJ_ENCODING_EMBSTR) { // [5] decrRefCount(o); return createStringObjectFromLongLongForValue(value); } } }
// [6] if (len <= OBJ_ENCODING_EMBSTR_SIZE_LIMIT) { robj *emb;
if (o->encoding == OBJ_ENCODING_EMBSTR) return o; emb = createEmbeddedStringObject(s,sdslen(s)); decrRefCount(o); return emb; }
// [7] trimStringObjectIfNeeded(o);
return o;}
复制代码


【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 命令与对应的处理函数,读者可以从这里查找感兴趣的命令的处理函数。


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

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


另外,我们可以通过 TYPE 命令查看数据对象类型,通过 OBJECT ENCODING 命令查看编码:

> SET msg "hello world"OK> TYPE msgstring> OBJECT ENCODING  msg"embstr"> SET Introduction "Redis is an open source (BSD licensed), in-memory data structure store, used as a database, cache and message broker. "OK> TYPE Introductionstring> OBJECT ENCODING  info"raw"> SET page 1OK> TYPE pagestring> OBJECT ENCODING  page"int"
复制代码


总结:


  • Redis 中的所有键和值都是 redisObject 变量。

  • sds 是 Redis 定义的字符串类型,支持二进制安全、扩容。

  • sds 可以在常数时间内获取字符串长度,并使用预分配内存机制减少内存拷贝次数。

  • Redis 对数据编码的主要目的是最大限度地节省内存。字符串类型可以使用 OBJ_ENCODING_ RAW、OBJ_ENCODING_EMBSTR、OBJ_ENCODING_INT 编码格式。


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

经过该书编辑同意,我会继续在个人技术公众号(binecy)发布书中部分章节内容,作为书的预览内容,欢迎大家查阅,谢谢。


京东链接

豆瓣链接

发布于: 3 小时前阅读数: 6
用户头像

binecy

关注

还未添加个人签名 2020.08.26 加入

《Redis核心原理与实践》作者,欢迎关注个人技术公众号binecy

评论

发布
暂无评论
Redis核心原理与实践--字符串实现原理