Перевод Int32 в ushort и обратно

Question

Я пытаюсь разработать систему для упаковки целых значений, превышающих 65535, в ushort. Позвольте мне объяснить.

У нас есть система, которая генерирует значения Int32, используя столбец IDENTITY из SQL Server, и ограничена производственным клиентским API, который переполняет наши идентификаторы Int32 до коротких. К счастью, клиент имеет около 20 или около того экземпляров вещей с этими идентификаторами - давайте назовем их пакетами - в любой момент времени, и ему нужно только, чтобы они были уникальными среди местных братьев и сестер. Общепринятым решением является перевод наших идентификаторов Int32 в ushorts (и нет, я не имею в виду приведение, я имею в виду перевод) перед передачей их клиенту, однако при таком подходе есть недостатки:

1. Некоторые идентификаторы, меньшие 65535, могут по-прежнему использоваться для данного клиента в любое время из-за не истечения срока действия.
2. У нас не может быть никаких коллизий идентификаторов - то есть, если пакет ID 1 отправляется клиенту, алгоритм, который отслеживает, сколько раз 65535 удаляется из Int32, чтобы сделать ushort при применении к 65536, также приведет к 1, таким образом вызывая столкновение.
3. Мы должны быть в состоянии восстановить ushort в Int32 по возвращении.

То, что у нас есть для решения этой проблемы, - это поле со знаком в виде одного байта, которое повторяется нам и дает нам 127 значений для игры (на самом деле 117, потому что мы используем 0-9 для чего-то еще). Я буду называть это «байтовым полем» с этого момента.

Мы обсудили три различные процедуры перевода:

1. Multiplicative: сохраните в байтовом поле, сколько раз мы удаляем 65535 из нашего Int32, чтобы сделать ushort. Это имеет проблемы столкновения, как описано выше.
2. Сериализированное состояние сеанса: для каждого клиента создайте идентификатор сеанса на основе фактов об этом клиенте. Затем сохраните таблицу перевода 1: 1, начиная с 1 до количества доставленных пакетов, чтобы при повторном обращении клиента к нашему серверу инвентаризация пакетов могла быть преобразована обратно в их известные идентификаторы базы данных. Это связано с дополнительными проблемами, поскольку мы выполняем резервное копирование сериализованного состояния сеанса в базу данных и хотим поддерживать от сотен до тысяч транзакций в секунду.
3. Разнообразный алгоритмический подход, где байтовое поле является идентификатором преобразовательного алгоритма, который принимает Int32 и преобразует его в ushort. Очевидно, что многие из них будут простыми Мультипликативными (чтобы увеличить наш потолок идентификаторов, которые мы можем преобразовать), но некоторые должны будут быть мультипликативными с меньшей границей (как 32768) с числом, добавленным к / вычтенным из, чтобы получить как можно ближе к число, которое может быть гарантировано уникальным среди братьев и сестер. Этот подход требует интенсивного использования процессора, но должен позволить нам избежать коллизий, оставаясь при этом масштабируемым (хотя при таком подходе мы имеем ограниченный потолок, который не будет достигнут, пока проблема ushort не исчезнет сама по себе из-за обновлений).

Итак, мой вопрос: есть ли лучший способ, чем мои подходы, описанные выше, и если нет, то что я должен искать в терминах алгоритмов (для подхода № 3), чтобы генерировать число в диапазоне 1-65535, когда данное число больше 0 и не должен быть односторонним хешем?

Пояснение: дело не в том, что верхний предел ushort является самой большой проблемой, а в том, что клиентский API использует ushort, поэтому я не могу объединить байтовое поле на клиенте, чтобы получить большие значения (клиентский API не подлежит обновлению, но в конечном итоге будет фазироваться из существования).

Answer 1

Я могу придумать несколько других вариантов:

Есть ли в мире менее 65536 записей в базе данных? Если это так, то вы можете поддерживать таблицу сопоставления, которая не связана с состоянием сеанса, но является постоянной частью приложения.

Большинство записей в индексах меньше, скажем, 50000? Если это так, вы можете отобразить такие значения напрямую и использовать карту, связанную с сеансом, для остальных.

Если сохранение таких данных сеанса является проблемой, и число клиентов достаточно мало, вы можете включить привязку клиента / сеанса и сохранить карту локально для сервера.

Если это не веб-приложение, вы можете сохранить карту на самом клиенте.

Я не вижу никакого алгоритмического способа избежать столкновений - я подозреваю, что вы всегда можете придумать примеры, которые столкнутся.

Answer 2

Относительно подхода 2:

Ваш второй подход заключается в том, как работает NAT. Каждый TCP / UDP-клиент в локальной сети имеет до 65535 используемых портов (кроме порта 0) и частный IP-адрес. Маршрутизатор знает только один публичный IP-адрес. Поскольку оба клиента могут иметь исходный порт 300, он не может просто заменить частный IP общедоступным, что может привести к возникновению коллизий. Таким образом он заменяет IP и «переводит» порт (NAT: сетевой адрес трансляция ). По возвращении он переводит порт обратно и снова заменяет общедоступный IP-адрес частным, прежде чем пересылать пакет обратно. Вы не будете делать ничего другого, кроме этого. Тем не менее, маршрутизаторы хранят эту информацию в памяти - и они не слишком медленны при выполнении NAT (компании с сотнями компьютеров иногда подключаются к Интернету, и в большинстве случаев замедление едва ли заметно). Вы говорите, что хотите до тысячи транзакций в секунду, но сколько будет клиентов? Поскольку это в основном будет определять размер памяти, необходимый для резервного копирования сопоставлений. Если клиентов не слишком много, вы можете сохранить отображение с отсортированной таблицей в памяти, в этом случае скорость будет наименьшей проблемой (размер таблицы увеличивается, а на сервере не хватает памяти).

Что мне немного неясно, так это то, что вы однажды сказали

К счастью, клиент имеет только около 20 или около того случаев с эти идентификаторы - давайте назовем их пакеты - в любой момент времени, и это нужно только они уникальны среди местных братья и сестры.

но тогда вы говорите

Некоторые идентификаторы меньше 65535 все еще могут быть в игре на данном клиенте в любое время из-за не истечения срока действия.

Полагаю, что вы, вероятно, подразумевали под вторым утверждением, что если клиент запрашивает идентификатор 65536, он все равно может иметь идентификаторы ниже 65535, и они могут быть столь же низкими, как (скажем) 20. Клиент не обрабатывает Идентификаторы в прямом порядке, верно? Таким образом, вы не можете сказать, просто потому, что он теперь запросил 65536, он может иметь некоторые меньшие значения, но, конечно, не в диапазоне 1-1000, правильно? Это может на самом деле сохранить ссылку на 20, 90, 2005 и 41238 и все же перейти на 65535, это то, что вы имели в виду?

Мне лично ваш второй подход больше, чем третий, так как в любом случае легче избежать столкновения, а перевод числа назад - простая и простая операция. Хотя я сомневаюсь, что ваш третий подход может работать в долгосрочной перспективе. Хорошо, у вас может быть байт для хранения того, как часто вы вычитаете 2 ^ 16 из числа. Однако вы можете только вычесть 117 * 2 ^ 16 как наибольшее число. Что вы будете делать, если цифры превысят это? Используя другой алгоритм, это не вычитает, но что делает? Делить? Биты сдвига? В этом случае вы теряете гранулярность, это означает, что этот алгоритм больше не может поражать любое возможное число (оно будет делать большие скачки). Если бы было так просто просто применить магическую функцию перевода к 32-битной системе, чтобы получить из нее 16-битную (+ один дополнительный байт), а затем просто преобразовать ее обратно, думаю, что каждый метод сжатия в этом мире будет использовать ее, как мог бы, нет Независимо от того, каким было 32-битное число, всегда сжимайте его до 24-битного (16 бит + один байт). Это было бы волшебно. Невозможно упаковать 32 бит в 24 бит, а также упаковать всю логику, как преобразовать его обратно в него. Вам понадобится некоторое внешнее хранилище, которое возвращает нас к вашему второму подходу. Это единственный подход, который будет работать, и он будет работать для каждого числа в диапазоне 32-битных чисел.

Answer 3

Сколько "больше" чем 65535 вам нужно? Вы всегда можете просто добавить несколько бит из своего «поля байтов» в качестве старших битов идентификатора. Всего 2 бита дадут вам 262 143, 3 бита - 524 287