redis

一. redis 实现原理

五种类型的键的底层实现数据结构

具体命令可参考命令

1. SDS( simple dynamic string) 简单动态字符串

   struct sdshdr{
   int len;
   int free;
   char buf[];
   }

2. 链表

   typedef struct listNode{
   struct listNode *prev;
   struct listNode *next;
   void *value;
   }listNode;
   
   typedef struct list{
   listNode *head;
   listNode *tail;
   unsigned long len;
   void *(*dup)(void *ptr);
   void (*free)(void *ptr);
   int (*match)(void *ptr,void *key);
   }

3. 字典

   Redis 的字典使用哈希表作为底层实现,一个哈希敷衍里面可以有多个节点,每个节点就保存了字典中的一个键值对;

   新添加一个键值对到字典里时,程序需要先根据键值对的键计算出哈希值和索引值,然后根据索引值,将包含新键值对的哈希表节点放到哈希表数组的指定索引上面.当有两个或以上数量的键被分配到哈希数组的同一个索引上面时,我们称为冲突.这里使用链地址法解决键冲突.

   • 哈希表

     typedef struct dictht{
     dictEntry **table;
     unsigned long size;
     unsigned long sizemask;
     unsigned long used;
     }

     sizemask 值和哈希值一起决定一个键应该被放到table数组的哪个索引上面.

   • 哈希表节点

     typedef struct dictEntry{
     void *key;
     union{
     void *val;
     uint64_tu64;
     int64_ts64;
     } v;
     struct dictEntry *next; //解决键冲突的问题
     } dictEntry;

   • 字典

     typedef struct dict{
     dictType *type; //类型特定函数
     void *privdata;//私有数据
     dictht ht[2];//哈希表
     int trehashidx;//索引
     } dict;

   • rehash(实际过程,是渐进式的)

     当哈希表中键值的数量太多或太少时,为了让哈希表的负载因子维持在一个合理的范围之内,程序需要对哈希表的大小进行相应的扩展或者收缩.

     1. 为字段的ht[1]哈希表分配空间,这个空间大小取决于要执行的操作,以及ht[0]当前包含的键值对数量

        1. 如果是扩展操作,那么大小为第一个大于等于ht[0].used*2的2的n次方
        2. 如果执行的是收缩操作,那么ht[1]的大小为第一个大于等于ht[0].used的2的n次方

     2. 将保存在ht[0]中的所有键值对rehash到ht[1]上面:rehash指重新计算键的哈希值和索引值,然后将键值对放置到ht[1]哈希表的指定位置上

     3. 将ht[0]释放空间,同时将ht[0]和ht[1]换位置

        何时进行扩展和收缩
        负载因子= ht[0].used(已保存的节点数量)/哈希表的大小

        当负载因子大于 5 (待确认),或<0.1 时

4. 跳跃表

   skiplist 是一种有序的数据结构,它通过在每个节点中维持多个指向其他节点的指针,从而达到快速访问节点的目的.
   redis在以下两个地方用到了跳跃表:

   1. 有序集合键 zset
   2. 在集群节点中用途内部数据结构

5. 整数集合

   intset 是集合键的底层实现之一,当一个集合只包含整数值元素,并且这个集合的元素数量不多时,Redis就会使用整数集合作为集合键的底层实现.

   127.0.0.1:6379> SADD numbers 1 3 5 6 7
   (integer) 5
   
   127.0.0.1:6379> OBJECT ENCODING numbers
   "intset"
   
   127.0.0.1:6379> sadd numbers 0943890384093845903845094385
   (integer) 1
   
   127.0.0.1:6379> smembers numbers
   1) "3"
   2) "0943890384093845903845094385"
   3) "7"
   4) "2"
   5) "6"
   6) "1"
   7) "9"
   8) "5"
   
   127.0.0.1:6379> OBJECT ENCODING numbers
   "hashtable"

   每当我们要将一个新元素添加到整数集合里面,并且新元素的类型比整数集合现有的所有元素的类型都要长时,整数集合需要先进行升级,然后才能将新元素添加到整数集合里面,请记住,这里不会降级的

   其是Redis保存整数值的集合抽象数据结构,它可以保存int16_t,int32_t,int64_t的整数值,并且保证集合中不会出现重复元素.

   typedef struct intset{
   uint32_t encoding;//编码方式 INTSET_ENC_INT16,INTSET_ENC_INT32,INTSET_ENC_INT64
   uint32_t length;//集合包含的元素数量
   int8_t contents[]; //保存元素的数组,数组中按值的大小从小到大有序排列,并且数组中不包含任何重复项;其真正的类型取决于encoding属性的值:
   }

6. 压缩列表
   ziplist,是列表键和哈希键的底层实现之一.当一个列表键只包含少量列表项,并且每个列表项要么就是小整数值,要么就是长度比较短的字符串,那么Redis就会使用压缩列表来做列表键的底层实现.

   127.0.0.1:6379> rpush kdf djf f df d f d f "sdf"
   (integer) 8
   
   127.0.0.1:6379> OBJECT ENCODING kdf
   "ziplist"

   压缩列表是为了节约内存而开发的,是由一系列特殊的连续内存块组成的顺序型数据结构.一个压缩列表可以包含任意多个节点,每个节点可以保存一个字节数组或者一个整数值.

对象处理机制以及数据库的实现原理

1. 导入

   1. Redis 基于这些数据结构创建一个对象系统,其包含 字符串,列表对象,哈希对象,集合对象和有序集合对象 五种类型的对象,每种对象都至少一种我们前面所介绍的数据结构.
   2. 使用对象的好处,我们可以针对不同的使用场景,为对象设置多种不同的数据结构pugmww而优化对象在不同场景下的使用效率.
   3. 对象系统基于引用计数技术的内存回收机制,当程序不再使用某个对象的时候,这个对象所战胜的内存就会被自动释放;另外,Redis还通过引用计数技术实现了对象共享机制,这一机制可以在适当的条件下,通过让多个数据库键共享同一个对象来节约内存.
   4. 对象带有访问时间记录信息,该信息可以用于计算数据库的空转时长 ,在服务器启用了maxmemory功能的情况下,空转时长较大的那些键可能会优先被服务器删除.

2. 对象的类型和编码 type

   Redis使用对象来表示数据库中的键值,每次我们在库中新创建一个键值对时,我们至少会创建两个对象,一个是键对象,另一个是值对象.

   127.0.0.1:6379> set name aaron
   OK
   127.0.0.1:6379> get name
   "aaron"
   127.0.0.1:6379> OBJECT ENCODING name
   "embstr"
   127.0.0.1:6379> type name
   string
   127.0.0.1:6379> OBJECT idletime name
   (integer) 46

   ---

   每一个对象都由一个redisObject结构表示,该结构中和保存数据有关的三个属性分别是type属性,encoding属性和ptr属性:

   typedef struct redisObject{
   unsigned type:4;
   unsigned encoding:4;
   void *ptr;//每日向底层实现数据结构的指针
   int refcount;//引用计数
   unsigned lru:22;//该对象最后一次被访问的时间
   }robj;

   type记录了对象的类型,这个属性的值有 string,list,hash,set,zset

3. 编码和底层实现 OBJECT ENCODING
   对象的ptr指针指向对象的底层实现数据结构,而这些数据结构由对象的encoding属性决定.也就是说这个对象使用了什么数据结构作为对象的底层实现,这个属性值可以是

   int (long 类型)
   embstr (embstr编码的简单动态字符串)
   raw (简单动态字符串)
   ht (字典)
   linkedlist (双端链表)
   ziplist (压缩链表)
   intset (整数集合)
   skiplist (跳跃链表和字典)

   每种类型对象都至少使用了两种不同的编码.

   string int/embstr/raw
   list ziplist/linkedlist
   hash ziplist/ht
   set  intset/ht
   zset  ziplist/skiplist

4. 数据共享 只共享0-9999的字符串对象

   127.0.0.1:6379> SET a 100
   OK
   127.0.0.1:6379> OBJECT refcount a
   (integer) 2
   127.0.0.1:6379> OBJECT refcount a
   (integer) 2
   127.0.0.1:6379> SET b 100
   OK
   127.0.0.1:6379> OBJECT refcount a
   (integer) 3
   127.0.0.1:6379>

单机数据库的实现

1. 在redisServer结构的db数组中,每个redisDb 结构代表一个数据库,启动服务器时,服务器会根据dbnum来决定应该创建多少个数据库:

   struct redisServer{
   ...
   redisDb *db;
   int dbnum;
   ...
   }redisClient

   客户端可以根据命令select来进行切换目标数据库

2. 数据库键空间

   是一个键值对数据库服务器,其中每个数据库都由一个redisDb结构表示,其中redisDb结构的dict字典保存了数据库中的所有键值对,我们称这个字典为 键空间
   typedef struct redisDb{
   dict *dict;
   dict *expires; key 是对象,value 是过期时间
   }redisDb

3. 设置生存时间或过期时间

   127.0.0.1:6379> set name wansong
   OK
   127.0.0.1:6379> expire name 10
   (integer) 1
   127.0.0.1:6379> get name
   "wansong"
   127.0.0.1:6379> get name
   (nil)

4. 数据库通知
   2.8 新版本中增加的功能,可以通过订阅给它的频道或者模式,来获知数据库中键的变化.及数据库中命令的执行情况.

RDB 持久化和 AOF 持久化的实现原理

RDB持久化功能,可以将Redis在内存中的数据库状态保存到磁盘里面,避免数据意外丢失.也可以根据服务器配置选项定期执行.
该功能可以将某个时间点上的数据库状态保存到一个RDB文件中.该文件是一个经过压缩的二进制文件,通过该文件可以还原生成RDB文件时的数据库状态.

1. RDB文件的创建与载入

   save 命令会阻塞Redis服务器进程,直到RDB文件创建完毕为止,在服务器进程阻塞期间,服务器不处理任务命令请求.

   bgsave background saving started 该命令会派生出一个子进程,然后由子进程负责创建RDB文件,服务器进程继续处理命令请求

   创建文件的实际工作由rdbSave函数完成,save和bgsave命令会以不同的方式调用这个函数.

   RDB文件的载入是自动的,当程序启动时会自动载入,另外注意AOF文件的更新频率通常比RDB高,所以:

   1. 如果服务器开启了AOF持久化功能,那么服务器会优先使用AOF文件还原数据库状态

   2. 只有在AOF持久化功能处于关闭状态时,服务器才会使用RDB文件来还原数据库状态.

      载入RDB文件的实际工作由rdbLoad函数完成;文件载入时服务器处于阻塞状态.

2. 自动间隔性保存

   可以通过save选项设置多个保存条件,但只要其中任意一个条件被满足,服务器就会执行bgsave.

   save 900 1 服务器900秒之内,对数据库进行至少一次修改,就进行bgsave

事件

Redis 基于 Reactor模式开发的网络事件处理器,称作 文件事件处理器 (File Event Handler)

1. 使用I/O多路复用程序来同时监听多个套接字,并根据目前执行的任务来为套接字关联不同的事件
2. 当被监听的套接字准备好执行连接应答,读取,写入,关闭 等操作时,与其对应的文件事件就会产生,这时1中注册好的事件处理器就来进行处理这些事件

时间事件 id/when/handlers

1. 定时事件
2. 周期性事件

事务实现原理 ACID

ServerCron函数

服务器 默认每100毫秒执行一次

1. 更新服务器时间缓存
2. 更新LRU时钟(如 Redis对象都会有一个LRU属性,这个属性保存了对象最后一次被命令访问的时间)
3. 更新服务器每秒执行命令的次数(INFO status)
4. 更新服务器内存峰值记录
5. 处理SIGTERM信号 每次运行时,程序会对服务器状态的shutdown_asap属性进行检查,看是否要关闭服务器
6. 管理客户端资源: 已超时 或 是否清理输出缓冲区
7. 管理数据库资源: 删除过期键,并在需要时 对字典进行收缩操作
8. 检查持久化操作的运行状态
9. 将AOF缓冲区的内容写入到AOF文件
10. 关闭异步客户端
11. 增加cronloops计数器的值

初始化过程

初始化服务器状态结构,载入配置选项,还原数据库状态,执行事件循环

订阅与发布实现原理

Lua 脚本功能的实现原理。

SORT 命令的实现原理。

慢查询日志的实现原理。 打开慢查询,查看日期 SLOWLOG GET

高并发如何做到

虽是单线程单进行,但 使用I/O多路复用(select/epoll,evport,kqueue)程序来同时监听多个套接字 的方式来处理命令请求,并与多个客户端进行通信.

二. redis 主要关注点

redis 为什么是单线程

redis 过期索引是如何做到的

1. redis 的存储结构

2. 删除策略

   * 定时删除:在设置键的过期时间的同时,创建一个定时器,让定时器在键的过期时间来临时,立即对键执行删除操作(对内存友好,最及时)
   * 定期删除:每一段时间,进行数据库过期索引的扫瞄,将已经过期的键 进行删除; 至于删除多少过期键和检查哪些数据库,都由算法决定
   * 惰性删除: 每次取键时,校验一下是否过期,若已经过期 就进行删除
   
   其实最终使用的是 定期和惰性 两个策略 配合实现

   redis 服务器配置

   redis 有哪些功能

   redis 如何Failover()

   哨兵（Sentinel）和复制（Replication）
   Sentinel可以管理多个Redis服务器，它提供了监控，提醒以及自动的故障转移的功能；Replication则是负责让一个Redis服务器可以配备多个备份的服务器

redis 目前流程的实施架构有哪些

1. 哨兵Sentinel,复制（replication）
2. 集群（cluster）

三. redis 应用场景

参考

1. Redis设计与实现