Int32 を ushort に変換して再度元に戻す

Question

65535 より大きい整数値を ushort にパックするシステムを考案しようとしています。説明しましょう。

SQL Server の IDENTITY 列を使用して Int32 値を生成するシステムがありますが、運用中のクライアント API によって Int32 ID が ushort にオーバーフローするという制限があります。幸いなことに、クライアントにはこれらの ID を持つインスタンス (パッケージと呼びましょう) が常に 20 程度しかなく、ローカルの兄弟間で一意にする必要があるだけです。一般に受け入れられている解決策は、クライアントに送信する前に、Int32 ID を ushort に変換することです (キャストという意味ではなく、翻訳という意味です)。ただし、このアプローチにはとげがあります。

1. 65535 未満の一部の ID は、有効期限がないため、特定のクライアントでいつでも使用できる可能性があります。
2. ID の衝突は発生しません。つまり、パッケージ ID 1 がクライアントに渡される場合、ushort を作成するために 65535 が Int32 から削除される回数を追跡するアルゴリズムが 65536 に適用されると、結果も 1 となり、衝突が発生します。
3. 戻ったときに ushort を Int32 に再構築できなければなりません。

この問題を解決するために利用できるのは、エコーされて 127 個の値を提供する単一の符号付きバイト フィールドです (0 ～ 9 を別の目的で使用しているため、実際には 117 個です)。以降、これを「バイトフィールド」と呼びます。

3 つの異なる変換ルーチンについて説明しました。

1. 乗法：ushort を作成するために Int32 から 65535 を削除する回数をバイト フィールドに格納します。これには、上で説明したように衝突の問題があります。
2. シリアル化されたセッション状態:クライアントごとに、そのクライアントに関する事実に基づいてセッション ID を生成します。次に、1 から配送されたパッケージの数までの 1:1 変換テーブルを保存します。これにより、クライアントがサーバーに再度アクセスしたときに、パッケージの在庫を既知のデータベース ID に変換して戻すことができます。シリアル化されたセッション状態をデータベースにバックアップし、1 秒あたり数百から数千のトランザクションをサポートする必要があるため、これにはオーバーヘッドの問題があります。
3. バイト フィールドが Int32 を取得して ushort に変換する変換アルゴリズムの ID である、さまざまなアルゴリズムのアプローチ。明らかに、これらの多くは単純な乗算になります (変換できる ID の上限を増やすため)。ただし、一部のものは、より小さい境界 (32768 など) で乗算し、数値にできるだけ近づけるために数値を加算/減算する必要があります。兄弟間で一意であることが保証できる番号。このアプローチはプロセッサを大量に消費しますが、スケーラビリティを維持しながら衝突を回避できるはずです (ただし、このアプローチでは、アップグレードによって ushort の問題が自然に解決するまでは到達しない制限された上限があります)。

そこで私の質問は次のとおりです。上記の私のアプローチよりも良い方法はありますか?そうでない場合、特定の数値が 0 より大きく、0 より大きくてはいけない場合に 1 ～ 65535 の数値を生成するアルゴリズム (アプローチ #3) に関して何を探す必要がありますか?一方向ハッシュ?

説明:ushort の上限が最大の問題であるというわけではありません。クライアント API が ushort を使用しているため、クライアントのバイト フィールドを組み合わせてより大きな値を取得できないことが原因です (クライアント API はアップグレードできませんが、最終的には廃止されます)。

Answer 1

アプローチ 2 について:

2 番目のアプローチは、NAT の仕組みとほぼ同じです。ローカル ネットワーク上のすべての TCP/UDP クライアントは、最大 65535 個のポート (ポート 0 を除く) とプライベート IP を使用します。ルーターは単一のパブリック IP のみを認識します。2 つのクライアントが両方とも送信元ポート 300 を持っている可能性があるため、単純にプライベート IP をパブリック IP に置き換えることはできず、衝突が発生します。したがって、IP を置き換えてポートを「変換」します (NAT:ネットワークアドレス 翻訳）。戻り時に、パッケージを転送する前に、ポートを変換して戻し、パブリック IP をプライベート IP に再度置き換えます。あなたはそれ以外何もしていないでしょう。ただし、ルーターはその情報をメモリに保持しており、NAT を実行してもそれほど遅くはありません (数百台のコンピューターを所有する企業では、インターネットに NAT 接続することがありますが、ほとんどの場合、速度の低下はほとんど顕著ではありません)。1 秒あたり最大 1,000 件のトランザクションが必要だと言いましたが、クライアントは何件あるのでしょうか?これは主に、マッピングのバックアップに必要なメモリのサイズを定義します。クライアントが多すぎない場合は、ソートされたテーブルを使用したマッピングをメモリ内に保持できます。その場合、速度が最も小さな問題になります (テーブルが大きくなり、サーバーのメモリ不足がより大きな問題になります)。

ちょっとわかりにくいのは、あなたがかつてこう言ったことです。

幸いなことに、クライアントはこれらのIDを使用して約20個のインスタンスしかありません - パッケージと呼びましょう - いつでも、地元の兄弟の間でユニークなだけである必要があります。

しかし、その後あなたは言います

65535未満の一部のIDは、非expirationのため、いつでも特定のクライアントで機能している可能性があります。

おそらく 2 番目のステートメントが言いたかったのは、クライアントが ID 65536 をリクエストした場合、65535 未満の ID がまだある可能性があり、それらの ID は (たとえば) 20 に達する可能性があるということです。クライアントが ID を順番に処理するわけではありませんね。つまり、現在 65536 を要求しているからといって、それよりも小さい値がある可能性はあるものの、1 ～ 1000 の範囲内にあるわけではない、とは言えませんよね?実際には 20、90、2005、および 41238 への参照を保持しながらも 65535 を超えている可能性があります。それが意味するところですか?

私は個人的には 3 番目のアプローチよりも 2 番目のアプローチの方が好きです。どのような場合でも衝突を避けるのが簡単で、数値を逆に変換するのは明白で単純な操作だからです。ただし、3 番目のアプローチが長期的には機能するとは思えません。数値の 2^16 を減算した頻度を格納するバイトがあるかもしれません。ただし、最大の数値として減算できるのは 117 * 2^16 のみです。数字がそれを超えたらどうしますか？別のアルゴリズムを使用すると、減算は行われませんが、何が行われるでしょうか?分ける？シフトビット？その場合、粒度が失われます。つまり、このアルゴリズムは実行できません。 打つ これ以上は任意の数を指定できます (大きくジャンプします)。32 ビットに魔法の変換関数を適用して、そこから 16 ビット (+ 1 バイト追加) を作成し、それを元に変換するだけが非常に簡単であれば、この世界のすべての圧縮方法で、可能な限りそれが使用されると思います。 32 ビットの数値が何であっても、必ず 24 ビット (16 ビット + 1 バイト) に圧縮してください。それは魔法でしょう。32 ビットを 24 ビットにパックし、それを変換して戻すためのすべてのロジックもパックすることはできません。外部ストレージが必要になるため、2 番目のアプローチに戻ります。これが機能する唯一のアプローチであり、32 ビット数値範囲内のすべての数値に対して機能します。

Answer 2

他にもいくつかの選択肢が考えられます。

データベース内のエントリは全体的に 65536 未満ですか?そうであれば、セッション状態に関連付けられていないが、アプリケーションの永続化された部分であるマッピング テーブルを維持できます。

インデックスのエントリの大部分は、たとえば 50,000 未満ですか?その場合は、そのような値を直接マップし、残りの値にはセッションに関連付けられたマップを使用できます。

このようなセッション データの永続化が問題であり、クライアントの数がかなり少ない場合は、クライアント/セッション アフィニティを有効にして、マップをサーバーに対してローカルに維持できます。

Web アプリケーションではない場合は、クライアント自体でマップを維持できます。

衝突を回避するアルゴリズム的な方法は見当たりません。衝突する例はいつでも思いつくことができると思います。

Answer 3

65535 よりどれだけ「多い」必要があるでしょうか?いつでも「バイト フィールド」から数ビットを ID の上位ビットとして追加することができます。2 ビットだけだと 262,143、3 ビットだと 524,287 になります。