设计 Instagram

让我们设计一个类似Instagram的照片分享服务，用户可以上传照片与其他用户分享。

类似服务：Flickr, Picasa
难度等级：中等

1. 什么是Instagram？

Instagram是一种社交网络服务，用户可以上传并与他人分享自己的照片和视频。Instagram用户可以选择公开或私密地分享信息。公开分享的内容可以被任何其他用户查看，而私密内容只能由指定的人访问。Instagram还支持通过多个社交网络平台分享内容，如Facebook、Twitter、Flickr和Tumblr。

在本练习中，我们计划设计一个简化版的Instagram，用户可以分享照片并关注其他用户。每个用户的“动态”将展示他们所关注用户的精选照片。

2. 系统的需求与目标

在设计Instagram时，我们将关注以下需求：

功能性需求

1. 用户可以上传、下载和查看照片。
2. 用户可以基于照片或视频标题进行搜索。
3. 用户可以关注其他用户。
4. 系统应生成并显示用户的“动态”，包括用户所关注的所有人的精选照片。

非功能性需求

1. 服务需具备高可用性。
2. 动态生成的系统延迟应在200毫秒内。
3. 为了提高可用性，一定程度的实时性一致性可以妥协，若用户在短时间内未看到照片，可接受。
4. 系统应高度可靠，任何上传的照片或视频不应丢失。

不在范围内：照片的标签添加、基于标签的照片搜索、照片评论、用户在照片上的标记、推荐关注等。

3. 设计考虑因素

系统的读取频率将会很高，因此我们将重点构建一个能快速检索照片的系统。

1. 用户可以实际上传任意数量的照片，因此在设计系统时，存储管理的高效性应是关键因素。
2. 用户在查看照片时对低延迟有较高期望。
3. 数据需具有100%的可靠性。系统应确保用户上传的任何照片都不会丢失。

4. 容量估算和约束

• 假设总用户数为5亿，每日活跃用户100万。
• 每天上传新照片200万张，即每秒新增23张照片。
• 照片的平均文件大小为200KB。
• 1天照片所需的存储空间：
  2M * 200KB = 400GB
• 10年所需的总存储空间：
  400GB * 365（天/年）* 10（年）≈ 1425TB

5. 高层系统设计

从高层次来看，我们需要支持两个场景：一个用于照片上传，另一个用于照片查看和搜索。服务需要一些 对象存储服务器 来存储照片，还需要一些数据库服务器来存储照片的元数据信息。

6. 数据库模式

💡 在面试初期定义数据库模式有助于理解各组件间的数据流动，后续也能指导数据分区。

我们需要存储关于用户、用户上传的照片以及用户关注关系的数据。照片表将存储与照片相关的所有数据；我们需要在PhotoID和CreationDate上创建索引，以便优先获取最新照片。

一种简单的存储方案是使用支持联接操作的关系型数据库（如MySQL），但关系型数据库在扩展时面临诸多挑战。关于详细对比，请参见SQL与NoSQL的区别。

• 照片存储：可以使用分布式文件存储系统，如 HDFS 或 S3。
• 元数据存储：可以使用分布式键值存储系统来实现NoSQL的优势。与照片相关的所有元数据可以存放在一个表中，其中“键”为PhotoID，“值”为包含PhotoLocation、UserLocation、CreationTimestamp等信息的对象。

我们还需要存储用户与照片的关系，以便知道谁拥有哪些照片；此外，还需存储用户的关注列表。对于这两个表，可以使用宽列数据存储，如 Cassandra。

• UserPhoto表：键为UserID，值为该用户拥有的PhotoID列表，分别存储在不同列中。
• UserFollow表：采用类似的模式存储用户关注的列表。

Cassandra或一般的键值存储通常会维持一定数量的副本以确保数据可靠性。此外，这类数据存储不会立即执行删除操作，数据会保留几天（以支持恢复）后再永久删除。

7. 数据量估算

我们来估算每张表所需的数据量以及10年所需的总存储空间。

• 用户表：假设每个“int”和“dateTime”字段占用4字节，每行数据68字节：

  • UserID（4字节）+ Name（20字节）+ Email（32字节）+ DateOfBirth（4字节）+ CreationDate（4字节）+ LastLogin（4字节）= 68字节
  • 如果有5亿用户，总存储需求为32GB：
    500M * 68 ~= 32GB

• 照片表：每行数据大小为284字节：

  • PhotoID（4字节）+ UserID（4字节）+ PhotoPath（256字节）+ PhotoLatitude（4字节）+ PhotoLongitude（4字节）+ UserLatitude（4字节）+ UserLongitude（4字节）+ CreationDate（4字节）= 284字节
  • 如果每天上传200万张新照片，1天需要0.5GB存储空间：
    2M * 284字节 ≈ 0.5GB每天
  • 10年所需存储空间为1.88TB。

• 用户关注表：每行数据大小为8字节。如果有5亿用户，每个用户平均关注500人，用户关注表所需存储空间为1.82TB：
  500M用户 * 500关注者 * 8字节 ≈ 1.82TB

10年内所有表的总存储需求约为3.7TB：
32GB + 1.88TB + 1.82TB ≈ 3.7TB

8. 组件设计

照片上传（或写操作）较慢，因为需要写入磁盘，而读取速度更快，尤其是从缓存中读取时。

• 上传并发问题：上传过程较慢，可能占用所有可用连接，导致系统忙于处理写请求而无法提供读服务。考虑到Web服务器的连接限制（假设每台服务器最多支持500个连接），并发上传或读取的数量不能超过500。
• 分离读写服务：为应对此瓶颈，可以将读写操作拆分为独立的服务。使用专用的服务器处理读取请求，另设服务器处理写入请求，确保上传不会阻塞系统。

通过将照片的读写请求分离，我们可以分别扩展和优化每种操作。

9. 可靠性与冗余

对于该服务而言，丢失文件不可接受。因此，我们会为每个文件存储多份副本，以确保某个存储服务器故障时，照片可从另一台存储服务器上的副本中恢复。

此原则同样适用于系统的其他组件。若要确保系统的高可用性，需要让服务在系统中以多副本方式运行，这样即使部分服务出现故障，系统仍能正常运行。冗余设计能够消除系统中的单点故障。

• 冗余副本：当只需要运行一个服务实例时，可以运行一个不处理流量的备用副本。当主副本出现问题时，该备用副本可接管。
• 冗余作用：在系统中创建冗余设计能消除单点故障，并在紧急情况下提供备用功能。例如，在生产环境中同时运行两个相同服务实例时，如果其中一个实例出现故障或性能下降，系统可以切换到健康的副本。此故障转移可以是自动完成的，也可以需要人工干预。

10. 数据分片

让我们讨论不同的元数据分片方案：

a. 基于UserID的分区

假设我们按“UserID”进行分片，以便将用户的所有照片保存在同一分片中。如果一个数据库分片为1TB，我们需要四个分片来存储3.7TB的数据。假设为了更好的性能和可扩展性，我们保留10个分片。

因此，我们将通过UserID % 10找到分片编号，然后将数据存储在这里。为了在我们的系统中唯一标识任何照片，我们可以将分片编号附加到每个PhotoID上。

如何生成PhotoID？每个数据库分片可以有自己的自增序列用于PhotoID，由于我们会将分片ID附加到每个PhotoID上，它将使其在整个系统中唯一。

此分区方案的不同问题是什么？

1. 我们如何处理热点用户？几个用户关注这些热点用户，许多其他人会查看他们上传的任何照片。
2. 有些用户的照片比其他用户多，从而导致存储分布不均。
3. 如果我们无法将用户的所有照片存储在一个分片中怎么办？如果我们将用户的照片分布到多个分片上，会导致更高的延迟吗？
4. 将用户的所有照片存储在一个分片中可能会导致问题，例如，如果该分片宕机，用户的所有数据都不可用，或者如果它正在处理高负载则延迟更高等。

b. 基于PhotoID的分区

如果我们可以先生成唯一的PhotoID，然后通过PhotoID % 10找到分片编号，上述问题将得到解决。在这种情况下，我们无需在PhotoID中附加分片ID，因为PhotoID本身将在整个系统中唯一。

我们如何生成PhotoID？在这里，我们无法在每个分片中有自增序列来定义PhotoID，因为我们需要先知道PhotoID，才能找到将要存储的分片。一个解决方案是我们专门设置一个数据库实例来生成自增ID。如果我们的PhotoID可以适应64位，我们可以定义一个只包含64位ID字段的表。因此，每当我们想在系统中添加照片时，我们可以在此表中插入新行，并将该ID作为新照片的PhotoID。

**这个ID生成数据库不会成为单点故障吗？**是的，它会。一个解决方法是定义两个这样的数据库，一个生成偶数ID，另一个生成奇数ID。对于MySQL，以下脚本可以定义这样的序列：

KeyGeneratingServer1:
auto-increment-increment = 2
auto-increment-offset = 1

KeyGeneratingServer2:
auto-increment-increment = 2
auto-increment-offset = 2

我们可以在这两个数据库前面放置一个负载均衡器，以便在它们之间进行轮询并处理停机。这两个服务器可能不同步，其中一个生成的密钥比另一个多，但这不会对我们的系统造成任何问题。我们可以通过为用户、照片评论或系统中其他对象定义单独的ID表来扩展此设计。

另外，我们可以实现类似于我们在设计类似TinyURL的URL缩短服务时讨论的“密钥”生成方案。

**我们如何为系统的未来增长做好规划？**我们可以有大量逻辑分区，以适应未来数据的增长，最开始时，多个逻辑分区可以驻留在单个物理数据库服务器上。由于每个数据库服务器可以有多个数据库实例，我们可以在任何服务器上为每个逻辑分区设置单独的数据库。因此，每当我们觉得某个数据库服务器的数据量很大时，我们可以将其中一些逻辑分区迁移到另一个服务器。我们可以维护一个配置文件（或一个单独的数据库），可以将我们的逻辑分区映射到数据库服务器；这将使我们能够轻松移动分区。每当我们想要移动一个分区时，只需更新配置文件以宣布更改即可。

11. 排名和新闻源生成

为了为任何给定用户创建新闻源，我们需要获取该用户所关注的人的最新、最受欢迎和相关的照片。为简化起见，假设我们需要获取用户新闻源中的前100张照片。我们的应用服务器将首先获取用户关注的人的列表，然后从每个用户那里获取最新100张照片的元数据信息。在最后一步，服务器将提交所有这些照片给我们的排名算法，该算法将根据最近性、喜好等因素确定前100张照片，并将其返回给用户。

这种方法可能存在一个问题，那就是由于我们必须查询多个表并对结果进行排序/合并/排名，因此延迟较高。为了提高效率，我们可以预生成新闻源并将其存储在一个单独的表中。

预生成新闻源：我们可以有专门的服务器，持续生成用户的新闻源并将其存储在“UserNewsFeed”表中。因此，每当用户需要最新照片以更新其新闻源时，我们只需查询该表并将结果返回给用户。

每当这些服务器需要为某个用户生成新闻源时，它们将首先查询UserNewsFeed表，以找出该用户上次生成新闻源的时间。然后，从该时间起生成新的新闻源数据（遵循上述步骤）。

向用户发送新闻源内容的不同方法有哪些？

1. 拉取（Pull）：客户端可以定期从服务器拉取新闻源内容，或者在需要时手动拉取。该方法可能存在的问题是：

• a. 新数据可能在客户端发出拉取请求之前不会显示给用户
• b. 大多数情况下，如果没有新数据，拉取请求将导致空响应。

2. 推送（Push）：服务器可以在新数据可用时立即将其推送给用户。为了有效管理这一点，用户必须与服务器保持 长轮询 请求以接收更新。该方法可能存在的问题是，对于关注了很多人或有数百万粉丝的名人用户，服务器必须非常频繁地推送更新。

3. 混合（Hybrid）：我们可以采取混合方法。我们可以将关注人数较多的用户转移到基于拉取的模型，仅向那些只有几百（或几千）关注者的用户推送数据。另一种方法是，服务器以不超过某一频率向所有用户推送更新，让有很多关注者/更新的用户定期拉取数据。

有关新闻源生成的详细讨论，请参见设计Facebook的新闻源。

12. 使用分片数据创建新闻源

为任何给定用户创建新闻源的最重要要求之一是从所有用户关注的人那里获取最新照片。为此，我们需要一种机制来按创建时间对照片进行排序。为了高效地完成这一点，我们可以将照片的创建时间作为PhotoID的一部分。由于我们将以PhotoID为主索引，因此查找最新的PhotoID将非常快速。

我们可以使用纪元时间。假设我们的PhotoID将由两部分组成；第一部分表示纪元时间，第二部分是自增序列。因此，为了生成新的PhotoID，我们可以获取当前的纪元时间，并附加来自我们的密钥生成数据库的自增ID。我们可以通过这个PhotoID（PhotoID % 10）计算出分片号，并将照片存储在该分片中。

我们的PhotoID的大小可能是多少？假设我们的纪元时间从今天开始，我们需要多少位来存储接下来50年的秒数？
86400秒/天 * 365（每年天数） * 50（年数） => 16亿秒

我们需要31位来存储这个数字。由于我们预计平均每秒会有23张新照片，因此可以分配9位来存储自增序列。因此，每秒我们可以存储（2^9 => 512）张新照片。我们可以每秒重置自增序列。

我们将在设计Twitter的“数据分片”部分讨论更多关于此技术的细节。

13. 缓存和负载均衡

我们的服务需要一个大规模的照片交付系统，以服务全球分布的用户。我们的服务应通过大量地理分布的照片缓存服务器，将内容推送更靠近用户，并使用内容分发网络（CDN）（有关详细信息，请参见缓存）。

我们可以为元数据服务器引入缓存，以缓存热数据库行。我们可以使用Memcache来缓存数据，应用服务器在访问数据库之前可以快速检查缓存是否有所需的行。最近最少使用（LRU）可以成为我们系统的合理缓存驱逐策略。在这种策略下，我们首先丢弃最近查看次数最少的行。

我们如何构建更智能的缓存？如果我们遵循80-20法则，即每日照片的20%读取量产生80%的流量，这意味着某些照片非常受欢迎，绝大多数人都会阅读它们。这表明我们可以尝试缓存每日读取量20%的照片和元数据。