ElasticSearch 是什么?工作原理是怎么樣的?
現(xiàn)在有三段文本,id 分別是 0、1、2,你需要快速找到哪段文本里含有關(guān)鍵詞"xiaobai".
I like xiaobai (點(diǎn)贊)
I follow xiaobai (關(guān)注)
I forward the video (轉(zhuǎn)發(fā))
我們很容易想到,可以依次遍歷這三段文本,匹配文本內(nèi)是否含有"xiaobai",最終將符合條件的文本 ID 輸出。
在數(shù)據(jù)量小的時(shí)候,問(wèn)題不大,但如果我有上百億條這樣的數(shù)據(jù)呢?
如果依次遍歷,這一把執(zhí)行下去,比你喜歡的女生回你消息的速度,還要慢。
像這種在海量數(shù)據(jù)中,通過(guò)關(guān)鍵詞檢索出有效信息的場(chǎng)景非常常見(jiàn),比如我們網(wǎng)購(gòu)用的某寶和某東的站內(nèi)商品搜索。那么問(wèn)題就來(lái)了,怎么處理類(lèi)似的搜索場(chǎng)景呢?
好辦,沒(méi)有什么是加一層中間層不能解決的,如果有,那就再加一層。
這次我們要加的中間層是 elasticSearch。
什么是 elasticSearch
elastic Search, 也就是 es,是一個(gè)開(kāi)源的搜索引擎。
它介于應(yīng)用和數(shù)據(jù)之間,只要將數(shù)據(jù)寫(xiě)入 es,應(yīng)用就可以通過(guò)一些關(guān)鍵詞搜索到數(shù)據(jù)。效果就像某度搜索一樣。
那它是怎么做到的呢?我們從倒排索引聊起。
什么是倒排索引
回到文章開(kāi)頭的例子。依次遍歷文本匹配是否含有"xiaobai",確實(shí)低效。那有更高效的解法嗎?有,我們可以對(duì)文本進(jìn)行切分,比如"I like xiaobai"切分為"I"、"like"、"xiaobai"三部分,這個(gè)操作叫分詞,分詞后的每部分,我們稱(chēng)為一個(gè)詞項(xiàng),也就是 term。記錄詞項(xiàng)和文本 id 的關(guān)系,于是上面的三段文本就變成了下面這樣。
term | 文本 id |
I | 0, 1, 2 |
like | 0 |
xiaobai | 0, 1 |
follow | 1 |
forward | 2 |
the | 2 |
video | 2 |
當(dāng)我們想要搜索 xiaobai 的時(shí)候,只需要匹配到 xiaobai 詞項(xiàng),就可以立馬得到它所在的文檔 id 是 0 和 1。但這有個(gè)問(wèn)題,短短三句話(huà),就已經(jīng)有這么多詞項(xiàng)了,要是換成三篇文檔,那詞項(xiàng)就會(huì)多得離譜,怎么在這么多的詞項(xiàng)里匹配出 xiaobai 呢?挨個(gè)遍歷的話(huà),時(shí)間復(fù)雜度就是 O(N), 太低效了。
怎么辦呢?我們可以將詞項(xiàng)按字典序從小到大排序,通過(guò)二分查找的方法,直接將時(shí)間復(fù)雜度優(yōu)化為 O(lgN)。就像下面這樣。
term | 文檔 id |
follow | 1 |
forward | 2 |
I | 0, 1, 2 |
like | 0 |
the | 2 |
video | 2 |
xiaobai | 0, 1 |
我們將這堆排好序的詞項(xiàng),稱(chēng)為T(mén)erm Dictionary,而詞項(xiàng)對(duì)應(yīng)的文檔 id 等信息的集合,就叫 Posting List。它們共同構(gòu)成了一個(gè)用于搜索的數(shù)據(jù)結(jié)構(gòu),它就是**倒排索引(Inverted Index)**。
注意,Posting List 其實(shí)還包含詞頻和詞項(xiàng)在文本里的偏移量等信息,但為了方便理解,我在上圖中去掉了這部分內(nèi)容。
但倒排索引還有個(gè)問(wèn)題,Term Dictionary 數(shù)據(jù)量很大,放內(nèi)存并不現(xiàn)實(shí),因此必須放在磁盤(pán)中。但查詢(xún)磁盤(pán)是個(gè)較慢的過(guò)程。有優(yōu)化手段嗎?有,我們聊下 Term Index。
Term Index 是什么
我們可以發(fā)現(xiàn),詞項(xiàng)和詞項(xiàng)之間,有些前綴是一致的,比如 follow 和 forward 前面的 fo 是一致的,如果我們將部分 term 前綴提取出來(lái),像下圖一樣,就可以用更少的空間表達(dá)更多的 term?;谶@個(gè)原理,我們可以將 Term Dictionary 的部分詞項(xiàng)提取出來(lái),用這些 詞項(xiàng) 的前綴信息,構(gòu)建出一個(gè)精簡(jiǎn)的目錄樹(shù)。目錄樹(shù)的節(jié)點(diǎn)中存放這些詞項(xiàng)在磁盤(pán)中的偏移量,也就是指向磁盤(pán)中的位置。這個(gè)目錄樹(shù)結(jié)構(gòu),體積小,適合放內(nèi)存中,它就是所謂的 Term Index??梢杂盟鼇?lái)加速搜索。
當(dāng)我們需要查找某個(gè)詞項(xiàng)的時(shí)候,只需要搜索 Term Index,就能快速獲得詞項(xiàng)在 Term Dictionary 中的大概位置。再跳轉(zhuǎn)到 Term Dictionary,通過(guò)少量的檢索,定位到詞項(xiàng)內(nèi)容。
Stored Fields 是什么
到這里,搜索功能就有了。但有個(gè)問(wèn)題,前面提到的倒排索引,搜索到的是文檔 id,我們還需要拿著這個(gè) id 找到文檔內(nèi)容本身,才能返回給用戶(hù)。因此還需要有個(gè)地方,存放完整的文檔內(nèi)容,它就是 Stored Fields(行式存儲(chǔ))。
Doc Values 是什么
有了 id,我們就能從 Stored Fields 中取出文檔內(nèi)容。
但用戶(hù)經(jīng)常需要根據(jù)某個(gè)字段排序文檔,比如按時(shí)間排序或商品價(jià)格排序。但問(wèn)題就來(lái)了,這些字段散落在文檔里。也就是說(shuō),我們需要先獲取 Stored Fields 里的文檔,再提取出內(nèi)部字段進(jìn)行排序。也不是說(shuō)不行。但其實(shí)有更高效的做法。我們可以用空間換時(shí)間的思路,再構(gòu)造一個(gè)列式存儲(chǔ)結(jié)構(gòu),將散落在各個(gè)文檔的某個(gè)字段,集中存放,當(dāng)我們想對(duì)某個(gè)字段排序的時(shí)候,就只需要將這些集中存放的字段一次性讀取出來(lái),就能做到針對(duì)性地進(jìn)行排序。這個(gè)列式存儲(chǔ)結(jié)構(gòu),就是所謂的 Doc Values。
segment
在上文中,我們介紹了四種關(guān)鍵的結(jié)構(gòu):倒排索引用于搜索,Term Index 用于加速搜索,Stored Fields 用于存放文檔的原始信息,以及 Doc Values 用于排序和聚合。這些結(jié)構(gòu)共同組成了一個(gè)復(fù)合文件,也就是所謂的"segment", 它是一個(gè)具備完整搜索功能的最小單元。
lucene 是什么
我們可以用多個(gè)文檔生成一份 segment,如果新增文檔時(shí),還是寫(xiě)入到這份 segment,那就得同時(shí)更新 segment 內(nèi)部的多個(gè)數(shù)據(jù)結(jié)構(gòu),這樣并發(fā)讀寫(xiě)時(shí)性能肯定會(huì)受影響。那怎么辦呢?我們定個(gè)規(guī)矩。segment 一旦生成,則不能再被修改。如果還有新的文檔要寫(xiě)入,那就生成新的 segment。這樣老的 segment 只需要負(fù)責(zé)讀,寫(xiě)則生成新的 segment。同時(shí)保證了讀和寫(xiě)的性能。
但 segment 變多了,我們?cè)趺粗酪阉鞯臄?shù)據(jù)在哪個(gè) segment 里呢?問(wèn)題不大,并發(fā)同時(shí)讀多個(gè) segment 就好了。
但這也引入了新問(wèn)題,隨著數(shù)據(jù)量增大,segment 文件越寫(xiě)越多,文件句柄被耗盡那是指日可待啊。是的,但這個(gè)也好解決,我們可以不定期合并多個(gè)小 segment,變成一個(gè)大 segment,也就是段合并(segment merging)。這樣文件數(shù)量就可控了。
到這里,上面提到的多個(gè) segment,就共同構(gòu)成了一個(gè)單機(jī)文本檢索庫(kù),它其實(shí)就是非常有名的開(kāi)源基礎(chǔ)搜索庫(kù) lucene。不少知名搜索引擎都是基于它構(gòu)建的,比如我們今天介紹的 ES。但這個(gè) lucene 屬實(shí)過(guò)于簡(jiǎn)陋,像什么高性能,高擴(kuò)展性,高可用,它是一個(gè)都不沾。我們來(lái)看下怎么優(yōu)化它。
高性能
lucene 作為一個(gè)搜索庫(kù),可以寫(xiě)入大量數(shù)據(jù),并對(duì)外提供搜索能力。多個(gè)調(diào)用方同時(shí)讀寫(xiě)同一個(gè) lucene 必然導(dǎo)致?tīng)?zhēng)搶計(jì)算資源。搶不到資源的一方就得等待,這不純純浪費(fèi)時(shí)間嗎!有解決方案嗎?有!首先是對(duì)寫(xiě)入 lucene 的數(shù)據(jù)進(jìn)行分類(lèi),比如體育新聞和八卦新聞數(shù)據(jù)算兩類(lèi),每一類(lèi)是一個(gè) Index Name,然后根據(jù) Index Name 新增 lucene 的數(shù)量,將不同類(lèi)數(shù)據(jù)寫(xiě)入到不同的 lucene 中,讀取數(shù)據(jù)時(shí),根據(jù)需要搜索不同的 Index Name 。這就大大降低了單個(gè) lucene 的壓力。
但單個(gè) Index Name 內(nèi)數(shù)據(jù)依然可能過(guò)多,于是可以將單個(gè) Index Name 的同類(lèi)數(shù)據(jù),拆成好幾份,每份是一個(gè) shard 分片,每個(gè) shard 分片本質(zhì)上就是一個(gè)獨(dú)立的 lucene 庫(kù)。這樣我們就可以將讀寫(xiě)操作分?jǐn)偟蕉鄠€(gè) 分片 中去,大大降低了爭(zhēng)搶?zhuān)嵘讼到y(tǒng)性能。
高擴(kuò)展性
隨著 分片 變多,如果 分片 都在同一臺(tái)機(jī)器上的話(huà),就會(huì)導(dǎo)致單機(jī) cpu 和內(nèi)存過(guò)高,影響整體系統(tǒng)性能。
于是我們可以申請(qǐng)更多的機(jī)器,將 分片 分散部署在多臺(tái)機(jī)器上,這每一臺(tái)機(jī)器,就是一個(gè) Node。我們可以通過(guò)增加 Node 緩解機(jī)器 cpu 過(guò)高帶來(lái)的性能問(wèn)題。
高可用
到這里,問(wèn)題又又來(lái)了,如果其中一個(gè) Node 掛了,那 Node 里所有分片 都無(wú)法對(duì)外提供服務(wù)了。我們需要保證服務(wù)的高可用。有解決方案嗎?有,我們可以給 分片 多加幾個(gè)副本。將 分片 分為 Primary shard 和 Replica shard,也就是主分片和副本分片 。主分片會(huì)將數(shù)據(jù)同步給副本分片,副本分片既可以同時(shí)提供讀操作,還能在主分片掛了的時(shí)候,升級(jí)成新的主分片讓系統(tǒng)保持正常運(yùn)行,提高性能的同時(shí),還保證了系統(tǒng)的高可用。
Node 角色分化
搜索架構(gòu)需要支持的功能很多,既要負(fù)責(zé)管理集群,又要存儲(chǔ)管理數(shù)據(jù),還要處理客戶(hù)端的搜索請(qǐng)求。如果每個(gè) Node 都支持這幾類(lèi)功能,那當(dāng)集群有數(shù)據(jù)壓力,需要擴(kuò)容 Node 時(shí),就會(huì)順帶把其他能力也一起擴(kuò)容,但其實(shí)其他能力完全夠用,不需要跟著擴(kuò)容,這就有些浪費(fèi)了。因此我們可以將這幾類(lèi)功能拆開(kāi),給集群里的 Node 賦予角色身份,不同的角色負(fù)責(zé)不同的功能。比如負(fù)責(zé)管理集群的,叫主節(jié)點(diǎn)(Master Node), 負(fù)責(zé)存儲(chǔ)管理數(shù)據(jù)的,叫數(shù)據(jù)節(jié)點(diǎn)(Data Node), 負(fù)責(zé)接受客戶(hù)端搜索查詢(xún)請(qǐng)求的叫協(xié)調(diào)節(jié)點(diǎn)(Coordinate Node)。集群規(guī)模小的時(shí)候,一個(gè) Node 可以同時(shí)充當(dāng)多個(gè)角色,隨著集群規(guī)模變大,可以讓一個(gè) Node 一個(gè)角色。
去中心化
上面提到了主節(jié)點(diǎn),那就意味著還有個(gè)選主的過(guò)程,但現(xiàn)在每個(gè) Node 都是獨(dú)立的,需要有個(gè)機(jī)制協(xié)調(diào) Node 間的數(shù)據(jù)。我們很容易想到,可以像 kafka 那樣引入一個(gè)中心節(jié)點(diǎn) Zookeeper,但如果不想引入新節(jié)點(diǎn),還有其他更輕量的方案嗎?有,去中心化。我們可以在 Node 間引入?yún)f(xié)調(diào)模塊,用類(lèi)似一致性算法 Raft 的方式,在節(jié)點(diǎn)間互相同步數(shù)據(jù),讓所有 Node 看到的集群數(shù)據(jù)狀態(tài)都是一致的。這樣,集群內(nèi)的 Node 就能參與選主過(guò)程,還能了解到集群內(nèi)某個(gè) Node 是不是掛了等信息。
ES 是什么?
好了,到這里,當(dāng)初那個(gè)簡(jiǎn)陋的 lucene,就成了一個(gè)高性能,高擴(kuò)展性,高可用,支持持久化的分布式搜索引擎,它就是我們常說(shuō)的 elastic search,簡(jiǎn)稱(chēng) ES。它對(duì)外提供 http 接口,任何語(yǔ)言的客戶(hù)端都可以通過(guò) HTTP 接口接入 es,實(shí)現(xiàn)對(duì)數(shù)據(jù)的增刪改查。從架構(gòu)角度來(lái)看,es 給了一套方案,告訴我們?nèi)绾巫屢粋€(gè)單機(jī)系統(tǒng) lucene 變成一個(gè)分布式系統(tǒng)。
按這個(gè)思路,是不是也可以將 lucene 改成其他單機(jī)系統(tǒng),比如 mysql 數(shù)據(jù)庫(kù),或者專(zhuān)門(mén)做向量檢索的單機(jī)引擎 faiss?那以后再來(lái)個(gè) elastic mysql 或者 elastic faiss 是不是就不那么意外了,大廠內(nèi)卷晉升或者下一個(gè)明星開(kāi)源大項(xiàng)目的小提示就給到這里了。
看完 es 的架構(gòu),是不是覺(jué)得有些似曾相識(shí)?沒(méi)錯(cuò),我說(shuō)的就是我前兩期聊過(guò)的 kafka。
ES 和 Kafka 的架構(gòu)差異
如果你不了解 kakfa 的架構(gòu),可以看下我之前寫(xiě)的《Kafka 是什么?》。然后你就會(huì)發(fā)現(xiàn):
- ? es 中用于分類(lèi)消息的 Index Name,其實(shí)就是 kafka 的 topic。
- ? es 中用于對(duì) Index Name 數(shù)據(jù)分片的 Shard,其實(shí)就是 kafka 中拆分 topic 數(shù)據(jù)的 Partition。
- ? es 中用于分散部署多個(gè) shard 的 Node, 其實(shí)就相當(dāng)于 kafka 中的 broker。
es 的架構(gòu)跟 kafka 以及我們上期聊過(guò)的 rocketMQ 都非常相似,果然優(yōu)秀的架構(gòu)都是相似的,丑陋的架構(gòu)各有各的丑陋。學(xué)一套優(yōu)秀架構(gòu),就等于弄通了好幾個(gè)中間件原理,簡(jiǎn)直血賺!
現(xiàn)在我們了解完 es 的架構(gòu),再來(lái)用兩個(gè)實(shí)際例子將這些概念串起來(lái),淺看下它的工作原理。
ES 的寫(xiě)入流程
- ? 當(dāng)客戶(hù)端應(yīng)用發(fā)起數(shù)據(jù)寫(xiě)入請(qǐng)求,請(qǐng)求會(huì)先發(fā)到集群中協(xié)調(diào)節(jié)點(diǎn)。
- ? 協(xié)調(diào)節(jié)點(diǎn)根據(jù) hash 路由,判斷數(shù)據(jù)該寫(xiě)入到哪個(gè)數(shù)據(jù)節(jié)點(diǎn)里的哪個(gè)分片(Shard),找到主分片并寫(xiě)入。分片底層是 lucene,所以最終是將數(shù)據(jù)寫(xiě)入到 lucene 庫(kù)里的 segment 內(nèi),將數(shù)據(jù)固化為倒排索引和 Stored Fields 以及 Doc Values 等多種結(jié)構(gòu)。
- ? 主分片 寫(xiě)入成功后會(huì)將數(shù)據(jù)同步給 副本分片。
- ? 副本分片 寫(xiě)入完成后,主分片會(huì)響應(yīng)協(xié)調(diào)節(jié)點(diǎn)一個(gè) ACK,意思是寫(xiě)入完成。
- ? 最后,協(xié)調(diào)節(jié)點(diǎn)響應(yīng)客戶(hù)端應(yīng)用寫(xiě)入完成。
ES 的搜索流程
ES 的搜索流程分為兩個(gè)階段:分別是查詢(xún)階段(Query Phase)和獲取階段(Fetch Phase) 我們分別看下。
查詢(xún)階段。
- 當(dāng)客戶(hù)端應(yīng)用發(fā)起搜索請(qǐng)求,請(qǐng)求會(huì)先發(fā)到集群中的協(xié)調(diào)節(jié)點(diǎn)。
- 協(xié)調(diào)節(jié)點(diǎn)根據(jù) index name 的信息,可以了解到 index name 被分為了幾個(gè) 分片,以及這些分片 分散哪個(gè)數(shù)據(jù)節(jié)點(diǎn)上,將請(qǐng)求轉(zhuǎn)發(fā)到這些數(shù)據(jù)節(jié)點(diǎn)的 分片 上面。
- 搜索請(qǐng)求到達(dá)分片后,分片 底層的 lucene 庫(kù)會(huì)并發(fā)搜索多個(gè) segment,利用每個(gè) segment 內(nèi)部的倒排索引獲取到對(duì)應(yīng)文檔 id,并結(jié)合 doc values 獲得排序信息。分片將結(jié)果聚合返回給協(xié)調(diào)節(jié)點(diǎn)。
- 協(xié)調(diào)節(jié)點(diǎn)對(duì)多個(gè)分片中拿到的數(shù)據(jù)進(jìn)行一次排序聚合,舍棄大部分不需要的數(shù)據(jù)。
獲取階段。
- 協(xié)調(diào)節(jié)點(diǎn)再次拿著文檔 id 請(qǐng)求數(shù)據(jù)節(jié)點(diǎn)里的 分片,分片 底層的 lucene 庫(kù)會(huì)從 segment 內(nèi)的 Stored Fields 中取出完整文檔內(nèi)容,并返回給協(xié)調(diào)節(jié)點(diǎn)。
- 協(xié)調(diào)節(jié)點(diǎn)最終將數(shù)據(jù)結(jié)果返回給客戶(hù)端。完成整個(gè)搜索過(guò)程。
現(xiàn)在大家通了嗎?
總結(jié)
- lucene 是 es 底層的單機(jī)文本檢索庫(kù),它由多個(gè) segment 組成,每個(gè) segment 其實(shí)是由倒排索引、Term Index、Stored Fields 和 Doc Values 組成的具備完整搜索功能的最小單元。
- 將數(shù)據(jù)分類(lèi),存儲(chǔ)在 es 內(nèi)不同的 Index Name 中。
- 為了防止 Index Name 內(nèi)數(shù)據(jù)過(guò)多,引入了 Shard 的概念對(duì)數(shù)據(jù)進(jìn)行分片。提升了性能。
- 將多個(gè) shard 分布在多個(gè) Node 上,根據(jù)需要對(duì) Node 進(jìn)行擴(kuò)容,提升擴(kuò)展性。
- 將 shard 分為主分片和副本分片,主分片掛了之后由副本分片頂上,提升系統(tǒng)的可用性。
- 對(duì) Node 進(jìn)行角色分化,提高系統(tǒng)的性能和資源利用率,同時(shí)簡(jiǎn)化擴(kuò)展和維護(hù)。
- es 和 kafka 的架構(gòu)非常像,可以類(lèi)比學(xué)習(xí)。