algorithm - 以紧凑的方式对带有后缀或前缀的数字进行编码
问题描述
假设我有 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 需要这个。不幸的是,没有办法解决它。
解决方案
我失去了很多可能的 id,将自己限制在基本上 10^4 而不是 10^6。
我们总共还有10^4 * 16
ids 。
有没有一种聪明的方法来编码 15 个唯一节点而不限制可能的数量?
这个问题类似于分布式哈希表键空间分区。该问题最著名的解决方案是创建大量虚拟节点,在这些虚拟节点之间划分密钥空间,然后以特定方式(循环、随机、按需等)将这些虚拟节点分配给物理节点。
实现键空间分区的最简单方法是确保每个节点生成这样一个 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)
我希望你掌握这个想法。
理想情况下,我会有 10^6 - 15 种可能性。
不幸的是,这是不可能的。考虑一下:我们有 10^6 个可能的 id 和 15 个不同的节点,每个节点生成一个唯一的id。
基本上,这意味着我们以一种或另一种方式在节点之间划分我们的 id,即每个节点得到平均10^6 / 15
,这远不如期望的10^6 - 15
。
使用上述方法,我们仍然有10^6
id,但它们将在 vnode 之间进行分区,这些 vnode 又将映射到物理节点。这是解决您的问题 AFAIK 的最佳实用解决方案。
我正在寻找一种不会将范围平均分配给每个节点 ID 的解决方案。我正在寻找一种方法来将节点 id 编码到已经存在的唯一 id 中,而不会丢失(理想情况下)更多的可能性节点数量。
不要期待奇迹。可能还有很多其他值得尝试的技巧。
例如,如果 Server 和所有 Client 都知道下一个订单 id 必须是 235,但假设 Client 5 生成订单 id 240 (235 + 5) 并将其发送给 Server。
服务器期望订单 id 235,但收到订单 id 240。所以现在服务器知道该订单来自客户端 5 (240 - 235)。
或者我们可以尝试使用另一个字段来存储客户端 ID。例如,如果您有一个时间字段 (HH:MM.SS),我们可能会使用秒来存储客户端 ID。
举几个例子,我想你明白了......
推荐阅读
- python - 为 ESP32 编写 Python 测试?
- amazon-web-services - 从私有子网访问 Lambda API
- asp.net-core - 在 ASP.NET Core 3.1 中使用虚拟目录
- python - 将条形之间的统计显着差异添加到 plotnine 图(ggpubr 等效项)
- java - 在 null (Thymeleaf) 的情况下返回静态内容
- geocoding - 地理编码和搜索 API v7
- python - 如何将自定义协议与 Callable 协议结合起来?
- batch-file - 在某些文件夹中使用 for 循环查找文件
- swift - Swift Cocoa:WKWebView Twilio 错误:客户端无法创建应用本地媒体描述。错误代码:53400
- r - SMOTE 困难,矩阵上的下标数量不正确