Rdis五大数据类型实现原理
对于五大数据类型（String,list,Hash,St,Zst）实现原理，Rdis在底层用到了多种数据结构，通过数据结构来实现键值对，将数据结构创建了一个对象rdisObjct，根据对象的类型typ，为对象设置多种不同的数据结构，对象可以执行特定的命令。
本章主要涉及到的知识点有：
-rdisObjct的属性-五大数据类型编码注意：本章内容每一小节可单独学习，无论先后。
rdisObjct属性
学完本章中，读者需要回答：
1．Rdis底层数据结构如何实现？2．Rdis是如何回收内存？
Rdis的一个键值对，有两个对象，一个是键对象，一个是值对象，键总是一个字符串对象，而值可以是字符串、列表、集合等对象，Rdis中的值对象都是由rdisObjct结构来表示。
typdfstructrdisObjct{//表示类型：string,list,hash,st,zstunsigndtyp:4;//编码：比如字符串的编码有int编码，mbstr编码，raw编码unsigndncoding:4;//指向底层数据结构的指针，prt是个指针变量，存放地址，指向数据存储的位置void*ptr;//引用计数，类似java里的引用计数intrfcount;//记录最后一次被程序访问的时间unsigndlru:22;}robj
typ属性
rdisObjct对象的typ属性记录了对象的类型（string,list,hash,st,zst），可以通过typky命令来判断对象类型，从而区分rdis中ky-valu的类型
.0.0.1:sttstStringtstValuOK.0.0.1:lpushtstListtstValu1tstValu2tstValu(intgr).0.0.1:hmsttsthash1:tstvalu2:tstvalu2OK.0.0.1:saddtststtstvalu(intgr)1.0.0.1:zaddtstzst1tstvalu(intgr)1.0.0.1:typtstStringstring.0.0.1:typtstListlist.0.0.1:typtsthashhash.0.0.1:typtststst.0.0.1:typtstzstzst
prt和ncoding属性
rdisObjct对象的prt指针，存放数据的地址，指向对象底层的数据结构，通过它可以找到数据的位置，而数据结构由ncoding属性，也就是编码，由它来决定,可以通过objctncodingky命令查看一个值对象的编码。
.0.0.1
bjctncodingtstString
"mbstr".0.0.1bjctncodingtstList"quicklist".0.0.1bjctncodingtsthash"ziplist".0.0.1bjctncodingtstst"hashtabl".0.0.1bjctncodingtstzst"ziplist"
rfcount属性
由于C语言跟贴近操作系统，直接跟操作系统交互，命令执行响应比较快，所以Rdis选择C语言进行编写可以提高性能，但是C语言不具备自动回收内存功能，于是乎Rdis自己构建了一个内存回收机制。
创建一个新对象，rdisObjct对象中的rfcount属性就会加1，对象被一个新程序使用，调用incrRfCount函数进行加1，如果有对象不再被应用程序使用了，那么它就会调用dcrRfCount函数进行减1，当对象的引用计数值为0的时候，那么这个对象所占用的内存就会被释放。
从这里可以看出来，这其实就是Java虚拟机中引用计数的内存回收机制，在Java中这种回收机制不被使用，因为它不能解决循环引用的问题。循环引用举例：A引用B，B引用C，C引用A。Rdis通过在配置文件中修改相关的配置，来达到解决循环引用的问题，在Rdis的配置文件里，Windows的配置文件是rdis.windows.conf,Linux系统的配置文件是rdis.conf。在配置文件中有一个配置：maxmmory-policy，当内存使用达到最大值时，rdis使用的清楚策略，默认配置是noviction1）volatil-lru删除已有的过期时间的ky2）allkys-lru删除所有的ky）volatil-random已有过期时间的ky随机删除4）allkys-random随机删除ky5）volatil-ttl删除即将过期的ky6）noviction不删除任何ky，只是返回一个写错误，这个是默认选项对于整数值的字符串对象（例如：1,2,这种的）可实现内存共享。问题：什么是内存共享？定义：键不同，值相同。举例：输入命令stky,键为ky1，值为的字符串对象，接着输入命令stky2，键为ky2，值为的字符串对象。这个时候，有二个不同的键，一个相同的值。实现原理：键的值，指针指向一个有值的对象，被共享的值对象引用rfcount加1。局限性：判断两个对象是否相等需要消耗运算的额外的时间。整数值，判断操作复杂度低；普通字符串，判断复杂度相比较而已是高的；哈希、列表、集合和有序集合，判断的复杂度更高，所以内存共享只适用于整数值的字符串。
lru属性
Lru属性是rdisObjct记录对象最后一次被命令程序访问的时间，用来辅助lru算法删除过期内存的。在Rdis配置文件中有三个配置，最大内存配置maxmmory，触发数据淘汰后的淘汰策略maxmmory_policy，随机采样的精度maxmmory_sampls。当有条件符合配置文件中三个配置的时候，继续往Rdis中加ky时，会触发执行lru策略，进行内存清除。最近最少使用，lru算法根据数据的历史访问记录进行数据淘汰。
Lru策略的运行原理是数据插入到链表头部，当缓存数据被访问之后，数据会移到链表头，链表满的时候，链表尾部的数据会被丢弃。
rdis配置中的淘汰策略（maxmmory_policy）对应的值：-Noviction：缓存里的数据超过maxmmory值，这个时候如果客户端正在执行命令，会让内存分配，给客户端返回错误响应-allkys-lru：所有的ky都用LRU进行淘汰。-volatil-lru：LRU策略淘汰已经设置过过期时间的键。-allkys-random：随机淘汰使用的。-kyvolatil-random：随机淘汰已设置过过期时间的ky-volatil-ttl：只回收设置了过期时间的ky
从rdis缓存中淘汰数据，我们的需求是淘汰一些不可能被使用的数据，保留有些以后可能会频繁访问的数据，频繁访问的数据，将来被访问的可能性大很多，所以rdis它记录每个数据的最后一次访问时间（lru记录的时间），通过当前时间减去键值对象lru记录的时间，最后可以计算出最少空闲时间，最少空闲时间的数据是最有可能被访问到，这就是LRU淘汰策略的设计思想，是不是很棒。
举例说明：A数据每10s访问一次，B数据每5s访问一次，C数据每50s访问一次，
代表计算空闲时间的截止点。
~~~~~A~~~~~A~~~~~A~~~~A~~~~~A~~~~~A~~
~~B~~B~~B~~B~~B~~B~~B~~B~~B~~B~~B~~B~
~~~~~~~~~~C~~~~~~~~~C~~~~~~~~~C~~~~~~
预测被访问的概率是BAC。过期ky的删除策略有两种：惰性删除：每次获取键时，都检查键是否过期，过期的话，就删除该键；未过期，就返回该键。定期删除：每隔一段时间，进行一次检查，删除里面的过期键。
String编码
我们最常使用的rdis的一个数据类型就是String类型，实现单值缓存，分布式锁，计数器，分布式系统全局序列号等等功能。它的底层编码分为三种，int，raw或者mbstr。int编码：存储整数值(例如：1,2,)，当int编码保存的值不再是整数值，又或者值的大小超过了long的范围，会自动转化成raw。例如：(1,2,)-(a,b,c)mbstr编码：存储短字符串。它只分配一次内存空间，rdisObjct和sds是连续的内存，查询效率会快很多，也正是因为rdisObjct和sds是连续在一起，伴随了一些缺点：当字符串增加的时候，它长度会增加，这个时候又需要重新分配内存，导致的结果就是整个rdisObjct和sds都需要重新分配空间，这样是会影响性能的，所以rdis用mbstr实现一次分配而后,只允许读，如果修改数据，那么它就会转成raw编码，不再用mbstr编码了。raw编码：用来存储长字符串。它可以分配两次内存空间，一个是rdisObjct，一个是sds，二个内存空间不是连续的内存空间。和mbstr编码相比，它创建的时候会多分配一次空间，删除时多释放一次空间。版本区别：mbstr编码版本之间的区别：在rdis.2版本之前，用来存储9字节以内的数据，在这之后用来存储44字节以内的数据。raw编码版本之间的区别：和mbstr相反，rdis.2版本之前，可用来存储超过9字节的数据，.2版本之后，它可以存储超过44字节的数据。问题一：为什么是9字节？从上面可以得知，mbstr是一块连续的内存区域，由rdisObjct和sdshdr组成。mbstr最多占64字节场景：rdisObjct占16个字节
structRdisObjct{int4typ;//4bits,不同的rdis对象会有不同的数据类型(string、list、hash等)，typ记录类型，会用到4bits。int4ncoding;//4bits,存储编码形式，用4bits。int24lru;//24bits,用24bits记录对象的LRU信息int2rfcount;//4byts=2bits,引用计数器，用到2bitsvoid*ptr;//8byts，64-bitsystm,指针指向对象的具体内容，需要64bits}
计算：4+4+24+2+64=bits=16bytssdshdr占48字节
structsdshdr{unsigndintln;//4个字节unsigndintfr;//4个字节charbuf[];//假设buf里面是9个字节};if(ptr){mmcpy(sh-buf,ptr,ln);sh-buf[ln]=\0;//一个字节
sdshdr的大小为8+9+1=48那么一个mbstr最多占64字节：16+48（4+4+1+9）=64从2.4版本开始，rdis用jmalloc内存分配器，比glibc的malloc要好一些，省内存，jmalloc会分配8，16，2，64等类型字节的内存。mbstr最小为字节场景：从上面我们可以得知rdisObjct占16个字节，现在buf中取8字节。
structsdshdr{unsigndintln;//4个字节unsigndintfr;//4个字节charbuf[];//假设buf里面是8个字节};if(ptr){mmcpy(sh-buf,ptr,ln);sh-buf[ln]=\0;//一个字节
sdshdr的大小为4+4+8+1=17计算得出：16+17(4+4+1+8)=8,16,2都比字节小，所以最小分配64字节。通过对比：16+17(4+4+1+8)=16+48（4+4+1+9）=64当字符数大于8时，会分配64字节。当字符数小于9时，会分配64字节。这个默认9就是这样来的。问题二：为什么分界值由9字节会变成44字节？被暴打的回答是：REDIS_ENCODING_EMBSTR_SIZE_LIMIT值被换成了44了。
#dfinREDIS_ENCODING_EMBSTR_SIZE_LIMIT9#dfinREDIS_ENCODING_EMBSTR_SIZE_LIMIT44
正经的回答是：每个sds都有一个sdshdr，里面的ln和fr记录了这个sds的长度和空闲空间。
structsdshdr{unsigndintln;unsigndintfr;
用的unsigndint可以表示很大的范围，短的sds空间被浪费了(unsigndintln和unsigndintfr8个字节)
