使用Bloom Filter高效管理游戏活动推送

背景信息

在现代的游戏运营中，游戏开发者和运营团队常常会推出各种的活动以提高用户的活跃度、参与度或付费率。通常以弹窗、站内信、NPC任务等形式将活动推送给玩家。然而，在一个复杂的游戏环境中，开发者需要确保这些活动信息的发送频率能够被控制，并避免重复推送相同信息而带来用户体验下降的问题，同时又需要保持整个系统的高效性。

在上述场景中，使用Bloom Filter数据结构是一种高效的解决方案，可以高效地实现对弹窗的重复控制。Bloom Filter是一种空间效率极高的概率型数据结构，用于判断某个元素是否在集合中。它可以很快地返回某个元素可能在集合中或者一定不在集合中，优点是具有较低的空间复杂度和查询时间复杂度，适合处理大量数据的场景，缺点是可能存在误判（在该场景中，误判为漏推送给某用户，不会重复推送）。

在该场景中使用Bloom Filter的优势：

• 高效性：由于Bloom Filter使用的是位数组，操作极为快速，并且其空间复杂度较低，非常适合存储大量的用户数据。

• 低内存占用：与传统的集合结构相比，Bloom Filter占用的空间要少得多，尤其在存储数百万个玩家的弹窗状态时，这一优势更加明显。

• 可扩展性：由于Bloom Filter的扩展性非常好，它适用于大规模的分布式场景，比如Redis集群。

Tair（企业版）提供的Bloom数据结构兼容Redis Bloom Filter数据结构，使用方式也与Redis Bloom Filter一致。

方案概述

以下为示例代码的概述，具体实现请参见下方的示例代码。

1. 连接Tair（企业版）实例。

2. 创建名为activity_popup的Bloom Filter数据结构，具体实现可参见示例代码中的createBloom函数。

   本示例创建Bloom Filter预计存储50000个元素，误判率设置为1%（即0.01）。

   误判率设置建议

   在使用Bloom Filter时，误判率是一个关键设计决策，误判是指错误地认为某个不在集合中的元素是存在的。误判率越低，过滤器的准确性越高，但占用的内存空间也越大。因此设置误判率需要在精度和内存空间之间做权衡，误判率的设置建议如下：

   • 低误判率（如0.01%）：如果业务场景对误判率非常敏感，如安全系统、金融系统等，则应该选择非常低的误判率（如 0.01% 或更低），但这会增加内存的开销。

   • 中误判率（如0.1%到1%）：对大多数场景来说，这个误判率是合理的折中方案。既能保持较好的内存使用效率，又能保证较低的误判率。

   • 高误判率（如1% 以上）：在对准确性要求较低的场景（如缓存预热、推荐系统等），可以选择1%甚至更高的误判率。这种情况下，内存需求较低，但误判率较高。

3. 当玩家登录时，打算向该玩家进行推送，具体实现可参见示例代码中的handlePopup函数。

   但推送前需要先检查是否需要推送，具体实现可参见示例代码中的shouldShowPopup函数。

   • 若玩家ID不在Bloom Filter中，表示未进行推送，此时需要向该玩家推送，并更新玩家的推送状态（updatePopupState函数）。

   • 若玩家ID已在Bloom Filter中，表示可能已推送，则不进行推送。

示例代码

Jedis的依赖如下：

<dependency>
    <groupId>redis.clients</groupId>
    <artifactId>jedis</artifactId>
    <version>5.1.0</version>
</dependency>

完整代码示例如下：

import redis.clients.jedis.*;
import redis.clients.jedis.UnifiedJedis;


public class TairBloomFilterDemo {
    static HostAndPort hostAndPort = new HostAndPort("r-bp1y****svonly41srpd.redis.rds.aliyuncs.com", 6379);  // 您可以在控制台获取实例连接地址与端口号。
    static JedisClientConfig config = DefaultJedisClientConfig.builder().password("tw:Da***3").build(); // 实例账号密码。
    static UnifiedJedis unifiedJedis = new UnifiedJedis(hostAndPort, config);
    private static final String BLOOM_KEY = "activity_popup";

    /**
    * 创建一个Bloom Filter Key。
    */
    public static void createBloom() {
        try {
            unifiedJedis.bfReserve(BLOOM_KEY, 0.01, 50000);
        } catch (Exception e) {
            e.printStackTrace(); // 超时等异常情况
        }
    }

    /**
    * 查询Bloom Filter中是否已经存在指定的玩家ID。
    */
    public static boolean shouldShowPopup(String playerId) {
        try {
            return !unifiedJedis.bfExists(BLOOM_KEY, playerId);
        } catch (Exception e) {
            e.printStackTrace(); // 超时等异常情况
            return true;
        }
    }

    /**
    * 将玩家ID添加到Bloom Filter Key中。
    */
    public static void updatePopupState(String playerId) {
        try {
            unifiedJedis.bfAdd(BLOOM_KEY, playerId);
        } catch (Exception e) {
            e.printStackTrace(); // 超时等异常情况。
        }
    }

    /**
    * 向指定玩家ID进行推送。
    */
    public static void handlePopup(String playerId) {
        if (shouldShowPopup(playerId)) {
            // 进行推送。
            System.out.println("推送给玩家: " + playerId);
            // 更新推送状态。
            updatePopupState(playerId);
        } else {
            System.out.println("玩家 " + playerId + " 已推送过");
        }
    }

    public static void main(String[] args) {
        createBloom();
        // 假设玩家ID为player123。
        String playerId = "player123";

        // 第一次调用时，应该推送。
        handlePopup(playerId);

        // 第二次调用时，不应该再推送。
        handlePopup(playerId);
    }
}

本示例的正确执行结果如下：

推送给玩家: player123
玩家 player123 已推送过