系统设计系列讲解 - ID Generator

Xavier · 29 November 2019 02:26

使用场景(Scenario) 微博和Twitter都有140字数的限制，如果分享一个长网址，很容易就超出限制，发布出去。短网址服务可以把一个长网址变成短网址，方便在社交网络上传播。需求(Needs) 很显然，要尽可能的短。长度设计为多少才合适呢？短网址的长度当前互联网上的网页总数大概是 45亿(参考 http://www.worldwidewebsize.com)，45亿超过了 2^{32}=4294967296232=4294967296，但远远小于64位整数的上限值，那么用一个64位整数足够了。微博的短网址服务用的是长度为7的字符串，这个字符串可以看做是62进制的数，那么最大能表示{62}^7=3521614606208627=3521614606208个网址，远远大于45亿。所以长度为7就足够了。一个64位整数如何转化为字符串呢？，假设我们只是用大小写字母加数字，那么可以看做是62进制数，log_{62} {(2^{64}-1)}=10.7log62(264−1)=10.7，即字符串最长11就足够了。实际生产中，还可以再短一点，比如新浪微博采…

https://soulmachine.gitbooks.io/system-design/content/cn/distributed-id-generator.html

亚麻04.18三轮VO Interview

timeline： 2.8 收到内推确认邮件 2.21 OA1 3.2 OA2 4.4 选VO时间 4.18 VO 第一轮，Senior Engineer台湾小哥。一道设计题，需要提供两个api，一个get()，一个put() 给了个例子: get() -> 1 get() -> 2 get() -> 3 put(2) get() -> 2 get() -> 4 put(3) get() -> 3 get() -> 5 follow up 是，如果get比put多很多怎么处理 BQ: tight deadline，从我给的例子又问了一些问题。第二轮，印度大哥，声音断断续续，让他重复了好多遍问题。第一题，给我画了一个tree, 先让我inorder顺序打印出来，然后说我现在加一个thread，楼主当时很开心，因为以前数据结构写过threaded tree， thread指向的是当前节点的inorder successor。但是这题里thread定义不一样，thread可以指向任何的inorder travers…

FB面试高频 | Instagram的分片与ID设计 Interview

Facebook 的系统设计面试，一般必考自家的技术实践难题。比如facebook news feed 如何设计，Instagram 的分片和 ID设计。今天我们来读一读 FB 官方技术博客的这篇《Instagram 分片与ID设计》。 Instagram上有大量的数据，每分钟就有超过25张的图片和90个点赞。为了确保所有重要的数据都能被合理存储并且及时得被提取应用，我们对数据进行了分片（sharding）——也就是说，我们把数据放到多个桶（bucket）中，每个桶里都有一部分数据。我们的应用服务器上运行的是Django，后端数据库是PostgreSQL。对数据分片首先要决定是否要保留PostgreSQL作为主要的数据存储库，是否要采用其他的数据库。经过评估一些不同的数据库解决方案，我们最终确定最适合的方案是在PostgreSQL数据库集群上实现数据分片。然而在把数据写到数据库之前，我们还要解决如何给数据（例如Instagram上发布的没一张图片）加上唯一标识符的问题。在单一数据库上的典型解法——使用数据库自带的自增主键功能——在当数据需要被同时插入到多个数据库时就不适…