全網搜索引擎架構與流程
全網搜索的宏觀架構長啥樣?
全網搜索的宏觀流程是怎麼樣的?
![搜索引擎的原理,架構與細節](http://p2.ttnews.xyz/loading.gif)
全網搜索引擎的宏觀架構如上圖,核心子系統主要分為三部分(粉色部分):
(1)spider爬蟲系統
(2)search&index建立索引與查詢索引系統,這個系統又主要分為兩部分:
一部分用於生成索引數據build_index
一部分用於查詢索引數據search_index
(3)rank打分排序系統
核心數據主要分為兩部分(紫色部分):
(1)web網頁庫
(2)index索引數據
全網搜索引擎的業務特點決定了,這是一個“寫入”和“檢索”完全分離的系統:
【寫入】
系統組成:由spider與search&index兩個系統完成
輸入:站長們生成的互聯網網頁
輸出:正排倒排索引數據
流程:如架構圖中的1,2,3,4
(1)spider把互聯網網頁抓過來
(2)spider把互聯網網頁存儲到網頁庫中(這個對存儲的要求很高,要存儲幾乎整個“萬維網”的鏡像)
(3)build_index從網頁庫中讀取數據,完成分詞
(4)build_index生成倒排索引
【檢索】
系統組成 :由search&index與rank兩個系統完成
輸入:用戶的搜索詞
輸出:排好序的第一頁檢索結果
流程:如架構圖中的a,b,c,d
(a)search_index獲得用戶的搜索詞,完成分詞
(b)search_index查詢倒排索引,獲得“字符匹配”網頁,這是初篩的結果
(c)rank對初篩的結果進行打分排序
(d)rank對排序後的第一頁結果返回
三、站內搜索引擎架構與流程
做全網搜索的公司畢竟是少數,絕大部分公司要實現的其實只是一個站內搜索,站內搜索引擎的宏觀架構和全網搜索引擎的宏觀架構有什麼異同?
以58同城100億帖子的搜索為例,站內搜索系統架構長啥樣?站內搜索流程是怎麼樣的?
![搜索引擎的原理,架構與細節](http://p2.ttnews.xyz/loading.gif)
站內搜索引擎的宏觀架構如上圖,與全網搜索引擎的宏觀架構相比,差異只有寫入的地方:
(1)全網搜索需要spider要被動去抓取數據
(2)站內搜索是內部系統生成的數據,例如“發佈系統”會將生成的帖子主動推給build_data系統
看似“很小”的差異,架構實現上難度卻差很多:全網搜索如何“實時”發現“全量”的網頁是非常困難的,而站內搜索容易實時得到全部數據。
對於spider、search&index、rank三個系統:
(1)spider和search&index是相對工程的系統
(2)rank是和業務、策略緊密、算法相關的系統,搜索體驗的差異主要在此,而業務、策略的優化是需要時間積累的,這裡的啟示是:
a)Google的體驗比Baidu好,根本在於前者rank牛逼
b)國內互聯網公司(例如360)短時間要搞一個體驗超越Baidu的搜索引擎,是很難的,真心需要時間的積累
四、搜索原理與核心數據結構
什麼是正排索引?
什麼是倒排索引?
搜索的過程是什麼樣的?
會用到哪些算法與數據結構?
前面的內容太宏觀,為了照顧大部分沒有做過搜索引擎的同學,數據結構與算法部分從正排索引、倒排索引一點點開始。
提問:什麼是正排索引(forward index)?
回答:由key查詢實體的過程,是正排索引。
用戶表:t_user(uid, name, passwd, age, sex),由uid查詢整行的過程,就是正排索引查詢。
網頁庫:t_web_page(url, page_content),由url查詢整個網頁的過程,也是正排索引查詢。
網頁內容分詞後,page_content會對應一個分詞後的集合list
簡易的,正排索引可以理解為Map
提問:什麼是倒排索引(inverted index)?
回答:由item查詢key的過程,是倒排索引。
對於網頁搜索,倒排索引可以理解為Map
舉個例子,假設有3個網頁:
url1 -> “我愛北京”
url2 -> “我愛到家”
url3 -> “到家美好”
這是一個正排索引Map
分詞之後:
url1 -> {我,愛,北京}
url2 -> {我,愛,到家}
url3 -> {到家,美好}
這是一個分詞後的正排索引Map
分詞後倒排索引:
我 -> {url1, url2}
愛 -> {url1, url2}
北京 -> {url1}
到家 -> {url2, url3}
美好 -> {url3}
由檢索詞item快速找到包含這個查詢詞的網頁Map
正排索引和倒排索引是spider和build_index系統提前建立好的數據結構,為什麼要使用這兩種數據結構,是因為它能夠快速的實現“用戶網頁檢索”需求(業務需求決定架構實現)。
提問:搜索的過程是什麼樣的?
假設搜索詞是“我愛”,用戶會得到什麼網頁呢?
(1)分詞,“我愛”會分詞為{我,愛},時間複雜度為O(1)
(2)每個分詞後的item,從倒排索引查詢包含這個item的網頁list
我 -> {url1, url2}
愛 -> {url1, url2}
(3)求list
看似到這裡就結束了,其實不然,分詞和倒排查詢時間複雜度都是O(1),整個搜索的時間複雜度取決於“求list
字符型的url不利於存儲與計算,一般來說每個url會有一個數值型的url_id來標識,後文為了方便描述,list
list1和list2,求交集怎麼求?
方案一:for * for,土辦法,時間複雜度O(n*n)
每個搜索詞命中的網頁是很多的,O(n*n)的複雜度是明顯不能接受的。倒排索引是在創建之初可以進行排序預處理,問題轉化
成兩個有序的list求交集,就方便多了。
方案二:有序list求交集,拉鍊法
有序集合1{1,3,5,7,8,9}
有序集合2{2,3,4,5,6,7}
兩個指針指向首元素,比較元素的大小:
(1)如果相同,放入結果集,隨意移動一個指針
(2)否則,移動值較小的一個指針,直到隊尾
這種方法的好處是:
(1)集合中的元素最多被比較一次,時間複雜度為O(n)
(2)多個有序集合可以同時進行,這適用於多個分詞的item求url_id交集
這個方法就像一條拉鍊的兩邊齒輪,一一比對就像拉鍊,故稱為拉鍊法
方案三:分桶並行優化
數據量大時,url_id分桶水平切分+並行運算是一種常見的優化方法,如果能將list1
舉例:
有序集合1{1,3,5,7,8,9, 10,30,50,70,80,90}
有序集合2{2,3,4,5,6,7, 20,30,40,50,60,70}
求交集,先進行分桶拆分:
桶1的範圍為[1, 9]
桶2的範圍為[10, 100]
桶3的範圍為[101, max_int]
於是:
集合1就拆分成
集合a{1,3,5,7,8,9}
集合b{10,30,50,70,80,90}
集合c{}
集合2就拆分成
集合d{2,3,4,5,6,7}
集合e{20,30,40,50,60,70}
集合e{}
每個桶內的數據量大大降低了,並且每個桶內沒有重複元素,可以利用多線程並行計算:
桶1內的集合a和集合d的交集是x{3,5,7}
桶2內的集合b和集合e的交集是y{30, 50, 70}
桶3內的集合c和集合d的交集是z{}
最終,集合1和集合2的交集,是x與y與z的並集,即集合{3,5,7,30,50,70}
方案四:bitmap再次優化
數據進行了水平分桶拆分之後,每個桶內的數據一定處於一個範圍之內,如果集合符合這個特點,就可以使用bitmap來表示集合:
如上圖,假設set1{1,3,5,7,8,9}和set2{2,3,4,5,6,7}的所有元素都在桶值[1, 16]的範圍之內,可以用16個bit來描述這兩個集合,原集合中的元素x,在這個16bitmap中的第x個bit為1,此時兩個bitmap求交集,只需要將兩個bitmap進行“與”操作,結果集bitmap的3,5,7位是1,表明原集合的交集為{3,5,7}
水平分桶,bitmap優化之後,能極大提高求交集的效率,但時間複雜度仍舊是O(n)
bitmap需要大量連續空間,佔用內存較大
方案五:跳錶skiplist
有序鏈表集合求交集,跳錶是最常用的數據結構,它可以將有序集合求交集的複雜度由O(n)降至O(log(n))
集合1{1,2,3,4,20,21,22,23,50,60,70}
集合2{50,70}
要求交集,如果用拉鍊法,會發現1,2,3,4,20,21,22,23都要被無效遍歷一次,每個元素都要被比對,時間複雜度為O(n),能不能每次比對“跳過一些元素”呢?
跳錶就出現了:
集合1{1,2,3,4,20,21,22,23,50,60,70}建立跳錶時,一級只有{1,20,50}三個元素,二級與普通鏈表相同
集合2{50,70}由於元素較少,只建立了一級普通鏈表
如此這般,在實施“拉鍊”求交集的過程中,set1的指針能夠由1跳到20再跳到50,中間能夠跳過很多元素,無需進行一一比對,跳錶求交集的時間複雜度近似O(log(n)),這是搜索引擎中常見的算法。
五、總結
文字很多,有宏觀,有細節,對於大部分不是專門研究搜索引擎的同學,記住以下幾點即可:
(1)全網搜索引擎系統由spider, search&index, rank三個子系統構成
(2)站內搜索引擎與全網搜索引擎的差異在於,少了一個spider子系統
(3)spider和search&index系統是兩個工程系統,rank系統的優化卻需要長時間的調優和積累
(4)正排索引(forward index)是由網頁url_id快速找到分詞後網頁內容list
(5)倒排索引(inverted index)是由分詞item快速尋找包含這個分詞的網頁list
(6)用戶檢索的過程,是先分詞,再找到每個item對應的list
(7)有序集合求交集的方法有
a)二重for循環法,時間複雜度O(n*n)
b)拉鍊法,時間複雜度O(n)
c)水平分桶,多線程並行
d)bitmap,大大提高運算並行度,時間複雜度O(n)
e)跳錶,時間複雜度為O(log(n))
------------------------------------------------------------------------------
閱讀更多 程序員界的彭于晏 的文章