Cara GitLab Memangkas Waktu Backup Repositori dari 48 Jam Menjadi 41 Menit

• GitLab menemukan masalah lamanya proses saat mencadangkan repositori berukuran besar dan melakukan perbaikan
• Penyebab utamanya adalah kompleksitas O(N²) pada sebuah fungsi Git berusia 15 tahun, dan performanya ditingkatkan secara signifikan lewat optimasi algoritme
• Hasil optimasi membuat waktu backup repositori terbesar turun dari 48 jam menjadi 41 menit
• Pendekatan yang telah ditingkatkan ini memberi efisiensi sumber daya dan keandalan, sekaligus berdampak positif pada alat berbasis Git dan komunitas lainnya
• Mulai versi GitLab 18.0, semua pengguna bisa menikmati manfaat ini tanpa konfigurasi tambahan

---

Pentingnya dan tantangan backup repositori

• Backup repositori adalah elemen inti dari strategi pemulihan darurat
• Semakin besar ukuran repositori, semakin meningkat pula kompleksitas dari proses backup yang andal
• Repositori Rails internal GitLab membutuhkan 48 jam untuk backup, sehingga muncul dilema antara frekuensi backup dan performa sistem
• Pada repositori berskala besar, ada berbagai masalah seperti waktu, sumber daya, risiko kegagalan, dan race condition
  • Hal ini membuat strategi tiap organisasi menjadi tidak konsisten, seperti sulit menjadwalkan backup, bergantung pada alat eksternal, atau mengurangi frekuensi backup

Analisis bottleneck performa dan identifikasi penyebab

• Fitur backup GitLab membuat snapshot repositori menggunakan perintah git bundle create
• Dalam implementasi perintah ini, terjadi bottleneck performa seiring bertambahnya jumlah reference
• Pada backup repositori besar yang memiliki jutaan reference, proses ini bisa memakan waktu lebih dari 48 jam

Analisis penyebab

• Analisis Flame Graph saat eksekusi perintah digunakan untuk menemukan titik bottleneck
• Saat jumlah reference mencapai 10.000, sekitar 80% waktu eksekusi dihabiskan di fungsi object_array_remove_duplicates()
• Fungsi ini diperkenalkan pada 2009 lewat commit ini untuk menangani reference duplikat
  • Saat menggunakan git bundle create, fungsi ini mencegah masalah jika reference duplikat ikut disertakan
  • Namun, deteksi duplikat dilakukan dalam bentuk nested for loop, sehingga menimbulkan kompleksitas O(N²)
  • Strukturnya membuat bottleneck makin parah saat jumlah reference bertambah

Beralih dari O(N²) ke pemetaan yang lebih efisien

• GitLab menyumbangkan patch ke Git dengan mengganti nested loop menggunakan struktur data map
  • Setiap reference ditambahkan ke map agar duplikat otomatis dihapus dan dapat diproses secara efisien
• Perubahan ini membuat performa git bundle create meningkat drastis dan dapat diskalakan lebih baik pada lingkungan dengan reference dalam jumlah besar
• Hasil benchmark menunjukkan peningkatan performa lebih dari 6 kali pada 100 ribu reference

Waktu backup yang jauh berkurang dan dampaknya

• Waktu backup repositori terbesar turun dari 48 jam menjadi 41 menit (sekitar 1,4% dari sebelumnya)
• Kini dimungkinkan memberikan performa yang konsisten tanpa bergantung pada ukuran repositori
• Ada manfaat tambahan seperti berkurangnya beban server dan peningkatan performa pada berbagai perintah Git yang berbasis backup
• Patch tersebut telah diterapkan ke upstream Git, dan GitLab juga segera menerapkannya agar pelanggan bisa merasakan manfaatnya lebih cepat

Perubahan nyata bagi pelanggan GitLab

• Pelanggan enterprise kini dapat menjalankan backup semalaman secara beruntun tanpa bentrok dengan workflow pengembangan
• Karena Recovery Point Objective (RPO) berkurang, risiko kehilangan data saat terjadi bencana juga menurun drastis
• Overhead operasional seperti konsumsi sumber daya, waktu pemeliharaan, dan biaya cloud ikut menurun
• Meski skala repositori terus bertambah, tidak perlu lagi khawatir memilih antara frekuensi backup dan performa sistem
• Kini semua pengguna GitLab dapat menikmati manfaat ini tanpa perubahan konfigurasi

Langkah berikutnya dan maknanya

• Peningkatan ini merupakan bagian dari upaya berkelanjutan GitLab untuk membangun infrastruktur Git kelas enterprise yang sangat skalabel
• Perubahan yang dikontribusikan GitLab juga masuk ke proyek upstream Git, sehingga memberi dampak positif ke industri secara luas dan komunitas open source
• Upaya perbaikan infrastruktur semacam ini kini menjadi model untuk pekerjaan peningkatan performa inti lainnya

Kisah yang lebih mendalam tentang pendekatan performa GitLab dapat dilihat di acara peluncuran virtual GitLab 18

[GN⁺]

Komentar Hacker News

• GitLab membagikan info bahwa kode peningkatan performa yang mereka kontribusikan ke Git dijadwalkan rilis di v2.50.0 tautan commit terkait

• Dari pengalaman langsung, ditekankan bahwa menghapus operasi n^2 dari kode yang ditulis sendiri selalu merupakan pilihan yang benar. Mereka juga merasa heran karena masalah seperti ini mudah terlihat bahkan pada nilai n yang sangat kecil, tanpa perlu menulis algoritme khusus

  • Mengutip hukum komputasi pertama Bruce Dawson: O(n^2) adalah titik yang menimbulkan masalah skalabilitas terburuk. Di production terlihat cukup cepat, tetapi setelah benar-benar dirilis justru memunculkan penurunan performa yang fatal tautan tulisan terkait

  • Berbagi pengalaman pribadi bahwa mereka sudah berkali-kali melihat situasi di mana kompleksitas waktu O(N^2) tampak cepat saat pengujian, tetapi meledak menjadi masalah serius di production

  • Menurut pengalaman mereka, pada sebagian besar masalah (80~90%), jika membutuhkan algoritme yang rumit, itu adalah tanda bahwa model datanya sendiri tidak tepat. Mereka menganggap algoritme kompleks memang secara esensial hanya diperlukan pada beberapa kasus khusus seperti compiler, internal DB, dan perencanaan jalur

  • Satu-satunya pengecualian yang disebut adalah kasus perangkat keras kecil dengan n di bawah 10, seperti antarmuka CAN. Jika n bisa bertambah tanpa mengganti perangkat keras, maka operasi n^2 wajib dihindari, dan perlu ada pembatasan di tingkat desain atau deteksi dini agar kebutuhan redesign disadari

  • Mereka mengungkapkan frustrasi karena bottleneck akibat operasi n^3 muncul hanya dengan 10.000 elemen, tetapi sampai sekarang belum menemukan solusinya

• Dinilai sebagai temuan yang menarik, sambil menyayangkan bahwa isi artikelnya sebenarnya tetap bisa tersampaikan efektif meski panjangnya hanya 1/10 dari sekarang. Meski begitu, sisi positifnya adalah ini bukan konten video sehingga mudah di-skim

  • Untuk mereka yang belum membaca artikelnya, ada tip bahwa cara paling efisien menangkap intinya adalah membaca sampai bagian setelah flame graph dan berhenti sebelum pembahasan backport

  • Kesan bahwa gaya keseluruhan artikel terasa seperti ditulis oleh LLM (large language model) karena isinya sangat panjang, dan itu justru yang paling membekas

  • Ada juga yang merasa artikel itu tetap akan baik-baik saja walau lebih panjang lagi, sambil tetap bertanya-tanya mengapa backup bundle dibuat menjadi dua ref

• Mereka heran bahwa kompresi folder git berukuran beberapa GB bisa memakan waktu sampai 48 jam, dan bahkan 41 menit pun masih terasa lama. Dipertanyakan juga alasan khusus mengapa harus memakai git bundle, alih-alih cukup melakukan snapshot/archive seluruh git repo. Mereka ingin tahu kelebihan git bundle dibanding backup ZFS yang dilakukan rutin

  • FAQ resmi Git menyebut pendekatan seperti ini berisiko karena melewati prosedur pemeriksaan integritas normal Git. Dalam kasus seperti itu, git fsck direkomendasikan untuk memverifikasi integritas koleksi. Untuk penggunaan pribadi, Syncthing dan snapshot Btrfs saja sudah cukup cepat dan andal. dokumen terkait

  • Disebutkan bahwa ada keterbatasan saat ingin membackup snapshot ZFS ke lokasi offsite berbasis non-ZFS seperti S3. Sebagai fitur git bundle yang kurang dikenal, lokasi bisa ditentukan lewat git clone --bundle-uri, dan jika server memberi tahu klien lokasi bundle, klien bisa mengambil bundle itu, mengekstraknya dengan cepat, lalu hanya mengambil update delta dari server, sehingga beban cloning repo besar berkurang drastis

  • Pada akhirnya ini dinilai seperti menambahkan caching di tempat yang memang membutuhkan caching. Mengingat sifat git repo sebagai sistem terdistribusi, muncul pertanyaan apakah bukannya cukup dengan melakukan mirroring ke repositori lain lalu mengelolanya memakai alat snapshot/backup filesystem. Ditekankan bahwa inti utamanya adalah informasi version control yang penting itu sendiri harus tersebar

• Mereka tidak punya banyak pengalaman membackup git, tetapi penasaran mengapa membuat backup langsung dari repo lokal bisa menimbulkan race condition

• Jika sampai serumit ini hanya karena protokol data di lapisan atas, dipertanyakan mengapa tidak sekalian memakai snapshot level blok. Ketiadaan WAL (Write Ahead Logging) seperti pada Git memang jadi kendala, tetapi pada SQLite strategi snapshot blok bisa dipakai di lingkungan layanan nyata hanya dengan menambahkan mode WAL. Mereka berpikir jika arsitektur seperti itu diterapkan ke Git, strategi backup yang jauh lebih andal akan mungkin dilakukan

  • Ada yang sepakat soal masalah yang timbul karena Git tidak punya mekanisme mirip WAL, sambil berbagi pengalaman bahwa jika backup hanya mengandalkan snapshot, repo bisa rusak saat dipulihkan. Masalah itu masih bisa dipulihkan, tetapi sangat merepotkan

  • Dibagikan juga tip bahwa SQLite kini punya solusi yang lebih baik, yaitu sqlite3_rsync

  • Dijelaskan dari sudut pandang GitLab bahwa ini bukan sekadar layanan managed sederhana, melainkan produk yang bisa diinstal sendiri dan dipakai di berbagai lingkungan, sehingga tiap pengguna punya filesystem, dukungan snapshot, dan kondisi OS yang berbeda. Artinya, GitLab menginginkan sistem backup independen yang bisa bekerja secara umum di semua lingkungan

• Setelah membaca ungkapan “waktu backup dipangkas secara eksponensial oleh perubahan algoritme”, ada yang bertanya apakah maksudnya dari O(n^2) menjadi O(n^2/2^n). Mereka menduga tentu bukan itu kenyataannya

  • Dijelaskan bahwa kompleksitas algoritme dari fungsi yang diperbaiki memang menjadi 6 kali lebih cepat, dan dalam konteks penggunaan lain waktu operasi total turun menjadi 1%, sehingga secara pemasaran ungkapan “peningkatan eksponensial” dianggap masih masuk akal. Penentuan kompleksitas persisnya dianggap tidak terlalu penting di sini

  • Ditegaskan bahwa dalam percakapan sehari-hari, "exponential" sering dipakai bukan dalam arti matematis yang ketat, melainkan sebagai kiasan untuk “meningkat sangat besar”

  • Ada juga yang menafsirkan bahwa mungkin n turun sampai log(n). Disebutkan situasi perubahan kompleksitas dari n^2 menjadi nlogn, mirip alasan quantum Fourier transform sering disebut jauh lebih cepat secara eksponensial dibanding DFT biasa

  • Jika algoritme n^2 diganti dengan cara lookup log(n), maka peningkatan kecepatannya memang bisa disebut eksponensial, tetapi dalam praktiknya sering kali malah sampai O(1), misalnya dengan lookup hash map, jadi lebih cepat lagi

  • Ada yang menganggap perdebatan semacam ini sendiri hanyalah mencari-cari kesalahan yang tidak produktif

• Ini dinilai sebagai contoh bagus bahwa menulis dalam C tidak otomatis membuat performa tinggi, dan bahwa struktur data serta algoritme lebih penting

  • Karena di C sangat sulit mengimplementasikan container yang tepat, masalah performa seperti ini lebih sering muncul. Di C++ atau Rust, berkat struktur data bawaan seperti unordered_set/HashSet, developer cenderung tidak asal melewatkan hal ini dengan satu for loop dan lebih alami melakukan optimisasi. Dalam kasus ini juga, Git sebenarnya punya string set, tetapi karena tidak standar, ada kemungkinan penulis aslinya tidak mengetahuinya

• Disebut sebagai pelajaran bahwa perlu keseimbangan antara premature optimization dan anticipatory optimization. Secara umum orang memang mewaspadai optimisasi yang terlalu dini, tetapi ada usulan aturan bahwa untuk fungsi yang dipanggil sangat sering, optimisasi yang jelas dan mudah sebaiknya diterapkan sejak awal

  • Diperkirakan bahwa jika saat implementasi bahasa sumbernya memiliki set-of-strings bawaan, developer aslinya mungkin akan mudah menerapkan optimisasi ini. Pada akhirnya masalah seperti ini dinilai berasal dari keterbatasan struktural bahasa seperti C yang miskin container

• Dibagikan langsung tautan commit terkait untuk rincian peningkatan algoritme tautan commit terkait

  • Berkat itu, mereka bisa menemukan submission terkait dan thread diskusi di kernel mailing list tautan diskusi terkait