Redis 源码剖析与实战
蒋德钧
中科院计算所副研究员
17049 人已学习
新⼈⾸单¥59
登录后,你可以任选4讲全文学习
课程目录
已完结/共 47 讲
Redis 源码剖析与实战
15
15
1.0x
00:00/00:00
登录|注册

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

你好,我是蒋德钧。今天我们来聊聊,Redis 中是如何通过优化设计数据结构,来提升内存利用率的。
我们知道 Redis 是内存数据库,所以,高效使用内存对 Redis 的实现来说非常重要。而实际上,Redis 主要是通过两大方面的技术来提升内存使用效率的,分别是数据结构的优化设计与使用,以及内存数据按一定规则淘汰
关于内存数据按规则淘汰,这是通过 Redis 内存替换策略实现的,也就是将很少使用的数据从内存中淘汰,从而把有限的内存空间用于保存会被频繁访问的数据。这部分的设计与实现,主要和内存替换策略有关,我会在后面的缓存模块给你详细介绍。
所以这节课,我主要是带你学习 Redis 数据结构在面向内存使用效率方面的优化,其中包括两方面的设计思路:一是内存友好的数据结构设计;二是内存友好的数据使用方式
这两方面的设计思路和实现方法是具有通用性的,当你在设计系统软件时,如果需要对内存使用精打细算,以便节省内存开销,这两种设计方法和实现考虑就非常值得学习和掌握。
好,接下来,我们就先来学习下内存友好的数据结构设计。

内存友好的数据结构

首先要知道,在 Redis 中,有三种数据结构针对内存使用效率做了设计优化,分别是简单动态字符串(SDS)、压缩列表(ziplist)和整数集合(intset)。下面,我们就分别来学习一下。
确认放弃笔记?
放弃后所记笔记将不保留。
新功能上线,你的历史笔记已初始化为私密笔记,是否一键批量公开?
批量公开的笔记不会为你同步至部落
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线
笔记
复制
AI
  • 深入了解
  • 翻译
    • 英语
    • 中文简体
    • 中文繁体
    • 法语
    • 德语
    • 日语
    • 韩语
    • 俄语
    • 西班牙语
    • 阿拉伯语
  • 解释
  • 总结
仅可试看部分内容,如需阅读全部内容,请付费购买文章所属专栏
《Redis 源码剖析与实战》
新⼈⾸单¥59
立即购买
登录 后留言

全部留言(17)

  • 最新
  • 精选
  • Kaito
    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 字节。
    13
    90
  • Darren
    Kaito大佬描述的已经很详细了,44是因为 N = 64 - 16(redisObject) - 3(sdshr8) - 1(\0), N = 44 字节。那么为什么是64减呢,为什么不是别的,因为在目前的x86体系下,一般的缓存行大小是64字节,redis为了一次能加载完成,因此采用64自己作为embstr类型(保存redisObject)的最大长度。
    65
  • 曾轼麟
    先回答老师的问题:为什么嵌入式字符串是以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中的字节大小,从而带来性能开销,当然这种情况比较极端基本上不会触发。
    17
  • 政由葛氏
    44字节是因为加上sds首部和redisobject后,大小为64字节,正好是CPU Cache Line的大小,CPU访问内存读取数据时以cache line为单位,一次读取64字节的数据,如果整个结构体起始地址64字节对齐,一次内存IO就可以读取全部数据
    4
  • 可怜大灰狼
    原先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.
    3
    3
  • 阿梵杰~
    而 sh+1 表示把内存地址从 sh 起始地址开始移动一定的大小,移动的距离等于 sdshdr8 结构体的大小。 o->ptr = sh+1; 【请教】为啥 +1 移动的距离就等于 sdshdr8 结构体的大小呢? 有大佬赐教下吗 ??
    4
    1
  • Geek_d8f539
    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]; };
收起评论
显示
设置
留言
17
收藏
沉浸
阅读
分享
手机端
快捷键
回顶部