一、序言
在實際開發中常常遇到如下需求：判斷當前元素是否存在于已知的集合中，將已知集合中的元素維護一個HashSet，使用時只需耗時O(1)的時間復雜度便可判斷出結果，Java內部或者Redis均提供相應的數據結構。使用此種方式除了占用內存空間外，幾乎沒有其它缺點。
當數據量達到億級別時，內存空間的占用顯著表現出來，BitMap便是解決此類問題的一種途徑。
二、BitMap結構
1、內存消耗分析
Redis BitMap能夠存儲的數據范圍為[0,2^32-1]，超過Integer.MAX_VALUE上界值。
為了簡化討論，假設討論的集合元素的范圍為[0,Integer.MAX_VALUE]，可以是其中的任何一個數。
使用HashSet數據結構占用內存空間僅與集合中的元素數量（N）相關。當集合中元素數量為N時，所需的內存空間大概為N*4/1024/1024MB，1億條數據約占內存空間381MB。
基于Redis的BitMap所占用的空間大小不與集合中元素數量相關，與集合中元素的最大值直接相關，因此BitMap所占用的內存空間范圍為[N / 8 / 1024 / 1024,Integer.MAX_VALUE / 8 / 1024 / 1024]。
|
1
2
3
4
5
6
|
// 測試1億、5億、10億、Integer.MAX_VALUEList<Integer> items = Arrays.asList(100000000, 500000000, 1000000000, Integer.MAX_VALUE);for (Integer item : items) { int size = item / 8 / 1024 / 1024; System.out.printf("如果集合中最大值為%-10s,則所占用的內存空間為%3sMB%n",item, size);} |
這里給出了一組測試參考數據
如果集合中最大值為100000000 ,則所占用的內存空間為 11MB
如果集合中最大值為500000000 ,則所占用的內存空間為 59MB
如果集合中最大值為1000000000,則所占用的內存空間為119MB
如果集合中最大值為2147483647,則所占用的內存空間為255MB
當集合中數據增長到10億條時，使用BItMap最大占用內存約為255MB，而使用HashSet增長到3.8GB。
2、命令行操作BitMap
使用Redis命令行可直接操作BitMap，將offset位置的值標注為1，則表示當前數據存在。默認情況下未標注的位置值為0。
|
1
2
3
4
|
# 默認位不賦值為0，當數據存在于集合中，將對應位賦值為1SETBIT key offset value# 查看對應位數據是否存在（1表示存在，0表示不存在）GETBIT key offset |
3、客戶端操作BitMap
這里提供一個SpringBoot生態的RedisUtils工具類，內部封裝操作Redis BitMap的工具方法。
|
1
2
3
4
|
// 將當前位置標記為trueRedisUtils.setBit(BIT_MAP_KEY, orderId, true);// 獲取指定位置的值（對應數值是否存在）RedisUtils.getBit(BIT_MAP_KEY, orderId) |
上述工具類的依賴如下，如果找不到Jar包，請直接使用Maven原始倉庫源，阿里云尚未同步完成。
|
1
2
3
4
5
|
<dependency> <groupId>xin.altitude.cms</groupId> <artifactId>ucode-cms-common</artifactId> <version>1.4.3</version></dependency> |
4、時間與空間復雜度
BitMap的存儲與取值時間復雜度為O(1)，根據數值可直接映射下標。
BitMap占用內存空間復雜度為O(n)，與集合中元素的最大值正相關，不是集合中元素的數量。
三、BitMap應用
1、回避緩存穿透
緩存穿透是指當前請求的數據在緩存中不存在，需要訪問數據庫獲取數據（數據庫中也不存在請求的數據）。緩存穿透給數據庫帶來了壓力，惡意緩存穿透甚至能造成數據庫宕機。
使用BitMap動態維護一個集合，當訪問數據庫前，先查詢數據的主鍵是否存在集合中，以此作為是否訪問數據庫的依據。
BitMap新增數據或者移除數據屬于輕量級操作，檢查操作的準確度依賴于動態集合維護的閉環的完整性。比如向數據庫增加數據時需要向BitMap中添加數據，從數據庫中刪除數據需要從BitMap中移除數據。如果要求嚴格的檢查可靠性，則可以單獨維護一個分布式定時任務，定期更新BitMap數據。
2、與布隆過濾器的區別
布隆過濾器與BitMap有相似的應用場景，但也有一定的區別。給定一個數，BitMap能準確知道是否存在于已知集合中；布隆過濾器能準確判斷是否不在集合中，卻不能肯定存在于集合中。
BitMap增加或者移除數據時間復雜度為O(1)，方便快捷。布隆過濾器新建容易，剔除數據操作比較繁瑣。
在一些需要精確判斷的場景，優先選擇BitMap，比如判斷手機號是否已經注冊。
四、小結
Redis BitMap不是一種新的數據結構，是利用字符串類型做的一層封裝，看起來像一種新型數據結構。BitMap不像一種技術，更像是算法，在時間復雜度和空間復雜度之間尋找平衡點。
BitMap其它應用場景比如簽到打卡，統計在線人數等等。
到此這篇關于基于Redis分布式BitMap的應用的文章就介紹到這了,更多相關Redis分布式BitMap內容請搜索服務器之家以前的文章或繼續瀏覽下面的相關文章希望大家以后多多支持服務器之家！
原文鏈接：https://www.cnblogs.com/javazhishitupu/archive/2022/03/04/15962910.html
