本文内容的思维导图如下：1.简介及应用语言API。其常用的类型主要有String、List、Hash、Set、ZSet。这五种Redis在互联网公司一般有以下应用：String：缓存，限流，计数器，分布式锁，分布式SessionHash：存储用户信息，用户首页访问，组合查询List：微博关注者的时间线列表，简单queueSet：喜欢，不喜欢，tags，友情Zset：排行榜比如电商大促的时候，为了保证系统的稳定，会采用一些特殊的设计，库存的扣减可以考虑如下设计：上图中直接在Redis中扣除库存，记录日志后，通过Worker同步到数据库。在设计Worker的同步时，需要考虑并发处理和重复处理的问题。从上面的应用场景可以看出Redis是非常高效和稳定的，那么Redis的底层是如何实现的呢？2、Redis对象redisObject当我们执行sethelloworld命令时，会有如下数据模型：dictEntry：Redis为每个key-value键值对分配一个dictEntry，其中包含key和val指针，next指向接下来dictEntry就形成了一个链表，这个指针可以将多个具有相同哈希值的键值对链接在一起，从而解决哈希冲突问题（链地址法）。sds：键“hello”存储在SDS（SimpleDynamicString）中，后面会详细介绍。redisObject：值val"world"存储在redisObject中。其实redis常用的5种类型都存储在redisObject中；而redisObject中的type字段表示Value对象的类型，ptr字段指向对象所在的地址。redisObject对象非常重要。Redis对象的类型、内部编码、内存回收、共享对象等功能都需要redisObject支持。这样设计的好处是，可以根据不同的使用场景，为常用的5种类型设置多种不同的数据结构实现，从而优化对象在不同场景下的使用效率。无论是dictEntry对象，还是redisObject或SDS对象，都需要内存分配器（如jemalloc）来分配内存进行存储。jemalloc作为Redis默认的内存分配器，在减少内存碎片方面做得比较好。例如，在64位系统中，jemalloc将内存空间划分为三个范围：small、large、huge；每个范围被分成许多小的内存块单元；Redis存储数据时，会选择大小最合适的内存块存储。前面提到，Redis的每一个对象都由一个redisObject结构体表示，其ptr指针指向底层实现的数据结构，数据结构由encoding属性决定。比如我们执行如下命令获取存储“hello”对应的代码：redis的所有数据结构类型如下（重要，后面会用到）：3.String字符串对象的底层实现可以是int,raw,embstr（上表对应名称介绍）。embstr编码是通过调用一次内存分配函数来分配一个连续的空间，而raw则需要调用两次。Int编码的字符串对象和embstr编码的字符串对象在一定条件下会被转换为raw编码的字符串对象。embstr：<=39字节字符串。int：8字节长整型。raw：大于39字节的字符串。简单动态字符串（SDS），这种结构更像C++的String或者Java的ArrayList，长度是动态可变的：structsdshdr{//lengthofoccupiedspaceinbufintlen;//buf中剩余的可用空间lengthintfree;//dataspacecharbuf[];//''空字符结束};get:sdsrange---O(n)set:sdscpy—O(n)create:sdsnew---O(1)len:sdslen---O(1)常数复杂度获取字符串长度：因为SDS记录了len属性中的length，获取SDS长度的时间复杂度仅为O(1)。预空间分配：如果一个SDS被修改，有两种情况：SDS的长度（len的值）小于1MB，那么程序会分配一个与len属性大小相同的未使用空间，以及free和len属性值相同。比如SDS的len会变成15个字节，程序也会分配15个字节未使用的空间，SDS的buf数组实际长度会变成15+15+1=31个字节（多一个字节用户保存空字符）。如果SDS长度（len值）大于或等于1MB，程序将分配1MB的未使用空间。比如修改后SDS的len变为30MB，那么它的实际长度就是30MB+1MB+1byte。延迟释放空间：执行sdstrim(截取字符串)后，SDS不会立即释放多余的空间。如果下次进行拼接字符串操作，拼接的没有刚才释放的空间那么大，未使用的空间就派上用场了。通过惰性释放空间避免了在某些情况下操作字符串的内存重新分配操作。消除缓冲区溢出：在使用C字符串操作时，如果字符串长度增加（如strcat操作）而忘记重新分配内存，很容易造成缓冲区溢出；而SDS记录了长度，相应的操作可能会导致缓冲区溢出时，会自动重新分配内存，防止缓冲区溢出。4、ListList对象的底层实现是quicklist（快速列表，是ziplist压缩列表和linkedlist双端链表的结合）。Redis中的列表支持两端插入和弹出，可以获取指定位置（或范围）的元素，可以充当数组、队列、栈等。typedefstructlistNode{//前节点structlistNode*prev;//后节点structlistNode*next;//节点值void*value;}listNode;typedefstructlist{//表头节点listNode*head;//表尾节点??listNode*tail;//节点值复制函数void*(*dup)(void*ptr);//节点值释放函数void(*free)(void*ptr);//节点值比较函数int(*match)(void*ptr,void*key);//链表包含的节点数unsignedlonglen;}list;rpush:listAddNodeHead---O(1)lpush:listAddNodeTail---O(1)push:listInsertNode---O(1)index:listIndex---O(N)pop:ListFirst/listLast---O(1)llen:listLength---O(N)4.1linkedlist（双端链表）这种结构比较像Java的LinkedList，有兴趣的可以去看看源码。从图中可以看出，Redis的linkedlist双端链表有以下特点：节点有prev、next指针、头指针、尾指针，获取前节点、后节点、头节点的复杂度，和尾节点都是一样的。是O(1)。获取节点数的len属性也是O(1)。与双端链表相比，压缩链表可以节省内存空间，但修改或增删操作时的复杂度较高；因此，当节点数较少时，可以使用压缩列表；但当节点数较多时，使用双端链表还是比较划算的。4.2ziplist（压缩列表）当一个listkey只包含少量列表项，并且是一个小整数值或者长度比较短的字符串时，那么redis使用ziplist（压缩列表）作为listkey的底层实现.Ziplist是Redis为了节省内存而开发的。它是由一系列经过特殊编码的连续内存块组成的顺序数据结构（而不??是像双端链表那样每个节点都是一个指针）。具体结构比较复杂。有兴趣的读者可以看Redis哈希结构内存模型分析。在新版本中，list链表使用quicklist代替了ziplist和linkedlist：quickList是zipList和linkedList的混合体。它将linkedList分成section，每个section使用zipList进行紧凑存储，多个zipList使用双向指针串联起来。因为链表的额外空间比较高，prev和next指针会占用16个字节（64位系统的指针是8个字节），每个节点的内存都是单独分配的，会加剧内存的碎片化，影响内存管理效率。quicklist默认压缩深度为0，即不压缩。为了支持快速的push/pop操作，quicklist的前两个ziplist没有压缩，此时深度为1。为了进一步节省空间，Redis还会对ziplist进行压缩存储，使用LZF算法进行压缩。5、HashHash对象的底层实现可以是ziplist（压缩列表）或者hashtable（字典或者也叫哈希表）。只有同时满足以下两个条件时，Hash对象才会使用ziplist（压缩列表）：1.hash中的元素个数小于512；2、哈希中所有键值对的键值串长度均小于64字节。hashtable哈希表可以实现O(1)复杂度的读写操作，所以效率很高。源码如下：typedefstructdict{//type-specificfunctiondictType*type;//privatedatavoid*privdata;//hashtabledictththt[2];//rehashindex//当没有进行rehash时，valueis-1intrehashidx;/*rehashingnotinprogressifrehashidx==-1*///当前运行的安全迭代器数量initerators;/*numberofiteratorscurrentlyrunning*/}dict;typedefstructdict{//哈希表数组dictEntry**table;//哈希表大小unsignedlongsize;//哈希表大小掩码，用于计算索引值//始终等于size-1unsignedlongsizemask;//哈希表中已有的节点数unsignedlongused;}dicttht;typedefstructdictEntry{void*key;union{void*val;uint64_tu64;int64_ts64;}v;//指向下一个哈希表节点组成链表strucdictEntry*next;}dictEntry;typedefstructdictType{//计算哈希值的函数unsignedint(*hashFunction)(constvoid*key);//复制键函数void*(*keyDup)(void*privdata,constvoid*key);//复制值函数void*(*valDup)(void*privdata,constvoid*obj);//比较键函数int(*keyCompare)(void*privdata,constvoid*key1,constvoid*key2);//销毁键的函数void(*keyDestructor)(void*privdata,void*key);//销毁值的函数void(*valDestructor))(void*privdata,void*obj);}dictType;上面的源码可以简化成如下结构：这种结构类似于JDK7之前的HashMap，当两个或多个key分配给索引上的相同哈希数组当发生hash冲突时，Redis也使用链地址的方式来解决key冲突。即每个哈希表节点都有一个next指针，多个哈希表节点使用next指针组成单项链表。链地址法是将哈希值相同的对象组织成一个链表，放在哈希值对应的槽中。如果Redis中的字典使用hashtable作为底层实现，那么每个字典都会有两个哈希表，一个用于正常使用，一个用于rehash（重新散列）。随着哈希表的运行，键会逐渐增加或减少。为了让哈希表的负载因子保持在一个合理的范围内，Redis会对哈希表进行扩容或缩容（rehash），即将ht[0]中的所有键值对进行多次分割，逐渐重新哈希到ht[1]。6、SetSet集合对象的底层实现可以是intset（整数集合）或者hashtable（字典或者也叫哈希表）。intset(integerset)当一个set只包含整数且元素不多时，intset(integerset)将作为Set集合对象的底层实现。typedefstructintset{//编码方式uint32_tencoding;//集合包含的元素个数uint32_tlength;//数组int8_tcontents[];}intset;sadd:intsetAdd---O(1)smembers:intsetGetO(1)---O(N)srem:intsetRemove---O(N)slen:intsetlen---O(1)intset的底层实现是一个有序的、不重复的数组来保存集合元素。intset结构中整数数组的类型可以是16位、32位或64位。如果数组中的所有整数都是16位长度，如果加入一个新的32位整数，整个16位数组就会升级为32位数组。升级可以提高intset的灵活性，节省内存，但不可逆。7、ZSet的底层实现ZSet有序集合对象可以是ziplist（压缩列表）或skiplist（跳过列表）。当一个有序集合的元素数量较多或者其成员是比较长的字符串时，Redis会使用skiplist（跳表）作为ZSet对象的底层实现。typedefstructzskiplist{//头节点和尾节点structzskiplistNode*header,*tail;//表中的节点数unsignedlonglength;//表中层数最高的节点的层数intlevel;}zskiplist;typedefstructzskiplistNode{//成员对象robj*obj;//scoredoublescore;//backwardpointerstructzskiplistNode*backward;//layerstructzskiplistLevel{//forwardpointerstructzskiplistNode*forward;//span---指向的节点之间的距离前向指针和当前节点unsignedintspan;}level[];}zskiplistNode;zadd---zslinsert---平均O(logN)，最差O(N)zrem---zsldelete---平均O(logN)，最差O(N)zrank--zslGetRank---平均O(logN)，最差O(N)skiplist的搜索时间复杂度为LogN，可以类比平衡二叉树，但实现起来更简单。跳表（skiplist）是一种有序的数据结构，它通过在某个节点中维护多个指向其他节点的指针来达到快速访问节点的目的。
