某音在海量数据场景下的点赞去重解决方案：

布隆过滤器的应用

背景

在像某音这样的大型社交媒体平台上，每天都会产生海量的用户行为数据，如点赞、评论、分享等。对于点赞功能，平台需要高效地处理用户的点赞请求，并且确保同一用户对同一内容只能点赞一次，以防止重复点赞导致数据异常。

挑战

高并发：每天有数亿用户同时在线，产生的点赞请求量巨大。
去重需求：需要高效地判断用户是否已经对某个内容点赞过，避免重复计数。
性能和存储：传统的存储和查询方式在这种规模下可能导致性能瓶颈和高昂的存储成本。

布隆过滤器的应用

为了解决上述挑战，某音可以使用布隆过滤器（Bloom Filter）来实现点赞去重功能。布隆过滤器是一种空间效率高、支持快速判断元素是否存在的数据结构，适合于海量数据的去重和判重。

布隆过滤器简介

原理：布隆过滤器由一个位数组和一组哈希函数组成。当一个元素被添加到过滤器时，通过多个哈希函数对其进行哈希，得到对应的位数组索引，将这些位置设为1。
判断存在性：要判断一个元素是否存在，只需通过同样的哈希函数检查对应的位数组位置是否都为1。
特点：
- 空间效率高：相比于传统的哈希表，布隆过滤器占用的空间更少。
- 允许一定的误判率：可能会出现假阳性，即元素实际上不存在，但布隆过滤器判断其存在。

在点赞去重中的应用

初始化布隆过滤器：
- 为每个热门内容（如视频）创建一个布隆过滤器，或者使用全局的布隆过滤器。
- 根据预期的用户数量和可接受的误判率，设置位数组的大小和哈希函数的数量。
用户点赞操作：
- 当用户对某个内容点赞时，首先使用布隆过滤器判断该用户是否已经点赞过。
- 判重流程：
  - 使用用户ID和内容ID的组合作为输入，经过多个哈希函数，检查对应的位是否都为1。
  - 如果有任何一位为0，表示用户尚未点赞，可以进行点赞操作。
  - 如果所有位都为1，可能用户已经点赞过，需要进一步确认（因为存在误判的可能）。
处理误判：
- 进一步验证：由于布隆过滤器可能产生误判，对于判定已点赞的情况，可以进一步查询数据库或缓存进行确认。
- 接受误判：在某些情况下，可以接受少量的误判，以换取性能的提升。
更新布隆过滤器：
- 如果确认用户尚未点赞过，进行点赞操作后，需要将用户ID和内容ID的组合添加到布隆过滤器中，更新相应的位。

优势

高性能：布隆过滤器只需进行哈希计算和位数组访问，速度非常快，适合高并发场景。
节省空间：相比存储所有用户点赞记录，布隆过滤器占用的内存更少。
扩展性好：可以根据需要调整位数组的大小和哈希函数的数量，以控制误判率。

实际案例中的考虑

误判率控制：需要根据业务需求选择合适的误判率。对于点赞功能，可能允许一定的误判，因为重复点赞通常不会造成严重后果。
多级缓存策略：结合布隆过滤器和缓存（如Redis）使用。先通过布隆过滤器快速过滤，再通过缓存或数据库进行精确判断。
分布式部署：在分布式环境中，需要考虑布隆过滤器的同步和一致性问题。可以使用分布式布隆过滤器，或者对数据进行分片处理。

示例代码

以下是一个简化的布隆过滤器示例

import java.util.BitSet;
import java.util.Random;

public class BloomFilter {
    private static final int DEFAULT_SIZE = 1 << 24; // 位数组大小
    private static final int[] seeds = new int[]{5, 7, 11, 13, 31, 37, 61}; // 哈希函数种子
    private BitSet bitSet = new BitSet(DEFAULT_SIZE);
    private HashFunction[] functions = new HashFunction[seeds.length];

    public BloomFilter() {
        for (int i = 0; i < seeds.length; i++) {
            functions[i] = new HashFunction(DEFAULT_SIZE, seeds[i]);
        }
    }

    // 添加元素
    public void add(String value) {
        for (HashFunction f : functions) {
            bitSet.set(f.hash(value), true);
        }
    }

    // 判断是否存在
    public boolean contains(String value) {
        if (value == null) return false;
        boolean ret = true;
        for (HashFunction f : functions) {
            ret = ret && bitSet.get(f.hash(value));
        }
        return ret;
    }

    // 哈希函数内部类
    public static class HashFunction {
        private int size;
        private int seed;

        public HashFunction(int cap, int seed) {
            this.size = cap - 1;
            this.seed = seed;
        }

        // 简单的哈希函数
        public int hash(String value) {
            int result = 0;
            int len = value.length();
            for (int i = 0; i < len; i++) {
                result = seed * result + value.charAt(i);
            }
            return (size & result);
        }
    }

    // 测试示例
    public static void main(String[] args) {
        BloomFilter filter = new BloomFilter();
        String userId = "user123";
        String contentId = "video456";
        String key = userId + "_" + contentId;

        if (!filter.contains(key)) {
            // 用户尚未点赞，可以进行点赞操作
            System.out.println("用户未点赞，执行点赞操作");
            filter.add(key);
        } else {
            // 用户可能已点赞，需要进一步确认
            System.out.println("用户可能已点赞，拒绝重复点赞");
        }
    }
}

注意事项

布隆过滤器的清理：由于布隆过滤器不能删除元素，随着时间推移，误判率会增加。需要定期重建或采用分段布隆过滤器。
持久化和同步：在分布式系统中，需要考虑布隆过滤器的数据持久化和节点间的同步。
与其他技术结合：布隆过滤器通常与缓存、数据库等其他技术结合使用，以实现更准确和高效的判重。

为什么选择布隆过滤器？

1. 空间效率高

位数组实现：布隆过滤器使用位数组来存储数据，占用空间远小于存储完整元素的信息。
可控的误判率：通过调整位数组的大小和哈希函数的数量，可以在空间和误判率之间找到平衡。

2. 查询和插入效率高

时间复杂度：查询和插入操作的时间复杂度为 O(k)，其中 k 为哈希函数的数量，通常是常数级别，性能高效。
无锁并发：位数组的特性允许一定程度的无锁并发操作，提高了在高并发场景下的性能。

3. 适用于海量数据

扩展性好：布隆过滤器适合处理海量数据的判重需求，能够在有限的内存中处理非常大的数据集。

不同数据量级的去重解决方案

其他去重方案

1. 哈希表（Hash Table）

特点：使用键值对存储数据，可以快速查询元素是否存在。
局限性：与 Set 类似，内存消耗大，不适合海量数据场景。

2. 数据库索引

特点：利用关系型数据库或 NoSQL 数据库的索引功能进行去重。
局限性：数据库的读写性能和扩展性在高并发、海量数据场景下可能成为瓶颈。

3. Redis 的位图（Bitmap）

特点：使用位图来表示某个键是否存在，占用空间小，操作高效。
应用：适用于需要对大量连续整数进行标记的场景，如用户 ID 连续的情况。
局限性：当键值不连续或范围过大时，位图的实现复杂度和空间需求增加。

4. 计数布隆过滤器（Counting Bloom Filter）

特点：在布隆过滤器的基础上，使用计数器数组，支持元素的删除操作。
应用：适用于需要动态添加和删除元素的场景。
局限性：相比布隆过滤器，空间占用更大，复杂度更高。

5. HyperLogLog

特点：一种用于基数估计的概率算法，能够在固定的空间内估计集合的基数（去重后的元素数量）。
应用：适用于统计不重复元素的数量，而非具体判断某个元素是否存在。

不同数据量级对应的解决方案

1. 小规模数据

方案选择：Set、HashMap 等简单的数据结构。
特点：实现简单，内存消耗可控，适合数据量较小的场景。
应用场景：小型应用、开发测试环境。

2. 中等规模数据

方案选择：Redis 的 Set、Bitmap。
特点：Redis 提供了高性能的内存存储，支持丰富的数据结构，适合中等规模的数据去重。
应用场景：中型应用、实时性要求较高的业务。

3. 大规模数据

方案选择：布隆过滤器、分布式缓存、分片数据库。
特点：
- 布隆过滤器：在有限内存内处理海量数据，允许可控的误判率。
- 分布式缓存：如使用 Redis Cluster，将数据分布到多个节点。
- 分片数据库：将数据分散到多个数据库实例，降低单个节点的压力。
应用场景：大型互联网应用、高并发、高性能需求的业务。

4. 超大规模数据

方案选择：分布式布隆过滤器、Big Data 技术（如 Hadoop、Spark）。
特点：
- 分布式布隆过滤器：在分布式环境中部署布隆过滤器，处理超大规模的数据。
- Big Data 技术：利用分布式计算框架，处理批量去重和统计任务。
应用场景：超大型互联网平台、需要处理 PB 级数据的业务。

总结

为什么选择布隆过滤器：
- 空间效率高：在有限的内存中处理海量数据，避免了使用 Set 带来的高内存消耗。
- 性能高效：插入和查询操作快速，适合高并发场景。
- 可扩展性：可以根据业务需求调整参数，控制误判率和内存占用。
去重的其他选择：
- 基于内存的数据结构：如 Set、HashMap，适用于小规模数据。
- 缓存和数据库：利用 Redis、数据库索引等，适用于中等规模数据。
- 概率算法：如 HyperLogLog，适用于基数估计。
不同量级的解决方案：
- 小规模：简单数据结构，易于实现。
- 中等规模：引入缓存和优化的数据结构，提高性能。
- 大规模：使用布隆过滤器、分布式系统，应对海量数据。
- 超大规模：结合分布式计算框架，处理批量任务。

海量数据去重方案-布隆过滤器