一个企业级高并发短链接服务项目分享

这个项目我在企业做过的一个高并发服务，功能很简单，但有很多技术难点和技术细节。没有做过企业级项目的同学可以好好看看，想想怎么挖掘自己项目的亮点。也欢迎各位同学跟我讨论，大家理解透彻后，完全可以实操一下这个项目，写在简历中。

1 目标

生产级别的互联网应用的架构、设计思路、原理及调优、演进思路。
涉及到三高：高可用、高性能、高并发。
广度和深度覆盖全面，能够全面体现出程序员的能力水平。

2 使用场景

电商推广：短信、邮件 一般来说，一条短信最多70个汉字，140个字节。如果超出一般会被运营商自动拆分为2条短信，增加了运营成本。
社交网络分享：微博和Twitter都有140字数的限制，如果分享一个长链接，很容易就超出限制。短链接服务可以把一个长链接变成短链接，方便在社交网络上传播。

3 真实案例

我们看到短信里面的URI是数字加子母组成的字符，跟我们平时写代码时的URI不太一样。
实际上这就是一个短链接，其实原始的内部长链接可能长这样：

https://dpubstatic.udache.com/static/dpubimg/d4c0e518e95afb4e669affa6eb15d1d6/index.html  

3.1 工作流程

用户点击这个短链接后，会跳转到内部的长链接。基本流程图:

客户端-->发出短链接请求--> 重定向跳转--->长链接

3.1.1 为什么使用302重定向

4 软件详细设计

4.1 功能性需求

1.给定原始的Long URL，短链服务能生成比它短且唯一的Short URL
2.用户点击Short URL， 能跳转到Long URL
3.有效期/过期机制
4.Short URL越短越好

4.2 非功能性需求

1.高可用：服务不能存在单点故障，用冗余来解决高可用问题。
2.高性能：生成Short URL以及从Short URL 跳转到Long URL 要近实时。读写比预估100:1
3.安全：短链不可被猜测(防止被攻击和滥用，引发不可知的情况)

4.3 短链生成

短链接的原理其实就是：将长链接通过一定的算法生成一个短链接。访问短链接时实际访问的是短链接服务器，然后根据短链接的参数找回对应的长链接重定向跳转。短URL包含一个短链接网站+短连接key。 系统本质上包含一个短链算法模块和一个Hash表。
长URL通过短链算法生成短URL。将短URL作为key，长URL作为value，保存到Hash表中。
用户输入短URL，直接从Hash表中查找并返回长URL。

4.4 算法选择

4.4.1 算法要求

1. 生成值比原始值短
2. 唯一性
3. 高效、低CPU内存消耗
4. 安全不可预测

4.4.2 常见Hash算法

4.4.2.1 MD5

准确说它是一种信息摘要算法，从一个字符串或一个文件中按照一定的规律生成一个特殊的字符串。
生成的字符串是满足唯一性的，但输出是128位的，还是比较长

4.4.2.2 SHA

SHA家族的五个算法，分别是SHA-1、SHA-224、SHA-256、SHA-384，和SHA-512，由美国国家安全局（NSA）所设计，并由美国国家标准与技术研究院（NIST）发布；是美国的政府标准。
生成的字符串是满足唯一性的。输出长度还是较大，而且这类算法属于加密型HASH算法，本质是为了数据加密传输，后续需要能够逆向得到原始字符串，相应的算法性能比较低。
评价一个哈希算法的好坏，人们通常会引用 SMHasher 测试集的运行结果。 Smhasher 测试Hash函数的功能，测试包括以下几个方面：

• Sanity 是不是可以使用的
• Performance 完成一个散列需要多长时间
• Differentials 产生相同哈希的概率，可能导致相同的的最小差异
• Keysets 分布均匀程度
  一系列的测试方式具体可参考：https://github.com/aappleby/smhasher/wiki/SMHasher

4.4.2.3 MurmurHash

随机分布特征表现更良好，发生 Hash 碰撞的几率更低。比起 MD5它的性能至少提升了一个数量级。生成的结果为32bit或64bit相比MD5的长度缩短了一个量级。
MurmurHash在很多现代KV型存储中间件中被广泛使用，如在Redis中当字典被用作数据库的底层实现或者哈希键的底层实现时，Redis 使用 MurmurHash2 算法来计算键的哈希值。
算法主页: http://code.google.com/p/smhasher/

4.4.3 如何做到最短

1000万用户平均每个月10条短信 每个月基本上1亿个短链接即可。 预估未来五年增长到5000万用户，5亿短链接基本够用。
通常短链是用 [0-9], [a-z], [A-Z] 这 62 个字符的组合来表示的，我们可以选择用这62个字符对MurmurHash的结果做base62编码，那么长度是 N 的短链可以映射的 URL 数量如下图：
5位长度基本满足未来五年需求，6位一定满足，按照6位来设计(扩展性更强，余地更多)。

4.4.4 如何解决HASH冲突

4.4.4.1 冲突识别

方案1：先根据短链接查询数据库，如果不存在则插入；
问题：先查再插入，涉及两次网络请求及可能的磁盘调度
方案2：短链接字段建立唯一索引，直接插入，通过数据库唯一索引检测判断重复
方案3：通过布隆过滤器快速判断短链不存在，不需要唯一索引，可消除磁盘IO调度影响
但这个看似挺好，实际由于布隆过滤器数据易丢失，造成短链生成冲突

4.4.4.2 解决冲突

尽管 MurmurHash 算法，冲突的概率非常低。但是，一旦冲突，就会导致两个原始链接被转化成同一个短链接。可以给原始链接拼接一串特殊字符，比如“[REPEAT]”，然后跟再重新计算哈希值，两次哈希计算都冲突的概率，显然是非常低的。

4.4.5 如何解决重复长地址转换攻击

用户连续发起对同样的长地址转换请求
服务端处理逻辑：
1）长地址 -> 短地址
2）短地址冲突
3）长地址叠加随机值 -> 短地址
4）入库
在大量请求下，一个长地址对应多个短地址，消耗数据库资源，并造成数据库操作效率降低。
解决方案：
1）给长地址也加唯一索引
有没更高效的办法？
2）使用布隆过滤器存储长地址，每次转换前先判断下长地址是否已经转换过。
这种方法效率高，虽然有布隆过滤器数据丢失后造成长地址对应多个短地址，但在高可用Redis集群模式下，丢失的不会太多，对应多个短地址也不影响用户使用

4.4.6 总结

采用计算速度快、冲突概率小的Murmur-Hash 算法，通过hash得到10进制数，然后转化成 62 进制表示法，进一步减小短链接的长度。对于哈希算法的哈希冲突问题，我们通过给原始网址添加特殊前缀字符，重新计算哈希值的方法来解决。

4.5 短链接过期解决方案

短链接数据多为短时效存储数据，不需要永久保存，如优惠券、促销活动等，之前的设计中短地址是永久保存在数据库和分布式缓存中，会带来数据库和Redis的存储资源容量持续增长，最终导致访问数据库速度下降以及Redis的OOM问题。
解决方案：设置过期时间，惰性删除 + 定时删除
1、接口层面
需要再重载一个接口，提供timeout字段可让用户自行决定保留时间，没有提供timeout可根据公司的业务场景给定一个默认保留时间
2、Redis层面
数据入Redis时设置过期时间，按照二八原则定律，百分之八十的数据会在存入数据后的百分之二十的过期时间内访问。
1）为减少内存消耗，Redis中数据的过期时间为数据库中相应数据剩余保留时间的一定比例
2）为避免缓存雪崩问题，保留比例设置为(0.2, 0.5)范围内的随机值。同时为避免Redis崩溃带来的雪崩问题，对Redis集群应做高可用处理
3、数据库层面
需加入createdTime，expiredTime两个数据类型为时间戳的字段， 参考Redis的数据过期处理原理 =》惰性+定时删除相结合。
1）数据库数据惰性删除
查询数据时判断已过期，则同步删除，返回提示用户短地址已失效。 2）数据库数据定时删除
通过定时任务，如每天凌晨扫描数据库中expiredTime < now()的数据。 为避免锁表：读已提交隔离级别 + expiredTime设置索引。
3）定时任务框架选择：
1）JDK自带ScheduledExecutorService
微服务多节点部署下重复执行的问题，不会出现业务问题，但浪费数据库性能
2）分布式任务调度框架
框架选型可参考：https://cloud.tencent.com/developer/article/2046586
考虑到Saturn、ElasticJob需要额外依赖Zookeeper增加维护成本，XXL-JOB作为初学者部署及开发难度相对较大，
数据库定时删除对于可用性和性能要求较低，这里选用Quartz作为调度框架

4.6 数据库设计

4.6.1 建表语句

4.6.2 分库分表

单表按照1800W数据来计算，3.6亿/1800W = 20张表。 单库按照8000W数据计算，3.6亿/8000W = 5个库。 url_mapping 分表的 key 可以使用短链 Key 或创建时间来计算 hash，通过一致性 Hash 算法把记录路由到对应的分表。
url_0 url_mapping_0 ~ url_mapping_3
url_1 url_mapping_4 ~ url_mapping_7
url_2 url_mapping_8 ~ url_mapping_11
url_3 url_mapping_12 ~ url_mapping_15
url_4 url_mapping_16 ~ url_mapping_19

4.7 性能极致优化

4.7.1 全局自增ID

所谓的全局自增ID：我们的服务是集群模式，全局自增意味着此ID在该集群内唯一且自增。

去掉Hash的过程，同时预生成一批短链接，请求来了直接建立映射关系。
不同于 Hash 算法，全局自增 ID 的方案不需要对长 URL 进行 Hash 转换。因为 ID 全局自增且唯一，能确保一个 ID 只映射一个长 URL，不存在Hash 算法中存在的多个长 URL 可能映射到同一个短链的问题。基于全局自增 ID 的方案，依赖自增ID产生的效率。
可以选用无需即时生成的分布式ID解决方案，如美团的leaf开源组件，百度Uidgenerator开源组件，都有批量号段缓存及缓存预加载机制，ID的获取操作就是一个简单的数据GET操作，轻松可以达到十万级生成效率。
缺点：生成的短链接是自增的，用户方可以猜测到业务的交易流水量，流水量对于很多互联网公司是机密敏感数据，会带来不安全性。可以考虑通过接口字段让用户自定义选择短链生成方式，同时短链服务本身也得做好功能可扩展性的设计。

4.7.2 查询优化

一般的短链系统，基本都是读多写少，对于高频操作(读)，如果每次都从数据库取，开销较大，通常采用缓存技术来解决。

4.8 服务高可用设计

短链接服务是一个高并发项目，需保证高性能的同时，也要保证服务不间断。
总体思路： Keepalive + Nginx + 多节点容器化部署 + Redis Sentinel + Mysql半同步

4.8.1 负载均衡器选择

4.8.1.1 DNS轮询

优点

1. 低成本：只需要在DNS服务器上把域名绑定多个A记录即可。域名注册商一般都免费提供此类解析服务。
2. 部署简单：部署多个web应用实例，然后在DNS服务器上添加A记录。

缺点

1. 可靠性低：业务机器出现问题，没有故障转移机制
2. 负载分配问题：缓存绑定，负载不均衡

4.8.1.2 硬件负载

优点

1. 高性能：硬件负载均衡器可以处理大量的网络请求，具有很高的性能，可以满足高流量负载的需求。
2. 高可靠性：硬件负载均衡器通常具有冗余的硬件和软件，可以提供高可靠性，防止单点故障导致整个系统崩溃。
3. 高扩展性：硬件负载均衡器可以轻松地扩展和升级，以应对增加的网络负载。
4. 安全性：硬件负载均衡器通常具有内置的安全特性，如DDoS攻击防御、SSL加速和安全连接等，可以保护网络安全。

缺点

1. 成本高：硬件负载均衡器通常价格昂贵，需要更多的预算。
2. 管理复杂：硬件负载均衡器的安装、配置和管理需要技术人员进行，需要较高的技术水平和时间投入。
3. 灵活性差：硬件负载均衡器通常需要进行预配置，而且不太灵活，无法快速适应变化的网络环境。

4.8.1.3 LVS

LVS是Linux Virtual Server的缩写，是一个基于Linux内核的负载均衡器软件，旨在为高性能、高可用性和可扩展性的应用程序提供负载均衡和高可用性服务。
优点

1. LVS是一个内核级别的负载均衡器，运行时不存在用户态、内核态上下文切换的消耗，因此具有很高的性能和吞吐量。
2. LVS支持多种负载均衡算法和协议，可以根据实际需求进行配置。
3. LVS具有较好的可靠性和可扩展性，可以通过增加后端服务器来增加负载容量。

缺点：

1. LVS的安装和配置比较复杂，使用门槛较高，需要有一定的Linux系统和网络知识。
2. LVS的管理和维护成本比较高，需要专门的管理人员来进行操作和维护。

• LVS的负载均衡器只能工作在内核空间中，不支持灵活的配置。

4.8.1.4 NGINX

优点

1. 灵活性：Nginx支持多种负载均衡策略，可以根据请求的源IP地址、目标IP地址、源端口号、目标端口号等信息来判断请求的目标服务器，并将请求转发到合适的服务器上。
2. 易于配置：Nginx的配置文件简单易懂，可以快速配置和部署，同时支持热部署，可以在不停止服务的情况下更新配置文件。
3. 支持缓存。

4.8.1.5 总结

短链接服务预期QPS不会过万，Nginx作为负载均衡已经足够了

4.8.2 负载均衡器高可用

Nginx作为负载均衡器，挂掉则服务整体不可用。这里选择用KeepAlive软件做Nginx高可用

基本原理：通过建立主备两台服务器，保证一台服务挂了后另外一台还能提供服务。

4.8.2.1 宕机检测

主节点和从节点维护心跳，从节点通过心跳检测主节点挂机，主节点挂机后，从节点升级为主节点

4.8.2.2 故障转移

从节点升级为主节点后，如何将用户访问转到新的主节点呢。用户访问的是短链接域名，通过DNS协议映射到负载均衡器节点。这里主备服务器会通过虚拟网卡技术生成同样的虚拟IP，DNS映射为该虚拟IP，那么理论上在IP协议层ARP协议会同时广播到这两台机器，但KeepAlive软件会只让主节点回复ARP包。这样当原主节点挂机后，用户访问的就是新的主节点。

4.8.3 Redis高可用

为避免单机Redis挂机导致缓存雪崩等问题，需建立Redis集群机制，常见的解决方案是搭建Redis Sentinel集群来做节点宕机检测及故障转移。这里注意不同的哨兵最好部署在不同的机房，进行隔离，以免没有足够的哨兵存活（<quorun），无法进行故障转移。

4.8.4 数据库高可用

常见的方案为建立主从集群，但注意数据库默认的复制为异步复制。主节点磁盘损坏，从节点未来得及复制时，数据会出现丢失。
可采取数据同步复制方案，主节点将数据同步到从节点，从节点返回数据重放成功后，主节点才返回用户成功。数据在主或从数据丢失后，用户是能实时感知的，可以通过选择重试来保证数据的可靠性。
在企业级生产中，一般会采取同步加异步复制相结合的方案，简称半同步复制。主节点和同步复制的从节点会部署在同一地点的不同机房，异步复制的从节点部署在另外的机房，这样可以避免极低概率下同一地点的数据中心出现着火、网络中断等数据中断异常。