短唯一标识符

Question

我正在设计一个HTTP服务，每天可以处理多达5亿个请求（由超过一个独立的机器提供支持）。

对于每个请求，我都必须生成唯一的ID并将其返回给用户。 ID必须在10分钟的时间窗口内保持100％唯一性。（最好是1天内全局唯一的ID。）不需要进行服务器间通信来生成该ID。

愚蠢的伪会话示例：

客户端：GET /foo
服务器：Content-Type: text/xml
<root>
            <id>ab9d1972-2844-11e0-86b2-000c29544403</id>
            <other_data/>
        </root>

在此HTTP服务的上一代中，我使用了UUIDs。

我很满意UUIDs，但有一个问题：它们太长了。在这么多的请求中，在日志文件的磁盘空间浪费中，这个额外长度是可以注意到的。

创建一个短而又唯一的标识符的最佳方法是什么？为了使事情值得，算法应该产生至少不到UUID长度的一半，同时在整个一天中保持唯一（10分钟的时间应该更短）。

理想情况下，建议的算法应该具有明智，轻量级且生产质量的C实现。

更新：生成的ID在传递GET请求时不需要进行URI编码。

- Alexander Gladysh

---

懒惰的问题（抱歉，太晚了，无法做数学）：使用ascii85从二进制编码UUID的长度是多少？ - Alexander Gladysh

@Alexander：数字的位数为 ceil(log(max_val)/log(num_different_chars))。 - Oliver Charlesworth

ASCII85将4个字节编码为5个字符。但它并不是真正的URI或人类友好的。（UUID是128位，即16个字节，对应20个ASCII85字符）。 - user166390

在使其独特方面，这取决于具体的要求，但可以考虑类似于推特雪花（推特消息编号）的方法--它只使用64位，但通过仔细选择机器/工作人员识别、时间和计数器来保证在该环境中的唯一性。更容易"猜测"，但这不是不使用更加问题空间优化的方法的充分理由/关注点。 - user166390

@pst：为什么ASCII85不适合URI？（人类友好性不是问题）20个字符很好！ - Alexander Gladysh

Answer 1

给每台机器一个独特的前缀，给每台机器一个计数器。为了生成ID，递增计数器，并将其值附加到前缀上。

如果您想混淆ID，则对其进行加密-密码是可逆转换，因此将其应用于独特值将产生独特值。

- Tom Anderson

---

也许还可以将每个ID分成三部分：机器ID-计数器-随机密钥，以消除ID预测攻击。 - Lawrence Dol

另外：如果按照您的方式生成ID，您认为ID可以有多短？ - Alexander Gladysh

@Alexander：注意，这是16进制的6位数字。 - Oliver Charlesworth

@Alexander：128位密钥的AES/ECB已经在每字节15-20个周期的速度下进行了基准测试，对于单个16字节块来说，最多需要320个周期。与您每条消息需要处理的IO（甚至是XML处理）相比，这只是小菜一碟。还有一些可能更快的密码（例如XTEA），但我找不到可靠的基准测试数据。 - Tom Anderson

@Alexander：如果你想要一个快速的密码，选择AES 128位 :) - JqueryToAddNumbers

Answer 2

一些想法：

• 每天 5 亿个请求。真的吗？
• 使用 UUID。
• 如果需要，不要使用 HTTP（因为这是更重要的开销），并以二进制形式传输 UUID。
• 您需要一定数量的字节来保证您的服务器返回一个真正的 独一无二 的 ID。
• 考虑使用 UDP？

无论如何，你到底在尝试什么？

- BastiBen

---

500M，真的（这是目标顶部容量，估计实际负载更像100M）。不幸的是，HTTP和TCP/IP是必须的。 - Alexander Gladysh

此外，每天500M的数据量应该在c10k限制范围内，这有什么令人惊讶的呢？ - Alexander Gladysh