ترجمة Int32 إلى اختصار والعودة مرة أخرى

Question

أحاول ابتكار نظام لتعبئة القيم الصحيحة الأكبر من 65535 في ملف قصير.دعني أشرح.

لدينا نظام يقوم بإنشاء قيم Int32 باستخدام عمود IDENTITY من SQL Server وهو مقيد بواجهة برمجة تطبيقات العميل أثناء الإنتاج والتي تفيض معرفات Int32 الخاصة بنا إلى ushorts.لحسن الحظ، لدى العميل حوالي 20 مثيلًا فقط من الأشياء التي تحتوي على هذه المعرفات - دعنا نسميها الحزم - في أي وقت ويحتاج فقط إلى جعلها فريدة بين الأشقاء المحليين.الحل المقبول عمومًا هو ترجمة معرفات Int32 الخاصة بنا إلى اختصارات (لا أقصد الإرسال، أعني الترجمة) قبل إرسالها إلى العميل، ولكن هناك انتقادات لاذعة في هذا الأسلوب:

1. قد تظل بعض المعرفات الأقل من 65535 قيد التشغيل على عميل معين في أي وقت بسبب عدم انتهاء الصلاحية.
2. لا يمكن أن يكون لدينا أي تصادمات للمعرفات - أي إذا انتقل معرف الحزمة 1 إلى العميل، فإن الخوارزمية التي تتعقب عدد المرات التي تتم فيها إزالة 65535 من Int32 لإجراء اختصار عند تطبيقه على 65536 ستؤدي أيضًا إلى 1 وبالتالي التسبب في تصادم.
3. يجب أن نكون قادرين على إعادة بناء ushort في Int32 عند العودة.

ما لدينا لحل هذه المشكلة هو حقل بايت واحد موقّع يتم تكراره لنا ويمنحنا 127 قيمة للعب بها (117 حقًا لأننا نستخدم 0-9 لشيء آخر).سأشير إلى هذا باسم "حقل البايت" من الآن فصاعدًا.

لقد ناقشنا ثلاثة إجراءات ترجمة مختلفة:

1. مضاعف:قم بتخزين عدد المرات التي قمنا فيها بإزالة 65535 من Int32 الخاص بنا في حقل البايت لإنشاء اختصار.هذا لديه مشاكل الاصطدام كما هو مفصل أعلاه.
2. حالة الجلسة المتسلسلة:لكل عميل، قم بإنشاء معرف جلسة بناءً على حقائق حول هذا العميل.ثم قم بتخزين جدول ترجمة 1:1 بدءًا من 1 وحتى عدد الحزم التي تم تسليمها، لذلك عندما يصل العميل إلى خادمنا مرة أخرى، يمكن ترجمة مخزون الحزم مرة أخرى إلى معرفات قاعدة البيانات المعروفة الخاصة به.ينطوي هذا على مشكلات عامة نظرًا لأننا سندعم حالة الجلسة المتسلسلة لقاعدة بيانات ونريد دعم مئات إلى آلاف المعاملات في الثانية.
3. نهج خوارزمي متنوع حيث يكون حقل البايت هو معرف خوارزمية تحويلية تأخذ Int32 وتحوله إلى اختصار.من الواضح أن العديد من هذه المعرفات ستكون بسيطة مضروبة (لزيادة سقف المعرفات التي يمكننا تحويلها) ولكن بعضها يجب أن تكون مضروبة بحد أصغر (مثل 32768) مع إضافة رقم إلى/طرح منه للاقتراب من رقم الرقم الذي يمكن ضمانه فريدًا بين الأشقاء.يعتمد هذا الأسلوب على المعالج بشكل مكثف ولكنه يجب أن يسمح لنا بتجنب الاصطدامات مع الحفاظ على قابلية التوسع (على الرغم من أنه مع هذا النهج لدينا سقف محدود لن يتم الوصول إليه قبل أن تختفي المشكلة القصيرة من تلقاء نفسها بسبب الترقيات).

لذلك سؤالي هو:هل هناك طريقة أفضل من طرقي المذكورة أعلاه، وإذا لم يكن الأمر كذلك، فما الذي يجب أن أبحث عنه فيما يتعلق بالخوارزميات (للطريقة رقم 3) لإنشاء رقم بين 1-65535 عندما يكون الرقم المحدد أكبر من 0 ويجب ألا يكون كذلك تجزئة طريقة واحدة؟

إيضاح:ليس الأمر أن الحد الأقصى القصير هو المشكلة الأكبر، بل أن واجهة برمجة تطبيقات العميل تستخدم اختصارًا لذا لا يمكنني دمج حقل البايت على العميل للحصول على قيم أكبر (واجهة برمجة تطبيقات العميل غير قابلة للترقية ولكنها ستنتهي في النهاية من الوجود).

Answer 1

فيما يتعلق بالنهج 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 2

يمكنني التفكير في بعض الخيارات الأخرى:

هل يوجد على مستوى العالم أقل من 65536 إدخالاً في قاعدة البيانات؟إذا كان الأمر كذلك، فيمكنك الاحتفاظ بجدول التعيين غير المرتبط بحالة الجلسة، ولكنه جزء ثابت من التطبيق.

هل غالبية الإدخالات في الفهارس أقل من 50000، على سبيل المثال؟إذا كان الأمر كذلك، فيمكنك تعيين هذه القيم مباشرةً، واستخدام خريطة مرتبطة بالجلسة للقيم المتبقية.

إذا كان استمرار بيانات الجلسة يمثل مشكلة وكان عدد العملاء صغيرًا بشكل معقول، فيمكنك تمكين تقارب العميل/الجلسة والحفاظ على الخريطة المحلية للخادم.

إذا لم يكن تطبيق ويب، فيمكنك الاحتفاظ بالخريطة على العميل نفسه.

لا أرى أي طريقة خوارزمية من شأنها تجنب الاصطدامات - أظن أنه يمكنك دائمًا التوصل إلى أمثلة قد تتصادم.

Answer 3

ما مقدار "أكثر" من 65535 الذي تحتاجه؟يمكنك دائمًا إضافة بضع بتات من "حقل البايت" الخاص بك باعتبارها البتات ذات الترتيب العالي للمعرف.فقط 2 بت ستوصلك إلى 262,143، 3 بت ستوصلك إلى 524,287.