以紧凑的方式使用后缀或前缀对数字进行编码
Encoding a number with a suffix or prefix in a compact way
假设我有 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 需要这个。不幸的是，没有办法解决它。
令n为6位输入的前2位所代表的数字。假设你有 16 个节点，我们可以这样做：
nodeId = n % 16
还有：
highDigit = n / 16
其中/表示整数除法。对于 16 个节点，highDigit = [0..6]
如果m是输入的最后4位代表的数字那么我们可以通过以下方式恢复原始订单id：
orderId = highDigit*10^5 + m
采用这种方案，16个节点，可以表示6*10^5 + 10^4个订单id。
您可以将 10^6 个可能的 ID 分成接近相等的块，其中每个块的起始索引等于 10^6 除以块数，向下取整，乘以块索引，块大小是 10^6 除以块数，向下舍入。在您的示例中，有十六个块：
10^6 / 16 = 62,500
chunk1: [ 0, 62500)
chunk2: [ 62500, 125000)
chunk3: [125000, 187500)
chunk4: [187500, 250000)
chunk5: [250000, 312500)
chunk6: [312500, 375000)
chunk7: [375000, 437500)
chunk8: [437500, 500000)
chunk9: [500000, 562500)
chunk10: [562500, 625000)
chunk11: [625000, 687500)
chunk12: [687500, 750000)
chunk13: [750000, 812500)
chunk14: [812500, 875000)
chunk15: [875000, 937500)
chunk16: [937500, 1000000)
要根据节点 X 上的本地 ID 计算全局 ID，请计算 62500 * X + 本地 ID。要确定节点的节点和本地 ID，请计算节点 = 全局 ID / 62500 向下舍入和本地 ID = 全局 ID mod 62500.
这样做，您基本上可以使用所有可用的索引，直到出现舍入误差。与节点之间的 I/O 相比，整数上的除法和 modulus 应该相对较快。
由于您选择使用数字（而不是位，我们可以将整个练习压缩成一个 32 位数字），这里是一种编码节点 ID 的方法。也许其他人可以想出更多的想法。
将数字字母扩展到 J。想象一下节点 ID 的位分布在六位数字上。对于每个设置位，将订单ID的十进制数字映射到一个字母：
0 -> A
1 -> B
2 -> C
...
9 -> J
例如：
{759243, 5} -> 759C4D
现在您可以将所有 10^6 订单 ID 与 6 位节点 ID 一起编码。
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键空间分区。该问题最著名的解决方案是创建大量虚拟节点，在这些虚拟节点之间划分密钥空间，然后以特定方式（循环、随机、按需等）将这些虚拟节点分配给物理节点。
实现键空间分区最简单的方法是确保每个节点都生成这样一个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 个不同的节点，每个节点生成一个 unique 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。
只是一些例子，我想你明白了......
假设我有 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 需要这个。不幸的是，没有办法解决它。
令n为6位输入的前2位所代表的数字。假设你有 16 个节点，我们可以这样做：
nodeId = n % 16
还有：
highDigit = n / 16
其中/表示整数除法。对于 16 个节点，highDigit = [0..6]
如果m是输入的最后4位代表的数字那么我们可以通过以下方式恢复原始订单id：
orderId = highDigit*10^5 + m
采用这种方案，16个节点，可以表示6*10^5 + 10^4个订单id。
您可以将 10^6 个可能的 ID 分成接近相等的块，其中每个块的起始索引等于 10^6 除以块数，向下取整，乘以块索引，块大小是 10^6 除以块数，向下舍入。在您的示例中，有十六个块：
10^6 / 16 = 62,500
chunk1: [ 0, 62500)
chunk2: [ 62500, 125000)
chunk3: [125000, 187500)
chunk4: [187500, 250000)
chunk5: [250000, 312500)
chunk6: [312500, 375000)
chunk7: [375000, 437500)
chunk8: [437500, 500000)
chunk9: [500000, 562500)
chunk10: [562500, 625000)
chunk11: [625000, 687500)
chunk12: [687500, 750000)
chunk13: [750000, 812500)
chunk14: [812500, 875000)
chunk15: [875000, 937500)
chunk16: [937500, 1000000)
要根据节点 X 上的本地 ID 计算全局 ID，请计算 62500 * X + 本地 ID。要确定节点的节点和本地 ID，请计算节点 = 全局 ID / 62500 向下舍入和本地 ID = 全局 ID mod 62500.
这样做，您基本上可以使用所有可用的索引，直到出现舍入误差。与节点之间的 I/O 相比，整数上的除法和 modulus 应该相对较快。
由于您选择使用数字（而不是位，我们可以将整个练习压缩成一个 32 位数字），这里是一种编码节点 ID 的方法。也许其他人可以想出更多的想法。
将数字字母扩展到 J。想象一下节点 ID 的位分布在六位数字上。对于每个设置位，将订单ID的十进制数字映射到一个字母：
0 -> A
1 -> B
2 -> C
...
9 -> J
例如：
{759243, 5} -> 759C4D
现在您可以将所有 10^6 订单 ID 与 6 位节点 ID 一起编码。
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键空间分区。该问题最著名的解决方案是创建大量虚拟节点，在这些虚拟节点之间划分密钥空间，然后以特定方式（循环、随机、按需等）将这些虚拟节点分配给物理节点。
实现键空间分区最简单的方法是确保每个节点都生成这样一个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 个不同的节点，每个节点生成一个 unique 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。
只是一些例子，我想你明白了......