1019      阿裏雲  技術社區[雲棲]

基於redis(key分段,避免一個key過大) 和db實現的 布隆過濾器（解決hash碰撞問題）

1.計算出key的哈希值。
2. 根據hash值和固定段大小取模計算出偏移位offset。
3. 根據固定前置+hash值／固定段大小計算出所處段的bitKey。
4. 根據bitKey和offset判斷是否存在。
5. 如果存在然後調用containsFromDb判斷是否存在。
6. 將redis setbit進行分段可以避免單個key數據量過大。
7. 如果redis是集群也可以將分出來的段根據jedis crc16算法有概率的被打算
在各個節點上，避免單個節點過熱。

代碼示例：
package six.com.crawler.work.space;

import java.util.Objects;

import redis.clients.jedis.Jedis;

public class RedisAndDbBloomFilter {

private String nameSpace;
private Jedis jedis;
private int fixSize;

public RedisAndDbBloomFilter(String nameSpace,Jedis jedis,int fixSize){
    this.nameSpace=nameSpace;
    this.jedis=jedis;
    this.fixSize=fixSize;
}

private int getHash(String key){
    return key.hashCode();
}

private void addToDb(int hash,String key){
    //TODO 將記錄保存至db
}

private boolean containsFromDb(int hash,String key){
    //TODO 根據 hash key 查詢數據庫是否存在
    return false;
}

/**
 * 根據hash和fixSize 算出bitKey
 * @param hash
 * @return
 */
private String getBitKey(int hash){
    int bitKeyIndex=hash/fixSize;
    String bitKey=nameSpace+bitKeyIndex;
    return bitKey;
}
/**
 * 判斷給定的key是否存在
 * @param key
 * @return
 */
public boolean contains(String key){
    //TODO 如果是集群模式這裏需要分布式鎖，如果是單機這裏需要線程鎖
    Objects.requireNonNull(key, "the key must not be null");
    int hash=getHash(key);
    int offset=hash%fixSize;
    String bitKey=getBitKey(hash);
    Boolean result=jedis.getbit(bitKey,offset);
    if(result.booleanValue()&&containsFromDb(hash, key)){
        return true;
    }
    return false;
}

/**
 * 根據給定的key添加一個過濾記錄
 * @param key
 */
public void addRecord(String key){
    //TODO 如果是集群模式這裏需要分布式鎖，如果是單機這裏需要線程鎖
    int hash=getHash(key);
    int offset=hash%fixSize;
    String bitKey=getBitKey(hash);
    jedis.setbit(bitKey,offset, true);
    addToDb(hash, key);
}    

}

最後更新：2017-08-13 22:22:35

  上一篇：  傳統企業轉向互聯網，如何快速提升研發效能？

  下一篇：  redis分布式鎖，無須設置有效期，自動檢測hold鎖的節點是否存活