系统设计：Instagram照片共享服务

需求

让我们设计一个像Instagram这样的照片共享服务，用户可以上传照片与其他用户共享。类似服务：Flickr、Picasa

难度等级：中等

1.什么是Instagram？

Instagram是一项社交网络服务，它允许用户上传照片和视频，并与其他用户共享。Instagram用户可以选择公开或私下共享信息。任何公开共享的内容都可以被任何其他用户看到，而私人共享的内容只能由指定的一组人访问。Instagram还允许其用户通过许多其他社交网络平台进行共享，如Facebook、Twitter、Flickr和Tumblr。

我们计划设计一个更简单的Instagram版本，用户可以共享照片，也可以关注其他用户。每个用户的“新闻提要”将包含用户关注的所有人的头像。

2.系统的要求和目标

在设计Instagram时，我们将重点关注以下一系列要求：

功能要求

• 1.用户应该能够上传/下载/查看照片。
• 2.用户可以根据照片/视频标题执行搜索。
• 3.用户可以关注其他用户。
• 4.该系统应该能够生成和显示用户的新闻饲料组成的顶级照片从用户跟踪的所有人中。

非功能性需求

• 1.我们的服务需要高可用。
• 2.系统可接受的新闻提要生成延迟为200ms，低延迟。
• 3.如果用户在一段时间内看不到照片，一致性可能会受到影响（为了可用性）
• 4.系统应高度可靠；任何上传的照片或视频都不应丢失，数据的可靠性。不在范围内：向照片添加标签、在标签上搜索照片、对照片进行评论、将用户标记到照片、跟踪谁等。

3.一些设计注意事项

该系统的阅读量会很大，因此我们将重点构建一个能够快速检索照片的系统。

1.实际上，用户可以上传任意数量的照片。在设计该系统时，有效的存储管理应该是一个关键因素。

2.查看照片时，预期延迟较低。

3.数据应100%可靠。如果用户上传照片，系统将保证它会永远不要丢失。

4.容量估计和限制

•假设我们有5亿总用户，每天有100万活跃用户。

•每天200万张新照片，每秒23张新照片。

•平均照片文件大小=>200KB

•1天照片所需的总空间 2M * 200KB => 400 GB

• 10年需要的总共空间为 400GB * 365 (days a year) * 10 (years) ~= 1425TB

5.高层系统设计

在高层，我们需要支持两种场景，一种是上传照片，另一种是查看/搜索照片。我们的服务需要一些对象存储服务器来存储照片，还需要一些数据库服务器来存储关于照片的元数据信息。

6.数据库语法

在访谈的早期阶段定义DB模式将有助于理解各个组件之间的数据流，并在以后指导数据分区。

我们需要存储有关用户、他们上传的照片以及他们关注的人的数据。照片表将存储与照片相关的所有数据；我们需要有一个索引（PhotoID，CreationDate），因为我们需要先获取最近的照片。

存储上述模式的简单方法是使用类似MySQL的RDBMS，因为我们需要连接。但关系数据库也面临着挑战，特别是当我们需要扩展它们时。有关详细信息，请查看SQL与NoSQL。

我们可以将照片存储在分布式文件存储器中，如HDFS或S3。

我们可以将上述模式存储在分布式键值存储中，以享受NoSQL提供的好处。所有与照片相关的元数据都可以放到一个表中，其中“key”是“PhotoID”，而“value”是一个包含PhotoLocation、UserLocation、CreationTimestamp等的对象。

我们需要存储用户和照片之间的关系，以了解谁拥有哪张照片。我们还需要存储用户跟踪的人员列表。对于这两个表，我们可以使用像Cassandra这样的宽列数据存储。对于“UserPhoto”表，“key”将是“UserID”，“value”将是用户拥有的“photoid”列表，存储在不同的列中。对于“UserFollow”表，我们将有一个类似的方案。

Cassandra或key value stores通常会维护一定数量的副本以提供可靠性。此外，在这样的数据存储中，删除不会立即应用，数据在从系统中永久删除之前会保留若干天（以支持取消删除）。

7.数据大小估计

让我们估计一下，每个表将需要多少数据，以及10年需要多少总存储空间。

用户：假设每个“int”和“dateTime”为四个字节，则用户表中的每一行将有68个字节：

UserID (4 bytes) + Name (20 bytes) + Email (32 bytes) + DateOfBirth (4 bytes) + CreationDate (4 bytes) + LastLogin (4 bytes) = 68 bytes

如果我们有5亿用户，我们将需要32GB的总存储空间。

500 million * 68 ~= 32GB

照片：照片表格中的每一行将有284字节：

PhotoID (4 bytes) + UserID (4 bytes) + PhotoPath (256 bytes) + PhotoLatitude (4 bytes) + PhotLongitude(4 bytes) + UserLatitude (4 bytes) + UserLongitude (4 bytes) + CreationDate (4 bytes) = 284 bytes

如果每天上传200万张新照片，我们一天需要0.5GB的存储空间：

2M * 284 bytes ~= 0.5GB per day

10年内，我们将需要1.88 TB的存储空间。

UserFollow：UserFollow表中的每一行将由8个字节组成。如果我们有5亿用户，平均每个用户跟踪500个用户。UserFollow表需要1.82TB的存储空间：

500 million users * 500 followers * 8 bytes ~= 1.82TB

所有表10年所需的总空间为3.7TB：

32GB + 1.88TB + 1.82TB ~= 3.7TB

8.组件设计

照片上传（或写入）可能会很慢，因为它们必须进入磁盘，而读取速度会更快，尤其是从缓存提供服务时。

上载用户可以使用所有可用的连接，因为上载是一个缓慢的过程。这意味着，如果系统忙于所有写入请求，则无法提供“读取”服务。在设计系统之前，我们应该记住web服务器有一个连接限制。如果我们假设一个web服务器在任何时候最多可以有500个连接，那么它的并发上载或读取不能超过500个。为了解决这个瓶颈，我们可以将读写分离到单独的服务中。我们将有专门的读取服务器和不同的写入服务器，以确保上传不会占用系统。

分离照片的读写请求也将允许我们独立地扩展和优化这些操作。

9可靠性和冗余

丢失文件不是我们服务的选项。因此，我们将存储每个文件的多个副本，这样，如果一个存储服务器死亡，我们就可以从另一个存储服务器上的另一个副本检索照片。

同样的原则也适用于系统的其他组件。如果我们希望系统具有高可用性，我们需要在系统中运行多个服务副本，这样，如果一些服务失效，系统仍然可用并运行。冗余消除了系统中的单点故障。

如果在任何时候只需要运行服务的一个实例，我们可以运行不服务于任何流量的服务的冗余辅助副本，但当主副本出现问题时，它可以在故障切换后进行控制。

在系统中创建冗余可以消除单点故障，并在危机中需要时提供备份或备用功能。例如，如果有两个相同服务的实例在生产环境中运行，而其中一个出现故障或降级，则系统可以故障切换到正常副本。故障切换可以自动进行，也可以需要手动干预。

10数据分片

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

A.基于UserID的分区

让我们假设我们基于“UserID”进行切分，这样我们就可以在同一个切分上保留用户的所有照片。如果一个DB分片为1TB，我们将需要四个分片来存储3.7TB的数据。让我们假设为了更好的性能和可伸缩性，我们保留了10个碎片。

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

我们如何生成类照片？每个DB碎片都可以有自己的PhotoID自动递增序列，因为我们将用每个PhotoID附加ShardID，这将使它在整个系统中唯一。

这个分区方案有哪些不同的问题？

• 1.我们将如何处理热门用户？有几个人关注这样的热门用户，还有很多人看到他们上传的任何照片。
• 2.与其他用户相比，一些用户将拥有大量照片，从而使存储分布不均匀。
• 3.如果我们不能将一个用户的所有图片存储在一个碎片上怎么办？如果我们将用户的照片分发到多个碎片上，会导致更高的延迟吗？
• 4.将用户的所有照片存储在一个分片上可能会导致一些问题，例如，如果该分片关闭，则用户的所有数据都不可用；如果该分片服务于高负载，则延迟更高等等。

B基于PhotoID的分区

如果我们能先生成唯一的PhotoID，然后通过“PhotoID%10”找到一个碎片号，上述问题就可以解决了。在这种情况下，我们不需要将ShardID附加到PhotoID中，因为PhotoID本身在整个系统中是唯一的。

我们如何生成类照片？

在这里，我们不能在每个分片中都有一个自动递增序列来定义PhotoID，因为我们需要先知道PhotoID才能找到存储它的分片。一种解决方案是，我们专门使用一个单独的数据库实例来生成自动递增的ID。如果我们的PhotoID可以容纳64位，那么我们可以定义一个只包含64位ID字段的表。因此，每当我们想在系统中添加一张照片时，我们都可以在这个表中插入一个新行，并将该ID作为新照片的PhotoID。

这个生成DB的密钥不是单点故障吗？

是的。解决方法是定义两个这样的数据库，其中一个生成偶数编号的ID，另一个生成奇数编号的ID。对于MySQL，以下脚本可以定义这样的序列：

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

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

或者，我们可以实现一个类似于我们在中讨论的“密钥”生成方案,可以参考之前的短链服务设计。

我们如何规划系统的未来增长？

我们可以有大量的逻辑分区来适应未来的数据增长，例如，在一开始，多个逻辑分区驻留在一个物理数据库服务器上。因为每个数据库服务器上都可以有多个数据库实例，所以我们可以为任何服务器上的每个逻辑分区都有单独的数据库。因此，每当我们觉得某个数据库服务器有大量数据时，我们就可以将一些逻辑分区从它迁移到另一个服务器。我们可以维护一个配置文件（或一个单独的数据库），它可以将我们的逻辑分区映射到数据库服务器；这将使我们能够轻松地移动分区。每当我们想要移动分区时，我们只需要更新配置文件来宣布更改。

11排名和新闻提要生成

要为任何给定用户创建新闻提要，我们需要获取用户关注的人的最新、最流行和相关的照片。

为了简单起见，假设我们需要为用户的新闻提要获取前100张照片。我们的应用服务器将首先获取用户关注的人的列表，然后从每个用户获取最新100张照片的元数据信息。在最后一步中，服务器将把所有这些照片提交给我们的排名算法，该算法将确定前100张照片（基于近况、相似性等），并将它们返回给用户。这种方法的一个可能问题是延迟更高，因为我们必须查询多个表并对结果执行排序/合并/排序。为了提高效率，我们可以预生成新闻提要并将其存储在单独的表中。

预生成新闻提要：

我们可以有专门的服务器不断生成用户的新闻提要，并将其存储在“UserNewsFeed”表中。因此，每当任何用户需要最新的照片作为他们的新闻提要时，我们只需查询此表并将结果返回给用户。

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

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

1.Pull：客户机可以定期或在需要时手动从服务器中提取新闻提要内容。这种方法可能存在的问题是a）在客户端发出拉取请求之前，新数据可能不会显示给用户b）如果没有新数据，大部分时间拉取请求将导致空响应。

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

3.混合：我们可以采用混合方法。我们可以将拥有大量追随者的所有用户移动到基于拉式模型，并且只将数据推送到拥有数百（或数千）追随者的用户。另一种方法是，服务器向所有用户推送更新，推送频率不超过某个频率，让拥有大量关注/更新的用户定期拉取数据

具体方案设计可以参考Facebook的新闻提要设计

12使用分片数据创建新闻提要

为任何给定用户创建新闻提要的最重要要求之一是从用户跟踪的所有人那里获取最新照片。为此，我们需要有一种机制来根据照片的创建时间对其进行排序。为了有效地做到这一点，我们可以使照片创建时间成为PhotoID的一部分。因为我们将有一个关于PhotoID的主要索引，它将很快找到最新的PhotoID。

我们可以用大纪元来做这个。假设我们的照片有两部分；第一部分表示历元时间，第二部分表示自动递增序列。因此，为了创建一个新的PhotoID，我们可以使用当前的历元时间，从生成密钥的数据库中附加一个自动递增的ID。我们可以从这个照片ID（照片ID%10）中找出碎片号，并将照片存储在那里。

我们的照片有多大？

假设我们的大纪元时间从今天开始，我们需要多少位来存储下一个50年的秒数？

86400 sec/day * 365 (days a year) * 50 (years) => 1.6 billion seconds

我们需要31位来存储这个数字。因为平均来说，我们期望每秒有23张新照片；我们可以分配9位来存储自动递增序列。因此，我们每秒钟都可以存储（2^9=>512）张新照片。我们可以每秒重置自动递增序列。

在设计Twitter时，我们将在“数据切分”一节中详细讨论这项技术。

13缓存和负载平衡

我们的服务将需要一个大规模的照片交付系统来服务全球分布的用户。我们的服务应该使用大量地理分布的照片缓存服务器和CDN（有关详细信息，请参阅缓存设计）将其内容推近用户。

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

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

参考资料

grok_system_design_interview.pdf