DBDB: قاعدة بيانات سرير الكلب

كأحدث عازف باس (وأحياناً تينور) في Countermeasure، يسعى تافي إلى كسر القالب... وأحياناً ببساطة تجاهل وجوده. وهذا صحيح بلا شك عبر تنوع أماكن عمله في مسيرته: IBM (يعمل بلغة C و Perl)، و FreshBooks (كل ما في ذلك)، و Points.com (يعمل بلغة Python)، والآن في PagerDuty (يعمل بلغة Scala). إلى جانب ذلك—حين لا يكون يركض بدراجته القابلة للطي من نوع Brompton—قد تجده يلعب Minecraft مع ابنه أو يمارس رياضة الباركور (أو تسلق الصخور، أو غيرها من المغامرات) مع زوجته. إنه يحيك بالطريقة القارية.

مقدمة

DBDB (Dog Bed Database) مكتبة Python تطبّق قاعدة بيانات بسيطة من نوع المفتاح/القيمة. تتيح لك ربط مفتاح بقيمة، وتخزين هذا الارتباط على القرص لاسترجاعه لاحقاً.

تسعى DBDB إلى الحفاظ على البيانات في مواجهة أعطال الحاسوب وحالات الخطأ. كما تتجنب الاحتفاظ بكل البيانات في الذاكرة العشوائية (RAM) في وقت واحد، تمكينك من تخزين بيانات أكثر مما تملك من ذاكرة عشوائية.

الذاكرة

أتذكر أول مرة انحشرت فيها حقاً بسبب خلل. حين أتممت كتابة برنامجي بـ BASIC ثم شغّلته، ظهرت بكسلات لامعة غريبة على الشاشة، وتوقف البرنامج مبكراً. حين رجعت لأنظر في الشيفرة، كانت الأسطر القليلة الأخيرة من البرنامج قد اختفت.

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

من تلك اللحظة فصاعداً، اهتتمت بتخصيص الذاكرة. تعلمت عن المؤشرات (pointers) وكيفية تخصيص الذاكرة عبر malloc. تعلمت كيف كانت بنى بياناتي موزَّعة في الذاكرة. وتعلمت أن أكون حذراً جداً في كيفية تغييرها.

بعد بضع سنوات، وأنا أقرأ عن لغة موجَّهة بالعمليات اسمها Erlang، تعلمت أنها لا تحتاج فعلاً إلى نسخ البيانات لإرسال الرسائل بين العمليات، لأن كل شيء غير قابل للتغيير. ثم اكتشفت بنى البيانات غير القابلة للتغيير في Clojure، وبدأ الأمر ينغرس فعلاً.

حين قرأت عن CouchDB عام 2013، إنما ابتسمت وأومأت برأسي، متعترفاً بالبنى والآليات الخاصة بإدارة البيانات المعقدة وهي تتغير.

تعلمت أنه بإمكانك تصميم أنظمة مبنية حول بيانات غير قابلة للتغيير.

ثم وافقت على كتابة فصل (chapter) من كتاب.

ظننت أن وصف مفاهيم تخزين البيانات الأساسية في CouchDB (بحسب ما فهمته) سيكون ممتعاً.

أثناء محاولتي كتابة خوارزمية (algorithm) لشجرة ثنائية تُعدِّل الشجرة في مكانها، انزعجت من مدى تعقيد الأمور. كان عدد الحالات الحدّية، ومحاولة استنتاج كيفية تأثير التغييرات في جزء من الشجرة على أجزاء أخرى، يلوي رأسي. لم أكن أعرف على الإطلاق كيف سأشرح كل ذلك.

وتذكر الدروس المستفادة، ألقيت نظرة على خوارزمية تكرارية (recursive) لتحديث أشجار ثنائية غير قابلة للتغيير، فإذا بها مباشرة نسبياً.

تعلمت، مرة أخرى، أن استنتاج الأمور التي لا تتغير أسهل بكثير.

هكذا تبدأ القصة.

لماذا هو مثير للاهتمام؟

معظم المشاريع تحتاج إلى نوع ما من قواعد البيانات. لا ينبغي لك حقاً أن تكتب قواعد بيانات خاصة بك؛ فهناك حالات حدّية كثيرة ستصيبك، حتى لو كنت تكتب JSON إلى القرص فحسب:

• ماذا يحدث إذا نفد من نظام الملفات لديك المساحة؟
• ماذا يحدث إذا ماتت بطارية حاسوبك المحمول أثناء الحفظ؟
• ماذا لو تجاوز حجم بياناتك الذاكرة المتاحة؟ (غير مرجّح لمعظم التطبيقات على أجهزة الحاسوب المكتبية الحديثة&hellip؛ لكنه غير مرجّح إطلاقاً بالنسبة إلى جهاز محمول أو تطبيق ويب من جهة الخادم.)

لكن إذا كنت تريد أن تفهم كيف تتعامل قاعدة البيانات مع كل هذه المشكلات، فإن كتابة واحدة بنفسك قد تكون فكرة جيدة.

التقنيات والمفاهيم التي نتناقش هنا ينبغي أن تنطبق على أي مشكلة تحتاج إلى سلوك عقلاني يمكن التنبؤ به عند مواجهة الفشل.

وبمناسبة الفشل...

توصيف الفشل

غالباً ما توصَّف قواعد البيانات مدى التزامها بخصائص ACID: الذرّية، والاتساق، والعزل، والمتانة.

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

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

لدينا أيضاً مشكلات أخرى في صيانة النظام علينا التفكير فيها. البيانات المهملة (stale) لا تُستعاد في هذه النسخة التنفيذية، لذا فإن التحديثات المتكررة (حتى على المفتاح نفسه) ستستهلك في النهاية كل مساحة القرص. (وستكتشف بعد قليل سبب حدوث ذلك.) تسمّي PostgreSQL عملية استعادة المساحة هذه «تنظيفاً» (vacuuming) (بحيث تصبح مساحة الصفوف القديمة متاحة لإعادة الاستخدام)، وتسمّيها CouchDB «ضغطاً» (compaction) (بإعادة كتابة أجزاء البيانات «الحيّة» في ملف جديد، ثم نقلها فوق القديمة بشكل ذرّي).

يمكن توسيع DBDB بإضافة ميزة ضغط، لكنها تُركت تمريناً للقارئ^[1].

معمارية DBDB

تفصل DBDB بين هموم «ضع هذا على القرص في مكان ما» (كيف تُوزَّع البيانات داخل ملف؛ الطبقة الفيزيائية) والبنية المنطقية للبيانات (شجرة ثنائية في هذا المثال؛ الطبقة المنطقية) عن محتوى مخزن المفتاح/القيمة (ارتباط المفتاح a بالقيمة foo؛ واجهة API العامة).

تفصل كثير من قواعد البيانات بين الجوانب المنطقية والفيزيائية، لأن من المفيد غالباً توفير تنفيذات بديلة لكل جانب للحصول على خصائص أداء مختلفة، مثل مساحات الجداول في DB2: SMS (ملفات داخل نظام ملفات) مقابل DMS (جهاز كتل خام)، أو تنفيذات محركات بديلة في MySQL.

اكتشاف التصميم

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

في هذا الفصل، سنفترض أن DBDB مشروع مكتمل، ونسير في أرجائه لتعلّم كيف يعمل. فلنستكشف بنية المشروع كاملاً أولاً.

الوحدات التنظيمية

الوحدات مرتبة هنا بحسب البُعد عن المستخدم النهائي؛ أي أن الوحدة الأولى هي التي يحتاج مستخدم هذا البرنامج إلى معرفتها أكثر من غيرها، بينما الأخيرة شيء ينبغي أن يكون تفاعله معها ضئيلاً جداً.

• يعرّف tool.py أداة سطر أوامر لاستكشاف قاعدة بيانات من نافذة طرفية.

• يعرّف interface.py صنفاً (DBDB) يطبّق واجهة API قاموس Python باستخدام التنفيذ الملموس BinaryTree. هكذا تستخدم DBDB داخل برنامج Python.

• يعرّف logical.py الطبقة المنطقية. إنها واجهة مجرّدة إلى مخزن مفتاح/قيمة.

  • توفّر LogicalBase واجهة API للتحديثات المنطقية (مثل get و set و commit) وتُحيل التنفيذ الفعلي للتحديثات إلى صنف فرعي ملموس. كما تتولى إدارة أقفال التخزين وإحالة العقد الداخلية.

  • ValueRef كائن Python يشير إلى كتلة ثنائية (blob) مخزَّنة في قاعدة البيانات. تتيح هذه الوساطة تفادي تحميل مخزن البيانات بأكمله إلى الذاكرة دفعة واحدة.

• يعرّف binary_tree.py خوارزمية شجرة ثنائية ملموسة تقع خلف الواجهة المنطقية.

  • توفّر BinaryTree تنفيذاً ملموساً لشجرة ثنائية، مع توابع لـ جلب أزواج المفتاح/القيمة وإدراجها وحذفها. تمثّل BinaryTree شجرة غير قابلة للتغيير؛ تُنفَّذ التحديثات بإعادة شجرة جديدة تتشارك بنية مشتركة مع الشجرة القديمة.

  • BinaryNode ينفّذ عقدة في الشجرة الثنائية.

  • BinaryNodeRef نوع متخصص من ValueRef يعرف كيف يهيّئ BinaryNode للتحويل إلى صيغة نصية واستعادتها منها.

• يعرّف physical.py الطبقة الفيزيائية. يوفّر الصنف Storage تخزين سجلات دائم (persistent)، (في معظمه) للإلحاق فقط (append-only).

نمت هذه الوحدات من محاولة إعطاء كل صنف مسؤولية واحدة. بعبارة أخرى، ينبغي أن يكون لكل صنف سبب واحد فقط للتغييّر.

قراءة قيمة

سنبدأ بأبسط حالة: قراءة قيمة من قاعدة البيانات. فلنرَ ما يحدث حين نحاول جلب القيمة المرتبطة بالمفتاح foo في example.db:

$ python -m dbdb.tool example.db get foo

هذا يشغّل الدالة main() من الوحدة dbdb.tool:

# dbdb/tool.py
def main(argv):
    if not (4 <= len(argv) <= 5):
        usage()
        return BAD_ARGS
    dbname, verb, key, value = (argv[1:] + [None])[:4]
    if verb not in {'get', 'set', 'delete'}:
        usage()
        return BAD_VERB
    db = dbdb.connect(dbname)          # CONNECT
    try:
        if verb == 'get':
            sys.stdout.write(db[key])  # GET VALUE
        elif verb == 'set':
            db[key] = value
            db.commit()
        else:
            del db[key]
            db.commit()
    except KeyError:
        print("Key not found", file=sys.stderr)
        return BAD_KEY
    return OK

تفتح الدالة connect() ملف قاعدة البيانات (ربما تنشئه، لكنها لا تكتب فوقه أبداً) وتعيد نسخة من DBDB:

# dbdb/__init__.py
def connect(dbname):
    try:
        f = open(dbname, 'r+b')
    except IOError:
        fd = os.open(dbname, os.O_RDWR | os.O_CREAT)
        f = os.fdopen(fd, 'r+b')
    return DBDB(f)

# dbdb/interface.py
class DBDB(object):

    def __init__(self, f):
        self._storage = Storage(f)
        self._tree = BinaryTree(self._storage)

نرى مباشرةً أن DBDB لديه مرجع إلى نسخة من Storage، لكنه أيضاً يشارك ذلك المرجع مع self._tree. لماذا؟ ألَا يستطيع self._tree أن يدير الوصول إلى التخزين بنفسه؟

سؤال أي الكائنات «تملك» مورداً ما هو غالباً سؤال مهم في التصميم، لأنه يمنحنا القرائن حول التغييرات التي قد تكون غير آمنة. فلنبقي هذا السؤال في أذهاننا بصدد المضي قدماً.

ما إن نتوفّر على نسخة من DBDB، يصبح جلب القيمة عند key عبر بحث في قاموس (db[key])، مما يجعل مفسّر Python يستدعي DBDB.__getitem__().

# dbdb/interface.py
class DBDB(object):
# ...
    def __getitem__(self, key):
        self._assert_not_closed()
        return self._tree.get(key)

    def _assert_not_closed(self):
        if self._storage.closed:
            raise ValueError('Database closed.')

يتحقق __getitem__() من أن قاعدة البيانات ما زالت مفتوحة عبر استدعاء _assert_not_closed. آه! هنا نرى على الأقل سبباً واحداً يحتاج DBDB من أجله وصولاً مباشراً إلى نسخة Storage عندنا: كي يفرض الشروط المسبقة. (هل توافق على هذا التصميم؟ هل تستطيع أن تتخيّل طريقة أخرى لتحقيق ذلك؟)

ثم يسترجع DBDB القيمة المرتبطة بـ key في _tree الداخلي عبر استدعاء _tree.get()، وهو مقدَّم من LogicalBase:

# dbdb/logical.py
class LogicalBase(object):
# ...
    def get(self, key):
        if not self._storage.locked:
            self._refresh_tree_ref()
        return self._get(self._follow(self._tree_ref), key)

يتحقق get() مما إذا كنا قد أقفلنا التخزين. لسنا متأكدين تماماً من سبب وجود قفل هنا، لكن يمكننا أن نخمّن أنه موجود على الأرجح للسماح للكاتبين بتسلسل الوصول إلى البيانات. وماذا يحدث إذا لم يكن التخزين مقفلاً؟

# dbdb/logical.py
class LogicalBase(object):
# ...
def _refresh_tree_ref(self):
        self._tree_ref = self.node_ref_class(
            address=self._storage.get_root_address())

تعيد _refresh_tree_ref تعيين «منظور» الشجرة على البيانات إلى ما هو موجود حالياً على القرص، مما يتيح لنا إجراء قراءة محدَّثة تماماً.

وماذا لو كان التخزين مقفلاً فعلاً حين نحاول القراءة؟ يعني هذا أن هناك على الأرجح عملية أخرى تغيّر البيانات التي نريد قراءتها الآن؛ ومن غير المرجح أن تكون قراءتنا محدَّثة مع الحالة الحالية للبيانات. يُعرف هذا عموماً بـ«القراءة المهملة» (dirty read). يتيح هذا النمط للقراء الكثيرين الوصول إلى البيانات دون أن يقلقهم الأمر يوماً بالحجب، على حساب أن تكون القراءة قديمة قليلاً.

لننظر الآن إلى كيفية استرجاعنا للبيانات فعلياً:

# dbdb/binary_tree.py
class BinaryTree(LogicalBase):
# ...
    def _get(self, node, key):
        while node is not None:
            if key < node.key:
                node = self._follow(node.left_ref)
            elif node.key < key:
                node = self._follow(node.right_ref)
            else:
                return self._follow(node.value_ref)
        raise KeyError

هذا بحث قياسي في شجرة ثنائية، يتبع المراجع إلى عقدها. نعلم من قراءة توثيق BinaryTree أن Nodes و NodeRefs كائنات قيمية (value objects): فهي غير قابلة للتغيير ولا يتغير محتواها إطلاقاً. تُنشأ Nodes بمفتاح وقيمة مرتبطين، وابنَين يسار ويمين. ولا تتغير تلك الارتباطات أيضاً. لا يتغيّر محتوى BinaryTree بالكامل بصورة مرئية إلا عند استبدال عقدة الجذر. وهذا يعني أننا لا نحتاج للقلق بشأن محتوى شجرتنا وهو يتغير أثناء أدائك للبحث.

ما إن تُعثر على القيمة المرتبطة، حتى تُكتب إلى stdout بواسطة main() دون إضافة أي أسطر جديدة إضافية، حفاظاً على بيانات المستخدم تماماً.

الإدراج والتحديث

الآن سنضبط المفتاح foo على القيمة bar في example.db:

$ python -m dbdb.tool example.db set foo bar

مرة أخرى، هذا يشغّل الدالة main() من الوحدة dbdb.tool. وبما أننا رأينا هذه الشيفرة من قبل، فسنكتفي بإبراز الأجزاء المهمة:

# dbdb/tool.py
def main(argv):
    ...
    db = dbdb.connect(dbname)          # CONNECT
    try:
        ...
        elif verb == 'set':
            db[key] = value            # SET VALUE
            db.commit()                # COMMIT
        ...
    except KeyError:
        ...

هذه المرة نضبط القيمة عبر db[key] = value، وهو ما يستدعي DBDB.__setitem__().

# dbdb/interface.py
class DBDB(object):
# ...
    def __setitem__(self, key, value):
        self._assert_not_closed()
        return self._tree.set(key, value)

يتحقق __setitem__ من أن قاعدة البيانات ما زالت مفتوحة، ثم يخزّن الارتباط من key إلى value في _tree الداخلي عبر استدعاء _tree.set().

أما _tree.set() فيقدّمه LogicalBase:

# dbdb/logical.py
class LogicalBase(object):
# ...
    def set(self, key, value):
        if self._storage.lock():
            self._refresh_tree_ref()
        self._tree_ref = self._insert(
            self._follow(self._tree_ref), key, self.value_ref_class(value))

يتحقق set() أولاً من قفل التخزين:

# dbdb/storage.py
class Storage(object):
    ...
    def lock(self):
        if not self.locked:
            portalocker.lock(self._f, portalocker.LOCK_EX)
            self.locked = True
            return True
        else:
            return False

وهناك أمران مهمان ينبغي ملاحظتهما هنا:

• قفلنا مقدَّم من مكتبة خارجية لأقفال الملفات اسمها portalocker.
• تُعيد lock() القيمة False إذا كانت قاعدة البيانات مقفلة مسبقاً، وTrue في غير ذلك.

بالعودة إلى _tree.set()، يمكننا الآن أن نفهم لماذا فحص قيمة إرجاع lock() من الأساس: فهو يتيح لنا استدعاء _refresh_tree_ref للحصول على أحدث مرجع لعقدة الجذر حتى لا نفقد تحديثات قد تكون قد أجرتها عملية أخرى منذ آخر مرة حدّثنا فيها الشجرة من القرص. ثم يستبدل عقدة جذر الشجرة بشجرة جديدة تحتوي زوج المفتاح/القيمة المُدرَج (أو المحدَّث).

إدراج مفاتيح الشجرة أو تحديثها لا يغيّر أي عقدة، لأن _insert() يعيد شجرة جديدة. تشارك الشجرة الجديدة الأجزاء غير المتغيرة مع الشجرة السابقة توفيراً للذاكرة وزمن التنفيذ. ومن الطبيعي تنفيذ هذا بشكل تكراري:

# dbdb/binary_tree.py
class BinaryTree(LogicalBase):
# ...
    def _insert(self, node, key, value_ref):
        if node is None:
            new_node = BinaryNode(
                self.node_ref_class(), key, value_ref, self.node_ref_class(), 1)
        elif key < node.key:
            new_node = BinaryNode.from_node(
                node,
                left_ref=self._insert(
                    self._follow(node.left_ref), key, value_ref))
        elif node.key < key:
            new_node = BinaryNode.from_node(
                node,
                right_ref=self._insert(
                    self._follow(node.right_ref), key, value_ref))
        else:
            new_node = BinaryNode.from_node(node, value_ref=value_ref)
        return self.node_ref_class(referent=new_node)

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

ربما لاحظت شيئاً غريباً هنا: لم نُجرِ أي تغيير على أي شيء على القرص بعد. كل ما فعلناه هو تعديل منظورنا للبيانات الموجودة على القرص بنقل عقد الشجرة إلى مواضع جديدة.

لكي نكتب هذه التغييرات فعلاً على القرص، نحتاج إلى استدعاء صريح لـ commit()، وقد رأيناه كجزء ثانٍ من عملية set في tool.py في بداية هذا القسم.

ينطوي التثبيت على كتابة كل الحالة المهملة الموجودة في الذاكرة، ثم حفظ عنوان القرص لعقدة جذر الشجرة الجديدة.

انطلاقاً من واجهة API:

# dbdb/interface.py
class DBDB(object):
# ...
    def commit(self):
        self._assert_not_closed()
        self._tree.commit()

أما تنفيذ _tree.commit() فيأتي من LogicalBase:

# dbdb/logical.py
class LogicalBase(object)
# ...
    def commit(self):
        self._tree_ref.store(self._storage)
        self._storage.commit_root_address(self._tree_ref.address)

تعرف جميع NodeRefs كيف تهيّئ نفسها للتحويل إلى صيغة نصية على القرص عبر طلب من أبنائها أن يفعلوا الشيء نفسه عبر prepare_to_store():

# dbdb/logical.py
class ValueRef(object):
# ...
    def store(self, storage):
        if self._referent is not None and not self._address:
            self.prepare_to_store(storage)
            self._address = storage.write(self.referent_to_string(self._referent))

أما self._tree_ref في LogicalBase فهو في الواقع BinaryNodeRef (صنف فرعي من ValueRef) في هذه الحالة، لذا فإن التنفيذ الملموس لـ prepare_to_store() هو:

# dbdb/binary_tree.py
class BinaryNodeRef(ValueRef):
    def prepare_to_store(self, storage):
        if self._referent:
            self._referent.store_refs(storage)

أما BinaryNode المعني، أي _referent، فيطلب من مراجعه أن تخزّن نفسها:

# dbdb/binary_tree.py
class BinaryNode(object):
# ...
    def store_refs(self, storage):
        self.value_ref.store(storage)
        self.left_ref.store(storage)
        self.right_ref.store(storage)

وهذا يتكرر إلى أسفل الشجرة لأي NodeRef يحمل تغييرات لم تُكتب بعد (أي لا يملك _address).

ها نحن من جديد في أعلى المكدس ضمن طريقة store في ValueRef. الخطوة الأخيرة من store() هي تحويل هذه العقدة إلى صيغة نصية وحفظ عنوان تخزينها:

# dbdb/logical.py
class ValueRef(object):
# ...
    def store(self, storage):
        if self._referent is not None and not self._address:
            self.prepare_to_store(storage)
            self._address = storage.write(self.referent_to_string(self._referent))

في هذه اللحظة يُضمن أن _referent الخاص بـ NodeRef يملك عناوين متاحة لجميع مراجعه الخاصة، فنحوّله إلى صيغة نصية بإنشاء سلسلة بايتات تمثّل هذه العقدة:

# dbdb/binary_tree.py
class BinaryNodeRef(ValueRef):
# ...
    @staticmethod
    def referent_to_string(referent):
        return pickle.dumps({
            'left': referent.left_ref.address,
            'key': referent.key,
            'value': referent.value_ref.address,
            'right': referent.right_ref.address,
            'length': referent.length,
        })

يُعدّ تحديث العنوان في طريقة store() تقنياً تغييراً لـ ValueRef. ولأنه لا أثر له على القيمة المرئية للمستخدم، فيمكننا اعتباره غير قابل للتغيير.

ما إن يكتمل store() على _tree_ref الجذري (داخل LogicalBase.commit())، نعلم أن جميع البيانات قد كُتبت على القرص. أصبح بإمكاننا الآن تثبيت عنوان الجذر عبر استدعاء:

# dbdb/physical.py
class Storage(object):
# ...
    def commit_root_address(self, root_address):
        self.lock()
        self._f.flush()
        self._seek_superblock()
        self._write_integer(root_address)
        self._f.flush()
        self.unlock()

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

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

لأننا نكتب البيانات الجديدة على القرص ونستدعي استدعاء النظام fsync^[2] قبل أن نكتب عنوان عقدة الجذر، تصبح البيانات غير المثبَّتة غير قابلة للوصول. وبالمقابل، ما إن يُحدَّث عنوان عقدة الجذر، نعلم أن جميع البيانات التي يشير إليها موجودة أيضاً على القرص. بهذه الطريقة تكون عمليات التثبيت متينة أيضاً.

انتهينا!

كيف توفّر NodeRefs الذاكرة

لتجنّب الاحتفاظ ببنية الشجرة كاملةً في الذاكرة في الوقت نفسه، حين تُقرأ عقدة منطقية من القرص يُحمَّل عنوانا قرص ابنيها الأيسر والأيمن (وكذلك قيمتها) إلى الذاكرة. يتطلب الوصول إلى الأبناء وقيمهم استدعاء دالة إضافياً واحدة هي NodeRef.get() لإحالة البيانات (أي «جلبها فعلاً»).

كل ما نحتاجه لبناء NodeRef هو عنوان:

+---------+
| NodeRef |
| ------- |
| addr=3  |
| get()   |
+---------+

استدعاء get() عليه سيعيد العقدة الملموسة، مع مراجع تلك العقدة في صورة NodeRef:

+---------+     +---------+     +---------+
| NodeRef |     | Node    |     | NodeRef |
| ------- |     | ------- | +-> | ------- |
| addr=3  |     | key=A   | |   | addr=1  |
| get() ------> | value=B | |   +---------+
+---------+     | left  ----+
                | right ----+   +---------+
                +---------+ |   | NodeRef |
                            +-> | ------- |
                                | addr=2  |
                                +---------+

حين لا تُثبَّت تغييرات الشجرة، فإنها موجودة في الذاكرة بمراجع من الجذر نزولاً إلى الأوراق المتغيّرة. لم تُحفظ التغييرات على القرص بعد، لذا فالعقد المتغيّرة تحتوي مفاتيح وقيماً ملموسة لا عناوين قرص. يستطيع العملية التي تكتب أن ترى التغييرات غير المثبَّتة وأن تجري المزيد من التغييرات قبل إصدار أمر تثبيت، لأن NodeRef.get() سيعيد القيمة غير المثبَّتة إن وُجدت؛ فلا فرق بين البيانات المثبَّتة وغير المثبَّتة عند الوصول إليها عبر واجهة API. ستظهر جميع التحديثات للقراء الآخرين على أنها ذرّية لأن التغييرات لا تصبح مرئية حتى يُكتب عنوان عقدة الجذر الجديدة على القرص. تُحجب التحديثات المتزامنة بواسطة ملف قفل (lockfile) على القرص. يُكتسب القفل عند أول تحديث، ويُحرَّر بعد التثبيت.