redis 底层数据结构实现原理：了解数据结构设计思想
redis 底层数据结构实现原理：了解数据结构设计思想redis的key可以是任意的数据类型，甚至可以是一个文件、音频、视屏。通过redis客户端把不同数据类型的key，传递给redis服务端，redis服务端把key转换成一个string对象即所有键都是string对象。redis客户端可以把任意类型字面量的key传给服务端redis无论是多线程版本还是老的单线程版本，最终执行命令都是单线程，所以就不能一次性把数据搬完，而是渐进式的一点点搬。同时存在2个hashtable怎么进行数据访问?`redis可以存储的数据结构
不同存储介质访问延迟- • 机械硬盘 10ms
- • 固态硬盘 100us
- • 内存条 150ns
- • 数组 链表
- • 计算key的hash值取余hashtable的大小得到索引位置，然后头插法或尾插法，将K V保存到链表中（redis使用的是头插法，因为热点数据放入缓存，访问链表头部节点就可以获取到，而不需要遍历整个链表，提高查询效率）
- • 数组中存储的都是指针数据，指向链表的头节点
- • 不同的key输入，可能会有相同的输出，那么就会产生hash冲突，通过链表法来解决冲突。
当链表越来越长，通过扩容的方式来减小链表长度
- • 开辟新的内存空间存放新的hashtable 长度是老的hashtable size的2倍
- • 将老的hashtable中的元素渐进式的搬到新的hashtable中，将原来的元素重新做hash计算并取模得到在新hashtable中的位置
- • 所有老的数据搬到新的上面来之后，把老的hashtable空间释放掉
渐进式的搬数据
在搬数据的时候，每次都是获取老的hashtable中的第一个hash槽，然后按照该槽上的链表顺序一个一个的去搬。
redis通过后台轮循事件，每次搬数据的时候默认获取前100个hash槽，一次性搬有限个，目的是为了降低主线程的卡顿时间。
redis无论是多线程版本还是老的单线程版本，最终执行命令都是单线程，所以就不能一次性把数据搬完，而是渐进式的一点点搬。
同时存在2个hashtable怎么进行数据访问?
- • 查询一个key，先访问老的hashtable，如果有则直接返回，如果没有，再访问新的hashtable。
- • 添加新的元素，放到新的数组中
`redis可以存储的数据结构
- • string
- • list
- • set
- • zset
- • hash
- • stream
redis客户端可以把任意类型字面量的key传给服务端
redis的key可以是任意的数据类型，甚至可以是一个文件、音频、视屏。通过redis客户端把不同数据类型的key，传递给redis服务端，redis服务端把key转换成一个string对象即所有键都是string对象。
redis string源码怎么设计的在c语言中用char[] data数组来表示一个字符串，比如char[] data="pingfanrenbiji\0"，c语言编译器还会在pingfanrenbiji后面加\0字符，作为字符串的结尾。但会有弊端，比如 data="dafasdasd\0dafadfa"，正巧里面有一些特殊字符会导致数据直接截断，后面的就会被丢弃。
redis不是这种方式，而是自定义了一个数据结构sds（simple dynamic string）
redis 3.2版本sds数据结构：
sds:
int len: 8
char[] buf="ping\0fan"
\0占一个字节
sds根据自定义长度来决定字符串是否结束，可以理解为这是一种二进制安全的数据结构。
int 占4个字节，无符号数据范围是2^32-1，这是几个亿的数据范围，在业务上根本不用上，所以有很大的内存空间的浪费。
redis 6.x sds数据结构
使用相对更小的空间去描述数据。
hdr是头部数据的意思，比如unsigned char flags;uint8_t len;这些都是头部数据，是用来描述真正业务数据的长度，不是真正的数据，而是一些描述信息。
char类型在c语言中占1个字节，在java中占2个字节。
真正的数据长度封装在了flags中
一个字节有8个bit位，其中后面5个bit位用来描述数据长度，前面3个bit作为数据类型。
Type
hisdshdr8
uint8_t代表占8个bit位一个字节。alloc是为了满足一种特殊的需求：
buffer数组一旦定义，空间大小不可变
在上面那个字符串的基础上追加bbbb，需要重新开辟一个内存空间，再把数据拷贝过来，然后再追加字符串，这是一般的方法，很浪费内存空间，在redis 3.版本的sds中定义了一个int free字段和redis 6.x版本的uint8_t alloc含义是一样的，有了该字段就可以适用不同长度需求。
redis 3.2版本sds数据结构：
sds:
int len: 6
int free: 0
char[] buf="pingfa\0"
追加一个1
pingfa -> pingfa1
redis会自动分配6 1=7 7*2=14即一次性开辟14个空间
buf[14]=pingfa1
用掉了7还剩7即free=7
sds:
int len: 7
int free: 7
buf[14]=pingfa1
再追加23
pingfa1-> pingfa123
变成了
sds:
int len: 9
int free: 5
buf[14]=pingfa123
这样的话，不需要重新分配内存空间，数据量比较大的情况下，直接追加，效率提升很明显。
alloc分配多少空间，减去使用的，就是剩下的free。
动态字符串，自动的去扩容。
char[] buf="pingfa123\0"
redis编译器自动加上\0字符，尽量兼容c语言本身的函数库。
通过redis源码了解数据库设计
底层数据结构
redisDb
- • dict *dict
字典数据结构和hashmap是同一种数据类型，只是不同语言的不同实现。
- • dict *expires
过期时间处理
- • dict *blocking_keys
阻塞API，比如BLPOP是list中的阻塞api
- • dict *ready_keys
阻塞的key，在收到消息时，做对应的处理
- • dict *watched_keys
事务相关的命令
dict
ht 就是hashtable，因为需要rehash，所以数组长度是2，一个是老的hashtable，另外一个是新的hashtable，新的是老的hashtable大小的2倍。如果没有rehash的话，只会用到其中一个。
rehashidx 是rehash到每个hash槽的一个索引。
元素个数超过hashtable本身数组容量，就会触发rehash，首先申请大一倍的内存空间，渐进式的把数据从老的hashtable中搬到新的hashtable中，搬完之后，将老的hashtable释放掉，ht[0]指向新的数组，h[1]指向null，回到正常状态。
dictType
键key通过hashFunction这个hash函数计算并取模hashtable size，得到hash槽的位置。
如果2个key hashcode一样，如果2个key不一样，则是hash冲突，使用链表关联起来，如果2个key一样，则会覆盖。
dictht
table指向了一个hash链表；sizemask是求模的一个优化;used是hashtable中有多少个元素。
dictEntry
union中是value的类型，同一时间只能用一个；比如val就是key-value键值对类型，redis底层会进一步封装成redisObject对象;next指向链表中的下一个节点。
redisObject
- • type 表示对象是什么类型，string、hash、list、set、zset，而type是什么取决于你使用什么样的api。
1、
value是整数、短字符串、长字符串，底层都是string类型。
set操作，底层就会封装成一个string对象。
2、
lpush操作，是list类型。list操作，底层会封装成一个list对象。
3、
hset操作，是hash类型。set操作，底层会封住成一个hash对象。
- • encoding
每种类型底层有不同的编码。相同类型，底层编码也可能不相同即在内存中使用不同的方式去存储。
整数的编码是int，长字符串的编码是raw，短字符串的编码是embstr。
hash value短字符串底层编码是ziplist，hash value长字符串底层编码是hashtable。
- • unsigned lru:LRU_BITS
内存淘汰算法
#define LRU_BITS 24
在内存中占24个bit位
- • int refcount
引用计数法，判断对象是否存活的一种算法。
redis是c语言写的，需要自己的管理内存，该值为0，则可以把这个对象回收掉。
- • void *ptr
这是指向内存区域的指针
看redis底层把数据存储在哪里？
redis底层最终会把100这个值封装成redisObject 通过encoding知道编码是int，确定编码之后，通过ptr找到真实的数据。
整数一般不会超过8个字节，java中最长是long类型占8个字节。
ptr指针在64位操作系统中占8个字节空间。
假设这个数据能用整型去表示，那也能用指针去表示，不让指针去存储真实的位置信息，而是直接存整数，是否可以？
ptr指向一个额外的内存空间，用额外的内存空间去存储整数的话，会导致什么问题？
- • 需要一个内存空间来存储数据
- • 先找到redisObject，通过ptr指针做一次io操作才能拿到真实的数据
如果直接用指针存储数据，有什么好处呢？
- • 减少了额外的内存空间来存储数据
- • 拿到redisObject中的ptr可以直接得到数据了，就不需要再通过ptr指针从内存中获取真实数据了，减少了一次io操作
