并查集

引言

• 在AB测试中，确保用户的一致性和唯一性是获得准确结果的关键。然而，在非强制登录的Web项目中，用户的唯一标识可能会因退出、登录、切换浏览器等行为而发生变化。这可能导致同一个用户被误认为是多个不同的用户，进而影响实验结果的准确性。本文将探讨如何解决这一问题，以提高AB测试的有效性。

问题描述

• 在Web应用中，如果简单地使用后端生成的用户token作为唯一用户标识，可能会遇到以下问题：用户在登录前后或退出登录时，会获取新的token。如果以token作为实验分流的唯一属性，可能会导致实验结果不准确。

具体原因

1. 用户token变化：用户在登录前后或退出登录时，token会发生变化。如果仅依赖token作为唯一标识，同一个用户在不同状态下会被视为不同的用户。
2. 前端尝试策略：前端生成一个唯一的客户端标识（client_id），并将其存储在cookie中。只要用户不清除浏览器缓存，无论登录状态如何变化，都能通过client_id唯一标识用户。但考虑到用户可能
3. 后端订单创建：后端在创建订单时，使用token作为用户标识。前端的client_id与订单业务没有直接关联，导致token与client_id之间的关联缺失。

• 由于存在用户token会变化的问题，那么这里前端采取的策略是生成一个唯一的客户端标识，存到cookie里，只要用户不清除浏览器缓存，无论登录状态变化与否，都能唯一标识用户。

• 但是后端在创建订单的时候，是获取token作为用户标识的，前端的客户端标识与订单业务没有任何关联，那我们需要将用户的token关联起来。

• 实验记录表（experiment_record）结构如下

id	主键
user_id	用户的唯一标识
client_id	用户的客户端id，会随着不同浏览器变化
feature_value	触发实验的值
…	其余属性

• 订单表（order）结构如下

id	主键
order_id	订单id
user_id	用户的唯一标识
amount	金额
…	其余属性

• 实验触发流程如下
  1. 首次进入网站，获取了一个未登录状态的token，触发了实验 -> 向实验记录表中插入了一条记录

  INSERT INTO experiment_record (user_id, client_id, feature_value) VALUES (5120, 9527, "cyan");

  2. 用户登录，系统会为该用户分配一个新的token，但是客户端标识没有变，触发了实验 -> 向实验记录表中插入了一条记录

  INSERT INTO experiment_record (user_id, client_id, feature_value) VALUES (5210, 9527, "cyan");

  • 当然这里会存在feature_value不同的情况，对于相同用户看到了不同的实验变体的数据，我们在分析的时候需要排除掉。
  3. 同时这个人在登录状态下提交了一个订单，那么订单表中只会有1条记录

  INSERT INTO order (order_id, user_id, amount) VALUES (123456, 5210, 100);

  4. 此时实验数据表中就会有2个token，但是其实是同一个人，计算转化率时，就会有误差。

分析与解决方案

• 为了最小化这种误差，这里考虑了一种轻量级的方法来关联同一用户的前后token。具体来说，我们引入了一张新的数据库表，用于记录用户的token变化情况。每当用户登录或登出时，我们会在这个表中添加一条记录，包含旧token、新token，以及变化的时间戳。
• 一个简单的表（token_changes）结构如下：

id	主键
old_user_id	表示未登录状态下的token
new_user_id	表示登录后的token
change_time	记录token变化的时间

数据处理逻辑

• 接下来，我们需要确保所有涉及用户行为的数据（如订单、实验参与等）都能正确地反映用户的身份一致性。
• 为此，我们需要先根据token_changes中的数据来建立并查集，划分出一个个集合。随后遍历实验数据表和订单表中的user_id，若在并查集中，则更新为根节点的值，保证所有相关联的token都指向同一个用户。

并查集

public class UnionFindUtils {
    public static final Map<String, String> parent = new HashMap<>(); // 记录每个token的父节点
    public static final Map<String, Integer> rank = new HashMap<>(); // 记录每个token的秩（树的高度）

    // Find操作：找到某个token的根节点，并路径压缩
    public static String find(String token) {
        // 如果token不在parent中，初始化自己为自己的父节点
        parent.putIfAbsent(token, token);
        rank.putIfAbsent(token, 1);

        // 路径压缩
        if (!parent.get(token).equals(token)) {
            parent.put(token, find(parent.get(token))); // 递归压缩路径
        }
        return parent.get(token);
    }

    // Union操作：合并两个token所在的集合
    public static void union(String token1, String token2) {
        String root1 = find(token1);
        String root2 = find(token2);

        // 如果两个根节点不同，合并集合
        if (!root1.equals(root2)) {
            int rank1 = rank.getOrDefault(root1, 1);
            int rank2 = rank.getOrDefault(root2, 1);

            // 按秩合并
            if (rank1 > rank2) {
                parent.put(root2, root1);
            } else if (rank1 < rank2) {
                parent.put(root1, root2);
            } else {
                parent.put(root2, root1);
                rank.put(root1, rank1 + 1); // 增加高度
            }
        }
    }

    // 判断两个token是否属于同一集合
    public static boolean isConnected(String token1, String token2) {
        return find(token1).equals(find(token2));
    }

    public static List<List<String>> getGroupResult() {
        // Map用于存储每个根节点对应的集合
        Map<String, List<String>> groups = new HashMap<>();

        // 遍历所有的元素，将它们归类到对应的根节点集合中
        for (String token : parent.keySet()) {
            String root = find(token); // 找到当前元素的根节点
            groups.computeIfAbsent(root, k -> new ArrayList<>()).add(token);
        }
        ArrayList<List<String>> resList = new ArrayList<>();
        // 打印结果
        for (Map.Entry<String, List<String>> entry : groups.entrySet()) {
            resList.add(entry.getValue());
        }
        return resList;
    }

    public static void main(String[] args) {

        UnionFindUtils.union("token1", "token2"); // token1 -> token2
        UnionFindUtils.union("token3", "token2"); // token2 -> token3
        UnionFindUtils.union("token4", "token5"); // token4 -> token5
        UnionFindUtils.union("token6", "token7"); // token6 -> token7

        // 测试查找
        System.out.println("token1的根节点: " + UnionFindUtils.find("token1"));
        System.out.println("token4的根节点: " + UnionFindUtils.find("token4"));

        // 测试是否连接
        System.out.println("token1和token3是否连接: " + UnionFindUtils.isConnected("token1", "token3"));
        System.out.println("token1和token4是否连接: " + UnionFindUtils.isConnected("token1", "token4"));

        // 打印集合个数及每个集合的元素
        System.out.println(UnionFindUtils.getGroupResult());
    }
}

业务实现

public void unionFind() {
    // 清空experimentTempInfo
    experimentTempInfoMapper.delete(Wrappers.lambdaQuery(ExperimentTempInfo.class));
    // 清空tempTorderInfo
    tempOrderMapper.delete(Wrappers.lambdaQuery(TempTorder.class));

    List<TokenChanges> changesList = tokenChangesMapper.selectList(Wrappers.lambdaQuery(TokenChanges.class));
    for (TokenChanges changes : changesList) {
        String oldUserId = changes.getOldUserId();
        String newUserId = changes.getNewUserId();
        UnionFindUtils.union(oldUserId, newUserId);
    }
    List<ExperimentInfo> experimentInfoList = experimentInfoMapper.selectList(Wrappers.lambdaQuery(ExperimentInfo.class).eq(ExperimentInfo::getFeatureId, "course-more-info-status"));
    for (ExperimentInfo experimentInfo : experimentInfoList) {
        String userId = experimentInfo.getUserId();
        String rootId = UnionFindUtils.find(userId);
        ExperimentTempInfo tempInfo = new ExperimentTempInfo();
        BeanUtils.copyProperties(experimentInfo, tempInfo);
        tempInfo.setUserId(rootId);
        experimentTempInfoMapper.insert(tempInfo);
    }

    List<Torder> courseOrderList = orderMapper.selectList(Wrappers.lambdaQuery(Torder.class).eq(Torder::getPolishType, Common.POLISH_TYPE_WITH_COURSE_PAPER));
    for (Torder torder : courseOrderList) {
        TempTorder tempTorder = new TempTorder();
        String userId = torder.getToken();
        String rootId = UnionFindUtils.find(userId);
        BeanUtils.copyProperties(torder, tempTorder);
        tempTorder.setToken(rootId);
        tempOrderMapper.insert(tempTorder);
    }
}

结果与结论

• 通过上述方法，我们可以显著降低由于用户身份变化而导致的AB测试误差。此方案不仅简单易行，而且有效地提高了实验结果的可靠性。同时，它也证明了即使是在没有强制登录的情况下，也可以通过合理的设计和技术手段保持用户的一致性和唯一性。