System design for instagram

Use cases and function:

  1. user can upload/download/view image and video.
  2. user can search image/video based on title.
  3. user can follow others.
  4. can generate new feeds for user with the users they follow(kinds of timeline).

Non-functional requirements

  1. Higher availability
  2. For new Feeds, system can tolerate 200ms latency.
  3. Lower requirement for consistency, user can not view new feeds for a moment which is a little bit acceptable.
  4. High reliability, which the new post can never be lost.

Top will not covered:

  1. tagging image.
  2. search image/video by tags.
  3. describe image/video.
  4. recommend followed users.
  5. feddback and advices.

3th consideration

  1. read-heavy system, so make sure the system can get the image or video quickly.
  2. high mount of image, so management the image/video storage efficiently can be really a reason for our focus.
  3. latency that users view image or video should meet the requirement for that.
  4. data should be highly 100% reliability, if user upload a image, it should never be lost if not deleted by creater.

4th

Storage estimation

  1. active users 1 million per day, totally 100 million users total.
  2. 2 million iamge/video per day uploaded.
  3. avg image 200 KB
  4. 2000000 * 200 KB = 400GB
  5. 400G * 365 ~= 142.5 TB

5th

So we have two senarios:

  1. upload iamge, 2. search image

    we need Object-storage Database (another topic about OSD we might need to cover)

    we might need some RDBS database to store metadata

    6th. data model

    user table: for info, upload iamge, follow users
    phone model: for save info for image/video, we need to index PhotoId and CreationDate, because we want to get the most recent image.

    1
    2
    3
    4
    5
    6
    7
    8
    9
     Photo  {
     	UserId int
     	PhonePath: varChar(256)
     	PhoneLatitude: int
     	PhoneLongitude: int
     	userLatitude: int
     	userLongitude: int
     	CreationDate: datatime
    }
{
1
2
3
4
5
6
		Name: varChar(20)
		Email: varChar(32)
		DateofBirth: datatime
		creationdate: datetime
		LastLogin: datetime
}
1
2
3
4
UserFollow {
	userId1: int
	useId2: int
}

  1. Obviously, database schema need join manipulation, so we need to use RDB, like MS SQL/PostgreSQL/MY SQL, but when scaling sysem, we might have trouble for that.
    So, we use noSQL database, and we might need to store image to HDFS or S3 kinds of distributed devices.

  2. we can use databases save in key-value distributed storage. and all the iamge info store in one table. the key could be photoID, value can be location, userLocation, creationtimeStamp and so on.

UserPhoto: user and image relation, key is userId, value: […list of phoneIds]
useFollowTable: same as userPhone, key: userId, value: […lists of userIds]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
```
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. Component Design ###

照片上传（写操作）可能比较慢，因为上传操作会写磁盘；而读操作会比较快，特别是在有缓存的情况下。

我们知道web服务器有连接数限制，所以我们设计系统的时候需要非常注意。因为上传操作速度比较慢，所以用户的上传操作可能会消耗掉所有可用的连接数。如果系统忙于应付写操作的话，那么“读”请求会无法得到处理。如果web服务器在任意时间点能处理最大500个连接的话，这就意味着它无法同时处理多于500个并发的“上传”或者“读”请求。为了处理这种极端情况，我们可以用把处理“读”和“写”请求的服务分开。我们可以用不同的服务器分别处理“读”和“写”请求，这样就不会阻塞住系统。

把“读”和“写”请求分开处理还可以让我们独立地扩展和优化这些服务。

### 9.可靠性和冗余(single point failure) ###

本系统的设计目标是不能丢失文件。所以，对于每个用户上传的文件我们需要保存多份拷贝；这样如果一个存储服务器失效了，那么我们仍然能从其他存储服务器上获取另一份拷贝。

这个原则也适用于系统的其他组件。如果系统要有高可用性，那么系统中运行的服务需要有多份拷贝。这样，如果一个服务死掉的话，系统依然是可用的并且仍然可以提供服务。所以，冗余可以消除系统的单点故障。

如果服务在任何时间点只需要运行一个实例的话，那么我们可以再运行该服务一个冗余的实例，但是该冗余实例不处理任何请求。一旦主服务出了问题，这个冗余的实例可以立刻通过“故障转移”（Failover）接管过来。

在系统中创建冗余可以移除系统的单点故障，并且提供功能的备份以防万一。假设在生产环境中有同一个服务的两个实例；如果其中一个失效或者降级了，那么系统可以通过“故障转移”（Failover）让另一个实例接管。“故障转移”（Failover）可以自动触发也可以手动触发。

10. Database Sharding

Below we will discuss metaData data sharding design methodology.

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表或者其他组件上。

如果将来数据大幅增长怎么办？我们可以在物理数据库服务器中创建多个逻辑分区来应对未来的数据增长。由于每个物理数据库服务器可以运行多个数据库实例，所以我们可以为各个逻辑分区运行各自独立的数据库实例。如果我们发现一个数据库服务器数据大量增长，就可以把该服务器的一些逻辑分区迁移到另一个服务器。我们可以维护一个配置文件（或者一个数据库）来把我们的逻辑分区映射到数据库服务器；这样我们就可以容易地移动分区。任何时候只要我们想移动一个分区，我们只需要升级这个配置文件以声明改动就行。

11.“推送新闻（News Feed）”

一个用户的“推送新闻（News Feed）”是由该用户关注的所有用户的最近的、最受欢迎的照片组成的。

生成“推送新闻（News Feed）”的基本流程如下。假设用户的“推送新闻（News Feed）”需要包含100张照片。那么我们的应用服务器首先要获取一张该用户关注的所有用户的列表，并且获取每个用户的最近的100张照片的元数据。然后，应用服务器会提交这些照片的元数据到我们的排名算法，该算法会基于照片的时间和用户的喜好来选择前100张照片并且返回给用户。这个流程的问题在于延时会比较高，因为我们需要查询多个表并基于查询结果做排序/合并/排名。为了提高效率，我们可以预先生成“推送新闻（News Feed）”并且将结果保存于另一个表。

预生成“推送新闻（News Feed）”：我们可以用一台专用服务器不断地生成用户的“推送新闻（News Feed）”，并且把结果保存于一个UserNewsFeed表中。这样，一旦需要返回“推送新闻（News Feed）”给用户的时候，我们只要查询一下这张表并返回结果就行了。

一旦这些服务器需要为一个用户生成“推送新闻（News Feed）”，它们可以查询UserNewsFeed表以找到该用户最新的“推送新闻（News Feed）”。然后，我们基于该时间点之后的数据按照以上步骤生成新的“推送新闻（News Feed）”。

有哪些不同的方法发送“推送新闻（News Feed）”给用户？

  1. Pull: 客户端可以一定频率或者手动方式直接向服务器请求“推送新闻（News Feed）”。这种方式的问题在于，a）只有客户端发送了请求，客户端的“推送新闻（News Feed）”才会更新；b）如果服务器端没有数据更新的话，那么大多数客户端请求只会得到空响应。

  2. Push: 一旦服务器端的数据更新了，服务器就会推送“推送新闻（News Feed）”到客户端。客户端需要维护一个Long Poll请求以接收数据更新。这种方式的问题在于，如果一个用户被大量的其他用户关注或者一个明星用户拥有数百万粉丝的话，服务器端的推送压力会很大。
    因为要把new feeds强行推送给所有的关注者，服务器会爆炸。

  3. 复合（Hybrid）: 复合（Hybrid）方式结合了Pull和Push的优点。对于有大量粉丝的用户，他们可以用Pull方式获取“推送新闻（News Feed）”；对于只有少量粉丝的用户，我们采用Push方式推送更新。另一种复合（Hybrid）方式是，服务器端以一定频率推送“推送新闻（News Feed）”给所有用户；对于有很多粉丝的用户，他们将采用一定频率的Pull模式获取更新。

12.如何基于分片数据生成”推送新闻（News Feed）”

为指定的用户生成“推送新闻（News Feed）”的最重要的要求之一是基于该用户关注的所有用户的列表获取最新的照片。为此我们需要一种有效的方法来按照照片的创建时间为照片排序。我们可以把照片的创建时间追加为PhotoID的一部分。因为我们对PhotoID创建了索引，所以我们能很快基于索引找到最新的PhotoID。
在此我们可以使用时间戳。假设我们的PhotoID由两部分构成：一是时间戳；二是auto-incrementing sequence。为创建PhotoID，我们可以使用当前时间戳并从我们在第10节中提到的键值生成数据库中获取一个auto-incrementing ID。然后，我们可以基于PhotoID算出ShardID，也就是PhotoID对10取余；我们可以把照片的元数据存放于该分片。

那么一个PhotoID需要多少存储字节？假设我们的时间戳从今天开始，那么我们需要多少字节来存储一个单位为秒的50年后的时间戳呢？
86400（秒） 365（天） 50（年） => 1，600，000，000
我们需要31个比特位来存储这个数字。平均而言，用户每秒会上传23张照片；我们可以分配9个比特位来存放auto incremented sequence。所以，每秒钟我们能存储至多512张照片，也是2的9次方。另外，我们每秒钟可以重置一次auto incremented sequence。
13.缓存与负载均衡

我们的服务需要一个海量照片发送系统以服务分布于全球的用户。我们的服务需要大量的分布于世界各地的照片缓存服务器和CDN，这样用户就可以从就近的服务器获取推送内容。

我们可以引入缓存来存放元数据库中的热点数据。在此我们可以使用Memcache，应用服务器在访问数据库之前可以先检查缓存中是否有需要的数据。LRU对我们的系统来说是一种可行的缓存策略。基于此策略，最旧的数据会被最先丢弃。

我们如何建立更有效的缓存机制呢？假设我们使用2-8原则，那么每天有20%的照片会产生80%的流量，这就意味着一部分照片是非常受欢迎的，大部分人都会访问这些照片。因此我们可以考虑缓存每天的20%的照片和其元数据。

译后记：

1）第10节写得不好，不知道作者到底希不希望所有数据在一个分片上
2）下面是我搜集的文中的一些概念的链接：
文件存储与对象存储的区别
https://www.zhihu.com/question/21536660
sql与nosql的区别
https://www.jianshu.com/p/b32fe4fe45a3
列式存储
https://blog.csdn.net/dc_726/article/details/41143175
数据分片
http://blog.zhaojie.me/2010/03/sharding-by-id-characteristic.html