设计一个短链接系统

前言

在发送短信和微博等限定字数的场景下，短链接的需求就应运而生了。

原理

一张图概括了短链接干的事：

来源：孤独的烟

短链接设计关键在于：

短链接生成的算法：如何保证足够短且不冲突。

其中常用的算法有

• 1、基于哈希的MurmurHash 算法
• 2、十进制转62进制
• 3、自增序列（Snowflake、Mysql 自增主键、类 uuid、redis）

关于短链接的原理研究可以阅读这两位大佬的文章：

xbmchina.cn/AAAAAG

xbmchina.cn/AAAAAH

实践

基于上面的理论思想：

本文采用十进制转62进制的算法+Redis全局自增的方式实现短链接服务。

公众号：爱编码

1、十进制转62进制

短链接是由 a-z、A-Z 和 0-9 共 62 个字符。

我们可以讲十进制的数字id，转换为一个62进制的数，例如20201122就可以转换为WvOi。

十进制转62进制工具类如下：

public class Base62 {
    private static final char[] toBase62 = {'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',
            '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'};

    private static final int[] fromBase62 = new int[128];
    private static final int RADIX = 62;

    static {
        Arrays.fill(fromBase62, -1);
        for (int i = 0; i < toBase62.length; i++) {
            fromBase62[toBase62[i]] = i;
        }
    }

    private Base62() {

    }


    public static String encode(Long l) {
        StringBuilder stringBuilder = new StringBuilder();
        while (l > 0) {
            stringBuilder.append(toBase62[(int) (l % RADIX)]);
            l /= RADIX;
        }
        return stringBuilder.reverse().toString();
    }

    public static long decode(String s) {

        long l = 0L;
        long d = 1L;
        for (int i = s.length() - 1; i >= 0; i--) {
            l = l + d * fromBase62[s.charAt(i)];
            d *= RADIX;
        }
        return l;
    }


    /**
     * 根据自增id，生成短链接。
     *
     * @param id
     * @return
     */
    public static String generateLink(Long id, int size) {
        if (size < 4) {
            size = 4;
        }
        long maxId = (long) Math.pow(62, size);
        String encode = Base62.encode(id % maxId);
        if (encode.length() < size) {
            String minLink = "";
            for (int i = 0; i < size; i++) {
                minLink += "A";
            }
            return minLink.substring(0, size - encode.length()) + encode;
        }
        return encode;
    }

    public static void main(String[] args) {
        //生成4位长短链接
        String s = generateLink(20201122L, 4);
        System.out.println(s);
    }
}

2、Redis全局id自增

因为生成的短链接与自增id有非常密切的关系，redis的自增对于后面的分库分表有好处。只要搭建个redis集群，保证redis不挂基本上是没有问题。

代码如下：

  /**
     * redis生成全局自增ID
     */
    public long generateId(String key, int increment) {
        try {
            RedisAtomicLong counter = new RedisAtomicLong(key, redisUtil.getRedisTemplate().getConnectionFactory());
            return counter.addAndGet(increment);
        } catch (Exception e) {
            e.printStackTrace();
        }
        return System.currentTimeMillis() + new Random(1000000).nextInt(1000000) + 1;
    }

3、分库分表

本文采用sharding-jdbc分库分表足以满足我的需求。

如果你对不是很懂，那就可以看一下官网中文使用教程：xbmchina.cn/AAAAAJ

表结构：short_url_xxx

CREATE TABLE `short_url_` (
  `id` bigint NOT NULL COMMENT '编号',
  `username` varchar(128) CHARACTER SET utf8 COLLATE utf8_bin DEFAULT NULL COMMENT '用户名',
  `url` varchar(512) CHARACTER SET utf8 COLLATE utf8_bin DEFAULT NULL COMMENT '长链接',
  `short_url` varchar(16) CHARACTER SET utf8 COLLATE utf8_bin DEFAULT NULL COMMENT '短链接',
  `client_count` int DEFAULT NULL COMMENT '点击次数',
  `create_time` datetime DEFAULT NULL COMMENT '创建时间',
  `last_click_time` datetime DEFAULT NULL COMMENT '最新的点击时间',
  PRIMARY KEY (`id`) USING BTREE,
  KEY `short_url` (`short_url`) USING BTREE
) ENGINE=InnoDB DEFAULT CHARSET=utf8 ROW_FORMAT=DYNAMIC;

以short_url_为模板创建a-z、A-Z 和 0-9 共 62 张表，存放短链接尾号一样的数据。注意字段short_url为utf8_bin编码区分大小写。

下面以2个库为例如何实现让数据均匀落到不同数据库对应尾号的表。

配置sharding-jdbc分库分表：

@Configuration
public class DataSourceConfig {

    @Autowired
    DbProperties dbProperties;

    @Bean
    public DataSource buildDataSource() throws SQLException {

        // 配置真实数据源
        Map, DataSource> dataSourceMap = new HashMap<>();
        List> dsList = dbProperties.getDsList();
        for (int i = 0; i < dsList.size(); i++) {
            DsEntity dsEntity = dsList.get(i);
            DruidDataSource dataSource1 = new DruidDataSource();
            dataSource1.setDriverClassName(dsEntity.getDriverClassName());
            dataSource1.setUrl(dsEntity.getUrl());
            dataSource1.setUsername(dsEntity.getUsername());
            dataSource1.setPassword(dsEntity.getPassword());
            dataSourceMap.put("ds" + i, dataSource1);
        }


        // 配置short_url表规则
        TableRuleConfiguration shortUrlTableRuleConfig = new TableRuleConfiguration("short_url", "ds${0..1}.short_url_${[" +
                "'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'," +
                "'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']}");
        // 配置分库 + 分表策略
        shortUrlTableRuleConfig.setDatabaseShardingStrategyConfig(new InlineShardingStrategyConfiguration("id", "ds${id % 2}"));
        shortUrlTableRuleConfig.setTableShardingStrategyConfig(new StandardShardingStrategyConfiguration("short_url", new MyPreciseShardingAlgorithm()));

        // 配置min_short_url表规则
        TableRuleConfiguration minShortUrlTableRuleConfig = new TableRuleConfiguration("min_short_url", "ds${0..1}.min_short_url_${[" +
                "'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'," +
                "'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']}");

        // 配置分库 + 分表策略
        minShortUrlTableRuleConfig.setDatabaseShardingStrategyConfig(new InlineShardingStrategyConfiguration("id", "ds${id % 2}"));
        minShortUrlTableRuleConfig.setTableShardingStrategyConfig(new StandardShardingStrategyConfiguration("short_url", new MyPreciseShardingAlgorithm()));

        // 配置分片规则
        ShardingRuleConfiguration shardingRuleConfig = new ShardingRuleConfiguration();
        shardingRuleConfig.getTableRuleConfigs().add(shortUrlTableRuleConfig);
        shardingRuleConfig.getTableRuleConfigs().add(minShortUrlTableRuleConfig);
        // 获取数据源对象
        DataSource dataSource = ShardingDataSourceFactory.createDataSource(dataSourceMap, shardingRuleConfig, new Properties());

        return dataSource;
    }
}

尾号分表策略：

@Slf4j
public class MyPreciseShardingAlgorithm implements PreciseShardingAlgorithm> {

    /**
     * 根据短链接最后一位进行定位表名
     *
     * @param collection           表名
     * @param preciseShardingValue 列值
     * @return
     */
    @Override
    public String doSharding(Collection> collection, PreciseShardingValue> preciseShardingValue) {
        String value = preciseShardingValue.getValue();
        String flag = value.substring(value.length() - 1);
        for (String name : collection) {
            if (name.endsWith(flag)) {
                log.info("return name:" + name);
                return name;
            }
        }
        return null;
    }
}

总结

以上实现已上传到GitHub：xbmchina.cn/AAAAAI

如果对你有用或者启发的，麻烦点个赞呗。