TinyUrl生成系统的设计

2019-03-14

.NET Core

> 本文介绍如何将冗长的Url地址，转换为精简Url地址的系统设计思路

## 思路

对于一个冗长的Url，可以用一个简短的字符串来做 key, value 的映射关系，在用户间传递的是 key，从而达到效果。

## key 的长度多少合适？

要回答这个问题，其实考虑的是，如何设计 key，来避免不同 Url key的重复？

答案是 长度 和 字符集

长度越长，字符集越多，key重复的概率越低。

当然，长度太长，精简Url的初衷就无法实现了，所以需要权衡长度与重复概率。

### 字符集

Url不会被编码的字符集，除了 ANSC 的字母和数字之外，还有一些符号，可以参考下面的地址查看：

[URL字符编码解码](https://www.qqxiuzi.cn/bianma/URL%E5%AD%97%E7%AC%A6%E7%BC%96%E7%A0%81%E8%A7%A3%E7%A0%81.htm)

这里先以26个小写字母、26个大写字母和10个数字，总共62个字符举例。

    abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890

### unique key 的数量

可以通过排列组合，计算出Unique Key的数量：

    数量 = 字符集 ^ 字符长度

| 字符长度 | 数量集（约） |
| -------- | ------------ |
| 5        | 10^9         |
| 6        | 57 * 10^9    |
| 7        | 3.5 * 10^12  |

### 重复概率

我们以字符长度为5举例

* 当已经生成的 unique key 集合为 0 时，再生成 unique key 重复概率为 0
* 当已经生成的 unique key 集合为 1000 时，再生成 unique key 重复概率为 10^-6
* 当已经生成的 unique key 集合为 10^6 时，再生成 unique key 重复概率为 10^-3

由此可以看到，字符集的长度多少，并不能一概而论，而是需要结合实际的业务需求来看。

* 如果使用量不大，不超过 10^6，则长度为5就够用。
* 如果使用量较大但又希望长度较短，则可以选择扩充可用字符集（比如加入符号等）
* 如果使用量很大，则根据实际情况选择合适的长度
* 如果初期使用量不大，但成长很快，甚至可以使用可变长度，利用重复概率作为触发因子。

## 一些思考

### 数据库的选择

这种需求非常适合使用那些基于 key, value 的数据库，这样的检索时间复杂度为 O(1)，不会随着数据量的增加而降低效率。

### 重复的 Url 被提交怎么办？

如果只有一张表，则仅能从 unique key 查出 Url，但无法知道 Url 是否已经有对应的 unique key。

此时需要一张重复检查表，将 Url 作为 key，将 unique key 作为 value

### Url转换，每次都要查询数据库吗？

试想一下这样一个场景，你准备了一个抢购的精简地址，告诉用户今天晚上八点准时抢购，数量有限仅有100台。晚上8点左右，百万用户大军前来抢购，精简地址无法正常跳转了……

可以设计一个缓存功能，以时间为单位，缓存最近1天访问到的精简地址，或者以数量为单位，缓存最近1000条精简地址，当大批量用户同时访问同一个精简地址时，直接从缓存读取数据而无需查询数据库，从而大大提高了效率。

## Unique Id 生成示例代码

```c#
var uniqueIdSets = new System.Collections.Generic.HashSet<string>();
var uniqueId = string.Empty;
var idLength = 5;
var existIdCount = 0;
var maxIdCount = 10 * 1000 * 1000;
var stepCount = maxIdCount / 100;
var idChars = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890".ToCharArray();
Console.WriteLine($"## length of id chars: {idChars.Length}, length of unique id: {idLength} ##");

var randomSeeds = new byte[idLength];
var crypto = new System.Security.Cryptography.RNGCryptoServiceProvider();
var result = new System.Text.StringBuilder(idLength);
var timeWatch = new System.Diagnostics.Stopwatch();
timeWatch.Start();

while (true)
{
    result.Clear();
    crypto.GetNonZeroBytes(randomSeeds);
    foreach (byte b in randomSeeds)
    {
        result.Append(idChars[b % idChars.Length]);
    }
    uniqueId = result.ToString();

    if (uniqueIdSets.Contains(uniqueId))
    {
        existIdCount++;
        //Console.WriteLine($"Exits, {uniqueId}, {uniqueIdSets.Count}, exist count: {++existIdCount}");
    }
    else
    {
        uniqueIdSets.Add(uniqueId);
    }

    if (uniqueIdSets.Count > maxIdCount)
    {
        break;
    }

    if (uniqueIdSets.Count % stepCount == 0)
    {
        Console.WriteLine($"id count: {uniqueIdSets.Count}, exist count: {existIdCount}, time: {timeWatch.ElapsedMilliseconds}ms");
        timeWatch.Restart();
    }
}
```

## 参考

* [Url长度限制](https://www.cnblogs.com/cuihongyu3503319/p/5892257.html)

本文为博主原创，如需转载，请注明出处：http://www.supperxin.com

返回博客列表