一种流行的短地址生成方案的原理、Bug及扩展

2021 Mar 23 See all posts


最近接手了一个新任务——扩展目前的短地址服务，目前的短地址长度是8位的，如 https://some_short_domain/h1fSpPka 。业务方嫌这个地址太长——往往就因为这个短地址太长，营销短信被拆成两条了成本翻倍， 换更短的垃圾短域名又要花钱换不起，只能往短地址码榨点油水，本着灵活的原则，答应了业务方，也别改成6位了，1-8位爱用几位用几位，都支持。

原理

仔细看了一下目前正在运行的短地址方案，发现前人设计得相当简洁实用：

    public static List<String> encode(String longUrl, Charset charset) throws NoSuchAlgorithmException {
        String md5 = buildMD5(longUrl, charset);
        return buildShortCode(md5);
    }
    
    private static List<String> buildShortCode(String md5) {
        Objects.requireNonNull(md5, "md5 must not be null.");

        List<String> codes = new LinkedList<>();
        //将32个字符的md5码分成4段处理，每段8个字符
        for (int i = 0; i < 4; i++) {
            int offset = i * 8;
            String sub = md5.substring(offset, offset + 8);
            long sub16 = Long.parseLong(sub, 16); //将sub当作一个16进制的数，转成long
//             & 0X3FFFFFFF，去掉最前面的2位，只留下30位
//            sub16 &= 0X3FFFFFFF;
            StringBuilder sb = new StringBuilder();
            //32位分8段处理，每段4位
            for (int j = 0; j < 8; j++) {
                //得到一个 <= 61的数字
                long t = sub16 & 0x0000003D;
                sb.append(chars[(int) t]);
                sub16 >>= 4;  //将sub16右移4位
            }
            codes.add(sb.toString());
        }
        return codes;

Bug

1. 短地址生成算法的bug

如果仔细观察上面的代码，就会发现一个错误，long t = sub16 & 0x0000003D 这样确实能得到一个<=62的数，但是这样做就是对的吗？

显然不是，正确的做法应该是 long t = sub16 % 62， 0x3D=0b00111101 和它 & 会丢掉很多字符，其中为0的bit位都会永远位0，如果字符表是：

public static String[] chars = {"a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z", "0", "1", "2", "3", "4", "5", "6", "7", "8", "9", "A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z" }

它会这样造成如cdghklopstwx014589CDGHKLOPSTWX永远不出现，62位的字符表瞬间缩水一半，再来个8次方，值域空间只达到了设计的\((1/2)^8=0.0039\)，不到1%，悲剧，大大增加了碰撞概率。 为什么会犯这样的错误？我觉得可能是太想当然了，虽然&比%快得多，但是只有当\(m = 2^n-1\) 时，& m 才等价于 % m。 62位的字符表再加个1字符如-就没有bug了。

2. 可用性bug

上面为每个长地址生成了4个短地址，如果没有被占用当然皆大欢喜，如果都被占用了怎么办？原来的代码是直接返回null罢工，这肯定是业务方无法接受的。

解决方式也很简单，如果4个候选短地址都被占用了，就为长地址加一点随机字符串如当前时间戳（当然最后数据库保存长短地址映射关系的时候还是原始的长地址），然后再算一次，多算几次肯定没有问题，毕竟短地址的值域空间大小是 \(62^8=218340105584896\)。

扩展

1. 短地址位数扩展

没有什么好说的，直接上代码，length长度必须[1, 8]在最外面就校验了，略去不表：

    private static List<String> buildShortCode(String md5, Integer length) {
        Objects.requireNonNull(md5, "md5 must not be null.");
        List<String> codes = new LinkedList<>();
        for (int i = 0; i < 4; i++) {
            int offset = i * 8;
            String sub = md5.substring(offset, offset + 8);
            long sub16 = Long.parseLong(sub, 16); //将sub当作一个16进制的数，转成long
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < length; j++) {
                long t = sub16 % 62;
                sb.append(chars[(int) t]);
                sub16 >>= 32 / length;  
            }
            codes.add(sb.toString());
        }
        return codes;
    }

2. 分布式扩展

(1). 目前是单表，如果营销活动暴增，一年内生成的短地址轻松上亿，MySQL单表可能有点坑了，分表吧。

方案如下，按照短地址码第一个字符分62张表，如SHORT_URL_REF_0 ~ SHORT_URL_REF_61，62亿个短地址很长时间都够用了；如果到时候再不够，再裂变一下，按照前两个字符分，62 * 62 = 3600亿短地址，全地球人都可以用到天荒地老，而且逻辑简单，可以平滑升级。

分表代码：

  @NotNull
  @Override
  protected String calculateTableName(@NotNull String template, @NotNull ShortUrlRef document) {
      Assertions.notNull(document);
      String shortUrl = document.getShortUrl();
      Assertions.notNull(shortUrl);
      char c = shortUrl.charAt(0);
      int index = 0;
      if (c >= '0' && c <= '9') {
          index = c - '0';
      } else if (c >= 'a' && c <= 'z') {
          index = c - 'a' + 10;
      } else if (c >= 'A' && c <= 'Z') {
          index = c - 'A' + 36;
      }
      return StringUtils.formatMessage(template, index);
  }

(2). 唯一性检查

之前判断短地址码的有没有被占用是通过unique key来保证的，现在分表了，那就通过分布式 bloom filter来搞吧，bm算法占用内存小效率又高——最后选取的是redis内置的bloom filter，不再赘述。

总结

短地址服务功能相对独立，对上下游的依赖少，开发也好，后期扩展也好都相对容易，是系统设计中一个非常经典的设计场景，即便如此，也不要太掉以轻心，精益求精才能不断进步。

Back to top