可能99%的同學(xué)不做搜索引擎，但99%的同學(xué)一定實(shí)現(xiàn)過(guò)檢索功能。搜索，檢索，這里面到底包含哪些技術(shù)，希望本文能夠給大家一些啟示。需求一：我想做一個(gè)全網(wǎng)搜索引擎，不復(fù)雜，和百度類似就行，兩個(gè)月能上線嗎？
全網(wǎng)搜索引擎架構(gòu)與流程如何？
全網(wǎng)搜索引擎的宏觀架構(gòu)如上圖，核心子系統(tǒng)主要分為三部分（粉色部分）：（1）spider爬蟲(chóng)系統(tǒng)；（2）search&index建立索引與查詢索引系統(tǒng)，這個(gè)系統(tǒng)又主要分為兩部分： - 一部分用于生成索引數(shù)據(jù)build_index - 一部分用于查詢索引數(shù)據(jù)search_index核心數(shù)據(jù)主要分為兩部分（紫色部分）：全網(wǎng)搜索引擎的業(yè)務(wù)特點(diǎn)決定了，這是一個(gè)“寫(xiě)入”和“檢索”分離的系統(tǒng)。系統(tǒng)組成：由spider與search&index兩個(gè)系統(tǒng)完成。輸入：站長(zhǎng)們生成的互聯(lián)網(wǎng)網(wǎng)頁(yè)。（1）spider把互聯(lián)網(wǎng)網(wǎng)頁(yè)抓過(guò)來(lái)；（2）spider把互聯(lián)網(wǎng)網(wǎng)頁(yè)存儲(chǔ)到網(wǎng)頁(yè)庫(kù)中（這個(gè)對(duì)存儲(chǔ)的要求很高，要存儲(chǔ)幾乎整個(gè)“萬(wàn)維網(wǎng)”的鏡像）；（3）build_index從網(wǎng)頁(yè)庫(kù)中讀取數(shù)據(jù)，完成分詞；系統(tǒng)組成：由search&index與rank兩個(gè)系統(tǒng)完成。（a）search_index獲得用戶的搜索詞，完成分詞；（b）search_index查詢倒排索引，獲得“字符匹配”網(wǎng)頁(yè)，這是初篩的結(jié)果；（c）rank對(duì)初篩的結(jié)果進(jìn)行打分排序；（d）rank對(duì)排序后的第一頁(yè)結(jié)果返回；做全網(wǎng)搜索的公司畢竟是少數(shù)，絕大部分公司要實(shí)現(xiàn)的其實(shí)只是一個(gè)站內(nèi)搜索，以同城100億帖子的搜索為例，其整體架構(gòu)如下：站內(nèi)搜索引擎的宏觀架構(gòu)如上圖，與全網(wǎng)搜索引擎的宏觀架構(gòu)相比，差異只有寫(xiě)入的地方：（1）全網(wǎng)搜索需要spider要被動(dòng)去抓取數(shù)據(jù)；（2）站內(nèi)搜索是內(nèi)部系統(tǒng)生成的數(shù)據(jù)，例如“發(fā)布系統(tǒng)”會(huì)將生成的帖子主動(dòng)推給build_data系統(tǒng)；畫(huà)外音：看似“很小”的差異，架構(gòu)實(shí)現(xiàn)上難度卻差很多，全網(wǎng)搜索如何“實(shí)時(shí)”發(fā)現(xiàn)“全量”的網(wǎng)頁(yè)是非常困難的，而站內(nèi)搜索容易實(shí)時(shí)得到全部數(shù)據(jù)。對(duì)于spider、search&index、rank三個(gè)系統(tǒng)：（1）spider和search&index是工程系統(tǒng)；（2）rank是和業(yè)務(wù)、策略緊密、算法相關(guān)的系統(tǒng)，搜索體驗(yàn)的差異主要在此，而業(yè)務(wù)、策略的優(yōu)化是需要時(shí)間積累的，這里的啟示是： - Google的體驗(yàn)比Baidu好，根本在于前者rank牛逼 - 國(guó)內(nèi)互聯(lián)網(wǎng)公司（例如360）短時(shí)間要搞一個(gè)體驗(yàn)超越Baidu的搜索引擎，是很難的，真心需要時(shí)間的積累前面的內(nèi)容太宏觀，為了照顧大部分沒(méi)有做過(guò)搜索引擎的同學(xué)，數(shù)據(jù)結(jié)構(gòu)與算法部分從正排索引、倒排索引一點(diǎn)點(diǎn)開(kāi)始。簡(jiǎn)言之，由key查詢實(shí)體的過(guò)程，使用正排索引。t_user(uid, name, passwd, age, sex)由uid查詢整行的過(guò)程，就是正排索引查詢。t_web_page(url, page_content)由url查詢整個(gè)網(wǎng)頁(yè)的過(guò)程，也是正排索引查詢。網(wǎng)頁(yè)內(nèi)容分詞后，page_content會(huì)對(duì)應(yīng)一個(gè)分詞后的集合list<item>。能夠由網(wǎng)頁(yè)url快速找到內(nèi)容的一個(gè)數(shù)據(jù)結(jié)構(gòu)。畫(huà)外音：時(shí)間復(fù)雜度可以認(rèn)為是O(1)。與正排索引相反，由item查詢key的過(guò)程，使用倒排索引。對(duì)于網(wǎng)頁(yè)搜索，倒排索引可以理解為：能夠由查詢?cè)~快速找到包含這個(gè)查詢?cè)~的網(wǎng)頁(yè)的數(shù)據(jù)結(jié)構(gòu)。畫(huà)外音：時(shí)間復(fù)雜度也是O(1)。舉個(gè)例子，假設(shè)有3個(gè)網(wǎng)頁(yè)：由檢索詞item快速找到包含這個(gè)查詢?cè)~的網(wǎng)頁(yè)Map<item, list<url>>就是倒排索引。畫(huà)外音：明白了吧，詞到url的過(guò)程，是倒排索引。正排索引和倒排索引是spider和build_index系統(tǒng)提前建立好的數(shù)據(jù)結(jié)構(gòu)，為什么要使用這兩種數(shù)據(jù)結(jié)構(gòu)，是因?yàn)樗軌蚩焖俚膶?shí)現(xiàn)“用戶網(wǎng)頁(yè)檢索”需求。畫(huà)外音，業(yè)務(wù)需求決定架構(gòu)實(shí)現(xiàn)，查詢起來(lái)都很快。（1）分詞，“我愛(ài)”會(huì)分詞為{我，愛(ài)}，時(shí)間復(fù)雜度為O(1)；（2）每個(gè)分詞后的item，從倒排索引查詢包含這個(gè)item的網(wǎng)頁(yè)list<url>，時(shí)間復(fù)雜度也是O(1)：（3）求list<url>的交集，就是符合所有查詢?cè)~的結(jié)果網(wǎng)頁(yè)，對(duì)于這個(gè)例子，{url1, url2}就是最終的查詢結(jié)果；畫(huà)外音：檢索的過(guò)程也很簡(jiǎn)單：分詞，查倒排索引，求結(jié)果集交集。就結(jié)束了嗎？其實(shí)不然，分詞和倒排查詢時(shí)間復(fù)雜度都是O(1)，整個(gè)搜索的時(shí)間復(fù)雜度取決于“求list<url>的交集”，問(wèn)題轉(zhuǎn)化為了求兩個(gè)集合交集。字符型的url不利于存儲(chǔ)與計(jì)算，一般來(lái)說(shuō)每個(gè)url會(huì)有一個(gè)數(shù)值型的url_id來(lái)標(biāo)識(shí)，后文為了方便描述，list<url>統(tǒng)一用list<url_id>替代。方案一：for * for，土辦法，時(shí)間復(fù)雜度O(n*n)每個(gè)搜索詞命中的網(wǎng)頁(yè)是很多的，O(n*n)的復(fù)雜度是明顯不能接受的。倒排索引是在創(chuàng)建之初可以進(jìn)行排序預(yù)處理，問(wèn)題轉(zhuǎn)化成兩個(gè)有序的list求交集，就方便多了。（1）如果相同，放入結(jié)果集，隨意移動(dòng)一個(gè)指針；（2）否則，移動(dòng)值較小的一個(gè)指針，直到隊(duì)尾；（1）集合中的元素最多被比較一次，時(shí)間復(fù)雜度為O(n)；（2）多個(gè)有序集合可以同時(shí)進(jìn)行，這適用于多個(gè)分詞的item求url_id交集；這個(gè)方法就像一條拉鏈的兩邊齒輪，一一比對(duì)就像拉鏈，故稱為拉鏈法；畫(huà)外音：倒排索引是提前初始化的，可以利用“有序”這個(gè)特性。
數(shù)據(jù)量大時(shí)，url_id分桶水平切分+并行運(yùn)算是一種常見(jiàn)的優(yōu)化方法，如果能將list1<url_id>和list2<url_id>分成若干個(gè)桶區(qū)間，每個(gè)區(qū)間利用多線程并行求交集，各個(gè)線程結(jié)果集的并集，作為最終的結(jié)果集，能夠大大的減少執(zhí)行時(shí)間。有序集合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}每個(gè)桶內(nèi)的數(shù)據(jù)量大大降低了，并且每個(gè)桶內(nèi)沒(méi)有重復(fù)元素，可以利用多線程并行計(jì)算：桶1內(nèi)的集合a和集合d的交集是x{3,5,7}桶2內(nèi)的集合b和集合e的交集是y{30, 50, 70}最終，集合1和集合2的交集，是x與y與z的并集，即集合{3,5,7,30,50,70}。畫(huà)外音：多線程、水平切分都是常見(jiàn)的優(yōu)化手段。數(shù)據(jù)進(jìn)行了水平分桶拆分之后，每個(gè)桶內(nèi)的數(shù)據(jù)一定處于一個(gè)范圍之內(nèi)，如果集合符合這個(gè)特點(diǎn)，就可以使用bitmap來(lái)表示集合：如上圖，假設(shè)set1{1,3,5,7,8,9}和set2{2,3,4,5,6,7}的所有元素都在桶值[1, 16]的范圍之內(nèi)，可以用16個(gè)bit來(lái)描述這兩個(gè)集合，原集合中的元素x，在這個(gè)16bitmap中的第x個(gè)bit為1，此時(shí)兩個(gè)bitmap求交集，只需要將兩個(gè)bitmap進(jìn)行“與”操作，結(jié)果集bitmap的3，5，7位是1，表明原集合的交集為{3,5,7}。水平分桶，bitmap優(yōu)化之后，能極大提高求交集的效率，但時(shí)間復(fù)雜度仍舊是O(n)。bitmap需要大量連續(xù)空間，占用內(nèi)存較大。畫(huà)外音：bitmap能夠表示集合，用它求集合交集速度非常快。有序鏈表集合求交集，跳表是最常用的數(shù)據(jù)結(jié)構(gòu)，它可以將有序集合求交集的復(fù)雜度由O(n)降至接近O(log(n))。集合1{1,2,3,4,20,21,22,23,50,60,70}要求交集，如果用拉鏈法，會(huì)發(fā)現(xiàn)1,2,3,4,20,21,22,23都要被無(wú)效遍歷一次，每個(gè)元素都要被比對(duì)，時(shí)間復(fù)雜度為O(n)，能不能每次比對(duì)“跳過(guò)一些元素”呢？集合1{1,2,3,4,20,21,22,23,50,60,70}建立跳表時(shí)，一級(jí)只有{1,20,50}三個(gè)元素，二級(jí)與普通鏈表相同。集合2{50,70}由于元素較少，只建立了一級(jí)普通鏈表。如此這般，在實(shí)施“拉鏈”求交集的過(guò)程中，set1的指針能夠由1跳到20再跳到50，中間能夠跳過(guò)很多元素，無(wú)需進(jìn)行一一比對(duì)，跳表求交集的時(shí)間復(fù)雜度近似O(log(n))，這是搜索引擎中常見(jiàn)的算法。（1）全網(wǎng)搜索引擎系統(tǒng)由spider, search&index, rank三個(gè)子系統(tǒng)構(gòu)成；（2）站內(nèi)搜索引擎與全網(wǎng)搜索引擎的差異在于，少了一個(gè)spider子系統(tǒng)；（3）spider和search&index系統(tǒng)是兩個(gè)工程系統(tǒng)，rank系統(tǒng)的優(yōu)化卻需要長(zhǎng)時(shí)間的調(diào)優(yōu)和積累；（4）正排索引（forward index）是由網(wǎng)頁(yè)url_id快速找到分詞后網(wǎng)頁(yè)內(nèi)容list<item>的過(guò)程；（5）倒排索引（inverted index）是由分詞item快速尋找包含這個(gè)分詞的網(wǎng)頁(yè)list<url_id>的過(guò)程；（6）用戶檢索的過(guò)程，是先分詞，再找到每個(gè)item對(duì)應(yīng)的list<url_id>，最后進(jìn)行集合求交集的過(guò)程； - 二重for循環(huán)法，時(shí)間復(fù)雜度O(n*n) - bitmap，大大提高運(yùn)算并行度，時(shí)間復(fù)雜度O(n) - 跳表，時(shí)間復(fù)雜度為O(log(n))需求二：我想做一個(gè)內(nèi)容檢索功能，不復(fù)雜，100億數(shù)據(jù)，每秒10萬(wàn)查詢而已，兩個(gè)星期能上線嗎？
大部分工程師未必接觸過(guò)“搜索內(nèi)核”，但互聯(lián)網(wǎng)業(yè)務(wù)，基本會(huì)涉及“檢索”功能。以同城的帖子業(yè)務(wù)場(chǎng)景為例，帖子的標(biāo)題，帖子的內(nèi)容有很強(qiáng)的用戶檢索需求，在業(yè)務(wù)、流量、并發(fā)量逐步遞增的各個(gè)階段，應(yīng)該如何實(shí)現(xiàn)檢索需求呢？
創(chuàng)業(yè)階段，常常用這種方法來(lái)快速實(shí)現(xiàn)。數(shù)據(jù)在數(shù)據(jù)庫(kù)中可能是這么存儲(chǔ)的：t_tiezi(tid, title, content)滿足標(biāo)題、內(nèi)容的檢索需求可以通過(guò)LIKE實(shí)現(xiàn)：select tid from t_tiezi where content like ‘%天通苑%’這種方式確實(shí)能夠快速滿足業(yè)務(wù)需求，存在的問(wèn)題也顯而易見(jiàn)：（1）效率低，每次需要全表掃描，計(jì)算量大，并發(fā)高時(shí)cpu容易100%；如何快速提高效率，支持分詞，并對(duì)原有系統(tǒng)架構(gòu)影響盡可能小呢，第一時(shí)間想到的是建立全文索引：alter table t_tiezi add fulltext(title,content)使用match和against實(shí)現(xiàn)索引字段上的查詢需求。全文索引能夠快速實(shí)現(xiàn)業(yè)務(wù)上分詞的需求，并且快速提升性能（分詞后倒排，至少不要全表掃描了），但也存在一些問(wèn)題：（2）由于全文索引利用的是數(shù)據(jù)庫(kù)特性，搜索需求和普通CURD需求耦合在數(shù)據(jù)庫(kù)中：檢索需求并發(fā)大時(shí)，可能影響CURD的請(qǐng)求；CURD并發(fā)大時(shí)，檢索會(huì)非常的慢；（3）數(shù)據(jù)量達(dá)到百萬(wàn)級(jí)別，性能還是會(huì)顯著降低，查詢返回時(shí)間很長(zhǎng)，業(yè)務(wù)難以接受；為了解決全文索的局限性，當(dāng)數(shù)據(jù)量增加到大幾百萬(wàn)，千萬(wàn)級(jí)別時(shí)，就要考慮外置索引了。外置索引的核心思路是：索引數(shù)據(jù)與原始數(shù)據(jù)分離，前者滿足搜索需求，后者滿足CURD需求，通過(guò)一定的機(jī)制（雙寫(xiě)，通知，定期重建）來(lái)保證數(shù)據(jù)的一致性。原始數(shù)據(jù)可以繼續(xù)使用Mysql來(lái)存儲(chǔ)，外置索引如何實(shí)施？Solr，Lucene，ES都是常見(jiàn)的開(kāi)源方案。其中，ES（ElasticSearch）是目前最為流行的。（1）Lucene只是一個(gè)庫(kù)，需要自己做服務(wù)，自己實(shí)現(xiàn)高可用/可擴(kuò)展/負(fù)載均衡等復(fù)雜特性；（2）Lucene只支持Java，如果要支持其他語(yǔ)言，必須得自己做服務(wù)；（3）Lucene不友好，這是很致命的，非常復(fù)雜，使用者往往需要深入了解搜索的知識(shí)來(lái)理解它的工作原理，為了屏蔽其復(fù)雜性，還是得自己做服務(wù)；
為了改善Lucene的各項(xiàng)不足，解決方案都是“封裝一個(gè)接口友好的服務(wù)，屏蔽底層復(fù)雜性”，于是有了ES：（1）ES是一個(gè)以Lucene為內(nèi)核來(lái)實(shí)現(xiàn)搜索功能，提供REStful接口的服務(wù)；（2）ES能夠支持很大數(shù)據(jù)量的信息存儲(chǔ)，支持很高并發(fā)的搜索請(qǐng)求；（3）ES支持集群，向使用者屏蔽高可用/可擴(kuò)展/負(fù)載均衡等復(fù)雜特性；目前，快狗打車使用ES作為核心的搜索服務(wù)，實(shí)現(xiàn)業(yè)務(wù)上的各類搜索需求，其中：（1）數(shù)據(jù)量最大的“接口耗時(shí)數(shù)據(jù)收集”需求，數(shù)據(jù)量大概在10億左右；（2）并發(fā)量最大的“經(jīng)緯度，地理位置搜索”需求，線上平均并發(fā)量大概在2000左右，壓測(cè)數(shù)據(jù)并發(fā)量在8000左右；所以，ES完全能滿足10億數(shù)據(jù)量，5k吞吐量的常見(jiàn)搜索業(yè)務(wù)需求。當(dāng)數(shù)據(jù)量進(jìn)一步增加，達(dá)到10億、100億數(shù)據(jù)量；并發(fā)量也進(jìn)一步增加，達(dá)到每秒10萬(wàn)吞吐量；業(yè)務(wù)個(gè)性也逐步增加的時(shí)候，就需要自研搜索引擎了，定制化實(shí)現(xiàn)搜索內(nèi)核了。到了定制化自研搜索引擎的階段，超大數(shù)據(jù)量、超高并發(fā)量為設(shè)計(jì)重點(diǎn)，為了達(dá)到“無(wú)限容量、無(wú)限并發(fā)”的需求，架構(gòu)設(shè)計(jì)需要重點(diǎn)考慮“擴(kuò)展性”，力爭(zhēng)做到：增加機(jī)器就能擴(kuò)容（數(shù)據(jù)量+并發(fā)量）。同城的自研搜索引擎E-search初步架構(gòu)圖如下：（1）上層proxy（粉色）是接入集群，為對(duì)外門戶，接受搜索請(qǐng)求，其無(wú)狀態(tài)性能夠保證增加機(jī)器就能擴(kuò)充proxy集群性能；
（2）中層merger（淺藍(lán)色）是邏輯集群，主要用于實(shí)現(xiàn)搜索合并，以及打分排序，業(yè)務(wù)相關(guān)的rank就在這一層實(shí)現(xiàn)，其無(wú)狀態(tài)性也能夠保證增加機(jī)器就能擴(kuò)充merger集群性能；（3）底層searcher（暗紅色大框）是檢索集群，服務(wù)和索引數(shù)據(jù)部署在同一臺(tái)機(jī)器上，服務(wù)啟動(dòng)時(shí)可以加載索引數(shù)據(jù)到內(nèi)存，請(qǐng)求訪問(wèn)時(shí)從內(nèi)存中l(wèi)oad數(shù)據(jù)，訪問(wèn)速度很快： - 為了滿足數(shù)據(jù)容量的擴(kuò)展性，索引數(shù)據(jù)進(jìn)行了水平切分，增加切分份數(shù)，就能夠無(wú)限擴(kuò)展性能，如上圖searcher分為了4組 - 為了滿足一份數(shù)據(jù)的性能擴(kuò)展性，同一份數(shù)據(jù)進(jìn)行了冗余，理論上做到增加機(jī)器就無(wú)限擴(kuò)展性能，如上圖每組searcher又冗余了2份如此設(shè)計(jì)，真正做到做到增加機(jī)器就能承載更多的數(shù)據(jù)量，響應(yīng)更高的并發(fā)量。為了滿足搜索業(yè)務(wù)的需求，隨著數(shù)據(jù)量和并發(fā)量的增長(zhǎng)，搜索架構(gòu)一般會(huì)經(jīng)歷這么幾個(gè)階段：
需求三：檢索的時(shí)效性，對(duì)用戶體驗(yàn)來(lái)說(shuō)很重要，必須檢索出5分鐘之前的新聞，1秒鐘之前發(fā)布的貼子，不復(fù)雜吧？
最后一個(gè)高級(jí)話題，關(guān)于搜索的實(shí)時(shí)性：
百度為何能實(shí)時(shí)檢索出5分鐘之前新出的新聞？同城為何能實(shí)時(shí)檢索出1秒鐘之前發(fā)布的帖子？實(shí)時(shí)搜索引擎系統(tǒng)架構(gòu)的要點(diǎn)是什么？大數(shù)據(jù)量、高并發(fā)量情況下的搜索引擎為了保證實(shí)時(shí)性，架構(gòu)設(shè)計(jì)上的兩個(gè)要點(diǎn)：首先，在數(shù)據(jù)量非常大的情況下，為了保證倒排索引的高效檢索效率，任何對(duì)數(shù)據(jù)的更新，并不會(huì)實(shí)時(shí)修改索引。畫(huà)外音：因?yàn)椋坏┊a(chǎn)生碎片，會(huì)大大降低檢索效率。既然索引數(shù)據(jù)不能實(shí)時(shí)修改，如何保證最新的網(wǎng)頁(yè)能夠被索引到呢？索引分級(jí)，分為全量庫(kù)、日增量庫(kù)、小時(shí)增量庫(kù)。（1）300億數(shù)據(jù)在全量索引庫(kù)中；（2）1000萬(wàn)1天內(nèi)修改過(guò)的數(shù)據(jù)在天庫(kù)中；（3）50萬(wàn)1小時(shí)內(nèi)修改過(guò)的數(shù)據(jù)在小時(shí)庫(kù)中；
當(dāng)有修改請(qǐng)求發(fā)生時(shí)，只會(huì)操作最低級(jí)別的索引，例如小時(shí)庫(kù)。當(dāng)有查詢請(qǐng)求發(fā)生時(shí)，會(huì)同時(shí)查詢各個(gè)級(jí)別的索引，將結(jié)果合并，得到最新的數(shù)據(jù)：（1）全量庫(kù)是緊密存儲(chǔ)的索引，無(wú)碎片，速度快；（3）小時(shí)庫(kù)數(shù)據(jù)量小，速度也快；分級(jí)索引能夠保證實(shí)時(shí)性，那么，新的問(wèn)題來(lái)了，小時(shí)庫(kù)數(shù)據(jù)何時(shí)反映到天庫(kù)中，天庫(kù)中的數(shù)據(jù)何時(shí)反映到全量庫(kù)中呢？dump&merge，索引的導(dǎo)出與合并，由這兩個(gè)異步的工具完成：dumper：將在線的數(shù)據(jù)導(dǎo)出。merger：將離線的數(shù)據(jù)合并到高一級(jí)別的索引中去。小時(shí)庫(kù)，一小時(shí)一次，合并到天庫(kù)中去；天庫(kù)，一天一次，合并到全量庫(kù)中去；這樣就保證了小時(shí)庫(kù)和天庫(kù)的數(shù)據(jù)量都不會(huì)特別大；如果數(shù)據(jù)量和并發(fā)量更大，還能增加星期庫(kù)，月庫(kù)來(lái)緩沖。超大數(shù)據(jù)量，超高并發(fā)量，實(shí)時(shí)搜索引擎的兩個(gè)架構(gòu)要點(diǎn)：關(guān)于“搜索”與“檢索”的需求，能滿足了嗎？架構(gòu)師之路-分享技術(shù)思路
