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

كتبه بركات يوم السبت, 29 آب 2015

جداول التجزئة hash tables أحد تراكيب البيانات الأساسية، حيث تسمح لك بإيجاد قيمة في جدول عن طريق مفتاح فريد، غالباً تعقيدها في المتوسط $\textrm{O}(1)$.

تعتمد جداول التجزئة على عناصر أساسية:

  • دالة التجزئة $h(k)$، حيث تختزل مفتاح طويل، كالنصوص، إلى قيم أصغر بحجم ثابت، كعدد بطول 32 بت.
  • جدول التجزئة، والذي تخزن فيه المفاتيح مع القيم، غالباً مصفوفة عادية بحجم $N$.
  • جزئية الضغط، حيث تحول القيم التي تعيدها دالة التجزئة إلى موقع في جدول التجزئة، عادة تتم عن طريق أخذ باقي القيمة التي تعيدها $h(k)$ على طول الجدول $N$، أي $h(k) \bmod N$ 1.

تمثل جداول التجزئة النواة التي تعتمد عليها خوام التخزين المؤقت2 والتخزين السحابي، ففي خدوام التخزين المؤقت، الجدول عبارة عن مجموعة خوادم بعدد $N$، عند البحث عن قيمة مخزنة بأحد هذه الخوام عن طريق مفتاح $k$، نحسب $h(k)$ ثم نحدد أي خادم يحتوي على هذه القيمة عن طريق أخذ باقي قسمة نتيجة $h(k)$ على عدد الخوام، وسنحصل على رقم بين $[0, N - 1]$ يمثل موقع الخادم الذي يحتوي هذه القيمة، مثلاً:

>>> def where_is_key(key, servers):
...     return hash(key) % servers
...
>>>
>>> where_is_key("user-id-1-data", 10)
2
>>> where_is_key("user-id-2-data", 10)
3
>>> where_is_key("user-id-3-data", 10)
8
>>>

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

>>> def where_is_key(key, servers):
...     return hash(key) % servers
...
>>>
>>> where_is_key("user-id-1-data", 11)
3
>>> where_is_key("user-id-2-data", 11)
7
>>> where_is_key("user-id-3-data", 11)
10
>>>

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

أحد الحلول المستخدمة لهذه المشكلة هي التجزئة المتسقة consistent hashing، حيث تعمل على تقليل عدد القيم المنقولة في المتوسط إلى $K/N$، حيث أن $K$ عدد المفاتيح أو القيم، حيث تهدف إلى التخلص من سبب المشكلة في الطريقة السابقة، جزئية الضغط.

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

يتم في هذه الطريقة حساب $h(k)$ لكل خادم، بأخذ مثلاً عنوان الـIP أو اسم الـDNS لهذا الخادم وتمريره لـ$h(k)$، ووضعها مرتبة في دائرة كما في الصورة، الدائرة مجرد مصفوفة عادية، لكننا نتخيلها كما لو أن آخرها متصل بأولها، يفضل استخدام خوارزمية آمنة لحساب $h(k)$ مثل md5 لتجنب حصول تصادم في أسماء الخوادم وتجنب صداع الـ3probing، الآن عندما يأتينا مفتاح $k$، فإننا نحسب $h(k)$ لهذا المفتاح ونبحث في تلك الدائرة عن أكبر خادم قيمة $H_i$ فيه أصغر أو تساوي قيمة $h(k)$، أي $H_i \ge h(k)$، إذا كانت $h(k)$ أكبر من أي $H_i$، فإننا ندور لأول خادم $H_0$، هذا يعني أن جميع المفاتيح الأكبر من $H_0$ وأقل أو تساوي $H_1$ تذهب إلى الخادم $H_1$ وهكذا في دائرة، والقيم الأكبر من $H_5$ تدور لتذهب إلى $H_0$.

الآن عند إضافة خادم لنسمه $H_\alpha$، لنقل أنه بين $H_3$ و $H_4$، فإننا سنحتاج فقط إلى نقل القيم الأصغر أو تساوي $H_\alpha$ من $H_4$، والخوادم الباقية لن تتأثر، وفي حال إزالة خادم أو تعطله، فالخادم الذي يليه سيتولى مسؤولية هذا الخادم الذي ذهب حتى يعود.

توزيع القيم في الدائرة

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

يمكن تقليل هذا التأثير عن طريق إنشاء أكثر من مدخل لنفس القيمة في الجدول، مدخلات وهمية بأسماء مختلفة لكنها تشير لنفس القيمة، مثلاً قيمة اسمها 10.0.0.1، يمكن إدخلها 25 مرة بأسماء متقاربة مثل 10.0.0.1:1 و 10.0.0.1:2 إلى 10.0.0.1:25، وهكذا، زيادة المدخلات الوهمية يساهم في تحسين توزيع القيم في الدائرة، لاحظ في الصورة على اليمين، الأول يمثل توزيع المدخلات بدون إنشاء مدخلات وهمية، والثانية باستخدام 25 مدخل وهمي لنفس القيمة، الثالثة 50، والرابعة 100، لأ أستطيع أن أحدد لك العدد المناسب، فهذه حدسية.

يلزم الإنتباه أنه بإضافة المدخلات الوهمية فإن خادم ما قد يجاور جميع الخوادم، أو حتى يجاور نفسه، لكنها ليست مشكلة من ناحية الأداء، فعند إضافة خادم جديد، قد تحتاج لنقل قيم من جميع الخوادم، لكن عدد القيم المنقولة يبقى تقريباً نفسه، وحتماً أقل من عدد القيم الازم نقلها لو استخدمت الطريقة التي أشرت لها في بداية المقال.

ستجد كود بسيط هنا يعطيك فكرة عن طريقة تطبيق التجزئة المتسقة، الكود مكتوب بـJava، لكنه لايصلح للإستخدام ويحتاج تعديل، مثلاً تحديد الخوادم الازم نقل البيانات منها، وكذلك وظيفة إزالة خادم.


  1. أحياناً تستخدم العملية الثنائية $\textrm{and}$ بدلاً من باقي القسمة إذا كان طول الجدول $N$ أحد مضاعفات 2، فبدلاً من استخدام $h(k) \bmod N$، يمكننا استخدام $h(k) \textrm{ and } N - 1$، فقط إذا كان طول الجدول $N = 2^i$، فحساب $\textrm{and}$ يستغرق دوارت معالجة أقل بكثير من باقي القسمة في معظم المعالجات. 

  2. خوادم التخزين المؤقت cache servers، أشهرها Memcached، تسمح لك بتخزين قيمة مؤقتاً يستغرق حسابها مجهود كبير، كاستعلام قاعدة بيانات معقد، فبدلاً من إعادة الإستعلام في كل مرة وإجهاد قاعدة البيانات، فيمكنك تخزينها مؤقتاً باستخدام مفتاح يميز هذه القيمة والحصول على البيانات المخزنة لاحقاً باستخدام هذا المفتاح، يمكن تحديث القيمة المخزنة كل فترة أو عند إجراء تغيير على قاعدة البيانات. 

  3. بطئ حساب $h(k)$ إذا استخدمنا خوارزمية آمنة مثل md5 ليست مشكلة، فالمفاتيح صغيرة وليست بيانات كبيرة، ولكن لو استخدمنا خوارزميات أسرع مثل djb2 فاحتمال حصول تصادم عالي بحيث أن خادمين لهما نفس البصمة.