التسجيل

11. التسجيل

من أشدّ مسائل تصميم نظم الملفات إثارةً للاهتمام مسألة الاستعادة بعد الانهيار. وتنشأ هذه المسألة لأنّ كثيرًا من عمليّات نظام الملفات تتطلّب كتاباتٍ متعدّدةً إلى القرص، وقد يترك الانهيار الحاصل بعد أداء مجموعةٍ فرعيّةٍ فقط من تلك الكتابات نظامَ الملفات المخزَّن على القرص في حالةٍ غير متّسقة. فمثلًا، لنفترض حدوثَ انهيارٍ أثناء اقتطاع ملفّ. ويستلزم الاقتطاع كتابةَ كتلتين على القرص (على الأقلّ): إحداهما تحتوي على عقدة الفهرس (inode)، والأخرى تحتوي على جزءٍ من خريطة البِتّات الحرّة (bitmap)؛ فيجب ضبط طول عقدة الفهرس على صفر، ومسح أرقام الكتل الواردة فيها، وضبط بِتّات خريطة البِتّات الخاصّة بكتل الملفّ على صفر (إشارةً إلى تحريرها). والانهيار الحاصل بعد إحدى الكتابتين، ولكن قبل أن تتاح للنواة فرصةُ أداء الكتابة الثانية، سيترك نظام الملفات على القرص في حالةٍ غير صحيحة. فإن حدثت كتابة خريطة البِتّات وحدها، كانت النتيجة بعد الانهيار وإعادة التشغيل عقدةَ فهرسٍ طولُها لا يساوي صفرًا تُشير إلى كتلٍ موسومةٍ بالحرّة؛ وإن حدثت كتابة عقدة الفهرس وحدها، كانت النتيجة كتلٍ لا يستخدمها أيّ ملفّ، لكنها غير موسومةٍ بالحرّة أيضًا.

والحالة الثانية حميدةٌ إلى حدّ نسبيّ، لكنّ عقدة فهرسٍ تُشير إلى كتلةٍ محرَّرةٍ يُرجَّح أن تسبّب مشكلاتٍ خطيرةً بعد إعادة التشغيل. فبعد إعادة التشغيل، قد تُخصّص النواة تلك الكتلة لملفّ آخر، فيصير لدينا ملفّان مختلفان يُشيران دون قصدٍ إلى الكتلة نفسها. ولو كان xv6 يدعم عدّة مستخدمين، لكانت هذه الحالة مشكلةً أمنيّةً، إذ سيتمكّن مالك الملفّ القديم من قراءة كتل الملفّ الجديد المملوك لمستخدمٍ آخر والكتابة فيها.

يحلّ xv6 مسألة الانهيارات التي تحدث أثناء عمليّات نظام الملفات بأسلوبٍ مبسّطٍ من التسجيل. فنداء النظام في xv6 لا يكتب بنيات بيانات نظام الملفات المخزَّنة على القرص مباشرةً، بل يضع وصفًا لجميع كتابات القرص التي يرغب في أدائها في سجلٍّ (log) على القرص. وحين يسجّل نداء النظام جميع كتاباته، يكتب سجلَّ تثبيتٍ (commit) خاصًّا إلى القرص، يشير إلى أنّ السجلّ يحتوي على عمليّةٍ كاملة. وعند تلك النقطة، ينسخ نداء النظام الكتابات إلى بنيات بيانات نظام الملفات على القرص. وبعد اكتمال تلك الكتابات، يمحو نداء النظام السجلّ عن القرص.

فإن انهار النظام وأُعيد تشغيله، فإنّ شيفرة نظام الملفات تستعيد الحالة من الانهيار على النحو الآتي، قبل تشغيل أيّ عمليّة. فإن كان السجلّ موسومًا بأنّه يحتوي على عمليّةٍ كاملة، تنسخ شيفرة الاستعادة الكتابات إلى مواضعها الصحيحة في نظام الملفات على القرص. وإن لم يكن السجلّ موسومًا بذلك، فإنّ شيفرة الاستعادة تتجاهله. وتنتهي شيفرة الاستعادة بمحو السجلّ.

فلماذا يحلّ سجلّ xv6 مسألة الانهيارات التي تحدث أثناء عمليّات نظام الملفات؟ فإن حدث الانهيار قبل تثبيت العمليّة، فلن يكون السجلّ على القرص موسومًا بالاكتمال، وستتجاهله شيفرة الاستعادة، وستكون حالة القرص كأنّ العمليّة لم تبدأ أصلًا. وإن حدث الانهيار بعد تثبيت العمليّة، فإنّ الاستعادة ستعيد تنفيذ جميع كتابات العمليّة، مُكرّرةً إيّاها ربّما إن كانت العمليّة قد بدأت بكتابتها إلى بنية البيانات على القرص. وفي الحالتين، يجعل السجلّ العمليّات ذرّيّةً إزاء الانهيارات: فبعد الاستعادة، إمّا أن تظهر جميع كتابات العمليّة على القرص، أو ألّا تظهر أيٌّ منها.

11.1 تصميم السجلّ

يقع السجلّ في موضعٍ ثابتٍ معروف (انظر الشكل 10.2)، تحدّده الكتلة الفائقة (superblock). وهو يتكوّن من كتلة ترويسة يتبعها تسلسلٌ من نسخ الكتل المحدَّثة («الكتل المسجَّلة»). وتحتوي كتلة الترويسة على مصفوفةٍ من أرقام الكتل، رقمٌ واحدٌ لكلّ كتلةٍ من الكتل المسجَّلة، وعلى عدّادٍ لكتل السجلّ. وقيمة العدّاد في كتلة الترويسة على القرص إمّا صفر، وهو ما يشير إلى عدم وجود معاملةٍ (transaction) في السجلّ، أو قيمةٌ غير صفريّة، وهو ما يشير إلى أنّ السجلّ يحتوي على معاملةً مكتملةً مثبَّتةٍ بالعدد المشار إليه من الكتل المسجَّلة. ويكتب xv6 كتلة الترويسة عند تثبيت معاملةً، لا قبله، ويضبط العدّاد على صفر بعد نسخ الكتل المسجَّلة إلى نظام الملفات. ومن ثمّ، فإنّ الانهيار الحاصل في منتصف معاملةٍ سيُنتج عدّادًا قيمته صفر في كتلة ترويسة السجلّ؛ أمّا الانهيار الحاصل بعد تثبيتٍ فسيُنتج عدّادًا غير صفريّ.

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

وتُعرَف فكرة تثبيت عدّة معاملاتٍ معًا بـالتثبيت الجماعي (group commit). وهو يقلّل عدد عمليّات القرص لأنّه يُوزّع الكلفة الثابتة للتثبيت على عمليّاتٍ متعدّدة. كما يقدّم التثبيت الجماعي إلى نظام القرص عددًا أكبر من الكتابات المتزامنة في الوقت نفسه، وهو ما قد يسمح للقرص بكتابتها جميعًا في دورةٍ قرصيّةٍ واحدة. ومشغّل xv6 للعِتاد virtio لا يدعم هذا النوع من التجميع (batching)، لكنّ تصميم نظام ملفات xv6 يسمح به.

ومن تَبِعات التثبيت الجماعي الدقيقة أنّه يجعل آثار نداء الكتابة غير متزامنة: أي أنّ الكتل التي عدّلها ليست مضمونةَ الوجود على القرص، حتّى بعد رجوع نداء النظام إلى التطبيق. فمثلًا، حين تنتهي معاملة كتابةٍ، قد تكون معاملةٌ أخرى قد بدأت، وستُثبَّت معاملة الكتابة مع المعاملة الثانية مجموعةً واحدةً، فيتأخّر أثر الكتابة على القرص حتّى تُثبَّت المعاملة الثانية. وإذا أراد تطبيقٌ أن ينتظر حتّى تصبح تعديلاته دائمةً (أي موجودةً على القرص)، فبإمكانه استدعاء نداء النظام sync بعد نداء الكتابة؛ وsync ينتظر حتّى يُثبَّت التثبيت الجماعي الجاري.

يُخصّص xv6 مقدارًا ثابتًا من المساحة على القرص لاحتواء السجلّ. ويجب أن يقتصر مجموع الكتل التي تكتبها نداءات النظام في معاملةً واحدةً على هذه المساحة. ولهذا تَبِعاتٌ اثنتان. فلا يجوز السّماح لأيّ نداء نظامٍ واحدٍ بكتابة عددٍ من الكتل المتمايزة يزيد على المساحة المتاحة في السجلّ. وهذه ليست مشكلةً في معظم نداءات النظام، لكنّ اثنين منها قد يكتبان كتلًا كثيرة: write وunlink. فكتابة ملفّ كبيرٍ قد تكتب كتلَ بياناتٍ كثيرةً وكتل خريطة بِتّاتٍ كثيفةً، فضلًا عن كتلة عقدة فهرس؛ وكذلك قد يكتب إلغاء ربط ملفّ كبيرٍ كتلَ خريطة بِتّاتٍ كثيرةً وعقدةَ فهرس. أمّا نداء النظام write في xv6 فيقطّع الكتابات الكبيرة إلى كتاباتٍ أصغرَ متناسبةٍ مع السجلّ، وunlink لا يُسبّب مشكلاتٍ لأنّ نظام ملفات xv6 لا يستخدم في العمليّة سوى كتلةٍ واحدةٍ من خريطة البِتّات. وتَبِعةُ المساحة المحدودة للسجلّ الأخرى هي أنّ نظام التسجيل لا يستطيع السّماح لنداء نظامٍ بالبدء إلّا إذا كان واثقًا من أنّ كتابات ذلك النداء ستقبلُ المساحة المتبقّية في السجلّ.

11.2 الشيفرة: التسجيل

وهذا مثالٌ على استخدام نموذجيّ للسجلّ في نداء نظام:

  begin_op();
  ...
  bp = bread(...);
  bp->data[...] = ...;
  log_write(bp);
  ...
  end_op();

تنتظر begin_op حتّى ينتهي نظام التسجيل من التثبيت الجاري، وحتّى تتوفّر مساحةٌ غير محجوزةٍ كافيةً في السجلّ لاستيعاب كتابات هذا النداء. ويحسب log.outstanding عدد نداءات النظام التي حجزت مساحةً في السجلّ؛ والمساحة المحجوزة الكلّيّة هي log.outstanding مضروبًا في MAXOPBLOCKS. وزيادةُ log.outstanding تحجز المساحة وتمنع حدوث تثبيتٍ أثناء نداء النظام هذا في الوقت نفسه. وتفترض الشيفرة على نحوٍ متحفّظٍ أنّ كلّ نداء نظامٍ قد يكتب حتّى MAXOPBLOCKS كتلةً متمايزةً.

وتعمل log_write كنائبٍ عن bwrite. فهي تسجّل رقم كتلة الكتلة في الذاكرة، محتجزةً لها موضعًا في السجلّ على القرص، وتُثبّت المخزن المؤقّت في مخبأ الكتل كي يمنع مخبأ الكتل من إخراجها. فيجب أن تبقى الكتلة في المخبأ حتّى يتمّ تثبيتها: فحتّى تلك اللحظة، تكون النسخة المخبأة هي السجلّ الوحيد للتعديل؛ ولا يمكن كتابتها إلى موضعها على القرص إلّا بعد التثبيت؛ كما يجب أن ترى القراءات الأخرى في المعاملة نفسها التعديلات. وتلاحظ log_write حين تُكتب كتلةٌ عدّة مرّاتٍ خلال معاملةً واحدة، فتخصّص لتلك الكتلة الموضع نفسه في السجلّ. ويُسمّى هذا التحسين عادةً الامتصاص (absorption). ومن الشائع أنّ، مثلًا، تُكتب كتلةُ القرص التي تحتوي على عقد فهرس عدّة ملفّاتٍ عدّة مرّاتٍ ضمن معاملةً واحدة. وبامتصاص عدّة كتابات قرصيّةٍ في كتابةٍ واحدة، يستطيع نظام الملفات توفير مساحة السجلّ وتحقيق أداءٍ أفضل؛ لأنّ نسخةً واحدةً فقط من كتلة القرص يجب كتابتها إلى القرص.

تخفض end_op أوّلًا عدّاد نداءات النظام قيد التنفيذ. فإن كان العدّاد صفرًا الآن، تثبّت المعاملة الحاليّة باستدعاء commit(). وهناك أربع مراحل في هذه العمليّة. فـwrite_log() تنسخ كلّ كتلةٍ عُدِّلت في المعاملة من مخبأ الكتل إلى موضعها في السجلّ على القرص. وwrite_head() تكتب كتلة الترويسة إلى القرص: وهذه هي نقطة التثبيت، والانهيار الحاصل بعد تلك الكتابة سيُؤدّي إلى استعادةٍ تُعيد تنفيذ كتابات المعاملة من السجلّ. وinstall_trans تقرأ كلّ كتلةٍ من السجلّ وتكتبها إلى موضعها الصحيح في نظام الملفات. وأخيرًا تكتب end_op ترويسة السجلّ بعدّادٍ قيمته صفر؛ ولا بدّ أن يحدث ذلك قبل أن تبدأ المعاملة التالية بكتابة الكتل المسجَّلة، حتّى لا يُؤدّي انهيارٌ إلى أن تستخدم الاستعادة ترويسة إحدى المعاملات مع الكتل المسجَّلة للمعاملة اللاحقة.

أحد الافتراضات الجوهريّة في تنفيذ end_op هو أنّ write_head تُحدّث كتلة الترويسة بصورةٍ ذرّيّة: إمّا كاملةً أو لا تحديثًا على الإطلاق. وتذكّر من الفصل 10 أنّ الكتلة في xv6 هي قطاعان من القرص، لكنّ ترويسة السجلّ تتّسع في القطاع الأوّل، فلا مشكلةَ من ثمّ حتّى لو كان القرص يضمن ذرّيّة تحديث قطاعٍ واحدٍ فقط.

تُستدعى recover_from_log من initlog، التي تُستدعى من fsinit خلال الإقلاع قبل أن تعمل أوّل عمليّة مستخدم (proc.c:526). وهي تقرأ ترويسة السجلّ، وتُحاكي أفعال end_op إذا دَلّت الترويسة على أنّ السجلّ يحتوي على معاملةً مثبَّتة.

ومن أمثلة استخدام السجلّ ما يحدث في filewrite. وتبدو المعاملة على النحو الآتي:

      begin_op();
      ilock(f->ip);
      r = writei(f->ip, ...);
      iunlock(f->ip);
      end_op();

وهذه الشيفرة ملفوفةٌ في حلقةٍ تقطّع الكتابات الكبيرة إلى معاملاتٍ فرديّةٍ لا تضمّ سوى بضع كتلٍ في المرّة، تفاديًا لفيض السجلّ. واستدعاء writei يكتب كتلًا كثيرةً كجزءٍ من هذه المعاملة: عقدةَ فهرس الملفّ، وكتلةً أو أكثر من كتل خريطة البِتّات، وبعض كتل البيانات.

11.3 العالم الواقعيّ

إنّ نظام التسجيل في xv6 غير كفؤ. فلا يمكن أن يجري التثبيت بالتزامن مع نداءات نظام الملفات. ويسجّل النظام كتلًا كاملةً، حتّى لو تغيّرت بضع بايتاتٍ فقط في كتلةٍ واحدة. وهو يؤدّي كتاباتٍ متزامنةً للسجلّ، كتلةً في المرّة، يُرجَّح أن كلّ واحدةٍ منها تستلزم دورةً قرصيّةً كاملة. وأنظمة التسجيل الحقيقيّة تعالج كلّ هذه المشكلات. - التسجيل ليس الطريقة الوحيدة لتوفير الاستعادة من الانهيار. فأنظمة الملفات المبكّرة كانت تستخدم كاسحًا خلال إعادة التشغيل (برنامج fsck في UNIX مثلًا) ليفحص كلّ ملفّ ومجلّد، وقوائم كتل وعقد الفهارس الحرّة، باحثًا عن التناقضات وحالًا لها. وقد يستغرق الكسح ساعاتٍ في نظم الملفات الكبيرة، وهناك حالاتٌ لا يكون فيها ممكنًا حلّ التناقضات بصورةٍ تجعل نداءات النظام الأصليّة ذرّيّة. والاستعادة من سجلٍّ أسرعُ بكثيرٍ وتجعل نداءات النظام ذرّيّةً في مواجهة الانهيارات.

printk("log write %d: %d %d %d\n", addr, bp->blockno, off, n);

$ echo hi > f

log write 47: 47 368 16
log write 936: 936 0 2
log write 936: 936 2 1