لبنات البيانات الموزّعة
صمّم مخزن key-value موزّعاً
عمليتان فقط: get(key) وput(key, value). ومع ذلك وُلدت Dynamo وCassandra وRiak كلها من هذا السؤال. لا SQL ولا joins ولا schema — ومع ذلك هو أصعب تصميم في هذه الدورة، لأن كل ضمانة تريدها تكلّفك ضمانة أخرى.
ابدأ ببساطة: جهاز واحد، وhash map واحدة في الذاكرة من المفتاح إلى القيمة. القراءات والكتابات O(1) وبسرعة الميكروثانية. لكن الذاكرة متطايرة، لذا تُلحَق كل كتابة أولاً بـcommit log على القرص — ملف append-only صِرف. وعند إعادة التشغيل تعيد تشغيل السجل فتُعيد بناء الخريطة. حدّان يقتلان هذه النسخة: يجب أن تسع البيانات ذاكرة جهاز واحد، وعندما يموت ذلك الجهاز يضيع كل شيء.
- ضع العُقد والمفاتيح على حلقة hash: طبّق hash على كل عقدة لتحديد موضعها، وطبّقه بالطريقة نفسها على كل مفتاح، ثم امشِ مع عقارب الساعة لتجد مالكه.
- إضافة عقدة أو إزالتها تنقل فقط مفاتيح جارها المباشر — نحو 1/N من فضاء المفاتيح، وليس إعادة خلط كاملة كما يفعل key % N.
- امنح كل عقدة فيزيائية عدة virtual nodes موزعة على الحلقة، ليتوزع الحمل بعدل، وتستطيع الآلة الكبيرة حمل virtual nodes أكثر من الصغيرة.
نسخة واحدة لكل مفتاح تموت مع عقدتها، لذا خزّن كل مفتاح على N=3 عُقد متتالية على الحلقة. ثم اختر W (عدد العقد التي يجب أن تؤكد الكتابة) وR (عدد العقد التي يجب أن تجيب عن القراءة). مع W=2 وR=2 تحصل على W+R>N — يجب أن تتقاطع مجموعة القراءة مع مجموعة الكتابة، فترى القراءة آخر كتابة ما دامت نسخة واحدة على الأكثر متأخرة. اقلبها إلى W=1 وR=1 وستطير العمليتان — لكن كتابة أكدتها العقدة A تليها قراءة تجيب عنها العقدة B لا تعيد شيئاً. لقد اشتريت السرعة ببيانات غيرك.
الـquorum الصارم يرفض الكتابة عندما تسقط إحدى العقد المالكة — ضاعت التوافرية. أما الـsloppy quorum فيقبلها: تذهب الكتابة إلى أول W عقد سليمة على الحلقة، حتى لو كانت بديلة لا تملك المفتاح، مع hint يذكر المالك الحقيقي. وعندما يتعافى المالك، يدفع البديل الكتابة إليه ويحذف نسخته — هذا هو الـhinted handoff. بقيت متاحاً طوال العطل، وفي المقابل قبلت أن قراءة أثناء الانقطاع قد لا ترى بيانات جالسة عند بديل.
عميلان يكتبان المفتاح نفسه في اللحظة نفسها على نسختين مختلفتين — أي قيمة تفوز؟ الـvector clocks تجيب بدقة: تحمل كل نسخة قائمة (عقدة، عدّاد)، فتستطيع معرفة ما إذا كانت نسخة تنحدر من الأخرى أم أنهما تباعدتا، وعندها تحتفظ بكلتيهما وتدع القارئ يوفّق بينهما. أما last-write-wins فهو الخيار الكسول: قارن طوابع الساعة الجدارية واحذف الخاسر بصمت. سطر واحد من الشيفرة يحذف البيانات — تحديث بطيء لسلة التسوق قد يمحو تحديثاً سريعاً. لا تختر LWW إلا إذا كان فقدان كتابة مقبولاً فعلاً.
لا يوجد master هنا، لذا تكتشف العُقد الأعطال بالـgossip: كل ثانية تتبادل كل عقدة نبضاتها وبيانات الإصدارات مع بضعة أقران عشوائيين، فينتشر الاشتباه في العنقود خلال O(log N) جولة دون أي رقيب مركزي. لكن الـgossip يكشف الحياة والموت فقط. النسخ تنحرف أيضاً بصمت — handoff سقط، أو كتابة ضاعت. يصلح الـanti-entropy ذلك بأشجار Merkle: تحسب كل عقدة hash لفضاء مفاتيحها على شكل شجرة، ويقارن الأقران hash الجذر، وعند اختلافه فقط ينزلون إلى الفروع المختلفة ويزامنون تلك المفاتيح وحدها. هكذا تقارن قسماً كاملاً بـhash واحد بدل شحن كل سجل.
تحط الكتابة أولاً في الـcommit log — إلحاق تسلسلي، أسرع ما يفعله القرص — ثم في memtable، وهي بنية مرتبة في الذاكرة. وعندما تمتلئ، تُسكب على القرص كـSSTable: ملف مرتّب غير قابل للتعديل. القراءات تفحص الـmemtable ثم ملفات SSTable من الأحدث إلى الأقدم، وتتخطى الـBloom filters الملفات التي لا يمكن أن تحوي المفتاح. لا شيء يُحدَّث في مكانه أبداً، لذا تبقى الكتابات I/O تسلسلياً بسرعة الذاكرة، بينما لا يرى القرص سوى إلحاقات وcompactions دورية تدمج ملفات SSTable القديمة وتحذف النسخ المستبدلة.
لاحظ ما لم تفعله أبداً: لم تختر قط «أفضل» إعداد. N وW وR، والـsloppy مقابل الصارم، والـvector clocks مقابل LWW — كل منها مؤشر قابل للضبط، وموضعه الصحيح يعتمد على ما يخشاه منتجك: استجابات بطيئة، أم قراءات قديمة، أم كتابات ضائعة. مخزن key-value الموزّع ليس بنية بيانات؛ بل حزمة مقايضات متفاوض عليها.
مع N=3 وW=1 وR=1، ماذا يمكن أن يقرأ العميل مباشرة بعد تأكيد كتابته — ولماذا؟ (ربما القيمة القديمة أو لا شيء إطلاقاً: W=1 تعني أن نسخة واحدة خزّنت الكتابة، وR=1 تعني أن القراءة قد تخدمها نسخة أخرى لم تستلم الكتابة بعد — فمجموع W+R=2 ليس أكبر من N=3، وبالتالي لا يُضمان تقاطع مجموعتي القراءة والكتابة.)
الخطأ الكلاسيكي هو التعامل مع «التوزيع» كترقية مجانية — انثر العُقد فتحصل على القابلية للتوسع والموثوقية. كل ضمانة في هذا الدرس مؤشر تدفع ثمنه: القراءات شبه القوية تكلّف زمن استجابة (انتظار تأكيدات W وR)، والتوافرية أثناء الأعطال تكلّف اتساقاً (sloppy quorum)، ومعالجة التعارضات الآمنة تكلّف تعقيداً وحجم بيانات (vector clocks)، والكتابات السريعة تكلّف تضخيماً في القراءة وعمل compaction. أي تصميم يدّعي امتلاكها كلها دفعة واحدة يخفي الفاتورة.
بنيته طبقة فوق طبقة: عقدة واحدة بـhash map وcommit log، وconsistent hashing لتوزيع فضاء المفاتيح، وثلاث نسخ N=3 مع W=2 وR=2 لقراءات ترى كتاباتها، وsloppy quorum مع hinted handoff للنجاة من الأعطال، وvector clocks لمواجهة التزامن بصدق، وgossip وأشجار Merkle للحفاظ على صحة العنقود، ومسار كتابة بأسلوب LSM يُبقي الكتابات تسلسلية. هذا هو هيكل Dynamo — وأصبح الآن هيكلك.
خذ مخزن بيانات يشغّله فريقك — Redis أو Cassandra أو حتى Postgres بنسخ مكررة — ودوّن سلوكه الفعلي في N وW وR: كم نسخة موجودة، ومتى تُؤكَّد الكتابة، وماذا يمكن أن تعيد القراءة أثناء سقوط عقدة. ثم اعثر على موضع واحد تعتمد فيه على last-write-wins واسأل أي بيانات قد يحذفها بصمت. عشر دقائق، وستعرف عقد الاتساق الحقيقي لنظامك لأول مرة.
لبنات البيانات الموزّعة