面经策

如何快速定位到五分钟内重复登录了两次的 QQ 号，用什么数据结构？ ​

  • 标签：后端、场景题

🏛 业务架构师 ​

"5 分钟内重复登录两次的 QQ 号"——这是实时风控的特征计算问题（异地登录提醒、撞库检测的底层特征）。我给从轻到重的三种数据结构方案，并按业务量级分档。

方案一：Redis ZSet 滑动窗口（面试标准答案）

ZADD login:{qq} <loginTime> <loginId>
ZREMRANGEBYSCORE login:{qq} 0 <now-300>   # 清理窗口外
ZCARD login:{qq} >= 2 → 命中

每个用户一个 ZSet，成员是登录记录，score 是时间戳。窗口语义精确，O(logN)。

方案二：Bitmap 按分钟分桶（海量用户更省）

login:202610241930 → QQ号对应bit置1
查询: 5个分钟桶的bit做AND/计数

每天 1440 个 key，空间 = 用户数 × 1440 bit，亿级用户约 17GB——适合全量扫描型分析，不适合单用户点查，但做"全量找异常账号"的批处理极佳。

方案三：Flink 实时计算（平台级方案）

登录事件流 → 按 QQ 号 KeyBy → 5 分钟滑动窗口 → 窗口内 count ≥ 2 输出到风控特征库。亿级登录日志、秒级检测时效的正规军方案，特征直接喂规则引擎（连续失败 + 异地 = 撞库告警）。

量级分档（架构师视角）

  • 日登录千万以内：Redis ZSet 足够，成本百元级
  • 亿级用户 + 多特征组合（IP 变化、设备变化、失败次数）：必须流计算 + 特征平台，此时**"重复登录"只是几十个风控特征之一**，单点方案没有意义

业务收尾：特征计算的产出要接到动作才有价值：二次验证（短信）、限制登录、告警通知——漏报的代价（盗号）和误报的代价（正常用户被打扰）要平衡，阈值靠运营数据调优而非拍脑袋。

🏗 系统架构师 ​

这题的关键词是"五分钟内"的时间窗口判定，我给三个层次：数据结构、精确解、工程化解法。

1. 直觉方案：HashMap + 双端队列 每个 QQ 号维护最近两次登录时间。新登录进来：

  • 查 HashMap，无记录则存入
  • 有记录：本次时间 - 上次时间 < 300s → 命中，输出；否则更新 追问"内存放不下怎么办"就引出下面的方案。

2. 流式 + Redis（工程首选） 海量 QQ 号、分布式部署，用 Redis：

text
SET login:last2:{qq} <t1,t2>  -- 或用 Hash 存最近两次时间
新登录：r = GET key
若 r 存在且 now - max(r) < 300 → 告警
EXPIRE key 300s               -- 窗口过期自动清理

用 ZSet 更优：ZADD login:{qq} now loginId，先 ZREMRANGEBYSCORE 清掉 300s 前的记录，ZCARD >= 2 即五分钟内登录了两次。TTL 保证只存"活跃窗口内"的账号，内存与活跃用户数成正比而不是全量用户。

3. 海量离线判定：位图/分桶 + 滚动时间窗 如果是离线日志分析（一天 N 亿条），按分钟分桶：每分钟一个 set/bitmap 记录该分钟登录的 QQ，检查"当前分钟与之前 4 分钟的并集"中出现的重复账号——滑动窗口用 5 个桶循环复用，空间 O(活跃账号数 × 5)。重复判定用 bitmap：第i分钟 bitmap 做按位 AND 找交集，Roaring Bitmap 压缩后单机可扛亿级。

答题要点：先给 HashMap+时间戳的朴素解，主动升级到"Redis ZSet + TTL"的工程解，海量离线场景再给分钟级 bitmap 滚动窗口——三层递进展示从数据结构到架构的完整思维。

💻 全栈开发专家 ​

"五分钟内登录两次"是滑动窗口判定，我的首选数据结构是 Redis ZSet。

方案：ZSet 滑动窗口

每次登录把时间戳写进 zset，同时清理窗口外的旧记录，再数窗口内次数：

bash
# login 事件
ZADD login:{qq} <now_ts> <loginId>          # score=时间戳
ZREMRANGEBYSCORE login:{qq} 0 <now_ts-300>  # 清理5分钟前
ZCARD login:{qq}                            # >= 2 则命中
EXPIRE login:{qq} 600                       # 兜底过期，防内存泄漏
java
public boolean isDupLogin(String qq) {
    String key = "login:" + qq;
    long now = System.currentTimeMillis() / 1000;
    redisTemplate.opsForZSet().add(key, UUID.randomUUID().toString(), now);
    redisTemplate.opsForZSet().removeRangeByScore(key, 0, now - 300);
    Long cnt = redisTemplate.opsForZSet().zCard(key);
    redisTemplate.expire(key, 600, TimeUnit.SECONDS);
    return cnt != null && cnt >= 2;
}

为什么是 ZSet

  • score 有序，ZREMRANGEBYSCORE O(logN) 精确裁剪窗口，比"分钟分桶计数"精确（分桶法跨桶边界会漏判）。
  • 一个 key 承载一个用户的完整登录历史，天然分布式。

海量用户的变体

如果是离线批处理找"所有重复登录的 QQ 号"（面试常见的反问），用双指针/差分：所有 (qq, timestamp) 事件按 qq+时间排序，同一 qq 相邻两次登录间隔 < 300s 即命中；十亿级放 Spark/Flink 窗口聚合（SESSION WINDOW gap 5min），数据结构退化为排序 + 滑窗比较。

坑：loginId 必须唯一成员（用事件 ID 而不是固定值），否则同秒多次登录会被 zset 去重漏判。