Instagram 的 ID 生成策略是经过精心设计过的。1 每一秒 Instagram 都会收到无数用户上传的照片，在内部使用 [[PostgreSQL]] 分片存储到不同的服务器上。

这就产生了一个问题，要设计一个唯一 ID 生成方法用来标记系统中发布的每一张图片。

系统唯一 ID 需要满足如下条件：

  • ID 应该是时间有序的，一组照片 ID 列表不再需要外部信息就可以排序（UUID 就不合适，因为完全无序）
  • ID 最好是 64bit ，可以节省存储空间，索引也可以更小，也方便存储到 Redis 这样的系统中
  • 系统应该尽可能少引入外部依赖 （比如使用 Snowflake，就需要引入 Zookeeper，Snowflake 服务）

所以最后 ID 的构成：

  • 41 bit 用来存储毫秒时间（使用自定义 epoch 可以表示 41 年）
  • 13 bit 存储逻辑分片 ID
  • 10 bit 存储自增序列（对 1024 取模， id%1024），这意味着每一个 shard 每一毫秒可以生成 1024 个 ID

Instagram 在他的API文档和网站地址栏中对同一个 Post，使用了两种不一样的ID。在他们的 API 文档中，ids 类似于 908540701891980503_1639186 ， 但是在网站浏览器中则使用的是 ybyPRoQWzX 这样的ID。如果查看几组 ids，能够确性这两种类型的 ids 之间存在关联，Instagram 内部也不可能为同一个帖子存储两套 ids。

在仔细看一下数字的ID，908540701891980503 显然下划线分割的后面为作者的id，前面18位的id 被转为 ybyPRoQWzX 10 位的长度。URL 中的ID信息的密度显然要比数字的id要高。

如果做一个测试，将数字id由base10转为 base64，就得到

9:0:8:5:4:0:7:0:1:8:9:1:9:8:0:5:0:3_10
50:27:50:15:17:40:16:22:51:23_64

这样两组数据，如果将 base64 的数组和10位的id比较，得到

number letter
50 y
27 b
50 y
15 P
17 R
40 o
16 Q
22 W
51 z
23 X

如果对该映射重新排序，则得到

number letter
15 P
16 Q
17 R
22 W
23 X
27 b
40 o
50 y
50 y
51 z

看到该映射，很容易联想到由 A-Z 和 a-z 的关系

number letter
00 A
01 B
02 C
03 D
07 H
08 I
09 J
10 K
11 L
13 N
15 P
16 Q
17 R
20 U
22 W
23 X
24 Y
26 a
27 b
29 d
32 g
34 i
36 k
37 l
40 o
42 q
43 r
47 v
50 y
51 z
56 4
62 -
63 _

这个表和标准 base64 的加密表几乎一致，除了将 + 和 / 变为了 - 和 _ 。这个变动大概因为 / 在URLs中是特殊字符，而 + 号在 URL 中是特殊的请求字符。

启示

知道了两种ids之间的关系，联系一些已知的事实可以知道

唯一性

Instagram 在全平台使用唯一的ID，在 Web 端是 https://instagram.com/p/ybyPRoQWzX , 而这个 ID 能够被转成数字ID，因此我们也知道这个 ID 也是唯一的。

更加惊奇的是数字ID也能够被用于请求 Instagram 内部的接口，比如查看 Instagram 网站的请求，可以发现请求特定用户的 Posts 的接口为

https://instagram.com/<username>/media/?max_id=<numeric id>

比如说 https://instagram.com/gitamba/media/?max_id=915362118751716223_7985735 而事实上，省略了后面的用户ID 也能更能够照样获得结果。而后面加任意内容都会被忽略

https://instagram.com/gitamba/media/?max_id=915398248830305252_whatever

这个请求的到内容和之前的内容一样。

进一步分析

如果知道 Instagram 产生 posts 的唯一ID 的原理 那么可以从 ID 中获取更多信息。在 Instagram 的文章中，没有提及内部的 epoch 是什么时候，但是可以通过计算来获取一个比较准确的值。

post id (base 10) known post created time (unix time)
908540701891980503 1422526513s
936303077400215759 1425836046s
188449103402467464 1336684905s

上面是三个已知发布时间的IDs， post 的id 是64bit ，如果转成 64 bits

post id (base 10) post id (base 2)
908540701891980503 0000110010011011110010001111010001101000010000010110110011010111
936303077400215759 0000110011111110011010101011000000101010100010111000000011001111
188449103402467464 0000001010011101100000010111011000001010100010111000000010001000

截取前41bits，表示的从 Instagram 内部 epoch 开始流逝的时间，毫秒

first 41 bits of post id time since Instagram epoch
00001100100110111100100011110100011010000 108306491600ms
00001100111111100110101010110000001010101 111616024661ms
00000010100111011000000101110110000010101 22464883733ms

最后在用创建post 的时间 unix time 来减去从 id 中获取的时间，得到

created time time since Instagram epoch Instagram epoch (unix time)
1422526513s 108306491600ms 1314220021.400s
1425836046s 111616024661ms 1314220021.339s
1336684905s 22464883733ms 1314220021.267s

如果计算一切都正确，得到的值应该是相等的。微小的误差来自，创建 post 的时间是秒，而 id中获取的时间是毫秒。

经过一系列计算，大致可以知道 Instagram epoch 时间开始于 1314220021 ，也就是 9:07pm UTC on Wednesday, August 24, 2011 看起来是一个随机的 epoch，但猜测可能是 Instagram 内部将 id 由自增长模式转变为现在模式的时间。

ids for testing

id in base 10 id in base64 converted to chars
936303077400215759 51:62:26:43:00:42:34:56:03:15 z-arAqi4DP
908540701891980503 50:27:50:15:17:40:16:22:51:23 ybyPRoQWzX
283455759575646671 15:47:02:24:11:51:02:56:07:15 PvCYLzC4HP
205004325645942831 11:24:20:37:36:23:34:56:00:47 LYUlkXi4Av
188449103402467464 10:29:32:23:24:10:34:56:02:08 KdgXYKi4CI
409960495 24:27:56:00:47 Yb4Av
167566273 09:63:13:47:01 J_NvB

翻译自： https://carrot.is/coding/instagram-ids

  1. https://instagram-engineering.com/sharding-ids-at-instagram-1cf5a71e5a5c?gi=506417a005c8 ↩