البحث الرئيسي في هذه المقالة هو رمز الخوارزمية المتناسقة.
تم اقتراح خوارزمية التجزئة الثابتة من قبل معهد ماساتشوستس للتكنولوجيا في عام 1997 (انظر 0). كان هدف التصميم هو حل مشكلة Hotpot في الإنترنت ، وكانت نيتها الأصلية مشابهة جدًا لـ CARP. يقوم التجزئة المتسقة بتصحيح المشكلة الناجمة عن خوارزمية التجزئة البسيطة التي يستخدمها CARP ، بحيث يمكن تطبيق DHT حقًا في بيئات P2P.
يقترح التجزئة المتسقة أربعة شروط تكيفية يجب أن تلبيها خوارزمية التجزئة في بيئة ذاكرة التخزين المؤقت المتغيرة ديناميكيًا:
يعني التوازن أنه يمكن توزيع نتيجة التجزئة على جميع ذاكرة التخزين المؤقت قدر الإمكان ، بحيث يمكن استخدام جميع مساحة ذاكرة التخزين المؤقت. يمكن للعديد من خوارزميات التجزئة تلبية هذا الشرط.
تشير الرتابة إلى ما إذا كان قد تم إرسال بعض المحتوى إلى ذاكرة التخزين المؤقت المقابلة من خلال التجزئة ، وتتم إضافة ذاكرة التخزين المؤقت الجديدة إلى النظام. يجب أن تضمن نتيجة التجزئة أن المحتوى المخصص الأصلي يمكن تعيينه إلى ذاكرة التخزين المؤقت الجديدة دون أن يتم تعيينه إلى المخازن المؤقتة الأخرى في مجموعة ذاكرة التخزين المؤقت القديمة.
غالبًا ما لا تستطيع خوارزميات التجزئة البسيطة تلبية متطلبات الرتابة ، مثل أبسط التجزئة الخطية:
x → ax + b mod (p)
في الصيغة أعلاه ، تمثل P حجم جميع ذاكرة التخزين المؤقت. ليس من الصعب أن نرى أنه عندما يتغير حجم ذاكرة التخزين المؤقت (من P1 إلى P2) ، ستتغير جميع نتائج التجزئة الأصلية ، وبالتالي لا تلبي متطلبات الرتابة.
التغييرات في نتائج التجزئة تعني أنه عندما تتغير مساحة ذاكرة التخزين المؤقت ، يجب تحديث جميع علاقات التعيين في النظام. في أنظمة P2P ، تعادل تغييرات ذاكرة التخزين المؤقت للانضمام إلى النظام أو الخروج من النظام. يحدث هذا الموقف بشكل متكرر في أنظمة P2P ، والتي ستجلب حمولة حوسبة ونقل ضخمة. تتطلب رتابة أن خوارزمية التجزئة يمكن أن تتجنب هذا الموقف.
في بيئة موزعة ، قد لا ترى المحطة جميع ذاكرة التخزين المؤقت ، ولكن يمكن أن ترى بعضها فقط. عندما ترغب المحطة في تعيين محتوى إلى ذاكرة التخزين المؤقت من خلال عملية التجزئة ، نظرًا لأن نطاق ذاكرة التخزين المؤقت التي تراها أطراف مختلفة قد تكون مختلفة ، فإن نتيجة التجزئة غير متسقة. والنتيجة النهائية هي أن نفس المحتوى يتم تعيينه في مناطق ذاكرة التخزين المؤقت المختلفة بواسطة محطات مختلفة. من الواضح أن هذا الموقف يجب تجنبه لأنه يتسبب في تخزين المحتوى نفسه في مخازن مؤقتة مختلفة ، مما يقلل من كفاءة تخزين النظام. تعريف التشتت هو شدة الموقف أعلاه. يجب أن تكون خوارزمية التجزئة الجيدة قادرة على تجنب التناقضات قدر الإمكان ، أي لتقليل التشتت.
مشكلة الحمل هي في الواقع النظر في مشكلة اللامركزية من منظور آخر. نظرًا لأن المحطات الطرفية المختلفة قد تقوم بتخطيط نفس المحتوى إلى المخازن المؤقتة المختلفة ، بالنسبة للمخزن المؤقت المحدد ، قد يتم تعيينه أيضًا إلى محتوى مختلف من قبل مستخدمين مختلفين. مثل التشتت ، يجب تجنب هذا الموقف ، لذلك يجب أن تكون خوارزمية التجزئة الجيدة قادرة على تقليل الحمل المخزن المؤقت.
على السطح ، يستهدف التجزئة المتسقة مشكلة التخزين المؤقت الموزعة ، ولكن إذا فكرت في التخزين المؤقت كأقران في نظام P2P والمحتوى المعين كموارد مشتركة مختلفة (البيانات ، والملفات ، ودفقات الوسائط ، وما إلى ذلك) ، فستجد أن الاثنين يصفان نفس المشكلة بالفعل.
في خوارزمية التجزئة المتسقة ، تحتوي كل عقدة (المقابلة للنظير في نظام P2P) على معرف تم تعيينه بشكل عشوائي. عند تعيين المحتوى إلى عقدة ، يتم تنفيذ عملية تجزئة ثابتة باستخدام الكلمة الرئيسية للمحتوى ومعرف العقدة ويحصل على قيمة المفتاح. يتطلب التجزئة المتسقة أن تكون القيمة الرئيسية ومعرف العقدة في نفس نطاق القيمة. يمكن أن تكون أبسط قيمة ومعرف رئيسي أحادي البعد ، مثل مجموعة من الأعداد الصحيحة من 0000 إلى 9999.
عند تخزين المحتوى استنادًا إلى قيمة المفتاح ، يتم تخزين المحتوى على العقدة مع الأقرب إلى المعرف إلى قيمته الرئيسية. على سبيل المثال ، إذا كانت القيمة الرئيسية هي 1001 ، فهناك عقد مع IDS 1000 و 1010 و 1100 في النظام ، وسيتم تعيين المحتوى إلى 1000 عقد.
لإنشاء الطرق المطلوبة للاستعلام ، يتطلب تجزئة الاتساق كل عقدة لتخزين معلومات الموقع (عنوان IP) لعقدة الوصلة الصاعدة الخاصة بها (قيمة المعرف أكبر من الأصغر بين العقد الخاصة بها) وعقدة الوصلة الهابطة (قيمة المعرف أقل من أكبرها بين العقد الخاصة). عندما تحتاج العقدة إلى العثور على محتوى ، يمكن أن تقرر بدء طلب استعلام إلى عقدة الوصلة الصاعدة أو الوصلة الهابطة بناءً على القيمة الرئيسية للمحتوى. إذا وجدت العقدة التي تتلقى طلب الاستعلام أن لديها الهدف المطلوب ، فيمكنها إرجاع تأكيد مباشرة إلى العقدة التي تبدأ طلب الاستعلام ؛ إذا وجدت أنها لا تنتمي إلى نطاقها الخاص ، فيمكنها إعادة توجيه الطلب إلى عقدة الوصلة الصاعدة/الوصلة الهابطة.
من أجل الحفاظ على معلومات التوجيه المذكورة أعلاه ، عندما تنضم العقدة/الخروج من النظام ، يجب على العقد المجاورة تحديث معلومات التوجيه في الوقت المناسب. يتطلب ذلك ألا تقوم العقد بتخزين معلومات موقع عقدة الوصلة الهابطة مباشرة ، ولكن أيضًا تعرف على معلومات عقدة الوصلة الهابطة غير المباشرة على عمق معين (N-HOP) ، والحفاظ على قائمة العقدة ديناميكيًا. عندما تخرج العقدة من النظام ، ستحاول عقدة الوصلة الصاعدة الاتصال مباشرة بأقرب عقدة الوصلة الهابطة. بعد نجاح الاتصال ، ستحصل على قائمة عقدة الوصلة الهابطة من عقدة الوصلة الهابطة الجديدة وتحديث قائمة العقدة الخاصة بها. وبالمثل ، عند إضافة عقدة جديدة إلى النظام ، ابحث أولاً عن عقدة الوصلة الهابطة وفقًا لمعرفها الخاص والحصول على قائمة عقدة الوصلة الهابطة ، ثم اطلب عقدة الوصلة الصاعدة لتعديل قائمة عقدة الوصلة الهابطة ، وبالتالي استعادة علاقة التوجيه.
يناقش
التجزئة المتسقة تحل بشكل أساسي المشكلة الأكثر أهمية في بيئة P2P - كيفية توزيع التخزين والتوجيه في طوبولوجيا الشبكة الديناميكية. تحتاج كل عقدة فقط إلى الحفاظ على معلومات عن عدد صغير من العقد المجاورة ، وعندما تنضم العقدة/الخروج من النظام ، يشارك عدد صغير فقط من العقد ذات الصلة في صيانة الطوبولوجيا. كل هذا يجعل التجزئة المتسقة أول خوارزمية DHT العملية.
ومع ذلك ، فإن خوارزمية التوجيه للتجزئة المتسقة لا تزال لديها أوجه القصور. أثناء عملية الاستعلام ، يجب أن تمر رسالة الاستعلام عبر O (n) الخطوة (O (n) تشير إلى وجود علاقة نسبية مع n ، ويمثل n العدد الإجمالي للعقد في النظام) قبل أن تتمكن من الوصول إلى عقدة الاستعلام. ليس من الصعب تخيل أنه عندما يكون النظام كبيرًا جدًا ، قد يتجاوز عدد العقد مليون ، ومن الواضح أن كفاءة الاستعلام هذه يصعب تلبية احتياجات الاستخدام. من منظور آخر ، حتى لو كان بإمكان المستخدم تحمل التأخير الطويل ، فإن الكمية الكبيرة من الرسائل التي تم إنشاؤها أثناء عملية الاستعلام ستجلب تحميلًا غير ضروري على الشبكة.
حزمة herotrix ؛ استيراد java.util.collection ؛ استيراد java.util.sortedmap ؛ استيراد java.util.treemap ؛ الطبقة العامة consertenhash <T> {// hash خوارزمية private finatedmap = inte inte ، treemap <integer ، t> () ؛ public conserenthash (hashfunction hashfunction ، int numberofreplicas ، collection <t> noves) {this.hashfunction = hashfunction ؛ this.numberofreplicas = numberOfReplicas ؛ لـ (t node: nodes) {add (node) ؛}} public void add (t node) {for (int i = 0 ؛ i <numberofreplicas ؛ i ++) {circle.put (hashfunction.hash (ade.toString ()+i) ، node) ؛ i ++) {circle.remove (hashfunction.hash (node.toString ()+i)) ؛}} // key key algorithm public t get get (object key) {if (circle.isempty ()) {return null ؛ if (! circle.containskey (hash)) {sortedMap <integer ، t> tailmap = circle.tailmap (hash) ؛ hash = tailmap.isempty ()؟ circle.firstkey (): tailmap.firstkey () ؛} return circle.get (hash) ؛}}ما ورد أعلاه هو المحتوى الكامل لهذه المقالة حول لغة جافا متسقة خوارزمية تجزئة ملاحظات التعلم (أمثلة رمز). آمل أن يكون ذلك مفيدًا للجميع. يمكن للأصدقاء المهتمين الاستمرار في الرجوع إلى الموضوعات الأخرى ذات الصلة على هذا الموقع. إذا كانت هناك أي أوجه قصور ، فيرجى ترك رسالة لإشارةها. شكرا لك يا أصدقائك لدعمكم لهذا الموقع!