将Int32转换成ushort并返回

Question

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

我们有一个系统，它使用来自SQL Server的IDENTITY列生成Int32值，并受到生产中的客户端API的限制，该API将我们的Int32 ID溢出到ushorts。幸运的是，客户端只有大约20个具有这些ID的事件实例 - 让我们称之为包 - 在任何给定的时间，它只需要让它们在本地兄弟姐妹中是唯一的。普遍接受的解决方案是我们的Int32 ID转换为ushorts（没有我的意思不是铸造，我的意思翻译）它们传送到客户端之前，但有这种方法倒钩：

1. 有些ID的少由于未到期，任何时候65535可能仍会在特定的客户端上运行。
2. 我们不能有任何ID冲突 - 也就是说，如果包ID 1进入客户端，跟踪从Int32中删除多少次65535以便在应用到65536时创建一个ushort的算法也会导致1碰撞。
3. 我们必须能够在返回时重建Int32。

我们可用来解决这个问题，什么是呼应给我们一个符号字节场，给了我们127倍的值（因为我们使用0-9别的东西真的117）一起玩。我将这里称之为“字节字段”。

我们已经讨论了三种不同的转换例程：

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

所以我的问题是：是否有比我的方法更好的方法上面，如果不是，我应该在算法方面关注（对＃3的方式），以1-65535之间时产生了一些给定的数字是否大于0并且不能是单向散列？

澄清：它不是ushort ceiling是最大的问题，它的客户端API使用ushort，所以我不能将客户端上的字节字段合并为更大的值（客户端API是不可升级的，但最终会阶段不存在）。

Answer 1

关于方法2：

你的第二种方法几乎是NAT的工作原理。本地网络上的每个TCP/UDP客户端最多有65535个端口（端口0除外）和一个私有IP。路由器只知道一个公共IP。由于两个客户端可能都具有源端口300，因此不能简单地将私有IP替换为公共IP，这会导致冲突出现。因此它会替换IP并“翻译”端口（NAT：网络地址Translation）。返回时，它将端口转换回来，并在将包返回之前再次使用私有IP替换公共。除此之外，你什么都不会做。但是，路由器会将这些信息保存在内存中 - 而且在进行NAT时速度不会太慢（有些公司有数百台计算机有时会连接到互联网，在大多数情况下，缓慢下降几乎不会）。你说你想要每秒多达几千个交易 - 但会有多少客户？因为这主要将定义备份映射所需的内存大小。如果没有太多的客户端，你可以在内存中保留一个有序表的映射，在这种情况下，速度将是最小的问题（表越来越大，服务器内存越大越好）。

什么是有点不清楚我是你曾经说

幸运客户端仅约 20个左右具有 这些ID的东西实例 - 我们姑且称之为包 - 在任何给定时间它只需要 让它们在当地的 兄弟姐妹中独一无二。

但你说

一些标识小于65535仍可能发挥 给定的客户在任何时候 由于非到期。

我想，你可能是由第二条语句的意思是，如果一个客户端请求ID 65536，它可能仍然有低于65535 ID和这些可以低至（比方说）20.这并不是说客户端以正确的顺序处理ID，对吧？所以你不能说，仅仅因为它现在要求65536，它可能有一些较小的值，但肯定不在1-1000范围内，对吗？它可能实际上保留了对20,90,2005和41238的引用，并仍然超过65535，这就是你的意思？

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

Answer 2

你需要多少“多于”65535？您始终可以在“字节字段”中添加少量位作为ID的高位。只需2比特就可以让你达到262,143，3比特会让你达到524,287。

Answer 3

我能想到的其他几个选项：

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

在指标低于大多数条目，说50000？如果是这种情况，您可以直接映射这些值，并为其余的会话使用与会话关联的映射。

如果坚持这样的会话数据是一个问题，客户端的数量是相当小的，你可以使客户端/会话的亲和力和维护地图的本地服务器。

如果它不是一个Web应用程序，你可以保持客户端本身在地图上。

我不认为这会避免任何冲突算法的方式 - 我怀疑你总是可以想出一个例子都将发生冲突。