W3Cschool
恭喜您成為首批注冊用戶
獲得88經(jīng)驗(yàn)值獎勵
《100億數(shù)據(jù)1萬屬性數(shù)據(jù)架構(gòu)設(shè)計(jì)》文章發(fā)布后,不少朋友對58同城自研搜索引擎E-search比較感興趣,故專門撰文體系化的聊聊搜索引擎,從宏觀到細(xì)節(jié),希望把邏輯關(guān)系講清楚,內(nèi)容比較多,分上下兩期。
主要內(nèi)容如下,本篇(上)會重點(diǎn)介紹前三章:
(1)全網(wǎng)搜索引擎架構(gòu)與流程
(2)站內(nèi)搜索引擎架構(gòu)與流程
(3)搜索原理、流程與核心數(shù)據(jù)結(jié)構(gòu)
(4)流量數(shù)據(jù)量由小到大,搜索方案與架構(gòu)變遷
(5)數(shù)據(jù)量、并發(fā)量、策略擴(kuò)展性及架構(gòu)方案
(6)實(shí)時(shí)搜索引擎核心技術(shù)
全網(wǎng)搜索的宏觀架構(gòu)長啥樣?
全網(wǎng)搜索的宏觀流程是怎么樣的?
全網(wǎng)搜索引擎的宏觀架構(gòu)如上圖,核心子系統(tǒng)主要分為三部分(粉色部分):
(1)spider爬蟲系統(tǒng)
(2)search&index建立索引與查詢索引系統(tǒng),這個(gè)系統(tǒng)又主要分為兩部分:
一部分用于生成索引數(shù)據(jù)build_index
一部分用于查詢索引數(shù)據(jù)search_index
(3)rank打分排序系統(tǒng)
核心數(shù)據(jù)主要分為兩部分(紫色部分):
(1)web網(wǎng)頁庫
(2)index索引數(shù)據(jù)
全網(wǎng)搜索引擎的業(yè)務(wù)特點(diǎn)決定了,這是一個(gè)“寫入”和“檢索”完全分離的系統(tǒng):
【寫入】
系統(tǒng)組成:由spider與search&index兩個(gè)系統(tǒng)完成
輸入:站長們生成的互聯(lián)網(wǎng)網(wǎng)頁
輸出:正排倒排索引數(shù)據(jù)
流程:如架構(gòu)圖中的1,2,3,4
(1)spider把互聯(lián)網(wǎng)網(wǎng)頁抓過來
(2)spider把互聯(lián)網(wǎng)網(wǎng)頁存儲到網(wǎng)頁庫中(這個(gè)對存儲的要求很高,要存儲幾乎整個(gè)“萬維網(wǎng)”的鏡像)
(3)build_index從網(wǎng)頁庫中讀取數(shù)據(jù),完成分詞
(4)build_index生成倒排索引
【檢索】
系統(tǒng)組成:由search&index與rank兩個(gè)系統(tǒng)完成
輸入:用戶的搜索詞
輸出:排好序的第一頁檢索結(jié)果
流程:如架構(gòu)圖中的a,b,c,d
(a)search_index獲得用戶的搜索詞,完成分詞
(b)search_index查詢倒排索引,獲得“字符匹配”網(wǎng)頁,這是初篩的結(jié)果
(c)rank對初篩的結(jié)果進(jìn)行打分排序
(d)rank對排序后的第一頁結(jié)果返回
做全網(wǎng)搜索的公司畢竟是少數(shù),絕大部分公司要實(shí)現(xiàn)的其實(shí)只是一個(gè)站內(nèi)搜索,站內(nèi)搜索引擎的宏觀架構(gòu)和全網(wǎng)搜索引擎的宏觀架構(gòu)有什么異同?
以58同城100億帖子的搜索為例,站內(nèi)搜索系統(tǒng)架構(gòu)長啥樣?站內(nèi)搜索流程是怎么樣的?
站內(nèi)搜索引擎的宏觀架構(gòu)如上圖,與全網(wǎng)搜索引擎的宏觀架構(gòu)相比,差異只有寫入的地方:
(1)全網(wǎng)搜索需要spider要被動去抓取數(shù)據(jù)
(2)站內(nèi)搜索是內(nèi)部系統(tǒng)生成的數(shù)據(jù),例如“發(fā)布系統(tǒng)”會將生成的帖子主動推給build_data系統(tǒng)
對于spider、search&index、rank三個(gè)系統(tǒng):
(1)spider和search&index是相對工程的系統(tǒng)
(2)rank是和業(yè)務(wù)、策略緊密、算法相關(guān)的系統(tǒng),搜索體驗(yàn)的差異主要在此,而業(yè)務(wù)、策略的優(yōu)化是需要時(shí)間積累的,這里的啟示是:
a)Google的體驗(yàn)比Baidu好,根本在于前者rank牛逼
b)國內(nèi)互聯(lián)網(wǎng)公司(例如360)短時(shí)間要搞一個(gè)體驗(yàn)超越Baidu的搜索引擎,是很難的,真心需要時(shí)間的積累
什么是正排索引?
什么是倒排索引?
搜索的過程是什么樣的?
會用到哪些算法與數(shù)據(jù)結(jié)構(gòu)?
提問:什么是正排索引(forward index)?
回答:由key查詢實(shí)體的過程,是正排索引。
用戶表:t_user(uid, name, passwd, age, sex),由uid查詢整行的過程,就是正排索引查詢。
網(wǎng)頁庫:t_web_page(url, page_content),由url查詢整個(gè)網(wǎng)頁的過程,也是正排索引查詢。
網(wǎng)頁內(nèi)容分詞后,page_content會對應(yīng)一個(gè)分詞后的集合list<item>。
簡易的,正排索引可以理解為Map<url, list<item>>,能夠由網(wǎng)頁快速(時(shí)間復(fù)雜度O(1))找到內(nèi)容的一個(gè)數(shù)據(jù)結(jié)構(gòu)。
提問:什么是倒排索引(inverted index)?
回答:由item查詢key的過程,是倒排索引。
對于網(wǎng)頁搜索,倒排索引可以理解為Map<item, list<url>>,能夠由查詢詞快速(時(shí)間復(fù)雜度O(1))找到包含這個(gè)查詢詞的網(wǎng)頁的數(shù)據(jù)結(jié)構(gòu)。
舉個(gè)例子,假設(shè)有3個(gè)網(wǎng)頁:
url1 -> “我愛北京”
url2 -> “我愛到家”
url3 -> “到家美好”
這是一個(gè)正排索引Map<url, page_content>。
分詞之后:
url1 -> {我,愛,北京}
url2 -> {我,愛,到家}
url3 -> {到家,美好}
這是一個(gè)分詞后的正排索引Map<url, list<item>>。
分詞后倒排索引:
我 -> {url1, url2}
愛 -> {url1, url2}
北京 -> {url1}
到家 -> {url2, url3}
美好 -> {url3}
由檢索詞item快速找到包含這個(gè)查詢詞的網(wǎng)頁Map<item, list<url>>就是倒排索引。
提問:搜索的過程是什么樣的?
假設(shè)搜索詞是“我愛”,用戶會得到什么網(wǎng)頁呢?
(1)分詞,“我愛”會分詞為{我,愛},時(shí)間復(fù)雜度為O(1)
(2)每個(gè)分詞后的item,從倒排索引查詢包含這個(gè)item的網(wǎng)頁list<url>,時(shí)間復(fù)雜度也是O(1):
我 -> {url1, url2}
愛 -> {url1, url2}
(3)求list<url>的交集,就是符合所有查詢詞的結(jié)果網(wǎng)頁,對于這個(gè)例子,{url1, url2}就是最終的查詢結(jié)果
list1和list2,求交集怎么求?
方案一:for * for,土辦法,時(shí)間復(fù)雜度O(n*n)
每個(gè)搜索詞命中的網(wǎng)頁是很多的,O(n*n)的復(fù)雜度是明顯不能接受的。倒排索引是在創(chuàng)建之初可以進(jìn)行排序預(yù)處理,問題轉(zhuǎn)化成兩個(gè)有序的list求交集,就方便多了。
有序集合1{1,3,5,7,8,9}
有序集合2{2,3,4,5,6,7}
兩個(gè)指針指向首元素,比較元素的大?。?/p>
(1)如果相同,放入結(jié)果集,隨意移動一個(gè)指針
(2)否則,移動值較小的一個(gè)指針,直到隊(duì)尾
這種方法的好處是:
(1)集合中的元素最多被比較一次,時(shí)間復(fù)雜度為O(n)
(2)多個(gè)有序集合可以同時(shí)進(jìn)行,這適用于多個(gè)分詞的item求url_id交集
這個(gè)方法就像一條拉鏈的兩邊齒輪,一一比對就像拉鏈,故稱為拉鏈法
方案三:分桶并行優(yōu)化
數(shù)據(jù)量大時(shí),url_id分桶水平切分+并行運(yùn)算是一種常見的優(yōu)化方法,如果能將list1<url_id>和list2<url_id>分成若干個(gè)桶區(qū)間,每個(gè)區(qū)間利用多線程并行求交集,各個(gè)線程結(jié)果集的并集,作為最終的結(jié)果集,能夠大大的減少執(zhí)行時(shí)間。
舉例:
有序集合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}
求交集,先進(jìn)行分桶拆分:
桶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{}
每個(gè)桶內(nèi)的數(shù)據(jù)量大大降低了,并且每個(gè)桶內(nèi)沒有重復(fù)元素,可以利用多線程并行計(jì)算:
桶1內(nèi)的集合a和集合d的交集是x{3,5,7}
桶2內(nèi)的集合b和集合e的交集是y{30, 50, 70}
桶3內(nèi)的集合c和集合d的交集是z{}
方案四:bitmap再次優(yōu)化
數(shù)據(jù)進(jìn)行了水平分桶拆分之后,每個(gè)桶內(nèi)的數(shù)據(jù)一定處于一個(gè)范圍之內(nèi),如果集合符合這個(gè)特點(diǎn),就可以使用bitmap來表示集合:
水平分桶,bitmap優(yōu)化之后,能極大提高求交集的效率,但時(shí)間復(fù)雜度仍舊是O(n)
bitmap需要大量連續(xù)空間,占用內(nèi)存較大
方案五:跳表skiplist
有序鏈表集合求交集,跳表是最常用的數(shù)據(jù)結(jié)構(gòu),它可以將有序集合求交集的復(fù)雜度由O(n)降至O(log(n))
集合1{1,2,3,4,20,21,22,23,50,60,70}
集合2{50,70}
要求交集,如果用拉鏈法,會發(fā)現(xiàn)1,2,3,4,20,21,22,23都要被無效遍歷一次,每個(gè)元素都要被比對,時(shí)間復(fù)雜度為O(n),能不能每次比對“跳過一些元素”呢?
集合1{1,2,3,4,20,21,22,23,50,60,70}建立跳表時(shí),一級只有{1,20,50}三個(gè)元素,二級與普通鏈表相同
集合2{50,70}由于元素較少,只建立了一級普通鏈表
文字很多,有宏觀,有細(xì)節(jié),對于大部分不是專門研究搜索引擎的同學(xué),記住以下幾點(diǎn)即可:
(1)全網(wǎng)搜索引擎系統(tǒng)由spider, search&index, rank三個(gè)子系統(tǒng)構(gòu)成
(2)站內(nèi)搜索引擎與全網(wǎng)搜索引擎的差異在于,少了一個(gè)spider子系統(tǒng)
(3)spider和search&index系統(tǒng)是兩個(gè)工程系統(tǒng),rank系統(tǒng)的優(yōu)化卻需要長時(shí)間的調(diào)優(yōu)和積累
(4)正排索引(forward index)是由網(wǎng)頁url_id快速找到分詞后網(wǎng)頁內(nèi)容list<item>的過程
(5)倒排索引(inverted index)是由分詞item快速尋找包含這個(gè)分詞的網(wǎng)頁list<url_id>的過程
(6)用戶檢索的過程,是先分詞,再找到每個(gè)item對應(yīng)的list<url_id>,最后進(jìn)行集合求交集的過程
(7)有序集合求交集的方法有
a)二重for循環(huán)法,時(shí)間復(fù)雜度O(n*n)
b)拉鏈法,時(shí)間復(fù)雜度O(n)
c)水平分桶,多線程并行
d)bitmap,大大提高運(yùn)算并行度,時(shí)間復(fù)雜度O(n)
e)跳表,時(shí)間復(fù)雜度為O(log(n))
a)流量數(shù)據(jù)量由小到大,搜索方案與架構(gòu)變遷-> 這個(gè)應(yīng)該很有用,很多處于不同發(fā)展階段的互聯(lián)網(wǎng)公司都在做搜索系統(tǒng),58同城經(jīng)歷過流量從0到10億,數(shù)據(jù)量從0到100億,搜索架構(gòu)也不斷演化著
b)數(shù)據(jù)量、并發(fā)量、策略擴(kuò)展性及架構(gòu)方案
c)實(shí)時(shí)搜索引擎核心技術(shù) -> 站長發(fā)布1個(gè)新網(wǎng)頁,Google如何做到15分鐘后檢索出來
Copyright©2021 w3cschool編程獅|閩ICP備15016281號-3|閩公網(wǎng)安備35020302033924號
違法和不良信息舉報(bào)電話:173-0602-2364|舉報(bào)郵箱:jubao@eeedong.com
掃描二維碼
下載編程獅App
編程獅公眾號
聯(lián)系方式:
更多建議: