42 篇博文 含有标签「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之前，用 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缓存。

读操作的容错

为什么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.成就。和别人相比，你有没有什么出类拔萃的地方。这就是你吹嘘以往成就的机会。成就不一定是实际的工作经验。

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

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

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