Traduzindo Int32 em ushort e vice-versa

Question

Eu estou tentando criar um sistema para embalar valores inteiros maiores do que 65535 em um ushort. Deixe-me explicar.

Temos um sistema que gera Int32 valores utilizando uma coluna de identidade de SQL Server e são limitados por uma API cliente em produção que transborda a nossa Int32 IDs para ushorts. Felizmente o cliente tem apenas cerca de 20 ou mais instâncias de tudo com essas IDs - chamada de deixá-los pacotes - a qualquer momento e ele só precisa tê-los o único entre os irmãos locais. A solução geralmente aceite é o de traduzir o nosso Int32 IDs para ushorts (e não faço fundição não significa, eu traduzir média) antes de os transmitir para o cliente, no entanto, existem farpas com esta abordagem:

1. Alguns IDs menos de 65535 ainda pode estar em jogo em um determinado cliente, a qualquer momento devido a não-validade.
2. Não podemos ter nenhum colisões ID - isto é, se ID pacote 1 vai para o cliente, um algoritmo que faixas quantas vezes 65535 é removida de um Int32 para fazer uma ushort quando aplicado a 65536 também resultaria em 1 causando, assim, uma colisão.
3. Temos de ser capazes de reconstruir o ushort para o Int32 em cima do retorno.

O que temos disponível para resolver este problema é um campo único byte assinado que é ecoado para nós e nos dá 127 valores de jogar com (realmente 117 porque estamos usando 0-9 para outra coisa). Vou me referir a isso como o "campo de byte" de agora em diante.

Nós discutimos três rotinas de tradução diferentes:

1. multiplicativo: loja no campo byte quantas vezes nós removemos 65535 da nossa Int32 para fazer uma ushort. Isto tem problemas de colisão, conforme detalhado acima.
2. Serialized Estado de sessão: para cada cliente, gerar um ID de sessão baseado em fatos sobre esse cliente. Em seguida, armazenar um 1: Tabela 1 a tradução a partir de 1 até o número de pacotes entregues por isso, quando o cliente acessa o nosso servidor novamente o inventário de pacotes pode ser traduzido de volta para seus IDs do banco de dados conhecidos. Isto tem problemas gerais, uma vez que estaria apoiando o estado da sessão serializado para um banco de dados e queremos apoiar centenas de milhares de transações por segundo.
3. variado abordagem algorítmica onde o campo byte é um ID de um algoritmo de transformação que leva um Int32 e transforma-lo em um ushort. Obviamente muitos destes vão ser simples multiplicativo (para aumentar nosso teto de IDs podemos transformar), mas alguns terão de ser multiplicativo com um boundry menor (como 32768) com um número adicionado / subtraído para obter tão perto de um número que pode ser garantido o único entre os irmãos. Esta abordagem é processador intensivo, mas deverá permitir-nos para evitar colisões enquanto restantes escalável (embora com esta abordagem, temos um teto limitado que não será alcançado antes de o problema ushort vai embora por conta própria devido a upgrades).

Então, minha pergunta é: se existe uma maneira melhor do que meus abordagens acima, e se não, o que eu deveria estar procurando em termos de algoritmos (para abordagem # 3) para gerar um número entre 1-65535 quando um determinado número é maior do que 0 e não deve ser um hash one-way?

Esclarecimento: sua fase não que o teto ushort é o maior problema, a que a API cliente utiliza um ushort por isso não pode combinar o campo byte no cliente para obter valores maiores (a API do cliente é não-atualizável, mas acabará por fora da existência).

Answer 1

Quanto abordagem 2:

Seu segunda abordagem é muito bonito como funciona o NAT. Cada cliente TCP / UDP na rede local tem até 65.535 portas em uso (exceto a porta 0) e um IP privado. O roteador conhece apenas um único IP público. Uma vez que dois clientes podem ambos têm porta de origem 300, ele não pode simplesmente substituir o IP privada com um público, que poderia causar colisões a aparecer. Assim, ele substitui o IP e "traduz" a porta (NAT: Network Address Tradução ). No retorno, traduz parte de trás da porta e substitui o público com um IP privado, novamente, antes de encaminhar a parte de trás do pacote. Você estaria fazendo nada mais do que isso. No entanto, os roteadores manter essa informação na memória - e eles não são muito lento ao fazer NAT (empresas com centenas de computadores são NATed à Internet, por vezes, ea desaceleração é dificilmente perceptível na maioria dos casos). Você diz que quer até mil transações por segundo - mas quantos clientes vão haver? Como este, principalmente, vai definir o tamanho da memória necessária para fazer o backup dos mapeamentos. Se não há também muitos clientes, você pode manter o mapeamento com uma tabela ordenada na memória, nesse caso, a velocidade será o menor problema (tabela chegar ao maior e servidor ficar sem memória é o maior).

O que é um pouco claro para mim é que você uma vez digamos

Felizmente, o cliente só tem cerca de 20 ou mais instâncias de coisas com essas identificações - vamos chamá-los de pacotes - a qualquer tempo e ele só precisa tê-los o único entre os locais irmãos.

mas então você diz

Alguns IDs menos de 65535 ainda pode ser em jogo em um determinado cliente, a qualquer momento devido a não-validade.

Eu acho que, o que você provavelmente quis dizer com a segunda declaração é que, se um solicitações do cliente ID 65536, ele ainda pode ter IDs abaixo 65535 e estes podem ser tão baixa quanto (digamos) 20. Não é que os processos de cliente IDs em uma ordem reta, certo? Então você não pode dizer, só porque agora solicitado 65536, ele pode ter alguns valores menores, mas certamente não na faixa 1-1000, correto? Ele pode realmente manter uma referência a 20, 90, 2005 e 41238 e ainda passar por cima de 65535, que é o que você quis dizer?

Eu, pessoalmente, como sua segunda abordagem mais do que o terceiro, como é mais fácil para evitar uma colisão em qualquer caso e traduzir o número de volta é uma operação simples, simples. Embora eu duvide que a sua terceira abordagem pode funcionar a longo prazo. Ok, você pode ter um byte para armazenar quantas vezes você subtraído 2 ^ 16 do número. No entanto, você só pode subtrair 117 * 2 ^ 16 como maiores números. O que você vai fazer se os números vão acima disso? Usando um algoritmo diferente, que não subtrair, mas faz o quê? Dividir? pedaços turno? Nesse caso, você perder granularidade, isso significa que este algoritmo não pode hit qualquer número possível por mais tempo (ele vai fazer grandes saltos). Se fosse tão fácil simplesmente aplicar uma função de tradução mágica em cima de 32 bits para fazer 16 bits a partir dele (+ um byte extra) e, em seguida, apenas transformá-lo de volta, acho que cada método de compressão neste mundo iria utilizá-lo, como ele podia, sem importa que o número de 32 bits foi, sempre comprimi-lo para baixo para 24 bits (16 bits + um byte). Isso seria mágico. Não é possível para embalar de 32 bits para 24 bits e também embalar toda a lógica de como transformá-lo de volta para ele também. Você vai precisar de algum tipo de armazenamento externo, o que nos leva de volta para sua segunda abordagem. Esta é a única abordagem que vai trabalhar e ele vai trabalhar para cada número no intervalo de números de 32 bits.

Answer 2

Não consigo pensar em algumas outras opções:

Existem globalmente menos de 65536 entradas no banco de dados? Se assim for, então você pode manter uma tabela de mapeamento que não está associado com o estado da sessão, mas é uma parte persistente da aplicação.

são a maioria das entradas em índices menos de, digamos, 50.000? Se for esse o caso, você pode mapear esses valores diretamente, e usar um mapa associado com a sessão para os restantes.

Se persistindo tais dados da sessão é um problema e o número de clientes é razoavelmente pequeno, você pode permitir que o cliente afinidade / sessão e manter o mapa local para o servidor.

Se não é uma aplicação web, você pode manter o mapa no próprio cliente.

Eu não vejo nenhuma maneira algorítmica que evitar colisões -. Eu suspeito que você poderia sempre vêm com um exemplos que iria colidir

Answer 3

Quanto "mais" do que 65535 que você precisa? Você pode sempre basta adicionar alguns pedaços de seu "campo de byte" como os bits de alta ordem do ID. Apenas 2 bits iria levá-lo a 262.143, 3 bits que você obtenha 524.287.