Redis数据结构和内存分配

编码方式

所有encoding编码方式：

OBJ_ENCODING_INT：表示成数字。最多标识long的最大值，超过转为OBJ_ENCODING_RAW。 OBJ_ENCODING_RAW： string原生表示方式。 OBJ_ENCODING_EMBSTR： 功能同RAW，只是数据是存储在一块连续的内存中，embstr创建和释放字符串操作内存的次数比RAW的2次降低为1次，修改将重新分配内存。 OBJ_ENCODING_HT： 类似hashtable，表示成dict。 OBJ_ENCODING_ZIPMAP： 是个旧的表示方式，已不再用。 OBJ_ENCODING_LINKEDLIST：双向列表，3.2以下版本使用 OBJ_ENCODING_ZIPLIST： 表示成ziplist。 OBJ_ENCODING_INTSET：表示成整数数组。用于set数据类型。 OBJ_ENCODING_SKIPLIST：表示成skiplist跳跃表。用于zset数据结构。 OBJ_ENCODING_QUICKLIST：表示成quicklist。用于list数据类型。

redisObject

Redis的key固定是string类型，但value类型可能是多个，Redis用dict来存储所有key对应value的类型的映射方式，而为了在dict中存储不同类型的value，redis使用了一个通用数据结构redisObject。

server.h：

SDS简单动态字符串

Sds （Simple Dynamic String，简单动态字符串）是Redis 底层所使用的字符串表示， 几乎所有的Redis 模块中都用了sds。 作用： Redis 底层所使用的字符串表示，替代C的char*类型。 每个包含字符串值的字符串对象都包含一个 sds 值。 sds.h结构，sds一共有5种类型的header。不同长度的字符串可以使用不同大小的header，从而节省内存。

struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; 
    uint8_t alloc; 
    unsigned char flags;  
    char buf[];
};

除了sdshdr5不用之外，其它4个header的结构都包含4个字段：

len: 表示字符串的长度（不包含空结束符）。 alloc: 表示字符串的最大容量（不包含空结束符字节）。 flags: 占用一个字节，通过bit低3位用来表示header的类型。 buf[]:字符串字节数组 注：header中__attribute__ ((packed))，是为了让编译器以紧凑模式分配内存。使header和sds的数据前后紧紧相邻

header转换逻辑：

例如，有一个s1 字符串 “pppp”，实际长度为4，但是会多分配两个单位，用来减少分配次数，以防将来扩展。

与C语言字符串对比好处：

• SDS获取字符串长度时间复杂度是O(1),而C是O(n)
• 杜绝缓冲区溢出:C 语言空间不足进行字符串拼接会造成缓冲区溢出，而SDS 会先进行空间扩展，再进行修改操作。
• 减少内存分配次数：C每次修改将进行内存重分配。SDS实现了空间预分配和惰性空间释放两种策略： (1)空间预分配：字符串扩展时内存分配比实际的多，减少内存重分配次数 (2)惰性空间释放：对字符串进行缩短操作，不会立即释放内存，等待后续使用
• 二进制安全：C字符串以\0作为结束标识，无法存取诸如图片等二进制文件，而SDS是以len属性长度来判断字符串是否结束。
• 兼容部分 C 字符串函数：SDS一样遵从每个字符串都是以\0结尾，可以重用一部分<string.h>函数

dict字典

dict跟java的Map类似。 dict数组 table 中每个元素都是指向 dictEntry 结构。 key 作键值，val 值可以是指针、uint64_t、int64_t、double。

• 1、哈希算法： hash = dict->type->hashFunction(key); //使用dictType的hashFunction计算哈希值 index = hash & dict->ht[x].sizemask; //使用sizemask计算索引值:
• 2、哈希冲突处理: 索引一样再对key进行比较
• 3、扩容和收缩：当哈希表保存的键值对太多或者太少时，就要通过 rerehash(重新散列）进行扩容或收缩 1、扩展：基于原哈希表创建一个大小等于 ht[0].used*2n 的哈希表（也就是扩大一倍） 2、通过哈希算法，计算索引值，将键值放到新的哈希表位置上 3、所有键值迁移后，释放原哈希表内存空间
• 4、触发扩容的条件： 　　　　　　1、服务器目前没有执行 BGSAVE 命令或者 BGREWRITEAOF 命令，并且负载因子大于等于1。 　　　　　　2、服务器目前正在执行 BGSAVE 命令或者 BGREWRITEAOF 命令，并且负载因子大于等于5。 　　　　注：负载因子 = 哈希表已保存节点数量(ht[0].used) / 哈希表大小(ht[0].size)
• 5、渐近式 rehash： 扩容和收缩是分批次、渐进式完成，在进行渐进式rehash期间，字典的删除、查找、更新等操作可能会在两个哈希表上进行，第一个哈希表没有找到，就会去第二个哈希表上进行查找。但是增加操作，一定是在新的哈希表上进行的。

ziplist压缩列表

ziplist是一个经过特殊编码的"双向链表"，它的设计目标就是为了提高存储效率。 可用于存储字符串或整数，其中整数被编码为实际整数，而不是编码成字符串序列。 它能以O(1)的时间复杂度在表的两端提供push和pop操作。 压缩列表的原理：不是按算法’压缩‘，而是将数据按照一定规则编码在一块连续的内存区域，

对比普通双向链表： 普通的双向链表，每个节点都占用独立的一块内存，各项之间用指针连接起来。这种方式可能会带来内存碎片，而且地址指针也会占用额外的内存。而ziplist却是将表中每一项存放在前后连续的地址空间内，一个ziplist整体占用一大块内存，并且对于值的存储采用了变长的编码方式。

entry转换为zlentry结构：

1、prevrawlen：记录压缩列表前一个节点的长度，根据前一个节点长度占用1个或5个字节，可以实现从尾部向头部遍历。 2、encoding：节点的encoding保存的是节点的content的内容类型以及长度，encoding类型一共有两种，一种字节数组一种是整数，encoding区域长度为1字节、2字节或者5字节长。 3、p：用于保存节点的内容，节点内容类型和长度由encoding决定。

为什么说ziplist节省内存？

测试数据：50万key，每个key10个field，hash结构使用ht(dict)编码和使用ziplist编码的差异：

(1)ht(dict)：

(2)ziplist ：

占用内存：

quicklist

3.2版本后推出的双向链表，替代原adList(linkedList)，减少大量数据下list的内存使用量。 简单的quicklist结构范例:

为什么用quicklist： adlist：耗内存，支持大量数据（数量或者单个的长度）的情况，插入、修改成本低。 ziplist：小规模数据下非常省内存，不适用大量数据，每次修改都会引发内存重分配。 基于空间和时间的考虑，Redis设计quicklist来结合双向链表和ziplist的优点

quicklist.h结构：

quicklist进行LZF压缩和不压缩逻辑：

quicklist不会对较小的ziplist进行压缩，由MIN_COMPRESS_BYTES控制，默认是48个字节。 quicklist 头、尾节点不会压缩，保证头、尾的插入是最高效的 插入数据到一个压缩节点，要先对ziplist解压，插入后再压缩 若压缩后的ziplist大小 - 未压缩的大小<MIN_COMPRESS_IMPROVE(默认8)，则还是用未压缩的数据。毕竟压缩后查询性能会变低。

附：list-compress-depth压缩深度配置： 0: 都不压缩，即头尾不压缩，默认值。 1: 两端各有1个节点不压缩，中间的节点压缩。 2: 两端各有2个节点不压缩，中间的节点压缩。 3: 两端各有3个节点不压缩，中间的节点压缩。 依此类推…

quicklist使用ziplist存储数据节点，那是如何避免ziplist大数据下的缺点的：

通过fill字段，即设置list-max-ziplist-size参数限制ziplist大小，避免ziplist过大产生内存碎片或锐化成一个大ziplist。 list-max-ziplist-size分正值和负值： (1)正值：每个quicklistNode节点上的ziplist长度，若配置成5，那每个节点下的ziplist最多包含5个数据项。 (2)负值：每个quicklist节点上的ziplist长度，值为-1到-5 -5: 每个节点ziplist大小不能超过64 Kb。 -4: 每个节点ziplist大小不能超过32 Kb。 -3: 每个节点ziplist大小不能超过16 Kb。 -2: 每个节点ziplist大小不能超过8 Kb。（Redis默认值） -1: 每个节点ziplist大小不能超过4 Kb

当节点ziplist大小超过list-max-ziplist-size参数限制，将新增一个quicklistNode节点插入到链表中 quicklist的一次头push操作：

skiplist

跳跃表（skiplist）是一种有序数据结构，它通过在每个节点中维持多个指向其它节点的指针，从而达到快速访问节点的目

当数据较少时，sorted set是由一个ziplist来实现的。

当数据多的时候，sorted set是用zset结构存储。

ziplist会转成zset的条件： 当sorted set中的元素个数，即(数据, score)对的数目超过128的时候，也就是ziplist数据项超过256的时候。

当sorted set中插入的任意一个数据的长度超过了64的时候。

skiplist有层级的概念，由很多层结构组成，但存在于不同层级中的同一个节点只保存一份； 每一层都是一个有序的链表； 最底层(Level 1) 的链表包含所有元素； 如果一个元素出现在 Level i 的链表中，则它在 Level i 之下的链表也都会出现； 节点只有1个后向指针存在于第一层链表，所以只有第1层链表是一个双向链表； 如图，如果要查找68这个元素，skiplist 的时间复杂度是O(4)，如果是普通有序链表，时间复杂度是O(6)。

skiplist每层之间的节点个数没有严格对应关系，通过随机层数算法，避免在新增、删除节点时重新排列。

随机算法：

intset整数集合

intset是一个整数的有序集合，使用二分查找，时间复杂度 O(lgN) 。

• intset可能会随着数据的添加而改变它的数据编码： 　　1、最开始，新创建的intset使用占内存最小的INTSET_ENC_INT16（类型为int16_t，16位，最大值32767）作为数据编码。 　　2、每添加一个新元素，则根据元素大小决定是否对数据编码进行升级（int32_t、int64_t）。
• 当新增元素比原编码最大值要大时，需要对集合进行升级，具体步骤是： 　　1、根据新元素类型，扩展整数集合底层数组的大小，并为新元素分配空间。 　 2、将旧元素转换成新的编码，并放到正确的位置，放置过程中，维持整个元素顺序都是有序的。 　　3、将新元素添加到整数集合中（保证有序）。 整数集合不支持降级操作，一旦对数组进行了升级，编码就会一直保持升级后的状态。

HyperLogLog

HyperLogLog是用来做基数统计的(一个集合中不重复的元素个数)。 其可以非常省内存的去统计各种计数，比如注册ip数、每日访问IP数、页面实时UV、在线用户数等在对准确性不是很重要的应用场景。 它是估计基数的算法，所以会有一定误差0.81%。 HperLogLog基本命令： 1 PFADD key element [element …] 添加指定元素到 HyperLogLog 中。 2 PFCOUNT key [key …] 返回给定 HyperLogLog 的基数估算值。 3 PFMERGE destkey sourcekey [sourcekey …] 将多个 HyperLogLog 合并为一个 HyperLogLog

bitmap

Redis实现的BloomFilter（布隆过滤器），bitmap并不是一种真实的数据结构，它本质上是String数据结构，只不过操作的粒度变成了位，即bit。因为String类型最大长度为512MB，所以bitmap最多可以存储2^32个bit。 命令： setbit key offset value 设置键的第offset个位的值(从0算起)，假设现在又20个用户，userid=0,5,11,15,19 的用户对网站进行了访问，那么当前 Bitmaps初始化结果如下图：

Geo

1、Geo本质是借助于Sorted Set（zset），并且使用GeoHash技术进行填充。 2、Geo数据结构可以在Redis中存储地理坐标，并且坐标有限制，规定如下： 有效的经度从-180度到180度。 有效的纬度从-85.05112878度到85.05112878度。 当坐标位置超出上述指定范围时，该命令将会返回一个错误。 3、Redis中处理这些地理位置坐标点的思想是：二维平面坐标点 --> 一维整数编码值 --> zset(score为编码值) --> zrangebyrank(获取score相近的元素)、zrangebyscore --> 通过score(整数编码值)反解坐标点 --> 附近点的地理位置坐标。

Streams

1、Redis5.0引入的全新数据结构，官方把它定义为：以更抽象的方式建模日志的数据结构，简单的说Streams就是Redis实现的内存版kafka。 2、功能有点类似于redis以前的Pub/Sub，但是也有基本的不同： streams支持多个客户端（消费者）等待数据，并且每个客户端得到的是完全相同的数据。 Pub/Sub是发送忘记的方式，并且不存储任何数据；而streams模式下，所有消息被无限期追加在streams中，除非用于显示执行删除（XDEL）。 streams支持消息持久化，可以保存到AOF和RDB中 3、使用场景：聊天室、IoT数据采集

内存分配机制

used_memory：Redis存储的所有数据所占用的内存。 used_memory_rss：Redis进程占用操作系统的内存，跟top命令返回值一致。 mem_fragmentation_ratio：内存碎片率,值=used_memory/ used_memory_rss。 值越大，内存碎片越多。 若值<1，操作系统会将部分内存分配到 磁盘（分配器释放内存，但未返还到操作系统）。 mem_allocator：使用的内存分配器，默认jemalloc，其他还有libc，tcmalloc。 maxmemory：最大内存上限，默认0 不限制。必须配置，不然超过操作系统上限， 进程会被杀掉。 maxmemory-polic：内存超过maxmemory，淘汰策略（noeviction、volatile-lru、volatile-random…）。

jemalloc分配机制：jemalloc将内存空间分为small、large、huge三个区间，每个区间再划分出小的内存块单位。 如：存储大小为130字节的对象，jemalloc会将其放入160字节的内存单元中，剩余30个字节将变成内存碎片， 不再分配给其他对象。 jemalloc保证内部碎片在20%左右，Redis内存碎片率一般在1.03左右。 4.0版本之前Redis内存碎片只有重启才清理，4.0开始可以自动清理。

使用总结

1、一定要注意设置过期时间（永久数据除外） 2、单个value值不宜过大：影响hash、zset、list等编码以及集群实际可用大小 3、值能用数字建议用数字，整数空间占用较低（当不设置maxmemory及部分淘汰策略，可以用共享变量） 4、使用zset(sorted set）时 预估数据量，skiplist消耗内存较多，容易造成大Key。 数据量较多时，建议进行数据拆分，排名靠前数据用ziplist或skiplist，排名靠后数据单独key用skiplist存储

5、使用Hash时 注意key的失效以及field中存在失效的数据，例： 用户活动奖品记录: hset record_{userId} {actId} {value }; 用户不断参与新actId活动，导致已结束活动数据无法清除 6、使用list 少量数据数据时(编码为ziplist)，建议尾插入 避免中间插入，头、尾插入速度最快 7、使用set 值可以用数字就用数字(intset编码) 8、注意大key集中到单个cluster节点，导致节点空间使用率差异较大 9、批量命令用hmset、hmget、mget等命令或pipeline管道，若查询元素过多，用scan、hscan、sscan等扫描。 10、避免频繁对value值进行变长、缩短，Redis采用很多变长的处理且不可逆，会产生内存碎片。