內存崩潰了?其實你只需要換一種方式
- 2019 年 12 月 2 日
- 筆記
使用 JDK 自帶的 Set 集合來進行 URL 去重,看上去效果不錯,但是這種做法有一個致命了缺陷,就是隨着採集的 URL 增多,你需要的內存越來越大,最終會導致你的內存崩潰。那我們在不使用數據庫的情況下有沒有解決辦法呢?布隆過濾器!它就可以完美解決這個問題,布隆過濾器有什麼特殊的地方呢?接下來就一起來學習一下布隆過濾器。
什麼是布隆過濾器
布隆過濾器是一種數據結構,比較巧妙的概率型數據結構,它是在 1970 年由一個名叫布隆提出的,它實際上是由一個很長的二進制向量和一系列隨機映射函數組成,這點跟哈希表有些相同,但是相對哈希表來說布隆過濾器它更高效、佔用空間更少,布隆過濾器有一個缺點那就是有一定的誤識別率和刪除困難。布隆過濾器只能告訴你某個元素一定不存在或者可能存在在集合中, 所以布隆過濾器經常用來處理可以忍受判斷失誤的業務,比如爬蟲 URL 去重。
布隆過濾器原理
在說布隆過濾器原理之前,我們先來複習一下哈希表,利用 Set 來進行 URL 去重,我們來看看 Set 的存儲模型
URL 經過一個哈希函數後,將 URL 存入了數組裡,這樣查詢時也是非常高效的,但是由於數組裡存入的是 URL,隨着 URL 的增多,需要的數組越來越大,意味着你需要更多的內存,比如我們採集了幾億的 URL,那麼可能就需要上百G 的內存,這是條件不允許的,因為內存特別的昂貴,所以這個在 url 去重中是不可取的,占內存更小的布隆過濾器就是一種不錯的選擇。
布隆過濾器實質上由長度為 m 的位向量或位列表(僅包含 0 或 1 位值的列表)組成,最初所有值均設置為 0,如下所示。
因為底層是 bit 數組,所以意味着數組只有 0、1 兩個值,跟哈希表一樣,我們將 URL 通過 K 個函數映射 bit 數組裡,並且將指向的 Bit 數組對應的值改成 1 。我們以存 /nba/2492297.html
為例,如下圖所示:
/nba/2492297.html
經過三個哈希函數分別映射到了 1、4、9 的位置,這三個 bit 數組的值就變成了 1,我們再存入一個 /nba/2492298.html
,此時 bit 數組就變成下面這樣:
/nba/2492298.html
被映射到了 0、4、11 的位置,所以此時 bit 數組上有 5 個位置的值為 1,本應該是有 6 個值為 1 的,但是因為在 4 這個位置重複了,所以會覆蓋。
布隆過濾器是如何判斷某個值一定不存在或者可能存在呢?通過判斷哈希函數映射到對應數組的值,如果都為 1,說明可能存在,如果有一個不為 1,說明一定不存在。對於一定不存在好理解,但是都為 1 時,為什麼說可能存在呢?這跟哈希表一樣,哈希函數會產生哈希衝突,也就是說兩個不同的值經過哈希函數都會得到同一個數組下標,布隆過濾器也是一樣的。我們以判斷 /nba/2492299.html
是否已經採集過為例,經過哈希函數映射的 bit 數組上的位置入下圖所示:
/nba/2492299.html
被哈希函數映射到了 4、9、11 的位置,而這幾個位置的值都為 1 ,所以布隆過濾器就認為 /nba/2492299.html
被採集過了,實際上是沒有採集過的,這就說明了布隆過濾器存在誤判,這也是我們業務允許的。布隆過濾器的誤判率跟 bit 數組的大小和哈希函數的個數有關係,如果 bit 數組過小,哈希函數過多,那麼 bit 數組的值很快都會變成 1,這樣誤判率就會越來越高,bit 數組過大,就會浪費更多的內存,所以就要平衡好 bit 數組的大小和哈希函數的個數,關於如何平衡這兩個的關係,不是我們這篇文章的重點。
布隆過濾器的原理我們已經了解了,為了加深對布隆過濾器的理解,我們用 Java 來實現一個簡易辦的布隆過濾器,代碼如下:
public class SimpleBloomFilterTest { // bit 數組的大小 private static final int DEFAULT_SIZE = 1000; // 用來生產三個不同的哈希函數的 private static final int[] seeds = new int[]{7, 31, 61,}; // bit 數組 private BitSet bits = new BitSet(DEFAULT_SIZE); // 存放哈希函數的數組 private SimpleHash[] func = new SimpleHash[seeds.length]; public static void main(String[] args) { SimpleBloomFilterTest filter = new SimpleBloomFilterTest(); filter.add("https://voice.hupu.com/nba/2492440.html"); filter.add("https://voice.hupu.com/nba/2492437.html"); filter.add("https://voice.hupu.com/nba/2492439.html"); System.out.println(filter.contains("https://voice.hupu.com/nba/2492440.html")); System.out.println(filter.contains("https://voice.hupu.com/nba/249244.html")); } public SimpleBloomFilterTest() { for (int i = 0; i < seeds.length; i++) { func[i] = new SimpleHash(DEFAULT_SIZE, seeds[i]); } } /** * 向布隆過濾器添加元素 * @param value */ public void add(String value) { for (SimpleHash f : func) { bits.set(f.hash(value), true); } } /** * 判斷某元素是否存在布隆過濾器 * @param value * @return */ public boolean contains(String value) { if (value == null) { return false; } boolean ret = true; for (SimpleHash f : func) { ret = ret && bits.get(f.hash(value)); } return ret; } /** * 哈希函數 */ public static class SimpleHash { private int cap; private int seed; public SimpleHash(int cap, int seed) { this.cap = cap; this.seed = seed; } public int hash(String value) { int result = 0; int len = value.length(); for (int i = 0; i < len; i++) { result = seed * result + value.charAt(i); } return (cap - 1) & result; } } }
把上面這段代碼理解好對我們理解布隆過濾器非常有幫助,實際上在工作中並不需要我們自己實現布隆過濾器,谷歌已經幫我們實現了布隆過濾器,在 Guava 包中提供了 BloomFilter,這個布隆過濾器實現的非常棒,下面就看看谷歌辦的布隆過濾器。
布隆過濾器 Guava 版
要使用 Guava 包下提供的 BloomFilter ,就需要引入 Guava 包,我們在 pom.xml 中引入下面依賴:
<dependency> <groupId>com.google.guava</groupId> <artifactId>guava</artifactId> <version>28.1-jre</version> </dependency>
Guava 中的布隆過濾器實現的非常複雜,關於細節我們就不去探究了,我們就來看看 Guava 中布隆過濾器的構造函數吧,Guava 中並沒有提供構造函數,而且提供了 create 方法來構造布隆過濾器:
public static <T> BloomFilter<T> create( Funnel<? super T> funnel, int expectedInsertions, double fpp) { return create(funnel, (long) expectedInsertions, fpp); }
funnel:你要過濾數據的類型
expectedInsertions:你要存放的數據量
fpp:誤判率
你只需要傳入這三個參數你就可以使用 Guava 包中的布隆過濾器了,下面這我寫的一段 Guava 布隆過濾器測試程序,可以改動 fpp 多運行幾次,體驗 Guava 的布隆過濾器。
public class GuavaBloomFilterTest { // bit 數組大小 private static int size = 10000; // 布隆過濾器 private static BloomFilter<String> bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charset.defaultCharset()), size, 0.03); public static void main(String[] args) { // 先向布隆過濾器中添加 10000 個url for (int i = 0; i < size; i++) { String url = "https://voice.hupu.com/nba/" + i; bloomFilter.put(url); } // 前10000個url不會出現誤判 for (int i = 0; i < size; i++) { String url = "https://voice.hupu.com/nba/" + i; if (!bloomFilter.mightContain(url)) { System.out.println("該 url 被採集過了"); } } List<String> list = new ArrayList<String>(1000); // 再向布隆過濾器中添加 2000 個 url ,在這2000 個中就會出現誤判了 // 誤判的個數為 2000 * fpp for (int i = size; i < size + 2000; i++) { String url = "https://voice.hupu.com/nba/" + i; if (bloomFilter.mightContain(url)) { list.add(url); } } System.out.println("誤判數量:" + list.size()); } }
布隆過濾器的應用
緩存擊穿
緩存擊穿是查詢數據庫中不存在的數據,如果有用戶惡意模擬請求很多緩存中不存在的數據,由於緩存中都沒有,導致這些請求短時間內直接落在了DB上,對DB產生壓力,導致數據庫異常。
最常見的解決辦法就是採用布隆過濾器,將所有可能存在的數據哈希到一個足夠大的bitmap中,一個一定不存在的數據會被這個bitmap攔截掉,從而避免了對底層存儲系統的查詢壓力。下面是一段偽代碼:
public String getByKey(String key) { // 通過key獲取value String value = redis.get(key); if (StringUtil.isEmpty(value)) { if (bloomFilter.mightContain(key)) { value = xxxService.get(key); redis.set(key, value); return value; } else { return null; } } return value; }
爬蟲 URL 去重
爬蟲是對 url 的去重,防止 url 重複採集,這也是我們這篇文章重點講解的內容
垃圾郵件識別
從數十億個垃圾郵件列表中判斷某郵箱是否垃圾郵箱,將垃圾郵箱添加到布隆過濾器中,然後判斷某個郵件是否是存在在布隆過濾器中,存在說明就是垃圾郵箱。