URL短网址系统的算法设计及实践

avatar
@京东科技

Alt
在通常情况下,URL是由系统生成的,通常包括URI路径,多个查询参数,可以对参数进行加密和解密。当人们要分享某个URL,比如短信,邮件,社交媒体,这就需要短URL。

而短网址,顾名思义就是在长度上比较短的网址。简单来说就是帮您把冗长的URL地址缩短成8个字符以内的短网址。

你有没有遇到过短信字符过长本来一条信息搞定的事情需要发两条?你有没有遇到过填报系统里填写网址却因为字符限制无法完整提交?你有没有遇到过排版好的内容由于链接过长而完全打乱了美感?

这时候,你就需要用到短网址生成工具了。

如开发者社区的某个链接:developer.jdcloud.com/article/894… 变成短网址后:w.3.cn/1000000xZ

我们可以看到,原URL从50多个字符,缩短为了10多个字符,跳转地址不会改变的同时,还能进行后台链接地址的数据追踪。非常便于消息通知、广告推广等场景中使用。

短网址是如何形成的?

通常情况下短网址的生成流程,分以下2条路径:

Alt

  • 从缓存中查询长网址是否已经生成过短网址,如果已经生成过,则直接返回缓存中的短网址,因为同一个长网址始终对应同一个短网址。
  • 从缓存中查询长网址是否已经生成过短网址,如果没有生成过,则使用算法生成一个短网址,然后保存短网址与长网址的关系,并判断是否碰撞,本案因采用了无碰撞递增算法,可直接返回短网址。

注意:此处市面上大多产品采用随机算法,存在很大的碰撞概率,如果缓存中已经存在了该短网址,就会重新生成,当并发极高的情况,碰撞率(新生成的短码在缓存中已存在,需要再次重新生的概率)也大大升高,就会形成一个死循环,如上图蓝色部分,极大的降低了性能。

分布式无碰撞短码生成算法

短如果你经常使用短网址就会发现,市面接口生成性能普遍较差,同时生成大量短链时,可能会超时或失败。这是因为市面大多的算法是随机算法,碰撞率比较高,还有部分数据库自增算法,虽然无碰撞,但是过度依赖数据库导致性能比较差。

而另外一种常遇到的情况是,生成的短链时不时的会出现出现短连接失效或链接内容无法追踪的情况。这是因为短链过期了,而我们的短网址只要在过期时间内有访问就会不断延期,达到有访问的连接永久有效,无访问的连接自动过期回收的效果。

那么怎样才能避免上述情况的出现呢?

我们通过采用缓存加内存的发号方式去对链接进行处理,实现了短链无碰撞且高性能的分布式无碰撞短码生成服务。

分布式无碰撞短码生成算法主要通过内存发号、缓存取号、保障机制三个主要环节来进行实现。

Alt

  • 绿色通道:内存发号,速度极快,每次从缓存取出10000个无重复号码,然后在内存中便可连续生成10000个短码,因此速度比传统基于数据库及缓存自增发号方式快万倍。
  • 蓝色通道:缓存取号,依赖缓存保证分布式发号无碰撞,批量发号,每一万次内存绿色通道才走一次蓝色缓存通道,因此性能极高
  • 红色通道:保障机制,保障生成的号码都在短网址对应长度的号码总容量范围内,仅在初始化及总容量用尽时执行,性能损耗可忽略不计。

通过该算法生成的短链主要有以下特点:

1、有访问自动延期,无访问自动过期回收,可根据业务需要自行选择有效期,减少死码长期占用资源消耗费用,避免短码越积越多导致的碰撞率升高及性能下降

2、自研专利算法、无碰撞率、只依赖缓存不依赖数据库,效率超高超稳定

3、用户自定义域名、体现自有品牌价值、成本低廉、接入简单

实用操作指南

短网址服务目前在京东主要应用于:订单消息通知、物流通知、促销短信、二维码分享 等任何有字数限制的使用场景。

微博、Twitter、消息推送、短信等都有单条发送字数的限制,以短信为例,单条发送限制70个字符。如果包含一个长网址(假设50个字符),则要传递的有效信息就只有20个字符,很容易表达不清,或超出70个字符产生2条短信费用。

以我们一开始生成的链接为例:w.3.cn/1000000xZ

短网址中分为域名host和短码部分,w.3.cn/1000000xZ 中,w.3.cn 为域名,1000000xZ为短码,短码长度可根据需求进行调整,对应不同的最大有效期。

Alt
最大有效期为当前长度下有效期可配置的最长时间,失效后将无法再使用,服务支持有访问时自动续期,需要传入有效期参数0,将自动配置为最大有效期同时有访问自动更新当前有效期为最大时间。

使用短网址服务可以把一个长网址缩短成短网址(假设20个字符),则要传递的有效信息就可以增长到50个字符,即能传递更多的有效信息,又能节省大量短信费用。因此,如何将长网址缩到最短,并且在高并发场景下保持高效率,至关重要。

你问我短码生成难不难?

来!

首先,打开浏览器输入网址http://short.jdcloud.com或直接点击 体验,输入长网址,然后点击生成即可。

Alt
欢迎点击“京东云”了解更多精彩内容。

Alt

Alt