本文翻译自https://www.educative.io/collection/page/5668639101419520/5649050225344512/5673385510043648
1.什么是Instagram
Instagram是一个社交网络服务，用户可以在这个网站上上传和分享他们的照片和视频。Instagram的用户能设置他们的分享内容为所有人可见或者部分人可见。向所有人分享的照片或视频可以被任何用户查看，但是向部分人分享的内容仅仅能被部分人查看。Instagram也能够让它的用户们通过其他社交媒体比如Facebook，Twitter，Flickr和Tumblr分享内容。
2.系统的需求和设计目标
在本题中，我们将主要解决以下问题：
功能性需求：
1.用户能够上传/下载/查看照片；
2.用户能够基于标题搜索照片/视频；
3.用户能够关注其他用户；
4.这个系统能够为用户生成和显示“推送新闻（News Feed）”，“推送新闻（News Feed）”由该用户关注的所有用户的最新照片/视频组成。
非功能性需求：
1.该系统的服务应该是高可用的；
2.对于“推送新闻（News Feed）”，系统可接受的延迟是200毫秒；
3.本系统对一致性的要求略低；如果用户暂时没看到其他用户更新的内容，也是可以接受的；
4.本系统应该高度可靠，并且任何上传的照片/视频永远不能丢失。
本文不讨论的问题：为图片添加标签，根据标签搜索照片，注释照片，推荐关注的用户，建议反馈，等等。
3.一些设计考虑
本系统是一个read-heavy的系统，所以我们的设计重点是确保该系统能够快速的获取照片。
1.因为用户能上传大量的照片，所以对存储的有效管理是设计该系统的关键点；
2.用户查看照片的延时应该满足设计要求；
3.数据应该100%可靠。如果用户上传了一张照片，那么系统应该保证该照片永远不丢失。
4.存储容量预估
假设我们有5亿用户，每天有1百万活跃用户；
每天都会有2百万新照片上传，也就是每秒有23张新照片上传；
假设平均的照片文件大小为200KB；
每天上传的照片占用的空间为 2000000 * 200KB = 400 GB
10年需要的空间为：400GB * 365 (days a year) * 10 (years) ~= 1425TB
5.系统整体设计
我们需要考虑两个使用场景，一是上传照片；二是查看/搜索照片。我们的服务需要使用面向对象存储服务器来保存照片，还需要一些数据库服务器存储照片的元数据。
6.数据库schema
在面试中尽早定义数据库schema能帮助你更好的理解不同组件间的数据流，并且能为后面的数据分区提供指导。
“User”表用来保存用户相关的数据、用户上传的照片和用户关注的其他用户。“Photo”表用来保存与照片相关的所有数据；我们要为PhotoID和 CreationDate创建索引，因为我们要获取最近的照片。
很明显，以上的数据库schema需要做join操作，所以我们可以用关系型数据库存储以上的数据库schema，比如MySql。但是如果我们选用关系型数据库的话，日后我们扩展系统的时候，会遇到很多问题。所以，在此我们选择NoSql数据库。具体原因请google（SQL vs. NoSQL）。
我们可以把照片存储在类似HDFS或者S3的分布式存储设备上。
我们可以把该数据库schema保存于基于key-value的分布式存储设备上，这样可以尽显NoSql的优势。所有和照片有关的元数据都会被存于一张表中，这张表的key可以是PhotoID，value可以是一个包含了PhotoLocation、UserLocation和CreationTimestamp的对象。
我们需要一个表UserPhoto保存用户和照片之间的关系，这样就可以知道谁拥有这些照片。我们还需要一个表UserFollow保存用户关注的人的列表。对于这两张表，我们可使用宽列数据存储（wide-column-store）如Cassandra。对于UserPhoto表，key是UserID，value是用户拥有的PhotoIDs的列表，这个列表被保存在不同的列族中。对于UserFollow表，我们也采用类似的schema。
一般来说，Cassandra或者key-value存储会提供一定数量的冗余存储以提供可靠性。另外，数据删除操作不会立即生效，因为数据在被永久删除前会保留几天以支持数据恢复。
7.数据大小预估
我们来估计一下10年后每张表的数据容量以及我们需要占用多少存储空间。
User: 假设每个“int”和“dateTime”是4 Bytes，那么User表中的每行是68 Bytes:
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
Photo: Photo表的每行是284 Bytes:
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
如果用户每天上传2百万新照片的话，那么Photo表每天增加0.5GB：
2M * 284 bytes ~= 0.5GB per day
所以，Photo表10年共需要1.88 TB存储空间。
UserFollow: UserFollow表中的每一行是8 Bytes。如果我们有5亿用户并且平均每个用户关注500个其他用户的话，UserFollow表将需要895 GB的空间。
500 million users * 500 followers * 8 bytes ~= 1.82TB
10年内这些表需要的全部存储空间大概是3.7 TB：
32GB + 1.88TB + 1.82TB ~= 3.7TB
8.组件设计
照片上传（写操作）可能比较慢，因为上传操作会写磁盘；而读操作会比较快，特别是在有缓存的情况下。
我们知道web服务器有连接数限制，所以我们设计系统的时候需要非常注意。因为上传操作速度比较慢，所以用户的上传操作可能会消耗掉所有可用的连接数。如果系统忙于应付写操作的话，那么“读”请求会无法得到处理。如果web服务器在任意时间点能处理最大500个连接的话，这就意味着它无法同时处理多于500个并发的“上传”或者“读”请求。为了处理这种极端情况，我们可以用把处理“读”和“写”请求的服务分开。我们可以用不同的服务器分别处理“读”和“写”请求，这样就不会阻塞住系统。
把“读”和“写”请求分开处理还可以让我们独立地扩展和优化这些服务。
9.可靠性和冗余
本系统的设计目标是不能丢失文件。所以，对于每个用户上传的文件我们需要保存多份拷贝；这样如果一个存储服务器失效了，那么我们仍然能从其他存储服务器上获取另一份拷贝。
这个原则也适用于系统的其他组件。如果系统要有高可用性，那么系统中运行的服务需要有多份拷贝。这样，如果一个服务死掉的话，系统依然是可用的并且仍然可以提供服务。所以，冗余可以消除系统的单点故障。
如果服务在任何时间点只需要运行一个实例的话，那么我们可以再运行该服务一个冗余的实例，但是该冗余实例不处理任何请求。一旦主服务出了问题，这个冗余的实例可以立刻通过“故障转移”（Failover）接管过来。
在系统中创建冗余可以移除系统的单点故障，并且提供功能的备份以防万一。假设在生产环境中有同一个服务的两个实例；如果其中一个失效或者降级了，那么系统可以通过“故障转移”（Failover）让另一个实例接管。“故障转移”（Failover）可以自动触发也可以手动触发。
10.数据分片
下文将讨论元数据分片的不同设计方法。
a. 基于UserID分区 如果我们基于UserID分片，那么我们可以将同一个用户的全部照片元数据保存于同一个分片上。如果一个数据库分片是1 TB，那么我们需要4个分片来保存3.7 TB的数据。另外，为了更好的性能和扩展性，假设我们保留10个分片。
所以我们可以通过UserID对10取余来找到对应的ShardID，从而保存数据。为了唯一的识别系统中的任意照片，我们可以在PhotoID后面追加ShardID。
那么我们如何生成PhotoID？每个数据库分片都有各自的auto-increment sequence用以生成PhotoID，并且由于我们会追加ShardID到每个PhotoID，因此我们能保证每个PhotoID在系统中都是唯一的。
这种数据库分片设计会有什么问题？
我们如何处理热点用户？有的人会关注热点用户，并且人们往往会查看热点用户上传的每一张照片。
有些用户相对于其他用户会上传大量照片，这会导致存储的不均匀分布。
如果我们无法将一个用户的全部照片的元数据保存于一个分片的话，那我们就只得把用户照片的元数据存放于不同的分片上，这会不会导致更高的延迟？
另外，把一个用户的全部照片的元数据存储于同一个分片上可能会导致一个问题是，如果保存元数据的分片失效了或者该分片的负载很高导致延时很大的话，那么该用户的全部数据就都不可用了。
b. 基于PhotoID分区 我们先生成唯一的PhotoID，然后再通过PhotoID对10取余找到ShardID，这就能解决以上问题。我们不必追加ShardID到PhotoID，因为PhotoID本身在系统中就是唯一的。
那么我们如何生成PhotoID呢？在每个分片中设置auto-incrementing sequence毫无意义，因为我们是先生成PhotoID，再通过PhotoID找到分片。解决方法是，我们可以运行一个独立的数据库实例以生成自动增长的PhotoID。假设我们的PhotoID是64位，那么我们可以定义一个只有64位ID列的表。如果一张新的照片被上传到系统，我们可以插入一行到这个表中并且取这个ID为新的照片的PhotoID。
那么这个生成PhotoID的数据库实例会不会有单点失败？是的，有可能。解决方法是，我们可以定义两个数据库实例，一个生成偶数ID，另一个生成奇数ID。
我们可以添加一个负载均衡器用来轮流调度这两个数据库实例。这两个数据库实例可能生成的ID数目不一样，但是这对系统不会造成任何问题。我们可以把这个设计思想用于系统的其他表比如Users表、Photo-Comments表或者其他组件上。
如果将来数据大幅增长怎么办？我们可以在物理数据库服务器中创建多个逻辑分区来应对未来的数据增长。由于每个物理数据库服务器可以运行多个数据库实例，所以我们可以为各个逻辑分区运行各自独立的数据库实例。如果我们发现一个数据库服务器数据大量增长，就可以把该服务器的一些逻辑分区迁移到另一个服务器。我们可以维护一个配置文件（或者一个数据库）来把我们的逻辑分区映射到数据库服务器；这样我们就可以容易地移动分区。任何时候只要我们想移动一个分区，我们只需要升级这个配置文件以声明改动就行。