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

KV 缓存就像一个巨大的哈希映射，用于减少数据访问的延迟，通常通过

1. 将来自慢速且便宜介质的数据转移到快速且昂贵的介质上。
2. 从基于树的数据结构的 O(log n) 索引转为基于哈希的数据结构的 O(1) 进行读写。

有各种缓存策略，如读穿/写穿（或写回）和旁路缓存。总体而言，互联网服务的读写比为 100:1 到 1000:1，因此我们通常会优化读取。

在分布式系统中，我们根据业务需求和上下文选择这些策略，并在 CAP 定理 的指导下进行选择。

常规模式​

• 读取
  • 读穿：客户端通过缓存层从数据库读取数据。当读取命中缓存时，缓存返回；否则，它从数据库获取数据，缓存后再返回值。
• 写入
  • 写穿：客户端写入缓存，缓存更新数据库。缓存在完成数据库写入后返回。
  • 写后 / 写回：客户端写入缓存，缓存立即返回。在缓存写入的背后，缓存异步写入数据库。
  • 绕过写入：客户端直接写入数据库，绕过缓存。

旁路缓存模式​

当缓存不支持原生的读穿和写穿操作，并且资源需求不可预测时，我们使用这种旁路缓存模式。

• 读取：尝试命中缓存。如果未命中，则从数据库读取，然后更新缓存。
• 写入：先写入数据库，然后 ==删除缓存条目==。这里一个常见的陷阱是 人们错误地用值更新缓存，而在高并发环境中双重写入会使缓存变脏。

==在这种模式下仍然存在缓存变脏的可能性。== 当满足以下两个条件时，会发生这种情况：

1. 读取数据库并更新缓存
2. 更新数据库并删除缓存

缓存放在哪里？​

• 客户端
• 独立层
• 服务器端

如果数据量达到缓存容量怎么办？使用缓存替换策略​

• LRU（最近最少使用）：检查时间，驱逐最近使用的条目，保留最近使用的条目。
• LFU（最不常用）：检查频率，驱逐最常用的条目，保留最常用的条目。
• ARC（自适应替换缓存）：其性能优于 LRU。通过同时保留最常用和频繁使用的条目，以及驱逐历史来实现。（保留 MRU + MFU + 驱逐历史。）

谁是缓存使用的王者？​

Facebook TAO

动机与假设​

• PB 级 Blob 存储
• 传统的基于 NFS 的设计（每张图像存储为一个文件）存在元数据瓶颈：大的元数据大小严重限制了元数据命中率。
  • 进一步解释元数据开销

对于照片应用，大部分元数据（如权限）未被使用，从而浪费了存储容量。然而，更重要的成本在于，文件的元数据必须从磁盘读取到内存中，以便找到文件本身。在小规模上这并不显著，但在数十亿张照片和 PB 级数据的情况下，访问元数据成为了吞吐量瓶颈。

解决方案​

通过将数十万张图像聚合在一个单一的 haystack 存储文件中，消除了元数据开销。

架构​

数据布局​

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

索引文件布局

haystack 存储文件

CRUD 操作​

• 创建：写入存储文件，然后 ==异步== 写入索引文件，因为索引不是关键的
• 读取：read(offset, key, alternate_key, cookie, data_size)
• 更新：仅追加。如果应用程序遇到重复键，则可以选择具有最大偏移量的一个进行更新。
• 删除：通过在标志字段中标记删除位进行软删除。硬删除通过压缩操作执行。

用例​

上传

下载

免责声明：以下所有内容均来自公共来源或纯原创。这里没有 Uber 机密信息。

需求​

• 针对全球交通市场的打车服务
• 大规模实时调度
• 后端设计

架构​

为什么选择微服务？​

==康威定律== 表示软件系统的结构是组织结构的复制。

结合单体 ==代码库== 和微服务可以带来双方的好处。

调度服务​

• 一致性哈希按地理哈希分片
• 数据是瞬态的，存在内存中，因此无需复制。(CAP: AP 优于 CP)
• 在分片中使用单线程或锁定匹配以防止双重调度

支付服务​

==关键是采用异步设计==，因为支付系统通常在多个系统之间的 ACID 事务中具有非常长的延迟。

• 利用事件队列
• 支付网关与 Braintree、PayPal、Card.io、支付宝等集成
• 密集记录以跟踪所有内容
• 具有幂等性、指数退避和随机抖动的 API

用户资料服务和行程服务​

• 低延迟与缓存
• 用户资料服务面临为越来越多类型的用户（司机、乘客、餐厅老板、吃货等）和不同地区和国家的用户架构提供服务的挑战。

推送通知服务​

• 苹果推送通知服务（可靠性不高）
• 谷歌云消息服务 GCM （可以检测可送达性）或
• 短信服务通常更可靠

需求​

1. 数据大小：值的数据大小过大，无法保存在内存中，我们应该利用外部存储来存储它们。然而，我们仍然可以将数据键保存在内存中。
2. 单主机解决方案。没有分布式设计。
3. 优化写入。

解决方案​

• 内存哈希表索引 + 索引提示文件 + 数据文件
• 仅追加以优化写入。仅有一个活动数据文件用于写入。并将活动数据压缩到旧的数据文件中以供读取。

组件​

1. 内存中的 HashMap<Key, <FildId, ValueOffset, ValueSize, Timestamp>>

2. 数据文件布局

|crc|timestamp|key_size|value_size|key|value|
...

3. （索引）提示文件，内存哈希表可以从中恢复

操作​

删除：通过内存哈希表获取位置，如果存在，则前往磁盘上的位置将值设置为一个魔法数字。

获取：通过内存哈希表获取位置，然后前往磁盘上的位置获取值。

放置：追加到活动数据文件并更新内存哈希表。

定期压缩策略

• 复制最新条目：内存哈希表始终是最新的。停止并复制到新文件中。时间复杂度为 O(n)，n 是有效条目的数量。

  • 优点：对于过期或删除的条目效率高。
  • 缺点：如果过期的条目很少，会消耗存储空间。可能会使空间翻倍。（可以通过让一个辅助节点定期进行压缩工作来解决，例如，Hadoop 辅助名称节点）。

• 扫描并移动：对于每个条目，如果是最新的，移动到已验证部分的尾部。时间复杂度为 O(n)，n 是所有条目的数量。

  • 优点：
    • 缩小大小
    • 不需要额外的存储空间
  • 缺点：
    • 复杂，需要通过事务同步哈希表和存储。可能会影响性能。

后续问题

• 如何检测可以压缩的记录？
  • 使用时间戳。
• 如果一个哈希表无法适应单台机器的内存怎么办？
  • 一致性哈希，Chord DHT，查询时间复杂度为 O(logn)，使用指针表，而不是这里的 O(1) 使用哈希表。

冷备份：使用心跳或指标/警报来跟踪故障。当发生故障时，配置新的备用节点。仅适用于无状态服务。

热备份：保持两个活动系统承担相同的角色。数据几乎实时镜像，两个系统将拥有相同的数据。

温备份：保持两个活动系统，但第二个系统在故障发生之前不接收流量。

检查点（或类似于 Redis 快照）：使用预写日志（WAL）在处理之前记录请求。备用节点在故障转移期间从日志中恢复。

• 缺点
  • 对于大型日志来说耗时较长
  • 自上次检查点以来丢失数据
• 使用案例：Storm、WhillWheel、Samza

主动-主动（或全活动）：在负载均衡器后保持两个活动系统。它们并行处理。数据复制是双向的。

设计一个系统，将用户提供的网址转换为缩短的网址，并重定向回原始网址。描述系统的工作原理。你将如何分配缩短的网址？你将如何存储缩短网址与原始网址的映射？你将如何实现重定向服务器？你将如何存储点击统计数据？

假设：我通常不会在初始问题陈述中包含这些假设。优秀的候选人会在提出设计时询问规模。

• 注册重定向网址的独特域名总数大约在数万左右
• 新网址注册量约为 10,000,000/天（100/秒）
• 重定向请求量约为 10B/天（100,000/秒）
• 提醒候选人这些是平均数字 - 在高峰流量时（例如“人们下班回家时”或“超级碗期间”）可能会高得多。
• 最近的统计数据（在当前日期内）应聚合并在 5 分钟延迟后可用
• 长期回顾统计数据可以每天计算

假设​

每天 1B 新网址，总共 100B 条目 越短越好 显示统计数据（实时和每日/月度/年度）

编码网址​

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

选择 1. md5（128 位，16 个十六进制数字，碰撞，生日悖论，2^(n/2) = 2^64）截断？（64 位，8 个十六进制数字，碰撞 2^32），Base64。

• 优点：哈希简单且水平可扩展。
• 缺点：太长，如何清理过期网址？

选择 2. 分布式序列 ID 生成器。（Base62：az，AZ，0~9，62 个字符，62^7），分片：每个节点维护一部分 ID。

• 优点：易于淘汰过期条目，更短
• 缺点：协调（zookeeper）

KV 存储​

MySQL（10k qps，慢，无关系），KV（100k qps，Redis，Memcached）

优秀的候选人会询问别名的生命周期，并设计一个系统来清理过期的别名。

后续问题​

问：如何生成缩短的网址？

• 一个差的候选人会提出一个使用单一 ID 生成器的解决方案（单点故障）或一个在每个请求中需要协调 ID 生成器服务器的解决方案。例如，使用自增主键的单一数据库服务器。
• 一个可接受的候选人会提出使用网址的 md5，或某种形式的 UUID 生成器，可以在任何节点独立完成。虽然这允许分布式生成不冲突的 ID，但会产生较大的“缩短”网址。
• 一个优秀的候选人会设计一个解决方案，利用一组 ID 生成器，从中央协调器（例如 ZooKeeper）保留 ID 空间的块，并独立从其块中分配 ID，必要时刷新。

问：如何存储映射？

• 一个差的候选人会建议使用单体数据库。这个存储没有关系方面。它是一个纯粹的键值存储。
• 一个优秀的候选人会建议使用任何轻量级的分布式存储。MongoDB/HBase/Voldemort 等等。
• 一个优秀的候选人会询问别名的生命周期，并设计一个系统来==清理过期的别名==。

问：如何实现重定向服务器？

• 一个差的候选人会从头开始设计某种东西来解决一个已经解决的问题。
• 一个优秀的候选人会建议使用现成的 HTTP 服务器，配备一个插件，解析缩短的网址键，在数据库中查找别名，更新点击统计并返回 303 到原始网址。Apache/Jetty/Netty/tomcat 等等都可以。

问：点击统计数据如何存储？

• 一个差的候选人会建议在每次点击时写回数据存储。
• 一个优秀的候选人会建议某种形式的==聚合层，接受点击流数据，聚合并定期写回持久数据存储==。

问：如何对聚合层进行分区？

• 一个优秀的候选人会建议使用低延迟消息系统来缓冲点击数据并将其传输到聚合层。
• 一个候选人可能会询问统计数据需要多频繁更新。如果是每日更新，将其存储在 HDFS 中并运行 map/reduce 作业来计算统计数据是一个合理的方法。如果是近实时的，聚合逻辑应计算统计数据。

问：如何防止访问受限网站？

• 一个优秀的候选人可以回答通过在 KV 存储中维护一个主机名黑名单。
• 一个优秀的候选人可能会提出一些高级扩展技术，如布隆过滤器。

为什么选择 Lambda 架构？​

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

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

例如，传统方式扩展页面查看服务的问题

1. 你从传统关系数据库开始。
2. 然后添加一个发布-订阅队列。
3. 然后通过水平分区或分片进行扩展。
4. 故障容错问题开始出现。
5. 数据损坏发生。

关键点是 ==AKF 规模立方体 的 X 轴维度单独并不足够。我们还应该引入 Y 轴 / 功能分解。Lambda 架构告诉我们如何为数据系统做到这一点。==

什么是 Lambda 架构？​

如果我们将数据系统定义为

查询 = 函数（所有数据）

那么 Lambda 架构是

批处理视图 = 函数（批处理作业执行时的所有数据）
实时视图 = 函数（实时视图，新数据）

查询 = 函数（批处理视图，实时视图）

==Lambda 架构 = CQRS（批处理层 + 服务层） + 快速层==

关系数据库是大多数存储使用案例的默认选择，原因在于 ACID（原子性、一致性、隔离性和持久性）。一个棘手的问题是“一致性”——它意味着任何事务都会将数据库从一个有效状态转变为另一个有效状态，这与 CAP 定理 中的一致性不同。

模式设计和第三范式 (3NF)​

为了减少冗余并提高一致性，人们在设计数据库模式时遵循 3NF：

• 1NF：表格形式，每个行列交集只包含一个值
• 2NF：只有主键决定所有属性
• 3NF：只有候选键决定所有属性（且非主属性之间不相互依赖）

数据库代理​

如果我们想消除单点故障怎么办？如果数据集太大，无法由单台机器承载怎么办？对于 MySQL，答案是使用数据库代理来分配数据，可以通过集群或分片。

集群是一种去中心化的解决方案。一切都是自动的。数据会自动分配、移动和重新平衡。节点之间互相传递信息（尽管这可能导致组隔离）。

分片是一种集中式解决方案。如果我们去掉不喜欢的集群属性，分片就是我们得到的结果。数据是手动分配的，不会移动。节点之间互不知晓。

在一个常规的互联网服务中，读取与写入的比例大约是 100:1 到 1000:1。然而，从硬盘读取时，数据库连接操作耗时，99% 的时间花费在磁盘寻址上。更不用说跨网络的分布式连接操作了。

为了优化读取性能，非规范化通过添加冗余数据或分组数据来引入。这四种 NoSQL 类型可以帮助解决这个问题。

键值存储​

键值存储的抽象是一个巨大的哈希表/哈希映射/字典。

我们希望使用键值缓存的主要原因是为了减少访问活跃数据的延迟。在快速且昂贵的介质（如内存或 SSD）上实现 O(1) 的读/写性能，而不是在传统的慢且便宜的介质（通常是硬盘）上实现 O(logn) 的读/写性能。

设计缓存时需要考虑三个主要因素。

1. 模式：如何缓存？是读透/写透/写旁/写回/缓存旁？
2. 放置：将缓存放在哪里？客户端/独立层/服务器端？
3. 替换：何时过期/替换数据？LRU/LFU/ARC？

现成的选择：Redis/Memcache？Redis 支持数据持久化，而 Memcache 不支持。Riak、Berkeley DB、HamsterDB、Amazon Dynamo、Project Voldemort 等等。

文档存储​

文档存储的抽象类似于键值存储，但文档（如 XML、JSON、BSON 等）存储在键值对的值部分。

我们希望使用文档存储的主要原因是灵活性和性能。灵活性通过无模式文档实现，性能通过打破 3NF 来提高。初创公司的业务需求时常变化。灵活的模式使他们能够快速行动。

现成的选择：MongoDB、CouchDB、Terrastore、OrientDB、RavenDB 等等。

列式存储​

列式存储的抽象就像一个巨大的嵌套映射：ColumnFamily<RowKey, Columns<Name, Value, Timestamp>>。

我们希望使用列式存储的主要原因是它是分布式的、高可用的，并且针对写入进行了优化。

现成的选择：Cassandra、HBase、Hypertable、Amazon SimpleDB 等等。

图数据库​

顾名思义，这种数据库的抽象是一个图。它允许我们存储实体及其之间的关系。

如果我们使用关系数据库来存储图，添加/删除关系可能涉及模式更改和数据移动，而使用图数据库则不需要。另一方面，当我们在关系数据库中为图创建表时，我们是基于我们想要的遍历进行建模；如果遍历发生变化，数据也必须随之变化。

现成的选择：Neo4J、Infinitegraph、OrientDB、FlockDB 等等。

布隆过滤器是一种数据结构，用于以时间和空间高效的方式检测一个元素是否在一个集合中。

可能会出现假阳性匹配，但不会出现假阴性——换句话说，查询返回“可能在集合中”或“绝对不在集合中”。元素可以添加到集合中，但不能移除（尽管可以通过“计数”布隆过滤器来解决这个问题）；添加到集合中的元素越多，假阳性的概率就越大。

使用案例

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