algorithm - 以紧凑的方式使用后缀或前缀对数字进行编码

Question

假设我有 6 位数的订单 ID:

000000
000001
000003
...
000020
...
999999

并假设其中每一个都来自分布式系统中的不同节点，我想将节点 ID 编码到订单中。 最简单的方法是像这样简单地保留节点 ID 的前 2 位数字:

010000 - second node
020001 - third node
010003 - second node again
150004 - 16th node
...

这工作得很好，但因为我确定我只期待少量节点(比如 16 个)，我失去了很多可能的 id，将自己限制在基本上 10^4 而不是 10^6 .有没有一种聪明的方法可以在不限制可能的数量的情况下对 15 个唯一节点进行编码？理想情况下，我会有 10^6 - 15 种可能性。

编辑:我正在寻找一种不会将范围平均分配给每个节点 ID 的解决方案。我正在寻找一种方法，将节点 ID 编码为已经存在的唯一 ID，而不会(理想情况下)丢失更多的可能性节点数。

EDIT2:这必须是 6 位数字的字符串表示的原因是因为我正在使用的 API 需要这个。不幸的是，没有办法解决它。

Answer 1

I'm losing lots of possible ids limiting myself to basically 10^4 instead of 10^6.

我们仍然有 10^4 * 16 个 ID 。

Is there a smart way to encode the 15 unique nodes without limiting the possible numbers?

这个问题类似于distributed hash table键空间分区。该问题最著名的解决方案是创建大量虚拟节点，在这些虚拟节点之间划分 key 空间，然后以特定方式(循环、随机、按需等)将这些虚拟节点分配给物理节点。

实现键空间分区最简单的方法是确保每个节点都生成这样一个id，即:

vnode_id = order_id % total_number_of_vnodes

例如，如果我们只有 3 个 vnode [0, 1, 2]，那么:

vnode 0 must generate ids: 0, 3, 6, 9...
vnode 1 must generate ids: 1, 4, 7, 10...
vnode 2 must generate ids: 2, 5, 7, 11...

如果我们有 7 个 vnode [0, 1, 2, 3, 4, 5, 6] 那么:

vnode 0 must generate ids: 0, 7, 14, 21... 
vnode 1 must generate ids: 1, 8, 15, 22... 
vnode 2 must generate ids: 2, 9, 16, 23... 
...
vnode 6 must generate ids: 6, 13, 20, 27... 

然后所有物理节点必须以已知和通用的方式映射到虚拟节点，例如 1:1 映射:

physical node 0 takes vnode 0
physical node 1 takes vnode 1
physical node 2 takes vnode 2

按需映射:

physical node 0 takes vnode 0, 3, 7 (many orders)
physical node 1 takes vnode 1, 4 (less orders)
physical node 2 takes vnode 2 (no orders) 

我希望你能理解这个想法。

Ideally, I would have 10^6 - 15 possibilities.

很遗憾，这是不可能的。考虑一下:我们有 10^6 个可能的 ID 和 15 个不同的节点，每个节点生成一个唯一 ID。

基本上，这意味着我们以某种方式在节点之间划分我们的 id，即每个节点平均得到 10^6/15，这远低于理想的 10^ 6 - 15。

使用上面描述的方法，我们仍然有 10^6 id，但是它们将在 vnode 之间进行分区，vnode 又将映射到物理节点。这是针对您的问题 AFAIK 的最佳实用解决方案。

I'm looking for a solution that won't equally distribute a range to each node id. I'm looking for a way to encode the node id in an already existing unique id, without losing (ideally) more that the number of nodes of possibilities.

不要期待奇迹。可能还有许多其他技巧值得尝试。

例如，如果Server和所有Client都知道下一个订单id必须是235，但是说Client 5生成订单id 240(235 + 5)并发送给Server。

服务器期望订单 ID 为 235，但收到订单 ID 为 240。所以现在服务器知道此订单来自客户端 5 (240 - 235)。

或者我们可以尝试使用另一个字段来存储客户端 ID。例如，如果您有一个时间字段 (HH:MM.SS)，我们可能会使用秒来存储客户 ID。

只是一些例子，我猜你明白了......