Redis原理简述
Redis 有哪些特性
1. 特性
- key-value 型内存数据库
- 单线程——原子化操作
- 支持lua脚本
- 发布与订阅
- 可持久化
- 逐出与过期
- ……
2. 持久化
- RDB：经过压缩的二进制文件；fork子进程进行操作
- AOF：保存所有写命令；先写缓存再同步至AOF文件；文件过大时会触发AOF重写
3. 过期：key到达了TTL时间
- 惰性删除 - 读、写操作前判断
- 定期删除 - 在定时事件中删除
- 抽样删除：配置为定期删除时，每次只选择一部分key来判断是否已经过期
4. 逐出：执行write但内存达到上限时，强制将一些key删除
- 逐出范围：allkeys、volatile
- 逐出策略：LRU、random、ttl
- 每次写入前都会判断，逐出会阻塞请求
- 抽样删除：LRU和ttl都是抽样进行计算的
Redis 启动与初始化
Redis内部数据结构
- 对外暴露的数据结构：string、list、hash、set、sortedSet
- 内部数据结构：dict、robj、sds、ziplist、quicklist、skiplist、intset
- 关注点：存储效率、响应速度
dict
- 拉链法解决冲突（线性探测、多重哈希、公共溢出区……）
- entry的value是union类型，如果是uint64_t、int64_t或double类型时，value存储数据本身，其他类型时value是指向真实数据的指针
- 负载因子：used / size >= 1
- 增量式重哈希：将重哈希的过程分散到对哈希表的每一次操作中。保证每个请求的响应速度。
- 在 rehash 时，字典会同时使用两个哈希表，所以在这期间的所有查找、删除等操作，除了在 ht[0] 上进行，还需要在 ht[1] 上进行。插入操作直接在ht[1]上进行。
- 一个database中的所有key-value的映射、hash、sortedSet等
robj
- string的编码过程：
- 可以表示成long型——OBJ_ENCODING_INT：0-10000内共享对象，*ptr存储数值
- 大小小于44字节——OBJ_ENCODING_EMBSTR：把robj和sds放在连续内存值，减少内存碎片
- OBJ_ENCODING_RAW：即 sds
sds
- 可动态扩展内存
- 兼容传统C字符串
- 可存储任意二进制数据
- 有5中不同类型的header，不同长度的字符串使用不同的header
- 预分配空间：需要对sds扩容时，会分配比实际所需要的更多空间，减少内存重新分配
ziplist 压缩列表
- zlbytes：4字节，32位
- zlend：结束标志固定值255
- previous_entry_length：变长编码，可能为1个字节（前一节点长度小于254）或者5个字节（大于254）
- 相比于普通链表：没有双向指针，节省了空间；连续内存块，减少了内存碎片。
- 当节点数量较少时，hash使用ziplist实现。配置：hash-max-ziplist-entries、hash-max-ziplist-value。
quicklist——A doubly linked list of ziplists
- 支持压缩
- list-max-ziplist-size：控制每个ziplist的长度或大小
- 插入操作：
- 当前ziplist大小没有超限：直接插入到ziplist中
- 当前ziplist大小超限，插入位置在ziplist的两端，且相邻的ziplist大小没有超限：插入到相邻的ziplist中
- 当前ziplist大小超限，插入位置在ziplist的两端，且相邻的ziplist大小也超限了：新建ziplist
- 其他：将当前ziplist拆分为两个ziplist
skiplist – 跳表
文章来源：https://www.toymoban.com/news/detail-646734.html
- 查找时间复杂度：O(logN)
- 平均每个节点的层数1/(1-p)，即redis中平均每个节点包含1.33个指针
- redis中第一层是双向链表
- 跳表与平衡树、哈希表相比：
- 跳表和平衡树元素有序，适合做范围查找。哈希表只能做单个key查找
- 平衡树的范围查找比跳表复杂，需要进行中序遍历。
- 平衡树的插入和删除可能会导致子树的调整，比跳表复杂。
- 平衡树需要至少2个指针，比跳表多
- 平衡树实现算法比跳表复杂
- sortedSet实现：
- 数据较少时：ziplist实现，数据在前，score在后
- 数据较多时：zset实现，zset包含一个dict和一个skiplist
intset——整数有序集合
文章来源地址https://www.toymoban.com/news/detail-646734.html
- encoding会随着数据的添加而改变。创建时为2字节。
- 二分查找，O(logN)
- 插入时，先扩容，查找要插入的位置，再插入，O(N)
- set：初始为inset，直到插入非数字、数字范围超限或者inset中数字个数超限，转换为dict（数据存储在dict的key中，value为null）
到了这里，关于Redis原理简述的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
