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

في علم الحاسوب ، التجزئة المتسقة ^{[ 1 ] [ 2 ]} هي نوع خاص من تقنيات التجزئة بحيث عند تغيير حجم جدول التجزئة ، فقط${\displaystyle n/m}$يجب إعادة تعيين المفاتيح في المتوسط ​​حيث${\displaystyle n}$هو عدد المفاتيح و${\displaystyle m}$يمثل عدد الخانات. يوزع التجزئة المتسقة مفاتيح التخزين المؤقت بالتساوي عبر الأجزاء ، حتى في حالة تعطل بعض الأجزاء أو عدم توفرها. ^{[ 3 ]} في المقابل، في معظم جداول التجزئة التقليدية، يؤدي تغيير عدد خانات المصفوفة إلى إعادة تعيين جميع المفاتيح تقريبًا لأن التعيين بين المفاتيح والخانات يتم تحديده بواسطة عملية نمطية .

تستخدم شبكات توصيل المحتوى التجزئة المتسقة لأنها مفيدة في توزيع طلبات المحتوى من مجموعة متغيرة من خوادم الويب. يُنسب الفضل إلى تيم بيرنرز لي، ومخترع خوارزميات التجزئة المتسقة، إلى دانيال ليوين ، في حل مشكلة النقاط المائلة التي عانت منها شبكة الويب العالمية في التسعينيات. ^{[ 4 ]}

صاغ ديفيد كارغر وزملاؤه في معهد ماساتشوستس للتكنولوجيا مصطلح "التجزئة المتسقة" لاستخدامه في التخزين المؤقت الموزع ، وخاصةً للويب . [ ^{5 ] وقدّمت} هذه الورقة البحثية، المنشورة عام 1997 في ندوة نظرية الحوسبة، مصطلح "التجزئة المتسقة" كوسيلة لتوزيع الطلبات بين مجموعة متغيرة من خوادم الويب. ^{[ 6 ]} ويمثل كل خانة خادمًا في نظام أو مجموعة خوادم موزعة. ولا تتطلب إضافة خادم أو إزالته (أثناء قابلية التوسع أو انقطاع الخدمة) سوى${\displaystyle num\_keys/num\_slots}$يُعاد ترتيب العناصر عند تغيير عدد الخانات (أي الخوادم). يشير المؤلفون إلى التجزئة الخطية وقدرتها على التعامل مع إضافة الخوادم وإزالتها بشكل متسلسل، بينما تسمح التجزئة المتسقة بإضافة الخوادم وإزالتها بترتيب عشوائي. ^{[ 1 ]} أُعيد استخدام الورقة لاحقًا لمعالجة التحدي التقني المتمثل في تتبع ملف في شبكات الند للند، مثل جدول التجزئة الموزع . ^{[ 7 ] [ 8 ]}

استخدمت شركة Teradata هذه التقنية في قاعدة بياناتها الموزعة ، التي أُصدرت عام ١٩٨٦، على الرغم من أنها لم تستخدم هذا المصطلح. ولا تزال Teradata تستخدم مفهوم جدول التجزئة لتحقيق هذا الغرض تحديدًا. تأسست شركة Akamai Technologies عام ١٩٩٨ على يد العالِمين دانيال ليوين وإف . طومسون لايتون (المؤلفين المشاركين للمقال الذي صاغ مصطلح "التجزئة المتسقة"). في شبكة توصيل المحتوى الخاصة بشركة Akamai، ^{[ ٩ ]} تُستخدم التجزئة المتسقة لموازنة الحمل داخل مجموعة من الخوادم، بينما تُستخدم خوارزمية دمج مستقرة لموازنة الحمل عبر المجموعات. ^{[ ٢ ]}

استُخدمت التجزئة المتسقة أيضًا للحد من تأثير الأعطال الجزئية في تطبيقات الويب الكبيرة، وذلك لتوفير تخزين مؤقت قوي دون التسبب في تداعيات عطل على مستوى النظام بأكمله. ^{[ 10 ]} كما تُعد التجزئة المتسقة حجر الزاوية في جداول التجزئة الموزعة (DHTs)، التي تستخدم قيم التجزئة لتقسيم مساحة المفاتيح عبر مجموعة موزعة من العقد، ثم تُنشئ شبكة تراكبية من العقد المتصلة التي توفر استرجاعًا فعالًا للعقد باستخدام المفتاح.

تُعدّ تقنية التجزئة Rendezvous ، التي صُممت عام 1996، تقنيةً أبسط وأكثر عمومية . وهي تحقق أهداف التجزئة المتسقة باستخدام خوارزمية الوزن العشوائي الأعلى (HRW) المختلفة تمامًا.

في مشكلة موازنة الأحمال ، على سبيل المثال، عندما يتعين تعيين كائن BLOB إلى أحد${\displaystyle n}$في حالة الخوادم الموجودة على مجموعة ، يمكن استخدام دالة تجزئة قياسية لحساب قيمة التجزئة لهذا الكائن الثنائي الكبير (BLOB)، بافتراض أن القيمة الناتجة للتجزئة هي${\displaystyle \beta }$نقوم بتنفيذ عمليات معيارية باستخدام عدد من الخوادم (${\displaystyle n}$(في هذه الحالة) لتحديد الخادم الذي يمكننا وضع الكائن الثنائي الكبير (BLOB) فيه:${\displaystyle \zeta =\beta \ \%\ n}$وبالتالي، سيتم وضع الكائن الثنائي الكبير (BLOB) في الخادم الذي${\displaystyle {\text{server ID}}}$هو خليفة لـ${\displaystyle \zeta }$في هذه الحالة. ومع ذلك، عند إضافة خادم أو إزالته أثناء انقطاع الخدمة أو توسيع نطاقها (عندما${\displaystyle n}$التغييرات)، يجب إعادة تعيين ونقل جميع الكائنات الثنائية الكبيرة (BLOBs) في كل خادم بسبب إعادة التجزئة ، ولكن هذه العملية مكلفة.

صُممت تقنية التجزئة المتسقة لتجنب مشكلة إعادة تعيين كل كائن ثنائي كبير (BLOB) عند إضافة خادم أو إزالته من المجموعة. وتتمثل الفكرة الأساسية في استخدام دالة تجزئة تربط كلاً من الكائن الثنائي الكبير والخوادم بدائرة الوحدة، عادةً${\displaystyle 2\pi }$الراديان. على سبيل المثال،${\displaystyle \zeta =\Phi \ \%\ 360}$(أين${\displaystyle \Phi }$هي دالة تجزئة لمعرف كائن ثنائي كبير (BLOB) أو خادم (مثل عنوان IP أو UUID ). يُخصص كل كائن ثنائي كبير (BLOB) للخادم التالي الذي يظهر على الدائرة بترتيب عقارب الساعة. عادةً ما تُستخدم خوارزمية البحث الثنائي أو البحث الخطي للعثور على "موقع" أو خادم لوضع هذا الكائن الثنائي الكبير (BLOB) فيه.${\displaystyle O(\log N)}$أو${\displaystyle O(N)}$التعقيدات على التوالي؛ وفي كل تكرار، والذي يحدث بطريقة في اتجاه عقارب الساعة، عملية${\displaystyle \zeta \ \leq \ \Psi }$(أين${\displaystyle \Psi }$تُجرى هذه العملية (قيمة الخادم داخل المجموعة) لتحديد الخادم المناسب لوضع كائن البيانات الثنائية الكبيرة (BLOB). يضمن هذا توزيعًا متساويًا لكائنات البيانات الثنائية الكبيرة على الخوادم. والأهم من ذلك، في حال تعطل خادم وإزالته من دائرة التوزيع، لا يلزم إعادة تعيين سوى كائنات البيانات الثنائية الكبيرة التي كانت مرتبطة بالخادم المتعطل إلى الخادم التالي في اتجاه عقارب الساعة. وبالمثل، عند إضافة خادم جديد، يُضاف إلى دائرة التوزيع، ولا يلزم إعادة تعيين سوى كائنات البيانات الثنائية الكبيرة المرتبطة بهذا الخادم.

الأهم من ذلك، عند إضافة خادم أو إزالته، فإن الغالبية العظمى من كائنات BLOB تحتفظ بتعيينات الخادم السابقة، وإضافة${\displaystyle n^{th}}$الخادم يسبب فقط${\displaystyle 1/n}$جزء من كائنات BLOB المراد نقلها. على الرغم من أن عملية نقل كائنات BLOB بين خوادم التخزين المؤقت في المجموعة تعتمد على السياق، إلا أنه عادةً ما يُحدد خادم التخزين المؤقت المُضاف حديثًا "خادمه السابق" وينقل منه جميع كائنات BLOB التي تنتمي إلى هذا الخادم (أي التي تكون قيمة تجزئتها أقل من قيمة تجزئته). مع ذلك، في حالة ذاكرة التخزين المؤقت لصفحات الويب ، لا تتضمن معظم التطبيقات نقلًا أو نسخًا، بافتراض أن حجم كائن BLOB المُخزن مؤقتًا صغير بما يكفي. عندما يصل طلب إلى خادم تخزين مؤقت مُضاف حديثًا، يحدث خطأ في ذاكرة التخزين المؤقت ، ويتم إرسال طلب إلى خادم الويب الفعلي ، ويتم تخزين كائن BLOB مؤقتًا محليًا للطلبات المستقبلية. تُزال كائنات BLOB الزائدة على خوادم التخزين المؤقت المستخدمة سابقًا وفقًا لسياسات إخلاء ذاكرة التخزين المؤقت . ^{[ 11 ]}

يتطلب استخدام التجزئة المتسقة بفعالية لتحقيق توازن الأحمال في التطبيق العملي عددًا من التحسينات على التقنية الأساسية. في المخطط الأساسي المذكور أعلاه، إذا تعطل خادم، تُعاد جميع كائنات BLOB الخاصة به إلى الخادم التالي بترتيب عقارب الساعة، مما قد يُضاعف حمل ذلك الخادم. قد لا يكون هذا مرغوبًا فيه. لضمان إعادة توزيع أكثر توازنًا لكائنات BLOB عند تعطل الخادم، يمكن تجزئة كل خادم إلى مواقع متعددة على دائرة الوحدة. عند تعطل خادم، تُعاد كائنات BLOB المخصصة لكل نسخة من نسخه على دائرة الوحدة إلى خادم مختلف بترتيب عقارب الساعة، وبالتالي إعادة توزيع كائنات BLOB بشكل أكثر توازنًا. يتعلق تحسين آخر بحالة يصبح فيها كائن BLOB واحد "مُستَخدَمًا بكثرة" ويتم الوصول إليه عددًا كبيرًا من المرات، مما يستدعي استضافته على خوادم متعددة. في هذه الحالة، يمكن تخصيص كائن BLOB لخوادم متجاورة متعددة من خلال اجتياز دائرة الوحدة بترتيب عقارب الساعة. تنشأ اعتبارات عملية أكثر تعقيدًا عندما يتم تجزئة كائنين من نوع BLOB بالقرب من بعضهما البعض في دائرة الوحدة، ويصبح كلاهما "ساخنًا" في الوقت نفسه. في هذه الحالة، سيستخدم كلا الكائنين نفس مجموعة الخوادم المتجاورة في دائرة الوحدة. يمكن تحسين هذا الوضع باختيار كل كائن دالة تجزئة مختلفة لربط الخوادم بدائرة الوحدة. ^{[ 2 ]}

تُعدّ تقنية التجزئة Rendezvous ، التي صُممت عام 1996، تقنيةً أبسط وأكثر عمومية، وتسمح بالاتفاق الموزع بالكامل على مجموعة من${\displaystyle k}$خيارات من بين مجموعة محتملة من${\displaystyle n}$خيارات. في الواقع، يمكن إثبات أن التجزئة المتسقة هي حالة خاصة من التجزئة التلاقية. وبسبب بساطتها وعموميتها، تُستخدم التجزئة التلاقية الآن بدلاً من التجزئة المتسقة في العديد من التطبيقات.

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

التعقيدات الزمنية التقاربية لـ${\displaystyle N}$العقد (أو الفتحات) و${\displaystyle K}$مفاتيح

	طاولة الهاش الكلاسيكية	التجزئة المتسقة
أضف عقدة	${\displaystyle O(K)}$	${\displaystyle O(K/N+\log N)}$
إزالة عقدة	${\displaystyle O(K)}$	${\displaystyle O(K/N+\log N)}$
ابحث عن مفتاح	${\displaystyle O(1)}$	${\displaystyle O(\log N)}$
أضف مفتاحًا	${\displaystyle O(1)}$	${\displaystyle O(\log N)}$
إزالة مفتاح	${\displaystyle O(1)}$	${\displaystyle O(\log N)}$

ال${\displaystyle O(K/N)}$يمثل متوسط ​​تكلفة إعادة توزيع المفاتيح و${\displaystyle O(\log N)}$تكمن صعوبة التجزئة المتسقة في حقيقة أن البحث الثنائي بين زوايا العقد مطلوب للعثور على العقدة التالية على الحلقة.

تشمل الأمثلة المعروفة للاستخدام المتسق للتجزئة ما يلي:

• تقسيم البيانات الآلي في Couchbase ^{[ 16 ]}
• خدمة تخزين الكائنات في OpenStack بلغة Swift ^{[ 17 ]}
• مكون التقسيم في نظام التخزين Dynamo الخاص بأمازون ^{[ 18 ]}
• تقسيم البيانات في أباتشي كاساندرا ^{[ 19 ]}
• تقسيم البيانات في ScyllaDB ^{[ 20 ]}
• تقسيم البيانات في فولدمورت ^{[ 21 ]}
• موجّه التجزئة المتسق لـ Akka ^{[ 22 ]}
• Riak ، قاعدة بيانات موزعة تعتمد على المفتاح والقيمة ^{[ 23 ]}
• Gluster ، وهو نظام ملفات تخزين متصل بالشبكة ^{[ 24 ]}
• شبكة توصيل المحتوى من أكاماي ^{[ 25 ]}
• تطبيق دردشة ديسكورد ^{[ 26 ]}
• موازنة تحميل طلبات gRPC إلى ذاكرة تخزين مؤقتة موزعة في SpiceDB ^{[ 27 ]}
• خوارزمية الوتر ^{[ 28 ]}
• نظام تخزين الكائنات MinIO ^{[ 29 ]}

• فهم التجزئة المتسقة
• التجزئة المتسقة بواسطة مايكل نيلسن في 3 يونيو 2009
• التجزئة المتسقة، داني ليوين، وإنشاء أكاماي
• التجزئة المتسقة بالقفز: خوارزمية تجزئة سريعة، ذات ذاكرة قليلة، ومتسقة
• التجزئة المتزامنة: بديل للتجزئة المتسقة
• تطبيقات بلغات مختلفة:
  • ج
  • لغة سي++
  • سي شارب
  • إرلانغ
  • يذهب
  • جافا
  • PHP
  • روبي
  • بايثون
  • بايثون (مرة أخرى)
  • بيرل
  • بيرل 6