從 Bitmap 到布隆過濾器，再到高并發(fā)緩存設(shè)計(jì)策略！
點(diǎn)擊上方“碼農(nóng)突圍”，馬上關(guān)注
這里是碼農(nóng)充電第一站，回復(fù)“666”，獲取一份專屬大禮包
真愛，請(qǐng)?jiān)O(shè)置“星標(biāo)”或點(diǎn)個(gè)“在看
前言：怎么能把風(fēng)馬牛不相及的概念串在一塊，就得看筆者的本事了。
bitmap和布隆過濾器
海量整數(shù)中是否存在某個(gè)值--bitmap
在一個(gè)程序中，經(jīng)常有讓我們判斷一個(gè)集合中是否存在某個(gè)數(shù)的case；大多數(shù)情況下，只需要用map或是list這樣簡單的數(shù)據(jù)結(jié)構(gòu)，如果使用的是高級(jí)語言，還能乘上快車調(diào)用幾個(gè)封裝好的api，加幾個(gè)if else，兩三行代碼就可以在控制臺(tái)看自己“完美”而又“健壯”的代碼跑起來了。
bitmap則使用位數(shù)代表數(shù)的大小，bit中存儲(chǔ)的0或者1來標(biāo)識(shí)該整數(shù)是否存在，具體模型如下：
這是一個(gè)能標(biāo)識(shí)0-9的“bitmap”，其中4321這四個(gè)數(shù)存在
計(jì)算一下bitmap的內(nèi)存開銷，如果是1億以內(nèi)的數(shù)據(jù)查找，我們只需要1億個(gè)bit = 12MB左右的內(nèi)存空間，就可以完成海量數(shù)據(jù)查找了，是不是極其誘人的一個(gè)內(nèi)存縮減，以下為Java實(shí)現(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)于對(duì)一個(gè)數(shù)字進(jìn)行右移動(dòng)3位，相當(dāng)于除以8
int index = number >> 3;
//相當(dāng)于 number % 8 獲取到byte[index]的位置
int position = number & 0x07;
//進(jìn)行|或運(yùn)算 參加運(yùn)算的兩個(gè)對(duì)象只要有一個(gè)為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ù)組和位運(yùn)算，就能做到時(shí)間與空間的完美均衡，是不是美美噠，wrong！
試想一下，如果我們明確這是一個(gè)一億以內(nèi)，但是數(shù)量級(jí)只有10的集合，我們使用bitmap，同樣需要開銷12M的數(shù)據(jù)，如果是10億以內(nèi)的數(shù)據(jù)，開銷就會(huì)漲到120M，bitmap的空間開銷永遠(yuǎn)是和他的數(shù)據(jù)取值范圍掛鉤的，只有在海量數(shù)據(jù)下，他才能夠大顯身手。
再說說剛剛提到的那個(gè)極端case，假設(shè)這個(gè)數(shù)據(jù)量在一千萬，但是取值范圍好死不死就在十個(gè)億以內(nèi)，那我們不可避免還是要面對(duì)120M的開銷，有方法應(yīng)對(duì)么？
布隆過濾器
如果面對(duì)筆者說的以上問題，我們結(jié)合一下常規(guī)的解決方案，譬如說hash一下，我將十億以內(nèi)的某個(gè)數(shù)據(jù)，hash成一億內(nèi)的某個(gè)值，再去bitmap中查怎么樣，如下圖，布隆過濾器就是這么干的：
利用多個(gè)hash算法得到的值，減小hash碰撞的概率。
像上面的圖注所說，我們可以利用多個(gè)hash算法減小碰撞概率，但只要存在碰撞，就一定會(huì)有錯(cuò)誤判斷，我們無法百分百確定一個(gè)值是否真的存在，但是hash算法的魅力在于，我不能確定你是否存在，但是我可以確定你是否真的不存在，這也就是以上的實(shí)現(xiàn)為什么稱之“過濾器”的原因了。
高并發(fā)緩存設(shè)計(jì)策略
why cache??
如果讀者是一個(gè)計(jì)算機(jī)專業(yè)的同學(xué)，cache這個(gè)詞應(yīng)該是能達(dá)到讓耳朵起繭的出現(xiàn)頻次。在計(jì)算機(jī)體系中，cache是介于cpu以及內(nèi)存之間，用來緩和cpu和內(nèi)存處理速度差距的那么一個(gè)和事佬；在OS中，page cache又是內(nèi)存和IO之間的和事佬。
cache是個(gè)和事老？？聽著似乎怪怪的，但是也蠻形象的啦。
前面講了大半截的算法理論，為了防止讀者犯困，直接進(jìn)入下半部分主題，高并發(fā)緩存設(shè)計(jì)。
即使是在軟件層，我們同樣需要這么一個(gè)和事老，從最簡單的服務(wù)架構(gòu)開始，通常我們在服務(wù)端發(fā)起請(qǐng)求，然后CURD某個(gè)關(guān)系型數(shù)據(jù)庫例如Mysql。但是，類似這樣的架構(gòu)都需要有一個(gè)磁盤作為終端持久化，即使增加索引，使用B+樹的這種數(shù)據(jù)結(jié)構(gòu)進(jìn)行優(yōu)化查詢，效率還是會(huì)卡在需要頻繁尋道的IO上。
這個(gè)時(shí)候，一個(gè)和事老的作用就十分明顯了，我們會(huì)添加一些內(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；
緩存穿透問題
第二種方案，就是使用布隆過濾器（點(diǎn)題），在cache與web服務(wù)器中間加一層布隆過濾器，對(duì)訪問的key做記錄，如此以來，同樣可以解決緩存擊穿的問題。
緩存雪崩問題
緩存雪崩發(fā)生于在某個(gè)時(shí)間點(diǎn)，緩存同時(shí)失效，例如緩存設(shè)置了失效時(shí)間，這會(huì)聯(lián)動(dòng)的導(dǎo)致大量緩存擊穿問題。
加分布式鎖是一種解決方案，只有拿到鎖的請(qǐng)求才能訪問database。但是這樣治標(biāo)不治本，當(dāng)請(qǐng)求量過多時(shí)，大量的線程阻塞，也會(huì)把內(nèi)存撐壞的。
預(yù)熱數(shù)據(jù)，分散地設(shè)置失效時(shí)間，這樣可以減少緩存雪崩發(fā)生的概率。
提高緩存可用性，cache的單點(diǎn)一樣是會(huì)是緩存雪崩的隱患，大部分緩存中間件都提供高可用架構(gòu)，如redis的主從+哨兵架構(gòu)。
原文鏈接：https://blog.csdn.net/that_is_cool/article/details/91346356
版權(quán)聲明：本文為CSDN博主「that_is_cool」的原創(chuàng)文章，遵循CC 4.0 BY-SA版權(quán)協(xié)議，轉(zhuǎn)載請(qǐng)附上原文出處鏈接及本聲明。
- END - 最近熱文
? 殺毒軟件 McAfee 創(chuàng)始人自殺，75 年傳奇人生畫下句號(hào) ? 大專學(xué)歷造假改成了 211 拿到了抖音 Offer ? 霸氣！女學(xué)霸考692分想當(dāng)“程序媛”，女王式發(fā)言：也沒見男生考得比我好 ? 騰訊面試官：如何停止一個(gè)正在運(yùn)行的線程？我一臉蒙蔽。。。