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

Question

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

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

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

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

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

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

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

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

Answer 1

Что касается подхода 2:

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

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

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

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

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

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

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

Answer 3

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