Grokking the System Design

设计一个电梯系统

项目链接

myElevator

思路

1. 这道题考察候选人的什么知识？

面试官不是真的想让候选人造一台电梯，而是想通过这个问题评估候选人的综合能力，主要包括：

• 需求分析与沟通能力：这是最重要的一点。一个优秀的工程师在动手前，会先问问题，明确需求和边界。直接埋头开始写代码的候选人通常会失分。
• 面向对象设计 (OOD) 能力：这个问题是考察OOD的绝佳场景。如何将现实世界的实体（电梯、楼层、按钮、乘客）抽象成清晰、低耦合的对象和类？
• 算法与数据结构：电梯调度策略是整个系统的核心，这直接考察候选人的算法设计能力。如何选择合适的数据结构来存储和处理请求，以实现高效的调度？
• 状态机建模能力：电梯的运行本身就是一个状态机（静止、上升、下降、开门、关门等）。能否清晰地定义这些状态以及它们之间的转换条件，是衡量逻辑思维严谨性的关键。
• 并发与同步问题：多部电梯、多个乘客请求，这些都是并发场景。候选人是否能意识到可能存在的竞态条件（Race Condition）和资源同步问题？
• 系统扩展性 (Scalability)：设计是只针对一台电梯，还是一个拥有多台电梯的系统？如何将单电梯的设计平滑地扩展到多电梯的调度系统？

2. 难点在哪？

这个问题的难点主要集中在调度算法和多电梯协同上。

核心难点：调度算法 (Scheduling Algorithm)

• 目标冲突：调度算法需要平衡多个目标，而这些目标可能是冲突的。例如：
  • 最短的乘客等待时间 (Fairness)：不能让某个楼层的乘客等太久。
  • 最短的电梯运行时间 (Efficiency)：电梯完成所有任务的总时间要短。
  • 最少的能耗：电梯运行的距离和启停次数要少。
• 算法选择：
  • 朴素算法 (Naive)：先来先服务 (FCFS)。这种算法非常低效，会导致电梯在楼层间来回“之”字形运行，是典型的错误答案。
  • 扫描算法 (SCAN/LOOK)：这是最经典的电梯算法。电梯在一个方向上持续运行，响应所有同方向的请求，直到该方向没有请求时再掉头。这大大提高了效率。
  • 优化算法：在SCAN的基础上，可以有很多优化，比如考虑乘客的目的地、预测高峰期人流模式（如早高峰时，大量请求从1楼去往各个楼层）等。

扩展难点：多电梯协同调度

• 当有多部电梯时，来了一个新的乘梯请求（比如在5楼按了“向上”按钮），应该派哪部电梯去响应？
• 这就需要一个中央控制器 (Central Controller) 来做决策。
• 决策的依据（成本函数）是什么？需要综合考虑：
  • 距离：哪部电梯离5楼最近？
  • 方向：是否有电梯正在朝5楼的方向（向上）行驶？
  • 负载：电梯是否已经满员？
  • 状态：电梯是否正在服务中或处于空闲状态？
  • 将请求分配给“综合成本”最低的电梯，是一个复杂的实时决策过程。

应该怎么设计？（面试回答步骤）

在面试中，候选人可以按照以下“四步法”来展示他的思考过程：

第一步：沟通和澄清需求 (Clarify Requirements)

“在开始设计之前，我想先明确一下系统的需求和范围。”

• 建筑信息：有多少层楼？有多少部电梯？
• 电梯规格：电梯的最大载重是多少？速度是多少？
• 核心目标：我们设计的首要目标是什么？是最小化平均等待时间，还是最节能？
• 功能范围：是否需要支持特殊功能，如消防模式、VIP模式、残障人士模式？

目的：展现严谨、需求先行的工作习惯。

第二步：面向对象建模 (Object-Oriented Modeling)

“好的，基于这些需求，我们可以将系统抽象成以下几个核心对象。”

• ElevatorCar (电梯轿厢)
  • 属性: id, currentFloor, direction (UP, DOWN, IDLE), state(MOVING, STOPPED, DOOR_OPEN), door, requests (一个存储内部按钮请求的集合)。
  • 行为: move(), stop(), openDoor(), closeDoor()。
• ElevatorController (电梯控制中心)
  • 属性: elevators (电梯列表), pendingRequests (待处理的外部请求队列)。
  • 行为: handleRequest(request) (接收外部请求并分配给最合适的电梯), getOptimalElevator(request)。
• Request (请求)
  • 属性: originFloor, destinationFloor, direction。可以分为InternalRequest和 ExternalRequest。
• Floor(楼层)
  • 属性: floorNumber, upButton, downButton。
• Button (按钮)
  • 属性: isPressed。

目的：展现候选人的OOD能力，将复杂系统分解为清晰的模块。

第三步：设计核心算法 (Design Algorithm)

“接下来，我们来设计最核心的调度算法。”

单电梯调度 (LOOK 算法)

• 电梯内部维护两个请求列表：upRequests和downRequests。
• 运行逻辑：
  • 如果当前方向是UP，则继续向上，停靠所有顺路的、需要上升的楼层。直到upRequests 中没有高于当前楼层的请求。
  • 然后改变方向为DOWN。
  • 如果当前方向是DOWN，则继续向下，停靠所有顺路的、需要下降的楼层。直到downRequests 中没有低于当前楼层的请求。
  • 然后改变方向为UP。
  • 如果两个列表都为空，则电梯状态变为IDLE。

多电梯协同调度

• 当一个外部请求（如5楼按“上”）产生时，ElevatorController 介入。
• 控制器遍历所有电梯，为每部电梯计算一个“成本(Cost)”。
• 成本函数 calculateCost(elevator, request) 可以这样设计：
  • 如果电梯方向与请求方向相反，成本无限大。
  • 如果电梯满载，成本无限大。
  • 如果电梯空闲，成本 = abs(elevator.currentFloor - request.originFloor)。
  • 如果电梯同向且在请求楼层之前，成本 = abs(elevator.currentFloor - request.originFloor)。
  • 如果电梯同向但在请求楼层之后，需要考虑绕行的距离，成本会更高。
  • 控制器将该请求分配给 cost 最低的那部电梯。

目的：展现候选人的算法设计和问题解决能力。

第四步：讨论优化与扩展 (Discuss Optimizations & Scalability)

“最后，我们可以讨论一些可以优化的点。”

• 性能优化：在高峰期（早晚高峰），可以采用不同的调度策略。例如，早高峰时，让几部电梯专门从1楼运送乘客上去，返回时不停站，以提高吞吐量。
• 用户体验：电梯关门前，如果红外传感器检测到有人或物体，应立即重新开门。
• 健壮性：增加紧急模式，如火警时，所有电梯应迫降到指定楼层（通常是1楼）并停止服务。
• 数据分析：可以收集乘客的乘梯数据，通过分析来预测未来的客流模式，从而动态调整调度算法，实现智能化调度。

设计图

设计一个音乐播放器系统

项目链接

myMusicPlayer

思路

1. 这道题考察候选人的什么知识？

设计一个音乐播放器（如Spotify, Apple Music），面试官关注的是候选人构建一个大规模、高可用、用户体验流畅的媒体服务的能力。主要考察点包括：

• 面向对象设计 (OOD)：如何抽象出歌曲(Song)、专辑(Album)、播放列表(Playlist)、用户(User) 和核心的播放器(Player)等实体？
• 数据建模与存储：如何存储海量的音乐元数据（SQL/NoSQL选型）和音乐文件本身（对象存储/CDN）？如何处理它们之间的复杂关系？
• 状态管理与同步：播放器本身是一个复杂的状态机（播放、暂停、停止）。如何管理其状态，并在用户的多个设备间（手机、电脑、音箱）实时同步播放进度？
• 网络与API设计：如何设计高效、低延迟的API来支持播放控制？如何实现流畅的音乐流式传输？
• 系统可伸缩性 (Scalability)：如何设计后端架构以支持千万级用户和亿级曲库的并发访问？缓存、CDN、负载均衡等技术的运用是关键。
• 用户核心功能设计：如何实现播放队列、随机播放、单曲循环等核心逻辑？

2. 难点在哪？

核心难点：实时状态同步 (Real-time State Synchronization)

• 一个用户可能在手机上暂停一首歌，然后希望在电脑上从完全相同的时间点继续播放。
• 这就要求系统能够近乎实时地捕捉、存储和分发播放状态（当前歌曲、播放时间戳、播放队列）。
• 这通常需要用到WebSocket等长连接技术，对后端的状态管理服务和数据库造成巨大压力。

架构难点：高并发流媒体分发 (High-Concurrency Streaming)

• 向全球数百万用户同时提供高质量的音频流，是一个巨大的挑战。
• 单纯依靠服务器读取文件并发送是不可行的。必须设计一套基于对象存储 (S3) + 内容分发网络 (CDN) 的架构，将音乐文件缓存到离用户最近的边缘节点，以保证低延迟和高可用性。
• 还需要考虑不同的码率（音质）以适应不同的网络条件。

算法难点：播放队列管理与推荐 (Queue Management & Recommendation)

• 播放队列的管理逻辑比看起来要复杂。如何处理“下一首播放”、“添加到队列末尾”？“随机播放”如何实现得更“智能”（避免最近播放过的歌曲）？
• 现代音乐播放器的核心竞争力在于其推荐引擎。这涉及到复杂的机器学习算法（如协同过滤、内容分析），虽然面试中不要求实现，但需要候选人能够从系统设计的角度阐述其位置和数据流。

应该怎么设计？（面试回答步骤）

第一步：沟通和澄清需求 (Clarify Requirements)

“在开始设计前，我想先明确一下核心功能和系统边界。”

• 核心功能：支持播放、暂停、上一首/下一首、进度条拖动。支持创建和管理播放列表。
• 用户功能：需要支持用户账户系统吗？（是）播放历史和状态需要在多设备间同步吗？（是，这是关键需求）
• 内容范围：曲库规模有多大？是否需要支持播客或视频？（先专注于音乐）
• 关键特性：是否需要支持离线下载？是否需要实现推荐功能？（先设计核心，再讨论扩展）
• 目标规模：我们预期的用户量是多少？（例如，千万级日活）

目的：展现产品思维和抓重点的能力。

第二步：面向对象建模 (Object-Oriented Modeling)

“基于需求，我们可以定义以下几个核心对象。”

• Player(播放器)
  • 属性: currentSong, playbackQueue(播放队列), state(PLAYING, PAUSED), playbackTimestamp(当前播放时间), repeatMode, shuffleMode。
  • 行为: play(song), pause(), seek(timestamp), playNext(), addToQueue(song)。
• User(用户)
  • 属性: userId, name, playlists, likedSongs。
• Song(歌曲)
  • 属性: songId, title, duration, audioFileUrl, artist, album。
• Playlist (播放列表)
  • 属性: playlistId, name, owner(User), songs(有序列表)。
• MusicService(音乐服务)
  • 作为核心业务逻辑的协调者，处理用户请求，并操作其他对象。

目的：展现清晰的模块划分和抽象能力。

第三步：设计核心架构与数据流 (Design Architecture & Data Flow)

“系统的核心是数据存储和实时通信，我将这样设计：”

数据存储

• 元数据 (Metadata): 用户信息、歌曲信息、播放列表等关系性强的数据，使用关系型数据库 (如 PostgreSQL)。数据库需要为高频查询（如查询用户播放列表）设计合适的索引。
• 音乐文件 (Audio Files): 存储在对象存储 (如 AWS S3) 中。这是存储海量非结构化数据的最佳实践。
• 缓存 (Cache): 使用分布式缓存 (如 Redis) 存储热门歌曲的元数据、用户播放列表和用户“会话”（当前播放状态），以减轻数据库压力。

系统架构与数据流

• 客户端 (Client): Web, iOS, Android 应用。
• API 网关 (API Gateway): 所有请求的入口，负责路由、认证和限流。
• 音乐服务 (Music Service): 处理业务逻辑，如获取歌曲信息、管理播放列表。
• 状态同步服务 (State Sync Service): 使用 WebSocket 与客户端保持长连接。当用户在一个设备上操作（如暂停），客户端通过WebSocket发送事件到此服务，服务更新缓存和数据库，并立即将新状态广播给该用户的所有其他在线设备。
• CDN: 客户端不直接从S3下载音乐，而是通过CDN获取。当用户请求播放一首歌，音乐服务返回的是一个CDN的URL，客户端从最近的CDN节点拉取音频流，实现低延迟播放。

目的：展现对后端架构、数据库选型和网络协议的综合运用能力。

第四步：讨论优化与扩展 (Discuss Optimizations & Scalability)

“在核心功能之上，我们可以从以下几个方面进行优化和扩展。”

• 离线播放：客户端需要一个下载管理器，将加密后的音乐文件存储在本地。同时需要一个机制，在设备恢复在线时，同步离线期间的播放记录。
• 推荐系统：可以构建一个独立的推荐服务 (Recommendation Service)。它异步地消费用户的播放历史数据流（通过Kafka等消息队列），运行机器学习模型（如协同过滤），并将推荐结果写入数据库，供主服务查询。
• 数据分析：收集用户行为数据（播放、暂停、跳过、喜欢），用于分析用户喜好、优化推荐算法和改进产品设计。
• 健壮性：所有服务都应是无状态且可水平扩展的。使用容器化（Docker/Kubernetes）进行部署，实现故障自愈和弹性伸缩。

设计图

类图

时序图