功能场景

【中等】如何设计一个排行榜功能？⭐⭐⭐⭐

🎯 目标等级：L2 ｜ ⏱ 建议用时：15 min ｜ 🏷 标签：功能设计 / 缓存

💎 关键结论

首选 Redis zset（有序集合）：以用户为 member、排行指标为 score，天然有序。ZINCRBY 原子加分，ZREVRANGE 取 Top N，ZREVRANK 查个人名次，O(logN) 复杂度，实时且简单。

经典数据结构

数组

题目	难度	状态
1. 两数之和	简单	通过
167. 两数之和 II - 输入有序数组	中等	通过
剑指 Offer II 006. 排序数组中两个数字之和	简单	通过
剑指 Offer 57. 和为 s 的两个数字	简单	通过
136. 只出现一次的数字	简单	通过
217. 存在重复元素	简单	通过
2073. 买票需要的时间	简单	通过
26. 删除有序数组中的重复项	简单	未通过
27. 移除元素
283. 移动零
344. 反转字符串
5. 最长回文子串
263. 丑数	简单	未通过
264. 丑数 II	中等	未通过
1201. 丑数 III	中等	未通过
313. 超级丑数	中等	未通过
373. 查找和最小的 K 对数字

ZooKeeper 并没有直接采用 Paxos 算法，而是采用了名为 ZAB 的一致性协议。ZAB 协议不是 Paxos 算法，只是比较类似，二者在操作上并不相同。Multi-Paxos 实现的是一系列值的共识，不关心最终达成共识的值是什么，不关心各值的顺序。而 ZooKeeper 需要确保操作的顺序性。

ZAB 协议是 Zookeeper 专门设计的一种支持故障恢复的原子广播协议。

ZAB 协议是 ZooKeeper 的数据一致性和高可用解决方案。

为什么需要复杂度分析

衡量算法的优劣，有两种评估方式：事前估计和后期测试。

后期测试有性能测试、基准测试（Benchmark）等手段。

但是，后期测试有以下限制：

• 测试结果非常依赖测试环境。如：不同机型、不同编译器版本、不同硬件配置等等，都会影响测试结果。
• 测试结果受数据规模的影响很大。

所以，需要一种方法，可以不受环境或数据规模的影响，粗略地估计算法的执行效率。这种方法就是复杂度分析。

时间复杂度分析

简介

Gossip 也叫 Epidemic Protocol （流行病协议），这个协议基于最终一致性以及去中心化设计思想。主要用于分布式节点之间进行信息交换和数据同步，这种场景的一个最大特点就是组成的网络的节点都是对等节点，是非结构化网络（去中心化）。

Gossip 协议最早是在 1987 年发表在 ACM 上的论文 《Epidemic Algorithms for Replicated Database Maintenance》中被提出，其理论基础来源于流行病学的数学模型，这种场景的一个最大特点就是组成的网络的节点都是去中心化的对等节点，在信息同步过程中不能保证某个时刻所有节点都收到消息，但是理论上最终所有节点都会收到消息，实现最终一致性协议。

Paxos 是一种基于消息传递且具有容错性的共识性（consensus）算法。

Paxos 算法解决了分布式一致性问题：在一个节点数为 2N+1 的分布式集群中，只要半数以上的节点（N + 1）还正常工作，整个系统仍可以正常工作。

Raft 简介

Raft 是一种为了管理日志复制的分布式共识性算法。从本质上说，Raft 算法是通过一切以领导者为准的方式，实现一系列值的共识和各节点日志的一致。

1. 为什么学习数据结构和算法

• 为了找到一份好工作：大厂面试喜欢考算法
• 更深入了解流行技术的设计思想：数据结构和算法是计算机基础学科，很多框架、中间、底层系统设的设计，都借鉴了其思想。因此，掌握数据结构和算法，有利于更深入了解这些技术的设计思想。
• 提升个人的编程水平
• 不满足于做业务狗，拓展性能思考的视角

2. 如何学习数据结构和算法

数据结构就是指一组数据的存储结构。算法就是操作数据的一组方法。