logo标签列表

创建唯一的、不可猜测的基于36进制的ID

phpmysqlprimary-keyuniquebase36
4
对于类似于URL缩短服务的应用程序，我想创建不可猜测的ID，我想你们都很熟悉。以下是这样一个ID的示例：http://example.com/sd23t9。有什么好的、高效的技术可以生成这些ID，并在将它们作为主键插入数据库表时减少（或不产生）冲突风险？编辑：Piskvor当然提出了一个很好的观点。我应该提到，在达到36^6限制之前，冲突风险最小。编辑2：嗯，算了吧，他的观点当然比那更有启发性。预先生成一个带有ID的表，也许是最有效的技术（就像我已经在其他地方读到的那样）？如果我受到36^6和非连续约束的限制，这是否是最有效的技术？
6
假如你的ID是[a-z0-9]{6}，根据你提供的例子，总会存在碰撞风险。当你有2,176,782,336个ID时，就会出现100%的碰撞（没有更多可用的密钥）。由于生日悖论，你会很快遭遇碰撞：http://en.wikipedia.org/wiki/Birthday_effect#Cast_as_a_collision_problem 。在这样一个小的密钥空间中，没有办法避免碰撞 - 相反，你需要采用某种碰撞恢复方案（例如，在不重复的情况下生成ID - 随着密钥空间被填满，这将变得越来越慢）。 - Piskvor left the building
1
总会有冲突的风险，但如果出现约束违规，您可以生成一个新的。 - Mrki
1
如果你预计要生成大量的ID，可以从较少的数字开始，并在持续出现太多冲突时逐渐增加长度。这样，即使你预计会有大量的ID，你也可以从更短的长度开始。 - Mrki
@Mrki：英雄所见略同 :) 随着较短的密钥空间填满，它仍将需要越来越多的时间，但应在几次迭代中终止（尽管它可能会非常理论地生成长ID）。 - Piskvor left the building
@fireeyedboy: 生成随机ID的方法并不重要 - 碰撞的概率来自您已经拥有的ID数量。您可以按顺序生成它们，但这是1）完全非随机的，因此2）完全可猜测，更不用说3）作为URL缩短器毫无用处（“ / aaaqaaa还是/ aaaaqaa？”） - Piskvor left the building
显示剩余2条评论
6个回答
5
Set ID length. // e.g. 6
do {
  Generate a short random ID of the given length
  Collision?
   - No:
      DONE!
   - Yes:
      increase ID length
 } while true

对于任何有限ID长度，总存在碰撞的风险：假设你有[a-z0-9]{6}个ID，当你拥有2,176,782,336个ID时，必然会发生碰撞（没有更多可用的密钥）。由于生日悖论，你会更早地遇到碰撞。在这样一个小的密钥空间中，没有办法避免碰撞 - 你需要有某种形式的碰撞恢复。

你可以生成ID直到不发生冲突 - 但随着密钥空间的填充，这将变得越来越慢：想象一下一个[a-z]的密钥空间，[a-n]和[p-z]已经被占用 - 现在每个新的随机ID更可能发生冲突而不是不冲突; 当您完全填满密钥空间时，循环将不会终止。

我提出的算法在这方面可能过度谨慎：如果它发现碰撞，它将尝试越来越长的ID（因为它假设“碰撞 => 不可行来检查更短的密钥空间”）。虽然它不高效，但很可能在几次迭代中找到一个不冲突的ID。

非常好的观点和答案。你认为预生成一个带有ID的表格可能更明智，就像在这个网站上已经建议过的那样吗？ - Decent Dabbler
数据太多，价值太少。当您首次遇到X次连续碰撞和/或Y%的碰撞时，只需更改其原始元代码以增加长度即可。（我会选择X = 3，Y = 50％）。 - Mrki
根据你希望看到的流量而定 - 但是除非你的网站每秒需要分配数百个ID，否则我不会费心。 - Piskvor left the building
@Mrki和@Piskvor：当然也有很好的观点。@Piskvor：我的目标是尽可能地保持简短（最长6个字符，用于Twitter等服务），所以我可能会减少长度（为了避免早期可猜测性，不以短长度开头）。但非常有用的答案。谢谢。 - Decent Dabbler
无论如何，我现在得走了。如果需要的话，我会回来的。到目前为止，再次感谢您。 - Decent Dabbler
4
一个有点奇怪的想法。为什么不使用排列？例如，您有一个值集[0-9a-z]，当您生成第一个id时，您按词典顺序取第一个排列，然后是第二个，依此类推。为了使其看起来不那么容易被猜测，您可以更改字典顺序的规则。例如，将“a”放在“t”之后或类似的规则。您还可以使用元组而不是完整的排列。这将确保没有冲突。
这个想法实际上是关于制作某种双向哈希函数。基本上，如果您能够以某种方式编码数字“1”，以获得类似“q8d3dw”的东西，并能够将“q8d3dw”解码回“1”，那么您可以确定该函数将为所有值从1到36 ^ 6提供唯一的字符串。
问题实际上是选择这个函数。简单的方法是将“1”与“000000”相关联，“2”与“000001”相关联，“12”与“00000b”相关联。基本上，按词典顺序排列所有可用字符串，并选择与id相等的位置上的字符串。但是，这很容易被猜测。因此，您可以人为地改变字典顺序的规则。例如，不使用正常顺序（0,1,2,3 ... a，b，c ... x，y，z），而是稍微洗牌一下，得到类似于（a，5，t，3 ...）的顺序。这将产生更加模糊的结果。但它仍然很容易被猜测，因为第一个元素将是“aaaaaa”，第二个将是“aaaaa5”，然后是“aaaaat”。因此，您可以进一步更改字典顺序的规则，使其依赖于字符的位置。例如，第一个字符id的顺序是（a，5，t，3 ...），第二个字符id的顺序是（y，7，3，r ...）等。
现在，我不会发布任何伪代码，因为它会相当冗长。并且，我不建议您采用这种路线，除非您有兴趣为乐趣创建此类算法：）。但是，如果您采用此路线，它可能是一种非常有效的生成此id的方法，而且没有冲突的机会。我建议您阅读唐纳德·科诺斯的《计算机编程艺术》第4卷。其中提供了许多有关实现此类算法的建议。
嗨，伊万，谢谢你的回答。虽然你的回答听起来很有吸引力，但我很难想象你具体是怎么想的，因为我对这些数学原理不是很熟悉。如果不麻烦的话，你能否用一个小例子（也许是一些伪代码）详细说明一下你的意思？我通常通过例子而不是数学理论更容易理解（我猜我不应该在学校太早就放弃数学了:-/）。对此我感到抱歉。 - Decent Dabbler
啊！我现在明白你的意思了。是的，这看起来是一个非常合理的方法。我现在已经理解得足够好，可以将其转化为编码算法。听起来像是一个有趣的小难题要解决。谢谢。不过出于好奇，你不建议使用它的原因是因为“安全通过模糊性”因素吗？就我所知，我还没有确定这个应用程序特性的安全性有多重要，所以如果安全性最终并不那么重要，我很可能会使用它。但我需要再考虑一下它的影响。 - Decent Dabbler
唯一不使用它的原因就是实现它需要花费的时间。除此之外，如果每个字符的顺序都是随机的话，这个算法应该快速、可靠，而且相当安全。 - Ivan
2

@ivan: 这里是一个实现。

首先，您需要6个字符串，以下是生成它们的代码：

$letters = range('a', 'z');
$numbers = range(0, 9);
$char_list = array_merge_recursive($letters, $numbers);
for ($i = 0; $i <= 5; $i++) {
    shuffle($char_list);
    echo '$mysterykey[' . $i . "] = '" . implode($char_list) . "';\n";
}

那么你可以在函数中使用该输出：
function int_to_x36($value) {
    $mysterykey[0] = 'awkbs81t3jyg20v4qhoxzcuenr65dfimlp97';
    $mysterykey[1] = 'ut17qclz96n3msky8jwp4r25gdvhxo0biaef';
    $mysterykey[2] = 'cewszx142nph05mi9ulafbdvy36o8gq7trjk';
    $mysterykey[3] = '37hp28wjdqe5vnlzxofrsybu4im90k16agtc';
    $mysterykey[4] = 'n9a3jksl5ct0eqfzo7pvgyd4m2hiu18xrb6w';
    $mysterykey[5] = 'mq0nbk3zs529gu4tecli8j176vardxoypfwh';

    $x36 = array();
    for ($i = 5; $i >= 0; $i--) {
        $x36[$i] = 0;  
        $y = pow(36, $i);

        if ($value >= $y) {
            $z = floor($value/$y);
            $value = $value - ($z * $y);
            $x36[$i] = $z;
        }   
    }      

    $encoded = '';
    for ($i = 0; $i <= 5; $i++) {
        $encoded .= $mysterykey[$i][$x36[$i]];
    }

    return $encoded;
}

function x36_to_int($value) {
    $mysterykey[0] = 'awkbs81t3jyg20v4qhoxzcuenr65dfimlp97';
    $mysterykey[1] = 'ut17qclz96n3msky8jwp4r25gdvhxo0biaef';
    $mysterykey[2] = 'cewszx142nph05mi9ulafbdvy36o8gq7trjk';
    $mysterykey[3] = '37hp28wjdqe5vnlzxofrsybu4im90k16agtc';
    $mysterykey[4] = 'n9a3jksl5ct0eqfzo7pvgyd4m2hiu18xrb6w';
    $mysterykey[5] = 'mq0nbk3zs529gu4tecli8j176vardxoypfwh';

    $value36 = str_split($value);

    $x36 = array();
    for ($i = 0; $i <= 5; $i++) {
        $x36[$i] = strpos($mysterykey[$i], $value36[$i]);
    }

    $x = 0;
    for ($i = 5; $i >= 0; $i--) {
        $x += $x36[$i] * pow(36, $i);
    }      

    return $x;
}

我相信我可能忽略了一些东西，但它似乎已经正常工作了。

1
如果网站足够大，我指的是非常大——比如说“我们需要每秒分配数百个新ID”（这将带来其他问题，例如在一年内耗尽36^6个密钥空间），那么您可以预先生成密钥并分配它们。
以下是一个伪代码示例——在这样一个高流量的网站上，您可能需要优化所使用的算法。
预生成是微不足道的——只需从000000开始，一直到zzzzzz，将每行插入表中并标记为未使用：
 ID     | used
==============
 000000   0   
 000001   0   
 ...
 zzzzzz   0

当您收到新ID的请求时，请选择一个随机的ID并标记为已使用（危险！并发问题！）：

SELECT ID FROM ids WHERE RAND() LIMIT 1
UPDATE ids SET used = 1, url=what_you_want_shortened WHERE ID = whatever_you_got_from_previous_query

你可能会遇到效率问题（例如使用WHERE RAND()，表锁等），但这是可行的。

嗨Piskvor，感谢您提供的又一个有用的答案。但是我实际上在考虑使用预先洗牌的带有递增主键的表，然后每次弹出或插入一条记录。我认为这将避免任何并发问题，不是吗？（或者我在这里忽略了什么重要的东西）。我将运行一些测试，以查看如何有效地预先洗牌大量数据的数组。我可以想象PHP会因此而崩溃。但我必须尝试才能找出答案。:) 再次感谢。如果您愿意，请告诉我您对我的计划的看法。再次感谢！ - Decent Dabbler
我必须说，你之前的答案现在更吸引我，因为它允许更多的ID（包括递减长度等），因为从0到zzzzzz预生成表格可能会有些过分。 - Decent Dabbler
@fireeyedboy：啊，那个方法有点用，但是我认为这种做法似乎过于复杂了。 - Piskvor left the building
1

比如大随机数和SHA-256哈希？您可以稍后缩短以适应您的需求。

为什么要使用哈希呢？为什么不只生成一个大的随机数并将其留下？毕竟，SHA-256哈希只是一个256位的数字。 - LukeH
因为他想要字母数字字符 :) - Tobias
1
请纠正我如果我错了，但我认为LukeH的意思是你同样可以采用一个随机数的十六进制表示。 - Decent Dabbler
0

如果您不介意引入 .NET dll，我已经创建了一个项目来实现这一点。源代码在 GitHub 这里，而二进制文件位于 IdGenerator NuGet Package。

它可以为您生成指定长度的有序序列和/或随机值，均以 36 为底。无论是多个 ID 生成器实例还是分布式环境中，ID 都是唯一的。

var generator = new Base36IdGenerator(
                numTimestampCharacters: 11, 
                numServerCharacters: 4, 
                numRandomCharacters: 5, 
                reservedValue: "", 
                delimiter: "-", 
                delimiterPositions: new[] {15, 10, 5});

// This instance would give you a 20-character Id, with an
// 11-character timestamp, 4-character servername hash, 
// and 5 character random sequence. This gives you 1.6 million
// hash combinations for the server component, and 60 million
// possible combinations for the random sequence. Timestamp is
// microseconds since epoch:
Console.WriteLine(generator.NewId());
// 040VZC6SL01003BZ00R2

// Argument name specified for readability only:
Console.WriteLine(generator.NewId(delimited: true));
// 040VZ-C6SL0-1003B-Z00R2

当然，如果你更关心字符串不可猜测而不是有序序列，你可以使用GetRandomString方法：

// 6-characters give you a little over 2 billion possible 
// combinations (36 ^ 6). 7 characters is about 78 billion.
Console.WriteLine(generator.GetRandomString(length: 6));

基本原则是：
  • 获取自纪元以来的微秒数（64位数字）
  • 获取0和（36 ^所需长度）之间（13个最大）的随机数（64位）
  • 获取服务器名称哈希（简单Sha1）
  • 将每个组件转换为基36字符串
  • 使用0左填充到所需的长度
Base36编码器本身来自http://www.stum.de/2008/10/20/base36-encoderdecoder-in-c/。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接