什么是布隆過濾器？
它實際上是一個很長的二進制向量和一系列隨機映射函式，把一個目標元素通過多個hash函式的計算，將多個隨機計算出的結果映射到不同的二進制向量的位中，以此來間接標記一個元素是否存在于一個集合中，
布隆過濾器可以做什么？
布隆過濾器可以用于檢索一個元素是否在一個集合中，它的優點是空間效率和查詢時間都比一般的演算法要好的多，缺點是有一定的誤識別率和洗掉困難，
布隆過濾器特點
如果布隆過濾器顯示一個元素不存在于集合中，那么這個元素100%不存在與集合當中
如果布隆過濾器顯示一個元素存在于集合中，那么很有可能存在，可能性取決于對布隆過濾器的定義（BF.RESERVE {key} {error_rate} {capacity}）
布隆過濾器的原理圖，這個就很容易理解了，
Redis中的布隆過濾器實作（rebloom模塊擴展）
下載并編譯
git clone git://github.com/RedisLabsModules/rebloom
cd rebloom
make
組態檔中加載rebloom
loadmodule /your_path/rebloom.so
重啟Redis服務器即可
./bin/redis-cli -h 127.0.0.1 -p 6379 -a ****** shutdown
./bin/redis-server redis.conf
rebloom在Redis中的使用
bloom filter定義
BF.RESERVE {key} {error_rate} {capacity}
使用給定的期望錯誤率和初始容量創建空的Bloom過濾器（如果不存在的話），如果打算向Bloom過濾器中添加許多項，則此命令非常有用，否則只能使用BF.ADD 添加項，
初始容量和錯誤率將決定過濾器的性能和記憶體使用情況，一般來說，錯誤率越小(即對誤差的容忍度越低)，每個過濾器條目的空間消耗就越大，
bloom filter基本操作
1，BF.ADD {key} {item}
單條添加元素
向Bloom filter添加一個元素，如果該key不存在，則創建該key(過濾器)，
如果項是新插入的，則為“1”;如果項以前可能存在，則為“0”，
2，BF.MADD {key} {item} [item...]
批量添加元素
布爾數(整數)的陣列，回傳值為0或1的范圍的資料，這取決于是否將相應的輸入元素新添加到過濾器中，或者是否已經存在，
3，BF.EXISTS {key} {item}
判斷單個元素是否存在
如果存在，回傳1，否則回傳0
4，BF.MEXISTS {key} {item} [item...]
判斷多個元素是否存在
布爾數(整數)的陣列，回傳值為0或1的范圍的資料，這取決于是否將相應的元是否已經存在于key中，
127.0.0.1:8001> bf.reserve bloom_filter_test 0.0000001 1000000OK127.0.0.1:8001> bf.reserve bloom_filter_test 0.0000001 1000000(error) ERR item exists127.0.0.1:8001>127.0.0.1:8001>127.0.0.1:8001> bf.add bloom_filter_test key1(integer) 1127.0.0.1:8001> bf.add bloom_filter_test key2(integer) 1127.0.0.1:8001>127.0.0.1:8001> bf.madd bloom_filter_test key2 key3 key4 key51) (integer) 02) (integer) 13) (integer) 14) (integer) 1127.0.0.1:8001> bf.exists bloom_filter_test key2(integer) 1127.0.0.1:8001> bf.exists bloom_filter_test key3(integer) 1127.0.0.1:8001> bf.mexists bloom_filter_test key3 key4 key51) (integer) 12) (integer) 13) (integer) 1127.0.0.1:8001>
5，bf.insert
bf.insert{key} [CAPACITY {cap}] [ERROR {ERROR}] [NOCREATE] ITEMS {item…}
該命令將向bloom過濾器添加一個或多個項，如果它還不存在，則默認情況下創建它，有幾個引數可用于修改此行為，
key:過濾器的名稱
capacity:如果指定了，應該在后面加上要創建的過濾器的所需容量，如果過濾器已經存在，則忽略此引數，如果自動創建了過濾器，并且沒有此引數，則使用默認容量(在模塊級指定)，見bf.reserve，
error:如果指定了，后面應該跟隨著新創建的過濾器的錯誤率(如果它還不存在)，如果自動創建過濾器而沒有指定錯誤，則使用默認的模塊級錯誤率，見bf.reserve，
nocreate:如果指定，表示如果過濾器不存在，就不應該創建它，如果過濾器還不存在，則回傳一個錯誤，而不是自動創建它，如果需要在創建過濾器和添加過濾器之間進行嚴格的分離，可以使用這種方法，將NOCREATE與容量或錯誤一起指定是一個錯誤，
item:指示要添加到篩選器的項的開頭，必須指定此引數，
127.0.0.1:8001> bf.insert bloom_filter_test2 items key1 key2 key31) (integer) 12) (integer) 13) (integer) 1127.0.0.1:8001> bf.insert bloom_filter_test2 items key1 key2 key31) (integer) 02) (integer) 03) (integer) 0127.0.0.1:8001> bf.insert bloom_filter_test2 capacity 10000 error 0.00001 nocreate items key1 key2 key31) (integer) 02) (integer) 03) (integer) 0127.0.0.1:8001>127.0.0.1:8001> bf.insert bloom_filter_test2 capacity 10000 error 0.00001 nocreate items key4 key5 key61) (integer) 12) (integer) 13) (integer) 1127.0.0.1:8001>
bf持久化操作
BF.SCANDUMP {key} {iter}對bloom過濾器進行增量保存，這對于不能適應常規save和restore模型的大型bloom filter非常有用，
第一次呼叫這個命令時，iter的值應該是0，這個命令將回傳連續的(iter, data)對，直到(0,NULL)，以表示完成
python偽代碼演示:
chunks = []iter = 0while True: iter, data = https://www.cnblogs.com/wy123/p/BF.SCANDUMP(key, iter) if iter == 0: break else: chunks.append([iter, data])# Load it backfor chunk in chunks: iter, data = chunk BF.LOADCHUNK(key, iter, data)bf.scandump示例
127.0.0.1:8001> bf.scandump bloom_filter_test2 01) (integer) 12) "\x06\x00\x00\x00\x00\x00\x00\x00\x01\x00\x00\x00\x04\x00\x00\x00\x80\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x06\x00\x00\x00\x00\x00\x00\x00{\x14\xaeG\xe1z\x84?\x88\x16\x8a\xc5\x8c+#@\a\x00\x00\x00j\x00\x00\x00\n"127.0.0.1:8001> bf.scandump bloom_filter_test2 11) (integer) 1292) "\x00\x00\x00\x00\xa2\x00\x00\x00\x00\x00\x00B\x01\x00\x00\x00\x00\x00\x00\x00\x80\x00\x00 \x00\x00\b\x00\x00\x00\x00\b\x00\x00@\x00\x01\x04\x18\x02\x00\x00\x00\x82\x00\x00\x80@\x00\b\x00\x00\x00\x00 \x00\x00@\x00\x00\x00\x00\x18\b\x00\b\x00\b\x00\x80B\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x80\x00\x00\x00\x00 (\x00\x00\x00\x00@\x00\x00\x00\x00@\x00\x00\x04\x00\x00\x00\x00\x00\x00\x00\x80\x00\x00\x00\x80\x00\x00@\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\b"127.0.0.1:8001> bf.scandump bloom_filter_test2 1291) (integer) 02) ""127.0.0.1:8001>
blool filter資料型別的屬性
bf.debug
這里可以看到，隨著bloom filter元素的增加，其空間容量也在不斷地增加
127.0.0.1:8001> bf.debug bloom_filter_test1) "size:5"2) "bytes:4194304 bits:33554432 hashes:24 hashwidth:64 capacity:1000200 size:5 ratio:1e-07"127.0.0.1:8001>127.0.0.1:8001>127.0.0.1:8001> bf.debug bloom_filter_test1) "size:128955"2) "bytes:4194304 bits:33554432 hashes:24 hashwidth:64 capacity:1000200 size:128955 ratio:1e-07"127.0.0.1:8001>127.0.0.1:8001>127.0.0.1:8001> bf.debug bloom_filter_test1) "size:380507"2) "bytes:4194304 bits:33554432 hashes:24 hashwidth:64 capacity:1000200 size:380507 ratio:1e-07"127.0.0.1:8001>127.0.0.1:8001>127.0.0.1:8001> bf.debug bloom_filter_test1) "size:569166"2) "bytes:4194304 bits:33554432 hashes:24 hashwidth:64 capacity:1000200 size:569166 ratio:1e-07"127.0.0.1:8001>127.0.0.1:8001>127.0.0.1:8001> bf.debug bloom_filter_test1) "size:852316"2) "bytes:4194304 bits:33554432 hashes:24 hashwidth:64 capacity:1000200 size:852316 ratio:1e-07"127.0.0.1:8001>127.0.0.1:8001>127.0.0.1:8001> bf.debug bloom_filter_test1) "size:1000005"2) "bytes:4194304 bits:33554432 hashes:24 hashwidth:64 capacity:1000200 size:1000005 ratio:1e-07"127.0.0.1:8001>
關于布隆過濾器資料型別的空間分析
redis的bigkeys選項可以分析整個實體中的big keys資訊，但是無法分析出MBbloom--型別的key值得大小
這里基于Redis的debug object功能，實作對MBbloom--型別的key的統計（沒有找到怎么用Python執行bf.debug原生命令的執行方式），
import redisimport sysimport timeimport randomdef get_bf_bigkeys(): try: redis_conn = redis.StrictRedis(host='127.0.0.1', port=8001, db=0, password='******') except: print("connect redis error") sys.exit(1) dict_key = {} cursor = 1 while cursor != 0: if cursor == 1: key = redis_conn.scan(cursor=0, match='*', count=5000) else: key = redis_conn.scan(cursor=cursor,match='*', count=5000) cursor = key[0] if len(key[1]) > 0: for var in key[1]: if str(redis_conn.type(var), encoding = "utf-8") == 'MBbloom--': info = redis_conn.debug_object(var) dict_key[var] = float(info['serializedlength']) / 1024 / 1024 # byte ---> mb res = sorted(dict_key.items(), key=lambda dict_key: dict_key[1], reverse=True) for i in range(10 if len(res) > 10 else len(res)): print(res[i])if __name__ == "__main__": get_bf_bigkeys()
統計結果示例如下
[root@tencent02 redis8001]# python3 static_big_bf_keys.py(b'bloom_filter_test', 4.000059127807617)(b'my_bf2', 0.04577445983886719)(b'bloom_filter_test2', 0.00014019012451171875)(b'my_bf1', 0.0001220703125)[root@tencent02 redis8001]#
參考：
https://redislabs.com/blog/rebloom-bloom-filter-datatype-redis/
https://oss.redislabs.com/redisbloom/Bloom_Commands/
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/40062.html
標籤：NoSQL
上一篇：pb資料視窗跳轉問題
下一篇：redis學習