redis中的数据结构和编码详解
typedef struct redisObject {
unsigned type:4; /* 对象类型 */
unsigned encoding:4; /* 内部编码 */
unsigned lru:LRU_BITS; /* lru time (relative to server.lruclock) */
int refcount; /* 引用计数器,内存回收机制就是基于该值实现的 */
void *ptr; /* 若要存储的是整数值则直接存储数据,否则表示指向数据的指针 */
} robj;
类型type:
说明:查看当前键的类型:type key
#define OBJ_STRING 0 /*字符串对象*/
#define OBJ_LIST 1 /*列表对象*/
#define OBJ_SET 2 /*集合对象*/
#define OBJ_ZSET 3 /*有序集合对象*/
#define OBJ_HASH 4 /*哈希对象*/
编码encoding;
说明:查看当前键的编码:object encoding key
#define OBJ_ENCODING_RAW 0 /*Raw representation 简单动态字符串*/
#define OBJ_ENCODING_INT 1 /*Encoded as integer long long类型整数*/
#define OBJ_ENCODING_HT 2 /* Encoded as hash table 字典*/
#define OBJ_ENCODING_ZIPMAP 3 /* Encoded as zipmap 压缩map*/
#define OBJ_ENCODING_LINKEDLIST 4 /* Encoded as regular linked list 双端链表*/
#define OBJ_ENCODING_ZIPLIST 5 /* Encoded as ziplist 压缩列表*/
#define OBJ_ENCODING_INTSET 6 /* Encoded as intset 整数集合*/
#define OBJ_ENCODING_SKIPLIST 7 /* Encoded as skiplist 跳跃表*/
#define OBJ_ENCODING_EMBSTR 8 /* Embedded sds string encoding embstr编码的简单动态字符串*/
#define OBJ_ENCODING_QUICKLIST 9 /* 基于压缩列表的双端列表实现的 快速表*/
最后被访问的时间lru:
概念:记录对象最后一次被访问的时间。
说明:
1 查看当前键的空闲时间(该命令不会更新lru字段);object idletime key 。可以通过scan + object idletime key 来收集长时间未被访问的数据,然后手动清理。
2 当配置了maxmemory和maxmemory-policy=volatile-lru或者allkeys-lru时,若内存超过了上限(maxmemory)后,则优先回收长时间没有被访问的数据,从而回收内存。
引用计数器refcount:
概念:记录当前对象被引用的次数,当refcount=0时,可以安全回收当前对象空间。
说明:获取当前对象引用:object refcount key
类型对应的编码:
字符串:
int:存放整形值的字符串。
embstr:存放字符的短字符串(大小不超过44个字节)。
raw:存放字符的长字符串(大小不超过44个字节)。
embstr和raw的比较:
raw调用2次内存分配函数,释放时当然也需要释放两次。
embstr调用1次内存分配函数,分配一块连续的内存,释放时只需释放一次。
列表(list):
压缩列表(ziplist):
结构:所有数据都是采用线性连续的内存结构(大致可类比数组),目的是为了减少内存的占用,追求空间和时间的平衡。
1 以O(1)时间复杂度入队和出队。
2 读写操作涉及复杂的指针移动,最坏时间复杂度为O(n2),故列表的元素不易太多。
3 新增删除操作涉及内存重新分配,加大了操作的复杂性。
优点:占用内存较少,且占用的是一块连续的内存,故加载的速度相对更快一些。
缺点:当元素的个数较大时,访问元素的时间较长。
应用:
适合存储小对象和长度有限(即使O(n2)的复杂度也不会太大)的数据。
当元素个数小于list-max-ziplist-entries(默认512) 且 所有元素值的大小都小于list-max-ziplist-value(默认64字节)时,使用ziplist作为列表的内部实现。
双端链表(linkedlist):
优点:元素的个数较多时,访问元素的时间比压缩列表更快一些。
缺点:因为是双向链表,故维护了前置指针、后置指针等结构,占用了更多的内存,且内存不是连续的,容易产生内存碎片。
说明:当无法满足ziplist的条件时,使用linkedlist作为列表的内部实现。
应用:当列表对象元素较多时,压缩列表就会转化为更适合存储大量元素的双端链表。
注意:只能小内存编码向大内存编码转换。(若当元素增删频繁时,数据向压缩编码转换是非常消耗CPU的,得不偿失)
快速列表(quicklist):
结构:一个双向链表,链表的每一个节点都是一个ziplist,故quicklist结合了双向链表和压缩列表的优点。
Redis3.2开始,列表采用quicklist进行编码。
哈希(hash):
压缩列表(ziplist):
应用:当元素个数小于hash-max-ziplist-entries(默认512) 且 所有元素value的大小都小于hash-max-ziplist-value(默认64字节)时,使用ziplist作为哈希的内部实现。
哈希表(hashtable):
优点:读写时间复杂度O(1)
缺点:占用内存较多。
应用:当无法满足ziplist的条件时,hashtable作为哈希的内部实现。
hash算法:与传统hash算法类似,根据key计算得到在哈希表中的位置,采用单链表解决冲突,达到加载因子时进行扩展,进而引发重哈希。
rehash:采用增量式重哈希:
概念:在扩容时不会一次性对所有的key进行rehash,而是将key的rehash操作分散延迟到其它操作(哈希表的查找、更新、删除)中。
优点:避免由于大量的key在同一时间段进行rehash操作导致服务短暂无响应的问题。
过程:在增量式的rehash过程中,会使用到两张哈希表:
查找:先从老表中查找,再从新表中查找,此外还会对一些key进行rehash操作。
新增:新增的键值对添加到新表中。
集合(set):
整数集合(intset):
结构:有序、不重复的整数集。
1 查找时间复杂度为O(logn)
2 插入时间复杂度为O(n)
优点:占用的内存远小于hashtable,
应用:当元素都是整数 且 元素个数小于set-max-intset-entries(默认512)时,使用intset作为集合的内部实现。
哈希表(hashtable):当无法满足intset的条件时,使用hashtable作为集合的内部实现。
有序集合(zset):
说明:redis给有序集合中的每个元素设置一个分数(score)作为排序的依据。
压缩列表(ziplist):
应用:当元素个数小于zset-max-ziplist-entries(默认128个) 且 每个元素的值都小于zset-max-ziplist-value(默认64字节)时,使用ziplist作为有序集合的内部实现。
跳跃表(skiplist):
结构:跳跃表通过在每个节点中(基于层和跨度等)维持多个指向其它节点的指针来实现快速访问。
查找时间复杂度平均O(logn)、最坏O(n)。
应用:当不满足ziplist条件时,使用skiplist作为内部实现。
内存优化:
场景:有海量key和value都比较小的数据,在redis中如何存储才更省内存。
原理:通过大幅减少key的数量来降低内存的消耗。
实现:在客户端通过分组将海量的key根据一定的策略映射到一组hash对象中,由于value较小,故hash类型的对象会使用占用内存较小的ziplist编码。
eg:如存在100万个键,可以映射到1000个hash中,每个hash保存1000个元素。
本篇文章到此结束,如果您有相关技术方面疑问可以联系我们技术人员远程解决,感谢大家支持本站!
我想要获取技术服务或软件
服务范围:MySQL、ORACLE、SQLSERVER、MongoDB、PostgreSQL 、程序问题
服务方式:远程服务、电话支持、现场服务,沟通指定方式服务
技术标签:数据恢复、安装配置、数据迁移、集群容灾、异常处理、其它问题
本站部分文章参考或来源于网络,如有侵权请联系站长。
数据库远程运维 redis中的数据结构和编码详解
相关文章
- Redis精彩起源:从中文编码到完美运行(redis中文)
- 深入了解:Redis:详解当下最热门的数据结构(redis到底是什么)
- 利用Redis灵活保存复杂数据结构(redis保存复杂对象)
- 深入理解 Redis 缓存设置(redis设置缓存)
- 掌握Redis中的编码格式规则(redis编码格式)
- 深入了解Redis编码设置,提升数据存储效率(redis编码设置)
- 微博与微信探索Redis架构(微博与微信redis架构)
- 调整使用Redis优化库存数据结构(库存数据结构redis)
- 优惠券节用Redis轻松领取优惠(领取优惠券redis)
- 一线大厂精心打造的Redis架构(一线大厂redis架构)
- ZK灰心丧气Redis出错突崩(zk因为redis报错)
- Redis的面试题研究其数据结构(redis面试题数据结构)
- Redis集群动态分片扩容实操指南(redis集群分片扩容)
- 利用Redis构建高效的键值对数据结构(redis键值对数据结构)
- Redis 键解开中文编码之谜(redis 键 中文)
- Redis重入锁实现原理及其优化(redis重入锁实现机制)
- 利用Redis连接池实现高效序列化(redis连接池序列化)
- 研究Redis设计与数据结构的奥秘(redis设计与数据结构)
- 架构Redis在分布式架构中的订阅发布模式(redis订阅发布分布式)
- 借助Redis,助力规范编码开发(redis规范开发)
- Redis编码规范性提升应用性能(redis编码规范)