Dunia teknologi memiliki pola penemuan berganda yang menarik, di mana terobosan yang sama terjadi secara independen di berbagai tim dan periode waktu yang berbeda. Meskipun kebanyakan orang tahu tentang kasus terkenal seperti Newton dan Leibniz yang sama-sama menemukan kalkulus, cerita serupa telah terjadi secara diam-diam di dunia struktur data dengan sesuatu yang disebut prolly trees.
Diskusi terbaru di komunitas developer mengungkapkan bahwa struktur data khusus ini telah ditemukan secara independen setidaknya empat kali sejak 2009, dengan setiap kelompok memberikan nama yang berbeda dan menggunakannya untuk tujuan yang berbeda. Pola ini menunjukkan bahwa prolly trees merepresentasikan evolusi alami dalam cara kita menangani data yang dikontrol versinya.
Timeline Penemuan Prolly Tree
| Tahun | Pencipta | Nama yang Digunakan | Kasus Penggunaan Utama |
|---|---|---|---|
| 2009 | Bup (Avery Pennarun) | Tidak ada nama formal | Backup sistem file |
| 2015 | Noms | Prolly Trees | Database dengan kontrol versi |
| 2019 | French Institute (INRIA) | Merkle Search Trees | Sistem terdistribusi/CRDTs |
| 2020 | DePaul University | Content-Defined Merkle Trees | Kompresi image Docker |
Misteri Kredit yang Hilang
Penemuan paling mengejutkan datang dari anggota komunitas yang menggali lebih dalam ke dalam timeline. Meskipun banyak yang mengkredit Noms pada 2015 sebagai penemu asli, developer menemukan bukti bahwa konsep yang sama muncul jauh lebih awal. Seorang komentator menunjuk ke Bup, sebuah tool backup dari 2009, yang menggunakan teknik yang persis sama tetapi tidak pernah memberikan nama formal.
Batas chunk harus ditentukan secara deterministik dari properti lokal data. Gunakan rolling checksum pada beberapa window kecil dan pisahkan file jika mencapai nilai khusus (0).
Bahkan lebih menarik, diskusi di mailing list Git dari 2005 menunjukkan developer secara santai mendeskripsikan pendekatan yang sama, menunjukkan mereka tidak menganggapnya sebagai hal yang sangat baru pada saat itu. Ini menyoroti masalah umum dalam inovasi teknologi - terkadang terobosan paling penting tidak diperhatikan karena tampak jelas bagi penciptanya.
Mengapa Semua Orang Terus Menemukan Ulang Roda yang Sama
Diskusi komunitas mengungkapkan mengapa prolly trees terus ditemukan kembali. Mereka menggabungkan tiga konsep yang sudah mapan yang telah ada selama beberapa dekade: Merkle trees (1979), rolling hash functions (1981), dan content-defined chunking (1996). Keajaiban terjadi ketika Anda menggabungkan ketiganya dengan cara tertentu.
Kelompok yang berbeda menemukan kombinasi ini saat memecahkan masalah yang benar-benar berbeda. Bup membutuhkan backup file yang lebih baik, Noms menginginkan database yang dikontrol versinya, peneliti Prancis sedang membangun sistem terdistribusi, dan DePaul University sedang mencoba mengoptimalkan image Docker. Setiap kelompok secara independen menyadari bahwa menggabungkan ketiga teknik ini menciptakan sesuatu yang kuat.
Struktur data ini menawarkan beberapa properti berharga yang membuatnya menarik untuk aplikasi modern: dapat menyimpan beberapa versi data secara efisien sambil berbagi bagian yang sama, dengan cepat mengidentifikasi perbedaan antara versi, dan mempertahankan performa yang baik bahkan dengan dataset besar.
Teknologi Dasar
| Teknologi | Tahun Diperkenalkan | Tujuan dalam Prolly Trees |
|---|---|---|
| Merkle Trees | 1979 | Verifikasi kriptografi dan integritas struktural |
| Rabin Fingerprint (Rolling Hash) | 1981 | Batas chunking yang didefinisikan konten |
| Content Defined Chunking (CDC) | 1996 (rsync) | Segmentasi data berukuran variabel |
Masalah Penamaan
Satu aspek yang menghibur dari penemuan berulang ini adalah kebingungan penamaan. Struktur data yang sama telah disebut prolly trees, Merkle search trees, content-defined Merkle trees, dan terkadang hanya dideskripsikan tanpa nama khusus sama sekali. Ini menciptakan tantangan bagi developer yang mencoba meneliti topik atau membangun berdasarkan pekerjaan yang sudah ada.
Komunitas tampak terbagi tentang nama mana yang akhirnya akan menjadi standar. Beberapa berargumen untuk prolly trees karena tampaknya merupakan nama formal paling awal, sementara yang lain lebih suka istilah yang lebih deskriptif seperti Merkle search trees. Tidak adanya halaman Wikipedia untuk nama-nama ini tidak membantu situasi.
Properti Utama Prolly Trees
- Dapat Dicari: Menyimpan data terurut dengan pencarian kunci/offset yang efisien
- Independensi Riwayat: Representasi unik terlepas dari urutan operasi
- Penyeimbangan Otomatis: Struktur pohon yang seimbang secara probabilistik
- Berbagi Struktural: Beberapa versi berbagi data yang sama, mengurangi penyimpanan
- Diffing Efisien: Membandingkan versi dalam kompleksitas waktu logaritmik
- Mutasi Efisien: Menerapkan perubahan dengan overhead komputasi minimal
Melihat ke Depan
Penemuan berulang prolly trees menunjukkan bahwa mereka memenuhi kebutuhan nyata dalam komputasi modern. Karena lebih banyak aplikasi memerlukan kontrol versi yang efisien dan sinkronisasi data, kita kemungkinan akan melihat pola ini berlanjut. Diskusi komunitas menunjukkan bahwa struktur serupa sedang dikembangkan untuk kasus penggunaan lain, dengan peneliti yang bekerja pada variasi menggunakan jenis tree dasar yang berbeda.
Cerita ini berfungsi sebagai pengingat bahwa inovasi sering terjadi secara paralel, didorong oleh kebutuhan serupa dan alat yang tersedia. Meskipun mungkin tampak tidak efisien untuk menemukan ulang hal yang sama beberapa kali, setiap iterasi telah membawa wawasan dan perbaikan baru yang menguntungkan seluruh bidang.
Referensi: People Keep Inventing Prolly Trees