360網站收錄（360搜索的百億級網頁搜索引擎架構實現）

奇技指南360搜索是360的重要產品，目前擁有上萬臺服務器，每日抓取網頁數量高達十億，引擎索引的優質網頁數量超過數百億。本文就來為大傢介紹一下，如此強大的搜索引擎是如何設計的，涉及瞭哪些關鍵技術點。360搜索概況目前360搜索每日抓取的網頁數量高達十億，已經收錄的網頁基本上是萬億級別的網頁集合，實際可檢索的網頁是在一個百億級別的網頁集合裡。目前360搜索的單日流量是億級pv。我們目前的在線、離線機群有幾萬臺服務器來維護這麼大量級的計算。主要內容我今天的分享的主要會側重於百億級網站搜索引擎架構的一些核心模塊的理論設計。本次分享內容分為以下四個模塊：如何設計搜索引擎百億級網頁計算關鍵技術網頁索引組織模式網頁檢索和相關性01 如何設計搜索引擎首先從如何設計一個搜索引擎講起。基礎檢索一個用戶請求過來之後，整個搜索引擎的工作流程大致如下：首先用切詞組件做分詞，把query分成多個word，然後多個word會從我們的倒排索引裡面獲取倒排拉鏈，在倒排拉鏈的基礎上，會做求交計算來拿到所有命中的doc list。拿到doc list之後，我們希望能夠把優質的網頁反饋給用戶，這時候我們還需要做rank計算。rank計算就是拿倒排裡面的一些位置索引信息，包括在正排裡面拿一些rank的屬性特征信息做打分，最終會把分數比較高的Top N結果反饋用戶。當然在前端web頁面展示的時候，需要從正排中提取摘要信息，展示給用戶。這就是整個的檢索過程。基礎索引整個檢索過程涉及到兩個庫。第一個是正排索引，另一個是倒排索引，我這裡針對這兩個庫給大傢做一個簡單的介紹。什麼是正排索引？我們從互聯網上抓取的網頁包含很多信息，包括網頁頭信息、標題、正文、標簽等。我們首先從網頁中把文章的正文以及文章相關的特征提取出來，當然也輸入一些挖掘的信息，然後做一些分詞處理。這個過程，我們是把整個的網頁生成瞭兩部分數據，第一部分就是屬性，所謂屬性就是針對這些網站的一些特征，比如說網站分類信息、網站rank相關信息等。第二個是針對的正文的分詞的結果。整個的正排索引，就是以doc為key，以屬性和word列表為value的一種結構。因為用戶在檢索時是以word為key來做檢索的，我們希望能夠把正排索引轉化成一種結構，來適應用戶的檢索，所以我們把正排索引轉化成瞭以word為key，以doclist為value的一種結構，這個結構能夠給用戶提供高效的檢索。這就是我們所謂的倒排索引。檢索模型上面簡單地介紹瞭搜索引擎的工作過程及基本概念，那下面我們講一下，站在用戶檢索的角度來說，如何來設計一個搜索引擎，它的檢索模型是什麼樣的？1、query分析首先要做的就是針對用戶輸入的query進行query分析。query分析基本包涵三點：確定檢索的粒度、Term屬性分析、Query需求分析。確定檢索的粒度所謂確定檢索粒度，就是分詞的粒度。我們會提供標準的分詞，以及短語、組合詞。針對不同的分詞粒度返回的網頁集合是不一樣的。標準分詞粒度越小，返回的結果越多，從中拿到優質結果的能力就越低。而短語和組合詞本身就是一個精準的檢索組合，相對的拿到的網頁集合的質量就會高一些。Term屬性分析這一塊主要是涉及到兩個點。第一個點就是query中每一個詞的term weight（權重）。權重是用來做什麼的？每一個用戶的query它本身都有側重點。舉個例子，比如“北京長城”這個query，用戶輸入這個詞搜索的時候其實他想搜的是長城，北京隻是長城的一個限定詞而已，所以說在term weight計算的時候，長城是作為一個主詞來推薦的。即使query隻搜長城也會返回一個符合用戶預期的結果，但是如果隻搜北京的話，是不可能返回用戶預期的結果的。第二個就是term本身的一些緊密性。緊密性代表用戶輸入的query的一些關聯關系。舉個明顯的例子，有些query是具有方向性的，比如說北京到上海的機票怎麼買？多少錢？這本身是有方向性的語義。Query需求分析針對query本身我們要分析用戶的意圖是什麼？當然也包括一些時效性的特征。舉個例子，比如說“非誠勿擾”這個詞，它有電影也有綜藝節目。如果說能夠分析出用戶本身他是想看電影還是看綜藝節目，我們就會給用戶反饋一個更優質的結果，來滿足用戶的需求。query分析這裡我主要做瞭一個簡單的介紹，query分析涉及到的一些算法的東西，可能以後有機會再具體分享，這裡先不做介紹。2、查詢策略查詢策略覆蓋的工具就是我們整個引擎架構所要做的工作。查詢策略主要包括四個方面的工作：檢索資源、確定相關網頁集合、結果相關性計算、重查策略。檢索資源所謂檢索資源就是我們從互聯網上拿到的網頁。從互聯網上能拿到的網頁，大概是萬億規模，如果說我們把所有網頁拿過來，然後做建庫做索引，在用戶層面檢索，從量級上來說是不太現實的。因為它需要很多的機器資源，包括一些服務資源，另外我們從這麼大一個集合裡面來選取符合用戶需求的數據，代價也是很大的。所以說我們會對整個檢索資源做一個縮減，也就是說我們會針對互聯網上所有的抓取過的網頁，做一個質量篩選。質量篩選出結果之後，我們還會對網頁做一個分類。我們拿到陌生的網頁，會根據它本身的站點的權威性，網站本身的內容質量做打分。然後我們會對網頁分類，標記高質量的網頁，普通網頁，時效性的一個網頁，這樣的話在用戶檢索的時候我們會優先選擇高質量的網頁返回給用戶。當然從另外一個維度來講，我們也會從內容上進行分類，就是說每個網頁的title和qanchor信息，也就是錨文本信息，是對整篇文章的一個描述信息，也代表文章的主體。如果我們優先拿title和anchor信息作為用戶的召回的一個相關url集合，那它準確性要比從正文拿到的結果質量要高。當然我們也會保留這種信息來提升它的召回的量。這是檢索要準備的檢索資源這一塊。確定相關網頁集合這一塊的話基本上可以分為兩點。一個是整個query切分後的 term命中，能夠命中query當然非常好，因為它能夠反應相關數據，正常情況下，網站和用戶query相關性是非常高的。但是也會存在這樣問題，所有的query全命中有可能返回網站數量不夠，我們這時候就需要做一些term部分命中的一些策略。前面query分析中講到瞭term weight的概念，我們可能會選擇一些term weight比較重要的term來作為這次召回結果的一個term。整個確定相關網頁集合的過程，就是一個求交計算的過程，後面我會再詳細介紹。結果相關性計算我們拿到瞭相關的網頁之後，會做一個打分，打分就是所說的結果相關性計算。我這裡列舉瞭兩個最基礎的計算。第一個是基礎權值的計算，針對每個term和文章本身的相關性的信息。第二個就是term緊密度計算，也就是整個query裡面的term在文章中的分佈情況。重查策略為什麼有重查策略，就是因為在用戶檢索過程中有可能返回的結果比較少，也有可能返回給用戶的結果質量比較低，最差的就是結果不符合用戶的真正意圖。我們可能通過以下三個方式來解決這個問題，一是增加檢索資源來拿到更多的結果；而是通過更小粒度的term，減掉一些不重要的term來拿到的結果，還有我們可能也會做一些query的改寫以及query的擴展，來滿足用戶的意圖。從整個檢索模型可以看到，我們要做的工作首先是query分析；第二我們需要把檢索資源提前準備好，那就是所謂的索引；第三點是在一個query過來之後，我們通過求交計算確定相關的網頁集合，然後通過相關性計算，把優質的集合返回給用戶，最後如果結果不滿足用戶要求的話，我們可以做一個重查。這個檢索模型，就是我們360搜索設計的一個基礎。02 百億級網頁計算關鍵技術下面我介紹一下360搜索這種百億級網頁的搜索引擎的關鍵技術。我這裡主要介紹離線建庫和在線檢索兩個核心模塊。離線建庫和在線檢索1、離線建庫首先離線建庫這一塊，我們要有一些基礎設施，主要有三部分：Hbase/HDFS、Map-reduce、Storm/Kaka。第一個是Hbase和HDFS。我們的網頁量級很大，我們會把互聯網上所有的網頁抓取過來存到Hbase庫裡，我們也會把我們提供檢索的網頁存到Hbase庫裡面。為什麼用Hbase呢，因為Hbase是一個面向分佈式，並支持列存儲的。支持列存儲這一點對我們很重要，因為我們所有的網頁在抓取的過程中，包括rank同學在做rank計算的過程中，都會做一些部分更新，就是按照他們所需要的數據進行更新，那列存儲就很容易滿足我們的需求。HDFS 主要用於建索引和存儲產出的索引文件，這些都是落地數據，啟動瞭和線上更新銜接的作用(線上從HDFS拉取數據)。當然我們的搜索引擎也會涉及到時效性的問題，特別是突發時效性，可能會也需要有實時計算模型。我們目前的話也基於Storm，當然還有我們自己內部在做的一些實時性的開發項目。整個離線建庫主要的核心點有三個部分：第一個就是索引劃分。所謂索引劃分，百億級的網頁我們不可能用一個數據庫就表示出來，即使我們能表示出來一點，也沒有這麼大的機器來提供這樣一個磁盤存放這些數據，因為索引大概是幾P的一個量級。所以說我們需要把索引劃分成小的網頁集合，然後再針對小的網頁集合做索引庫，在小的網頁集合的基礎上和線上的在線服務做一個一一對應的關系。第二點是索引創建。索引創建這一塊基本上是基於Map-reduce跑的批量任務。因為我們上百億的網頁需要跑下來的話，可能需要的資源很多，時間也會拉得很長，Map-reduce本身提供瞭分佈式計算的機制，能夠滿足我們的需求。第三點是索引更新。這一塊主要涉及到的一是我們每天新抓過來的數據；二是rank的同學要做線上特征，或者屬性的一些迭代計算，要更新到線上。所以說也會涉及到百億級別的數據的索引更新。2、在線檢索在線檢索的基礎設施有三部分：分佈式服務、請求廣播、負載均衡。分佈式的服務框架是在線檢索的一個基礎配件；在索引劃分的時候，我們會把大的網頁集合換成小的集合，在提供檢索的時候，我們會以廣播的方式來廣播到各個小的索引單元，收集所有符合預期的網頁集合才能夠把它做歸並排序，選出最優數據；在線檢索服務我們需要考慮更多的還有系統本身的穩定性，這個主要靠負載均衡來保證。在線檢索裡面最底層的兩個核心模塊是求交計算和基礎相關性計算。架構我會通過下面這個圖給大傢大概講解一下搜索引擎整體架構的流程。首先我們先從官網上抓取網頁，抓取的網頁會存到基於Hbase的網頁庫裡。這個是一個萬億量級的網頁庫，下一步要做的工作是質量篩選，然後我們會把通過質量篩選的網頁放到我們的索引網頁庫中，所有的建庫，包括rank計算，以及所有與搜索引擎相關的部分都是依賴於下邊的網頁索引庫進行的。我們在建索引的時候，會做一個分片處理，分片的機制采用瞭區間劃分。那麼區間劃分基本上我們就是用md5作為Key，本身md5是64位的整數，按照這64位整數的范圍作為一個區間劃分。從url轉換上md5它本身是均勻分佈的，那我們分片按照這個區間劃分也會是均勻的，實際上我們劃分的各個索引節點的量級也是均等的。進行分片之後，我們會針對每個分片基於Map-reduce來跑，生成索引，索引主要包括上面講的正排索引和倒排索引。然後會把索引推送到下面的在線服務推薦，每個在線服務推薦負責一個索引庫。這裡可以看到，我們根據網頁的類型對索引庫也做瞭一個劃分，比如說重要網頁索引庫和普通網頁索引庫。還有一個問題，就是我們每天的新增的網站，超過我們實時的網頁怎麼辦？這種情況我們會走另外一個流程，在網頁抓取過來之後，也會有一個質量篩選，這個質量篩選有2個流程，第一個是實時計算，通過我們剛才講到的Storm集群，包括我們目前公司內部的Titan集群，進行實時計算來生成實時性的索引。第二個是我們會把每天更新的這些數據做批量計算，基於Map-reduce生成一個相互索引，這樣的話在時間上能夠覆蓋到所有的時間點。整個離線建庫基本是這樣一個流程，下面介紹一下在線檢索的模塊。用戶檢索過來之後，我們首先做一個query分析。然後我們把query分析的結果扔給分佈式服務的一個請求節點，這個請求節點通過廣播的方式會把請求廣播到這幾種索引庫這裡。在索引庫內部會做一些求交計算。第二步我們會做基礎相關性的計算，然後把優質結果的Top N 來返回給上層的服務請求節點。服務請求節點還會做一些策略，比如說用戶的一些特定需求，包括一些機器學習的排序，最終返回給用戶的網頁基本上是幾百條的一個量級。整個架構流程是就是這樣的模式。下面我會具體講一下我們重點的一些核心模塊的設計。03 網頁索引組織模式我先講一下網頁索引組織模式，也就是正排索引和倒排索引是怎麼組織的。正排索引我們要用正排索引，首先要考慮的第一個問題，就是如何支持獨立更新？為什麼要做獨立更新，是因為我們rank的同學在做任何數據挖掘，包括一些特征計算的時候，每天都有新的迭代出現，這樣的話他就需要正排索引能夠支持這種天級的更新，甚至支持小時級的更新。所以我們希望正排索引能夠設計得足夠簡單，也足夠獨立。我們這塊所有的設計依賴的主要是每個索引庫的url列表。url列表中它的位置就代表doc id，數據屬性的存儲會按照固定長度的數據塊存放在數據文件中。數據塊的下方位置就是它對應的doc id信息。這樣在更新和查找的過程中，我們隻需要知道它的doc id，就很容易找到它所在的位置。這樣的好處第一是容易生成索引文件；第二個是可以按照自己的要求進行更新。我們還要考慮另外一個問題，就是有一些算法資源挖出來的特征，並不是包含瞭所有的信息。比如說有一些團購網站、美食介紹網站裡面，會有一些位置信息，但這些是稀疏的信息，不可能按照這種固定長度，每個url都會分配一個數據塊，這樣會造成大量的資源浪費。所以我們這裡會針對這種稀疏的屬性做一個變長的數據塊，但是它在結構上發生瞭變化，它有一個頭信息。頭信息主要是用來存儲它在數據文件裡面的位置信息，整個頭信息和url列表是一 一對應的，本身它裡面存的就是屬性信息，這樣的話我們再通過他的doc id直接找到他的偏移，然後通過偏移很容易找到它的屬性。倒排索引倒排索引我們也需要考慮兩個問題，第一個問題，從正排索引轉化為倒排，數據量會劇增，因為我們面向的是一個word對應的doc list，doc list重復度非常高，這樣的話我們就需要針對倒排索引進行一個壓縮。壓縮的話我們采用的原則基本是壓縮比例越多越好；解壓時越快越好。這就需要對整個倒排表做一個結構化的設計。我們采取的做法是把整個倒排表劃分成多個塊，針對每一個塊通過一些壓縮算法做壓縮。整個倒排表劃分成塊之後，檢索的時候，也需要按照這種塊的模式來進行解壓，所以隻要解壓到的塊能夠滿足用戶的需求，那下面的塊就不用再解壓瞭，這樣的話就能減少解壓的成本。一個用戶檢索的請求過來之後，我們希望檢索能越快越好，所以我們希望能夠提供一個范圍查找。我們會設立一個段，每個段會記錄每一個動態表塊的最小的id和最大的id來表示范圍。那這樣的話我們在檢索一個倒排list的過程中，就先可以先檢索段，通過段找到它的在哪個塊， 再做檢索。整個倒排索引組成瞭一個四級結構，第一個就是它本身的詞表，第二個是段信息，第三個是倒排表，第四個是針對每個word在某個doc裡面一些位置信息，這個信息主要是用來做基礎相關性計算的。04 網頁檢索和相關性求交模型我們下面講一下，在檢索的過程中，求交計算是怎麼做的？求交是檢索一個非常核心的模塊，也是對檢索性能提出非常大要求的一個模塊。我簡單地舉一個例子來給大傢講一下整個求交模塊的設計。比如用戶query是由三個詞來組成的，在求交過程中，首先要從這三個word中選出拉鏈最短的一個word。因為用最短的拉鏈去和其他拉鏈求交，會減少求交次數。第二步，我們拿到最短拉鏈之後，比如現在word 1的拉鏈是最短的，那我們會依次建立word 1的倒排拉鏈，從倒排拉鏈中獲得每個doc id和其他倒排拉鏈的doc id做求交計算。我拿doc id=11這個來給大傢解釋一下求交的具體步驟。比如說倒排拉鏈裡面有11這個word，那在倒排拉鏈裡，我們首先要查找的是它的段信息。我們發現它是在第二個段裡面，就能夠很明確地知道它在word 2的第二個倒排拉鏈的數據塊，找到這個塊之後，我們再做二分查找，因為我們在做索引的時候，doc list 的信息有序的。做二分查找來獲取它是比較穩定的。當然我們在做二分查找的過程中，也會做一些優化處理，就是一些步長策略。什麼是步長策略？我舉個例子，如果我們要查找6倍的doc id。如果我們隻做二分查找的話，我們大概要做4次 query查找才能找到這個doc id。所以我們希望有些策略來補充二分查找的不足，這就是步長策略。第一步我們先做一次查找，比如查找6這個doc id會分佈在1到7的范圍之內。然後我們會通過1和7的邊界信息來進一步計算它到6的距離。通過計算我們可以看到7到6就是一個步長，而1到6是五個步長。在這種情況下我們會改變策略，也就是我們會通過一個步長就找到6這個信息。當然這是一個非常極端的例子。我想通過這個例子說明，隻要距離它的邊界比較近的時候，我們就會轉換這種步長策略，來提升query查找的性能。基礎相關性下面我給大傢簡單介紹下基礎相關性。這也是整個檢索的一個核心部分，對檢索來說，它也是比較耗時的一個模塊。相關性計算它不可能把非常多的策略相關的信息都拿來計算，這樣會影響底層收集數據的性能。我們這裡主要做瞭兩個方面的工作，一是基礎賦權，二是緊密度計算。1、基礎賦權什麼是基礎賦權？它是來解決query中的每一個term和它對應的文章的權重計算。這裡先介紹TF和IDF這兩個概念。TF：代表承載信息量，即這個word在文章中出現的次數；IDF：代表信息承載能力，即這個word在全網的出現次數一個技術的模型，就是TF*IDF。但是在實際的應用中不會隻有這麼簡單，還會出現很多問題。比如一篇文章很長，那麼它的TF就不會太準。現在業界也有一個模型叫BM25，它主要加入瞭文章長度，和這個詞語的term weight的一些概念。我們如果想達到更好的效果的話，那麼就要在數據挖掘上做一些工作。比如說我們需要挖掘出每篇文章的主題、關鍵詞，以及關鍵詞的一些限定詞這些信息，這樣可以針對term做一個分級，拿到詞性信息，這樣可以更容易、更準確地來描述這個word對文章的權重信息。2、緊密度計算所謂緊密度計算就是用戶的query過來之後，針對query的分詞，一是相鄰word之間的緊密程度在文章中是怎樣的分佈；二是跨term的信息，那也就是方向的信息。可以簡單理解為我要算的就是一個距離問題。我這裡列瞭一個簡單的具體的模型。我們首先在query中選一個詞作為中心點，比如B。然後我們拿text文本的位置信息減去query的位置信息，然後再通過中心點的一個計算，算出它的相對位置。比如說A這個term本身它的距離像1這個位置，當然就是說他後邊A的距離在算的過程中，你會發現因為它是在B的後面，他的距離可能就會拉長，這樣的話它解決的是一個方向性的問題。(參考: proximity距離)在後面A的距離大概是4。所以針對距離變長的這種情況我們會做一些打壓。基礎相關性是檢索的一個基礎。當然在基礎相關性的基礎上，我們會把優質的網頁集合拿到上層，上層也會做一些rank的計算。大傢可能有的瞭解比如這種LTR模型來做一些排序的計算，當然也會有一些針對用戶策略，包括用戶意圖的一些策略來打分。最終返回用戶一個豐富的結果集。其他相關技術點前面我基本介紹瞭360搜索的核心模塊以及關鍵技術。當然搜索還涉及很多其他的技術點，比如：時效性機群資源優化檢索性能Cache系統系統穩定性大數據實時計算以上就是360搜索引擎架構的整體設計以及關鍵技術。關於360技術360技術是360技術團隊打造的技術分享公眾號，每天推送技術幹貨內容更多技術信息歡迎關註“360技術”微信公眾號