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

全網(wǎng)搜索引擎架構(gòu)與流程如何?

全網(wǎng)搜索引擎的宏觀架構(gòu)如上圖，核心子系統(tǒng)主要分為三部分(粉色部分)：

(1)spider爬蟲系統(tǒng);

(2)search&index建立索引與查詢索引系統(tǒng)，這個系統(tǒng)又主要分為兩部分：

• 一部分用于生成索引數(shù)據(jù)build_index
• 一部分用于查詢索引數(shù)據(jù)search_index

(3)rank打分排序系統(tǒng);

核心數(shù)據(jù)主要分為兩部分(紫色部分)：

• web網(wǎng)頁庫;
• index索引數(shù)據(jù);

全網(wǎng)搜索引擎的業(yè)務(wù)特點決定了，這是一個“寫入”和“檢索”分離的系統(tǒng)。

寫入是如何實施的?

系統(tǒng)組成：由spider與search&index兩個系統(tǒng)完成。

• 輸入：站長們生成的互聯(lián)網(wǎng)網(wǎng)頁。
• 輸出：正排倒排索引數(shù)據(jù)。

流程：如架構(gòu)圖中的1，2，3，4：

• (1)spider把互聯(lián)網(wǎng)網(wǎng)頁抓過來;
• (2)spider把互聯(lián)網(wǎng)網(wǎng)頁存儲到網(wǎng)頁庫中(這個對存儲的要求很高，要存儲幾乎整個“萬維網(wǎng)”的鏡像);
• (3)build_index從網(wǎng)頁庫中讀取數(shù)據(jù)，完成分詞;
• (4)build_index生成倒排索引;

檢索是如何實施的?

系統(tǒng)組成：由search&index與rank兩個系統(tǒng)完成。

輸入：用戶的搜索詞。

輸出：排好序的第一頁檢索結(jié)果。

流程：如架構(gòu)圖中的a，b，c，d：

• (a)search_index獲得用戶的搜索詞，完成分詞;
• (b)search_index查詢倒排索引，獲得“字符匹配”網(wǎng)頁，這是初篩的結(jié)果;
• (c)rank對初篩的結(jié)果進行打分排序;

站內(nèi)搜索引擎架構(gòu)與流程如何?

做全網(wǎng)搜索的公司畢竟是少數(shù)，絕大部分公司要實現(xiàn)的其實只是一個站內(nèi)搜索，以58同城100億帖子的搜索為例，其整體架構(gòu)如下：

站內(nèi)搜索引擎的宏觀架構(gòu)如上圖，與全網(wǎng)搜索引擎的宏觀架構(gòu)相比，差異只有寫入的地方：

• 全網(wǎng)搜索需要spider要被動去抓取數(shù)據(jù);
• 站內(nèi)搜索是內(nèi)部系統(tǒng)生成的數(shù)據(jù)，例如“發(fā)布系統(tǒng)”會將生成的帖子主動推給build_data系統(tǒng);

畫外音：看似“很小”的差異，架構(gòu)實現(xiàn)上難度卻差很多，全網(wǎng)搜索如何“實時”發(fā)現(xiàn)“全量”的網(wǎng)頁是非常困難的，而站內(nèi)搜索容易實時得到全部數(shù)據(jù)。

• 對于spider、search&index、rank三個系統(tǒng)：
• spider和search&index是相對工程的系統(tǒng);

rank是和業(yè)務(wù)、策略緊密、算法相關(guān)的系統(tǒng)，搜索體驗的差異主要在此，而業(yè)務(wù)、策略的優(yōu)化是需要時間積累的，這里的啟示是：

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

前面的內(nèi)容太宏觀，為了照顧大部分沒有做過搜索引擎的同學，數(shù)據(jù)結(jié)構(gòu)與算法部分從正排索引、倒排索引一點點開始。

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

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

例如，用戶表：

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

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

又例如，網(wǎng)頁庫：

t_web_page(url, page_content) 

由url查詢整個網(wǎng)頁的過程，也是正排索引查詢。

網(wǎng)頁內(nèi)容分詞后，page_content會對應(yīng)一個分詞后的集合list。

簡易的，正排索引可以理解為：

Map<url, list<item>> 

能夠由網(wǎng)頁url快速找到內(nèi)容的一個數(shù)據(jù)結(jié)構(gòu)。

畫外音：時間復(fù)雜度可以認為是O(1)。

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

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

對于網(wǎng)頁搜索，倒排索引可以理解為：

Map<item, list<url>> 

能夠由查詢詞快速找到包含這個查詢詞的網(wǎng)頁的數(shù)據(jù)結(jié)構(gòu)。

畫外音：時間復(fù)雜度也是O(1)。

舉個例子，假設(shè)有3個網(wǎng)頁：

url1 -> “我愛北京” 
url2 -> “我愛到家” 
url3 -> “到家美好” 

這是一個正排索引：

Map<url, page_content>

分詞之后：

url1 -> {我，愛，北京} 
url2 -> {我，愛，到家} 
url3 -> {到家，美好} 

這是一個分詞后的正排索引：

Map<url, list<item>>

分詞后倒排索引：

我 -> {url1, url2} 
愛 -> {url1, url2} 
北京 -> {url1} 
到家 -> {url2, url3} 
美好 -> {url3} 

由檢索詞item快速找到包含這個查詢詞的網(wǎng)頁Map>就是倒排索引。

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

正排索引和倒排索引是spider和build_index系統(tǒng)提前建立好的數(shù)據(jù)結(jié)構(gòu)，為什么要使用這兩種數(shù)據(jù)結(jié)構(gòu)，是因為它能夠快速的實現(xiàn)“用戶網(wǎng)頁檢索”需求。

畫外音，業(yè)務(wù)需求決定架構(gòu)實現(xiàn)，查詢起來都很快。

檢索的過程是什么樣的?

假設(shè)搜索詞是“我愛”：

• 分詞，“我愛”會分詞為{我，愛}，時間復(fù)雜度為O(1);
• 每個分詞后的item，從倒排索引查詢包含這個item的網(wǎng)頁list，時間復(fù)雜度也是O(1)：
• 求list的交集，就是符合所有查詢詞的結(jié)果網(wǎng)頁，對于這個例子，{url1, url2}就是最終的查詢結(jié)果;

我 -> {url1, url2} 
愛 -> {url1, url2} 

畫外音：檢索的過程也很簡單：分詞，查倒排索引，求結(jié)果集交集。

就結(jié)束了嗎?其實不然，分詞和倒排查詢時間復(fù)雜度都是O(1)，整個搜索的時間復(fù)雜度取決于“求list的交集”，問題轉(zhuǎn)化為了求兩個集合交集。

字符型的url不利于存儲與計算，一般來說每個url會有一個數(shù)值型的url_id來標識，后文為了方便描述，list統(tǒng)一用list替代。

list1和list2，求交集怎么求?

(1) 方案一：for * for，土辦法，時間復(fù)雜度O(n*n)

每個搜索詞命中的網(wǎng)頁是很多的，O(n*n)的復(fù)雜度是明顯不能接受的。倒排索引是在創(chuàng)建之初可以進行排序預(yù)處理，問題轉(zhuǎn)化成兩個有序的list求交集，就方便多了。

畫外音：比較笨的方法。

(2) 方案二：有序list求交集，拉鏈法

有序集合1{1,3,5,7,8,9} 
有序集合2{2,3,4,5,6,7} 

兩個指針指向首元素，比較元素的大?。?/p>

• 如果相同，放入結(jié)果集，隨意移動一個指針;
• 否則，移動值較小的一個指針，直到隊尾;

這種方法的好處是：

• 集合中的元素最多被比較一次，時間復(fù)雜度為O(n);
• 多個有序集合可以同時進行，這適用于多個分詞的item求url_id交集;

這個方法就像一條拉鏈的兩邊齒輪，一一比對就像拉鏈，故稱為拉鏈法;

畫外音：倒排索引是提前初始化的，可以利用“有序”這個特性。

(3) 方案三：分桶并行優(yōu)化

數(shù)據(jù)量大時，url_id分桶水平切分+并行運算是一種常見的優(yōu)化方法，如果能將list1和list2分成若干個桶區(qū)間，每個區(qū)間利用多線程并行求交集，各個線程結(jié)果集的并集，作為最終的結(jié)果集，能夠大大的減少執(zhí)行時間。

舉例：

有序集合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{} 

每個桶內(nèi)的數(shù)據(jù)量大大降低了，并且每個桶內(nèi)沒有重復(fù)元素，可以利用多線程并行計算：

桶1內(nèi)的集合a和集合d的交集是x{3,5,7} 
桶2內(nèi)的集合b和集合e的交集是y{30, 50, 70} 
桶3內(nèi)的集合c和集合d的交集是z{} 

最終，集合1和集合2的交集，是x與y與z的并集，即集合{3,5,7,30,50,70}。

畫外音：多線程、水平切分都是常見的優(yōu)化手段。

(4)方案四：bitmap再次優(yōu)化

數(shù)據(jù)進行了水平分桶拆分之后，每個桶內(nèi)的數(shù)據(jù)一定處于一個范圍之內(nèi)，如果集合符合這個特點，就可以使用bitmap來表示集合：

如上圖，假設(shè)set1{1,3,5,7,8,9}和set2{2,3,4,5,6,7}的所有元素都在桶值[1, 16]的范圍之內(nèi)，可以用16個bit來描述這兩個集合，原集合中的元素x，在這個16bitmap中的第x個bit為1，此時兩個bitmap求交集，只需要將兩個bitmap進行“與”操作，結(jié)果集bitmap的3，5，7位是1，表明原集合的交集為{3,5,7}。

水平分桶，bitmap優(yōu)化之后，能極大提高求交集的效率，但時間復(fù)雜度仍舊是O(n)。bitmap需要大量連續(xù)空間，占用內(nèi)存較大。

畫外音：bitmap能夠表示集合，用它求集合交集速度非?？?。

(5)方案五：跳表skiplist

有序鏈表集合求交集，跳表是最常用的數(shù)據(jù)結(jié)構(gòu)，它可以將有序集合求交集的復(fù)雜度由O(n)降至接近O(log(n))。

集合1{1,2,3,4,20,21,22,23,50,60,70}

集合2{50,70}

要求交集，如果用拉鏈法，會發(fā)現(xiàn)1,2,3,4,20,21,22,23都要被無效遍歷一次，每個元素都要被比對，時間復(fù)雜度為O(n)，能不能每次比對“跳過一些元素”呢?

跳表就出現(xiàn)了：

集合1{1,2,3,4,20,21,22,23,50,60,70}建立跳表時，一級只有{1,20,50}三個元素，二級與普通鏈表相同。

集合2{50,70}由于元素較少，只建立了一級普通鏈表。

如此這般，在實施“拉鏈”求交集的過程中，set1的指針能夠由1跳到20再跳到50，中間能夠跳過很多元素，無需進行一一比對，跳表求交集的時間復(fù)雜度近似O(log(n))，這是搜索引擎中常見的算法。

簡單小結(jié)一下：

(1)全網(wǎng)搜索引擎系統(tǒng)由spider, search&index, rank三個子系統(tǒng)構(gòu)成;

(2)站內(nèi)搜索引擎與全網(wǎng)搜索引擎的差異在于，少了一個spider子系統(tǒng);

(3)spider和search&index系統(tǒng)是兩個工程系統(tǒng)，rank系統(tǒng)的優(yōu)化卻需要長時間的調(diào)優(yōu)和積累;

(4)正排索引(forward index)是由網(wǎng)頁url_id快速找到分詞后網(wǎng)頁內(nèi)容list的過程;

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

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

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

• 二重for循環(huán)法，時間復(fù)雜度O(n*n)
• 拉鏈法，時間復(fù)雜度O(n)
• 水平分桶，多線程并行
• bitmap，大大提高運算并行度，時間復(fù)雜度O(n)
• 跳表，時間復(fù)雜度為O(log(n))

畫外音：面試應(yīng)該夠用了。

大部分工程師未必接觸過“搜索內(nèi)核”，但互聯(lián)網(wǎng)業(yè)務(wù)，基本會涉及“檢索”功能。還是以58同城的帖子業(yè)務(wù)場景為例，帖子的標題，帖子的內(nèi)容有很強的用戶檢索需求，在業(yè)務(wù)、流量、并發(fā)量逐步遞增的各個階段，應(yīng)該如何實現(xiàn)檢索需求呢?

原始階段-LIKE

創(chuàng)業(yè)階段，常常用這種方法來快速實現(xiàn)。

數(shù)據(jù)在數(shù)據(jù)庫中可能是這么存儲的：

t_tiezi(tid, title, content) 

滿足標題、內(nèi)容的檢索需求可以通過LIKE實現(xiàn)：

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

這種方式確實能夠快速滿足業(yè)務(wù)需求，存在的問題也顯而易見：

• 效率低，每次需要全表掃描，計算量大，并發(fā)高時cpu容易100%;
• 不支持分詞;

初級階段-全文索引

如何快速提高效率，支持分詞，并對原有系統(tǒng)架構(gòu)影響盡可能小呢，第一時間想到的是建立全文索引：

alter table t_tiezi add fulltext(title,content) 

使用match和against實現(xiàn)索引字段上的查詢需求。

全文索引能夠快速實現(xiàn)業(yè)務(wù)上分詞的需求，并且快速提升性能(分詞后倒排，至少不要全表掃描了)，但也存在一些問題：

• 只適用于MyISAM;
• 由于全文索引利用的是數(shù)據(jù)庫特性，搜索需求和普通CURD需求耦合在數(shù)據(jù)庫中：檢索需求并發(fā)大時，可能影響CURD的請求;CURD并發(fā)大時，檢索會非常的慢;
• 數(shù)據(jù)量達到百萬級別，性能還是會顯著降低，查詢返回時間很長，業(yè)務(wù)難以接受;
• 比較難水平擴展;

中級階段-開源外置索引

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

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

Lucene雖好，潛在的不足是：

• Lucene只是一個庫，需要自己做服務(wù)，自己實現(xiàn)高可用/可擴展/負載均衡等復(fù)雜特性;
• Lucene只支持Java，如果要支持其他語言，必須得自己做服務(wù);
• Lucene不友好，這是很致命的，非常復(fù)雜，使用者往往需要深入了解搜索的知識來理解它的工作原理，為了屏蔽其復(fù)雜性，還是得自己做服務(wù);

為了改善Lucene的各項不足，解決方案都是“封裝一個接口友好的服務(wù)，屏蔽底層復(fù)雜性”，于是有了ES：

• ES是一個以Lucene為內(nèi)核來實現(xiàn)搜索功能，提供REStful接口的服務(wù);
• ES能夠支持很大數(shù)據(jù)量的信息存儲，支持很高并發(fā)的搜索請求;
• ES支持集群，向使用者屏蔽高可用/可擴展/負載均衡等復(fù)雜特性;

目前，快狗打車使用ES作為核心的搜索服務(wù)，實現(xiàn)業(yè)務(wù)上的各類搜索需求，其中：

• 數(shù)據(jù)量最大的“接口耗時數(shù)據(jù)收集”需求，數(shù)據(jù)量大概在10億左右;
• 并發(fā)量最大的“經(jīng)緯度，地理位置搜索”需求，線上平均并發(fā)量大概在2000左右，壓測數(shù)據(jù)并發(fā)量在8000左右;

所以，ES完全能滿足10億數(shù)據(jù)量，5k吞吐量的常見搜索業(yè)務(wù)需求。

高級階段-自研搜索引擎

當數(shù)據(jù)量進一步增加，達到10億、100億數(shù)據(jù)量;并發(fā)量也進一步增加，達到每秒10萬吞吐量;業(yè)務(wù)個性也逐步增加的時候，就需要自研搜索引擎了，定制化實現(xiàn)搜索內(nèi)核了。

到了定制化自研搜索引擎的階段，超大數(shù)據(jù)量、超高并發(fā)量為設(shè)計重點，為了達到“無限容量、無限并發(fā)”的需求，架構(gòu)設(shè)計需要重點考慮“擴展性”，力爭做到：增加機器就能擴容(數(shù)據(jù)量+并發(fā)量)。

58同城的自研搜索引擎E-search初步架構(gòu)圖如下：

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

(2) 中層merger(淺藍色)是邏輯集群，主要用于實現(xiàn)搜索合并，以及打分排序，業(yè)務(wù)相關(guān)的rank就在這一層實現(xiàn)，其無狀態(tài)性也能夠保證增加機器就能擴充merger集群性能;

(3) 底層searcher(暗紅色大框)是檢索集群，服務(wù)和索引數(shù)據(jù)部署在同一臺機器上，服務(wù)啟動時可以加載索引數(shù)據(jù)到內(nèi)存，請求訪問時從內(nèi)存中l(wèi)oad數(shù)據(jù)，訪問速度很快：

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

如此設(shè)計，真正做到做到增加機器就能承載更多的數(shù)據(jù)量，響應(yīng)更高的并發(fā)量。

簡單小結(jié)一下：

為了滿足搜索業(yè)務(wù)的需求，隨著數(shù)據(jù)量和并發(fā)量的增長，搜索架構(gòu)一般會經(jīng)歷這么幾個階段：

• 原始階段-LIKE;
• 初級階段-全文索引;
• 中級階段-開源外置索引;
• 高級階段-自研搜索引擎;

最后一個高級話題，關(guān)于搜索的實時性：百度為何能實時檢索出15分鐘之前新出的新聞?58同城為何能實時檢索出1秒鐘之前發(fā)布的帖子?

實時搜索引擎系統(tǒng)架構(gòu)的要點是什么?

大數(shù)據(jù)量、高并發(fā)量情況下的搜索引擎為了保證實時性，架構(gòu)設(shè)計上的兩個要點：

• 索引分級;
• dump&merge;

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

畫外音：因為，一旦產(chǎn)生碎片，會大大降低檢索效率。

既然索引數(shù)據(jù)不能實時修改，如何保證最新的網(wǎng)頁能夠被索引到呢?

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

如上圖所述：

• 300億數(shù)據(jù)在全量索引庫中;
• 1000萬1天內(nèi)修改過的數(shù)據(jù)在天庫中;
• 50萬1小時內(nèi)修改過的數(shù)據(jù)在小時庫中;

當有修改請求發(fā)生時，只會操作最低級別的索引，例如小時庫。

當有查詢請求發(fā)生時，會同時查詢各個級別的索引，將結(jié)果合并，得到最新的數(shù)據(jù)：

• 全量庫是緊密存儲的索引，無碎片，速度快;
• 天庫是緊密存儲，速度快;
• 小時庫數(shù)據(jù)量小，速度也快;

分級索引能夠保證實時性，那么，新的問題來了，小時庫數(shù)據(jù)何時反映到天庫中，天庫中的數(shù)據(jù)何時反映到全量庫中呢?

dump&merge，索引的導出與合并，由這兩個異步的工具完成：

• dumper：將在線的數(shù)據(jù)導出。
• merger：將離線的數(shù)據(jù)合并到高一級別的索引中去。

小時庫，一小時一次，合并到天庫中去;

天庫，一天一次，合并到全量庫中去;

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

如果數(shù)據(jù)量和并發(fā)量更大，還能增加星期庫，月庫來緩沖。

簡單小結(jié)一下：

超大數(shù)據(jù)量，超高并發(fā)量，實時搜索引擎的兩個架構(gòu)要點：

• 索引分級;
• dump&merge;

關(guān)于“搜索”與“檢索”，GET到新技能了嗎?

【本文為51CTO專欄作者“58沈劍”原創(chuàng)稿件，轉(zhuǎn)載請聯(lián)系原作者】

戳這里，看該作者更多好文