Bagaimana Google bisa begitu cepat?

89

Teknologi dan keputusan pemrograman apa yang membuat Google dapat melayani kueri dengan begitu cepat?

Setiap kali saya mencari sesuatu (satu dari beberapa kali per hari), saya selalu heran bagaimana mereka menyajikan hasil dalam waktu dekat atau kurang dari 1 detik. Konfigurasi dan algoritme seperti apa yang dapat mereka miliki untuk menyelesaikan hal ini?

Catatan sampingan: Ini adalah pemikiran yang luar biasa bahwa bahkan jika saya meletakkan aplikasi desktop dan menggunakannya di mesin saya mungkin tidak akan secepat Google. Teruslah belajar, kataku.

Berikut adalah beberapa jawaban dan petunjuk bagus yang diberikan:

performance algorithm Jorge Ferreira
sumber

Jawaban:

47

Latensi dimatikan oleh akses disk. Oleh karena itu, masuk akal untuk percaya bahwa semua data yang digunakan untuk menjawab pertanyaan disimpan dalam memori. Ini berarti ribuan server, masing-masing mereplikasi salah satu dari banyak pecahan. Oleh karena itu, jalur penting untuk pencarian tidak mungkin mencapai teknologi sistem terdistribusi andalan mereka GFS, MapReduce, atau BigTable. Ini akan digunakan untuk memproses hasil perayap, secara kasar.

Hal yang berguna tentang pencarian adalah tidak perlu memiliki hasil yang sangat konsisten atau data yang benar-benar mutakhir, sehingga Google tidak dicegah untuk menanggapi permintaan karena hasil pencarian yang lebih mutakhir telah tersedia.

Jadi arsitektur yang mungkin cukup sederhana: server ujung depan memproses kueri, menormalkannya (mungkin dengan menghapus kata-kata berhenti, dll.) Kemudian mendistribusikannya ke subset replika apa pun yang memiliki bagian ruang kueri itu (arsitektur alternatif adalah membagi data oleh halaman web, sehingga salah satu dari setiap set replika perlu dihubungi untuk setiap kueri). Banyak replika mungkin dipertanyakan, dan tanggapan tercepat menang. Setiap replika memiliki kueri pemetaan indeks (atau istilah kueri individual) ke dokumen yang dapat mereka gunakan untuk mencari hasil dalam memori dengan sangat cepat. Jika hasil yang berbeda kembali dari sumber yang berbeda, server front-end dapat memeringkatnya saat mengeluarkan html.

Perhatikan bahwa ini mungkin jauh berbeda dari apa yang sebenarnya Google lakukan - mereka akan merekayasa kehidupan dari sistem ini sehingga mungkin ada lebih banyak cache di area yang aneh, indeks aneh dan semacam skema load-balancing yang funky di antara kemungkinan perbedaan lainnya .

HenryR
sumber
22

Satu fakta yang saya anggap lucu adalah bahwa Google sebenarnya dijalankan oleh bioinformatika ('oke, menurut saya itu lucu karena saya bioinf… thingy). Biar saya jelaskan.

Bioinformatika sejak awal memiliki tantangan untuk mencari teks kecil dalam string raksasa dengan sangat cepat. Bagi kami, "tali raksasa" tentu saja adalah DNA. Seringkali bukan DNA tunggal tetapi database beberapa DNA dari spesies / individu yang berbeda. Teks-teks kecil adalah protein atau pasangan genetiknya, sebuah gen. Sebagian besar karya pertama ahli biologi komputasi dibatasi untuk menemukan homologi antar gen. Hal ini dilakukan untuk memantapkan fungsi gen yang baru ditemukan dengan memperhatikan kemiripan gen yang sudah diketahui.

Sekarang, string DNA ini menjadi sangat besar dan pencarian (lossy!) Harus dilakukan dengan sangat efisien. Dengan demikian, sebagian besar teori modern pencarian string dikembangkan dalam konteks biologi komputasi.

Namun, beberapa waktu yang lalu, pencarian teks konvensional telah habis. Diperlukan pendekatan baru yang memungkinkan pencarian string besar dalam waktu sublinear, yaitu tanpa melihat setiap karakter. Diketahui bahwa hal ini dapat diselesaikan dengan pra-pemrosesan string besar dan membangun struktur data indeks khusus di atasnya. Banyak struktur data yang berbeda telah diusulkan. Masing-masing memiliki kekuatan dan kelemahan, tetapi ada satu yang sangat luar biasa karena memungkinkan pencarian dalam waktu yang konstan. Sekarang, dalam urutan besarnya di mana Google beroperasi, ini tidak sepenuhnya benar lagi karena load balancing di seluruh server, pemrosesan awal dan beberapa hal canggih lainnya harus diperhitungkan.

Tetapi pada intinya, yang disebut indeks q-gram memungkinkan pencarian dalam waktu yang konstan. Satu-satunya kelemahan: Struktur data menjadi sangat besar. Pada dasarnya, untuk memungkinkan pencarian string hingga karakter q (karena itu namanya), diperlukan tabel yang memiliki satu bidang untuk setiap kemungkinan kombinasi huruf q (yaitu, q S , di mana S adalah ukuran alfabet , katakan 36 (= 26 + 10)). Selain itu, harus ada satu bidang untuk setiap posisi huruf dalam string yang diindeks (atau dalam kasus google, untuk setiap situs web).

Untuk mengurangi ukuran yang sangat besar, Google mungkin akan menggunakan beberapa indeks (pada kenyataannya, memang demikian , untuk menawarkan layanan seperti koreksi ejaan). Yang paling atas tidak akan berfungsi pada level karakter tetapi pada level kata. Ini mengurangi q tetapi membuat S jauh lebih besar sehingga mereka harus menggunakan tabel hashing dan collision untuk mengatasi jumlah kata yang berbeda yang tidak terbatas.

Pada level berikutnya, kata-kata yang di-hash ini akan mengarah ke struktur data indeks lain yang, pada gilirannya, akan menampilkan karakter-karakter hash yang mengarah ke situs web.

Singkatnya, struktur data indeks q -gram ini bisa dibilang bagian paling sentral dari algoritma pencarian Google. Sayangnya, tidak ada makalah non-teknis yang menjelaskan cara kerja indeks q -gram. Satu-satunya publikasi yang saya tahu yang berisi penjelasan tentang cara kerja indeks semacam itu adalah… sayangnya, skripsi saya .

Konrad Rudolph
sumber
4
Saya berada di bioinformatika selama 5 tahun, dan mesin pencari setelah itu - dan q-gram tidak sepenting yang Anda kira. Struktur data fundamental untuk jenis pencarian yang dilakukan Google (pada tingkat yang sangat, sangat dasar) adalah indeks terbalik.
SquareCog
Sepertinya itu salah. Google sedang atau sedang menjalankan indeks terbalik. q-gram akan berguna untuk frase tetapi tidak secara umum
Stefan Savev
@ Stefan: Komentar yang sama sudah dibuat oleh SquareCog - dan saya tidak menyangkal bahwa indeks terbalik memainkan peran besar (dan mungkin jauh lebih besar dari indeks n-gram). Saya memilih teknologi yang satu ini karena n-gram adalah struktur data hewan peliharaan saya, dan menurut saya wawasan utamanya - Google cepat karena tidak benar-benar harus "menelusuri", ia dapat melakukan pencarian yang kurang lebih langsung - bergantung pada indeks seperti itu (nb: ini mungkin dilakukan melalui hashing tetapi ini masih indeks n-gram). Bahwa indeks ini juga kebetulan terbalik adalah kebetulan bagi saya (meskipun mungkin bukan untuk Google ;-)).
Konrad Rudolph
4

Mereka telah menerapkan algoritme yang baik, terdistribusi, dan berjalan pada sejumlah besar perangkat keras.

Anders Sandvig
sumber
4

Salah satu penundaan terpenting adalah server web mengirimkan kueri Anda ke server web, dan responsnya kembali. Latensi ini dibatasi oleh kecepatan cahaya, yang bahkan harus dipatuhi oleh Google. Namun, mereka memiliki pusat data di seluruh dunia. Akibatnya, jarak rata-rata ke salah satu dari mereka lebih rendah. Ini membuat latensi turun. Tentu, perbedaannya diukur dalam milidetik, tetapi penting jika respons harus sampai dalam 1000 milidetik.

MSalters
sumber
4

Semua orang tahu itu karena mereka menggunakan merpati , tentunya!

Oh ya, itu dan Mapreduce.

HanClinto
sumber
Jika mereka membuat tikus bekerja untuk mereka juga, dua makhluk yang paling tidak berguna dan menjengkelkan akan memiliki pekerjaan ...
Xn0vv3r
Saya banyak tertawa dengan yang satu ini haha
victrnava
3

Mereka cukup banyak memiliki salinan lokal dari internet yang di-cache di ribuan PC di sistem file kustom.

Richard Walton
sumber
Memukul sistem file berbasis disk akan menghabiskan banyak biaya dalam hal latensi (Amazon menemukan ini dengan Dynamo dan mengorbankan beberapa ketahanan untuk itu); Saya menduga bahwa semua yang ada di jalur kritis disimpan dalam memori.
HenryR
3

Google mempekerjakan yang terbaik dari yang terbaik. Beberapa orang terpintar di bidang TI bekerja di google. Mereka memiliki uang yang hampir tak terbatas untuk dibelanjakan pada perangkat keras dan insinyur.

Mereka menggunakan mekanisme penyimpanan yang sangat dioptimalkan untuk tugas-tugas yang mereka lakukan.

Mereka memiliki peternakan server yang berlokasi secara geografis.

Matthew Watson
sumber
3

Upaya membuat daftar umum (yang tidak bergantung pada Anda memiliki akses ke alat internal Google):

  1. Membuat paralel permintaan (misalnya memecah satu permintaan menjadi set yang lebih kecil)
  2. Async (buatlah sesinkronisasi mungkin, mis. Tidak akan memblokir permintaan pengguna)
  3. Memori / cache (Disk I / O lambat, simpan sebanyak mungkin di memori)
  4. Prapenghitungan (Lakukan pekerjaan sebanyak mungkin sebelumnya, jangan menunggu pengguna meminta data / pemrosesan)
  5. Peduli dengan HTML front-end Anda (lihat Yslow dan teman-teman)
Jilles
sumber
1

Perangkat keras.

Banyak sekali perangkat keras. Mereka menggunakan kelompok besar PC komoditas sebagai ladang server mereka.

TraumaPony
sumber
Hanya untuk memperjelas 'masif': ratusan ribu server. Saya kira tidak ada di luar Google yang tahu nomor sebenarnya dan itu pasti berubah sepanjang waktu.
Sergio Acosta
1

TraumaPony benar. Banyak server dan arsitektur cerdas untuk load balancing / caching dan voila Anda dapat menjalankan kueri dalam waktu kurang dari 1 detik. Ada banyak artikel di internet yang menjelaskan arsitektur layanan google. Saya yakin Anda dapat menemukannya melalui Google :)

aku
sumber
0

Dan algoritme yang dapat memanfaatkan kekuatan perangkat keras tersebut. Seperti mapreduce misalnya.

Vinko Vrsalovic
sumber
MapReduce tidak digunakan untuk menanggapi pertanyaan.
MSalters
MapReduce berjalan pada sekumpulan besar mesin dan sangat skalabel: komputasi MapReduce biasanya memproses banyak terabyte data pada ribuan mesin. Ratusan program MapReduce telah diimplementasikan dan lebih dari seribu pekerjaan MapReduce dijalankan di kluster Google setiap hari
Vinko Vrsalovic
MapReduce hampir pasti digunakan untuk mengindeks data perayap secara asinkron. Saya akan sangat terkejut jika itu berada di jalur pencarian yang kritis. Memecat pekerjaan MapReduce benar-benar akan mematikan latensi.
HenryR
Henry - mereka mungkin menggunakannya untuk mengarahkan ke arah / peta. Tapi ya, untuk kasus umum. Anda tidak ingin komputasi hardcore terjadi untuk menanggapi kueri pengguna biasa.
SquareCog
0

Jika Anda tertarik untuk mengetahui detail lebih lanjut tentang cara kerja cluster google, saya akan menyarankan implementasi open source HDFS mereka .

Ini didasarkan pada Mapreduce oleh google.

yann.kmm
sumber
HDFS adalah sistem file terdistribusi. Klon mapreduce disebut Hadoop, dan dapat berjalan baik di HDFS atau di sistem file lokal Anda.
SquareCog
0

  1. Penyimpanan, pemrosesan, dan pengambilan data multi-tahap

  2. Distribusi EFISIEN (100 dari 1000 mesin) dari tugas-tugas di atas

  3. Kerangka kerja yang baik untuk menyimpan data mentah dan hasil olahan

  4. Kerangka kerja yang bagus untuk mengambil hasil

Bagaimana tepatnya semua ini dilakukan dirangkum oleh semua tautan yang Anda miliki di ringkasan pertanyaan

kehidupan komputasi
sumber