31 TinyUrl生成系统的设计 - xiaoxin01/Blog GitHub Wiki

本文介绍如何将冗长的Url地址，转换为精简Url地址的系统设计思路

思路

对于一个冗长的Url，可以用一个简短的字符串来做 key, value 的映射关系，在用户间传递的是 key，从而达到效果。

key 的长度多少合适？

要回答这个问题，其实考虑的是，如何设计 key，来避免不同 Url key的重复？

答案是长度和字符集

长度越长，字符集越多，key重复的概率越低。

当然，长度太长，精简Url的初衷就无法实现了，所以需要权衡长度与重复概率。

字符集

Url不会被编码的字符集，除了 ANSC 的字母和数字之外，还有一些符号，可以参考下面的地址查看：

URL字符编码解码

这里先以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 生成示例代码

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长度限制