Redis服务&基本数据结构

  2019-6-1 

Redis（Remote Dictionary Server )，即远程字典服务

数据库是它的一个功能应用，它还可以作为其它中间件使用

redis-cli在命令行进入Redis服务客户端，可以用Jedis在JAVA中操作Redis客户端

Jedis常用API：https://www.cnblogs.com/yepei/p/5662734.html

(注意，当我们在本机运行redis服务端之后，我们无论是其它机器在远程访问redis，还是本地用jedis或redis-cli访问redis，都是客户端)

基本数据结构

以下数据结构大都可以通过储存指向对象的void*指针来储存各种类型的值

Redis 的value有 5 种基础数据结构，分别为：string (字符串)、list (列表)、set (集合)、hash (哈希) 和 zset (有序集合)。

  1. 基本数据结构（五大value）

    1. 简单动态字符串（SDS）

      字符串结构使用非常广泛，一个常见的用途就是缓存用户信息。我们将用户信息结构体使用 JSON 序列化成字符串，然后将序列化后的字符串塞进 Redis 来缓存。

      Redis字符串封装了C字符串，加入了字符串长度字段和未使用空间字段，优势：常数复杂度获取字符串长度、杜绝缓冲区溢出、二进制安全

      Redis 的字符串是动态字符串，是可以修改的字符串，内部结构实现上类似于 Java 的 ArrayList，采用预分配冗余空间和惰性空间释放的方式来减少内存的频繁分配。（成倍分配空间）

      set、get、del、mset、mget、setnx 、expire、incr

      set name1 thisname1

    2. 双端链表（list）

      Redis 的列表相当于 Java 语言里面的 LinkedList，叫做quicklist，注意它是链表而不是数组。

      当列表元素较少的时候的是ziplist（减小空间冗余），它在空间上连续，当数据量较多的时候，它将多个ziplist用双向指针串起来组成quickList。

      这意味着 list 的插入和删除操作非常快，时间复杂度为 O(1)，但是索引定位很慢，时间复杂度为 O(n)

      Redis 的列表结构常用来做异步队列使用。将需要延后处理的任务结构体序列化成字符串塞进 Redis 的列表，另一个线程从这个列表中轮询数据进行处理

      l/rpush、l/rpop、l/rlen（求长度）

      lindex 、ltrim（遍历链表，所以是慢操作）

    3. 字典（hash）

      Redis 的字典使用hash实现，相当于 Java 语言里面的 HashMap，它是无序字典。内部实现结构上同 Java 的 HashMap 也是一致的

      redis字典的rehash和java 的hashmap的rehash方式不一样：Redis 为了高性能，不能堵塞服务，所以采用了渐进式 rehash 策略。（保留新旧两个hash结构，查询时同时查询两个，然后将旧hash内容一点一点迁移）

      hset、hget、hmset、hmget

      注意，那么加入进redis里的就是<key,<key1_of_hash,value1，key2_of_hash,value2...>>

    4. 集合（set）

      相当于java里的hashset，它的内部实现相当于一个特殊的字典，字典中所有的 value 都是一个值NULL。

      sadd、smembers、sismember 、scard、spop

    5. 有序集合（zset）

      一方面它是一个 set，保证了内部 value 的唯一性，另一方面它可以给每个 value 赋予一个 score，代表这个 value 的排序权重。它的内部实现用的是一个【hash表】【和】一个叫做【跳跃表】（用于指定score的范围来获取value）的数据结构。（因为链表二分查找效率极低，所以不能二分查找，当然直接遍历就更慢了）。hash表能快速查找成员、跳跃表能实现排序，zset中的元素同时被保存在这两种数据结构中。

      跳跃表提供了一种比红黑树更简单但效率差不多的排序数据结构：https://www.zhihu.com/search?type=content&q=%E8%B7%B3%E8%B7%83%E5%88%97%E8%A1%A8，注意为了每次插入后不用全部重新建表，每一个节点的层数是随机出来的，大大降低了插入的复杂度。跳跃列表使得我们可以像二分查找一样可以快速锁定目标所在的段

      <key,<value1_of_set,score1，value2_of_hash,score2...>>

      可以用zset的score来做时间戳，设置一个时间窗口来限流，将同用户的同行为设置为一个key的zset，<value_of_set,score>设置为<时间戳，时间戳>（value_of_set无实际意义），然后就可以通过窗口来限流了

  2. 还有些特殊数据结构如①位图、②HyperLogLog 提供不精确的去重计数方案（替代set方案，速度快耗资源小，可以做网站的UV）：pfadd指令增加计数、 pfcount获取计数③BloomFilter提供不精确的去重方案（替代set方案，某个值存在时，这个值可能不存在；当它说不存在时，那就肯定不存在。它省去90%空间，解决了HyperLogLog只能计数不能去重的问题）原理：每个布隆过滤器由一个大型的位数组和几个不一样的无偏 hash 函数。所谓无偏就是能够把元素的 hash 值算得比较均匀。每add一个数就是将该数用不同的hash函数计算出一个位，然后把这几个位都置为1；查该数的时候，计算hash，只要有一个hash算出来的位置不为1，那么就代表该结构中一定没有这个数（而都为1不一定有，因为冲突可能）；数组越大越准确。

  3. 对象

    每个对象都对应内存中的一个redisObject结构，其中有个指针指向实际数据结构

    Redis基于五大数据结构创建了一个对象系统，将这五大数据结构封装成各自对象，我们实际上是与各类对象打交道。（这样可以做到同一类型对象根据不同情形灵活选择不同编码实现；可以手动指定通过encoding属性设置不同编码实现）满足一定条件或操作会自动进行编码的转换

    Redis除了会根据值对象的类型来判断键是否能够执行指令命令之外（类型检查），还会根据值对象的编码方式，选择正确的命令实现代码来执行命令（根据不同编码，调用不同的函数实现）。

    Redis的对象引用计数机制实现了内存回收机制、对象共享机制（共享一个对象，节约内存）

    Redis的对象共享机制和JAVA原理差不多，但是不同的是Redis只对整数值的字符串对象进行共享。Redis是在初始化服务器的时候创建一万个字符串对象，这些对象包含了从0到9999的所有整数值，当服务器用到就直接使用这些共享对象。（非整数值会有大量检查开销）

    Redis对象还有个对象空转时长的字段（记录了对象最后一次被命令程序访问的时间），如果服务器设置了maxmemory选项，那么当内存超过maxmemory后，Redis会优先释放对象空转时长高的对象。

    编码：

    ①字符串对象就有三种编码（int编码整数、raw编码长字符串，以SDS保存、embstr编码短字符串）

    在embstr中，redisObject数据和SDS数据是相邻的，那么新建一个对象只需要一次malloc；而raw中两者是不相邻的，新建一次对象需要两次malloc

    ②list对象就可以是ziplist或linkedlist

    ③字典对象可以是ziplist（短且值长度小）或hashtable

    ④集合对象可以是intset或hashtable

    ⑤有序集合zset可以是ziplist（很短时）或skiplist（跳表）

    Long double类型表示的浮点数在Redis中也是作为字符串值来保存的，不过操作的时候会转换为浮点

    （ziplist见小对象压缩部分）

单机数据库的实现

  1. 数据库

    ①结构

    Redis服务器将所有的数据库都保存在服务器状态redis.h/redisServer结构的db数组中

    db数组每一项都是个redis.h/redisDb结构，每个redisDb结构代表一个数据库

    redisDb结构体中的a.键空间即数据库的数据，b.expires字典保存了数据库中所有键的过期时间

    在初始化Redis服务器时，程序会根据服务器状态的dbnum属性来决定应该创建多少个数据库，默认为16

    Redis客户端状态redis.h/redisClient结构的db属性是一个指向redisDb结构的指针，表明目前client的目标数据库。客户端可以执行SELECT指令切换目标数据库。

    键空间本身就是个字典hash。加入其中的所有的数据结构都是以唯一的 key 字符串作为名称，然后通过这个唯一 key 值来获取相应的 value 数据。都是key-value键值对储存，这个value就可以是Redis任意数据结构类型。举例：即使是字典，也是key->[dict_key,dict_value]，[dict_key,dict_value]即为字典类型的value

    ②过期

    redisDb中的expires字典保存了数据库中所有键的过期时间，常用指令EXPIRE、PERSIST、TTL等

    过期字典存的是时间戳+过期期限，然后检查当前时间戳是否大于记录值即可

    过期键删除策略：定期删除（确定删除操作执行的时长和频率）、惰性删除（用再检查）、定期删除（计时器）

Redis通信协议RESP（更新）

RESP(Redis Serialization Protocol)： Redis 序列化协议

RESP非常浪费流量，但Redis 的作者认为数据库系统的瓶颈一般不在于网络流量，而是数据库自身内部逻辑处理上。

Redis 协议将传输的结构数据分为 5 种最小单元类型，单元结束时统一加上回车换行符号\r\n。

  1. 单行字符串 以 + 符号开头。
  2. 多行字符串 以 $ 符号开头，后跟字符串长度。
  3. 整数值 以 : 符号开头，后跟整数的字符串形式。
  4. 错误消息 以 - 符号开头。
  5. 数组 以 * 号开头，后跟数组的长度。

客户端向服务器发送的指令只有一种格式：多行字符串数组

比如set aaa bbbb->

*3
$3
set
$3
aaa
$4
bbbb

服务器向客户端回复的响应要支持多种数据结构。

小对象压缩

redis可以使用32bit编译

同时redis有个ziplist，当hashtable、linkedlist需要储存的内容很少的时候，redis就会自动有ziplist来实现hash字典和list列表。ziplist在空间上是连续的。对于hash，key-value在ziplist是相邻储存的，linkedkist就不比多说。

当元素个数超过一定数量，那就会自动变换成标准储存结构来储存了

管道

客户端通过对管道中的指令列表改变读写顺序就可以大幅节省 IO 时间。管道中指令越多，效果越好。

因为实际上我们在socket请求中，客户端与服务端都存在各自的recv buffer和send buffer；write实际上是用户进程将数据写到send buffer中，再由操作系统内核将缓冲区内容发送到网卡，再层层包装转送出去；read实际上是客户端进程从本地的recv buffer中读取数据，而数据是由操作系统内核负责接收数据到缓冲区。

也就是说，我们实际上的网络开销是read等待缓冲区非空，而write等待缓冲非满。而如果缓冲区是空，我们read要等，而write不用等的情况下，诸如write-read-write-read，我们改成write-write-read-read，显然更好更快，两次write根本不需要等待，不被阻塞。

事务

multi指示事务的开始，exec指示事务的执行，discard指示事务的丢弃（丢弃未执行的指令，不是回滚！）。

multi~exec之间收到的指令都不执行，只有在收到exec的时候执行，如果一旦捕获到异常，那么就执行回滚

Redis事务仅满足隔离性，不满足原子性，因为Redis事务不支持回滚（因为回滚复杂，为了保持Redis的简单和高效）

通常 Redis 的客户端在执行事务时都会结合 pipeline 一起使用，这样可以将多次 IO 操作压缩为单次 IO 操作。比如我们在使用 Python 的 Redis 客户端时执行事务时是要强制使用 pipeline 的：

pipe = redis.pipeline(transaction=true)  #管道
pipe.multi() #事务开始
pipe.incr("books")
pipe.incr("books")
values = pipe.execute() #事务执行

Jedis

如果是多线程redis请求，那么就要使用jedis的连接池：JedisPool来 管理多线程Jedis连接对象

需要使用try catch语句来保证如果jedis对象抛出异常，要归还jedis给连接池

在jedis连接失败不会提供重试机制，所以要人为写重试代码：try捕获连接异常，捕获到就重连

安全

使用rename-command把危险指令flushdb、flushall等重命名

要有密码，不然小心被lua脚本注入

redis不支持ssl，所以可以使用ssl代理：spiped

其它

  1. info指令可以获取redis的运行状态信息

  2. scan指令

    可以从海量的 key 中找出满足特定前缀的 key 列表来，

    scan 参数提供了三个参数，第一个是 cursor 整数值，第二个是 key 的正则模式，第三个是遍历的 limit hint。

    （具体原理略）

  3. redis服务器默认监听端口 6379

  4. 命令行中可以使用重定向<,>等语句，很方便
赏

且听风吟