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...