redis 6种数据结构
SDS
Redis 是用 C 语言实现的，但是它没有直接使用 C 语言的 char* 字符数组来实现字符串， 而是自己封装了一个名为简单动态字符串（simple dynamic string，SDS） 的数据结构来表示字符串，也就是 Redis 的 String 数据类型的底层数据结构是 SDS
C 语言字符串的缺陷 在 C 语言里，对字符串操作时，char * 指针只是指向字符数组的起始位置，而字符数组的结尾位置就用“\0”表示。
- C 语言获取字符串长度的函数 strlen，就是通过字符数组中的每一个字符，并进行计数，等遇到字符为“\0”后，就会停止遍历，然后返回已经统计到的字符个数，即为字符串长度
- 除了字符串中不能 “\0” 字符外，用 char* 字符串中的字符必须符合某种编码（比如ASCII），这些限制使得 C 语言的字符串只能保存文本数据，不能保存像图片、音频、视频文化这样的二进制数据
- C 语言的字符串是不会记录自身的缓冲区大小的，稍微一不注意，就会导致缓冲区溢出。
综上：
- 获取字符串长度的时间复杂度为 O（N）；
- 字符串的结尾是以 “\0” 字符标识，而且字符必须符合某种编码（比如ASCII），只能保存文本数据，不能保存二进制数据；
- 字符串操作函数不高效且不安全，比如可能会发生缓冲区溢出，从而造成程序运行终止；
SDS 结构设计
- len: SDS 所保存的字符串长度
- alloc: 分配给字符数组的空间长度
- flags: SDS 类型，用来表示不同类型的 SDS, 一共设计了 5 种类型，分别是 sdshdr5、sdshdr8、sdshdr16、sdshdr32 和 sdshdr64
- buf[]: 字节数组，用来保存实际数据, 不需要用 “\0” 字符来标识字符串结尾了，而是直接将其作为二进制数据处理，可以用来保存图片等二进制数据
优点：
- O（1）复杂度获取字符串长度
- 二进制安全
- 不会发生缓冲区溢出
- 节省内存空间，之所以 SDS 设计不同类型的结构体，是为了能灵活保存不同大小的字符串，从而有效节省内存空间。除了设计不同类型的结构体，Redis 在编程上还使用了专门的编译优化来节省内存空间
链表
C 语言本身也是没有链表这个数据结构的，所以 Redis 自己设计了一个链表数据结构
链表节点结构设计
typedef struct listNode {//前置节点struct listNode *prev;//后置节点struct listNode *next;//节点的值void *value;
} listNode;
链表结构设计
Redis 在 listNode 结构体基础上又封装了 list 这个数据结构，这样操作起来会更方便，链表结构如下：
typedef struct list {//链表头节点listNode *head;//链表尾节点listNode *tail;//节点值复制函数void *(*dup)(void *ptr);//节点值释放函数void (*free)(void *ptr);//节点值比较函数int (*match)(void *ptr, void *key);//链表节点数量unsigned long len;
} list;
list 结构为链表提供了链表头指针 head、链表尾节点 tail、链表节点数量 len、以及可以自定义实现的 dup、free、match 函数
Redis 的链表实现优点如下：
- listNode 链表节点带有 prev 和 next 指针，获取某个节点的前置节点或后置节点的时间复杂度只需O(1)，而且这两个指针都可以指向 NULL，所以链表是无环链表；
- list 结构因为提供了表头指针 head 和表尾节点 tail，所以获取链表的表头节点和表尾节点的时间复杂度只需O(1)；
- list 结构因为提供了链表节点数量 len，所以获取链表中的节点数量的时间复杂度只需O(1)；
链表的缺陷也是有的，链表每个节点之间的内存都是不连续的，意味着无法很好利用 CPU 缓存。
能很好利用 CPU 缓存的数据结构就是数组，因为数组的内存是连续的，这样就可以充分利用 CPU 缓存来加速访问。
因此，Redis 的 list 数据类型在数据量比较少的情况下，会采用「压缩列表」作为底层数据结构的实现，压缩列表就是由数组实现的，下面我们会细说压缩列表。
压缩列表
- 当一个列表键（list）只包含少量的列表项，并且每个列表项都是小整数值，或者长度比较短的字符串，那么 Redis 就会使用压缩列表作为列表键（list）的底层实现
- 当一个哈希键（hash）只包含少量键值对，并且每个键值对的键和值都是小整数值，或者长度比较短的字符串，那么 Redis 就会使用压缩列表作为哈希键（hash）的底层实现
压缩列表结构设计
压缩列表是 Redis 为了节约内存而开发的，它是由连续内存块组成的顺序型数据结构，有点类似于数组。
- zlbytes: 记录整个压缩列表占用对内存字节数
- zltail: 记录压缩列表「尾部」节点距离起始地址由多少字节，也就是列表尾的偏移量
- zllen: 记录压缩列表包含的节点数量
- zlend: 标记压缩列表的结束点，特殊值 OxFF（十进制255）
- prevlen: 记录了前一个节点的长度
- encoding: 记录了当前节点实际数据的类型以及长度
- data: 记录了当前节点的实际数据 当我们往压缩列表中插入数据时，压缩列表 就会根据数据是字符串还是整数，以及它们的大小会在 prevlen 和 encoding 这两个元素里保存不同的信息，这种根据数据大小进行对应信息保存的设计思想，正是 Redis 为了节省内存而采用的
连锁更新
压缩列表除了查找复杂度高的问题，压缩列表在插入元素时，如果内存空间不够了，压缩列表还需要重新分配一块连续的内存空间，而这可能会引发连锁更新的问题 压缩列表里的每个节点中的 prevlen 属性都记录了「前一个节点的长度」，而且 prevlen 属性的空间大小跟前一个节点长度值有关
- 如果前一个节点的长度小于 254 字节，那么 prevlen 属性需要用 1 字节的空间来保存这个长度值；
- 如果前一个节点的长度大于等于 254 字节，那么 prevlen 属性需要用 5 字节的空间来保存这个长度值；
现在假设一个压缩列表中有多个连续的、长度在 250～253 之间的节点
因为这些节点长度值小于 254 字节，所以 prevlen 属性需要用 1 字节的空间来保存这个长度值。这时，如果将一个长度大于等于 254 字节的新节点加入到压缩列表的表头节点，即新节点将成为 e1 的前置节点
因为 e1 节点的 prevlen 属性只有 1 个字节大小，无法保存新节点的长度，此时就需要对压缩列表的空间重分配操作，并将 e1 节点的 prevlen 属性从原来的 1 字节大小扩展为 5 字节大小。多米诺牌的效应就此开始
这种在特殊情况下产生的连续多次空间扩展操作就叫做「连锁更新」
因此，压缩列表只会用于保存的节点数量不多的场景，只要节点数量足够小，即使发生连锁更新，也是能接受的。
哈希表
哈希表是一种保存键值对（key-value）的数据结构 哈希表中的每一个 key 都是独一无二的，程序可以根据 key 查找到与之关联的 value 当一个哈希键包含的 key-value 比较多，或者 key-value 中元素都是比较长多字符串时，Redis 就会使用哈希表作为哈希键的底层实现 Hash 表优点在于，它能以 O(1) 的复杂度快速查询数据，但是随着数据不断增多，那么哈希冲突的可能性也会越高。 解决哈希冲突的方式，有很多种。Redis 采用了链式哈希，在不扩容哈希表的前提下，将具有相同哈希值的数据链接起来
rehash
Redis 会使用了两个全局哈希表进行 rehash 在正常服务请求阶段，插入的数据，都会写入到「哈希表 1」，此时的「哈希表 2 」 并没有被分配空间 随着数据逐步增多，触发了 rehash 操作，这个过程分为三步：
- 给「哈希表 2」 分配空间，一般会比「哈希表 1」 大 2 倍
- 将「哈希表 1 」的数据迁移到「哈希表 2」 中
- 迁移完成后，「哈希表 1 」的空间会被释放，并把「哈希表 2」 设置为「哈希表 1」，然后在「哈希表 2」 新创建一个空白的哈希表，为下次 rehash 做准备
渐进式 rehash
为了避免 rehash 在数据迁移过程中，因拷贝数据的耗时，影响 Redis 性能的情况，所以 Redis 采用了渐进式 rehash，也就是将数据的迁移的工作不再是一次性迁移完成，而是分多次迁移
- 给「哈希表 2」 分配空间
- 在 rehash 进行期间，每次哈希表元素进行新增、删除、查找或者更新操作时，Redis 除了会执行对应的操作之外，还会顺序将「哈希表 1 」中索引位置上的所有 key-value 迁移到「哈希表 2」 上
- 随着处理客户端发起的哈希表操作请求数量越多，最终会把「哈希表 1 」的所有 key-value 迁移到「哈希表 2」，从而完成 rehash 操作
在进行渐进式 rehash 的过程中，会有两个哈希表，所以在渐进式 rehash 进行期间，哈希表元素的删除、查找、更新等操作都会在这两个哈希表进行。
比如，查找一个 key 的值的话，先会在哈希表 1 里面进行查找，如果没找到，就会继续到哈希表 2 里面进行找到。
另外，在渐进式 rehash 进行期间，新增一个 key-value 时，会被保存到「哈希表 2 」里面，而「哈希表 1」 则不再进行任何添加操作，这样保证了「哈希表 1 」的 key-value 数量只会减少，随着 rehash 操作的完成，最终「哈希表 1 」就会变成空表。
跳跃表
对于一个单链表来讲，即便链表中存储的数据是有序的，如果我们要想在其中查找某个数据，也只能从头到尾遍历链表。这样查找效率就会很低，时间复杂度会很高，是 O(n)
如果我们想要提高其查找效率，可以考虑在链表上建索引的方式。每两个结点提取一个结点到上一级，我们把抽出来的那一级叫作索引
像这种链表加多级索引的结构，就是跳跃表
Redis使用跳跃表作为有序集合键的底层实现之一,如果一个有序集合包含的元素数量比较多,又或者有序集合中元素的成员是比较长的字符串时, Redis就会使用跳跃表来作为有序集合健的底层实现 跳跃表在链表的基础上增加了多级索引以提升查找的效率，但其是一个空间换时间的方案，必然会带来一个问题——索引是占内存的。原始链表中存储的有可能是很大的对象，而索引结点只需要存储关键值值和几个指针，并不需要存储对象，因此当节点本身比较大或者元素数量比较多的时候，其优势必然会被放大，而缺点则可以忽略
跳跃表的实现
- 一个跳表应该有几个层（level）组成
- 跳表的第一层包含所有的元素
- 每一层都是一个有序的链表
- 如果元素x出现在第i层，则所有比i小的层都包含x
- 第i层的元素通过一个down指针指向下一层拥有相同值的元素
- Head指针指向最高层的第一个元素
Redis的跳跃表由zskiplistNode和skiplist两个结构定义,其中 zskiplistNode结构用于表示跳跃表节点,而 zskiplist结构则用于保存跳跃表节点的相关信息,比如节点的数量,以及指向表头节点和表尾节点的指针等等
- header:指向跳跃表的表头节点，通过这个指针程序定位表头节点的时间复杂度就为O(1)
- tail:指向跳跃表的表尾节点,通过这个指针程序定位表尾节点的时间复杂度就为O(1)
- level:记录目前跳跃表内,层数最大的那个节点的层数(表头节点的层数不计算在内)，通过这个属性可以再O(1)的时间复杂度内获取层高最好的节点的层数
- length:记录跳跃表的长度,也即是,跳跃表目前包含节点的数量(表头节点不计算在内)，通过这个属性，程序可以再O(1)的时间复杂度内返回跳跃表的长度
结构右方的是四个 zskiplistNode结构,该结构包含以下属性
- 层(level): 每个层都带有两个属性:前进指针和跨度
- 前进指针用于访问位于表尾方向的其他节点
- 跨度记录了前进指针所指向节点和当前节点的距离(跨度越大、距离越远)。在上图中,连线上带有数字的箭头就代表前进指针,而那个数字就是跨度
- 每次创建一个新跳跃表节点的时候,程序都根据幂次定律(powerlaw,越大的数出现的概率越小)随机生成一个介于1和32之间的值作为level数组的大小,这个大小就是层的“高度”。
- 后退(backward)指针：节点中用BW字样标记节点的后退指针,它指向位于当前节点的前一个节点。与前进指针所不同的是每个节点只有一个后退指针，因此每次只能后退一个节点。
- 分值(score): 各个节点中的1.0、2.0和3.0是节点所保存的分值。在跳跃表中,节点按各自所保存的分值从小到大排列
- 成员对象(oj): 各个节点中的o1、o2和o3是节点所保存的成员对象。在同一个跳跃表中,各个节点保存的成员对象必须是唯一的,但是多个节点保存的分值却可以是相同的:分值相同的节点将按照成员对象在字典序中的大小来进行排序
代码实现
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
/*** 实现跳跃表*/
public class SkipList<T> {public static void main(String[] args) {SkipList<String> list = new SkipList<>();list.put(1, "1");list.put(2, "2");list.put(3, "3");list.put(5, "5");list.put(100, "100");list.put(66, "66");System.out.println(list);System.out.println("查找66 : " + list.get(66));list.delete(66);}/*** 跳跃表的节点的构成** @param <E>*/private static class SkipNode<E> {/*** 存储的数据*/E val;/*** 跳跃表按照这个分数值进行从小到大排序。*/Integer score;/*** next指针，指向下一层的指针*/SkipNode<E> next, down;SkipNode(E val, int score) {this.val = val;this.score = score;}}/** 节点的高度，这里限制最高 4 层 */private static final int MAX_LEVEL = 4;/*** 跳跃表数据结构*/private SkipNode<T> head;/** 节点级别 */private int level = 0;/*** 用于产生随机数的Random对象**/private Random random = new Random();public SkipList() {//创建默认初始高度的跳跃表this(4);}/*** 跳跃表的初始化*/public SkipList(int level) {this.level = level;int i = level;SkipNode<T> temp = null;SkipNode<T> prev = null;while (i-- != 0) {temp = new SkipNode<T>(null, Integer.MAX_VALUE);temp.down = prev;prev = temp;}//头节点head = temp;}/*** 产生节点的高度。使用抛硬币** @return*/private int getRandomLevel() {int lev = 1;while (random.nextInt() % 2 == 0) {lev++;}return lev > MAX_LEVEL ? MAX_LEVEL : lev;}/*** 查找跳跃表中的一个值** @param score 分数* @return*/public T get(Integer score) {SkipNode<T> t = head;while (t != null) {if (t.score.equals(score)) {return t.val;}if (t.next == null) {if (t.down != null) {t = t.down;continue;} else {return null;}}if (t.next.score > score) {t = t.down;} else {t = t.next;}}return null;}/**** @param score 分数键（排序）* @param val 值*/public void put(Integer score, T val) {SkipNode<T> t = head, cur = null;//记录每一层当前节点的前驱节点List<SkipNode<T>> path = new ArrayList<>();while (t != null) {if (t.score .equals(score)) {//表示存在该值的点，表示需要更新该节点cur = t;break;}if (t.next == null) {//需要向下查找，先记录该节点path.add(t);if (t.down != null) {//进入下一个层级t = t.down;continue;} else {break;}}if (t.next.score > score) {//需要向下查找，先记录该节点path.add(t);if (t.down == null) {break;}t = t.down;} else {t = t.next;}}if (cur != null) {while (cur != null) {cur.val = val;cur = cur.down;}} else {//随机层级int lev = getRandomLevel();if (lev > level) {SkipNode<T> temp = null;//前驱节点现在是top了SkipNode<T> prev = head;while (level++ != lev) {temp = new SkipNode<T>(null, Integer.MIN_VALUE);//加到path的首部path.add(0, temp);temp.down = prev;prev = temp;}//头节点head = temp;//level长度增加到新的长度level = lev;}//从后向前遍历path中的每一个节点，在其后面增加一个新的节点SkipNode<T> downTemp = null, temp, prev;for (int i = level - 1; i >= level - lev; i--) {temp = new SkipNode<T>(val, score);prev = path.get(i);temp.next = prev.next;prev.next = temp;temp.down = downTemp;downTemp = temp;}}}/*** 根据score的值来删除节点。** @param score 分数键（排序）*/public void delete(Integer score) {//1,查找到节点列的第一个节点的前驱SkipNode<T> t = head;while (t != null) {if (t.next == null) {t = t.down;continue;}// 在这里说明找到了该删除的节点if (t.next.score.equals(score)) {t.next = t.next.next;t = t.down;//删除当前节点后，还需要继续查找之后需要删除的节点continue;}if (t.next.score > score) {t = t.down;} else {t = t.next;}}}/*** 输出结果，一层一层输出* @return*/@Overridepublic String toString() {StringBuilder sb = new StringBuilder();SkipNode<T> t = head, next;while (t != null) {next = t;while (next != null) {sb.append(next.score).append(" ");next = next.next;}sb.append("\n");t = t.down;}return sb.toString().replace(Integer.MAX_VALUE+"","").replace("-2147483648","");}
}
持久化
- 客户端向数据库 发送写命令 (数据在客户端的内存中)
- 数据库 接收 到客户端的 写请求 (数据在服务器的内存中)
- 数据库 调用系统 API 将数据写入磁盘 (数据在内核缓冲区中)
- 操作系统将 写缓冲区 传输到 磁盘控控制器 (数据在磁盘缓存中)
- 操作系统的磁盘控制器将数据 写入实际的物理媒介 中 (数据在磁盘中)
Redis 中的两种持久化方式
快照
Redis 快照 是最简单的 Redis 持久性模式。当满足特定条件时，它将生成数据集的时间点快照
Redis 是一个 单线程 的程序，这意味着，我们不仅仅要响应用户的请求，还需要进行内存快照。而后者要求 Redis 必须进行 IO 操作，这会严重拖累服务器的性能
还有一个重要的问题是，我们在 持久化的同时，内存数据结构 还可能在 变化
使用系统多进程 COW(Copy On Write) 机制 | fork 函数
操作系统多进程 COW(Copy On Write) 机制 拯救了我们。Redis 在持久化时会调用 glibc 的函数 fork 产生一个子进程，简单理解也就是基于当前进程复制 了一个进程，主进程和子进程会共享内存里面的代码块和数据段：
所以 快照持久化 可以完全交给 子进程 来处理，父进程 则继续 处理客户端请求。子进程 做数据持久化，它 不会修改现有的内存数据结构，它只是对数据结构进行遍历读取，然后序列化写到磁盘中。但是 父进程 不一样，它必须持续服务客户端请求，然后对 内存数据结构进行不间断的修改。
这个时候就会使用操作系统的 COW 机制来进行 数据段页面 的分离。数据段是由很多操作系统的页面组合而成，当父进程对其中一个页面的数据进行修改时，会将被共享的页面复 制一份分离出来，然后 对这个复制的页面进行修改。这时 子进程 相应的页面是 没有变化的，还是进程产生时那一瞬间的数据。
子进程因为数据没有变化，它能看到的内存里的数据在进程产生的一瞬间就凝固了，再也不会改变，这也是为什么 Redis 的持久化 叫「快照」的原因
AOF
AOF(Append Only File - 仅追加文件) 它的工作方式非常简单：每次执行 修改内存 中数据集的写操作时，都会 记录 该操作。假设 AOF 日志记录了自 Redis 实例创建以来 所有的修改性指令序列，那么就可以通过对一个空的 Redis 实例 顺序执行所有的指令，也就是 「重放」，来恢复 Redis 当前实例的内存数据结构的状态
当 Redis 收到客户端修改指令后，会先进行参数校验、逻辑处理，如果没问题，就 立即 将该指令文本 存储 到 AOF 日志中，也就是说，先执行指令再将日志存盘。这一点不同于 MySQL、LevelDB、HBase 等存储引擎，如果我们先存储日志再做逻辑处理，这样就可以保证即使宕机了，我们仍然可以通过之前保存的日志恢复到之前的数据状态
AOF 重写
Redis 在长期运行的过程中，AOF 的日志会越变越长。如果实例宕机重启，重放整个 AOF 日志会非常耗时，导致长时间 Redis 无法对外提供服务。所以需要对 AOF 日志 "瘦身"。
Redis 提供了 bgrewriteaof 指令用于对 AOF 日志进行瘦身。其 原理 就是 开辟一个子进程 对内存进行 遍历 转换成一系列 Redis 的操作指令，序列化到一个新的 AOF 日志文件 中。序列化完毕后再将操作期间发生的 增量 AOF 日志 追加到这个新的 AOF 日志文件中，追加完毕后就立即替代旧的 AOF 日志文件了，瘦身工作就完成了
fsync
AOF 日志是以文件的形式存在的，当程序对 AOF 日志文件进行写操作时，实际上是将内容写到了内核为文件描述符分配的一个内存缓存中，然后内核会异步将脏数据刷回到磁盘的
我们需要借助 glibc 提供的 fsync(int fd) 函数来讲指定的文件内容 强制从内核缓存刷到磁盘。但 "强制开车" 仍然是一个很消耗资源的一个过程，需要 "节制"！通常来说，生产环境的服务器，Redis 每隔 1s 左右执行一次 fsync 操作就可以了
Redis 4.0 混合持久化
重启 Redis 时，我们很少使用 rdb 来恢复内存状态，因为会丢失大量数据。我们通常使用 AOF 日志重放，但是重放 AOF 日志性能相对 rdb 来说要慢很多，这样在 Redis 实例很大的情况下，启动需要花费很长的时间。
Redis 4.0 为了解决这个问题，带来了一个新的持久化选项——混合持久化。将 rdb 文件的内容和增量的 AOF 日志文件存在一起。这里的 AOF 日志不再是全量的日志，而是 自持久化开始到持久化结束 的这段时间发生的增量 AOF 日志，通常这部分 AOF 日志很小：
于是在 Redis 重启的时候，可以先加载 rdb 的内容，然后再重放增量 AOF 日志就可以完全替代之前的 AOF 全量文件重放，重启效率因此大幅得到提升。
Bitmap
位图简介
如果我们需要记录某一用户在一年中每天是否有登录我们的系统这一需求该如何完成呢？如果使用KV存储，每个用户需要记录365个，当用户量上亿时，这所需要的存储空间是惊人的
Redis 为我们提供了位图这一数据结构，每个用户每天的登录记录只占据一位，365天就是365位，仅仅需要46字节就可存储，极大地节约了存储空间
位图数据结构其实并不是一个全新的玩意，我们可以简单的认为就是个数组，只是里面的内容只能为0或1而已(二进制位数组)
命令实战
Redis提供了SETBIT、GETBIT、BITCOUNT、BITOP四个常用命令用于处理二进制位数组。
- SETBIT：为位数组指定偏移量上的二进制位设置值，偏移量从0开始计数，二进制位的值只能为0或1。返回原位置值。
- GETBIT：获取指定偏移量上二进制位的值。
- BITCOUNT：统计位数组中值为1的二进制位数量。
- BITOP：对多个位数组进行按位与、或、异或运算。
127.0.0.1:6379> SETBIT first 0 1 # 0000 0001
(integer) 0
127.0.0.1:6379> SETBIT first 3 1 # 0000 1001
(integer) 0
127.0.0.1:6379> SETBIT first 0 0 # 0000 1000
(integer) 1127.0.0.1:6379> GETBIT first 0
(integer) 0
127.0.0.1:6379> GETBIT first 3
(integer) 1127.0.0.1:6379> BITCOUNT first # 0000 1000
(integer) 1
127.0.0.1:6379> SETBIT first 0 1 # 0000 1001
(integer) 0
127.0.0.1:6379> BITCOUNT first # 0000 1001
(integer) 2
127.0.0.1:6379> SETBIT first 1 1 # 0000 1011
(integer) 0
127.0.0.1:6379> BITCOUNT first # 0000 1011
(integer) 3127.0.0.1:6379> SETBIT x 3 1
(integer) 0
127.0.0.1:6379> SETBIT x 1 1
(integer) 0
127.0.0.1:6379> SETBIT x 0 1 # 0000 1011
(integer) 0
127.0.0.1:6379> SETBIT y 2 1
(integer) 0
127.0.0.1:6379> SETBIT y 1 1 # 0000 0110
(integer) 0
127.0.0.1:6379> SETBIT z 2 1
(integer) 0
127.0.0.1:6379> SETBIT z 0 1 # 0000 0101
(integer) 0127.0.0.1:6379> BITOP AND andRes x y z #0000 0000
(integer) 1
127.0.0.1:6379> BITOP OR orRes x y z #0000 1111
(integer) 1
127.0.0.1:6379> BITOP XOR x y z #0000 1000
(integer) 1# 对给定的位数组进行按位取反
127.0.0.1:6379> SETBIT value 0 1
(integer) 0
127.0.0.1:6379> SETBIT value 3 1 #0000 1001
(integer) 0
127.0.0.1:6379> BITOP NOT notValue value #1111 0110
(integer) 1
布隆过滤器
布隆过滤器（Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多，缺点是有一定的误识别率和删除困难
布隆过滤器的优点：
- 时间复杂度低，增加和查询元素的时间复杂为O(N)，（N为哈希函数的个数，通常情况比较小）
- 保密性强，布隆过滤器不存储元素本身
- 存储空间小，如果允许存在一定的误判，布隆过滤器是非常节省空间的（相比其他数据结构如Set集合）
布隆过滤器的缺点：
- 有点一定的误判率，但是可以通过调整参数来降低
- 无法获取元素本身
- 很难删除元素
布隆过滤器可以告诉我们 “某样东西一定不存在或者可能存在”，也就是说布隆过滤器说这个数不存在则一定不存，布隆过滤器说这个数存在可能不存在
原理
布隆过滤器它实际上是一个很长的二进制向量和一系列随机映射函数。以Redis中的布隆过滤器实现为例，Redis中的布隆过滤器底层是一个大型位数组（二进制数组）+多个无偏hash函数
无偏hash函数就是能把元素的hash值计算的比较均匀的hash函数，能使得计算后的元素下标比较均匀的映射到位数组中
往布隆过滤器增加元素，添加的key需要根据k个无偏hash函数计算得到多个hash值，然后对数组长度进行取模得到数组下标的位置，然后将对应数组下标的位置的值置为1
布隆过滤器最大的用处就在于判断某样东西一定不存在或者可能存在，而这个就是查询元素的结果。其查询元素的过程如下：
- 通过k个无偏hash函数计算得到k个hash值
- 依次取模数组长度，得到数组索引
- 判断索引处的值是否全部为1，如果全部为1则存在（这种存在可能是误判），如果存在一个0则必定不存在
分布式锁
想要实现分布式锁，必须借助一个外部系统，所有进程都去这个系统上申请「加锁」
而这个外部系统，必须要实现「互斥」的能力，即两个请求同时进来，只会给一个进程返回成功，另一个返回失败（或等待）。
这个外部系统，可以是 MySQL，也可以是 Redis 或 Zookeeper。但为了追求更好的性能，我们通常会选择使用 Redis 或 Zookeeper 来做。
实现
想要实现分布式锁，必须要求 Redis 有「互斥」的能力，我们可以使用 SETNX 命令，这个命令表示SET if Not eXists，即如果 key 不存在，才会设置它的值，否则什么也不做
# SET if Not eXists# 如果不存在set成功返回int的1，这个key存在了返回0SETNX key value# setex是一个原子性(atomic)操作# 将值 value 关联到 key ，并将 key 的生存时间设为 seconds (以秒为单位)。# 如果 key 已经存在，setex命令将覆写旧值SETEX key seconds value
其他问题：
- 锁过期：客户端 1 操作共享资源耗时太久，导致锁被自动释放，之后被客户端 2 持有
- 加锁时，先设置一个过期时间，然后我们开启一个「守护线程」，定时去检测这个锁的失效时间，如果锁快要过期了，操作共享资源还未完成，那么就自动对锁进行「续期」，重新设置过期时间
- 释放别人的锁：客户端 1 操作共享资源完成后，却又释放了客户端 2 的锁
- 客户端在加锁时，设置一个只有自己知道的「唯一标识」进去。 例如，可以是自己的线程 ID，也可以是一个 UUID（随机且唯一），这里我们以 UUID 举例
// 锁是自己的，才释放
if redis.get("lock") == $uuid:redis.del("lock")
这里释放锁使用的是 GET + DEL 两条命令，这时，又会遇到我们前面讲的原子性问题了。
- 客户端 1 执行 GET，判断锁是自己的
- 客户端 2 执行了 SET 命令，强制获取到锁（虽然发生概率比较低，但我们需要严谨地考虑锁的安全性模型）
- 客户端 1 执行 DEL，却释放了客户端 2 的锁 由此可见，这两个命令还是必须要原子执行才行。
怎样原子执行呢？Lua 脚本。 因为 Redis 处理每一个请求是「单线程」执行的，在执行一个 Lua 脚本时，其它请求必须等待，直到这个 Lua 脚本处理完成，这样一来，GET + DEL 之间就不会插入其它命令了。
Redisson 是一个 Java 语言实现的 Redis SDK 客户端，在使用分布式锁时，它就采用了「自动续期」的方案来避免锁过期，这个守护线程我们一般也把它叫做「看门狗」线程
EVAL "local key = KEYS[1]; local value = ARGV[1]; redis.call('SET', key, value);" 1 mykey "myvalue""local key = KEYS[1]; local value = ARGV[1]; redis.call('SET', key, value);" 是要执行的 Lua 脚本。1 表示你将传递一个键给脚本。mykey 是你要传递的实际键名。"myvalue" 是你要传递的实际值。commandExecutor.evalWriteAsync(getName(), LongCodec.INSTANCE, command,//如果锁不存在，则通过hset设置它的值，并设置过期时间"if (redis.call('exists', KEYS[1]) == 0) then " +"redis.call('hset', KEYS[1], ARGV[2], 1); " +"redis.call('pexpire', KEYS[1], ARGV[1]); " +"return nil; " +"end; " +//如果锁已存在，并且锁的是当前线程，则通过hincrby给数值递增1"if (redis.call('hexists', KEYS[1], ARGV[2]) == 1) then " +"redis.call('hincrby', KEYS[1], ARGV[2], 1); " +"redis.call('pexpire', KEYS[1], ARGV[1]); " +"return nil; " +"end; " +//如果锁已存在，但并非本线程，则返回过期时间ttl"return redis.call('pttl', KEYS[1]);",Collections.<Object>singletonList(getName()), internalLockLeaseTime, getLockName(threadId));// lock如果锁已经存在了，那对比一下线程，线程是一个那就证明可以重入，锁在了，但是不是当前线程，证明别人还没释放，那就把剩余时间返回，加锁失败。// unlockcommandExecutor.evalWriteAsync(getName(), LongCodec.INSTANCE, EVAL,//如果锁已经不存在， 发布锁释放的消息"if (redis.call('exists', KEYS[1]) == 0) then " +"redis.call('publish', KEYS[2], ARGV[1]); " +"return 1; " +"end;" +//如果释放锁的线程和已存在锁的线程不是同一个线程，返回null"if (redis.call('hexists', KEYS[1], ARGV[3]) == 0) then " +"return nil;" +"end; " +//通过hincrby递减1的方式，释放一次锁//若剩余次数大于0 ，则刷新过期时间"local counter = redis.call('hincrby', KEYS[1], ARGV[3], -1); " +"if (counter > 0) then " +"redis.call('pexpire', KEYS[1], ARGV[2]); " +"return 0; " +//否则证明锁已经释放，删除key并发布锁释放的消息"else " +"redis.call('del', KEYS[1]); " +"redis.call('publish', KEYS[2], ARGV[1]); " +"return 1; "+"end; " +"return nil;",Arrays.<Object>asList(getName(), getChannelName()), LockPubSub.unlockMessage, internalLockLeaseTime, getLockName(threadId));
小结一下，基于 Redis 的实现分布式锁，前面遇到的问题，以及对应的解决方案：
- 死锁：设置过期时间
- 过期时间评估不好，锁提前过期：守护线程，自动续期
- 锁被别人释放：锁写入唯一标识，释放锁先检查标识，再释放
zk 分布式锁
zk节点有个唯一的特性，就是我们创建过这个节点了，你再创建zk是会报错的，那我们就利用一下他的唯一性去实现一下 创建成功的第一个返回true他就可以继续下面的扣减库存操作，后续的节点访问就会全部报错，扣减失败，我们把它们丢一个队列去排队。
临时顺序节点，可以顺利解决这个问题 全部监听一个节点问题很大，那我们就监听我们的前一个节点，因为是顺序的，很容易找到自己的前后。
zk通过临时节点，解决掉了死锁的问题，一旦客户端获取到锁之后突然挂掉（Session连接断开），那么这个临时节点就会自动删除掉，其他客户端自动获取锁。
zk通过节点排队监听的机制，也实现了阻塞的原理，其实就是个递归在那无限等待最小节点释放的过程。
我上面没实现锁的可重入，但是也很好实现，可以带上线程信息就可以了，或者机器信息这样的唯一标识，获取的时候判断一下
zk的集群也是高可用的，只要半数以上的或者，就可以对外提供服务了
基于zookeeper临时有序节点可以实现的分布式锁。大致思想为：每个客户端对某个方法加锁时，在zookeeper上的与该方法对应的指定节点的目录下，生成一个唯一的瞬时有序节点。判断是否获取锁的方式很简单，只需要判断有序节点中序号最小的一个。当释放锁的时候，只需将这个瞬时节点删除即可。同时，其可以避免服务宕机导致的锁无法释放，而产生的死锁问题。完成业务流程后，删除对应的子节点释放锁。
Redlock
Redis 作者提出的 Redlock 方案，是如何解决主从切换后，锁失效问题的
缓存一致性
先删缓存，再更新数据库
先删除缓存，数据库还没有更新成功，此时如果读取缓存，缓存不存在，去数据库中读取到的是旧值，缓存不一致发生。
解决方案
延时双删 延时双删的方案的思路是，为了避免更新数据库的时候，其他线程从缓存中读取不到数据，就在更新完数据库之后，再sleep一段时间，然后再次删除缓存。
sleep的时间要对业务读写缓存的时间做出评估，sleep时间大于读写缓存的时间即可。
流程如下：
- 线程1删除缓存，然后去更新数据库
- 线程2来读缓存，发现缓存已经被删除，所以直接从数据库中读取，这时候由于线程1还没有更新完成，所以读到的是旧值，然后把旧值写入缓存
- 线程1，根据估算的时间，sleep，由于sleep的时间大于线程2读数据+写缓存的时间，所以缓存被再次删除
- 如果还有其他线程来读取缓存的话，就会再次从数据库中读取到最新值
先更新数据库，再删除缓存
解决方案
先更新数据库，成功后往消息队列发消息，消费到消息后再删除缓存，借助消息队列的重试机制来实现，达到最终一致性的效果。
这个解决方案其实问题更多。
- 引入消息中间件之后，问题更复杂了，怎么保证消息不丢失更麻烦
- 就算更新数据库和删除缓存都没有发生问题，消息的延迟也会带来短暂的不一致性，不过这个延迟相对来说还是可以接受的
进阶版消息队列
为了解决缓存一致性的问题单独引入一个消息队列，太复杂了 其实，一般大公司本身都会有监听binlog消息的消息队列存在，主要是为了做一些核对的工作。
这样，我们可以借助监听binlog的消息队列来做删除缓存的操作。这样做的好处是，不用你自己引入，侵入到你的业务代码中，中间件帮你做了解耦，同时，中间件的这个东西本身就保证了高可用。
当然，这样消息延迟的问题依然存在，但是相比单纯引入消息队列的做法更好一点。
而且，如果并发不是特别高的话，这种做法的实时性和一致性都还算可以接受的。
_web前端开发设计_荆州百度推广_百度一下首页手机版)
