system design interview by alex xu

type

status

date

slug

summary

Vertical scaling vs Horizontal Scaling

“Vertical scaling”（垂直扩展）和“Horizontal scaling”（水平扩展）是两种常见的系统扩展方式，用来提升系统的处理能力或容量。下面是它们的定义和对比：

✅ 定义：

类型	定义
Vertical Scaling（垂直扩展）	增强单台服务器的性能，比如升级 CPU、增加内存、增加磁盘容量。
Horizontal Scaling（水平扩展）	增加服务器数量（节点），通过分布式系统处理更多的请求或数据。

🔍 详细比较：

对比维度	垂直扩展（Vertical Scaling）	水平扩展（Horizontal Scaling）
扩展方式	升级单台机器硬件	增加机器数量（集群）
复杂度	相对简单（硬件替换）	更复杂，需要分布式架构设计
成本	一次性高昂（高性能服务器）	可渐进增加，单机便宜但数量多
可扩展性上限	受限于单机物理资源	理论上可无限扩展
可用性	单点故障风险较高	多节点容错，容灾能力强
常见使用场景	数据库、老系统、开发环境	微服务、云计算、大数据、高并发应用

🛠 举例：

垂直扩展：

你有一台服务器运行数据库，发现内存不足，于是把内存从 16GB 升级到 64GB。

水平扩展：

你的网站流量激增，一台服务器不够用，就加多几台 Web Server，通过负载均衡来分摊请求。

📌 总结建议：

中小型项目、快速开发阶段： 可以先用垂直扩展，简单直接。

高并发、可用性要求高的系统： 应优先考虑水平扩展，结合分布式架构。

Load Balancer

如上图所示，如果只有一个数据库怎么搞？即使server多个

✅ 什么是 Load Balancer（负载均衡器）？

Load Balancer 是一种把请求流量平均分发到多个服务器上的机制或工具，确保每台服务器都不会过载，从而提高系统的可用性与扩展性。

🔧 Load Balancer 与水平扩展的关系：

项目	说明
水平扩展后，你会有多台服务器（节点）	比如多个 Web Server 或多个 API Server。
负载均衡器作为统一入口	所有客户端请求都打到 Load Balancer，由它决定请求发给哪台服务器。
核心作用	分发请求 + 故障转移 + 健康检查。

💡 类比：

没有负载均衡器： 客户端必须自己知道访问哪台服务器（复杂、不灵活）。

有负载均衡器： 客户端只访问一个 IP 或域名，由负载均衡器智能调度请求。

🧠 常见的负载均衡策略：

策略	说明
轮询（Round Robin）	顺序分配请求，平均分布
最少连接数（Least Connections）	分发给当前连接最少的服务器
IP 哈希（IP Hash）	根据客户端 IP 绑定到特定节点（做会话保持）
加权分配（Weighted）	给性能更好的服务器分配更多请求

🌐 常见的负载均衡器工具：

类型	示例
硬件负载均衡器	F5、Cisco（价格高、企业级）
软件负载均衡器	Nginx、HAProxy、Envoy
云服务负载均衡	AWS ELB、阿里云 SLB、GCP Load Balancer

🧾 总结：

负载均衡器是水平扩展的前提和关键。

它把用户请求智能分发到多台服务器，防止任何一台机器成为瓶颈或单点故障。

如果你准备做微服务、高并发、可用性要求高的系统，负载均衡器是必须的组件。

Database replication

解决的问题：

高可用性（High Availability）

主库宕机时可以快速切换到从库，减少系统不可用时间。

负载均衡（Load Balancing）

读写分离：主库写入，从库读取，减轻主库压力。

数据备份与灾难恢复（Disaster Recovery）

一旦主库出问题，从库可以作为数据备份进行恢复。

跨区域访问加速（Geographical Distribution）

跨地域部署从库，用户就近访问，加快响应。

所以有了load balanacer和db replication可能是这样的

Cache

1.when to use

2.过期策略

3.一致性：

✅ 为什么缓存和数据库之间的一致性很难保证？

1. 缓存和数据库是两个独立的系统

数据库（如 MySQL）是“真相来源”，支持事务和持久化。

缓存（如 Memcached）是速度优化层，不支持事务、不持久化，而且是“可有可无”的。

当我们对数据库更新数据时，还需要手动更新缓存，这两个操作不是原子性的，容易中断或不一致。

👉 举个简单例子：

2. 跨 Region 的多副本问题

Facebook 这种大型系统在全球有多个数据中心（region），每个 region 有自己的缓存节点。

假如用户在美国区提交了数据更新请求，更新了数据库和缓存。

但亚洲区的缓存没有立刻同步更新，可能仍然返回旧数据。

这就出现了缓存“局部新旧不一致”问题，对用户体验影响很大。

✅ Facebook 的做法（《Scaling Memcache at Facebook》中的方案）

🔧 1. Cache-aside 模式（传统做法）

Facebook 最初也用的是“cache-aside”模式：

读数据：先查缓存，缓存没有再查数据库并写入缓存；

写数据：先更新数据库，再更新缓存（或删除缓存）。

📉 问题：不是原子操作 → 写入数据库成功，但缓存更新失败 → 缓存脏数据。

🛠 2. 采用删除缓存而非更新缓存

Facebook发现：更新缓存有并发风险，于是他们选择删除缓存（invalidate），让下一次读自动从数据库加载。

这简化了逻辑，也减少了缓存-数据库的“竞争写”风险。

🧩 3. 引入 “Lease” 机制来解决缓存穿透和并发读写问题

当多个请求同时读一个失效的缓存键，都会打到数据库，形成“缓存穿透”。

Facebook引入了一种叫做**“Lease”** 的机制：

当某个 key 缓存失效，第一个请求获得“Lease”权利，去数据库加载并写入缓存。

其他并发请求等待该 Lease 完成，避免大量并发查数据库。

这样可以大幅减少数据库压力，同时确保缓存更新一致。

🌍 4. 分层缓存和异步同步机制

Facebook 在不同的数据中心使用本地 Memcached 节点，同时通过异步消息机制传播缓存失效信号，实现“最小程度的一致性”。

他们不是强一致性，而是设计了一种最终一致性架构：

本地快速响应，跨 region 缓存靠异步失效广播 + TTL 清理。

✅ 总结

原因	缓存与数据库一致性难点
1	非事务操作，更新不原子
2	跨地域部署导致同步延迟
3	并发访问导致缓存穿透和竞争更新
4	缓存是临时系统，可能失效或重启丢数据

Facebook 的解决方式包括：

使用“删除缓存”代替“更新缓存”

引入 Lease 避免缓存穿透

实现异步跨区域缓存同步

采用最终一致性，而非强一致性

4.避免多个node 用一个single cache

CDN

CDN（Content Delivery Network，内容分发网络）是一种分布式的服务器网络，用于加速用户访问静态内容（如图片、视频、CSS、JS、网页等）的速度，提高网站性能和可用性。

把你网站的静态资源复制一份，提前放到离用户更近的服务器上（“节点”），让用户就近访问，更快更稳定。

🎯 CDN 解决了什么问题？

问题	解决方式
用户离服务器太远，访问慢	在全球分布节点，用户就近访问，减少延迟
高峰期源站压力大，容易崩	CDN节点分担访问压力，保护源站
网络不稳定，丢包延迟高	节点优化传输路径，提高稳定性
静态资源更新不及时或加载失败	多副本 + 缓存，提高可用性与加载速度

✅ CDN 的主要功能

内容缓存加速（加快访问速度）

图片、视频、HTML、JS、CSS 等静态资源

负载均衡

分担源站压力

带宽节省

大量访问由 CDN 承担，不占用源站出口带宽

防护源站

通过隐藏源站 IP、抗 DDoS、WAF 等功能提升安全性

👍 CDN 的优点

优点	说明
🚀 加快访问速度	用户访问离自己最近的节点，提升体验
🌍 全球访问无障碍	国际网站常用 CDN 提供全球内容分发
📉 减少源站压力	大量请求由 CDN 节点响应，源站轻松
🛡 提高安全性	提供 DDoS 防护、隐藏源站 IP
🕒 提高可用性	即使源站短暂宕机，CDN 还能提供缓存内容

👎 CDN 的缺点

缺点	说明
❌ 缓存更新延迟	内容更新后，如果 CDN 缓存没及时刷新，用户可能看到旧内容
⚙️ 配置复杂	对于某些动态内容或自定义缓存策略，需要精细配置
💰 成本问题	高流量网站使用商业 CDN（如 Akamai、Cloudflare、阿里云 CDN）费用较高
🪓 无法缓存动态请求	CDN 主要用于静态资源，对动态 API/数据库查询无效（除非使用边缘计算等新技术）

🔧 常见使用场景

视频点播平台（如 YouTube、Bilibili）

电商网站（加快商品图展示）

静态网站或前端部署（如 React/Vue 项目打包后的静态资源）

全球用户访问的网站（需要全球加速）

防止恶意流量攻击（利用 CDN 安全服务）

Stateful Server VS Stateless Server

✅ 定义

类型	定义
Stateful Server（有状态）	服务器保存客户端的状态信息，每次请求依赖之前的会话（session）或上下文（context）
Stateless Server（无状态）	服务器不保存客户端状态，每次请求都是独立的，服务端只根据请求内容做出响应

🎯 为什么有这些差别？核心原因在于：

✅ 状态（State）是否保存在服务端

Stateful：服务器记录了你是谁、你上一步做了什么。例如传统的登录会话、购物车、游戏进度等。

Stateless：客户端每次请求都要提供足够的信息（如 token、参数），服务器不“记得你”。

🔍 关键区别对比

特性	Stateful Server	Stateless Server
是否记录状态	✅ 记录客户端状态	❌ 不记录
扩展性	❌ 扩展困难，需要 session 共享	✅ 易扩展
容错性	❌ 某台服务挂了状态就丢	✅ 任意服务可处理
请求独立性	❌ 请求之间有关联	✅ 每个请求独立
示例	FTP、传统 HTTP Session 登录	RESTful API、OAuth2 token

💡 举例说明

Stateful（有状态）：

你登录了一个网站，登录状态保存在服务器内存中（session）。

下次请求这个服务器记得你，不需要再次登录。

但如果请求被转发到另一台服务器，状态就可能丢失，除非有 session 同步机制。

Stateless（无状态）：

每次请求都带上身份信息（如 JWT token）。

服务端不保留任何会话信息。

请求可以被任意一台服务器处理，非常适合负载均衡、微服务、云原生部署。

✅ 为什么更推荐 Stateless Server？

在现代架构中（特别是 REST API、微服务、云服务），Stateless Server 更受欢迎，因为：

更容易扩展（scalable）：请求可以均匀分配到多个服务器。

更高可用性（fault tolerant）：服务无状态，不怕节点宕机。

更适合容器化、无服务器架构（如 Kubernetes、AWS Lambda）

🧠 总结一句话：

Stateful server 需要“记住你”，Stateless server 每次都“重新认识你”。

Message Queue

Message Queue（消息队列）是一种异步通信机制，主要用于解耦系统中的各个模块、削峰填谷、提高系统的可伸缩性与容错性。它解决的核心问题包括以下几个方面：

✅ 1. 系统解耦

问题： 系统之间紧密耦合，比如服务 A 调用服务 B，如果 B 挂了，A 也出问题。

MQ 解决： A 把消息发送到 MQ，B 订阅 MQ。即使 B 挂了，消息仍在队列中，A 正常运行。

✅ 2. 削峰填谷（流量削峰）

问题： 高并发时数据库或服务容易被打垮（如秒杀、抢购）。

MQ 解决： 将请求放入消息队列，后端系统异步慢慢处理，平滑瞬时高流量。

✅ 3. 异步处理

问题： 某些操作耗时，但用户不需同步等待（比如下单后发短信）。

MQ 解决： 下单逻辑立即返回，发送短信的任务丢到 MQ 异步处理，提高响应速度和用户体验。

✅ 4. 系统扩展性

问题： 如果写死“一个生产者一个消费者”，扩展困难。

MQ 解决： 你可以动态增加消费者消费消息，实现水平扩展。

✅ 5. 容错和失败重试

问题： 某个模块短暂故障，消息丢失。

MQ 解决： 支持持久化、消息确认机制、重试机制，避免数据丢失。

举例说明：

假设你做一个电商平台：

用户下单 → 系统发消息给 MQ

库存系统、物流系统、积分系统都去订阅这个消息

它们分别异步地更新库存、准备物流、增加积分

这样每个模块互不影响，出现故障也不会拖垮整条链路。

常见 MQ 系统：

Kafka（高吞吐、适合大数据）

RabbitMQ（支持复杂路由、功能丰富）

RocketMQ（阿里出品，国产分布式方案）

NATS（轻量、高性能，适合微服务）

DB Sharding

分片是实现horizontal scaling的手段，因为可能数据库一个处理了所有请求，需要load balance.

sharding的方式：

类型	说明
按用户 ID 分片	用户 ID % 4 分到 4 个分片
按地理位置分片	中国、美国、欧洲分别存储在不同节点
按时间分片	日志数据按月存储，1月放A库，2月放B库

难点：

某个shards特别多data，会exhausted—>重新考虑sharding function

celebrity problem:某个shard有特别多celebrity的data，query都往这里来

BACK-OF-THE ENVELOPE ESTIMATION

back-of-the-envelope calculations are estimates you create using a combination of thought experiments and common performance numbers to get a good feel for which designs will meet your requirements

🔢 基本假设：

300 million monthly active users.

50% of users use Twitter daily.

Users post 2 tweets per day on average.

10% of tweets contain media.

Data is stored for 5 years.

一、QPS（Query Per Second）估算过程：

✅ 1. 计算每日活跃用户数：

✅ 2. 每天的总推文数：

✅ 3. QPS 计算（平均推文写入速率）：

一整天 = 24 小时 = 24 * 3600 = 86400 秒

✅ 4. 峰值 QPS：

为了应对瞬时流量，估计峰值为平均值的两倍：

二、媒体存储估算过程：

✅ 1. 每天带有媒体的推文数量：

只有 10% 的推文包含媒体：

✅ 2. 每条带媒体推文大小 = 1MB

所以：

✅ 3. 5 年媒体总存储：

一年按 365 天算：

✅ 总结公式式：

QPS = 总条数 ÷ 秒数

媒体存储每天 = 推文数 × 10% × 1MB

媒体总存储 = 每日存储 × 365 × 年数

如果你想我可以进一步帮你估算 text 字段的存储量，或者包括 metadata 的总 tweet 存储量（而不只是媒体）。是否需要？

Interview Step

1.Understand Problem and establish design scope

2.PROPOSE HIGH-LEVEL design

Design deep

4.wrap up

Design Rate Limiter

搞清楚是client side / server side

client not reliable

server side最好还是用middleware的形式，比如上面的限制only 2 users; 3rd 就会报错429

—》

microservice最好用api gateway (includes ssl,auth,ip whitelist….)

Algorithms for rate limiting:

token bucket

Leaking bucket

FIFO

bucket size= queue size

pros: fixed rate

cons:old request没有被处理就一直在queue里面

Fixed Window Counter

设定一个固定时间窗口（如 1 秒、1 分钟、1 小时）。

为每个时间窗口维持一个计数器。

当请求到来时：

如果当前时间属于该窗口并且计数器未超过限额，允许请求并加 1；
如果超过限额，拒绝请求；
如果进入了下一个时间窗口，重置计数器为 1，重新计

Sliding window

我们不按「整秒」切，而是看过去 X 秒内所有请求总数。

比如「5 秒内最多 10 个请求」，我们会实时滑动

像保安在数过去 60 秒内总共进了多少人。只要超过 5 个，就不让进。这样就不会让人“钻空子”。

一般来说用redis之类的存这个counter

detail design

如果是分布式

一般用redis的 lua/sorted set来解决

当然可以。我们来系统地深入讲清楚 Lua 脚本限流 和 Redis Sorted Set 限流 的策略、底层原理、为什么能解决分布式限流问题，以及使用场景、优劣对比等。

✅ 一、为什么分布式限流难？

在单机系统中，限流很简单，用内存计数器或队列即可。但在分布式系统中：

多台机器并发处理请求；

每台机器之间没有共享内存；

请求分布随机，单机限流失效。

因此，我们需要一个全局共享的状态中心（比如 Redis），来记录请求行为。

✅ 二、方案一：使用 Lua 脚本 + Redis 计数器限流（Fixed Window）

📌 场景：

每个用户每分钟最多发起 100 次请求（Fixed Window，即“固定时间窗口”限流）。

🧠 基本逻辑：

Redis 中记录每个用户当前窗口内的访问次数。

超过限制就拒绝。

利用 Lua 脚本来保证整个判断 + 修改操作是原子的（即不会被并发打断）。

✅ 实现细节：

Redis 键：

例子：rate_limit:123:202505291432，后缀是当前分钟。

Lua 脚本步骤：

INCR key：当前窗口内请求计数加 1；

如果是第一次访问，调用 EXPIRE 设置 TTL，比如 60 秒；

如果计数值大于限制，返回拒绝；

否则，允许请求。

Lua 示例：

调用方式（举例）：

✅ 特点：

简单高效：只操作一个计数器；

有“突刺问题”：

如果在 12:00:59 发 100 次，12:01:00 再发 100 次，短时间内共发 200 次。

✅ 三、方案二：使用 Redis Sorted Set（ZSET）实现 Sliding Window 限流

📌 场景：

用户每 任意 60 秒内 最多访问 100 次（更精准控制）。

🧠 核心思想：

利用 Redis 的有序集合（ZSET），将每次访问的时间戳作为 score 和 member 插入，然后删除时间窗口外的数据，最后统计数量。

✅ 实现步骤（滑动窗口算法）：

获取当前时间戳（毫秒）；

从 Redis ZSET 中删除所有 score < (now - 60000) 的条目；

统计 ZSET 中剩余元素数量；

如果数量 < 限制，允许并写入当前请求；

否则拒绝。

Lua 实现示例：

调用方式：

✅ 特点：

优点	缺点
精确滑动窗口控制，无突刺	每次都插入时间戳，占用更多内存
灵活性高，可支持复杂统计	每秒操作多个 ZSET，性能比计数器低

✅ 四、两个策略对比总结

特性	Lua + 计数器（Fixed）	Sorted Set 滑动窗口
实现复杂度	⭐⭐ 简单	⭐⭐⭐⭐ 中等
性能（QPS）	⭐⭐⭐⭐⭐ 极高	⭐⭐ 中等
精度	⭐⭐ 存在边界突刺	⭐⭐⭐⭐⭐ 精确
内存占用	⭐⭐ 低	⭐⭐⭐⭐ 高（记录每次请求）
Redis 操作次数	1~2	3~4
是否原子	✅ Lua 保证	✅ Lua 保证

✅ 五、实战建议

场景	推荐策略
用户量大、性能敏感	Lua + Counter
精确控制请求频率	Sorted Set
接口级限流 / 网关	用 Redis + Token Bucket / Envoy RateLimit
复杂限流规则	用限流组件（如 Sentinel、Envoy、Nginx+Lua）

📌 原始代码：

✅ ARGV 是什么？

在 Redis 中使用 Lua 脚本时：

KEYS 是传入的 Redis 键名列表（例如限流的 key，如 rate_limit:user123）

ARGV 是传入的参数值列表（例如限流的最大次数、过期时间）

✅ `ARGV[1]` 和 `ARGV[2]` 表示什么？

假设我们这样调用脚本：

1 表示有 1 个 key，后面第一个参数是 key：rate_limit:user123

后面依次是 ARGV 参数：

ARGV[1] 是 "100"（最大请求数限制）
ARGV[2] 是 "60"（过期时间，单位秒）

✅ 那 `tonumber` 是干嘛的？

Lua 默认读取 ARGV 是字符串类型，为了做数值比较或运算，需要用 tonumber 转成数字类型。

✅ 举个完整例子：

你调用这个脚本时传入的是：

Lua 脚本中就会得到：

然后这个脚本就能根据这些参数来判断是否允许访问。

要点回顾：

表达式	含义
`ARGV[1]`	脚本外部传入的第一个参数（字符串）
`tonumber(ARGV[1])`	转为数字（才能做数值比较）
`local limit = ...`	把值赋给局部变量 `limit`

分布式同步的问题

在分布式限流中出现 Synchronization issue（同步问题），指的是多个节点（应用实例）对同一资源的访问频率无法正确同步，导致限流失效或不准确。我们来解释常见的同步问题和对应的解决方案：

✅ 一、常见的 Synchronization Issues

1. ❌ 各节点独立计数，状态不共享

每个实例自己维护请求计数 → 总体请求量无法统一控制（如限制“全站 QPS 1000”）

2. ❌ 多节点并发操作同一个 Redis 键，未使用原子操作

多台机器并发读 + 写，可能出现“读旧值 + 写覆盖”的 race condition

3. ❌ 延迟 / 时钟不一致

如果使用本地时间窗口，机器时间不同会导致滑动窗口计算不一致

✅ 二、解决方案汇总

问题类型	解决方案
状态不一致	使用 Redis 或分布式共享存储统一计数
操作不原子	使用 Redis + Lua 保证操作原子性
滑动窗口失真	使用 Redis Sorted Set 并精确清理时间外数据
节点间时钟不同	避免本地时间戳，统一使用服务端时间（如 Redis 当前时间）
分布式高并发冲突	使用 Redlock 分布式锁（不推荐用于高频限流）

✅ 三、核心解决方案详解

✅ 1. 使用 Redis + Lua（原子操作）

Lua 脚本在 Redis 中运行是原子的，可以一次完成计数 + 判断 + 设置过期等操作：

这个脚本只会在 Redis 内部执行，不会被并发打断，防止同步问题。

✅ 2. 全局状态存 Redis，所有节点统一读写

所有服务实例都访问同一个 Redis 实例或集群

不使用本地缓存计数

避免状态不一致

✅ 3. 精确滑动窗口：使用 Redis Sorted Set

插入请求时间戳（score）

清除窗口外时间戳（ZREMRANGEBYSCORE）

获取当前窗口计数（ZCARD）

这样可以做到：

所有节点都基于 Redis 状态判断

不依赖本地系统时间

✅ 4. 使用服务端时间戳（如 Redis 的 `TIME` 命令）

Redis 中执行：

可以返回服务端时间，避免各机器时钟不一致导致的问题。

✅ 5. 对高并发场景，避免分布式锁（除非是低频限流）

使用 Redis 的 Redlock 分布式锁 虽然可以串行处理限流逻辑，但：

❗ 并发高时性能瓶颈明显，不推荐用于频繁限流

✅ 四、建议实践方案（总结）

需求类型	推荐方案
精确控制用户行为	Redis Sorted Set + Lua
高性能全局 QPS 限制	Redis Counter + Lua
服务网关限流	API Gateway + Redis
请求量极高	加入本地缓存预估 + Redis 确认
多地部署	Redis 主从或集群统一状态

✅ 示例：Redis 解决限流同步问题流程图

所有请求行为通过 Redis 集中判断是否限流，实现状态同步 + 原子性控制。

如你需要，我可以为你生成一整套 Java + Redis 限流实现（包括 Lua、滑动窗口、Token Bucket 等）作为模板使用。是否需要？

✅ 一、常见的 Synchronization Issues

1. ❌ 各节点独立计数，状态不共享

每个实例自己维护请求计数 → 总体请求量无法统一控制（如限制“全站 QPS 1000”）

2. ❌ 多节点并发操作同一个 Redis 键，未使用原子操作

多台机器并发读 + 写，可能出现“读旧值 + 写覆盖”的 race condition

3. ❌ 延迟 / 时钟不一致

如果使用本地时间窗口，机器时间不同会导致滑动窗口计算不一致

✅ 二、解决方案汇总

问题类型	解决方案
状态不一致	使用 Redis 或分布式共享存储统一计数
操作不原子	使用 Redis + Lua 保证操作原子性
滑动窗口失真	使用 Redis Sorted Set 并精确清理时间外数据
节点间时钟不同	避免本地时间戳，统一使用服务端时间（如 Redis 当前时间）
分布式高并发冲突	使用 Redlock 分布式锁（不推荐用于高频限流）

✅ 三、核心解决方案详解

✅ 1. 使用 Redis + Lua（原子操作）

Lua 脚本在 Redis 中运行是原子的，可以一次完成计数 + 判断 + 设置过期等操作：

这个脚本只会在 Redis 内部执行，不会被并发打断，防止同步问题。

✅ 2. 全局状态存 Redis，所有节点统一读写

所有服务实例都访问同一个 Redis 实例或集群

不使用本地缓存计数

避免状态不一致

✅ 3. 精确滑动窗口：使用 Redis Sorted Set

插入请求时间戳（score）

清除窗口外时间戳（ZREMRANGEBYSCORE）

获取当前窗口计数（ZCARD）

这样可以做到：

所有节点都基于 Redis 状态判断

不依赖本地系统时间

✅ 4. 使用服务端时间戳（如 Redis 的 `TIME` 命令）

Redis 中执行：

可以返回服务端时间，避免各机器时钟不一致导致的问题。

✅ 5. 对高并发场景，避免分布式锁（除非是低频限流）

使用 Redis 的 Redlock 分布式锁 虽然可以串行处理限流逻辑，但：

❗ 并发高时性能瓶颈明显，不推荐用于频繁限流

✅ 四、建议实践方案（总结）

需求类型	推荐方案
精确控制用户行为	Redis Sorted Set + Lua
高性能全局 QPS 限制	Redis Counter + Lua
服务网关限流	API Gateway + Redis
请求量极高	加入本地缓存预估 + Redis 确认
多地部署	Redis 主从或集群统一状态

✅ 示例：Redis 解决限流同步问题流程图

所有请求行为通过 Redis 集中判断是否限流，实现状态同步 + 原子性控制。

Redis是中心的？怎么做到的

你问的这个问题非常关键，是设计全球/跨地域分布式系统时最核心的架构挑战之一：

“这个 Redis 中心到底放在哪里？”
“分布式系统部署在世界各地，还怎么访问同一个 Redis？”

✅ 一、如果 Redis 放在单个机房，会有什么问题？

1. 网络延迟高

假如你的 Redis 在北京，但服务实例部署在美国，那调用 Redis 可能需要几百毫秒，限流判断效率极差。

2. 单点瓶颈 / 宕机风险

只有一个 Redis 节点会变成所有服务的瓶颈，甚至可能因 Redis 宕机导致全部限流功能失效。

✅ 二、常见部署方案（全球多机房 Redis 限流策略）

📌 方案 1：使用 Redis Cluster + 多地访问（不推荐全球跨洲）

将 Redis 部署为集群，各服务节点访问主节点。

适合部署在同一大洲或数据中心区域（如 AWS us-east-1）。

不适合全球级别的跨区域访问（因延迟大）。

📌 方案 2：按地理区域部署多个 Redis + 地区独立限流（推荐）

✅ 原理：

每个机房/地区部署自己的 Redis。

限流逻辑只在本地区范围内生效。

✅ 架构图：

✅ 特点：

每个区域限流独立，延迟低，架构简单。

比如：“每个用户每分钟最多请求 100 次”，指的是在某一区域限制。

✅ 缺点：

无法实现“全站级别”统一限流，比如“全球 QPS 不超过 10 万”。

📌 方案 3：使用边缘限流 + 中心聚合统计

在边缘节点本地限流（快速响应），再周期性将状态同步到中心 Redis。

适合流量大、对实时性要求高的业务。

✅ 三、实际生产建议（按业务选择）

业务类型	推荐方案
单区域部署	使用中心 Redis 即可
多区域部署，限流只需本地有效	每个区域部署自己的 Redis 限流
全球统一限流（如统一计费）	Kafka + 聚合 Redis/数据库
大流量内容分发 CDN 接口	网关限流 + 地区独立 Redis

✅ 四、总结：Redis 中心部署要因地制宜

你想要的效果	Redis 架构建议
延迟低 + 高并发	各地区独立 Redis 限流
全球统一统计	Redis 集群或 Kafka + 聚合
原子性强 + 状态一致性	Redis + Lua 脚本
高可用性	Redis Sentinel / Cluster

Consistent Hashing

✅ 先从你熟悉的开始：普通哈希（mod）

假设有 3 台服务器：A、B、C

我们将请求分发给服务器的方法是：

hash("user1") % 3 = 0 → 服务器A

hash("user2") % 3 = 1 → 服务器B

💥 问题来了：

如果你加了一台新服务器D，变成 4 台：

👉 原来的数据全部乱了，缓存全部失效！

✅ 一致性哈希：换一种分发思路

想象一下：

我们不是用 mod，而是把所有服务器排在一个“圆环”上：

每台服务器和每个 key 都映射成这个环上的一个位置（用 hash 算出来）：

✅ 怎么找 key 属于哪个服务器？

👉 沿着圆环 顺时针 走，遇到的第一个服务器 就是目标！

Key1(3500) → 顺时针走 → 命中 Server B (4000)

Key2(8000) → 顺时针走 → 命中 Server C (9000)

Key3(9500) → 走到最末了，就“转圈”回到 Server A

✅ 为什么这样设计就牛了？

加新服务器示例：

现在新增一台 Server D → 6000

只会影响：

4000 ~ 6000 这个区域的 key，其他 key 不动！

这就是一致性哈希最大的好处：

🟢 只迁移一小部分 key，不动全局。

✅ 类比帮助你理解：

你可以把一致性哈希理解为：

概念	类比
环（0 ~ 2³²）	一个钟表圆盘
节点 A/B/C	放在钟表上的 3 个标签
key	一个小纸条，贴在某个角度上
请求路由	顺时针走，走到第一个标签就贴上去

✅ 小结一句话：

一致性哈希的本质是：把 key 和服务器都放在一个圆上，顺时针找目标节点，从而减少节点变化带来的整体影响。

❗ 一致性哈希的常见问题 & 对应解决方案

### 🧨 问题 1：数据分布不均

假设我们有 3 台服务器 A、B、C：

hash("A") = 1000

hash("B") = 900000

hash("C") = 1000000

大多数 key 的哈希值都在 900000 到 2³² 范围之间，就都被分给 C。

👉 问题：服务器负载不均，部分机器很忙，部分很闲

✅ 解决方案：引入虚拟节点（Virtual Nodes）

📌 什么是虚拟节点？

每个真实服务器映射成多个虚拟节点，均匀散布在环上。

比如 A → A#1, A#2, A#3, ..., A#100

这样 key 不是分配给“服务器”，而是分配给“虚拟节点”，最后再映射到对应服务器。

✅ 效果：

把一台服务器变成多个虚拟副本，散布在环上，数据更均匀。

所有节点都承担一部分负载，整体平衡。

### 🧨 问题 2：节点频繁上下线，维护复杂

比如微服务场景，服务实例频繁扩缩容，新节点加入、旧节点下线太频繁，环结构变动太频繁。

✅ 解决方案：

使用服务注册中心（如 Consul、Eureka、Etcd） 监控节点变化。

引入 Gossip 协议 或 动态重建哈希环结构。

如果变化频率太高，可以考虑用其他策略：如一致性哈希 + LRU 缓存做中间层，减少真实数据迁移。

🧨 问题 3：节点数量少时，虚拟节点也不够均匀

例如你只有 2~3 台服务器，即使加了 100 个虚拟节点，哈希函数不够好，依旧有分布偏差。

✅ 解决方案：

使用强分布性的哈希函数，比如 MurmurHash、CityHash 替代 Java 默认的 hashCode。

监控分布情况，动态调整虚拟节点数量。

🧨 问题 4：环结构难于跨区域使用

如果你的节点分布在全球（比如 AWS 多区域），一致性哈希会遇到：

网络延迟（节点在国外）

数据迁移慢

管理困难

✅ 解决方案：

每个地区构建 自己的哈希环

利用 地理位置感知 的调度策略，例如将北美用户请求 hash 到北美节点环上，避免跨洲访问

✅ 最终建议总结：

问题	建议解决方案
数据分布不均	引入虚拟节点 + 更好的哈希函数
节点频繁变化	动态重建哈希环 + 服务注册中心 + 节流策略
跨区域通信延迟大	按区域建独立 hash 环
哈希不均或冲突	使用高质量哈希函数（MurmurHash 等）

Build up a key-value store

ideally希望每个node直接能够propagate

但万一网络挂了就不行（real world case）

CAP理论

Consistency: consistency means all clients see the same data at the same time no matter which node they connect to. Availability: availability means any client which requests data gets a response even if some of the nodes are down. Partition Tolerance: a partition indicates a communication break between two nodes. Partition tolerance means the system continues to operate despite network partitions.

选择Consistency Partition 那么不能进行write操作到n1 n2不然n3不能和他们统一 (Bank！)

AP?：

对可用性要求高、对一致性容忍的系统，例如：

缓存系统（如 Redis Cluster）

日志记录、广告点击系统

https://soulmachine.gitbooks.io/system-design/content/cn/key-value-store.html

组件	核心目标	常见解决方案
Data Partition	扩展性	Consistent Hash / Range 分片
Data Replication	容错 & 高可用	主从复制、Paxos、Raft
Consistency	数据可信度	强一致 or 最终一致
Inconsistency Resolution	副本冲突处理	LWW、Vector Clock、Read Repair
Handling Failures	系统稳定性	重试、选主、WAL、快照恢复
Write Path	安全写入	WAL + Quorum + 异步复制
Read Path	快速读取	缓存 + 多副本读 + 冲突检测修复

🏗️ 从零开始的分布式KV存储系统

第一章：问题的起源

想象你在开发一个社交平台。最开始，你用一台服务器存储用户信息就够了。但随着用户增长到千万级别，问题来了：

存储爆炸：单机硬盘装不下所有数据

性能瓶颈：每秒十万次请求，单机扛不住

可用性风险：服务器宕机，整个系统瘫痪

解决方案很直接：用多台机器！但这就引出了分布式系统的核心挑战。

第二章：数据分区 - 数据该放哪里？

现在你有4台服务器，1000万用户数据该怎么分配？

问题具体化：用户查询"user_12345"时，系统怎么知道去哪台服务器找？

方案演进：

简单哈希：hash(user_id) % 4 决定放在哪台服务器

问题：增加服务器时，需要重新分配75%的数据

一致性哈希：把服务器和数据都映射到一个环上

优势：增加服务器时，只需迁移少量数据

这就是数据分区的最终解决方案

关键洞察：分区解决了"数据放哪里"的问题，但引入了新问题：单台服务器故障怎么办？

第三章：数据复制 - 备份才是王道

单台服务器存储用户数据，服务器故障就丢数据了。解决方案：每份数据存3份。

具体做法：

用户"user_12345"的数据不仅存在服务器A

还复制到服务器B和服务器C

这样任何一台服务器故障，数据都不会丢失

复制策略的权衡：

同步复制：3台服务器都写成功才返回成功 → 安全但慢

异步复制：主服务器写成功就返回 → 快但可能丢数据

半同步：2台写成功就返回 → 平衡方案

关键洞察：复制解决了"数据丢失"问题，但引入了新问题：多个副本的数据可能不一致！

第四章：一致性挑战 - 多个副本谁说了算？

现在出现了复杂情况：

用户在北京修改了个人信息

数据写入了服务器A（北京）

但还没同步到服务器B（上海）

这时用户在上海查询，看到的是旧数据

这就是一致性问题的本质：同一份数据的多个副本在某个时刻可能不一致。

解决思路：

强一致性：读写都必须访问多数节点，保证看到最新数据

最终一致性：允许短暂不一致，但保证最终会一致

冲突解决：两个用户同时修改怎么办？用时间戳、版本号等方式解决

关键洞察：一致性是分布式系统最核心的挑战。你必须在性能和一致性之间做权衡。

第五章：故障处理 - 墨菲定律永远适用

分布式系统的铁律：能出错的地方一定会出错。

故障场景串联：

服务器故障：硬件损坏、软件崩溃

解决：健康检查+自动切换到副本

网络分区：机房之间网络中断

结果：集群被分成两部分，彼此无法通信

解决：仲裁机制（多数派继续工作，少数派停止服务）

数据损坏：磁盘出错、数据错误

解决：校验和验证+从副本恢复

关键洞察：故障处理不是可选功能，而是分布式系统的必需品。

第六章：完整流程 - 把所有部分串起来

现在我们把所有概念串联成一个完整的操作流程：

写入流程（存储用户信息）：

客户端：PUT user_12345 {name: "张三", age: 25}

路由层：计算hash(user_12345)，确定数据应该存在服务器A

主节点A：写入数据到内存和磁盘

复制层：同步数据到副本节点B和C

一致性层：等待至少2个节点确认写入成功

返回：告诉客户端"写入成功"

读取流程（查询用户信息）：

客户端：GET user_12345

路由层：计算hash(user_12345)，确定数据在服务器A

读取策略：根据一致性要求，选择从1个节点还是多个节点读取

数据校验：如果发现不一致，触发读修复

返回：返回用户数据给客户端

故障处理流程（服务器A故障）：

检测：其他节点发现服务器A心跳停止

切换：自动将读写请求路由到副本节点B

恢复：服务器A恢复后，从副本同步最新数据

重新加入：服务器A重新加入集群

🎯 核心串联逻辑

现在你可以看到这些概念是如何相互关联的：

数据分区解决了"数据太多，单机放不下"的问题

数据复制解决了"单机故障，数据丢失"的问题

一致性控制解决了"多副本数据不一致"的问题

故障处理解决了"系统组件必然会出错"的问题

系统架构把这些组件组织起来，形成完整系统

读写路径定义了数据如何在这个系统中流动

Vertical scaling vs Horizontal Scaling

✅ 定义：

🔍 详细比较：

🛠 举例：

📌 总结建议：

Load Balancer

✅ 什么是 Load Balancer（负载均衡器）？

🔧 Load Balancer 与水平扩展的关系：

💡 类比：

🧠 常见的负载均衡策略：

🌐 常见的负载均衡器工具：

🧾 总结：

Database replication

解决的问题：

Cache

✅ 为什么缓存和数据库之间的一致性很难保证？

1. 缓存和数据库是两个独立的系统

2. 跨 Region 的多副本问题

✅ Facebook 的做法（《Scaling Memcache at Facebook》中的方案）

🔧 1. Cache-aside 模式（传统做法）

🛠 2. 采用删除缓存而非更新缓存

🧩 3. 引入 “Lease” 机制 来解决缓存穿透和并发读写问题

🌍 4. 分层缓存和异步同步机制

✅ 总结

CDN

🎯 CDN 解决了什么问题？

✅ CDN 的主要功能

👍 CDN 的优点

👎 CDN 的缺点

🔧 常见使用场景

Stateful Server VS Stateless Server

✅ 定义

🎯 为什么有这些差别？核心原因在于：

✅ 状态（State）是否保存在服务端

🔍 关键区别对比

💡 举例说明

Stateful（有状态）：

Stateless（无状态）：

✅ 为什么更推荐 Stateless Server？

🧠 总结一句话：

Message Queue

✅ 1. 系统解耦

✅ 2. 削峰填谷（流量削峰）

✅ 3. 异步处理

✅ 4. 系统扩展性

✅ 5. 容错和失败重试

举例说明：

常见 MQ 系统：

DB Sharding

BACK-OF-THE ENVELOPE ESTIMATION

🔢 基本假设：

一、QPS（Query Per Second）估算过程：

✅ 1. 计算每日活跃用户数：

✅ 2. 每天的总推文数：

✅ 3. QPS 计算（平均推文写入速率）：

✅ 4. 峰值 QPS：

二、媒体存储估算过程：

✅ 1. 每天带有媒体的推文数量：

✅ 2. 每条带媒体推文大小 = 1MB

✅ 3. 5 年媒体总存储：

✅ 总结公式式：

Interview Step

Design Rate Limiter

✅ 一、为什么分布式限流难？

✅ 二、方案一：使用 Lua 脚本 + Redis 计数器限流（Fixed Window）

📌 场景：

🧠 基本逻辑：

✅ 实现细节：

Redis 键：

Lua 脚本步骤：

Lua 示例：

调用方式（举例）：

✅ 特点：

✅ 三、方案二：使用 Redis Sorted Set（ZSET）实现 Sliding Window 限流

📌 场景：

🧠 核心思想：

✅ 实现步骤（滑动窗口算法）：

Lua 实现示例：

调用方式：

✅ 特点：

🧩 3. 引入 “Lease” 机制来解决缓存穿透和并发读写问题

✅ `ARGV[1]` 和 `ARGV[2]` 表示什么？

✅ 那 `tonumber` 是干嘛的？

✅ 4. 使用服务端时间戳（如 Redis 的 `TIME` 命令）

✅ 4. 使用服务端时间戳（如 Redis 的 `TIME` 命令）

📌 方案 3：使用边缘限流 + 中心聚合统计