Facebook 的系统设计面试，一般必考自家的技术实践难题。比如facebook news feed 如何设计，Instagram 的分片和 ID设计。今天我们来读一读 FB 官方技术博客的这篇 《Instagram 分片与ID设计》。
Instagram上有大量的数据，每分钟就有超过25张的图片和90个点赞。为了确保所有重要的数据都能被合理存储并且及时得被提取应用，我们对数据进行了分片（sharding）——也就是说，我们把数据放到多个桶（bucket）中，每个桶里都有一部分数据。
我们的应用服务器上运行的是Django， 后端数据库是PostgreSQL。 对数据分片首先要决定是否要保留PostgreSQL作为主要的数据存储库，是否要采用其他的数据库。经过评估一些不同的数据库解决方案，我们最终确定最适合的方案是在PostgreSQL数据库集群上实现数据分片。
然而在把数据写到数据库之前，我们还要解决如何给数据（例如Instagram上发布的没一张图片）加上唯一标识符的问题。在单一数据库上的典型解法——使用数据库自带的自增主键功能——在当数据需要被同时插入到多个数据库时就不适用了。文章的下面就来讲讲我们是如何解决这个问题的。
开始前，我们先列出系统所需要的所有重要的功能。
- 产生的数据ID需是可以按时间排序的。（比如对一列图片数据的ID进行排序，可以不需要提取太多图片本身的信息）
- 理想的ID是64位的。（这样索引更小，存储也更优，像Redis）
- 系统要尽量少的引用“可变动因素”——在很少工程师的情况下还可以扩张Instagram的很大一部分原因就是，我们相信简单易懂的方案。
现有的解决方案
现有很多产生ID的解决方案，我们考虑的有以下这些：
Part
1
由Web应用层生成ID
这种方案将ID的生成完全交到应用层，而不是数据库。例如，MongoDB的ObjectId，就是12字节长并且在最前面加上时间戳进行编码。另一个流行的方案是使用UUIDs。
优点：
- 每个应用线程独立生成ID，最小的降低ID生成的失败和竞争。
- 如果用时间戳作为ID的起始部分，那么ID可以按时间排序。
缺点：
- 通常需要更多的存储空间（96位或者更多）来确保ID的合理唯一性。
- 一些UUID类型完全是随机的，无法排序。
Part
2
通过单独的服务产生ID
例如： Twitter的Snowflake，是一个Thrift服务，使用了Apache Zookeeper来协调各个结点并且产生64为的唯一ID。
优点：
- Snowflake的ID只有64位，是UUID的一半。
- 可以放时间戳到ID头，从而可以按时间排序。
- 分布式系统保证了系统结点不会挂掉。
缺点：
增加了复杂性，而且引入了更多的“可变动因素”（如ZooKeeper, Snowflake服务器）到系统构架中。
Part
3
数据库票据（DB Ticket）服务器
利用数据库自带的自增特性来确保唯一性。Flicker采用这一方法，不过还用了两台ticket数据库（一个生成偶数，一个生成奇数）来避免单点失败。
优点：
数据库好理解，带有易预测的可扩张功能。
缺点：
- 最终会出现数据写入的瓶颈（尽管Flicker称在高扩展下没有问题）。
- 需要管理多的两台服务器（或者EC2实例）。
- 如果单独使用数据库，会出现单点失效。如果使用多个数据库，则不能保证ID可以按时间排序。
在所有这些方案中，Twitter的snowflake是最接近的，但是生成ID所需的添加复杂性又和我们的目标冲突。我们的替换方案是采用概念上相近的方法，但是带到PostgreSQL内部实现。
Instagram 的方案
我们的分片系统是由上千个“逻辑”分片组成的，由代码映射到少量的物理分片。
通过这个方法，我们一开始用少数数据库实现，慢慢扩展到更多个数据库，只需要把部分逻辑分片从一台数据库转移到另一台数据库里，不需要重新把数据重新聚合。我们用到的PostgreSQL的schema的特性可以轻松的实现计划和管理。
Schema（不要和SQL单个表的schema搞混了）是PostgreSQL里的一个逻辑分组功能。每一个PostgreSQL数据库都有好几个schema，每一个schema都有一到多个表。表名在没个schema中都是唯一的，而不是每个数据库，默认情况下，PostgreSQL会把所有数据都放在一个叫“public”的schema中。
在我们的系统中每个“逻辑”分片都是一个PostgreSQL schema， 每个分片的表（比如照片的“点赞”功能）都存在每个schema中。
我们通过使用PL/PGSQL, PostgreSQL内部的编程语言，和PostgreSQL现有的自增功能来生成ID。
每个ID都由下面几个部分组成：
41位的毫秒级时间（用于产生41年的ID）
13位用来表示逻辑分片的ID
10位的自增序列，模上1024， 意味着每个分片每毫秒可以产生1024个ID
下面通过一个例子说明：比如说现在是2011年的九月九日，我们的纪元是从2011年的一月一号开始。从新纪元开始到此有1387263000毫秒，那么我们把这个数字左移41位来填满ID的头。
id = 1387263000 <<(64 – 41)
接下来， 我们拿来我们准备把这个数据插入的分片ID；如果我们用户ID是31341， 这个分片的ID是 31341%2000 → 1341。 我们接下来把下面13为填满：
id |= 1341 << (64-41-13)
最后， 我们用所剩的自增序列（每个schema中每个表中这个序列都是唯一的）来填满的后面的位数。 假设这张表中已经有了5000个ID； 我们下一个数据就是5001，我们把它模上1024得到：
id |= （5001%1024）
我们就得到了我们的ID， 我们把这个id作为insert中的RETURNING返回给应用层。
下面是是实现以上过程的PL/PGSQL代码（这里用的schema是insta5）
要生成表示执行下面的部分：
成了！我们得到了应用中唯一的主键（还有一个好处是，ID中包含了分片ID可以用来轻松映射）。我们已经把这个方法用在产品中，并且对结果感到非常满意。