【中间件开发】Redis存储原理与数据模型
文章目录
前言
本文通过redis的数据模型引入了redis线程结构、string和跳表的底层实现。
1. redis是不是单线程？
redis的命令处理（核心线程）是在一个单线程中的。但是在其他任务中是开启了对应线程的。
1.1 命令处理为什么是单线程？
单线程具有局限性：
- 不能有耗时操作，CPU运算和阻塞IO
- 对于redis而言会影响性能
redis中的io密集型或cpu密集型：
- io密集型
- 磁盘io：fork进程，在子进程中持久化 & 异步刷盘
- 网络io：需要服务多个客户；reactor网络模型；数据请求或返回数据量大；开启io多线程
- cpu密集型
- 分治：将一个操作量大的问题，批量解决。将耗时问题，批量解决。
- 数据结构切换：因为redis是内存数据库，需要根据具体情况切换时间快或空间少的方案。
- 渐进式数据迁移：rehash
为什么不采用多线程：
- 加锁复杂，加锁的粒度不好控制。比如MySQL中的MVCC机制，只是在B+树中就需要提供多种加锁方案。
- 频繁CPU上下文切换，抵消多线程的优势。（都是内存中数据）
1.2 单线程为什么快？
采用了高效机制：
- 内存数据库：磁盘（一次磁盘io 10ms）比内存（100ns）要慢10万倍
- 数据组织方式：hashtable --> 在扩容或者缩容的过程中可能需要rehash
- 数据结构高效：在执行效率与空间占用保持平衡。
- reactor网络模型
做了一些优化：
- 分治
- 耗时阻塞操作，在其他线程处理
- 对象类型采用不同数据结构
hashtable：
前置概念：
负载因子 = used / size = 数组元素个数 / 数组长度
（负载因子越小，冲突越小；负载因子越大，冲突越大；）
redis的的负载因子为1
负载因子大于1时，发生扩容。也就是size * 2。
负载因子小于0.1，发生缩容。规则为恰好包含used的2^n
假如此时数组存储元素个数为 9，恰好包含该元素的就是
2^4，也就是 16；
渐进式rehash（此时不会发生扩缩容）：
- 分治：将rehash分到之后的每步增删改查当中。
- 在redis不忙的时候，设计一个定时器，每次最大执行1ms，每次步长100个数组槽位。
2. string的三种编码方式：int，raw，embstr
用int来存储不用存储’\0’。
2.1 柔性数组
定义：
- 结构体
- 结构体最后
- 结构体除了柔性数组必须包含其他成员
struct __attribute__ ((__packed__)) sdshdr16 {
uint16_t len;
uint16_t alloc;
unsigned char flags;
char buf[];
}
char * sds = (char *) malloc(sdshdr16 + 128);
sds + sizeof(sdshdr16);
// 当前柔性数组占128字节，而且包含头部信息
2.2 string为什么用64个字节作为分界线？
当字符串小于44字节，选择embstr编码，大于44字节，选择raw编码。
embstr是嵌入到redisObject中，而raw是在redisObject中维持一个指向堆上的资源。
内存分配器都是按照2^n来进行分配资源的，同时cpu cache line最小访问单位是64字节，所以选择了64作为分界线。
// 占用16字节
typedef struct redisObject {
unsigned type:4;
unsigned enconding:4;
unsigned lru:LRU_BITS;
int refcount;
void *ptr;
}robj;
// 64字节需要用sdshdr8来存，占3字节
struct __attribute__ ((__packed__)) sdshdr8 {
uint8_t len;
uint8_t alloc;
unsigned char flags;
char buf[];
}
buf可用空间：64-16-3-1=44；最后减一是为了兼容C的字符串函数。
3. 跳表的实现
跳表是一个（多层级有序链表）。
3.1 理想跳表
每隔一个节点生成一个层级节点；模拟二叉树结构，以此达到搜索时间复杂度O(logn)。空间换时间。
3.2 概率跳表
当对理想跳表进行DML操作，很有可能改变跳表结构。所以数学家提出用概率的方法来优化；
从每一个节点出发，每增加一个节点都有1/2的概率增加一个层级， 1/4的概率增加两个层级， 1/8的概率增加 3 个层级，以此类推；经过证明，当数据量足够大（128）时，通过概率构造的跳表趋向于理想跳表，并且此时如果删除节点，无需重构跳表结构，此时依然趋向于理想跳表
3.3 redis跳表
redis会限制跳表的最高层级（32）。让跳表结构变扁平。
4 redis的多线程原理
当多个客户端连接到服务端，并发送多个命令。reactor网络会分发这些任务到不同线程。
每次的任务流程：读取数据（read） -> 解码（decode） -> 处理（compute） -> 编码（encode） -> 发送数据（send） 。
多线程的运行方式：下面开启了4条线程。主线程完成compute，其他的任务分发给其他线程。
总结
本文总结了redis的对象编码的数据结构，详细解释了string类型和zset的跳表的编码方式。其次阐述了redis的线程结构和存储原理。
参考链接：
https://github.com/0voice
原文地址：https://blog.csdn.net/Morso/article/details/144378088
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！