system-design-interview笔记
限流器
-
放在哪里?
- 客户端, 容易被伪造绕过
- 服务端应用代码, 灵活性高, 但占据工程资源
- 云上微服务, api网关等, 灵活性低
-
经典算法:
-
令牌桶: 固定速率产生令牌, 每个请求消耗令牌
- pros: 容易实现, 内存占用少, 允许突发流量
- cons: 调参困难, 可能需要不断填充桶
-
漏桶: 请求进入一个定长FIFO队列, server给定速度从队列取数据处理
- pros: 容易实现, 内存占用少, 请求以固定速率处理
- cons: 突发请求占据队列使得新请求得不到处理, 调参困难,可能需要不断填充桶
-
固定窗口计数器: 每一个给定时间窗口进行计数,例如每分钟100个请求
- pros: 容易实现, 内存占用少
- cons: 突发请求可以达到两倍限制的QPS(在窗口边缘有突刺)
-
滑动窗口日志: 记录请求时间戳, 数据保存在redis等缓存,每当新请求进来的时候把过时时间戳删除, 如果请求时间 戳比时间窗口的最低值还低, 拒绝请求
- pros: 速率限制准确
- cons: 内存开销大, 需要存储多个时间戳
-
滑动窗口计数器: 某时刻限制请求数 = 窗口上限 - 上一个窗口请求数 * 这一个窗口的和上一个窗口的重叠百分比。例如, 窗口为每分钟1000, 上一分钟800, 在这一分钟的30秒时, 限制这一分钟窗口的请求数最多为 1000 - 30 / 60 * 800 = 600
-
相当于假设上一个窗口的平均速率
-
pros: 平滑了流量峰值, 内存高效(只需要计数)
-
cons: 不太严格, 然而其实可以
然而，这个问题可能并不像它看起来那么糟糕。 根据Cloudflare[10]所做的实验，在4亿个请求中，只有0.003%的请求被错误地允许或限制速率
-
-
超过速率限制
如果一个请求被限制了速率，API会向客户端返回一个HTTP响应代码429（请求太多）。根据不同的使用情况，我们可能会将速率受限的请求排队等候以后处理。 例如，如果一些订单由于系统过载而受到速率限制，我们可以保留这些订单以便以后处理。
限流器请求头
一个客户如何知道它是否被节流？客户端如何知道在被节流之前允许的剩余请求的数量？答案就在HTTP响应头中。限流器向客户端返回以下 HTTP 标头：
- X-Ratelimit-Remaining：窗口内允许请求的剩余数量
- X-Ratelimit-limit：它表示客户端在每个时间窗口可以进行多少次调用
- X-Ratelimit-Retry-After：等待的秒数，直到你可以再次提出请求而不被节流。
当用户发送过多请求时，将向客户端返回 429 too many requests 错误和 X-Ratelimit-Retry-After 标头。
- 规则被存储在磁盘上。工作者经常从磁盘 中提取规则，并将其存储在高速缓存中。
- 当客户端向服务器发送请求时，该请求首先被发送到限流中间件。
- 限流中间件从缓存中加载规则。它从Redis缓存中获取计数器和最后一次请求的时间戳。根据响应，限流器决定：
- 如果请求没有速率限制，它将被转发到API服务器。
- 如果请求受到速率限制，限流器会向客户端返回 429 too many requests 错误。 同时，请求被丢弃或转发到队列。
分布式限流
redis:
- lua脚本
- sorted set每个用户有一个自己的set,试图执行动作时,使用MULTI原子地执行下列操作:
ZREMRANGEBYSCORE删除给定时间间隔前的元素, ZADD 添加当前时间戳, ttl设置为rate limit,计算sorted set的数量,如果超过限额,就失败 (滑动窗口日志)(有一说一我觉得这个如果没有精确的需求不如滑动窗口计数器, 开销感觉有点大)
多限流器同步: 用户hash redis集群分配之类, 尽量别做这种事情
其他层级的限流:
- iptables
- ...
一致性hash
基本步骤如下：
- 使用均匀分布的哈希函数将服务器和键映射到环上。
- 要想知道一个键被映射到哪个服务器，从键的位置顺时针查找，直到找到环上的第一个服务器。
步骤是很简单的, 麻烦的是问题
环上服务器分区大小难以保证相同(添加删除服务器)
解决方法: 虚拟节点(分成更小的块)
每个服务器动态地分配小块(虚拟节点), 这样还可以考虑服务器容量自动缩放问题
一致性模型
N = 副本数
W = 大小为 W 的规定写入。要将写入操作视为成功，必须从 W 个副本确认写入操作。
R = 大小为 R 的读取规定人数。为了使读取操作被认为是成功的，读取操作必须等待至少R个副本的响应。
如何配置N、W和R以适应我们的使用情况？
下面是一些可能的设置：
- 如果
R=1，W=N，系统被优化为快速读取- 如果
W=1，R=N，系统被优化为快速写入- 如果
W+R>N，就可以保证强一致性（通常N=3，W=R=2）。- 如果
W+R<=N，则不能保证强一致性
复制->高可用->不一致
发现并解决冲突: 常用是向量时钟 vector clock, 但有几个问题
- 处理冲突逻辑复杂
- 动态增加删除服务器逻辑复杂
参考:
实际业界的用例参考Dynamo
算法简介:在每个服务器内部维护一个所有服务器的vector
- 当自己发生事件时,增加
vector[self], 并告诉需要告诉的服务器(核心就在于不广播, 没有全局时间!当然也因此不保证解决冲突) - 当自己收到A server的事件时,
vector[A] += d
最后想要觉得一个事件的全局顺序的时候, 查看所有的server的vec
如果有一个server的vec是最大的,那么严格有因果关系,取它的值就行
但如果没有最大的vec, 就需要解决冲突的策略
策略
- 交给客户端, 如dynamo
- 加上时间戳,
vec' = [...servers, timestamp]冲突取ts最大的 - 随机取一个
所以向量时钟算法的实质是：
（1）将逻辑上可以合并的冲突成功合并；
（2）逻辑上无法合并的冲突依旧冲突；
拓展: 向量时钟的剪枝, riak, 牺牲绝对的正确性(false merge)来换取对太长的vec clock的剪枝
gossip 协议 quorom
唯一ID生成器
-
多主复制: 下一个id += k, k是服务器数量,拓展性差
-
uuid
-
引自维基百科，"在每秒产生10亿个UUIDs，大约100年后，创造一个重复的概率会达到50%"。
-
优点：
-
生成 UUID 很简单。服务器之间不需要协调，因此不会有任何同步问题。
-
该系统易于扩展，因为每个 Web 服务器负责生成它们使用的 ID。 ID 生成器可以轻松地与 Web 服务器一起扩展。
-
-
缺点：
- ID 是 128 位长, 空间开销。
- ID 不会随时间上升
- ID 可以是非数字的
-
-
ticket服务器, 在分布式系统之中维持一个唯一的ticket server用于签发id
-
**优点：**数字 ID，易于实施，适用于中小型应用程序
-
**缺点：**单点故障
-
-
twitter雪花算法
- 符号位：1 位，它将始终为 0。这是为将来使用 保留的。它可以潜在地用于区分有符号数和无符号数。
- 时间戳：41 位。自纪元或自定义纪元以来的毫秒数。我们使用 Twitter 雪花默认纪元 1288834974657，相当于 2010 年 11 月 4 日 01:42:54 UTC。
- 数据中心 ID：5 位，这给了我们 25=3225=32 个数据中心。
- 机器 ID：5 位，每个数据中心有 25=3225=32 台机器
- 序列号：12 位。对于在该机器/进程上生成的每个 ID，序列号都会递增 1。该数字每毫秒重置为 0。
也就是说雪花在一台机器上1毫秒可以支持4096个新id
额外要点:
- 时钟同步。在我们的设计中，我们假设 ID 生成服务器具有相同的时钟。当服务器在多个内核上运行时，此假设可能不成立。同样的挑战存在于多机场景中。时钟同步的解决方案超出了本书的范围；但是，了解问题的存在很重要。网络时间协议是这个问题最流行的解决方案。
- 节段长度调整。例如，较少的序列号但较多的时间戳位对低并发性和长期应用是有效的。
- 高可用性。由于 ID 生成器是关键任务系统，因此它必须具有高可用性
拓展阅读: 网络时间协议
短URL
点击较短的别名重定向到原始url
-
URL缩短：给定一个长的URL => 返回一个短得多的URL
-
URL重定向：给定一个短的URL => 重定向到原来的URL
-
高可用性、可扩展性和容错考虑
值得在这里讨论的一件事是 301 重定向与 302 重定向。
301重定向 。301重定向表明，请求的URL被 "永久 "地移到了长URL上。由于是永久重定向，浏览器会缓存响应，对同一URL的后续请求将不会被发送到URL缩短服务上。相反，请求将直接被重定向到长网址服务器。
302重定向。302重定向意味着URL被 "暂时 "移到长URL上，这意味着对同一URL的后续请求将首先被发送到URL缩短服务上。然后，它们会被重定向到长网址服务器。
每种重定向方法都有其优点和缺点。如果优先考虑减少服务器负载，使用301重定向是有意义的，因为只有同一URL的第一个请求被发送到URL缩短服务器。然而，如果分析是重要的，302重定向是一个更好的选择，因为它可以更容易地跟踪点击率和点击的来源。
一个简单的解决方案 <shortURL, LongURL>的rdbms
假设系统支持3650亿个url=10年 * 每天1亿
可以使用0-9a-zA-Z62个字符， 62^n > 3650 亿 n = 7
方法1: hash+碰撞解决
longURL -> hash -> short -> exist on db?(opt bloomfilter + query) -> save/return/collision
collision 的一种解决方法是 longURL -> longURL + predefined string
方法2: base62转换
给每一个请求的长url分配一个数字类型的唯一id, 再对唯一id做base62转换
坏处是可能出现安全问题
longURL -> in DB ? -> yes,return short
|
-> no, generate new ID -> id to base62 -> save id, longurl, shorturl in db
读多于写, 加缓存
爬虫系统
算法侧: 从url seed开始, 将link视为边, 用BFS去爬取不同的网页
架构侧:
seed url -> url frontier -> html downloader(DNS resolver) -> content parser -> content seen(重复检测器, 例如 hash, BF) + 存储-> link extractor -> url filter -> url seen -> url storage
优先级: 简单的做法是根据Url内容变化的速度(可以基于历史抓取记录)和本身的价值（例如是个人博客还是官方网站）设计一个优先级估价函数, 根据url区分k个工作队列, 保证一个队列内只有一个url（的多个请求）, 这样就可以实现优先级
爬虫需要考虑礼貌性, DDoS
做法是每个url作为一个后端队列, 在优先级的selector出来之后, 维护一张(url,back queue)的表, 将url放到back queue里面去
对每一个url(backqueue), 维护一个时间t, 是下一次抓取的最早时间(例如当前时间+10倍前一次获取时间)
而爬虫线程每次从时间的最小堆之中取出元素, (如需要, 等待到t), 然后爬取
html下载器: Robots 排除协议, 分布式抓取, 超时
其他问题: 冗余内容, 蜘蛛陷阱, 垃圾数据, js-需要动态渲染得到链接和其他数据
通知系统
删重, 跟踪, 限速, 用户设置(接受哪些通知), 失败时的重试机制, 安全性(客户验证)
推送流：
核心在fan out系统, 读扇出(拉模式)还是写扇出(推模式), 热键问题和速率问题
混 合: 对大多数用户使用推送模式。对于名人或有很多朋友/粉丝的用户，我们让粉丝按需提取信息内容以避免系统过载
get friend IDs: graph DB
fanout service先从graph DB拿到friend ids, 再从用户缓存(用户db)得到朋友相关信息:
例如，如果你把某人调成静音，她的帖子将不会显示在你的信息流中，尽管你们仍然是朋友。帖子可能不显示的另一个原因是，用户可以有选择地与特定的朋友分享信息或对其他人隐藏信息。
把更新的需求包成任务(例如<post_id, user_id>)丢到mq
mq入库, 写缓存
缓存层级:
-
News Feed：它存储了信息的ID。
-
Content：它存储每个帖子的数据。受欢迎的内容被存储在热缓存中。
-
Social Graph：它存储用户关系数据。
-
Action：它存储有关用户是否喜欢帖子、回复帖子或对帖子执行其他操作的信息。
-
Counters：它存储点赞、回复、关注者、关注等的计数器。
聊天系统
无状态有状态分离
-
无状态的服务 http
无状态服务是传统的面向公众的请求/响应服务，用于管理登录、注册、用户资料等。这些是许多网站和应用程序中的常见功能。
无状态服务位于负载均衡器后面，其工作是根据请求路径将请求路由到正确的服务。这些服务可以是单体的，也可以是单独的微服务。我们不需要自己建立许多这样的无状态服务，因为市场上有一些服务可以很容易地被集成。
我们将深入讨论的一个服务是服务发现。它的主要工作是给 客户提供一个客户可以连接到的聊天服务器的DNS主机名列表。
-
有状态的服务 websocket
唯一有状态的服务是聊天服务。该服务是有状态的，因为每个客户都与一个聊天服务器保持持久的网络连接。在这个服务中，只要服务器仍然可用，客户通常不会切换到另一个聊天服务器。服务发现与聊天服务密切协调，以避免服务器过载。我们将在深入研究中详细介绍。
服务器的切分:
- chat server 管理信息的收发
- presence server 管理在线/离线状态
- api server 处理无状态服务
- notification server 推送通知
DB选择: KV数据库
为什么？聊天数据的读写模式
- 数据量巨大 需要水平拓展
- 只有最近的聊天记录才会被频繁访问
- 但“最近”里面也不完全是顺序的, 引用, 跳转, 提及等
- 读写比约为1:1, 读并不远远高于写
这样的wkld下kv比关系型的优势:
- 水平拓展轻松
- 分层架构对热数据容易优化
- 关系型数据库的index在数据量变大时昂贵
消息ID设计:
一对一聊天: 主键message id
群聊: 复合主键 {channel_id, message_id}
问题: id用什么?
要求: 唯一性 + 可以按照时间排序
- 自增: 分布式实现困难
- 全局序列号发生器: 将时间项提前就可以按照时间排序
- 本地序列号生成器: 只保证消息在一个组内(channel内)唯一, 实现比较简单
发送信息的流程
- 用户A向聊天服务器1发送了一条聊天信息。
- 聊天服务器1从ID生成器获得一个信息ID。
- 聊天服务器1将消息发送至消息同步队列。
- 消息被储存在一个键值存储中。
- a. 如果用户B在线，信息被转发到用户B 所连接的聊天服务器2。
- b. 如果用户B处于离线状态，则从推送通知（PN）服务器发送推送通知。
- 聊天服务器2将消息转发给用户B，用户B和聊天服务器2之间有一个持久的WebSocket连接。
群组聊天:
第一种方法: A发消息, 在每一个成员的收件箱里面复制一个副本, 适用于群组人数较少的时候(例如微信的500人约束); 每个收件人有自己的收件箱(消息同步队列), 所以并不保证一致性
在线状态指示器:
- naive的做法: 建立连接就在线, 断开就离线。问题在网络波动时候, 变化太快
- 更优雅的做法, 心跳
- 推送, 类似微信这种小群(500人限制)可以直接查询实时的ws连接。大群需要懒加载
扩展聊天应用程序以支持媒体文件，如照片和视频。媒体文件的大小明显大于文本。压缩、云存储和缩略图是值得讨论的话题。
- 端到端加密。Whatsapp支持信息的端到端加密。只有发件人和收件人可以阅读信息。有兴趣的读者请参考参考资料中的文章[9]。
- 在客户端缓存信息，可以有效地减少客户端和服务器之间的数据传输。
- 提高加载时间。Slack建立了一个地理分布的网络来缓存用户的数据、频道等，以获得更好的加载时间[10]。
- 故障处理。
- 聊天服务器错误。可能有数十万，甚至更多的，坚持不懈的连接到一个聊天服务器。如果一个聊天服务器离线，服务发现（Zookeeper）会提供一个新的聊天服务器，让客户建立新的连接。
- 消息重发机制。重试和排队是重发消息的常用技术。
多媒体支持的大体流程
- client 通过 rest 将多媒体资源发送到服务器
- 服务器转换媒体文件(例如图片生成缩略图, 压缩)
- 服务器存到s3
- 服务器通过s3链接响应client
- 客户端再将s3链接通过ws发送(广播)给聊天的其他用户
- 其他client 收到s3连接, 根据定义的消息类型进行渲染
简单的搜索支持: trie
topK: 先找到前缀, 再遍历子树
问题: 太慢
解决方法:
- 在每个节点缓存常用的前k个查询
- 控制前缀的最大长度
更新trie: 数据搜集, 对于实时应用服务, 短时间间隔; 对于非实时的, 可以例如一周定时更新一次
合法性: 自动完成可以根据hash等过一个filter, 避免补出禁止的网站等
多语言：unicode trie
分片: 可以基于字母, 但是要考虑到频率问题
实时(趋势)搜索: 流式, 领域特定, AI
视频流
核心是分成几个部分, 一部分类似传统的server, 提供视频metadata
另一部分依托云服务和CDN, 做好视频传输和解码编码
其中特定部分的逻辑复杂, 例如解编码的模块化和引擎化, CDN贵所以视频基于历史数据做冷热分离, 冷视频走自建而不是CDN
还有比如错误处理, 数字版权之类
临近服务
由于是读远多于写的情况, 所以常见用关系型db
关系型的问题是, 如果是经纬度, 二维数据index利用率低
解决方法是二维转一维再index搜索, 例如geohash, R tree, 四叉树, google s2
geohash: 经纬度网格编码再转base32, 共享前缀越长, 越接近
边界问题: 反过来不成立, 接近的两个地块可能共享前缀并不长(在子午线/赤道等大格子边界), 所以geohash LIKE 'sth%'检索出来结果不全
方法是不仅检索自己格子的geohash, 也把邻居格子的一起检索
业务问题：范围内部商家不够, 解决方法是放大格子继续检索
google s2: 基于希尔伯特曲线的球面->1d算法, 保证2d上接近在1d上也接近