1.1 授人以鱼不如授人以渔

1.1.1 由Redis面试想到的

1.1.2 本书的内容范围

1.1.3 Redis可以做什么

Redis可视为一块进程公共的、线程安全的、可扩展的内存区域。对该区域中数据的单次读写操作均是线程安全的。 Redis与数据库的对比，两者都是进程公共的、线程安全的（数据库依靠事务隔离来实现）。但Redis是内存中的，性能高，但非持久化。而数据库是硬盘上的，持久化，但性能低。理论上来讲，Redis的工作，数据库都能完成，只是读写性能低得多。

1.2 万丈高楼平地起——Redis基础数据结构

1.2.1 Redis的安装

1.2.2 5种基础数据结构

Redis所有的数据结构都以唯一的key字符串作为名称，然后通过这个唯一的key值来获取相应的value数据。不同类型的数据结构的差异就在于value的结构不一样（key都是字符串，value有以下五种类型）。

  • string
  • hash
  • list
  • set
  • zset

    string（字符串）

    Redis的字符串是动态字符串，是可以修改的字符串，内部结构的实现类似于Java的ArrayList，采用预分配冗余空间的方式来减少内存的频繁分配。当空间不够时，自动扩容。
    字符串的最大长度为512MB。
    关于字符串的内部结构实现，请阅读第5.1节。

    list（列表）

    Redis的列表相当于Java语言里面的LinkedList（实际比这个复杂），注意它是链表而不是数组。这意味着list的插入和删除操作非常快，时间复杂度为O(1)，但是索引定位很慢，时间复杂度为O(n)。list中的每个元素都使用双向指针链接，可以支持前后遍历。
    当列表弹出了最后一个元素之后，该数据结构被自动删除，内存被回收。
    Redis的list常用来做异步队列。将需要异步处理的任务结构体序列化成字符串，塞进Redis的列表，另一个线程从这个列表中轮询数据进行处理。
    Redis的底层存储并非简单的LinkedList，而是一种被称之为QuickList的结构。
    在List中元素较少时，会使用一块连续的内存进行存储，这个结构称之为ziplist，即压缩列表。它将所有的元素彼此紧挨在一起进行存储。当数据量比较多的时候，才会改成quicklist。由于普通的链表元素都需要包含两个指针，会浪费空间，且加重内存的碎片化，所以Redis将链表和ziplist结合起来，组成了所谓的quicklist，也就是将多个ziplist使用双向指针串起来。
    image.png
    关于list的详细内部结构，请阅读5.3和5.4节。

    hash（字典）

    Redis的字典相当于Java语言里面的HashMap，它是无需字典，内部存储了很多键值对。实现结构上与Java的HashMap也是一样的，都是“数组+链表”二维结构。第一维hash的数组位置碰撞时，就会将碰撞的元素使用链表串接起来。
    不同的是，Redis的字典的值只能是字符串，另外它们（在扩容时）rehash的方式不一样。Java的HashMap是一次性rehash完成的，而Redis为了避免rehash堵塞后续请求，所以采用了渐进式rehash的策略。渐进式rehash会在rehash的同时，保留新旧两个hash结构。查询时会同时查询两个hash结构，然后在后续的定时任务以及hash操作指令中，循序渐进地将旧hash的内容一点点迁移到新的hash结构中。当迁移完成了，就是用新的hash结构取代之。
    当hash移除了最后一个元素之后，该数据结构被自动删除，内存被回收。

    set（集合）

    Redis的集合相当于Java语言里的HashSet，它内部的键值对是无序的、唯一的。它的内部实现相当于一个特殊的字典，字典中所有的value都是一个值NULL。
    当集合中最后一个元素被移除之后，数据结构被自动删除，内存被回收。

    zset（有序列表）

    zset类似于Java的SortedSet，一方面它是一个set，保证了内部value的唯一性，另一方面它可以 给每个value赋予一个score，代表这个value的排序权重。它的内部实现用的是一种叫做“跳跃列表（skip list）”的数据结构。
    zset中最后一个value被移除后，数据结构将被自动删除，内存被回收。
    关于zset的内部实现，请阅读5.5节。

    1.2.3 容器型数据结构的通用规则

    list、hash、set、zset这四种数据结构是容器型数据结构，它们共享下面两条通用规则。
  1. create if not exists：如果容器不存在，那就自动创建一个，再进行操作。
  2. drop if no elements：如果容器里的元素没有了，那么立即删除容器，释放内存。

    1.2.4 过期时间

    Redis所有的数据结构都可以设置过期时间，时间到了，Redis会自动删除相应的对象。需要注意的是，过期是以顶层的key-value作为单位的，比如一个hash结构的过期是整个hash对象的过期，而不是其中的某个子key的过期。
    另外，如果一个字符串已经设置了过期时间，然后你调用set方法修改了它，它的过期时间就会消失。

1.3 千帆竞发——分布式锁

1.3.1 分布式锁的奥义

分布式锁本质上要实现的目标就是在Redis里面占一个“坑”，当别的进程也要来占坑时，那里已经有一根“大萝卜”了，就只好放弃或者稍后再试。

回顾操作系统中锁的基础知识，只要提供一个状态标识和对该状态标识的原子性读写操作（如CAS），就可以实现一个自旋锁。在操作系统中，原子性读写操作是由CPU提供的，而在Redis中，借助于Redis的单线程执行模型，也可以提供原子性的读写操作，因此可以借助于Redis实现分布式自旋锁。 而要实现重量级锁，还需要：

  1. 无锁的线程安全的队列。
  2. 线程睡眠和唤醒的机制。

借助于Redis的阻塞队列，可以实现这些功能。 不过，一个完善的锁还要考虑可重入性，公平性，如何确保锁一定会释放等问题。 PS：分布式条件下，最大的问题是没有办法确保锁一定会释放。核心难点在于超时带来的三态问题。

为了实现分布式（自旋）锁，我们需要以下Redis指令：

  1. 在没有某个key时，设置某个key-value（抢占锁标志位）。
  2. 为key设置过期时间。这是为了避免由于线程异常退出而导致锁无法释放的场景。
  3. 删除某个key。

其中，1和2两步必须是一个原子性操作。在Redis 2.8版本之前，无法实现将1和2融合为一个原子操作，因此要实现分布式锁比较复杂。而在Redis 2.8之后，可以借助以下指令将1和2融合为一个原子操作：

  1. set lock:xxx true ex [过期时间] nx

1.3.2 超时问题

对一个抢到锁的线程而言，如果在加锁和释放锁之间的逻辑执行得太久，以至于超出了锁的超时限制，就会出现问题。此时该线程抢到的锁已经由于超时而过期了，可能第二个线程已经在第一个线程执行完之前提前抢到了锁，从而导致多个线程进入了临界区。

对于单个进程内的锁，不需要超时时间，因为一个线程挂点了的话，只要进程没有挂，总是可以在finally语句中释放掉锁的。但是进程间的分布式锁则无法保证一定能释放掉锁。

最基础的解决方案是，不要让分布式锁的超时时间接近任务完成时间，而应该有较大的余量。如果出现了问题，就人工修复。
稍微安全一点的做法是，在抢锁的时候，给锁设置一个随机值。在释放锁时，先比较锁值是否是随机值，如果是，再释放；如果不是，说明锁已经被别人抢走了，当前线程需要回滚。但是，读取key和删除key不能融合为一个原子操作（借助lua脚本可以实现），且另一个线程进入临界区可能已经导致了数据异常，无法正常回滚。

1.3.3 可重入性

Redis分布式锁如果要支持可重入，需要对客户端的set方法进行包装，使用线程的ThreadLocal变量存储当前持有锁的计数。
要实现完善的可重入性非常复杂，不建议使用。

1.4 缓兵之计——延时队列

1.4.1 异步消息队列

1.4.2 队列空了怎么办

1.4.3 阻塞读

1.4.4 空闲连接自动断开

1.4.5 锁冲突处理

在分布式锁中，当客户端请求加锁时失败，应该怎么办？通常有以下三种策略：

  • 直接抛出异常，通知用户稍后重试。
  • sleep一会儿，然后重试。
  • 将请求转移到延时队列，过一会再试（这里的请求应该是指整个业务处理请求，而非加锁请求）。即是把同步过程降级为一部过程进行处理。

1.4.6 延时队列的实现

生产者-消费者模型。

1.4.7 进一步优化

1.5 节衣缩食——位图

位图不是特殊的数据结构，它的类型其实就是字符串，不过使用时将其视为byte数组。我们可以使用字符串的get/set直接获取整个位图的内容，也可以使用位图操作getbit/setbit等将byte数组看成“位数组”来处理。

1.5.1 基本用法

Redis的位数组是自动扩展的，如果设置了某个偏移位置超出了现有的内容范围，就会自动将位数组进行零扩充。
命令：

  • SETBIT key offset value

  • GETBIT key offset

    1.5.2 统计和查找

  • BITCOUNT key [start] [end]：计算给定字符串中，被设置为 1 的比特位的数量。

  • BITPOS key bit [start] [end]：返回位图中第一个值为 bit 参数值的二进制位的位置。

    1.5.3 魔术指令bitfield

    BITFIELD 命令可以将一个 Redis 字符串看作是一个由二进制位组成的数组， 并对这个数组中储存的长度不同的整数进行访问 （被储存的整数无需进行对齐）。 换句话说， 通过这个命令， 用户可以执行诸如 “对偏移量 1234 上的 5 位长有符号整数进行设置”、 “获取偏移量 4567 上的 31 位长无符号整数”等操作。 此外， BITFIELD 命令还可以对指定的整数执行加法操作和减法操作， 并且这些操作可以通过设置妥善地处理计算时出现的溢出情况。

    http://redisdoc.com/bitmap/bitfield.html

1.6 四两拨千斤——HyperLogLog

用于基数统计。
优点：体积小，最多12KB。
缺点：

  • 有极小误差。

  • 只能用于统计基数，无法判断具体某个元素是否存在（即不能代替Set）。

    1.6.1 使用方法

    命令：

  • pfadd

  • pfcount

1.7 层峦叠嶂——布隆过滤器

可视为一个有误差的、大型set。主要用于大数据场景下的去重。

数据类型 基数统计 判断一个元素是否出现过 得到实际元素
Set YES YES YES
位图 YES YES YES
布隆过滤器 NO YES NO
HyperLogLog YES NO NO

1.8 断尾求生——简单限流

1.8.1 如何使用Redis来实现简单限流策略

场景：限定用户的某个行为在指定的时间间隔内只能发生N次。
分析：难点在于需要维护一个滑动窗口。滑动窗口大小代表指定的时间间隔。要求滑动窗口内的行为数量低于一个阈值。
解决方案：使用zset。用单个记录的score代表时间。用zremrangeByScore命令来去除当前滑动窗口以外的数据。最后统计窗口内的数据。
缺点：每个用户行为都需要记录，因此占用空间较大。

1.9 一毛不拔——漏斗限流

1.10 近水楼台——GeoHash

1.11 大海捞针——scan