Skip to main content

system-design-interview笔记

· 27 min read
ayanami

限流器​

  • 放在哪里?

    • 客户端, 容易被伪造绕过
    • 服务端应用代码, 灵活性高, 但占据工程资源
    • 云上微服务, 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​

基本步骤如下：

  1. 使用均匀分布的哈希函数将服务器和键映射到环上。
  2. 要想知道一个键被映射到哪个服务器，从键的位置顺时针查找，直到找到环上的第一个服务器。

步骤是很简单的, 麻烦的是问题

环上服务器分区大小难以保证相同(添加删除服务器)

解决方法: 虚拟节点(分成更小的块)

每个服务器动态地分配小块(虚拟节点), 这样还可以考虑服务器容量自动缩放问题

一致性模型​

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, 就需要解决冲突的策略

策略

  1. 交给客户端, 如dynamo
  2. 加上时间戳, vec' = [...servers, timestamp]冲突取ts最大的
  3. 随机取一个

所以向量时钟算法的实质是：

（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内)唯一, 实现比较简单

发送信息的流程

  1. 用户A向聊天服务器1发送了一条聊天信息。
  2. 聊天服务器1从ID生成器获得一个信息ID。
  3. 聊天服务器1将消息发送至消息同步队列。
  4. 消息被储存在一个键值存储中。
  5. a. 如果用户B在线，信息被转发到用户B所连接的聊天服务器2。
  6. b. 如果用户B处于离线状态，则从推送通知（PN）服务器发送推送通知。
  7. 聊天服务器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上也接近

Loading Comments...