從bitmap到布隆過濾器，再到高并發(fā)緩存設(shè)計策略

前言：怎么能把風(fēng)馬牛不相及的概念串在一塊，就得看筆者的本事了。

bitmap和布隆過濾器

海量整數(shù)中是否存在某個值--bitmap

在一個程序中，經(jīng)常有讓我們判斷一個集合中是否存在某個數(shù)的case；大多數(shù)情況下，只需要用map或是list這樣簡單的數(shù)據(jù)結(jié)構(gòu)，如果使用的是高級語言，還能乘上快車調(diào)用幾個封裝好的api，加幾個if else，兩三行代碼就可以在控制臺看自己“完美”而又“健壯”的代碼跑起來了。

但是，事無完美，在高并發(fā)環(huán)境下，所有的case都會極端化，如果這是一個十分龐大的集合（給這個龐大一個具體的值吧，一個億），簡單的一個hash map，不考慮鏈表所需的指針內(nèi)存空間，一億個int類型的整數(shù)，就需要380多M（4byte × 10 ^8），十億的話就是4個G，不考慮性能，光算算這內(nèi)存開銷，即使現(xiàn)在滿地都是128G的服務(wù)器，也不好吃下這一壺。

bitmap則使用位數(shù)代表數(shù)的大小，bit中存儲的0或者1來標(biāo)識該整數(shù)是否存在，具體模型如下：

計算一下bitmap的內(nèi)存開銷，如果是1億以內(nèi)的數(shù)據(jù)查找，我們只需要1億個bit = 12MB左右的內(nèi)存空間，就可以完成海量數(shù)據(jù)查找了，是不是極其誘人的一個內(nèi)存縮減，以下為Java實現(xiàn)的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) {
        //相當(dāng)于對一個數(shù)字進(jìn)行右移動3位，相當(dāng)于除以8
        int index = number >> 3;
        //相當(dāng)于 number % 8 獲取到byte[index]的位置
        int position = number & 0x07;
        //進(jìn)行|或運算  參加運算的兩個對象只要有一個為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數(shù)組和位運算，就能做到時間與空間的完美均衡，是不是美美噠，wrong！試想一下，如果我們明確這是一個一億以內(nèi)，但是數(shù)量級只有10的集合，我們使用bitmap，同樣需要開銷12M的數(shù)據(jù)，如果是10億以內(nèi)的數(shù)據(jù)，開銷就會漲到120M，bitmap的空間開銷永遠(yuǎn)是和他的數(shù)據(jù)取值范圍掛鉤的，只有在海量數(shù)據(jù)下，他才能夠大顯身手。

再說說剛剛提到的那個極端case，假設(shè)這個數(shù)據(jù)量在一千萬，但是取值范圍好死不死就在十個億以內(nèi)，那我們不可避免還是要面對120M的開銷，有方法應(yīng)對么？

布隆過濾器

如果面對筆者說的以上問題，我們結(jié)合一下常規(guī)的解決方案，譬如說hash一下，我將十億以內(nèi)的某個數(shù)據(jù)，hash成一億內(nèi)的某個值，再去bitmap中查怎么樣，如下圖，布隆過濾器就是這么干的：

像上面的圖注所說，我們可以利用多個hash算法減小碰撞概率，但只要存在碰撞，就一定會有錯誤判斷，我們無法百分百確定一個值是否真的存在，但是hash算法的魅力在于，我不能確定你是否存在，但是我可以確定你是否真的不存在，這也就是以上的實現(xiàn)為什么稱之“過濾器”的原因了。

高并發(fā)緩存設(shè)計策略

why cache??

如果讀者是一個計算機(jī)專業(yè)的同學(xué)，cache這個詞應(yīng)該是能達(dá)到讓耳朵起繭的出現(xiàn)頻次。在計算機(jī)體系中，cache是介于cpu以及內(nèi)存之間，用來緩和cpu和內(nèi)存處理速度差距的那么一個和事佬；在OS中，page cache又是內(nèi)存和IO之間的和事佬。

cache是個和事老？？聽著似乎怪怪的，但是也蠻形象的啦。

前面講了大半截的算法理論，為了防止讀者犯困，直接進(jìn)入下半部分主題，高并發(fā)緩存設(shè)計。

即使是在軟件層，我們同樣需要這么一個和事老，從最簡單的服務(wù)架構(gòu)開始，通常我們在服務(wù)端發(fā)起請求，然后CURD某個關(guān)系型數(shù)據(jù)庫例如Mysql。但是，類似這樣的架構(gòu)都需要有一個磁盤作為終端持久化，即使增加索引，使用B+樹的這種數(shù)據(jù)結(jié)構(gòu)進(jìn)行優(yōu)化查詢，效率還是會卡在需要頻繁尋道的IO上。這個時候，一個和事老的作用就十分明顯了，我們會添加一些內(nèi)存操作，來緩和IO處理速度慢帶來的壓力。cache is not a problem，how to use it is actually a problem。

緩存一致性問題

緩存處理的機(jī)制有以下幾種：

• cache aside；
• read through；
• write through；
• write behind caching；

緩存穿透問題

所謂的緩存擊穿，就是當(dāng)請求發(fā)出，而無法在緩存中讀到數(shù)據(jù)時，請求還是會作用到database，這樣的話，緩存減壓的效果就不復(fù)存在了。

設(shè)想這么一個場景，如果一個用戶，使用大流量惡意頻繁地去查詢一條數(shù)據(jù)庫中沒有的記錄，一直擊穿緩存，勢必會把database打死，如何避免緩存擊穿，這就是一個問題了。

有兩種方案，第一種，在緩存中添加空值，如果在database中查詢無果，我們大可以把值設(shè)置為null，防止下次再次訪問數(shù)據(jù)庫，這樣做簡單便捷，但是多少有些浪費空間。

第二種方案，就是使用布隆過濾器（點題），在cache與web服務(wù)器中間加一層布隆過濾器，對訪問的key做記錄，如此以來，同樣可以解決緩存擊穿的問題。

緩存雪崩問題

緩存雪崩發(fā)生于在某個時間點，緩存同時失效，例如緩存設(shè)置了失效時間，這會聯(lián)動的導(dǎo)致大量緩存擊穿問題。

加分布式鎖是一種解決方案，只有拿到鎖的請求才能訪問database。但是這樣治標(biāo)不治本，當(dāng)請求量過多時，大量的線程阻塞，也會把內(nèi)存撐壞的。

預(yù)熱數(shù)據(jù)，分散地設(shè)置失效時間，這樣可以減少緩存雪崩發(fā)生的概率。

提高緩存可用性，cache的單點一樣是會是緩存雪崩的隱患，大部分緩存中間件都提供高可用架構(gòu)，如redis的主從+哨兵架構(gòu)。