百度第三代搜索引擎工作原理
搜收錄網整理 發布日期:2017/1/16 13:48:45
百度第三代Spider是什么?
 
在過去,百度搜索引擎的數據處理的多數工作是由MapReduce系統完成的,處理延時達到天級。從2014年開始,Spider系統進行了大規模重構,以搜索結果更新延遲從周級縮短到分鐘級為目標,設計實現了海量實時數據庫Tera。在此基礎上,構建了每天實時處理幾萬億鏈接與網頁更新的百度第三代Spider系統。
 
區別于上一代系統,新系統的核心流程全部實時化,從互聯網上出現一篇新網頁,到基于歷史分析與機器學習快速發現鏈接,到基于鏈接價值的抓取調度,再到對網頁進行分類、篩選每個步驟都在幾秒鐘內完成,以保證新網頁能以分鐘級更新到搜索結果中。
 
也就是說,當互聯網上產生一個新的網頁時,Spider 2.0把它下載回來的時間大概是2-3天,而Spider 3.0卻只需要5分鐘,相當于大概是3個量級的提升。
 
我從一加入百度,就開始構想第三代Spider了,后面的五年幾乎都在開發百度Spider第三代系統。因為它是一個非常龐大的業務系統,所以底層需要各種各樣的基礎架構系統支持,包括分布式文件系統、集群管理系統和數據庫系統等等。當前,這些底層系統都已經開源,如果有興趣可以一起參與進來。
 
搜索引擎與Spider3.0
 
首先故事從互聯網和搜索引擎開始,大家平時經常接觸到的互聯網以及百度搜索引擎,很多人也思考過互聯網上的網頁怎么轉化成百度搜索引擎里面這十條結果的。這里面的工作分為很多階段,如下圖所示。最開始,由Spider去做信息采集。
 
后面的Pagerank其實代表了一系列的計算,包含了反作弊、去重和基于頁面質量的篩選等等。此階段之后會對網頁進行切詞,計算網頁的正排,再做轉置變成倒排。最后進入檢索系統供網民直接檢索。Spider是該系統的起點,它的主要目的就是快速、全面地采集全網數據。那么,全網數據到底是什么概念呢?
大家設想一下,當前中文互聯網到底有多少網頁?不知道有多少人嘗試算過或者估算過,其實我們也不知道具體的數字,但是我們通過搜索引擎估算,結果大概有100萬億的網頁。其中高質量的部分大概有10萬億,這10萬億就是百度Spider所要采集網頁的核心任務。
 
但是,光采集回來還不夠,還要知道它到底有沒有價值。中文互聯網每天新增多少網頁?100億,也就是說互聯網每天就會產生100億的新網頁。那么會產生多少條超級鏈接呢?每個網頁上會有多少條鏈接?百度統計的大概結果是,平均一張網頁上有120條鏈接,這不是指特定某個網頁上有120條,而是平均值。從這一點就看到整個百度Spider每天要處理的數據量,大概每天要處理1萬多億的鏈接。
 
怎么去處理這么大規模的數據,其實在過去有個比較通用的解決方案:Hadoop。基于Hadoop的第二代Spider主要流程如下圖所示,所有持久化數據存儲在HDFS中,通過MapReduce任務進行選取、挖掘、回灌和抓取結果入庫。
Hadoop時代的百度Spider
 
但這個Spider有什么問題嗎?其實它的首要問題就是線性擴展的問題。很多時候大家接觸到的線性擴展或者水平擴展都是一個褒義詞,即用10倍的機器就能處理10倍的數據,線性增長,處理能力沒有明顯的下降。
 
但是,在這里它卻變成了一個嚴重的問題:舉個例子,在過去Spider系統每天處理1000億鏈接的時候需要500臺服務器,而今天互聯網上的鏈接呈爆炸性的增長,系統每天要處理10萬億級的鏈接,就需要5萬臺服務器,這肯定是一個不可承受的代價或者成本,所以這時候我們必須得有新的解決方案,不能再做全量的處理,必須有一種增量的,只處理新鏈接的方式。
我們期望的處理過程如圖所示。
 
很多人看到后可能有些失望,百度Spider就這么點東西嗎?其實大家仔細去想,簡單代表了更更大的靈活性和更強的擴展性。它其實就是一個流式計算系統,然后系統中的每一個策略也好,或者過程也好,都是流式系統上的一個算子,比如調度、抓取、頁面解析、頁面打分、鏈接權值打分。
 
整套系統的核心在于數據。一方面,我們做實時數據處理,表面上完成工作的是這些算子和計算流程,而每個算子的計算都依賴與數據的輸入和輸出,算子的計算延遲很大程度上決定于輸入數據的獲取延遲,輸出數據的寫出延遲。算子計算的穩定性又依賴與數據的不重不丟,這些數據必須有一個持久存儲,又能隨時、隨地獲取的方式,這樣才能更好的去做實時的流式的處理。
 
另一方面,區別于普通的流式處理,如果僅去對單個鏈接或網頁做流式處理,常規的Strom、Flink這些框架都是可以做到的。那么,它的真正的難點是什么?其實整個搜索引擎的計算,數據之間是有依賴性的,一張網頁的價值誰說了算,一部分是由所在站點的權值和路徑深度決定,更多的是由指向它的鏈接(前鏈)來投票決定。
 
也就是說處理一張網頁時其實要同時處理整個數據集里面上百處位置的狀態,一張網頁價值變化了,要同時更新網頁上包含的所有鏈接對應網頁的權值,同樣,在判斷一個鏈接的價值時,也可能要依賴它的成百上千個前鏈上的實時數據。這就要求前面提到的那個可以隨時、隨地訪問的數據集不是一個局部數據集,而是涵蓋互聯網全網數據的全集。
 
Tera的模型與架構
 
百度的第三代Spider系統,它的核心在于實時的數據處理,這些實時的數據處理的主要挑戰:
 
第一個挑戰就是全量數據的數據集比較大,大概10萬億條,百PB量級。如果是冷數據,把它放在冷備存儲上可以很低價的維護,但是在Spider中不可能做到這樣,因為每時每刻這個數據集中的每一條都有可能被改變,要保證它被改變時隨時被更新,也就是在10萬億條數據級上隨時去讀寫。
第二個挑戰就是每天新抓網頁100億,觸發1萬億條鏈接更新,每秒屬性更新近億次,這帶來的是一個量級的提升,會對底層數據庫造成每秒上億次的隨機讀寫訪問。另外搜索引擎有一個特點,就是需要做調度,底層數據訪問既可以隨機訪問也可以順序訪問,要求底層存儲里的這些數據有序,這樣就可以很好的統計一個站點上到底抓了多少,我們知道我們現在控制的一個站點壓力不要把這個站點壓跨,所以說需要很多維度的調度。
面對這些挑戰,我們給出來的解決方案就是分布式的數據庫 Tera ,首先容量自不必多說,必須要達到萬億量級百P的容量,再就是它要多維度的調度,支持區間訪問,方便統計,就必須是一個有序表,它最核心的點是要支持自動的負載均衡,自動擴容,自動縮容。
 
因為眾所周知的一種情況是互聯網上熱點頻發,經常有一些站點成為爆發狀態,還有一些站點突然就消失了。還有一種情況就是業務迭代非常快,可能有些業務剛創建了表,只需要10臺機器進行服務,可一旦快速擴張,可能就需要幾百臺機器了,你應該很快地實現這種擴容,同樣當它的峰值過去后也能很快地實現縮容。
 
除此之外,這個系統還要有一個多版本特點。有這么一種情況,上線一種新的策略或者新的活動時,因為有些地方邏輯出了個BUG,把數據庫寫壞了,這時候需快速恢復或者止損,就只有一個辦法,就是將整個數據庫狀態回滾。此外,這個數據庫還有一個特性,比如列存儲、分布式事務,都是一些比較擴展性的特征。
 
該數據庫的核心數據模型是三維的,除了行和列還有時間的維度,通過這個維度我們可以存儲網頁或普通的歷史數據,這樣一方面方便我們去做歷史行為的挖掘,另一方面它也實現了剛才我說的回滾,可回滾到昨天前天或者某個時間的特殊狀態。
 
第二點就是說這個數據庫它的分片(sharding)方式,是一個全順序按行去切分的,也就是說行與行之間絕對有序,然后在中間把它切開以后分到不同的區間上去,區間與區間之間也是有順序的。
 
 
按行切分成多區間(Tablet)
 
在這里大家可以看到它的一個簡化的架構圖,我們把整個數據表按行去切分層多個Tablet,或者切分為一個子區間,每一個子區間都可以在TabletServer上服務,這張圖其實還有一個核心點,我想讓大家注意一下就是它的一個核心設計的思想在于它把所有的數據全部放在底層的分布式文件系統,這里面提到的BFS上,這樣整個數據庫都是無狀態的,它的所有的數據全部是落在分布式文件系統上的,這就為了后面的很多特征的實現提供了可能。
 
 
Tera架構
 
這個具體做的事就是一件事,就是把隨機寫轉換成順序寫,讓我們對整個海量的順序這種隨機讀寫的訪問成為了可能,它把隨機寫轉換成順序寫的算法也很簡單,他通過先寫Log再寫內存,等內存寫到一定量的時候,把內存成為一種靜態文件,這種方式去實現了支持順序寫,還能夠保證最后下去的數據有序,然后再去后臺,進行垃圾收集,保證整體的數據量有限的膨脹。
 
以上就是它的架構了,那么它給為我們帶來什么呢?首先,它實現了在流式的處理系統中做到海量數據隨時隨處可用,上層的計算系統有很大的空間,有PB級的內存,統一的地址空間,幾乎你在任何一臺機器上想存的數據都是可以存下。再下面就是百PB級存儲,不用擔心持久化,你不用擔心數據丟失,它做到了數據寫下去以后,任何其他機器實時可讀,寫入立即可讀。
 
很多人都用過Hbase,下面列一下它和HBase的一些相同點和不同點。
 
相同點有兩個:
 
Bigtable數據模型
開源
不同點有三個:
 
一是可用性,這個系統最核心的一點就是說我們通過提升可用性,來解決了在我們上層實時業務中能夠真正去支持實時業務。這一點怎么去做到的,后面會詳細介紹。它主要解決了區間熱點的問題,不會因為某些區間熱點導致區間不可服務。
二是吞吐和延遲,Tera是C++實現,效率更高的同時,沒有內存GC,不存在延遲不穩定的問題。
三是擴展性,HBase可以做到數百臺,而它可以做到數千臺。
以上這些我們怎么做到的?首先就是快速負載均衡,其實更核心的一個點在于熱點區間的分裂,就是說我們如果由于業務的變化,或者說上層用戶行為的變化,導致一個區間變成了一個熱點區間,那么我們會在很快的時間內把它分裂開,一個區間分裂成多個區間,然后把其中的一部分遷移到比較空閑的機器上,通過這種方式實現了快速的負載均衡。這個快速負載均衡是通過文件引用的方式去實現的,也就是說不論是區間的分裂還是區間的遷移都是沒有任何數據拷貝的,因為數據全部分布在底層的分布式系統上的。
 
在此大家也會想到其實HBase也是有這個功能,它熱點區間也是可以提供這種在線的分裂,但是這里往往會引入這么一個問題,就是原來0這個區間是個熱點的時候把它分為1和2,很快2這個區間又成為熱點了,你把2再分成3和4,如果現在4這個區間又成為熱點又怎么辦?
 
在HBase上敢這么分嗎?你剛開始初期創建了一個表,有一千個分片,那么可能兩天三天以后就變成一千萬個分片,因為不停分裂下去,分片數就完全不可控了,所以這里負載均衡核心問題不在于快速分裂,而在于很好的處理分裂后的碎片問題,能做到一旦一個區間不再是熱點區間了,能瞬間合并。
 
所以在此要強調一點,能快速合并才能做到敢分裂,這才是一個真正的解決熱點問題的方式。在這一點上TabletServer系統就是區間快速遷移,區間快速合并,僅有元數據變更,代價小,時間短,全自動,無人工干預。
 
表面上我們解決熱點問題的方式是用快速的區間分裂和遷移去做的,實際上這個問題本質上是通過什么方式解決的呢?這里通過一張圖去展示這一點,即連續區間本身是存在一臺機器上服務的,但是這一個區間內部可能會有很多這種SST這種靜態文件,這種靜態文件實際上在底層分布式文件系統上是散在幾百臺甚至上千臺機器上的,這種非常強的隨機讀能力去解決的熱點問題,也就是說雖然你看到了一個區間是在一臺機器上服務,實際上它的所有數據文件,所有你讀它產生的IO都會被打散到底層的幾百臺機器上去。
 
這里有一個背后的英雄,就是百度文件系統BFS,這套文件系統的設計非常復雜,但是它核心是解決了HDFS的擴展性以及延遲的問題,可以真正面向實時應用,做到持續可用、低延遲。這個文件系統當前也已經開源。
 
系統構建中的經驗與教訓
 
下面介紹一些在構建上層業務系統、底層分布式系統中積累的一些經驗。
 
第一個經驗,是采用分層設計的原則,如下圖所示。
 
 
工業實踐-分層設計
 
從圖中可以看到當前百度網頁搜索的軟件棧,最底層的網絡框架包含了分布式文件系統、集群調度系統和分布式協調服務;再上層是數據庫;再上層才是實際的業務。
 
這些技術系統都是一層一層堆上去的,比如說最底層的網絡通信框架,所有的網絡問題,包含Socket編程的封裝,網絡的流量控制,跨地域的鏈接優化,全部會封裝在這一層。上層用它開發分布式文件系統時,就完全不需要考慮網絡問題、流量控制問題了,只需要關注分布式文件系統的邏輯就可以了。
 
然后,把所有數據持久化甚至IO相關的一些工作全部放在分布式文件系統這一層。在構建上層的分布式數據庫、分布式數據處理框架,乃至上層業務系統的時候,都不再需要考慮數據持久化的問題,也不需要考慮IO持久能力的問題。這樣就能讓數據庫可以做到完全無狀態的。大家可能接觸過很多數據庫,沒有任何一個數據庫系統可以做到完全無狀態的。這個完全無狀態甚至包含cache無狀態。
 
也就是說這種分層設計帶來一個最大的好處,就是任何問題在一處解決了,很多處都會受益,同樣問題在一個地方解決一次就夠了,上層系統完全不需要考慮網絡問題、丟數據的問題、IO能力的問題。
 
第二個經驗,是要去為可用性設計,要能做到容錯。通常我們計算可用性可以用:可用性=(總時間-故障數*恢復時間)/總時間。很多工程師和架構師做系統設計的時候,會把很多精力放在降低故障發生的頻率,降低故障發生的機會,盡量讓系統不要出故障,以這種方式來提高可用性,而在我們這套設計思想里,我們不通過這種方式提高可用性,為什么?
 
因為故障不可避免。假設我們單臺服務器的平均故障間隔時間是30年,在市場上你是絕對買不到這種30年都不會壞的服務器的,但我們假設你有這種服務器,你去搭建一個萬臺的集群,你在使用這個集群的過程中會發現每一兩天就會壞一臺機器。也就是說無論你的服務器再好,都不能避免故障。
 
我們提高可用性的思路就是降低故障恢復的時間,平常所說的幾個9,就是總請求數減去故障數,乘以故障影響的數,通過這套思想,這套分布式數據庫做到比以前高一個9,就在于故障恢復時間。
 
第三個經驗,是要去為低延遲設計。因為我們現在整個上層的業務系統都在從批量到實時過渡,我們要做實時系統,實時系統很大程度上對延遲有很高的要求,backup request是個很好的選擇,我希望他99.9分位的延遲不要超過10毫秒。我期待這個服務平均1毫秒返回,如果2毫秒還沒返回,我就再發一個請求到備份節點,這樣來降低延遲的長尾。
 
另外是慎用自動GC的語言,實時處理,大量小請求,頻繁觸發STW,服務無響應,不必要的failover,導致整個系統不穩定,所以盡量不要用這種自動GC語言。剩下可選的語言可能就不多了,所以我們這套系統選擇用C++開發。
 
未來工作
 
這套系統未來的工作是走出百度、走向社區。今天,百度這一套核心的分布式系統已經完全開源了,我們也把所有的開發、codereview和版本的發布,全部放在GitHub上,外部提交的代碼已經在驅動百度的這套搜索了。

信息網址:http://www.qjafkd.live/ziyuan/view15951.htm
相關信息
抢红包试玩