جدول التجزئة الموزع

📅 آخر تحديث: ٢٩ يوليو ٢٠٢٦
✍️ نُشر في: ٢٩ يوليو ٢٠٢٦
📷 يحتوي على 17 صور
الموسوعة الحرة

جدول التجزئة الموزع ( DHT ) هو نظام موزع يوفر خدمة بحث مشابهة لجدول التجزئة . تُخزَّن أزواج المفاتيح والقيم في جدول التجزئة الموزع، ويمكن لأي عقدة مشاركة استرجاع القيمة المرتبطة بمفتاح معين بكفاءة. تتمثل الميزة الرئيسية لجدول التجزئة الموزع في إمكانية إضافة أو إزالة العقد بأقل جهد ممكن لإعادة توزيع المفاتيح. [ 1 ] المفاتيح هي معرّفات فريدة تُشير إلى قيم محددة ، والتي بدورها قد تكون أي شيء من العناوين إلى المستندات إلى أي بيانات أخرى . [ 2 ] تُوزَّع مسؤولية الحفاظ على الربط بين المفاتيح والقيم بين العقد، بحيث يُحدث أي تغيير في مجموعة المشاركين أقل قدر من الاضطراب. وهذا يسمح لجدول التجزئة الموزع بالتوسع ليشمل أعدادًا هائلة من العقد، والتعامل مع وصول العقد ومغادرتها وتعطلها بشكل مستمر.

تُشكّل جداول التجزئة الموزعة (DHTs) بنيةً تحتيةً يُمكن استخدامها لبناء خدمات أكثر تعقيدًا، مثل البث المتعدد ، والتخزين المؤقت التعاوني للويب ، وأنظمة الملفات الموزعة ، وخدمات أسماء النطاقات ، والمراسلة الفورية ، والبث المتعدد ، بالإضافة إلى أنظمة مشاركة الملفات وتوزيع المحتوى من نظير إلى نظير . ومن أبرز الشبكات الموزعة التي تستخدم جداول التجزئة الموزعة: متتبع BitTorrent الموزع، وشبكة Kad ، وشبكة Storm للبوتات ، وبرنامج المراسلة الفورية Tox ، وشبكة Freenet ، ومحرك البحث YaCy ، ونظام الملفات بين الكواكب .

جداول التجزئة الموزعة

تاريخ

استُلهمت أبحاث DHT في الأصل، جزئيًا، من أنظمة الند للند (P2P) مثل Freenet و Gnutella و BitTorrent و Napster ، التي استغلت الموارد الموزعة عبر الإنترنت لتقديم تطبيق واحد مفيد. وعلى وجه الخصوص، استفادت هذه الأنظمة من زيادة عرض النطاق الترددي وسعة القرص الصلب لتوفير خدمة مشاركة الملفات. [ 3 ]

اختلفت هذه الأنظمة في كيفية تحديدها للبيانات التي يقدمها نظراؤها. كان نظام نابستر، أول نظام واسع النطاق لتوزيع المحتوى عبر تقنية الند للند، يتطلب خادم فهرسة مركزيًا: إذ كان كل عقدة، عند انضمامها، ترسل قائمة بالملفات المخزنة محليًا إلى الخادم، الذي كان يُجري عمليات البحث ويُحيل الاستعلامات إلى العقد التي تحتوي على النتائج. جعل هذا المكون المركزي النظام عرضةً للهجمات والدعاوى القضائية.

انتقلت شبكة غنوتيلا والشبكات المشابهة إلى نموذج إغراق الاستعلامات ، حيث كان كل بحث يُرسل رسالة إلى جميع الأجهزة في الشبكة. ورغم تجنب نقطة فشل واحدة ، إلا أن هذه الطريقة كانت أقل كفاءة بكثير من نابستر. ثم انتقلت الإصدارات اللاحقة من عملاء غنوتيلا إلى نموذج الاستعلام الديناميكي الذي حسّن الكفاءة بشكل كبير. [ 4 ] 

شبكة Freenet موزعة بالكامل، لكنها تستخدم توجيهًا قائمًا على المفاتيح ، حيث يرتبط كل ملف بمفتاح، وتميل الملفات ذات المفاتيح المتشابهة إلى التجمع على مجموعة مماثلة من العقد. ومن المرجح أن يتم توجيه الاستعلامات عبر الشبكة إلى هذه المجموعة دون الحاجة إلى زيارة العديد من النظراء. [ 5 ] ومع ذلك، لا تضمن Freenet العثور على البيانات.

تستخدم جداول التجزئة الموزعة توجيهًا أكثر تنظيمًا قائمًا على المفاتيح لتحقيق كلٍ من اللامركزية التي تتميز بها شبكتا Freenet وGnutella، والكفاءة وضمان النتائج التي تتميز بها شبكة Napster. ومن عيوبها، كما هو الحال في Freenet، أنها تدعم البحث عن التطابق التام فقط، وليس البحث بالكلمات المفتاحية، على الرغم من إمكانية تعميم خوارزمية التوجيه الخاصة بـ Freenet لتشمل أي نوع من المفاتيح التي يمكن تعريف عملية تقارب لها. [ 6 ]

في عام ٢٠٠١، لفتت أربعة أنظمة - CAN [ ٧ ] و Chord [ ٨ ] و Pastry و Tapestry - الانتباه إلى تقنية DHT. وفي عام ٢٠٠٢، مُوِّل مشروعٌ يُسمى "البنية التحتية لأنظمة الإنترنت المرنة " (Iris) بمنحةٍ قدرها ١٢ مليون دولار من المؤسسة الوطنية للعلوم في الولايات المتحدة. [ ٩ ] وشمل الباحثون سيلفيا راتناسيمي ، وإيون ستويكا ، وهاري بالاكريشنان ، وسكوت شينكر . [ ١٠ ] وخارج الأوساط الأكاديمية، اعتُمدت تقنية DHT كمكوّنٍ من مكونات BitTorrent وفي مشاريع PlanetLab مثل شبكة توزيع المحتوى Coral. [ ١١ ]

ملكيات

تتميز هرمونات ديهيدروتستوستيرون (DHTs) بالخصائص التالية:

تتمثل إحدى التقنيات الرئيسية المستخدمة لتحقيق هذه الأهداف في أن أي عقدة تحتاج إلى التنسيق مع عدد قليل فقط من العقد الأخرى في النظام - في أغلب الأحيان، O (log n ) من المشاركين n (انظر أدناه) - بحيث لا يلزم سوى قدر محدود من العمل لكل تغيير في العضوية.

تسعى بعض تصميمات DHT إلى أن تكون آمنة ضد المشاركين الضارين [ 13 ] وأن تسمح للمشاركين بالبقاء مجهولين ، على الرغم من أن هذا أقل شيوعًا من العديد من أنظمة الند للند الأخرى (وخاصة مشاركة الملفات )؛ انظر P2P المجهول .

بناء

يمكن تقسيم بنية شبكة التجزئة الموزعة (DHT) إلى عدة مكونات رئيسية. [ 14 ] [ 15 ] الأساس هو فضاء مفاتيح مجرد ، مثل مجموعة السلاسل النصية بطول 160 بت. يقوم نظام تقسيم فضاء المفاتيح بتوزيع ملكية هذا الفضاء بين العقد المشاركة. ثم تربط شبكة تراكبية هذه العقد، مما يسمح لها بالعثور على مالك أي مفتاح مُعطى في فضاء المفاتيح.

بمجرد تثبيت هذه المكونات، يمكن استخدام جدول التجزئة الموزع (DHT) للتخزين والاسترجاع على النحو التالي: لنفترض أن مساحة المفاتيح هي مجموعة من السلاسل النصية بطول 160 بت. لفهرسة ملف باسم وبيانات محددة في جدول التجزئة الموزع، يتم توليد تجزئة SHA-1 لاسم الملف ، مما ينتج عنه مفتاح k بطول 160 بت ، ثم تُرسل رسالة put ( k, data ) إلى أي عقدة مشاركة في جدول التجزئة الموزع. تُعاد توجيه الرسالة من عقدة إلى أخرى عبر الشبكة المتراكبة حتى تصل إلى العقدة المسؤولة عن المفتاح k، كما هو محدد في تقسيم مساحة المفاتيح. تقوم هذه العقدة بعد ذلك بتخزين المفتاح والبيانات. يمكن لأي عميل آخر استرجاع محتويات الملف عن طريق تجزئة اسم الملف مرة أخرى لإنتاج k ، ثم طلب رسالة get ( k ) من أي عقدة في جدول التجزئة الموزع للعثور على البيانات المرتبطة بـ k . ستُعاد توجيه الرسالة عبر الشبكة المتراكبة إلى العقدة المسؤولة عن k ، والتي سترد بالبيانات المخزنة .

يتم وصف مكونات تقسيم مساحة المفاتيح وشبكة التراكب أدناه بهدف التقاط الأفكار الرئيسية المشتركة بين معظم خوارزميات التجزئة الموزعة (DHTs)؛ وتختلف العديد من التصميمات في التفاصيل.

تقسيم مساحة المفاتيح

تستخدم معظم جداول التجزئة الموزعة (DHTs) نوعًا من التجزئة المتسقة أو التجزئة المتزامنة لربط المفاتيح بالعقد. ويبدو أن الخوارزميتين قد تم ابتكارهما بشكل مستقل ومتزامن لحل مشكلة جدول التجزئة الموزع.

تتميز كل من التجزئة المتسقة والتجزئة المتزامنة بخاصية أساسية، وهي أن إزالة أو إضافة عقدة واحدة لا تُغير سوى مجموعة المفاتيح التي تملكها العقد ذات المعرفات المتجاورة، دون التأثير على باقي العقد. وعلى النقيض من ذلك، في جداول التجزئة التقليدية ، تؤدي إضافة أو إزالة خانة واحدة إلى إعادة تعيين مساحة المفاتيح بالكامل تقريبًا. وبما أن أي تغيير في الملكية عادةً ما يرتبط بنقل مكثف لعرض النطاق الترددي للكائنات المخزنة في جدول التجزئة الموزع (DHT) من عقدة إلى أخرى، فإن تقليل إعادة التنظيم هذه ضروري لدعم معدلات التغيير العالية (وصول العقد وتعطلها) بكفاءة.

التجزئة المتسقة

تستخدم عملية التجزئة المتسقة دالةدلتا(ك1،ك2){\displaystyle \delta (k_{1},k_{2})}ذلك يحدد مفهومًا مجردًا للمسافة بين المفاتيحك1{\displaystyle k_{1}}وك2{\displaystyle k_{2}}وهذا لا يرتبط بالمسافة الجغرافية أو زمن استجابة الشبكة . يتم تخصيص مفتاح واحد لكل عقدة يُسمى مُعرّفها (ID). العقدة ذات المعرّفأناx{\displaystyle i_{x}}يمتلك جميع المفاتيحكم{\displaystyle k_{m}}والتيأناx{\displaystyle i_{x}}هو أقرب مُعرّف، تم قياسه وفقًا لـدلتا(كم،أناx){\displaystyle \delta (k_{m},i_{x})}.

على سبيل المثال، يستخدم Chord DHT التجزئة المتسقة، التي تعامل العقد كنقاط على دائرة، ودلتا(ك1،ك2){\displaystyle \delta (k_{1},k_{2})}هي المسافة التي تقطعها في اتجاه عقارب الساعة حول الدائرة منك1{\displaystyle k_{1}}لك2{\displaystyle k_{2}}وبالتالي، يتم تقسيم مساحة المفاتيح الدائرية إلى أجزاء متجاورة تكون نقاط نهايتها هي مُعرّفات العقد. إذاأنا1{\displaystyle i_{1}}وأنا2{\displaystyle i_{2}}هما معرفان متجاوران، بمسافة أقصر باتجاه عقارب الساعة منأنا1{\displaystyle i_{1}}لأنا2{\displaystyle i_{2}}ثم العقدة ذات المعرفأنا2{\displaystyle i_{2}}يمتلك جميع المفاتيح التي تقع بينهماأنا1{\displaystyle i_{1}}وأنا2{\displaystyle i_{2}}.

تجزئة اللقاء

في التجزئة المتزامنة، والتي تسمى أيضًا التجزئة ذات الوزن العشوائي الأعلى (HRW)، يستخدم جميع العملاء نفس دالة التجزئةح(){\displaystyle h()}(يتم اختيارها مسبقًا) لربط مفتاح بأحد الخوادم المتاحة البالغ عددها n . يمتلك كل عميل نفس قائمة المعرفات { S1 , S2 , ..., Sn } ، معرف واحد لكل خادم. بمعرف مفتاح k ، يحسب العميل n من أوزان التجزئة w1 = h ( S1 , k ), w2 = h ( S2 , k ), ... , wn = h ( Sn , k ) . يربط العميل هذا المفتاح بالخادم الذي يتوافق مع أعلى وزن تجزئة لهذا المفتاح. الخادم ذو المعرفSx{\displaystyle S_{x}}يمتلك جميع المفاتيحكم{\displaystyle k_{m}}وزن الهاشح(Sx،كم){\displaystyle h(S_{x},k_{m})}أعلى من وزن التجزئة لأي عقدة أخرى لهذا المفتاح.

التجزئة التي تحافظ على الموقع

يضمن التجزئة الحافظة للموقع تخصيص المفاتيح المتشابهة للكائنات المتشابهة. وهذا يُتيح تنفيذًا أكثر كفاءة لاستعلامات النطاق، إلا أنه على عكس التجزئة المتسقة، لا يوجد ضمان إضافي بأن المفاتيح (وبالتالي الحمل) موزعة عشوائيًا وبشكل متساوٍ على فضاء المفاتيح والأقران المشاركين. تعالج بروتوكولات DHT مثل Self-Chord وOscar [ 16 ] هذه المشكلات. يفصل Self-Chord مفاتيح الكائنات عن معرّفات الأقران، ويرتب المفاتيح على طول الحلقة باستخدام منهج إحصائي قائم على نموذج ذكاء السرب . [ 17 ] يضمن الترتيب تخزين المفاتيح المتشابهة بواسطة العقد المجاورة، وإمكانية تنفيذ إجراءات الاكتشاف، بما في ذلك استعلامات النطاق ، في وقت لوغاريتمي. يبني Oscar شبكة عالم صغير قابلة للتنقل تعتمد على أخذ عينات المشي العشوائي ، مما يضمن أيضًا وقت بحث لوغاريتمي.

شبكة تراكبية

تحتفظ كل عقدة بمجموعة من الروابط مع العقد الأخرى (جيرانها أو جدول التوجيه ). تشكل هذه الروابط مجتمعةً شبكة التراكب. [ 18 ] تختار العقدة جيرانها وفقًا لبنية معينة، تُسمى طوبولوجيا الشبكة .

تشترك جميع بنيات DHT في خاصية أساسية واحدة: لكل مفتاح k ، إما أن يكون لكل عقدة مُعرّف عقدة يمتلك k، أو أن يكون لها رابط إلى عقدة يكون مُعرّفها أقرب إلى k ، وذلك وفقًا لمسافة فضاء المفاتيح المحددة سابقًا. وبالتالي، يسهل توجيه الرسالة إلى مالك أي مفتاح k باستخدام الخوارزمية الجشعة التالية (مع العلم أنها ليست بالضرورة الأمثل عالميًا): في كل خطوة، يتم توجيه الرسالة إلى الجار الأقرب مُعرّفًا إلى k . عندما لا يوجد جار كهذا، نكون قد وصلنا إلى أقرب عقدة، وهي مالكة k كما هو مُعرّف سابقًا. يُطلق على هذا النمط من التوجيه أحيانًا اسم التوجيه القائم على المفاتيح .

إلى جانب صحة التوجيه الأساسية، هناك قيدان مهمان على بنية الشبكة: ضمان أن يكون الحد الأقصى لعدد القفزات في أي مسار (طول المسار) منخفضًا، لضمان سرعة إتمام الطلبات؛ وضمان أن يكون الحد الأقصى لعدد الجيران لأي عقدة (الحد الأقصى لدرجة العقدة ) منخفضًا، لضمان عدم تجاوز تكاليف الصيانة الحد المسموح به. وبطبيعة الحال، يتطلب وجود مسارات أقصر حدًا أقصى أعلى لدرجة العقدة . وفيما يلي بعض الخيارات الشائعة للحد الأقصى لدرجة العقدة وطول المسار، حيث n هو عدد العقد في شبكة التجزئة الموزعة (DHT)، باستخدام ترميز Big O :

أقصى درجةأقصى طول للمساريستخدم فيملحوظة
يا(1){\displaystyle O(1)}يا(ن){\displaystyle O(n)}أسوأ أطوال البحث، مع أوقات بحث أبطأ بكثير على الأرجح
يا(1){\displaystyle O(1)}يا(سجل⁡ن){\displaystyle O(\log n)}Koorde (بدرجة ثابتة)أكثر تعقيدًا في التنفيذ، ولكن يمكن إيجاد وقت بحث مقبول مع عدد ثابت من الاتصالات
يا(سجل⁡ن){\displaystyle O(\log n)}يا(سجل⁡ن){\displaystyle O(\log n)}نسيج معجنات كورد كاديملياالأكثر شيوعًا، ولكنه ليس الأمثل (من حيث الدرجة/طول المسار). Chord هو الإصدار الأساسي، بينما يبدو أن Kademlia هو الإصدار المُحسَّن الأكثر شيوعًا (يفترض أن يكون متوسط ​​وقت البحث فيه أفضل).
يا(سجل⁡ن){\displaystyle O(\log n)}يا(سجل⁡ن/سجل⁡(سجل⁡ن)){\displaystyle O(\log n/\log(\log n))}Koorde (مع بحث مثالي)أكثر تعقيداً في التنفيذ، لكن عمليات البحث قد تكون أسرع (لها حد أدنى أقل في أسوأ الحالات).
يا(ن){\displaystyle O({\sqrt {n}})}يا(1){\displaystyle O(1)}أسوأ احتياجات التخزين المحلي، مع الكثير من الاتصالات بعد اتصال أو انقطاع أي عقدة.

الخيار الأكثر شيوعاً،يا(سجل⁡ن){\displaystyle O(\log n)}لا يُعدّ استخدام درجة الشبكة/طول المسار الأمثل من حيث المفاضلة بين درجة الشبكة وطول المسار، ولكن هذه البنى الشبكية عادةً ما تتيح مرونة أكبر في اختيار الجيران. تستغل العديد من سلاسل التجزئة الموزعة (DHTs) هذه المرونة لاختيار جيران متقاربين من حيث زمن الاستجابة في الشبكة المادية الأساسية. بشكل عام، تُنشئ جميع سلاسل التجزئة الموزعة بنى شبكية قابلة للتنقل ذات عالم صغير، والتي تُوازن بين طول المسار ودرجة الشبكة. [ 19 ]

يرتبط أقصى طول للمسار ارتباطًا وثيقًا بالقطر : وهو الحد الأقصى لعدد القفزات في أقصر مسار بين العقد. من الواضح أن أسوأ حالة لطول المسار في الشبكة لا تقل عن قطرها، لذا فإن جداول التجزئة الموزعة (DHTs) محدودة بموازنة الدرجة/القطر [ 20 ] ، وهي معادلة أساسية في نظرية الرسوم البيانية . قد يكون طول المسار أكبر من القطر، لأن خوارزمية التوجيه الجشعة قد لا تجد أقصر المسارات. [ 21 ]

خوارزميات الشبكات المتراكبة

إلى جانب التوجيه، توجد العديد من الخوارزميات التي تستغل بنية الشبكة المتراكبة لإرسال رسالة إلى جميع العقد، أو مجموعة فرعية منها، في شبكة DHT. [ 22 ] تستخدم التطبيقات هذه الخوارزميات لإجراء البث المتعدد المتراكب ، أو استعلامات النطاق، أو لجمع الإحصائيات. من بين الأنظمة التي تعتمد على هذا النهج نظاما Structella [ 23 ] ، الذي يُنفذ خوارزميتي الفيضان والمشي العشوائي على شبكة Pastry المتراكبة، وDQ-DHT، الذي يُنفذ خوارزمية بحث استعلام ديناميكي على شبكة Chord. [ 24 ]

حماية

بسبب اللامركزية، وتحمل الأعطال، وقابلية التوسع في DHTs، فإنها تتمتع بطبيعتها بمرونة أكبر ضد المهاجمين المعادين مقارنة بالنظام المركزي.

تُعد الأنظمة المفتوحة لتخزين البيانات الموزعة والتي تتمتع بالمتانة في مواجهة الهجمات المعادية الضخمة أمراً ممكناً. [ 25 ]

يمكن لنظام DHT المصمم بعناية ليتحمل أخطاء بيزنطية أن يحمي من ثغرة أمنية تُعرف بهجوم سيبيل ، والتي تؤثر على معظم تصميمات DHT الحالية. [ 26 ] [ 27 ] وWhanau هو نظام DHT مصمم لمقاومة هجمات سيبيل. [ 28 ]

اقترح بيتر مايمونكوف، أحد المؤلفين الأصليين لنظام كاديميليا ، طريقةً لتجاوز ثغرة هجوم سيبيل من خلال دمج علاقات الثقة الاجتماعية في تصميم النظام. [ 29 ] يعتمد النظام الجديد، المسمى تونيكا أو المعروف أيضًا باسم نطاقه 5ttt، على تصميم خوارزمية يُعرف باسم "التوجيه الكهربائي"، وقد شارك في تأليفه عالم الرياضيات جوناثان كيلنر. [ 30 ] وقد بذل مايمونكوف جهدًا كبيرًا في تنفيذ هذا النظام الجديد. مع ذلك، لا يزال البحث عن وسائل دفاع فعّالة ضد هجمات سيبيل يُعتبر عمومًا مسألةً مفتوحة، ويتم اقتراح مجموعة واسعة من وسائل الدفاع المحتملة سنويًا في مؤتمرات أبحاث الأمن السيبراني الرائدة. [ 31 ]

التطبيقات

تشمل أبرز الاختلافات التي تمت مواجهتها في الحالات العملية لتطبيقات DHT ما يلي على الأقل:

  • مساحة العناوين هي أحد معايير DHT. تستخدم العديد من جداول DHT الواقعية مساحة مفاتيح 128 بت أو 160 بت.
  • تستخدم بعض خوارزميات التجزئة الموزعة (DHTs) في العالم الحقيقي وظائف تجزئة أخرى غير SHA-1 .
  • في العالم الحقيقي، يمكن أن يكون المفتاح k عبارة عن تجزئة لمحتوى الملف بدلاً من تجزئة اسم الملف لتوفير تخزين قابل للعنونة بالمحتوى ، بحيث لا تمنع إعادة تسمية الملف المستخدمين من العثور عليه.
  • قد تنشر بعض جداول التجزئة الموزعة (DHTs) كائنات من أنواع مختلفة. على سبيل المثال، يمكن أن يكون المفتاح k هو مُعرّف العقدة ، ويمكن أن تصف البيانات المرتبطة به كيفية الاتصال بهذه العقدة. يتيح ذلك نشر معلومات التواجد، ويُستخدم غالبًا في تطبيقات المراسلة الفورية، وما إلى ذلك. في أبسط الحالات، يكون المُعرّف مجرد رقم عشوائي يُستخدم مباشرةً كمفتاح k (لذا في جدول تجزئة موزعة 160 بت ، سيكون المُعرّف رقمًا من 160 بت، يُختار عادةً عشوائيًا). في بعض جداول التجزئة الموزعة، يُستخدم نشر مُعرّفات العقد أيضًا لتحسين عمليات جدول التجزئة الموزعة.
  • يمكن إضافة التكرار لتحسين الموثوقية. يمكن تخزين زوج المفاتيح (k، البيانات) في أكثر من عقدة واحدة لكل مفتاح. عادةً، بدلاً من اختيار عقدة واحدة فقط، تختار خوارزميات DHT العملية i عقدة مناسبة، حيث يمثل i مُعاملًا خاصًا بتنفيذ DHT. في بعض تصميمات DHT، تتفق العقد على التعامل مع نطاق معين من مساحة المفاتيح، ويمكن اختيار حجم هذا النطاق ديناميكيًا، بدلاً من تحديده مسبقًا.
  • تُجري بعض جداول التجزئة الموزعة المتقدمة، مثل Kademlia، عمليات بحث متكررة في جدول التجزئة الموزعة لاختيار مجموعة من العقد المناسبة، ثم تُرسل رسائل put(k, data) إليها فقط، مما يُقلل بشكل كبير من حركة البيانات غير الضرورية، حيث تُرسل الرسائل المنشورة فقط إلى العقد التي تبدو مناسبة لتخزين المفتاح k . كما أن عمليات البحث المتكررة تُغطي مجموعة صغيرة من العقد بدلاً من جدول التجزئة الموزعة بأكمله، مما يُقلل من إعادة التوجيه غير الضرورية. في هذه الجداول، قد لا تتم إعادة توجيه رسائل put(k, data) إلا كجزء من خوارزمية إصلاح ذاتي: إذا استقبلت عقدة مستهدفة رسالة put(k, data) ، ولكنها تعتقد أن k خارج نطاقها المُعالج، وأن هناك عقدة أقرب (من حيث مساحة مفاتيح جدول التجزئة الموزعة) معروفة، تُعاد توجيه الرسالة إلى تلك العقدة. وإلا، تُفهرس البيانات محليًا. هذا يُؤدي إلى سلوك جدول تجزئة موزعة متوازن ذاتيًا إلى حد ما. بالطبع، تتطلب هذه الخوارزمية من العقد نشر بيانات وجودها في جدول التجزئة الموزعة حتى يُمكن إجراء عمليات البحث المتكررة.
  • بما أن إرسال الرسائل في معظم الأجهزة أكثر تكلفة بكثير من الوصول إلى جداول التجزئة المحلية، فمن المنطقي تجميع العديد من الرسائل المتعلقة بعقدة معينة في دفعة واحدة. بافتراض أن لكل عقدة دفعة محلية تتكون من b عملية على الأكثر، فإن إجراء التجميع يكون كما يلي: تقوم كل عقدة أولاً بفرز دفعتها المحلية حسب مُعرِّف العقدة المسؤولة عن العملية. باستخدام فرز الدلو ، يمكن القيام بذلك في زمن O(b + n) ، حيث n هو عدد العقد في جدول التجزئة الموزع (DHT). عندما تكون هناك عمليات متعددة تتناول نفس المفتاح ضمن دفعة واحدة، يتم ضغط الدفعة قبل إرسالها. على سبيل المثال، يمكن تقليل عمليات البحث المتعددة عن نفس المفتاح إلى عملية بحث واحدة، أو يمكن تقليل عمليات الزيادة المتعددة إلى عملية جمع واحدة. يمكن تنفيذ هذا الاختزال بمساعدة جدول تجزئة محلي مؤقت. أخيرًا، تُرسل العمليات إلى العقد المعنية. [ 32 ]

أمثلة

بروتوكولات وتطبيقات DHT

التطبيقات التي تستخدم DHTs

انظر أيضاً

مراجع

  1. ^ هوتا، شيتارانجان؛ سريماني ، براديب ك. (2013/01/11). الحوسبة الموزعة وتكنولوجيا الإنترنت: المؤتمر الدولي التاسع، ICDCIT 2013، بوبانسوار، الهند، 5-8 فبراير 2013، وقائع . سبرينغر. رقم ISBN 978-3-642-36071-8.
  2. ↑ ستويكا، آي .؛ موريس، آر.؛ كارغر، دي .؛ كاشوك، إم إف؛ بالاكريشنان، إتش. (2001). "Chord: خدمة بحث قابلة للتوسع من نظير إلى نظير لتطبيقات الإنترنت" (ملف PDF) . مجلة ACM SIGCOMM لمراجعة اتصالات الحاسوب . 31 (4): 149. doi : 10.1145/964723.383071 . مؤرشف (PDF) من الأصل بتاريخ 2023-07-07 . تم الاسترجاع بتاريخ 2018-09-18 . يمكن أن تكون القيمة عنوانًا أو مستندًا أو عنصر بيانات عشوائيًا.
  3. ↑ ليز، كروكروفت، وآخرون (2005). "دراسة استقصائية ومقارنة لأنظمة شبكات التراكب من نظير إلى نظير" (ملف PDF) . مجلة IEEE لدراسات الاتصالات والدروس التعليمية . 7 (2): 72-93 . CiteSeerX 10.1.1.109.6124 . doi : 10.1109/COMST.2005.1610546 . S2CID 7971188. مؤرشف (ملف PDF) من الأصل بتاريخ 2023-10-05 . تم الاطلاع عليه بتاريخ 2019-09-24 .   
  4. ↑ ريختر، ستيفنسون؛ وآخرون (2009). "تحليل تأثير نماذج الاستعلام الديناميكية على علاقات العميل والخادم". اتجاهات في الحوسبة الحديثة : 682-701 . 
  5. ↑ البحث في عالم صغير، الفصلان 1 و2 (ملف PDF) ، مؤرشف من النسخة الأصلية (ملف PDF) بتاريخ 16 مارس 2012 ، تم الاطلاع عليه بتاريخ 10 يناير 2012
  6. ↑ "القسم 5.2.2" (ملف PDF) ، نظام تخزين واسترجاع معلومات موزع لا مركزي ، مؤرشف من النسخة الأصلية (ملف PDF) بتاريخ 16-03-2012 ، تم استرجاعه بتاريخ 10-01-2012
  7. ↑ راتناسيمي، سيلفيا؛ فرانسيس، بول؛ هاندلي، مارك؛ كارب، ريتشارد؛ شينكر، سكوت (27 أغسطس/آب 2001). "شبكة قابلة للتوسع ذات عناوين محتوى" . مجلة SIGCOMM لمراجعات الحوسبة والاتصالات ، 31 (4): 161-172 . doi : 10.1145/964723.383072 . ISSN 0146-4833 . 
  8. ↑ هاري بالاكريشنان ، إم. فرانس كاشوك ، ديفيد كارغر، روبرت موريس ، وإيون ستويكا. البحث عن البيانات في أنظمة الند للند. مؤرشف في 19 مايو 2016 على موقع Wayback Machine . في مجلة اتصالات ACM ، فبراير 2003.
  9. ↑ ديفيد كوهين (1 أكتوبر 2002). "تمويل الحكومة الأمريكية لشبكة نظير إلى نظير جديدة" . مجلة نيو ساينتست . مؤرشف من الأصل في 6 أبريل 2008. تم الاطلاع عليه في 10 نوفمبر 2013 .
  10. ↑ "معهد ماساتشوستس للتكنولوجيا، وجامعة بيركلي، ومعهد علوم الحاسوب والمعلومات، وجامعة نيويورك، وجامعة رايس تطلق مشروع IRIS" . بيان صحفي . معهد ماساتشوستس للتكنولوجيا. 25 سبتمبر 2002. مؤرشف من الأصل في 26 سبتمبر 2015. تم الاطلاع عليه في 10 نوفمبر 2013 .
  11. ↑ "إضفاء الطابع الديمقراطي على نشر المحتوى باستخدام كورال" (ملف PDF) . NSDI . 4. 2004. تم الاطلاع عليه بتاريخ 1 مايو 2024 .
  12. ↑ ر. موكادم، أ. هامورلين، و أ. م. تجوا. خدمة اكتشاف الموارد مع تقليل تكاليف الصيانة في أنظمة DHT الهرمية. مؤرشف في 9 أغسطس 2022 على موقع Wayback Machine . وقائع مؤتمر iiWas، 2010
  13. ↑ غيدو أوردانيتا، غيوم بيير، ومارتن فان ستين. دراسة استقصائية لتقنيات أمن DHT. مؤرشفة بتاريخ 1 يونيو 2023 في Wayback Machine . مجلة ACM Computing Surveys، المجلد 43، العدد 2، يناير 2011.
  14. ↑ موني ناور وأودي ويدر. بنى جديدة لتطبيقات الند للند: النهج المتصل-المنفصل. مؤرشف بتاريخ 2019-12-09 في آلة Wayback . وقائع SPAA، 2003.
  15. ↑ غورميت سينغ مانكو. ديبسي: جدول تجزئة موزع معياري. مؤرشف في 10 سبتمبر 2004 على موقع Wayback Machine . أطروحة دكتوراه (جامعة ستانفورد)، أغسطس 2004.
  16. ↑ جيردزياوسكاس، شاروناس؛ داتا، أنويتامان؛ أبيرير، كارل (2010-02-01). "التراكب المهيكل للبيئات غير المتجانسة" . معاملات ACM في الأنظمة المستقلة والتكيفية . 5 (1): 1-25 . doi : 10.1145/1671948.1671950 . ISSN 1556-4665 . S2CID 13218263. مؤرشف من الأصل في 2020-07-12 . تم الاسترجاع في 2020-03-12 .  
  17. ↑ فوريستيرو، أغوستينو؛ ليوناردي، إميليو؛ ماستروياني، كارلو؛ ميو، ميكايلا (أكتوبر 2010). "سيلف-كورد: إطار عمل نظير إلى نظير مستوحى من علم الأحياء للأنظمة الموزعة ذاتية التنظيم" . معاملات IEEE/ACM في الشبكات . 18 (5): 1651-1664 . رمز Bibcode : 2010ITNet..18.1651F . doi : 10.1109/TNET.2010.2046745 . S2CID 14797120. مؤرشف من الأصل في 1 يوليو 2012. تم الاسترجاع في 28 يوليو 2019 . 
  18. ↑ غالوبا، فويتش؛ غيردزياوسكاس، ساروناس (2009)، "شبكات التراكب من نظير إلى نظير: البنية والتوجيه والصيانة"، في ليو، لينغ ؛ أوزسو، م. تامر (محرران)، موسوعة أنظمة قواعد البيانات ، سبرينغر الولايات المتحدة، ص 2056-2061 ، doi : 10.1007/978-0-387-39940-9_1215 ، ISBN  9780387399409
  19. ↑ جيردزياوسكاس، ساروناس (2009). تصميم طبقات الند للند: منظور العالم الصغير . epfl.ch (أطروحة). EPFL. doi : 10.5075/epfl-thesis-4327 . مؤرشف من الأصل بتاريخ 2020-03-03 . تم الاطلاع عليه بتاريخ 2019-11-11 .
  20. ↑ مسألة (الدرجة، القطر) للرسوم البيانية ، Maite71.upc.es، مؤرشفة من الأصل بتاريخ 17-02-2012 ، تم استرجاعها بتاريخ 10-01-2012
  21. ↑ غورميت سينغ مانكو، موني ناور، وأودي ويدر. "اعرف جار جارك: قوة التنبؤ في شبكات الند للند العشوائية". مؤرشف في 20 أبريل 2008 على موقع Wayback Machine . وقائع مؤتمر STOC، 2004.
  22. ↑ علي قدسي (22 مايو 2007). "نظام k-ary الموزع: خوارزميات لجداول التجزئة الموزعة" . مؤرشف من الأصل في 22 مايو 2007.. المعهد الملكي للتكنولوجيا (KTH)، 2006.
  23. ↑ كاسترو، ميغيل؛ كوستا، مانويل؛ روسترون، أنتوني (1 يناير 2004). "هل ينبغي لنا بناء غنوتيلا على طبقة هيكلية؟" ( ملف PDF) . مجلة ACM SIGCOMM لمراجعة اتصالات الحاسوب . 34 (1): 131. CiteSeerX 10.1.1.221.7892 . doi : 10.1145/972374.972397 . S2CID 6587291. مؤرشف (ملف PDF) من الأصل في 14 فبراير 2021. تم الاطلاع عليه في 25 سبتمبر 2019 .  
  24. ↑ تاليا، دومينيكو؛ ترونفيو، باولو (ديسمبر 2010). "تمكين الاستعلام الديناميكي على جداول التجزئة الموزعة". مجلة الحوسبة المتوازية والموزعة . 70 (12): 1254-1265 . doi : 10.1016/j.jpdc.2010.08.012 .
  25. ↑ باروخ أويربوخ، كريستيان شيديلر. "نحو تجزئة هرمية قابلة للتطوير وقوية". 2006. doi : 10.1145/1148109.1148163
  26. ↑ ماكسويل يونغ؛ أنيكيت كيت؛ إيان غولدبرغ؛ مارتن كارستن. "اتصال عملي قوي في جداول التجزئة الموزعة مع تحمل خصم بيزنطي" مؤرشف في 22-07-2016 في آلة Wayback .
  27. ^ ناتاليا فيدوتوفا. جيوردانو أورزيتي؛ لوكا فيلتري؛ اليساندرو زاكاجنيني. “الاتفاقية البيزنطية لإدارة السمعة في شبكات نظير إلى نظير المستندة إلى DHT”. دوى : 10.1109/ICTEL.2008.4652638
  28. ↑ Whanau: جدول تجزئة موزع مقاوم لهجمات سيبيل https://pdos.csail.mit.edu/papers/whanau-nsdi10.pdf مؤرشف بتاريخ 25 يناير 2022 في أرشيف الإنترنت
  29. ↑ ليسنيوسكي-لاس، كريس (1 أبريل 2008). "DHT أحادي القفزة مقاوم لهجمات سيبيل" . وقائع ورشة العمل الأولى حول أنظمة الشبكات الاجتماعية . SocialNets '08. نيويورك، نيويورك، الولايات المتحدة الأمريكية: رابطة آلات الحوسبة. الصفحات 19-24 . doi : 10.1145/1435497.1435501 . ISBN  978-1-60558-124-8.
  30. ↑ كيلنر، جوناثان؛ مايمونكوف، بيتر (22 يوليو 2011). "التوجيه الكهربائي وقطع التدفق المتزامن" . علوم الحاسوب النظرية . الخوارزميات والحساب. 412 (32): 4123-4135 . doi : 10.1016/j.tcs.2010.06.013 . hdl : 1721.1/71604 . ISSN 0304-3975 . 
  31. ↑ "هجمات سيبيل ودفاعاتها: دراسة استقصائية" . 2013-12-22.
  32. ↑ ساندرز، بيتر؛ ميلهورن، كورت؛ ديتزفيلبينجر، مارتن؛ ديمينتييف، رومان (2019). الخوارزميات المتسلسلة والمتوازية وهياكل البيانات: مجموعة الأدوات الأساسية . دار نشر سبرينغر الدولية. ISBN 978-3-030-25208-3أُرشف من المصدر الأصلي بتاريخ 17 أغسطس 2021. تم الاطلاع عليه بتاريخ 22 يناير 2020 .
  33. ↑ ويكي تريبلر مؤرشف في 4 ديسمبر 2010، في آلة Wayback Machine تم استرجاعه في يناير 2010.
  34. ↑ الأسئلة الشائعة حول Retroshare مؤرشفة بتاريخ 17 يوليو 2013 في Wayback Machine ، تم استرجاعها في ديسمبر 2011
  • جداول التجزئة الموزعة، الجزء الأول، بقلم براندون وايلي.
  • روابط جداول التجزئة الموزعة، صفحة كارليس بايرو حول أبحاث جداول التجزئة الموزعة وشبكات الند للند
  • لقطات من موقع kademlia.scs.cs.nyu.edu على موقع Archive.org
  • إنج-كيونغ لوا؛ كروكروفت، جون؛ بياس، مارسيلو؛ شارما، رافي؛ ليم، ستيف (2005). "دراسة استقصائية لمعهد مهندسي الكهرباء والإلكترونيات حول مخططات الشبكات المتراكبة" . CiteSeerX 10.1.1.111.4197 تغطي شبكات التراكب اللامركزية غير المنظمة والمنظمة بما في ذلك DHTs (Chord و Pastry و Tapestry وغيرها).
  • قياس DHT الرئيسي في قسم علوم الحاسوب، جامعة هلسنكي، فنلندا.