Traduire Int32 en ushort et revenir

Question

Je tente de concevoir un système permettant de stocker les valeurs entières supérieures à 65535 dans un ushort. Laissez-moi vous expliquer.

Nous avons un système qui génère des valeurs Int32 à l’aide d’une colonne IDENTITY de SQL Server et est limité par une API cliente en production qui déborde de nos identifiants Int32 dans des shorts de stockage. Heureusement, le client ne possède à peu près qu'une vingtaine d'instances d'objets portant ces ID (appelons-les packages) à tout moment et il suffit de les avoir uniques parmi les frères et sœurs locaux. La solution généralement acceptée est de traduire nos ID Int32 en ushorts (et non, je ne veux pas dire de casting, je veux dire traduire) avant de les transmettre au client, mais il existe des barbes avec cette approche:

1. Certains ID inférieurs à 65535 peuvent toujours être en jeu sur un client donné à tout moment pour des raisons d'expiration.
2. Nous ne pouvons pas avoir de collisions d’ID - c’est-à-dire que si le package ID 1 est envoyé au client, un algorithme qui détermine le nombre de fois où 65535 est supprimé d’un Int32 pour créer un ushort appliqué à 65536 aurait également pour conséquence que 1 collision.
3. Nous devons être en mesure de reconstituer l’ushort en Int32 à son retour.

Ce que nous avons à disposition pour résoudre ce problème est un champ à un seul octet signé qui nous est renvoyé et nous donne 127 valeurs avec lesquelles jouer (en réalité 117 parce que nous utilisons 0-9 pour autre chose). J'appellerai cela le "champ d'octets". à partir de maintenant.

Nous avons discuté de trois routines de traduction différentes:

1. Multiplicative: indiquez dans le champ d'octet combien de fois nous supprimons 65535 de notre Int32 pour créer un ushort. Cela pose des problèmes de collision, comme indiqué ci-dessus.
2. Etat de la session sérialisée: pour chaque client, générez un ID de session basé sur des faits concernant ce client. Stockez ensuite une table de traduction 1: 1 à partir de 1 jusqu'au nombre de packages livrés. Ainsi, lorsque le client aura à nouveau accès à notre serveur, l'inventaire des packages pourra être reconverti en identifiants de base de données connus. Cela pose des problèmes de temps système car nous sauvegardions l’état de la session sérialisée dans une base de données et souhaitions prendre en charge des centaines à des milliers de transactions par seconde.
3. Approche algorithmique variée dans laquelle le champ d'octets est l'ID d'un algorithme de transformation qui prend un Int32 et le transforme en un ushort. Évidemment, beaucoup d’entre elles vont être simples multiplicatives (pour augmenter notre plafond d'identifiants que nous pouvons transformer), mais certaines devront être multiplicatives avec une limite plus petite (comme 32768) avec un nombre ajouté à / soustrait pour se rapprocher d'un nombre qui peut être garanti unique parmi les frères et soeurs. Cette approche nécessite de nombreux processeurs, mais elle devrait nous permettre d’éviter les collisions tout en restant évolutive (nous avons toutefois un plafond limité qui ne sera pas atteint avant que le problème à court terme ne disparaisse de lui-même à cause des mises à niveau).

Ma question est donc la suivante: existe-t-il un meilleur moyen que mes approches ci-dessus, et si non, que devrais-je rechercher en termes d'algorithmes (pour l'approche n ° 3) pour générer un nombre compris entre 1 et 65535 lorsqu'un nombre donné est supérieur à 0 et ne doit pas être un hash à sens unique?

Clarification: le problème n’est pas le plus gros problème avec ushort, c’est que l’API client utilise un ushort. Je ne peux donc pas combiner le champ d’octets sur le client pour obtenir de plus grandes valeurs (l’API client ne peut pas être mis à niveau mais finira par passer en phase. hors de l'existence).

Answer 1

En ce qui concerne l'approche 2:

Votre deuxième approche est à peu près la façon dont fonctionne le NAT. Chaque client TCP / UDP du réseau local utilise jusqu'à 65 535 ports (sauf le port 0) et une adresse IP privée. Le routeur ne connaît qu'une seule adresse IP publique. Étant donné que deux clients peuvent avoir le port source 300, il ne peut pas simplement remplacer l'adresse IP privée par une adresse IP publique, ce qui provoquerait des collisions. Ainsi, il remplace l'adresse IP et "traduit" le port (NAT: adresse réseau Traduction ). Au retour, il convertit le port et remplace le public par une adresse IP privée, avant de renvoyer le paquet. Vous ne feriez rien d'autre que cela. Cependant, les routeurs conservent ces informations en mémoire - et ils ne sont pas trop lents en NAT (les entreprises possédant des centaines d'ordinateurs sont parfois NAT en connexion Internet et le ralentissement est à peine perceptible dans la plupart des cas). Vous dites que vous voulez jusqu'à mille transactions par seconde - mais combien de clients y aura-t-il? Comme cela va principalement définir la taille de la mémoire nécessaire pour sauvegarder les mappages. S'il n'y a pas trop de clients, vous pouvez conserver le mappage avec une table triée en mémoire. Dans ce cas, la vitesse sera le plus petit problème (la table devient plus grande et la mémoire saturée du serveur est la plus grande).

Ce qui n’est pas clair pour moi, c’est que vous disiez une fois

  

Heureusement, le client a seulement environ   20 ou plus cas de choses avec   ces identifiants - appelons-les paquets -   à un moment donné et il suffit de   les avoir unique parmi les locaux   frères et soeurs.

mais ensuite vous dites

  

Certains identifiants inférieurs à 65535 peuvent toujours l'être   en jeu sur un client donné à tout moment   en raison de la non-expiration.

Je suppose que ce que vous vouliez dire probablement par la deuxième déclaration est que si un client demande l'ID 65536, il peut toujours avoir des ID inférieurs à 65535 et que ceux-ci peuvent être aussi bas que (disons) 20. Ce n'est pas que le client traite IDs dans un ordre, non? Donc, vous ne pouvez pas dire, simplement parce qu'il demande maintenant 65536, il peut avoir des valeurs plus petites, mais certainement pas dans la plage 1-1000, correct? Il pourrait en fait garder une référence à 20, 90, 2005 et 41238 tout en dépassant 65535, c'est ce que vous vouliez dire?

Personnellement, j'apprécie votre deuxième approche plus que la troisième, car il est plus facile d'éviter une collision dans tous les cas et la conversion du numéro est une opération simple et intuitive. Bien que je doute que votre troisième approche puisse fonctionner à long terme. D'accord, vous pourriez avoir un octet pour stocker la fréquence à laquelle vous avez soustrait 2 ^ 16 numéros. Toutefois, vous ne pouvez soustraire que 117 * 2 ^ 16 en tant que plus grand nombre. Que ferez-vous si les chiffres vont au-dessus de cela? En utilisant un algorithme différent, cela ne soustrait pas mais fait quoi? Diviser? Bits de décalage? Si vous perdez de la granularité, cela signifie que cet algorithme ne peut plus composer tout nombre possible (il effectuera de grands sauts). S'il était si facile d'appliquer simplement une fonction de traduction magique sur 32 bits pour en créer 16 bits (+ un octet supplémentaire), puis de la reconvertir, supposez que chaque méthode de compression de ce monde l'utiliserait, comme elle le pourrait, quel que soit le nombre 32 bits, compressez-le toujours en 24 bits (16 bits + un octet). Ce serait magique. Il n’est pas possible d’emballer du 32 bits dans le 24 bits et d’emballer également toute la logique permettant de la reconvertir. Vous aurez besoin d'un stockage externe, ce qui nous ramène à votre deuxième approche. C’est la seule approche qui fonctionnera, et cela fonctionnera pour chaque nombre compris dans la plage de numéros 32 bits.

Answer 2

Je peux penser à quelques autres options:

Y a-t-il globalement moins de 65 536 entrées dans la base de données? Si tel est le cas, vous pouvez conserver une table de mappage qui n'est pas associée à l'état de session, mais qui est persistante dans l'application.

La majorité des entrées aux index est-elle inférieure à, disons 50 000? Si tel est le cas, vous pouvez mapper directement ces valeurs et utiliser une carte associée à la session pour les autres.

Si la persistance de telles données de session pose problème et que le nombre de clients est relativement petit, vous pouvez activer l'affinité client / session et conserver la mappe au niveau local sur le serveur.

S'il ne s'agit pas d'une application Web, vous pouvez conserver la carte sur le client lui-même.

Je ne vois aucun moyen algorithmique d'éviter les collisions - je suppose que vous pouvez toujours trouver un exemple qui pourrait entrer en collision.

Answer 3

Combien de "plus" que 65535 avez-vous besoin? Vous pouvez toujours simplement ajouter quelques bits de votre " champ d'octets " comme les bits de poids fort de l'ID. Seulement 2 bits vous mèneraient à 262.143, 3 bits vous donneraient 524.287.