首页
题库
面试
求职
学习
竞赛
More+
所有博客
搜索面经/职位/试题/公司
搜索
我要招人
去企业版
登录 / 注册
首页
>
试题广场
>
微博中的url往往很长,发送前要转化为tinyurl,请设计
[问答题]
微博中的url往往很长,发送前要转化为tinyurl
1、url如何转为tinyurl编码
2、如果用户输入一个已经转换过的URL,如何快速定位到已经生成了的tinyurl 3、如果数据为10亿条,需要10个tinyurl服务器,怎么设计?
添加笔记
求解答(0)
邀请回答
收藏(14)
分享
纠错
2个回答
添加回答
1
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)
0
威士忌
提供自己觉得还不是完美的方案。
1、使用Hash函数对字符串进行hash,得到一个int值,(32位下int值域是2,147,483,648)。然后采用a-z A-Z 0-9组成的编码,该编码可表示 26+26+10=62进制系统,62
5
=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收藏
29014浏览
热门推荐
相关试题
假设一个 mp3 搜索引擎收录了 ...
百度
分布式
系统设计
百元难题
评论
(1)
大规模的字典中,需要词与词中间的搭...
查找
分布式
系统设计
百元难题
评论
(0)
分页系统的逻辑地址结构是一维的,分...
操作系统
评论
(1)
关于分段系统与分页系统的区别,描述...
操作系统
评论
(1)
扫描二维码,关注牛客网
意见反馈
下载牛客APP,随时随地刷题