Guava -- Bloom Filter原理

  • 2020 年 2 月 10 日
  • 筆記

去重在軟體開發中經常需要用到，在Java當中一般使用Set集合，面對大量數據則可以利用取MD5簽名等值後再進行去重，然而Set集合的實現原理決定了如果有大量的key需要判斷，必然會需要大量的記憶體來支撐，且隨著數據量增大效率也變得不那麼盡人意。另外業務中存在著很多對精確性不需要那麼高的場景，此時使用Set集合則是一種資源浪費，因此就可以利用布隆過濾器等演算法手段進行去重。

業務場景

筆者實習面試的時候，面試官問了個關於怎麼判斷爬蟲URL是否已經爬過的問題，筆者先回答了使用Set集合，然後升級為記憶體很小，數據量很大怎麼辦？筆者想了想往資料庫插，取簽名值後，可以分庫分表，利用資料庫唯一鍵來約束。面試官沒再追問。。。後來見識到了布隆過濾器，才想起來面試官真正的用意。

布隆過濾器的原理

布隆過濾器原理很簡單，用一個很大的bit位數組與多個無偏hash函數(即計算出來的hash值呈均勻分布)，當存入一個元素時，使用每一個hash函數進行hash，再與bit數組取模，得出的位置置為1。判斷一個元素是否存在時，同樣也是利用這樣的方法判斷對應的數組位是不是否為1。

從原理上可以得出布隆過濾器的特性：

  1. 存在不一定真的存在：存在則可能對應的數組位與其他key產生了碰撞。
  2. 不存在則一定不存在：不存在則一定不存在，那麼這個特性則可以很好的實現去重。

那麼問題又來了，布隆過濾器既然有一定誤判率，怎麼使這個誤判率降低？ 具體有相關公式，不過一般使用直接計算工具，比如bloom-calculator，100w的數據判斷，萬分之一的誤判率才需要2M記憶體，優勢巨大。

常見實現方案

guava

在Guava中提供了com.google.common.hash.BloomFilter類，如下所示，可以很方便的實現布隆過濾器。其實現原理中有很多值得學習的點。

@Test     public void test() {         // 100w bit長度 ,0.01%誤判率         // bf對象則會生成 299534 個long數組,使用13次hash計算.         BloomFilter<String> bf = BloomFilter             .create(Funnels.stringFunnel(Charset.defaultCharset()), 100 * 10000, 0.0001d);           System.out.println(bf.test("quding")); // false         bf.put("quding"); // bitCount=13         System.out.println(bf.test("quding")); // true         bf.put("quding1"); // bitCount=26       }

如何表示超長的bit數組？

在Java中提供的基本類型最小的位Byte，佔8bits，最大的為Long，佔64bits，因此常見方案是使用Long數組作為bits數組使用，舉個例子 128bits可以用long[2]標識，146bits可以用long[3]表示，在Guava中對應的實現為com.google.common.hash.BloomFilterStrategies.LockFreeBitArray。 清單1: 

static final class LockFreeBitArray {      private static final int LONG_ADDRESSABLE_BITS = 6;      // long數組,表示超長bit位,使用Atomic提供原子操作能力,保證執行緒安全      final AtomicLongArray data;      // 當前數組中為1的bit位數量,其實現可以看錯JDK8中的LongAdder      private final LongAddable bitCount;        LockFreeBitArray(long bits) {          // 初始化時傳入bit位,然後按照64位進行拆分計算,比如傳入146bits,則會拆分位long[3]數組        this(new long[Ints.checkedCast(LongMath.divide(bits, 64, RoundingMode.CEILING))]);      }  }

那麼可以想像更新bits位的操作需要先定位到long數組的下標，然後使用將對應bits位置為1，具體做法如清單2所示。 清單2: bit位更新操作 

boolean set(long bitIndex) {      if (get(bitIndex)) {        return false;      }      // 定位到long數組對應的下標      int longIndex = (int) (bitIndex >>> LONG_ADDRESSABLE_BITS);      // 左移,將對應位置的bit位置為1,其他全是0      long mask = 1L << bitIndex; // only cares about low 6 bits of bitIndex        long oldValue;      long newValue;      do {        oldValue = data.get(longIndex);        // 或操作將對應bit位變成1        newValue = oldValue | mask;        if (oldValue == newValue) {          return false;        }        // CAS保證原子性      } while (!data.compareAndSet(longIndex, oldValue, newValue));        // We turned the bit on, so increment bitCount.      bitCount.increment();      return true;    }

擴展一下，這種拆分思想的應用很多，DB上有分庫分表，應用上有各種鎖拆分,比如ConcurrentHashMap，LongAdder，那麼業務上可以怎麼利用呢?想到一種在業務中一個賬戶的金額如果頻繁變動，那麼就需要對這個賬戶不停的做更新操作，到DB那一層則是高並發,那麼此時將一個賬戶拆分為多個呢？比如收入是一個賬戶，支出是另一個賬戶，或者按照幣種維護，按照業務維度等方法，那麼就將一個賬戶的鎖拆分為賬戶的鎖，有效的降低了高並髮帶來的鎖競爭問題。當然一致性上還需要應用層使用事務等機制來解決。

如何多次hash計算？

如上圖計算，100w元素，0.0001誤判率下需要13次hash計算，hash在快次數一多也必然會成為性能瓶頸，在Guava中並沒有引入多個Hash函數，而是計算出一個hash值後，其他的使用位移，乘除等方法快速計算出來，其實本身是均勻分布的隨機值，也沒必要使用多個hash函數。 清單3: hash計算 

MURMUR128_MITZ_32() {      @Override      public <T> boolean put(          T object, Funnel<? super T> funnel, int numHashFunctions, LockFreeBitArray bits) {        long bitSize = bits.bitSize();        // 計算出一個hash值        long hash64 = Hashing.murmur3_128().hashObject(object, funnel).asLong();        // 取低32位        int hash1 = (int) hash64;        // 取高32位        int hash2 = (int) (hash64 >>> 32);          boolean bitsChanged = false;        // 根據hash次數分別計算出hash值,然後設置到bits數組中        for (int i = 1; i <= numHashFunctions; i++) {          int combinedHash = hash1 + (i * hash2);          // Flip all the bits if it's negative (guaranteed positive number)          if (combinedHash < 0) {            combinedHash = ~combinedHash;          }          // 填充bits位          bitsChanged |= bits.set(combinedHash % bitSize);        }        return bitsChanged;      }  }

另外com.google.common.hash.BloomFilterStrategies也是枚舉策略模式的典型應用場景，值得學習，關於策略模式可以參考 設計模式–策略模式的思考

Redis

Guava只能本地使用，面對分散式場景時則可以選擇一些快取類組件實現，在Redis4.0版本之後，提供了module支援了布隆過濾器 RedisBloom，主要命令如下所示，具體實現原理不是很了解了，在此也不多討論。 清單1: redis bloom filter命令 

BF.RESERVE {key} {error_rate} {size}  初始化一個布隆過濾器  BF.ADD {key} {item}  添加單個元素  BF.EXISTS {key} {item} 是否存在  bf.madd {key} {item} [item...]  添加多個元素  BF.MEXISTS {key} {item} [item...]  判斷多個元素是否存在

參考

  1. Redis深度歷險

Tags:

VirMach 便宜 VPS