敲定系统设计:面试敲开大厂的门-读书笔记
2025-05-09 10:00:09 0 举报AI智能生成
**精炼读书笔记：《敲定系统设计：面试敲开大厂的门》** 在紧张的面试氛围中，系统的构建能力往往决定了求职者是否能顺利成为顶尖企业的敲门砖。《敲定系统设计：面试敲开大厂的门》是一本旨在帮助软件工程师提升系统设计面试技能的实战指南。本书深入剖析了系统设计的基本理念、常见的面试问题及其解决方案，帮助应聘者在面对各种系统设计挑战时能够逻辑清晰地展示自己的设计思维。 书中详细介绍了分布式系统的设计原则、扩展性、一致性和容错机制等关键概念，用丰富的实际案例教会读者如何针对真实世界的复杂需求构建灵活且高效的系统架构。每个章节都配有精心设计的练习题，旨在加深读者对关键概念的理解，并激发解题创意。 作为技术面试者必备的参考资料，本书不仅仅是一份书面指南，它还包含了一系列面试技巧，帮助求职者克服面试中的难关，提供了一整套应对系统设计面试的方法论。精读本书，并结合实践中的经验，无疑将大大增加进入心仪企业的机会。
作者其他创作
大纲/内容
阅读前后的对比
读书前
读书后
书籍的思维导图
部分
1 从0到100万用户的扩展
关键词
持续改进
不断优化
请求流
流量源头
横向扩展
纵向扩展
负载均衡器
数据库复制
缓存层
缓存读
CDN
无状态网络层
数据中心
解耦
消息队列
重要内容
演化过程
最初
服务和数据库都在一起
第一层分割
服务和数据库拆分
网站访问的请求流程
1用户输入域名,访问网站
2域名通过dns解析为ip地址,返回给请求端
3请求端使用ip地址构建http请求,发送到服务器
4web服务器,返回html页面,或者其他响应信息给请求端
流量源头
web应用
移动应用
数据库选择
关系型数据库
关系型数据库通过表和行来表示和存储数据。你可以使用SQL对不同的数据库表执行连接(join)操作。
非关系型数据库
可以分为四类：键值存储、图存储、列存储和文档存储。非关系型数据库一般不支持连接操作。
何时该选择非关系数据库
•你的应用只能接受非常低的延时。
•应用中的数据是非结构化的，或者根本没有任何关系型数据。
•只需要序列化（JSON、XML、YAML等格式）和反序列化数据。
•需要存储海量数据。
扩展方向选择
纵向扩展
纵向扩展也叫作向上扩展，指的是提升服务器的能力（CPU、RAM等）。
初期价格低廉,越往后性价比越低
纵向扩展是有硬性限制的，你不可能给一台服务器无限添加CPU和内存。
纵向扩展没有故障转移和冗余。一旦一台服务器宕机，网站/应用也会随着一起完全不可用。
横向扩展
横向扩展也叫作向外扩展，指的是为你的资源池添加更多服务器
初期性价比较低,越往后性价比越高
由于纵向扩展存的限制，因此对于大型应用来说，采用横向扩展更合适一些。
负载均衡器
作用
将输入流量均匀分配到负载均衡集中的各个web服务器上
增加了负载均衡器和一台Web服务器后，我们成功解决了网络层的故障转移问题，提升了网络层的可用性
对外不再暴露web服务器,只暴露负载均衡器
为了提高安全性，服务器之间的通信使用私有IP地址。
私有IP地址只可以被同一个网络中的服务器访问，在公网中是无法访问的。
负载均衡器和Web服务器之间使用私有IP地址来通信。
数据库复制-主从数据库架构
概念
在很多数据库管理系统中，通常都可以利用原始数据库（Master，主库）和拷贝数据库（Slave，从库）之间的主从关系进行数据库复制
构成
主库
主库通常只支持写操作。
所有修改数据的指令，如插入、删除或更新等，都必须发送给主库来执行。
从库
从库保存主库的数据副本且仅支持读操作
优点
性能更好
可靠性高
可用性高
解决的问题
数据库宕机后可以更块的提供服务
数据库初期读写请求数据量差异较大时的性能瓶颈
从库宕机
从其他从库提供服务
没有从库,暂时将读写请求都迁移到主库
主库宕机
会有一个从库推选为新的主库
产生的问题
在生产环境中，因为从库的数据不一定是最新的，所以推选一个新的主库会更麻烦。缺失的数据需要通过运行数据恢复脚本来补全。
缓存优化
缓存
概念
缓存是临时的存储空间，用于存储一些很耗时的响应结果或者内存中经常被访问的数据，这样后续再访问这些数据时能更快
目的
提升数据反馈效率
作用
提高系统性能，减轻数据库的工作负载以及能够单独扩展缓存层
使用缓存后的访问过程
缓存读
当收到一个请求时，Web服务器首先检查缓存中是否有可用的数据：如果有，Web服务器就直接将数据返回给客户端；如果没有，就去查询数据库并把返回的响应存储在缓存中，再将其返回给Web服务器
缓存使用注意事项
什么时候使用缓存
如果对数据的读操作很频繁，而修改却不频繁，则可考虑使用缓存。因为被缓存的数据是存储在易变的内存中的，所以缓存服务器不是持久化数据的理想位置。
过期决策
执行过期策略是好的做法。一旦缓存中的数据过期，就应该将其从缓存中清除。如果不设置过期策略，缓存中的数据会一直被保存在内存中。
一致性
这关系到数据存储和缓存的同步。当对数据的修改在数据存储和缓存中不是通过同一个事务来操作的时候，就会发生不一致。
减轻出错的影响
单缓存服务器是系统中的一个潜在单点故障
驱逐策略
一旦缓存已满，任何对缓存添加条目的请求都有可能导致已有条目被删除，这叫作缓存驱逐。
不同的驱逐策略
LRU
最近最少使用
LFU
最不经常使用
FIFO
先进先出
CDN-内容分发网络
概念
内容分发网络(Content Delivery Network，CDN)是由在地理上分散的服务器组成的网络，被用来传输静态内容。
CDN中的服务器缓存了像图片、视频、CSS和JavaScript文件这一类的静态内容。
CDN基本工作原理
当用户访问一个网站时，离用户最近的CDN服务器会返回静态资源。
给人的直观感受是，离CDN服务器越远，网站加载内容就越慢。
使用CDN的注意事项
花销
设置合理的缓存过期时间
CDN回退
作废文件
示意图
子主题
子主题
无状态网络层
有状态架构
概念
有状态的服务器处理客户端发来的一个个请求，并记下客户端的数据（状态）。无状态的服务器则不保存状态信息。
示意图
子主题
无状态架构
概念
在无状态架构中，用户的HTTP请求可以发给任意Web服务器，然后Web服务器从共享的数据存储中拉取数据。
状态数据存储在共享数据存储而非Web服务器中。无状态的系统更加简单，更健壮，也更容易扩展
集群中的每个Web服务器都可以经由数据库访问状态数据。这就是所谓的无状态网络层。
基本方案
现在是时候考虑横向扩展网络层了。为此，我们需要将状态（例如，用户会话数据）从网络层中移出。一个好的做法是将会话数据存储在持久性存储（如关系型数据库或NoSQL）中
数据中心
概念
解决的问题
超大流量下,单个数据中心,单个负载均衡,是无法承接那么大的数据流量的
数据中心通过不同区域访问不通数据中心,进行前置流量分流,从而处理更大更多的流量
产生的问题
流量重定向
要有能把流量引导到正确数据中心的有效工具
geoDNS
数据同步
不同地区的用户可以使用不同的本地数据库或者缓存。
在故障转移的场景中，流量可能被转到一个数据不可用的数据中心。常用的一个策略是在多个数据中心复制数据
测试和部署
设置多数据中心后，在不同的地点测试你的网站/应用是很重要的。
而自动部署工具则对于确保所有数据中心的服务一性至关重要
解耦系统中的不同的组件-消息队列
概念
消息队列是一个持久化的组件，存储在内存中，支持异步通信。它被用作缓冲区，分配异步的请求。
基本结构
生产者
消费者
消息队列
消息队列的作用
当消费者无法处理消息时，生产者依然可以将消息发布到队列中；
就算生产者不可用，消费者也可以从队列中读取消息。
解耦使消息队列成为构建可扩展和可靠应用的首选架构。
记录日志,收集指标自动化
日志记录
日志采集
日志链路追踪
日志汇总
日志分析
收集指标
常用指标
主机级别
cpu
内存
磁盘IO
网络流量
聚合级别指标
数据库性能
缓存性能
关键业务指标
每日活跃用户数DAU
留存率
收益
自动化
复杂庞大系统,需要自动化工具来提高效率
持续集成-CICD
数据库进一步扩展
数据库的扩展方式
纵向扩展
缺点
纵向扩展的上限明显,后期性价比低
更大的单点故障
成本很高
横向扩展
执行横向扩展的方式
分配策略选择
在选择分片键时，最重要的标准之一是选择一个可以让数据均匀分布的键。
缺点
引入了更多的复杂性
热点问题
进一步分片,将热点拆分
重分片数据问题
使用一致性哈希处理
数据分配不均问题
链接和去规范化
细节
随着用户基数的增长，一台服务器已经无法满足需求，我们需要多台服务器：一台用于处理Web应用/移动应用的流量，另一台用作数据库
服务的设计中,用户直接连接到服务器
问题
一旦服务器离线,用户就无法访问网站
当非常多用户同时访问到web服务器,达到服务器的负载上限,用户会普遍感受到网站响应慢,或者无法连接到服务器
解决方案
负载均衡器
架构设计
第一版本有一定可用性的设计
•用户从DNS获取负载均衡器的IP地址。
•用户通过这个IP地址连接负载均衡器。
•HTTP请求被转发到服务器1或者服务器2上。
•Web服务器在从库中读取用户数据。
•Web服务器把所有修改数据的操作请求都转发到主库上，包括写、更新和删除操作。
读后总结章节内容
1.当单独服务的性能无法响应大量处理时,考虑进行拆分服务,通过更多的服务器去处理更多的请求
网站访问的请求流程
1用户输入域名,访问网站
2域名通过dns解析为ip地址,返回给请求端
3请求端使用ip地址构建http请求,发送到服务器
4web服务器,返回html页面,或者其他响应信息给请求端
演化过程
使用单个服务器,放置服务和数据库
子主题
将服务和数据库拆分到不通的服务器上
子主题
将服务分解为多个服务,通过负载均衡器进行统一对外
子主题
数据库的扩展-主从架构
子主题
子主题
缓存层的加入
子主题
加入缓存和CDN
子主题
加入无状态架构
子主题
子主题
加入数据中心
子主题
加入消息队列,日志记录,监控指标,自动化
子主题
加入数据库横向扩展-数据库分片
子主题
演化过程中引入各种不同组件的原因
引入负载均衡
为了解决横向扩展
引入主从数据库
为了解决大流量系统中,读多写少,数据库压力大问题
引入缓存
为了解决大流量系统中,读多写少,数据库压力大问题
引入CDN
为了提升静态资源访问效率,降低web服务器压力,将静态资源从就近的cdn中读取
引入无状态架构
为了方便横向扩展,处理用户的粘性会话问题,让一个用户可以访问任意服务器都得到相同的结果
引入数据中心
为了应对超大流量,单独机房,单独负载均衡器无法承接这些流量的问题
引入消息队列
为了缓解峰值流量,业务服务器无法及时处理,导致请求丢失等问题,将流量请求平稳的引入到业务服务器
缓存使用注意事项
什么时候使用缓存
如果对数据的读操作很频繁，而修改却不频繁，则可考虑使用缓存。因为被缓存的数据是存储在易变的内存中的，所以缓存服务器不是持久化数据的理想位置。
过期决策
执行过期策略是好的做法。一旦缓存中的数据过期，就应该将其从缓存中清除。如果不设置过期策略，缓存中的数据会一直被保存在内存中。
一致性
这关系到数据存储和缓存的同步。当对数据的修改在数据存储和缓存中不是通过同一个事务来操作的时候，就会发生不一致。
减轻出错的影响
单缓存服务器是系统中的一个潜在单点故障
驱逐策略
一旦缓存已满，任何对缓存添加条目的请求都有可能导致已有条目被删除，这叫作缓存驱逐。
使用CDN的注意事项
花销
设置合理的缓存过期时间
CDN回退
作废文件
支持大流量用户的技术要点
让网络层无状态
每一层都要有冗余
尽量多存储数据
支持多个数据中心
用cdn来承载静态资源
通过分片来扩展数据层
把不通架构分成不通的服务
监控你的系统
使用自动化工具
2 封底估算
关键词
封底估算
2的幂次
字节
操作耗时
可用性
SLA-服务水平协议
QPS-每秒查询量
重要内容
封底估算
封底估算是你将想象中的实验和常见性能指标数据结合而得出的一些估算值
这些值使你对何种设计可以满足系统需求有初步的概念
面试中经常问道的封底估算指标
QPS
峰值QPS
存储大小
缓存大小
服务器数量
细节
字节
1字节(byte)是8比特(bit)。一个ASCII字符占用1字节的内存（8比特）。表
字节的基本数量单位对比
子主题
操作耗时
计算机中常见的操作耗时
子主题
子主题
1 ns=10-9s
1 µs=10-6 s=1，000ns，
1 ms=10-3s=1，000 µs=1，000，000ns
高可用
概念
高可用性是指一个系统长时间持续运转的能力
可用性相关数字
SLA-服务水平协议
SLA（服务水平协议）是服务提供商普遍使用的一个术语。
它是你（服务提供商）和你的客户之间的协议，正式规定了你提供的服务应该正常运行的时间。
不同级别对应是示意图
子主题
如何进行封底估算
案例
基本信息
•推特有3亿月活用户。
•50%的用户每天都使用推特。
•用户平均每天发两条推文。
•10%的推文包含多媒体数据。
•数据要存储5年。
估算方式
qps-每秒查询量估算
•每日活跃用户(DAU)=300，000，000×50%=150，000，000
•推文QPS=150，000，000×2÷24小时÷3600秒≈3500
•峰值QPS=2×推文QPS≈7000
估算多媒体数据的存储量
•平均推文大小。
◆ tweet_id：64字节。
◆ 文本：140字节。
◆ 多媒体文件：1MB。
•多媒体数据存储量=150，000，000×2×10%×1MB=30TB/天
•5年的多媒体数据存储量=30TB×365×5≈55PB
小技巧
凑整和近似
写下假设
标明单位
面试中经常问道的封底估算指标
QPS
峰值QPS
存储大小
缓存大小
服务器数量
读后总结章节内容
封底估算是设计架构的基础,对于封底估算要根据当前已知信息去进行评估计算,最终得出一个初步的资源信息情况,用于指导后序系统设计
3 系统设计面试的框架
关键词
系统设计面试
模拟现实
模糊问题
开放问题
问正确的问题
设计边界
重要内容
有效系统设计面试的4个步骤
理解问题并确定设计的边界
要点
问正确的问题
做合适的假设
在提问过程中收集构建系统所需要的信息
不要害怕提问
常用的问题
我们要构建什么样的具体功能
该产品有多少用户
公司预计多久需要扩展系统
预计3个月,6个月,1年后系统的规模是什么样的
公司的技术栈是什么样的?有哪些服务可以直接使用,简化设计
目标
要在问题过程中,厘清需求不明确的地方
提议高层级的设计,并获得认同
要点
设计出高层设计
和面试官就这个设计达成一致
多和面试官协作
制作高层级设计
为设计定制一个初始蓝图
在白板或者纸张上使用关键组件画出框图
进行封底估算
评估你的初步设计是否满足系统需求
设计继续深入
•就系统的整体目标和功能范围，与面试官达成一致。
•勾画出系统整体设计的高层级蓝图。
•从面试官那里得到关于系统高层级设计的反馈。
•基于面试官的反馈，大概知道自己需要在哪些地方继续深入研究。
总结
可能的问题
面试官会对你之前的回答进一步追问
让你自由讨论一些其他问题
我们可能尝试的方向
•面试官可能想让你识别出系统的瓶颈并讨论潜在的改进方案。
总有一些地方可以改进。这是一个好机会，你可以展示批判性思维，给面试官留下好的最终印象。
永远不要说你的设计是完美的，不需要改进。
•给面试官扼要复述你的设计方案是有用的。
如果你提出了几个设计方案，那么这一点就特别重要。
在一个很长的会谈后，重新唤起面试官的记忆是对面试的最终结果有帮助的。
•故障场景（服务器故障、数据包丢失等）值得讨论。
•运维问题值得讨论。比如，怎样监控指标和错误日志？如何发布系统？
•怎样应对下一次扩展也是一个重要话题。
举个例子，如果你现在的设计支持100万用户，你需要改变什么才能支持1000万用户？
如果还有时间，你可以提出其他的改进点。
正确操作
总是向面试官寻求明确的解释。不要认为你的假设是对的。
•理解问题的要求。
•没有正确的答案或者最佳答案。为了解决年轻创业公司的问题而设计的方案与为了解决拥有数百万用户的成熟公司的问题而设计的方案是不相同的。要确保你理解了需求。
•让面试官知道你在想什么。与面试官持续沟通。
•如果有可能，请提出多个方案。
•一旦你和面试官就设计蓝图达成了一致，接下来就要深入讨论每个组件的细节。先设计最重要的组件。
•试探面试官的想法。一个好的面试官可以和你做队友一起来解决问题。
•永不放弃。
禁忌操作
•对于常见的面试问题没有做好准备。
•在没有弄清需求和假设之前就给出解决方案
•在面试一开始就讨论关于某一组件的大量细节。
请先给出高层级设计后再深入讨论细节。
•思路卡住的时候，自己干着急。
如果你一时找不到解题的突破口，去找面试官要点提示，不要犹豫。
•不沟通。
再说一次，一定要沟通。别在那里一个人默默思考。
•认为给出设计方案后面试就结束了。
记住，面试官说结束才是真的结束。要尽早且尽量频繁地征求面试官的反馈。
细节
系统设计面试的意义
系统设计面试模拟现实生活中两个同事一起解决模糊问题的过程。
在此过程中，两人共同想出一个满足要求的解决方案。
这个问题是开放的，并没有完美答案。
与你在设计过程中付出的努力相比，最终的设计结果并不重要。
你在这个过程可以展示自己的设计能
系统设计面试的目的
展示自己的设计能力
协作能力
压力下的工作能力
建设性解决模糊问题的能力
提问能力
系统设计面试中要注意的问题
不要过度设计
不要忽视权衡,执着在纯粹性
不要忽视设计的成本代价
不要有狭隘或者固执的表现
要多思考,不要不假思索快速给出答案
面试中每一步的时间分配
第一步：理解问题并确定设计的边界（3～10分钟）
第二步：提议高层级的设计并获得认同（10～15分钟）。
第三步：设计继续深入（10～25分钟）。
第四步：总结（3～5分钟）。
读后总结章节内容
在系统设计面试中:好消息是没有人期待你能给出完美的答案。
问正确的问题做合适的假设,是一种很重要的能力
在提问过程中收集构建系统所需要的信息
构建系统设计常用的问题
我们要构建什么样的具体功能
该产品有多少用户
公司预计多久需要扩展系统
预计3个月,6个月,1年后系统的规模是什么样的
公司的技术栈是什么样的?有哪些服务可以直接使用,简化设计
系统设计面试很容易就会陷入一些无法证明自己能力的小细节中。
你必须向面试官展示自己的能力。尽量不要陷入不必要的细节讨论。
你必须向面试官展示自己的能力。尽量不要陷入不必要的细节讨论。
面试过程中的操作
正确操作
总是向面试官寻求明确的解释。不要认为你的假设是对的。
•理解问题的要求。
•没有正确的答案或者最佳答案。为了解决年轻创业公司的问题而设计的方案与为了解决拥有数百万用户的成熟公司的问题而设计的方案是不相同的。要确保你理解了需求。
•让面试官知道你在想什么。与面试官持续沟通。
•如果有可能，请提出多个方案。
•一旦你和面试官就设计蓝图达成了一致，接下来就要深入讨论每个组件的细节。先设计最重要的组件。
•试探面试官的想法。一个好的面试官可以和你做队友一起来解决问题。
•永不放弃。
禁忌操作
•对于常见的面试问题没有做好准备。
•在没有弄清需求和假设之前就给出解决方案
•在面试一开始就讨论关于某一组件的大量细节。
请先给出高层级设计后再深入讨论细节。
•思路卡住的时候，自己干着急。
如果你一时找不到解题的突破口，去找面试官要点提示，不要犹豫。
•不沟通。
再说一次，一定要沟通。别在那里一个人默默思考。
•认为给出设计方案后面试就结束了。
记住，面试官说结束才是真的结束。要尽早且尽量频繁地征求面试官的反馈。
4 设计限流器
关键词
限流器
阈值
重要内容
API限流器的好处
预防拒绝服务攻击
降低成本
预防服务器过载
常见限流算法
代币桶算法-Token Bucket
原理
•代币桶是一个有预定义容量的容器。代币按照预定的速率被放入桶中。一旦桶被装满，就不再往里面添加代币。
代币桶的容量是4个代币。重新注入装置每秒将两个代币放入桶中。如果桶满了，多出来的代币就会溢出。
•每个请求消耗一个代币。当一个请求到达时，我们检查桶里有没有足够的代币。图4-5解释了它是如何工作的。
◆ 如果有足够的代币，每次请求到达时，我们就取出一个代币，然后这个请求就可以通过。
◆ 如果没有足够的代币，这个请求将被丢弃。
示意图
子主题
子主题
算法实现
参数
通大小
桶内最多有多少代币
重新注入代币的速度
每秒放进桶中多少代币
桶的数量
如果要对不同API有不同的限制则需要根据API去设置桶的数量
如果是每个IP有自己的限制频率,则每一个IP有一个自己的桶
如果是全局的桶,一个就可以
根据不同逻辑定义不同的桶逻辑
优缺点
优点
算法容易实现
内存使用率高
允许在很短时间内出现突发流量,只要还有代币,请求就可以通过
缺点
参数数量虽然不多,但是调整好两个参数需要比较丰富的经验
漏桶算法-leaking bucket
原理
当一个请求到达,系统检查桶是否已满,没有满就将请求添加到队列中
否则丢弃请求
定期从队列中获取请求并进行处理
示意图
子主题
算法实现
参数
桶的大小
出栈速度
每秒可以处理多少个请求
优缺点
优点
因为队列大小有限,所以内存使用率更高
因为对请求的处理是按照固定速率来处理的,所以漏洞算法很适合出栈速度稳定的场景
缺点
突发流量会使队列中积压大量的旧请求,如果请求不能被及时处理,最新的请求会丢失
该算法有两个参数，要调校好它们可能不那么容易。
固定窗口计数器算法-fixed window counter
原理
•将时间轴分成固定大小的时间窗口，并给每个时间窗口分配一个计数器。
•每到达一个请求，计数器的值都会加1。
•一旦计数器到达预先设定的阈值，新请求就会被丢弃，直到开始一个新的时间窗口。
示意图
子主题
子主题
算法实现
系统每分钟最多只允许通过5个请求，并且可用配额（阈值）在整分钟时会重置。在2:00:00和2:01:00之间有5个请求，在2:01:00和2:02:00之间又有5个请求。对于2:00:30至2:01:30这1分钟的时间窗口，有10个请求通过，而这是允许通过的请求数量的两倍。
优缺点
优点
内存使用率比较高
容易理解
每个单位时间窗口结束时,重置请求阈值,适用于某些特殊场景
缺点
在时间窗口边界流量激增,会导致通过请求超过设定阈值
滑动窗口日志算法-sliding window log
原理
固定窗口计数器算法有一个重大问题：在时间窗口的边界上，它允许更多的请求通过。滑动窗口日志算法解决了这个问题。它的工作原理如下所述。
•算法记录每个请求的时间戳。时间戳数据通常保存在缓存中，比如Redis中的有序集合。
•当新请求到达时，移除所有过时的时间戳。过时时间戳是指那些早于当前时间窗口起始时间的时间戳。
•将新请求的时间戳添加到日志中。
•如果日志的条数等于或者少于允许的请求数，则请求通过，否则请求被拒绝。
算法实现
当一个新请求在1:01:40到达时，所有在[1:00:40，1:01:40）范围内的请求都在最近的时间窗口中，所有早于1:00:40发送的请求都已过时。两个过时的时间戳1:00:01和1:00:30从日志中被删除。删除后，日志的条数变成2；因此，这个请求被允许通过。
示意图
子主题
优缺点
优点
实现流量的限制非常准确,在任何欢动的时间窗口中,请求的数量不会超过阈值
缺点
消耗内存过多
滑动窗口计数器算法-sliding window counter
原理
滑动窗口计数器算法是组合了固定窗口计数器算法和滑动窗口日志算法的方法。
算法实现
假设限流器每分钟最多允许通过7个请求，然后前一分钟有5个请求，当前分钟有3个请求。
当一个新请求出现在当前分钟的30%的位置时，滑动窗口所允许的请求数量通过下面的公式来计算：
当前窗口的请求数+之前窗口的请求数×滑动窗口和之前窗口的重合率
示意图
子主题
优缺点
优点
•它平滑了流量中的波动，因为当前时间窗口内请求的速率是基于前一个时间窗口内请求的平均速率计算出来的。
•对内存的使用很高效。
缺点
滑动窗口计数器算法的缺点是，它只对不那么严格的回溯窗口起作用。该算法只是对真实流量速率进行了近似估计，因为它假设前一个窗口中的请求是均匀分布的。尽管如此，这个问题可能并没有看起来那么严重。
细节
限流器-设计过程
理解并确认设计的边界
提问过程
候选人：我们要设计什么样的限流器？是客户端限流器还是服务器端API限流器？
面试官：好问题。我们重点讨论服务器端API限流器。
候选人：这个限流器是基于IP地址、用户ID还是其他属性来限制API请求速率的？
面试官：限流器需要足够灵活来支持不同的限流规则。
候选人：这个系统的规模如何？是为初创公司还是为有大量用户的大公司创建的？
面试官：该系统必须能处理大量请求。
候选人：这个系统是在分布式环境中运行的吗？
候选人：这个系统是在分布式环境中运行的吗？
候选人：限流器需要作为一个独立服务还是应该在应用程序的代码里实现？
面试官：这取决于你如何设计。
候选人：我们需要通知被限流的用户吗？
面试官：是的。
得出的需求结论
•准确限制过量的请求。
•低延时。限流器不能拖慢HTTP响应时间。
•尽量占用较少的内存。
•这是一个分布式限流器，可以在多个服务器或者进程之间共享。
•需要处理异常。当用户的请求被拦截时，给用户展示明确的异常信息。
•高容错性。如果限流器出现任何问题（比如某个缓存服务器宕机），不能影响整个系统。
提议高层级的设计并获得认同
相关问题
在哪里实现限流器
客户端
服务器
子主题
中间件作为限流器
子主题
当前公司的技术栈是什么样的
使用什么样的限流算法
选择自实现限流器,还是使用商业版的限流器
高层级架构
基本理念
我们需要一个计数器来记录有多少请求是由同一个用户、同一个IP地址等发来的。
如果计数器的值超出设定的阈值，请求就不允许通过。
计数器存储在哪
数据库
速度太慢
redis中央缓存
速度比较快,并且有过期策略,可以更好的去对限流做支持
设计继续深入
深入的问题
流量限制规则如何创建的?
这些流量限制规则存储在哪里?
如何处理限流的请求?
客户端如何知道请求有没有被限流呢？
流量限制规则
限制规则可以写在配置中
示例
子主题
子主题
超过流量的限制
如果一个请求被限流，API会给客户端返回HTTP响应码429（请求过多）。
根据应用场景，我们有可能会把超过阈值的请求放入队列，之后再处理。比如，一些订单请求因为系统过载被限流了，我们可以保存这些订单以便稍后处理。
返回结果
当用户发送的请求过多时，限流器将向客户端返回HTTP响应码429（表示请求太多）和X-Ratelimit-Retry-After响应头。
限流后在http头中添加限定信息
•X-Ratelimit-Remaining：在当前时间窗口内剩余的允许通过的请求数量。
•X-Ratelimit-Limit：客户端在每个时间窗口内可以发送多少个请求。
•X-Ratelimit-Retry-After：在被限流之后，需要等待多少秒才能继续发送请求而不被拦截。
详细设计
示意图
子主题
限流器的基本工作方式
•从Redis中读取计数器的值。
•检查计数器值加1后是否超过了阈值。
•如果没有，就把计数器的值在Redis中加1。
分布式系统中的限流器
分布式系统中限流器的问题
竞争条件
在高并发环境下,限流器的整个流程如果不是事务性的,那么就存在发生错误的可能性
子主题
解决方案
锁
但是会有效率问题
在redis中可以使用lua脚本和redis的有序集合数据结构
同步问题
为了支持百万量级的用户，一个限流器有可能不足以处理所有的流量
使用多个限流器时，限流器之间就必须同步。
问题
示意图
子主题
子主题
解决方案
使用中心化的数据存储-redis
性能优化
多数据中心
近距离数据处理
边缘服务器降低延时
最终一致性模型来同步数据
降低数据同步的难度
监控
通过监控去检查限流是否生效
流量限制算法是否有效
流量限制规则是否有效
总结
限流算法
•代币桶算法。
•漏桶算法。
•固定窗口计数器算法。
•滑动窗口日志算法。
•滑动窗口计数器算法。
限流类型
硬流量限制是指请求数量不能超过阈值。
软流量限制是指请求数量可以在短时间内超过阈值。
限流的位置-在不通层级做限制
读后总结章节内容
5 设计一致性哈希系统
关键词
一致性
哈希
一致性哈希
重新哈希问题
哈希空间
哈希环
虚拟节点
重要内容
一致性哈希的作用
为了实现横向扩展,在服务器之间高效和均匀的分配请求和数据
重新哈希问题
常规的给n个服务器进行负载均衡
服务器序号=hash(key)%N（N代表服务器池的大小）
这个方法在服务器池的大小固定不变的时候效果很好，并且数据的分布是均匀的。
当服务器发生增加或减少时出现请求/分配到不同的位置
大部分的键都被重新分配了，不仅仅是原来存储在宕机服务器(server1)中的那些键。
这意味着当server1宕机时，大部分缓存客户端都会连接错误的服务器来获取数据。
这会导致大量的缓存未命中(Cache Miss)。
一致性哈希
概念
一致性哈希是一种特殊的哈希。
如果一个哈希表被调整了大小，那么使用一致性哈希，则平均只需要重新映射k/n个键，这里k是键的数量，n是槽(Slot)的数量。
对比来看，在大多数传统的哈希表中，只要槽的数量有变化，几乎所有的键都需要重新映射一遍
一致性哈希中的重要概念
哈希空间
哈希环
虚拟节点
工作方式
1.构建一个足够大的hash空间,创建出用于映射服务器节点的空间,并进行首尾相连构建一个hash环
2.将服务器根据指定的规则,比如ip或者编号,通过hash函数映射到hash空间中的不同位置
查找某个服务器
为了确认某个键存储在哪个服务器上
一个键过来,根据特定规则,使用hash函数将键,打到hash环上,然后顺时针向下找服务器
添加服务器
当进行添加服务器时,新的节点映射到hash环上某个位置
这个服务器,会均摊一部分键
其他部分的键是不会有变动
移除服务器
当移除一个服务器
原本的节点移出
原本这个节点的负载会移动到当前移出节点的下一个节点,其他的键不会有变化
存在的问题
第一，考虑到可以添加或移除服务器，所以很难保证哈希环上所有服务器的分区大小相同。
分区是相邻服务器之间的哈希空间。在哈希环上分配给每个服务器的分区可能很小，也可能很大。
分区是相邻服务器之间的哈希空间。在哈希环上分配给每个服务器的分区可能很小，也可能很大。
第二，有可能键在哈希环上是非均匀分布的。
解决存在的问题
使用虚拟节点
将一个服务器虚拟为大量节点,分散到hash环
这时候可以解决非均匀分布的问题
好处
•添加或者移除服务器的时候，需要重新分配的键最少。
•更容易横向扩展，因为数据分布得更均匀。
•减轻了热点键问题。过多访问一个特定分区可能会导致服务器过载。
应用位置
•亚马逊Dynamo数据库的分区组件。
•Apache Cassandra集群的数据分区。
•Discord聊天应用。
•Akamai内容分发网络
•Maglev网络负载均衡器。
细节
读后总结章节内容
6 设计健值存储系统
关键词
键值存储
非关系型数据库
CAP理论
Gossip协议
重要内容
CAP理论-分布式系统的重要理论
基础概念
C-一致性
指的是所有的客户端在相同的时间点看到的是同样的数据，而不管它们连接的是哪个节点（服务器）。
A-可用性
指的是即便有节点发生故障，任意客户端发出的请求都能被响应。
P-分区容错性
分区意味着两个节点之间的通信中断。
分区容错性的意思是尽管网络被分区，系统依然可以继续运行。
理论内容
CAP理论提出，如果要支持上述三个特性中的两个，就必须牺牲剩下的那一个
示意图
子主题
不同选择
CP系统
支持一致性和分区容错性，但牺牲了可用性。
AP系统
支持可用性和分区容错性，但牺牲了一致性。
CA系统
支持一致性和可用性，但牺牲了分区容错性。
因为网络故障是无法避免的，所以分布式系统必须容忍网络分区。
因此，在现实世界中CA系统不可能存在。
细节
设计的边界
键值对的大小范围
是否可以存储大数据
高可用性有什么要求
对于可扩展性有什么要求,系统可以扩展以支持大数据集
自动伸缩
基于流量情况自动添加/移出服务器
可调节的一致性
低延时
单服务器的键值存储
方式
把键值对存储在哈希表中，将所有的数据都保存到内存里。虽然内存访问起来很快，但因为空间有限，
可能无法将所有数据都放在里面。为了在单服务器上存储更多的数据，
优化
压缩数据
只把频繁使用的数据存储在内存里,其他的则放在硬盘
分布式键值存储
构建分布式键值存储系统的核心技术和组件
数据分区
存在的挑战
•将数据均匀地分布在多个服务器上。
•添加或者移除节点时，尽量减少数据的迁移。
解决方案
一致性hash
数据复制
为了实现高可用性和可靠性，数据必须在N个服务器上异步复制
为了提高可靠性，数据副本被存储在不同的数据中心，并且数据中心之间通过高速网络连接。这样即使一个数据中心发生故障，其他数据中心仍然可以提供服务，确保系统的可用性和容错性。
一致性
因为数据被复制到多个节点上，所以副本之间必须同步。仲裁一致性(QuorumConsensus)可以保证读写操作的一致性
一致性模型
所需前置定义内容
N：代表副本的数量。
W：代表写操作的Quorum大小。一个写操作要被认为是成功的，必须获得W个副本的确认。
R：代表读操作的Quorum大小。一个读操作要被认为是成功的，必须至少获得R个副本的响应。
W、R和N的配置是典型的延时和一致性之间的权衡。
如果W=1或者R=1，因为协调者只需要等待任意一个副本的响应，所以一个操作很快会返回。
如果W＞1或者R＞1，系统就会有更好的一致性，但是查询会变慢,因为协调者必须等待最慢的副本响应。
如果W+R＞N，意味着在进行读取或写入操作时，至少会有一个共同的副本同时参与，这个共同的副本会包含最新的数据，因此在这种情况下可以保证强一致性。
配置N、W和R来适配我们的使用场景
如果R=1且W=N，则系统针对快速读进行了优化。
如果W=1且R=N，则系统针对快速写进行了优化。
如果W+R＞N，则强一致性得到保证（通常配置成N=3，W=R=2）。
如果W+R≤N，则不一定能保证强一致性。
一致性模型分类
强一致性模型
任何读操作返回的值都是最新写入的数据。客户端永远不会看到过时的数据。
弱一致性模型
随后的读操作返回的可能不是最新的值。
最终一致性模型
这是弱一致性的一种特殊形态。经过足够长的时间，所有的数据更新都会传播开来，并且所有副本会变得一致。
不一致性的解决方案
复制副本提供了高可用性但会导致副本之间的数据不一致
解决方案
版本控制
版本控制的意思是每次修改数据都生成一个新的不可变的数据版本。
向量时钟
作用
没有明确的方法来解决最后两个版本之间的冲突。
为了解决这个问题，我们需要一个版本控制系统来检测和解决冲突。
向量时钟是解决这个问题的常用方法。
概念
向量时钟是与数据项相关联的[服务器，版本]对。
它可以用于检查一个版本是先于还是后于其他版本，或者是否与其他版本有冲突。
缺点
第一，向量时钟增加了客户端的复杂性，因为客户端需要实现冲突解决逻辑。
第二，向量时钟中的[服务器，版本号]数据对可能会迅速增长
故障处理
故障检测
判定故障的标准
在分布式系统中，不能仅凭服务器A说服务器B出了故障就断定服务器B真的出了故障。
通常，至少需要两个独立的信息源才能标记一个服务器出故障了。
去中心化的故障检测方法
Gossip协议
•每个节点维护一个节点成员列表，其中包括成员ID和心跳计数。
•每个节点定期地增加自己的心跳计数
•每个节点定期地给一组随机节点发送心跳信号，这些节点又会将心跳信号接着传递给另一组节点。
•一旦节点收到心跳信号，就会据此更新成员列表。
•如果心跳计数在预定时间内没有增加，该成员就被认为宕机了。
处理临时故障
通过Gossip协议发现故障后，系统需要采取某种机制来确保可用性。在严格的仲裁协议中，读写操作可能会被阻塞，
松散仲裁”(Sloppy Quorum)
用来提高可用性
在哈希环上最先发现的W个正常工作的服务器来进行写操作，并选择在哈希环上最先发现的R个正常工作的服务器来进行读操作。
发生故障的服务器将被忽略。
暗示性传递(Hinted Handoff)
如果一个服务器因为网络或者服务器故障而不可用，另一个服务器会临时处理请求。当该服务器恢复运行时，变更会被推送回来以实现数据一致性。
暗示性传递被用来处理临时故障
处理永久故障
反熵协议(Anti-entropy Protocol)
保持副本同步
反熵需要比较副本上的每条数据并将每个副本都更新到最新的版本。
Merkle树
概念
哈希树也叫作Merkle树，对于每个非叶节点，它的标记是基于其子节点的标签或值进行的哈希运算得到的结果。
如果该节点是叶子节点，那么其标记直接由该叶子节点的值进行哈希运算得到。
作用
哈希树可以高效和安全地验证大型数据结构的内容。
Merkle树被用来检测不一致性并最小化数据传输量。
如何构建Merkle树
第一步：把键空间分成不同的桶,桶用作根节点以维护树的有限深度。
第二步：一旦创建了桶，就把桶里的每个键都用一致哈希方法(Uniform HashingMethod)计算哈希值
第三步：为每个桶创建一个哈希节点
第四步：向上构建树，直到根节点，通过计算子节点的哈希值来得到父节点的哈希值
比较两个Merkle树是从比较根节点的哈希值开始的。
如果根节点的哈希值匹配上了，则表示两个服务器有同样的数据。
如果根节点的哈希值不一样，那么采用“先左后右”的顺序来比较子节点的哈希值。
你可以遍历这两个Merkle树来找出哪些桶不同步并同步这些桶。
处理数据中心故障
因为电力中断、网络故障、自然灾害等原因，数据中心有可能发生故障。
要构建一个可以处理数据中心故障的系统，在多个数据中心之间复制数据至关重要。
就算某个数据中心完全无法工作，用户依然可以从其他数据中心获取数据。
系统架构图
分布式键值存储架构的特点
•客户端与键值存储系统之间通过简单的API通信：get(key)和put(key，value)。
•协调者是一个节点，在客户端和键值存储系统之间充当代理。
•节点通过一致性哈希分布在哈希环上。
•系统完全去中心化，所以添加和移除节点的工作完全可以自动进行。
•数据被复制到多个节点。
•因为每个节点有同样的职责，所以没有单点故障
写路径
写请求在一个节点中发生的事情-基于Cassandra的架构
1.写请求在提交日志(Commit Log)文件中被持久化。
2.数据被保存在内存缓存中。
3.当内存缓存已满或者达到预定的阈值时，数据会被刷新到硬盘上的SSTable
SSTable（Sorted-String Table，有序字符串表）
SSTable（Sorted-String Table，有序字符串表）是一个排过序的<键，值>对列表。
读路径
读请求的过程
1.系统首先检查数据是否在内存缓存中，如果不在，则转到第2步。
2.检查布隆过滤器。
3.通过布隆过滤器确定哪个SSTable可能包含这个键。
4.SSTable返回结果数据。
5.结果数据被返回给客户端。
高效查找哪个SStable中包含所需数据
处理方案
布隆过滤器
读后总结章节内容
问题/目标
存储大数据的能力
使用一致性哈希把负载分散到各个服务器上
高可用的读
数据复制
多数据中心
高可用的写
版本控制,通过向量时钟来制定冲突解决方案
数据集分区
一致性哈希
增量可扩展性
一致性哈希
异质性
一致性哈希
可调一致性
仲裁一致性
处理暂时故障
松散仲裁
暗示性传递
处理永久故障
merkle树
处理数据中心故障
跨数据中心复制
7 设计分布式系统中的唯一ID生成器
关键词
唯一ID
雪花算法
UUID
工单服务器
多主复制
时钟同步
重要内容
1 问题边界
唯一ID的特征是什么
ID必须是唯一的可排序的
对每个新纪录,ID是否递增1
ID随着时间增加但幵不一定只增加1。在同一天中，夜里创建的ID要比早上创建的大
ID只包含数字么
是的
对ID的长度有什么要求
ID长度应该是64位
系统规模多大
系统应该可以每秒生成10，000个ID。
2 高层设计
生成唯一ID的方法
•多主复制(Multi-master Replication)。
实现方式
利用了数据库的自增特性。
我们并不是把下一个ID加1，而是加k，这里k是正在使用的服务器数量。
有2台服务器的情况下,生成的下一个ID等于同一个服务器上的前一个ID加2
缺点
很难与多个数据中心一起扩展，需要进行额外的同步和协调操作。
•在分布式环境下，多个服务器同时生成ID，可能导致ID并不连续，也即ID并不随时间递增。
•当服务器被添加或者移除时，ID不能很好地随之变化。
•通用唯一标识符(Universally UniqueIdentifier，UUID)。
概念
UUID是另一种获取唯一ID的简单方法。
UUID是一个128位的数字，用来标识计算机系统中的信息。
UUID重复的概率非常低。
这里引用维基百科的说法，“每秒产生10亿个UUID且持续约100年，产生一个重复UUID的概率才达到50%。”。
UUID可以独立地生成而不需要在服务器之间做任何协调。
优点
•生成ID很简单。服务器之间不需要任何协调，所以不会有任何同步问题。
•系统易于扩展，因为每个Web服务器只负责生成它们自己使用的ID。ID生成器可以很容易地随Web服务器一起扩展。
缺点
ID长128位，但是我们要求的是64位。
•ID并不随时间增加。
•ID可能是非数字的。
•工单服务器(Ticket Server)。
原理
这个方法的思想是利用中心化的单数据库服务器（工单服务器）的自增特性
优点
•ID为数字。
•容易实现，适用于中小型应用。
缺点
其缺点是存在单点故障。单个工单服务器意味着，如果这个服务器发生故障，所有依赖于它的系统就都会面临问题。为了避免单点故障，我们可以设置多个工单服务器。但是这会引入新的挑战，比如数据同步问题。
•推特的雪花(Snowflake)系统。
原理
我们不直接生成一个ID，而是把一个ID分成不同的部分。
一个64位ID的构成。
子主题
组成部分
预留位
1
时间戳
41
数据中心ID
5
机器ID
5
序列号
12
优点
id为数字
数据递增
可以分布式或者自行生成
3 深入设计
选择雪花算法后进一步进行操作
雪花算法组成部分
预留位
1
时间戳
41
数据中心ID
5
机器ID
5
序列号
12
算法细节
时间戳和序列号是在ID生成器运行后才生成的。
数据中心ID和机器ID
数据中心ID和机器ID通常在起始阶段就选好了，一旦系统运行起来，这两个部分就是固定的。
对数据中心ID和机器ID所做的任何更改都需要仔细审查，因为对这些值的意外改动可能会导致ID冲突。
时间戳
41位的时间戳是ID中最重要的部分。随着时间的推移，时间戳不断增长，因此ID可以按时间排序。
41位能表示的最大时间戳是241-1，即2，199，023，255，551毫秒(ms)，约等于69年（计算方法为2，199，023，255，551÷1000÷365÷24÷3600）。
这意味着ID生成器可以工作约69年。
如果我们把纪元开始时间定制得离今天的日期足够近，就可以延迟溢出时间。
69年后，我们需要一个新的纪元时间或者采用别的技术来迁移ID。
序列号
序列号有12位，相当于4096种组合(212)。
这个部分一般是0，除非在1毫秒内同一个服务器生成了多个ID。
理论上，一个服务器每毫秒最多生成4096个新ID。
延伸问题
时钟同步
在我们的设计里，我们假设生成ID的服务器都有同样的时钟。
但是，当服务器运行在多核上时，这个假设可能并不成立。在多机器的场景中也存在同样的挑战。
时钟同步的解决方案不在本书的讨论范围内；
但是，知道这个问题的存在是很重要的。
网络时间协议(NTP)是这个问题最流行的解决方案
调整ID各部分的长度
对于低并发且长时间持续运行的应用，减少序列号部分的长度，增加时间戳部分的长度，生成的ID会更高效。
高可用性
因为ID生成器是一个非常关键的系统，所以它必须是高可用的。
细节
读后总结章节内容
设计唯一ID生成器先要考虑清楚数据边界范围情况
数据量情况
新增数据情况
是否有排序要求
是否有特殊要求
唯一ID生成的算法选择
简单的使用数据库id
没有数字或者其顺序要求可以直接使用UUID
对于工单服务,这个存在理解不深,不做深入讨论,感觉上就是一个单独服务出id调用就返回一个id就好
雪花算法核心是分段,使用一个数字的不同位,表示不同的意义,最终得到一个id结果
8 设计URL缩短器
关键词
URL
重定向
301重定向
永久重定向
302重定向
暂时重定向
基数转换
重要内容
1 确认问题边界
你能给一个URL缩短器如何工作的例子吗？
假设https://www.systeminterview.com/q=chatsystem&c=loggedin&v=v3&l=long是原URL，
你的服务应该可以创建一个更短的URL（短链接）：https://tinyurl.com/y7keocwj，将其作为原URL的别名。
如果点击这个短链接，它就可以把你重新导向至原URL。
业务量有多大？
每天要生成1亿个URL。
短链接的长度是多少？
越短越好。
短链接中允许有哪些字符？
短链接可以是数字(0～9)和字母(a～z、A～Z)的组合。
短链接可以被删除或者更新吗？
为简单起见，我们假设短链接不能被删除或者更新。
2 封底估算
•写操作：每天生成1亿个URL。
•写操作：每天生成1亿个URL。
•每秒的读操作数：假设读操作与写操作的比例是10∶1，那么每秒的读操作数是1160×10=11，600。
•假设URL缩短器会运行10年，这意味着我们必须支持1亿×365×10=3650亿条记录。
•假设URL的平均长度是100个字符，那么10年的存储容量需求是：3650亿×100字节≈36.5TB。
3 高层设计
API端点
缩短URL
重定向URL
URL重定向
重定向的方式
301重定向
301重定向：意味着所请求的URL“永久”移动到长URL。
因为是永久重定向，所以浏览器会缓存该响应，以后对同一个URL的请求就不会发给URL缩短服务器了，而会将其直接重定向到长URL服务器。
302重定向
302重定向：意味着URL“暂时”移动到长URL，
这也意味着对于同一个URL的后续请求会先发给URL缩短服务器，然后它们才会被重定向到长URL服务器。
根据不通需求选择不同重定向方式
如果降低服务器的负载是需要优先考虑的事项，使用301重定向就是合适的，因为对于同一个URL只有第一次请求会被发到URL缩短服务器上。
如果数据分析很重要，那么302重定向就是更好的选择，因为它可以更轻松地跟踪点击率和点击来源。
实现方式
实现URL重定向的最直观的方法就是使用哈希表。
假设哈希表存储了<shortURL，longURL＞键值对，可以通过以下步骤实现URL重定向。
•获取长URL：longURL=hashTable.get(shortURL)。
•一旦获取了长URL，就实施URL重定向。
生成缩短URL的方式
为了支持URL缩短的使用场景，我们必须找到一个哈希函数fx，它可以把长URL(longURL)映射成哈希值
这个哈希函数必须满足
•每个长URL必须可以通过哈希函数转换成一个哈希值(hashValue)。
•每个哈希值可以被映射回原始的长URL。
4 深入设计
数据模型
根据我们的封底估算,我们选择缓存作为数据存储方式基本上不现实的
我们最好选择在关系型数据库或者NewSql中存储我们的短链接到长链接的键值对
hash函数
根据我们的封底估算我们要支持存储千亿级别的数据
根据我们了解到的边界信息,我们的hash函数中可以有数字和大小写字幕,这样一位中可以有62种可能的字符,也就是62进制
这样我们需要确认下62的多少次幂能够到达千亿
如何设计hash函数
目标
实现一个hash函数将长链接hash成7位的字符串
实现方式
哈希+解决冲突
hash函数算法
crc32
md5
sha-1
一个url通过对应算法得出的长度表
子主题
我们只要7位返回的结果都太长了
截取7位
处理hash碰撞/冲突
检查过程
子主题
快速检查的方式
布隆过滤器
缺点
可能存在hash冲突
base 62
实现方式
将长URl存储到数据库,得到一个数据id
将数据id通过base64转化为字符串,作为短链接
缺点
需要依赖唯一ID生成器
如果新纪录的ID会增加1,name容易推导出其他短URL是什么,这是一个安全隐患
短URL长度不固定,会随着ID变化
URL缩短
缩短的流程
子主题
URL重定向
重定向流程
子主题
延伸问题
限流器
web服务器伸缩
数据库扩展
数据分析
可用性,一致性,可靠性
细节
读后总结章节内容
9 设计网络爬虫
关键词
爬虫
dfs-深度优先
bfs-广度优先
礼貌性
前线url
重要内容
爬虫的作用
搜索引擎索引
这是最常见的使用场景。爬虫收集网页并为搜索引擎创建本地索引。例如，Googlebot就是谷歌搜索引擎背后的爬虫。
网页存档
这是指从网上收集信息并保存起来以备未来使用的过程。很多国家图书馆运行爬虫来存档网站，比如美国国会图书馆和欧盟网页存档。
网络挖掘
互联网的迅猛发展为数据挖掘提供了前所未有的机会。网络挖掘帮助我们从互联网上发现有用的信息。比如，顶级金融公司使用爬虫来获取关键公司的股东会议信息和年报，从而了解它们的动向。
网络监控
爬虫可以帮助监控互联网上的版权和商标侵权行为。例如，Digimarc公司利用爬虫发现盗版作品并上报。
爬虫基本算法
1.给定一组URL，下载这些URL对应的所有网页。
2.从这些网页中提取URL。
3.将新的URL添加到需要下载的URL列表里。然后重复执行这3个步骤。
1 问题边界
爬虫的主要目的是什么？是用于搜索引擎索引、数据挖掘还是其他什么？
搜索引擎索引。
爬虫每个月收集多少网页？
10亿个。
包括哪些内容类型？是只有HTML页面，还是也包括其他内容类型，比如PDF文件、图片等？
仅包括HTML页面。
我们需要考虑新增的或者有更新的网页吗？
是的，我们应该要考虑新增的或者有更新的网页。
我们需要保存从网络上爬取的HTML页面吗？
是的，最多要保存5年。
我们如何处理有重复内容的网页？
忽略有重复内容的网页。
爬虫的一些额外的点
可扩展性：互联网很庞大，存在数十亿的网页。爬虫需要通过并行化来高效爬取信息
健壮性：网络上充满了陷阱。糟糕的HTML页面、无响应的服务器、宕机、恶意链接等都很常见。爬虫必须应对所有这些极端场景。
礼貌性：爬虫不应该在很短的时间间隔内对一个网站发送太多请求。
可扩展性：系统应该具有灵活性，只需要做最少的更改就能支持新的内容类型。举个例子，如果我们将来想要爬取图片，应该不需要重新设计整个系统。
2 封底估算
假设每个月要下载10亿个网页。
QPS：1，000，000，000÷30÷24÷3600≈400，即每秒约400个网页。
•峰值QPS=2×QPS=800。
•假设平均每个网页的大小是500KB。
•每月需要存储1，000，000，000×500KB=500TB。
•假设数据要保存5年，则500TB×12×5=30PB，即需要30PB的存储空间来保存5年的内容。
3 高层设计
爬虫的工作流程
示意图
子主题
种子url
爬虫使用种子URL作为爬行的起点。
url前线
爬虫状态
即将下载
已经下载
用来存储即将下载的URL的组件叫URL前线,你可以把它看作一个先进先出(FIFO)的队列
html下载器
HTML下载器从互联网上下载网页。要下载的URL由URL前线来提供。
dns解析器
要下载网页，必须将URL转换成IP地址。HTML下载器请求DNS解析器来获取URL对应的IP地址。
内容解析器
网页被下载以后，必须进行解析和校验，因为有问题的网页可能会引发问题且浪费存储空间。在爬虫服务器中实现内容解析器会减慢爬虫的速度。因此，内容解析器是一个独立的组件。
已见过的内容？
完成这个任务的一个高效方法是比较两个网页的哈希值。
内容存储
存储HTML内容的存储系统。选择什么样的存储系统，取决于数据的类型、大小、访问频率、生命周期等因素。硬盘和内存都被用到。
url提取器
URL提取器从HTML页面中解析和提取链接
url过滤器
URL过滤器用于排除特定内容类型、文件扩展名、问题链接和“黑名单”网站的URL。
已见过的URL？
“已见过的URL？”是一种数据结构，可以用来追踪记录已访问过的或者已经在URL前线里的URL。
“已见过的URL？”可以帮我们避免多次添加同一个URL，重复添加URL会增加服务器负载并导致潜在的无限循环。
url存储
URL存储用于保存已访问过的URL。
4 深入设计
链接遍历的方式
dfs-深度优先遍历
bfs-广度优先遍历
概念
BFS是爬虫常用的方法，通过先进先出(FIFO)队列来实现。在一个FIFO队列中，URL按照它们入列的顺序出列
存在问题
同一个网页的大部分链接都指向同一个主机。如图9-5所示，wikipedia.com中的所有链接都是内部链接，这使得爬虫忙于处理来自同一个主机(wikipedia.com)的URL。当爬虫尝试并行下载网页时，维基百科的服务器会被大量请求“淹没”。这样做被认为是“不礼貌”的。
标准的BFS并没有考虑URL的优先级。互联网很大，不是每个网页都有同样水平的质量和同等重要性。因此，我们可能想要基于网页的排名、网络流量、更新频率等对URL进行排序，以便优先处理某些网页。
URL前线
URL前线是一个重要组件，它是一个存储待下载URL的数据结构，能确保爬虫礼貌地访问网页，确定URL优先级并保证内容新鲜度
礼貌性
确保礼貌性的大致思路是，从同一个主机每次只下载一个网页。可以在两次下载任务之间加入一定的延时。礼貌性约束是通过维护网站主机名和下载线程(Worker)的映射来实现的。每个下载线程都有独立的FIFO队列且只下载这个队列里的URL。
子主题
队列路由器
确保每个队列(b1，b2，…，bn)只包含来自同一个主机的URL。
映射表
把每个主机映射到队列中
FIFO队列（从b1到bn）
每个队列只包含来自同一个主机的URL。
队列选择器
每个Worker都被映射到一个FIFO队列，它只下载来自这个队列的URL。队列选择器实现队列选择的逻辑。
细节
读后总结章节内容
10 设计通知系统
关键词
重要内容
细节
读后总结章节内容
11 设计news feed系统
关键词
重要内容
细节
读后总结章节内容
12 设计聊天系统
关键词
重要内容
细节
读后总结章节内容
13 设计搜索自动补全系统
关键词
重要内容
细节
读后总结章节内容
14 设计视频分享系统
关键词
重要内容
细节
读后总结章节内容
15 设计云盘
关键词
重要内容
细节
读后总结章节内容
16 设计支付系统
关键词
重要内容
细节
读后总结章节内容
17 设计指标监控和告警系统
关键词
重要内容
细节
读后总结章节内容
我读书前预留的问题
为什么
解决什么问题
如何做
要设计一个系统或者设计一个功能,需要先考虑哪些事情
如何进行对问题的细化?
这本书主要想表达什么?
我从书中收获了什么
设计一个功能的基本框架
边界问题
设计这个服务的边界是什么样的?
封底估算
根据边界,评估出大概会使用多少资源
服务器成本
存储成本
网络成本
高层设计
设计这个功能会涉及哪些部分,有什么选型,大概怎么选
深入设计
对于高层设计中的内容进行细化,得出一个基本可用方案
延伸问题
会有哪些延伸问题
高可用
高可靠
数据分析
数据库扩展
服务扩展
限流
书中我觉得最有价值的话
书籍中的问题
0 条评论
下一页
