1. 背景介绍

        所谓的短域名服务，就是处理我们平常经常收到的那种带有短链的短信中的短链的。它具有四个基本的功能：a. 用户点击短域名，服务端接收到请求之后，将其重定向到对应的长域名中；b. 其他的服务通过RPC请求，传一个短域名code，服务端将对应的长域名信息返回；c. 调用方传一个长域名过来，将其转换为短域名，并且返回；d. 记录每个短域名每个小时的点击量数据，并且提供查询接口；

2. 设计思路

2.1 思考思路

        首先，短域名服务需要实现的两个基本的功能分别是：a. 接收一个长域名信息，返回一个标记短域名的code；b. 如果调用方是其他服务，那么其传过来一个短域名code，就需要将相应的长域名信息返回给调用方；c. 客户端直接调用，请求参数就是一个短域名，而服务器则需要将短域名转换为长域名，然后通过一定的方式将客户端页面重定向到长域名。其实这个题目需要做的就是存储长域名和短域名的映射关系，而最简单的映射关系就是“id->url”的这种映射关系，而且id也是唯一的，也就保证了这种映射关系的唯一性。使用id作为映射我们有如下几个点需要注意：

• 调用方肯定不能直接传一个id过来，因为我们的调用方有一部分直接是用户，可能有人通过id自增的特性，恶意刷我们的接口。这里我们可以对id进行编码，因为url中只直接支持a-zA-Z0-9这总共62个字符，其他的字符则需要编码，我们可以将id通过base62的方式进行编码，从而得到一个字符串，而且base62编码有一个好处就是，十进制的1亿，编码之后也只有5个字符，因而base62编码能够支持大量的短码，而不用过于担心短码不够的问题；

• 如果直接采用按顺序a-zA-Z0-9的base62编码，可能用户根据这个顺序顺推，而恶意刷我们的短码，造成我们的服务器宕机，因而这里我们在使用base62的时候，需要对原始字符进行乱序，然后依据这个乱序来编码和解码操作；

• 在使用短码查询对应的长域名的时候，我们一般是将数据存储在数据库和redis中，一般的，为了提升效率，查询的时候都会到redis中查询，然后再到数据库查，然后持久化到redis中，当然一般的也都直接能从redis中读取到。但是这里存在一个问题是，如果用户恶意的刷一些无效的短码请求，这些请求都会先去redis中查，redis中没有，然后会去数据库查，从而导致整个服务宕机。这个问题我们有一个解决方案就是，对短码计算一个checksum，比如很简单的，将最后一个字符作为存储checksum的字符，然后将前面几个字符的整型值相加，而最后一个字符用base62编码有62个值，因而前面几个字符的加和然后对62取余，然后经过base62编码的值作为checksum。这样每次接收到查询请求的时候，将code计算一下checksum，判断其与最后一个字符是否相同，不相同的就可以过滤掉了。如下是这种思路下短码的编码方式：

  |--------id base62编码--------|---校验和---|
           a s d x K 9 1              M
  

• 这里还存在一个问题是，如果后台服务器需要对短码进行不兼容的升级，比如这次可以支持8个字符，下个版本可以支持10个字符，这样我们可以做一些优化，或者支持一些新的功能，那么我们就需要对短码加版本号，这里存在一个问题是，这个版本号是直接编码到短码中还是根据短码与长域名的映射关系而存储在表征这个映射关系model的某个字段中。如果只是简单的存储在映射关系的model中，有可能新版本与旧版本生成的短码结果是一样的，此时我们就不知道这个短码是什么版本的了。因而我们将版本号存储在生成的短码中。如下是改进后的短码的编码方式：

  |--------id base62编码--------|---版本---|---校验和---|
           a s d x K 9              1           M
  

• 生成短码还有一个特点是，需要能够生成尽量多的短码，上述改进后的生成方式，我们相当于有两个固定字符分别作为版本和校验和，也就是只剩下6个字符给我们用于标记“id”与“长链接”的映射关系了，虽然也不少，但我们可以更优化一些。我们注意到，版本是很少发生变化的，而校验和是通过对某个数字取余计算得到的，这个数字我们可以缩小一些，也就是说我们可以将版本和校验和压缩到一个字符中。base62表示的62个状态，转成二进制之后有6位，因而我们可以随意使用的只有5位（当然，我们可以更优一点，就是使用6位，只要对应的十进制值不是63和64即可），我们可以将这5位的前两位用于表示版本号，后三位用于存储校验和，也就是说目前，我们最多支持4个版本，而计算得到的校验和是0~7中的某个值，然后将这整个值经过base62编码之后，就得到了短码的最后一个字符。这种处理方式相对于前一个也有一个好处是，对于同一个版本的短码，其每个字符都是不一样的，而前一种编码方式，倒数第二个字符始终是同一个字符，比如版本1。如下是这种短码的编码方式：

  |--------id base62编码--------|---校验和+版本---|            |--版本--|--校验和--|
           a s d x K 9 1               M                        0 1     1 0 1
  

• 这里我们还需要讨论的一个问题是，用于进行base62编码的id应该如何生成。生成唯一的id很简单，但是如何高效率的生成id则需要做额外的处理。这里我们有如下几种方案：

  • 通过数据库的自增id来生成一个唯一的id，这种方式主要有两个缺点：a. 每次操作都要连接数据库；b. 每次请求需要竞争自增id的锁；这两个问题都会直接影响生成id的效率，从而造成系统整体性能的下降，而且这种方式严重依赖了数据库的TPS；
  • 鉴于数据库的自增id方式，我们可以换一种方案生成id，我们注意到，只要生成的id是唯一的即可，而不需要其是自增的，因而我们可以在数据库中使用一条数据存储当前已经申请的id的最大值base，以及申请的批次大小size，每次申请的时候只需要将base更新为”base+size“即可，然后将获取的一堆id存储在内存中，不够时再来申请即可，这种方式可以极大的提升服务性能，而且一般的生成短码的QPS也不会特别高，因而我们可以再进一步做一些优化，即每个服务可以缓存多个批次的数据，然后随机在某个批次中获取id，每个批次的id使用量达到80%的时候可以异步的到数据库中加载下一个批次的数据，从而保证请求几乎都是在内存中处理完成；
  • 除了数据库，我们还可以使用redis作为生成id的组件，比如redis的incr函数，每次都可以自增得到一个id。当然，存在的问题就是，每次请求都需要到redis中竞争读取id，并且还有网络的开销；
  • 结合第二种方式，我们也可以对redis自增id进行优化，比如通过pipeline一次批量获取一批id，这样可以减少网络开销，然后缓存这些id。另外，我们也可以不用redis的自增id，而是在redis中存储当前已经使用的id的最大值base，然后每个批次获取的时候只需要将base更新为”base+size“即可。当然，需要注意的问题是，redis不像数据库支持SQL，因而在更新的时候，需要额外加一个redis锁；
  • 理论上，上述几个方案已经够用了，而且性能也非常好，但是我们还可以更优化一些，因为我们注意到一点是，这里生成的id只要是唯一的即可，因而我们可以借鉴雪花算法来实现，这样我们就可以始终在内存中生成，而无需加任何的锁或者中间件，效率将会更高。但是这里题目要求短码长度最多为8个字符，而我们有一个字符需要固定作为版本号和校验和，因而我们能自由使用的字符数是7个字符，7个字符能表示的最大长整型数字是3521614606207，转成二进制有42位，因而我们能自由使用的只有41位。笔者在本地做了实验，41位确实太少了，因为我们不仅需要记录当前的时间（无论是以小时的差值为基准还是以毫秒数的差值作为基准）、服务器实例id、服务内部的自增序列号。因而我们假设线上服务只有一个实例，位数也还是不够的，如果这里能够增加字符数上限的限制，比如可以使用10个字符，那么就可以采用雪花算法来实现。

2.2 思路总结

        结合上述的讨论，我们采用的实现方案主要有如下几个部分：

• 接收长链接请求，然后通过redis一次生成一个批次的id数据，redis中存储数据的格式主要是记录了一个base字段，该值是下一个批次可以使用的id的起始值，每次申请时，只需要将base更新为”base+size“即可。然后在服务内部会使用多个片段，每个片段会存储一个或多个批次的id数据，每次在申请id的时候，会随机到某个片段中去申请，这样可以减小内存中锁的竞争（因为更新记录批次数据的model时，必然需要将这个批次给锁住）；
• 使用随机顺序的a-zA-Z0-9数组对生成的id进行编码，生成一个最长7位的字符串；
• 对上面的七位字符串计算校验和，这里采用的方案是对8取余（计算的时候更优化的方式是只需要与二进制的0b111进行&操作即可），然后将取余后的结果加上当前版本号（第一个版本值为0），将其结果经过base62编码之后，作为最后一个字符，放到生成的短码最后一位；
• 异步存储生成的短码与长链接的映射关系，即可返回；