内容简介:学习完《redis设计与实现》前面关于数据结构与对象的章节,以上问题都能得到解答。你也能了解到redis作者如此的煞费苦心设计了这么多丰富的数据结构,目的就是优化内存。学完这些内容,在使用redis的过程中,也会合理的使用以适应它内部的特点。当然新版本的redis支持了更多更丰富的特性,该书基于redis3版本,还没有涉及到那些内容。位于adlist.h文件位于dict.h文件
- redis性能为什么这么出色?它与其他缓存中间件有什么区别?
- redis底层使用了哪些数据结构支撑它如此高效的性能?
- 内部丰富的数据类型底层为什么都使用至少两种数据结构实现?分别是什么?
- 如果合理的使用 redis 才能发挥它最大的优势?
学习完《redis设计与实现》前面关于数据结构与对象的章节,以上问题都能得到解答。你也能了解到redis作者如此的煞费苦心设计了这么多丰富的数据结构,目的就是优化内存。学完这些内容,在使用redis的过程中,也会合理的使用以适应它内部的特点。当然新版本的redis支持了更多更丰富的特性,该书基于redis3版本,还没有涉及到那些内容。
概述
特点
- c语言开发,性能出色,纯内存操作,每秒可处理超过10w读写(QPS)
- 多种数据结构,单个最大限制可到1GB(memcached只支持字符串,最大1M)
- 受物理内存限制,不能作海量数据的读写。适用于较小数据量的高性能操作和运算上
- 支持事务,持久化
- 单线程模型(memcached是多线程)
支持的数据类型
- Sring
- List
- Set
- SortedSet
- hash
- Bitmap
- Hyperloglogs
- Geo
- pub/sub
redis为什么这么快
- 纯内存操作,没有磁盘io
- 单线程处理请求,没有线程切换开销和竞争条件,也不存在加锁问题
- 多路复用模型epoll,非阻塞io(多路:多个网络连接;复用:复用同一个线程) 多路复用技术可以让单个线程高效的处理多个连接请求
- 数据结构简单,对数据操作也简单。还做了自己的数据结构优化
redis为什么是单线程的
- 单线程已经很快了,减少多线程带来的网络开销,锁操作
- 后续的4.0版本在考虑多线程
- 单线程是指处理网络请求的时候只有一个线程,并不是redis-server只有一个线程在工作。持久化的时候,就是通过fork一个子线程来执行。
- 缺点:耗时的命令会导致并发的下降,比如keys *
redis的回收策略
- volatile-lru:从过期的数据集 server.db[i].expires中挑选最近最少使用的数据
- volatile-ttl:从过期的数据集 server.db[i].expires中挑选将要过期的数据淘汰
- volatile-random: server.db[i].expires中挑选任意数据淘汰
- allkeys-lru: 从数据集(server.db[i].dict)中挑选最近最少使用的数据淘汰
- allkeys-random:从数据集(server.db[i].dict)中任意选择数据淘汰
- no-enviction(驱逐):禁止驱逐数据
使用注意
- redis单线程无法发挥多核cpu性能,可以通过单机开多个redis实例来完善
- redis实现分布式锁:先用setnx(如果不存在才设置)争抢锁,抢到后,expire设置过期时间,防止忘记释放。
- redis实现一对多消息订阅:sub/pub数据结构
- redis实现延时消息队列:zadd时间戳作为score 消费的时候根据时间戳+延时时间做查询操作。
各大版本介绍
redis5版本新增功能:
- zpopmax zpopmin以及阻塞变种:返回集合中给定分值最大最小的数据数量
reids4版本新增功能:
- 模块功能,提供类似于插件的方式,自己开发一个.so模块,并加装 作者本人提供了一个神经网络的module。 可到redis-modules-hub上查看更多的module 模块功能使得用户可以将 Redis 用作基础设施, 并在上面构建更多功能, 这给 Redis 带来了无数新的可能性。
- PSYNC:解决了旧版本的 Redis 在复制时的一些不够优化的地方
- 缓存清理策略优化 新增last frequently used 对已有策略进行优化
- 非阻塞DEL FLUSHDB FLUSHALL 解决了之前执行这些命令的时候导致阻塞的问题 Flushdb async, flushall async, unlink(替代del)
- 添加了swapdb:交换数据库
- 混合RDB-AOF的持久化格式
- 添加内存使用情况命令:MEMORY
数据结构
- redis里面每个键值对都是由对象组成的
- 键总是一个字符串对象,
- 值则可以是以下对象的一种:
- 字符串对象
- 列表对象
- 哈希对象
- 集合对象
- 有序结合对象
简单动态字符串SDS
数据结构
struct sdshdr { uint8_t len; /* used,使用的字节数 */ uint8_t alloc; /* excluding the header and null terminator,预分配总字节数,不包括结束符\0的长度 */ unsigned char flags; /* 3 lsb of type, 5 unused bits */ char buf[]; /*c风格的字符,包括结束符\0*/ }; 复制代码
- 位于sds.h文件
- SDS遵循C字符串以\0结尾的惯例,存储在buf中(不同于nginx的底层实现,nginx实现时不保存最后一个\0)
- 但是不计算最后一个字符的长度到len中
- 保留c风格buf的好处是可以重用一部分c函数库的函数
分配和释放策略
空间预分配
- 用于优化SDS字符串增长操作,以减少连续执行增长操作所需的内存重分配次数
- 扩展SDS空间时,先检查未使用的空间是否足够,如果足够直接使用,如果不够,不仅分配够用,还预分配一些空间
- 预分配策略:
- 修改后的SDS长度(len的值)< 1MB,预分配同样len大小的空间
- 修改后的SDS长度(len的值)>= 1MB,预分配1MB大小的空间
惰性空间释放
- 用于优化SDS字符缩短操作
- 缩短SDS空间时,并不立即进行内存重分配释放空间,而是记录free的字节数
- SDS提供相应api,有需要时真正释放空间
比C字符串的优势
- 获取字符串的长度时间复杂度由O(N)降到O(1)
- 避免缓冲区溢出
- 减少修改字符串时带来的内存重分配次数。内存分配会涉及复杂算法,且可能需要系统调用,非常耗时。
- 二进制安全:c语言的结束符限制了它只能保存文本数据,不能保存图片,音频等二进制数据
链表
数据结构
位于adlist.h文件
typedef struct listNode { struct listNode *prev; // 前置节点 struct listNode *next; // 后置节点 void *value;//节点值 } listNode; typedef struct list { listNode *head; // 表头节点 listNode *tail; // 表尾节点 void *(*dup)(void *ptr); // 节点值复制函数 void (*free)(void *ptr); // 节点值释放函数 int (*match)(void *ptr, void *key); // 节点值对比函数 unsigned long len; // 节点数量 } list; 复制代码
特点
- 双端队列,可以获取某个节点前置节点和后置节点,复杂度为O(1)
- 无环
- 获取表头和表尾复杂度为O(1)
- 带长度,获取链表长度复杂度为O(1)
- 多态:使用void*保存节点值,可保存不同类型的值
字典
数据结构
位于dict.h文件
哈希表
// 哈希表 typedef struct dictht { dictEntry **table; // 一个数组,数组中每个元素都是指向dictEntry结构的指针 unsigned long size; // table数组的大小 unsigned long sizemask; // 值总数size-1 unsigned long used; // 哈希表目前已有节点(键值对)的数量 } dictht; 复制代码
哈希节点
// 每个dictEntry都保存着一个键值对,表示哈希表节点 typedef struct dictEntry { void *key; // 键值对的键 // 键值对的值,可以是指针,整形,浮点型 union { void *val; uint64_t u64; int64_t s64; double d; } v; struct dictEntry *next; // 哈希表节点指针,用于解决键冲突问题 } dictEntry; 复制代码
字典类型
每个字典类型保存一簇用于操作特定类型键值对的函数
typedef struct dictType { // 计算哈希值的函数 uint64_t (*hashFunction)(const void *key); // 复制键的函数 void *(*keyDup)(void *privdata, const void *key); // 复制值的函数 void *(*valDup)(void *privdata, const void *obj); // 对比键的函数 int (*keyCompare)(void *privdata, const void *key1, const void *key2); // 销毁键的函数 void (*keyDestructor)(void *privdata, void *key); // 销毁值的函数 void (*valDestructor)(void *privdata, void *obj); } dictType; 复制代码
字典
// 字典 typedef struct dict { dictType *type; // 不同键值对类型对应的操作函数 void *privdata; // 需要传递给对应函数的参数 dictht ht[2]; // ht[0]用于存放数据,ht[1]在进行rehash时使用 long rehashidx; /* rehashing not in progress if rehashidx == -1,目前rehash的进度*/ unsigned long iterators; /* number of iterators currently running */ } dict; 复制代码
哈希算法
- redis使用MurmurHash2算法计算键的hash值
- 哈希值与sizemask取或,得到哈希索引
- 哈希冲突(两个或以上数量键被分配到哈希表数组同一个索引上):链地址法解决冲突
rehash
- 对哈希表进行扩展或收缩,以使哈希表的负载因子维持在一个合理范围之内
- 负载因子 = 保存的节点数(used)/ 哈希表大小(size)
rehash步骤包括
- 为字典的ht[1]哈希表分配空间,大小取决于要执行的操作以及ht[0]当前包含的键值对数量
- 扩展操作:ht[1]大小为第一个大于等于ht[0].used乘以2的2的n次幂
- 收缩操作:ht[1]大小为第一个大于等于ht[0].used的2的n次幂
- 将保存在ht[0]的所有键值对rehash到ht[1]上面:重新计算键的哈希值和索引值
- 当所有ht[0]的键值对都迁移到ht[1]之后,释放ht[0],将ht[1]置为ht[0],并新建一个恐怖hash作为ht[1]
自动扩展的条件
- 服务器没有执行BGSave命令或GBRewriteAOF命令,并且哈希表的负载因子 >= 1
- 服务器正在执行BGSave命令或GBRewriteAOF命令,并且哈希表的负载因子 >= 5
- BGSave命令或GBRewriteAOF命令时,服务器需要创建当前服务器进程的子进程,会耗费内存,提高负载因子避免写入,节约内存
自动收缩的条件
- 哈希表负载因子小于0.1时,自动收缩
渐进式rehash
- ht[0]数据重新索引到ht[1]不是一次性集中完成的,而是多次渐进式完成(避免hash表过大时导致性能问题)
渐进式rehash详细步骤
- 为ht[1]分配空间,让自动同时持有两个哈希表
- 字典中rehashidx置为0,表示开始执行rehash(默认值为-1)
- rehash期间,每次对字典执行操作时,顺带将ht[0]哈希表在rehashidx索引上的所有键值对rehash到ht[1]
- 全部rehash完毕时,rehashidx设为-1
注意点
- rehash的所有操作会在两个哈希表进行
- 新增加的值一律放入ht[1],保证数据只会减少不会增加
跳跃表
- 跳跃表是一种有序数据结构,通过在每个节点维持多个指向其他节点的指针,达到快速访问节点的目的
- 时间复杂度:最坏O(N),平均O(logN)
- 大部分情况下,效率可与平衡树媲美,不过比平衡树实现简单
- 有序集合的底层实现之一
数据结构
位于server.h文件中
// 跳跃表节点 typedef struct zskiplistNode { sds ele; // 成员对象 double score; // 分值,从小到大排序 struct zskiplistNode *backward; // 后退指针,从表尾向表头遍历时使用 struct zskiplistLevel { struct zskiplistNode *forward; // 前进指针 unsigned long span; // 跨度,记录两个节点之间的距离 } level[]; // 层,是一个数组 } zskiplistNode; // 跳跃表相关信息 typedef struct zskiplist { struct zskiplistNode *header, *tail; // 表头和表尾 unsigned long length; // 跳跃表长度(包含节点的数量) int level; // 跳跃表内层数最大那个节点的层数(不包括表头节点层数) } zskiplist; 复制代码
- level数组的大小在每次新建跳跃表的时候,随机生成,大小介于1-32直接
- 遍历操作只使用前进指针,跨度用来计算排位(rank),沿途访问的所有层跨度加起来就是节点的排位
- 多个节点可以包含相同的分支,但每个节点成员对象是唯一的
整数集合
- intset是集合键的底层实现之一
- 当一个集合只包含整数值原素,且数量不多时,会使用整数集合作为底层实现
数据结构
位于intset.h文件
typedef struct intset { uint32_t encoding; // 编码方式 uint32_t length; // 长度 int8_t contents[]; // 内容,数组内容类型取决于encoding属性,并不是int8_t。按照大小排序,没有重复 } intset; 复制代码
升级
- 当我们要将一个新元素添加到整数集合里,并且新元素的类型比整数集合现有所有的元素类型都要长时,集合要先进行升级才能添加新数据
- 升级步骤包括三步:
- 根据类型,扩展大小,分配空间
- 将底层数组数据都转换成新的类型,并反倒正确位置
- 新元素添加到底层数组里面
- 添加元素可能导致升级,所以添加新元素的世界复杂度为O(N)
- 不支持降级,升级后将一直保持新的数据类型
升级的好处
- 提高灵活性
- 节约内存
压缩列表
- ziplist是列表键和哈希键的底层实现之一
- redis为了节约内存而开发的顺序型数据结构
- 当列表键只包含少量列表项,且每个列表项要么是小整数,要么是短字符串,就使用ziplist作为列表键底层实现
- 压缩列表遍历时,从表位向表头回溯遍历
- ziplist没有专门的struct来表示
压缩列表的构成
属性 | 类型 | 长度 | 用途 |
---|---|---|---|
zlbytes | uint32_t | 4字节 | 整个压缩列表占用的内存字节数 |
zltail | uint32_t | 4字节 | 表尾节点距离压缩列表起始地址有多少字节,无需遍历就可得到表尾节点 |
zllen | uint16_t | 2字节 | 节点数量,小于65535时是实际值,超过时需要遍历才能算出 |
entryN | 列表节点 | 不定 | 包含的各个节点 |
zlend | uint8_t | 1字节 | 特殊值0xFF,末端标记 |
压缩列表节点的构成
- previos_entry_length:前一个节点的长度,用于从表尾向表头回溯用
- 如果前面节点长度小于254字节,preivos_entry_length用1字节表示
- 如果前面节点长度小于254字节,preivos_entry_length用5字节表示,第1个字节为0xFE(254),后面四个字节表示实际长度
- encoding:记录content的类型以及长度,encoding分为两部分,高两位和余下的位数,最高两位的取值有以下情况:
最高两位取值 表示是数据类型 encoding字节数 余下的bit数 最大范围 00 字符数组 一个字节 6bit 63位 01 字符数组 两个字节 14bit 2^14-1 10 字符数组 五个字节 4*8,第一个字节余下的6bit留空 2^32-1位 11 整数 1个字节 000000 int16_t类型整数 11 整数 1个字节 010000 int32_t类型整数 11 整数 1个字节 100000 int64_t类型整数 11 整数 1个字节 110000 24位有符号整数 11 整数 1个字节 111110 8位有符号整数 11 整数 1个字节 xxxxxx 没有content,xxxx本身就表示了0-12的整数 - content:保存节点的值
连锁更新
- 连续多个节点大小介于254左右的节点,因扩展导致连续内存分配的情况。不过在时间情况下,这种情况比较少。
对象
概述
- redis并没有直接使用前面的数据结构来实现键值对的数据库,而是基于数据结构创建了一个对象系统,每种对象都用到前面至少一种数据结构
- 每个对象都由一个redisObject结构来表示
//server.h typedef struct redisObject { unsigned type:4; //类型 unsigned encoding:4; // 编码 // 对象最后一个被命令程序访问的时间 unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or * LFU data (least significant 8 bits frequency * and most significant 16 bits access time). */ int refcount; // 引用计数 void *ptr; // 指向底层的数据结构指针 } robj; 复制代码
使用对象的好处
- 在执行命令之前,根据对象类型判断一个对象是否可以执行给定的命令
- 针对不同厂家,Wie对象设置多种不同的数据结构实现,从而优化效率
- 实现了基于引用计数的内存回收机制,不再使用的对象,内存会自动释放
- 引用计数实现对象共享机制,多个数据库共享同一个对象以节约内存
- 对象带有时间时间积累信息,用于计算空转时间
redis中的对象
- 字符串对象
- 列表对象
- 哈希对象
- 集合对象
- 有序结合对象
对象的类型与编码
对象的类型
对象 | 对象type属性 | type命令的输出 |
---|---|---|
字符串对象 | REDIS_STRING | string |
列表对象 | REDIS_LIST | list |
哈希对象 | REDIS_HASH | hash |
集合对象 | REDIS_SET | set |
有序集合对象 | REDIS_ZSET | zset |
对象的编码
- 编码决定了ptr指向的数据类型,表明使用什么数据类型作为底层实现
- 每种类型对象至少使用两种不同的编码
- 通过编码,redis可以根据不同场景设定不同编码,极大提高灵活性和效率
编码常量 | 对应的数据结构 | OBJECT ENCODING命令输出 |
---|---|---|
REDIS_ENCODING_INT | long类型的整数 | “int” |
REDIS_ENCODING_EMBSTR | embstr编码的简单动态字符串 | “embstr” |
REDIS_ENCODING_RAW | 简单动态字符串 | “raw” |
REDIS_ENCODING_HT | 字典 | “hashtable” |
REDIS_ENCODING_LINKEDLIST | 双端链表 | “linkedlist” |
REDIS_ENCODING_ZIPLIST | 压缩列表 | “ziplist” |
REDIS_ENCODING_INTSET | 整数集合 | “intset” |
REDIS_ENCODING_SKIPLIST | 跳跃表和字典 | “skiplist” |
字符串对象
- 字符串对象的编码可以是
- int
- raw
- embstr
- 浮点数在redis中也是作为字符串对象保存,涉及计算时,先转回浮点数。
字符串对象内容 | 长度 | 编码类型 |
---|---|---|
整数值 | - | int |
字符串值 | 小于32字节 | embstr |
字符串值 | 大于32字节 | raw |
embstr编码是专门用于保存短字符串的一种优化编码方式。这种编码和raw编码一样,都使用redisObject结构和sdshdr结构来表示对象。区别在于:
- raw编码调用两次内存分配函数来分别创建redisObject和sdrhdr结构
- embstr则调用一次内存分配函数来创建一块连续空间,里面包括redisObject和sdrhdr
编码转换
int编码和embstr编码的对象满足条件时会自动转换为raw编码的字符串对象
- int编码对象,执行命令导致对象不再是整数时,会转换为raw对象
- embstr编码没有相应执行函数,是只读编码。涉及修改时,会转换为raw对象
字符串命令
redis中所有键都是字符串对象,所以所有对于键的命令都是针对字符串键来构建的
- set
- get
- append
- incrbyfloat
- incrby
- decrby
- strlen
- strrange
- getrange
列表对象
- 列表对象的编码可以是
- ziplist
- linkedlist
编码转换
使用ziplist编码的两个条件如下,不满足的都用linkedlist编码(这两个条件可以在配置文件中修改):
- 保存的所有字符串元素的长度都小于64字节
- 列表的元素数量小于512个
列表命令
- lpush
- rpush
- lpop
- rpop
- lindex
- llen
- linsert
- lrem
- ltrim
- lset
哈希对象
哈希对象的编码可以是
- ziplist
- hashtable
编码转换
- 使用ziplist需要满足两个条件,不满足则都使用hashtable(这两个条件可以在配置文件中修改)
- 所有键值对的键和值的字符串长度都小于64字节
- 键值对数量小于512个
哈希命令
- hset
- hget
- hexists
- hdel
- hlen
- hgetall
集合对象
集合对象的编码可以是:
- intset:所有元素保存在整数集合里
- hashtale:字典的值为null
编码转换
集合使用intset需要满足两个条件,不满足时使用hashtable(参数可通过配置文件修改)
- 保存的所有元素都是整数值
- 元素数量不超过512个
集合命令
- sadd
- scard
- sismember
- smembers
- srandmember
- spop
- srem
有序结合对象
有序集合的编码可以是
- ziplist:每个元素使用两个紧挨在一起的节点表示,第一个表示成员,第二个表示分值。分值小的靠近表头,分值大的靠近表尾
- skiplist:使用zset作为底层实现,zset结构同时包含了字典和跳跃表,分别用于根据key查找score和分值 排序 或范围查询
// 两种数据结构通过指针共享元素成员和分值,不会浪费内存 typedef struct zset { zskplist *zsl; //跳跃表,方便zrank,zrange dict *dict; //字典,方便zscore }zset; 复制代码
编码转换
当满足以下两个条件时,使用ziplist编码,否则使用skiplist(可通过配置文件修改)
- 保存的元素数量少于128个
- 成员长度小于64字节
有序集合命令
- zadd
- zcard
- zcount
- zrange
- zrevrange
- zrem
- zscore
类型检查和命令多态
redis的命令可以分为两大类:
- 可以对任意类型的键执行,如
- del
- expire
- rename
- type
- object
- 只能对特定类型的键执行,比如前面各种对象的命令。是通过redisObject的type属性实现的
内存回收
redis通过对象的refcount属性记录对象引用计数信息,适当的时候自动释放对象进行内存回收
对象共享
- 包含同样数值的对象,键的值指向同一个对象,以节约内存。
- redis在初始化时,创建一万个字符串对象,包含从0-9999的所有整数值,当需要用到这些值时,服务器会共享这些对象,而不是新建对象
- 数量可通过配置文件修改
- 目前不包含字符串的对象共享,因为要比对字符串是否相同本身就会造成性能问题
对象空转时长
- 空转时长=现在时间-redisObject.lru,lru记录对象最后一次被访问的时间
- 当redis配置了最大内存(maxmemory)时,回收算法判断内存超过该值时,空转时长高的会优先被释放以回收内存
参考命令
# 设置字符串 set msg "hello world" rpush numbers 1 2 3 4 5 llen numbers lrange numbers 0 5 # 获取键值使用的底层数据结构 object encoding numbers # 查看对象的引用计数值 object refcount numbers # 对象空转时长: value=now-object.lru object idletime numbers 复制代码
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
猜你喜欢:- 十二张图带你了解 Redis 的数据结构和对象系统
- 简读笔记_Redis设计与实现_第一章_数据结构与对象
- Python cookbook(数据结构与算法)实现对不原生支持比较操作的对象排序算法示例
- 数据结构 – 用于构建文件系统的数据结构?
- 荐 用Python解决数据结构与算法问题(三):线性数据结构之栈
- 数据库索引背后的数据结构
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。