Redis作为KV缓存服务器，具有极高的性能。与Memcache相比，Redis支持的数据类型更多，因此在业界得到广泛应用。记得刚面试毕业的时候，面试官会问我Redis为什么快。由于当时技术水平有限，只能回答以下两点：数据是存储在内存中的。Redis是单线程的。当然，将数据存储在内存中，读取时不需要磁盘IO，单线程也保证了系统没有线程的上下文切换。但是这两点只是Redis高性能的一小部分原因。下面我们从数据存储层面来分析为什么Redis的性能如此之高。Redis性能之所以这么高，我总结了以下几点：纯内存操作单线程高效数据结构合理的数据编码其他方面的优化在Redis中，常用的五种数据结构和应用场景如下：String：缓存、计数器、分布式锁等List：链表、队列、微博关注时间线列表等Hash：用户信息、哈希表等Set：去重、喜欢、不喜欢、共同好友等Zset：访问量排行榜，点击排行榜等。SDSRedis是用C语言开发的，但是在Redis的字符串中，并没有使用C语言中的字符串，而是使用了一个叫做SDS（SimpleDynamicString）的结构来保存字符串。structsdshdr{intlen;intfree;charbuf[];}SDS的结构如上图：len：用于记录buf中已使用空间的长度。free：buf中空闲空间的长度。buf[]：存储实际内容。例如：执行命令setkeyvalue，key和value都以SDS类型结构存储在内存中。SDS和C字符串的区别①常数时间内获取字符串长度C字符串本身不记录长度信息，每次都需要遍历整个字符串获取长度信息，复杂度为O(n);结束于“\0”。SDS中的len字段存储的是字符串的长度，所以字符串的长度总能在常数时间内得到，复杂度为O(1)。②避免缓冲区溢出假设内存中有两个相邻的字符串，s1="xxxxx"和s2="yyyyy"。由于内存中的紧密连接，当我们扩展s1时，设置s1="xxxxxzzzzz"后，由于没有相应的内存重新分配，s1覆盖了s2，导致s2被莫名修改。但是SDSAPI在修改zfc的时候，会先检查空间是否足够，如果不够再分配新的空间，避免了bufferoverflow的问题。③减少字符串修改引起的内存重新分配次数在C语言中，当我们频繁修改（append或trim）一个字符串时，需要进行频繁的内存重新分配操作，这对性能影响很大。如果不小心忘记了，可能会导致内存溢出或者内存泄漏。对于Redis来说，字符串本身会被修改的很频繁，所以使用C字符串是不合适的。SDS实现了空间预分配和惰性空间释放两种优化策略：空间被分配。分配规则如下：如果修改SDS后len的长度小于1M，程序将分配与len长度相同的未使用空间。例如len=10，重新分配后，buf的实际长度变为10（已用空间）+10（多余空间）+1（空字符）=21。如果修改SDS后len的长度大于1M，程序会分配1M的未使用空间。Lazyspacerelease：在缩短SDS时，程序不会回收多余的内存空间，而是使用free字段记录字节数，不释放。如果后面需要追加操作，直接使用空闲空间中未使用的，减少内存分配。④二进制安全在Redis中，不仅可以存储String类型的数据，还可以存储一些二进制数据。二进制数据不是常规的字符串格式，其中包含一些特殊字符如'\0'，在C中遇到'\0'表示字符串结束，但在SDS中，标志字符串结束是长度属性。字典类似于Java中的HashMap，Redis中的Hash比Java更高级。Redis本身就是一个KV服务器。除了Redis数据库本身，字典也是hashkey的底层实现。字典的数据结构如下：typedefstructdict{dictType*type;void*privdata;dictththt[2];inttrehashidx;}typedefstructdict{//hashtablearraydectEntrt**table;//hashtablesizeunsignedlongsize;//unsignedlongsizemask;//哈希表中已有节点的个数unsignedlongused;}两个重要的字段是dicttht和trehashidx，与rehash有关。下面将重点介绍rehash。学过Java中Rehash的朋友应该知道HashMap是如何进行rehash的。我不会在这里详细介绍。下面介绍Redis中Rehash的过程。从上面的代码我们知道dict中存储了一个dicttht数组，长度为2，说明这个数据结构中实际存储了两个哈希表ht[0]和ht[1]。为什么我们需要存储两个哈希表？？当然对于Rehash来说，Rehash的过程是这样的：为ht[1]分配空间。如果是扩容操作，ht[1]的大小为大于等于ht[0].used*2的前2^n；如果是收缩操作，ht[1]的大小是第一个大于等于2^n的ht[0].used。将ht[0]中的键值重新散列为ht[1]。ht[0]全部迁移到ht[1]后，释放ht[0]，将ht[1]设置为ht[0]，并为ht[1]新建一张表，为下一次Rehash做准备。ProgressiveRehash因为Redis的Rehash操作是将ht[0]中的所有key值迁移到ht[1]中，如果数据量小，迁移过程非常快。但是如果数据量很大，当一个Hash表中存储了数万甚至数百万的keyvalues时，迁移过程就会非常缓慢，并且会影响其他用户的使用。为了避免Rehash对服务器性能的影响，Redis采用渐进式Rehash策略，分多次将ht[0]中的数据逐渐迁移到ht[1]中。前者的过程如下：为ht[1]分配空间，让字典同时有两个哈希表ht[0]和ht[1]。在字典中维护一个rehashidx，设置为0，表示开始Rehash。rehash时，每次对字典进行操作时，程序也会将rehashidx索引上ht[0]的所有键值对rehash为ht[1]，rehash完成后rehashidx属性+1。当所有rehash完成后，将rehashidx设置为-1，表示rehash完成。注意，由于维护了两张Hash表，Rehash过程中内存会增加。另外，在Rehash过程中，字典会同时使用ht[0]和ht[1]。所以在删除、查找、更新的时候，都会在两个表中进行操作。查询时，会在第一个表中查询。如果不在第一个表中，则在第二个表中查询。但是，所有新增的内容都会在ht[1]中进行，保证ht[0]中的数据只会减少不会增加。跳表Zset是一个有序链表结构，其底层数据结构是跳表skiplist，其结构如下：*backward;//layerstructzskiplistLevel{structzskiplistNode*forward;//前向指针unsignedintspan;//span}level[];}zskiplistNode;typedefstructzskiplist{//表头节点和表尾节点structzskiplistNode*header,*tail;//nodesinthetableQuantityunsignedlonglength;//表中***级别的节点层数intlevel;}zskiplist;正向指针：用于从表头遍历到表尾。向后指针：用于从表尾向表头倒退一个节点。与前向指针不同的是，前向指针可以一次跳转多个节点，而后向指针每次只能回到上一个节点。跨度：表示当前节点与下一个节点之间的距离。跨度越大，两个节点之间的元素越多。查询时向前跳转。由于后向指针的存在，如果查询超出范围，通过后向指针回到上一个节点后，仍然可以继续向前遍历。CompressedListCompressedlistziplist是为Redis节省内存而开发的，是listkeys和dictionarykeys的底层实现之一。当元素数量较少时，Redis使用ziplist来存储数据。当元素个数超过一定值时，链表key会将ziplist转成linkedlist，dictionarykey会将ziplist转成hashtable。Ziplist是一种顺序数据结构，由一系列经过特殊编码的连续内存块组成。Ziplist可以包含多个入口节点，每个节点可以存储整数或字符串。由于内存是连续分配的，所以遍历很快。编码转换Redis使用对象（redisObject）来表示数据库中的键值。我们在Redis中创建键值对时，至少会创建两个对象，一个对象是作为键值对的键对象，另一个是键值对的值对象。例如，当我们执行SETMSGXXX时，键值对的key是包含字符串“MSG”的对象，键值对的值对象是包含字符串“XXX”的对象。redisObject的结构如下：typedefstructredisObject{//typeunsignedtype:4;//encodingunsignedencoding:4;//指向底层数据结构的指针void*ptr;//...}robj;其中type字段记录了对象的类型，包含字符串对象、列表对象、哈希对象、集合对象、排序后的集合对象。当我们执行typekey命令时，返回的结果如下：ptr指针字段指向对象的底层数据结构，这些数据结构由encoding字段决定。每个对象至少有两种数据编码：可以通过对象编码key查看对象使用的编码：细心的读者可能会注意到，list、hash、zset这三个key使用的是ziplist压缩列表编码，这就涉及到了底层Redis的编码转换。如上所述，ziplist是一个紧凑的数据结构。当一个键包含的元素较少时，它将首先存储在ziplist中。当元素个数超过某个值时，ziplist会转为Standard存储结构，这个值是可配置的。String对象的编码转换String对象的编码可以是int或raw。对于String类型的键值，如果我们存储的是纯数字，Redis底层使用的是int类型编码。如果包含非数字，则立即转换对于原始编码：127.0.0.1:6379>setstr1OK127.0.0.1:6379>objectencodingstr"int"127.0.0.1:6379>setstr1aOK127.0.0.1:6379>objectencodingstr"raw"127.0.0.1:6379>Listobjectencoding转换List对象的代码可以是ziplist或linkedlist。对于List类型的key值，当list对象同时满足以下两个条件时，使用ziplist编码：list对象中存储的所有字符串元素长度小于64字节。列表对象包含少于512个元素。如果这两个条件有一个不满足，就会转为链表编码。注意：这两个条件可以修改。redis.conf中：list-max-ziplist-entries512list-max-ziplist-value64集合类型编码转换集合对象编码可以是intset或hashtable，intset编码的婚姻对象使用整数集合作为底层实现，所有元素都是存储在一个整数集中。127.0.0.1:6379>saddset123(integer)3127.0.0.1:6379>objectencodingset"intset"127.0.0.1:6379>如果set集合中存储非整数数据，Redis会将intset转换为hashtable:127.0.0.1:6379>saddset123(integer)3127.0.0.1:6379>objectencodingset"intset"127.0.0.1:6379>saddseta(integer)1127.0.0.1:6379>objectencodingset"hashtable"127.0.0.1:6379>当Set对象满足以下两个时object在满足两个条件时用intset编码：存储的所有元素都是整数值（不接受小数）。Set对象持有的所有元素个数小于512，如果这两个条件中的任何一个都不满足，Set就会被存储到hashtable中。注意：第二个条件可以修改，在redis.conf中：set-max-intset-entries512Hash对象编码转换Hash对象编码可以是ziplist或者hashtable，当Hash存储为ziplist编码时，保存同一个key的两个节点valuepair总是紧靠在一起，key节点在前，value节点在后：当Hash对象同时满足以下两个条件时，Hash对象采用ziplist编码：所有key的keys-存储在Hash对象中的值对，值的字符串长度和值都小于64字节。Hash对象中存储的键值对数量小于512，如果不满足以上任何一个条件，ziplist将转为hashtable编码。注意：这两个条件可以修改。redis.conf中：hash-max-ziplist-entries512hash-max-ziplist-value64Zset对象编码转换Zset对象编码可以是ziplist或zkiplist，当使用ziplist编码存储时，每个集合元素存储为紧挨着的两个packedlist彼此。第一个节点存储元素的成员，第二个节点存储元素的分数，按照分数从小到大的顺序排列。当Zset对象同时满足以下两个条件时，使用ziplist编码：Zset中保存的元素个数小于128个，Zset元素的成员长度均小于64字节。如果不满足上述任何条件，ziplist将转换为zkiplist编码。注：这两个条件可以修改，在redis.conf中：zset-max-ziplist-entries128zset-max-ziplist-value64思考：Zset是如何做到O(1)复杂度，快速进行范围操作的？Zset在使用skiplist编码时，底层实现是使用zset结构。该数据结构包含一个跳跃列表和一个字典。其结构如下：typedefstructzset{zskiplist*zsl;dict*dict;}Zset中的dict字典为集合创建成员到分数的映射，字典中的键存储成员，字典中的值存储成员，所以定位元素的时间复杂度是O(1)。Zset中的zsl跳表适用于范围操作，如ZRANK、ZRANGE等，程序使用zkiplist。另外，Zset中虽然使用了dict和skiplist来存储数据，但是这两个数据结构会通过指针共享同一个内存，所以不用担心浪费内存。删除过期数据对Redis性能的影响当我们为一些key设置过期时，到时候数据会自动删除。如果密钥过期，什么时候会被删除？下面介绍三种删除策略：定时删除：当此时是key的过期时间，创建定时器Timer，让定时器在key过期时间到来时立即执行过期key的删除。懒删除：无论key过期后，每次读取key，都会判断key是否过期，如果key过期，则删除key并返回空。定期删除：每隔一段时间检查数据库中的过期键。定时删除：对内存友好，对CPU不友好。如果过期删除key较多，删除key的行为会占用相当一部分CPU性能，对Redis的吞吐量有一定的影响。懒删除：对CPU友好，对内存不友好。如果很多key已经过期，但是以后很长一段时间不会有很多客户端访问这些key，那么过期的key不会被删除，这样会占用大量的内存空间。定期删除：它是定期删除和懒惰删除之间的折衷。定期执行删除过期键的操作，并限制删除操作的时间和频率。具体操作如下：Redis会将每一个设置了expire的key保存在一个独立的字典中，并会周期性的遍历这个字典删除过期的key。除了定时遍历外，它还采用惰性删除策略来删除过期键。默认情况下，Redis每秒执行十次过期扫描。过期扫描不会扫描过期字典中的所有key，而是采用简单的贪心策略。从过期字典中随机选择20个key；删除20个key中过期的key；如果过期键的比例超过1/4，则重复步骤1。同时，为了保证过期扫描时不会出现过多的循环，导致线程卡死，算法也增加了上限扫描时间，默认不会超过25ms。总结总而言之，Redis为了高性能在各个方面都进行了优化。下次面试的时候小伙伴们会问为什么Redis的性能那么高。不能光说单线程和内存存储。
