布隆过滤器
1、讲一讲布隆过滤器？
布隆过滤器，它是一个连续的数据结构，每个存储位存储都是一个bit，即0或者1, 可以用来快速判断某个数据是否存在。
标记某个数据时： 我们使用K个不同的哈希函数将这个数据映射为bit数组上的K个点，并把它们置为1。
查询某个数据时：先使用K个哈希函数得到这个数据在bit数组中对应的k个位置 ，然后判断bit值是不是1：
- 只要有一个不是1，就说明布隆过滤器没有对该数据做过标，即该数据不存在 ；
- 如果都是1，也只是表示数据可能存在。
优点：
- 布隆过滤器的查询速度很快，一般只需要几毫秒；
- 布隆过滤器只需要很少的空间，因为它只是一个位数组。
缺点：
- 它在判断元素是否在集合中时是有一定错误机率，因为哈希算法有一定的碰撞的概率。
- 不支持删除元素。
2、布隆过滤器的误判率如何解决优化？
布隆过滤器的误判率可以通过调整布隆过滤器的参数来优化：
主要有两个参数：
- 位数组的大小：越大，误判率就越小。但是，位数组越大，所需的空间就越大。
- 哈希函数的个数：越多，误判率就越小。但是，哈希函数越多，查询时间就越长。
优化
- 一般来说，当位数组的大小和哈希函数的个数同时增大时，布隆过滤器的误判率会越来越小。但是，要注意的是，当位数组的大小或哈希函数的个数超过某个值时，布隆过滤器的性能可能不再提升，甚至可能下降。
- 此外，还可以通过使用更高效的哈希函数来优化布隆过滤器的性能。一般来说，使用高质量的哈希函数能够提高布隆过滤器的性能，减小误判率。
- 另外，还可以通过使用多个布隆过滤器，并将它们组合起来使用，来进一步优化布隆过滤器的性能。例如，可以使用多个布隆过滤器，并将它们的结果用位或运算结合起来，从而降低误判率。
应用
1、Redis如何实现去重？
- 使用set类型：Redis中的set类型是一个无序的集合，它可以用于存储不重复的元素。使用set类型可以方便地实现去重，每次添加元素时会自动去重，如果元素已经存在于set中，则不会重复添加。set类型的优点是快速且内存占用较小，但不支持元素的顺序操作。
- 使用sorted set类型：Redis中的sorted set类型是一个有序的集合，它可以用于存储不重复的元素，并且支持按照分数进行排序。使用sorted set类型可以实现去重，并且可以按照指定的分数对元素进行排序。sorted set类型的优点是支持按照分数进行排序，并且可以使用zrange和zrevrange等命令获取有序集合中的元素，但相比set类型内存占用更大。
- 使用bitmap类型：Redis中的bitmap类型是一个位图，可以用于存储一组二进制位。使用bitmap类型可以实现去重，每个元素对应bitmap中的一位，如果该位为1，则表示该元素已经存在。bitmap类型的优点是内存占用较小，但相比set类型和sorted set类型只支持二进制位的操作。
- 使用HyperLogLog类型：Redis中的HyperLogLog类型是一种基数算法，可以用于估计一个集合中不重复元素的数量。使用HyperLogLog类型可以实现去重，但是无法获取具体的元素，只能获取去重后的元素数量。HyperLogLog类型的优点是内存占用非常小，但估计的元素数量可能会存在误差。
2、Redis如何实现分布式锁？
2.1 基于单个节点
加锁
在基于单个Redis实例实现分布式锁时，对于加锁操作，我们需要满足四个条件:
- 加锁包括了读取锁变量、检查锁变量值和设置锁变量值三个操作，但需要以原子操作的方式完成，所以，我们使用SET命令带上NX选项来实现加锁；
- 锁变量需要设置过期时间，以免客户端拿到锁后发生异常，导致锁一直无法释放，所以，我们在SET命令执行时加上EX/PX选项，设置其过期时间；
- 锁变量的值需要能区分来自不同客户端的加锁操作，以免在释放锁时，出现误释放操作，所以，我们使用SET命令设置锁变量值时，每个客户端设置的值是一个唯一值，用于标识客户端。
- 为了实现可重入，为每个锁关联一个请求计数器和一个占有它的线程。
- 当计数为0时，认为锁是未被占有的；
- 线程请求一个未被占有的锁时，JVM将记录锁的占有者，并且将请求计数器置为1 。
解锁
和加锁类似，释放锁也包含了读取锁变量值、判断锁变量值和删除锁变量三个操作，不过，我们无法使用单个命令来实现，所以，我们可以采用Lua脚本执行释放锁操作，通过Redis原子性地执行Lua脚本，来保证释放锁操作的原子性。
2.2 基于多个节点
为了避免Redis实例故障而导致的锁无法工作的问题，可以使用分布式锁算法Redlock。
Redlock算法的基本思路：
- 让客户端和多个独立的Redis实例依次请求加锁，如果客户端能够和半数以上的实例成功地完成加锁操作，那么我们就认为，客户端成功地获得分布式锁了，否则加锁失败。
- 这样一来， 即使有单个Redis实例发生故障，因为锁变量在其它实例上也有保存，所以，客户端仍然可以正常地进行锁操作，锁变量并不会丢失。
加锁
Redlock算法的实现需要有N个独立的Redis实例，可以分成3步来完成加锁操作：
- 第一步是，客户端获取当前时间。
- 第二步是，客户端按顺序依次向N个Redis实例执行加锁操作。
- 第三步是，一旦客户端完成了和所有Redis实例的加锁操作，客户端就要计算整个加锁过程的总耗时。
客户端只有在满足下面的这两个条件时，才能认为是加锁成功。
- 条件一：客户端从超过半数（大于等于 N/2+1）的Redis实例上成功获取到了锁；
- 条件二：客户端获取锁的总耗时没有超过锁的有效时间。
如果客户端在和所有实例执行完加锁操作后，没能同时满足这两个条件，那么，客户端向所有Redis 节点发起释放锁的操作。
释放锁
在Redlock算法中，释放锁的操作和在单实例上释放锁的操作一样，只要执行释放锁的Lua脚本就可以了。
这样一来，只要N个Redis实例中的半数以上实例能正常工作，就能保证分布式锁的正常工作了。
3、Redis如何实现消息队列？
- 使用list类型：Redis中的list类型可以用于实现队列，每个元素都可以看作是一个消息。使用lpush和rpop等命令可以将消息添加到队列中，并从队列中取出消息。如果需要支持多个消费者，可以使用blpop和brpop等命令，这些命令会在队列中有新的消息时阻塞，直到有消息可以取出为止。使用list类型可以实现简单的消息队列，但不支持消息的优先级和持久化等高级功能。
- 使用Redis Streams：Redis 5.0及以上版本提供了Streams类型，可以用于实现更为高级的消息队列。Streams可以存储多个消息，每个消息都有一个唯一的ID和一个内容。使用XADD命令可以向Streams中添加消息，使用XREAD命令可以从Streams中读取消息。Streams还支持多个消费者，每个消费者可以读取不同的消息，并且可以设置消息的最大长度、过期时间等高级属性。使用Redis Streams可以实现更为复杂的消息队列，支持消息的优先级、持久化和高可用等高级功能。
