في هذه المقالة ، سنلقي نظرة مفصلة على كيفية عمل شجرة B + في قاعدة بيانات Apache Ignite الموزعة.

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

قبل قراءة المقالة أكثر ، أنصحك بمشاهدة محاضرة لمكسيم بابينكو ، إذا كنت لا تزال لا تعرف ما هي شجرة B من الناحية النظرية. لكنني لست بحاجة إلى معرفة جافا بعمق أو مشروع Apache Ignite - إما أن أكتب التفاصيل بشكل صريح أو أخفيها تحت المخربين.

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

يرجى ملاحظة أنني لست المطور الرئيسي لـ Apache Ignite ويمكن أن أسيء فهم شيء من الرمز. لذا ، أضع عبارة "بقدر ما أفهم" ، والتي يجب إضافتها ذهنيًا قبل كل جملة إيجابية.

لماذا شجرة B + في Apache Ignite

Apache Ignite هي قاعدة بيانات داخل الذاكرة ، ولكن منذ الإصدار 2.1 يحتوي على مخزن بيانات دائم - وهي وظيفة لحفظ البيانات على القرص (لا علاقة له ببنية البيانات المستمرة ) . لذلك ، من الواضح لماذا هناك حاجة إلى بنية للذاكرة الخارجية ، يبقى فهم لماذا لم يختاروا بنية أخرى.

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

B * و B + * - أكثر كثافة على القرص ، ولكن أداءهما أسوأ ، لأن نقوم بتخزين البيانات من ذاكرة الوصول العشوائي ، والأداء أكثر أهمية بالنسبة لنا.

استنادًا إلى المعايير ، تعد شجرة LSM أسرع في الكتابة ، ولكنها أبطأ في القراءة. علاوة على ذلك ، فإن الخسارة في القراءة أكبر من المكتسب في الكتابة ، لذلك بالنسبة للحالة العامة الافتراضية ، أود أيضًا أن آخذ شجرة B +.

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

أنا شخصياً مهتم أكثر لماذا كان من المستحيل أخذ خلفية قرص جاهزة ، مثل LevelDB ؟ الإجابة الجزئية هي أن PDS يدعم التخزين من جهة خارجية.

تنفيذ الخلية الكبيرة

في البداية ، طورت GridGain Apache Ignite ، ولكن قبل المغادرة إلى المصدر المفتوح ، تحمل اسم الشركة ، لذلك تبدأ بعض أسماء المكونات بـ Grid وأخرى مع Ignite . لذلك GridCursor ، لكن IgniteTree . لا يوجد منطق آخر هنا.

يتم كتابة كود Apache Ignite في أنماط أفضل ممارسات Java ، وكل فئة ترث واجهة ، إن لم تكن واحدة. من واجهة IgniteTree وابدأ الرقص. أعطي الرمز بدون javadoc ، باختصار.

 public interface IgniteTree<L, T> { public T put(T val) throws IgniteCheckedException; public void invoke(L key, Object x, InvokeClosure<T> c) throws IgniteCheckedException; public T findOne(L key) throws IgniteCheckedException; public GridCursor<T> find(L lower, L upper) throws IgniteCheckedException; public GridCursor<T> find(L lower, L upper, Object x) throws IgniteCheckedException; public T findFirst() throws IgniteCheckedException; public T findLast() throws IgniteCheckedException; public T remove(L key) throws IgniteCheckedException; public long size() throws IgniteCheckedException; interface InvokeClosure<T> { void call(@Nullable T row) throws IgniteCheckedException; T newRow(); OperationType operationType(); } enum OperationType { NOOP, REMOVE, PUT } } 

تصف واجهة IgniteTree مجموعة قياسية من العمليات. يرجى ملاحظة أن البحث في النطاق يتطلب منك ربط الأوراق في قائمة. تدعم المكافأة عملية تسجيل تعسفية - invoke .

تأخذ عملية الوضع وسيطة واحدة فقط من النوع T بدون مفتاح. لن تجد تفسيرًا لذلك في IgniteTree ، ولكن الإجابة مخفية في رأس BPlusTree .

 public abstract class BPlusTree<L, T extends L> extends DataStructure implements IgniteTree<L, T> 

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

عادة ما يصنعون خريطة من خلال ربط ثابت القمامة بالقيمة. ومع ذلك ، في شجرة B + ، يتم تخزين المفاتيح فقط في العقد ؛ إذا كانت القيمة تخزن المفتاح أيضًا ، فعندها في الأوراق يكفي تخزين القيم فقط . وإذا كانت الشجرة عبارة عن مجموعة ، فعندئذٍ يتضح تلقائيًا أنه في الأوراق سيكون هناك مفاتيح فقط بدون قيم القمامة.

الآن دعونا نلقي نظرة على رمز بحث العنصر.

 /** * @param g Get. * @throws IgniteCheckedException If failed. */ private void doFind(Get g) throws IgniteCheckedException { for (;;) { // Go down with retries. g.init(); switch (findDown(g, g.rootId, 0L, g.rootLvl)) { case RETRY: case RETRY_ROOT: checkInterrupted(); continue; default: return; } } } /** * @param g Get. * @param pageId Page ID. * @param fwdId Expected forward page ID. * @param lvl Level. * @return Result code. * @throws IgniteCheckedException If failed. */ private Result findDown(final Get g, final long pageId, final long fwdId, final int lvl) throws IgniteCheckedException { long page = acquirePage(pageId); try { for (;;) { // Init args. g.pageId = pageId; g.fwdId = fwdId; Result res = read(pageId, page, search, g, lvl, RETRY); switch (res) { case GO_DOWN: case GO_DOWN_X: assert g.pageId != pageId; assert g.fwdId != fwdId || fwdId == 0; // Go down recursively. res = findDown(g, g.pageId, g.fwdId, lvl - 1); switch (res) { case RETRY: checkInterrupted(); continue; // The child page got split, need to reread our page. default: return res; } case NOT_FOUND: assert lvl == 0 : lvl; g.row = null; // Mark not found result. return res; default: return res; } } } finally { if (g.canRelease(pageId, lvl)) releasePage(pageId, page); } } 

بقي أساس خوارزمية اجتياز شجرة B دون تغيير: ينزلون الشجرة بشكل متكرر إلى الورقة المطلوبة: إذا كانت القيمة موجودة ، فإنهم يعيدون النتيجة ، وإذا لم يكن الأمر كذلك ، فلا قيمة لها. يبدو أن العودية تركت للراحة ، على أي حال ، فإن أشجار B ليست عميقة.

لقد فوجئت لأنه كان هناك تثبيت واضح في رأسي: تتم إزالة العودية دائمًا في مشروع حقيقي ( لا يوجد تحسين عائد الذيل في Java ، العودية مقبولة في المشاريع بلغات أخرى). ولكن في الحقيقة ، يتم قياس ارتفاع شجرة B بوحدات ، لأن حجم كتلة الأمر $$$2 ^ {10}$، وعدد بيانات الطلب $$$2 ^ {40}$وسيكون الارتفاع $$$\ frac {log (2 ^ {40})} {log (2 ^ {10})} = 4$.

يحب Apache Ignite التزامن . لذلك ، تدعم الشجرة التعديل التنافسي. في وقت العملية ، يتم حظر صفحة واحدة ، ولكن قد يقوم مؤشر ترابط آخر بتعديل باقي الشجرة بحيث تكون القراءة الثانية مطلوبة. وبالتالي يمكن أن يصل الإجراء إلى الجذر.

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

الآن دعنا نرى الرمز لإضافة عنصر.

 private T doPut(T row, boolean needOld) throws IgniteCheckedException { checkDestroyed(); Put p = new Put(row, needOld); try { for (;;) { // Go down with retries. p.init(); Result res = putDown(p, p.rootId, 0L, p.rootLvl); switch (res) { case RETRY: case RETRY_ROOT: checkInterrupted(); continue; case FOUND: // We may need to insert split key into upper level here. if (!p.isFinished()) { // It must be impossible to have an insert higher than the current root, // because we are making decision about creating new root while keeping // write lock on current root, so it can't concurrently change. assert p.btmLvl <= getRootLevel(); checkInterrupted(); continue; } return p.oldRow; default: throw new IllegalStateException("Result: " + res); } } } catch (IgniteCheckedException e) { throw new IgniteCheckedException("Runtime failure on row: " + row, e); } catch (RuntimeException e) { throw new IgniteException("Runtime failure on row: " + row, e); } catch (AssertionError e) { throw new AssertionError("Assertion error on row: " + row, e); } finally { checkDestroyed(); } } /** * @param p Put. * @param pageId Page ID. * @param fwdId Expected forward page ID. * @param lvl Level. * @return Result code. * @throws IgniteCheckedException If failed. */ private Result putDown(final Put p, final long pageId, final long fwdId, final int lvl) throws IgniteCheckedException { assert lvl >= 0 : lvl; final long page = acquirePage(pageId); try { for (;;) { // Init args. p.pageId = pageId; p.fwdId = fwdId; Result res = read(pageId, page, search, p, lvl, RETRY); switch (res) { case GO_DOWN: case GO_DOWN_X: assert lvl > 0 : lvl; assert p.pageId != pageId; assert p.fwdId != fwdId || fwdId == 0; res = p.tryReplaceInner(pageId, page, fwdId, lvl); if (res != RETRY) // Go down recursively. res = putDown(p, p.pageId, p.fwdId, lvl - 1); if (res == RETRY_ROOT || p.isFinished()) return res; if (res == RETRY) checkInterrupted(); continue; // We have to insert split row to this level or it is a retry. case FOUND: // Do replace. assert lvl == 0 : "This replace can happen only at the bottom level."; return p.tryReplace(pageId, page, fwdId, lvl); case NOT_FOUND: // Do insert. assert lvl == p.btmLvl : "must insert at the bottom level"; assert p.needReplaceInner == FALSE : p.needReplaceInner + " " + lvl; return p.tryInsert(pageId, page, fwdId, lvl); default: return res; } } } finally { if (p.canRelease(pageId, lvl)) releasePage(pageId, page); } } 

والفرق الوحيد هو أنه بعد اكتشاف الموضع ، يتحول الرمز إلى replace insert . لم يعد بالإمكان مشاهدة رمز remove . الآلية الأساسية هي أنه مع المحاولات المتكررة للسير بشكل متكرر من خلال الشجرة مع كائن خاص اعتمادًا على العملية: Get أو Put أو Remove .

يعمل Invoke بنفس الطريقة ، تتم العملية فقط مع نسخة من السجل ، ثم يتم تحديد نوعه: NOOP للقراءة ، REMOVE و PUT للتحديث أو الإضافة ، ثم يتم إنشاء كائن Put أو Remove المقابل ، والذي يتم تطبيقه على السجل في الشجرة.

استخدم

أدناه سوف ألقي نظرة فاحصة على اثنين من BPlusTree : CacheDataTree و PendingEntriesTree . Overboard هو تنفيذ الفهارس - هذا موضوع لمناقشة منفصلة ، لست على استعداد بعد.

قبل الانتقال ، IgniteCache أن الخريطة الموزعة المحلية لها وظائف IgniteCache وتسمى IgniteCache - فيما يلي ببساطة ذاكرة تخزين مؤقت.

CacheDataTree

CacheDataTree تعيين IgniteCache إلى القرص. الفرز متعدد المستويات: أولاً الفرز حسب معرف ذاكرة التخزين المؤقت إلى مفاتيح المجموعة في ذاكرة تخزين مؤقت واحدة ، ثم حسب التجزئة.

لا تتكرر CacheDataTree عبر النطاق ، حيث يتم تنفيذ الفهارس في خلف H2Tree extends BPlusTree ، وبالتالي ، فإن النوع المحدد من الفرز ليس مهمًا: أيًا ما يكفي put وتنفيذ العمليات. مقارنة التجزئة هي أسرع من الأشياء. ولكن الأهم من ذلك ، أن التجزئة الموحدة ستملأ الشجرة بكثافة أكبر.

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

إن استخدام التجزئة في شجرة البحث ليس فكرة غريبة كما يبدو ، فإن تطويرها المنطقي سيؤدي إلى صفيف Hash تعيينه .

PendingEntriesTree

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

افهم كيف تعمل هذه المغامرة المنفصلة.

 @Override public boolean expire( GridCacheContext cctx, IgniteInClosure2X<GridCacheEntryEx, GridCacheVersion> c, int amount ) 

 private final IgniteInClosure2X<GridCacheEntryEx, GridCacheVersion> expireC = new IgniteInClosure2X<GridCacheEntryEx, GridCacheVersion>() { @Override public void applyx(GridCacheEntryEx entry, GridCacheVersion obsoleteVer) { boolean touch = !entry.isNear(); while (true) { try { if (log.isTraceEnabled()) log.trace("Trying to remove expired entry from cache: " + entry); if (entry.onTtlExpired(obsoleteVer)) touch = false; break; } catch (GridCacheEntryRemovedException ignore) { entry = entry.context().cache().entryEx(entry.key()); touch = true; } } if (touch) entry.context().evicts().touch(entry, null); } }; 

 cctx.cache().removeEntry(this); 

تفاصيل التنفيذ

العمل مع الصفحات في Offheap

Offheap هي تقنية لتحسين إدارة الذاكرة اليدوية بلغة باستخدام جامع القمامة.

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

لكن ما سيحدث بالفعل هو المشكلة هو انتهاك فرضية الأجيال على كومة كبيرة.

وهنا شيء من هذا القبيل أنه قبل ظهور PDS ، تم وضع Apache Ignite بشكل أساسي كذاكرة تخزين مؤقت بين الخدمات وقاعدة بيانات القرص (على سبيل المثال ، Hadoop ). لذلك ، تسمى الخرائط في Ignite IgniteCache ولها وظيفة البثق المقابلة. وتنتهك ذاكرة التخزين المؤقت فقط فرضية الأجيال - حيث يزداد احتمال حذف كائن بمرور الوقت. لذلك ، في هذه الحالة ، يعمل Offheap لتخزين بيانات المستخدم على تحسين الأداء.

المزيد من المكافآت:

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

نظرًا لإرسال البيانات بعد ذلك إلى القرص ، يتم إجراء تسلسل للكائنات في الذاكرة مباشرة من خلال unsafe ، ثم يتم استخدام منطقة الذاكرة هذه لمخزن الإدخال / الإخراج المؤقت.

اكتب سجل المستقبل

Write Ahead Log عبارة عن سجل للعمليات ذات بنية خطية ، ويضيف إليها تكلفة ثابتة ، على عكس الشجرة. يتم تحديث الشجرة بشكل أقل تكرارًا ، وإذا فقدت البيانات بسبب السقوط ، فستتم استعادتها من السجل عن طريق تطبيق العمليات بدءًا من آخر حالة تم حفظها. والنتيجة هي تحسين الأداء دون المساومة على الموثوقية. أنصحك بإلقاء نظرة على واجهة IgniteWriteAheadLogManager - هناك وثائق مفصلة.

تجاوز العقدة

نظرًا لأن العقد في أشجار B ليست صغيرة ، يتم تجاوزها من خلال البحث الثنائي. لهذا ، يتم BPlusTree.GetPageHandler أحفاد فئة BPlusTree.GetPageHandler ، وبالنسبة للعمليات المختلفة فهي مختلفة.

 private int findInsertionPoint(int lvl, BPlusIO<L> io, long buf, int low, int cnt, L row, int shift) throws IgniteCheckedException { assert row != null; int high = cnt - 1; while (low <= high) { int mid = (low + high) >>> 1; int cmp = compare(lvl, io, buf, mid, row); if (cmp == 0) cmp = -shift; // We need to fix the case when search row matches multiple data rows. //noinspection Duplicates if (cmp < 0) low = mid + 1; else if (cmp > 0) high = mid - 1; else return mid; // Found. } return -(low + 1); // Not found. } 

 if (cmp == 0) cmp = -shift; 

قائمة الأوراق

للتجول في النطاق بكفاءة ، يتم ربط الأوراق بقائمة. BPlusTree.ForwardCursor ، الذي ينتقل من ورقة إلى ورقة ، كنتيجة بحث. على ما يبدو ، لم يتم عزل مرور المؤشر عن العمليات الأخرى في الشجرة ، لأنه عند المرور ، يؤخذ القفل على صفحة واحدة فقط. لم أجد آلية مزامنة تحمي الوصول إلى طرق المؤشر.

الخلاصة

نظرًا لأن شجرة B + في Apache Ignite صغيرة مقارنةً بقواعد البيانات العلائقية الأخرى ، نحصل على المجموعة اللازمة لإنتاج شجرة B + الجاهزة للإنتاج:

• يوفر WAL أمانًا رخيصًا ، ونتيجة لذلك ، نادرًا ما يتم تحديث الشجرة على القرص.
• Offheap مع البيانات في شكل متسلسل.
• التزامن - لأجزاء الشجرة المحملة في الذاكرة.