求解 Design Tiny URL

https://leetcode.com/problems/en ... inyurl/description/
求解 discussion里面好像没有很好的答案

手机打字。。。这本质上就是一个发号器。每一个regional的cluster要发出unique的号码，还要保证latency(不能加global)的锁。 那么我们可以从前缀入手，每个region，甚至于每个cluster deploy的时候就直接为其指定一个regional前缀。之后查询的时候就知道初始数据在哪里，如果本地cache没有可以很容易找到原始记录。 而每个地区的数据库也可以分表，每个表assign不同的前缀。每个表内部id唯一。

staycrazy 发表于 2017-8-22 04:31
手机打字。。。这本质上就是一个发号器。每一个regional的cluster要发出unique的号码，还要保证latency(不 ...

完全不懂，求问这个new grad面试会考到您说的东西么

是这样的，先从需求入手分析，我们其实就需要两个功能

1.给出一个url，吐出来一个唯一的id

2.给出一个id，返回曾经记录的url

那么抛去实现的细枝末节，这里#1的难点在于concurrency，就是说两个或者多个用户同时请求的时候，我们不能给出同样的id。如果我们只有一个数据中心一个数据库，当然是很好解决的，用relational数据库的sequence number就好。但是我们都知道唯一数据中心唯一数据库有availability、latency和scalability的问题。

所以我们就要多地区多中心，每个数据中心存自己的unique id和url的mapping。这里又回到开始的问题就是会有重复的id。那么我们给不同的数据中心的id加上一个前缀，也就是这个数据中心的唯一编号，就很容易地解决了这个问题。在数据中心内部，可以用类似的手法分数据库，避免过载。每个数据库用sequencial number就好了，保证编号唯一。查询的时候要加分布式cache，要不然跨区查询太耗时。每天跑一个或者多个job把其他中心的data propagate过来存在本地，这样可以减少跨区域读取。

最后，new grads一般不会面，但是也看面试者对你的期望。。。如果你简历很厉害还是有可能会考察的。。。

staycrazy 发表于 2017-8-24 02:23
是这样的，先从需求入手分析，我们其实就需要两个功能

1.给出一个url，吐出来一个唯一的id

谢谢，作为ee转过来的果然还是理解太少了，非常感谢！希望工作几年能理解这些。。

staycrazy 发表于 2017-8-24 02:23
是这样的，先从需求入手分析，我们其实就需要两个功能

1.给出一个url，吐出来一个唯一的id

谢谢解释! 我想问一下您说的--"两个或者多个用户同时请求的时候，我们不能给出同样的id".
我对这题的feature有点疑问 (不是质疑您的答案), 如果两个不同用户请求shorten两个不同的url, 我们当然是需要给出不一样的id, 但是如果这两个用户请求shorten相同的url呢? 其实我们应不应该返回同一个id呢? 感觉这个scenario我们只需要查找database看一下原URL是不是已经给过一个id了, 对吧? 楼主贴的leetcode的答案貌似没有check这个, 而是重新生成新的id. 所以我有点对feature不太理解了.
进一步说, 如果user需要login才能生成shorten url的话, 那么两个不同的用户shorten同样的URL, 应不应该生成同一个id呢? 我感觉不应该生成同一个ID, 因为这个id跟user是有关联的.
求赐教! 谢谢!

Felix1218 发表于 2017-10-1 04:52
谢谢解释! 我想问一下您说的--"两个或者多个用户同时请求的时候，我们不能给出同样的id".
我对这题的fe ...

当时手机打字有所遗漏在所难免。。

现在也是，大致说一下

check url是否存在可行，但是并非必要。我们的key是shortened url，如果我们要反查，就要做index on origin，而且还不能保证百分百成功，因为有race condition。做index也有performance问题。

这里可以做的一个优化是做一个lru cache，把最近的创建结果index扔里面。

关于登录用户，参考gist的实现，在路径上加个用户名参数就好了