布隆フィルタのデモ

 
/**
 *     
 * @author 
 *
 */
@RunWith(SpringJUnit4ClassRunner.class)
@ContextConfiguration(locations = {"classpath:config/spring/spring-dao.xml",
		"classpath:config/spring/spring-bean.xml",
		"classpath:config/spring/spring-redis.xml"})
public class CacheBreakDownTest {
	private static final Logger logger = LoggerFactory.getLogger(CacheBreakDownTest.class);
	
	private static final int THREAD_NUM = 100;//    
	
	@Resource
	private UserDao UserDao;
	
	@Resource
	private RedisTemplate redisTemplate;
	
	private int count = 0;
	
	//        
	private CountDownLatch countDownLatch = new CountDownLatch(THREAD_NUM);
	
	private BloomFilter bf;
	
	List allUsers;
	
	@PostConstruct
	public void init(){
		//            
		allUsers = UserDao.getAllUser();
		if(allUsers == null || allUsers.size()==0){
			return;
		}
		//       (  3%  )
		bf = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8), allUsers.size());
		//          
		for(UserDto userDto : allUsers){
			bf.put(userDto.getUserName());
		}
	}
	
	@Test
	public void cacheBreakDownTest(){
		for(int i=0;i operation = (ValueOperations) redisTemplate.opsForValue();
			synchronized (countDownLatch) {
				Object cacheUser = operation.get(key);
				if(cacheUser!=null){
					System.out.println("return user from redis");
					return;
				}
				//            
				List user = UserDao.getUserByUserName(randomUser);
				if(user == null || user.size() == 0){
					return;
				}
				// mysql            redis 
				System.out.println("write to redis");
				operation.set("Key:"+user.get(0).getUserName(), user.get(0).getUserName());
			}
		}
		
	}
}

demo 2

@RunWith(SpringRunner.class)
	@SpringBootTest
	public class BloomFilterTest {
	    private BloomFilter bloomFilter;

	    private int size = 1000000;
	    @Before
	    public void init(){
	        //         ，      0.03
	        //bloomFilter = BloomFilter.create(Funnels.integerFunnel(), size);
	        //        ，        hash  。bit      size fpp    
	        //       size    ，  size 2 n  。
	        bloomFilter = BloomFilter.create(Funnels.integerFunnel(), size, 0.01);
	        for(int i = 0; i < size; i++){
	            bloomFilter.put(i);
	        }
	    }
	    @Test
	    public void testBloomFilter(){
	        for(int i = 0; i < size; i++){
	            if(!bloomFilter.mightContain(i)){
	                //    ，              
	                System.out.println("      " + i);
	            }
	        }

	        List list = new ArrayList<>(1000);
	        for (int i = size + 10000; i < size + 20000; i++) {
	            if (bloomFilter.mightContain(i)) {
	                list.add(i);
	            }
	        }
	        //        
	        System.out.println("       ：" + list.size());
	    }
	}
	

布隆フィルタには以下のような応用シーンがあります.
1、ブラックリスト、例えばブラックリストフィルタ、メールアドレスがブラックリストにあるかどうかを判定します.
2、ネットの爬虫類はエンドロールがすでに登られたかどうかを判定します.
3、初めて訪問し、エンドアクセスサイトのIPは初めての訪問かどうかを判定する.
4、キャッシュの破壊、不法攻撃を防止し、キャッシュに命中できない要求を頻繁に送り、キャッシュの破壊を引き起こし、キャッシュの雪崩を最も引き起こす.
5、英語の単語のスペルが正しいかどうかを確認します.
6、K-Vシステムは迅速にあるkeyが存在するかどうかを判断し、典型的な例はHbaseであり、HbaseのRegionの各々にはBloomFilterが含まれており、クエリ時にあるkeyがこのregionに存在するかどうかを素早く判断し、存在しない場合は直接に戻り、後続のクエリを節約する.
どのように布隆フィルタの削除をサポートするかを拡張します.
カウント削除を行いますが、カウント削除は元のビットよりも1つの値を記憶する必要があり、占有メモリサイズが大きくなります.このようにすると、1つの値を追加すると、対応するインデックススロットに格納されている値を1つ加算し、削除するとマイナス1となり、存在するかどうかを判断すると、0より大きい値を見ることになる.