劉志偉,邢永旭,于 澔,李 濤,張曉東

1(百度(中國(guó))有限公司,上海 201210)

2(百度在線網(wǎng)絡(luò)技術(shù)(北京)有限公司,北京 100193)

3(西安交通大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)系,陜西 西安 710049)

軟件開(kāi)發(fā)過(guò)程中所涉及到的活動(dòng)非常廣泛,比如需求編寫(xiě)、代碼開(kāi)發(fā)、編譯、部署等等.研究發(fā)現(xiàn),代碼搜索是軟件開(kāi)發(fā)活動(dòng)中最為頻繁的活動(dòng)之一[1].比如,Google工程師每工作日使用代碼搜索多達(dá)12次[2].為了避免重復(fù)造輪子的過(guò)程,尤其在企業(yè)開(kāi)發(fā)實(shí)踐中代碼搜索更為普遍,因?yàn)樵谄髽I(yè)里構(gòu)建軟件幾乎都不是從零開(kāi)始,而是通過(guò)復(fù)用大量代碼完成構(gòu)建.因此,尋找程序員感興趣的代碼片段或者 API使用方式等代碼搜索活動(dòng)變得非常重要[3].

然而,構(gòu)建企業(yè)級(jí)的代碼搜索系統(tǒng)是非常困難的.

· 首先,代碼量巨大,Google代碼庫(kù)超過(guò)20億行[4],百度使用Git(https://git-scm.com/)進(jìn)行代碼管理,Git存儲(chǔ)代碼規(guī)?？臻g就多達(dá)TB級(jí).更為關(guān)鍵的是,代碼量時(shí)刻在急速增長(zhǎng)中,百度平均每天新增代碼153萬(wàn)行,刪除代碼 63萬(wàn)行.因此,企業(yè)級(jí)的代碼搜索工具必須能處理海量的代碼數(shù)據(jù),并且能保證代碼更新的時(shí)效性,這是極為困難的.

· 其次,大規(guī)模的企業(yè)里所使用的開(kāi)發(fā)語(yǔ)言往往較為繁雜,在百度,包括各種腳本語(yǔ)言、數(shù)據(jù)庫(kù)語(yǔ)言等在內(nèi),使用了多達(dá)30種以上的編程語(yǔ)言.由于不同語(yǔ)言的語(yǔ)法分析不同,并且不能限制在單語(yǔ)言內(nèi)進(jìn)行搜索,使得在企業(yè)里提供針對(duì)語(yǔ)法代碼檢索變得非常困難.

· 再次,不同企業(yè)對(duì)代碼的管理方式不同,比如,百度利用多分支與多 tag的方式進(jìn)行代碼管理.雖然 Git會(huì)優(yōu)化多分支與多 tag的存儲(chǔ),但是如果不加以對(duì)于重復(fù)的處理,將會(huì)造成代碼索引的迅速膨脹,使得搜索引擎工具很難容納如此海量的索引數(shù)據(jù).

· 然后,企業(yè)內(nèi)對(duì)如何提升海量代碼搜索質(zhì)量的研究仍不足,比如在百度,通過(guò)用戶輸入一個(gè)單詞或幾個(gè)單詞組成的query(query是用戶進(jìn)行搜索的關(guān)鍵詞,比如方法名或者類名),在數(shù)十億行的代碼文件進(jìn)行查找,返回給用戶想要的結(jié)果是非常難的.因此,必需要利用豐富的特征信息,對(duì)大量代碼搜索結(jié)果進(jìn)行排序.此方面的研究尚比較缺乏.

· 最后,如何保證檢索效率,能夠在百度TB級(jí)的索引數(shù)據(jù)中ms級(jí)內(nèi)完成檢索,并且呈獻(xiàn)給用戶,也極具挑戰(zhàn)性.

互聯(lián)網(wǎng)搜索引擎比如百度、Google等也有檢索代碼的功能,但是還沒(méi)有考慮代碼本身特征進(jìn)行索引排序等策略,效果還不理想.Google內(nèi)部有強(qiáng)大的代碼搜索引擎,兼顧易用性以及準(zhǔn)確性,當(dāng)前對(duì)外可以通過(guò) chromium(https://cs.chromium.org/chromium/)體驗(yàn).商業(yè)的代碼搜索軟件,比如 Krugle(http://www.krugle.com/)以及insight.io等,通過(guò)關(guān)鍵詞進(jìn)行搜索,以及代碼托管網(wǎng)站,比如 Github(https://github.com/)、Bitbucket(https://bitbucket.org/)等也提供了通過(guò)關(guān)鍵字進(jìn)行代碼搜索功能,這類工具的搜索準(zhǔn)確性還有待提升.同時(shí),已有大量代碼搜索的研究工作[5-11],有的工作對(duì)用戶查詢的輸入形式進(jìn)行約束,比如 Kashyap等人[6]開(kāi)發(fā)的 Source Forage引擎以 C/C++函數(shù)的形式作為輸入,以便更好地利用語(yǔ)法與語(yǔ)義,更精確地對(duì)相似代碼進(jìn)行查找.有的工作是定義規(guī)約化的語(yǔ)言,讓用戶描述自己想要搜索的需求,從而能更容易地找到用戶需要的結(jié)果.然而,這種約束用戶輸入復(fù)雜的查詢條件的方法在企業(yè)里往往不現(xiàn)實(shí).與自然語(yǔ)言的搜索引擎一樣,復(fù)雜的輸入將會(huì)限制用戶的使用.在企業(yè)的實(shí)際開(kāi)發(fā)過(guò)程中,用戶只是會(huì)輸入簡(jiǎn)單的一個(gè)或幾個(gè)單詞組成的查詢語(yǔ)句,比如搜索函數(shù) sort,期望找到大家普遍使用、功能為排序的函數(shù);如果用戶輸入code search,那么可能搜索code search這個(gè)系統(tǒng)的代碼庫(kù),或者出現(xiàn)在文件路徑上的這個(gè)單詞,其次才可能是包括這個(gè)詞的文件.另外,比如近期的研究中,Gu等人[5]是以自然語(yǔ)言作為query,利用神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)的方法搜索到與自然語(yǔ)言語(yǔ)義上所匹配的代碼片段,達(dá)到利用自然語(yǔ)言檢索到實(shí)現(xiàn)相關(guān)功能代碼段的目的.

然而,從企業(yè)級(jí)軟件開(kāi)發(fā)的角度看,絕大部分是邏輯較為復(fù)雜的業(yè)務(wù)代碼,而不是可以用自然語(yǔ)言具名描述的算法或者過(guò)程;同時(shí),企業(yè)開(kāi)發(fā)中,往往由于業(yè)務(wù)進(jìn)度壓力,代碼缺乏豐富的注釋,文檔也經(jīng)常落后代碼迭代的速度,這也使得無(wú)法訓(xùn)練出解釋代碼語(yǔ)義的模型.根據(jù) Google的研究[2],在實(shí)際研發(fā)過(guò)程中,工程師搜索代碼的需求主要包括如何使用一個(gè)API、API如何實(shí)現(xiàn)、API定義在哪里等,由此可見(jiàn),企業(yè)級(jí)軟件開(kāi)發(fā)過(guò)程中代碼搜索這一環(huán)節(jié),工程師搜索出發(fā)點(diǎn)是已經(jīng)有關(guān)鍵詞.此外,每個(gè)Google工程師每次搜索平均使用1.85個(gè)關(guān)鍵詞(中位數(shù)是 1個(gè)關(guān)鍵詞).因此,針對(duì)企業(yè)級(jí)的海量代碼,與自然語(yǔ)言的搜索引擎一樣,利用簡(jiǎn)單關(guān)鍵詞進(jìn)行檢索匹配代碼的方案更為實(shí)用與迫切.

針對(duì)百度的實(shí)際需求以及企業(yè)開(kāi)發(fā)中的現(xiàn)狀,本文提出了一套企業(yè)級(jí)的代碼搜索的實(shí)現(xiàn)方案,包括離線建庫(kù)部分和在線端用戶搜索部分.離線部分負(fù)責(zé)將不同的代碼相關(guān)的源數(shù)據(jù),比如 Git代碼庫(kù),以批量或?qū)崟r(shí)增量等方式進(jìn)行獲取,然后經(jīng)過(guò)數(shù)據(jù)分析,比如進(jìn)行語(yǔ)法識(shí)別、語(yǔ)法解析等,持久化到分布式海量數(shù)據(jù)庫(kù)(Elasticsearch集群)中.在線端負(fù)責(zé)完成用戶的實(shí)時(shí)代碼搜索,主要包括:首先是針對(duì)用戶的請(qǐng)求進(jìn)行鑒權(quán),保證權(quán)限安全;其次,在確定搜索請(qǐng)求安全后,對(duì)用戶的query關(guān)鍵詞進(jìn)行變換處理,以搜索更多的相關(guān)的代碼;再次,向分布式數(shù)據(jù)庫(kù)進(jìn)行請(qǐng)求,并獲得檢索到的結(jié)果;最后,對(duì)檢索結(jié)果進(jìn)行排序,利用高級(jí)定制化的排序算法返回給用戶更合理的結(jié)果.另外,本系統(tǒng)使用緩存管理以提高搜索的性能,利用摘要生成模塊以為每條結(jié)果提供描述.

此代碼搜索系統(tǒng)自推出上線以來(lái),索引了百度TB級(jí)的Git庫(kù),并能在分鐘級(jí)準(zhǔn)確索引變更代碼,支撐平均每天新增代碼153萬(wàn)行、平均每日刪除代碼63萬(wàn)行的索引,能夠針對(duì)文件、代碼庫(kù)、代碼提交時(shí)間等進(jìn)行搜索.該系統(tǒng)在百度內(nèi)部使用過(guò)程中,每周平均為數(shù)千名工程師提供代碼搜索服務(wù),每周平均完成數(shù)萬(wàn)次的搜索,平均每次檢索時(shí)間為1s以內(nèi).

根據(jù)調(diào)研,本工作是首次站在企業(yè)海量的代碼數(shù)據(jù)上,提出以及應(yīng)用包括針對(duì)代碼的query變換、提出了更多代碼相關(guān)的特征并應(yīng)用其進(jìn)行排序的方法、針對(duì)代碼搜索結(jié)果的排序評(píng)估方法、摘要生成等創(chuàng)新性的技術(shù),形成一套實(shí)用的代碼搜索方案.本文的主要工作貢獻(xiàn)如下.

· 在工業(yè)級(jí)的海量代碼上,提出了代碼的 query變換,應(yīng)用新的代碼相關(guān)特征進(jìn)行排序,且提出代碼排序的評(píng)估方法;同時(shí),結(jié)合摘要生成,使得根據(jù)用戶簡(jiǎn)單的輸入即可給出用戶想要的搜索結(jié)果.

· 并且針對(duì)此方案,實(shí)現(xiàn)了一套實(shí)用效果極佳的企業(yè)級(jí)系統(tǒng),索引了百度 TB級(jí)的代碼,且能在分鐘級(jí)處理每日百萬(wàn)級(jí)代碼行的變更.

本文第1節(jié)概述系統(tǒng)框架并簡(jiǎn)介應(yīng)用到的技術(shù).第2節(jié)介紹代碼搜索系統(tǒng)的工作流程.第3節(jié)對(duì)系統(tǒng)進(jìn)行實(shí)際應(yīng)用的評(píng)估.第4節(jié)列舉系統(tǒng)當(dāng)前不足之處.第5節(jié)是相關(guān)的研究工作.第6節(jié)進(jìn)行總結(jié)與未來(lái)工作的展望.

1 方案框架概述以及應(yīng)用到的技術(shù)簡(jiǎn)介

本文提出的企業(yè)級(jí)代碼搜索系統(tǒng)主要由離線端和在線端兩部分組成.離線端采用Elasticsearch作為持久化存儲(chǔ),Elasticsearch是一個(gè)基于Apache Lucene(TM)的開(kāi)源搜索引擎,它提供了一個(gè)分布式多用戶能力的全文搜索引擎,是當(dāng)前流行的企業(yè)級(jí)搜索引擎.離線端主要目標(biāo)是將不同的代碼源數(shù)據(jù)以批量或?qū)崟r(shí)增量等方式獲取,同時(shí)導(dǎo)入代碼等相關(guān)數(shù)據(jù),然后經(jīng)過(guò)數(shù)據(jù)分析,持久化儲(chǔ)存到Elasticsearch集群中.為了實(shí)現(xiàn)此目標(biāo),離線端分為3層:數(shù)據(jù)導(dǎo)入、數(shù)據(jù)分析、索引管理.

· 數(shù)據(jù)導(dǎo)入模塊主要負(fù)責(zé)適配各種代碼數(shù)據(jù)源.在百度的實(shí)際應(yīng)用中,主要以 Git倉(cāng)庫(kù)為主,除了批量獲取數(shù)據(jù),還對(duì)數(shù)據(jù)源進(jìn)行監(jiān)聽(tīng)以實(shí)時(shí)導(dǎo)入變更代碼庫(kù).

· 數(shù)據(jù)分析模塊主要由多個(gè)流水線解析器組成,解析器主要完成編碼檢測(cè)、代碼提交信息萃取等工作.通過(guò)對(duì)代碼以及其衍生數(shù)據(jù)(比如編碼信息、作者提交信息、文本屬性等)的解析,獲得抽象語(yǔ)法樹(shù)(abstract syntax tree,簡(jiǎn)稱AST)和代碼相關(guān)數(shù)據(jù),其中,AST解析由Eclipse CDT/JDT完成,Eclipse CDT/JDT是基于Eclipse平臺(tái)并提供C/C++(CDT),Java(JDT)集成開(kāi)發(fā)環(huán)境的插件.

· 索引管理模塊主要負(fù)責(zé)海量數(shù)據(jù)在分布式情況下的持久化存儲(chǔ)與管理,主要采用Elasticsearch作為數(shù)據(jù)索引存儲(chǔ).索引化數(shù)據(jù)除了支持代碼檢索,也應(yīng)用在了代碼跳轉(zhuǎn)上.由于代碼跳轉(zhuǎn)是另外的話題,本文不詳細(xì)展開(kāi).

在線端主要負(fù)責(zé)實(shí)時(shí)響應(yīng)用戶關(guān)鍵詞搜索,實(shí)現(xiàn)包括接口管理、搜索管理、隊(duì)列管理.

· 接口管理模塊主要包括請(qǐng)求鑒權(quán)和數(shù)據(jù)收集,其中,請(qǐng)求包括兩類:一是單個(gè)用戶的關(guān)鍵詞搜索,二是來(lái)自各個(gè)產(chǎn)品線的API調(diào)用(比如代碼重復(fù)度查詢).百度產(chǎn)品線眾多,不同的產(chǎn)品代碼有著嚴(yán)格的保密等級(jí),因此,標(biāo)識(shí)用戶身份、防止機(jī)密代碼泄露,做到代碼安全是搜索系統(tǒng)所必須的.因安全相關(guān)與本文關(guān)聯(lián)不大,這里暫略過(guò).

· 搜索管理主要包括查詢變換、Ranker、緩存管理、摘要生成模塊.此外,搜索管理模塊還通過(guò)分析用戶搜索行為數(shù)據(jù),反饋給Ranker,提高了搜索質(zhì)量和相關(guān)性.

· 隊(duì)列管理主要負(fù)責(zé)對(duì)Elasticsearch分布式數(shù)據(jù)庫(kù)的并行訪問(wèn)與參數(shù)優(yōu)化.

如圖1所示,當(dāng)用戶在前端發(fā)生一次代碼提交后,系統(tǒng)監(jiān)聽(tīng)到代碼變更消息,通過(guò)增量的方式完成整個(gè)流水線,以達(dá)到實(shí)時(shí)性的目標(biāo).當(dāng)用戶在檢索端嘗試搜索時(shí),系統(tǒng)適當(dāng)調(diào)整query關(guān)鍵詞后,根據(jù)不同用戶權(quán)限,通過(guò)在緩存、全文索引、語(yǔ)法索引等不同index中搜索,在原始召回的結(jié)果中應(yīng)用ranker中的排序策略,并在最終的結(jié)果中提煉最相關(guān)的摘要片段返回給用戶,以完成整個(gè)檢索過(guò)程.

Fig.1 Interactive process chart of Baidu code search圖1 百度代碼搜索用戶交互流程圖

2 方案實(shí)現(xiàn)

2.1 代碼數(shù)據(jù)爬蟲(chóng)與代碼索引

爬蟲(chóng)是搜索引擎系統(tǒng)中不可缺少的組成部分,代碼檢索系統(tǒng)的爬蟲(chóng)同互聯(lián)網(wǎng)爬蟲(chóng)一樣[12-14],從遠(yuǎn)端系統(tǒng)獲取數(shù)據(jù).代碼數(shù)據(jù)爬蟲(chóng)負(fù)責(zé)是從各種代碼管理系統(tǒng)獲取海量的代碼數(shù)據(jù),比如 SVN(https://subversion.apache.org/)、Git,然后進(jìn)行代碼索引.除此之外,在企業(yè)中數(shù)據(jù)安全也是數(shù)據(jù)爬蟲(chóng)端遇到的重要問(wèn)題,尤其是代碼數(shù)據(jù),是企業(yè)的核心資產(chǎn),代碼數(shù)據(jù)數(shù)據(jù)的爬蟲(chóng)與索引同樣需要極高的安全保障,不能使得爬下來(lái)的代碼發(fā)生泄漏的可能.由于安全是另外非常重要的話題,且并不是本文的重點(diǎn),因此這里并不會(huì)展開(kāi)闡述.

代碼數(shù)據(jù)爬蟲(chóng)需要解決的主要問(wèn)題是數(shù)據(jù)的時(shí)效性和數(shù)據(jù)的準(zhǔn)確性:時(shí)效性指在海量的代碼數(shù)據(jù)情況下,比如百度數(shù)TB以上的Git代碼庫(kù)基礎(chǔ)上,還能實(shí)時(shí)處理平均每日新增與刪除的數(shù)百萬(wàn)代碼數(shù)據(jù),能夠確保新變更的代碼數(shù)據(jù)能夠被快速索引到,以便用戶把代碼合入代碼庫(kù)后,即可進(jìn)行搜索;數(shù)據(jù)的準(zhǔn)確性是指在如此大規(guī)模的數(shù)據(jù)變更索取下,索引的數(shù)據(jù)不能和真實(shí)的數(shù)據(jù)有所偏差,否則會(huì)造成用戶的使用障礙.因此,本文系統(tǒng)所設(shè)計(jì)的代碼數(shù)據(jù)爬蟲(chóng)分為3個(gè)服務(wù):批量爬蟲(chóng)服務(wù)、定時(shí)爬蟲(chóng)服務(wù)、實(shí)時(shí)爬蟲(chóng)服務(wù).

批量數(shù)據(jù)爬蟲(chóng)負(fù)責(zé)遍歷全代碼庫(kù)進(jìn)行索引,主要的用途是第 1次構(gòu)建代碼搜索,或者由于代碼索引技術(shù)的升級(jí),需要再次進(jìn)行全庫(kù)重新索引,比如在第 1次索引代碼的時(shí)候沒(méi)有進(jìn)行代碼變更時(shí)間的索引,所以需要再次

全庫(kù)重新索引,這時(shí)都需要利用批量數(shù)據(jù)爬蟲(chóng)服務(wù).實(shí)時(shí)索引是代碼庫(kù)合入事件觸發(fā)的,每次只會(huì)索引變更的代碼文件,因此能保證在分鐘級(jí)甚至更少的時(shí)間索引完成.定時(shí)索引的任務(wù)是為了確保數(shù)據(jù)的準(zhǔn)確性,因?yàn)樵谡麄€(gè)系統(tǒng)中并不能保證服務(wù)是 100%可用的,我們必須進(jìn)行容錯(cuò)處理,比如事件觸發(fā)可能沒(méi)有通知到爬蟲(chóng)系統(tǒng),或者爬蟲(chóng)系統(tǒng)所在的機(jī)器異常等情況.基于系統(tǒng)是可能出錯(cuò)的前提下,需要保證代碼索引數(shù)據(jù)的準(zhǔn)確性,就需要一個(gè)額外的定時(shí)索引任務(wù),它會(huì)對(duì)比索引的數(shù)據(jù)與真實(shí)代碼數(shù)據(jù)之間的差異,處理可能由于錯(cuò)誤引發(fā)的數(shù)據(jù)異常.為了提高代碼數(shù)據(jù)爬蟲(chóng)索引代碼的效率,數(shù)據(jù)爬蟲(chóng)系統(tǒng)被設(shè)計(jì)為是多個(gè)進(jìn)程、多個(gè)線程在多物理機(jī)上執(zhí)行,能夠很好地使得機(jī)器的負(fù)載均衡.

代碼數(shù)據(jù)爬蟲(chóng)系統(tǒng)除了關(guān)鍵的 3個(gè)服務(wù)以外,還有一個(gè)特殊的代碼去重的服務(wù).因?yàn)檎缭诘?1節(jié)簡(jiǎn)介中所描述的,在百度是通過(guò)分支、tag對(duì)代碼進(jìn)行管理,如果針對(duì)分支、tag進(jìn)行代碼索引,就需要跟默認(rèn)開(kāi)發(fā)分支或者稱為主干代碼進(jìn)行去重,因?yàn)榉种?、tag的代碼跟主干代碼會(huì)非常大量的重復(fù)代碼.對(duì)大量的重復(fù)代碼進(jìn)行索引,不僅造成存儲(chǔ)空間的浪費(fèi),同時(shí)降低了搜索性能,并且如果用戶搜索出大量的重復(fù)代碼,并沒(méi)有什么意義,這降低了用戶的體驗(yàn),所以必須要對(duì)索引代碼進(jìn)行去重.對(duì)索引代碼去重有多種方式,首先推薦的是在代碼索引之前,利用Git命令查找出,不同分支、tag與主干代碼的區(qū)別,然后只對(duì)這些有區(qū)別的代碼進(jìn)行索引.這種方法往往意味著再次遍歷全代碼庫(kù),并且效率也很低.另外一個(gè)方法是,利用 Elasticsearch的索引庫(kù)進(jìn)行去重,因?yàn)樵贓lasticsearch進(jìn)行信息檢索非常高效.判斷文件內(nèi)容的重復(fù),可以利用一個(gè)文件內(nèi)容的md5或者直接使用一個(gè)文件的Git blob(https://git-scm.com/book/en/v2/Git-Internals-Git-Objects)信息,md5或者Git blob可以唯一標(biāo)識(shí)一個(gè)文件,如果在索引庫(kù)里一個(gè)md5或者Git blob值出現(xiàn)了多個(gè)文件,那么就需要對(duì)這些文件進(jìn)行去重.

利用上述方案,在代碼數(shù)據(jù)爬蟲(chóng)解決了數(shù)據(jù)的時(shí)效性和準(zhǔn)確性后,就可以進(jìn)行真正的代碼索引了.因?yàn)樵谄髽I(yè)實(shí)際應(yīng)用中,用戶不僅可以對(duì)代碼進(jìn)行搜索,也希望對(duì)代碼庫(kù)進(jìn)行搜索,所以也需要索引代碼庫(kù)本身的屬性信息.但是代碼庫(kù)本身的屬性信息和代碼文件是完全不同的索引,需要對(duì)他們進(jìn)行分別索引.

對(duì)于代碼庫(kù)的搜索而言,圖2中代碼庫(kù)的屬性信息是非常重要的,比如代碼庫(kù)的類型,它是一個(gè)公開(kāi)的還是一個(gè)私有的代碼庫(kù),這個(gè)屬性在企業(yè)里控制代碼庫(kù)是否開(kāi)放給其他人進(jìn)行訪問(wèn)查看.再比如代碼庫(kù)編程語(yǔ)言,如果一個(gè)進(jìn)行搜索的開(kāi)發(fā)者,他本身是長(zhǎng)期開(kāi)發(fā)PHP的,那么這個(gè)開(kāi)發(fā)者在搜索字符串的時(shí)候,比如sort,他有很大的概率是在尋找PHP下的sort函數(shù),而不是C++或其他編程語(yǔ)言的,因此,索引了代碼庫(kù)的下編程語(yǔ)言有哪些這樣的數(shù)據(jù),代碼搜索系統(tǒng)就可以進(jìn)行更為精確的查找.

同樣,對(duì)于代碼搜索而言,圖2中的代碼文件的屬性也是對(duì)于搜索來(lái)說(shuō)非常重要的,比如編程語(yǔ)言的識(shí)別,同上面講的代碼庫(kù)的編程語(yǔ)言識(shí)別作用一樣.再比如最近提交作者與時(shí)間,則對(duì)豐富代碼搜索系統(tǒng)的功能很重要,使得用戶可以檢索一段時(shí)間內(nèi)的代碼,或者針對(duì)開(kāi)發(fā)者進(jìn)行搜索.其中,對(duì)代碼搜索而言,非常重要的一個(gè)屬性就是語(yǔ)法.代碼不同于自然語(yǔ)言,更加結(jié)構(gòu)化.語(yǔ)法的信息能夠幫助系統(tǒng)更容易給出用戶想要的結(jié)果,比如用戶在搜索代碼時(shí),經(jīng)常會(huì)使用函數(shù)名、類名、變量名等作為query,因此需要對(duì)所有語(yǔ)言進(jìn)行語(yǔ)法解析,獲取到代碼的語(yǔ)言元素,從而提高搜索質(zhì)量和相關(guān)性.雖然語(yǔ)法解析的工具已經(jīng)很成熟,但是實(shí)際上在企業(yè)里解析海量代碼的時(shí)候,依然困難重重,比如,C++是百度的主流編程語(yǔ)言之一,雖然使用了 CDT這樣非常成熟的工具,但它的解析還是很困難,因?yàn)槌苏Z(yǔ)法本身比較復(fù)雜(https://en.wikipedia.org/wiki/Most_vexing_parse),每個(gè)編譯單元(單個(gè) cpp文件)還需要準(zhǔn)確的給定頭文件輸入和預(yù)處理宏定義才可能進(jìn)行正確的語(yǔ)法處理,本系統(tǒng)通過(guò)解析百度內(nèi)部編譯工具Bcloud(開(kāi)源版本broc(https://github.com/baidu/broc))的中間產(chǎn)出,收集了所有頭文件和宏定義,再通過(guò)項(xiàng)目依賴關(guān)系進(jìn)行二次推測(cè)來(lái)降低CDT解析符號(hào)的錯(cuò)誤率完成索引.

Fig.2 Index data of code圖2 代碼索引數(shù)據(jù)

2.2 query變換

代碼搜索是基于文本搜索匹配的技術(shù),而用戶給出的 query和真正的代碼片段可能不盡相同[15],為了提高檢索效率和相關(guān)性,適當(dāng)?shù)貙?duì)用戶的輸入詞進(jìn)行糾錯(cuò)或調(diào)整,是每個(gè)搜索引擎所必須的.

近年來(lái),不少用于代碼搜索的query變換方法被相繼提出,比如:Wang等人[16]將用戶的意見(jiàn)納入代碼搜索引擎返回的反饋代碼片段,以優(yōu)化結(jié)果列表;Roldan-Vega等人[17]通過(guò)計(jì)算同一個(gè)詞與查詢中的詞的頻率來(lái)建議替代查詢?cè)~;Lu等人[18]通過(guò)利用查詢和 WordNet[19]中每個(gè)單詞的詞性(POS)來(lái)擴(kuò)展查詢,并提出了一種表示為PWordNet的查詢擴(kuò)展方法;Lemos等人[20]基于WordNet和與代碼相關(guān)的同義詞庫(kù)自動(dòng)擴(kuò)展測(cè)試用例.

本系統(tǒng)通過(guò)分析大量用戶行為,發(fā)現(xiàn)大部分錯(cuò)誤均為諸如下劃線(_)和短橫線(-)混淆等誤寫(xiě) 1～2個(gè)字符的情況,借鑒文獻(xiàn)[17],本系統(tǒng)保存最常引用、最常搜索點(diǎn)擊的詞為候選集合,并基于編輯距離的貝葉斯模型獲得最可能的輸入調(diào)整.算法詳細(xì)如下.

對(duì)于給定的query關(guān)鍵詞w,期望從候選集合中找到用戶實(shí)際最可能搜索的詞c,即求解條件概率最大的c:

根據(jù)貝葉斯公式(https://en.wikipedia.org/wiki/Bayes’_theorem),上式等價(jià)于

不妨假設(shè)P(w)為常數(shù),即用戶搜索任意關(guān)鍵詞概率相等,得出:

問(wèn)題轉(zhuǎn)變?yōu)榍蟪鯿的概率和w與c的某種概率關(guān)系.

· 首先構(gòu)造候選詞c集合,通過(guò)分析已索引中的數(shù)據(jù)和用戶行為統(tǒng)計(jì),將最常引用、最常搜索點(diǎn)擊的詞存為候選集,即{word:〈ref_count,click_count〉},那么P(c)=〈ref_count,click_count〉,因total_count對(duì)于所有c相等,遵循避免除法原則,P(c)=〈ref_count,click_count〉.

· 其次,w與c的概率關(guān)系,如上所述,用戶多數(shù)情況下為手寫(xiě)錯(cuò)誤或混淆某個(gè)字符,因此,系統(tǒng)通過(guò)編輯距離來(lái)模擬,即,編輯距離越近,則概率越大.此外,除了用戶最多誤寫(xiě) 1個(gè)～2個(gè)字符,加之對(duì)系統(tǒng)實(shí)時(shí)性能的約束,系統(tǒng)最終采用了編輯距離小于2的概率計(jì)算.

2.3 搜索策略

2.3.1 Elasticsearch原生排序的問(wèn)題

Elasticsearch的原始結(jié)果是根據(jù)文本匹配程度排序的(https://www.elastic.co/guide/en/elasticsearch/guide/current/scoring-theory.html),每個(gè)結(jié)果會(huì)計(jì)算 query出現(xiàn)的次數(shù)(TF)和 query在倒排索引中出現(xiàn)的次數(shù)(IDF),TF/IDF作為此結(jié)果的得分,并用來(lái)排序.但對(duì)于代碼搜索,Elasticsearch的打分能夠提供一定的參考,但文本匹配程度并不是最理想的排序方式,因?yàn)樗雎粤舜a的結(jié)構(gòu)、語(yǔ)義等[8].比如,當(dāng)搜索函數(shù)名的時(shí)候,用戶更希望獲得它的函數(shù)聲明、定義和針對(duì)該函數(shù)的單元測(cè)試等.

2.3.2 ranker模塊整體方案

如圖3所示,從Elasticsearch獲取的結(jié)果,首先根據(jù)庫(kù)歸類為多個(gè)群組;接下來(lái),根據(jù)庫(kù)本身的屬性調(diào)整分?jǐn)?shù);最后,在每個(gè)庫(kù)群組的結(jié)果中,根據(jù)語(yǔ)法策略判斷結(jié)果的語(yǔ)法屬性,最后對(duì)所有結(jié)果重新排序分頁(yè).

Fig.3 Rough sketch of search strategy圖3 搜索策略示意圖

2.3.3 根據(jù)代碼庫(kù)權(quán)重調(diào)整

結(jié)果會(huì)按照下面公式根據(jù)代碼庫(kù)權(quán)重調(diào)整:

其中,

·ScoreES為Elasticsearch的原始得分,代表結(jié)果的文本匹配程度;

·bcerti為認(rèn)證的公共基礎(chǔ)模塊(包括開(kāi)源三方庫(kù))的權(quán)重調(diào)整系數(shù),該認(rèn)證列表由公司的各編程語(yǔ)言技術(shù)委員會(huì)提供;

·bdepend為離線計(jì)算的庫(kù)之間依賴關(guān)系的權(quán)重調(diào)整系數(shù);

·bclick為用戶在搜索中點(diǎn)擊數(shù)據(jù)生成的權(quán)重調(diào)整系數(shù);

·bvote為用戶對(duì)搜索結(jié)果投票數(shù)據(jù)生成的權(quán)重調(diào)整系數(shù).

其中,bclick和bvote會(huì)在線定時(shí)根據(jù)新的數(shù)據(jù)更新權(quán)重.

2.3.4 語(yǔ)法策略

經(jīng)過(guò)代碼庫(kù)權(quán)重的調(diào)整,每組結(jié)果會(huì)根據(jù)離線生成的語(yǔ)法數(shù)據(jù)庫(kù)判斷屬性,如果能夠判斷為函數(shù)或類的聲明、定義、單元測(cè)試等,則標(biāo)記為對(duì)應(yīng)的語(yǔ)法元素.以 C++為例,同一個(gè)函數(shù)的聲明所在頭文件會(huì)優(yōu)先于對(duì)應(yīng)的源代碼文件.

2.3.5 摘要生成

為了提高用戶體驗(yàn),絕大多數(shù)搜索引擎都會(huì)為用戶提供摘要預(yù)覽,代碼搜索也不例外,通過(guò)展現(xiàn)與搜索詞最相關(guān)的代碼片段(摘要),以減少用戶尋找相關(guān)結(jié)果的時(shí)間,提高點(diǎn)擊的精準(zhǔn)率.

3 實(shí)際應(yīng)用評(píng)估

3.1 實(shí)施場(chǎng)景

本系統(tǒng)索引了百度所有的Git代碼庫(kù),總數(shù)據(jù)量為TB級(jí),平均每天新增代碼153萬(wàn)行,刪除代碼63萬(wàn)行.

系統(tǒng)功能強(qiáng)大,同時(shí)支持代碼搜索、代碼庫(kù)搜索和文件搜索.搜索結(jié)果可以根據(jù)編程語(yǔ)言歸類,支持全部主流編程語(yǔ)言.提供包括庫(kù)名、編程語(yǔ)言等的篩選.

搜索響應(yīng)時(shí)間在1s以內(nèi).搜索結(jié)果會(huì)對(duì)代碼更改保持接近實(shí)時(shí)的更新,代碼從提交到可被搜索到,間隔時(shí)間為分鐘級(jí).

本系統(tǒng)的用戶包括了大部分的百度開(kāi)發(fā)人員,每周的使用用戶數(shù)千人,每周總搜索次數(shù)達(dá)數(shù)萬(wàn)次,工作日提交代碼的開(kāi)發(fā)者平均進(jìn)行7次搜索.

3.2 搜索結(jié)果精度

3.2.1 評(píng)估指標(biāo)

信息檢索的常用評(píng)估指標(biāo)為精確率和召回率(https://en.wikipedia.org/wiki/Precision_and_recall).

· 這兩個(gè)評(píng)估指標(biāo)在某種程度上是互相矛盾的.對(duì)于搜索引擎,由于召回率相對(duì)容易滿足,一般更常用精確率作為主要評(píng)估指標(biāo).

· 評(píng)估單個(gè)搜索關(guān)鍵詞的精確率,本系統(tǒng)采用Precision@N(以下簡(jiǎn)稱P@N).即,對(duì)每個(gè)關(guān)鍵詞預(yù)設(shè)N個(gè)最佳結(jié)果,和實(shí)際搜索結(jié)果的前N項(xiàng)進(jìn)行比較,匹配數(shù)量/N作為此關(guān)鍵詞的精確率.根據(jù)定義,P@N結(jié)果在0～1之間,實(shí)際選取的N值為5.

· 評(píng)估代碼搜索的整體精確率,本系統(tǒng)采用 Mean Average Precision(https://en.wikipedia.org/wiki/Evaluation_measures_(information_retrieval)#Mean_average_precision)(以下簡(jiǎn)稱 MAP),即,對(duì)所有預(yù)設(shè)的關(guān)鍵詞得到的P@N結(jié)果,再取平均值.MAP的得分在0～1之間.

3.2.2 關(guān)鍵詞選取和設(shè)置預(yù)設(shè)最佳結(jié)果

關(guān)鍵詞從用戶實(shí)際搜索的熱門關(guān)鍵詞中選取,經(jīng)過(guò)人工選擇.

預(yù)設(shè)最佳結(jié)果同樣要避免過(guò)多的人為因素,采用用戶數(shù)據(jù)分析加人工優(yōu)化選擇方式.用戶數(shù)據(jù)包括用戶實(shí)際搜索的點(diǎn)擊數(shù)據(jù)、用戶都搜索結(jié)果的投票統(tǒng)計(jì)等.人工選擇部分,針對(duì)不同的用戶搜索模式設(shè)置不同的評(píng)估原則,見(jiàn)表1.

Table 1 Measurement principle of different types of query words表1 不同關(guān)鍵詞類別的評(píng)估原則

以上評(píng)估原則綜合參考了多種方法[2,21,22]并進(jìn)行了用戶調(diào)研,調(diào)研覆蓋了百度內(nèi)部多個(gè)部門的各種主流編程語(yǔ)言開(kāi)發(fā)人員,超過(guò)80%的受訪者認(rèn)可上述原則.系統(tǒng)上線后的統(tǒng)計(jì)信息也表明,表1中的關(guān)鍵詞類別覆蓋了超過(guò)90%的搜索.

3.2.3 一個(gè)例子

正如前文概述中所述,工程師常用的搜索大多是一個(gè) API或者類名,從線上環(huán)境取一個(gè)用戶實(shí)際 query baidu::rpc::Controller作為本次評(píng)估用例,這是baidu-rpc庫(kù)(一個(gè)C++的網(wǎng)絡(luò)服務(wù)基礎(chǔ)庫(kù),即百度對(duì)外開(kāi)源的brpc(https://github.com/brpc/brpc)的內(nèi)部版本)的一個(gè)類名,根據(jù)前述原則和代碼實(shí)際結(jié)構(gòu),設(shè)置5個(gè)期待結(jié)果及說(shuō)明見(jiàn)表2.

Table 2 Expected results of baidu::rpc::Controller表2 baidu::rpc::Controller的期待結(jié)果

實(shí)際搜索結(jié)果共計(jì)2 700余個(gè),其中前5個(gè)均為本庫(kù)內(nèi)結(jié)果,可見(jiàn)表3.

Table 3 Actual results of baidu::rpc::Controller表3 baidu::rpc::Controller的實(shí)際結(jié)果

和前述期待結(jié)果對(duì)照,共計(jì)3個(gè)匹配,此搜索詞P@N得分為0.6.

作為對(duì)比,在GitHub上進(jìn)行對(duì)應(yīng)的搜索,注意:開(kāi)源版本的brpc和公司內(nèi)baidu-rpc在namespace和代碼結(jié)構(gòu)有所區(qū)別,但基本可以對(duì)應(yīng).比如,搜索關(guān)鍵詞相應(yīng)的變更為brpc::Controller,它的聲明頭文件在brpc庫(kù)的src/brpc/controller.h

對(duì)全 GitHub代碼的搜索中(https://github.com/search?q=brpc%3A%3AController&type=Code),搜索結(jié)果的前2頁(yè)沒(méi)有任何來(lái)自brpc庫(kù)的結(jié)果.第1個(gè)來(lái)自brpc的結(jié)果出現(xiàn)在第27條.

對(duì)brpc庫(kù)內(nèi)搜索(https://github.com/brpc/brpc/search?q=brpc%3A%3AController),其前5條結(jié)果見(jiàn)表4.

Table 4 Actual results of brpc::Controller on GitHub code search表4 brpc::Controller在GitHub代碼搜索的實(shí)際結(jié)果

和前述期待結(jié)果對(duì)照,只有第3條匹配,GitHub在此搜索詞的P@N得分為0.2.

3.2.4 搜索精度得分

如表5所示,作為對(duì)比,同時(shí)列出Elasticsearch原始結(jié)果的MAP得分.

Table 5 MAP score表5 MAP得分

4 不足之處

當(dāng)前實(shí)現(xiàn)的系統(tǒng)還有幾個(gè)不足之處.

· 首先是還沒(méi)有更好地利用代碼相關(guān)的各種屬性使得搜索結(jié)果更好.代碼相對(duì)于自然語(yǔ)言有著明確的語(yǔ)法約束以及語(yǔ)義,現(xiàn)在僅能對(duì)語(yǔ)法元素在搜索結(jié)果的排序上進(jìn)行處理,但是尚未通過(guò)分析或者挖掘代碼語(yǔ)義進(jìn)行優(yōu)化搜索結(jié)果的排序.

· 其次,尚未充分利用代碼之間的調(diào)用關(guān)系.在傳統(tǒng)的信息檢索中,PageRank算法使得相關(guān)度較高的網(wǎng)頁(yè)獲得更靠前的排序[23].與之類似,代碼中的函數(shù)與函數(shù)之間、類與類之間、文件與文件之間、代碼庫(kù)與代碼庫(kù)之間,皆存在著清晰明確的調(diào)用關(guān)系.目前還沒(méi)有充分挖掘調(diào)用關(guān)系以及和代碼相關(guān)聯(lián)的數(shù)據(jù)特征,在未來(lái)可以利用知識(shí)圖譜[24]、PageRank等技術(shù)優(yōu)化代碼搜索的排序結(jié)果.

· 再次,尚未利用開(kāi)發(fā)者的自身信息.代碼不是孤立存在的,編寫(xiě)代碼的開(kāi)發(fā)者也具有獨(dú)特的特征,比如在企業(yè)里,每個(gè)開(kāi)發(fā)者的代碼權(quán)限是不一樣的,每個(gè)開(kāi)發(fā)者的技能水平也是不一樣的.

· 最后,尚未挖掘用戶行為信息.代碼搜索系統(tǒng)推出以后,大量用戶開(kāi)始使用,已經(jīng)累積大量的用戶行為數(shù)據(jù),比如在什么時(shí)間進(jìn)行了哪些搜索、在哪頁(yè)第幾個(gè)結(jié)果上進(jìn)行了點(diǎn)擊、用戶瀏覽搜索結(jié)果的停留時(shí)間、用戶查看結(jié)果并且更新了搜索詞進(jìn)行了二次搜索、用戶對(duì)結(jié)果條目進(jìn)行了滿意度評(píng)價(jià)等等.這些行為數(shù)據(jù)可以用來(lái)進(jìn)行點(diǎn)擊率預(yù)估[25],使得系統(tǒng)給出的搜索結(jié)果更加符合用戶預(yù)期.

5 相關(guān)研究工作

近年來(lái),代碼搜索領(lǐng)域的研究者提出了許多不同的搜索方法,絕大多數(shù)通過(guò)自然語(yǔ)言或者自定義的規(guī)格對(duì)用戶輸入約束,返回抽象調(diào)用序列、函數(shù)片段等不同粒度的代碼.簡(jiǎn)要介紹如下.

· Yahav[26]以部分代碼作為輸入,基于對(duì)象類型查找語(yǔ)義相關(guān)的代碼片段.

· DEEPAPI[5]使用深度學(xué)習(xí)循環(huán)神經(jīng)網(wǎng)絡(luò)的方法,對(duì)于給定的查詢語(yǔ)句,生成API用法序列.

· Sourcerer[27]在代碼實(shí)體完全限定名上使用TF-IDF技術(shù),結(jié)合right-most handside boosting技術(shù)和圖排序算法來(lái)查找功能的實(shí)現(xiàn)代碼、現(xiàn)有代碼片段的使用及包含特定屬性及模式的代碼.

· Xsnippet[10]給對(duì)象實(shí)例化任務(wù)提供示例代碼,靈活設(shè)定查詢范圍,并根據(jù)代碼片段長(zhǎng)度、出現(xiàn)頻率等進(jìn)行啟發(fā)式排序.

· Portfolio[28]利用函數(shù)調(diào)用圖建立模型,模擬編程者瀏覽及關(guān)聯(lián)其他函數(shù)行為,檢索到能夠解決查詢語(yǔ)句中描述的多項(xiàng)任務(wù)的具體函數(shù).

· Mica[29]為用戶提供更多API使用的相關(guān)信息,返回相關(guān)的API方法類和域,并根據(jù)頻率相關(guān)性排序.

· PARSEWeb[30]與Google Code Search Engine交互,通過(guò)對(duì)代碼分析,將代碼片段抽象表示成方法調(diào)用序列的形式,然后對(duì)方法調(diào)用序列進(jìn)行聚類和排序.

· Exemplar[31]結(jié)合信息檢索和程序分析技術(shù),使用方法關(guān)鍵字匹配查詢應(yīng)用的描述、源代碼以及幫助文檔.

· RACS[32]聚焦JavaScript框架代碼特征,支持自由形式的查詢語(yǔ)句,使用方法調(diào)用關(guān)系圖來(lái)描述API調(diào)用之間的復(fù)雜關(guān)系;同時(shí),從自然語(yǔ)言查詢語(yǔ)句中也捕捉相對(duì)應(yīng)的關(guān)系,提高了 JavaScript框架代碼示例搜索的準(zhǔn)確率.

· SP[8]基于用戶提供的規(guī)格描述(包括關(guān)鍵字、類或方法簽名、測(cè)試用例、約束、安全限制),檢索出滿足要求的函數(shù)及類.

· Prospector[33]工具為程序員編寫(xiě)API客戶端代碼提供幫助.用戶描述輸入/輸出類型,自動(dòng)使用API方法簽名及從大量示例客戶端代碼中挖掘到的jungloids來(lái)合成便于復(fù)用的查詢結(jié)果.

· DERECS[34]方法基于方法調(diào)用及代碼片段的結(jié)構(gòu)特征對(duì)代碼進(jìn)行描述增強(qiáng)的方法,減小了被搜索的代碼與自然語(yǔ)言查詢語(yǔ)句之間的差異,提高了搜索的準(zhǔn)確性.

本文針對(duì)企業(yè)級(jí)的海量代碼,提出了和自然語(yǔ)言搜索引擎一樣,利用簡(jiǎn)單關(guān)鍵詞進(jìn)行檢索匹配代碼的方法.

6 總結(jié)與未來(lái)工作

本文提出了企業(yè)級(jí)海量代碼下的代碼檢索與管理方案以及系統(tǒng)實(shí)現(xiàn),整個(gè)系統(tǒng)分為離線建庫(kù)端和在線搜索端:離線建庫(kù)使得代碼數(shù)據(jù)通過(guò)批量和實(shí)時(shí)的方式進(jìn)行獲取、語(yǔ)法解析、索引建庫(kù);在線搜索端接收用戶的輸入請(qǐng)求,對(duì)用戶的請(qǐng)求進(jìn)行變換,然后在Elasticsearch上進(jìn)行數(shù)據(jù)檢索,拿到Elasticsearch基于詞頻等特征給出搜索結(jié)果,利用多個(gè)排序策略再次進(jìn)行排序,最后呈現(xiàn)搜索結(jié)果.系統(tǒng)在百度上線以后,廣受百度工程師用戶的好評(píng).

然而正如在第 4節(jié)所描述的,未來(lái)還有大量的優(yōu)化工作需要進(jìn)行:首先,需要進(jìn)一步挖掘代碼本身語(yǔ)法與語(yǔ)義信息,更好地匹配用戶的搜索意圖;其次,需要挖掘代碼、文件、代碼庫(kù)、開(kāi)發(fā)者等之間的關(guān)系,利用知識(shí)圖譜、PageRank等算法優(yōu)化搜索結(jié)果;最后,用戶的行為數(shù)據(jù)是真實(shí)地指明系統(tǒng)現(xiàn)狀以及用戶想要的結(jié)果是什么,所以接下來(lái)會(huì)挖掘用戶的行為數(shù)據(jù),進(jìn)行點(diǎn)擊率預(yù)估,進(jìn)一步優(yōu)化系統(tǒng)給出的結(jié)果.

同時(shí),根據(jù)百度內(nèi)部的調(diào)查,用戶在使用后,反饋的需求和改進(jìn)包括:根據(jù)提交信息搜索、支持搜索注釋、能夠識(shí)別和過(guò)濾敏感信息(如誤遞交的帳號(hào)密碼等)等.接下來(lái)也會(huì)在這些功能上進(jìn)行完善.經(jīng)過(guò)這些措施完善后的代碼搜索工具,借助于百度研發(fā)效率云對(duì)外開(kāi)放.