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楼）并停止服务。
• 数据分析：可以收集乘客的乘梯数据，通过分析来预测未来的客流模式，从而动态调整调度算法，实现智能化调度。

设计图

classDiagram
    class ElevatorController {
        -ElevatorService elevatorService
        +createElevator(maxCapacity: int) ResponseEntity<Elevator>
        +createRequest(elevatorId: Long, originFloor: int, destinationFloor: int) ResponseEntity<Request>
        +processNextStep(elevatorId: Long) ResponseEntity<Void>
        +getAllElevators() ResponseEntity<List<Elevator>>
        +getElevator(elevatorId: Long) ResponseEntity<Elevator>
        +getPendingRequests(elevatorId: Long) ResponseEntity<List<Request>>
    }

    class ElevatorService {
        -ElevatorRepository elevatorRepository
        -RequestRepository requestRepository
        +createElevator(maxCapacity: int) Elevator
        +createRequest(originFloor: int, destinationFloor: int) Request
        +processNextStep(elevatorId: Long) void
        +findOptimalElevator(request: Request) Elevator
        +calculateCost(elevator: Elevator, requestFloor: int) int
        +processLookAlgorithm(elevator: Elevator, requests: List<Request>) void
        +findNextStop(currentFloor: int, direction: Direction, stops: Set<Integer>) Optional<Integer>
        +handleFloorArrival(elevator: Elevator, floor: int) void
        +getAllElevators() List<Elevator>
        +getElevator(id: Long) Elevator
        +getPendingRequests(elevatorId: Long) List<Request>
    }

    class Elevator {
        -Long id
        -int maxCapacity
        -int currentLoad
        -int currentFloor
        -Direction direction
        -State state
        -Set<Integer> stops
        -Set<Request> requests
    }

    class Request {
        -Long id
        -int originFloor
        -int destinationFloor
        -Direction direction
        -boolean completed
        -boolean passengerPickedUp
        -Date createdAt
        -Date completedAt
        -Elevator elevator
    }

    class Direction {
        <<enumeration>>
        UP
        DOWN
        IDLE
    }

    class State {
        <<enumeration>>
        MOVING
        STOPPED
        DOOR_OPEN
        IDLE
    }

    class ElevatorRepository {
        <<interface>>
        +findAll() List<Elevator>
        +save(elevator: Elevator) Elevator
        +findById(id: Long) Optional<Elevator>
    }

    class RequestRepository {
        <<interface>>
        +findByCompletedFalse() List<Request>
        +findByElevatorIdAndCompletedFalse(elevatorId: Long) List<Request>
        +findByOriginFloorAndDirectionAndCompletedFalse(floor: int, direction: Direction) List<Request>
    }

    ElevatorController --> ElevatorService : uses
    ElevatorService --> ElevatorRepository : uses
    ElevatorService --> RequestRepository : uses
    Elevator "1" --> "*" Request : has
    Request "*" --> "1" Elevator : belongs to
    Elevator ..> Direction : uses
    Elevator ..> State : uses
    Request ..> Direction : uses

sequenceDiagram
    actor User
    participant API as "REST API"
    participant ElevatorService as "ElevatorService"
    participant RequestService as "RequestService"
    participant Elevator1 as "Elevator 1"
    participant Elevator2 as "Elevator 2"
    participant Database as "Database"

    Note over User: 用户在3楼，想去10楼
    User->>API: POST /api/elevators/requests?origin=3&dest=10
    activate API
    API->>ElevatorService: createRequest(3, 10)
    activate ElevatorService
    
    Note over ElevatorService: 寻找最优电梯
    ElevatorService->>Database: findAllElevators()
    Database-->>ElevatorService: [Elevator1, Elevator2]
    
    par "计算各电梯成本"
        ElevatorService->>ElevatorService: calculateCost(Elevator1)
        Note over ElevatorService: Elevator1: floor=1, IDLE, cost=2
        ElevatorService->>ElevatorService: calculateCost(Elevator2)
        Note over ElevatorService: Elevator2: floor=8, DOWN, cost=10
    end
    
    Note over ElevatorService: 选择Elevator1（成本最低）
    ElevatorService->>Database: saveRequest(Request)
    ElevatorService->>Elevator1: addStop(3)
    ElevatorService-->>API: Request created
    deactivate ElevatorService
    deactivate API
    
    Note over User: 电梯开始响应
    
    loop 直到到达3楼
        User->>API: POST /api/elevators/{id}/step
        API->>ElevatorService: processNextStep(elevatorId)
        ElevatorService->>Elevator1: processLookAlgorithm()
        Elevator1->>Elevator1: move 1→2→3
        Elevator1->>Database: saveState()
    end
    
    Note over Elevator1: 到达3楼
    Elevator1->>ElevatorService: handleFloorArrival(3)
    ElevatorService->>Database: updateRequest(pickedUp=true)
    ElevatorService->>Elevator1: addStop(10)
    ElevatorService->>Elevator1: removeStop(3)
    
    Note over User: 用户进入电梯，按下10楼
    
    User->>API: POST /api/elevators/{id}/requests?origin=3&dest=10
    API->>ElevatorService: createInternalRequest(10)
    ElevatorService->>Elevator1: addStop(10)
    
    loop 直到到达10楼
        User->>API: POST /api/elevators/{id}/step
        API->>ElevatorService: processNextStep(elevatorId)
        ElevatorService->>Elevator1: processLookAlgorithm()
        Elevator1->>Elevator1: move 3→4→...→10
        Elevator1->>Database: saveState()
    end
    
    Note over Elevator1: 到达10楼
    Elevator1->>ElevatorService: handleFloorArrival(10)
    ElevatorService->>Database: updateRequest(completed=true)
    ElevatorService->>Elevator1: removeStop(10)
    
    Note over User: 用户离开电梯

设计一个音乐播放器系统

项目链接

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）进行部署，实现故障自愈和弹性伸缩。

设计图

类图

classDiagram
    class MusicController {
        -MusicService musicService
        +getSong(songId: Long) ResponseEntity<Song>
        +createPlaylist(userId: Long, name: String) ResponseEntity<Playlist>
        +addToPlaylist(playlistId: Long, songId: Long) ResponseEntity<Void>
        +getUserState(userId: Long) ResponseEntity<PlayerState>
    }

    class MusicService {
        -SongRepository songRepository
        -PlaylistRepository playlistRepository
        -StateCache stateCache
        -StateSyncService stateSyncService
        +getSong(songId: Long) Song
        +createPlaylist(userId: Long, name: String) Playlist
        +updatePlayerState(userId: Long, state: PlayerState) void
    }

    class StateSyncService {
        <<WebSocket Server>>
        +notifyClients(userId: Long, state: PlayerState) void
        +handleClientEvent(userId: Long, event: PlayerEvent) void
    }

    class Song {
        -Long id
        -String title
        -String artist
        -String album
        -int duration
        -String cdnUrl
    }

    class Playlist {
        -Long id
        -String name
        -User owner
        -List<Song> songs
    }

    class User {
        -Long id
        -String username
    }

    class PlayerState {
        <<Value Object>>
        -Long currentSongId
        -int timestamp
        -PlayerStatus status
        -List<Long> queue
    }

    class PlayerStatus {
        <<enumeration>>
        PLAYING
        PAUSED
        STOPPED
    }

    class SongRepository {<<interface>>}
    class PlaylistRepository {<<interface>>}
    class StateCache {<<interface>>}

    MusicController --> MusicService
    MusicService --> SongRepository
    MusicService --> PlaylistRepository
    MusicService --> StateCache
    MusicService --> StateSyncService
    Playlist "1" *-- "1" User : owned by
    Playlist "1" o-- "*" Song : contains

时序图

sequenceDiagram
    actor User
    participant Client as "Client App"
    participant Gateway as "API Gateway"
    participant MusicSvc as "Music Service"
    participant StateSvc as "State Sync Service (WebSocket)"
    participant Cache as "Redis Cache"
    participant DB as "Database"
    participant CDN as "Content Delivery Network"

    Note over User, Client: 用户在歌曲列表中点击播放按钮
    Client->>Gateway: POST /api/player/play (songId)
    activate Gateway
    Gateway->>MusicSvc: play(userId, songId)
    deactivate Gateway
    
    activate MusicSvc
    MusicSvc->>Cache: getSong(songId)
    activate Cache
    Cache-->>MusicSvc: null (cache miss)
    deactivate Cache
    
    MusicSvc->>DB: findSongById(songId)
    activate DB
    DB-->>MusicSvc: Song{..., url: s3://...}
    deactivate DB
    
    Note over MusicSvc: 将S3 URL转换为CDN URL
    MusicSvc->>Cache: setSong(songId, songData)
    MusicSvc-->>Client: {cdnUrl: "https://cdn.xyz/..."}
    deactivate MusicSvc
    
    Client->>CDN: GET /audio.mp3
    activate CDN
    CDN-->>Client: Streaming audio data...
    deactivate CDN
    
    Note over Client: 开始播放，并上报状态
    Client->>StateSvc: send(event: {action: "PLAY", songId: ..., time: 0})
    activate StateSvc
    StateSvc->>MusicSvc: updatePlayerState(userId, state)
    activate MusicSvc
    MusicSvc->>Cache: saveState(userId, playerState)
    MusicSvc-->>StateSvc: ack
    deactivate MusicSvc
    
    Note over StateSvc: 将新状态广播给用户其他设备
    StateSvc->>Client: broadcast(newState)
    deactivate StateSvc