تصميم مخزن موزع للمفاتيح والقيم

تصميم مخزن موزع للمفاتيح والقيم

يُشكّل المخزن الموزع للمفاتيح والقيم العمود الفقري لأنظمة لا حصر لها على نطاق واسع. Redis وDynamoDB وCassandra وRiak — جميعها تواجه نفس التحدي الجوهري: كيف توزع البيانات على عشرات أو مئات من العقد، وتحافظ على نسخ منها للحماية من الأعطال، وتسمح للعملاء بالعثور على أي مفتاح في أجزاء من الميلي ثانية؟ تحلّل هذه الدرس الآليتين الأساسيتين اللتين تجعلان ذلك ممكنًا: التجزئة المتسقة (أين يعيش المفتاح؟) والنسخ مع التقسيم (كم نسخة موجودة وكيف تُوزَّع؟).

لمحة سريعة عن المتطلبات

• وظيفية: put(key, value)، get(key)، delete(key). المفاتيح والقيم سلاسل بايت عشوائية.
• غير وظيفية: زمن استجابة للقراءة والكتابة أقل من 10 ms عند النسبة المئوية 99؛ البيانات تنجو من فشل أي عقدة واحدة (أو حتى رف كامل)؛ قابلية توسع أفقي للكتابة حتى عشرات العقد؛ اتساق قابل للضبط (قوي أو نهائي).
• الحجم: 1 تيرابايت من البيانات اليوم، 10 تيرابايت خلال سنتين؛ 50,000 QPS قراءة + 5,000 QPS كتابة عند الذروة.

النهج الساذج — ولماذا يفشل

أبسط استراتيجيات التقسيم هي التجزئة المعيارية: node = hash(key) % N. مع 4 عقد، قد يُجزّأ المفتاح "user:42" إلى 2 ويعيش دائمًا على العقدة 2. يعمل هذا حتى تُضيف عقدة خامسة. الآن تُعيد تقريبًا كل مفتاح التعيين إلى عقدة مختلفة. يجب عليك ترحيل ~80% من بياناتك — عملية مكلفة ومعرّضة للأخطاء تترك الكتلة غير متسقة لساعات. هذا غير مقبول لنظام حي.

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

تحل التجزئة المتسقة مشكلة إعادة التعيين بوضع كل من المفاتيح والعقد على نفس الحلقة الدائرية للتجزئة (خط عددي من 0 إلى 2³²−1 يلتف على نفسه). للعثور على عقدة مفتاح، جزّئ المفتاح إلى نقطة على الحلقة، ثم امشِ في اتجاه عقارب الساعة حتى تصل إلى أول عقدة. هذه تُسمى عقدة المنسق للمفتاح.

عند إضافة عقدة جديدة، ترث فقط المفاتيح التي تقع بينها وبين جارتها عكس عقارب الساعة. مع 100 عقدة، تنقل إضافة عقدة واحدة ما يقارب 1% من المفاتيح — لا 80%. يُسلّم إزالة عقدة مفاتيحها للعقدة التالية في اتجاه عقارب الساعة.

العقد الافتراضية — التعامل مع الحمل غير المتوازن

أحد مشاكل الحلقة الأساسية هو أن العقد قد تنتهي بشرائح ذات أحجام متباينة جدًا إذا تجمعت مواضع تجزئتها معًا. الحل هو العقد الافتراضية (vnodes): بدلًا من وضع كل عقدة فيزيائية مرة واحدة، ضعها في N مواضع عشوائية على الحلقة (تستخدم DynamoDB 150–200 vnode لكل عقدة فيزيائية). تملك الآن كل عقدة فيزيائية عدة أقواس صغيرة متناثرة بدلًا من قوس كبير واحد، فيتوازن الحمل بشكل طبيعي حتى حين تمتلك العقد الفيزيائية قدرات مختلفة. يمكن تعيين عدد أكبر من العقد الافتراضية للخادم الأكثر قدرة.

النسخ والتقسيم

تخبرك التجزئة المتسقة أين تعيش النسخة الأساسية. لكن نسخة واحدة ليست متينة — إذا فشلت تلك العقدة، ضاعت البيانات. الحل القياسي هو نسخ كل مفتاح على العقد الـN التالية في اتجاه عقارب الساعة على الحلقة (N عادةً 3). تُسمى هذه قائمة التفضيل.

مثلًا، مع N=3، يُخزَّن المفتاح "user:42" على Node B (المنسق)، وNode C (النسخة الأولى)، وNode D (النسخة الثانية). إذا تعطلت Node B، تتولى Node C القراءات والكتابات تلقائيًا. لا يلاحظ العملاء شيئًا — يتصلون فقط بقائمة التفضيل.

قراءات وكتابات الكوروم

مع N=3 نسخ، يمكنك ضبط الاتساق بمعاملين: W (كوروم الكتابة — عدد العقد التي يجب أن تُقرّ الكتابة قبل إرجاعها) وR (كوروم القراءة — عدد العقد التي يجب أن تستجيب قبل إرجاع القراءة). القاعدة هي:

• W + R > N — اتساق قوي. تتداخل عقدة واحدة على الأقل في كل قراءة مع كل كتابة. تدعم Cassandra وDynamoDB هذا مع مستوى الاتساق QUORUM.
• W = 1، R = 1 — اتساق نهائي. أسرع مسار، أقل زمن استجابة، لكن قد تقرأ قيمة قديمة في الميلي ثواني قبل اكتمال النسخ.
• W = N، R = 1 — محسّن للقراءة. يجب على كل عقدة تأكيد الكتابة (كتابات بطيئة، قراءات سريعة).

الخيارات الواقعية: DynamoDB تعتمد الاتساق النهائي افتراضيًا (أسرع وأرخص) لكنها تتيح طلب قراءات متسقة بقوة بتكلفة إضافية. تتيح Cassandra للمطورين الاختيار لكل استعلام.

التعامل مع فشل العقد — Hinted Handoff ومكافحة الانجراف

ماذا يحدث حين تكون إحدى عقد النسخ الـN معطلة مؤقتًا أثناء كتابة؟ يستخدم المنسق hinted handoff: يكتب البيانات إلى عقدة سليمة خارج قائمة التفضيل ويُرفق "تلميحًا" — "سلّم هذا إلى Node C حين تتعافى". حين تعود Node C، تُعيد العقدة صاحبة التلميح توجيه الكتابات المعلقة. يحافظ هذا على توافر الكتابة أثناء الأعطال العابرة دون التضحية بالمتانة.

للإصلاح بعد الأعطال الطويلة أو اكتشاف التباين الصامت (تلف البتات، الأخطاء البرمجية)، الأداة القياسية هي أشجار Merkle. تحتفظ كل عقدة بشجرة تجزئة فوق بياناتها. مقارنة عقدتين تعني مقارنة تجزئتيهما الجذريتين في O(1)؛ إذا اختلفتا، تتنقل في الشجرة للعثور على نطاقات الأوراق المتباينة فقط. تستخدم Cassandra هذا في عملية إصلاح مكافحة الانجراف.

تجميع كل شيء — البنية الكاملة

يجمع المخزن الموزع للمفاتيح والقيم في بيئة الإنتاج كل ما سبق:

1. حلقة التجزئة المتسقة مع 150 عقدة افتراضية لكل عقدة فيزيائية لتوزيع الأجزاء بالتساوي.
2. نسخ N=3 عبر رفوف أو مناطق توافر مختلفة حتى لا يؤدي فشل رف واحد إلى فقدان بيانات.
3. كوروم قابل للضبط (W وR قابلان للتكوين لكل طلب) ليتمكن استخدامات الإنتاجية العالية من تبادل الاتساق مقابل زمن الاستجابة.
4. Hinted Handoff للأعطال العابرة للعقد؛ مكافحة الانجراف بأشجار Merkle لإصلاح التباين طويل الأمد.
5. بروتوكول Gossip للعضوية — تتشارك كل عقدة دوريًا رؤيتها للحلقة مع نظير عشوائي. لا نقطة فشل واحدة لطوبولوجيا الكتلة.
6. محرك تخزين LSM-Tree (كـ RocksDB) لإنتاجية كتابة عالية — تذهب الكتابات إلى memtable في الذاكرة، ثم تُفرَّغ إلى SSTables مرتبة على القرص. يدمج الضغط الخلفي SSTables. أداء القراءة يأتي من فلاتر Bloom التي تتخطى الملفات غير ذات الصلة.