[2009 WSDM] Tantangan Membangun Sistem Pengambilan Informasi Skala Besar

Dimensi Utama dan Trade-off dalam Sistem Pengambilan Informasi

• Saat merancang sistem, trade-off rekayasa antara elemen-elemen berikut harus dipertimbangkan secara seimbang.
  • Jumlah dokumen yang diindeks
  • Jumlah kueri yang diproses per detik (QPS)
  • Tingkat kemutakhiran indeks/kecepatan pembaruan
  • Latensi kueri
  • Jumlah informasi yang disimpan untuk setiap dokumen
  • Kompleksitas/biaya perhitungan skor dan algoritma pencarian
• Tingkat kesulitan rekayasa cenderung sebanding dengan hasil kali parameter-parameter ini.
• Semua elemen ini memengaruhi kinerja keseluruhan dan kinerja terhadap biaya (kinerja per dolar).

Perubahan Skala Sistem (1999 vs 2009)

• Dalam 10 tahun terakhir, skala sistem dan kebutuhan performa berubah secara dramatis.
  • # dokumen: ~70 juta → miliaran (~naik 100x)
  • jumlah kueri harian yang diproses: (~naik 1000x)
  • informasi indeks per dokumen: (~naik 3x)
  • latensi pembaruan: beberapa bulan → beberapa menit (~turun 10000x)
  • latensi kueri rata-rata: <1 detik → <0,2 detik (~turun 5x)
  • sumber daya sistem: lebih banyak mesin * mesin yang lebih cepat (~naik 1000x)
• Karena parameter-parameter ini terus berubah, kadang hingga beberapa orde besaran, desain sistem harus terus berevolusi.
  • Desain yang cocok pada titik waktu tertentu (X) bisa menjadi desain yang sangat keliru pada skala 10x atau 100x. (Karena itu, rancang dengan pertumbuhan sekitar 10x dalam pikiran, tetapi rencanakan penulisan ulang sebelum mencapai 100x)
  • Dalam 10 tahun terakhir, telah terjadi 7 perombakan besar.

Arsitektur Sistem Awal (1997-1999)

• Tahap proyek riset (1997):
  • Server web frontend menerima kueri lalu mendistribusikan permintaan pemrosesan ke server indeks dan server dokumen
  • Server indeks: sharding berdasarkan ID dokumen (docid)
  • Server dokumen: sharding berdasarkan ID dokumen (docid)
• Prinsip dasar:
  • Dokumen diberi ID bilangan bulat (docid) (dokumen penting/berkualitas tinggi diberi ID yang lebih kecil)
  • Server indeks: (kueri) → mengembalikan daftar terurut (skor, docid, ...). Sharding berbasis docid, dengan replication untuk menambah kapasitas. Biaya O(#kueri * #dokumen dalam indeks).
  • Server dokumen: (docid, kueri) → menghasilkan (judul, snippet). Memetakan docid → teks penuh dokumen di disk. Sharding berbasis docid. Biaya O(#kueri).
• Sistem serving (1999):
  • Menambahkan server cache dan integrasi sistem iklan ke struktur proyek riset
  • Menjalankan replica shard server indeks/dokumen
  • Caching: hasil indeks dan snippet dokumen sama-sama di-cache. Rasio cache hit 30-60%. Sangat berkontribusi pada peningkatan performa dan penurunan latensi kueri. (Namun perlu waspada terhadap lonjakan latensi besar saat pembaruan indeks/cache flush)

Strategi Partisi Indeks

• Berdasarkan dokumen (By doc): setiap shard menyimpan indeks untuk sebagian dokumen (pilihan Google)
  • Kelebihan: pemrosesan kueri independen per shard, mudah mempertahankan informasi tambahan per dokumen, traffic jaringan (permintaan/respons) lebih kecil
  • Kekurangan: semua shard harus memproses kueri, untuk kueri K kata dibutuhkan O(K*N) disk seek pada N shard
• Berdasarkan kata (By word): setiap shard menyimpan indeks untuk sebagian kata atas seluruh dokumen
  • Kelebihan: kueri K kata diproses oleh paling banyak K shard, O(K) disk seek
  • Kekurangan: membutuhkan bandwidth jaringan yang jauh lebih besar (informasi per kata untuk dokumen yang cocok harus dikumpulkan di satu tempat), sulit mempertahankan informasi per dokumen

Crawling dan Indexing Awal (1998-1999)

• Crawling:
  • Sistem crawling batch sederhana: daftar URL awal → crawl halaman → ekstrak tautan dan tambahkan ke antrean → berhenti saat jumlah halaman yang cukup telah dikumpulkan
  • Hal yang perlu dipertimbangkan: mencegah kelebihan beban pada situs tertentu, menentukan prioritas halaman yang belum di-crawl (misalnya PageRank), mengelola antrean URL yang belum di-crawl secara efisien, menangani kegagalan mesin
• Indexing:
  • Sistem indexing batch sederhana: berbasis alat Unix sederhana
  • Masalah: tanpa checkpointing sehingga kegagalan mesin sangat menyakitkan, tanpa checksum data mentah sehingga muncul masalah error bit perangkat keras (diperparah oleh mesin awal tanpa ECC/parity, masalah "mostly sorted"), pengalaman dengan "memori dan pemrograman yang bermusuhan"
  • Solusi: mengembangkan abstraksi file yang menyimpan checksum record kecil dan dapat melewati/menyinkronkan ulang record yang rusak

Metode Pembaruan Indeks (1998-1999)

• Periode: sekitar sekali per bulan
• Proses:
  1. Menunggu hingga jam dengan traffic rendah
  2. Mengalihkan sebagian replica ke offline
  3. Menyalin indeks baru ke replica offline
  4. Menjalankan frontend baru yang menunjuk ke indeks yang diperbarui dan memproses sebagian traffic
• Strategi pemanfaatan disk pada server indeks:
  • Bagian luar disk (outer part) memberikan bandwidth lebih tinggi
  1. (Saat indeks lama masih melayani) salin indeks baru ke bagian dalam disk (inner half)
  2. Restart agar menggunakan indeks baru
  3. Hapus indeks lama
  4. Salin ulang indeks baru ke bagian luar yang lebih cepat (faster half)
  5. Hapus salinan pertama indeks baru yang sebelumnya ditaruh di bagian dalam
  6. Gunakan ruang kosong di bagian dalam untuk membangun struktur data peningkat performa (misalnya Pair cache - pra-perhitungan hasil irisan posting list untuk pasangan istilah kueri yang sering muncul bersama)

Menangani Pertumbuhan dan Skalabilitas (1999-2001)

• Pada '99, '00, dan '01 ukuran indeks serta traffic melonjak tajam (~50 juta → lebih dari 1 miliar halaman, pertumbuhan traffic 20% per bulan + kemitraan Yahoo yang menggandakan traffic dalam semalam, dll.)
• Performa server indeks menjadi sangat penting: perlu penambahan mesin terus-menerus + peningkatan performa berbasis software 10-30% setiap bulan
• Cara ekspansi: menambah lebih banyak shard dan replica
• Implikasi:
  • Waktu respons shard dipengaruhi oleh jumlah disk seek dan banyaknya data yang harus dibaca
  • Area potensial untuk peningkatan performa: penjadwalan disk yang lebih baik, encoding indeks yang ditingkatkan

Evolusi Teknik Encoding Indeks

• Encoding awal ('97): format byte-aligned yang sangat sederhana (WORD → [docid+nhits:32b, hit:16b, hit:16b...]). hit adalah posisi + atribut (ukuran font, judul, dll.). Ditambahkan skip table untuk posting list besar. Decoding murah tetapi rasio kompresi rendah sehingga membutuhkan bandwidth disk besar.
• Berbagai teknik encoding:
  • Tingkat bit: Unary, Gamma, Rice_k (kasus khusus kode Golomb), Huffman-Int
  • Byte-aligned: varint (7 bit per byte + continuation bit)
• Format indeks berbasis blok: mengurangi penggunaan ruang dan CPU (~ukuran turun 30%), sekaligus meningkatkan kecepatan decoding. Menggunakan blok dengan panjang variabel. Header (delta, panjang, dll.) + delta ID dokumen (Rice_k) + jumlah hit (Gamma) + atribut hit (run-length Huffman) + posisi hit (Huffman-Int).
• Format indeks baru (setelah 2004): menggunakan satu ruang posisi flat. Struktur data tambahan melacak batas dokumen. Posting list berupa daftar posisi yang di-delta-encode. Kompak dan kecepatan decoding yang sangat tinggi sama-sama penting.

Sistem Indeks In-Memory (awal 2001)

• Latar belakang: ekspansi sharding + bertambahnya replica → total memori yang cukup untuk menyimpan salinan penuh indeks di memori
• Arsitektur: frontend → load balancer (bal) → shard (beberapa replica server indeks in-memory per shard)
• Kelebihan: throughput meningkat drastis, latency turun drastis (terutama untuk kueri kompleks yang sebelumnya membutuhkan I/O disk berukuran GB — misalnya "circle of life")
• Masalah:
  • Varians (Variance): penggunaan ribuan mesin, bukan puluhan, membuat perilaku semakin sulit diprediksi (misalnya pekerjaan cron acak yang menimbulkan masalah)
  • Ketersediaan (Availability): jumlah replica data indeks tiap dokumen hanya 1 atau sedikit → "kueri kematian" (semua backend mati bersamaan), masalah ketersediaan data indeks saat mesin gagal (terutama dokumen penting perlu direplikasi)

Desain dan Teknologi Sistem Tahap Lanjut (setelah 2004)

• Perangkat keras: data center berskala lebih besar, rack rancangan sendiri, motherboard kelas PC, hardware storage/networking murah, Linux + software buatan sendiri
• Desain serving (edisi 2004): struktur hierarkis
  • Server Root → server Parent → server Leaf (memuat Repository Shard dari GFS melalui File Loader)
  • Terintegrasi dengan server cache

Encoding Group Varint

• Ide: mengatasi inefisiensi decoding varint (banyak operasi branch/shift/mask). Empat nilai integer dikelompokkan dan di-encode menjadi 5~17 byte.
• Cara kerja:
  • Empat tag 2 bit yang menyatakan panjang byte tiap nilai (1~4 byte) digabung menjadi satu byte prefix
  • Setelah byte prefix, byte data aktual disimpan
• Decoding: baca byte prefix, gunakan sebagai indeks untuk lookup tabel 256 entri yang telah dipra-hitung → dapatkan informasi offset dan mask untuk mendecode 4 nilai sekaligus.
• Performa: jauh lebih cepat daripada metode sebelumnya (Group Varint: ~400M/detik, 7-bit Varint: ~180M/detik, 30-bit Varint w/ 2-bit len: ~240M/detik)

Universal Search (2007)

• Sistem yang menampilkan tidak hanya hasil pencarian web, tetapi juga mengintegrasikan berbagai jenis informasi (gambar, informasi lokal, berita, video, blog, buku, dll.).
• Node super root mengirim kueri ke beberapa sistem pencarian khusus (search engine vertikal) dan menggabungkan hasilnya.

Tantangan Crawling dan Indexing Berlatensi Rendah

• Mencerminkan pembaruan dalam hitungan menit adalah tantangan yang sangat sulit.
• Heuristik crawling: halaman mana yang harus di-crawl?
• Sistem crawling: harus mampu melakukan crawl halaman dengan cepat.
• Sistem indexing: bergantung pada data global seperti PageRank dan anchor text → membutuhkan pendekatan real-time approximation online.
• Sistem serving: harus siap menerima pembaruan saat memproses kueri (memerlukan struktur data yang sangat berbeda dari sistem pembaruan batch).

Pentingnya Eksperimen dan Infrastruktur

• Kemudahan eksperimen: sangat penting (siklus eksperimen cepat → lebih banyak eksperimen → lebih banyak peningkatan).
• Jenis eksperimen:
  • Eksperimen mudah: seperti menyesuaikan bobot data yang sudah ada.
  • Eksperimen sulit: membutuhkan data baru yang tidak ada di indeks produksi. (Harus mudah membuat/mengintegrasikan data baru dan menggunakannya dalam eksperimen)
• Infrastruktur inti:
  • GFS: sistem file terdistribusi skala besar
  • MapReduce: memudahkan penulisan/eksekusi pekerjaan pemrosesan data skala besar. (Mempercepat pembuatan data indeks produksi, menjalankan eksperimen ad hoc dengan cepat)
  • BigTable: sistem penyimpanan semi-terstruktur. (Akses online/efisien ke informasi per dokumen, memungkinkan beberapa proses memperbarui informasi dokumen secara asinkron — penting untuk pembaruan dari hitungan jam menjadi hitungan menit)

Siklus Eksperimen dan Rilis

1. Perumusan ide dan eksperimen offline:
   • Membuat data dengan MapReduce, BigTable, dll.
   • Menjalankan eksperimen offline dan memverifikasi efektivitasnya (set kueri evaluasi manusia, set kueri acak, dll.).
   • Pada tahap ini, latency/throughput prototipe tidak penting.
   • Melakukan perbaikan iteratif berdasarkan hasil eksperimen.
2. Eksperimen live:
   • Jika hasil eksperimen offline baik, lakukan eksperimen live pada sebagian kecil traffic pengguna nyata (biasanya sampel acak, kadang untuk kelas kueri tertentu).
   • Pada tahap ini, latency lebih penting daripada throughput! Kerangka eksperimen harus berjalan mendekati latency lingkungan produksi.
3. Tuning performa dan rilis:
   • Jika hasil eksperimen live baik, lakukan tuning performa/reimplementasi agar dapat berjalan pada beban penuh (misalnya pra-hitung data alih-alih menghitung saat runtime, gunakan pendekatan yang lebih murah jika "cukup baik").
   • Proses rollout penting: terus mempertimbangkan trade-off kualitas vs biaya, menyeimbangkan rilis cepat dengan latency rendah/stabilitas situs (diperlukan kolaborasi yang baik antara tim kualitas pencarian dan tim performa/stabilitas).

Arah dan Tantangan Masa Depan

• Pengambilan Informasi Lintas Bahasa (Cross-Language IR): menerjemahkan semua dokumen di dunia ke semua bahasa → ukuran indeks melonjak, biaya komputasi tinggi. (Kualitas terjemahan terus membaik, tetapi dibutuhkan sistem skala besar untuk menangani model bahasa yang lebih besar dan lebih kompleks)
• Access Control Lists (ACLs) dalam sistem pengambilan informasi: lingkungan campuran dokumen pribadi/semi-pribadi/dibagikan luas/publik. (Perlu sistem yang dapat menangani ACL dengan ukuran yang sangat bervariasi secara efisien — solusi optimal untuk dokumen yang dibagikan ke 10 orang berbeda dari dokumen yang dibagikan ke seluruh dunia, dan pola berbagi bisa berubah seiring waktu)
• Pembangunan otomatis sistem IR yang efisien: saat ini digunakan berbagai sistem untuk tujuan berbeda (untuk pembaruan supercepat, untuk dokumen skala sangat besar, dll.). (Mungkinkah mengembangkan satu sistem yang dapat secara otomatis membangun sistem pencarian efisien sesuai kebutuhan saat parameter diberikan?)
• Ekstraksi informasi dari data semi-terstruktur: data dengan label semantik yang jelas sangat sedikit. Tabel, formulir, dan data semi-terstruktur sangat melimpah. (Diperlukan algoritme/teknik yang lebih baik untuk mengekstrak informasi terstruktur dari sumber tak terstruktur/semi-terstruktur — banyak noise tetapi dapat memanfaatkan redundansi, serta kemampuan mengaitkan/menggabungkan/mengagregasi informasi dari banyak sumber)

Kesimpulan

• Merancang dan membangun sistem pengambilan informasi skala besar adalah pekerjaan yang menantang dan menyenangkan.
• Teknologi pencarian baru sering kali membutuhkan desain sistem yang baru.