本文转载自微信公众号《SH的全栈笔记》，作者SH。转载本文请联系SH全栈笔记公众号。如果你是一个有经验的后端或者服务器开发者，你一定听说过Redis，它的全称是RemoteDictionaryServer。它是一个用C语言编写的基于Key-Value的存储系统。说白了就是内存数据库。由于是内存数据库，如果服务器意外宕机，会遇到数据不一致的问题。这和很多游戏服务器一样。有兴趣的可以参考我之前的文章游戏服务器和web服务器的区别。它的数据会先流向内存，基于内存的快速读写实现高性能，然后在内存中定时落地数据。Redis其实就是这么一个进程。基于快速的内存读写操作，单机Redis甚至可以处理100,000QPS。除了高性能，Redis还拥有丰富的数据结构，可以支持大部分业务场景。这也是它如此受欢迎的原因之一。下面我们就来看看Redis的基本数据类型以及它们在底层是如何实现的。1.数据类型基本数据类型有String、List、Hash、Set、SortedSet。这些是常用的基本数据类型。可以看到他们很丰富，几乎可以满足大部分需求。其实还有一些高级的数据结构，我们本章暂时不提，只讲基本的数据结构。2、StringString可以说是最基本的数据结构。在用法上，可以直接和Java中的String挂钩。你可以用String类型来存储某个flag，某个counter，甚至更残忍的，序列化后的JSON都是strings就可以了，单个key的限制是512M。它的常用命令有get、set、incr、decr、mget。2.1使用get获取一个key。如果key不存在，则返回一个空指针set给key赋值，并将key设置为指定的值。如果键已经有一个值，它将被新值覆盖到当前值。key的值+1，如果key不存在，会先调用set给key赋值0，然后调用incr。当然，如果不能加上key的类型，比如字符串，会抛出一个错误decr，给当前key的值-1，其他同上。mget和get一样，但是一次返回多条数据，不存在的key会是可以理解的是，大部分返回空指针字符串相关的命令只使用一次，但是如果是一个追求技术的发展，或者有接近大厂的想法，一定要追根究底。的精神。只有真正了解了某件事的底层原理，才能在遇到问题时提供更多解决问题的思路。接下来说说Redis中String的底层是如何实现的。2.2原理2.2.1结构我们知道Redis是用C语言编写的，但是Redis并没有直接使用它。相反，它实现了一种称为SDS（简单动态字符串）的结构来实现字符串。结构如下。structsdshdr{//记录buf中使用的字节数intlen;//记录buf中未使用的字节数intfree;//字节数组，用于保存字符串charbuf[];}2.2.2优点为什么要Redis自己实现SDS而不是直接使用C字符串？主要是因为以下几点。降低获取字符串长度的代价C语言获取字符串长度需要遍历整个字符串，直到遇到结束标志\0，时间复杂度为O(n)。而SDS直接维护了长度的变量，长度的时间复杂度为O(1)，避免缓冲区溢出。在C语言中，如果向一个字节数组中塞入超过其容量的字节数，会导致缓冲区溢出，而SDS通过维护自由变量来解决这个问题。向buf数组写入数据时，会先判断剩余空间是否足够插入新数据。如果不是，SDS将重新分配缓冲区并扩大以前的缓冲区。并且增加的长度等于新增数据的长度。空间预分配&空间惰性释放在C语言中，每修改一个字符串，都会重新分配内存空间。如果字符串被修改了n次，那么必然会有n次内存重新分配。但是，由于部分空间的冗余，SDS优化了这个问题。必然会重新分配n次，最多n次。当数据从buf中移除时，空闲内存不会立即回收，防止新的写入数据导致内存重新分配，保证二进制安全。C语言中遇到\0会截断字符串，而SDS不会因为数据中有\0而截断字符串。也就是说，它不会因为一些特殊字符而截断字符串，影响实际运行结果，可以结合下图来理解SDS。图片来自网络，侵删总结就是上面列表中的四个字幕，为了降低获取字符串长度的成本，避免缓冲区溢出，空间预分配&空间惰性释放，保证二进制安全。3、ListList也是一种经常使用的数据结构。它涉及太多命令。不像String要一一演示。有兴趣的可以搜索一下。命令包括lpush、lpushx、rpush、rpushx、lpop、rpop、lindex、linsert、lrange、llen、lrem、lset、ltrim、rpoplpush、brpoplpush、blpop、brpop，这些都是对数组中元素的操作。3.1我认为使用List的目的主要集中在以下两个方面。将数据存储为普通列表（类似于Java的ArrayList），作为异步队列的普通列表使用。不用说，它存储了不可避免的业务所需的数据。让我们关注异步队列。什么鬼，List也能当队列用？List除了可以作为队列使用，还可以作为栈使用。上面介绍了很多操作List的命令。当我们使用rpush/lpop组合命令时，实际上是在使用一个队列，而当我们使用rpush/rpop组合命令时，我们使用的是一个栈。lpush/rpop和lpush/lpop是一样的。假设我们使用rpush生产消息，当我们的程序需要消费消息时，我们使用lpop从异步队列中消费消息。但是如果使用这种方式，当队列为空时，可能需要不断询问队列中是否有数据，会造成机器上CPU资源的浪费。所以可以让当前线程休眠一段时间，确实可以节省一些CPU资源。但您可能需要考虑睡眠时间。如果间隔太短，CPU上下文切换也可能是相当大的开销。如果间隔太长，可能会导致这条消息被延迟消费（不过都是用的异步队列，所以应该可以。无视这个问题）。除了Sleep，还有别的办法吗？是的，答案是blpop。当我们使用blpop消费的时候，如果当前队列为空，那么线程就会被阻塞，直到出现以下两种情况。当达到设置的超时时间后，队列中就有消息可以消费了。与Sleep一段时间相比，实时性会更好；它比轮询对CPU资源更友好。3.2原理在Redis3.2之前，Redis使用ZipList（压缩列表）或者LinkedList（链表）。当List中的元素满足每个元素小于64字节且List元素个数小于512时，存储方式为ZipList。每当不满足条件时，它将转换为LinkedList。3.2之后，它的实现变成了QuickList（快速列表）。由于LinkedList是一个比较基础的东西，这里就不赘述了。3.2.1ZipListZipList采用连续紧凑的内存存储方式，不像链表需要额外的空间来存储前驱节点和后续节点的指针。根据其存储区域的划分，大致可以分为三部分，每一部分也有自己的划分。详细结构如下。headerziplist头信息的zlbytes，标识ziplist占用内存的字节数zltail到ziplist尾节点的偏移量zllenziplist条目存储的节点数存储实际节点的信息pre_entry_length记录了上一个节点的长度，通过这个值可以快速跳转到上一个节点。encoding顾名思义，存储元素长度的编码格式就是存储数据的长度。content保存节点的内容end标记ziplist的结尾。该方法可能会造成一定的内存碎片。指针也会占用额外的存储空间。ZipList没有这些情况，ZipList占用的是一块连续的内存空间。但相应的，ZipList的修改操作效率比较低，插入和删除的操作会被设计成频繁的内存空间申请和释放（有点类似于ArrayList的重新扩容），查询效率也会受到影响。本质上，ZipList查询元素是遍历链表。3.2.2QuickList3.2版本后，list的实现被QuickList取代。QuickList将链表分成多个节点，每个节点使用ZipList存储数据。4、Hash的用法和Java中的HashMap是一样的，都是把键值对丢到map里面。4.1使用基本命令如下：hset设置哈希中的键值对hget获取哈希中的键值hdel删除哈希中的键hlen统计哈希中的元素个数hmget获取哈希中的键值hmset批量设置hash中的key和valuehexists判断hash中某个key是否存在hkeys返回hash中的所有key（不包括value）hvals返回hash中的所有value（不包括key）hgetall获取所有key-valuepairs，包含keys和values其实大部分情况下的使用和HashMap类似，并没有什么特别之处。4.2原理hash的底层实现也有两个，ZipList和HashTable。但是使用哪一个与Redis的版本无关，而与当前hash存储的元素有关。首先，当我们创建哈希时，我们使用ZipList进行存储。随着hash中元素个数的增加，达到Redis设定的阈值，就会转为HashTable。设置的阈值如下：存储的key或value的长度大于默认值（64）ZipList存储的元素个数大于默认值（512）上面我们简单分析了ZipList，应该是这个设定比较容易理解。当ZipList中的元素过多时，查询效率会变低。HashTable的底层设计其实和Java中的HashMap类似，都是用zipper的方式来解决hash冲突。具体可以参考《从基础使用深入HashMap》一文。5、SetSet的概念可以等同于Java中的Set，用来存储一个不包含重复元素的集合。5.1主要用到的命令如下，key代表redis中的Set，member代表集合中的元素。saddsaddkeymember[...]添加一个或多个元素到集合中，并忽略现有元素。sremsremkeymember[...]从集合中移除一个或多个元素，不存在的元素将被忽略smemberssmemberskey返回集合中的所有成员sismemberdismemberkeymember判断该成员是否存在于key中，返回1如果存在，如果不存在则为0scardscardkey返回collectionkey中的元素个数movemovesourcedestinationmember将元素从源集合移动到目标集合。如果source不包含成员，则不执行任何操作，并且当且仅当它存在时才将其从集合中删除。如果目标已经有一个元素，则不会对目标执行任何操作。这个命令是一个原子操作。spopspopkey随机删除并返回集合中的一个元素。srandmembersrandmemberkey和spop一样，只是元素不会被删除。可以理解为从集合中随机选择一个元素。sinter找到一组或多组的交集。sinterstoresinterstoredestinationkey[...]类似于sinter，但结果会存储在destination中。sunion求一个或多个集合的并集sunionstoresunionstoredestinationkey[...]sdiff求一个或多个集合的差异sdiffstoresdiffstoredestinationkey[...]类似于sdiff，但将结果保存到目的地。5.2原理我们知道Java中Set的实现有很多种。同样在Redis中，有IntSet和HashTable两种实现。首先使用IntSet进行初始化，当满足以下条件时，会转为HashTable。当集合中存储的所有元素都是整数时，集合对象中存储的元素个数不超过512个。HashTable上面已经简单介绍过了，这里只讲IntSet。5.2.1IntSetintset底层是一个数组。由于数据结构是数组，所以存储的数据可以排序，这也使得intset的底层查询可以通过二分查找来实现。它的结构如下。structintset{//编码方法uint32_tencoding;//集合中包含的元素个数uint32_tlength;//存储元素的数组int8_tcontents[];}与ZipList类似，IntSet也是使用一系列的内存空间，不同的是ZipList可以存储二进制内容，而IntSet只能存储整数；ZipList存储是无序的，而IntSet是有序的。这样在元素个数相同的前提下，IntSet的查询效率会更高。6.SortedSet其功能与Set大致相似，但在此基础上可以为每个元素分配一个权重。你可以理解为Java的TreeSet。和List、Hash、Set一样，有两种底层实现，分别是ZipList和SkipList（跳表）。在初始化SortedSet时，将使用ZipList作为其实现。其实很好理解。这时候元素的数量就很少了，使用ZipList进行紧凑存储会节省更多的空间。当当前周期满足以下条件时，将转为SkipList：存储元素个数小于128个，所有存储元素长度小于64字节。6.1下面命令中key代表zset的名称；4代表score，也就是权重；member是zset中键的名称。zaddzaddkey4member用于添加元素zcardzcardkey用于获取zset中的元素个数zremzremkeymember[...]删除zset中的一个或多个keyzincrbyzincrbykey1member添加到权重值thekeyscore的值（即1）zscorezscorekey成员用于获取指定key的权重值zrangezrangekey0-1获取zset中的所有元素，zrangekey0-1withscores获取所有元素和权重，withscores参数的作用是决定是否也返回权重值。返回的元素从小到大排序，如果元素权重相同，则按字典顺序排序。zrevrangezrevrangekey0-1withscores，和zrange类似，只是zrevrange是从大到小排序的。zrangebyscorezrangebyscorekey15，返回key中权重在(1,5)范围内的元素。当然也可以用withscores一起返回权重值，元素从小到大排序。1代表min,5代表max，也可以分别是**-inf和inf**，可以在不知道key中score区间的时候使用。还有一个可选参数，类似于SQL中的limit，所以这里就不细说了，除了可以给里面的元素加上权重，使用ZSet还可以实现一个延迟队列，延迟队列就是用来存放延迟任务的，那么什么是延迟队列呢？一个很简单的例子，你在一个电商APP下单，但是没有付款，这时候会提醒你，“订单超过1小时未付款，将自动关闭”；再比如在某个事件结束前1小时向用户发送消息；或者在订单完成后多少天自动matically确认收据等。用人话解释，那是以后要做的事情。ZSet是如何实现这个功能的？其实很简单，就是将任务的执行时间设置为ZSet中的元素权重，然后使用后台线程周期性的从ZSet中查询权重最小的元素，然后通过当前时间戳进行判断，如果大于当前时间戳（即应该执行），则从ZSet中取出。那么，如何获得呢？其实我看到很多关于Redis实现延迟队列的博客都没有解释清楚如何获取，使用什么命令，传递什么参数。我们使用zrangebyscore命令来实现。记住-inf和inf，全称是infinity，分别表示无限小和无限大。由于我们不知道延迟队列中分数（即任务执行时间）的范围，所以可以直接使用-inf和inf。完整的命令如下。zrangescorekey-infinflimt01withscores还是有用的，那么ZSet底层是怎么实现的呢？ZipList上面已经说了，就不赘述了。让我们谈谈SkipList。6.2原理6.2.1SkipListSkipList存在于zset(SortedSet)的结构中，如下：structzset{//dictionarydict*dict;//skiplistzskiplist*zsl;}SkipList的结构如下：structzskiplist{//headernodeAndtabletailnodestructzskiplistNode*header,*tail;//表中的节点数unsignedlonglength;//表中层数最大的节点的层数intlevel;}我不知道大家有没有想过，为什么Redis用SkipList来实现ZSet而不是数组呢？首先，如果ZSet存储在数组中，由于ZSet中存储的元素是有序的，存储时需要将元素放到数组中对应的位置。这样会造成对数组的频繁增删改查，而频繁的增删改查在数组中效率不高，因为涉及到数组元素的移动。如果元素插入到第一个位置，则所有后续元素都将被移动。所以为了应对频繁的增删改查，我们需要用到链表。但是，随着链表中元素个数的增加，也会出现同样的问题。虽然增删改查效率提高了，但是查询效率变低了，因为查询元素会从头到尾遍历链表。所以如果有什么办法可以提高链表的查询效率，那就太好了。于是跳表诞生了。基于单向链表，从第一个节点开始，每隔一个节点进行索引。其实也是单链表。只是中间省略了节点。比如在抽象索引为14791317之后有一个单链表13457891013161718，如果要查询16，只需要遍历到索引中的13层，然后根据13(real链表节点的地址)中存储的下层节点，此时只需要再遍历两个节点，找到值为16的节点。所以我们可以重新定义跳转表。链表加多级索引的结构意味着跳表在跳表中，查询任意一条数据的时间复杂度为O(logn)。时间复杂度与二分查找相同。换句话说，二分查找是用单向链表实现的。但这也是一种用空间换取时间的想法，并不是免费的。End这里简单说一下Redis的基本数据结构及其底层原理。接下来的几篇文章应该会讲讲Redis的高可用以及对应的解决方案。感兴趣的可以继续关注。公众号会比较其他平台先更新。
