短链接系统的算法原理

平时我们在上网的时候，印象最深刻的有一次是短链接的服务。例如：平时在微信上看一个网页的时候，如果我们选择在浏览器打开的时候，会看到很长的URL，我们分享的时候，会看到一个很短URL，这就是本次所说的歼岩短链接的应用之一。

长链接示例： https://mp.weixin.qq.com/s?__biz=MzAxNzMwOTQ0NA==&mid=2653355437&idx=1&sn=5901826ea638462ff71b7f2d06c6331d&chksm=8035d7c6b7425ed06661866af60657414bb71765d2ce915d14726736fa1e72ea8a529331c947&scene=0&key=34df968fd24033237ff036c7de8b6745e1968de9564cf2a8db689025dd0c3682848381771dab960824f506e6f9d484614746f9c0eecb48b884ce4320bb86470a77ce811cc5b401a8800b6fd6b36be097&ascene=0&uin=ODU5NDQ1NjI1&devicetype=iMac+MacBookAir6%2C2+OSX+OSX+10.12.6+build(16G29)&version=12020810&nettype=WIFI&悄槐fontScale=100&pass_ticket=IvPqxUmCJqZg9%2B3GfAIQSbQ4IGRIHx796D0UwlCyUCu4b5P4bSsjlN89A0eRzSfL

我用短链接系统生成的（长期会失效）： https://0x9.me/FAKcm

废话少说，短链接就是我们很短的链接。我们的目的是要把长链接转换成短链接。接下来我要提出一个问题：怎么把长链接转换成短链接呢？

1.压缩

实现一种算法，将长地址转换成短地址。然后再实现一种逆运算，将短地址转换成原来的地址。其实仔细的想一下，这是不可能的。

2.Hash算法

可能是大多数人都会想到的一种方法。有人会提出，将一个长URL进行Hash运算，然后将Hash值作为这个长链接的唯一标示。但是通常容易想到的不一定是最优的，我们知道Hash有可能产生碰撞，Hash碰撞的解决，会增强短链接系统的复杂度。

顾名思义这个系统的第一个请求过来了，我们以微博为例，短链接系统的第一个请求我们可以给变为t.cn/0，第二个t.cn/1等等；

实现的方式也会很简单

1、小型的系统用MySQL的自增索引就可以满足。

2、大型系统可以考虑分布式key-value系统。

发号策略是这样的，当一个新的链接过来时，发号器发一个号与之对应。往后只要有新链接过来，发号器不停发号就好。举个例子，第一个进来的链接发号器发0号，对应的短链接为 xx.xxx/0，第二个进来的链接发号器发1号，对应的短链接为 xx.xxx/1，以此类推。

发号器发出的10进制号需要转启改友换成62进制，这样可以大大缩短号码转换成字符串后的长度。比如发号器发出 10,000,000,000 这个号码，如果不转换成62进制，直接拼接在域名后面，得到这样一个链接 xx.xxx/10000000000。将上面的号码转换成62进制，结果为AOYKUa，长度只有6位，拼接得到的链接为 xx.xxx/AOYKUa。可以看得出，进制转换后得到的短链接长度变短了一些。6位62进制数，对应的号码空间为626，约等于568亿，所以基本上不用担心发号器无号可发的情况。

上面设计看起来有一个单点，那就是发号器。如果做成分布式的，那么多节点要保持同步加1，多点同时写入。这样难以避免产生单点性能瓶颈。因此我们可以考虑将单点变为多点。我们可以引入多个机器，我们可以设定机器A发号只发向100取余等于0的数字100n，同理机器B只发向100取余等于1数字 100n+1，以此类推，各个机器相互独立互不干扰，我们可以随时扩展我们的机器了。

同一长链接，每次转成的短链接不一定一样，原因在于如果查询缓存时，如果未命中，发号器会发新号给这个链接。需要说明的是，缓存应该缓存经常转换的热门链接，假设设定缓存过期时间为一小时，如果某个链接很活跃的话，缓存查询命中后，缓存会刷新这个链接的存活时间，重新计时，这个链接就会长久存在缓存中。

我们也可以引入LRU算法。进行淘汰我们不经常使用到的链接。

选取301，还是302？

301是永久重定向，302是临时重定向。

如果选择301 ：短地址生成以后就不会变化，所以用301是符合http语义的。同时对服务器压力也会有一定减少。这样一来，我们就无法统计到短地址被点击的次数了。

如果选择302 ：选择302虽然会增加服务器压力，但是可以统计到短地址被点击的次数了，我可以针对点击的次数来进行后期的大数据处理，机器学习，以及推荐算法。

选择302还是301，想必读者心中有肯定有数了。

原理很简单，就是把你的网址放到他的数据库，然后与一个自动生成的短字符关联起来 那么下次你点击拍弊的时候就可以直做做接输入这个短地址，然后他的网站把你的浏览器重定向到你原来输入的网址袭胡族

微地址是指微指令在控制存储器的存储位置。

微地址形成方法三种。

1、由指令的OP字段确定。

2、增量方式。类似于机器指令的控制方式，也有顺序，转移和转子之分。一般将μMAR改为具有计数功能的寄存器，起到μPC的功能。

3、断定方式。后继微指令地址可由微程序设计者制定。即根据顺序控制字段中的测试字段和下地址字段确定。

扩展资料

一条机器指令对埋闷应一个微程序，这个微程序是由若干条微指令构成的。因此，一条机器指令的功能是若干条微指令组成的序列来实现的。简而言之，一条机器指令所完成弯贺弯的 *** 作划分成若干条微指令来完成，由微指令进行解释和执行。

从指令与微指令，程序与微程序，地址与微地址的一一对应关系上看，前者与内存储器有关，而后者与控制存储器（它是微程序控制器的一部分。微程序控制器主要由控制存储器、微指令寄存器和地址转移逻辑三部分组成。其中，微指令寄存器又分为微地址寄存器和微命拍敏令寄存器两部分）有关，与此相关也有相对应的硬设备。

一条机器指令对应4个CPU周期，每个CPU周期就对于一条微指令。

---