Pada artikel ini, kita akan melihat secara terperinci bagaimana pohon B + dibuat dalam database Apache Ignite yang didistribusikan.

Sudah ada beberapa artikel tentang pohon-H di pohon-B ( satu , dua ), tetapi mereka lebih cenderung teoretis dan bahkan jika mengandung implementasi, maka mereka belum siap produksi . Dari sini ada minat untuk melihat implementasi yang digunakan dalam kehidupan.

Sebelum membaca artikel lebih lanjut, saya menyarankan Anda untuk menonton kuliah oleh Maxim Babenko , jika Anda masih tidak tahu apa teori B-tree secara teori. Tapi saya tidak perlu terlalu mengenal Java atau proyek Apache Ignite - saya akan menulis detailnya secara eksplisit atau menyembunyikannya di bawah spoiler.

Saat membaca sumber Ignite, saya menyarankan Anda untuk melompati argumen metode dalam pikiran Anda, yang maknanya tidak terlalu jelas dan untuk membaca nama-nama fungsi - jauh lebih mudah untuk membaca isi fungsi jika Anda tahu sebelumnya apa fungsinya.

Harap dicatat bahwa saya bukan pengembang utama Apache Ignite dan bisa salah mengerti sesuatu dari kode. Jadi, saya mengeluarkan frasa "sejauh yang saya mengerti", yang harus ditambahkan secara mental sebelum setiap kalimat afirmatif.

Mengapa pohon B + di Apache Ignite

Apache Ignite adalah basis data dalam memori, tetapi karena versi 2.1 ia memiliki penyimpanan data persisten - fungsi untuk menyimpan data ke disk (tidak ada hubungannya dengan struktur data persisten ) . Oleh karena itu, jelas mengapa struktur diperlukan untuk memori eksternal, masih memahami mengapa mereka tidak memilih yang lain.

Untuk mulai dengan, pohon B + adalah optimasi dari pohon-B, di mana nilai disimpan hanya dalam daun. Dalam pengoptimalan ini, lebih banyak kunci masuk dalam sebuah simpul, yang meningkatkan tingkat percabangan. Oleh karena itu, tidak ada banyak alasan untuk menggunakan B-tree klasik.

B * dan B + * - lebih padat pada disk, tetapi mereka memiliki kinerja yang lebih buruk, karena kami menyimpan data dari RAM, kinerja lebih penting bagi kami.

Dilihat berdasarkan tolok ukur, pohon LSM lebih cepat dalam menulis, tetapi lebih lambat dalam membaca. Selain itu, kerugian dalam membaca lebih besar daripada keuntungan dalam menulis, jadi untuk kasus umum hipotetis, saya juga akan mengambil pohon B +.

Ada juga pohon fraktal yang aneh, namun, tampaknya, mereka dipatenkan dan diimplementasikan hanya di TokuDB .

Secara pribadi, saya lebih tertarik pada mengapa tidak mungkin untuk mengambil backend disk yang sudah jadi, seperti LevelDB ? Jawaban parsial adalah bahwa PDS mendukung penyimpanan pihak ketiga.

Implementasi Sel Besar

Awalnya, GridGain mengembangkan Apache Ignite, tetapi sebelum berangkat ke open-source, ia memakai nama perusahaan, jadi beberapa nama komponen dimulai dengan Grid dan yang lainnya dengan Ignite . Oleh karena itu GridCursor , tetapi IgniteTree . Tidak ada logika lain di sini.

Kode Apache Ignite ditulis dalam pola praktik terbaik Java, dan setiap kelas mewarisi antarmuka, jika tidak satu. Dari antarmuka IgniteTree dan mulai tariannya. Saya memberikan kode tanpa javadoc, singkatnya.

 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 } } 

Antarmuka IgniteTree menggambarkan serangkaian operasi standar. Harap perhatikan bahwa memiliki pencarian rentang mengharuskan Anda untuk merajut daun dalam daftar. Bonus mendukung operasi catatan yang sewenang-wenang - invoke .

Operasi put hanya membutuhkan satu argumen tipe T tanpa kunci. Anda tidak akan menemukan penjelasan untuk ini di IgniteTree , namun jawabannya tersembunyi di header BPlusTree .

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

Seperti yang Anda lihat, nilai mewarisi kunci, oleh karena itu, dalam operasi put, kunci dihitung dari nilai. Ini tidak membatasi fungsionalitas pohon. Asumsi saya adalah lebih kompak untuk menyimpan set.

Biasanya mereka membuat set peta dengan menempelkan konstan sampah ke nilai. Namun, dalam pohon B +, hanya kunci yang disimpan dalam node, jika nilainya juga menyimpan kunci, maka di daun itu cukup untuk menyimpan hanya nilai-nilai . Dan jika pohon adalah satu set, maka secara otomatis ternyata di daun hanya akan ada kunci tanpa nilai sampah.

Sekarang mari kita lihat kode pencarian elemen.

 /** * @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); } } 

Dasar dari algoritma B-tree traversal tetap tidak berubah: mereka secara rekursif turun pohon ke daun yang diinginkan: jika nilainya ada, maka mereka mengembalikan hasilnya, dan jika tidak, maka null . Rekursi itu rupanya dibiarkan nyaman, toh, pohon-B tidak dalam.

Saya terkejut karena ada instalasi yang jelas di kepala saya: rekursi selalu dihapus dalam proyek nyata ( tidak ada optimasi rekursi ekor di Jawa , rekursi dapat diterima dalam proyek dalam bahasa lain). Tapi sungguh, ketinggian pohon-B diukur dalam satuan, karena ukuran blok pesanan $$$2 ^ {10}$, dan jumlah data pesanan $$$2 ^ {40}$dan tingginya akan $$$\ frac {log (2 ^ {40})} {log (2 ^ {10})} = 4$.

Apache Ignite menyukai konkurensi . Karena itu, pohon mendukung modifikasi kompetitif. Pada saat operasi, satu halaman diblokir, tetapi utas lainnya dapat memodifikasi sisa pohon sehingga diperlukan pembacaan kedua. Sehingga prosedur dapat mencapai root.

Pada awalnya, saya tidak mengerti arti fungsi seperti itu, karena disknya lambat dan satu utas akan dengan tenang memproses semua operasi I / O. Jelas bahwa pencarian di node yang dimuat dari disk sedikit biaya dan selama waktu ini Anda dapat memuat disk dengan operasi lain, tetapi upaya berulang akan memakan keuntungan. Namun, kemudian saya sadar bahwa dalam implementasi ini node tidak segera memerah ke disk setelah modifikasi, tetapi mereka menggantung di memori untuk sementara waktu, untuk kemudian segera menerapkan banyak modifikasi. Tidak ada data yang hilang berkat Write Ahead Log. Lebih lanjut tentang itu akan ada di akhir artikel.

Sekarang mari kita lihat kode untuk menambahkan item.

 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); } } 

Satu-satunya perbedaan adalah bahwa setelah posisi terdeteksi, kode akan replace dan insert . Anda tidak dapat lagi menonton kode remove . Mekanisme dasarnya adalah bahwa dengan upaya berulang untuk berjalan secara rekursif melalui pohon bersama dengan objek khusus tergantung pada operasinya: Get , Put atau Remove .

Invoke bekerja dengan cara yang sama, hanya operasi yang dilakukan dengan salinan catatan, maka jenisnya ditentukan: NOOP untuk membaca, REMOVE untuk menghapus dan PUT untuk memperbarui atau menambah, dan kemudian objek Put atau Remove sesuai dihasilkan, yang diterapkan pada catatan di pohon.

Gunakan

Di bawah ini saya akan melihat lebih dekat dua BPlusTree : CacheDataTree dan PendingEntriesTree . Overboard adalah implementasi indeks - ini adalah topik untuk diskusi terpisah, yang belum saya siapkan.

Sebelum melanjutkan, saya akan mengklarifikasi bahwa peta yang didistribusikan lokal memiliki fungsi IgniteCache dan disebut IgniteCache - selanjutnya hanya cache.

CacheDataTree

CacheDataTree adalah pemetaan beberapa IgniteCache ke disk. Penyortiran bersifat multi-level: pertama-tama urutkan berdasarkan id cache ke kunci grup dalam satu cache, dan kemudian dengan hash.

CacheDataTree tidak mengulangi rentang, karena indeks diterapkan pada penerus H2Tree extends BPlusTree , oleh karena itu, jenis penyortiran spesifik tidak penting: ada cukup untuk put dan get operasi. Membandingkan hash lebih cepat dari objek. Tapi yang lebih penting, hash yang seragam akan mengisi pohon lebih padat.

Pohon seimbang sehingga tidak merosot menjadi daftar. Tetapi jika Anda menambahkan kunci yang didistribusikan secara merata ke pohon pencarian, itu akan secara otomatis seimbang. Karena B-tree mulai menyeimbangkan ketika masalah muncul, dan hash mencampur kunci secara merata, menyortir berdasarkan hash mengurangi frekuensi keseimbangan.

Menggunakan hash di pohon pencarian bukanlah ide yang aneh karena tampaknya, pengembangan logisnya akan mengarah ke trias array Hash dipetakan .

PendingEntriesTree

PendingEntriesTree menyimpan kunci untuk data dari waktu ke waktu dan digunakan sebagaimana diatur. Penyortiran bersifat multi-level: pertama disortir berdasarkan id cache ke kunci grup dalam satu cache, dan kemudian menurut masa pakai. Berikutnya adalah putaran perbandingan lainnya - tampaknya, murni teknis, untuk membedakan antara elemen-elemen. Dari pengurutan, mudah ditebak bahwa kelas ini digunakan untuk mencari rentang. Pohon ini menggandakan kunci entri cache untuk preemption.

Pahami bagaimana petualangan terpisah ini bekerja.

 @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); 

Detail implementasi

Bekerja dengan halaman di Offheap

Offheap adalah teknik untuk mengoptimalkan manajemen memori manual dalam bahasa dengan pengumpul sampah.

Ini adalah mitos bahwa karena pengumpul sampah semuanya melambat, biasanya pengumpul biaya persentase kinerja yang menyedihkan . Bahkan tumpukan besar dalam diri mereka sendiri tidak menjadi masalah, karena kolektor bekerja secara kompetitif (misalnya, CMS dan G1 di Jawa), dan server memiliki puluhan inti . Tentu saja, kolektor menambahkan jeda yang tidak terduga ke aplikasi, yang penting untuk game, tetapi dapat ditoleransi untuk database.

Tapi apa yang sebenarnya menjadi masalah adalah pelanggaran hipotesis generasi pada tumpukan besar.

Dan di sini ada hal yang sebelum munculnya PDS, Apache Ignite diposisikan terutama sebagai cache antara layanan dan database disk (misalnya, Hadoop ). Oleh karena itu, peta di Ignite disebut IgniteCache dan memiliki fungsi ekstrusi yang sesuai. Dan cache hanya melanggar hipotesis generasi - di dalamnya, probabilitas suatu objek yang dihapus meningkat seiring waktu. Oleh karena itu, dalam hal ini, Offheap untuk menyimpan data pengguna meningkatkan kinerja.

Lebih banyak bonus:

• Offheap memudahkan untuk mengimplementasikan struktur yang mengandung lebih dari elemen Integer.MAX_VALUE .
• Jika Anda menyimpan banyak kurang dari 32GB, maka tautannya akan berbobot 4 byte , yang menghemat beberapa gigabytes.
• Karena kolektor membuat grafik objek, ia mengkonsumsi memori secara proporsional dengan jumlah mereka. Dan jumlah objek sebanding dengan heap. Kolektor juga mengkonsumsi CPU, yang lebih baik dihabiskan untuk kompresi data, misalnya.
• Pada tumpukan yang sangat besar, bahkan jika hipotesis generasi tidak dilanggar secara keseluruhan, masih akan ada cukup banyak benda tua dalam nilai absolut yang akan melanggarnya.

Karena data kemudian dikirim ke disk, objek serial ke memori secara langsung melalui unsafe , dan kemudian area memori ini digunakan untuk buffer I / O.

Tulis log di depan

Write Ahead Log adalah log operasi dengan struktur linier, menambah biayanya konstan, tidak seperti pohon. Pohon diperbarui lebih jarang, dan jika data hilang karena jatuh, mereka dipulihkan dari log dengan menerapkan operasi mulai dari keadaan tersimpan terakhir. Hasilnya adalah peningkatan kinerja tanpa mengurangi keandalan. Saya menyarankan Anda untuk melihat antarmuka IgniteWriteAheadLogManager - ada dokumentasi rinci.

Bypass node

Karena node di pohon-B tidak kecil, mereka dilewati oleh pencarian biner. Untuk ini, keturunan dari kelas BPlusTree.GetPageHandler , dan untuk operasi yang berbeda mereka berbeda.

 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; 

Daftar lembar

Untuk menyiasatinya secara efisien, lembaran diikat ke daftar. BPlusTree.ForwardCursor , yang BPlusTree.ForwardCursor dari lembar ke lembar, dikembalikan sebagai hasil pencarian. Rupanya, bagian kursor tidak diisolasi dari operasi lain di pohon, karena ketika lewat, kunci hanya diambil pada satu halaman. Saya tidak menemukan mekanisme sinkronisasi yang melindungi akses ke metode kursor.

Kesimpulan

Karena pohon B + di Apache Ignite masih muda dibandingkan dengan basis data relasional lainnya, kami mendapatkan set yang diperlukan untuk pohon B + siap produksi:

• WAL memberikan keamanan murah, sebagai akibatnya, pohon jarang diperbarui pada disk.
• Offheap dengan data dalam bentuk serial.
• Concurrency - untuk bagian-bagian pohon yang dimuat ke dalam memori.