全網搜尋引擎架構與流程如何？
全網搜尋引擎的宏觀架構如上圖，核心子系統主要分為三部分（粉色部分）：
（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。
簡易的，正排索引可以了解為：
Map<url, list>
能夠由網頁url快速找到内容的一個資料結構。
畫外音：時間複雜度可以認為是O(1)。
什麼是反向索引（inverted index）？
與正排索引相反，由item查詢key的過程，使用反向索引。
對于網頁搜尋，反向索引可以了解為：
Map<item, list>
能夠由查詢詞快速找到包含這個查詢詞的網頁的資料結構。
畫外音：時間複雜度也是O(1)。
舉個例子，假設有3個網頁：
url1 -> “我愛北京”
url2 -> “我愛到家”
url3 -> “到家美好”
這是一個正排索引：
Map。
分詞之後：
url1 -> {我，愛，北京}
url2 -> {我，愛，到家}
url3 -> {到家，美好}
這是一個分詞後的正排索引：
Map>。
分詞後反向索引：
我 -> {url1, url2}
愛 -> {url1, url2}
北京 -> {url1}
到家 -> {url2, url3}
美好 -> {url3}
由檢索詞item快速找到包含這個查詢詞的網頁Map>就是反向索引。
畫外音：明白了吧，詞到url的過程，是反向索引。
正排索引和反向索引是spider和build_index系統提前建立好的資料結構，為什麼要使用這兩種資料結構，是因為它能夠快速的實作“使用者網頁檢索”需求。
畫外音，業務需求決定架構實作，查詢起來都很快。
檢索的過程是什麼樣的？
假設搜尋詞是“我愛”：
（1）分詞，“我愛”會分詞為{我，愛}，時間複雜度為O(1)；
（2）每個分詞後的item，從反向索引查詢包含這個item的網頁list，時間複雜度也是O(1)：
（3）求list的交集，就是符合所有查詢詞的結果網頁，對于這個例子，{url1, url2}就是最終的查詢結果；
畫外音：檢索的過程也很簡單：分詞，查反向索引，求結果集交集。
就結束了嗎？其實不然，分詞和倒排查詢時間複雜度都是O(1)，整個搜尋的時間複雜度取決于“求list的交集”，問題轉化為了求兩個集合交集。
字元型的url不利于存儲與計算，一般來說每個url會有一個數值型的url_id來辨別，後文為了友善描述，list統一用list替代。
list1和list2，求交集怎麼求？
方案一：for for，土辦法，時間複雜度O(nn)
每個搜尋詞命中的網頁是很多的，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的過程；
（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：将離線的資料合并到高一級别的索引中去。
小時庫，一小時一次，合并到天庫中去；
天庫，一天一次，合并到全量庫中去；
這樣就保證了小時庫和天庫的資料量都不會特别大；
如果資料量和并發量更大，還能增加星期庫，月庫來緩沖。
超大資料量，超高并發量，實時搜尋引擎的兩個架構要點：
關于“搜尋”與“檢索”，GET到新技能了嗎？
本文轉自“架構師之路”公衆号，58沈劍提供。