杭州高端网站,中国服务外包研究中心,郑州网络科技有限公司,简单静态网页制作代码Redis是一个key-value存储系统#xff0c;现在在各种系统中的使用越来越多#xff0c;大部分情况下是因为其高性能的特性#xff0c;被当做缓存使用。Redis由于其丰富的数据结构也可以被应用到其他场景。Redis是一个K-V的非关系型数据库#xff08;NoSQL#xff09;#… Redis是一个key-value存储系统现在在各种系统中的使用越来越多大部分情况下是因为其高性能的特性被当做缓存使用。Redis由于其丰富的数据结构也可以被应用到其他场景。Redis是一个K-V的非关系型数据库NoSQL常见的NoSQL数据库有K-V数据库如Redis、Memcached列式数据库如大数据组件HBase文档数据库如mogoDB。Redis应用广泛尤其是被作为缓存使用。 Redis的具有很多优势1读写性能高--100000次/s以上的读速度80000次/s以上的写速度2K-Vvalue支持的数据类型很多字符串(String)队列List,哈希Hash集合Sets有序集合Sorted Sets5种不同的数据类型。3原子性Redis的所有操作都是单线程原子性的。4特性丰富--支持订阅-发布模式通知、设置key过期等特性。5在Redis3.0 版本引入了Redis集群可用于分布式部署。有需要Redis大厂面试题的小伙伴点击这里 IT架构师lukeRedis面试题BAT大厂真题zhuanlan.zhihu.comRedis数据类型及其底层实现方式Redis是由C语言编写的。Redis支持5种数据类型以K-V形式进行存储K是String类型的V支持5种不同的数据类型分别是stringlisthashsetsorted set每一种数据结构都有其特定的应用场景。从内部实现的角度来看是如何更好的实现这些数据类型。Redis底层数据结构有以下数据类型简单动态字符串SDS链表字典跳跃表整数集合压缩列表对象。接下来就探讨一下Redis是怎么通过这些数据结构来实现value的5种类型的。简单动态字符串simple dynamic string SDSString的数据类型是由SDS实现的。Redis并没有采用C语言的字符串表示而是自己构建了一种名为SDS的抽象类型并将SDS作为Redis的默认字符串表示。redisSET msg hello worldOK上边设置keymsgvaluehello world的键值对它们的底层存储是键key是字符串类型其底层实现是一个保存着“msg”的SDS。值value是字符串类型其底层实现是一个保存着“hello world”的SDS。 注意SDS除了用于实现字符串类型还被用作AOF持久化时的缓冲区。SDS的定义为/* * 保存字符串对象的结构 */ struct sdshdr { // buf 中已占用空间的长度 int len; // buf 中剩余可用空间的长度 int free; // 数据空间 char buf[]; };为什么要使用SDS我们一定会思考redis为什么不使用C语言的字符串而是费事搞一个SDS呢这是因为C语言用N1的字符数组来表示长度为N的字符串这样做在获取字符串长度字符串扩展等操作方面效率较低并且无法满足redis对字符串在安全性、效率以及功能方面的要求。获取字符串长度SDS O1在C语言字符串中为了获取一个字符串的长度必须遍历整个字符串时间复杂度为O(1)而SDS中有专门用于保存字符串长度的变量所以可以在O1时间内获得。防止缓冲区溢出C字符串容易导致缓冲区溢出假设在程序中存在内存紧邻的字符串s1和s2s1保存rediss2保存MongoDB如下图如果我们现在将s1 的内容修改为redis cluster但是又忘了重新为s1 分配足够的空间这时候就会出现以下问题因为s1和s2是紧邻的所以原本s2 中的内容已经被S1的内容给占领了s2 现在为 cluster而不是“Mongodb”。而Redis中的SDS就杜绝了发生缓冲区溢出的可能性。当我们需要对一个SDS 进行修改的时候redis 会在执行拼接操作之前预先检查给定SDS 空间是否足够free记录了剩余可用的数据长度如果不够会先拓展SDS 的空间然后再执行拼接操作。减少扩展或收缩字符串带来的内存重分配次数当字符串进行扩展或收缩时都会对内存空间进行重新分配。 1. 字符串拼接会产生字符串的内存空间的扩充在拼接的过程中原来的字符串的大小很可能小于拼接后的字符串的大小那么这样的话就会导致一旦忘记申请分配空间就会导致内存的溢出。 2. 字符串在进行收缩的时候内存空间会相应的收缩而如果在进行字符串的切割的时候没有对内存的空间进行一个重新分配那么这部分多出来的空间就成为了内存泄露。比如字符串redis当进行字符串拼接时将rediscluster13会将SDS的长度修改为13同时将free也改为13这意味着进行预分配了将buffer大小变为了26。这是为了如果再次执行字符串拼接操作如果拼接的字符串长度13,就不需要重新进行内存分配了。通过这种预分配策略SDS将连续增长N次字符串所需的内存重分配次数从必定N次降低为最多N次。通过惰性空间释放SDS 避免了缩短字符串时所需的内存重分配操作并未将来可能有的增长操作提供了优化。二进制安全 C 字符串中的字符必须符合某种编码并且除了字符串的末尾之外字符串里面不能包含空字符否则最先被程序读入的空字符将被误认为是字符串结尾这些限制使得C字符串只能保存文本数据而不能保存想图片音频视频压缩文件这样的二进制数据。 但是在Redis中不是靠空字符来判断字符串的结束的而是通过len这个属性。那么即便是中间出现了空字符对于SDS来说读取该字符仍然是可以的。但是SDS依然可以兼容部分C字符串函数。链表链表是list的实现方式之一。当list包含了数量较多的元素或者列表中包含的元素都是比较长的字符串时Redis会使用链表作为实现List的底层实现。此链表是双向链表typedef struct listNode{ struct listNode *prev; struct listNode * next; void * value; }一般我们通过操作list来操作链表typedef struct list{ //表头节点 listNode * head; //表尾节点 listNode * tail; //链表长度 unsigned long len; //节点值复制函数 void *(*dup) (void *ptr); //节点值释放函数 void (*free) (void *ptr); //节点值对比函数 int (*match)(void *ptr, void *key);} 链表结构的特点是可以快速的在表头和表尾插入和删除元素但查找复杂度高是列表的底层实现之一也因此列表没有提供判断某一元素是否在列表中的借口因为在链表中查找复杂度高。字典 字典又称为符号表symbol table、关联数组associative array或映射map是一种用于保存键值对的抽象数据结构。 在字典中一个键key可以和一个值value进行关联字典中的每个键都是独一无二的。在C语言中并没有这种数据结构但是Redis 中构建了自己的字典实现。redis SET msg hello worldOKRedis本身的K-V存储就是利用字典这种数据结构的另外value类型的哈希表也是通过这个实现的。哈希表dicy的定义为typedef struct dictht { //哈希表数组 dictEntry **table; //哈希表大小 unsigned long size; //哈希表大小掩码用于计算索引值 unsigned long sizemask; //该哈希表已有节点的数量 unsigned long used;}我们可以想到对比Java hashMap的实现方式在dictht中table数组的类型是typeof struct dictEntry{ //键 void *key; //值 union{ void *val; uint64_tu64; int64_ts64; } struct dictEntry *next;}我们存入里面的key 并不是直接的字符串而是一个hash 值通过hash 算法将字符串转换成对应的hash 值然后在dictEntry 中找到对应的位置。这时候我们会发现一个问题如果出现hash 值相同的情况怎么办Redis 采用了链地址法来解决hash冲突。这与hashmap的实现类似。注意Redis又在dictht的基础上又抽象了一层字典dict其定义为typedef struct dict { // 类型特定函数 dictType *type; // 私有数据 void *privedata; // 哈希表 dictht ht[2]; // rehash 索引 in trehashidx;} type 属性 和privdata 属性是针对不同类型的键值对为创建多态字典而设置的。 ht 属性是一个包含两个项两个哈希表的数组如图解决hash冲突采用链地址法来实现。扩充Rehash 随着对哈希表的不断操作哈希表保存的键值对会逐渐的发生改变为了让哈希表的负载因子维持在一个合理的范围之内我们需要对哈希表的大小进行相应的扩展或者压缩这时候我们可以通过 rehash重新散列操作来完成。其实现方式和hashmap略有不同因为dict有两个hash表dictht所以它是通过这两个dictht互相进行转移的。比如上图这种情况代表要进行扩容了所以就要将ht[0]的数据转移到ht[1]中。ht[1]创建为2*ht[0].size大小的如下图将ht[0]释放然后将ht[1]设置成ht[0]最后为ht[1]分配一个空白哈希表其实上边的扩容过程和Java 的HashMap具体的扩容实现方式还是挺像的。渐进式rehash在实际开发过程中这个rehash 操作并不是一次性、集中式完成的而是分多次、渐进式地完成的。采用渐进式rehash 的好处在于它采取分而治之的方式避免了集中式rehash 带来的庞大计算量。渐进式rehash 的详细步骤 1、为ht[1] 分配空间让字典同时持有ht[0]和ht[1]两个哈希表 2、在几点钟维持一个索引计数器变量rehashidx并将它的值设置为0表示rehash 开始 3、在rehash 进行期间每次对字典执行CRUD操作时程序除了执行指定的操作以外还会将ht[0]中的数据rehash 到ht[1]表中并且将rehashidx加一 4、当ht[0]中所有数据转移到ht[1]中时将rehashidx 设置成-1表示rehash 结束跳跃表Redis 只在两个地方用到了跳跃表一个是实现有序集合键sorted Sets另外一个是在集群节点中用作内部数据结构。其实跳表主要是来替代平衡二叉树的比起平衡树来说跳表的实现要简单直观的多。跳跃表skiplist是一种有序数据结构它通过在每个节点中维持多个指向其他节点的指针从而达到快速查找访问节点的目的。跳跃表是一种随机化的数据,跳跃表以有序的方式在层次化的链表中保存元素效率和平衡树媲美 ——查找、删除、添加等操作都可以在Ologn期望时间下完成。 Redis 的跳跃表 主要由两部分组成zskiplist链表和zskiplistNode 节点 typedef struct zskiplistNode{ //层 struct zskiplistLevel{ //前进指针 struct zskiplistNode *forward; //跨度 unsigned int span; } level[]; //后退指针 struct zskiplistNode *backward; //分值 double score; //成员对象 robj *obj;}1、层level 数组可以包含多个元素每个元素都包含一个指向其他节点的指针。level数组的每个元素都包含前进指针用于指向表尾方向的前进指针跨度用于记录两个节点之间的距离2、后退指针用于从表尾向表头方向访问节点3、分值和成员跳跃表中的所有节点都按分值从小到大排序按照这个进行排序的也就是平衡二叉树搜索树的的节点大小。成员对象指向一个字符串这个字符串对象保存着一个SDS值实际存储的值 typedef struct zskiplist { //表头节点和表尾节点 structz skiplistNode *header,*tail; //表中节点数量 unsigned long length; //表中层数最大的节点的层数 int level;}zskiplist; 从结构图中我们可以清晰的看到headertail分别指向跳跃表的头结点和尾节点。level 用于记录最大的层数length 用于记录我们的节点数量。 跳跃表是有序集合的底层实现之一 主要有zskiplist 和zskiplistNode两个结构组成 每个跳跃表节点的层高都是1至32之间的随机数 在同一个跳跃表中多个节点可以包含相同的分值但每个节点的对象必须是唯一的 节点按照分值的大小从大到小排序如果分值相同则按成员对象大小排序怎么使用跳表来实现Ologn的增删改查其实跳表的实现原理我们可以结合二分法来看。比如上图我们要查找55如果通过遍历则必须得从头遍历到最后一个才能找到所以在数组实现中我们可以使用二分法来实现但是在链表中我们没办法直接通过下标来访问元素所以一般我们可以用二叉搜索树平衡树来存储元素我们知道跳表就是来替代平衡树的那么跳表是如何快速查询呢看下图从上图我们可以看到我们通过第4层只需一步便可找到55另外最耗时的访问46需要6次查询。即L4访问55L3访问21、55L2访问37、55L1访问46。我们直觉上认为这样的结构会让查询有序链表的某个元素更快。这种实现方式跟二分很相似其时间复杂度就是O(logn)。其插入删除都是Ologn。我们可以看到redis正是通过定义这种结构来实现上边的过程其层数最高为32层也就是他可以存储2^32次方的数据其查找过程与上图很类似。整数集合Intset《Redis 设计与实现》 中这样定义整数集合“整数集合是集合建(sets)的底层实现之一当一个集合中只包含整数且这个集合中的元素数量不多时redis就会使用整数集合intset作为集合的底层实现。”我们可以这样理解整数集合他其实就是一个特殊的集合里面存储的数据只能够是整数并且数据量不能过大。typedef struct intset{ //编码方式 uint32_t enconding; // 集合包含的元素数量 uint32_t length; //保存元素的数组 int8_t contents[];} 整数集合是集合建的底层实现之一.整数集合的底层实现为数组这个数组以有序无重复的范式保存集合元素在有需要时程序会根据新添加的元素类型改变这个数组的类型.压缩列表压缩列表是列表键list和哈希键hash的底层实现之一。当一个列表键只有少量列表项并且每个列表项要么就是小整数要么就是长度比较短的字符串那么Redis 就会使用压缩列表来做列表键的底层实现。 1、zlbytes:用于记录整个压缩列表占用的内存字节数 2、zltail记录要列表尾节点距离压缩列表的起始地址有多少字节 3、zllen记录了压缩列表包含的节点数量。 4、entryX要说列表包含的各个节点 5、zlend用于标记压缩列表的末端压缩列表是一种为了节约内存而开发的顺序型数据结构压缩列表被用作列表键和哈希键的底层实现之一压缩列表可以包含多个节点每个节点可以保存一个字节数组或者整数值添加新节点到压缩列表可能会引发连锁更新操作。如果你喜欢我写的技术文章以及面试总结欢迎关注收看我的视频并且点赞、收藏、关注我哦。我是luke感谢你的关注也可以加入到我的圈子一起学习成长哦【架构师之路】点击链接申请加入圈子架构师之路 - 知乎www.zhihu.com
