bitmap 和布隆过滤器
海量整数中是否存在某个值 –bitmap
在一个程序中，常常有让咱们判断一个汇合中是否存在某个数的 case；大多数状况下，只须要用 map 或是 list 这样简略的数据结构，如果应用的是高级语言，还能乘上慢车调用几个封装好的 api，加几个 if else，两三行代码就能够在控制台看本人“完满”而又“强壮”的代码跑起来了。
然而，事无完满，在高并发环境下，所有的 case 都会极端化，如果这是一个非常宏大的汇合（给这个宏大一个具体的值吧，一个亿），简略的一个 hash map，不思考链表所需的指针内存空间，一亿个 int 类型的整数，就须要 380 多 M（4byte × 10 ^8），十亿的话就是 4 个 G，不思考性能，光算算这内存开销，即便当初满地都是 128G 的服务器，也不好吃下这一壶。
bitmap 则应用位数代表数的大小，bit 中存储的 0 或者 1 来标识该整数是否存在，具体模型如下：
这是一个能标识 0 - 9 的“bitmap”，其中 4321 这四个数存在
计算一下 bitmap 的内存开销，如果是 1 亿以内的数据查找，咱们只须要 1 亿个 bit = 12MB 左右的内存空间，就能够实现海量数据查找了，是不是极其迷人的一个内存缩减，以下为 Java 实现的 bitmap 代码：
public class MyBitMap {private byte[] bytes;
private int initSize;
public MyBitMap(int size) {if (size <= 0) {return;}
initSize = size / (8) + 1;
bytes = new byte[initSize];
}
public void set(int number) {
// 相当于对一个数字进行右挪动 3 位，相当于除以 8
int index = number >> 3;
// 相当于 number % 8 获取到 byte[index] 的地位
int position = number & 0x07;
// 进行 | 或运算 加入运算的两个对象只有有一个为 1，其值为 1。bytes[index] |= 1 << position;
}
public boolean contain(int number) {
int index = number >> 3;
int position = number & 0x07;
return (bytes[index] & (1 << position)) != 0;
}
public static void main(String[] args) {MyBitMap myBitMap = new MyBitMap(32);
myBitMap.set(30);
myBitMap.set(13);
myBitMap.set(24);
System.out.println(myBitMap.contain(2));
}
}应用简略的 byte 数组和位运算，就能做到工夫与空间的完满平衡，是不是美美哒，wrong！
试想一下，如果咱们明确这是一个一亿以内，然而数量级只有 10 的汇合，咱们应用 bitmap，同样须要开销 12M 的数据，如果是 10 亿以内的数据，开销就会涨到 120M，bitmap 的空间开销永远是和他的数据取值范畴挂钩的，只有在海量数据下，他才可能大显神通。
再说说刚刚提到的那个极其 case，假如这个数据量在一千万，然而取值范畴好死不死就在十个亿以内，那咱们不可避免还是要面对 120M 的开销，有办法应答么？
布隆过滤器
如果面对笔者说的以上问题，咱们联合一下惯例的解决方案，譬如说 hash 一下，我将十亿以内的某个数据，hash 成一亿内的某个值，再去 bitmap 中查怎么样，如下图，布隆过滤器就是这么干的：
利用多个 hash 算法失去的值，减小 hash 碰撞的概率。
像下面的图注所说，咱们能够利用多个 hash 算法减小碰撞概率，但只有存在碰撞，就肯定会有错误判断，咱们无奈百分百确定一个值是否真的存在，然而 hash 算法的魅力在于，我不能确定你是否存在，然而我能够确定你是否真的不存在，这也就是以上的实现为什么称之“过滤器”的起因了。
高并发缓存设计策略
why cache??
如果读者是一个计算机专业的同学，cache 这个词应该是能达到让耳朵起茧的呈现频次。在计算机体系中，cache 是介于 cpu 以及内存之间，用来弛缓 cpu 和内存处理速度差距的那么一个和事佬；在 OS 中，page cache 又是内存和 IO 之间的和事佬。
cache 是个和事老？？听着仿佛怪怪的，然而也蛮形象的啦。
后面讲了大半截的算法实践，为了避免读者犯困，间接进入下半局部主题，高并发缓存设计。
即便是在软件层，咱们同样须要这么一个和事老，从最简略的服务架构开始，通常咱们在服务端发动申请，而后 CURD 某个关系型数据库例如 Mysql。然而，相似这样的架构都须要有一个磁盘作为终端长久化，即便减少索引，应用 B + 树的这种数据结构进行优化查问，效率还是会卡在须要频繁寻道的 IO 上。
这个时候，一个和事老的作用就非常显著了，咱们会增加一些内存操作，来弛缓 IO 处理速度慢带来的压力。cache is not a problem，how to use it is actually a problem。
缓存一致性问题
缓存解决的机制有以下几种：
- cache aside；
- read through；
- write through；
- write behind caching；
缓存穿透问题
所谓的缓存击穿，就是当申请收回，而无奈在缓存中读到数据时，申请还是会作用到 database，这样的话，缓存减压的成果就不复存在了。
构想这么一个场景，如果一个用户，应用大流量歹意频繁地去查问一条数据库中没有的记录，始终击穿缓存，势必会把 database 打死，如何防止缓存击穿，这就是一个问题了。
有两种计划，第一种，在缓存中增加空值，如果在 database 中查问无果，咱们大能够把值设置为 null，避免下次再次拜访数据库，这样做简略便捷，然而多少有些节约空间。
第二种计划，就是应用布隆过滤器（点题），在 cache 与 web 服务器两头加一层布隆过滤器，对拜访的 key 做记录，如此以来，同样能够解决缓存击穿的问题。
缓存雪崩问题
缓存雪崩产生于在某个工夫点，缓存同时生效，例如缓存设置了生效工夫，这会联动的导致大量缓存击穿问题。
加分布式锁是一种解决方案，只有拿到锁的申请能力拜访 database。然而这样治标不治本，当申请量过多时，大量的线程阻塞，也会把内存撑坏的。
预热数据，扩散地设置生效工夫，这样能够缩小缓存雪崩产生的概率。
进步缓存可用性，cache 的单点一样是会是缓存雪崩的隐患，大部分缓存中间件都提供高可用架构，如 redis 的主从 + 哨兵架构。
原文链接：https://blog.csdn.net/that_is…