跳至主要內容

获客项目——RoaringBitmap位图计算组件

util6大约 12 分钟

获客项目——RoaringBitmap位图计算组件

项目背景与技术选型

业务场景描述

面试官：请介绍一下你们获客项目中位图计算组件的应用场景？

标准回答：
我们的获客系统面向教育、金融等多行业提供全链路智能获客解决方案。系统需要处理亿级用户的标签管理和人群圈选，核心痛点是：

  1. 海量用户标签存储：1000+标签 × 亿级用户，传统关系型数据库无法承载
  2. 复杂标签组合计算：业务需要支持"A且B非C"等复杂逻辑的秒级响应
  3. 实时人群圈选：营销活动需要实时筛选目标人群，要求毫秒级响应
  4. 用户ID稀疏分布：使用雪花算法生成的用户ID，分布极度稀疏

基于这些需求，我们最终选择了RoaringBitmap直接存储用户ID的方案。

技术选型演进过程

阶段方案问题决策
初期调研Redis传统Bitmap雪花ID导致极大空间浪费放弃
方案探索Redis Bitmap + ID映射需要维护复杂的映射表复杂度过高
最终方案RoaringBitmap直接存储完美解决稀疏ID问题✅ 采用

一、RoaringBitmap核心技术原理

1.1 为什么选择RoaringBitmap？

面试官：为什么最终选择RoaringBitmap而不是Redis Bitmap？

回答要点：

  1. 稀疏数据优化：我们的用户ID是雪花算法生成，极度稀疏，传统Bitmap会浪费大量空间
  2. 直接存储ID：RoaringBitmap可以直接存储任意大整数，无需额外的ID映射表
  3. 自动压缩：根据数据密度自动选择最优存储结构，空间利用率极高
  4. 高效集合运算：支持AND/OR/NOT等操作，性能优于传统集合结构

1.2 RoaringBitmap底层实现原理

面试官：RoaringBitmap是如何对大整数进行优化的？底层的位运算是如何实现的？

详细技术解析：

分块+自适应容器机制

/**
 * RoaringBitmap核心结构解析
 * 
 * 设计思想：将32位整数空间分为65536个"块"，每个块最多包含65536个整数
 * 高16位作为"块号"，低16位作为块内"偏移量"
 */
public class RoaringBitmapStructure {
    
    /**
     * 整数分块示例
     * 
     * 用户ID: 123456789
     * 二进制: 0111 0101 1011 1100 1101 0001 0101 (32位)
     * 高16位: 0111 0101 1011 1100 = 30140 (块号)
     * 低16位: 1101 0001 0101 = 53525 (块内偏移)
     */
    public static void demonstrateBlocking() {
        long userId = 123456789L;
        int blockId = (int) (userId >>> 16);  // 高16位：块号
        int offset = (int) (userId & 0xFFFF); // 低16位：偏移量
        
        System.out.println("用户ID: " + userId);
        System.out.println("块号: " + blockId);
        System.out.println("块内偏移: " + offset);
    }
}

三种自适应容器类型

容器类型适用场景存储结构空间复杂度切换条件
ArrayContainer稀疏数据short[]数组O(N)元素数 < 4096
BitmapContainer稠密数据8KB位图固定8KB元素数 ≥ 4096
RunContainer连续区间区间编码O(区间数)连续区间较多时
/**
 * 容器自动切换机制演示
 */
public class ContainerSwitchingDemo {
    
    public void demonstrateContainerSwitching() {
        RoaringBitmap bitmap = new RoaringBitmap();
        
        // 阶段1：稀疏数据 -> ArrayContainer
        bitmap.add(100);
        bitmap.add(200);
        bitmap.add(300);
        // 此时内部使用ArrayContainer存储[100, 200, 300]
        
        // 阶段2：数据增多 -> 自动切换到BitmapContainer
        for (int i = 0; i < 5000; i++) {
            bitmap.add(i);
        }
        // 当元素数超过4096时，自动切换为BitmapContainer
        
        // 阶段3：连续区间 -> RunContainer
        bitmap.add(10000, 20000); // 添加连续区间
        // 如果连续区间较多，可能切换为RunContainer
        
        System.out.println("最终大小: " + bitmap.getSizeInBytes() + " bytes");
        System.out.println("元素数量: " + bitmap.getCardinality());
    }
}

1.3 RoaringBitmap vs 传统Bitmap的本质区别

面试官：RoaringBitmap的位运算与传统Bitmap有什么区别？

核心区别解析：

对比维度传统BitmapRoaringBitmap
存储方式固定长度bit数组分块+自适应容器
位运算方式全量bit数组按位运算只对有数据的块进行容器级运算
空间利用按最大ID分配空间只为实际数据分配空间
运算效率O(最大ID/8)O(实际数据块数)
/**
 * RoaringBitmap集合运算实现
 */
public class RoaringBitmapOperations {
    
    /**
     * 交集运算演示
     * 
     * 关键点：只对两个RoaringBitmap都有数据的块进行运算
     */
    public RoaringBitmap intersectionDemo() {
        RoaringBitmap bitmap1 = new RoaringBitmap();
        RoaringBitmap bitmap2 = new RoaringBitmap();
        
        // bitmap1: 块0有数据，块1有数据
        bitmap1.add(100);    // 块0
        bitmap1.add(65536);  // 块1
        
        // bitmap2: 块0有数据，块2有数据  
        bitmap2.add(200);    // 块0
        bitmap2.add(131072); // 块2
        
        // 交集运算：只对块0进行运算（两个bitmap都有的块）
        RoaringBitmap result = RoaringBitmap.and(bitmap1, bitmap2);
        
        // 结果：空集（块0内没有相同元素）
        System.out.println("交集结果数量: " + result.getCardinality());
        
        return result;
    }
    
    /**
     * 并集运算演示
     */
    public RoaringBitmap unionDemo() {
        RoaringBitmap bitmap1 = new RoaringBitmap();
        RoaringBitmap bitmap2 = new RoaringBitmap();
        
        bitmap1.add(100, 200, 300);
        bitmap2.add(150, 250, 350);
        
        // 并集运算：合并所有块的数据
        RoaringBitmap result = RoaringBitmap.or(bitmap1, bitmap2);
        
        System.out.println("并集结果: " + Arrays.toString(result.toArray()));
        // 输出: [100, 150, 200, 250, 300, 350]
        
        return result;
    }
}

二、项目中的RoaringBitmap实现

2.1 核心架构设计

2.2 完整Java实现

/**
 * 获客系统RoaringBitmap标签计算服务
 * 
 * 核心特点：
 * 1. 直接存储雪花ID，无需映射表
 * 2. 序列化存储到Redis，支持分布式访问
 * 3. 高效的集合运算，支持复杂标签组合
 */
@Service
@Slf4j
public class CustomerAcquisitionBitmapService {
    
    @Autowired
    private RedisTemplate&lt;String, byte[]&gt; redisTemplate;
    
    /**
     * 为用户打标签
     * 
     * @param tagId 标签ID（如"male", "vip", "beijing"等）
     * @param userIds 用户雪花ID列表
     */
    public void tagUsers(String tagId, List&lt;Long&gt; userIds) {
        log.info("开始为标签 {} 打标，用户数量: {}", tagId, userIds.size());
        
        // 创建RoaringBitmap并直接添加雪花ID
        RoaringBitmap bitmap = new RoaringBitmap();
        userIds.forEach(userId -> {
            // 注意：雪花ID是long类型，需要转换为int
            // 这里假设我们的雪花ID在int范围内，或者使用RoaringBitmap的long版本
            bitmap.add(userId.intValue());
        });
        
        // 序列化并存储到Redis
        try {
            byte[] serializedBitmap = serializeRoaringBitmap(bitmap);
            String redisKey = buildTagKey(tagId);
            
            redisTemplate.opsForValue().set(redisKey, serializedBitmap);
            redisTemplate.expire(redisKey, Duration.ofDays(30)); // 30天过期
            
            log.info("标签 {} 打标完成，压缩后大小: {} bytes，压缩比: {}", 
                tagId, serializedBitmap.length, calculateCompressionRatio(userIds.size(), serializedBitmap.length));
                
        } catch (IOException e) {
            log.error("标签 {} 序列化失败", tagId, e);
            throw new RuntimeException("标签存储失败", e);
        }
    }
    
    /**
     * 标签交集计算 - 核心人群圈选逻辑
     * 
     * @param tagIds 标签ID列表
     * @return 圈选结果
     */
    public CrowdSelectionResult selectCrowdByIntersection(List&lt;String&gt; tagIds) {
        log.info("开始计算标签交集，标签: {}", tagIds);
        long startTime = System.currentTimeMillis();
        
        // 批量从Redis加载RoaringBitmap
        List&lt;RoaringBitmap&gt; bitmaps = loadBitmapsFromRedis(tagIds);
        
        if (bitmaps.isEmpty()) {
            return new CrowdSelectionResult(new RoaringBitmap(), 0, 0);
        }
        
        // 执行交集运算
        RoaringBitmap result = bitmaps.get(0);
        for (int i = 1; i < bitmaps.size(); i++) {
            result = RoaringBitmap.and(result, bitmaps.get(i));
            
            // 早期退出优化：如果交集为空，直接返回
            if (result.isEmpty()) {
                break;
            }
        }
        
        long calculateTime = System.currentTimeMillis() - startTime;
        
        log.info("标签交集计算完成，结果人群数量: {}，耗时: {} ms", 
            result.getCardinality(), calculateTime);
        
        return new CrowdSelectionResult(result, result.getCardinality(), calculateTime);
    }
    
    /**
     * 复杂标签组合：A且B非C
     * 
     * @param includeTags 必须包含的标签
     * @param excludeTags 必须排除的标签
     * @return 圈选结果
     */
    public CrowdSelectionResult selectCrowdByComplexLogic(
            List&lt;String&gt; includeTags, List&lt;String&gt; excludeTags) {
        
        log.info("开始复杂标签圈选，包含标签: {}，排除标签: {}", includeTags, excludeTags);
        long startTime = System.currentTimeMillis();
        
        RoaringBitmap result = null;
        
        // 第一步：计算包含标签的交集
        if (!includeTags.isEmpty()) {
            CrowdSelectionResult includeResult = selectCrowdByIntersection(includeTags);
            result = includeResult.getBitmap();
        }
        
        // 第二步：排除不需要的标签
        if (!excludeTags.isEmpty() && result != null && !result.isEmpty()) {
            List&lt;RoaringBitmap&gt; excludeBitmaps = loadBitmapsFromRedis(excludeTags);
            
            // 计算排除标签的并集
            RoaringBitmap excludeUnion = new RoaringBitmap();
            for (RoaringBitmap excludeBitmap : excludeBitmaps) {
                excludeUnion = RoaringBitmap.or(excludeUnion, excludeBitmap);
            }
            
            // 从结果中排除
            result = RoaringBitmap.andNot(result, excludeUnion);
        }
        
        if (result == null) {
            result = new RoaringBitmap();
        }
        
        long calculateTime = System.currentTimeMillis() - startTime;
        
        log.info("复杂标签圈选完成，最终人群数量: {}，耗时: {} ms", 
            result.getCardinality(), calculateTime);
        
        return new CrowdSelectionResult(result, result.getCardinality(), calculateTime);
    }
    
    /**
     * 从圈选结果提取用户ID列表
     * 
     * @param result 圈选结果
     * @param limit 限制返回数量
     * @return 用户ID列表
     */
    public List&lt;Long&gt; extractUserIds(CrowdSelectionResult result, int limit) {
        List&lt;Long&gt; userIds = new ArrayList<>();
        
        IntIterator iterator = result.getBitmap().getIntIterator();
        int count = 0;
        
        while (iterator.hasNext() && count < limit) {
            int userId = iterator.next();
            userIds.add((long) userId); // 转换回long类型的雪花ID
            count++;
        }
        
        log.info("提取用户ID完成，实际返回数量: {}", userIds.size());
        return userIds;
    }
    
    /**
     * 批量从Redis加载RoaringBitmap
     */
    private List&lt;RoaringBitmap&gt; loadBitmapsFromRedis(List&lt;String&gt; tagIds) {
        List&lt;RoaringBitmap&gt; bitmaps = new ArrayList<>();
        
        // 构建Redis键列表
        List&lt;String&gt; redisKeys = tagIds.stream()
            .map(this::buildTagKey)
            .collect(Collectors.toList());
        
        // 批量获取序列化数据
        List&lt;byte[]&gt; serializedBitmaps = redisTemplate.opsForValue().multiGet(redisKeys);
        
        // 反序列化
        for (int i = 0; i < serializedBitmaps.size(); i++) {
            byte[] data = serializedBitmaps.get(i);
            if (data != null) {
                try {
                    RoaringBitmap bitmap = deserializeRoaringBitmap(data);
                    bitmaps.add(bitmap);
                } catch (IOException e) {
                    log.error("反序列化标签 {} 失败", tagIds.get(i), e);
                }
            } else {
                log.warn("标签 {} 在Redis中不存在", tagIds.get(i));
            }
        }
        
        return bitmaps;
    }
    
    /**
     * RoaringBitmap序列化
     */
    private byte[] serializeRoaringBitmap(RoaringBitmap bitmap) throws IOException {
        ByteArrayOutputStream baos = new ByteArrayOutputStream();
        DataOutputStream dos = new DataOutputStream(baos);
        bitmap.serialize(dos);
        dos.close();
        return baos.toByteArray();
    }
    
    /**
     * RoaringBitmap反序列化
     */
    private RoaringBitmap deserializeRoaringBitmap(byte[] data) throws IOException {
        ByteArrayInputStream bais = new ByteArrayInputStream(data);
        DataInputStream dis = new DataInputStream(bais);
        RoaringBitmap bitmap = new RoaringBitmap();
        bitmap.deserialize(dis);
        dis.close();
        return bitmap;
    }
    
    /**
     * 构建标签Redis键
     */
    private String buildTagKey(String tagId) {
        return "customer_tag:" + tagId;
    }
    
    /**
     * 计算压缩比
     */
    private String calculateCompressionRatio(int userCount, int compressedSize) {
        int uncompressedSize = userCount * 4; // 每个int 4字节
        double ratio = (double) compressedSize / uncompressedSize * 100;
        return String.format("%.2f%%", ratio);
    }
}

/**
 * 人群圈选结果封装
 */
@Data
@AllArgsConstructor
public class CrowdSelectionResult {
    private RoaringBitmap bitmap;        // 结果位图
    private long crowdCount;             // 人群数量
    private long calculateTimeMs;        // 计算耗时
    
    /**
     * 获取压缩效果信息
     */
    public String getCompressionInfo() {
        long compressedSize = bitmap.getSizeInBytes();
        long uncompressedSize = crowdCount * 4; // 每个用户ID 4字节
        double compressionRatio = (double) compressedSize / uncompressedSize * 100;
        
        return String.format("压缩前: %d bytes, 压缩后: %d bytes, 压缩比: %.2f%%", 
            uncompressedSize, compressedSize, compressionRatio);
    }
    
    /**
     * 检查是否为空结果
     */
    public boolean isEmpty() {
        return bitmap.isEmpty();
    }
}

2.3 用户ID映射策略的最终方案

面试官：你们是如何解决用户ID与Bitmap位映射的问题的？

回答要点：
经过技术调研，我们最终采用了RoaringBitmap直接存储用户ID的方案，完全避免了映射问题：

/**
 * 用户ID映射问题的解决方案演进
 */
public class UserIdMappingSolution {
    
    /**
     * 方案演进过程说明
     */
    public void explainSolutionEvolution() {
        
        // ❌ 方案1：传统Bitmap直接存储雪花ID
        // 问题：雪花ID如1234567890123456789，会导致需要分配巨大的位图空间
        
        // ❌ 方案2：维护userId -> index映射表
        // 问题：需要额外的映射表，增加系统复杂度和维护成本
        
        // ✅ 方案3：RoaringBitmap直接存储（最终采用）
        // 优势：
        // 1. 直接存储原始用户ID，无需映射
        // 2. 自动压缩稀疏数据，空间利用率极高
        // 3. 结果直接就是原始用户ID，无需反查
        
        RoaringBitmap userBitmap = new RoaringBitmap();
        
        // 直接添加雪花ID
        userBitmap.add(1234567890); // 雪花ID
        userBitmap.add(1234567891);
        userBitmap.add(1234567892);
        
        // 圈选结果直接遍历出原始ID
        userBitmap.forEach(userId -> {
            System.out.println("圈选到用户: " + userId);
            // 直接就是原始的雪花ID，无需任何转换
        });
        
        System.out.println("存储大小: " + userBitmap.getSizeInBytes() + " bytes");
        System.out.println("用户数量: " + userBitmap.getCardinality());
    }
}

三、性能优化与实际效果

3.1 性能对比数据

指标传统MySQL方案Redis Set方案RoaringBitmap方案
存储空间1GB+500MB50MB
查询响应时间30-60秒5-10秒100-500毫秒
并发支持100 QPS1000 QPS5000+ QPS
复杂查询不支持有限支持完全支持

3.2 实际业务效果

/**
 * 性能监控和统计
 */
@Component
public class BitmapPerformanceMonitor {
    
    private final MeterRegistry meterRegistry;
    
    /**
     * 记录实际业务数据
     */
    @EventListener
    public void recordBusinessMetrics(CrowdSelectionEvent event) {
        
        // 记录查询性能
        Timer.Sample sample = Timer.start(meterRegistry);
        sample.stop(Timer.builder("crowd.selection.time")
            .tag("tag_count", String.valueOf(event.getTagCount()))
            .register(meterRegistry));
        
        // 记录压缩效果
        Gauge.builder("bitmap.compression.ratio")
            .tag("tag_id", event.getTagId())
            .register(meterRegistry, event, e -> e.getCompressionRatio());
        
        log.info("业务指标记录 - 标签数: {}, 人群数: {}, 耗时: {}ms, 压缩比: {}%",
            event.getTagCount(), event.getCrowdCount(), 
            event.getCalculateTime(), event.getCompressionRatio());
    }
}

四、面试常见问题深度解答

Q1: RoaringBitmap如何处理超大整数？

技术深度回答：
RoaringBitmap通过分块机制处理大整数：

  1. 分块策略：将32位整数空间分为65536个块，每个块处理65536个连续整数
  2. 稀疏优化：只为有数据的块分配存储空间，未使用的块完全不占内存
  3. 容器自适应：每个块根据数据密度自动选择最优存储方式
// 示例：雪花ID 1234567890 的存储过程
long snowflakeId = 1234567890L;
int blockId = (int) (snowflakeId >>> 16);  // 块号: 18838
int offset = (int) (snowflakeId & 0xFFFF); // 偏移: 722

// RoaringBitmap只会为第18838号块分配空间
// 其他未使用的块完全不占内存

Q2: 与Redis Bitmap相比有什么优势？

对比分析：

维度Redis BitmapRoaringBitmap
稀疏数据处理空间浪费严重极致压缩
大整数支持需要巨大内存自动分块处理
序列化传输需要传输整个位图只传输有数据的部分
内存使用按最大ID分配按实际数据分配

Q3: 如何保证分布式环境下的数据一致性？

解决方案：

  1. 写入策略：先更新MySQL主数据，再异步同步到Redis
  2. 版本控制：每个RoaringBitmap带时间戳版本号
  3. 缓存失效：数据更新时主动清理相关缓存
  4. 最终一致性：通过消息队列保证最终数据一致

Q4: 系统如何支撑高并发查询？

高并发优化策略：

  1. 读写分离：查询走Redis，更新走MySQL
  2. 本地缓存：热点数据缓存到应用本地
  3. 异步计算：复杂查询异步处理，先返回预估结果
  4. 连接池优化：Redis连接池参数调优

五、项目亮点与个人成长

技术创新点

  1. 直接存储方案：避免了复杂的ID映射，简化了系统架构
  2. 压缩算法应用：深入理解RoaringBitmap的压缩原理，实现极致的空间优化
  3. 序列化优化：自定义序列化策略，减少网络传输开销
  4. 性能监控：建立完整的性能监控体系，实时掌握系统状态

业务价值

  1. 响应速度提升：人群圈选从分钟级优化到毫秒级，提升用户体验
  2. 成本大幅降低：存储成本降低95%，服务器资源节省80%
  3. 业务能力增强：支持更复杂的营销策略，转化率提升40%
  4. 系统稳定性：99.9%可用性，支撑日均千万级查询

个人技术成长

  1. 深度学习能力：从不了解到深入掌握RoaringBitmap底层原理
  2. 架构设计能力：学会从业务需求出发选择最适合的技术方案
  3. 性能优化能力：掌握了大规模数据处理的优化技巧
  4. 问题解决能力：在技术选型过程中，学会了系统性地分析和解决问题

本文档记录了获客项目中RoaringBitmap技术的完整应用过程，从初期的技术调研到最终方案的确定，展现了一个完整的技术学习和应用过程。

util6 knowledge hub
Copyright © 2026 util6