|
|
51CTO旗下网站
|
|
移动端

Redis概念以及底层数据结构

Redis是一个开源的使用ANSI C语言编写、遵守BSD协议、支持网络、可基于内存亦可持久化的日志型、Key-Value数据库,并提供多种语言的API。

作者:佚名来源:segmentfault|2019-04-17 15:35

Redis 简介

REmote DIctionary Server(Redis) 是一个由SalvatoreSanfilippo写的key-value存储白菜送彩金大全。

Redis是一个开源的使用ANSI C语言编写、遵守BSD协议、支持网络、可基于内存亦可持久化的日志型、Key-Value数据库,并提供多种语言的API。

它通常被称为数据结构服务器,因为值(value)可以是字符串(String), 哈希(Map), 列表(list), 集合(sets) 和有序集合(sorted sets)等类型。

Redis特点

Redis 是完全开源免费的,遵守BSD协议,是一个高性能的key-value数据库。

Redis 与其他 key - value 缓存产品有以下三个特点:

  • Redis支持数据的持久化,可以将内存中的数据保持在磁盘中,重启的时候可以再次加载进行使用。
  • Redis不仅仅支持简单的key-value类型的数据,同时还提供list,set,zset,hash等数据结构的存储。
  • Redis支持数据的备份,即master-slave模式的数据备份。

Redis 优势

性能极高 – Redis能读的速度是110000次/s,写的速度是81000次/s 。

丰富的数据类型 – Redis支持 Strings, Lists, Hashes, Sets 及 Ordered Sets 数据类型操作。

原子 – Redis的所有操作都是原子性的,同时Redis还支持对几个操作全并后的原子性执行。

丰富的特性 – Redis 还支持 publish/subscribe, 队列,key 过期等等特性。

Redis对象类型简介

Redis是一种key/value型数据库,其中,每个key和value都是使用对象表示的。

比如,我们执行以下代码:

  1. redis> SET message "hello redis" 

其中的key是message,是一个包含了字符串"message"的对象。而value是一个包含了"hello redis"的对象。

Redis共有五种对象的类型,分别是:

类型常量 对象的名称
REDIS_STRING 字符串对象
REDIS_LIST 列表对象
REDIS_HASH 哈希对象
REDIS_SET 集合对象
REDIS_ZSET 有序集合对象

Redis中的一个对象的结构体表示如下:

  1. typedef struct redisObject {  
  2. // 类型  
  3. unsigned type:4;  
  4. // 编码方式  
  5. unsigned encoding: 4;  
  6. // 引用计数  
  7. int refcount;  
  8. // 指向对象的值  
  9. void *ptr;  
  10. } robj;  

type表示了该对象的对象类型,即上面五个中的一个。但为了提高存储效率与程序执行效率,每种对象的底层数据结构实现都可能不止一种。encoding就表示了对象底层所使用的编码。

  • Redis对象底层数据结构
编码常量 编码所对应的底层数据结构
REDIS_ENCODING_INT long 类型的整数
REDIS_ENCODING_EMBSTR embstr 编码的简单动态字符串
REDIS_ENCODING_RAW 简单动态字符串
REDIS_ENCODING_HT 字典
REDIS_ENCODING_LINKEDLIST 双端链表
REDIS_ENCODING_ZIPLIST 压缩列表
REDIS_ENCODING_INTSET 整数集合
REDIS_ENCODING_SKIPLIST 跳跃表和字典
  • 字符串对象

字符串对象的编码可以是int、raw或者embstr

如果一个字符串的内容可以转换为long,那么该字符串就会被转换成为long类型,对象的ptr就会指向该long,并且对象类型也用int类型表示。

普通的字符串有两种,embstr和raw。embstr应该是Redis 3.0新增的数据结构,在2.8中是没有的。如果字符串对象的长度小于39字节,就用embstr对象。否则用传统的raw对象。

  1. #define REDIS_ENCODING_EMBSTR_SIZE_LIMIT 44  
  2. robj *createStringObject(char *ptr, size_t len) {  
  3. if (len <= REDIS_ENCODING_EMBSTR_SIZE_LIMIT)  
  4. return createEmbeddedStringObject(ptr,len);  
  5. else  
  6. return createRawStringObject(ptr,len);  
  7.  

embstr的好处有如下几点:

  1. embstr的创建只需分配一次内存,而raw为两次(一次为sds分配对象,另一次为objet分配对象,embstr省去了第一次)。
  2. 相对地,释放内存的次数也由两次变为一次。
  3. embstr的objet和sds放在一起,更好地利用缓存带来的优势。

raw和embstr的区别可以用下面两幅图所示:

  • 列表对象

列表对象的编码可以是ziplist或者linkedlist

  1. ziplist是一种压缩链表,它的好处是更能节省内存空间,因为它所存储的内容都是在连续的内存区域当中的。当列表对象元素不大,每个元素也不大的时候,就采用ziplist存储但当数据量过大时就ziplist就不是那么好用了。因为为了保证他存储内容在内存中的连续性,插入的复杂度是O(N),即每次插入都会重新进行realloc。如下图所示,对象结构中ptr所指向的就是一个ziplist整个ziplist只需要malloc一次,它们在内存中是一块连续的区域。

linkedlist是一种双向链表。它的结构比较简单,节点中存放pre和next两个指针,还有节点相关的信息。当每增加一个node的时候,就需要重新malloc一块内存。

  • 哈希对象

哈希对象的底层实现可以是ziplist或者hashtable。

ziplist中的哈希对象是按照key1,value1,key2,value2这样的顺序存放来存储的。当对象数目不多且内容不大时,这种方式效率是很高的。

hashtable的是由dict这个结构来实现的, dict是一个字典,其中的指针dicht ht[2] 指向了两个哈希表

  1. typedef struct dict {  
  2. dictType *type;  
  3. void *privdata;  
  4. dictht ht[2];  
  5. long rehashidx; /* rehashing not in progress if rehashidx == -1 */  
  6. int iterators; /* number of iterators currently running */  
  7. } dict;  
  8. typedef struct dictht {  
  9. dictEntry **table;  
  10. unsigned long size;  
  11. unsigned long sizemask;  
  12. unsigned long used;  
  13. } dictht;  

dicht[0] 是用于真正存放数据,dicht[1]一般在哈希表元素过多进行rehash的时候用于中转数据。

dictht中的table用语真正存放元素了,每个key/value对用一个dictEntry表示,放在dictEntry数组中。

  • 集合对象

集合对象的编码可以是intset或者hashtable

intset是一个整数集合,里面存的为某种同一类型的整数,支持如下三种长度的整数:

  1. #define INTSET_ENC_INT16 (sizeof(int16_t))  
  2. #define INTSET_ENC_INT32 (sizeof(int32_t))  
  3. #define INTSET_ENC_INT64 (sizeof(int64_t))  

intset是一个有序集合,查找元素的复杂度为O(logN),但插入时不一定为O(logN),因为有可能涉及到升级操作。比如当集合里全是int16_t型的整数,这时要插入一个int32_t,那么为了维持集合中数据类型的一致,那么所有的数据都会被转换成int32_t类型,涉及到内存的重新分配,这时插入的复杂度就为O(N)了。

intset不支持降级操作。

  • 有序集合对象

有序集合的编码可能两种,一种是ziplist,另一种是skiplist与dict的结合。

ziplist作为集合和作为哈希对象是一样的,member和score顺序存放。按照score从小到大顺序排列

skiplist是一种跳跃表,它实现了有序集合中的快速查找,在大多数情况下它的速度都可以和平衡树差不多。但它的实现比较简单,可以作为平衡树的替代品。它的结构比较特殊。下面分别是跳跃表skiplist和它内部的节点skiplistNode的结构体:

  1. /*  
  2. * 跳跃表  
  3. */  
  4. typedef struct zskiplist {  
  5. // 头节点,尾节点  
  6. struct zskiplistNode *header, *tail;  
  7. // 节点数量  
  8. unsigned long length;  
  9. // 目前表内节点的最大层数  
  10. int level;  
  11. } zskiplist;  
  12. /* ZSETs use a specialized version of Skiplists */  
  13. /*  
  14. * 跳跃表节点  
  15. */  
  16. typedef struct zskiplistNode {  
  17. // member 对象  
  18. robj *obj;  
  19. // 分值  
  20. double score;  
  21. // 后退指针  
  22. struct zskiplistNode *backward;  
  23. // 层  
  24. struct zskiplistLevel {  
  25. // 前进指针  
  26. struct zskiplistNode *forward;  
  27. // 这个层跨越的节点数量  
  28. unsigned int span;  
  29. } level[];  
  30. } zskiplistNode;  

head和tail分别指向头节点和尾节点,然后每个skiplistNode里面的结构又是分层的(即level数组)

用图表示,大概是下面这个样子:

总结

以上简单介绍了Redis的简介,特性以及五种对象类型和五种对象类型的底层实现。事实上,Redis的高效性和灵活性正是得益于同一个对象类型采用不同的底层结构,并且在必要的时候对二者进行转换,还有就是各种底层结构对内存的合理利用。

【编辑推荐】

  1. 数据库 | 一次非常有趣的SQL优化经历
  2. 查询数据库,你还在 Select * 吗?
  3. 2019年4月数据库流行度排行:Oracle持续增长股价获新高
  4. 一次诡异的线上数据库的死锁问题排查过程
  5. 一份完整的阿里云Redis开发规范,值得收藏!
【责任编辑:庞桂玉 TEL:(010)68476606】

点赞 0
分享:
大家都在看
猜你喜欢

订阅专栏+白菜送彩金59网站大全

CentOS文件服务的最佳实战

CentOS文件服务的最佳实战

涨薪跳槽必备技能
共15章 | 追风蚂蚁

79人订阅学习

小白网工宝典

小白网工宝典

一次搞定思科华为
共15章 | 思科小牛

294人订阅学习

防火墙大佬修炼手册

防火墙大佬修炼手册

网工达人必备
共20章 | 捷哥CCIE

324人订阅学习

读 书 +白菜送彩金59网站大全

网管员必读—网络应用

本书是一本介绍当前主流计算机网络应用技术的工具图书,全面总结了当前最主流、最基础的计算机网络应用,包括局域网和互联网应用两方面。在...

订阅51CTO邮刊

点击这里查看样刊

订阅51CTO邮刊

51CTO服务号

51CTO播客

博聚网