it-swarm-id.com

Bagaimana Anda menerapkan Pencarian Google?

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 tepat 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. Apa layanan/mesin arsitektur Anda terdiri dari. Akan seperti apa latensi kueri? Bagaimana dengan gangguan otak? Dll ...

47
ripper234

The posting di Quora menghasilkan artikel asli diterbitkan oleh Sergey Brin dan Larry Page. Tampaknya menjadi referensi yang sangat baik untuk jenis pertanyaan ini.

Google Architecture

19
ripper234

Pertimbangkan meta-point: apa yang dicari pewawancara?

Sebuah pertanyaan raksasa seperti itu tidak mencari Anda untuk membuang waktu Anda dalam sepele demi mengimplementasikan algoritma tipe PageRank atau bagaimana melakukan pengindeksan terdistribusi. Alih-alih, fokuslah pada gambar lengkap dari apa yang diperlukan. Sepertinya Anda sudah tahu semua bagian besar (BigTable, PageRank, Map/Reduce). 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, lalu Mengurangi hasilnya menjadi 'benda' tunggal.) 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 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. (Lebih banyak tautan 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 umumnya adalah cara yang dapat diskalakan untuk menganalisis data Anda .

Fase 3: Melayani Hasil (menghabiskan 10 menit 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 jumlah 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 memerlukan cara untuk menemukan data di dalamnya dengan cepat. (E.g., 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 topik apa pun yang Anda ketahui.

  • Performa 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. (E.g., 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.

46
Chris Smith