生成简短、唯一的标识符

Question

我正在寻找一种算法，该算法可以生成适用于两者的标识符，例如外部使用。 URLs 以及具有以下要求的持久性：

短，像一个最大值。共 8 个字符
URL-友好，所以没有特殊字符
人性化，例如没有歧义字符，如 L/l、0/O
增量用于快速索引
随机防止在不知道算法的情况下猜测（会很好，但不重要）
唯一无需检查数据库

我查看了各种解决方案，但我发现的所有解决方案都有一些主要的权衡。例如：

GUID：太长，不是增量的
GUID base64 编码：仍然太长，不是增量的
GUID ascii85 编码：短，不增量，不合适的字符太多
GUID 编码，如 base32、base36：短，但信息丢失
Comb GUID：太长，但是增量
所有其他基于随机：需要检查数据库的唯一性
基于时间：在集群或多线程环境中容易发生冲突

编辑：为什么这被标记为题外话？这些要求描述了一个特定的问题，可以提供许多合法的解决方案。事实上，这里的一些解决方案非常好，我正在努力选择一个标记为答案。

Answer 1

下面使用已知唯一的 ID（因为它来自关系数据库中的唯一 ID 列）和随机的字母和数字序列的组合来生成令牌：

public static string GenerateAccessToken(string uniqueId) // generates a unique, random, and alphanumeric token
{
    const string availableChars = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
    using (var generator = new RNGCryptoServiceProvider())
    {
        var bytes = new byte[16];
        generator.GetBytes(bytes);
        var chars = bytes.Select(b => availableChars[b % availableChars.Length]);
        var token = new string(chars.ToArray());
        return uniqueId + token;
    }
}

令牌保证是唯一且随机的（或至少 "pseudo random"）。您可以通过更改 bytes.

的长度来操纵长度

为避免混淆“0”和"O"或"l"和“1”，您可以从availableChars.

中删除这些字符

编辑

我刚刚意识到这并没有完全满足 "no database check" 要求，尽管当我使用这样的代码时，我一直在内存中拥有一个我知道包含唯一 ID 的实体，所以我希望这同样适用于你的情况。我认为不可能完全达到你所有的要求，所以我希望这仍然是一个很好的属性平衡。

Answer 2

如果可能的话，我会将用户需求（简短、可读）和数据库需求（增量、快速索引）分开。面向用户的需求发生变化。您不希望因为明天您决定更改面向用户的 ID 的长度或其他细节而不得不修改您的 table。

一种方法是使用用户友好的字符生成您的 ID，例如
23456789ABCDEFGHJKLMNPQRSTUVWXYZ 让它随机。

但是当插入数据库时，不要将该值作为它引用的记录的主键，甚至不要将它存储在 table 中。使用身份主键将其插入到自己的 table 中，然后将 int 或 bigint 键与您的记录一起存储。

这样你的主 table 可以有一个增量主键。如果您需要通过其 "friendly" ID 引用记录，那么您可以加入您的友好 ID table。

我的猜测是，如果您生成的这些 ID 数量足够多，您担心索引性能，那么人类用户检索这些值的速度将会低得多。所以在友好 ID table 中查找随机值稍微慢一点不会有问题。

Answer 3

你试过proquints了吗？

Proquint 是一个 PRO-nouncable QUINT-uplet，由交替的明确辅音和元音组成，例如："lusab"。

我觉得他们几乎可以满足你的所有要求。

查看提案 here。 here 是 C 中的官方实现，Java.

我已经开发了 .NET 端口，您可以下载为 Proquint.NET。

Answer 4

我之前实施的一个简单解决方案并未满足您的所有限制，但如果您对问题的看法略有不同，则可能是可以接受的。

首先，我使用了一个函数来混淆数据库 ID func(id) => y 和 func(y) => id。（我使用 Feistel cipher, and here 是实现此类功能的示例）其次，将混淆后的 ID 转换为 base 62，使其变得简短且 url 友好。（您可以使用较小的字符集来实现 Human-friendly）这将创建一个从数据库 ID 到字符串标识符的一对一映射。在我的实现中，1、2 对应地映射到 2PawdM、5eeGE8，我可以从字符串 2PawdM 和 5eeGE8 中取回数据库 ID 1、2。当您使用不同的混淆函数时，映射可能会完全不同。

使用此解决方案，标识符本身 不是递增的 ，但是，因为标识符直接映射到数据库 ID，您可以计算相应的数据库 ID 并直接执行任何数据库查询而不是在 id 列上。您不需要生成字符串标识符并将其存储到数据库中，当您存储带有自增id列的记录时，唯一性由数据库本身保证。

生成简短、唯一的标识符

Generate short, unique identifiers

.net

c#

guid

identifier

uniqueidentifier