背景
業務方需要實作一個曝光去重的功能，決定采用布隆過濾器，又因為是多節點應用，為保證資料一致性，通過Redis實作，本文記錄下開發時的思路，以及優化程序，
初次實作
Redis4.0以上對布隆進行了插件支持，可以用特定的指令進行元素添加和判重，但考慮到不是所有環境的Redis都支持插件安裝，以及違背死磕精神，決定自行實作，
第一版的實作使用Guava的BloomFilter進行hash操作，redis通過String型別存放bit陣列，
估算空間
在實作業務前，估算大致需要插入的元素以及能接受的誤判率，來計算預計需要的空間（參考Guava中的方法），
/**
* @param n 預計插入的元素
* @param p 誤判率（0 < p < 1）
*/
long optimalNumOfBits(long n, double p) {
if (p == 0) {
p = Double.MIN_VALUE;
}
return (long) (-n * Math.log(p) / (Math.log(2) * Math.log(2)));
}
例如我們預計插入500個元素，誤判率取千分之三，輸入到函式中得到 6045 ，即6045 bit = 755.625 B = 0.73 KB ， 當然在Redis中資料結構還有額外存盤，所以結果僅供參考，
Setbit & Getbit
布隆的Hash演算法有很多，例如MURMUR128_MITZ_32，演算法實作此處不贅述，可以google一下，經過數次hash后得到下標陣列，儲存著元素映射到陣列的下標，
判重：
for (int i : offset) {
if (!redisTemplate.opsForValue().getBit(key, i)){
return false;
}
}
return true;
添加：
for (int i : offset) {
redisTemplate.opsForValue().setBit(key, i, true);
}
至此，布隆就實作完畢了，
Pipeline
雖然getbit和setbit都是O(1)操作，然而每個元素的 添加/判重 都需要進行數次setbit，其次數與插入量和布隆過濾器長度相關：
/**
* @param n 預估插入量
* @param m 布隆過濾器長度
*/
int optimalNumOfHashFunctions(long n, long m) {
return Math.max(1, (int) Math.round((double) m / n * Math.log(2)));
}
取上文中的6045bit以及500個預估插入，進行代入得到操作次數 = 5，
每 添加/判重 1個元素就需要進行 5 次bit操作，這期間建立了5次TCP連接，顯然對通道造成浪費，我們用redis pipeline優化一下～
添加：
redisTemplate.executePipelined((RedisCallback) connection -> {
for (int i : offset) {
connection.setBit(redisTemplate.getKeySerializer().serialize(key), i, true);
}
return null;
});
判重：
List<Boolean> list = redisTemplate.executePipelined((RedisCallback) connection -> {
for (int i : offset) {
connection.getBit(redisTemplate.getKeySerializer().serialize(key), i);
}
return null;
});
List<List<Boolean>> valuePairs = Lists.partition(list, numHashFunctions);
Map<R, Boolean> result = Maps.newHashMapWithExpectedSize(values.size());
for (int i = 0; i < values.size(); i++) {
R v = values.get(i);
result.put(v, valuePairs.get(i).stream().reduce(true, Boolean::logicalAnd));
}
return result;
同時筆者將方法改造成可批量判重元素的形式，將結果集按操作次數拆分成數個子集（pipeline回傳的結果集是有序的，這點很重要），每個子集各自累加，最終得到一張[元素:是否存在]的Map，
實測pipeline化后速度提升了不少，不過還沒完，
bitfield
bit操作快，但請求次數也多，在上述pipeline上線后，redis在業務高峰時qps有明顯的上升，
set/get bit每次只能操作單個bit位，是否可以一條命令操作完成多個bit位的操作？
BITFIELD
BITFIELD key [GET type offset] [SET type offset value] [INCRBY type offset increment] [OVERFLOW WRAP|SAT|FAIL]
BITFIELD 命令可以將一個 Redis 字串看作是一個由二進制位組成的陣列， 并對這個陣列中任意偏移進行訪問，
BITFIELD可以指定多個子命令，有 get/set/incr 三種操作型別，可以在一條命令中完成復合操作，并回傳結果集，當然命令的執行速度取決于由多少個子命令組成，
Redis官方解釋開發bitfield的動機是為了方便操作bitmap，但不妨礙我們在布隆過濾器中使用它，
添加：
BitFieldSubCommands commands = BitFieldSubCommands.create();
for (int i : offset) {
commands.set(BitFieldSubCommands.BitFieldType.unsigned(1))
.valueAt(i)
.to(1);
}
redisTemplate.opsForValue().bitField(key, commands);
注意在定義子命令時要宣告運算元的長度，指定為無符號1位即可，
判重：
BitFieldSubCommands commands = BitFieldSubCommands.create();
for (int i : offset) {
commands.get(BitFieldSubCommands.BitFieldType.unsigned(1))
.valueAt(i);
}
List<Long> result = redisTemplate.opsForValue().bitField(key, commands);
判重時對結果集的處理同pipeline，
使用bitfield后，經測驗高qps現象有明顯改善，但對cpu改善不大，因為redis內部執行的bit操作并沒有減少，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/256610.html
標籤：Java