读完这篇,你能做什么
能验证点赞去重、共同关注和同一时间戳的 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["授权详情与顺序恢复"]按顺序看,每一步做了什么
- 以成员变化定义点赞和取消的幂等结果。
- 将关注关系与Feed排序索引分开。
- 明确同分排序与游标全部字段。
- 用同时间多条数据验证连续分页。
- 再评估写扩散、读扩散和并发变更的语义。
03对照实现代码
OpenJDK 17 GA,jdk-17+35 · TreeSet.tailSet / iterator
下方为原创 Java 教学片段,调用已核验的 JDK API 说明局部机制;不是该类原样源码,不代表Redis或数据库内核实现。完整程序见算法模块。
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分数字节排序、编码与命令边界仍需按官方文档实现和测试。
代码先调用谁,再调用谁
- 定义时间与ID全序
- 构建唯一内容索引
- 读取严格游标后的范围
- 按上限取页并保存最后键
- 按同一数据版本继续
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)寻找严格落在游标之后的第一个键,之后顺序迭代。游标对应记录即使不存在,排序边界仍有定义,不需要依赖全局偏移。
冻结集合上的相邻页严格不重叠,每个尚未读取的键仍位于最后游标之后。动态插入、删除和排序字段变更会改变可见集合,需额外快照政策。
为什么这样写是对的页内和跨页顺序都遵守同一全序;下一页所有键严格晚于游标的比较器位置,冻结集合中不会重复上页最后项。
TreeSet定位边界对数时间,迭代k条按树顺序摊销线性;ID唯一性哈希检查平均线性,数据集不在每页重新构建。
保存为 Main.java,运行 javac --release 17 -encoding UTF-8 Main.java,再运行 java Main。程序包含固定输入自测,断言失败时会抛出错误。
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 写扩散
- 并发分页边界
重点内容会多练几次。先说清楚怎么做,再试试空数据、出错或条件改变时会发生什么。
先自己做,卡住时记下问题,再回来查。问答题写清“为什么、什么时候适用”;动手题留下输入、输出和运行步骤,方便下次重做。
基础必做
- 作业 01代码推演
用户先点赞、取消、再次点赞,三个请求乱序抵达;产品同时显示点赞人数与最近点赞者。定义可观察状态及操作身份,说明哪些信息仅靠成员集合不足以表达。
- 提交内容
- 事件序列与状态契约
- 怎样算完成
- 区分成员唯一性与操作顺序
- 覆盖重复网络请求
练到的知识点ZSet 点赞 · 成员去重
- 作业 02原理问答
关注关系允许单向存在,用户可能屏蔽对方。画出 5 人关系图并定义共同关注、互相关注、可见共同关注三种查询。
- 提交内容
- 关系图与查询口径
- 怎样算完成
- 明确边的方向
- 包含无关系和屏蔽边界
练到的知识点Set 关注关系 · 共同关注
综合应用
- 作业 03设计评审
普通作者有 30 个粉丝,头部作者有 30 万粉丝,均每分钟发布一条。比较 Feed 写入与读取成本,设定删帖后的展示契约。
- 提交内容
- 成本估算与读写流程
- 怎样算完成
- 列出计量单位和访问假设
- 考虑重复投递及不可见内容
练到的知识点Feed 写扩散 · 按分数逆序
- 作业 04代码推演
给定多条同分值 Feed,在两次翻页之间插入、删除各一条,并变更一条内容的可见性。自行生成数据,逐页记录游标和实际返回项。
- 提交内容
- 数据集与逐页轨迹
- 怎样算完成
- 游标包含完整语义
- 标明允许遗漏或重复的契约边界
练到的知识点同分值偏移 · 并发分页边界
- 作业 05编程实践
实现本地 Feed 翻页演示,支持固定快照和动态集合两种测试模式,加入重复成员、相同时间戳、空页与大页大小输入。
- 提交内容
- Java 程序与性质检验记录
- 怎样算完成
- 每页记录排序键和游标
- 说明测试能覆盖与不能覆盖的并发情况
练到的知识点ZSet 点赞 · 成员去重 · Feed 写扩散 · 按分数逆序 · 同分值偏移 · 并发分页边界
- 作业 06设计评审
一条笔记发布后作者把可见范围改为仅好友,已有投递副本仍在粉丝 Feed 中。评审推送完成与当前可见性检查之间的职责。
- 提交内容
- 可见性变更流程
- 怎样算完成
- 覆盖已缓存副本和直接访问
- 区分投递事实与阅读权限
练到的知识点Feed 写扩散
- 作业 07代码推演
用户分别在手机和网页连续翻页,两端游标来自不同时间,期间一条笔记从置顶恢复普通排序。定义游标适用范围与可接受的结果变化。
- 提交内容
- 双端翻页轨迹
- 怎样算完成
- 记录排序规则版本
- 不把不同快照游标默认混用
练到的知识点并发分页边界
- 作业 08编程实践
写本地 Feed 代价模拟器,输入作者粉丝分布、发帖率与读者活跃率,比较至少两种自定投递策略的写量、读量和陈旧窗口。
- 提交内容
- 源码与小型数据报告
- 怎样算完成
- 公开成本假设
- 不将模拟次数换算成真实 Redis QPS
练到的知识点Feed 写扩散 · 并发分页边界
进阶挑战 · 掌握前置后选做
- 作业 09设计评审
用户取关后不应继续收到新推送,已读历史仍需保留。定义取关与发布并发时的生效时点,并设计清理与校验流程。
- 提交内容
- 时序图与验收矩阵
- 怎样算完成
- 区分关注事实与投递副本
- 覆盖取关后又关注的周期
练到的知识点Set 关注关系 · 共同关注 · Feed 写扩散 · 并发分页边界
思维拓展
先写出你的猜想,再用例子或实验验证。答案可以不同,但要说清依据、适用情况,以及还有什么没弄懂。
- 作业 10思维拓展 · 跨域迁移
迁移到突发事件通知:少量用户必须立即收到,其他用户允许批量汇总。重新设计投递与分页契约,并说明为什么同一套 Feed 目标不再适用。
- 提交内容
- 跨域需求与方案评审
- 怎样算完成
- 区分时效等级
- 检验重复通知及权限变更
练到的知识点Feed 写扩散 · 并发分页边界
完成后,再检验一次
给每题标记“独立完成 / 查阅后完成 / 尚未完成”。查过资料或没做出的题,记下卡在哪里。隔一天换一组输入再试,能解释结果和出错原因,再把这个知识点标为掌握。
继续阅读
先看能帮你完成当前练习的部分。例子跑通后,再读更深入的解释。
- 必读参考文档英文
Redis:ZADD (新标签页)↗
阅读 NX、分数和成员更新,验证点赞去重与时间线插入。
- 实践参考文档英文
Redis:SINTER (新标签页)↗
阅读集合交集与复杂度,用小规模数据验证共同关注。
- 深入参考文档英文
Redis:ZRANGE (新标签页)↗
阅读 BYSCORE、REV 和 LIMIT,处理同分值分页与版本差异。
- 深入教程英文
Redis:Sorted Sets (新标签页)↗
阅读分数排序、成员唯一与范围查询,设计排行榜和时间线索引。
- 深入参考文档英文
OpenJDK 17 TreeSet 源码 (新标签页)↗
按指定版本定位
TreeSet.tailSet/ iterator;对照源码分析理解实际调用边界。