45 篇博文 含有标签「系统设计」

冷备份：使用心跳或指标/警报来跟踪故障。当发生故障时，配置新的备用节点。仅适用于无状态服务。

热备份：保持两个活动系统承担相同的角色。数据几乎实时镜像，两个系统将拥有相同的数据。

温备份：保持两个活动系统，但第二个系统在故障发生之前不接收流量。

检查点（或类似于 Redis 快照）：使用预写日志（WAL）在处理之前记录请求。备用节点在故障转移期间从日志中恢复。

• 缺点
  • 对于大型日志来说耗时较长
  • 自上次检查点以来丢失数据
• 使用案例：Storm、WhillWheel、Samza

主动-主动（或全活动）：在负载均衡器后保持两个活动系统。它们并行处理。数据复制是双向的。

设计一个系统，将用户提供的网址转换为缩短的网址，并重定向回原始网址。描述系统的工作原理。你将如何分配缩短的网址？你将如何存储缩短网址与原始网址的映射？你将如何实现重定向服务器？你将如何存储点击统计数据？

假设：我通常不会在初始问题陈述中包含这些假设。优秀的候选人会在提出设计时询问规模。

• 注册重定向网址的独特域名总数大约在数万左右
• 新网址注册量约为 10,000,000/天（100/秒）
• 重定向请求量约为 10B/天（100,000/秒）
• 提醒候选人这些是平均数字 - 在高峰流量时（例如“人们下班回家时”或“超级碗期间”）可能会高得多。
• 最近的统计数据（在当前日期内）应聚合并在 5 分钟延迟后可用
• 长期回顾统计数据可以每天计算

假设​

每天 1B 新网址，总共 100B 条目 越短越好 显示统计数据（实时和每日/月度/年度）

编码网址​

http://blog.codinghorror.com/url-shortening-hashes-in-practice/

选择 1. md5（128 位，16 个十六进制数字，碰撞，生日悖论，2^(n/2) = 2^64）截断？（64 位，8 个十六进制数字，碰撞 2^32），Base64。

• 优点：哈希简单且水平可扩展。
• 缺点：太长，如何清理过期网址？

选择 2. 分布式序列 ID 生成器。（Base62：az，AZ，0~9，62 个字符，62^7），分片：每个节点维护一部分 ID。

• 优点：易于淘汰过期条目，更短
• 缺点：协调（zookeeper）

KV 存储​

MySQL（10k qps，慢，无关系），KV（100k qps，Redis，Memcached）

优秀的候选人会询问别名的生命周期，并设计一个系统来清理过期的别名。

后续问题​

问：如何生成缩短的网址？

• 一个差的候选人会提出一个使用单一 ID 生成器的解决方案（单点故障）或一个在每个请求中需要协调 ID 生成器服务器的解决方案。例如，使用自增主键的单一数据库服务器。
• 一个可接受的候选人会提出使用网址的 md5，或某种形式的 UUID 生成器，可以在任何节点独立完成。虽然这允许分布式生成不冲突的 ID，但会产生较大的“缩短”网址。
• 一个优秀的候选人会设计一个解决方案，利用一组 ID 生成器，从中央协调器（例如 ZooKeeper）保留 ID 空间的块，并独立从其块中分配 ID，必要时刷新。

问：如何存储映射？

• 一个差的候选人会建议使用单体数据库。这个存储没有关系方面。它是一个纯粹的键值存储。
• 一个优秀的候选人会建议使用任何轻量级的分布式存储。MongoDB/HBase/Voldemort 等等。
• 一个优秀的候选人会询问别名的生命周期，并设计一个系统来==清理过期的别名==。

问：如何实现重定向服务器？

• 一个差的候选人会从头开始设计某种东西来解决一个已经解决的问题。
• 一个优秀的候选人会建议使用现成的 HTTP 服务器，配备一个插件，解析缩短的网址键，在数据库中查找别名，更新点击统计并返回 303 到原始网址。Apache/Jetty/Netty/tomcat 等等都可以。

问：点击统计数据如何存储？

• 一个差的候选人会建议在每次点击时写回数据存储。
• 一个优秀的候选人会建议某种形式的==聚合层，接受点击流数据，聚合并定期写回持久数据存储==。

问：如何对聚合层进行分区？

• 一个优秀的候选人会建议使用低延迟消息系统来缓冲点击数据并将其传输到聚合层。
• 一个候选人可能会询问统计数据需要多频繁更新。如果是每日更新，将其存储在 HDFS 中并运行 map/reduce 作业来计算统计数据是一个合理的方法。如果是近实时的，聚合逻辑应计算统计数据。

问：如何防止访问受限网站？

• 一个优秀的候选人可以回答通过在 KV 存储中维护一个主机名黑名单。
• 一个优秀的候选人可能会提出一些高级扩展技术，如布隆过滤器。

为什么选择 Lambda 架构？​

为了解决大数据带来的三个问题

1. 准确性（好）
2. 延迟（快）
3. 吞吐量（多）

例如，传统方式扩展页面查看服务的问题

1. 你从传统关系数据库开始。
2. 然后添加一个发布-订阅队列。
3. 然后通过水平分区或分片进行扩展。
4. 故障容错问题开始出现。
5. 数据损坏发生。

关键点是 ==AKF 规模立方体 的 X 轴维度单独并不足够。我们还应该引入 Y 轴 / 功能分解。Lambda 架构告诉我们如何为数据系统做到这一点。==

什么是 Lambda 架构？​

如果我们将数据系统定义为

查询 = 函数（所有数据）

那么 Lambda 架构是

批处理视图 = 函数（批处理作业执行时的所有数据）
实时视图 = 函数（实时视图，新数据）

查询 = 函数（批处理视图，实时视图）

==Lambda 架构 = CQRS（批处理层 + 服务层） + 快速层==

关系数据库是大多数存储使用案例的默认选择，原因在于 ACID（原子性、一致性、隔离性和持久性）。一个棘手的问题是“一致性”——它意味着任何事务都会将数据库从一个有效状态转变为另一个有效状态，这与 CAP 定理 中的一致性不同。

模式设计和第三范式 (3NF)​

为了减少冗余并提高一致性，人们在设计数据库模式时遵循 3NF：

• 1NF：表格形式，每个行列交集只包含一个值
• 2NF：只有主键决定所有属性
• 3NF：只有候选键决定所有属性（且非主属性之间不相互依赖）

数据库代理​

如果我们想消除单点故障怎么办？如果数据集太大，无法由单台机器承载怎么办？对于 MySQL，答案是使用数据库代理来分配数据，可以通过集群或分片。

集群是一种去中心化的解决方案。一切都是自动的。数据会自动分配、移动和重新平衡。节点之间互相传递信息（尽管这可能导致组隔离）。

分片是一种集中式解决方案。如果我们去掉不喜欢的集群属性，分片就是我们得到的结果。数据是手动分配的，不会移动。节点之间互不知晓。

在一个常规的互联网服务中，读取与写入的比例大约是 100:1 到 1000:1。然而，从硬盘读取时，数据库连接操作耗时，99% 的时间花费在磁盘寻址上。更不用说跨网络的分布式连接操作了。

为了优化读取性能，非规范化通过添加冗余数据或分组数据来引入。这四种 NoSQL 类型可以帮助解决这个问题。

键值存储​

键值存储的抽象是一个巨大的哈希表/哈希映射/字典。

我们希望使用键值缓存的主要原因是为了减少访问活跃数据的延迟。在快速且昂贵的介质（如内存或 SSD）上实现 O(1) 的读/写性能，而不是在传统的慢且便宜的介质（通常是硬盘）上实现 O(logn) 的读/写性能。

设计缓存时需要考虑三个主要因素。

1. 模式：如何缓存？是读透/写透/写旁/写回/缓存旁？
2. 放置：将缓存放在哪里？客户端/独立层/服务器端？
3. 替换：何时过期/替换数据？LRU/LFU/ARC？

现成的选择：Redis/Memcache？Redis 支持数据持久化，而 Memcache 不支持。Riak、Berkeley DB、HamsterDB、Amazon Dynamo、Project Voldemort 等等。

文档存储​

文档存储的抽象类似于键值存储，但文档（如 XML、JSON、BSON 等）存储在键值对的值部分。

我们希望使用文档存储的主要原因是灵活性和性能。灵活性通过无模式文档实现，性能通过打破 3NF 来提高。初创公司的业务需求时常变化。灵活的模式使他们能够快速行动。

现成的选择：MongoDB、CouchDB、Terrastore、OrientDB、RavenDB 等等。

列式存储​

列式存储的抽象就像一个巨大的嵌套映射：ColumnFamily<RowKey, Columns<Name, Value, Timestamp>>。

我们希望使用列式存储的主要原因是它是分布式的、高可用的，并且针对写入进行了优化。

现成的选择：Cassandra、HBase、Hypertable、Amazon SimpleDB 等等。

图数据库​

顾名思义，这种数据库的抽象是一个图。它允许我们存储实体及其之间的关系。

如果我们使用关系数据库来存储图，添加/删除关系可能涉及模式更改和数据移动，而使用图数据库则不需要。另一方面，当我们在关系数据库中为图创建表时，我们是基于我们想要的遍历进行建模；如果遍历发生变化，数据也必须随之变化。

现成的选择：Neo4J、Infinitegraph、OrientDB、FlockDB 等等。

布隆过滤器是一种数据结构，用于以时间和空间高效的方式检测一个元素是否在一个集合中。

可能会出现假阳性匹配，但不会出现假阴性——换句话说，查询返回“可能在集合中”或“绝对不在集合中”。元素可以添加到集合中，但不能移除（尽管可以通过“计数”布隆过滤器来解决这个问题）；添加到集合中的元素越多，假阳性的概率就越大。

使用案例

• Cassandra 使用布隆过滤器来确定 SSTable 是否包含特定行的数据。
• HBase 布隆过滤器是一种有效的机制，用于测试 StoreFile 是否包含特定行或行-列单元格。
• 网站的反欺诈系统可以有效地使用布隆过滤器来拒绝被禁止的用户。
• 谷歌 Chrome 浏览器曾经使用布隆过滤器来识别恶意 URL。

跳表本质上是一种链表，允许您在其上进行二分查找。它通过添加额外的节点来实现这一点，使您能够‘跳过’链表的某些部分。通过随机投掷硬币来创建额外节点，跳表的搜索、插入和删除操作的时间复杂度应为 O(logn)。

用例

• LevelDB MemTable
• Redis SortedSet
• Lucene 倒排索引

总之，在选择公共 API、API 网关或 BFF（前端后端）网关的工具时，我更喜欢 GraphQL，因为它具有尾随结果、批处理嵌套查询、性能追踪和显式缓存等功能。

什么是面试？​

面试是员工寻找未来同事的过程，在此过程中，他们 寻找信号来回答以下三个关键问题：

1. 能力问题 - 你能胜任这份工作吗？
2. 意愿问题 - 你愿意做这份工作吗？
3. 文化契合问题 - 你能融入团队吗？

为什么软技能如此重要？​

以上任何一个关键问题都无法在没有良好沟通的情况下回答。 你的工作将被那些沟通能力比你更强的人取代。

准备的通用回答（故事）​

1. 艰难取得的胜利。你是如何应对失败的？简要谈谈你经历的最艰难时刻，然后专注于你是如何反击的，并感谢那些帮助过你的人。这表明你具备毅力、团队建设能力以及与工作相关的素质。
2. 影响力。你能引导他人接受你的观点吗？领导者 = 激励自我牺牲的愿景者。没有说服能力，领导者就不存在。
3. 技术技能。你有故事证明你出色的技术技能吗？
4. 文化契合。联邦调查局曾经询问潜在特工他们读过哪些书，直到一个地下线人的网络找到了理想答案：“汤姆·克兰西的间谍小说。”
5. 吸引力。你有什么吸引人的地方？是什么让你与其他人不同？

Apache Kafka 是一个分布式流处理平台。

为什么使用 Apache Kafka？​

它的抽象是一个 ==队列==，并且它具有

• 一个分布式的发布-订阅消息系统，将 N^2 关系解决为 N。发布者和订阅者可以以自己的速度操作。
• 采用零拷贝技术，速度极快
• 支持容错的数据持久性

它可以应用于

• 按主题进行日志记录
• 消息系统
• 地理复制
• 流处理

为什么 Kafka 这么快？​

Kafka 使用零拷贝，CPU 不需要将数据从一个内存区域复制到另一个内存区域。

没有零拷贝的情况下：

使用零拷贝的情况下：

架构​

从外部看，生产者写入代理，消费者从代理读取。

数据存储在主题中，并分割成多个分区，这些分区是复制的。

1. 生产者将消息发布到特定主题。
   • 首先写入内存缓冲区，然后刷新到磁盘。
   • 仅追加的顺序写入以实现快速写入。
   • 写入磁盘后可供读取。
2. 消费者从特定主题中拉取消息。
   • 使用“偏移指针”（偏移量作为 seqId）来跟踪/控制其唯一的读取进度。
3. 一个主题由分区组成，负载均衡，分区（= 有序 + 不可变的消息序列，持续追加）
   • 分区决定最大消费者（组）并行性。一个消费者在同一时间只能从一个分区读取。

如何序列化数据？Avro

它的网络协议是什么？TCP

分区的存储布局是什么？O(1) 磁盘读取

如何容错？​

==同步副本 (ISR) 协议==。它容忍 (numReplicas - 1) 个死掉的代理。每个分区有一个领导者和一个或多个跟随者。

总副本 = ISRs + 不同步副本

1. ISR 是活着的副本集合，并且已经完全追赶上领导者（注意领导者始终在 ISR 中）。
2. 当发布新消息时，领导者会等待直到它到达 ISR 中的所有副本，然后才提交消息。
3. ==如果一个跟随者副本失败，它将被移出 ISR，领导者随后继续以更少的副本在 ISR 中提交新消息。注意，现在系统正在以不足副本模式运行。== 如果领导者失败，将选择一个 ISR 成为新的领导者。
4. 不同步副本继续从领导者拉取消息。一旦追赶上领导者，它将被重新添加到 ISR 中。

Kafka 是 CAP 定理 中的 AP 还是 CP 系统？​

Jun Rao 说它是 CA，因为“我们的目标是在单个数据中心内支持 Kafka 集群的复制，在那里网络分区是罕见的，因此我们的设计专注于保持高度可用和强一致性的副本。”

然而，这实际上取决于配置。

1. 默认配置（min.insync.replicas=1，default.replication.factor=1）开箱即用时，您将获得 AP 系统（至多一次）。

2. 如果您想实现 CP，您可以将 min.insync.replicas 设置为 2，主题复制因子设置为 3 - 然后使用 acks=all 生产消息将保证 CP 设置（至少一次），但（如预期）在特定主题/分区对可用副本不足（<2）时将会阻塞。

API 如何可能不够健壮且不可预测？

1. 网络不可靠。
2. 服务器更可靠，但仍可能出现故障。

如何解决这个问题？三个原则：

1. 客户端重试以确保一致性。

2. 使用幂等性和幂等性键进行重试，以允许客户端传递唯一值。

   1. 在 RESTful API 中，PUT 和 DELETE 动词是幂等的。
   2. 然而，POST 可能导致==“双重收费”问题==。因此，我们使用==幂等性键==来识别请求。
      1. 如果故障发生在服务器之前，则会进行重试，服务器将首次看到该请求，并正常处理。
      2. 如果故障发生在服务器中，则 ACID 数据库将通过幂等性键保证事务。
      3. 如果故障发生在服务器回复之后，则客户端重试，服务器简单地回复成功操作的缓存结果。

3. 使用==指数退避和随机抖动==进行重试。要考虑==雷鸣般的群体问题==，即服务器可能处于降级状态，突发的重试可能会进一步损害系统。

例如，Stripe 的客户端重试计算延迟如下...

def self.sleep_time(retry_count)
  # 根据到目前为止的尝试次数应用初始网络重试延迟的指数退避。不要让这个数字超过最大网络重试延迟。
  sleep_seconds = [Stripe.initial_network_retry_delay * (2 ** (retry_count - 1)), Stripe.max_network_retry_delay].min

  # 通过在 (sleep_seconds / 2) 到 (sleep_seconds) 范围内随机化值来应用一些抖动。
  sleep_seconds = sleep_seconds * (0.5 * (1 + rand()))

  # 但永远不要少于基础睡眠秒数。
  sleep_seconds = [Stripe.initial_network_retry_delay, sleep_seconds].max

  sleep_seconds
end

AKF 规模立方体将扩展过程可视化为三个维度…

1. ==水平复制== 和克隆 (X 轴)。在负载均衡器或反向代理后面拥有一组相同且最好是无状态的实例。因此，每个请求都可以由这些主机中的任何一个来处理，并且不会有单点故障。
2. ==功能分解== 和分段 - 微服务 (Y 轴)。例如，身份验证服务、用户资料服务、照片服务等。
3. ==水平数据分区== - 分片 (Z 轴)。将整个堆栈复制到不同的“集群”。每个集群可以针对特定的大用户群。例如，Uber 在中国和美国都有数据中心。每个数据中心可能会有不同区域的“集群”。

想要一个例子吗？去看看 Facebook 如何扩展其社交图谱数据存储。