首页 > 试题广场 >

微博中的url往往很长，发送前要转化为tinyurl，请设计

[问答题]

微博中的url往往很长，发送前要转化为tinyurl
1、url如何转为tinyurl编码
2、如果用户输入一个已经转换过的URL，如何快速定位到已经生成了的tinyurl 3、如果数据为10亿条，需要10个tinyurl服务器，怎么设计？

fakir

1. url转换为tinyurl编码使用数据库的自增ID, 但是随着url数量的增加可能数字串很长, 所以我们对id进行进制压缩,转换为一个字符串, 这里我们不采用传统的十六进制,而是将所有字母和数字都用上, 其中字母只使用大写字母, 去除数字0和字母O这两个难以分辨, 这样我们可以使用的字符数为 26+10-2=34, 所以我们使用34进制进行压缩

比如我们tinyurl长度限制在5个字符,那么可以标示的url数量为

34^1+34^2+34^3+34^4+34^5 这是一个非常惊人的数字

2. 数据库中自增ID都是建立索引的, 一个请求的tinyurl我们可以很快的将其还原为唯一ID, 然后直接查询数据库即可以获得原始url, 当然我们在这个过程中可以使用redis, leveldb等kv数据库进一步家加快查询过程

3.由于自增ID的特殊性质,我们使用取模轮训的方式完全能够保证这10亿条url能够均匀分布在10太服务器, 在十台服务器之前加上负载均衡, 根据进制压缩的结果讲请求转发到相应的服务器,每个服务器中有独立***, 后端公用数据库

发表于 2015-01-16 11:32:23 回复(0)

威士忌

提供自己觉得还不是完美的方案。

1、使用Hash函数对字符串进行hash，得到一个int值，（32位下int值域是2,147,483,648）。然后采用a-z A-Z 0-9组成的编码，该编码可表示 26+26+10=62进制系统，62⁵=916,132,832，就是说5位编码能容下9亿多条url。只要是hash就免不了会冲突，当hash值冲突时，采用开散列，记录下标，再采用上述编码进行编号。

最终编码格式为： 5位hash值编码 + 不定长下标编码

简单描述为 Encode(Hash(url)) + Encode(CollideIndex(Hash(url)))

重点是挑个均匀点的Hash函数，否则会出现服务器负载不均。

然后均匀分到10个服务器， Hash(url)/916,132,84 =服务器编号，最后一个服务器会比其他服务器少8个值，但总体还是均匀的。

2、Decode(tinyurl[:5])/ 916,132,84得到服务器编号，Decode( tinyurl[:5] )是hash值， Decode(tinyurl[5:])是开散列下标

3、当Hash函数是均匀分布时，10亿条平均散到10台服务器，每台是1亿条，即100M。假设平均url长度为100，那就需要10GB内存。可以考虑按区间将区间内的url写入文件，保留部分热点url在内存中，切换规则可以考虑LRU。

发表于 2014-12-30 20:09:50 回复(0)

提交观点

问题信息

百度分布式系统设计

上传者：KnightCastle

难度：

2条回答 14收藏 29261浏览

微博中的url往往很长，发送前要转化为tinyurl，请设计

问题信息

热门推荐

相关试题