1

我正在尝试设计一个将大于 65535 的整数值打包到 ushort 中的系统。让我解释。

我们有一个系统，它使用 SQL Server 的 IDENTITY 列生成 Int32 值，并受到生产中客户端 API 的限制，该 API 将我们的 Int32 ID 溢出到 ushorts。幸运的是，客户端在任何给定时间只有大约 20 个具有这些 ID 的事物实例（我们称它们为包），并且它只需要使它们在本地兄弟姐妹中是唯一的。普遍接受的解决方案是将我们的 Int32 ID 转换为 ushorts（不，我不是指强制转换，我的意思是翻译），然后再将它们传输给客户端，但是这种方法存在一些问题：

  1. 由于未过期，某些小于 65535 的 ID 可能随时在给定客户端上运行。
  2. 我们不能有任何 ID 冲突 - 也就是说，如果包 ID 1 发送到客户端，则跟踪从 Int32 中删除 65535 多少次以在应用于 65536 时进行 ushort 的算法也会导致 1 从而导致冲突。
  3. 我们必须能够在返回时将 ushort 重构为 Int32。

我们可以用来解决这个问题的是一个单一的有符号字节字段，它会回显给我们并给我们 127 个值来玩（实际上是 117，因为我们使用 0-9 来做其他事情）。从这里开始，我将其称为“字节字段”。

我们已经讨论了三种不同的翻译例程：

  1. 乘法：在字节字段中存储我们从 Int32 中删除 65535 以制作 ushort 的次数。这具有如上所述的碰撞问题。
  2. 序列化会话状态：对于每个客户端，根据有关该客户端的事实生成一个会话 ID。然后存储一个从 1 到交付的包裹数量的 1:1 转换表，这样当客户端再次访问我们的服务器时，可以将包裹清单转换回它们已知的数据库 ID。这存在开销问题，因为我们要将序列化会话状态备份到数据库，并且我们希望每秒支持数百到数千个事务。
  3. 各种算法方法，其中字节字段是转换算法的 ID，该算法采用 Int32 并将其转换为 ushort。显然，其中许多将是简单的乘法（以增加我们可以转换的 ID 上限），但有些必须乘以较小的边界（如 32768），并加上/减去一个数字才能接近可以保证在兄弟姐妹中唯一的数字。这种方法是处理器密集型的，但应该允许我们在保持可扩展性的同时避免冲突（尽管使用这种方法，我们有一个有限的上限，在 ushort 问题由于升级而自行消失之前无法达到）。

所以我的问题是：有没有比我上面的方法更好的方法，如果没有，我应该在算法方面寻找什么（对于方法＃3），当给定数字大于0 并且不能是单向哈希？

澄清：最大的问题不是 ushort 上限，而是客户端 API 使用 ushort，所以我无法组合客户端上的字节字段以获得更大的值（客户端 API 不可升级，但最终会逐步淘汰）。

4

3 回答 3

1

我可以想到其他一些选择：

数据库中的全球条目是否少于 65536 个？如果是这样，那么您可以维护一个与会话状态无关的映射表，但它是应用程序的持久部分。

索引中的大多数条目是否少于 50,000 个？如果是这种情况，您可以直接映射这些值，并将与会话关联的映射用于剩余的值。

如果持久化此类会话数据是一个问题并且客户端的数量相当少，您可以启用客户端/会话亲和性并维护服务器本地的映射。

如果它不是 Web 应用程序，您可以在客户端本身上维护地图。

我没有看到任何可以避免冲突的算法方式——我怀疑你总能想出一个会发生冲突的例子。

于 2008-09-23T20:13:46.993 回答
1

关于方法2：

您的第二种方法几乎是 NAT 的工作原理。本地网络上的每个 TCP/UDP 客户端都有多达 65535 个正在使用的端口（端口 0 除外）和一个私有 IP。路由器只知道一个公共 IP。由于两个客户端可能都有源端口 300，因此不能简单地将私有 IP 替换为公共 IP，否则会导致冲突出现。因此，它取代了 IP 并“翻译”了端口（NAT：网络地址翻译）。返回时，它会将端口转换回来并再次用私有 IP 替换公共 IP，然后再将包转发回去。你不会做任何其他事情。然而，路由器将这些信息保存在内存中——并且在进行 NAT 时它们不会太慢（拥有数百台计算机的公司有时会通过 NAT 连接到 Internet，在大多数情况下速度几乎不会明显下降）。您说您希望每秒进行上千笔交易——但是会有多少客户？因为这主要将定义备份映射所需的内存大小。如果没有太多的客户端，你可以在内存中保留一个排序表的映射，在这种情况下，速度将是最小的问题（表变大，服务器内存不足是最大的问题）。

我有点不清楚的是你曾经说过

幸运的是，客户端在任何给定时间只有大约 20 个具有这些 ID 的事物实例（我们称它们为包），并且它只需要使它们在本地兄弟姐妹中是唯一的。

但是你说

由于未过期，某些小于 65535 的 ID 可能随时在给定客户端上运行。

我想，您可能通过第二个语句的意思是，如果客户端请求 ID 65536，它可能仍然具有低于 65535 的 ID，并且这些 ID 可能低至（比方说）20。这并不是客户端在直接下单吧？所以你不能说，仅仅因为它现在请求 65536，它可能有一些较小的值，但肯定不在 1-1000 范围内，对吗？它实际上可能保留对 20、90、2005 和 41238 的引用，但仍然超过 65535，这就是你的意思？

我个人更喜欢您的第二种方法而不是第三种方法，因为在任何情况下都更容易避免碰撞，并且将数字翻译回来是一个简单而简单的操作。尽管我怀疑您的第三种方法从长远来看是否可行。好的，您可能有一个字节来存储您从数字中减去 2^16 的频率。但是，您只能减去 117 * 2^16 作为最大数。如果数字超过这个值，你会怎么做？使用不同的算法，它不会减去，而是做什么？划分？位移位？在这种情况下，您会失去粒度，这意味着该算法无法命中任何可能的数字（它会产生很大的跳跃）。如果在 32 位上应用魔术转换函数以从中生成 16 位（+ 一个额外字节）然后将其转换回来是如此容易，那么猜测这个世界上的每种压缩方法都会使用它，因为它可以，不无论 32 位数字是多少，始终将其压缩到 24 位（16 位 + 一个字节）。那将是魔术。不可能将 32 位打包成 24 位，也无法打包如何将其转换回它的所有逻辑。您将需要一些外部存储，这使我们回到您的第二种方法。这是唯一可行的方法，它适用于 32 位数字范围内的每个数字。

于 2008-09-23T20:26:35.997 回答
0

您需要比 65535“多”多少？您总是可以从“字节字段”中添加几位作为 ID 的高位。只需 2 位即可获得 262,143，3 位将使您获得 524,287。

于 2008-09-23T19:49:28.610 回答