Перевод Int32 в ushort и обратно
Я пытаюсь разработать систему для упаковки целочисленных значений, превышающих 65535, в ushort. Позволь мне объяснить.
У нас есть система, которая генерирует значения Int32 с использованием столбца IDENTITY из SQL Server и ограничена производственным клиентским API, который переполняет наши идентификаторы Int32 до коротких. К счастью, клиент имеет около 20 или около того экземпляров вещей с этими идентификаторами - давайте назовем их пакетами - в любой момент времени, и ему нужно только, чтобы они были уникальными среди местных братьев и сестер. Общепринятым решением является преобразование наших идентификаторов Int32 в короткие (и нет, я не имею в виду приведение, я имею в виду перевод) перед передачей их клиенту, однако при таком подходе есть препятствия:
- Некоторые идентификаторы, меньшие 65535, могут все еще находиться в игре на данном клиенте в любое время из-за не истечения срока действия.
- У нас не может быть никаких коллизий идентификаторов - то есть, если пакетный идентификатор 1 отправляется клиенту, алгоритм, который отслеживает, сколько раз 65535 удаляется из Int32, чтобы сделать ushort при применении к 65536, также приведет к 1, что вызовет коллизию.
- Мы должны быть в состоянии восстановить ushort в Int32 по возвращении.
Для решения этой проблемы у нас есть одно подписанное байтовое поле, которое повторяется нам и дает нам 127 значений для игры (на самом деле 117, потому что мы используем 0-9 для чего-то еще). Я буду называть это "байтовым полем".
Мы обсудили три разные процедуры перевода:
- Мультипликативный: сохраните в байтовом поле, сколько раз мы удаляем 65535 из нашего Int32, чтобы сделать ushort. Это имеет проблемы со столкновением, как описано выше.
- Сериализованное состояние сеанса: для каждого клиента создайте идентификатор сеанса на основе фактов об этом клиенте. Затем сохраните таблицу перевода 1:1, начиная с 1 до количества доставленных пакетов, чтобы при повторном обращении клиента к нашему серверу инвентаризация пакетов могла быть преобразована обратно в их известные идентификаторы базы данных. Это связано с дополнительными проблемами, поскольку мы будем резервировать сериализованное состояние сеанса в базу данных и хотим поддерживать от сотен до тысяч транзакций в секунду.
- Разнообразный алгоритмический подход, где байтовое поле является идентификатором преобразовательного алгоритма, который принимает Int32 и преобразует его в ushort. Очевидно, что многие из них будут простыми мультипликативными (чтобы увеличить потолок идентификаторов, которые мы можем преобразовать), но некоторые должны будут быть мультипликативными с меньшей границей (например, 32768) с числом, добавленным к / вычтенным из, чтобы получить как можно ближе к число, которое может быть гарантировано уникальным среди братьев и сестер. Этот подход требует интенсивного использования процессора, но должен позволить нам избежать коллизий, оставаясь при этом масштабируемым (хотя при таком подходе мы имеем ограниченный потолок, который не будет достигнут до тех пор, пока проблема ushort не исчезнет сама по себе из-за обновлений).
Итак, мой вопрос: есть ли лучший способ, чем мои подходы выше, и если нет, то что я должен искать в терминах алгоритмов (для подхода № 3), чтобы генерировать число в диапазоне 1-65535, когда данное число больше, чем 0 а не должен быть односторонний хеш?
Пояснение: дело не в том, что верхний предел ushort является самой большой проблемой, а в том, что клиентский API использует ushort, поэтому я не могу объединить байтовое поле на клиенте, чтобы получить большие значения (клиентский API не подлежит обновлению, но в конечном итоге постепенно прекратит свое существование).
3 ответа
Что касается подхода 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-битных чисел.
Я могу придумать еще несколько вариантов:
Есть ли в мире менее 65536 записей в базе данных? Если это так, то вы можете сохранить таблицу сопоставления, которая не связана с состоянием сеанса, но является постоянной частью приложения.
Большинство записей в индексах меньше, скажем, 50000? Если это так, вы можете отобразить такие значения напрямую и использовать карту, связанную с сеансом, для остальных.
Если сохранение таких данных сеанса является проблемой, и число клиентов достаточно мало, вы можете включить привязку клиент / сеанс и сохранить карту локально для сервера.
Если это не веб-приложение, вы можете сохранить карту на самом клиенте.
Я не вижу какого-либо алгоритмического способа избежать столкновений - я подозреваю, что вы всегда можете придумать примеры, которые будут сталкиваться.
Сколько "больше" чем 65535 вам нужно? Вы всегда можете просто добавить несколько бит из своего "поля байтов" в качестве старших битов идентификатора. Всего 2 бита дадут вам 262 143, 3 бита - 524 287.