Tradurre Int32 in ushort e viceversa

Question

Sto tentando di escogitare un sistema per impacchettare valori interi maggiori di 65535 in un ushort. Lasciami spiegare.

Abbiamo un sistema che genera valori Int32 utilizzando una colonna IDENTITY da SQL Server e sono limitati da un'API client in produzione che trabocca i nostri ID Int32 negli utenti. Fortunatamente il cliente ha solo circa 20 istanze di cose con questi ID - chiamiamoli pacchetti - in qualsiasi momento e deve solo averli unici tra i fratelli locali. La soluzione generalmente accettata è quella di tradurre i nostri ID Int32 in ushorts (e no, non intendo il casting, intendo tradurre) prima di trasmetterli al client, tuttavia ci sono ostacoli con questo approccio:

1. Alcuni ID inferiori a 65535 potrebbero essere ancora in gioco su un determinato client in qualsiasi momento a causa della mancata scadenza.
2. Non possiamo avere alcuna collisione ID - cioè se l'ID pacchetto 1 va al client, un algoritmo che tiene traccia di quante volte 65535 viene rimosso da un Int32 per creare un ushort quando applicato a 65536 comporterebbe anche 1 causando così un collisione.
3. Dobbiamo essere in grado di ricostruire l'Usort in Int32 al ritorno.

Ciò che abbiamo a disposizione per risolvere questo problema è un singolo campo byte con segno che ci fa eco e ci dà 127 valori con cui giocare (davvero 117 perché stiamo usando 0-9 per qualcos'altro). Mi riferirò a questo come al "campo byte" da qui in avanti.

Abbiamo discusso di tre diverse procedure di traduzione:

1. Moltiplicativo: memorizza nel campo byte quante volte rimuoviamo 65535 dal nostro Int32 per creare un ushort. Ciò ha problemi di collisione come descritto sopra.
2. Stato sessione serializzato: per ogni client, genera un ID sessione basato su fatti relativi a quel client. Quindi archiviare una tabella di traduzione 1: 1 a partire da 1 fino al numero di pacchetti consegnati, quindi quando il client accede nuovamente al nostro server, l'inventario dei pacchetti può essere ritrasferito nei loro ID database noti. Ciò ha problemi di overhead poiché avremmo eseguito il backup dello stato della sessione serializzata su un database e desideriamo supportare centinaia o migliaia di transazioni al secondo.
3. Approccio algoritmico vario in cui il campo byte è un ID di un algoritmo trasformativo che accetta un Int32 e lo trasforma in un ushort. Ovviamente molti di questi saranno moltiplicativi semplici (per aumentare il nostro massimale di ID che possiamo trasformare) ma alcuni dovranno essere moltiplicativi con una lavanderia più piccola (come 32768) con un numero aggiunto / sottratto per avvicinarsi a un numero che può essere garantito unico tra i fratelli. Questo approccio richiede un uso intensivo del processore, ma dovrebbe consentirci di evitare le collisioni rimanendo scalabili (sebbene con questo approccio abbiamo un limite limitato che non sarà raggiunto prima che il problema ushort scompaia da solo a causa degli aggiornamenti).

Quindi la mia domanda è: c'è un modo migliore dei miei approcci sopra e, in caso contrario, cosa dovrei cercare in termini di algoritmi (per l'approccio # 3) per generare un numero compreso tra 1-65535 quando un determinato numero è maggiore di 0 e non deve essere un hash unidirezionale?

Chiarimento: non è che il massimale di ushort sia il problema più grande, è che l'API client utilizza un ushort quindi non riesco a combinare il campo byte sul client per ottenere valori più grandi (l'API client non è aggiornabile ma alla fine verrà eliminata fuori dall'esistenza).

Answer 1

Riguardo all'approccio 2:

Il tuo secondo approccio è praticamente il modo in cui funziona NAT. Ogni client TCP / UDP sulla rete locale ha fino a 65535 porte in uso (tranne la porta 0) e un IP privato. Il router conosce solo un singolo IP pubblico. Poiché due client possono entrambi avere la porta di origine 300, non può semplicemente sostituire l'IP privato con uno pubblico, causando la comparsa di collisioni. Quindi sostituisce l'IP e "traduce" la porta (NAT: indirizzo di rete traduzione ). Al ritorno, traduce la porta indietro e sostituisce nuovamente il pubblico con un IP privato, prima di inoltrare nuovamente il pacchetto. Non faresti altro. Tuttavia, i router mantengono tali informazioni in memoria - e non sono troppo lenti quando eseguono NAT (le aziende con centinaia di computer sono NAT su Internet a volte e il rallentamento è quasi evidente nella maggior parte dei casi). Dici di volere fino a mille transazioni al secondo, ma quanti clienti ci saranno? Poiché ciò definirà principalmente la dimensione della memoria necessaria per il backup dei mapping. Se non ci sono troppi client, è possibile mantenere il mapping con una tabella ordinata in memoria, in tal caso, la velocità sarà il problema più piccolo (la tabella diventa più grande e il server che esaurisce la memoria è il più grande).

Ciò che non è chiaro per me è che una volta dici

  

Fortunatamente il client ha solo circa   Circa 20 casi di cose con   questi ID - chiamiamoli pacchetti -   in qualsiasi momento e deve solo   li hanno unici tra i locali   fratelli.

ma poi dici

  

Potrebbero essere ancora alcuni ID inferiori a 65535   in gioco su un determinato cliente in qualsiasi momento   a causa della non scadenza.

Suppongo che ciò che probabilmente intendevi con la seconda affermazione è che se un client richiede ID 65536, potrebbe avere ID inferiori a 65535 e questi possono essere bassi come (diciamo) 20. Non è che il client elabori ID in un ordine diretto, giusto? Quindi non puoi dire, solo perché ora ha richiesto 65536, potrebbe avere alcuni valori più piccoli, ma certamente non nell'intervallo 1-1000, giusto? Potrebbe effettivamente mantenere un riferimento a 20, 90, 2005 e 41238 e andare ancora oltre 65535, questo è ciò che intendevi?

Personalmente mi piace il tuo secondo approccio più del terzo, poiché in ogni caso è più facile evitare una collisione e tradurre il numero indietro è un'operazione semplice e chiara. Anche se dubito che il tuo terzo approccio possa funzionare a lungo termine. Ok, potresti avere un byte per memorizzare la frequenza con cui hai sottratto 2 ^ 16 del numero. Tuttavia, puoi sottrarre 117 * 2 ^ 16 solo come numeri più grandi. Cosa farai se i numeri superano quello? Usando un algoritmo diverso, che non sottrae, ma cosa fa? Dividere? Spostare i bit? In tal caso si perde granularità, ciò significa che questo algoritmo non può più colpire nessun numero possibile (farà grandi salti). Se fosse così facile applicare una funzione di traduzione magica su 32 bit per ricavarne 16 bit (+ un byte in più) e poi semplicemente trasformarla indietro, immagino che ogni metodo di compressione in questo mondo lo userebbe, come potrebbe, no indipendentemente dal numero di 32 bit, comprimilo sempre fino a 24 bit (16 bit + un byte). Sarebbe magico. Non è possibile impacchettare 32 bit in 24 bit e impacchettare anche tutta la logica su come trasformarlo in esso. Avrai bisogno di un po 'di memoria esterna, che ci riporta al tuo secondo approccio. Questo è l'unico approccio che funzionerà e funzionerà per ogni numero nell'intervallo di numeri a 32 bit.

Answer 2

Posso pensare ad alcune altre opzioni:

Esistono globalmente meno di 65536 voci nel database? In tal caso, è possibile mantenere una tabella di mapping che non è associata allo stato della sessione, ma è una parte persistente dell'applicazione.

La maggior parte delle voci negli indici è inferiore, diciamo 50.000? In tal caso, è possibile mappare direttamente tali valori e utilizzare una mappa associata alla sessione per i restanti.

Se il persistere di tali dati di sessione è un problema e il numero di client è ragionevolmente piccolo, è possibile abilitare l'affinità client / sessione e mantenere la mappa locale sul server.

Se non si tratta di un'applicazione Web, è possibile mantenere la mappa sul client stesso.

Non vedo alcun modo algoritmico che eviti le collisioni - sospetto che potresti sempre trovare degli esempi che potrebbero scontrarsi.

Answer 3

Quanto " più " di 65535 hai bisogno? Puoi sempre aggiungere solo alcuni bit dal campo "byte" " come bit di ordine superiore dell'ID. Solo 2 bit ti porterebbero a 262.143, 3 bit ti porterebbero a 524.287.