「轉」“搜索”的原理,架構,實現,實踐,面試不用再怕了

可能99%的同學不做搜索引擎,但99%的同學一定實現過檢索功能。搜索,檢索,這裡面到底包含哪些技術的東西,希望本文能夠給大家一些啟示。

全網搜索引擎架構與流程如何?

「轉」“搜索”的原理,架構,實現,實踐,面試不用再怕了


全網搜索引擎的宏觀架構如上圖,核心子系統主要分為三部分(粉色部分):

(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億帖子的搜索為例,其整體架構如下:

「轉」“搜索”的原理,架構,實現,實踐,面試不用再怕了


站內搜索引擎的宏觀架構如上圖,與全網搜索引擎的宏觀架構相比,差異只有寫入的地方:

(1)全網搜索需要spider要被動去抓取數據;

(2)站內搜索是內部系統生成的數據,例如“發佈系統”會將生成的帖子主動推給build_data系統;

畫外音:看似“很小”的差異,架構實現上難度卻差很多,全網搜索如何“實時”發現“全量”的網頁是非常困難的,而站內搜索容易實時得到全部數據。

對於spider、search&index、rank三個系統:

(1)spider和search&index是相對工程的系統;

(2)rank是和業務、策略緊密、算法相關的系統,搜索體驗的差異主要在此,而業務、策略的優化是需要時間積累的,這裡的啟示是:

  • Google的體驗比Baidu好,根本在於前者rank牛逼
  • 國內互聯網公司(例如360)短時間要搞一個體驗超越Baidu的搜索引擎,是很難的,真心需要時間的積累

前面的內容太宏觀,為了照顧大部分沒有做過搜索引擎的同學,數據結構與算法部分從正排索引、倒排索引一點點開始。

什麼是正排索引(forward index)?

簡言之,由key查詢實體的過程,使用正排索引。

例如,用戶表:

t_user(uid, name, passwd, age, sex)

由uid查詢整行的過程,就時正排索引查詢。

又例如,網頁庫:

t_web_page(url, page_content)

由url查詢整個網頁的過程,也是正排索引查詢。

網頁內容分詞後,page_content會對應一個分詞後的集合list<item>。/<item>

簡易的,正排索引可以理解為:

Map>

能夠由網頁url快速找到內容的一個數據結構。

畫外音:時間複雜度可以認為是O(1)。

什麼是倒排索引(inverted index)?

與正排索引相反,由item查詢key的過程,使用倒排索引。

對於網頁搜索,倒排索引可以理解為:

Map<item>>/<item>

能夠由查詢詞快速找到包含這個查詢詞的網頁的數據結構。

畫外音:時間複雜度也是O(1)。

舉個例子,假設有3個網頁:

url1 -> “我愛北京”

url2 -> “我愛到家”

url3 -> “到家美好”

這是一個正排索引:

Map

分詞之後:

url1 -> {我,愛,北京}

url2 -> {我,愛,到家}

url3 -> {到家,美好}

這是一個分詞後的正排索引:

Map>。

分詞後倒排索引:

我 -> {url1, url2}

愛 -> {url1, url2}

北京 -> {url1}

到家 -> {url2, url3}

美好 -> {url3}

由檢索詞item快速找到包含這個查詢詞的網頁Map<item>>就是

倒排索引。/<item>

畫外音:明白了吧,詞到url的過程,是倒排索引。

正排索引和倒排索引是spider和build_index系統提前建立好的數據結構,為什麼要使用這兩種數據結構,是因為它能夠快速的實現“用戶網頁檢索”需求。

畫外音,業務需求決定架構實現,查詢起來都很快。

檢索的過程是什麼樣的?

假設搜索詞是“我愛”:

(1)分詞,“我愛”會分詞為{我,愛},時間複雜度為O(1);

(2)每個分詞後的item,從倒排索引查詢包含這個item的網頁list,時間複雜度也是O(1):

我 -> {url1, url2}

愛 -> {url1, url2}

(3)求list

的交集,就是符合所有查詢詞的結果網頁,對於這個例子,{url1, url2}就是最終的查詢結果;

畫外音:檢索的過程也很簡單:分詞,查倒排索引,求結果集交集。

就結束了嗎?其實不然,分詞和倒排查詢時間複雜度都是O(1),整個搜索的時間複雜度取決於“求list的交集”,問題轉化為了求兩個集合交集。

字符型的url不利於存儲與計算,一般來說每個url會有一個數值型的url_id來標識,後文為了方便描述,list統一用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和list2分成若干個桶區間,每個區間利用多線程並行求交集,各個線程結果集的並集,作為最終的結果集,能夠大大的減少執行時間。

舉例:

有序集合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需要大量連續空間,佔用內存較大。

畫外音: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<item>的過程;/<item>

(5)倒排索引(inverted index)是由分詞item快速尋找包含這個分詞的網頁list的過程;

(6)用戶檢索的過程,是先分詞,再找到每個item對應的list,最後進行集合求交集的過程;

(7)有序集合求交集的方法有:

  • 二重for循環法,時間複雜度O(n*n)
  • 拉鍊法,時間複雜度O(n)
  • 水平分桶,多線程並行
  • bitmap,大大提高運算並行度,時間複雜度O(n)
  • 跳錶,時間複雜度為O(log(n))

畫外音:面試應該夠用了。

大部分工程師未必接觸過“搜索內核”,但互聯網業務,基本會涉及“檢索”功能。還是以58同城的帖子業務場景為例,帖子的標題,帖子的內容有很強的用戶檢索需求,在業務、流量、併發量逐步遞增的各個階段,應該如何實現檢索需求呢?

原始階段-LIKE

創業階段,常常用這種方法來快速實現。

數據在數據庫中可能是這麼存儲的:

t_tiezi(tid, title, content)

滿足標題、內容的檢索需求可以通過LIKE實現:

select tid from t_tiezi where content like ‘%天通苑%’

這種方式確實能夠快速滿足業務需求,存在的問題也顯而易見:

(1)效率低,每次需要全表掃描,計算量大,併發高時cpu容易100%;

(2)不支持分詞;

初級階段-全文索引

如何快速提高效率,支持分詞,並對原有系統架構影響儘可能小呢,第一時間想到的是建立全文索引:

alter table t_tiezi add fulltext(title,content)

使用match和against實現索引字段上的查詢需求。

全文索引能夠快速實現業務上分詞的需求,並且快速提升性能(分詞後倒排,至少不要全表掃描了),但也存在一些問題:

(1)只適用於MyISAM;

(2)由於全文索引利用的是數據庫特性,搜索需求和普通CURD需求耦合在數據庫中:檢索需求併發大時,可能影響CURD的請求;CURD併發大時,檢索會非常的慢;

(3)數據量達到百萬級別,性能還是會顯著降低,查詢返回時間很長,業務難以接受;

(4)比較難水平擴展;

中級階段-開源外置索引

為了解決全文索的侷限性,當數據量增加到大幾百萬,千萬級別時,就要考慮外置索引了。外置索引的核心思路是:索引數據與原始數據分離,前者滿足搜索需求,後者滿足CURD需求,通過一定的機制(雙寫,通知,定期重建)來保證數據的一致性。

原始數據可以繼續使用Mysql來存儲,外置索引如何實施?Solr,Lucene,ES都是常見的開源方案。其中,ES(ElasticSearch)是目前最為流行的。

Lucene雖好,潛在的不足是:

(1)Lucene只是一個庫,需要自己做服務,自己實現高可用/可擴展/負載均衡等複雜特性;

(2)Lucene只支持Java,如果要支持其他語言,必須得自己做服務;

(3)Lucene不友好,這是很致命的,非常複雜,使用者往往需要深入瞭解搜索的知識來理解它的工作原理,為了屏蔽其複雜性,還是得自己做服務;

為了改善Lucene的各項不足,解決方案都是“封裝一個接口友好的服務,屏蔽底層複雜性”,於是有了ES:

(1)ES是一個以Lucene為內核來實現搜索功能,提供REStful接口的服務;

(2)ES能夠支持很大數據量的信息存儲,支持很高併發的搜索請求;

(3)ES支持集群,向使用者屏蔽高可用/可擴展/負載均衡等複雜特性;

目前,快狗打車使用ES作為核心的搜索服務,實現業務上的各類搜索需求,其中:

(1)數據量最大的“接口耗時數據收集”需求,數據量大概在10億左右;

(2)併發量最大的“經緯度,地理位置搜索”需求,線上平均併發量大概在2000左右,壓測數據併發量在8000左右;

所以,ES完全能滿足10億數據量,5k吞吐量的常見搜索業務需求。

高級階段-自研搜索引擎

當數據量進一步增加,達到10億、100億數據量;併發量也進一步增加,達到每秒10萬吞吐量;業務個性也逐步增加的時候,就需要自研搜索引擎了,定製化實現搜索內核了。

到了定製化自研搜索引擎的階段,超大數據量、超高併發量為設計重點,為了達到“無限容量、無限併發”的需求,架構設計需要重點考慮“擴展性”,力爭做到:增加機器就能擴容(數據量+併發量)。

58同城的自研搜索引擎E-search初步架構圖如下:

「轉」“搜索”的原理,架構,實現,實踐,面試不用再怕了


(1)上層proxy(粉色)是接入集群,為對外門戶,接受搜索請求,其無狀態性能夠保證增加機器就能擴充proxy集群性能;

(2)中層merger(淺藍色)是邏輯集群,主要用於實現搜索合併,以及打分排序,業務相關的rank就在這一層實現,其無狀態性也能夠保證增加機器就能擴充merger集群性能;

(3)底層searcher(暗紅色大框)是檢索集群,服務和索引數據部署在同一臺機器上,服務啟動時可以加載索引數據到內存,請求訪問時從內存中load數據,訪問速度很快:

  • 為了滿足數據容量的擴展性,索引數據進行了水平切分,增加切分份數,就能夠無限擴展性能,如上圖searcher分為了4組
  • 為了滿足一份數據的性能擴展性,同一份數據進行了冗餘,理論上做到增加機器就無限擴展性能,如上圖每組searcher又冗餘了2份


如此設計,真正做到做到增加機器就能承載更多的數據量,響應更高的併發量。

簡單小結一下:

為了滿足搜索業務的需求,隨著數據量和併發量的增長,搜索架構一般會經歷這麼幾個階段:

(1)原始階段-LIKE;

(2)初級階段-全文索引;

(3)中級階段-開源外置索引;

(4)高級階段-自研搜索引擎;

最後一個高級話題,關於搜索的實時性

百度為何能實時檢索出15分鐘之前新出的新聞?58同城為何能實時檢索出1秒鐘之前發佈的帖子?

實時搜索引擎系統架構的要點是什麼?

大數據量、高併發量情況下的搜索引擎為了保證實時性,架構設計上的兩個要點:

(1)索引分級;

(2)dump&merge;

首先,在數據量非常大的情況下,為了保證倒排索引的高效檢索效率,任何對數據的更新,並不會實時修改索引。

畫外音:因為,一旦產生碎片,會大大降低檢索效率。

既然索引數據不能實時修改,如何保證最新的網頁能夠被索引到呢?

索引分級,分為全量庫、日增量庫、小時增量庫。

「轉」“搜索”的原理,架構,實現,實踐,面試不用再怕了


如上圖所述:

(1)300億數據在全量索引庫中;

(2)1000萬1天內修改過的數據在天庫中;

(3)50萬1小時內修改過的數據在小時庫中;

有修改請求發生時,只會操作最低級別的索引,例如小時庫。

「轉」“搜索”的原理,架構,實現,實踐,面試不用再怕了


有查詢請求發生時,會同時查詢各個級別的索引,將結果合併,得到最新的數據:

(1)全量庫是緊密存儲的索引,無碎片,速度快;

(2)天庫是緊密存儲,速度快;

(3)小時庫數據量小,速度也快;

分級索引能夠保證實時性,那麼,新的問題來了,小時庫數據何時反映到天庫中,天庫中的數據何時反映到全量庫中呢?

dump&merge,索引的導出與合併,由這兩個異步的工具完成:

「轉」“搜索”的原理,架構,實現,實踐,面試不用再怕了


dumper:將在線的數據導出。

merger:將離線的數據合併到高一級別的索引中去。

小時庫,一小時一次,合併到天庫中去;

天庫,一天一次,合併到全量庫中去;

這樣就保證了小時庫和天庫的數據量都不會特別大;

如果數據量和併發量更大,還能增加星期庫,月庫來緩衝。

簡單小結一下:

超大數據量,超高併發量,實時搜索引擎的兩個架構要點:

(1)索引分級;

(2)dump&merge;

關於“搜索”與“檢索”,GET到新技能了嗎?




分享到:


相關文章: