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

免责声明：以下所有内容均来自公共资源或纯粹原创。 这里不包含优步的涉密内容。

要求​

• 为全球的交通运输市场提供服务
• 大规模的实时调度
• 后端设计

架构​

为何要微服务？​

==Conway定律== 软件的系统结构会对应企业的组织结构。

结合单体 ==代码库== 和微服务可以同时利用两者的长处.

调度服务​

• 由geohash提供一致的哈希地址
• 数据在内存中是瞬态的，因此不需要复制. (CAP: AP高于CP)
• 分片中使用单线程或者锁，以防止双重调度

支付服务​

==关键是要有异步设计==, 因为跨多个系统的ACID交易支付系统通常具有非常长的延迟.

• 利用事件队列
• 支付接口集成 Braintree, PayPal, Card.io, Alipay 等
• 通过详尽的 log 来记录所有 event
• 使用具有等幂性、指数退避和随机抖动的API

用户档案服务和行程记录服务​

• 使用缓存降低延迟
• 随着 1) 支持更多的国家和地区 2) 用户角色（司机，骑手，餐馆老板，食客等）逐渐增加，为这些用户提供用户档案服务也面临着巨大的挑战。

通知推送服务​

• 苹果通知推送服务 (不可靠)
• 谷歌云消息服务GCM （它可以检测到是否成功递送) 或者
• 短信服务通常更可靠

我们为什么要在架构上费心思？​

答案是：为了减少在每做一个功能的时候所耗费的人力资源。

移动开发人员会在以下三个层面上评估一个架构的好坏：

1. 各个功能分区的职责分配是否均衡
2. 是否具有易测试性
3. 是否易于使用和维护

紧耦合MVC​

举一个例子，在一个多页面的网页Web应用程序中，当你点击一个链接导航至其他页面的时候，该页面就会被全部重新加载。该架构的问题在于视图（View）与控制器（Controller）和模型（Model）是紧密耦合的。

Cocoa MVC​

Cocoa MVC 是苹果公司建议iOS开发者使用的架构。理论上来说，该架构可以通过控制器（Controller）将模型（Model）与视图（View）剥离开。

然而，在实际操作过程中，Cocoa MVC 鼓励大规模视图控制器的使用，最终使得视图控制器完成所有操作。

尽管测试这样的耦合大规模视图控制器是十分困难的，然而在开发速度方面，Cocoa MVC是现有的这些选择里面表现最好的。

MVP​

在MVP中，Presenter与视图控制器（view controller）的生命周期没有任何关系，视图可以很轻易地被取代。我们可以认为UIViewController实际上就是视图（View）。

还有另外一种类型的MVP：带有数据绑定的MVP。如下图所示，视图（View）与模型（Model）和控制器（Controller）是紧密耦合的。

MVVM​

MVVM与MVP相似不过MVVM绑定的是视图（View）与视图模型（View Model）。

VIPER​

不同于MV(X)的三层结构，VIPER具有五层结构（VIPER View, Interactor, Presenter, Entity, 和 Routing）。这样的结构可以很好地进行职责分配但是其维护性较差。

相较于MV(X)，VIPER有下列不同点：

1. Model 的逻辑处理转移到了 Interactor 上，这样一来，Entities 没有逻辑，只是纯粹的保存数据的结构。
2. ==UI相关的业务逻辑分在Presenter中，数据修改功能分在Interactor中==。
3. VIPER为实现模块间的跳转功能引入了路由模块 Router 。

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

使用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浏览器曾使用布隆过滤器来识别恶意链接。