DEV Community

Cover image for bitcask-kv: مخزن key/value مبني على الـ log بلغة Rust، من الورقة العلمية
Abdeldjalil Chougui
Abdeldjalil Chougui

Posted on Originally published at abdeldjalilchougui.biz

bitcask-kv: مخزن key/value مبني على الـ log بلغة Rust، من الورقة العلمية

مخزن المفتاح/القيمة (key/value store) يبدو أبسط قاعدة بيانات ممكنة: put وget وdelete. الصعوبة ليست في الـ API. الصعوبة فيما يحدث حين تنقطع الكهرباء في منتصف كتابة، وحين تكبر ملفات البيانات بلا نهاية لأن القيم القديمة لا تُستردّ مساحتها، وحين يُعاد تشغيل البرنامج وعليه أن يجد كل مفتاح من جديد.

ورقة Bitcask، المكتوبة لقاعدة البيانات Riak، تجيب عن الثلاثة بفكرة واحدة: لا تعدّل البيانات في مكانها أبدًا. ألحِق كل كتابة بسجل (log)، واحتفظ بفهرس في الذاكرة، ونظّف في الخلفية. الورقة بضع صفحات فقط، مما يجعلها محرّك تخزين مناسبًا كأول تجربة. bitcask-kv هو تنفيذي بلغة Rust: ملفات بيانات للإلحاق فقط (append-only)، فهرس hash في الذاكرة (يسمّى "keydir")، دمج وضغط (merge/compaction)، ملفات hint لإقلاع سريع، واستعادة بعد الكتابات المبتورة (torn writes). هذا ما بنيته وما يعلّمه.

ماذا بنيت

ملفات بيانات للإلحاق فقط. ملفات باسم 0000000000.data وما بعده تحمل سجلات بهذا التخطيط، بترتيب little endian:

crc32 | key_len | val_len | key | value
Enter fullscreen mode Exit fullscreen mode

الكتابة تتم في أحدث ملف فقط. حين يبلغ max_file_size (64 MiB افتراضيًا) يُغلق ويبدأ ملف جديد. والحذف لا يزيل شيئًا: يُلحق tombstone (شاهد قبر)، أي سجلًا قيمة val_len فيه هي u32::MAX.

الـ keydir. بنية HashMap<key, (file_id, offset, len)> فيها مدخل لكل مفتاح حي. عملية get تبحث عن المفتاح في الذاكرة، ثم تنفّذ pread واحدة عند الموضع الصحيح وتتحقق من CRC السجل. فالقراءة تكلّف استدعاء نظام واحدًا مهما كان حجم المخزن.

الإقلاع. فتح المخزن يعيد قراءة الملفات من الأقدم إلى الأحدث ويعيد بناء الـ keydir. والملف الذي له ملف hint يُفهرَس من الـ hint بدل ذلك. مداخل الـ hint هي key_len | rec_len | rec_pos | key محمية بـ CRC، فيعرف المخزن موضع كل قيمة دون قراءة القيم.

الاستعادة بعد الانهيار. إعادة القراءة تتوقف عند أول سجل مبتور أو يفشل في فحص CRC، ويُقطع الملف عند تلك النقطة. الكتابة المبتورة في الذيل تُرمى، والكتابات الجديدة تكمل بعد آخر سجل سليم. والأمر stats يخبرك بعدد البايتات المرمية.

الـ merge. مع الوقت تمتلئ الملفات بقيم كُتب فوقها وبـ tombstones. عملية merge تنسخ السجلات الحية إلى ملفات جديدة تأخذ أعلى المعرّفات، وتكتب ملفات الـ hint الخاصة بها، ثم تحذف الملفات القديمة، الأقدم أولًا. الترتيب مهم: أي انهيار في أي لحظة أثناء الـ merge يترك مجموعة ملفات تعطي إعادةُ قراءتها الحالةَ الصحيحة.

قفل. ملف LOCK مع قفل استشاري (advisory lock) من النظام يمنع عمليتين من فتح نفس المجلد.

طريقة الاستعمال

انسخ المستودع وابنِه. أداة سطر الأوامر اسمها bitcask.

git clone https://github.com/AbdeldjalilChougui/bitcask-kv
cd bitcask-kv
cargo build --release
B=target/release/bitcask

$B ./db put greeting "hello"
echo -n "from stdin" | $B ./db put note
$B ./db get greeting
$B ./db keys
$B ./db del greeting
$B ./db stats
$B ./db merge
Enter fullscreen mode Exit fullscreen mode

الوسيط الأول هو مجلد المخزن. والأمر put يأخذ القيمة كوسيط أو من stdin.

وهو مكتبة أيضًا:

let mut db = bitcask_kv::Bitcask::open("./db")?;
db.put(b"k", b"v")?;
assert_eq!(db.get(b"k")?, Some(b"v".to_vec()));
db.delete(b"k")?;
db.merge()?;
Enter fullscreen mode Exit fullscreen mode

لاستعمال المكتبة في مشروع آخر، أضفها كـ git dependency:

cargo add --git https://github.com/AbdeldjalilChougui/bitcask-kv
Enter fullscreen mode Exit fullscreen mode

تجربة أولى جيدة: اكتب نفس المفتاح بضعة آلاف مرة، وانظر إلى stats وحجم المجلد، ثم نفّذ merge وانظر ثانية. ثم افتح أحد ملفات .data في عارض hex وابحث عن مفاتيحك.

ماذا يعلّم

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

الـ CRC هو ما يجعل هذه القاعدة تعمل. السجل نصف المكتوب في الذيل ليس دائمًا أقصر من المتوقع. قد يكون بالطول الصحيح وفي داخله بيانات عشوائية. المجموع الاختباري (checksum) في أول كل سجل هو ما يميّز به المخزن السجل السليم من المبتور. والاختبارات تغطي الحالتين: ذيلًا مقطوعًا وذيلًا فيه بيانات عشوائية.

الحذف كتابة. في سجل لا يمكنك المحو، يمكنك فقط أن تقول "هذا المفتاح ذهب" في سجل أحدث. ويجب أن يبقى الـ tombstone حتى يثبت الـ merge أنه لا يوجد ملف أقدم ما زال يحمل قيمة لذلك المفتاح.

ترتيب العمليات هو الأمان من الانهيار. الـ merge يعطي الملفات الجديدة أعلى المعرّفات ويحذف القديمة من الأقدم. ولأن إعادة القراءة تسير من الأقدم إلى الأحدث، كل حالة وسيطة تعطي الجواب الصحيح. لا شيء هنا يحتاج سجل معاملات. يحتاج الترتيب الصحيح.

زمن الإقلاع مشكلة تصميم. إعادة بناء الفهرس بقراءة كل قيمة بطيئة لمخزن كبير. ملفات الـ hint هي الحل: ملف جانبي صغير فيه المفاتيح والمواضع فقط.

فحص النموذج (model check) يجد ما تفوّته الأمثلة. اختبارات المخزن تقارنه بـ map عادية في الذاكرة عبر إعادة الفتح والـ merge وتدوير الملفات. إن اختلفا يومًا فهناك خطأ.

ما يجب معرفته

هذا مشروع تعليمي. الـ README يذكر هذه الحدود:

  • كاتب واحد، وغير آمن للخيوط (not thread-safe). الكتابة تأخذ &mut self. ولا يوجد merge متزامن.
  • الـ keydir كله في الذاكرة، كما في Bitcask. كل مفتاح يجب أن تتسع له الـ RAM. والمسح (scan) يقرأ كل ملف بيانات كاملًا في الذاكرة.
  • التلف في وسط ملف قديم يُعامَل كذيل مبتور: كل ما بعده في ذلك الملف يُرمى.
  • الديمومة اختيارية. الخيار sync_on_write معطَّل افتراضيًا. الـ CLI ينفّذ fsync بعد كل أمر؛ والمكتبة تنفّذه فقط عند sync() وعند تدوير الملف وعند الـ merge.
  • لا انتهاء صلاحية للمفاتيح ولا range scans. فهرس الـ hash لا ترتيب فيه.
  • Unix فقط. يستعمل FileExt::read_exact_at.

ما تم اختباره. الأمر cargo test يغطي ترميز السجلات والمخزن: فحص النموذج عبر إعادة الفتح والـ merge والتدوير، الاستعادة من ذيل مقطوع ومن ذيل عشوائي، تلف الـ CRC، والـ CLI. والأمر cargo bench يشغّل اختبارات أداء بـ criterion. يعطي الـ README أرقامًا مثالية من حاسوب محمول بقيم حجمها 100 بايت ودون fsync: نحو 7 µs للـ put، نحو 7 µs للـ get، نحو 10 ms للفتح بمسح 10 آلاف سجل، ونحو 12 ms لدمج 10 آلاف كتابة على ألف مفتاح. ودون fsync، هذه الأرقام تقيس مسار الكود والـ page cache، وليس القرص.

لماذا بنيته

أردت أن أفهم كيف ينجو محرّك تخزين من انهيار، وأردت أن أتعلم ذلك على تصميم صغير يتسع له ذهني كاملًا. Bitcask هو ذلك التصميم. لا توجد B-tree تحتاج موازنة، ولا write-ahead log منفصل عن البيانات: السجل هو قاعدة البيانات.

والحدود جزء من الدرس أيضًا. إبقاء كل مفتاح في الذاكرة والتخلي عن الـ range scans هما ثمن القراءة بوصول واحد إلى القرص، ورؤية هذه المقايضة في كودك تشرح لماذا اختارت محرّكات أخرى، مثل LSM trees، خيارات مختلفة.

الكود

الكود والاختبارات واختبارات الأداء موجودة على GitHub: https://github.com/AbdeldjalilChougui/bitcask-kv. الرخصة MIT، والـ issues والـ pull requests مرحّب بها. وورقة Bitcask التي يتبعها مرتبطة من الـ README.


نُشر في الأصل على abdeldjalilchougui.biz.

Top comments (0)