2024-04-17 23:34:56 发布
网友
我需要生成一个32位随机整数,但取决于一些参数。其思想是为通过自己的P2P网络发送的每条消息生成一个唯一的ID。为了生成它,我想作为参数:我的IP和时间戳。我的问题是,如何从这些参数生成这个32位随机整数?在
再次感谢!在
以下是选项及其相关问题的列表:
使用随机数。您将在大约一半的位中得到一个碰撞(非唯一值)(这是“生日碰撞”)。所以对于32位,在2*16条消息后会发生冲突。如果你发送的信息少于65000条,这不是问题,但65000条并不是一个很大的数字。
使用某个服务的顺序计数器。这就是twitter的snowflake所做的(在这里看到另一个答案)。问题是通过网络提供这些信息。通常在分布式系统中,你给每个代理一组数字(a可能得到0-9,B得到10-19,等等),然后他们使用这些数字请求一个新的块。这减少了网络流量和提供数字服务的负载。但这很复杂。
从一些将是唯一的值生成哈希。这听起来很有用,但实际上并不比(1)好,因为你的散列会发生碰撞(我在下面解释原因)。所以你可以散列IP地址和时间戳,但你所做的只是生成32位的随机数,实际上(区别在于你可以复制这些值,但你似乎并不需要这个功能),所以在65000条左右的消息之后,你会再次发生冲突,这并不多。
在生成id以保证唯一性方面更加聪明。(3)中的问题是哈希超过32位,因此压缩信息并获得重叠。相反,您可以显式地管理位以避免冲突。例如,为每个客户端编号16位(最多允许65000个客户端),然后让每个客户端用户使用一个16位计数器(每个客户端最多允许65000条消息,这是(3)的一大改进)。它们不会发生冲突,因为每一个都保证是唯一的,但是系统中有很多限制,事情开始变得复杂(需要为每个客户机编号和存储计数器状态)。
使用更大的区域。如果您使用64位ID,那么您可以使用随机数,因为碰撞将是每2**32条消息发生一次,实际上从来没有(40000000000中有1条)。或者,您可以使用32位的时间戳连接ip地址(32位)(但要小心,这可能意味着每秒来自客户端的消息不超过1条)。唯一的缺点是带宽稍大,但在大多数情况下,id要比有效负载小得多。
就我个人而言,我会使用一个更大的字段和随机数-这很简单而且很有效(尽管好的随机数在嵌入式系统中是个问题)。在
最后,如果您需要值是“真的”随机的(因为,例如,id用于决定优先级,您希望事情公平),那么您可以使用上面的一个具有确定性值的解决方案,并将位重新排列为伪随机的。例如,反转计数器中的位就足够了(首先比较lsb)。在
我建议使用一些散列。有许多可能的散列,FNV hash有多种大小,而且速度很快。如果你想要某种加密安全的东西,它会慢很多。你可能需要添加一个计数器:1,2,3,4。。。以确保在同一时间戳内不会得到重复的哈希值。在
你有没有试着看看Twitter的Snowflake?有一个Python包装器。在
以下是选项及其相关问题的列表:
使用随机数。您将在大约一半的位中得到一个碰撞(非唯一值)(这是“生日碰撞”)。所以对于32位,在2*16条消息后会发生冲突。如果你发送的信息少于65000条,这不是问题,但65000条并不是一个很大的数字。
使用某个服务的顺序计数器。这就是twitter的snowflake所做的(在这里看到另一个答案)。问题是通过网络提供这些信息。通常在分布式系统中,你给每个代理一组数字(a可能得到0-9,B得到10-19,等等),然后他们使用这些数字请求一个新的块。这减少了网络流量和提供数字服务的负载。但这很复杂。
从一些将是唯一的值生成哈希。这听起来很有用,但实际上并不比(1)好,因为你的散列会发生碰撞(我在下面解释原因)。所以你可以散列IP地址和时间戳,但你所做的只是生成32位的随机数,实际上(区别在于你可以复制这些值,但你似乎并不需要这个功能),所以在65000条左右的消息之后,你会再次发生冲突,这并不多。
在生成id以保证唯一性方面更加聪明。(3)中的问题是哈希超过32位,因此压缩信息并获得重叠。相反,您可以显式地管理位以避免冲突。例如,为每个客户端编号16位(最多允许65000个客户端),然后让每个客户端用户使用一个16位计数器(每个客户端最多允许65000条消息,这是(3)的一大改进)。它们不会发生冲突,因为每一个都保证是唯一的,但是系统中有很多限制,事情开始变得复杂(需要为每个客户机编号和存储计数器状态)。
使用更大的区域。如果您使用64位ID,那么您可以使用随机数,因为碰撞将是每2**32条消息发生一次,实际上从来没有(40000000000中有1条)。或者,您可以使用32位的时间戳连接ip地址(32位)(但要小心,这可能意味着每秒来自客户端的消息不超过1条)。唯一的缺点是带宽稍大,但在大多数情况下,id要比有效负载小得多。
就我个人而言,我会使用一个更大的字段和随机数-这很简单而且很有效(尽管好的随机数在嵌入式系统中是个问题)。在
最后,如果您需要值是“真的”随机的(因为,例如,id用于决定优先级,您希望事情公平),那么您可以使用上面的一个具有确定性值的解决方案,并将位重新排列为伪随机的。例如,反转计数器中的位就足够了(首先比较lsb)。在
我建议使用一些散列。有许多可能的散列,FNV hash有多种大小,而且速度很快。如果你想要某种加密安全的东西,它会慢很多。你可能需要添加一个计数器:1,2,3,4。。。以确保在同一时间戳内不会得到重复的哈希值。在
你有没有试着看看Twitter的Snowflake?有一个Python包装器。在
相关问题 更多 >
编程相关推荐