Google 為什麼能在 0.15 秒找到數十萬筆資料?認識搜尋霸主的核心技術

當你在瀏覽器上輸入想要搜尋的字串時,Google 會檢視數十億個網頁,並依據索引值從中找出內容相符合的網頁,再依據相關的規則列出先後次序,而搜尋引擎會將結果以最快的時間回傳。

但是,網路上的資料量不但龐大,而且內容隨時都在變化,甚至同一個網頁的內容都會一天數變,因此,Google 就必須時時進行更新的動作,這個動作叫「爬行」(Crawling),而執行爬行動作的程式一般俗稱「爬蟲」(Crawler)或「網路蜘蛛」(Spider),除了搜尋引擎之外,常見的應用還有比價系統,像是 FindPrice、背包客棧國際訂房中心比價等都是。

而 Google 之所以能成為其中的霸主,當然是有其過人之處。本篇文章就跟各位讀者簡單地分享一下 Google 所開發的三個核心技術:GFS、BigTable 與 MapReduce 演算法。

1. Google File System,用來用以儲存 Big Data

Google File System(GFS 或 GoogleFS)是由數百個叢集(Cluster)所組成。每一個叢集有多達數千台的伺服器,是一種分散式容錯檔案系統,主要的任務是儲存網頁、影片、照片、Email 和 Google Map等資料,而這些檔案極少被刪除或異動,大多數時候都是新增或讀取,因此,對其進行最佳化的管理就非常重要了。

儲存在 GFS 的檔案會被切割成 64 MB 左右的資料塊(Chunk),分別放在三台稱為 Chunkserver 的伺服器內,當 Chunkserver 發生問題時,主伺服器(Master Server)就會將資料複製到另一個 Chunkserver 上。

2. BigTable ,利用成對的 Key-Value,快速讀取資料

BigTable 就字面上的意思看來,就是「大型的資料表」,它主要負責管理 GFS 的機制,屬於分散式資料儲存系統,可以管理分佈在數千台伺服器上的 Big Data,就像是一張資料表(Table),資料表上註明了每一台伺服器所有的資料,包括 Google Analytics、Google Earth、Gmail、Google Reader、Google Map、Google Finance 以及 YouTube 等。

由於上述這些產品的應用對於 BigTable 的需求與所組成的結構各不相同,因此 BigTable 採用了鍵與值 Key-Value 的資料架構,其具有水平擴充的能力,只要空間不足就可以立即新增資料庫,而它的儲存容量屬於 PB 等級(1 Petabyte(PB)= 1024 TB)。

當然對 Google 而言,系統的回應時間仍是首要考量,因此,BigTable 設計時的主要目標就著重於「可靠地處理大量的數據」,因而採用了叢集平行處理技術。
3. MapReduce ,用來處理與分析 Big Data

MapReduce 用來進行 Big Data 的計算,其包含了 Map 和 Reduce 兩個部份,主要用於大規模資料集的平行運算。

簡單來說,MapReduce 在處理資料時,Map 函數會把原始資料映射成新的一組鍵與值(Key-Value)的序對,並切割成有規律性的小資料,並經過 Shuffle 做排序,最後再透過 Reducer 函數依相同的 Key 整合結果,最後才能將整體的結果輸出。

例如,上網查 MapReduce 這個字串,會透過 Map 函數計算網頁上出現「MapReduce」的次數,如果出現 10 次就用(MapReduce, 10)來表示;再用 Reduce 函數彙整所有具有相同 Key 值的資料,並統計它們出現的次數。


資料來源:TechOrange

如果喜歡我們的文章,請即分享到︰