建站
咨詢
售后
建站咨詢
新聞中心
一、序言
當(dāng)數(shù)據(jù)量達(dá)到億級(jí)別時(shí)，內(nèi)存空間的占用顯著表現(xiàn)出來，BitMap便是解決此類問題的一種途徑。
建網(wǎng)站原本是網(wǎng)站策劃師、網(wǎng)絡(luò)程序員、網(wǎng)頁設(shè)計(jì)師等，應(yīng)用各種網(wǎng)絡(luò)程序開發(fā)技術(shù)和網(wǎng)頁設(shè)計(jì)技術(shù)配合操作的協(xié)同工作。成都創(chuàng)新互聯(lián)公司專業(yè)提供成都網(wǎng)站建設(shè)、成都做網(wǎng)站,網(wǎng)頁設(shè)計(jì),網(wǎng)站制作(企業(yè)站、自適應(yīng)網(wǎng)站建設(shè)、電商門戶網(wǎng)站)等服務(wù),從網(wǎng)站深度策劃、搜索引擎友好度優(yōu)化到用戶體驗(yàn)的提升,我們力求做到極致!
二、BitMap結(jié)構(gòu)
1、內(nèi)存消耗分析
Redis BitMap能夠存儲(chǔ)的數(shù)據(jù)范圍為[0,2^32-1]，超過Integer.MAX_VALUE上界值。
為了簡化討論，假設(shè)討論的集合元素的范圍為[0,Integer.MAX_VALUE]，可以是其中的任何一個(gè)數(shù)。
使用HashSet數(shù)據(jù)結(jié)構(gòu)占用內(nèi)存空間僅與集合中的元素?cái)?shù)量(N)相關(guān)。當(dāng)集合中元素?cái)?shù)量為N時(shí)，所需的內(nèi)存空間大概為N*4/1024/1024MB，1億條數(shù)據(jù)約占內(nèi)存空間381MB。
基于Redis的BitMap所占用的空間大小不與集合中元素?cái)?shù)量相關(guān)，與集合中元素的最大值直接相關(guān)，因此BitMap所占用的內(nèi)存空間范圍為[N / 8 / 1024 / 1024,Integer.MAX_VALUE / 8 / 1024 / 1024]。
// 測試1億、5億、10億、Integer.MAX_VALUE
Listitems = Arrays.asList(100000000, 500000000, 1000000000, Integer.MAX_VALUE);
for (Integer item : items) {
int size = item / 8 / 1024 / 1024;
System.out.printf("如果集合中最大值為%-10s,則所占用的內(nèi)存空間為%3sMB%n",item, size);
}
這里給出了一組測試參考數(shù)據(jù)
如果集合中最大值為100000000 ,則所占用的內(nèi)存空間為 11MB
如果集合中最大值為500000000 ,則所占用的內(nèi)存空間為 59MB
如果集合中最大值為1000000000,則所占用的內(nèi)存空間為119MB
如果集合中最大值為2147483647,則所占用的內(nèi)存空間為255MB
當(dāng)集合中數(shù)據(jù)增長到10億條時(shí)，使用BItMap最大占用內(nèi)存約為255MB，而使用HashSet增長到3.8GB。
2、命令行操作BitMap
使用Redis命令行可直接操作BitMap，將offset位置的值標(biāo)注為1，則表示當(dāng)前數(shù)據(jù)存在。默認(rèn)情況下未標(biāo)注的位置值為0。
# 默認(rèn)位不賦值為0，當(dāng)數(shù)據(jù)存在于集合中，將對應(yīng)位賦值為1
SETBIT key offset value
# 查看對應(yīng)位數(shù)據(jù)是否存在（1表示存在，0表示不存在）
GETBIT key offset
3、客戶端操作BitMap
這里提供一個(gè)SpringBoot生態(tài)的RedisUtils工具類，內(nèi)部封裝操作Redis BitMap的工具方法。
// 將當(dāng)前位置標(biāo)記為true
RedisUtils.setBit(BIT_MAP_KEY, orderId, true);
// 獲取指定位置的值（對應(yīng)數(shù)值是否存在）
RedisUtils.getBit(BIT_MAP_KEY, orderId)
上述工具類的依賴如下，如果找不到Jar包，請直接使用Maven原始倉庫源，阿里云尚未同步完成。
xin.altitude.cms
ucode-cms-common
1.4.3
4、時(shí)間與空間復(fù)雜度
BitMap的存儲(chǔ)與取值時(shí)間復(fù)雜度為O(1)，根據(jù)數(shù)值可直接映射下標(biāo)。
BitMap占用內(nèi)存空間復(fù)雜度為O(n)，與集合中元素的最大值正相關(guān)，不是集合中元素的數(shù)量。
三、BitMap應(yīng)用
1、回避緩存穿透
緩存穿透是指當(dāng)前請求的數(shù)據(jù)在緩存中不存在，需要訪問數(shù)據(jù)庫獲取數(shù)據(jù)(數(shù)據(jù)庫中也不存在請求的數(shù)據(jù))。緩存穿透給數(shù)據(jù)庫帶來了壓力，惡意緩存穿透甚至能造成數(shù)據(jù)庫宕機(jī)。
使用BitMap動(dòng)態(tài)維護(hù)一個(gè)集合，當(dāng)訪問數(shù)據(jù)庫前，先查詢數(shù)據(jù)的主鍵是否存在集合中，以此作為是否訪問數(shù)據(jù)庫的依據(jù)。
BitMap新增數(shù)據(jù)或者移除數(shù)據(jù)屬于輕量級(jí)操作，檢查操作的準(zhǔn)確度依賴于動(dòng)態(tài)集合維護(hù)的閉環(huán)的完整性。比如向數(shù)據(jù)庫增加數(shù)據(jù)時(shí)需要向BitMap中添加數(shù)據(jù)，從數(shù)據(jù)庫中刪除數(shù)據(jù)需要從BitMap中移除數(shù)據(jù)。如果要求嚴(yán)格的檢查可靠性，則可以單獨(dú)維護(hù)一個(gè)分布式定時(shí)任務(wù)，定期更新BitMap數(shù)據(jù)。
2、與布隆過濾器的區(qū)別
布隆過濾器與BitMap有相似的應(yīng)用場景，但也有一定的區(qū)別。給定一個(gè)數(shù)，BitMap能準(zhǔn)確知道是否存在于已知集合中;布隆過濾器能準(zhǔn)確判斷是否不在集合中，卻不能肯定存在于集合中。
BitMap增加或者移除數(shù)據(jù)時(shí)間復(fù)雜度為O(1)，方便快捷。布隆過濾器新建容易，剔除數(shù)據(jù)操作比較繁瑣。
在一些需要精確判斷的場景，優(yōu)先選擇BitMap，比如判斷手機(jī)號(hào)是否已經(jīng)注冊。
四、小結(jié)
Redis BitMap不是一種新的數(shù)據(jù)結(jié)構(gòu)，是利用字符串類型做的一層封裝，看起來像一種新型數(shù)據(jù)結(jié)構(gòu)。BitMap不像一種技術(shù)，更像是算法，在時(shí)間復(fù)雜度和空間復(fù)雜度之間尋找平衡點(diǎn)。
BitMap其它應(yīng)用場景比如簽到打卡，統(tǒng)計(jì)在線人數(shù)等等。
名稱欄目：基于Redis分布式BitMap的應(yīng)用
瀏覽地址：http://m.fisionsoft.com.cn/article/djpchds.html
