Yilena
境界の備忘録
这里是一处被时间遗忘的避难所。
浮空之岛上，堆叠着理性构筑的文字、应对命运审判的答卷，还有那些在午夜寂静时、从指缝间溜走的虚幻灵感。
终究是要展翅远航的吧。在你的羽翼尚未丰满前，愿这些微弱的火光，能稍微温暖你疲惫的旅程。
文章标签
872 字
2 分钟
布隆过滤器因内存上限无法处理超量数据的优化方案
目录
一、业务需求
你负责的项目使用布隆过滤器进行缓存穿透的防御，但是随着数据量的增加，布隆过滤器桶的数量已经不足以容纳新的数据，请你提供一种解决方案。
二、分析
不足这问题解决方案其实也只有扩容两字，无非就是扩容的方式不同，比如说如果一个布隆过滤器不够的话我们就再多创建几个，然后通过分片将其合并；又或是直接换个大点的地方存储，我们的优化方案实际上也就是这两个方向。
三、优化方案
（一）分片布隆过滤器
直接哈希取模即可，简单高效。
public class ShardedBloomFilter { private final List<BloomFilter<String>> shards; private final int shardCount;
// 初始化分片 public ShardedBloomFilter(int shardCount, long totalExpectedInsertions, double falsePositiveRate) { this.shardCount = shardCount; this.shards = new ArrayList<>(shardCount);
// 计算每个分片的预期插入量 long insertionsPerShard = (totalExpectedInsertions + shardCount - 1) / shardCount; for (int i = 0; i < shardCount; i++) { shards.add(BloomFilter.create( Funnels.stringFunnel(StandardCharsets.UTF_8), insertionsPerShard, falsePositiveRate )); } }
// 根据元素哈希选择分片 private int getShardIndex(String element) { return Math.abs(element.hashCode()) % shardCount; }
// 插入 public void put(String element) { int shardIndex = getShardIndex(element); shards.get(shardIndex).put(element); }
// 判断是否存在 public boolean mightContain(String element) { int shardIndex = getShardIndex(element); return shards.get(shardIndex).mightContain(element); }}但是同时缺点也很明显，一是只能部署在单机上，无法在上应用；二是其存储在JVM的堆内存空间中，会挤压其他对象的内存空间，而且其以位数组的方式存储，直接晋升老年代，从而增多Minor GC甚至Full GC的次数，拖慢程序性能；三是位数组为大对象，容易引发OOM。
（二）分布式布隆过滤器
分布式布隆过滤器一般指的是在Redis上的布隆过滤器，由于摆脱了单机JVM的内存存储限制，所以被广泛应用在分布式架构上。其跟普通布隆过滤器的区别就是存储的地方不一样。
其有封装的包装类RBloomFilter，直接使用即可，非常的方便。
但是其也会挤占普通缓存数据的空间，导致触发缓存淘汰的次数增加，为了解决这个问题，我们也可以给其进行分片，分散到集群当中。
public class DistributedShardedBloomFilter { private final List<RedisShard> shards; private final double falsePositiveRate; private final long expectedInsertions; private static final String BLOOM_PREFIX = "bf:shard:";
/** * Redis分片封装类 * * 包含分片标识和对应的Redis客户端连接 */ private static class RedisShard { // 分片唯一标识 private final String name; // Redis客户端连接 private final StringRedisTemplate redisTemplate;
public RedisShard(String name, StringRedisTemplate redisTemplate) { this.name = name; this.redisTemplate = redisTemplate; } }
public DistributedShardedBloomFilter(List<RedisNode> nodes, long expectedInsertions, double falsePositiveRate) { this.falsePositiveRate = falsePositiveRate; this.expectedInsertions = expectedInsertions; this.shards = new ArrayList<>(nodes.size());
// 初始化每个Redis分片的连接 for (RedisNode node : nodes) { // 创建Redis客户端连接 StringRedisTemplate template = createRedisTemplate(node.host(), node.port()); // 封装分片信息 shards.add(new RedisShard(node.id(), template)); }
// 在所有分片上初始化布隆过滤器 initializeFilters(); }
/** * 创建Redis客户端连接 */ private StringRedisTemplate createRedisTemplate(String host, int port) { // 配置Redis连接参数 RedisStandaloneConfiguration config = new RedisStandaloneConfiguration(host, port);
// 创建连接工厂（使用Jedis客户端） JedisConnectionFactory factory = new JedisConnectionFactory(config); // 初始化连接池 factory.afterPropertiesSet();
// 创建Redis模板 StringRedisTemplate template = new StringRedisTemplate(); template.setConnectionFactory(factory); template.afterPropertiesSet();
return template; }
/** * 初始化所有分片的布隆过滤器 * 计算每个分片应处理的数据量，并在各分片上创建布隆过滤器 */ private void initializeFilters() { // 计算每个分片的预期容量（向上取整） long perShardCapacity = (expectedInsertions + shards.size() - 1) / shards.size();
// 在每个分片上初始化布隆过滤器 for (RedisShard shard : shards) { // 执行命令创建布隆过滤器 executeBloomCommand( shard.redisTemplate, BloomCommand.RESERVE, BLOOM_PREFIX + shard.name, String.valueOf(falsePositiveRate), String.valueOf(perShardCapacity) ); } }
/** * 使用一致性哈希定位元素所在分片 */ private RedisShard getShard(String element) { // 计算元素的128位MurmurHash long hash = Hashing.murmur3_128().hashString(element, StandardCharsets.UTF_8).asLong();
// 使用一致性哈希算法确定分片位置 int shardIndex = Hashing.consistentHash(hash, shards.size());
return shards.get(shardIndex); }
// 添加 public void add(String element) { RedisShard shard = getShard(element); executeBloomCommand( shard.redisTemplate, BloomCommand.ADD, BLOOM_PREFIX + shard.name, element ); }
// 检查是否存在 public boolean mightContain(String element) { RedisShard shard = getShard(element); return Boolean.TRUE.equals(shard.redisTemplate.execute((RedisCallback<Boolean>) connection -> { String key = BLOOM_PREFIX + shard.name;
// 发送Redis命令并解析响应 Long result = (Long) connection.execute( BloomCommand.EXISTS.name(), key.getBytes(StandardCharsets.UTF_8), element.getBytes(StandardCharsets.UTF_8) );
// 结果1表示存在，0表示不存在 return result != null && result == 1; })); }
// 添加元素的执行命令 private void executeBloomCommand(StringRedisTemplate redisTemplate, BloomCommand command, String key, String... args) { redisTemplate.execute((RedisCallback<Void>) connection -> { // 构建命令参数数组 byte[][] commandArgs = new byte[args.length + 1][]; commandArgs[0] = key.getBytes(StandardCharsets.UTF_8);
// 填充剩余参数 for (int i = 0; i < args.length; i++) { commandArgs[i + 1] = args[i].getBytes(StandardCharsets.UTF_8); }
// 执行原始命令 connection.execute(command.name(), commandArgs); return null; }); }
private enum BloomCommand { // 创建布隆过滤器 RESERVE, // 添加元素 ADD, // 检查元素 EXISTS }
/** * Redis节点信息记录 */ public record RedisNode(String id, String host, int port) {}}（三）可扩展布隆过滤器
这个方案采取的思想就是直接扩容，当原本的布隆过滤器内存占用率达九成时，就再创建一个空间为原来两倍大的布隆过滤器作为下一层，原来那层的权限变为只读，新写入的元素都会插入在第二层的布隆过滤器上，如果第二次的内存占用率也达九成就继续创建下一层……
public class ScalableBloomFilter { // 目标总误判率 private final double targetFalsePositiveRate; // 衰减因子 private final double decayFactor; // 初始层容量 private final int initialCapacity; // 扩容填充阈值 private final double fillRatioThreshold;
private final List<BloomFilter<String>> filters = new ArrayList<>(); private int currentLayerIndex = -1;
public ScalableBloomFilter(double targetFalsePositiveRate, double decayFactor, int initialCapacity) { this.targetFalsePositiveRate = targetFalsePositiveRate; this.decayFactor = decayFactor; this.initialCapacity = initialCapacity; this.fillRatioThreshold = 0.75; // 初始化第一层 addNewLayer(); }
// 添加新层 private void addNewLayer() { double layerFalsePositiveRate = targetFalsePositiveRate * Math.pow(decayFactor, filters.size()); int layerCapacity = (currentLayerIndex == -1) ? initialCapacity : filters.get(currentLayerIndex).approximateElementCount() * 2;
BloomFilter<String> newFilter = BloomFilter.create( Funnels.stringFunnel(StandardCharsets.UTF_8), layerCapacity, layerFalsePositiveRate );
filters.add(newFilter); currentLayerIndex++; }
// 插入元素 public void add(String element) { BloomFilter<String> currentLayer = filters.get(currentLayerIndex); if (currentLayer.approximateElementCount() >= fillRatioThreshold * currentLayer.expectedFpp()) { // 扩容 addNewLayer(); // 更新当前层 currentLayer = filters.get(currentLayerIndex); } currentLayer.put(element); }
// 检查元素是否存在 public boolean mightContain(String element) { // 从旧层到新层遍历 for (BloomFilter<String> filter : filters) { if (filter.mightContain(element)) { // 任一层命中即返回 return true; } } return false; }}但是很容易想到，分片布隆过滤器有的缺点它都有，但是其动态扩展的特点也能够腾出多余的内存空间供其他对象使用，但依旧无法掩盖其劣势。
除此之外还有一个缺点就是使用越久，层数越多，查询最新元素的效率就越慢，因为得逐层寻找。
四、总结
三种方案，单机项目优先使用分片方案，分布式则采取分布式分片方案即可，但可扩展方案并不推荐。
码文不易，留个赞再走吧
原文链接: 布隆过滤器因内存上限无法处理超量数据的优化方案 作者: Yilena
分享
如果这篇文章对你有帮助，欢迎分享给更多人！
布隆过滤器因内存上限无法处理超量数据的优化方案
https://blog.csdn.net/2401_88959292/article/details/150222807?spm=1001.2014.3001.5501 部分信息可能已经过时
相关文章 智能推荐
1
116秒→6秒：Redis管道+批处理优化用户好友关系校验的方案
业务拆解 本文针对社交平台中用户好友关系数据一致性问题，提出了一种高效的定时任务解决方案。通过分析初版方案的性能瓶颈（单线程串行处理导致116秒耗时），逐步优化为多线程并行处理（70秒）和最终版批量预加载策略（6秒）。终版方案的核心改进包括：1）预加载所有关注关系并建立内存映射；2）批量处理好友数据更新；3）使用Redis管道技术减少网络请求。最终将请求次数从35万次降至常数级，同时提供了完整的Java实现代码，包含分片处理、批量数据库操作和Redis管道更新等关键优化技术。
2
360s→15s：近25倍的性能优化重构十万Excel券码批量导入方案
业务拆解 本文针对十万级Excel券码批量导入场景，将原逐行解析导致的20万次网络IO，通过Redis管道与MQ批处理优化至182次。方案兼顾了宕机恢复与库存扣减，最终将耗时从360秒大幅缩减至15秒左右。
3
如何应对海量Key带来的redis内存占用问题？
业务拆解 本文针对海量Key导致的Redis内存占用过高问题，深入分析了内存碎片化与元数据开销的根源，并提出了五种切实可行的解决方案。从基础的合并小Key（利用Hash结构）与临时添加TTL救急，到架构层面的Redis集群模式与Redis on Flash（内存+SSD）降本方案，再到结合MySQL的冷热数据分离策略（全量/冷数据存DB，热数据存Redis）。文章通过详实的流程图与优劣对比，帮助开发者在不同预算与业务场景下，科学应对Redis内存瓶颈。
4
优化：将针对单一日志表的冷热数据分离类改造成通用类
业务拆解 本文记录了将针对单一日志表的冷热数据分离逻辑重构为通用类的优化过程。为解决旧版方案中代码冗余及复用性差的问题，新方案通过参数化固定逻辑、引入泛型机制适配不同数据实体，并为不同日志表提供专属的Elasticsearch插入重载函数，实现了高度定制化与通用性的统一。文章详细展示了重构后的具体流程图及Java代码实现，包括利用CompletableFuture进行多线程并行处理、基于游标的批量数据查询与迁移、以及完善的重试与异常处理机制，有效提升了海量日志数据冷热分离任务的执行效率与代码可维护性。
5
优化日志分析店铺推荐方案：用户范围的精确度以及ES与MySQL的查询效率差异
业务拆解 本文针对点餐场景下的店铺推荐方案进行了深度优化。首先，通过Redis记录用户月度登录天数，精准筛选出热点用户，解决了旧版方案中推荐用户范围不精确的问题。其次，对比了Elasticsearch与MySQL在十万级数据量下的查询效率，将热数据迁移至MySQL并建立索引以提升查询性能，同时保留ES作为冷数据备份。文章详细展示了优化后的业务流程图及Java代码实现，包括基于Lua脚本的Redis原子操作、多线程并行处理用户日志分析以及加权评分推荐算法，为高并发场景下的日志分析与个性化推荐提供了高效的工程实践。