MIX Fold3包裝盒泄露 新機本月登場
小米的全新折疊屏旗艦MIX Fold3將于本月發布，近日該機的真機包裝盒在網上泄露。從圖上來看，新的MIX Fold3包裝盒在外觀設計方面延續了之前的方案，變化不大，這也是目前小米旗艦
在互聯網中，我們經常遇到需要在大量數據中判斷目標數據是否存在的情況。例如，在網絡爬蟲中，我們需要判斷某個網址是否已經被訪問過。為了實現這一功能，通常需要使用一個容器來存儲已訪問過的網址。如果將這些數據直接存儲在磁盤中，每次判斷都要進行磁盤查詢，這將導致大量的IO操作，效率較低。因此，我們希望將這些數據保存在內存中。在數據量較小的情況下，可以使用Redis來存儲這些數據。但是，當數據量超過上千萬時，將會消耗幾GB甚至幾十GB的內存空間。然而，對于僅需要記錄數據是否存在的情況而言，這樣使用大量內存顯然是浪費的。為了解決這個問題，我們可以使用布隆過濾器(Bloom Filter)。布隆過濾器是一種占用空間少且時間效率高的工具。
布隆過濾器（Bloom Filter）是1970年由布隆提出的，它實質上是一個很長的二進制向量和一系列隨機映射函數 (Hash函數)。
作用：它是一個空間效率高的概率型數據結構，用來告訴你:一個元素一定不存在或者可能存在。
布隆過濾器實現原理就是一個超大位數的數組和多個不同Hash算法函數。假設位數組的長度為 m，哈希函數的個數為 k。如下圖，一個長度16位的數組，3個不同Hash算法函數，數組里面存儲的是 bit 位，只放 0 和 1，初始為 0。
不同Hash算法函數
guava是谷歌開源工具類，其中就有能直接實現布隆過濾器的方法，不需要重復造輪子。
方法名 | 功能 | 參數 | 返回值 |
put | 添加元素 | put(T object) | boolean |
mightContain | 檢查元素是否存在 | mightContain(T object) | boolean |
copy | 根據此實例創建一個新的BloomFilte | copy() | BloomFilter |
approximateElementCount | 已添加到Bloom過濾器的元素的數量 | approximateElementCount() | long |
expectedFpp | 返回元素存在的錯誤概率 | expectedFpp() | double |
isCompatible | 確定給定的Bloom篩選器是否與此Bloom篩選器兼容 | isCompatible(BloomFilterthat) | boolean |
putAll | 通過執行的逐位OR將此Bloom過濾器與另一個Bloom過濾器組合 | putAll(BloomFilterthat) | void |
引入依賴
<dependency> <groupId>com.google.guava</groupId> <artifactId>guava</artifactId> <version>23.0</version></dependency>測試代碼
private static void GuavaBloomFilter() { // 創建布隆過濾器對象 BloomFilter bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charset.defaultCharset()),EXPECTED_INSERTIONS,FALSE_PROBABILITY); // 向過濾器中添加元素 bloomFilter.put("element001"); bloomFilter.put("element003"); // 判斷元素是否存在 System.out.println(bloomFilter.mightContain("element001"));//true System.out.println(bloomFilter.mightContain("element002"));//false // 已添加到Bloom過濾器的元素的數量 System.out.println(bloomFilter.approximateElementCount());// 2 // 返回元素存在的錯誤概率 System.out.println(bloomFilter.expectedFpp());}Redisson方法
方法名 | 功能 | 參數 | 返回值 |
add | 添加元素 | add(T object) | boolean |
contains | 檢查元素是否存在 | contains(T object) | boolean |
count | 已添加到Bloom過濾器的元素的數量 | count() | long |
getExpectedInsertions | 返回的預期插入元素的個數 | getExpectedInsertions() | long |
getFalseProbability | 返回元素存在的錯誤概率 | getFalseProbability() | double |
getHashIterations | 返回每個元素使用的哈希迭代次數 | getHashIterations() | int |
getSize | 返回此實例所需Redis內存的位數 | getSize() | long |
tryInit | 初始化Bloom篩選器參數 | tryInit(long expectedInsertions, double falseProbability) | boolean |
delete | 刪除對象 | delete() | boolean |
引入依賴
<dependency> <groupId>org.redisson</groupId> <artifactId>redisson</artifactId> <version>3.22.1</version></dependency>測試代碼
private static void RedissonBloomFilter() { Config config = new Config(); config.useSingleServer().setAddress("redis://" + REDIS_IP + ":" + REDIS_PORT); config.useSingleServer().setPassword(REDIS_PASSWORD); // 獲取客戶端 RedissonClient redissonClient = Redisson.create(config); RBloomFilter<String> bloomFilter = redissonClient.getBloomFilter(BLOOM_FILTER_NAME); // 初始化布隆過濾器：預期插入量為100000000L,預期錯誤概率為1% bloomFilter.tryInit(EXPECTED_INSERTIONS, FALSE_PROBABILITY); // 插入數據 bloomFilter.add("element001"); bloomFilter.add("element003"); // 判斷下面元素是否在布隆過濾器中 System.out.println(bloomFilter.contains("element002"));//false System.out.println(bloomFilter.contains("element001"));//true // 已添加到Bloom過濾器的元素的數量 System.out.println(bloomFilter.count());//2 // 預期插入元素的個數 System.out.println(bloomFilter.getExpectedInsertions());//1000000 // 元素存在的錯誤概率 System.out.println(bloomFilter.getFalseProbability());//0.01 // 每個元素使用的哈希迭代次數 System.out.println(bloomFilter.getHashIterations()); // 實例所需Redis內存的位數 System.out.println(bloomFilter.getSize());}基礎命令
命令 | 功能 | 參數 |
BF.RESERVE | 創建一個大小為capacity，錯誤率為error_rate的空的Bloom | BF.RESERVE {key} {error_rate} {capacity} [EXPANSION {expansion}] [NONSCALING] |
BF.ADD | 向key指定的Bloom中添加一個元素itom | BF.ADD {key} {item} |
BF.MADD | 向key指定的Bloom中添加多個元案 | BF.MADD {key} {item ...} |
BF.INSERT | 向key指定的Bloom中添加多個元素，添加時可以指定大小和錯誤率，且可以控制在Bloom不存在的時候是否自動創建 | BF.INSERT {key} [CAPACITY {cap}] [ERROR {error}] [EXPANSION {expansion}] [NOCREATE] [NONSCALING] ITEMS {item ...} |
BF.EXISTS | 檢查一個元秦是否可能存在于key指定的Bloom中 | BF.EXISTS {key} {item} |
BF.MEXISTS | 同時檢查多個元素是否可能存在于key指定的Bloom中 | BF.MEXISTS {key} {item ...} |
BF.SCANDUMP | 對Bloom進行增量持久化操作 | BF.SCANDUMP {key} {iter} |
BF.LOADCHUNK | 加載SCANDUMP持久化的Bloom數據 | BF.LOADCHUNK {key} {iter} {data} |
BF.INFO | 查詢key指定的Bloom的信息 | BF.INFO {key} |
BF.DEBUG | 查看BloomFilter的內部詳細信息(如每層的元素個數，錯誤率等) | BF.DEBUG (key} |
引入依賴
<dependency> <groupId>redis.clients</groupId> <artifactId>jedis</artifactId> <version>4.2.0</version> </dependency>測試代碼
private static void RedisBloomFilter() { // 建立連接 BloomFilterCommands bloomFilterCommands = new JedisPooled(REDIS_IP, REDIS_PORT, "", REDIS_PASSWORD); // 構建布隆過濾器參數 BFReserveParams bfReserveParams = new BFReserveParams(); bfReserveParams.expansion(2); // 創建一個過濾器 String test = bloomFilterCommands.bfReserve(BLOOM_FILTER_NAME, FALSE_PROBABILITY, EXPECTED_INSERTIONS, bfReserveParams); // 向過濾器中添加元素 bloomFilterCommands.bfAdd(BLOOM_FILTER_NAME, "element001"); bloomFilterCommands.bfAdd(BLOOM_FILTER_NAME, "element003"); // 判斷元素是否存在 System.out.println(bloomFilterCommands.bfExists(BLOOM_FILTER_NAME, "element001"));//true System.out.println(bloomFilterCommands.bfExists(BLOOM_FILTER_NAME, "element002"));//false}自定義方法
方法名 | 功能 | 參數 | 返回值 |
add | 添加元素 | add(String key, String element, int expireSec) | boolean |
contains | 檢查元素是否存在 | contains(String key, String element) | boolean |
getExpectedInsertions | 返回的預期插入元素的個數 | getExpectedInsertions() | long |
getFalseProbability | 返回元素存在的錯誤概率 | getFalseProbability() | double |
getNumHashFunctions | 返回每個元素使用的哈希迭代次數 | getNumHashFunctions() | int |
getBitmapLength | 返回Bitmap長度 | getBitmapLength() | long |
BloomFilterUtils | 創建Bloom對象 | BloomFilterUtils(long expectedInsertions, double falseProbability) | BloomFilterUtils |
測試代碼
public class BloomFilterUtils { private static final String BF_KEY_PREFIX = "bf_"; private long numApproxElements; private double falseProbability; // hash個數 private int numHashFunctions; // 數組長度 private int bitmapLength; private JedisResourcePool jedisResourcePool; /** * 構造布隆過濾器。注意：在同一業務場景下，三個參數務必相同 * * @param numApproxElements 預估元素數量 * @param fpp 可接受的最大誤差 * @param jedisResourcePool Codis專用的Jedis連接池 */ public BloomFilterUtils(Long numApproxElements, double fpp, JedisResourcePool jedisResourcePool) { this.numApproxElements = numApproxElements; this.falseProbability = fpp; this.jedisResourcePool = jedisResourcePool; // 數組長度 m = (n * lnp)/ln2^2 bitmapLength = (int) (-numApproxElements * Math.log(fpp) / (Math.log(2) * Math.log(2))); // hash個數 k = (n / m ) * ln2 numHashFunctions = Math.max(1, (int) Math.round((double) bitmapLength / numApproxElements * Math.log(2))); } /** * 取得預估元素數量 */ public long getExpectedInsertions() { return numApproxElements; } /** * 返回元素存在的錯誤概率 */ public double getFalseProbability() { return falseProbability; } /** * 取得自動計算的最優哈希函數個數 */ public int getNumHashFunctions() { return numHashFunctions; } /** * 取得自動計算的最優Bitmap長度 */ public int getBitmapLength() { return bitmapLength; } /** * 計算一個元素值哈希后映射到Bitmap的哪些bit上 * * @param element 元素值 * @return bit下標的數組 */ private long[] getBitIndices(String element) { long[] indices = new long[numHashFunctions]; // 元素 使用MurMurHash3 128位Hash算法轉換值 byte[] bytes = Hashing.murmur3_128() .hashObject(element, Funnels.stringFunnel(Charset.forName("UTF-8"))) .asBytes(); // 低8位轉Long值 long hash1 = Longs.fromBytes( bytes[7], bytes[6], bytes[5], bytes[4], bytes[3], bytes[2], bytes[1], bytes[0] ); // 高8位轉Long值 long hash2 = Longs.fromBytes( bytes[15], bytes[14], bytes[13], bytes[12], bytes[11], bytes[10], bytes[9], bytes[8] ); long combinedHash = hash1; // 雙重哈希進行散列 for (int i = 0; i < numHashFunctions; i++) { indices[i] = (combinedHash & Long.MAX_VALUE) % bitmapLength; combinedHash += hash2; } return indices; } /** * 插入元素 * * @param key 原始Redis鍵，會自動加上'bf_'前綴 * @param element 元素值，字符串類型 * @param expireSec 過期時間（秒） */ public void add(String key, String element, int expireSec) { if (key == null || element == null) { throw new RuntimeException("鍵值均不能為空"); } String actualKey = BF_KEY_PREFIX.concat(key); try (Jedis jedis = jedisResourcePool.getResource()) { try (Pipeline pipeline = jedis.pipelined()) { // 遍歷元素所有hash結果的bit位置 for (long index : getBitIndices(element)) { pipeline.setbit(actualKey, index, true); } pipeline.syncAndReturnAll(); } jedis.expire(actualKey, expireSec); } } /** * 檢查元素在集合中是否（可能）存在 * * @param key 原始Redis鍵，會自動加上'bf_'前綴 * @param element 元素值，字符串類型 */ public boolean contains(String key, String element) { if (key == null || element == null) { throw new RuntimeException("鍵值均不能為空"); } String actualKey = BF_KEY_PREFIX.concat(key); boolean result = false; try (Jedis jedis = jedisResourcePool.getResource()) { // 遍歷元素所有hash結果的bit位置 try (Pipeline pipeline = jedis.pipelined()) { for (long index : getBitIndices(element)) { pipeline.getbit(actualKey, index); } result = !pipeline.syncAndReturnAll().contains(false); } } return result; } public static void main(String[] args) { String path = Path.getCurrentPath() + "/config/zzjodis.properties"; ConfigReadUtil configReadUtil = new ConfigReadUtil(path); try { JedisResourcePool jedisResourcePool = RoundRobinJedisPool. create() .curatorClient(configReadUtil.getString("jodisZkStr"), 5000) .zkProxyDir(configReadUtil.getString("zkProxyDir")) .team(configReadUtil.getString("team")) .connectionTimeoutMs(configReadUtil.getInt("connectionTimeoutMs")) .soTimeoutMs(configReadUtil.getInt("soTimeoutMs")) .appKey(configReadUtil.getString("appKey")) .password("".equals(configReadUtil.getString("password")) ? null : configReadUtil.getString("password")) .build(); BloomFilterUtils bloomFilterUtils = new BloomFilterUtils(10000, 0.01, jedisResourcePool); bloomFilterUtils.add("filter01", "element001", 30 * 60); System.out.println(bloomFilterUtils.contains("filter01", "element001")); // true System.out.println(bloomFilterUtils.contains("filter01", "element002")); // false } catch (Exception e) { e.printStackTrace(); } }}在C1看視頻得曝光活動項目中，為了在個人中心頁為擁有在架商品的用戶展示活動入口，需要高效地判斷用戶是否有在架商品。目前存在上億存量用戶和上百萬的在架商品用戶。每次用戶進入個人中心頁時，需要查詢用戶是否有在架商品，以確定是否展示活動入口。然而，直接查詢商品服務會導致大量的重復查詢和增加服務耗時?？梢允褂貌悸∵^濾器來優化此過程，它只需要幾十MB內存，相比于使用Redis存儲每日在架商品用戶需要幾GB內存，更加高效節省內存消耗。
實現方式 | 儲存位置 | 適用場景 | 備注 |
Guava | 機器 | 單機 | 只需要機器內存不需要其他資源 |
Redisson | redis | 分布式 | 連接Redis即可使用 |
Redis插件 | redis | 分布式 | 需要對redis集群進行設置支持布隆過濾器插件 |
Redis的bitMap | redis | 分布式 | 需要自己實現添加和查詢 |
對于分布式服務環境，Guava方式不適合使用，而Redis插件需要復雜的配置和高成本支持。相比之下，Redisson連接Redis并進行插入和查詢的方式更適合當前場景，因此最終選擇了Redisson方式。
1、內存占用情況
- 上線初期，我們將符合條件的用戶存入Codis緩存中。這使得內存從1.98GB增長到9.52GB，此次數據量占用了7.54GB的內存。
- 隨后，為進一步優化，我們成功將用戶量縮小了25倍。這使得內存占用降至308.8MB。
- 最終，我們切換到了Redisson方式使用布隆過濾器。這次Redis內存從2.7172GB增長到2.7566GB，而數據量僅占用39.4MB的內存。
使用Codis內存占用情況
插入數據前：
插入數據后：
使用布隆過濾器內存占用情況
插入數據前：
插入數據后：
2、通過使用布隆過濾器減少對商品服務的查詢，從而提升服務性能。之前需要查詢商品服務來判斷用戶商品狀態，但使用布隆過濾器后，減少了這部分服務間的調用耗時，整體流程的耗時減少了大約5ms。
作者介紹
李帥齊，轉轉商業后端開發工程師，目前負責商業C端相關業務系統開發(廣告檢索、計費以及特征工程系統等)。
本文鏈接：http://m.www897cc.com/showinfo-26-81233-0.html布隆過濾器：提高效率與降低成本的秘密
聲明：本網頁內容旨在傳播知識，若有侵權等問題請及時與本網聯系，我們將在第一時間刪除處理。郵件：2376512515@qq.com
Copyright ? 2016-2023 天津谷騏科技有限公司 版權所有 sitemap.xml
違法及侵權請聯系：2376512515@qq.com 津ICP備18001702號
津公網安備 12010102000574號