Yah, saya tidak yakin apakah MapReduce yang memecahkan masalah, tetapi MapReduce tidak akan menyelesaikan sendiri semua pertanyaan yang Anda ajukan. Tetapi di sini ada hal-hal penting yang perlu dipertimbangkan, dan itu memungkinkan untuk memiliki latensi rendah seperti pada pertanyaan dari semua TB data di mesin yang berbeda:
- komputasi terdistribusi: dengan didistribusikan tidak berarti bahwa indeks hanya didistribusikan di mesin yang berbeda, mereka sebenarnya direplikasi bersama kelompok yang berbeda, yang memungkinkan banyak pengguna melakukan kueri yang berbeda dengan waktu pengambilan yang rendah (ya, perusahaan besar mampu membayar sebanyak itu mesin);
- caching: cache sangat mengurangi waktu eksekusi, baik itu untuk langkah merangkak, untuk pengambilan halaman, atau untuk peringkat dan exihibition hasil;
- banyak penyesuaian: semua algoritma di atas dan sangat efisien / solusi hanya bisa efektif jika implementasi juga efisien. Ada banyak optimasi (kode keras), seperti lokalitas referensi, kompresi, caching; semuanya biasanya berlaku untuk berbagai bagian pemrosesan.
Mengingat hal itu, mari kita coba menjawab pertanyaan Anda:
tapi saya bayangkan itu tidak layak untuk hasil setiap permintaan yang mungkin diindeks
Ya, itu akan, dan sebenarnya tidak mungkin memiliki hasil untuk setiap permintaan yang mungkin . Ada jumlah istilah yang tak terbatas di dunia (bahkan jika Anda menganggap bahwa hanya istilah yang dieja dengan benar yang akan dimasukkan), dan ada jumlah kueri eksponensial dari n -> infpersyaratan ini ( 2^n). Jadi apa yang dilakukan? Caching. Tetapi jika ada begitu banyak pertanyaan / hasil, yang mana yang di-cache? Kebijakan caching. Kueri yang paling sering / populer / relevan untuk pengguna adalah yang di-cache.
bukankah latensi perangkat keras di perangkat keras Google menjadi besar? Bahkan jika data di Google semuanya disimpan dalam TB / SSD
Saat ini, dengan prosesor yang sangat maju, orang cenderung berpikir bahwa setiap tugas yang mungkin harus diselesaikan dalam satu detik (atau kurang), dan yang berkaitan dengan begitu banyak data, harus diproses oleh prosesor yang sangat kuat dengan banyak inti dan banyak memori. Namun, satu-satunya pasar yang berkuasa adalah uang, dan para investor tidak tertarik menyia-nyiakannya. Jadi apa yang dilakukan?
Preferensi sebenarnya untuk memiliki banyak mesin, masing-masing menggunakan prosesor sederhana / dapat diakses (dalam hal biaya), yang menurunkan harga membangun banyak cluster yang ada. Dan ya, itu berhasil. Hambatan utama selalu bermuara pada disk, jika Anda mempertimbangkan pengukuran kinerja sederhana . Tetapi begitu ada begitu banyak mesin, orang bisa memuat semuanya ke memori utama, alih-alih bekerja pada hard disk.
Kartu memori mahal bagi kita, manusia biasa, tetapi sangat murah untuk perusahaan yang membeli banyak kartu seperti itu sekaligus. Karena tidak mahal, memiliki banyak memori yang diperlukan untuk memuat indeks dan menyimpan cache di tangan bukanlah masalah. Dan karena ada begitu banyak mesin, tidak perlu prosesor super cepat, karena Anda dapat mengarahkan pertanyaan ke tempat yang berbeda, dan memiliki kelompok mesin yang bertanggung jawab untuk menghadiri wilayah geografis tertentu , yang memungkinkan untuk penyimpanan data yang lebih khusus , dan bahkan respons yang lebih baik waktu.
Apakah MapReduce membantu menyelesaikan masalah ini?
Meskipun saya tidak berpikir bahwa menggunakan atau tidak MapReduce adalah informasi terbatas di dalam Google, saya tidak fasih tentang hal ini. Namun, implementasi Google dari MapReduce (yang tentunya bukan Hadoop) harus memiliki banyak optimasi, banyak melibatkan aspek yang dibahas di atas. Jadi, arsitektur MapReduce mungkin membantu memandu bagaimana perhitungan didistribusikan secara fisik, tetapi ada banyak poin lain yang harus dipertimbangkan untuk membenarkan kecepatan seperti itu dalam waktu pencarian.
Oke, jadi saya mengerti bahwa pencarian populer dapat di-cache dalam memori. Tetapi bagaimana dengan pencarian yang tidak populer?
Grafik di bawah ini menyajikan kurva bagaimana jenis pertanyaan terjadi. Anda dapat melihat bahwa ada tiga jenis utama pencarian, masing-masing dari mereka memegang sekitar 1/3 dari volume kueri (area di bawah kurva). Plot menunjukkan hukum kekuasaan, dan memperkuat fakta bahwa permintaan yang lebih kecil adalah yang paling populer. Sepertiga kedua dari query masih layak untuk diproses, karena mereka memiliki beberapa kata. Tetapi set yang disebut kueri tidak jelas , yang biasanya terdiri dari kueri pengguna yang tidak berpengalaman, bukan bagian yang diabaikan dari kueri.
Dan ada ruang untuk solusi baru. Karena ini bukan hanya satu atau dua pertanyaan (tetapi sepertiga dari mereka), mereka harus memiliki hasil yang relevan . Jika Anda mengetik sesuatu yang terlalu tidak jelas dalam pencarian Google, itu tidak akan memakan waktu lebih lama untuk mengembalikan daftar hasil, tetapi kemungkinan besar akan menunjukkan kepada Anda sesuatu yang disimpulkan yang ingin Anda katakan. Atau mungkin hanya menyatakan bahwa tidak ada dokumen dengan istilah seperti itu - atau bahkan mengurangi pencarian Anda menjadi 32 kata (yang baru saja terjadi pada saya dalam tes acak di sini).
Ada puluhan heuristik yang dapat diterapkan, yang bisa mengabaikan beberapa kata, atau mencoba memecah kueri menjadi yang lebih kecil, dan mengumpulkan hasil yang paling populer . Dan semua solusi ini dapat dirancang dan disesuaikan untuk menghormati waktu tunggu yang layak , katakanlah, kurang dari sedetik? : D
MapReduce tidak ada hubungannya dengan real-time apa pun. Ini adalah kerangka kerja pemrosesan berorientasi batch yang cocok untuk beberapa tugas offline, seperti ETL dan pembuatan indeks. Google telah pindah dari MapReduce untuk sebagian besar pekerjaan sekarang, dan bahkan ekosistem Hadoop melakukan hal yang sama.
Jawaban untuk latensi rendah umumnya untuk menjaga indeks yang telah dihitung sebelumnya dalam memori. Apa pun yang menyentuh disk sulit dibuat cepat dan diskalakan. Ini adalah bagaimana mesin SQL Hadoop berbasis generasi baru seperti Impala mendapatkan kecepatan begitu banyak dibandingkan dengan infrastruktur berbasis MapReduce seperti Hive , misalnya.
Infrastruktur pencarian tidak dapat men-cache hasil dari setiap permintaan tunggal. Tapi itu pasti bisa men-cache hasil menengah, atau, hasil yang lebih lengkap untuk kueri teratas. Dengan sedikit caching, Anda dapat menyajikan hasil untuk sebagian kecil dari semua kueri.
Pencarian juga dibagi di beberapa server. Jadi satu mesin dapat mendelegasikan ke 100 untuk masing-masing mendapatkan bagian dari hasil dan kemudian menggabungkannya.
Anda juga bisa lolos dengan beberapa tingkat perkiraan. Google tidak secara harfiah membentuk seribu halaman hasil pencarian; itu hanya harus mendapatkan halaman pertama tentang yang benar.
Perlu diingat bahwa Google memiliki jutaan komputer di seluruh dunia. Pertanyaan Anda akan ke pusat data secara geografis dekat dengan Anda dan itu hanya melayani geografi Anda. Ini memotong sebagian besar latensi, yang merupakan jaringan dan tidak memproses waktu di pusat data.
sumber
MapReduce tidak digunakan dalam pencarian. Sudah lama digunakan untuk membangun indeks; tetapi ini adalah kerangka kerja pemrosesan batch, dan sebagian besar web tidak berubah sepanjang waktu, sehingga arsitektur yang lebih baru semuanya bersifat inkremental alih-alih berorientasi batch.
Pencarian di Google sebagian besar akan bekerja sama dengan kerjanya di Lucene dan Elastic Search, kecuali untuk banyak pembobotan dan optimisasi ekstra yang disesuaikan. Tetapi pada intinya, mereka akan menggunakan beberapa bentuk indeks terbalik . Dengan kata lain, mereka tidak mencari beberapa terabyte ketika Anda memasukkan permintaan pencarian (bahkan ketika itu tidak di-cache). Mereka sepertinya tidak melihat dokumen yang sebenarnya sama sekali. Tetapi mereka menggunakan tabel pencarian yang mencantumkan dokumen mana yang cocok dengan istilah permintaan Anda (dengan stemming, salah eja, sinonim, dll. Semua sudah diproses sebelumnya). Mereka mungkin mengambil daftar 10.000 dokumen teratas untuk setiap kata (bilangan bulat 10k - hanya beberapa kb!) Dan menghitung kecocokan terbaik dari itu. Hanya jika tidak ada kecocokan yang baik dalam daftar ini, mereka berkembang ke blok berikutnya berikutnya dll.
Pertanyaan untuk kata-kata umum dapat dengan mudah di-cache; dan melalui preprocessing Anda dapat membuat daftar hasil 10k teratas dan kemudian memeriksanya kembali sesuai dengan profil pengguna. Tidak ada yang bisa diperoleh dengan menghitung jawaban yang "tepat" juga. Melihat hasil 10k teratas sepertinya cukup; tidak ada jawaban yang benar; dan jika hasil yang lebih baik di suatu tempat di posisi 10001 terlewatkan, tidak ada yang akan tahu atau memperhatikan (atau peduli). Kemungkinan sudah peringkat bawah dalam preprocessing dan tidak akan berhasil masuk ke 10 besar yang disajikan kepada pengguna di akhir (atau 3 teratas, pengguna benar-benar melihat)
Istilah langka di sisi lain juga tidak banyak tantangan - salah satu daftar hanya berisi beberapa dokumen yang cocok, dan Anda dapat segera membuang yang lainnya.
Saya sarankan membaca artikel ini:
Dan ya, itulah pendiri Google yang menulis ini. Ini bukan keadaan terbaru, tetapi sudah akan bekerja pada skala yang cukup besar.
sumber