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

为什么需要这样一个协议？​

使用HTTP直播流的移动视频播放服务有以下问题：

1. ==手机的内存和外存有限==。
2. 受制于不稳定的网络连接以及不同的带宽，需要==在传输过程中动态调整传输视频的质量==。

解决方法​

1. 服务器层面：在典型的设置中，编码硬件接受音视频输入，将其编码为H.264格式的视频和ACC格式的音频，然后将他们以MPEG-2格式流输出。
   1. 其后通过一个软件分流器将原始输出流分割为一系列短媒体文件（长度可能为10s的.ts文件）。
   2. 分流器同时也会维护一个包含所有媒体文件列表的索引文件（.m3u8格式）。
   3. 将以上步骤生成的媒体文件和索引文件发布在网络服务器上。
2. 客户端层面：客户端读取索引，然后向服务器顺序请求所需要的媒体文件，并且流畅地将各个短媒体文件的内容播放出来。

架构​

为什么 Facebook 要自己做图片存储？​

• PB级别的Blob数据量
• 传统的基于NFS的设计（每个图像存储为文件）都存在元数据瓶颈：庞大的元数据严重限制了元数据命中率。
  • 以下是细节解释：

对于图片应用程序，图片的权限等大多数元数据是无用的，从而浪费了存储空间。然而，更大的开销在于，必须将文件的元数据从磁盘读入内存中才能找到文件本身。虽然对于小规模存储来说这微不足道，但当乘以数十亿的照片和数PB的数据时，那么访问元数据将是吞吐量的瓶颈。

解决方案​

通过把数以十万计的图像聚集到单个Haystack存储文件中，从而消除了元数据负荷。

结构​

数据布局​

索引文件（用于快速加载内存）+ 包含很多图片的haystack存储文件。

索引文件布局

储存文件

CRUD操作​

• 增: 写入存储文件，然后==异步==写入索引文件，因为建立索引并不是关键的步骤。
• 删: 通过在标志字段中标记已删除的位来进行软删除。通过紧凑操作执行硬删除。
• 改: 在更新时，只能追加 (append-only)，如果遇到了重复的键，应用程序可以选择具有最大偏移量的键去改和读。
• 查: 读取操作（偏移量，健，备用键，Cookie 以及数据大小）

用例​

上传

下载

为什么要关注架构？​

答案：为了降低每个功能的人力资源成本。

移动开发者从三个维度评估架构。

1. 功能参与者之间责任的平衡分配。
2. 可测试性
3. 易用性和可维护性

紧耦合 MVC​

例如，在一个多页面的 web 应用中，一旦点击链接导航到其他地方，页面会完全重新加载。问题在于视图与控制器和模型紧密耦合。

Cocoa MVC​

苹果的 MVC 理论上通过控制器将视图与模型解耦。

实际上，苹果的 MVC 鼓励 ==庞大的视图控制器==。而视图控制器最终负责所有事情。

测试耦合的庞大视图控制器是困难的。然而，Cocoa MVC 在开发速度方面是最佳的架构模式。

MVP​

在 MVP 中，呈现者与视图控制器的生命周期无关，视图可以轻松模拟。我们可以说 UIViewController 实际上就是视图。

还有另一种 MVP：带有数据绑定的 MVP。正如你所看到的，视图与其他两个之间存在紧密耦合。

MVVM​

它类似于 MVP，但绑定是在视图和视图模型之间。

VIPER​

与 MV(X) 相比，VIPER 有五个层次（VIPER 视图、交互器、呈现者、实体和路由）。这很好地分配了责任，但可维护性较差。

与 MV(X) 相比，VIPER

1. 模型逻辑转移到交互器，实体作为简单的数据结构保留。
2. ==与 UI 相关的业务逻辑放入呈现者，而数据修改能力放入交互器==。
3. 引入路由器负责导航。

设计一个系统，可以将用户给的网址变成短网址，用户使用这些短网址可以访问他们原来给的网址（下面简称长网址）。描述这个系统是怎么运作的，需包括但不限于下面的问题：怎么分配短网址？怎么存储短网址和长网址的映射关系？怎么实现跳转服务？怎么存储访问数据？

假设：在一开始的问题描述中不包含这些假设。一个优秀的面试者在得到一个具体设计的时候会问关于系统规模的问题。

• 长网址的域名大概有上万个
• 新的长网址流量大概是 10,000,000/天 （100/秒）
• 使用短网址访问长网址的跳转服务的流量大概是 10B/天 （100,000/秒）
• 提醒面试者这些是平均数字 - 在一些高峰期的时候这些数字会大很多（一种时间导致的高峰期，比如用户刚工作完回家的时候， 另一种是事件导致的高峰期，比如春节联欢晚会的时候）
• 最近的数据（比如今天的数据）应该被提前收集好，并且在用户想要看的时候可以在五分钟内得到。
• 每天计算历史数据

假设​

每天有1B新网址，100B的短网址访问 短网址越短越好 数据的展示（实时/每天/每个月/每年）

网址编码​

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

方法1. md5(128位，16个16进制数字，冲突，生日悖论，2^(n/2) = 2^64) 再短一些？（64位，8个16进制数字，冲突 2^32）, 64进制。

• 优点：哈希比较简单 而且 易于横向拓展。
• 缺点：太长，怎么去处理过期的网址？

方法2. 分布式的序号生成器。(62进制: az, AZ, 0~9, 62种字符, 62^7), 分区：每个节点包含一些序号。

• 优点：容易淘汰过期的网址，网址更短
• 缺点：不同分区之间的协调（zookeeper)

键值（KV）存储​

MySQL(10k 每秒访问量，慢，没有关系不需要关系型数据库)，键值（100k 每秒访问量，Redis, Memcached）

一个优秀的面试者会问关于短网址的预期使用期限，设计一套系统可以自动清理已经过期的短网址。

跟进​

问题：怎么生成短网址？

• 一个差的面试者 会提议用一个id生成器（单点故障）或者要在每个id生成的时候需要id生成器之间协同合作。 举例，使用自动增值的主键（auto-increment primary key）的数据库。
• 一个可以接受的面试者 会提议用md5，或者一些UUID生成器可以在一些结点上自己生成id的。这些方法可以在分布式系统上生成不冲突的ID，所以可以生产大量的短网址。
• 一个优秀的面试者 会设计一个方法利用一些id生成器，每个生成器先从中央协调器（例如ZooKeeper）保留一块id序列，这些id生成器可以单独从他们的id序列中分配id，有必要的时候在自己的id序列中做一些清理。

问题：怎么存储长网址和短网址之间的映射关系？

• 一个差的面试者 会建议使用一个单一的，非分布式，非关系型的数据库。它只是一个单纯的键值数据库。
• 一个优秀的面试者 会建议用简便的分布式系存储，例如 MongoDB/HBase/Voldemort 等。
• 一个更优秀的面试者 会问关于短网址的预期使用周期，然后设计一套系统==可以清理过期的短网址==。

问题：怎么实现跳转服务？

• 一个差的面试者 会从头开始设计这套系统来解决已经被解决的问题
• 一个优秀的面试者 会建议使用一个现成的HTTP服务器加上一个插件，用这个插件来翻译这个短网址的id，在数据库中找这个id，更新访问数据，返回303，跳转到长网址。 现成HTTP服务器比如 Apache/Jetty/Netty/tomcat 等。

问题：怎么存储访问数据？

• 一个差的面试者 会建议每次访问都写到数据库。
• 一个优秀的面试者 会建议由几个不同部分去做这件事情==生成访问流数据，收集整理，每过一段时间写到永久数据库中==。

问题：怎么分上一个问题优秀面试者提出的存储访问数据的不同部分？

• 一个优秀的面试者 会建议用一个延迟较低的信息系统去暂时存储访问数据，然后将数据交给收集整理部分
• 面试者可能会问访问数据多久需要被更新一次。如果每天更新，一个比较合理的方法是存储在HDFS，用map/reduce去计算数据。 如果是要近乎实时的数据，收集整理的部分就要计算出所需的数据

问题：怎么阻止访问受限的网站？

• 一个优秀的面试者 会要求在键值数据库里维护一个域名的黑名单。
• 一个好的面试者 可能会提出一些先进的技术， 可以用在系统规模变得很大的情况下， 比如bloom filter。

失效转移：失效转移（failover）是一种备份操作模式，用于提高系统稳定性和可用性。当主要组件由于失效或预定关机时间的原因而无法工作时，这种模式中的系统组件（如处理机、服务器、网络或数据库）的功能被转嫁到二级系统组件。

冷备份:冷备份是将关键性文件拷贝到另外的位置的一种说法，使用特征或指标/警报来跟踪故障。系统在发生故障时提供新的备用节点，当然，冷备份仅适用于无状态服务。对于备份Oracle数据库而言，冷备份是最快和最安全的方法。

热备份:保持两个活动系统承担相同的任务角色，也就是系统处于正常运转状态下的备份。两个系统中数据几乎是实时镜像的，且拥有相同的数据。

温备份:保持两个活动系统，除非发生故障，否则次要系统不占用流量。

检查点(或类似于Redis快照):系统在处理任务之前使用预先写入（write-ahead）日志(WAL)记录请求。备用节点在故障转移期间从日志中恢复。

• 缺点
  • 大量的日志恢复起来很耗时
  • 自上次检查点以来丢失数据
• 用户案例:Storm, WhillWheel, Samza

双主机(或全部主机)模式:将两个活动系统保留在负载平衡器之后。主机之间是平行的，且数据复制是双向的。

为什么要使用lambda架构？​

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

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

例如：以传统方式扩展网页浏览数据记录的问题

1. 首先使用传统的关系数据库
2. 然后添加一个“发布/订阅”模式队列
3. 然后通过横向分区或者分片的方式来扩展规模
4. 容错性问题开始出现
5. 数据损坏(data corruption)的现象开始出现

关键问题在于AKF扩展立方体中，==仅有X轴的水平分割一个维度是不够的，我们还需要引入Y轴的功能分解。而 lambda 架构可以指导我们如何为一个数据系统实现扩展==。

什么是lambda架构​

如果我们将一个数据系统定义为以下形式：

Query=function(all data)

那么一个lamda架构就是

batch view = function(all data at the batching job's execution time)
realtime view = function(realtime view, new data)

query = function(batch view. realtime view)

==lambda架构 = 读写分离(批处理层 + 服务层) + 实时处理层==

跳跃表本质上是一个允许对其进行二分搜索的链表。它实现这一点的方法是添加额外的节点，使你能够“跳过”链接列表的部分。对于给定一个正反随机数来创建额外的节点，跳跃表具有O(logn)复杂度的查询、插入和删除。

用例

• LevelDB MemTable
• Redis 有序集合(Redis SortedSet)
• 倒排索引(Lucene inverted index)

布隆过滤器(Bloom filter)是一种数据结构，用于以远高于其他一般算法的空间和时间效率来检索一个元素是否在一个集合中。

使用布隆过滤器获得的结果，可能为假阳性匹配，但是不可能为假阴性匹配。换句话说，查询返回的结果是“==要么在可能不在，要么不在肯定不在==”。元素可以添加到集合中，但不能删除（尽管这可以通过额外的“计数”布隆过滤器来解决）；添加到集合中的元素越多，误报的可能性越大。

用例

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

目标受众​

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

问题描述​

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

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

面试官提示​

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

得分​

优秀的候选人能够：

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

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

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

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

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

而好的候选人能够：

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

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

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

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

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

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

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

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

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

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

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

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缓存。

读操作的容错