Membangun DB deret waktu dari nol

• Ditulis dengan Go, tetapi pada dasarnya hampir tidak bergantung pada bahasa

• Data deret waktu adalah kumpulan berbagai nilai yang diberi stempel waktu. Setiap item adalah titik data

→ Volumenya besar. Harus banyak agar bermakna. Sering juga ada kasus yang menangkap hingga jutaan kali per detik

→ Append-only, diurutkan berdasarkan waktu, data terbaru didahulukan

→ Pembacaan massal berdasarkan satuan waktu tertentu

→ High Cardinality (ukuran himpunannya sangat besar)

→ Sebagian besar digunakan dengan membaca data terbaru

• Untuk mencerminkan karakteristik data deret waktu yang umumnya berat di penulisan, dibuat library engine DB TStorage dalam bahasa Go

• Model data

→ Model data linear

→ Titik data dipartisi berdasarkan satuan waktu

→ Setiap partisi berperilaku seperti DB terpisah dan independen yang memiliki seluruh data dalam rentang waktu tersebut

→ Hanya head dan partisi berikutnya yang disimpan di heap, sehingga dapat dimodifikasi sebagai partisi memori

→ Untuk mencegah kehilangan data, ditulis ke WAL (Write Ahead Log) sebelum penulisan

→ Data partisi yang lebih lama disimpan ke disk sebagai satu file. Partisi di disk bersifat read-only

• Partisi memori

→ Daftar titik data direpresentasikan di heap sebagai array (mirip slice di Go)

→ Karena latensi dan sinkronisasi, out-of-order sering terjadi. Jika masih dalam partisi yang sama, data diurutkan ulang saat disimpan melalui buffering; jika partisinya berbeda, dapat dilakukan dengan menambahkan ke belakang partisi sebelumnya yang bukan head

→ Menyimpan data yang sama persis dengan yang benar-benar dicatat ke WAL, sehingga tetap bisa dipulihkan saat terjadi error

• Partisi disk

→ Menyimpan metadata dan data aktual yang sudah dikompresi dalam satu direktori per partisi (versi mini dari Prometheus V3 Storage)

→ Format data memory-mapped (dapat di-cache oleh kernel melalui mmap)

→ Metadata membentuk indeks dalam format JSON

• Encoding data yang direpresentasikan sebagai tuple stempel waktu dan nilai menggunakan metode encoding yang diusulkan dalam paper Gorilla dari Facebook

→ Timestamp dan value di-encode dengan metode yang berbeda

→ timestamp menggunakan nilai integer unsigned 64-bit dengan encoding Delta-of-delta

✓ Encoding Delta: metode yang hanya mencatat selisih antara nilai sebelumnya dan nilai saat ini

✓ Encoding Delta-of-Delta: karena umumnya terjadi pada interval waktu tertentu, yang dicatat hanya delta dari delta

✓ Karena di-encode dengan panjang variabel, Delta-of-Delta menggunakan ruang paling kecil

→ values menggunakan nilai floating-point signed 64-bit dengan encoding XOR

✓ Nilai pertama disimpan apa adanya

✓ Nilai berikutnya di-XOR; jika hasilnya 0 berarti sama dengan nilai sebelumnya, sehingga hanya menyimpan satu bit 0

✓ Jika bukan 0, dihitung berdasarkan bit-bit yang berbeda (meaningful bit)

✓ Menghitung nol di depan/belakang; jika jumlah nolnya sama, hanya 0 dan meaningful bit yang disimpan, jika berbeda maka jumlah leading zero, jumlah meaningful bit, dan nilainya sendiri yang disimpan