网站空间流量不够,国外销售网站怎样建设,thinkphp开源cms系统,西安高端品牌网站文章目录1. 短网址服务整体介绍2. 如何通过哈希算法生成短网址#xff1f;2.1 如何让短网址更短2.2 如何解决哈希冲突#xff1f;2.3 如何优化哈希算法生成短网址的性能#xff1f;3. 如何通过ID生成器生成短网址#xff1f;3.1 相同的原始网址可能会对应不同的短网址3.2 如…
文章目录1. 短网址服务整体介绍2. 如何通过哈希算法生成短网址2.1 如何让短网址更短2.2 如何解决哈希冲突2.3 如何优化哈希算法生成短网址的性能3. 如何通过ID生成器生成短网址3.1 相同的原始网址可能会对应不同的短网址3.2 如何实现高性能的 ID 生成器4. 总结在微博里发布一条带网址的信息微博会把里面的网址转化成一个更短的网址。只要访问这个短网址就相当于访问原始的网址。
原始网址https://github.com/wangzheng0822/ratelimiter4j
短网址http://t.cn/EtR9QEG1. 短网址服务整体介绍
当用户点击短网址时短网址服务会将浏览器重定向为原始网址。这个过程是如何实现的呢 从图中可看出浏览器会先访问短网址服务通过短网址获取到原始网址再通过原始网址访问到页面。这部分功能今天不讲。重点来看如何将长网址转化成短网址
2. 如何通过哈希算法生成短网址
哈希算法可以将一个不管多长的字符串转化成一个长度固定的哈希值。
在生成短网址这个问题上我们不需要考虑反向解密的难度只需关心哈希算法的计算速度和冲突概率。
比较著名并且应用广泛的一个哈希算法那就是 MurmurHash 算法。尽管这个哈希算法在2008年才被发明出来但现在它已经广泛应用到Redis、MemCache、Cassandra、HBase、Lucene等众多著名的软件中。
MurmurHash 算法提供了两种长度的哈希值一种是32bits一种是128bits。为了让最终生成的短网址尽可能短可以选择32bits的哈希值。对于开头那个GitHub网址经过MurmurHash 计算后得到的哈希值就是181338494。我们再拼上短网址服务的域名就变成了最终的短网址 http://t.cn/181338494其中http://t.cn是短网址服务的域名。
2.1 如何让短网址更短
通过MurmurHash 算法得到的短网址还是很长而且跟开头那个网址的格式好像也不一样。
我们将10进制的哈希值转化成更高进制的哈希值这样哈希值就变短了。我们知道16进制中我们用AE 来表示10~15。在网址URL中常用的合法字符有09、azA ~ Z 这样62个字符。为了让哈希值表示起来尽可能短可以将10进制的哈希值转化成62进制。计算过程如下。最终用62进制表示的短网址就是http://t.cn/cgSqq。
2.2 如何解决哈希冲突
尽管 MurmurHash 算法冲突概率非常低。一旦冲突会导致两个原始网址被转化成同一个短网址。当用户访问短网址时就无从判断想要访问的是哪一个。这个问题该如何解决呢
一般情况下我们会保存短网址跟原始网址之间的对应关系以便后续用户在访问短网址的时候可以根据对应关系查找到原始网址。存储这种对应关系的方式有很多比如自己设计存储系统或者利用现成的数据库。前面我们讲到的数据库有MySQL、Redis。就拿MySQL来举例。假设短网址与原始网址之间的对应关系就存储在MySQL 数据库中。
当有一个新的原始网址需要生成短网址的时候先利用MurmurHash 算法生成短网址。然后拿这个新生成的短网址在MySQL 数据库中查找。 如果没有找到相同的短网址表明这个新生成的短网址没有冲突。于是我们就将这个短网址返回给用户请求生成短网址的用户然后将这个短网址与原始网址之间的对应关系存储到MySQL数据库中。 如果找到了相同的短网址那也并不一定说明就冲突了。我们从数据库中将这个短网址对应的原始网址也取出来。 如果数据库中记录的原始网址跟正在处理的原始网址一样说明已经有人请求过这个原始网址的短网址了。就可以拿这个短网址直接用。如果数据库中记录的原始网址跟正在处理的原始网址不一样说明哈希算法发生了冲突。不同的原始网址经过计算得到的短网址重复了。这个时候怎么办 可以给原始网址拼接一串特殊字符比如“[DUPLICATED]然后再重新计算哈希值两次哈希计算都冲突的概率显然是非常低的。 假设出现非常极端的情况又发生冲突了我们可以再换一个拼接字符串比如“[OHMYGOD]再计算哈希值。然后把计算得到的哈希值跟原始网址拼接了特殊字符串之后的文本一并存储在MySQL数据库中。 当用户访问短网址的时候短网址服务先通过短网址在数据库中查找到对应的原始网址。如果原始网址有拼接特殊字符这个很容易通过字符串匹配算法找到我们就先将特殊字符去掉然后再将不包含特殊字符的原始网址返回给浏览器。
2.3 如何优化哈希算法生成短网址的性能
为了判断生成的短网址是否冲突需要拿生成的短网址在数据库中查找。如果数据库数据非常多查找会非常慢影响短网址服务的性能。如何优化
可以给短网址字段添加B树索引。这样通过短网址查询原始网址的速度就提高了。在短网址生成的过程中我们会跟数据库打两次交道也就是会执行两条SQL语句。第一个SQL 语句是通过短网址查询短网址与原始网址的对应关系第二个SQL语句是将新生成的短网址和原始网址之间的对应关系存储到数据库。
我们知道一般情况下数据库和应用服务只做计算不存储数据的业务逻辑部分会部署在两个独立的服务器或者虚拟服务器上。那两条SQL 语句的执行就需要两次网络通信。这种IO通信耗时以及SQL 语句的执行才是整个短网址服务的性能瓶颈所在。所以为了提高性能需要尽量减少SQL 语句。如何减少SQL 语句呢
可以给数据库中的短网址字段添加一个唯一索引不止是索引还要求表中不能有重复的数据。当有新的原始网址需要生成短网址的时候我们并不会先拿生成的短网址在数据库中查找判重而是直接将生成的短网址与对应的原始网址尝试存储到数据库中。如果数据库能够将数据正常写入那说明并没有违反唯一索引也就是说这个新生成的短网址并没有冲突。如果数据库反馈违反唯一性索引异常那还得重新执行刚刚讲过的“查询、写入”过程SQL语句执行的次数不减反增。但是在大部分情况下我们把新生成的短网址和对应的原始网址插入到数据库的时候并不会出现冲突。所以大部分情况下只需要执行一条写入的SQL语句就可以了。所以从整体上看总的SQL语句执行次数会大大减少。
我们还有另外一个优化SQL语句次数的方法那就是借助布隆过滤器。 把已经生成的短网址构建成布隆过滤器。我们知道布隆过滤器是比较节省内存的一种存储结构长度是10亿的布隆过滤器也只需要125MB左右的内存。 当有新的短网址生成的时候先拿这个新生成的短网址在布隆过滤器中查找。如果查找不存在说明这个新生成的短网址没有冲突。再执行写入短网址和对应原始网页的SQL语句就可以了。通过先查询布隆过滤器总的SQL语句的执行次数减少了。
3. 如何通过ID生成器生成短网址
可以维护一个ID自增生成器。它可以生成1、2、3…这样自增的整数ID。当短网址服务接收到一个原始网址转化成短网址的请求之后它先从ID生成器中取一个号码然后将其转化成62进制表示法拼接到短网址服务的域名比如http://t.cn/后面就形成了最终的短网址。最后我们还是会把生成的短网址和对应的原始网址存储到数据库中。
理论非常简单好理解。有几个细节需要处理。
3.1 相同的原始网址可能会对应不同的短网址
每次新来一个原始网址就生成一个新的短网址会导致两个相同的原始网址生成了不同的短网址。如何处理呢 第一种思路是不做处理。相同的原始网址对应不同的短网址用户是可以接受的。用户只关心短网址能否正确地跳转到原始网址。短网址长什么样他根本就不关心。 第二种思路是借助哈希算法生成短网址的处理思想当要给一个原始网址生成短网址的时候要先拿原始网址在数据库中查找看数据库中是否已经存在相同的原始网址了。如果数据库中存在那我们就取出对应的短网址直接返回给用户。 不过这种处理思路有个问题我们需要给数据库中的短网址和原始网址这两个字段都添加索引。短网址上加索引是为了提高用户查询短网址对应的原始网页的速度原始网址上加索引是为了加快刚刚讲的通过原始网址查询短网址的速度。这种解决思路虽然能满足“相同原始网址对应相同短网址”这样一个需求但是是有代价的一方面两个索引会占用更多的存储空间另一方面索引还会导致插入、删除等操作性能的下降。
3.2 如何实现高性能的 ID 生成器
实现ID生成器的方法有很多比如利用数据库自增字段。当然我们也可以自己维护一个计数器不停地加一加一。但是一个计数器来应对频繁的短网址生成请求显然是有点吃力的因为计数器必须保证生成的ID不重复笼统概念上讲就是需要加锁。如何提高ID生成器的性能呢
第一种思路可以给ID生成器装多个前置发号器。我们批量地给每个前置发号器发送ID号码。当我们接受到短网址生成请求的时候就选择一个前置发号器来取号码。这样通过多个前置发号器明显提高了并发发号的能力。 第二种思路跟第一种差不多。不再使用一个ID生成器和多个前置发号器这样的架构直接实现多个ID生成器同时服务。为了保证每个ID生成器生成的ID不重复。我们要求每个ID生成器按照一定的规则来生成ID号码。比如第一个ID生成器只能生成尾号为0的第二个只能生成尾号为1的以此类推。通过多个ID生成器同时工作也提高了ID生成的效率。
4. 总结
短网址服务的两种实现方法。
通过哈希算法生成短网址。采用计算速度快、冲突概率小的MurmurHash算法并将计算得到的10进制数转化成62进制表示法进一步缩短短网址的长度。对于哈希算法的哈希冲突问题通过给原始网址添加特殊前缀字符重新计算哈希值的方法来解决。
通过ID生成器生成短网址。维护一个ID自增的ID生成器给每个原始网址分配一个ID号码并且同样转成62进制表示法拼接到短网址服务的域名之后形成最终的短网址。
