Bagaimana Anda menerapkan Pencarian Google? [Tutup]

44

Andaikata Anda ditanya dalam sebuah wawancara "Bagaimana Anda akan menerapkan Pencarian Google?" Bagaimana Anda menjawab pertanyaan seperti itu? Mungkin ada sumber daya di luar sana yang menjelaskan bagaimana beberapa bagian di Google diimplementasikan (BigTable, MapReduce, PageRank, ...), tetapi itu tidak sepenuhnya cocok dalam sebuah wawancara.

Arsitektur keseluruhan apa yang akan Anda gunakan, dan bagaimana Anda akan menjelaskannya dalam rentang waktu 15-30 menit?

Saya akan mulai dengan menjelaskan bagaimana membangun mesin pencari yang menangani ~ 100rb dokumen, kemudian memperluas ini melalui sharding ke sekitar 50 juta dokumen, kemudian mungkin lompatan arsitektur / teknis.

Ini adalah pemandangan 20.000 kaki. Yang saya suka adalah detailnya - bagaimana Anda akan menjawabnya dalam sebuah wawancara. Struktur data mana yang akan Anda gunakan. Layanan / mesin apa yang tersusun dari arsitektur Anda. Akan seperti apa latensi kueri? Bagaimana dengan gangguan otak? Dll ...

ripper234
sumber
1
Itu pertanyaan wawancara yang cukup. Berapa banyak detail yang mereka cari?
Paddy
1
Sebenarnya, itu adalah pertanyaan yang saya gunakan ketika saya melakukan beberapa wawancara beberapa waktu lalu. Keindahannya adalah bahwa jumlah detail yang Anda berikan benar-benar terserah Anda, dan waktu yang ingin dihabiskan pewawancara Anda untuk hal ini.
ripper234
2
"Peta perkecil! Tolong, pertanyaan selanjutnya." "Kami akan memanggilmu."
2
pertanyaan yang bagus tetapi tipe yang bisa Anda habiskan berjam-jam menjawab. Mungkin saya akan membobol google dengan flash drive
Saya pikir ini adalah pertanyaan yang bagus walaupun saya akan menemukan itu sangat luar biasa. Saya baru-baru ini berpikir tentang bagaimana membangun algoritma untuk "menimbang" artikel di situs berita (secara teori saja, sesuatu yang membuat saya sibuk di kamar mandi :) dan saya akui bahwa saya menemukan ide ini bahkan cukup sulit /kompleks.

Jawaban:

45

Pertimbangkan meta-point: apa yang dicari pewawancara?

Sebuah pertanyaan besar seperti itu tidak mencari Anda untuk membuang-buang waktu Anda dalam seluk beluk menerapkan algoritma tipe PageRank atau bagaimana melakukan pengindeksan terdistribusi. Alih-alih, fokuslah pada gambaran lengkap tentang apa yang akan diambil. Sepertinya Anda sudah tahu semua bagian besar (BigTable, PageRank, Peta / Kurangi). Jadi pertanyaannya adalah, bagaimana Anda benar-benar menyatukan mereka?

Ini tikaman saya.

Fase 1: Infrastruktur Pengindeksan (menghabiskan 5 menit untuk menjelaskan)

Fase pertama penerapan Google (atau mesin pencari) adalah membuat pengindeks. Ini adalah perangkat lunak yang merayapi kumpulan data dan menghasilkan hasilnya dalam struktur data yang lebih efisien untuk melakukan pembacaan.

Untuk menerapkan ini, pertimbangkan dua bagian: crawler dan pengindeks.

Tugas crawler web adalah untuk spider tautan halaman web dan membuangnya ke dalam satu set. Langkah paling penting di sini adalah untuk menghindari terjebak dalam infinite loop atau pada konten yang dihasilkan tanpa batas. Tempatkan masing-masing tautan ini dalam satu file teks besar (untuk saat ini).

Kedua, pengindeks akan berjalan sebagai bagian dari pekerjaan Map / Reduce. (Memetakan fungsi ke setiap item dalam input, dan kemudian Mengurangi hasilnya menjadi satu 'hal'.) Pengindeks akan mengambil satu tautan web, mengambil situs web, dan mengubahnya menjadi file indeks. (Diskusikan berikutnya.) Langkah reduksi hanya akan menggabungkan semua file indeks ini menjadi satu unit. (Daripada jutaan file yang lepas.) Karena langkah-langkah pengindeksan dapat dilakukan secara paralel, Anda dapat mengolah pekerjaan Peta / Perkecil ini di pusat data yang besar dan sewenang-wenang.

Fase 2: Spesifikasi Algoritma Pengindeksan (luangkan 10 menit untuk menjelaskan)

Setelah Anda menyatakan bagaimana Anda akan memproses halaman web, bagian selanjutnya adalah menjelaskan bagaimana Anda dapat menghitung hasil yang bermakna. Jawaban singkat di sini adalah 'peta lebih banyak / Mengurangi', tetapi pertimbangkan hal-hal yang dapat Anda lakukan:

  • Untuk setiap situs web, hitung jumlah tautan yang masuk. (Halaman yang lebih banyak ditautkan ke halaman harus 'lebih baik'.)
  • Untuk setiap situs web, lihat bagaimana tautan disajikan. (Tautan dalam <h1> atau <b> harus lebih penting daripada yang terkubur dalam <h3>.)
  • Untuk setiap situs web, lihat jumlah tautan keluar. (Tidak ada yang suka spammer.)
  • Untuk setiap situs web, lihat jenis kata yang digunakan. Misalnya, 'hash' dan 'tabel' mungkin berarti situs web tersebut terkait dengan Ilmu Komputer. 'hash' dan 'brownies' di sisi lain akan menyiratkan situs itu tentang sesuatu yang jauh berbeda.

Sayangnya saya tidak cukup tahu tentang macam-macam cara untuk menganalisis dan memproses data menjadi super bermanfaat. Tetapi ide umum adalah cara yang dapat diskalakan untuk menganalisis data Anda .

Fase 3: Melayani Hasil (luangkan 10 menit untuk menjelaskan)

Fase akhir sebenarnya melayani hasil. Semoga Anda telah membagikan beberapa wawasan menarik tentang cara menganalisis data halaman web, tetapi pertanyaannya adalah bagaimana Anda sebenarnya menanyakannya? Secara anekdot, 10% permintaan pencarian Google setiap hari belum pernah terlihat sebelumnya. Ini berarti Anda tidak dapat menyimpan hasil sebelumnya.

Anda tidak dapat memiliki satu 'pencarian' dari indeks web Anda, jadi mana yang akan Anda coba? Bagaimana Anda melihat indeks yang berbeda? (Mungkin menggabungkan hasil - mungkin kata kunci 'stackoverflow' muncul sangat banyak dalam beberapa indeks.)

Juga, bagaimana Anda melihatnya? Apa jenis pendekatan yang dapat Anda gunakan untuk membaca data dari sejumlah besar informasi dengan cepat? (Jangan ragu untuk memberi nama pada basis data NoSQL favorit Anda di sini dan / atau lihat apa yang dimaksud dengan BigTable Google.) Sekalipun Anda memiliki indeks luar biasa yang sangat akurat, Anda perlu cara untuk menemukan data di dalamnya dengan cepat. (Misalnya, cari nomor pangkat untuk 'stackoverflow.com' di dalam file 200GB.)

Masalah Acak (sisa waktu)

Setelah Anda menutupi 'tulang-tulang' mesin pencari Anda, jangan ragu untuk mencari tahu tentang setiap topik yang Anda ketahui.

  • Kinerja antarmuka situs web
  • Mengelola pusat data untuk pekerjaan Peta / Kurangi Anda
  • A / B menguji peningkatan mesin pencari
  • Mengintegrasikan volume pencarian / tren sebelumnya ke dalam pengindeksan. (Misalnya, mengharapkan server frontend memuat lonjakan 9-5 dan mati di awal pagi.)

Jelas ada lebih dari 15 menit materi untuk dibahas di sini, tapi semoga cukup untuk memulai.

Chris Smith
sumber
1
Ini adalah jawaban yang bagus, tetapi saya merasa itu tidak mulai mengatasi masalah skala dengan membangun Google. Saya pikir bagian yang lebih menantang adalah dalam Melayani Hasil bagian dari jawaban Anda, dan di mana banyak keajaiban Google berada. Saya punya beberapa ide tentang bagaimana membuat arsitek seperti itu, tetapi saya menarik untuk mendengarkan orang lain.
ripper234
Saya menanyakan ini pada Quora - saya pikir mungkin ada penonton yang menjawab pertanyaan ini. quora.com/…
ripper234
Lihatlah jawaban saya.
ripper234