شرح أساسي بسيط لجدول التجزئة الموزع (DHT)

Question

هل يمكن لأي أحد أن يقدم شرحًا لكيفية عمل DHT؟

لا شيء ثقيل جدًا، فقط الأساسيات.

Answer 1

حسنًا، إنها في الأساس فكرة بسيطة جدًا.يمنحك DHT واجهة تشبه القاموس، ولكن يتم توزيع العقد عبر الشبكة.تكمن الحيلة في DHTs في أنه يتم العثور على العقدة التي يمكنها تخزين مفتاح معين عن طريق تجزئة هذا المفتاح، وبالتالي فإن مجموعات جدول التجزئة الخاصة بك أصبحت الآن عقدًا مستقلة في الشبكة.

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

أحد أمثلة DHT التي تعالج بعض هذه المشكلات هو حلقة منطقية من العقد n، تتحمل كل منها مسؤولية 1/n من مساحة المفاتيح.بمجرد إضافة عقدة إلى الشبكة، تجد مكانًا على الحلقة لتجلس بين عقدتين أخريين، وتتحمل مسؤولية بعض المفاتيح في العقد الشقيقة.يكمن جمال هذا النهج في عدم تأثر أي من العقد الأخرى في الحلقة؛يجب على العقدتين الشقيقتين فقط إعادة توزيع المفاتيح.

على سبيل المثال، لنفترض أنه في حلقة ثلاثية العقد، تحتوي العقدة الأولى على مفاتيح 0-10، والثانية 11-20 والثالثة 21-30.إذا جاءت عقدة رابعة وأدخلت نفسها بين العقدتين 3 و0 (تذكر أنهما في حلقة)، فيمكنها تحمل مسؤولية نصف مساحة المفاتيح الخاصة بالرقم 3، لذا فهي تتعامل الآن مع 26-30 والعقدة 3 تتعامل مع 21 -25.

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

اقرأ صفحة ويكيبيديا، وإذا كنت تريد حقًا أن تعرف شيئًا متعمقًا، فراجع هذا صفحة الدورة في جامعة هارفارد والتي لديها قائمة قراءة شاملة جدًا.

Answer 2

توفر DHTs نفس نوع الواجهة للمستخدم مثل جدول التجزئة العادي (البحث عن قيمة حسب المفتاح)، ولكن يتم توزيع البيانات عبر عدد عشوائي من العقد المتصلة.تحتوي ويكيبيديا على مقدمة أساسية جيدة سأتذمر منها إذا كتبت المزيد -

http://en.wikipedia.org/wiki/Distributed_hash_table

Answer 3

أود أن أضيف إلى إجابة HenryR المفيدة حيث تلقيت نظرة ثاقبة على التجزئة المتسقة.البحث عن التجزئة العادي/الساذج هو دالة لمتغيرين، أحدهما هو عدد المجموعات.يكمن جمال التجزئة المتسقة في أننا نحذف عدد الدلاء "n" من المعادلة.

في التجزئة الساذجة، المتغير الأول هو مفتاح الكائن الذي سيتم تخزينه في الجدول.سوف نسمي المفتاح "x".المتغير الثاني هو عدد الدلاء "n".لذا، لتحديد الدلو/الجهاز الذي سيتم تخزين الكائن فيه، عليك حساب:التجزئة (س) وزارة الدفاع (ن).لذلك، عندما تقوم بتغيير عدد المجموعات، فإنك تقوم أيضًا بتغيير العنوان الذي يتم تخزين كل كائن تقريبًا عليه.

قارن هذا بالتجزئة المتسقة.دعونا نعرّف "R" على أنه نطاق دالة التجزئة.R هو مجرد بعض الثوابت.في التجزئة المتسقة، يقع عنوان الكائن في hash(x)/R.نظرًا لأن بحثنا لم يعد يعتمد على عدد المجموعات، فقد انتهى بنا الأمر إلى إعادة تعيين أقل عندما نغير عدد المجموعات.

http://michaelnielsen.org/blog/consistent-hashing/

Answer 4

الدفع هذه المقالة في ويكيبيدياأو هذا شريحة باور بوينت

Answer 5

تحقق من Dynamo من Amazon، فهو يشرح تنفيذ DHT بسيط ولكنه جديد يعتمد على التجزئة المتسقة للدائرة.