文档章节

基于redis(key分段,避免一个key过大) 和db实现的 布隆过滤器(解决hash碰撞问题)

小虾米DYX
 小虾米DYX
发布于 2017/08/16 14:14
字数 581
阅读 35
收藏 0

点击查看全文

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);
}    

}

 

 

点击查看全文

本文转载自:http://click.aliyun.com/m/28535/

小虾米DYX
粉丝 0
博文 113
码字总数 0
作品 0
海淀
私信 提问
Redis缓存使用-穿透、雪崩、热点key问题

一、缓存穿透 redis缓存穿透:查询一个数据库中不存在的数据,比如商品详情,查询一个不存在的ID,每次都会访问DB,如果有人恶意破坏,很可能直接对DB造成过大地压力。 解决方案: 1、缓存空...

淡淡的倔强
02/25
0
0
分布式系列之缓存设计中常见的问题

缓存这个东西相信大家工作中都接触得比较多,相应的在不同场景下也会遇到各种各样的问题。下面我列举几种可能会遇到的问题并提供一些解决建议。 1、如何把海量数据存放在缓存中并提供快速查询...

浮云骑士LIN
2018/07/24
0
0
redis缓存击穿、缓存穿透、缓存雪崩

对于缓存而言, 约束好key的规范,合理确定Val值的大小,选择合适的缓存介质(相应的根据实际的业务情况分析,哪种缓存方式合适 redis、zk、memcached 亦或者 local)。(生产实际案例:red...

noob_fly
02/19
3.5K
0
LevelDB 入门 —— 全面了解 LevelDB 的功能特性

本节我们将全面了解一下 LevelDB 的各种特性。LevelDB 的开发语言是 C++,考虑到会使用 C++ 语言的同学不是很多,在本节我们将使用 Java 语言来描述 LevelDB 的特性。其它语言栈的同学也不必...

技术小能手
01/11
0
0
详解布隆过滤器的原理、使用场景和注意事项

今天碰到个业务,他的 Redis 集群有个大 Value 用途是作为布隆过滤器,但沟通的时候被小怼了一下,意思大概是 “布隆过滤器原理都不懂,还要我优化?”。技术菜被人怼认了、怪不得别人,自己...

YoungChen__
2018/08/30
0
0

没有更多内容

加载失败,请刷新页面

加载更多

川普给埃尔多安和内堪尼亚胡的信

任性 https://twitter.com/netanyahu/status/1186647558401253377 https://edition.cnn.com/2019/10/16/politics/trump-erdogan-letter/index.htm...

Iridium
24分钟前
10
0
golang-mysql-原生

db.go package mainimport ("database/sql""time"_ "github.com/go-sql-driver/mysql")var (db *sql.DBdsn = "root:123456@tcp(127.0.0.1:3306)/test?charset=u......

李琼涛
52分钟前
5
0
编程作业20191021092341

1编写一个程序,把用分钟表示的时间转换成用小时和分钟表示的时 间。使用#define或const创建一个表示60的符号常量或const变量。通过while 循环让用户重复输入值,直到用户输入小于或等于0的值...

1李嘉焘1
53分钟前
7
0
Netty整合Protobuffer

现在我们都知道,rpc的三要素:IO模型,线程模型,然后就是数据交互模型,即我们说的序列化和反序列化,现在我们来看一下压缩比率最大的二进制序列化方式——Protobuffer,而且该方式是可以跨...

算法之名
58分钟前
19
0
如何用C++实现栈

栈的定义 栈(stack)又名堆栈,它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶,相对地,把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压...

BWH_Steven
今天
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部