Redisobject 对象
对象分为键对象和值对象
键对象一般是string类型
值对象可以是string,list,set,zset,hash
q:redisobj的结构
typedef struct redisObject { //类型 unsigned type:4; //编码 unsigned encoding:4; //指向底层实现数据结构的指针 void *ptr; //引用计数,垃圾回收的时候使用int refcount;//最近被使用的时间,内存淘汰的时候用unsigned lru;
} robj;
q:数据类型,编码和数据结构之间的对应 关系?
Redis对象和数据结构的关系
键总是一个字符串对象
而值可以是五种中的一种
type 命令 得到的结果就是值的类型
可以用object encoding命令查看编码
list数据类型的编码由linkedlist和ziplist编码合并成了quicklist编码
q: 通用数据类型命令
keys * //查看当前库所有key (匹配:keys *1)exists key //判断某个key是否存在,如果键存在则返回1,不存在则返回0:type key //查看你的key是什么类型del key //删除指定的key数据,del是一个通用命令,无论值是什么数据结构类型,del命令都可以将其 删除,返回结果为成功删除键的个数,假设删除一个不存在的键,就会返回 0unlink key //根据value选择非阻塞删除,仅将keys从keyspace元数据中删除,真正的删除会在后续异步操作。expire key 10 //10秒钟:为给定的key设置过期时间ttl key //查看还有多少秒过期,-1表示永不过期,-2表示已过期select number //命令切换数据库dbsize //查看当前数据库的key的数量flushdb //清空当前库flushall //通杀全部库
命令在执行前都会判断 参数是否是自己可以接收,否则会返回错误
数据类型
string 字符串
q: 特点
其value是字符串,不过根据字符串的格式不同,又可以分为3类:
-
string:普通字符串
-
int:整数类型,可以做自增、自减操作
-
float:浮点类型,可以做自增、自减操作
q: 适用场景?
String 的常见应用场景如下:
- 常规数据(比如 session、token、序列化后的对象、图片的路径)的缓存;
- 计数比如用户单位时间的请求数(简单限流可以用到)、页面单位时间的访问数;
- 分布式锁(利用
SETNX key value
命令可以实现一个最简易的分布式锁);
q:常用命令?
set <key> <value> //添加键值对*NX:当数据库中key不存在时,可以将key-value添加数据库*XX:当数据库中key存在时,可以将key-value添加数据库,与NX参数互斥*EX:key的超时秒数*PX:key的超时毫秒数,与EX互斥get <key> //查询对应键值append <key> <value> //将给定的<value> 追加到原值的末尾,返回长度strlen <key> //获得值的长度setnx <key> <value> //只有在 key 不存在时 设置 key 的值incr <key> //将 key 中储存的数字值增1 只能对数字值操作,如果为空,新增值为1decr <key> //将 key 中储存的数字值减1 只能对数字值操作,如果为空,新增值为-1incrby / decrby <key> <步长> //将 key 中储存的数字值增减。自定义步长。mset <key1><value1><key2><value2> ..... //同时设置一个或多个 key-value对 mget <key1><key2><key3> ..... //同时获取一个或多个 value msetnx <key1><value1><key2><value2> ..... //同时设置一个或多个 key-value 对,当且仅当所有给定 key 都不存在。 原子性,有一个失败则都失败getrange <key><起始位置><结束位置> //得值的范围,类似java中的substring,前包,后包setrange <key><起始位置><value> //用 <value> 覆写<key>所储存的字符串值,从<起始位置>开始(索引从0开始)。setex <key><过期时间><value> //设置键值的同时,设置过期时间,单位秒。getset <key><value> //以新换旧,设置了新值同时获得旧值。
q:底层编码方式和数据结构?
- 当存储的是long 数字的时候,使用int编码,prt直接存储数字
不包括浮点数
- 当存储的字符串小于44个字节的时候,使用embstr编码,字符串和redisobject存储在一起
- 当存储的字符串大于44个字节的时候,使用raw编码,prt存储的是sds的地址指针
set 集合
q: 特点
-
无序
-
元素不可重复
-
查找快
-
支持交集、并集、差集等功能
q: 适用场景?
应用场景:
- 需要存放的数据不能重复的场景
- 不可重复下单
- 点赞
- 需要获取多个数据源交集、并集和差集的场景
- 共同好友(交集)、共同粉丝(交集)、共同关注(交集)、好友推荐(差集)、音乐推荐(差集)、订阅号推荐(差集+交集) 等场景。
- 需要随机获取数据源中的元素的场景
- 抽奖系统、随机点名等场景。
- 相关命令:
SPOP
(随机获取集合中的元素并移除,适合不允许重复中奖的场景)、SRANDMEMBER
(随机获取集合中的元素,适合允许重复中奖的场景)。
q:常用命令?
sadd <key><value1><value2> ..... //将一个或多个 member 元素加入到集合 key 中,已经存在的 member 元素将被忽略smembers <key> //取出该集合的所有值。sismember <key><value> //判断集合<key>是否为含有该<value>值,有1,没有0scard<key> //返回该集合的元素个数。srem <key><value1><value2> .... //删除集合中的某个元素。spop <key> //随机从该集合中吐出一个值。srandmember <key><n> //随机从该集合中取出n个值。不会从集合中删除 。smove <source><destination>value //把集合中一个值从一个集合移动到另一个集合sinter <key1><key2> //返回两个集合的交集元素。sunion <key1><key2> //返回两个集合的并集元素。sdiff <key1><key2> //返回两个集合的差集元素(key1中的,不包含key2中的)
q:底层编码方式和数据结构?
- 当存储的所有数据都是整数,元素数量不超过set-max-intset-entries时,Set会采用IntSet编码,以节省内存,底层数据结构是intset
- 当存储的所有数据不都是整数,或元素数量超过set-max-intset-entries时,set采用hashtable编码,底层是Dict中的key用来存储元素,value统一为null。
hash 哈希
q: 特点
hash也叫散列, 是一个键值对集合。
q: 适用场景?
hash特别适合用于存储对象。
q:常用命令?
hset <key><field><value> <field2><value2> //给<key>集合中的 <field>键赋值<value>hget <key1><field> //从<key1>集合<field>取出 valuehmset <key1><field1><value1><field2><value2>... //批量设置hash的值,hmset被弃用,可以用hset做到hexists<key1><field> //查看哈希表 key 中,给定域 field 是否存在。hkeys <key> //列出该hash集合的所有fieldhvals <key> //列出该hash集合的所有valuehincrby <key><field><increment> //为哈希表 key 中的域 field 的值加上增量 1 -1hsetnx <key><field><value> //将哈希表 key 中的域 field 的值设置为 value ,当且仅当域 field 不存在 .
q:底层编码方式和数据结构?
-
Hash结构默认采用ZipList编码,用以节省内存。 ZipList中相邻的两个entry 分别保存field和value;底层数据结构式ziplist
-
当数据量较大时,Hash结构会转为hashtable编码,底层数据结构是Dict,触发条件有两个:
- ZipList中的元素数量超过了hash-max-ziplist-entries(默认512)
- ZipList中的任意entry大小超过了hash-max-ziplist-value(默认64字节)
节点过多,或单个节点过大
zset/sorted set 有序集合
q: 特点
- 无重复
- 有序
每个成员都关联了一个评分(score),这个评分(score)被用来按照从最低分到最高分的方式排序集合中的成员。
集合的成员是唯一的,但是评分可以是重复了 。
q: 适用场景?
适合范围或者排序的应用场景:
- 排行榜
q:常用命令?
zadd <key><score1><value1><score2><value2>… //将一个或多个 member 元素及其 score 值加入到有序集 key 当中。zrange <key><start><stop> [WITHSCORES] //返回有序集 key 中,下标在<start><stop>之间的元素,带WITHSCORES,可以让分数一起和值返回到结果集。zrangebyscore key minmax [withscores] [limit offset count] //返回有序集 key 中,所有 score 值介于 min 和 max 之间(包括等于 min 或 max )的成员。有序集成员按 score 值递增(从小到大)次序排列。 zrevrangebyscore key maxmin [withscores] [limit offset count] //同上,改为从大到小排列。 zincrby <key><increment><value> // 为元素的score加上增量zrem <key><value> //删除该集合下,指定值的元素 zcount <key><min><max> //统计该集合,分数区间内的元素个数 zrank <key><value> //返回该值在集合中的排名,从0开始。
q:底层编码方式和数据结构?
- 当满足下面条件时,采用ziplist编码,底层数据结构是ziplist
- 元素数量小于zset_max_ziplist_entries,默认值128
- 每个元素都小于zset_max_ziplist_value字节,默认值64
ziplist本身没有排序功能,而且没有键值对的概念,因此需要有zset通过编码实现:
- ZipList是连续内存,因此score和element是紧挨在一起的两个entry, element在前,score在后
- score越小越接近队首,score越大越接近队尾,按照score值升序排列
- 否则采用zset编码,底层是zset数据结构,zset的数据结构又指向skiplist和dict
- SkipList:可以排序,并且可以同时存储score和ele值(member)
- Dict:可以键值存储,并且可以根据key找value,实现O(1)的查找
二者实际上共用对象,不会造成内存的浪费
list 列表
q: 特点
双向链表结构。既可以支持正向检索和也可以支持反向检索。
特征也与LinkedList类似:
- 单键多值
- 有序
- 元素可以重复
- 插入和删除快
- 查询速度一般
q: 适用场景?
应用场景:
- 常用来存储一个有序数据,例如:朋友圈点赞列表,评论列表等。
- 可以用来做消息队列,只是功能过于简单且存在很多缺陷,不建议这样做。
q:常用命令?
lpush/rpush <key><value1><value2><value3> //.... 从左边/右边插入一个或多个值。lpush是头插法lpop/rpop <key> //从左边/右边吐出一个值。值在键在,值光键亡。rpoplpush <key1><key2>从<key1> //列表右边吐出一个值,插到<key2>列表左边。lrange <key><start><stop> //按照索引下标获得元素(从左到右)lrange <key> 0 -1 //0左边第一个,-1右边第一个,(0 -1表示获取所有)lindex <key><index> //按照索引下标获得元素(从左到右)llen <key> //获得列表长度 linsert <key> before/after <value><newvalue> //在<value>的前面、后面插入<newvalue>插入值lrem <key><n><value> //从左边删除n个value(从左到右)lset<key><index><value> //将列表key下标为index的值替换成value
q:底层编码方式和数据结构?
- List的编码方式是quicklist,底层数据结构为快速链表quickList,quicklist的节点又指向了ziplist
Redis 3.2 之前,List 底层实现是 LinkedList 或者 ZipList。 Redis 3.2 之后,引入了 LinkedList 和 ZipList 的结合 QuickList,List 的底层实现变为 QuickList。
首先在列表元素较少的情况下会使用一块连续的内存存储,这个结构是ziplist,也即是压缩列表。(它将所有的元素紧挨着一起存储,分配的是一块连续的内存。)
当数据量比较多的时候才会改成quicklist。
因为普通的链表需要的附加指针空间太大,会比较浪费空间。比如这个列表里存的只是int类型的数据,结构上还需要两个额外的指针prev和next。
Redis将链表和ziplist结合起来组成了quicklist。也就是将多个ziplist使用双向指针串起来使用。这样既满足了快速的插入删除性能,又不会出现太大的空间冗余。
数据结构
sds 简单动态字符串
q:sds的结构
sds的结构
struct sdshdr {
//记录buf数组中已使用字节的数量
//等于SDS所保存字符串的长度
int len;
//记录buf数组中未使用字节的数量
int free;
//字节数组,用于保存字符串
char buf[];
};
q: sds和c字符串的区别
相同点:
- 都是用char数组来记录字符,最后都有一个
\0
来代表字符串结束
sds最后也用
\0
代表结束,是为了重用c语言字符串的一些函数,例如printf打印,而不用重写所有的函数
不同点
肯定是c语言字符串存在一定的缺陷,redis才会重写,那么这些既是redis和c语言字符串的不同点,也是redis sds的优点
- 常数级别获取字符串长度,sds获取字符串长度的时间复杂度是O(1),c语言是O(n),通过len的冗余存储来实现
- 杜绝缓冲区溢出,字符串在拼接之前可以做内存检查,确保空间充足,否则进行扩充;不会像c语言一样造成内存溢出
- 减少修改字符串时带来的内存重分配次数,预分配空间free,来减少内存重分配的次数,可以提升性能
- 二进制安全,c语言字符串通过
\0
空字符来标志字符串结束,因此不能包含空字符;而sds通过len来表示字符串结束,可以包含空字符,可以存储图片等二进制信息,因此是二进制安全的
q: 容量扩充机制?
如图中所示,内部为当前字符串实际分配的空间capacity一般要高于实际字符串长度len。
- 当字符串长度小于1M时,扩容都是加倍现有的空间
- 如果超过1M,扩容时一次只会多扩1M的空间。需要注意的是字符串最大长度为512M。
intset 正数集合
q: intset的结构
typedef struct intset { //编码方式 uint32_t encoding; //集合包含的元素数量 uint32_t length; //保存元素的数组 int8_t contents[];
} intset;
- 数组升序排列
- 没有重复
q: 如何升级?
当新元素很大的时候,集合要升级成更大的编码方式
升级整数集合并添加新元素共分为三步进行:
1)根据新元素的类型,扩展整数集合底层数组的空间大小,并为新元素分配空间。
2)将底层数组现有的所有元素都转换成与新元素相同的类型,并将类型转换后的元素放置到正确的位上,而且在放置元素的过程中,需要继续维持底层数组的有序性质不变。
3)将新元素添加到底层数组里面。
❑升级操作为整数集合带来了操作上的灵活性,并且尽可能地节约了内存。
❑整数集合只支持升级操作,不支持降级操作。
dictht 哈希表
typedef struct dictht { //哈希表数组 dictEntry **table; //哈希表大小 unsigned long size; //哈希表大小掩码,用于计算索引值 //总是等于size-1 unsigned long sizemask; //该哈希表已有节点的数量 unsigned long used;
} dictht;
哈希表结点
typedef struct dictEntry { //键 void *key; //值 union{ void *val; uint64_tu64; int64_ts64; } v; //指向下个哈希表节点,形成链表 struct dictEntry *next;
} dictEntry;
q:如何解决哈希冲突?
用拉链法的头插法解决哈希冲突
dict 字典
typedef struct dict { //类型特定函数 dictType *type; //私有数据 void *privdata; //哈希表 dictht ht[2]; // rehash索引 //当rehash不在进行时,值为-1 in trehashidx; /* rehashing not in progress if rehashidx == -1 */
} dict;
ht有两个,一般只使用第一个,第二个哈希表只在rehash的时候用
插入数据的时候,先计算哈希值,再计算索引值,再插入到指定位置
q : 如何rehash?
随着操作的不断执行,哈希表保存的键值对会逐渐地增多或者减少,为了让哈希表的负载因子(load factor)维持在一个合理的范围之内,当哈希表保存的键值对数量太多或者太少时,程序需要对哈希表的大小进行相应的扩展或者收缩。
扩展和收缩哈希表的工作可以通过执行rehash(重新散列)操作来完成,Redis对字典的哈希表执行rehash的步骤如下:
1)为字典的ht[1]哈希表分配空间,这个哈希表的空间大小取决于要执行的操作,以及ht[0]当前包含的键值对数量(也即是ht[0].used属性的值):
❑如果执行的是扩展操作,那么ht[1]的大小为第一个大于等于ht[0].used*2的2 n(2的n次方幂);
❑如果执行的是收缩操作,那么ht[1]的大小为第一个大于等于ht[0].used的2 n。
2)将保存在ht[0]中的所有键值对rehash到ht[1]上面:rehash指的是重新计算键的哈希值和索引值,然后将键值对放置到ht[1]哈希表的指定位置上。
3)当ht[0]包含的所有键值对都迁移到了ht[1]之后(ht[0]变为空表),释放ht[0],将ht[1]设置为ht[0],并在ht[1]新创建一个空白哈希表,为下一次rehash做准备。
为ht[1]分配空间,复制ht[0]的数据到ht[1],释放ht[0],把ht[1]设为ht[0],ht[1]创建一个空哈希表
q:什么时候rehash
哈希表的扩展与收缩
哈希表的扩展与收缩当以下条件中的任意一个被满足时,程序会自动开始对哈希表执行扩展操作:
1)服务器目前没有在执行BGSAVE命令或者BGREWRITEAOF命令,并且哈希表的负载因子大于等于1。
2)服务器目前正在执行BGSAVE命令或者BGREWRITEAOF命令,并且哈希表的负载因子大于等于5。
为什么rehash是渐进式?
如果ht[0]的数据非常多,那么把数据全部转移到ht[1]将会非常耗费时间,因此这个过程是分多次,渐进式完成的
rehashidx记录了正在转移的索引下标,当转移完成,会置为-1
因为在进行渐进式rehash的过程中,字典会同时使用ht[0]和ht[1]两个哈希表,所以在渐进式rehash进行期间,字典的删除(delete)、查找(find)、更新(update)等操作会在两个哈希表上进行。例如,要在字典里面查找一个键的话,程序会先在ht[0]里面进行查找,如果没找到的话,就会继续到ht[1]里面进行查找,诸如此类。
另外,在渐进式rehash执行期间,新添加到字典的键值对一律会被保存到ht[1]里面,而ht[0]则不再进行任何添加操作,这一措施保证了ht[0]包含的键值对数量会只减不增,并随着rehash操作的执行而最终变成空表。
ziplist 压缩列表
q: ziplist的结构?
每个压缩列表节点可以保存一个字节数组或者一个整数值
q: ziplist过大的时候有什么缺点?
当ziplist变得很⼤的时候,它有如下几个缺点:
- 每次插⼊或修改引发的realloc操作会有更⼤的概率造成内存拷贝,从而降低性能。
- ⼀旦发生内存拷贝,内存拷贝的成本也相应增加,因为要拷贝更⼤的⼀块数据。
- 当ziplist数据项过多的时候,在它上⾯查找指定的数据项就会性能变得很低,因为ziplist上的查找需要进行遍历。
skiplist 跳表
skiplist是多层级不同跨度的链表
q: skiplist的结构?
zsikpList
typedef struct zskiplist { //表头节点和表尾节点 structz skiplistNode *header, *tail; //表中节点的数量 unsigned long length; //表中层数最大的节点的层数 int level;
} zskiplist;
zskipListNode
typedef struct zskiplistNode { //层 struct zskiplistLevel { //前进指针 struct zskiplistNode *forward; //跨度 unsigned int span; } level[]; //后退指针 struct zskiplistNode *backward; //分值 double score; //成员对象 robj *obj;
} zskiplistNode;
每个结点的成员对象是唯一的,但是分值可以相同,分值相同就按照成员对象由小到大排序,整个链表都是按照分值由小到大排序
q: skiplist如何遍历?
遍历:
首先遍历高层级跨度大的指针,如果过大,就遍历下一层级
zset
q:zset的结构?
typedef struct zset { zskiplist *zsl; dict *dict;
} zset;
- SkipList:可以排序,并且可以同时存储score和ele值(member)
- Dict:可以键值存储,并且可以根据key找value,实现O(1)的查找
二者实际上共用对象,不会造成内存的浪费
quicklist 快表
q:quicklist的结构
quicklist 实际上是 zipList 和 linkedList 的混合体,它将 linkedList 按段切分,每一段使用 zipList 来紧凑存储,多个 zipList 之间使用双向指针串接起来。
typedef struct quicklist { quicklistNode *head; quicklistNode *tail; unsigned long count; /* total count of all entries in all ziplists */ unsigned long len;
} quicklist;
typedef struct quicklistNode { struct quicklistNode *prev; //上一个node节点 struct quicklistNode *next; //下一个node unsigned char *zl; //保存的数据 压缩前ziplist 压缩后压缩的数据 unsigned int sz; /* ziplist size in bytes */ unsigned int count : 16; /* count of items in ziplist */ } quicklistNode;