31 篇博文 含有标签「system design」

目标受众​

拥有一定或较少的经验，或者是在职业生涯中没有担任过任何领导或设计职位的人（无论是正式还是非正式）。

问题描述​

描述你以前特别感兴趣或难忘的项目经历。后续的问题包括：

• 为什么你会觉得它有趣？
• 该项目最具挑战性的部分是什么，你又是如何应对这些挑战的呢？
• 你从这个项目中学习到了什么？你又希望在项目开始前了解什么？
• 你有考虑其他的设计或实现方法吗？ 你为什么选择你做的那个方案？ 如果再次选择做同样的项目，你有什么不同的做法吗？

面试官提示​

由于这里的目标是评估一个人的技术沟通能力和兴趣水平，而他们有可能参与过速成班，所以你应该准备好问他们更多的问题（无论是为了更多的细节，还是有关项目的其他方面）。如果是他们是刚写完论文的毕业生，那么毕业论文通常是很好的切入点。虽然这个问题在很多方面都类似于电话面试中的简历问题，但其内容大约是电话面试的四倍，而且应该按比例更详细地询问他们都做了些什么。因此，虽然评分标准是相似的，但应该用更高的期望和更多的数据来评估面试者。

得分​

优秀的候选人能够：

• 充分地谈论项目经历，在面试中，与面试官的互动应当是对话而不是指导

• 对整个项目具有一定的了解，而不仅仅是他们所关注的领域，并且能够清楚地表达出项目的设计和意图

• 无论是什么项目，都要充满激情，并且能够清楚地描述出激发这种激情的项目要素

• 能够清楚地解释考虑了哪些备选方案，以及他们为什么选择他们所采取的实施策略

• 是否有从他们的经历中反思并吸取教训

而好的候选人能够：

• 在面试中可能会遇到一些问题，但是能够在面试官的帮助下解决

• 可能缺乏对项目更广范围的一些了解，但仍然对与他们直接交互的部分和特定领域具有很强的了解

• 也许看起来充满激情，但无法准确解释这种激情来自何处

• 也许能够讨论他们所做的替代方案，但是考虑的不够深刻

• 从他们的过往经历中反思并汲取经验

而差的候选人则是这样的：

• 在面试交流中表现得费劲，面试官觉得面试者是在询问他，而不是与他交谈

• 即使是在他们工作的领域，也可能缺乏对项目的详细了解。他们可能不了解他们的产品为何这样设计，或者不明白产品是如何与其他系统交互的

• 当你在询问所做过最有趣的项目时，他们对产品表现得应该很感兴趣，但事实上是，他们看起来可能并不太感兴趣

• 可能不熟悉潜在替代方案的实现方法

• 似乎并没有从他们的过往项目经历中反思和学习。而判断这种情况的重要迹象是：“你学到了什么”和“你会有什么不同”的答案很短，或者几乎千篇一律

Apache Kafka 是一个分布式流(streaming)平台。

为什么使用 Apache Kafka?​

它的抽象是一个==队列==，它的特点包括

• 分布式发布-订阅(pub-sub)消息传递系统，可将 N ^ 2 的关系简化成 N.发布者和订阅者可以按自己的速率运行。
• 超快速的零复制(zero-copy)技术
• 支持可容错的数据持久化

它可以被应用于

• 按主题打日志
• 消息系统
• 异地备份
• 流处理

为什么 Kafka 如此的快？​

Kafka 使用零复制技术，其中，CPU 不会执行数据跨存储区复制副本(replica)的任务。

不使用零复制技术:

使用零复制技术:

构架​

从外部看，生产者写给 kafka 集群，而用户从 kafka 集群读取内容。

数据按照主题存储，并分割为可复制副本的分区。

1. 生产者将消息发布到特定主题中。
   • 首先写入内存缓冲区中并更新到磁盘中。
   • 为了实现快速写，使用 append-only 的序列写。
   • 写入后方可读取。
2. 消费者从特定主题中提取消息。
   • 使用“偏移指针”（偏移量为 SEQ ID）来跟踪/控制其唯一的读取进度。
3. 一个主题包括分区和负载均衡，其中，每个分区是一个有序,不变的序列的记录。
   • 分区决定用户（组）的并行性。同一时间内，一个用户只可以读取一个分区。

如何序列化数据? Avro

它的网络协议是什么？ TCP

分区内的存储布局是怎样的 y？ O（1）磁盘读取

如何容错？​

==同步副本（ISR）协议==. 其容许 (numReplicas - 1) 的节点挂掉。每个分区有一个 leader, 一个或多个 follower.

总副本量 = 同步的副本 + 不同步的副本

1. ISR 是一组活的并且与 leader 同步的副本（注意领导者总是在 ISR 中）。
2. 当发布新消息时，leader 在提交消息之前等待，直到它到达 ISR 中的所有副本为止。
3. ==如果 follower 同步失败，它将从 ISR 中退出，然后 leader 继续用 ISR 中较少的副本提交新消息。注意，此时系统运行在低副本数量的状态下== 如果一个 leader 失败了，另一个 ISR 将被选成为一个新的 leader 。
4. 未同步的副本不断的从 leader 那里拉出消息。一旦追赶上 leader ，它将被添加回 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，topic replication factor 为 3，然后生成一个 acks=all 的消息将保证 CP 设置（至少一次），但是，如果没有足够的副本（副本数＜ 2）用于特定主题/分区时，则无法成功地写。

面临的挑战是什么？​

在 TAO 之前，使用缓存旁路模式

社交图谱数据存储在 MySQL 中，并缓存于 Memcached 中

三个问题：

1. Memcached 中的列表更新操作效率低。无法追加，只能更新整个列表。
2. 客户端必须管理缓存
3. 难以提供 ==读后写一致性==

为了解决这些问题，我们有三个目标：

• 高效扩展的在线数据图服务
• 优化读取（其读写比为 500:1）
  • 低读取延迟
  • 高读取可用性（最终一致性）
• 写入的及时性（读后写）

数据模型​

• 具有唯一 ID 的对象（例如用户、地点、评论）
• 两个 ID 之间的关联（例如标签、喜欢、作者）
• 两者都有键值数据以及时间字段

解决方案：TAO​

1. 高效扩展并减少读取延迟

   • 图特定缓存
   • 在无状态服务层和数据库层之间的独立缓存层（即 功能分解）
   • 数据中心的细分（即 水平数据分区）

2. 写入及时性

   • 写透缓存
   • 领导/跟随缓存以解决雷鸣般的拥挤问题
   • 异步复制

3. 读取可用性

   • 读取故障转移到备用数据源

TAO 的架构​

• MySQL 数据库 → 持久性
• 领导缓存 → 协调对每个对象的写入
• 跟随缓存 → 提供读取但不提供写入。将所有写入转发给领导。

读取故障转移

挑战是什么?​

在TAO之前，用 cache-aside pattern

社交图谱是存储在MySQL和缓存在Memcached里的

3个存在的问题:

1. 在Memcached中更新社交图谱的边列表操作效率太低。不是在列表的后面加一条边，而是要更新整个列表。
2. 客户端管理缓存的逻辑很复杂
3. 很难维持==数据库读在写之后这种一致性==

为了解决这些问题，我们有3个目标：

• 面对大规模数据仍然高效的图(graph)存储
• 优化读操作(读写比是500:1)
  • 降低读操作的时长
  • 提高读操作的可用性(最终一致性)
• 及时完成写操作 (先写再读)

数据模型​

• 带 unique ID 的对象 (例如用户，地址，评论)
• 两个ID之间的关联 (例如被标记，点赞，发表)
• 以上两个数据模型都有键值数据和时间相关数据

解决方案: TAO​

1. 加快读操作，高效处理大规模的读

   • 专门针对图做缓存
   • 在无状态的服务器层和数据库层中间加一层缓存 (参考 业务拆分)
   • 拆分数据中心 (参考 按数据分割)

2. 及时完成写操作

   • 透写缓存(write-through cache)
   • 用follower/leader缓存去解决==惊群问题==
   • 异步复制

3. 提高读操作的可用性

   • 如果读出错，则从其他可读的地方读

TAO 的架构​

• MySQL数据库 → 持久性（durability）
• Leader缓存 → 协调每个对象的写操作
• Follower缓存 → 用来读而不是用来写。转移所有的写操作到leader缓存。

读操作的容错

动机​

如何在规模上保持用户的观看数据（每天数十亿事件）？

在这里，观看数据指的是...

1. 观看历史。我看过哪些标题？
2. 观看进度。我在某个标题中停留在哪里？
3. 正在观看的内容。我的账户现在还在观看什么？

架构​

观看服务有两个层次：

1. 有状态层 = 活动视图存储在内存中

   • 为什么？为了支持最高的读/写量
   • 如何扩展？
     • 按照 account_id mod N 分区为 N 个有状态节点
       • 一个问题是负载分布不均，因此系统容易出现热点
     • 在 CAP 定理 下选择 CP 而非 AP，并且没有活动状态的副本。
       • 一个失败的节点将影响 1/n 的成员。因此，他们使用过时的数据以优雅地降级。

2. 无状态层 = 数据持久性 = Cassandra + Memcached

   • 使用 Cassandra 进行非常高的写入量和低延迟。
     • 数据均匀分布。由于使用虚拟节点进行一致性哈希来分区数据，因此没有热点。
   • 使用 Memcached 进行非常高的读取量和低延迟。
     • 如何更新缓存？
       • 在写入 Cassandra 后，将更新的数据写回 Memcached
       • 最终一致性，以处理多个写入者，具有短的缓存条目 TTL 和定期的缓存刷新。
     • 将来，优先考虑 Redis 的追加操作到时间排序列表，而不是 Memcached 中的“读-修改-写”。

为什么API会不可靠？

1. 网络会出错
2. 服务器会出错

怎么解决这个问题呢？三个原则

1. 客户端用“重试”来保证状态的一致性

2. 重试的请求里要有==幂等的唯一性ID==

   1. 在 RESTful API 设计里面，PUT 和 DELETE 的语义本身是幂等的
   2. 但是 POST 在在线支付领域可能会导致==“重复付两次钱”的问题==，所以我们用“幂等的唯一性ID”来识别某个请求是否被发了多次
      1. 如果错误发生在到达服务器之前，重试过后，服务器第一次见到它，正常处理
      2. 如果错误发生在服务器，基于这个“唯一性ID”，用 ACID 的数据库保证这个事务只发生一次
      3. 如果错误发生在服务器返回结果之后，重试过后，服务器只需要返回缓存过的成功的结果

3. 重试要负责任，比如遵循==指数退避算法==，因为不希望一大波客户端同时重试。

举个例子，Stripe 的客户端是这样计算重试的等待时间的：

def self.sleep_time(retry_count)
  # Apply exponential backoff with initial_network_retry_delay on the
  # number of attempts so far as inputs. Do not allow the number to exceed
  # max_network_retry_delay.
  sleep_seconds = [Stripe.initial_network_retry_delay * (2 ** (retry_count - 1)), Stripe.max_network_retry_delay].min

  # Apply some jitter by randomizing the value in the range of (sleep_seconds
  # / 2) to (sleep_seconds).
  sleep_seconds = sleep_seconds * (0.5 * (1 + rand()))

  # But never sleep less than the base sleep seconds.
  sleep_seconds = [Stripe.initial_network_retry_delay, sleep_seconds].max

  sleep_seconds
end

==一个字：拆==

==AKF扩展立方==告诉了我们"拆"的三个纬度：

1. ==水平扩展== 把很多无状态的服务器放在负载均衡器或者反向代理的后面，这样每个请求都能被其中任意一个服务器受理，就不会有单点故障了。
2. ==业务拆分== 典型的按照功能分的微服务，比如 auth service, user profile service, photo service, etc
3. ==数据分割== 分割出整套技术栈和数据存储专门给特定的一大组用户，比如优步有中国和美国的数据中心，每个数据中心内部有不同的 Pod 给不同的城市或地区。

KV Cache的本质是为了减少访问数据的延迟。比如，把存在又贵又慢的媒体上的数据库的O(logN)的读写和复杂的查询，变成存在又快又贵的媒体上的 O(1)的读写。cache 的设计有很多策略，常见的有 read-through/write-through(or write-back) 和 cache aside.

常见的互联网服务读写比是 100:1 到 1000:1，我们常常对读做优化。

在分布式系统中，这些 pattern 的组合都是 consistency, availability, partition tolerance 之间的 trade-off，要根据你的业务需求具体 选择。

一般的策略​

• 读
  • Read-through: clients 和 databases 之间加一层 cache layer，clients 不直接访问数据库，clients 通过 cache 间接访问数据库。 读的时候 cache 里面没有东西则从database更新再返回，有则直接返回。
• 写
  • Write-through: clients 先写数据到 cache，cache 更新 database，只有 database 最终更新了，操作才算完成。
  • write-behind/Write-back: clients 先写数据到 cache，先返回。回头将 cache 异步更新到 database. 一般来讲 write-back 是最快的
  • Write-around: client 写的时候绕过 cache 直接写数据库。

cache aside pattern​

Cache 不支持 read-through 和 write-through/write-behind 的时候用 Cache aside pattern

读数据? 命中 cache 读 cache，没命中 cache 读 database 存 cache 改数据? 先改 database，后删除 cache entry

为什么不是写完数据库后更新缓存？主要是怕两个并发的 database 写操作导致两个并发的 cache 更新导致脏数据。

是不是Cache Aside这个就不会有并发问题了？还是有很低的概率有可能发生脏数据，就是一边读 database 并更新 cache 的时候，一边更新 database 并删除 cache entry

缓存放在哪？​

• client side,
• distinct layer
• server side

缓存大小不够用的话怎么办？缓存回收策略(cache replacement policies)​

• LRU - least-recently used 看时间，只保留最近时间使用的，回收最近时间没使用的
• LFU - least-frequently used 看次数，只保留使用次数最多的，回收使用次数最少的
• ARC 性能比LRU好，大致做法是既保持 RU，又保持 FU，还记录了最近回收的历史。

缓存用起来谁家强？​

为什么要重视软技能？​

因为你的工作会被软技能强的人抢走。

美国人的讲话能力非常强，从小学校教育就重视表达，一说话都是一套一套的。那么在同等情况下，哪怕中国人的技术更好，工作机会也被美国人抢走了。这个其实不是种族歧视，是自我表达能力的问题。

像印度人，在美国的势力非常强大，尤其是在高科技公司管理层这一块，中国人的势力远远不如印度人。这也是因为印度人讲故事的能力特别强。印度人的英语发音并不标准，但是他们敢说，而且往往能说到点子上。所以我们经常看到的局面就是一个印度经理欺负他手下几个技术比他好的中国员工。我们经常嘲笑印度人是 “PPT 治国”，但是这个讲故事的能力你不可不察。

这也说明“自由技艺”的软技能，是我们当代中国人的一个短板。

面试的本质是回答下面三个问题​

1. 能干不能干
2. 想干不想干
3. 合拍不合拍

如何回答这三个问题？​

面试的五个谈话点。

1.逆境。强调的可不是困难有多大，而是你是如何战胜这些困难的。你要证明自己不但没被逆境杀死，而且更强大了。最好举重若轻，把明明很大的困难轻描淡写，充满乐观情绪。然后你要顺便感谢一下在困境中曾经帮助过你的人，让人感觉到你是一个懂得感恩的人。

2.影响力。所有的交流问题本质上都是领导力问题，所有的领导力问题本质上就是交流问题。如果你善于说服别人，说明你天生就具备领导力。

3.技术水平。有什么故事能够展现你的技术水平？

4.合拍。美国联邦调查局（FBI）以前面试人的时候，喜欢问应聘者看过什么书。应聘者就会报一大堆书名，但其实 FBI 最想听的是他们看过汤姆.克兰西（Tom Clancy）的间谍小说。有一段时间，凡是说看过克兰西间谍小说的人都容易被录取。后来这个内部信息被传出去了，然后每个来面试的人都这么说，这招就不好使了。

5.成就。和别人相比，你有没有什么出类拔萃的地方。这就是你吹嘘以往成就的机会。成就不一定是实际的工作经验。

再往大了说，连美国总统竞选也是这个套路。奥巴马说，我父亲是一个移民，后来他抛弃了我妈妈，我从小在一个单亲家庭长大我是一个黑人我怎么怎么不容易……但是这些都不叫事儿现在的我就是这么乐观而又强大。特朗普说我做过这个项目这个项目和这个项目，现在我想做造福美国的大项目。

如何准备这五个谈话点？​

• 多尝试，经历失败，丰富你的人生经验；
• 多跟人交往，练习交流和组织能力；
• 学点技术，掌握一些实用工具；
• 要善于做调研，了解你所在的领域正在发生什么事儿；找机会取得能让自己脱颖而出的成绩。

ACID（一致性优先于可用性）

• 原子性确保事务要么完全成功，要么完全失败。
• 一致性：在 ACID 中，C 表示事务保留所有数据库规则，如唯一键、触发器、级联等。相比之下，CAP 中的 C 仅指单一副本一致性，是 ACID 一致性的严格子集。
• 隔离性确保并发执行的事务使数据库保持在与顺序执行事务相同的状态。
• 持久性确保一旦事务提交，即使在系统故障（如断电或崩溃）情况下也会保持提交状态。

BASE（可用性优先于一致性）

• 基本可用表示系统确保可用。
• 软状态表示系统的状态可能随时间变化，即使没有输入。这主要是由于最终一致性模型导致的。
• 最终一致性表示只要系统在一定时间内不接收输入，系统最终将达到一致状态。

虽然大多数 NoSQL 采用 BASE 原则，但它们正逐渐学习或转向 ACID，例如，Google Spanner 提供强一致性，MongoDB 4.0 增加了对多文档 ACID 事务的支持。