Luft: Kisah pengembangan datastore yang mengueri 1 miliar data dalam 10 detik

Di lingkungan dengan rata-rata lebih dari 10 miliar event per bulan, muncul kebutuhan untuk menganalisis data dengan cepat dan melakukan analisis fungsi perilaku pengguna (Cohort).

(contoh: perempuan usia 30-an yang membelanjakan lebih dari 100.000 won per bulan di aplikasi kami selama 6 bulan terakhir → tingkat kunjungan kembali mereka)

Tulisan ini membahas kisah membangun sendiri datastore yang sebelumnya hanya digunakan oleh developer.

Untuk mengimplementasikan kueri analisis perilaku pengguna…

• Harus bisa mengueri metrik yang tidak dihitung lebih dulu sebelumnya (+ jenis analisis baru juga harus dimungkinkan tanpa re-indexing)

• Saat melakukan Group By pada data event per pengguna, bottleneck dari high-cardinality shuffle harus kecil

Mempertimbangkan apakah memakai solusi yang sudah ada atau membuat solusi sendiri

• Druid sudah digunakan di tempat lain, tetapi kurang cocok untuk implementasi fitur karena keterbatasan pre-aggregation (metode yang hanya membaca nilai yang sudah dihitung)

• Data warehouse seperti Snowflake atau Redshift memang bisa dioperasikan dalam skala besar, tetapi karena sifatnya yang serbaguna, perlu menjalankan cluster yang terlalu besar dibanding target sehingga mahal

• Untuk mencakup berbagai kebutuhan seperti funnel dan ID matching, DB berbasis SQL memiliki keterbatasan

Pada akhirnya membuat datastore sendiri

• Luft = data store yang dioptimalkan sejak awal untuk mengeksekusi kueri analisis perilaku pengguna yang sudah di-Group By berdasarkan user ID dengan cepat

• Dibangun berbasis Golang

• Menganalisis data pengguna berukuran puluhan TB hanya dengan kurang dari 5 node dalam rata-rata 3 detik hingga maksimum 10 detik

• Berbeda dari RDBMS umum, sistem ini memiliki sifat immutable (jika perlu, data untuk periode yang sama ditimpa ulang) → desain cluster yang sederhana, performa tinggi tanpa implementasi page manager yang rumit, dan bisa merancang format penyimpanan data yang diinginkan

Membongkar fondasi teknis

• TrailDB (storage engine) - rowstore penyimpanan event time-series yang dioptimalkan untuk partisi user ID

→ Nilai dibuat menjadi dictionary terlebih dahulu lalu hanya ID-nya yang disimpan

→ Event pengguna diurutkan berdasarkan waktu, lalu hanya menyimpan nilai waktu yang bertambah dibanding event sebelumnya serta kolom yang berubah (karena sebagian besar properti pengguna tidak berubah)

→ Tidak ada indeks. Harus full scan apa pun yang terjadi.

→ Namun secara mengejutkan memiliki rasio kompresi yang sangat tinggi (CSV 13GB → ~TrailDB 300mb)

→ Karena kompleksitas waktunya O(n), muncul pemikiran bahwa kompleksitas ruang saja yang perlu dikurangi

• LLVM (query engine)

→ Tetapi TrailDB hanya menyediakan equals berbentuk OR-AND, dan kueri yang diparse di Go harus diteruskan ke C, C++

→ Lalu diketahui bahwa PostgreSQL mengompilasi kueri dengan LLVM JiT

→ Fitur kueri sering diperluas, dan jika ditulis dalam C, C++ akan menambah biaya pengembangan; ini bisa dihindari (cukup hasilkan LLVM IR di Golang lalu kirim, kemudian dijalankan lewat kompilasi JiT di C, C++)

• Membangun sendiri layer komputasi

→ MapReduce banyak digunakan, tetapi tidak bisa dipakai karena menggunakan Golang

→ Spark/Hadoop dioptimalkan untuk long-running job sehingga meski dihubungkan, performanya tidak terlalu bagus

→ Ini juga dibuat sendiri → https://github.com/ab180/lrmr

→ Kombinasi gRPC + Protobuf + etcd, banyak mengadopsi desain Spark yang familiar

→ Mengorbankan resiliency → jika performa didorong sampai ekstrem, bahkan bila terjadi kegagalan, menjalankan ulang dari awal tetap kurang dari 10 detik

→ Karena pemrosesan data skala besar sering menyebabkan buffer overflow (backpressure), pendekatannya diubah menjadi pull-based event stream (diadopsi di Kafka, Armeria, dll.)

• Mengimplementasikan sendiri sharding

→ Shard = historical node

→ Bagaimana jika rentang tanggal partisi dipakai sebagai nilai shard key?

→ Semua kueri memiliki waktu → mudah untuk filtering

→ Pada rentang waktu yang sama, volume data cenderung serupa → mudah untuk distribusi data

→ Lingkungan terdistribusi tidak indah…

→ Bagaimana jika node mati atau baru ditambahkan?

→ Bagaimana jika ruang penyimpanan penuh?

→ Bagaimana jika karena gangguan beban menumpuk hanya pada satu node?

→ Dengan mengustomisasi cost function milik Druid, cost dibuat makin tinggi jika rentang tanggal partisi makin dekat dan makin saling tumpang tindih

→ Untuk ketersediaan shard, dilakukan hal berikut

→ Memberi TTL pada informasi shard dan memperbaruinya secara berkala (etcd)

 → Menyimpan partisi di S3, dan mengelola daftar partisi dengan DynamoDB

Situasi produksi saat ini

• Hanya dengan 4 instance c5.2xlarge, mampu memindai 500GB data dalam waktu kurang dari 15 detik

Target ke depan (atau hal yang harus dikerjakan)

• Ingin melakukan analisis funnel real-time dengan cluster kurang dari 10 mesin

• Ingin mendukung Spark agar integrasi ML dan lainnya bisa didukung

• Sedang mengembangkan column store sendiri (Ziegel) untuk menggantikan TrailDB

→ Optimasi SIMD dan multicore

→ Pra-filtering berdasarkan properti pengguna dengan Bitmap Index

[gera1d]

traildb memang menarik. https://www.youtube.com/watch?v=-oPFxSwn0lM Seru. Meski videonya sudah lama, sepertinya traildb tidak banyak berubah selama ini.

[hiddenest]

Sekarang saya lihat ternyata ada juga tulisan blog dari developernya,

https://engineering.ab180.co/stories/introducing-luft

Saya baru pertama kali mendengar TrailDB, dan ini proyek seperti ini...

https://github.com/traildb/traildb