Apa Itu Pohon LSM? Penjelasan Log-Structured Merge Tree

Apa itu pohon LSM?

Log-structured merge tree (LSM) adalah struktur data yang menyangga penulisan masuk di memori dan menggabungkannya ke disk dalam batch yang terurut dan tidak dapat diubah. Struktur ini tidak pernah mengubah data secara langsung di tempatnya. Sebaliknya, struktur ini mengakumulasi perubahan dan menunda pekerjaan pengorganisasian, dengan menukar kesederhanaan pembacaan demi throughput penulisan.

Pohon LSM diformalkan dalam makalah tahun 1996 karya Patrick O’Neil, Edward Cheng, Dieter Gawlick, dan Elizabeth O’Neil berjudul The log-structured merge-tree (LSM-tree). Struktur ini menghabiskan sekitar satu dekade sebagai struktur akademis yang relatif tidak dikenal sebelum Bigtable milik Google membangun lapisan penyimpanannya berdasarkan konsep tersebut. Desain Bigtable melahirkan LevelDB, LevelDB melahirkan RocksDB, dan beberapa variasi pohon LSM mendasari sebagian besar sistem yang dibuat untuk penyerapan data berskala besar.  

Namanya menyiratkan satu pohon tunggal, yang sangat menyesatkan. 

Pohon LSM lebih tepat dipahami sebagai orkestrasi tiga komponen:

• Memtable: buffer dalam memori yang menyimpan penulisan terbaru
• Write-ahead log (WAL): file khusus penambahan di disk yang membuat penulisan tersebut tahan lama
• Kumpulan file sorted string table (SST) yang terus bertambah: file terurut dan tidak dapat diubah yang menyimpan semua data yang lebih lama

Hampir semua hal menarik tentang perilaku LSM berasal dari cara data berpindah di antara ketiga komponen ini. Semua perpindahan tersebut dimulai dengan satu pemanggilan fungsi yang tampak sederhana, biasanya disebut sebagai put.

Apa itu put? 

Put adalah wrapper praktis yang secara internal membuat WriteBatch berisi tepat satu record dan menyerahkannya kepada Write(), yang menangani mutasi. 

Titik awal yang alami adalah Put(key, value), tetapi secara teknis RocksDB tidak memiliki operasi semacam itu. Setiap operasi tulis adalah batch, dan satu put hanyalah batch berisi satu item. Penulisan atomik untuk beberapa key tersedia secara bawaan di RocksDB karena ini merupakan operasi native.

WriteBatch adalah string byte ringkas dengan bentuk tetap. Tepatnya, header 12 byte yang menyimpan sequence number 8 byte dan jumlah record 4 byte, diikuti oleh record itu sendiri. Setiap record terdiri dari tag tipe satu byte, key dengan awalan panjang, dan, untuk penulisan, value dengan awalan panjang.

Pernyataan dari artikel pertama dalam seri ini—key dan value adalah array byte arbitrer—menjadi harfiah. Encoding batch tidak mengetahui maupun memedulikan arti byte tersebut. Satu-satunya struktur yang diterapkan adalah awalan panjang. 

Setiap batch diberi penanda berupa penghitung yang terus meningkat, yang dikenal sebagai sequence number. Penanda ini menetapkan urutan total atas setiap operasi tulis yang pernah diterima database. Sequence number memungkinkan snapshot, pembacaan konsisten, dan pemulihan setelah crash. WAL dapat diputar ulang karena setiap record di dalamnya mengetahui posisinya dalam urutan.

Put, Delete, Merge

Hal penting yang perlu diperhatikan adalah bahwa Put merupakan kTypeValue dan Delete merupakan kTypeDeletion, yang berarti delete bukanlah penghapusan langsung. Sebaliknya, delete adalah operasi tulis—sebuah tombstone—yang mencatat penghapusan tersebut, sementara pengambilan kembali ruangnya ditunda hingga compaction.

Put dan Delete berbagi format WriteBatch dengan kTypeMerge, yang ditulis oleh operasi Merge. Merge tersedia karena read-modify-write sangat merugikan penyimpanan yang dioptimalkan untuk penulisan. Menaikkan penghitung dengan Put mengharuskan pembacaan value saat ini, penambahan satu, lalu penulisan kembali hasilnya. Artinya, database harus dilalui dua kali hanya untuk mengubah satu angka, dan pembacaan menanggung seluruh biaya jalur pembacaan. 

Merge sepenuhnya melewati pembacaan. 

Sebagai gantinya, Merge menambahkan operand (yaitu deskripsi perubahan, seperti “tambahkan satu”) lalu selesai. Tidak ada yang dihitung saat penulisan. Database menggabungkan operand menjadi value akhir di kemudian waktu menggunakan merge operator yang disediakan aplikasi, baik saat key dibaca berikutnya maupun ketika compaction menemukan rangkaian tersebut.

Delete menunda pengambilan kembali ruang, sedangkan merge menunda komputasi. 

Seluruh karakter pohon LSM terlihat dalam ketiga tag tipe ini: setiap mutasi, termasuk yang secara logis bergantung pada state yang ada, menjadi penambahan tanpa pembacaan. Dalam pohon LSM, semuanya adalah penambahan. 

Penjelasan Jalur Penulisan Pohon LSM

Cara paling jelas untuk memahami pohon LSM adalah mengikuti satu Put(key, value) dari pemanggilan fungsi hingga ke disk.

Langkah Satu: Write-Ahead Log

Operasi tulis pertama-tama ditambahkan ke WAL. Penambahan ini terjadi sebelum memtable disentuh, dan urutan inilah yang membentuk kontrak durabilitas. Artinya, setelah penambahan WAL selesai, operasi tulis sudah tersimpan di disk dalam bentuk yang dapat bertahan dari crash, meskipun belum diatur agar dapat dibaca.

Menambahkan data ke log adalah operasi disk termurah, dan itulah inti desain ini. Durabilitas diperoleh dengan biaya penulisan berurutan.

RocksDB mengelompokkan penulisan serentak ke dalam group commit untuk semakin mengamortisasi biaya, sementara opsi sync mengontrol apakah penambahan diteruskan melalui page cache OS ke penyimpanan stabil sebelum pemanggilan selesai.

Langkah Dua: Memtable

Setelah durabilitas terjamin, operasi tulis dimasukkan ke memtable. Secara default, memtable RocksDB adalah skiplist. Skiplist digunakan karena memtable harus menyerap penulisan serentak dan mengembalikan isinya dalam urutan key yang terurut, baik untuk pembacaan maupun flush berikutnya.

Skiplist mendukung penyisipan serentak tanpa lock sekaligus menjaga semuanya tetap terurut setiap saat. Ini adalah padanan struktur data dari mengarsipkan dokumen saat tiba, alih-alih membiarkannya menumpuk.

Langkah Tiga: Memtable Terisi Penuh

Memtable terus bertambah hingga mencapai ambang batas yang dikonfigurasi (yaitu write_buffer_size), yang secara default sebesar 64 MB. Pada titik ini, memtable ditandai tidak dapat diubah, memtable baru yang kosong menggantikannya, dan penulisan masuk berlanjut tanpa gangguan. Memtable yang penuh dan dibekukan menunggu gilirannya untuk di-flush di latar belakang. 

Penulisan tidak pernah terblokir oleh proses flush itu sendiri.

Langkah Empat: Flush

Thread latar belakang menulis memtable yang tidak dapat diubah ke disk sebagai file SST di level 0 (L0) pohon. Karena skiplist sudah terurut, flush hanya memerlukan satu lintasan berurutan yang menelusuri entri sesuai urutan dan menuliskannya.

Tugas memtable selesai, dan entri WAL terkait pada akhirnya dapat dibuang. Data kini bertahan di disk dalam bentuk permanen yang dapat dibaca.

Apa isi file SST?

File SST adalah tempat data menghabiskan sisa masa pakainya. File ini disusun menjadi tiga blok dan satu footer:

• Blok data: entri terurut itu sendiri, masing-masing berukuran beberapa kilobyte dan dikompresi secara individual
• Blok indeks: memetakan rentang key ke offset blok agar pencarian dapat langsung menuju blok yang tepat
• Blok bloom filter opsional: ringkasan probabilistik ringkas yang dapat menjawab “key ini pasti tidak ada dalam file ini” tanpa membaca bagian lain
• Footer: menunjukkan lokasi semua bagian di atas

Setiap elemen tata letak ini dirancang agar pembacaan berikutnya menyentuh sesedikit mungkin byte, terutama indeks dan bloom filter.

Menelusuri Jalur Penulisan

Semua yang dijelaskan di atas dapat diamati secara langsung. Bagian ini menelusuri secara singkat satu Put melalui database menggunakan ldb dan sst_dump, alat inspeksi yang disertakan bersama RocksDB. Contoh ini menggunakan Rust dan crate rocksdb, meskipun binding apa pun dapat digunakan.

Prasyarat

Untuk mengikuti panduan ini, instal alat command-line RocksDB dan toolchain Rust. 

Di macOS, brew install rocksdb menyediakan ldb dan sst_dump. Di Debian/Ubuntu, paketnya adalah rocksdb-tools.

Setelah semuanya terinstal, buat proyek baru:

$ cargo new lsm-trace
$ cd lsm-trace
$ cargo add rocksdb

Crate rocksdb mengompilasi library C++ RocksDB dari source pada build pertama, jadi cargo run pertama mungkin memerlukan waktu beberapa menit.

Langkah Satu: Tulis dan Hentikan

Ganti isi src/main.rs dengan kode berikut:

use rocksdb::{Options, DB};

fn main() {
    let mut opts = Options::default();
    opts.create_if_missing(true);
    let db = DB::open(&opts, "/tmp/lsm-trace").unwrap();

    db.put(b"slot:0001", b"hello").unwrap();
// Deliberately no flush. Let the process exit.
}

Jalankan sekali dengan cargo run, lalu tampilkan daftar isi direktori database yang dibuatnya:

$ ls /tmp/lsm-trace
000004.log CURRENT IDENTITY LOCK LOG MANIFEST-000005 OPTIONS-000007

CURRENT dan file MANIFEST melacak inventaris file database, sementara OPTIONS mencatat konfigurasi yang digunakan saat database dibuka. LOG, tanpa angka, adalah log teks yang dapat dibaca manusia untuk debugging dan tidak boleh tertukar dengan 000004.log, yang merupakan write-ahead log itu sendiri.

Nomor file yang tepat akan berbeda pada setiap eksekusi, tetapi strukturnya tetap sama.

Perhatikan bahwa direktori tersebut belum memiliki satu pun file .sst. Operasi tulis sudah tahan lama karena tetap ada setelah proses berhenti, tetapi hanya tersimpan sebagai record WAL. Inilah pemisahan durabilitas dan pengorganisasian dalam praktik.

Langkah Dua: Tampilkan Isi WAL

Arahkan ldb ke file .log apa pun yang terdapat dalam direktori:

$ ldb dump_wal --walfile=/tmp/lsm-trace/000004.log --header
Sequence,Count,ByteSize,Physical Offset,Key(s) 1,1,29,0,PUT(0) : 0x736C6F743A30303031

Kita memiliki satu batch: sequence number 1 yang berisi 1 record (29 byte), yaitu PUT dengan key berupa encoding heksadesimal dari slot:0001. 

Ukurannya sesuai dengan encoding yang dijelaskan sebelumnya: header 12 byte ditambah record 17 byte, yang mencakup satu tag tipe, dua awalan panjang, key 9 byte, dan value 5 byte.

Langkah Tiga: Flush dan Tampilkan Isi SST

Pertama, hapus direktori database (yaitu rm -rf /tmp/lsm-trace) agar eksekusi ini dimulai dari kondisi bersih.

Tambahkan satu baris ke main.rs setelah put:

db.put(b"slot:0001", b"hello").unwrap();
db.flush().unwrap();

Memanggil db.flush().unwrap(); memaksa memtable ditulis sebagai file SST tanpa menunggu hingga penuh.

Jalankan kembali file tersebut, lalu tampilkan daftar isi direktori. 

Sekarang kita dapat melihat file .sst baru dalam output. Kita dapat memeriksanya dengan kedua mode sst_dump yang berguna, dengan mengganti nama file sesuai nama sebenarnya:

$ sst_dump --file=/tmp/lsm-trace/000010.sst --command=scan
'slot:0001' seq:1, type:1 => hello

Perhatikan bahwa sst_dump mencetak beberapa baris pembuka tentang format file sebelum output pemindaian; baris tersebut dipangkas di sini dan dalam output di bawah.

Inilah pasangan key-value di tempat permanen barunya, masih dengan sequence number yang sama. 

Kemudian kita dapat melihat propertinya menggunakan perintah berikut:

$ sst_dump --file=/tmp/lsm-trace/000010.sst --show_properties

Output properti merinci anatomi SST yang dibahas sebelumnya dalam artikel: jumlah dan ukuran blok data, ukuran blok indeks, keberadaan filter, algoritma kompresi, dan jumlah entri. 

Meskipun hanya ada satu key, semua elemen struktural dirinci dengan satu pengecualian penting. Ukuran blok filter adalah nol dan kebijakan filter adalah N/A karena bloom filter bersifat opt-in di RocksDB, dikonfigurasi melalui filter_policy, dan opsi default tidak menetapkannya. 

Artikel berikutnya dalam seri ini akan membahas alasan deployment produksi hampir selalu mengaktifkannya. 

Langkah Empat: Buka Kembali dan Periksa Log

Jadikan baris put dan flush sebagai komentar sehingga hanya menyisakan baris DB::open, lalu jalankan sekali lagi. Daftar isi direktori kini menunjukkan bahwa 000004.log lama telah hilang dan digantikan oleh log baru yang hampir kosong dengan nomor lebih tinggi. Isinya telah di-flush ke SST pada langkah ketiga, sehingga record tersebut menjadi usang dan RocksDB membuang file itu saat dibuka kembali.

Inilah keseluruhan keterkaitan siklus hidup WAL-memtable. 

Untuk melihat satu lapisan lebih dalam, kita dapat menjalankan binary dari langkah pertama dengan strace -e trace=write,fdatasync di Linux guna menunjukkan kontrak durabilitas pada batas syscall. Pemanggilan write berurutan menambahkan data ke file .log, sedangkan fdatasync hanya muncul ketika WriteOptions.sync ditetapkan.

Langkah Lima: Hapus Key dan Lihat Apa yang Tersisa

Pernyataan sebelumnya bahwa delete adalah operasi tulis dapat diamati secara langsung. 

Ubah main.rs untuk menghapus key dan memaksa flush lainnya:

db.delete(b"slot:0001").unwrap();
db.flush().unwrap();

Jalankan, lalu tampilkan daftar isi direktori. 

Kini akan ada dua file .sst. File yang lebih lama tidak berubah karena tidak dapat diubah, sehingga masih berisi key dan value-nya. Kita dapat memverifikasinya dengan pemindaian:

$ sst_dump --file=/tmp/lsm-trace/000010.sst --command=scan
'slot:0001' seq:1, type:1 => hello

Sekarang pindai file yang lebih baru:

$ sst_dump --file=/tmp/lsm-trace/000014.sst --command=scan
'slot:0001' seq:2, type:0 =>

Ini adalah key yang sama, tetapi dengan sequence number lebih tinggi, memiliki type:0 alih-alih type:1, dan tidak membawa value. Ini adalah tombstone: record kTypeDeletion dari bagian WriteBatch yang di-flush ke SST tersendiri. Database kini berisi value dan record penghapusannya secara berdampingan dalam file terpisah.

Pembacaan key akan menyelesaikan kontradiksi ini dengan mengutamakan tombstone. 

Kita dapat memverifikasinya dengan menambahkan lookup ke program:

match db.get(b"slot:0001").unwrap() {
    Some(v) => println!("found: {:?}", v),
    None => println!("not found"),
}

Program akan mencetak not found karena jalur pembacaan memeriksa data yang lebih baru terlebih dahulu, dan sequence number 2 lebih tinggi daripada sequence number 1. Dari sudut pandang database, value tersebut telah hilang, tetapi secara fisik masih tersimpan di disk dalam file SST yang lebih lama. 

Belum ada ruang yang diambil kembali. Penghapusan baru dicatat, dan tombstone akan terus menutupi value tersebut hingga compaction akhirnya menggabungkan kedua file serta membuang tombstone dan value yang tertutupi.

Langkah Enam: Hapus Key dan Lihat Apa yang Tersisa

Tipe record Merge juga dapat diamati. Ini memerlukan konfigurasi merge operator karena RocksDB tidak mengetahui arti operand tanpa operator tersebut.

Hapus direktori database sekali lagi dan ganti main.rs dengan kode berikut:

use rocksdb::{Options, DB, MergeOperands};

fn add(_key: &[u8], existing: Option<&[u8]>, operands: &MergeOperands) -> Option<Vec<u8>> {
    let mut total: i64 = existing
        .and_then(|v| std::str::from_utf8(v).ok())
        .and_then(|s| s.parse().ok())
        .unwrap_or(0);
    for op in operands {
        total += std::str::from_utf8(op).ok().and_then(|s| s.parse().ok()).unwrap_or(0);
    }
    Some(total.to_string().into_bytes())
}

fn main() {
    let mut opts = Options::default();
    opts.create_if_missing(true);
    opts.set_merge_operator_associative("add", add);
    let db = DB::open(&opts, "/tmp/lsm-merge").unwrap();

    db.merge(b"counter", b"1").unwrap();
    db.merge(b"counter", b"1").unwrap();
    db.merge(b"counter", b"1").unwrap();
    println!("{:?}", db.get(b"counter").unwrap());
}

Menampilkan isi WAL memperlihatkan tiga record MERGE terpisah. Artinya, tiga penambahan, bukan satu pembacaan:

$ ldb dump_wal --walfile=/tmp/lsm-trace/000004.log --header
Sequence,Count,ByteSize,Physical Offset,Key(s)
1,1,23,0,MERGE(0) : 0x636F756E746572
2,1,23,30,MERGE(0) : 0x636F756E746572
3,1,23,60,MERGE(0) : 0x636F756E746572

Merge operator menggabungkan rangkaian tersebut saat pembacaan dengan hasil berupa byte mentah. Program mencetak Some([51]) karena 51 adalah kode ASCII untuk karakter 3. Sekali lagi, ini karena key dan value adalah array byte arbitrer.

Kita juga dapat menambahkan db.flush().unwrap(); sebelum lookup, menghapus direktori, lalu menjalankan program kembali. Pemindaian SST menunjukkan satu record:

'counter' seq:3, type:2 => 3

Flush menerapkan operator dan menyatukannya menjadi satu operand.

Mengapa level 0 istimewa?

File SST baru ditempatkan di level 0. File tersebut merupakan snapshot langsung dari memtable, dan masing-masing mencakup rentang key apa pun yang kebetulan diserap memtable itu. Karena itu, file L0 dapat dan sering kali saling tumpang tindih. Kondisi ini berbeda dari setiap level yang lebih dalam karena file di sana tidak saling tumpang tindih; setiap file memiliki rentang key tersendiri, sehingga paling banyak hanya satu file per level yang dapat memuat key tertentu.

Akibatnya, setiap file L0 menjadi lokasi terpisah tempat sebuah key mungkin tersembunyi, sehingga jumlah file L0 secara langsung membebani performa pembacaan. Inilah alasan RocksDB memantau jumlah file L0 dengan cermat dan mulai memperlambat, atau bahkan menghentikan, penulisan ketika jumlahnya terlalu tinggi.

Menjaga L0 tetap kecil adalah salah satu tugas utama compaction.

Mengapa pohon LSM mengungguli B-tree untuk penulisan?

B-tree membayar biaya pengorganisasian saat penulisan agar pembacaan dapat menemukan semuanya tepat di tempatnya, sedangkan pohon LSM menunda pengorganisasian ke compaction latar belakang yang dibayar kemudian secara massal.

B-tree adalah struktur yang mendasari sebagian besar database tradisional. Struktur ini memperbarui data secara langsung di tempatnya. Artinya, setiap operasi tulis mencari halaman yang memiliki key, membacanya, mengubahnya, lalu menulisnya kembali. Halaman terkait tersebar di seluruh disk, sehingga rangkaian penulisan yang acak secara logis menjadi rangkaian I/O yang acak secara fisik.

Pohon LSM menolak membayar biaya tersebut saat penulisan. Struktur ini menambahkan data (ke WAL), menyangga (di memtable), dan membuat batch (melalui flush). Setiap penulisan ke disk berlangsung secara berurutan, sementara utang pengorganisasian ditunda hingga compaction. Pekerjaan tersebut tidak menghilang. Sebaliknya, pekerjaan itu dibayar kemudian secara massal dan dikonsolidasikan ke bentuk yang dapat ditangani disk dengan sangat baik.

Hal ini sangat penting pada SSD karena SSD sama sekali tidak dapat menimpa data secara langsung di tempatnya. 

Penyimpanan flash dihapus dalam blok besar, mulai dari ratusan kilobyte hingga megabyte, dan ditulis dalam halaman yang lebih kecil. Artinya, setiap penimpaan acak berukuran kecil memaksa flash translation layer (FTL) perangkat untuk memindahkan data aktif dan menghapus blok di balik layar. 

Penulisan halaman acak oleh B-tree membuat FTL terus melakukan hal tersebut. Write amplification yang disebabkan perangkat bertumpuk di atas biaya yang ditimbulkan struktur data itu sendiri, lalu dibayar melalui penurunan throughput dan masa pakai perangkat. Penulisan berurutan berukuran besar pada pohon LSM mendekati skenario terbaik yang dapat diberikan kepada perangkat keras flash.

Cara terbaik untuk memahaminya adalah sebagai pinjaman. Pengorganisasian yang ditunda akan jatuh tempo dalam bentuk I/O compaction, dan pembacaan harus memeriksa lebih banyak lokasi dibandingkan B-tree. Dengan demikian, pohon LSM memperoleh throughput penulisan sekarang dan membayarnya nanti dalam bentuk read amplification dan space amplification. 

Untuk pembahasan lebih mendalam tentang perbandingan pohon LSM dan B-tree terkait read amplification, write amplification, dan space amplification, lihat B-Tree vs LSM-Tree. 

Apa yang terjadi setelah RocksDB mengalami crash?

Memtable berada di memori volatil, yang berarti crash akan menghapusnya. Inilah alasan utama WAL tersedia.

Saat dimulai ulang, RocksDB memutar ulang setiap operasi tulis yang telah dikonfirmasi tetapi belum di-flush ke SST. RocksDB memasukkannya ke memtable baru untuk merekonstruksi state sebelum crash. Biaya pemulihan sebanding dengan data yang belum di-flush. Karena itu, siklus hidup WAL dan memtable saling terkait. Setelah isi memtable di-flush dengan aman ke SST, entri log terkait menjadi usang dan WAL dapat dipangkas.

Operasi tulis menjadi tahan lama saat penambahan log tersimpan. Operasi itu baru menjadi murah untuk dibaca setelah flush mengaturnya. B-tree menggabungkan kedua proses ini, sedangkan pohon LSM memisahkannya, dan sebagian besar karakter struktur ini berasal dari pemisahan tersebut. 

Bagaimana Solana membebani jalur penulisan?

Artikel pertama dalam seri ini menjelaskan cara Agave menyimpan ledger Solana di RocksDB. Jika dilihat dari jalur penulisan, workload tersebut hampir menyerupai stress test yang dibuat khusus. Shred (yaitu unit mentah data ledger) terus tiba melalui jaringan dengan kecepatan penuh, dan semuanya harus melewati jalur penambahan WAL dan penyisipan memtable sebelum lapisan penyimpanan validator menyelesaikan tugasnya.

Mekanisme yang terlibat sama persis dengan yang ditelusuri artikel ini, tetapi dalam skala produksi. Saat shred tiba, jalur penyisipan Blockstore di Agave memvalidasi seluruh batch shred masuk, mencoba pemulihan Reed-Solomon untuk shred yang hilang, dan menyiapkan semuanya (yaitu payload shred, metadata slot, metadata erasure, serta pembaruan indeks) ke dalam satu WriteBatch RocksDB sebelum melakukan commit dalam satu operasi tulis atomik.

Disederhanakan dari insert_data_shred:

// We don't want only a subset of these changes going through.
write_batch.put_bytes::<cf::ShredData>((slot, index), &shred.payload)?;
update_slot_meta(/* ...metadata updates */);
data_index.set_present(index, true);

Komentar tersebut menunjukkan engineer Agave merangkum inti artikel ini dalam sembilan kata: batch adalah unit atomisitas, dan crash pada validator di tengah penyisipan tidak boleh membuat ledger hanya diperbarui sebagian. 

Batch berisi satu item yang ditelusuri dalam panduan ini menjadi batch berisi ribuan item di dalam validator—shred dan metadatanya di beberapa column family, satu rentang sequence number, satu penambahan WAL, dan satu group commit.

Namun, bagian baiknya adalah shred diawali dengan nomor slot (yaitu tuple (slot, index) dari cuplikan kode yang disederhanakan merupakan key ShredData), dan slot bertambah hampir secara monoton. Karena itu, setiap memtable menyerap bagian keyspace yang sempit dan sebagian besar berurutan, lalu flush menghasilkan file L0 yang hampir tidak saling tumpang tindih.

Kami merasakan dampak jalur penulisan ini secara langsung. 

Sistem pengarsipan yang kami operasikan di Helius menyerap seluruh riwayat transaksi Solana ke RocksDB—ratusan terabyte dalam workload yang sangat bergantung pada penambahan dan terus bertambah secara permanen—dan migrasi yang menghasilkan arsitektur tersebut didokumentasikan dalam artikel migrasi ClickHouse ke RocksDB kami.

Kesimpulan

Pohon LSM adalah kesepakatan dengan perangkat keras. Semua penulisan dibuat berurutan sebagai imbalan atas penundaan pekerjaan untuk menjaga data tetap terorganisasi. Artinya, jalur pembacaan harus mencari data di lebih banyak lokasi dibandingkan B-tree, misalnya. Memtable menyerap, WAL menjamin, dan SST terus terakumulasi. Pada penyimpanan flash, tempat penimpaan acak terkena penalti dua kali, ini merupakan kesepakatan yang sangat menguntungkan.

Namun, penulisan adalah bagian yang mudah. Harga desain ini dibayar pada pembacaan karena value terbaru dari suatu key mungkin berada di memtable, file L0, atau level mana pun di bawahnya. Mekanisme yang menjaga biaya tersebut tetap terbatas adalah bagian yang membuat rekayasa LSM semakin menarik. 

Artikel berikutnya dalam seri ini akan membahas jalur pembacaan, termasuk memtable, bloom filter, block cache, dan amplification triangle dalam praktik.

Jika menelusuri satu pasangan key-value melalui empat struktur data yang berbeda terdengar seperti cara menyenangkan untuk menghabiskan sore, bergabunglah membangun bersama kami. Sistem yang dijelaskan dalam seri ini adalah sistem yang kami deploy, operasikan, dan optimalkan pada skala pasar modal internet. Kami membuka lowongan di seluruh tim engineering. Lihat semua posisi yang tersedia di helius.dev/careers.