摘要

　　多年以來，主搜索的集群架構和排序算法相對比較單一，一定程度上制約了搜索業務的發展。本文主要介紹主搜索最新采用的索引分層技術。這種分層技術把主搜索集群架構從二維擴展到了三維。基于這種三維的新架構，主搜索可以根據不同的應用場景，選擇不同的檢索和排序算法，從而更好的提升主搜索的檢索性能與檢索效果。實踐表明，這種分層技術能提升主搜索120%的檢索性能和6%的搜索GMV。

　　1. 背景

　　主搜索多年以來一直采用二維集群架構來提供淘寶網商品的檢索服務，其結構如圖 1所示。主要的檢索流程如下：

　　step 1. SP向QRS提交查詢請求，QRS根據查詢內容和Searcher的狀態信息動態選擇出一行searcher機器，把查詢轉發到這些searcher機器上進行檢索。每個searcher只包含部分商品的索引，而被選擇出的一行searcher則包含一個完整商品的索引。

　　step 2. Searcher機器根據查詢，在索引的商品中檢索符合查詢串的商品，并對這些商品進行排序后返回top-k結果給QRS。Searcher機器之間查詢是并行的處理，各searcher使用的檢索與排序算法都一樣。

　　step 3. QRS根據一定的規則對searcher返回的結果進行合并和排序，然后返回top-k’結果給SP。

圖1. 主搜索集群二維結構示意圖

　　這種二維結構的集群架構和在這基礎上的檢索流程主要有以下幾個問題：

1. 集群需要的機器多。目前主搜索需索引的商品數量近10億。在一定的查詢響應時間下，單機的索引量非常有限。例如單機索引4000萬商品，那就需要25臺機器才能索引完整的商品數據。為了達到一定的服務規模，需要的行數也會特別多。如果單行的服務能力為1000QPS，那么在10萬QPS的壓力下，需要100行，共2500臺searcher機器。
2. 查詢范圍大，檢索效率相對較低。QRS挑出的一行searcher索引了完整的商品數據。在這完整的商品中，與查詢相關的商品可能有上百萬個，而QRS最終只返回幾十條最相關的結果給用戶。因此絕大部分的商品是對查詢結果沒有用的，而對這些相關性小的商品的檢索降低了檢索的效率。主搜索中存在大量的冷門商品，它們與絕大部分的查詢都不相關，索引和檢索這些冷門商品都會浪費一定的資源。
3. 支持索引結構單一，可使用檢索優化方法較少。因為各個searcher中索引的結構是一致的，一旦采用了一種全局序索引優化就難再使用其它的全局序優化。 單一的全局序優化雖然能提升針對這種按全局序排序的查詢性能，但對其它類型的排序就會有損害。在未做分層優化之前，主搜索的索引一直采用按商品下架時間（END_TIME）全局排序后進行索引。它對按END_TIME排序的查詢能提升不少性能，但對按人氣或銷量排序的查詢就非常低效。
4. 對檢索和排序的多樣性支持并不友好。例如最終查詢結果可能需要包含部分銷量高的商品，部分相關性好的商品還需要照顧展示商品的多樣性。基于這種結構需要多次完整查詢才能得到結果，從而制約了相關性選擇算法的問題空間。

　　顯然，上述的問題對主搜索引擎都是致命的，它從一定程度上限制了主搜索的規模以及與搜索相關的業務發展，急需要一種新的方法來解決或緩解上述的問題。

　　2. 相關知識

　　  在介紹主搜索具體的分層優化方法之前，我們先簡單介紹一下搜索引擎中常用優化技術—索引剪枝（又稱索引截斷）。因為主搜索中使用三維集群架構，以及在些架構上采用的檢索方法都是這些基礎索引截斷技術的演化版。通常索引截斷可分為靜態索引截斷和動態索引截斷：在靜態索引截斷中，以下三種方法比較常用：

1. 根據文檔靜態質量分把文檔劃分成多個類別。例如在全網搜索中根據網頁質量可把網頁劃分成正常網頁和垃圾網頁，同樣主搜索中根據商品銷量等可把商品劃分成熱門商品和冷門商品。這樣我們就可以針對不同類別文檔應用不同的索引結構和檢索策略以便更高效的進行大規模的文檔索引與檢索。
2. 根據每個索引詞出現的文檔按特定的特征對這些文檔進行篩選。這個特征可以是文檔的全局特征，也可以是term-doc的特征。例如在全網搜索中可以根據BM25分數挑出與索引詞相關性程度較高的文檔單獨建成一個倒排鏈。在主搜索中可以根據商品的質量挑出與這個索引詞最相關的高質量商品單獨建倒排鏈。在搜索時，我們可以優先使用這個截斷鏈快迅的找到與這個詞最相關或最熱門的文檔。
3. 根據文檔中每個詞的特性挑選出最能代表文檔內容的詞來代替全文內容，以減少索引量。例如，主搜索中的每個商品只挑選商品標題和SKU中的詞進入索引，以減少倒排索引的大小或減少引入不相關的內容。

　　  動態索引剪枝的技術比較多，但其剪枝算法通常與排序模型相關。多階段的檢索與排序是目前比較常用的方法。這種方法把文檔的查詢與排序劃分成多個階段，越靠前的階段計算單個文檔相關性所需的時間越少，但找出的文檔越多；越后的階段計算單個文檔相關性所需要的時間越多，找到的文檔越少。

　　主搜索一直使用二階段排序模型來優化檢索的性能。第一階段商品的海選，先前主搜索默認按商品的下架時間海選出數萬個最近會下架的商品。這主要是為了照顧快下架的商品有更多的展示機會。這些選出的商品不區分質量，只匹配查詢詞。第二階段商品的精選階段，對海選出的商品利用相關性等各種特征計算最匹配幾十條商品返回給用戶。二階段的排序模型給主搜索帶來的很大的性能提升，但由于后面階段的輸入依賴于前面階段的輸出。例如第一階段輸出的商品質量不高，則直接影響第二階段的排序效果。所以主搜索為了保證二階段的商品輸入的質量，從一階段中挑選了數千個文檔給二階段排序，但這些輸入的文檔絕大部分最終沒有返回。

　　3. 分層優化

　　3. 1 輔鏈優化

　　主搜索先前采用的二維結構比較直觀，也容易理解，但它很難滿足檢索性能與排序多樣性的需求。主搜索的流量組成非常多樣化，有來自網頁、無線和各種應用的請求。在這些請求中，包含各種各樣的商品排序需要，其中按人氣排序和按END_TIME在主搜索查詢流量中占比最大，它們分別是無線搜索與網頁搜索的默認排序方式。

　　為了更快的支持END_TIME排序的查詢處理速度，主搜索的索引一直按END_TIME全局序排序。當索引全局按END_TIME有序，就能通過二分查找快速的定位到滿足查詢條件商品的開始位置，可以略過很多相關但不符END_TIME的商品。但因為第一階段的排序不包含其它信息，所以找出的文檔質量參差不齊，因此需要找較多的文檔給第二階段的排序才能挑選出合適的商品給用戶。

　　按人氣排序的查詢顯然不能利用END_TIME排序的索引優化，所以它只能從前到后找人氣高的并符合查詢條件的商品。這種按人氣排序的查詢在一階段選出的商品人氣分很高，通常人手高的商品質量也比較好，所以二階段只需要對少量的商品進行重排序即可找到非常相關的文檔。但由于索引的商品按END_TIME排序，人氣高的相關商品就會隨機的出現索引的不同位置，所以在第一階段需要查找的文檔數量會比較多。

　　針對這個問題，主搜索目前使用人氣輔鏈（截斷鏈）來加速查詢。人氣輔鏈構建過程如下：

1. 針對倒排鏈較長的詞，遍歷出現這個詞的全部文檔，根據一定的規則把人氣分高的文檔保存到另一個鏈中。每個詞的篩選規則與出現這個詞的文檔整體水平相關，因此各個詞篩選的閾值都會不一樣。
2. 所有的輔鏈組成一個輔鏈索引，輔鏈中文檔的出現順序與原始鏈中的順序完全一致。

　　當有了人氣輔鏈，按人氣排序的查詢在第一階段就可以根據輔鏈信息快速找到人氣高的商品。但使用輔鏈主要有以下兩個問題：

1. 使用輔鏈查找發現得到的商品數量不夠，則還需要重新從原始鏈中重新查找。
2. 使用輔鏈容易造成符合要求的商品沒有第一階段被召回。

　　商品沒有被主要原因是各個詞建出輔鏈的人氣閾值都不一樣，文檔在能進詞A的輔鏈但可能進不了詞B的輔鏈。當同時使用多個輔鏈查詢就出現這個問題。所以主搜索在一次查詢中最多選一個詞的輔鏈。雖然輔鏈在一定程序上能加快選定排序查詢的檢索速度，但同時增加了構建索引的復雜程序。特別是存在實時索引的情況下，構建輔鏈的開銷將會非常大，另外輔鏈增加索引存儲的開銷。

　　3. 2 分層優化

　　索引全局序和輔鏈加速了檢索速度，但沒有解決低質量商品對查詢的影響：1. 低質量商品通常包含一大堆熱門查詢詞，所以對熱門查詢都需要重復的計算這些低質量的商品，但這些商品最終都不會被展示。2. 低質量商品占用大量索引存儲， 由于絕大部分低質量的商品展示機會很少，重復的存儲這些信息就的有點浪費了。另外，輔鏈中文檔號與主鏈是順序是一致的，所以輔鏈也沒有解決索引結構單一的問題。最后，雖然輔鏈上的大部分文檔在特定排序下優化于主鏈中的文檔，但在查詢仍需要完整遍歷輔鏈，因為最相關的文檔有可以出現在輔鏈的最尾部。

　　針對低質量商品的影響，一個簡單的想法就是根據商品的質量把商品劃分成多個類別，然后用不同的集群索引不同類別的文檔。檢索時，如果高質量的集群找出的商品數已經足夠好，就直接返回檢索結果。只有當高質量集群檢索到的文檔數量不夠時，才會向低質量集群檢索結果，最終合并檢索結果返回。這種做法帶來的好處是減少查找商品的范圍，同時也降低質量商品對查詢結果的影響。因為高質量的集群中的商品是原先的一個子集，包含的商品數量比完整的少很多。而且低質量商品不會現象先前一樣重復的參與計算，因為這些低質量商品已經被移到另一個集群索引中。如果絕大部分的查詢都可以通過高質量集群就可以滿足，那么向低質量機群查詢數就會變少，因此低質量集群所需要的行數會高質量的行會少很多，從而可以節省很多機器數量。當然不同質量的集群仍可以使用不同的輔鏈來優化不同排序的查詢。

　　商品按質量分層部分解決了機器數量多與查找范圍廣的問題，仍沒有解決索引結構單一與支持排序算法種類少的問題。我們知道輔鏈中包含選定排序下最好的文檔信息，所以它能較大的提升特定排序查詢的檢索速度。由于它構建成本大，仍需要全部遍歷限制了不能大規模的使用。我們可以把輔鏈索引的思想進一步的擴展，即把特定排序的輔鏈索引的中商品單獨做成一個集群。單獨做成一個集群的好處是：1. 索引商品的順序不再受原始鏈的影響，可以靈活的采用自己特定排序方式，可使用的排序方案就會變多。2. 單獨特定排序的集群的倒排鏈中得分高的商品在前面，得分低的在后面，檢索算法很容易做動態截斷，即不再需要完整的查找整個鏈。3.索引的構建與維護代價比使用輔鏈小。

　　我們可以針對不同排序的查詢構建不同的小集群，雖然這些小集群索引的商品可能重復，但它極大減小檢索商品的范圍和提升檢索速度，同時做多樣化的商品檢索也變比很容易，只需要向不同的小集群查詢相應數量的商品即可。

　　有了低質量和高質量集群，再加按不同排序優化后的小集群，整個搜索集群的結構就可以拓展成如圖2所示的三維架構。相對于二維結構，主要是增加集群維度。各維度的集群索引的商品集合如圖3所示，其中高質量與低質量集群索引的商品是沒有交集，小集群索引的商品是有交集的。

圖2 基于分層的三維集群結構圖

圖3. 各集群索引文檔的范圍示意圖

　　3. 3 主搜索的分層

　　主搜索目前采用的分層方案與上述討論的類似，首先由算法團隊根據一定的規則把商品分成了兩類，good與bad。使用兩個機群分別索引這兩類商品。這種結構下，雖然索引完整數據的列數沒有變大，good集群如果已經能滿足絕大部分的查詢需求，bad集群的查詢量相對就較少。所以bad集群只需少數幾行就可以滿足搜索需要。在主搜索中，仍超過50%商品在good集群中，所以good集群索引的文檔數量還是非常大的。由于查詢總量還是不變，因此good集群需要行數未變。其次，其它針對人氣排序等的查詢，從Good集群的商品中挑選出人氣分最高的商品單獨組成一個集群，稱為Excellent集群。Excellent機群的商品是Good機群的商品的子集，商品約占Good機群商品的15%。其結構如圖4所示，有了這三個集群，其主搜索查詢流程如下：

1. 對人氣排序的查詢：首先查Excellent集群，如果Excellent集群查找到的文檔不滿足要求，則丟棄該結果，重新到Good 和Bad集群查詢。否則，直接使用Excellent集群的結果返回。其它排序時則不查Excellent集群，直接查Good和Bad集群。
2. 對非人氣的查詢，優先查詢good集群，如果good集群返回的商品不滿足相應條件，則會向bad機群再次查詢結果，并把good與bad集群的商品合并后返回。Good與bad集群都會使用輔鏈加速不同排序查詢的檢索速度。

圖4 主搜索分層后的三維結構示意圖

　　4. 分層優化的效果

　　Good-Bad集群拆分極大減少了主搜索使用的機器數量。未拆分前一行有18列，拆分后Good機群索引近54%的商品，劃分為9列。Bad機群索引46%的商品，劃分為5列。Good集群承擔的總流量不變，Bad機群承擔的流量減少了50%。并且在Bad集群中商品信息明顯少于Good集群，所以Bad集群的查詢速度比Good快，一行的服務能力也比Good強。目前主搜索Good與Bad集群的行數比約為2:1，所以經過拆分后，總節約機群的百分比約為36%，而整體性能的提升約為40%。由于絕大多數的商品仍在Good集群，所以對檢索的效果基本無影響。

　　Good-Bad拆分后，Bad集群的壓力變小，但Good機群的性能仍是瓶頸。Excellent機群則分流按人氣排序的查詢。目前Excellent機群索引的商品數為Good機群的15%，劃分成2列。約有45%流量走Excellent集群，這些走Excellent的查詢中，約28%的查詢由于不滿相關條件重新查Good和Bad集群。Excellent集群的行數與Good機群約為8:3。雖然拆分Excellent集群整體使用的機器數量并沒有減少，但它給Good集群分擔約32%的流量。這些走Excellent集群的查詢通常所需要的計算資源比較多，實驗表明Good機群的性能比未拆分前提升近1倍，而Excellent-Good-Bad相對于只有Good-Bad機群時，整體提升了60%。

　　經Excellent-Good-Bad集群的拆分后，主搜索整體性能提升約為120%，那其搜索效果如何呢？以下是算法團隊提供的Excellent拆分前后的一些指標變化。

　　Excellent-Good分層對無線流量的影響如圖 5所示。分層后android客戶端整體展現商品數量下降2.73%，轉化率、CTR、客單價、筆單價、成交金額沒有明顯變化。iphone客戶端整體展現商品數量下降3.36%，CTR下跌2.61%，客單價下跌0.63%，筆單價下跌0.66%，成交金額下跌0.68%。展現商品數量下降的原因是Excellent集群中的商品多樣性有待豐富。

圖5 Excellent-Good分層對無線流量的影響

　　分層對賣家的影響如圖 6所示，分層后大賣家影響最小，中賣家其次，小賣家以及無成交賣家影響交大。小賣家以及無成交賣家PV和展現商品數下跌較明顯。這是因為小賣家或無成交賣家在Excellent中的商品比例相對于大賣家少。

圖6 Excellent-Good分層對賣家商品數的影響

　　 　分層對行業數據的影響如圖7所示，我們可以發現分層對各行業展示商品的數量都有略微的下降。

圖7 Excellent-Good對行業數據的影響

　　5. 分層相關的挑戰

　　分層優化給主搜索帶來極大的性能提升，但優化過程中也碰到了一些挑戰：

1. 如何劃分商品到各個機群中，以及拆分多少個機群比較合適的問題。商品的劃分通過算法團隊的不懈努盡，分層后的檢索的一些關鍵指標如轉化率、CTR、GMV、客單價等指標基本沒有影響，但我們也注意到商品、商家的多樣性都有略微的影響，如何減少影響將是未來的研究內容。
2. 實時build性能。分層后有些機群的列數比較少，但因商品質量較高，商品發生變化的概率也較大，所以這些機群需要實時build的文檔也多。例如Excellent集群列數只有2列，單臺機器需要實時build的文檔是good機群的3倍，bad機群的4倍。 為了緩解build的壓力，線上開啟異步build方式，即多個文檔處理線程進行處理。多線程處理文檔雖然能提升build的性能，但它占用檢索資源，容易導致機器抖動，從而影響整個機群的性能。
3. 消息系統的挑戰。swift作為主搜索的消息系統，在流量高峰向swift機群請求消息容易引起網絡堵塞等問題。