1. redis数据类型

1.1 基本的数据类型

1.1.1 string字符串类型

string是redis最基本的数据类型, 典型的key-value形式. string类型可以包含任何数据, 即便是图片或者是序列化对象, 单个value值最大上限是1G字节。key最大可以存储512M。

set name zs // 赋值
get name    // 取值
getset name ls // 取值并赋值
expire name 5 // 5秒后到期
setex name 5 zs // 设置name,5秒后到期
setnx name zs // 如果不存在, 就执行set命令
mset name zs sex male year 18     // 批量设置字段
mset user:1001:name zs user:1001:year 20
mget name sex year 
append name 123 // 向尾部追加 
strlen name        // 获取字符串的长度
del name 
exists name 
incr year
incrby year 5 
incrby year -5

String采用的编码类型有int(int类型的整数),embstr(小字符串, 长度小于44字节)和raw(长度大于44字节)

1.1.2 list 列表类型

队列: 
rpush books java c++ python 
lpop books
blpop books 1   // 从列表左侧取出，当列表为空时阻塞，可以设置最大阻塞时间，单位为秒
栈:
rpush books java c++ python 
rpop books 
brpop books 1 // 从列表右侧取出，当列表为空时阻塞，可以设置最大阻塞时间，单位为秒

lpushx books start // 列表头添加数据
rpushx books end // 列表的尾添加数据 
llen books // 列表中元素个数
lindex books 0 // 获取指定下标的值
lrange books 0 3  // 获取前4个数据
lrange books 0 -1  // 获取全部数据 -1代表到队尾
lrem books 1 java // 删除books列表里与java值相等的元素, 数字代表删除几个一样的数据, 正数从列表左边删除, 负数从列表右边删除, 0删除所有一样的值
lset books 1 javaweb // 将列表index位置的元素设置成value的值
ltrim books 0 3 // 截取指定下标后的几位
ltrim books 1 0 // 清空集合

列表有序可以作为栈和队列使用, 或者各种列表，比如用户列表、商品列表、评论列表等。

list列表的编码类型是quicklist

1.1.3 set集合类型

Redis 的集合相当于 Java 语言里面的 HashSet，它内部的键值对是无序的唯一的。

sadd books python java c++ python   // 添加成员
srem books python // 删除成员
smembers books // 获取全部集合数据
spop books // 随机返回一个元素, 并将该元素删除
srandmember books n // 随机获取n个数据 不删除元素
scard books // 类似count
sismember books java // 查询某一个value是否存在集合中
sinter set1 set2 set3 // 求交集
sunion set1 set2 set3 // 求并集
sdiff set1 set2 // 求差集 set1中存在, set2中不存在的

通过spop进行随机抽奖

set集合的编码是整形集合(集合元素都是整数且都处于64位有符号整数范围)和字典

1.1.4 zset集合类型

SortedSet(ZSet) 有序集合: 元素本身是无序不重复的,每个元素关联一个分数(score),可按分数排序，分数可重复.

zadd books 9.0 "世界上最好的语言-java" 1.0 "php才是世界上最好的语言" 6.6 "你们都是垃圾,python yyds"
zrem books "php才是世界上最好的语言"    // 删除
zcard books // count
zcount books 3 9 // 返回集合中score值在[min,max]区间的元素数量
zincrby books 10 "php才是世界上最好的语言" // 提升对应value值的score值
zscore books "你们都是垃圾,python yyds" // 获取指定value的score
zrank books "世界上最好的语言-java"     // 在集合中排名
zrange books 0 -1  // 指定区间内元素, 正序排序输出 
zrevrange books 0 -1 // 逆序排序输出

由于可以按照分值排序，所以适用于各种排行榜。比如：点击排行榜、销量排行榜、关注排行榜等
有序集合的编码是压缩列表(元素个数少,且都是小整数和短字符串)和跳跃表+字典(元素多或者元素是大整数)

1.1.5 hash(散列表)类型

hash 是一个 string 类型的 fifield 和 value 的映射表，它提供了字段和字段值的映射

hset books java "thinking in java"
hmset books c++ "太难盘了" php "php是世界上最好的语言"
hsetnx books java "java进阶"    //如果filed存在则不操作
hexists books java  // 查看某个field是否存在
hget books c++
hmget books java c++
hgetall books // 获取全部集合数据
hlen books // 获取字段数量
hdel books java // 删除指定字段
hincrby books num 9     // 指定字段自增

进行对象的存储, 表结构的映射。

散列表的编码是字典(元素多或者都是大整数/字符串)和压缩列表(元素少或者都是小整数/字符串).

1.2 高级的数据类型

1.2.1 bitmap位图

操作二进制来进行数据保存。

setbit name 0 1 // 将字段串name的第一位设置为1
getbit name 0    // 获取字符串name第0位的值
bitcount name start end    // 统计name 位为1的个数 这里的start,end是字节数, 不是位数
bitpos name 1 start end // name字符串 第一个被设置为1的位索引值 同上

1.2.1 HyperLogLog

redis提供了HyperLogLog数据结构, 来进行基数统计(不重复的元素).
优势: 占用内存是固定的, 只需要很少的内存(12K)

pfadd halo a b c c d     // 创建一批元素
pfadd halo2 b d e f g // 创建第二批元素
pfcount halo    // 数据统计
pfmerge halo3 halo halo2

1.2.3 geo地理位置(GeoHash)

geo是Redis用来处理位置信息的, 主要使用GeoHash算法(业界比较通用的地理位置距离排序算法)。

geoadd company 116.48105 39.996794 juejin     // 添加地理坐标
geodist company juejin meituan km    // 计算两个元素之间的距离
geopos company juejin    // 获取元素经纬度
geohash company juejin     // 获取元素的经纬度编码字符串

georadiusbymember company juejin 20 km withdist     // 获取元素20公里范围内的元素, 按距离正序排序

1.2.4 布隆过滤器:

布隆过滤器主要作用是证明这个数据是否存在(存在偏差). 布隆过滤器本质上是一个数组. 但是特殊点是这个数组只存储0或者1.
原理: 往过滤器里设置”你好”字符串时候, 执行第一个hash函数后, 得到下标位, 设置为1. 同理,执行其他hash函数, 设置对应的坐标位置。在判断”你好”是否存在的时候, 只有经过所有的hash函数, 得到的下标对应的值均为1, 认定为该字符串存在于布隆过滤器中。

优点: 二进制数组, 占用内存少, 基于数组查询, 速率快。并且有若干个hash函数, 保密性好。
缺点: 不允许进行删除操作(对于一个下标对应的值为1, 不仅仅代表某一个数据, 可能若干个数据该下标均为1) 并且会存在误判.

布隆过滤器使用:

public class BloomFilterTest {
    public static void main(String[] args) {
        // 预计插入的数据
        int expectedInsertions = 1000000;
        // 误判率 误判率约下, 内存占用越大, 计算时间越长
        double fpp = 0.01;
        BloomFilter filter = BloomFilter.create(Funnels.integerFunnel(), expectedInsertions, fpp);

        // 插入100万样本数据
        int total = 1000000;
        for (int i = 0; i < total; i++) {
            filter.put(i);
        }
        int count = 0;
        // 从total 开始向后取 100000数据 判断是否会被判定为存在于布隆过滤器中
        for (int i = total; i < total + 100000; i++) {
            if (filter.mightContain(i)) {
                count++;
                System.out.println(i + "误判了");
            }
        }
        System.out.println("total 误判: " + count);
    }
}

2. 使用场景:

2.1 string 字符串

2.1.1 缓存:

缓存信息, 将对象信息序列化成字符串, 设置到redis中来做缓存。

public String set(String key, Object obj, int ttl) {
    String result;
    Jedis jedis = null;
    try {
        String value = objectToJson(obj);
        jedis = getJedis();
        result = jedis.set(key, value);
        expireKey(jedis, key, ttl);
    } catch(Exception e){
        log.error("RedisUtil.set error , will skip",e);
        return null;
    } finally {
        returnJedis(jedis);
    }
    return result;
}

2.1.2 分布式锁:

分布式锁实现主要逻辑: 在redis中占一个坑, 当别的线程进来后, 发现已经被别人占了, 则放弃。借助的是setnx命令, 在业务逻辑处理完成之后, 使用del命令去释放。
为防止业务逻辑发生异常, 导致坑位无法释放, 所以需要设置过期时间, 借助的命令是expire.
setnx lock true
expire lock 5
但是setnx月expire之间也不是原子性的, 会存在还没有来得及设置过期时间, 就发生异常。为解决这个问题, redis对set做了扩展
set key value ex time nx 该命令代表着设置如果key不存在才设值, 且设置过期时间, 这样setnx和expire就是原子组合了, 这也是分布式锁的核心。

public boolean getLock(String lockKey, String requestId, int expireTime) {
    boolean res = false;
    Jedis jedis = null;
    try {
        jedis = getJedis();
        String result = jedis.set(lockKey, requestId, SetParams.setParams().nx().ex(expireTime));
        if (LOCK_SUCCESS.equals(result)) {
            res = true;
        }
    } finally {
        returnJedis(jedis);
    }
    return res;

}

存在问题:

问题1: [锁过期释放了，业务还没执行完]. 假设线程a获取锁成功，一直在执行临界区的代码。但是100s过去后，它还没执行完。但是，这时候锁已经过期了，此时线程b又请求过来。显然线程b就可以获得锁成功，也开始执行临界区的代码。那么问题就来了，临界区的业务代码都不是严格串行执行的啦。
问题2: [锁被别的线程误删]。假设线程a执行完后，去释放锁。但是它不知道当前的锁可能是线程b持有的（线程a去释放锁时，有可能过期时间已经到了，此时线程b进来占有了锁）。那线程a就把线程b的锁释放掉了，但是线程b临界区业务代码可能都还没执行完呢。

对于问题2, 可以在set的时候, 设置随机数(也可以是当前线程), 在释放锁的时候,匹配value是否一致,然后再删除key。匹配个过程借助lua脚本。保证多个指令是原子性执行。

public boolean releaseLock(String lockKey, String requestId) {
    boolean res = false;
    String script = "if redis.call('get', KEYS[1]) == ARGV[1] then return redis.call('del', KEYS[1]) else return 0 end";
    Jedis jedis = null;
    try {
        jedis = getJedis();
        Object result = jedis
            .eval(script, Collections.singletonList(lockKey), Collections.singletonList(requestId));
        if (RELEASE_SUCCESS.equals(result)) {
            res = true;
        }
    } finally {
        returnJedis(jedis);
    }
    return res;

}

对于问题1,可以借助开源框架Redisson, 开源框架底层原理:

只要线程一加锁成功，就会启动一个watch dog看门狗，它是一个后台线程，会每隔10秒检查一下，如果线程1还持有锁，那么就会不断的延长锁key的生存时间。因此，Redisson就是使用watch dog解决了「锁过期释放，业务没执行完」问题。

zk锁: 主要就是靠创建临时的顺序节点来实现的

zk实现分布式锁的流程如下图:

创建一个锁目录lock
线程A获取锁会在lock目录下，创建临时顺序节点。并获取锁目录下所有的子节点，然后找到比自己小的兄弟节点，如果不存在，则说明当前线程顺序号最小，获得锁。
线程B创建临时节点并获取所有兄弟节点，判断自己不是最小节点，设置监听(watcher)比自己次小的节点。
线程A处理完，删除自己的节点，线程B监听到变更事件，判断自己是最小的节点，获得锁.

为什么是顺序节点: 如果是非顺序节点, 每进来一个线程, 都会去持有锁的节点上注册一个监听器, 容易引发羊群效应。有顺序的话, 只会监听自己的前一个节点。
为什么是临时节点: 防止 ZK 服务器宕机，临时节点会随着服务器的宕机而消失，避免了死锁的情况。

zk锁 & redis锁 比较

实现方式的不同，Redis 实现为去插入一条占位数据，而 ZK 实现为去注册一个临时节点。
遇到宕机情况时，Redis 需要等到过期时间到了后自动释放锁，而 ZK 因为是临时节点，在宕机时候已经是删除了节点去释放锁。
Redis 在没抢占到锁的情况下一般会去自旋获取锁，比较浪费性能，而 ZK 是通过注册监听器的方式获取锁，性能而言优于 Redis。

redis锁 可重入性

redis锁可重入性主要是在分布式锁实现的基础上结合了threadLocal来实现的。

2.2 list集合

2.2.1 消息队列

redis可以使用list集合做简易的异步消息队列,使用rpush/lpush做入队列, lpop和rpop出队列。

上述实现的异步队列是无法做到一次生产多次消费的, 可以使用redis的的主题订阅模式,可以做到一次生产多次消费。

a.问题1: 队列空了怎么预防空轮询

客户端通过pop操作获取消息, 如果队列为空, 客户端就陷入死循环, 不停地在空轮询。会拉高cpu.
我们可以使用blpop或者brpop命令, 进行阻塞读, 队列没有数据, 会立即进入休眠状态, 还可以设置阻塞时间, 一但队列中新进数据或者阻塞时间到了, 才会醒过来.

2.3 zset集合

2.3.1 延时队列

在设置分布式锁的时候, 如果加锁失败怎么办??
方案1: 直接抛出异常, 重新发起请求(最常用方式)
方案2: 睡一段时间继续获取锁, 直到获取成功(CAS方式)
方案3: 延时队列可以通过 Redis 的 zset(有序列表) 来实现。我们将消息序列化成一个字符串作为 zset 的 value，这个消息的到期处理时间作为 score，然后用多个线程轮询 zset 获取到期的任务进行处理.

2.3.2 位置距离 & 查找附近的人

详见1.2.3

2.3.3 简单限流

接口限流: 在限定的时间内, 只允许N次接口的调用

方式1: 使用计数法:

在一段时间内, 进行计数, 与阈值比较, 到了时间临界点, 将计数器清空。该方法是比较简单的限流, 但是会存在一个问题: 如果在单位时间 1min 内的前 1s ，已经通过了 100 个请求，那后面的 59s ，只能把请求拒绝，这种现象称为 突刺现象。

方式2: 滑动窗口:

滑动窗口就是记录一个滑动的时间窗口内的操作次数，操作次数超过阈值则进行限流

借助zset数据结构来实现这个功能, value是当前操作的时间戳。每次新的操作请求进来时，先判断当前时间窗口内记录的操作次数 count，小于阈值max则允许进行操作，超过阈值则进行限流。同时对时间窗口之外的数据进行清理，节省内存。

public boolean isActionAllowed(String userId, String actionKey, int period, int maxCount) {
    String key = userId + "#" + actionKey;
    long nowTs = System.currentTimeMillis();
    Pipeline pipe = jedis.pipelined();
    //开启事务
    pipe.multi();
    //1. 存放记录, 第二个参数是score，第三个参数是value
    pipe.zadd(key, nowTs, "" + nowTs);
    //2. 清除滑动窗口外的数据
    //pipe.zremrangeByScore(key, 0, nowTs - period * 1000);
    //3. 当前窗口的元素个数
    //Response<Long> count = pipe.zcard(key);
    // 2,3 步骤可以用: zcount books 3 9
    Response<Long> count = pipe.zcount(key, nowTs - period * 1000, nowTs);
    //4. 要设置过期时间
    pipe.expire(key, period + 1);
    //执行事务
    pipe.exec();
    pipe.close();
    return count.get() <= maxCount;
}

方式3: 漏斗限流:

以固定速率从桶中流出水滴，以任意速率往桶中放入水滴，桶容量大小是不会发生改变的。
流入：以任意速率往桶中放入水滴。
流出：以固定速率从桶中流出水滴。
因为桶中的容量是固定的，如果流入水滴的速率>流出的水滴速率，桶中的水滴可能会溢出。那么溢出的水滴请求都是拒绝访问。

redis中限流模块(redis-cell), 也是采用了漏斗算法, 并提供了原子的限流指令。

允许执行操作的频率为每 60s 最多 30 次(漏水速率)，漏斗的初始容量为 15。

方式4: 令牌桶算法(Token)

会以一个恒定的速度往桶里放入令牌，而如果请求需要被处理，则需要先从桶里获取一个令牌，当桶里没有令牌可取时，则拒绝服务。(Guava中的RateLimiter)

2.4 高级应用

2.4.1 统计打卡,用户是否活跃,用户是否登录

通过bitset来进行用户打卡统计

2.4.2 网站uv统计

方式1: 使用set命令(sadd 某一页面 用户id), 通过scard获取页面uv总数。(占用内存大)
方式2: 使用bitmaps(setbit 某一页面 用户id 1) 通过bitcount获取页面uv总数。
(假设一亿用户, 一个页面一天需要占用的内存:100000000 % 8 % 1024 % 1024 约等于12M, 1000个页面一年占内存是4.2T, 也不是最优解)
方式3:使用HyperLogLog(pfadd 某一页面 用户id)

3. redis底层数据结构

redis存在数据库的概念, redis服务器在初始化的时候, 会预先分配16个数据库。但是redis没有表的概念, 所有的数据都是key-value的形式, 这里的value是一个RedisObject对象。(这个对象包含字符串, 列表对象, hash对象, 集合对象, 有序集合对象)。如下图是redis的数据结构:

3.1 redisObject对象:

redis中的所有value对象都是一个redisObject对象(字符串, 列表对象, hash对象, 集合对象, 有序集合对象)

结构体信息
typedef struct redisObject { 
    //对象的类型 占4位, 五种对象类型
    unsigned type;
    // 对象内部编码 占4位,  
    unsigned encoding;
    //指向底层实现数据结构的指针 指向具体的数据
    void *ptr;
    //对象被引用次数
    int refcount;
    // 24位 高16位存储一个分钟数级别的时间戳，低8位存储访问计数
    // lru 使用 高16位: 最后被访问的时间
    // lfu 使用 低8位：最近访问次数
    unsigned lru; 
}

3.2 字符串对象

string对象使用了sds(simple dynamic string)动态字符串。用于存储字符串和整形数据。

struct sdshdr{ 
    //记录buf数组中已使用字节的数量 
    int len; 
    //记录 buf 数组中未使用字节的数量 
    int free; 
    //字符数组，用于保存字符串 
    char buf[]; 
}

sds优势:
1.sds在字符串的基础上加了free和len字段, 在获取字符串长度的时候, 可以直接获取, 时间复杂度是O(1).
2.sds记录了长度, 避免了缓存区的溢出。
3.二进制安全问题。对于存储图片，音频，视频，压缩文件的二进制数据,肯定会有空字符串’\0’, redis不判断空字符，他判断长度,所以不会存在识别部分数据的问题。

3.3. intset整数集合

是一个有序的（整数升序）、存储整数的连续存储结构.

typedef struct intset{ 
    //编码方式 
    uint32_t encoding; 
    //集合包含的元素数量
    uint32_t length; 
    //保存元素的数组
    int8_t contents[]; 
}intset;

3.4 ziplist(压缩列表)

压缩列表（ziplist）本质上就是一个字节数组，是Redis为了节约内存而设计的一种线性数据结构，一个 ziplist 可以包含任意多个 entry，每一个 entry 又可以保存一个字节数组或者一个整数值。ziplist最大特点是它不维护前后节点的指针, 而是维护了上一个节点的长度和当前节点的长度。然后每次通过长度来计算出前后节点的位置, 这就是一种典型的用「时间来换取空间」的做法。
Redis的有序集合、哈希以及列表都直接或者间接使用了压缩列表。当有序集合或哈希的元素数目比较少，且元素都是短字符串时，Redis便使用压缩列表作为其底层数据存储方式。列表使用快速链表（quicklist）数据结构存储.


每一个压缩列表的节点有三个属性组成previous_entry_length(前一个节点的长度), encoding, content(可以是整形/可以是字节数组) 三部分组成。
entry 结构如下:

typedef struct zlentry {
    unsigned int prevrawlensize;//存储prevrawlen所占用的字节数
    unsigned int prevrawlen;//存储上一个链表节点需要的字节数
    unsigned int lensize;//存储len所占用的字节数
    unsigned int len;//存储链表当前节点的字节数
    unsigned int headersize;//当前链表节点的头部大小(prevrawlensize + lensize)即非数据域的大小
    unsigned char encoding;//编码方式
    unsigned char *p;//指向当前节点的起始位置(因为列表内的数据也是一个字符串对象)
} zlentry;

3.5 quicklist(快速列表)

快速列表是列表底层的重要实现, 是双向列表和压缩列表的结合. quicklist是双向列表, 链表的每一个节点是ziplist结构. 每一个ziplist能存储多个数据元素。

PS: 可以进一步对ziplist进行压缩, 采取的方式是(LZF:数据与前面重复, 不去记录原始数据, 而是记录重复位置以及长度)

3.6 dict(字典)

字典dict又称散列表（hash）, 是用来存储键值对的一种数据结构。Redis整个数据库是用字典来存储的。
这里类似于hashmap的存储结构, 有一个数组, 用来存储数据的容器, 通过hash计算来决定存储的下标(hash冲突),如果冲突则采用拉链法存储数据, 当根据key找Value时，找到数组下标，遍历单链表可以找出key相同的value。

3.6.1 实现

3.6.2 特殊点:

typedef struct dict { 
    dictType *type; // 该字典对应的特定操作函数 
    void *privdata; // 上述类型函数对应的可选参数 
    dictht ht[2]; /* 两张哈希表，存储键值对数据，ht[0]为原生 哈希表， ht[1]为 rehash 哈希表 */ 
    long rehashidx; /*rehash标识 当等于-1时表示没有在 rehash， 否则表示正在进行rehash操作，存储的值表示 hash表 ht[0]的rehash进行到哪个索引值 (数组下标)*/ 
    int iterators; // 当前运行的迭代器数量 
} dict;

在字典结构中, 存储两张hash表, ht[0]代表原生hash表, ht[1]代表rehash哈希表. 原因:redis采用的是渐进式hash。

渐进式hash步骤:

1. 初次申请默认容量为4个dictEntry，非初次申请为当前hash表容量的一倍。

   1. rehashidx=0表示要进行rehash操作。
      3. 新增加的数据在新的hash表h[1]
      4. 修改、删除、查询在老hash表h[0]、新hash表h[1]中（rehash中）
      5. 一点点的, 将老的hash表h[0]的数据重新计算索引值后全部迁移到新的hash表h[1]中, 当最后一个元素移完成后, 老hash表内存被回收.

3.7 跳跃表

3.7.1 跳跃表的基本思想：

1. 将有序链表中的部分节点分层，每一层都是一个有序链表。
2. 在查找时优先从最高层开始向后查找，当到达某个节点时，如果next节点值大于要查找的值或next指针指向null，则从当前节点下降一层继续向后查找。
比如要寻找7, 常规情况是0,1,2,5,6,7. 但是使用跳跃表的时候,我们在第二层寻找中, 发现10大于要查找的值.接着向下一层继续寻找, 发现8还是大于要寻找的值, 继续向下一层, 寻找到了想要的7.

4. 问题:

1. 疑问: 存储对象信息是使用string还是使用hash

2. hash 结构也可以用来存储用户信息，不同于字符串一次性需要全部序列化整个对象. hash 可以对用户结构中的每个字段单独存储。这样当我们需要获取用户信息时可以进行部分获取。缺点: hash 结构的存储消耗要高于单个字符串
   2. 整个字符串的形式去保存用户信息的话就只能一次性全部读取, 方便简单, 但是会比较浪费网络流量。

3. 疑问: redis锁 & zk锁