Struktur Data untuk Aplikasi yang Intensif Data [PDF]

Struktur data key-value adalah komponen inti sistem berbasis data, dan perbedaan performanya dapat sangat besar tergantung workload dan kondisi perangkat keras
Struktur fisik dibagi menjadi tata letak data, metadata untuk penelusuran, dan algoritme penyimpanan·pencarian; juga disebut access methods, data container, atau search structure
Workload dinyatakan sebagai kombinasi point query, range query, insert, delete, dan update, sementara kapasitas dan biaya memori·penyimpanan persisten juga menjadi kebutuhan desain
B+-tree kuat untuk pembacaan dan range query, tetapi ketika insert·update meningkat, rekonstruksi leaf node menjadi beban, sedangkan LSM-tree menangani banyak insert melalui buffering dan merge
Di lingkungan tempat perpindahan data menjadi bottleneck, kita perlu memilih struktur yang ada atau merancang struktur baru sesuai aplikasi baru, perubahan perangkat keras, dan pertumbuhan data

Masalah yang diselesaikan oleh struktur data key-value

Struktur data key-value banyak digunakan dalam aplikasi yang intensif data, dan karena model key-value bersifat umum, ia menjadi fondasi banyak sistem
Satu key dipetakan ke satu value, tetapi value yang sama dapat terhubung ke beberapa key
Makna value berbeda-beda tergantung aplikasinya
- Bisa berupa record dari basis data relasional
- Bisa berupa Pandas DataFrame
- Bisa berupa sekumpulan field dalam sistem NoSQL yang diparse dan digunakan oleh aplikasi
- Dalam sistem yang menangani data jejaring sosial, bisa mencakup referensi ke objek besar seperti gambar atau video

Secara fisik, struktur data key-value terdiri dari tiga elemen
- Data yang disimpan dalam layout tertentu
- Metadata opsional yang membantu penelusuran data
- Algoritme yang mendukung operasi penyimpanan dan pencarian
Struktur data digunakan dalam berbagai bentuk di sistem data, sistem operasi, file system, compiler, dan sistem jaringan
Contoh dalam buku ini terutama berfokus pada sistem data berskala besar dan perangkat penyimpanan sekunder, tetapi cara analisis dan perancangannya juga berlaku untuk sistem in-memory
Analisis ini ditujukan untuk lingkungan dengan hierarki memori·penyimpanan yang memiliki dua tingkat atau lebih

B+-tree banyak digunakan untuk menyeimbangkan biaya baca dan biaya tulis pada workload yang sedikit insert dan update tetapi banyak point query·range query
Fanout node yang tinggi mengurangi akses ke memori sekunder yang diperlukan saat bergerak dari root ke leaf, dan level atas di-cache pada hierarki memori yang lebih cepat
Semua key dipertahankan dalam keadaan terurut di leaf node, dan leaf node dihubungkan sebagai linked list untuk mendukung range query
Ketika insert dan update meningkat, rekonstruksi atau pemisahan leaf node menjadi perlu dan dapat menjadi bottleneck performa
LSM-tree menggunakan pendekatan berbeda untuk workload dengan banyak insert
- Menaruh semua update ke dalam buffer memori bersama
- Melakukan flush ke disk saat buffer penuh
- Menggabungkan buffer yang menumpuk menjadi koleksi data terurut yang lebih besar
- Modifikasi diproses dengan kebijakan out-of-place, sehingga beberapa pasangan key-value dengan key yang sama dapat ada bersamaan di dalam struktur
- Value saat ini untuk key tertentu dimiliki oleh pasangan key-value yang paling baru diinsert

Selain pendekatan merancang struktur data dengan memperkirakan workload sebelumnya, juga dibahas struktur data yang secara bertahap mendekati bentuk ideal selama eksekusi
Dalam desain aslinya, B+-tree dan LSM-tree memaksakan urutan terurut di dalam node yang berada di disk untuk menjawab semua point query atau range query
Struktur data adaptif dapat dimulai dari satu atau lebih node yang belum terurut, lalu diurutkan secara bertahap saat ada kesempatan
Database cracking menggunakan pola akses dari query yang masuk untuk terus-menerus dan secara inkremental mereorganisasi fisik data dasar
Tujuannya adalah meningkatkan performa query di masa depan

Perkembangan perangkat keras menciptakan tantangan dan peluang baru dalam desain struktur data
Pada hierarki penyimpanan, tingkat yang lebih bawah menyediakan ruang simpan lebih besar dengan harga lebih rendah tetapi memiliki latensi akses tinggi, sedangkan tingkat atas yang lebih dekat ke prosesor lebih cepat tetapi lebih kecil dan biaya per byte-nya lebih tinggi
Lapisan yang menjadi bottleneck untuk aplikasi tertentu bergantung pada ukuran data aplikasi dan kapasitas penyimpanan di tiap lapisan
B+-tree pada awalnya berupaya memaksimalkan fanout untuk mengurangi akses disk, tetapi ketika ukuran memori membesar dan data masuk ke RAM atau memori sekunder nonvolatile, trade-off berubah drastis
B+-tree in-memory menunjukkan performa terbaik pada fanout kecil
Memory wall mengacu pada tren membesarnya kesenjangan antara kecepatan prosesor dan kecepatan memori off-chip
Sejak awal 2000-an, sistem operasi dan sistem manajemen data telah didesain ulang untuk mengoptimalkan penggunaan memori cache

Dibahas bagaimana merapikan ruang pilihan dalam desain struktur data dan cara memilih struktur yang sesuai dengan tujuan aplikasi dan workload
Karena perangkat keras dan karakteristik data terus berubah, inovasi berkelanjutan juga diperlukan dalam desain struktur data
Ruang desain yang telah dirapikan dan panduan ini digunakan untuk memilih struktur data yang paling cocok di antara yang sudah ada, atau merancang struktur data baru yang sesuai dengan workload tertentu