通過Lua腳本批量插入資料到布隆過濾器
有關布隆過濾器的原理之前寫過一篇部落格： 算法(3)---布隆過濾器原理
在實際開發過程中經常會做的一步操作，就是判斷目前的key是否存在。
那這篇部落客要分為三部分：
1、幾種方式判斷目前key是否存在的性能進行比較。
2、Redis實作布隆過濾器并批量插入資料,并判斷目前key值是否存在。
3、針對以上做一個總結。 一、性能對比
主要對以下方法進行性能測試比較：
1、List的 contains 方法
2、Map的 containsKey 方法
3、Google布隆過濾器 mightContain 方法
前提準備
在SpringBoot項目啟動的時候，向 List集合、Map集合、Google布隆過濾器 分布存儲
500萬條
，長度為
32位的String
字元串。
1、示範代碼
@Slf4j
@RestController
public class PerformanceController {
/**
* 存儲500萬條資料
*/
public static final int SIZE = 5000000;
/**
* list集合存儲資料
*/
public static List<String> list = Lists.newArrayListWithCapacity(SIZE);
/**
* map集合存儲資料
*/
public static Map<String, Integer> map = Maps.newHashMapWithExpectedSize(SIZE);
/**
* guava 布隆過濾器
*/
BloomFilter<String> bloomFilter = BloomFilter.create(Funnels.unencodedCharsFunnel(), SIZE);
/**
* 用來校驗的集合
*/
public static List<String> exist = Lists.newArrayList();
/**
* 計時工具類
*/
public static Stopwatch stopwatch = Stopwatch.createUnstarted();
/**
* 初始化資料
*/
@PostConstruct
public void insertData() {
for (int i = 0; i < SIZE; i++) {
String data = UUID.randomUUID().toString();
data = data.replace("-", "");
//1、存入list
list.add(data);
//2、存入map
map.put(data, 0);
//3、存入本地布隆過濾器
bloomFilter.put(data);
//校驗資料 相當于從這500萬條資料,存儲5條到這個集合中
if (i % 1000000 == 0) {
exist.add(data);
}
}
}
/**
* 1、list 檢視value是否存在 執行時間
*/
@RequestMapping("/list")
public void existsList() {
//計時開始
stopwatch.start();
for (String s : exist) {
if (list.contains(s)) {
log.info("list集合存在該資料=============資料{}", s);
}
}
//計時結束
stopwatch.stop();
log.info("list集合測試，判斷該元素集合中是否存在用時:{}", stopwatch.elapsed(MILLISECONDS));
stopwatch.reset();
}
/**
* 2、檢視map 判斷k值是否存在 執行時間
*/
@RequestMapping("/map")
public void existsMap() {
//計時開始
stopwatch.start();
for (String s : exist) {
if (map.containsKey(s)) {
log.info("map集合存在該資料=============資料{}", s);
}
}
//計時結束
stopwatch.stop();
//擷取時間差
log.info("map集合測試，判斷該元素集合中是否存在用時:{}", stopwatch.elapsed(MILLISECONDS));
stopwatch.reset();
}
/**
* 3、檢視guava布隆過濾器 判斷value值是否存在 執行時間
*/
@RequestMapping("/bloom")
public void existsBloom() {
//計時開始
stopwatch.start();
for (String s : exist) {
if (bloomFilter.mightContain(s)) {
log.info("guava布隆過濾器存在該資料=============資料{}", s);
}
}
//計時結束
stopwatch.stop();
//擷取時間差
log.info("bloom集合測試，判斷該元素集合中是否存在用時:{}", stopwatch.elapsed(MILLISECONDS));
stopwatch.reset();
}
} 2、測試輸出結果
測試結果
這裡其實對每一個校驗是否存在的方法都執行了5次，如果算單次的話那麼，那麼在
500萬條資料，且每條資料長度為32位的String類型情況下
，可以大概得出。
1、List的contains方法執行所需時間，大概80毫秒左右。
2、Map的containsKey方法執行所需時間，不超過1毫秒。
3、Google布隆過濾器 mightContain 方法，不超過1毫秒。 總結
Map比List效率高的原因這裡就不用多說，沒有想到的是它們速度都這麼快。我還測了
100萬條資料通過list周遊key時間竟然也不超過1毫秒
。這說明在實際開發過程中，如果資料
量不大的話，用哪裡其實都差不多。
3、占用記憶體分析
從上面的執行效率來看，Google布隆過濾器 其實沒什麼優勢可言，确實如果資料量小，完全通過上面就可以解決，不需要考慮布隆過濾器，但如果資料量巨大，千萬甚至億級
别那種，用集合肯定不行，不是說執行效率不能接受，而是占記憶體不能接受。
我們來算下key值為32位元組的500萬條條資料，存放在List集合需要占多少記憶體。
500萬 * 32 = 16000000位元組 ≈ 152MB
一個集合就占這麼大記憶體，這點顯然無法接受的。
那我們來算算布隆過濾器所需要占記憶體
- 設bit數組大小為m，樣本數量為n，失誤率為p。
-
由題可知 n = 500萬，p = 3%（Google布隆過濾器預設為3%，我們也可以修改）
通過公式求得：
m ≈ 16.7MB
是不是可以接收多了。
那麼Google布隆過濾器也有很大缺點
1、每次項目啟動都要重新将資料存入Google布隆過濾器，消費額外的資源。
2、分布式叢集部署架構中，需要在每個叢集節點都要存儲一份相同資料到布隆過濾器中。
3、随着資料量的加大，布隆過濾器也會占比較大的JVM記憶體，顯然也不夠合理。 那麼有個更好的解決辦法，就是用redis作為分布式叢集的布隆過濾器。
二、Redis布隆過濾器
1、Redis伺服器搭建
如果你不是用docker,那麼你需要先在伺服器上部署redis，然後單獨安裝支援redis布隆過濾器的插件
rebloom
。
如果你用過docker那麼部署就非常簡單了，隻需以下指令：
docker pull redislabs/rebloom # 拉取鏡像
docker run -p 6379:6379 redislabs/rebloom # 運作容器 這樣就安裝成功了。
2、Lua批量插入腳本
SpringBoot完整代碼我這裡就不粘貼出來了，文章最後我會把整個項目的github位址附上，這裡就隻講下腳本的含義：
bloomFilter-inster.lua
local values = KEYS
local bloomName = ARGV[1]
local result_1
for k,v in ipairs(values) do
result_1 = redis.call('BF.ADD',bloomName,v)
end
return result_1 1）參數說明
這裡的
KEYS
和
ARGV[1]
都是需要我們在java代碼中傳入，redisTemplate有個方法
execute(RedisScript<T> script, List<K> keys, Object... args) - script實體中中封裝批量插入的lua腳本。
- keys 對于腳本的 KEYS。
- ARGV[1]對于可變參數第一個，如果輸入多個可變參數，可以可以通過ARGV[2].....去擷取。
2）周遊
Lua周遊腳本有兩種方式一個是
ipairs
,另一個是
pairs
它們還是有差别的。這裡也不做展開，下面有篇部落格可以參考。
注意
Lua的周遊和java中周遊還有有點差別的，我們java中是從0開始，而對于Lua腳本 k是從1開始的。
3）插入指令
BF.ADD
是往布隆過濾器中插入資料的指令，插入成功傳回 true。
3、判斷布隆過濾器元素是否存在Lua腳本
bloomFilter-exist.lua
local bloomName = KEYS[1]
local value = KEYS[2]
-- bloomFilter
local result_1 = redis.call('BF.EXISTS', bloomName, value)
return result_1 從這裡我們可以很明顯看到， KEYS[1]對于的是keys集合的get(0)位置,是以說Lua周遊是從1開始的。
BF.EXISTS
是判斷布隆過濾器中是否存在該資料指令，存在傳回true。
4、測試
我們來測下是否成功。
@Slf4j
@RestController
public class RedisBloomFilterController {
@Autowired
private RedisService redisService;
public static final String FILTER_NAME = "isMember";
/**
* 儲存 資料到redis布隆過濾器
*/
@RequestMapping("/save-redis-bloom")
public Object saveReidsBloom() {
//資料插入布隆過濾器
List<String> exist = Lists.newArrayList("11111", "22222");
Object object = redisService.addsLuaBloomFilter(FILTER_NAME, exist);
log.info("儲存是否成功====object:{}",object);
return object;
}
/**
* 查詢 目前資料redis布隆過濾器是否存在
*/
@RequestMapping("/exists-redis-bloom")
public void existsReidsBloom() {
//不存在輸出
if (!redisService.existsLuabloomFilter(FILTER_NAME, "00000")) {
log.info("redis布隆過濾器不存在該資料=============資料{}", "00000");
}
//存在輸出
if (redisService.existsLuabloomFilter(FILTER_NAME, "11111")) {
log.info("redis布隆過濾器存在該資料=============資料{}", "11111");
}
}
} 這裡先調插入接口，插入兩條資料，如果傳回true則說明成功，如果是同一個資料第一次插入傳回成功，第二次插入就會傳回false，說明重複插入相同值會失敗。
然後調查詢接口，這裡應該兩條日志都會輸出，因為上面"00000"是取反的，多了個！号。
我們來看最終結果。
符合我們的預期，說明，redis布隆過濾器從部署到整合SpringBoot都是成功的。
三、總結
下面個人對整個做一個總結吧。主要是思考下，在什麼環境下可以考慮用以上哪種方式來判斷該元素是否存在。
1、資料量不大，且不能有誤差。
那麼用List或者Map都可以，雖然說List判斷該元素是否存在采用的是周遊集合的方式，在性能在會比Map差，但就像上面測試一樣，100萬的資料，
List周遊和Map都不超過1毫秒，選誰不都一樣，何必在乎那0.幾毫秒的差異。
2、資料量不大，且允許有誤差。
這就可以考慮用
Google布隆過濾器
了，盡管查詢資料效率都差不多，但關鍵是它可以減少記憶體的開銷，這就很關鍵。
3、資料量大，且不能有誤差。
如果說數量大，為了提升查詢元素是否存在的效率，而選用Map的話，我覺得也不對，因為如果資料量大，所占記憶體也會更大，是以我更推薦用
Redis的map資料結構來存儲資料，這樣可以大大減少JVM記憶體開銷，而且不需要每次重新開機都要往集合中存儲資料。
4、資料量大，且允許有誤差。
如果是單體應用，資料量記憶體也可以接收，那麼可以考慮Google布隆過濾器，因為它的查詢速度會比redis要快。畢竟它不需要網絡IO開銷。
如果是分布式叢集架構，或者資料量非常大，那麼還是考慮用redis布隆過濾器吧，畢竟它不需要往每一節點都存儲資料，而且不占用JVM虛拟機記憶體。
Github位址
：https://github.com/yudiandemingzi/spring-boot-redis-lua
參考
1、redis lua官方文檔
2、redis lua中文翻譯文檔
3、Lua泛型for周遊table時ipairs與pairs的差別
隻要自己變優秀了，其他的事情才會跟着好起來（上将10）