Redis原理对象的数据结构SDSInsetDictZipL

　　Redis数据结构
　　1。SDS
　　Redis是用C语言写的，但是对于Redis的字符串，却不是C语言中的字符串（即以空字符’’结尾的字符数组），它是自己构建了一种名为简单动态字符串（simpledynamicstring，SDS）的抽象类型，并将SDS作为Redis的默认字符串表示
　　因为C语言字符串存在很多问题：获取字符串长度的需要通过运算非二进制安全不可修改
　　例如，我们执行命令：127。0。0。1：6379setnamezhangsanok复制代码
　　那么Redis将在底层创建两个SDS，其中一个是包含name的SDS，另一个是包含zhangsan的SDS。1。1SDS是什么
　　Redis是C语言实现的，其中SDS是一个结构体，源码如下：
　　例如，一个包含字符串name的sds结构如下：第一次分配时并不会分配多余空间
　　SDS之所以叫做动态字符串，是因为它具备动态扩容的能力，例如一个内容为hi的SDS：
　　假如我们要给SDS追加一段字符串，Amy，这里首先会申请新内存空间：
　　如果新字符串小于1M，则新空间为扩展后字符串长度的两倍1；
　　如果新字符串大于1M，则新空间为扩展后字符串长度1M1。称为内存预分配。
　　1。2SDS的优点获取字符串长度的时间复杂度为O（1）支持动态扩容支持内存预分配，减少用户线程与内核线程交互次数二进制安全
　　一般来说，SDS除了保存数据库中的字符串值以外，SDS还可以作为缓冲区（buffer）：包括AOF模块中的AOF缓冲区以及客户端状态中的输入缓冲区2。Inset
　　intset是set集合的一种实现方式，基于整数数组来实现，并且具备长度可变、有序等特征。2。1Inset是什么？
　　结构如下：
　　其中的encoding包含三种模式，表示存储的整数大小不同：
　　为了方便查找，Redis会将intset中所有的整数按照升序依次保存在contents数组中，结构如图：
　　现在，数组中每个数字都在int16t的范围内，因此采用的编码方式是INTSETENCINT16，每部分占用的字节大小为：encoding：4字节（可以理解为标识每个元素的类型）length：4字节contents：2字节36字节2。2inset自动升级
　　我们向该其中添加一个数字：50000，这个数字超出了int16t的范围，intset会自动升级编码方式到合适的大小。以当前案例来说流程如下：升级编码为INTSETENCINT32，每个整数占4字节，并按照新的编码方式及元素个数扩容数组倒序依次将数组中的元素拷贝到扩容后的正确位置将待添加的元素放入数组末尾最后，将inset的encoding属性改为INTSETENCINT32，将length属性改为4
　　那么如果我们删除掉刚加入的int32类型时，会不会做一个降级操作呢？
　　不会。主要还是减少开销的权衡
　　源码如下：
　　2。3总结：
　　Intset可以看做是特殊的整数数组，具备一些特点：Redis会确保Intset中的元素唯一、有序具备类型升级机制，可以节省内存空间底层采用二分查找方式来查询3。Dict
　　我们知道Redis是一个键值型（KeyValuePair）的数据库，我们可以根据键实现快速的增删改查。而键与值的映射关系正是通过Dict来实现的。是set和hash的实现方式之一3。1Dict是什么？
　　Dict由三部分组成，分别是：哈希表（DictHashTable）、哈希节点（DictEntry）、字典（Dict）
　　当我们向Dict添加键值对时，Redis首先根据key计算出hash值（h），然后利用hsizemask来计算元素应该存储到数组中的哪个索引位置。我们存储k1v1，假设k1的哈希值h1，则131，因此k1v1要存储到数组角标1位置。
　　注意这里还有一个指向下一个哈希表节点的指针，我们知道哈希表最大的问题是存在哈希冲突，如何解决哈希冲突，有开放地址法和链地址法。这里采用的便是链地址法，通过next这个指针可以将多个哈希值相同的键值对连接在一起，用来解决哈希冲突。
　　Dict由三部分组成，分别是：哈希表（DictHashTable）、哈希节点（DictEntry）、字典（Dict）
　　3。2深入理解哈希算法：Redis计算哈希值和索引值方法如下：1、使用字典设置的哈希函数，计算键key的哈希值hashdicttypehashFunction（key）；2、使用哈希表的sizemask属性和第一步得到的哈希值，计算索引值indexhashdictht〔x〕。sizemask；复制代码解决哈希冲突：这个问题上面我们介绍了，方法是链地址法。通过字典里面的next指针指向下一个具有相同索引值的哈希表节点。扩容和收缩：当哈希表保存的键值对太多或者太少时，就要通过rerehash（重新散列）来对哈希表进行相应的扩展或者收缩。具体步骤：计算新hash表的realeSize，值取决于当前要做的是扩容还是收缩：如果是扩容，则新size为第一个大于等于dict。ht〔0〕。used1的2n如果是收缩，则新size为第一个小于等于dict。ht〔0〕。used的2n（不得小于4）按照新的realeSize申请内存空间，创建dictht，并赋值给dict。ht〔1〕设置dict。rehashidx0，标示开始rehash将dict。ht〔0〕中的每一个dictEntry都rehash到dict。ht〔1〕将dict。ht〔1〕赋值给dict。ht〔0〕，给dict。ht〔1〕初始化为空哈希表，释放原来的dict。ht〔0〕的内存将rehashidx赋值为1，代表rehash结束在rehash过程中，新增操作，则直接写入ht〔1〕，查询、修改和删除则会在dict。ht〔0〕和dict。ht〔1〕依次查找并执行。这样可以确保ht〔0〕的数据只减不增，随着rehash最终为空触发扩容的条件：服务器目前没有执行BGSAVE命令或者BGREWRITEAOF命令，并且负载因子大于等于1。服务器目前正在执行BGSAVE命令或者BGREWRITEAOF命令，并且负载因子大于等于5。
　　ps：负载因子哈希表已保存节点数量哈希表大小。渐进式rehash
　　什么叫渐进式rehash？也就是说扩容和收缩操作不是一次性、集中式完成的，而是分多次、渐进式完成的。如果保存在Redis中的键值对只有几个几十个，那么rehash操作可以瞬间完成，但是如果键值对有几百万，几千万甚至几亿，那么要一次性的进行rehash，势必会造成Redis一段时间内不能进行别的操作。所以Redis采用渐进式rehash，这样在进行渐进式rehash期间，字典的删除查找更新等操作可能会在两个哈希表上进行，第一个哈希表没有找到，就会去第二个哈希表上进行查找。但是进行增加操作，一定是在新的哈希表上进行的。3。3总结：
　　Dict的结构：类似java的HashTable，底层是数组加链表来解决哈希冲突Dict包含两个哈希表，ht〔0〕平常用，ht〔1〕用来rehash
　　Dict的伸缩：当LoadFactor大于5或者LoadFactor大于1并且没有子进程任务时，Dict扩容当LoadFactor小于0。1时，Dict收缩扩容大小为第一个大于等于used1的2n收缩大小为第一个大于等于used的2nDict采用渐进式rehash，每次访问Dict时执行一次rehashrehash时ht〔0〕只减不增，新增操作只在ht〔1〕执行，其它操作在两个哈希表4。ZipList
　　ZipList是一种特殊的双端链表，由一系列特殊编码的连续内存块组成。可以在任意一端进行压入弹出操作，并且该操作的时间复杂度为O（1）。4。1ZipList是什么？
　　zlbytes：字段的类型是uint32t，这个字段中存储的是整个ziplist所占用的内存的字节数
　　zltail：字段的类型是uint32t，它指的是ziplist中最后一个entry的偏移量。用于快速定位最后一个entry，以快速完成pop等操作
　　zllen：字段的类型是uint16t，它指的是整个ziplit中entry的数量。这个值只占2bytes（16位）：如果ziplist中entry的数目小于65535（2的16次方），那么该字段中存储的就是实际entry的值。若等于或超过65535，那么该字段的值固定为65535，但实际数量需要一个个entry的去遍历所有entry才能得到。
　　zlend是一个终止字节，其值为全F，即0xff。ziplist保证任何情况下，一个entry的首字节都不会是2554。2ZipListEntry
　　ZipList中的Entry并不像普通链表那样记录前后节点的指针，因为记录两个指针要占用16个字节，浪费内存。而是采用了下面的结构：
　　previousentrylength：前一节点的长度，占1个或5个字节。如果前一节点的长度小于254字节，则采用1个字节来保存这个长度值如果前一节点的长度大于254字节，则采用5个字节来保存这个长度值，第一个字节为0xfe，后四个字节才是真实长度数据encoding：编码属性，记录content的数据类型（字符串还是整数）以及长度，占用1个、2个或5个字节contents：负责保存节点的数据，可以是字符串或整数
　　第一种情况：一般结构
　　prevlen：前一个entry的大小，编码方式见下文；
　　encoding：不同的情况下值不同，用于表示当前entry的类型和长度；
　　entrydata：真是用于存储entry表示的数据；
　　第二种情况：在entry中存储的是int类型时，encoding和entrydata会合并在encoding中表示，此时没有entrydata字段；
　　redis中，在存储数据时，会先尝试将string转换成int存储，节省空间；此时entry结构：prevlen编码
　　当前一个元素长度小于254（255用于zlend）的时候，prevlen长度为1个字节，值即为前一个entry的长度，如果长度大于等于254的时候，prevlen用5个字节表示，第一字节设置为254，后面4个字节存储一个小端的无符号整型，表示前一个entry的长度；prevlenfrom0to253encodingentry长度小于254结构0xFE4bytesunsignedlittleendianprevlenencodingentry长度大于等于254复制代码encoding编码
　　encoding的长度和值根据保存的是int还是string，还有数据的长度而定；
　　前两位用来表示类型，当为11时，表示entry存储的是int类型，其它表示存储的是string；
　　存储string时：
　　00xxxxxx：此时encoding长度为1个字节，该字节的后六位表示entry中存储的string长度，因为是6位，所以entry中存储的string长度不能超过63；
　　01xxxxxxxxxxxxxx此时encoding长度为两个字节；此时encoding的后14位用来存储string长度，长度不能超过16383；
　　10000000xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx此时encoding长度为5个字节，后面的4个字节用来表示encoding中存储的字符串长度，长度不能超过2321；
　　存储int时：
　　11000000encoding为3个字节，后2个字节表示一个int16；
　　11010000encoding为5个字节，后4个字节表示一个int32；
　　11100000encoding为9个字节，后8字节表示一个int64；
　　11110000encoding为4个字节，后3个字节表示一个有符号整型；
　　11111110encoding为2字节，后1个字节表示一个有符号整型；
　　1111xxxxencoding长度就只有1个字节，xxxx表示一个012的整数值；
　　11111111zlend4。3ZipList的连锁更新问题ZipList的每个Entry都包含previousentrylength来记录上一个节点的大小，长度是1个或5个字节：如果前一节点的长度小于254字节，则采用1个字节来保存这个长度值如果前一节点的长度大于等于254字节，则采用5个字节来保存这个长度值，第一个字节为0xfe，后四个字节才是真实长度数据现在，假设我们有N个连续的、长度为250253字节之间的entry，因此entry的previousentrylength属性用1个字节即可表示，如图所示：
　　ZipList这种特殊情况下产生的连续多次空间扩展操作称之为连锁更新（CascadeUpdate）。新增、删除都可能导致连锁更新的发生。虽然发生的条件非常苛刻，但不代表不会发生4。4总结：
　　ZipList特性：压缩列表的可以看做一种连续内存空间的双向链表列表的节点之间不是通过指针连接，而是记录上一节点和本节点长度来寻址，内存占用较低如果列表数据过多，导致链表过长，可能影响查询性能增或删较大数据时有可能发生连续更新问题5。QuickList5。1QuickList是什么？
　　ZipList虽然节省内存，但申请内存必须是连续空间，但是我们要存储大量数据，内存中碎片比较多，很难找到一块大的连续空间。于是，大数据量下，内存申请效率低成了ziplist的最大问题，而quickList就是为了帮助zipList摆脱困境的。为了缓解内存申请效率低的问题，QuickList提供了可限制ZipList的最大节点数和每个entry的大小的方式。那么对于大数据量，我们可以采用分片的思想，存储在多个ZipList中，而QuickList可以将这些ZipList作为节点连接起来。
　　为了避免QuickList中的每个ZipList中entry过多，Redis提供了一个配置项：listmaxziplistsize来限制。如果值为正，则代表ZipList的允许的entry个数的最大值如果值为负，则代表ZipList的最大内存大小，分5种情况：1：每个ZipList的内存占用不能超过4kb2：每个ZipList的内存占用不能超过8kb3：每个ZipList的内存占用不能超过16kb4：每个ZipList的内存占用不能超过32kb5：每个ZipList的内存占用不能超过64kb
　　其默认值为2：
　　以下是QuickList的和QuickListNode的结构源码：
　　5。2QuickList内存布局
　　5。3总结：
　　QuickList的特点：是一个节点为ZipList的双端链表节点采用ZipList，解决了传统链表的内存占用问题控制了ZipList大小，解决连续内存空间申请效率问题中间节点可以压缩，进一步节省了内存6。SkipList
　　跳跃表结构在Redis中的运用场景只有一个，那就是作为有序列表（Zset）的使用。跳跃表的性能可以保证在查找，删除，添加等操作的时候在对数期望时间内完成，这个性能是可以和平衡树来相比较的，而且在实现方面比平衡树要优雅，这就是跳跃表的长处。跳跃表的缺点就是需要的存储空间比较大，属于利用空间来换取时间的数据结构6。1SkipList是什么？
　　SkipList（跳表）首先是链表，但与传统链表相比有几点差异：元素按照升序排列存储节点可能包含多个指针，指针跨度不同。
　　6。2SkipListNode结构ele字段，持有数据，是sds类型score字段，其标示着结点的得分，结点之间凭借得分来判断先后顺序，跳跃表中的结点按结点的得分升序排列。backward指针，这是原版跳跃表中所没有的。该指针指向结点的前一个紧邻结点。level字段，用以记录所有结点（除过头节点外）；每个结点中最多持有32个zskiplistLevel结构。实际数量在结点创建时，按幂次定律随机生成（不超过32）。每个zskiplistLevel中有两个字段forward字段指向比自己得分高的某个结点（不一定是紧邻的），并且，若当前zskiplistLevel实例在level〔〕中的索引为X，则其forward字段指向的结点，其level〔〕字段的容量至少是X1。这也是上图中，为什么forward指针总是画的水平的原因。span字段代表forward字段指向的结点，距离当前结点的距离。紧邻的两个结点之间的距离定义为1。6。3skiplist与平衡树、哈希表的比较
　　skiplist和各种平衡树（如AVL、红黑树等）的元素是有序排列的，而哈希表不是有序的。因此，在哈希表上只能做单个key的查找，不适宜做范围查找。所谓范围查找，指的是查找那些大小在指定的两个值之间的所有节点。
　　在做范围查找的时候，平衡树比skiplist操作要复杂。在平衡树上，我们找到指定范围的小值之后，还需要以中序遍历的顺序继续寻找其它不超过大值的节点。如果不对平衡树进行一定的改造，这里的中序遍历并不容易实现。而在skiplist上进行范围查找就非常简单，只需要在找到小值之后，对第1层链表进行若干步的遍历就可以实现。
　　平衡树的插入和删除操作可能引发子树的调整，逻辑复杂，而skiplist的插入和删除只需要修改相邻节点的指针，操作简单又快速。
　　从内存占用上来说，skiplist比平衡树更灵活一些。一般来说，平衡树每个节点包含2个指针（分别指向左右子树），而skiplist每个节点包含的指针数目平均为1（1p），具体取决于参数p的大小。如果像Redis里的实现一样，取p14，那么平均每个节点包含1。33个指针，比平衡树更有优势。
　　查找单个key，skiplist和平衡树的时间复杂度都为O（logn），大体相当；而哈希表在保持较低的哈希值冲突概率的前提下，查找时间复杂度接近O（1），性能更高一些。所以我们平常使用的各Map或dictionary结构，大都是基于哈希表实现的。
　　从算法实现难度上来比较，skiplist比平衡树要简单得多。6。4总结：
　　SkipList的特点：跳跃表是一个双向链表，每个节点都包含score和ele值节点按照score值排序，score值一样则按照ele字典排序每个节点都可以包含多层指针，层数是1到32之间的随机数不同层指针到下一个节点的跨度不同，层级越高，跨度越大增删改查效率与红黑树基本一致，实现却更简单7。RedisObject7。1RedisObject是什么？
　　Redis中的任意数据类型的键和值都会被封装为一个RedisObject，也叫做Redis对象
　　从Redis的使用者的角度来看，个Redis节点包含多个database（非cluster模式下默认是16个，cluster模式下只能是1个），而一个database维护了从keyspace到objectspace的映射关系。这个映射关系的key是string类型，value可以是多种数据类型，比如：string，list，hash、set、sortedset等。我们可以看到，key的类型固定是string，而value可能的类型是多个。
　　从Redis内部实现的度来看，database内的这个映射关系是用个dict来维护的。dict的key固定用种数据结构来表达就够了，这就是动态字符串sds。而value则比较复杂，为了在同个dict内能够存储不同类型的value，这就需要个通的数据结构，这个通用的数据结构就是robj，全名是redisObject。
　　！
　　type：占4bit，五个取值类型，表示对象类型String，Hash，List，set，zset。encoding：占4bit，十一种编码方式lru：占用3字节，记录最后一次被访问的时间，主要用于lru算法，最近最少使用refcount：占用4字节，引用计数器，无人用就回收ptr：占用8字节，只想存放实际数据的空间
　　redis的头部占用16字节7。2encoding取值：
　　Redis中会根据存储的数据类型不同，选择不同的编码方式，共包含11种不同类型：
　　编号
　　编码方式
　　说明
　　0hrOBJENCODINGRAW
　　raw编码动态字符串
　　1hrOBJENCODINGINT
　　long类型的整数的字符串
　　2hrOBJENCODINGHT
　　hash表（字典dict）
　　3hrOBJENCODINGZIPMAP
　　已废弃
　　4hrOBJENCODINGLINKEDLIST
　　双端链表
　　5hrOBJENCODINGZIPLIST
　　压缩列表
　　6hrOBJENCODINGINTSET
　　整数集合
　　7hrOBJENCODINGSKIPLIST
　　跳表
　　8hrOBJENCODINGEMBSTR
　　embstr的动态字符串
　　9hrOBJENCODINGQUICKLIST
　　快速列表
　　10hrOBJENCODINGSTREAM
　　Stream流7。3五种数据结构
　　Redis中会根据存储的数据类型不同，选择不同的编码方式。每种数据类型的使用的编码方式如下：
　　数据类型
　　编码方式
　　OBJSTRING
　　int、embstr、raw
　　OBJLIST
　　LinkedList和ZipList（3。2以前）、QuickList（3。2以后）
　　OBJSET
　　intset、HT
　　OBJZSET
　　ZipList、HT、SkipList
　　OBJHASH
　　ZipList、HT