- VisualStudio2022插件的安装及使用-编程手把手系列文章
- pprof-在现网场景怎么用
- C#实现的下拉多选框,下拉多选树,多级节点
- 【学习笔记】基础数据结构:猫树
前几天面试遇到的,感觉比较有趣。第一次面试遇到考架构设计相关的题目,挺新奇的,开始向国外大厂靠拢了,比天天问八股文好太多了,工作5年左右的,问八股文,纯纯的不负责任偷懒行为.
感觉此问题比较有趣,这几天简单的实现了一版本,和大家分享一下具体的细节,也欢迎大家交流讨论, 代码github链接 short-url.
业界实现短链的方式大概是有两种.
由长url通过 hash 算法,生成短的url,如果hash冲突,需要解决解决hash冲突。那么这个哈希函数该怎么取呢,相信肯定有很多人说用 MD5,SHA 等算法,其实这样做有点杀鸡用牛刀了,而且既然是加密就意味着性能上会有损失,我们其实不关心反向解密的难度,反而更关心的是哈希的运算速度和冲突概率.
能够满足这样的哈希算法有很多,这里推荐 Google 出品的 MurmurHash 算法,MurmurHash 是一种非加密型哈希函数,适用于一般的哈希检索操作。与其它流行的哈希函数相比,对于规律性较强的 key,MurmurHash 的随机分布特征表现更良好。非加密意味着着相比 MD5,SHA 这些函数它的性能肯定更高(实际上性能是 MD5 等加密算法的十倍以上),也正是由于它的这些优点,所以虽然它出现于 2008,但目前已经广泛应用到 Redis、MemCache、Cassandra、HBase、Lucene 等众多著名的软件中.
MurmurHash32会生成32位的十进制,MurmurHash64会生成64位的十进制。那我们把它转为 62 进制可缩短它的长度,为什么是62进制,不是64呢?因为62进制表示 【a-z A-Z 0-9】字符之和.
在优秀的哈希函数,都不可避免地会产生哈希冲突(尽管概率很低),该怎么解决呢。我们设计如下mysql表 。
CREATE TABLE `short_url` (
`id` int(11) unsigned NOT NULL AUTO_INCREMENT,
`lurl` varchar(150) NOT NULL,
`surl` varchar(10) NOT NULL,
`gmt_create` timestamp NOT NULL DEFAULT CURRENT_TIMESTAMP COMMENT '创建时间',
PRIMARY KEY (`id`),
UNIQUE KEY `idx_surl` (`surl`),
KEY `idx_lurl` (`lurl`)
) ENGINE=InnoDB AUTO_INCREMENT=15536 DEFAULT CHARSET=utf8;
以上步骤显然是要优化的,插入一条记录居然要经过两次 sql(根据短链查记录,将长短链对应关系插入数据库中),如果在高并发下,显然会成为瓶颈.
也就是整一个流程我们只和数据库有一次交互,同时我们引入了LRU的缓存,极大了提高了性能.
维护一个自增id,比如 1,2,3 这样的整数递增 ID,当收到一个长链转短链的请求时,ID 生成器为其分配一个 ID,再将其转化为 62 进制,拼接到短链域名后面就得到了最终的短网址。但此方法需要全局维护一个自增id,同时同一个长的url会生成不同的短的url,并且短的url会有规律,比较容易猜测到.
常见的有以下几种:uuid,redis计数,Snowflake雪花算法,Mysql 自增主键。总和比较感觉雪花算法以及redis计数比较靠谱,可以尝试去使用.
本次选择的hash映射方式,来生成短链。底层数据存储选择是mysql,通过mysql的分库分表,读写分离,也可以有非常高效的效率。如果采用redis,缓存会丢失数据,如果采用hbase,效率不可控,故最后选择mysql作为底层存储数据.
先说下hash函数测试的结论,比较有说服力, 可以直接看HashTest类 。
100W数据,murmur32算法(产生一个32位的hash值),100W大概会有121个冲突 。
- i = 100000(10W), conflictSize = 1
- i = 200000(20W), conflictSize = 6
- i = 300000(30W), conflictSize = 12
- i = 400000(40W), conflictSize = 19
- i = 500000(50W), conflictSize = 32
- i = 600000(60W), conflictSize = 46
- i = 700000(70W), conflictSize = 54
- i = 800000(80W), conflictSize = 76
- i = 900000(90W), conflictSize = 94
- i = 1000000(100W), conflictSize = 121
修改为 murmur64算法,100W 0冲突,500W 0冲突,建议使用murmur64算法 。
public String generateShortUrl(String longUrl) {
if (StringUtils.isEmpty(longUrl)) {
throw new RuntimeException("longUrl 不能为空");
}
String shortUrl = CacheUtils.get(MapConstants.longCache, longUrl);
if (StringUtils.isNotEmpty(shortUrl)) {
return shortUrl;
}
return getShortUrl(longUrl, getLongUrlRandom(longUrl));
}
private String getShortUrl(String rawUrl, String longUrl) {
long hash = HashUtil.murmur64(longUrl.getBytes());
String base62 = Base62.encode(hash + "");
log.info("longUrl = {}, hash = {}, base62 = {}", longUrl, hash, base62);
if (StringUtils.isEmpty(base62)) {
throw new RuntimeException("hash 算法有误");
}
String shortUrl = StringUtils.substring(base62, 6);
ShortUrl url = new ShortUrl(rawUrl, shortUrl);
try {
int insert = shortUrlDAO.insert(url); // 这里进行分库分表 提高性能
if (insert == 1) {
CacheUtils.put(MapConstants.longCache, rawUrl, shortUrl);
}
} catch (DuplicateKeyException e) {
// Hash冲突
log.warn("hash冲突 触发唯一索引 rawUrl = {}, longUrl = {}, shortUrl = {}, e = {}", rawUrl, longUrl, shortUrl, e.getMessage(), e);
CacheUtils.put(MapConstants.hashFailMap, rawUrl, shortUrl);
return getShortUrl(rawUrl, getLongUrlRandom(shortUrl));
} catch (Exception e) {
log.error("未知错误 e = {}", e.getMessage(), e);
throw new RuntimeException("msg = " + e.getMessage());
}
return shortUrl;
}
private String getLongUrlRandom(String longUrl) {
return longUrl + RandomUtil.randomString(6); // 解决冲突多的问题,随机字符串
}
public String getLongUrl(String shortUrl) {
if (StringUtils.isEmpty(shortUrl)) {
throw new RuntimeException("shortUrl 不能为空");
}
String longUrl = CacheUtils.get(MapConstants.shortCache, shortUrl);
if (StringUtils.isNotEmpty(longUrl)) {
return longUrl;
}
LambdaQueryWrapper<ShortUrl> wrapper = new QueryWrapper<ShortUrl>().lambda().eq(ShortUrl::getSUrl, shortUrl);
ShortUrl url = shortUrlDAO.selectOne(wrapper);
CacheUtils.put(MapConstants.shortCache, shortUrl, url.getLUrl());
return url.getLUrl();
}
可以看到生成短链只需要访问一次数据库,获取短链也只需要访问一次数据库,是非常的快的.
本文对短链设计方案作了详细地剖析,旨在给大家提供几种不同的短链设计思路,文中涉及到挺多的技术细节。比如murmur64 hash算法,base62,LRU,以及为什么选择mysql,而不是redis等等。文中没有展开讲,建议大家回头可以去再详细了解一下,同时也希望大家有空,可以自己动手实现一套短链服务,一定会有不小的收获.
最后此篇关于面试官:你讲下如何设计支持千万级别的短链?的文章就讲到这里了,如果你想了解更多关于面试官:你讲下如何设计支持千万级别的短链?的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。
关闭。这个问题需要更多focused .它目前不接受答案。 想改善这个问题吗?更新问题,使其仅关注一个问题 editing this post . 4年前关闭。 Improve this questi
.NET 框架:4.5.1 我在 Blend for visual studio 2015 中遇到一个奇怪的错误,我找不到它的来源。 如果我在 VS 中打开我的 WPF 解决方案,它会加载并运行良好。
我经常遇到这样的问题,与 Hierarchical RESTful URL design 非常相似 假设该服务仅提供用户上传文档。 POST, GET /accounts PUT, DELETE /a
在 Rails 应用程序中,我使用 devise 来管理我的用户,而我用来销毁 session 的链接不再有效。它正在工作,现在我添加了事件管理员,但没有。 我的链接是 :delete, :clas
我已经坚持了超过 24 小时,试图按照此处发布的其他解决方案进行操作,但我无法使其正常工作。我是 Rails 新手,需要帮助! 我想让我的/users/edit 页面正常工作,以便我可以简单地更改用户
Devise 在以下情况下不会使用户超时: 用户登录,关闭选项卡,然后在超时 + X 分钟内重新访问该 URL。用户仍处于登录状态。 如果选项卡已打开并且稍后刷新/单击,则超时可以正常工作。这意味着
我想使用这样的 slider 我希望该 slider 根据提供给它的值进行相应调整。到目前为止,我只能应用具有渐变效果的背景,但无法获得这种效果。请通过提供样式代码来帮助我。
您应该为每种方法创建一个请求/响应对象,还是应该为每个服务创建一个? 如果我在所有方法中使用它,我的服务请求对象中将只有 5 个不同的东西,因为我对几乎所有方法使用相同的输入。 响应对象将只有一个字典
我正在尝试在 REST 中对实体的附件进行建模。假设一个缺陷实体可以附加多个附件。每个附件都有描述和一些其他属性(上次修改时间、文件大小...)。附件本身是任何格式的文件(jpeg、doc ...)
我有以下表格: Blogs { BlogName } BlogPosts { BlogName, PostTitle } 博客文章同时建模一个实体和一个关系,根据 6nf(根据第三个宣言)这是无效的。
如果 A 类与 B、C 和 D 类中的每一个都有唯一的交互,那么交互的代码应该在 A 中还是在 B、C 和 D 中? 我正在编写一个小游戏,其中许多对象可以与其他对象进行独特的交互。例如,EMP点击
关于如何记住我与 Omniauth 一起工作似乎有些困惑。 根据这个wiki ,您需要在 OmniauthCallbacksController 中包含以下内容: remember_me(user)
设计问题: 使用 非线程安全 组件(集合,API,...)在/带有 多线程成分 ... 例子 : 组件 1 :多线程套接字服务器谁向消息处理程序发送消息... 组件 2 :非线程安全 消息处理程序 谁
我们目前正在设计一个 RESTful 应用程序。我们决定使用 XML 作为我们的基本表示。 我有以下关于在 XML 中设计/建模应用程序数据的问题。 在 XML 中进行数据建模的方法有哪些?从头开始然
我正在设计一个新的 XSD 来从业务合作伙伴那里获取积分信息。对于每笔交易,合作伙伴必须提供至少一种积分类型的积分值。我有以下几点:
设计支持多个版本的 API 的最佳方法是什么。我如何确保即使我的数据架构发生更改(微小更改),我的 api 的使用者也不会受到影响?任何引用架构、指南都非常有用。 最佳答案 Mark Nottingh
关闭。这个问题是opinion-based 。目前不接受答案。 想要改进这个问题吗?更新问题,以便 editing this post 可以用事实和引文来回答它。 . 已关闭 4 年前。 Improv
我想用 php 创建一个网站,其工作方式与 https://www.bitcoins.lc/ 相同。确实,就每个页面上具有相同布局但内容会随着您更改链接/页面而改变而言,我如何在 php 中使用lay
我有一个关于编写 Swing UI 的问题。如果我想制作一个带有某些选项的软件,例如在第一个框架上,我有三个按钮(新建、选项、退出)。 现在,如果用户单击新按钮,我想将框架中的整个内容更改为其他内容。
我正在尝试找出并学习将应用程序拥有的一堆Docker容器移至Kubernetes的模式和最佳实践。诸如Pod设计,服务,部署之类的东西。例如,我可以创建一个其中包含单个Web和应用程序容器的Pod,但
我是一名优秀的程序员,十分优秀!