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

跳表本质上是一种链表，允许您在其上进行二分查找。它通过添加额外的节点来实现这一点，使您能够‘跳过’链表的某些部分。通过随机投掷硬币来创建额外节点，跳表的搜索、插入和删除操作的时间复杂度应为 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 如何扩展其社交图谱数据存储。

动机​

移动设备上的 HTTP 实时流媒体视频服务，...

1. ==内存/存储有限==
2. 遭受不稳定的网络连接和可变带宽的影响，并需要 ==中途质量调整。==

解决方案​

1. 服务器端：在典型配置中，硬件编码器接收音视频输入，将其编码为 H.264 视频和 AAC 音频，并以 MPEG-2 传输流的形式输出。

   1. 然后，流被软件流分段器分解为一系列短媒体文件（.ts 可能为 10 秒）。
   2. 分段器还创建并维护一个索引（.m3u8）文件，其中包含媒体文件的列表。
   3. 媒体文件和索引文件都发布在网络服务器上。

2. 客户端：客户端读取索引，然后按顺序请求列出的媒体文件，并在段之间无任何暂停或间隙地显示它们。

架构​

SOLID 是一组设计原则的首字母缩写，帮助软件工程师在项目中编写稳健的代码。

1. S - 单一职责原则。一个模块应该只对一个角色负责，一个模块只是一个功能和数据结构的内聚集合。

2. O - 开放/封闭原则。软件工件应该对扩展开放，但对修改封闭。

3. L - 里氏替换原则。通过接口和实现、泛型、子类化和鸭子类型来简化代码的继承。

4. I - 接口隔离原则。将单一的庞大接口分割成更小的接口，以解耦模块。

5. D - 依赖倒置原则。源代码的依赖关系与控制流相反。我们架构图中最明显的组织原则。

   1. 事物应该是稳定的具体，或者是过时的抽象，而不是 ==具体和不稳定==。
   2. 因此使用 ==抽象工厂== 来创建不稳定的具体对象（管理不希望的依赖关系）。产生接口的接口
   3. DIP 违规无法完全消除。大多数系统至少会包含一个这样的具体组件——这个组件通常被称为主组件。

结构化编程 vs. 面向对象编程 vs. 函数式编程

1. 结构化编程是一种对直接控制转移的约束。

   1. 可测试性：软件就像科学：科学不是通过证明陈述为真来工作的，而是通过证明陈述为假来工作的。结构化编程迫使我们递归地将程序分解为一组小的可证明函数。

2. 面向对象编程是一种对间接控制转移的约束。

   1. 封装、继承、多态（指向函数的指针）并不是面向对象特有的。
   2. 但面向对象使多态的使用变得安全和方便。然后启用强大的==插件架构==与依赖反转
      1. 源代码依赖关系和控制流通常是相同的。然而，如果我们让它们都依赖于接口，依赖关系就会反转。
      2. 接口赋予独立部署的能力。例如，在部署Solidity智能合约时，导入和使用接口消耗的气体远远少于对整个实现进行操作。

3. 函数式编程：不可变性。是一种对变量赋值的约束。

   1. 为什么重要？所有的竞争条件、死锁条件和并发更新问题都是由于可变变量造成的。
   2. ==事件溯源==是一种策略，我们存储事务，而不是状态。当需要状态时，我们只需从时间的开始应用所有事务。

为什么副本和一致性？​

大数据集 ⟶ 扩展 ⟶ 数据分片/分区 ⟶ 1) 数据访问路由 2) 可用性副本 ⟶ 一致性挑战

CAP定理的一致性权衡​

• 一致性：所有节点在同一时间看到相同的数据
• 可用性：保证每个请求都能收到关于其成功或失败的响应
• 分区容忍性：系统在任意消息丢失或部分系统故障的情况下继续运行

任何网络共享数据系统只能拥有三种理想属性中的两种。

• 关系数据库管理系统（rDBMS）倾向于CP ⟶ ACID
• NoSQL倾向于AP ⟶ BASE

“2 of 3”是误导性的​

12年后，作者埃里克·布鲁尔（Eric Brewer）表示“2 of 3”是误导性的，因为

1. 分区是罕见的，当系统没有分区时，几乎没有理由放弃C或A。
2. 选择实际上可以在同一系统内的多个地方以非常细的粒度应用。
3. 选择不是二元的，而是有一定程度的。

因此，当没有分区（节点正确连接）时，这种情况经常发生，我们应该同时拥有AC。当出现分区时，处理它们的步骤如下：

1. 检测分区的开始，
2. 进入可能限制某些操作的显式分区模式，并
3. 当通信恢复时启动分区恢复（补偿错误）。