شجرة دمج ذات بنية سجلية

في علوم الحاسوب ، تُعدّ شجرة الدمج ذات البنية السجلية (المعروفة أيضًا باسم شجرة LSM أو LSMT ^{[ 1 ]} ) بنية بيانات تتميز بخصائص أداء تجعلها جذابة لتوفير وصول مُفهرس إلى الملفات ذات حجم الإدخال العالي، مثل بيانات سجلات المعاملات . تحتفظ أشجار LSM، كغيرها من أشجار البحث ، بأزواج المفتاح والقيمة. تُخزّن أشجار LSM البيانات في بنيتين منفصلتين أو أكثر، كلٌّ منها مُحسَّن لوسيط التخزين الأساسي الخاص بها؛ ويتم مزامنة البيانات بين البنيتين بكفاءة، على دفعات.

إحدى أبسط نسخ شجرة LSM هي شجرة LSM ثنائية المستوى. ^{[ 2 ]} وكما وصفها باتريك أونيل ، تتألف شجرة LSM ثنائية المستوى من بنيتين شجريتين ، تُسميان C0 _و C1 _. تكون C0 _أصغر حجمًا وموجودة بالكامل في الذاكرة، بينما تكون _C1 موجودة على القرص. تُضاف السجلات الجديدة إلى مكون C0 الموجود في الذاكرة _. إذا تسبب الإضافة في تجاوز مكون C0 _حدًا معينًا للحجم، تُزال مجموعة متصلة من الإدخالات من C0 _وتُدمج في C1 _على القرص. تنبع خصائص أداء أشجار LSM من حقيقة أن كل مكون مُصمم خصيصًا لخصائص وسيط التخزين الأساسي، وأن البيانات تُنقل بكفاءة عبر الوسائط على دفعات متجددة، باستخدام خوارزمية تُشبه فرز الدمج . يتضمن هذا التصميم كتابة البيانات بشكل تسلسلي بدلًا من سلسلة من طلبات الوصول العشوائي المنفصلة. يؤدي هذا التحسين إلى تقليل إجمالي وقت البحث في محركات الأقراص الصلبة (HDDs) ووقت الوصول في محركات الأقراص ذات الحالة الصلبة (SSDs).

تستخدم معظم أشجار LSM المستخدمة عمليًا مستويات متعددة. يُحفظ المستوى 0 في الذاكرة الرئيسية، ويمكن تمثيله باستخدام شجرة. تُنظم البيانات الموجودة على القرص في مجموعات بيانات مُرتبة. تحتوي كل مجموعة بيانات على بيانات مُرتبة حسب مفتاح الفهرس. يمكن تمثيل المجموعة على القرص كملف واحد، أو كمجموعة من الملفات ذات نطاقات مفاتيح غير متداخلة. لإجراء استعلام على مفتاح معين للحصول على قيمته المرتبطة، يجب البحث في شجرة المستوى 0 وفي كل مجموعة بيانات. يُعد إصدار Stepped-Merge من شجرة LSM ^{[ 3 ]} نوعًا مُعدّلًا من شجرة LSM يدعم مستويات متعددة مع هياكل شجرية متعددة في كل مستوى.

قد يظهر مفتاح معين في عدة عمليات تشغيل، ويختلف تأثير ذلك على الاستعلام باختلاف التطبيق. فبعض التطبيقات ترغب ببساطة في الحصول على أحدث زوج من المفتاح والقيمة لمفتاح محدد. بينما تتطلب تطبيقات أخرى دمج القيم بطريقة ما للحصول على القيمة الإجمالية المطلوبة. على سبيل المثال، في أباتشي كاساندرا ، تمثل كل قيمة صفًا في قاعدة البيانات، وقد تحتوي الإصدارات المختلفة من الصف على مجموعات مختلفة من الأعمدة. ^{[ 4 ]}

من أجل خفض تكلفة الاستعلامات، يجب على النظام تجنب الوضع الذي يكون فيه عدد كبير جدًا من عمليات التشغيل.

تم اقتراح امتدادات لطريقة "المستويات" لتضمين هياكل شجرة B+ ، مثل bLSM ^{[ 5 ]} وDiff-Index ^{[ 6 ]} . صُممت شجرة LSM في الأصل لأحمال العمل التي تتطلب كتابة مكثفة. ومع تزايد أحمال عمل القراءة والكتابة المتزامنة ضمن بنية تخزين شجرة LSM، قد تعاني عمليات الوصول إلى بيانات القراءة من زمن استجابة عالٍ وإنتاجية منخفضة نتيجةً لعمليات إبطال البيانات المخزنة مؤقتًا في مخازن البيانات المؤقتة المتكررة بواسطة عمليات ضغط شجرة LSM. ولإعادة تمكين التخزين المؤقت الفعال للوصول السريع إلى البيانات، تم اقتراح شجرة مدمجة مخزنة مؤقتًا ذات بنية سجلية (LSbM-tree) وتطبيقها ^{[ 7 ] .}

العمليات

يكتب

في أشجار LSM، صُممت عمليات الكتابة لتحسين الأداء عن طريق تقليل عمليات الإدخال/الإخراج العشوائية والاستفادة من عمليات الكتابة المتسلسلة على القرص. عند بدء عملية كتابة، تُخزن البيانات مؤقتًا في مكون داخل الذاكرة، وغالبًا ما يُنفذ ذلك باستخدام بنية بيانات مُرتبة مثل قائمة التخطي أو شجرة B+ .

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

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

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

يؤدي هذا التصميم إلى تكاليف كتابة مُستهلكة قدرها $O\left({T\cdot L \over B}\right)$ لتسوية سياسات الدمج، حيث $T$ نسبة الحجم بين المستويات، $L$ هو عدد المستويات، و $B$ ^[⁸^] هو عدد الإدخالات في الصفحة الواحدة.

البحث عن نقطة

تسترجع عملية البحث عن نقطة القيمة المرتبطة بمفتاح محدد. في أشجار LSM، ونظرًا لبنية متعددة المستويات وعدم قابلية مكونات القرص للتغيير، تتضمن عمليات البحث عن نقطة فحص عدة مستويات لضمان استرجاع أحدث قيمة للمفتاح.

تبدأ العملية بالبحث في المكون الموجود في الذاكرة (C0)، والذي يحتوي على أحدث البيانات. وبما أن هذا المكون مُنظّم على شكل بنية مُرتّبة، فإن البحث يكون فعالاً. إذا تم العثور على المفتاح هنا، يتم إرجاع قيمته فوراً.

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

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

تتوقف عملية البحث بمجرد العثور على المفتاح، مما يضمن إرجاع أحدث نسخة. إذا وصل البحث إلى المستوى الأخير دون العثور على المفتاح، يستنتج النظام أن المفتاح غير موجود.

تعقيد البحث عن نقطة هو $O(L)$ بدون استخدام مرشحات بلوم، حيث يجب البحث في كل مستوى. أما مع مرشحات بلوم، فتنخفض تكلفة عمليات البحث التي لا تُسفر عن نتائج بشكل ملحوظ. $O\left(L\cdot e^{-{\frac {M}{N}}}\right)$ حيث M هو الحجم الإجمالي لمرشح بلوم وN هو عدد المفاتيح. بالنسبة لعمليات البحث عن المفاتيح الموجودة، تكون التكلفة هي $O(1)$ بسبب وجود مرشحات بلوم. ^{[ 8 ]}

استعلام النطاق

يسترجع استعلام النطاق جميع أزواج المفاتيح والقيم ضمن نطاق محدد. تتضمن هذه العملية مسح مكونات متعددة عبر البنية الهرمية لشجرة LSM وتوحيد الإدخالات لضمان نتائج دقيقة وكاملة.

يبدأ استعلام النطاق بالبحث في المكون الموجود في الذاكرة (C0). وبما أن هذا المكون عادةً ما يكون بنية بيانات مُرتبة، يُمكن تنفيذ استعلامات النطاق بكفاءة. بمجرد الانتهاء من المكون الموجود في الذاكرة، ينتقل الاستعلام إلى مكونات القرص، بدءًا من المستوى الأول (C1) وصولًا إلى المستويات الأعمق.

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

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

يعتمد أداء استعلام النطاق في أشجار LSM على انتقائية الاستعلام. بالنسبة للاستعلامات قصيرة المدى، التي تصل إلى عدد من المفاتيح أقل من ضعف عدد المستويات، يجب على الاستعلام فحص المكونات عبر جميع المستويات، مما يؤدي إلى تكلفة تتناسب مع عدد المستويات. أما بالنسبة للاستعلامات طويلة المدى، التي تصل إلى العديد من المفاتيح، فإن التكلفة تهيمن عليها عملية مسح المستوى الأكبر، لأنه يحتوي على معظم البيانات. لهذا السبب، يكون وقت تشغيل الاستعلامات قصيرة المدى أقل. $O(L)$ و $O\left({\frac {s}{B}}\right)$ للاستعلامات بعيدة المدى، حيث $s$ يمثل عدد المفاتيح في النطاق. ^{[ 8 ]}

مراجع

↑ تشانغ، ويتاو؛ شو، ينلونغ؛ لي، يونغكون؛ لي، دينغلونغ (ديسمبر 2016). "تحسين أداء الكتابة في مخزن القيم الرئيسية القائم على LSMT". المؤتمر الدولي الثاني والعشرون لـ IEEE حول الأنظمة المتوازية والموزعة (ICPADS) لعام 2016. الصفحات 553-560 . doi : 10.1109/ICPADS.2016.0079 . ISBN 978-1-5090-4457-3. S2CID 13611447 .
↑ أونيل، باتريك؛ تشينغ، إدوارد؛ غاوليك، ديتر؛ أونيل، إليزابيث (1996-06-01). "شجرة الدمج ذات البنية اللوغاريتمية (LSM-tree)" (ملف PDF) . مجلة Acta Informatica . 33 (4): 351-385 . doi : 10.1007/s002360050048 . ISSN 1432-0525 . S2CID 12627452 .
↑ جاغاديش، إتش في؛ نارايان، بي بي إس؛ سيشادري، إس؛ سودارشان، إس؛ كانيغانتي، راما (1997). "التنظيم التدريجي لتسجيل البيانات وتخزينها" (ملف PDF) . وقائع مؤتمر VLDB . مؤسسة VLDB: 16-25 .
↑ "الضغط المُستوي في أباتشي كاساندرا : داتا ستاكس" . 13 فبراير 2014. مؤرشف من الأصل في 13 فبراير 2014.
↑ سيرز، راسل؛ راماكريشنان، راغو (2012-05-20). "BLSM" . وقائع مؤتمر ACM SIGMOD الدولي لإدارة البيانات لعام 2012. SIGMOD '12. نيويورك، نيويورك، الولايات المتحدة الأمريكية: رابطة آلات الحوسبة. الصفحات 217-228 . doi : 10.1145/2213836.2213862 . ISBN 978-1-4503-1247-9. S2CID 207194816 .
↑ تان، وي؛ تاتا، سانديب؛ تانغ، يوزهي؛ فونغ، ليانا (2014)، فهرس التفاضل: فهرس مُتمايز في مخازن البيانات الموزعة ذات البنية اللوغاريتمية (ملف PDF) ، OpenProceedings.org، doi : 10.5441/002/edbt.2014.76 ، تاريخ الاسترجاع : 22-05-2022
↑ ديجون تينغ؛ لي غو؛ روباو لي؛ فينغ تشن؛ يانفنغ تشانغ؛ سييوان ما؛ شياودونغ تشانغ (2018). "حل منخفض التكلفة للأقراص يمكّن LSM-tree من تحقيق أداء عالٍ لأحمال العمل المختلطة للقراءة والكتابة" . معاملات ACM في مجال التخزين. الصفحات 1-26 . doi : 10.1145/3162615 .
1 2 3 لو، تشين؛ كاري، مايكل جيه. (يوليو 2019). "تقنيات التخزين القائمة على LSM: دراسة استقصائية". مجلة VLDB . 29 : 393-418 . arXiv : 1812.07527 . doi : 10.1007/s00778-019-00555-y . S2CID 56178614 .

عام

أونيل، باتريك إي؛ تشينغ، إدوارد؛ غاوليك، ديتر؛ أونيل، إليزابيث (يونيو 1996). "شجرة الدمج ذات البنية اللوغاريتمية (LSM-tree)". مجلة Acta Informatica . 33 (4): 351-385 . CiteSeerX 10.1.1.44.2782 . doi : 10.1007/s002360050048 . S2CID 12627452 .
لي، ينان؛ هو، بينغشنغ؛ لو، تشيونغ؛ يي، كه (2009). “فهرسة الشجرة على أقراص فلاش”. 2009 المؤتمر الدولي الخامس والعشرون لـ IEEE حول هندسة البيانات . الصفحات من 1303 إلى 6. CiteSeerX 10.1.1.144.6961 . دوى : 10.1109/ICDE.2009.226 . رقم ISBN 978-1-4244-3422-0. S2CID 2343303 .

روابط خارجية

نظرة عامة على أشجار الدمج ذات البنية السجلية

[1] تشانغ، ويتاو؛ شو، ينلونغ؛ لي، يونغكون؛ لي، دينغلونغ (ديسمبر 2016). "تحسين أداء الكتابة في مخزن القيم الرئيسية القائم على LSMT". المؤتمر الدولي الثاني والعشرون لـ IEEE حول الأنظمة المتوازية والموزعة (ICPADS) لعام 2016. الصفحات 553-560 . doi : 10.1109/ICPADS.2016.0079 . ISBN 978-1-5090-4457-3. S2CID 13611447 .

[2] أونيل، باتريك؛ تشينغ، إدوارد؛ غاوليك، ديتر؛ أونيل، إليزابيث (1996-06-01). "شجرة الدمج ذات البنية اللوغاريتمية (LSM-tree)" (ملف PDF) . مجلة Acta Informatica . 33 (4): 351-385 . doi : 10.1007/s002360050048 . ISSN 1432-0525 . S2CID 12627452 .

[3] جاغاديش، إتش في؛ نارايان، بي بي إس؛ سيشادري، إس؛ سودارشان، إس؛ كانيغانتي، راما (1997). "التنظيم التدريجي لتسجيل البيانات وتخزينها" (ملف PDF) . وقائع مؤتمر VLDB . مؤسسة VLDB: 16-25 .

[4] "الضغط المُستوي في أباتشي كاساندرا : داتا ستاكس" . 13 فبراير 2014. مؤرشف من الأصل في 13 فبراير 2014.

[5] سيرز، راسل؛ راماكريشنان، راغو (2012-05-20). "BLSM" . وقائع مؤتمر ACM SIGMOD الدولي لإدارة البيانات لعام 2012. SIGMOD '12. نيويورك، نيويورك، الولايات المتحدة الأمريكية: رابطة آلات الحوسبة. الصفحات 217-228 . doi : 10.1145/2213836.2213862 . ISBN 978-1-4503-1247-9. S2CID 207194816 .

[6] تان، وي؛ تاتا، سانديب؛ تانغ، يوزهي؛ فونغ، ليانا (2014)، فهرس التفاضل: فهرس مُتمايز في مخازن البيانات الموزعة ذات البنية اللوغاريتمية (ملف PDF) ، OpenProceedings.org، doi : 10.5441/002/edbt.2014.76 ، تاريخ الاسترجاع : 22-05-2022

[7] ديجون تينغ؛ لي غو؛ روباو لي؛ فينغ تشن؛ يانفنغ تشانغ؛ سييوان ما؛ شياودونغ تشانغ (2018). "حل منخفض التكلفة للأقراص يمكّن LSM-tree من تحقيق أداء عالٍ لأحمال العمل المختلطة للقراءة والكتابة" . معاملات ACM في مجال التخزين. الصفحات 1-26 . doi : 10.1145/3162615 .

[:0-8] 1 2 3 لو، تشين؛ كاري، مايكل جيه. (يوليو 2019). "تقنيات التخزين القائمة على LSM: دراسة استقصائية". مجلة VLDB . 29 : 393-418 . arXiv : 1812.07527 . doi : 10.1007/s00778-019-00555-y . S2CID 56178614 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ] .

اللغة	العربية (RTL)
روابط موسوعية	25 رابطاً
المصدر الأصلي	ويكيبيديا ↗