La traducción Int32 en ushort y de vuelta otra vez

Question

Estoy tratando de diseñar un sistema para el embalaje de valores enteros mayores a 65535 en un ushort.Me explico.

Tenemos un sistema que genera valores Int32 el uso de una columna de IDENTIDAD de SQL Server y están limitados en la producción de la API de cliente que desborda nuestra Int32 Identificadores de ushorts.Afortunadamente, el cliente sólo tiene alrededor de 20 o más instancias de cosas con estos IDs - vamos a llamarlos paquetes en cualquier momento y sólo necesita tener únicos entre los locales de los hermanos.La aceptación general de la solución es convertir nuestro Int32 Identificadores de ushorts (y no, no me refiero a los casting, me refiero a la traducción) antes de transmitir al cliente, sin embargo hay barbas con este enfoque:

1. Algunos Identificadores de menos de 65535 todavía puede estar en juego en un determinado cliente en cualquier momento debido a la falta de expiración.
2. No podemos tener ningún tipo de IDENTIFICACIÓN colisiones, es decir si el ID de paquete 1 va para el cliente, un algoritmo que realiza un seguimiento de cuántas veces 65535 se retira de un Int32 para hacer un ushort cuando se aplica a 65536 también se traduciría en 1, causando una colisión.
3. Debemos ser capaces de reconstruir la ushort en el Int32 tras el retorno.

Lo que tenemos disponible para resolver este problema es de un solo byte con signo de campo que se hizo eco y nos da 127 valores a jugar con (realmente 117 debido a que estamos usando las teclas 0-9 para algo más).Me voy a referir a esto como el "campo de byte" de aquí en adelante.

Hemos hablado de tres diferentes rutinas de traducción:

1. Multiplicativo:tienda en el campo de byte cuántas veces nos quite 65535 de nuestro Int32 para hacer un ushort.Esto ha colisión problemas detallados anteriormente.
2. Serializa El Estado De La Sesión:para cada cliente, generar un IDENTIFICADOR de sesión basada en hechos acerca de ese cliente.A continuación, almacenar un 1:1 de la tabla de traducción a partir del 1 hasta el número de paquetes entregados, así que cuando el cliente acceda a nuestro servidor de nuevo el inventario de paquetes puede ser traducida a su conocida base de datos de Identificadores.Este tiene sobrecarga de problemas, ya que nos gustaría ser la copia serializada del estado de la sesión a una base de datos y queremos apoyar a los cientos de miles de transacciones por segundo.
3. Variada aproximación algorítmica donde el byte de campo es un IDENTIFICADOR de un transformador algoritmo que toma un Int32 y la transforma en una ushort.Obviamente muchos de estos van a ser simples Multiplicativo (para aumentar nuestro techo de IDs podemos transformar), pero algunos tendrán que ser multiplicativa con un menor boundry (como 32768) con un número, sumado/restado de acercarse a un número que puede ser garantizado único entre los hermanos.Este enfoque es el uso intensivo del procesador, pero nos debe permitir evitar colisiones mientras que los restantes escalable (a pesar de que con este enfoque se ha limitado techo que no se alcanza antes de la ushort problema desaparece por su propia cuenta debido a las mejoras).

Así que mi pregunta es:hay una manera mejor de mis planteamientos anteriores, y si no, ¿a qué debo estar buscando en términos de algoritmos de enfoque #3) generar un número entre 1 a 65535 cuando un número es mayor que 0 y no debe ser un hash de una vía?

Aclaración:no es que el ushort techo es el mayor problema, su que el cliente de la API utiliza un ushort así que no puedo combinar el campo de byte en el cliente para obtener más valores (el cliente de la API no es actualizable, pero finalmente la fase de existencia).

Answer 1

Respecto al enfoque de las 2:

El segundo enfoque es más o menos como funciona NAT.Cada TCP/UDP del cliente en la red local tiene hasta 65535 puertos que están en uso (excepto el puerto 0) y una IP privada.El router sólo conoce una sola IP pública.Desde dos clientes pueden tener el puerto de origen de 300, no puede simplemente reemplazar la IP privada con la pública, que podría causar colisiones a aparecer.Así, se sustituye la IP y "traduce" el puerto (NAT:Dirección De Red Traducción).En cambio, traduce el puerto de nuevo y reemplaza al público con una dirección IP privada de nuevo, antes de reenviar el paquete.Usted estaría haciendo nada más que eso.Sin embargo, los routers de mantener esa información en la memoria - y de que no sean demasiado lento al hacer NAT (empresas con cientos de equipos son Coordinadas a la Internet a veces y la desaceleración es apenas notable en la mayoría de los casos).Usted dice que quiere hasta miles de transacciones por segundo - pero, ¿cuántos clientes habrá?Como esto se va a definir el tamaño de la memoria necesaria para la copia de seguridad de las asignaciones.Si no hay demasiados clientes, se podría mantener la asignación de una tabla ordenada en la memoria, en ese caso, la velocidad va a ser el menor de los problemas (tabla llegar a más, y servidor que ejecuta fuera de la memoria es el más grande).

Lo que es poco claro para mí es que una vez que dicen

Afortunadamente, el cliente sólo tiene acerca de 20 o más instancias de las cosas con estos IDs - vamos a llamarlos paquetes - en cualquier momento dado y sólo necesita tienen ellos es único entre locales hermanos.

pero luego te dicen

Algunos Identificadores de menos de 65535 todavía puede ser en juego en un determinado cliente en cualquier momento debido a la falta de expiración.

Supongo que, lo que probablemente significa que la segunda declaración es, que si un cliente solicita un IDENTIFICADOR de 65536, puede ser que todavía tienen Identificadores de abajo 65535 y estos pueden ser tan bajos como los de (digamos) 20.No es que el cliente los procesos de Identificadores en un recto orden, ¿verdad?Así que usted no puede decir, porque ahora solicitado 65536, puede tener algunos valores más pequeños, pero ciertamente no en el rango 1-1000, ¿correcto?En realidad, puede mantener una referencia a las 20, 90, 2005 y 41238 y todavía ir más de 65535, que es lo que quiso decir?

Personalmente, me gusta su segundo enfoque, más que el tercero, ya que es más fácil para evitar una colisión, en cualquier caso, y traducir el número de la espalda es una simple operación.Aunque dudo que su tercer enfoque puede funcionar en el largo plazo.Bien, usted puede tener un byte para almacenar con qué frecuencia se resta 2^16 de la serie.Sin embargo, sólo puede restar 117 * 2^16 números más grandes.¿Qué vas a hacer si los números van por encima de eso?Usando un algoritmo diferente, que no restar, pero ¿qué?Dividir?Cambio de los bits?En ese caso se pierden granularidad, que significa que este algoritmo no puede hit cualquier número posible por más tiempo (es de hacer grandes saltos).Si era tan fácil solo tienes que aplicar una magia función de traducción en 32 bits para hacer 16 bits de ella (+ un byte adicional) y, a continuación, sólo transformar de nuevo, imagino que cada método de compresión en este mundo lo usan, como podría, no importa lo que el número de 32 bits fue, siempre comprimirlo a 24 bits (16 bits + un byte).Eso sería magia.No es posible pack de 32 bits a 24 bits y también el pack de toda la lógica de cómo transformarla en ella.Usted necesitará algunas de almacenamiento externo, el cual nos trae de vuelta a su 2do enfoque.Este es el único enfoque que va a funcionar y va a trabajar para cada número en número de 32 bits rango.

Answer 2

No puedo pensar en un par de otras opciones:

Existen a nivel mundial, menos de 65536 entradas en la base de datos?Si es así, entonces usted podría mantener una tabla de asignación que no está asociada con el estado de la sesión, pero es un persistió parte de la aplicación.

La mayoría de las entradas en los índices de menos de, digamos 50,000?Si ese es el caso, usted podría asignar estos valores directamente, y el uso de un mapa asociado con la sesión para el resto.

Si se mantienen los datos de la sesión es un problema y el número de clientes es razonablemente pequeño, se puede habilitar el cliente/la afinidad de sesión y mantener el mapa de local en el servidor.

Si no es una aplicación web, se podría mantener el mapa en el propio cliente.

Yo no veo ninguna algorítmica de manera que se evite colisiones - sospecho que usted siempre puede venir para arriba con un ejemplo que colisionen.

Answer 3

Cuánto "más" que 65535 necesita?Usted siempre puede simplemente añadir un par de bits a partir de su "campo de byte" como los bits de orden alto de la ID.Sólo 2 bits te llevaría a 262,143, 3 bits se le 524,287.