ruby-on-rails - URL 缩短器如何大规模工作(例如 t.co 在 Twitter 的情况下)

Question

标准方法包括生成一个唯一的 ID(较小的整数，通常是一个自动递增的 ID)，然后在双射函数中使用该 ID 来生成一个较小的字符串，如下所述: https://stackoverflow.com/a/742047/762747

但这种方法不适用于大规模的分布式系统。 NoSQL 数据库的 id 通常要大得多以确保唯一性。可以尝试生成自动递增 ID，但这肯定会很低效。

是否有任何其他方法来生成短 URL。具体来说:

1) twitter 如何生成 t.co URL，因为这是我们谈论规模时我能想到的最好的例子。推文 ID 大得多(他们使用雪花)，所以我们可以说推特没有(而且可能不能)使用自动递增 ID。

2) 如果他们使用相同的方法，那么 URL 缩短是异步的，以确保他们在生成自动递增 ID 和短 URL 时不会影响性能吗？

至于我的具体情况，我试图从 mongo BSON id 生成一个唯一的缩短字符串。当我尝试缩短 BSON id 时，上述方法会产生一个 16 个字符的 base 62 字符串。我可以采用唯一的自动递增 id 路线，但由于显而易见的原因，这听起来效率很低。想法？如果 Twitter 可以做到，我们也可以。好人@twitter，你介意分享你的方法吗？

Answer 1

自增不是要求，要求是ID唯一。您只需将连续的 ID block 外包给每个发布新 ID 的服务器使用。这些服务器然后从 block 的开始自动递增到 block 的末尾。跨服务器锁定是在 ID block 级别而不是单个 ID 级别完成的。

您可以通过对数据库进行低优先级后台扫描来处理不可避免的 ID 差距，该数据库会收集 ID 中的差距，并将它们添加到要养殖的范围的“已知免费”列表中在发布新的 ID 范围之前退出。

无论是全局自增还是局部自增，理论上ID个数都是O(N)。这仅表明，有时算法复杂度并不能很好地衡量预期性能。