qinghuan
← 黑马点评 / 全部笔记

单元 81 / 黑马点评

P1 · 重点提升L2 · 进阶

黑马点评:点赞、关注与滚动 Feed

先正确记录谁点过赞、关注了谁,再处理 Feed 的排序和翻页边界,避免重复计数或漏掉同一时间的内容。

本篇目录 · 按需要跳转

读完这篇,你能做什么

能验证点赞去重、共同关注和同一时间戳的 Feed 翻页,并说明游标限制。

学习理由、准备要求与知识点

为什么学它

互动功能适合练习集合和排序结构,也能暴露分页游标与并发新增之间的边界。

先读这些内容

知识点清单

  • ZSet 点赞
  • 成员去重
  • Set 关注关系
  • 共同关注
  • Feed 写扩散
  • 按分数逆序
  • 同分值偏移
  • 并发分页边界

运行前先确认完整算法使用 Java 17 标准库;JDK 源码基线为 OpenJDK 17 GA。示例是内存中的机制模型,外部服务接入需要另外配置和验证。

01先弄懂它是什么

点赞先是一条“谁给哪篇笔记点了赞”的关系,点赞数是据此计算或维护的结果。如果只存数字,就难以判断重试是否又加了一次,也无法回答当前用户是否点过。把用户 ID 放进 Set 或 Sorted Set,只有成员真的新增时才增加计数,取消时也按实际删除结果处理。

关注集合记录哪些关系存在,交集能找共同关注;Feed 列表则还要按顺序展示内容,目标不同。写扩散是在发布时把内容放进粉丝收件箱,读扩散是在用户打开页面时汇总关注作者的内容。粉丝极多的作者和普通作者可能需要不同安排,不能只根据 Redis 选了什么类型就决定整个方案。

滚动翻页时,要记清上一页读到了哪里。同一毫秒可能发布多篇笔记:下一页若排除这个时间,尚未读到的同时间笔记会漏掉;若全部包含,又会把读过的再取一次。教学中的办法是同时记下时间和这个时间内已读的条数,但并发插入同时间笔记仍可能改变条数位置。还可以用时间加 ID 明确先后边界,不过真实存储也必须支持相同的复合排序和查询。

文中这几个词,先认一认

成员身份
用稳定的用户 ID 或内容 ID 记录究竟是哪条关系,而不是只记关系总数。
复合游标
把决定排序的全部字段放进翻页位置,例如时间和编号,避免同一时间的多条数据难以区分。
写扩散
作者发布时就把内容索引送到接收者列表中,用更多写入换取之后更快读取。

还有陌生词?到术语小抄里看一个具体例子 ↗

02看看它怎么工作

本题先按时间从新到旧排,同一时间再按数字 ID 从大到小排,让不同笔记也能分清先后,这叫全序。游标同时保存上一页末条的时间和 ID。TreeSet 使用同一套比较规则建立索引;下一页只取严格排在这条笔记后面的内容,最多取 limit 条。这样同一时间的三篇笔记即使分在两页,也能继续从正确位置读取。

例如时间二千有ID一百零三、一百零二、一百零一,每页两条,第一页得到前两个,游标为二千和一百零二;下一页先返回一百零一,再进入更旧时间。只保存时间二千无法区分已读两个成员和尚未读的成员。

Java比较器按数字ID排序,Redis Sorted Set同分成员通常按字节字典序排序,二者不能直接等同。仅用时间作为score时,BYSCORE不能直接表达第二字段的任意复合比较,真实实现需同分处理、合适编码或支持复合索引的存储。算法针对冻结数据集,不保证动态增删后的快照一致性。

正在加载流程图…

图中状态只描述本篇可执行机制;业务调用仍需由外层应用负责。
查看流程图源码(Mermaid)
flowchart TD
  L["点赞成员变化"] --> C["派生计数与对账"]
  F["关注关系"] --> B["Feed投递或聚合"]
  B --> O["明确时间和同分排序"]
  O --> P["复合游标分页"]
  P --> D["授权详情与顺序恢复"]

按顺序看,每一步做了什么

  1. 以成员变化定义点赞和取消的幂等结果。
  2. 将关注关系与Feed排序索引分开。
  3. 明确同分排序与游标全部字段。
  4. 用同时间多条数据验证连续分页。
  5. 再评估写扩散、读扩散和并发变更的语义。

03对照实现代码

OpenJDK 17 TreeSet 源码 (新标签页)↗

OpenJDK 17 GA,jdk-17+35 · TreeSet.tailSet / iterator

下方为原创 Java 教学片段,调用已核验的 JDK API 说明局部机制;不是该类原样源码,不代表Redis或数据库内核实现。完整程序见算法模块。

核心机制代码 · java
NavigableSet<Post> remaining = cursor == null ? index : index.tailSet(cursor, false);
// false排除游标本身;方向由构造索引时的比较器决定。
Iterator<Post> iterator = remaining.iterator(); // 范围视图迭代,不复制整个Feed。
while (iterator.hasNext() && page.size() < limit) page.add(iterator.next());
// 视图依赖原集合,真实分页需要另外约定数据变更与快照版本。

TreeSet内部基于NavigableMap维护排序集合,tailSet返回按比较器意义的后半范围视图。比较器降序时,后半就是时间更旧或同时间ID更小的内容。

iterator遍历集合当前顺序,范围视图不是冻结快照。并发修改可能影响视图或触发快速失败,因此完整算法先构建只读数据集供顺序分页验证。

TreeSet 用比较器判断两项是否占同一个排序位置。若只比较时间,同一时刻的不同笔记就可能被当成重复。本题把 ID 也加入排序,并额外拒绝“同一 ID 却内容不同”的记录。

Java有序集合只是复合游标机制的桥梁,不是Redis Sorted Set源码。Redis分数字节排序、编码与命令边界仍需按官方文档实现和测试。

代码先调用谁,再调用谁

  1. 定义时间与ID全序
  2. 构建唯一内容索引
  3. 读取严格游标后的范围
  4. 按上限取页并保存最后键
  5. 按同一数据版本继续

04动手写一个例子

同时间Feed的复合游标分页

输入ID唯一、时间非负的冻结笔记集合,按时间降序和数字ID降序分页。游标包含全部排序字段,limit为1到1000。Java17自测。

输入 1
(2000,103),(2000,102),(2000,101),页大小2
输出 1
第一页103,102;第二页101
输入 2
空索引
输出 2
空页

比较器使用Long.compare构建两个降序字段,避免时间差或ID差溢出。索引构造时用ID集合检查业务唯一性,而TreeSet负责排序位置。

tailSet(cursor,false)寻找严格落在游标之后的第一个键,之后顺序迭代。游标对应记录即使不存在,排序边界仍有定义,不需要依赖全局偏移。

冻结集合上的相邻页严格不重叠,每个尚未读取的键仍位于最后游标之后。动态插入、删除和排序字段变更会改变可见集合,需额外快照政策。

为什么这样写是对的页内和跨页顺序都遵守同一全序;下一页所有键严格晚于游标的比较器位置,冻结集合中不会重复上页最后项。

时间 建索引O(n log n),每页O(log n+k)额外空间 O(n)索引及O(k)页结果

TreeSet定位边界对数时间,迭代k条按树顺序摊销线性;ID唯一性哈希检查平均线性,数据集不在每页重新构建。

保存为 Main.java,运行 javac --release 17 -encoding UTF-8 Main.java,再运行 java Main。程序包含固定输入自测,断言失败时会抛出错误。

Main.java · 完整可运行程序 · Java
import java.util.*;
public class Main {
    record Post(long time,long id){}
    static final Comparator<Post> ORDER=Comparator.comparingLong(Post::time).reversed().thenComparing(Comparator.comparingLong(Post::id).reversed());
    static NavigableSet<Post> index(List<Post> posts){
        TreeSet<Post> set=new TreeSet<>(ORDER);Set<Long> ids=new HashSet<>();
        for(Post p:posts){if(p.time()<0||p.id()<=0||!ids.add(p.id()))throw new IllegalArgumentException("post");set.add(p);} // 业务ID唯一,不只依赖排序键唯一。
        return Collections.unmodifiableNavigableSet(set);
    }
    static List<Post> page(NavigableSet<Post> set,Post cursor,int limit){
        if(limit<=0||limit>1000||cursor!=null&&(cursor.time()<0||cursor.id()<=0))throw new IllegalArgumentException("page");
        NavigableSet<Post> rest=cursor==null?set:set.tailSet(cursor,false); // 严格排除复合游标边界。
        List<Post> out=new ArrayList<>();for(Post p:rest){if(out.size()==limit)break;out.add(p);} // 只取有限页,避免复制整个索引。
        return List.copyOf(out);
    }
    static void eq(List<Post> e,List<Post> a){if(!e.equals(a))throw new AssertionError(a);}
    public static void main(String[] args){
        NavigableSet<Post> s=index(List.of(new Post(2000,101),new Post(2000,103),new Post(2000,102),new Post(1900,99)));
        eq(List.of(new Post(2000,103),new Post(2000,102)),page(s,null,2));
        eq(List.of(new Post(2000,101),new Post(1900,99)),page(s,new Post(2000,102),2));
        eq(List.of(),page(s,new Post(1900,99),2));eq(List.of(),page(index(List.of()),null,2));
        eq(List.of(new Post(1900,99)),page(s,new Post(1950,1),2));
        eq(List.of(new Post(Long.MAX_VALUE,Long.MAX_VALUE)),page(index(List.of(new Post(Long.MAX_VALUE,Long.MAX_VALUE))),null,1));
        try{index(List.of(new Post(1,1),new Post(2,1)));throw new AssertionError();}catch(IllegalArgumentException expected){}
        System.out.println("PASS 7 tests");
    }
}

这些特殊情况也要试一试

  • 比较器数字ID顺序不等于Redis成员字典序。
  • 模型集合冻结,不声称动态数据快照。
  • 修改排序字段可能使已有游标语义变化。
进阶选读 · 后续再读:热点作者与稳定Feed快照

场景粉丝数量差异巨大,推送成本与读取成本失衡。

做法普通作者写扩散,热点作者读时合并;为分页带入读取水位或快照版本,对删除、权限变化和迟到内容明确处理。

复杂度写扩散成本随粉丝数增长,读扩散随关注源和候选数量增长;混合方案需按负载测量,不能仅比较单次ZADD复杂度。

好处与代价冻结快照更稳定但存储和保留成本更高,实时Feed更及时却必须接受明确的变更语义。

05项目里怎么用

点赞采用稳定成员身份,ZADD NX的新增结果与ZREM删除结果可以判断是否首次变化。数据库计数与Redis成员若双写,需要可靠事件与对账,不能把两个调用串起来就认为原子。取消后再次点赞是否更新时间由业务规则决定。

关注交集适合Set,但跨Redis Cluster键操作也要考虑同槽或应用聚合;不能默认任意两个用户键都能直接多键执行。关系删除、拉黑和内容权限变更应在读取时再次校验,不能只依赖投递时的权限快照。

用时间加偏移翻页时,要累计边界时间已经读过几条;切到新时间再重新计数。若使用时间加 ID 的复合游标,真实索引也必须按相同规则排序。去数据库补详情后应恢复 Feed 顺序,并处理内容删除或不可见造成的页数不足;游标还可绑定用户与版本,避免拿到另一用户收件箱使用。

容易踩的坑

  • 重复点赞每次都把计数加一。
  • 同分时间直接排除导致漏读。
  • 把Redis字典序当作数字ID顺序。
  • 补数据库详情后丢失Feed原排序。

几种做法,怎么选

表格有四列,窄屏可左右滑动查看代价和适用条件。

方案优势代价与限制适用条件
Set关系去重和成员判断直接不提供时间排序关注与纯点赞关系
Sorted Set收件箱支持有序范围查询同分游标与双写需设计时间流Feed
复合游标避免全局偏移漂移要求全序与存储支持稳定顺序分页

06检验是否读懂了

先自己想、自己写,再展开答案核对。场景题是假设的练习情境;遇到还没学过的内容,可以做完基础后再回来。

先用自己的话解释

01计数为何不是关系本身?

展开参考答案与推导

计数不能判断某用户是否存在,也不能单独识别重复点赞,成员集合才包含身份信息。

02游标为何包含ID?

展开参考答案与推导

同时间内容需要第二字段确定唯一位置,否则无法区分已读与未读。

03冻结集合上的不重复能推广到实时吗?

展开参考答案与推导

不能直接推广,插入、删除和排序字段修改需要额外可见性与快照规则。

换个情况,还会处理吗

01三条同毫秒内容每页两条,怎样继续?

展开参考答案与推导

保存最后时间和明确同分位置;复合方案保存最后ID,下一页从严格后续键读取。

02数据库IN查询返回顺序不同怎么办?

展开参考答案与推导

按Feed中ID到排序位置的映射恢复顺序,并过滤不存在或不可见内容。

03共同关注跨集群槽报错,如何处理?

展开参考答案与推导

重新设计必要同槽范围或在应用侧聚合,不能假定多键集合命令跨槽原子执行。

写代码试一试

01第二页为什么先返回101?

输入 / 条件
游标(2000,102)
输出 / 预期
(2000,101)

提示 两个字段都降序。

展开参考答案与推导

101同时间且ID更小,严格位于游标之后,比1900时间更靠前。

02只按时间构造TreeSet有什么问题?

输入 / 条件
三条time相同
输出 / 预期
被当作相同比较键

提示 比较器决定集合位置。

展开参考答案与推导

必须加入唯一次关键字,否则不同笔记会被排序集合合并。

03不存在的游标能定位吗?

输入 / 条件
游标(1950,1)
输出 / 预期
下一项(1900,99)

提示 使用排序边界。

展开参考答案与推导

范围查询不要求边界记录存在,这比依赖记录偏移更稳定,但仍需验证游标来源。

读完之后,独立完成

课后作业:自己做一遍

本篇共 10 道作业,先完成 8 道基础与综合任务,再按前置知识挑战进阶题。其中包含 1 道思维拓展,试着换个条件,看看原来的办法是否还管用。不附参考答案。

这次练什么

能验证点赞去重、共同关注和同一时间戳的 Feed 翻页,并说明游标限制。

本篇重点加练

Feed 的成本与正确性取决于写扩散和实时分页同时变化时的产品契约。

  • Feed 写扩散
  • 并发分页边界

重点内容会多练几次。先说清楚怎么做,再试试空数据、出错或条件改变时会发生什么。

先自己做,卡住时记下问题,再回来查。问答题写清“为什么、什么时候适用”;动手题留下输入、输出和运行步骤,方便下次重做。

基础必做

  1. 作业 01代码推演

    用户先点赞、取消、再次点赞,三个请求乱序抵达;产品同时显示点赞人数与最近点赞者。定义可观察状态及操作身份,说明哪些信息仅靠成员集合不足以表达。

    提交内容
    事件序列与状态契约
    怎样算完成
    • 区分成员唯一性与操作顺序
    • 覆盖重复网络请求

    练到的知识点ZSet 点赞 · 成员去重

  2. 作业 02原理问答

    关注关系允许单向存在,用户可能屏蔽对方。画出 5 人关系图并定义共同关注、互相关注、可见共同关注三种查询。

    提交内容
    关系图与查询口径
    怎样算完成
    • 明确边的方向
    • 包含无关系和屏蔽边界

    练到的知识点Set 关注关系 · 共同关注

综合应用

  1. 作业 03设计评审

    普通作者有 30 个粉丝,头部作者有 30 万粉丝,均每分钟发布一条。比较 Feed 写入与读取成本,设定删帖后的展示契约。

    提交内容
    成本估算与读写流程
    怎样算完成
    • 列出计量单位和访问假设
    • 考虑重复投递及不可见内容

    练到的知识点Feed 写扩散 · 按分数逆序

  2. 作业 04代码推演

    给定多条同分值 Feed,在两次翻页之间插入、删除各一条,并变更一条内容的可见性。自行生成数据,逐页记录游标和实际返回项。

    提交内容
    数据集与逐页轨迹
    怎样算完成
    • 游标包含完整语义
    • 标明允许遗漏或重复的契约边界

    练到的知识点同分值偏移 · 并发分页边界

  3. 作业 05编程实践

    实现本地 Feed 翻页演示,支持固定快照和动态集合两种测试模式,加入重复成员、相同时间戳、空页与大页大小输入。

    提交内容
    Java 程序与性质检验记录
    怎样算完成
    • 每页记录排序键和游标
    • 说明测试能覆盖与不能覆盖的并发情况

    练到的知识点ZSet 点赞 · 成员去重 · Feed 写扩散 · 按分数逆序 · 同分值偏移 · 并发分页边界

  4. 作业 06设计评审

    一条笔记发布后作者把可见范围改为仅好友,已有投递副本仍在粉丝 Feed 中。评审推送完成与当前可见性检查之间的职责。

    提交内容
    可见性变更流程
    怎样算完成
    • 覆盖已缓存副本和直接访问
    • 区分投递事实与阅读权限

    练到的知识点Feed 写扩散

  5. 作业 07代码推演

    用户分别在手机和网页连续翻页,两端游标来自不同时间,期间一条笔记从置顶恢复普通排序。定义游标适用范围与可接受的结果变化。

    提交内容
    双端翻页轨迹
    怎样算完成
    • 记录排序规则版本
    • 不把不同快照游标默认混用

    练到的知识点并发分页边界

  6. 作业 08编程实践

    写本地 Feed 代价模拟器,输入作者粉丝分布、发帖率与读者活跃率,比较至少两种自定投递策略的写量、读量和陈旧窗口。

    提交内容
    源码与小型数据报告
    怎样算完成
    • 公开成本假设
    • 不将模拟次数换算成真实 Redis QPS

    练到的知识点Feed 写扩散 · 并发分页边界

进阶挑战 · 掌握前置后选做

  1. 作业 09设计评审

    用户取关后不应继续收到新推送,已读历史仍需保留。定义取关与发布并发时的生效时点,并设计清理与校验流程。

    提交内容
    时序图与验收矩阵
    怎样算完成
    • 区分关注事实与投递副本
    • 覆盖取关后又关注的周期

    练到的知识点Set 关注关系 · 共同关注 · Feed 写扩散 · 并发分页边界

思维拓展

先写出你的猜想,再用例子或实验验证。答案可以不同,但要说清依据、适用情况,以及还有什么没弄懂。

  1. 作业 10思维拓展 · 跨域迁移

    迁移到突发事件通知:少量用户必须立即收到,其他用户允许批量汇总。重新设计投递与分页契约,并说明为什么同一套 Feed 目标不再适用。

    提交内容
    跨域需求与方案评审
    怎样算完成
    • 区分时效等级
    • 检验重复通知及权限变更

    练到的知识点Feed 写扩散 · 并发分页边界

完成后,再检验一次

给每题标记“独立完成 / 查阅后完成 / 尚未完成”。查过资料或没做出的题,记下卡在哪里。隔一天换一组输入再试,能解释结果和出错原因,再把这个知识点标为掌握。

继续阅读

先看能帮你完成当前练习的部分。例子跑通后,再读更深入的解释。

打开资料库,找下一份学习材料 ↗