此項(xiàng)目是自己學(xué)習(xí)搜索引擎過(guò)程中的一些心得，在使用go語(yǔ)言的時(shí)候，發(fā)現(xiàn)了悟空這個(gè)搜索引擎項(xiàng)目，結(jié)合此項(xiàng)目代碼以及《信息檢索導(dǎo)論》，自己對(duì)搜索引擎的原理是實(shí)現(xiàn)都有了一個(gè)初步的認(rèn)識(shí)，然后結(jié)合工作中可能遇到的場(chǎng)景，做了一個(gè)簡(jiǎn)單的demo。寫(xiě)下這篇文章，可能比較啰嗦，希望幫助到需要的人。

基礎(chǔ)知識(shí)

一個(gè)簡(jiǎn)單例子

假如有四個(gè)文檔，分別代表四部電影的名字：

1. The Shawshank Redemption
2. Forrest Gump
3. The Godfather
4. The Dark Knight

如果我們想根據(jù)這四個(gè)文檔建立信息檢索，即輸入查找詞就可以找到包含此詞的所有電影，最直觀的實(shí)現(xiàn)方式是建立一個(gè)矩陣，每一行代表一個(gè)詞，每一列代表一個(gè)文檔，取值1/0代表該此是否在該文檔中。如下：

如果輸入是Dark，只需要找到Dark對(duì)應(yīng)的行，選出值為1對(duì)應(yīng)的文檔即可。當(dāng)輸入是多個(gè)單詞的時(shí)候，例如：The Gump，我們可以分別找到The和Gump對(duì)應(yīng)的行：1011和0100，如果是想做AND運(yùn)算（既包括The也包括Gump的電影），1011和0100按位與操作返回0000，即沒(méi)有滿足查詢的電影；如果是OR運(yùn)算（包括The或者包括Gump的電影），1011和0100按位與操作返回1111，這四部電影都滿足查詢。

實(shí)際情況是我們需要檢索的文檔很多，一個(gè)中等規(guī)模的bbs網(wǎng)站發(fā)布的帖子可能也有好幾百萬(wàn)，建立這么龐大的一個(gè)矩陣是不現(xiàn)實(shí)的，如果我們仔細(xì)觀察這個(gè)矩陣，當(dāng)數(shù)據(jù)量急劇增大的時(shí)候，這個(gè)矩陣是很稀疏的，也就是說(shuō)某一個(gè)詞在很多文檔中不存在，對(duì)應(yīng)的值為0，因此我們可以只記錄每個(gè)詞所在的文檔id即可，如下：

查詢的第一步還是找到每個(gè)查詢?cè)~對(duì)應(yīng)的文檔列表，之后的AND或者OR操作只需要按照對(duì)應(yīng)的文檔id列表做過(guò)濾即可。實(shí)際代碼中一般會(huì)保證此id列表有序遞增，可以極大的加快過(guò)濾操作。上圖中左邊的每一個(gè)詞叫做詞項(xiàng)，整張表稱(chēng)作倒排索引。

實(shí)際搜索過(guò)程

如果要實(shí)現(xiàn)一個(gè)搜索功能，一般有如下幾個(gè)過(guò)程

• 搜集要添加索引的文本，例如想要在知乎中搜索問(wèn)題，就需要搜集所有問(wèn)題的文本。

• 文本的預(yù)處理，把上述的收集的文本處理成為一個(gè)個(gè)詞項(xiàng)。不同語(yǔ)言的預(yù)處理過(guò)程差異很大，以中文為例，首先要把搜集到的文本做分詞處理，變?yōu)橐粋€(gè)個(gè)詞條，分詞的質(zhì)量對(duì)最后的搜索效果影響很大，如果切的粒度太大，一些短詞搜索正確率就會(huì)很低；如果切的粒度太小，長(zhǎng)句匹配效果會(huì)很差。針對(duì)分詞后的詞條，還需要正則化：例如濾除停用詞（例如：的 把 并且，一些幾乎所有中文文檔都包含的一些詞，這些詞對(duì)搜索結(jié)果沒(méi)有實(shí)質(zhì)性影響），去掉形容詞后面的的字等。

• 根據(jù)上一步的詞項(xiàng)和文檔建立倒排索引。實(shí)際使用的時(shí)候，倒排索引不僅僅只是文檔的id，還會(huì)有其他的相關(guān)的信息：詞項(xiàng)在文檔中出現(xiàn)的次數(shù)、詞項(xiàng)在文檔中出現(xiàn)的位置、詞項(xiàng)在文檔中的域（以文章搜索舉例，域可以代表標(biāo)題、正文、作者、標(biāo)簽等）、文檔元信息（以文章搜索舉例，元信息可能是文章的編輯時(shí)間、瀏覽次數(shù)、評(píng)論個(gè)數(shù)等）等。因?yàn)樗阉鞯男枨蟾鞣N各樣，有了這些數(shù)據(jù)，實(shí)際使用的時(shí)候就可以把查詢出來(lái)的結(jié)果按照需求排序。

• 查詢，將查詢的文本做分詞、正則化的處理之后，在倒排索引中找到詞項(xiàng)對(duì)應(yīng)的文檔列表，按照查詢邏輯進(jìn)行過(guò)濾操作之后可以得到一份文檔列表，之后按照相關(guān)度、元數(shù)據(jù)等相關(guān)信息排序展示給用戶。

相關(guān)度

文檔和查詢相關(guān)度是對(duì)搜索結(jié)果排序的一個(gè)重要指標(biāo)，不同的相關(guān)度算法效果千差萬(wàn)別，針對(duì)同樣一份搜索，百度和谷歌會(huì)把相同的帖子展示在不同的位置，極有可能就是因?yàn)橄嚓P(guān)度計(jì)算結(jié)果不一樣而導(dǎo)致排序放在了不同的位置。

基礎(chǔ)的相關(guān)度計(jì)算算法有：TF-IDF，BM25 等，其中BM25 詞項(xiàng)權(quán)重計(jì)算公式廣泛使用在多個(gè)文檔集和多個(gè)搜索任務(wù)中并獲得了成功。尤其是在TREC 評(píng)測(cè)會(huì)議上，BM25 的性能表現(xiàn)很好并被多個(gè)團(tuán)隊(duì)所使用。由于此算法比較復(fù)雜，我也是似懂非懂，只需要記住此算法需要詞項(xiàng)在文檔中的詞頻，可以用來(lái)計(jì)算查詢和文檔的相關(guān)度，計(jì)算出來(lái)的結(jié)果是一個(gè)浮點(diǎn)數(shù)，這樣就可以將用戶最需要知道的文檔優(yōu)先返回給用戶。

搜索引擎代碼

悟空搜索（項(xiàng)目地址： https://github.com/huichen/wukong）是一款小巧而又性能優(yōu)異的搜索引擎，核心代碼不到2000行，帶來(lái)的缺點(diǎn)也很明顯：支持的功能太少。因此這是一個(gè)非常適合深入學(xué)習(xí)搜索引擎的例子，作者不僅給出了詳細(xì)的中文文檔，還在代碼中標(biāo)注了大量的中文注釋?zhuān)喿x源碼不是太難，在此結(jié)合悟空搜索代碼和搜索原理，深入的講解搜索具體的實(shí)現(xiàn)。

索引

索引的核心代碼在core/index.go。

索引結(jié)構(gòu)體

// 索引器
type Indexer struct {
    // 從搜索鍵到文檔列表的反向索引
    // 加了讀寫(xiě)鎖以保證讀寫(xiě)安全
    tableLock struct {
        sync.RWMutex
        table     map[string]*KeywordIndices
        docsState map[uint64]int // nil: 表示無(wú)狀態(tài)記錄，0: 存在于索引中，1: 等待刪除，2: 等待加入
    }
    addCacheLock struct {
        sync.RWMutex
        addCachePointer int
        addCache        types.DocumentsIndex
    }
    removeCacheLock struct {
        sync.RWMutex
        removeCachePointer int
        removeCache        types.DocumentsId
    }

    initOptions types.IndexerInitOptions
    initialized bool

    // 這實(shí)際上是總文檔數(shù)的一個(gè)近似
    numDocuments uint64

    // 所有被索引文本的總關(guān)鍵詞數(shù)
    totalTokenLength float32

    // 每個(gè)文檔的關(guān)鍵詞長(zhǎng)度
    docTokenLengths map[uint64]float32
}

// 反向索引表的一行，收集了一個(gè)搜索鍵出現(xiàn)的所有文檔，按照DocId從小到大排序。
type KeywordIndices struct {
    // 下面的切片是否為空，取決于初始化時(shí)IndexType的值
    docIds      []uint64  // 全部類(lèi)型都有
    frequencies []float32 // IndexType == FrequenciesIndex
    locations   [][]int   // IndexType == LocationsIndex
}

tableLock中的table就是倒排索引，map中的key即是詞項(xiàng)，value就是該詞項(xiàng)所在的文檔列表信息，keywordIndices包括三部分：文檔id列表（保證docId有序）、該詞項(xiàng)在文檔中的頻率列表、該詞項(xiàng)在文檔中的位置列表，當(dāng)initOptions中的IndexType被設(shè)置為FrequenciesIndex時(shí)，倒排索引不會(huì)用到keywordIndices中的locations，這樣可以減少內(nèi)存的使用，但不可避免地失去了基于位置的排序功能。

由于頻繁的更改索引會(huì)造成性能上的急劇下降，悟空在索引中加入了緩存功能。如果要新加一個(gè)文檔至引擎，會(huì)將文檔信息加入addCacheLock中的addCahe中，addCahe是一個(gè)數(shù)組，存放新加的文檔信息。如果要?jiǎng)h除一個(gè)文檔，同樣也是先將文檔信息放入removeCacheLock中的removeCache中，removeCache也是一個(gè)數(shù)組，存放需要?jiǎng)h除的文檔信息。只有在對(duì)應(yīng)緩存滿了之后或者觸發(fā)強(qiáng)制更新的時(shí)候，才會(huì)將緩存中的數(shù)據(jù)更新至倒排索引。

添加刪除文檔

添加新的文檔至索引由函數(shù)AddDocumentToCache和AddDocuments實(shí)現(xiàn)，從索引中刪除文檔由函數(shù)RemoveDocumentToCache和RemoveDocuments實(shí)現(xiàn)。因?yàn)榇a較長(zhǎng)，就不貼在文章里面，感興趣的同學(xué)可以結(jié)合代碼和下面的講解，更深入的了解實(shí)現(xiàn)方法。

刪除文檔

1. RemoveDocumentToCache首先檢查索引是否已經(jīng)存在docId，如果存在，將文檔信息加入removeCache中，并將此docId的文檔狀態(tài)更新為1（待刪除）；如果索引中不存在但是在addCahe中，則只是把文檔狀態(tài)更新為1（待刪除）。
2. 如果removeCache已滿或者是外界強(qiáng)制更新，則會(huì)調(diào)用RemoveDocuments將removeCache中要?jiǎng)h除的文檔從索引中抹除。
3. RemoveDocuments會(huì)遍歷整個(gè)索引，如果發(fā)現(xiàn)詞項(xiàng)對(duì)應(yīng)的文檔信息出現(xiàn)在removeCache中，則抹去table和docState中相應(yīng)的數(shù)據(jù)。

備注：removeCache和docIds均已按照文檔id排好序，所以RemoveDocuments可以以較高的效率快速找到需要?jiǎng)h除的數(shù)據(jù)。

添加文檔

1. AddDocumentToCache首先會(huì)將需要添加的文檔信息放入到addCahe中，如果緩存已滿或者是強(qiáng)制更新，則會(huì)遍歷addCache，如果索引中存在此文檔，則把該文檔狀態(tài)置為1（待刪除），否則置為2（新加）并將狀態(tài)為1（待刪除）的文檔數(shù)據(jù)放在addCache列表前面，addCache列表后面都是需要直接更新的文檔數(shù)據(jù)。
2. 調(diào)用RemoveDocumentToCache更新索引，如果更新成功，則把addCache中所有的數(shù)據(jù)調(diào)用AddDocuments添加至索引，否則只會(huì)把addCache中狀態(tài)為2（新加）的文檔調(diào)用AddDocuments添加至索引。
3. AddDocuments遍歷每個(gè)文檔的詞項(xiàng)，更新對(duì)應(yīng)詞項(xiàng)的KeywordIndices數(shù)據(jù)，并保證KeywordIndices文檔id有序。

備注：第二步相同的文檔只會(huì)將最后一條添加的文檔更新至索引，避免了緩存中頻繁添加刪除可能造成的問(wèn)題。

搜索實(shí)現(xiàn)

從上面添加刪除文檔的操作可以發(fā)現(xiàn)，真正有效的數(shù)據(jù)是tableLock中的table和docState，其他的數(shù)據(jù)結(jié)構(gòu)均是出于性能方面的妥協(xié)而添加的一些緩存。查詢的函數(shù)Lookup也只是從這兩個(gè)map中找到相關(guān)數(shù)據(jù)并進(jìn)行排序。

1. 合并搜索關(guān)鍵詞和標(biāo)簽詞，從table中找到這些詞對(duì)應(yīng)的所有KeywordIndices數(shù)據(jù)

2. 從上面的KeywordIndices數(shù)據(jù)中找出所有公共的文檔，并根據(jù)文檔詞頻和位置信息計(jì)算bm25和位置數(shù)據(jù)。

代碼架構(gòu)

悟空使用了很多異步的方式提高運(yùn)行效率，針對(duì)我們開(kāi)發(fā)高效的代碼很有借鑒意義。項(xiàng)目文檔里面有一份粗略的架構(gòu)圖，我根據(jù)engine源碼，畫(huà)出了一份詳細(xì)的架構(gòu)圖。下面就以接口為粒度講解具體的執(zhí)行流程。

備注：圓柱體代表管道，矩形代表worker。

初始化引擎

這部分體現(xiàn)在圖最上面的persistentStorageInitWorker和persistentStorageInitChannel，如果指定了索引的持久化數(shù)據(jù)庫(kù)的信息，在引擎啟動(dòng)的時(shí)候，會(huì)異步調(diào)用persistentStorageInitWorker，這個(gè)routine會(huì)將持久化的索引數(shù)據(jù)（所有storage shard）加載到內(nèi)存中，加載完畢后通過(guò)persistentStorageInitChannel通知主routine.

添加文檔

IndexDocument是對(duì)外的添加文檔的接口，當(dāng)此接口執(zhí)行的時(shí)候，先將需要分詞的文本放入管道segmenterChannel，segmentWorker從segmenterChannel取出文本做分詞處理，然后將分詞的結(jié)果均勻的分配到各個(gè)shard對(duì)應(yīng)的indexerAddDocChannels和rankerAddDocChannels，indexerAddDocumentWorker和rankerAddDocWorker分別從上面兩個(gè)管道中取出數(shù)據(jù)更新索引數(shù)據(jù)和排序數(shù)據(jù)。

如果設(shè)置了持久化數(shù)據(jù)，IndexDocument還會(huì)將文檔數(shù)據(jù)均勻的放入到各個(gè)storage shard的persistentStorageIndexDocumentChannels中，persistentStorageIndexDocumentWorker負(fù)責(zé)將管道中的文檔數(shù)據(jù)持久化到文件中。

刪除文檔

RemoveDocument是對(duì)外的刪除文檔的接口，當(dāng)接口執(zhí)行的時(shí)候，找到文檔所在的shard，然后將請(qǐng)求放入indexerRemoveDocChannels和rankerRemoveDocChannels，indexerRemoveDocWorker和rankerRemoveDocWorker分別監(jiān)聽(tīng)上面兩個(gè)管道，清除索引數(shù)據(jù)和排序數(shù)據(jù)。

查詢

search是對(duì)外的搜索接口，它會(huì)針對(duì)所有的shard里的indexerLookupChannels發(fā)送請(qǐng)求數(shù)據(jù)，之后阻塞在監(jiān)聽(tīng)rankerReturnChannel這一步，indexerLookupWorker會(huì)調(diào)用函數(shù)Lookup從倒排索引中找到制定的文檔，如果不要求排序，直接將數(shù)據(jù)放入rankerReturnChannel，否則將數(shù)據(jù)交給rankerRankChannels，然后由rankerRankWorker排完序再放入rankerReturnChannel。當(dāng)search發(fā)現(xiàn)所有數(shù)據(jù)都返回之后，再將各個(gè)shard的數(shù)據(jù)做一次排序，然后返回。

總結(jié)

由架構(gòu)圖可以很清晰地看出整個(gè)運(yùn)行流程，同時(shí)知道此引擎無(wú)法分布式部署。如果需要做分布式部署，需要將每個(gè)shard作為一個(gè)獨(dú)立的進(jìn)程，而且上層有一個(gè)類(lèi)似網(wǎng)管的進(jìn)程做數(shù)據(jù)分發(fā)和匯總操作。

實(shí)例講解

為了方便自己和大家的使用，我寫(xiě)了一個(gè)比較簡(jiǎn)單的例子，用orm的callback方式更新搜索引擎。

數(shù)據(jù)準(zhǔn)備

文檔數(shù)據(jù)是我從知乎的戀愛(ài)和婚姻話題爬取的精品回復(fù)，大概有1800左右回復(fù)，包括問(wèn)題標(biāo)題，回復(fù)正文，點(diǎn)贊個(gè)數(shù)以及問(wèn)題標(biāo)簽，下載鏈接：https://github.com/LiuRoy/sakura/blob/master/spider/tables.sqlite，存儲(chǔ)格式為sqlite，數(shù)據(jù)如下：

對(duì)如何爬取的同學(xué)可以參看代碼https://github.com/LiuRoy/sakura/blob/master/spider/crawl.py，執(zhí)行如下命令直接運(yùn)行

cd sakura/spider/
pip install -r requirement
python scrawl.py

啟動(dòng)引擎

用上一步爬取的數(shù)據(jù)構(gòu)建一個(gè)搜索引擎，代碼參考server.go，在運(yùn)行之前需要自己配置一下詞典以及數(shù)據(jù)路徑，悟空提供了一份分詞詞典和停用詞列表，配置完成后運(yùn)行go run server.go啟動(dòng)服務(wù)，然后通過(guò)瀏覽器就可以使用搜索服務(wù)了。

更新索引

一般搜索服務(wù)的數(shù)據(jù)都是動(dòng)態(tài)變化的，如何在數(shù)據(jù)頻繁變動(dòng)的時(shí)候以最簡(jiǎn)單的方式更新索引呢？我能想到的方法有如下幾種：

1. 定時(shí)全量更新索引
2. 定時(shí)查找數(shù)據(jù)庫(kù)修改數(shù)據(jù)，將修改的數(shù)據(jù)更新至索引
3. 讀取數(shù)據(jù)庫(kù)binlog，將數(shù)據(jù)變動(dòng)實(shí)時(shí)更新到索引
4. 每次數(shù)據(jù)庫(kù)變更時(shí)，通過(guò)接口調(diào)用或者隊(duì)列的方式通知搜索引擎修改索引

我采用了第四種方式做了一個(gè)demo，代碼參考sender.go，為了避免代碼耦合，通過(guò)orm的callback方式將修改的數(shù)據(jù)通過(guò)zeromq消息隊(duì)列發(fā)送給搜索服務(wù)，搜索服務(wù)有一個(gè)goroutine來(lái)消費(fèi)數(shù)據(jù)并更改索引，當(dāng)執(zhí)行go run sender.go后，新建的一條數(shù)據(jù)就可以馬上被索引到。