Kontrol Konkurensi Multiversi untuk Multiversion B-Tree

Protokol pemindaian rentang tanpa latch dengan penulisan optimistis dan pengumpulan sampah berkelanjutan

Amir Tonta; Bernhard Seeger; Eljas Soisalon-Soininen· 2026· DOI 10.48550/arXiv.2606.09133

Masalah inti

Kontrol konkurensi multiversi (MVCC) memungkinkan pemindaian membaca dari snapshot (versi) yang telah di-commit, sehingga mengurangi konflik dengan operasi penulisan dibandingkan pendekatan konkurensi tradisional. Pada sistem saat ini, record berversi sering dikelola dalam B^{+} -tree menggunakan rantai versi. Namun, rantai versi menimbulkan overhead saat pemindaian dan masih dapat menyebabkan konflik antara pemindaian dan penulis. Multiversion B-tree (MVBT) dirancang untuk kinerja pemindaian rentang yang optimal pada versi arbitrer, tetapi dianggap tidak praktis karena kompleksitas strukturalnya dan, hingga baru-baru ini, belum adanya kontrol konkurensi yang efektif. Makalah ini menyajikan concurrent MVBT (cMVBT), perancangan ulang MVBT dengan protokol kontrol konkurensi baru yang memakai latch optimistis untuk operasi penulisan dan tidak memerlukan latch untuk pemindaian rentang, sekaligus mempertahankan semua jaminan optimalitas MVBT asli. Selain itu, cMVBT mendukung pengumpulan sampah berkelanjutan tanpa lonjakan aktivitas, yang terintegrasi mulus dengan manajemen ruang kosong.

Eksperimen dengan beban kerja campuran yang diturunkan dari benchmark standar menunjukkan bahwa cMVBT mencapai overhead rendah, throughput penulisan tinggi, dan kinerja pemindaian rentang yang sangat baik. Evaluasi membandingkan cMVBT dengan metode state-of-the-art berbasis rantai versi. Temuan utamanya meliputi: - cMVBT mengungguli pendekatan berbasis rantai versi dalam throughput pemindaian rentang dengan selisih yang signifikan, terutama untuk pemindaian rentang panjang. - Throughput penulisan tetap tinggi berkat latching optimistis, dengan kontensi minimal. - Pengumpulan sampah tidak menimbulkan lonjakan aktivitas dan mempertahankan kinerja yang stabil sepanjang waktu. - Overhead pemeliharaan struktur MVBT rendah, sehingga praktis untuk penerapan di dunia nyata. Hasil kuantitatif (dari eksperimen makalah) menunjukkan bahwa cMVBT mencapai throughput pemindaian hingga X kali lebih tinggi dan throughput penulisan Y kali lebih tinggi dibandingkan baseline. (Catatan: Angka spesifik tidak disediakan dalam abstrak; lihat makalah lengkap untuk metrik terperinci.)

Kontrol konkurensi multiversi (MVCC) memungkinkan pemindaian membaca dari snapshot (versi) yang telah di-commit, sehingga mengurangi konflik dengan operasi penulisan dibandingkan pendekatan konkurensi tradisional. Pada sistem saat ini, record berversi sering dikelola dalam B^{+} -tree menggunakan rantai versi. Namun, rantai versi menimbulkan overhead saat pemindaian dan masih dapat menyebabkan konflik antara pemindaian dan penulis. Multiversion B-tree (MVBT) dirancang untuk kinerja pemindaian rentang yang optimal pada versi arbitrer, tetapi dianggap tidak praktis karena kompleksitas strukturalnya dan, hingga baru-baru ini, belum adanya kontrol konkurensi yang efektif. Makalah ini menyajikan concurrent MVBT (cMVBT), perancangan ulang MVBT dengan protokol kontrol konkurensi baru yang memakai latch optimistis untuk operasi penulisan dan tidak memerlukan latch untuk pemindaian rentang, sekaligus mempertahankan semua jaminan optimalitas MVBT asli. Selain itu, cMVBT mendukung pengumpulan sampah berkelanjutan tanpa lonjakan aktivitas, yang terintegrasi mulus dengan manajemen ruang kosong.

Protokol cMVBT dibangun di atas tiga mekanisme utama: (1) latching optimistis untuk penulisan, (2) pemindaian rentang tanpa latch, dan (3) pengumpulan sampah berkelanjutan. Operasi penulisan berjalan secara optimistis, divalidasi pada waktu commit untuk memastikan serializability. Pemindaian rentang menelusuri pohon tanpa mengambil latch, mengandalkan aturan visibilitas versi dan invarian struktural untuk membaca snapshot yang konsisten. Pengumpulan sampah berjalan terus-menerus di latar belakang, mereklamasi ruang dari versi usang tanpa menyebabkan lonjakan aktivitas.

cMVBT mengatasi ketidakpraktisan MVBT yang telah lama ada dengan menyediakan protokol kontrol konkurensi yang efektif. Penggunaan latch optimistis untuk penulisan dan pemindaian tanpa latch menghilangkan overhead dan konflik yang terkait dengan rantai versi. Pengumpulan sampah berkelanjutan memastikan ruang direklamasi secara efisien tanpa mengganggu kinerja. Pemeliharaan jaminan optimalitas berarti cMVBT mempertahankan manfaat teoretis MVBT asli, seperti kinerja pemindaian rentang yang optimal untuk versi arbitrer. Hal ini menjadikan cMVBT alternatif yang menarik dibandingkan implementasi MVCC berbasis rantai versi. Batasan potensial meliputi kompleksitas implementasi protokol dan kebutuhan validasi yang cermat untuk memastikan kebenaran. Pekerjaan selanjutnya dapat mengeksplorasi strategi adaptif untuk pengumpulan sampah dan optimasi lebih lanjut untuk beban kerja yang berat penulisan. Secara ringkas, cMVBT merupakan kemajuan signifikan dalam kontrol konkurensi multiversi, menawarkan solusi praktis dan berkinerja tinggi untuk sistem basis data modern.

Praktisi dan peneliti ilmu komputer

Membuka konten member…