04 | 内存友好的数据结构该如何细化设计？

1、要想理解 Redis 数据类型的设计，必须要先了解 redisObject。 Redis 的 key 是 String 类型，但 value 可以是很多类型（String/List/Hash/Set/ZSet等），所以 Redis 要想存储多种数据类型，就要设计一个通用的对象进行封装，这个对象就是 redisObject。 // server.h typedef struct redisObject { unsigned type:4; unsigned encoding:4; unsigned lru:LRU_BITS; int refcount; void *ptr; } robj; 其中，最重要的 2 个字段： - type：面向用户的数据类型（String/List/Hash/Set/ZSet等） - encoding：每一种数据类型，可以对应不同的底层数据结构来实现（SDS/ziplist/intset/hashtable/skiplist等） 例如 String，可以用 embstr（嵌入式字符串，redisObject 和 SDS 一起分配内存），也可以用 rawstr（redisObject 和 SDS 分开存储）实现。 又或者，当用户写入的是一个「数字」时，底层会转成 long 来存储，节省内存。 同理，Hash/Set/ZSet 在数据量少时，采用 ziplist 存储，否则就转为 hashtable 来存。 所以，redisObject 的作用在于： 1) 为多种数据类型提供统一的表示方式 2) 同一种数据类型，底层可以对应不同实现，节省内存 3）支持对象共享和引用计数，共享对象存储一份，可多次使用，节省内存 redisObject 更像是连接「上层数据类型」和「底层数据结构」之间的桥梁。 2、关于 String 类型的实现，底层对应 3 种数据结构： - embstr：小于 44 字节，嵌入式存储，redisObject 和 SDS 一起分配内存，只分配 1 次内存 - rawstr：大于 44 字节，redisObject 和 SDS 分开存储，需分配 2 次内存 - long：整数存储（小于 10000，使用共享对象池存储，但有个前提：Redis 没有设置淘汰策略，详见 object.c 的 tryObjectEncoding 函数） 3、ziplist 的特点： 1) 连续内存存储：每个元素紧凑排列，内存利用率高 2) 变长编码：存储数据时，采用变长编码（满足数据长度的前提下，尽可能少分配内存） 3）寻找元素需遍历：存放太多元素，性能会下降（适合少量数据存储） 4) 级联更新：更新、删除元素，会引发级联更新（因为内存连续，前面数据膨胀/删除了，后面要跟着一起动） List、Hash、Set、ZSet 底层都用到了 ziplist。 4、intset 的特点： 1) Set 存储如果都是数字，采用 intset 存储 2) 变长编码：数字范围不同，intset 会选择 int16/int32/int64 编码（intset.c 的 _intsetValueEncoding 函数） 3）有序：intset 在存储时是有序的，这意味着查找一个元素，可使用「二分查找」（intset.c 的 intsetSearch 函数） 4) 编码升级/降级：添加、更新、删除元素，数据范围发生变化，会引发编码长度升级或降级 课后题：SDS 判断是否使用嵌入式字符串的条件是 44 字节，你知道为什么是 44 字节吗？ 嵌入式字符串会把 redisObject 和 SDS 一起分配内存，那在存储时结构是这样的： - redisObject：16 个字节 - SDS：sdshdr8（3 个字节）+ SDS 字符数组（N 字节 + \0 结束符 1 个字节） Redis 规定嵌入式字符串最大以 64 字节存储，所以 N = 64 - 16(redisObject) - 3(sdshr8) - 1(\0)， N = 44 字节。

Kaito大佬描述的已经很详细了，44是因为 N = 64 - 16(redisObject) - 3(sdshr8) - 1(\0)， N = 44 字节。那么为什么是64减呢，为什么不是别的，因为在目前的x86体系下，一般的缓存行大小是64字节，redis为了一次能加载完成，因此采用64自己作为embstr类型(保存redisObject)的最大长度。

先回答老师的问题：为什么嵌入式字符串是以44字节为边界？ 在了解这个问题之前，我们来了解一下jemalloc 分配内存机制，jemalloc 为了减少分配的内存空间大小不是2的幂次，在每次分配内存的时候都会返回2的幂次的空间大小，比如我需要分配5字节空间，jemalloc 会返回8字节，15字节会返回16字节。其常见的分配空间大小有： 8, 16, 32, 64, ..., 2kb, 4kb, 8kb。 但是这种方式也可能会造成，空间的浪费，比如我需要33字节，结果给我64字节，为了解决这个问题jemalloc将内存分配划分为，小内存（small_class）和大内存（large_class）通过不同的内存大小使用不同阶级策略，比如小内存允许存在48字节等方式。 Redis的嵌入式字符串，头部空间大小（redisObject + sdshdr8 + 1）已经去到了20字节，为了仍然能够满足jemalloc的64字节范围(48的太小了)，所以限制为44字节大小 此外总结一下阅读本文后的理解： redis为了充分提高内存利用率，从几个方面入手： 1、淘汰不在使用的内存空间（后面章节会详细说明） 2、紧凑型的内存设计 3、实例内存共享 在为了提高内存利用率，redis做出了以下努力： 1、设计实现了SDS 2、设计实现了ziplist 3、设计实现了intset 4、搭配redisObject设计了嵌入式字符串 5、设计了共享对象（共享内存大部是常量实例） 此外补充一下老师文章中的内容，ziplist虽然能带来内存的节省，但是本质上是时间换空间的结果，当插入或者删除元素的时候由于内存使用率的变化，每次都有可能导致previous_entry_length 等字段需要扩展/缩小字节大小，从而导致一种现象【连锁更新】，就是每次更新或者删除的时候都要取重新修改head中的字节大小，从而带来性能开销，当然这种情况比较极端基本上不会触发。

44字节是因为加上sds首部和redisobject后，大小为64字节，正好是CPU Cache Line的大小，CPU访问内存读取数据时以cache line为单位，一次读取64字节的数据，如果整个结构体起始地址64字节对齐，一次内存IO就可以读取全部数据

原先embstr的限制长度是39，现在提升到了44，还是归功于sdshdr变成sdshdr8，头减少了5字节。 注释：The current limit of 44 is chosen so that the biggest string object. we allocate as EMBSTR will still fit into the 64 byte arena of jemalloc.

而 sh+1 表示把内存地址从 sh 起始地址开始移动一定的大小，移动的距离等于 sdshdr8 结构体的大小。 o->ptr = sh+1; 【请教】为啥 +1 移动的距离就等于 sdshdr8 结构体的大小呢？ 有大佬赐教下吗 ？？

Redis rawstr 中redisObject 和 SDS 分开存储，这样有什么优点呢

server.c中看到struct sharedObjectsStruct shared; ，createSharedObjects函数里只看到对shared变量赋值，在代码里没看到如何将这个变量搞到共享内存里？

zipStoreEntryEncoding函数里为什么判断rawlen长度0x3f 0x3fff后直接没有判断0x3fffffff直接len+4了？

ziplist 为啥不直接用这种结构体定义 不更清晰吗？ struct __attribute__ ((__packed__)) zipList { uint32_t totalBytes; uint32_t lastItemOffset; uint16_t itemCount; char items[0]; };