作者：dunwu

來源：dunwu.github.io/db-tutorial/nosql/elasticsearch/elasticsearch-interview.html

集群部署

ES 部署情況：

5 節(jié)點（配置：8 核 64 G 1T），總計 320 G，5 T。

約 10+ 索引，5 分片，每日新增數(shù)據(jù)量約為 2G，4000w 條。記錄保存 30 天。

性能優(yōu)化

#?filesystem cache

你往 es 里寫的數(shù)據(jù)，實際上都寫到磁盤文件里去了，查詢的時候，操作系統(tǒng)會將磁盤文件里的數(shù)據(jù)自動緩存到?filesystem cache?里面去。

es 的搜索引擎嚴(yán)重依賴于底層的?filesystem cache?，你如果給?filesystem cache?更多的內(nèi)存，盡量讓內(nèi)存可以容納所有的?idx segment file索引數(shù)據(jù)文件，那么你搜索的時候就基本都是走內(nèi)存的，性能會非常高。

性能差距究竟可以有多大？我們之前很多的測試和壓測，如果走磁盤一般肯定上秒，搜索性能絕對是秒級別的，1 秒、5 秒、10 秒。但如果是走?filesystem cache?，是走純內(nèi)存的，那么一般來說性能比走磁盤要高一個數(shù)量級，基本上就是毫秒級的，從幾毫秒到幾百毫秒不等。

這里有個真實的案例。某個公司 es 節(jié)點有 3 臺機器，每臺機器看起來內(nèi)存很多，64G，總內(nèi)存就是?64 * 3 = 192G?。每臺機器給 es jvm heap 是?32G?，那么剩下來留給?filesystem cache?的就是每臺機器才?32G?，總共集群里給?filesystem cache?的就是?32 * 3 = 96G?內(nèi)存。而此時，整個磁盤上索引數(shù)據(jù)文件，在 3 臺機器上一共占用了?1T?的磁盤容量，es 數(shù)據(jù)量是?1T?，那么每臺機器的數(shù)據(jù)量是?300G?。這樣性能好嗎？?filesystem cache?的內(nèi)存才 100G，十分之一的數(shù)據(jù)可以放內(nèi)存，其他的都在磁盤，然后你執(zhí)行搜索操作，大部分操作都是走磁盤，性能肯定差。

歸根結(jié)底，你要讓 es 性能要好，最佳的情況下，就是你的機器的內(nèi)存，至少可以容納你的總數(shù)據(jù)量的一半。

根據(jù)我們自己的生產(chǎn)環(huán)境實踐經(jīng)驗，最佳的情況下，是僅僅在 es 中就存少量的數(shù)據(jù)，就是你要用來搜索的那些索引，如果內(nèi)存留給?filesystem cache?的是 100G，那么你就將索引數(shù)據(jù)控制在?100G?以內(nèi)，這樣的話，你的數(shù)據(jù)幾乎全部走內(nèi)存來搜索，性能非常之高，一般可以在 1 秒以內(nèi)。

比如說你現(xiàn)在有一行數(shù)據(jù)。?id,name,age ....?30 個字段。但是你現(xiàn)在搜索，只需要根據(jù)?id,name,age?三個字段來搜索。如果你傻乎乎往 es 里寫入一行數(shù)據(jù)所有的字段，就會導(dǎo)致說?90%?的數(shù)據(jù)是不用來搜索的，結(jié)果硬是占據(jù)了 es 機器上的?filesystem cache?的空間，單條數(shù)據(jù)的數(shù)據(jù)量越大，就會導(dǎo)致?filesystem cahce?能緩存的數(shù)據(jù)就越少。其實，僅僅寫入 es 中要用來檢索的少數(shù)幾個字段就可以了，比如說就寫入 es?id,name,age?三個字段，然后你可以把其他的字段數(shù)據(jù)存在 mysql/hbase 里，我們一般是建議用?es + hbase?這么一個架構(gòu)。

hbase 的特點是適用于海量數(shù)據(jù)的在線存儲，就是對 hbase 可以寫入海量數(shù)據(jù)，但是不要做復(fù)雜的搜索，做很簡單的一些根據(jù) id 或者范圍進(jìn)行查詢的這么一個操作就可以了。從 es 中根據(jù) name 和 age 去搜索，拿到的結(jié)果可能就 20 個?doc id?，然后根據(jù)?doc id?到 hbase 里去查詢每個?doc id?對應(yīng)的完整的數(shù)據(jù)，給查出來，再返回給前端。

寫入 es 的數(shù)據(jù)最好小于等于，或者是略微大于 es 的 filesystem cache 的內(nèi)存容量。然后你從 es 檢索可能就花費 20ms，然后再根據(jù) es 返回的 id 去 hbase 里查詢，查 20 條數(shù)據(jù)，可能也就耗費個 30ms，可能你原來那么玩兒，1T 數(shù)據(jù)都放 es，會每次查詢都是 5~10s，現(xiàn)在可能性能就會很高，每次查詢就是 50ms。

#?數(shù)據(jù)預(yù)熱

假如說，哪怕是你就按照上述的方案去做了，es 集群中每個機器寫入的數(shù)據(jù)量還是超過了?filesystem cache?一倍，比如說你寫入一臺機器 60G 數(shù)據(jù)，結(jié)果?filesystem cache?就 30G，還是有 30G 數(shù)據(jù)留在了磁盤上。

其實可以做數(shù)據(jù)預(yù)熱。

舉個例子，拿微博來說，你可以把一些大 V，平時看的人很多的數(shù)據(jù)，你自己提前后臺搞個系統(tǒng)，每隔一會兒，自己的后臺系統(tǒng)去搜索一下熱數(shù)據(jù)，刷到?filesystem cache?里去，后面用戶實際上來看這個熱數(shù)據(jù)的時候，他們就是直接從內(nèi)存里搜索了，很快。

或者是電商，你可以將平時查看最多的一些商品，比如說 iphone 8，熱數(shù)據(jù)提前后臺搞個程序，每隔 1 分鐘自己主動訪問一次，刷到?filesystem cache?里去。

對于那些你覺得比較熱的、經(jīng)常會有人訪問的數(shù)據(jù)，最好做一個專門的緩存預(yù)熱子系統(tǒng)，就是對熱數(shù)據(jù)每隔一段時間，就提前訪問一下，讓數(shù)據(jù)進(jìn)入?filesystem cache?里面去。這樣下次別人訪問的時候，性能一定會好很多。

#?冷熱分離

es 可以做類似于 mysql 的水平拆分，就是說將大量的訪問很少、頻率很低的數(shù)據(jù)，單獨寫一個索引，然后將訪問很頻繁的熱數(shù)據(jù)單獨寫一個索引。最好是將冷數(shù)據(jù)寫入一個索引中，然后熱數(shù)據(jù)寫入另外一個索引中，這樣可以確保熱數(shù)據(jù)在被預(yù)熱之后，盡量都讓他們留在?filesystem os cache?里，別讓冷數(shù)據(jù)給沖刷掉。

你看，假設(shè)你有 6 臺機器，2 個索引，一個放冷數(shù)據(jù)，一個放熱數(shù)據(jù)，每個索引 3 個 shard。3 臺機器放熱數(shù)據(jù) index，另外 3 臺機器放冷數(shù)據(jù) index。然后這樣的話，你大量的時間是在訪問熱數(shù)據(jù) index，熱數(shù)據(jù)可能就占總數(shù)據(jù)量的 10%，此時數(shù)據(jù)量很少，幾乎全都保留在?filesystem cache?里面了，就可以確保熱數(shù)據(jù)的訪問性能是很高的。但是對于冷數(shù)據(jù)而言，是在別的 index 里的，跟熱數(shù)據(jù) index 不在相同的機器上，大家互相之間都沒什么聯(lián)系了。如果有人訪問冷數(shù)據(jù)，可能大量數(shù)據(jù)是在磁盤上的，此時性能差點，就 10% 的人去訪問冷數(shù)據(jù)，90% 的人在訪問熱數(shù)據(jù)，也無所謂了。

#?document 模型設(shè)計

對于 MySQL，我們經(jīng)常有一些復(fù)雜的關(guān)聯(lián)查詢。在 es 里該怎么玩兒，es 里面的復(fù)雜的關(guān)聯(lián)查詢盡量別用，一旦用了性能一般都不太好。

最好是先在 Java 系統(tǒng)里就完成關(guān)聯(lián)，將關(guān)聯(lián)好的數(shù)據(jù)直接寫入 es 中。搜索的時候，就不需要利用 es 的搜索語法來完成 join 之類的關(guān)聯(lián)搜索了。

document 模型設(shè)計是非常重要的，很多操作，不要在搜索的時候才想去執(zhí)行各種復(fù)雜的亂七八糟的操作。es 能支持的操作就那么多，不要考慮用 es 做一些它不好操作的事情。如果真的有那種操作，盡量在 document 模型設(shè)計的時候，寫入的時候就完成。另外對于一些太復(fù)雜的操作，比如 join/nested/parent-child 搜索都要盡量避免，性能都很差的。

#?分頁性能優(yōu)化

es 的分頁是較坑的，為啥呢？舉個例子吧，假如你每頁是 10 條數(shù)據(jù)，你現(xiàn)在要查詢第 100 頁，實際上是會把每個 shard 上存儲的前 1000 條數(shù)據(jù)都查到一個協(xié)調(diào)節(jié)點上，如果你有個 5 個 shard，那么就有 5000 條數(shù)據(jù)，接著協(xié)調(diào)節(jié)點對這 5000 條數(shù)據(jù)進(jìn)行一些合并、處理，再獲取到最終第 100 頁的 10 條數(shù)據(jù)。

分布式的，你要查第 100 頁的 10 條數(shù)據(jù)，不可能說從 5 個 shard，每個 shard 就查 2 條數(shù)據(jù)，最后到協(xié)調(diào)節(jié)點合并成 10 條數(shù)據(jù)吧？你必須得從每個 shard 都查 1000 條數(shù)據(jù)過來，然后根據(jù)你的需求進(jìn)行排序、篩選等等操作，最后再次分頁，拿到里面第 100 頁的數(shù)據(jù)。你翻頁的時候，翻的越深，每個 shard 返回的數(shù)據(jù)就越多，而且協(xié)調(diào)節(jié)點處理的時間越長，非?？拥?。所以用 es 做分頁的時候，你會發(fā)現(xiàn)越翻到后面，就越是慢。

我們之前也是遇到過這個問題，用 es 作分頁，前幾頁就幾十毫秒，翻到 10 頁或者幾十頁的時候，基本上就要 5~10 秒才能查出來一頁數(shù)據(jù)了。

有什么解決方案嗎？

#?不允許深度分頁（默認(rèn)深度分頁性能很差）

跟產(chǎn)品經(jīng)理說，你系統(tǒng)不允許翻那么深的頁，默認(rèn)翻的越深，性能就越差。

#?類似于 app 里的推薦商品不斷下拉出來一頁一頁的

類似于微博中，下拉刷微博，刷出來一頁一頁的，你可以用?scroll api?，關(guān)于如何使用，自行上網(wǎng)搜索。

scroll 會一次性給你生成所有數(shù)據(jù)的一個快照，然后每次滑動向后翻頁就是通過游標(biāo)?scroll_id?移動，獲取下一頁下一頁這樣子，性能會比上面說的那種分頁性能要高很多很多，基本上都是毫秒級的。

但是，唯一的一點就是，這個適合于那種類似微博下拉翻頁的，不能隨意跳到任何一頁的場景。也就是說，你不能先進(jìn)入第 10 頁，然后去第 120 頁，然后又回到第 58 頁，不能隨意亂跳頁。所以現(xiàn)在很多產(chǎn)品，都是不允許你隨意翻頁的，app，也有一些網(wǎng)站，做的就是你只能往下拉，一頁一頁的翻。

初始化時必須指定?scroll?參數(shù)，告訴 es 要保存此次搜索的上下文多長時間。你需要確保用戶不會持續(xù)不斷翻頁翻幾個小時，否則可能因為超時而失敗。

除了用?scroll api?，你也可以用?search_after?來做，?search_after?的思想是使用前一頁的結(jié)果來幫助檢索下一頁的數(shù)據(jù)，顯然，這種方式也不允許你隨意翻頁，你只能一頁頁往后翻。初始化時，需要使用一個唯一值的字段作為 sort 字段。

1.1、設(shè)計階段調(diào)優(yōu)

（1）根據(jù)業(yè)務(wù)增量需求，采取基于日期模板創(chuàng)建索引，通過 roll over API 滾動索引；

（2）使用別名進(jìn)行索引管理；

（3）每天凌晨定時對索引做 force_merge 操作，以釋放空間；

（4）采取冷熱分離機制，熱數(shù)據(jù)存儲到 SSD，提高檢索效率；冷數(shù)據(jù)定期進(jìn)行 shrink 操作，以縮減存儲；

（5）采取 curator 進(jìn)行索引的生命周期管理；

（6）僅針對需要分詞的字段，合理的設(shè)置分詞器；

（7）Mapping 階段充分結(jié)合各個字段的屬性，是否需要檢索、是否需要存儲等?！?.

1.2、寫入調(diào)優(yōu)

（1）寫入前副本數(shù)設(shè)置為 0；

（2）寫入前關(guān)閉 refresh_interval 設(shè)置為-1，禁用刷新機制；

（3）寫入過程中：采取 bulk 批量寫入；

（4）寫入后恢復(fù)副本數(shù)和刷新間隔；

（5）盡量使用自動生成的 id。

1.3、查詢調(diào)優(yōu)

（1）禁用 wildcard；

（2）禁用批量 terms（成百上千的場景）；

（3）充分利用倒排索引機制，能 keyword 類型盡量 keyword；

（4）數(shù)據(jù)量大時候，可以先基于時間敲定索引再檢索；

（5）設(shè)置合理的路由機制。

1.4、其他調(diào)優(yōu)

部署調(diào)優(yōu)，業(yè)務(wù)調(diào)優(yōu)等。

上面的提及一部分，面試者就基本對你之前的實踐或者運維經(jīng)驗有所評估了。

#?工作原理

#?es 寫數(shù)據(jù)過程

• 客戶端選擇一個 node 發(fā)送請求過去，這個 node 就是?coordinating node?（協(xié)調(diào)節(jié)點）。

• coordinating node?對 document 進(jìn)行路由，將請求轉(zhuǎn)發(fā)給對應(yīng)的 node（有 primary shard）。

• 實際的 node 上的?primary shard?處理請求，然后將數(shù)據(jù)同步到?replica node?。

• coordinating node?如果發(fā)現(xiàn)?primary node?和所有?replica node?都搞定之后，就返回響應(yīng)結(jié)果給客戶端。

#?es 讀數(shù)據(jù)過程

可以通過?doc id?來查詢，會根據(jù)?doc id?進(jìn)行 hash，判斷出來當(dāng)時把?doc id?分配到了哪個 shard 上面去，從那個 shard 去查詢。

• 客戶端發(fā)送請求到任意一個 node，成為?coordinate node?。

• coordinate node?對?doc id?進(jìn)行哈希路由，將請求轉(zhuǎn)發(fā)到對應(yīng)的 node，此時會使用?round-robin?隨機輪詢算法，在?primary shard?以及其所有 replica 中隨機選擇一個，讓讀請求負(fù)載均衡。

• 接收請求的 node 返回 document 給?coordinate node?。

• coordinate node?返回 document 給客戶端。

  
  

#?es 搜索數(shù)據(jù)過程

es 最強大的是做全文檢索，就是比如你有三條數(shù)據(jù)：

你根據(jù)?java?關(guān)鍵詞來搜索，將包含?java?的?document?給搜索出來。es 就會給你返回：java 真好玩兒啊，java 好難學(xué)啊。

• 客戶端發(fā)送請求到一個?coordinate node?。

• 協(xié)調(diào)節(jié)點將搜索請求轉(zhuǎn)發(fā)到所有的 shard 對應(yīng)的?primary shard?或?replica shard?，都可以。

• query phase：每個 shard 將自己的搜索結(jié)果（其實就是一些?doc id?）返回給協(xié)調(diào)節(jié)點，由協(xié)調(diào)節(jié)點進(jìn)行數(shù)據(jù)的合并、排序、分頁等操作，產(chǎn)出最終結(jié)果。

• fetch phase：接著由協(xié)調(diào)節(jié)點根據(jù)?doc id?去各個節(jié)點上拉取實際的?document?數(shù)據(jù)，最終返回給客戶端。

寫請求是寫入 primary shard，然后同步給所有的 replica shard；讀請求可以從 primary shard 或 replica shard 讀取，采用的是隨機輪詢算法。

#?寫數(shù)據(jù)底層原理

先寫入內(nèi)存 buffer，在 buffer 里的時候數(shù)據(jù)是搜索不到的；同時將數(shù)據(jù)寫入 translog 日志文件。

如果 buffer 快滿了，或者到一定時間，就會將內(nèi)存 buffer 數(shù)據(jù)?refresh?到一個新的?segment file?中，但是此時數(shù)據(jù)不是直接進(jìn)入?segment file?磁盤文件，而是先進(jìn)入?os cache?。這個過程就是?refresh?。

每隔 1 秒鐘，es 將 buffer 中的數(shù)據(jù)寫入一個新的?segment file?，每秒鐘會產(chǎn)生一個新的磁盤文件?segment file?，這個?segment file?中就存儲最近 1 秒內(nèi) buffer 中寫入的數(shù)據(jù)。

但是如果 buffer 里面此時沒有數(shù)據(jù)，那當(dāng)然不會執(zhí)行 refresh 操作，如果 buffer 里面有數(shù)據(jù)，默認(rèn) 1 秒鐘執(zhí)行一次 refresh 操作，刷入一個新的 segment file 中。

操作系統(tǒng)里面，磁盤文件其實都有一個東西，叫做?os cache?，即操作系統(tǒng)緩存，就是說數(shù)據(jù)寫入磁盤文件之前，會先進(jìn)入?os cache?，先進(jìn)入操作系統(tǒng)級別的一個內(nèi)存緩存中去。只要?buffer?中的數(shù)據(jù)被 refresh 操作刷入?os cache?中，這個數(shù)據(jù)就可以被搜索到了。

為什么叫 es 是準(zhǔn)實時的？?NRT?，全稱?near real-time?。默認(rèn)是每隔 1 秒 refresh 一次的，所以 es 是準(zhǔn)實時的，因為寫入的數(shù)據(jù) 1 秒之后才能被看到?？梢酝ㄟ^ es 的?restful api?或者?java api?，手動執(zhí)行一次 refresh 操作，就是手動將 buffer 中的數(shù)據(jù)刷入?os cache?中，讓數(shù)據(jù)立馬就可以被搜索到。只要數(shù)據(jù)被輸入?os cache?中，buffer 就會被清空了，因為不需要保留 buffer 了，數(shù)據(jù)在 translog 里面已經(jīng)持久化到磁盤去一份了。

重復(fù)上面的步驟，新的數(shù)據(jù)不斷進(jìn)入 buffer 和 translog，不斷將?buffer?數(shù)據(jù)寫入一個又一個新的?segment file?中去，每次?refresh?完 buffer 清空，translog 保留。隨著這個過程推進(jìn)，translog 會變得越來越大。當(dāng) translog 達(dá)到一定長度的時候，就會觸發(fā)?commit?操作。

commit 操作發(fā)生第一步，就是將 buffer 中現(xiàn)有數(shù)據(jù)?refresh?到?os cache?中去，清空 buffer。然后，將一個?commit point?寫入磁盤文件，里面標(biāo)識著這個?commit point?對應(yīng)的所有?segment file?，同時強行將?os cache?中目前所有的數(shù)據(jù)都?fsync?到磁盤文件中去。最后清空?現(xiàn)有 translog 日志文件，重啟一個 translog，此時 commit 操作完成。

這個 commit 操作叫做?flush?。默認(rèn) 30 分鐘自動執(zhí)行一次?flush?，但如果 translog 過大，也會觸發(fā)?flush?。flush 操作就對應(yīng)著 commit 的全過程，我們可以通過 es api，手動執(zhí)行 flush 操作，手動將 os cache 中的數(shù)據(jù) fsync 強刷到磁盤上去。

translog 日志文件的作用是什么？你執(zhí)行 commit 操作之前，數(shù)據(jù)要么是停留在 buffer 中，要么是停留在 os cache 中，無論是 buffer 還是 os cache 都是內(nèi)存，一旦這臺機器死了，內(nèi)存中的數(shù)據(jù)就全丟了。所以需要將數(shù)據(jù)對應(yīng)的操作寫入一個專門的日志文件?translog?中，一旦此時機器宕機，再次重啟的時候，es 會自動讀取 translog 日志文件中的數(shù)據(jù)，恢復(fù)到內(nèi)存 buffer 和 os cache 中去。

translog 其實也是先寫入 os cache 的，默認(rèn)每隔 5 秒刷一次到磁盤中去，所以默認(rèn)情況下，可能有 5 秒的數(shù)據(jù)會僅僅停留在 buffer 或者 translog 文件的 os cache 中，如果此時機器掛了，會丟失?5 秒鐘的數(shù)據(jù)。但是這樣性能比較好，最多丟 5 秒的數(shù)據(jù)。也可以將 translog 設(shè)置成每次寫操作必須是直接?fsync?到磁盤，但是性能會差很多。

實際上你在這里，如果面試官沒有問你 es 丟數(shù)據(jù)的問題，你可以在這里給面試官炫一把，你說，其實 es 第一是準(zhǔn)實時的，數(shù)據(jù)寫入 1 秒后可以搜索到；可能會丟失數(shù)據(jù)的。有 5 秒的數(shù)據(jù)，停留在 buffer、translog os cache、segment file os cache 中，而不在磁盤上，此時如果宕機，會導(dǎo)致 5 秒的數(shù)據(jù)丟失。

總結(jié)一下，數(shù)據(jù)先寫入內(nèi)存 buffer，然后每隔 1s，將數(shù)據(jù) refresh 到 os cache，到了 os cache 數(shù)據(jù)就能被搜索到（所以我們才說 es 從寫入到能被搜索到，中間有 1s 的延遲）。每隔 5s，將數(shù)據(jù)寫入 translog 文件（這樣如果機器宕機，內(nèi)存數(shù)據(jù)全沒，最多會有 5s 的數(shù)據(jù)丟失），translog 大到一定程度，或者默認(rèn)每隔 30mins，會觸發(fā) commit 操作，將緩沖區(qū)的數(shù)據(jù)都 flush 到 segment file 磁盤文件中。

數(shù)據(jù)寫入 segment file 之后，同時就建立好了倒排索引。

#?刪除/更新數(shù)據(jù)底層原理

如果是刪除操作，commit 的時候會生成一個?.del?文件，里面將某個 doc 標(biāo)識為?deleted?狀態(tài)，那么搜索的時候根據(jù)?.del?文件就知道這個 doc 是否被刪除了。

如果是更新操作，就是將原來的 doc 標(biāo)識為?deleted?狀態(tài)，然后新寫入一條數(shù)據(jù)。

buffer 每 refresh 一次，就會產(chǎn)生一個?segment file?，所以默認(rèn)情況下是 1 秒鐘一個?segment file?，這樣下來?segment file?會越來越多，此時會定期執(zhí)行 merge。每次 merge 的時候，會將多個?segment file?合并成一個，同時這里會將標(biāo)識為?deleted?的 doc 給物理刪除掉，然后將新的?segment file?寫入磁盤，這里會寫一個?commit point?，標(biāo)識所有新的?segment file?，然后打開?segment file?供搜索使用，同時刪除舊的?segment file?。

#?底層 lucene

簡單來說，lucene 就是一個 jar 包，里面包含了封裝好的各種建立倒排索引的算法代碼。我們用 Java 開發(fā)的時候，引入 lucene jar，然后基于 lucene 的 api 去開發(fā)就可以了。

通過 lucene，我們可以將已有的數(shù)據(jù)建立索引，lucene 會在本地磁盤上面，給我們組織索引的數(shù)據(jù)結(jié)構(gòu)。

#?倒排索引

在搜索引擎中，每個文檔都有一個對應(yīng)的文檔 ID，文檔內(nèi)容被表示為一系列關(guān)鍵詞的集合。例如，文檔 1 經(jīng)過分詞，提取了 20 個關(guān)鍵詞，每個關(guān)鍵詞都會記錄它在文檔中出現(xiàn)的次數(shù)和出現(xiàn)位置。

那么，倒排索引就是關(guān)鍵詞到文檔?ID 的映射，每個關(guān)鍵詞都對應(yīng)著一系列的文件，這些文件中都出現(xiàn)了關(guān)鍵詞。

舉個栗子。

有以下文檔：

DocId	Doc
1	谷歌地圖之父跳槽 Facebook
2	谷歌地圖之父加盟 Facebook
3	谷歌地圖創(chuàng)始人拉斯離開谷歌加盟 Facebook
4	谷歌地圖之父跳槽 Facebook 與 Wave 項目取消有關(guān)
5	谷歌地圖之父拉斯加盟社交網(wǎng)站 Facebook

對文檔進(jìn)行分詞之后，得到以下倒排索引。

WordId	Word	DocIds
1	谷歌	1, 2, 3, 4, 5
2	地圖	1, 2, 3, 4, 5
3	之父	1, 2, 4, 5
4	跳槽	1, 4
5	Facebook	1, 2, 3, 4, 5
6	加盟	2, 3, 5
7	創(chuàng)始人	3
8	拉斯	3, 5
9	離開	3
10	與	4
..	..	..

另外，實用的倒排索引還可以記錄更多的信息，比如文檔頻率信息，表示在文檔集合中有多少個文檔包含某個單詞。

那么，有了倒排索引，搜索引擎可以很方便地響應(yīng)用戶的查詢。比如用戶輸入查詢?Facebook?，搜索系統(tǒng)查找倒排索引，從中讀出包含這個單詞的文檔，這些文檔就是提供給用戶的搜索結(jié)果。

要注意倒排索引的兩個重要細(xì)節(jié)：

• 倒排索引中的所有詞項對應(yīng)一個或多個文檔；

• 倒排索引中的詞項根據(jù)字典順序升序排列

上面只是一個簡單的栗子，并沒有嚴(yán)格按照字典順序升序排列。

#?elasticsearch 的倒排索引是什么

面試官：想了解你對基礎(chǔ)概念的認(rèn)知。

解答：通俗解釋一下就可以。

傳統(tǒng)的我們的檢索是通過文章，逐個遍歷找到對應(yīng)關(guān)鍵詞的位置。

而倒排索引，是通過分詞策略，形成了詞和文章的映射關(guān)系表，這種詞典+映射表即為倒排索引。有了倒排索引，就能實現(xiàn) o（1）時間復(fù)雜度的效率檢索文章了，極大的提高了檢索效率。

學(xué)術(shù)的解答方式：

倒排索引，相反于一篇文章包含了哪些詞，它從詞出發(fā)，記載了這個詞在哪些文檔中出現(xiàn)過，由兩部分組成——詞典和倒排表。

加分項：倒排索引的底層實現(xiàn)是基于：FST（Finite State Transducer）數(shù)據(jù)結(jié)構(gòu)。

lucene 從 4+版本后開始大量使用的數(shù)據(jù)結(jié)構(gòu)是 FST。FST 有兩個優(yōu)點：

（1）空間占用小。通過對詞典中單詞前綴和后綴的重復(fù)利用，壓縮了存儲空間；

（2）查詢速度快。O(len(str))的查詢時間復(fù)雜度。

#?3、elasticsearch 索引數(shù)據(jù)多了怎么辦，如何調(diào)優(yōu)，部署

面試官：想了解大數(shù)據(jù)量的運維能力。

解答：索引數(shù)據(jù)的規(guī)劃，應(yīng)在前期做好規(guī)劃，正所謂“設(shè)計先行，編碼在后”，這樣才能有效的避免突如其來的數(shù)據(jù)激增導(dǎo)致集群處理能力不足引發(fā)的線上客戶檢索或者其他業(yè)務(wù)受到影響。

如何調(diào)優(yōu)，正如問題 1 所說，這里細(xì)化一下：

3.1 動態(tài)索引層面

基于模板+時間+rollover api 滾動創(chuàng)建索引，舉例：設(shè)計階段定義：blog 索引的模板格式為：blogindex時間戳的形式，每天遞增數(shù)據(jù)。這樣做的好處：不至于數(shù)據(jù)量激增導(dǎo)致單個索引數(shù)據(jù)量非常大，接近于上線 2 的 32 次冪-1，索引存儲達(dá)到了 TB+甚至更大。

一旦單個索引很大，存儲等各種風(fēng)險也隨之而來，所以要提前考慮+及早避免。

3.2 存儲層面

冷熱數(shù)據(jù)分離存儲，熱數(shù)據(jù)（比如最近 3 天或者一周的數(shù)據(jù)），其余為冷數(shù)據(jù)。

對于冷數(shù)據(jù)不會再寫入新數(shù)據(jù)，可以考慮定期 force_merge 加 shrink 壓縮操作，節(jié)省存儲空間和檢索效率。

3.3 部署層面

一旦之前沒有規(guī)劃，這里就屬于應(yīng)急策略。

結(jié)合 ES 自身的支持動態(tài)擴展的特點，動態(tài)新增機器的方式可以緩解集群壓力，注意：如果之前主節(jié)點等規(guī)劃合理，不需要重啟集群也能完成動態(tài)新增的。

#?4、elasticsearch 是如何實現(xiàn) master 選舉的

面試官：想了解 ES 集群的底層原理，不再只關(guān)注業(yè)務(wù)層面了。

解答：

前置前提：

（1）只有候選主節(jié)點（master：true）的節(jié)點才能成為主節(jié)點。

（2）最小主節(jié)點數(shù)（min_master_nodes）的目的是防止腦裂。

核對了一下代碼，核心入口為 findMaster，選擇主節(jié)點成功返回對應(yīng) Master，否則返回 null。選舉流程大致描述如下：

第一步：確認(rèn)候選主節(jié)點數(shù)達(dá)標(biāo)，elasticsearch.yml 設(shè)置的值

discovery.zen.minimum_master_nodes；

第二步：比較：先判定是否具備 master 資格，具備候選主節(jié)點資格的優(yōu)先返回；

若兩節(jié)點都為候選主節(jié)點，則 id 小的值會主節(jié)點。注意這里的 id 為 string 類型。

題外話：獲取節(jié)點 id 的方法。

#?詳細(xì)描述一下 Elasticsearch 索引文檔的過程

面試官：想了解 ES 的底層原理，不再只關(guān)注業(yè)務(wù)層面了。

解答：

這里的索引文檔應(yīng)該理解為文檔寫入 ES，創(chuàng)建索引的過程。

文檔寫入包含：單文檔寫入和批量 bulk 寫入，這里只解釋一下：單文檔寫入流程。

記住官方文檔中的這個圖。

第一步：客戶寫集群某節(jié)點寫入數(shù)據(jù)，發(fā)送請求。（如果沒有指定路由/協(xié)調(diào)節(jié)點，請求的節(jié)點扮演路由節(jié)點的角色。）

第二步：節(jié)點 1 接受到請求后，使用文檔_id 來確定文檔屬于分片 0。請求會被轉(zhuǎn)到另外的節(jié)點，假定節(jié)點 3。因此分片 0 的主分片分配到節(jié)點 3 上。

第三步：節(jié)點 3 在主分片上執(zhí)行寫操作，如果成功，則將請求并行轉(zhuǎn)發(fā)到節(jié)點 1 和節(jié)點 2 的副本分片上，等待結(jié)果返回。所有的副本分片都報告成功，節(jié)點 3 將向協(xié)調(diào)節(jié)點（節(jié)點 1）報告成功，節(jié)點 1 向請求客戶端報告寫入成功。

如果面試官再問：第二步中的文檔獲取分片的過程？

回答：借助路由算法獲取，路由算法就是根據(jù)路由和文檔 id 計算目標(biāo)的分片 id 的過程。

#?詳細(xì)描述一下 Elasticsearch 搜索的過程？

面試官：想了解 ES 搜索的底層原理，不再只關(guān)注業(yè)務(wù)層面了。

解答：

搜索拆解為“query then fetch” 兩個階段。

query 階段的目的：定位到位置，但不取。

步驟拆解如下：

（1）假設(shè)一個索引數(shù)據(jù)有 5 主+1 副本 共 10 分片，一次請求會命中（主或者副本分片中）的一個。

（2）每個分片在本地進(jìn)行查詢，結(jié)果返回到本地有序的優(yōu)先隊列中。

（3）第 2）步驟的結(jié)果發(fā)送到協(xié)調(diào)節(jié)點，協(xié)調(diào)節(jié)點產(chǎn)生一個全局的排序列表。

fetch 階段的目的：取數(shù)據(jù)。

路由節(jié)點獲取所有文檔，返回給客戶端。

#?Elasticsearch 在部署時，對 Linux 的設(shè)置有哪些優(yōu)化方法

面試官：想了解對 ES 集群的運維能力。

解答：

（1）關(guān)閉緩存 swap;

（2）堆內(nèi)存設(shè)置為：Min（節(jié)點內(nèi)存/2, 32GB）;

（3）設(shè)置最大文件句柄數(shù)；

（4）線程池+隊列大小根據(jù)業(yè)務(wù)需要做調(diào)整；

（5）磁盤存儲 raid 方式——存儲有條件使用 RAID10，增加單節(jié)點性能以及避免單節(jié)點存儲故障。

# lucence 內(nèi)部結(jié)構(gòu)是什么？

面試官：想了解你的知識面的廣度和深度。

解答：

Lucene 是有索引和搜索的兩個過程，包含索引創(chuàng)建，索引，搜索三個要點?？梢曰谶@個脈絡(luò)展開一些。

# Elasticsearch 是如何實現(xiàn) Master 選舉的？

（1）Elasticsearch 的選主是 ZenDiscovery 模塊負(fù)責(zé)的，主要包含 Ping（節(jié)點之間通過這個 RPC 來發(fā)現(xiàn)彼此）和 Unicast（單播模塊包含一個主機列表以控制哪些節(jié)點需要 ping 通）這兩部分；

（2）對所有可以成為 master 的節(jié)點（node.master: true）根據(jù) nodeId 字典排序，每次選舉每個節(jié)點都把自己所知道節(jié)點排一次序，然后選出第一個（第 0 位）節(jié)點，暫且認(rèn)為它是 master 節(jié)點。

（3）如果對某個節(jié)點的投票數(shù)達(dá)到一定的值（可以成為 master 節(jié)點數(shù) n/2+1）并且該節(jié)點自己也選舉自己，那這個節(jié)點就是 master。否則重新選舉一直到滿足上述條件。

（4）補充：master 節(jié)點的職責(zé)主要包括集群、節(jié)點和索引的管理，不負(fù)責(zé)文檔級別的管理；data 節(jié)點可以關(guān)閉 http 功能*。

#?10、Elasticsearch 中的節(jié)點（比如共 20 個），其中的 10 個

選了一個 master，另外 10 個選了另一個 master，怎么辦？

（1）當(dāng)集群 master 候選數(shù)量不小于 3 個時，可以通過設(shè)置最少投票通過數(shù)量（discovery.zen.minimum_master_nodes）超過所有候選節(jié)點一半以上來解決腦裂問題；

（3）當(dāng)候選數(shù)量為兩個時，只能修改為唯一的一個 master 候選，其他作為 data 節(jié)點，避免腦裂問題。

#?客戶端在和集群連接時，如何選擇特定的節(jié)點執(zhí)行請求的？

TransportClient 利用 transport 模塊遠(yuǎn)程連接一個 elasticsearch 集群。它并不加入到集群中，只是簡單的獲得一個或者多個初始化的 transport 地址，并以 輪詢 的方式與這些地址進(jìn)行通信。

#?詳細(xì)描述一下 Elasticsearch 索引文檔的過程。

協(xié)調(diào)節(jié)點默認(rèn)使用文檔 ID 參與計算（也支持通過 routing），以便為路由提供合適的分片。

（1）當(dāng)分片所在的節(jié)點接收到來自協(xié)調(diào)節(jié)點的請求后，會將請求寫入到 MemoryBuffer，然后定時（默認(rèn)是每隔 1 秒）寫入到 Filesystem Cache，這個從 MomeryBuffer 到 Filesystem Cache 的過程就叫做 refresh；

（2）當(dāng)然在某些情況下，存在 Momery Buffer 和 Filesystem Cache 的數(shù)據(jù)可能會丟失，ES 是通過 translog 的機制來保證數(shù)據(jù)的可靠性的。其實現(xiàn)機制是接收到請求后，同時也會寫入到 translog 中 ，當(dāng) Filesystem cache 中的數(shù)據(jù)寫入到磁盤中時，才會清除掉，這個過程叫做 flush；

（3）在 flush 過程中，內(nèi)存中的緩沖將被清除，內(nèi)容被寫入一個新段，段的 fsync 將創(chuàng)建一個新的提交點，并將內(nèi)容刷新到磁盤，舊的 translog 將被刪除并開始一個新的 translog。

（4）flush 觸發(fā)的時機是定時觸發(fā)（默認(rèn) 30 分鐘）或者 translog 變得太大（默認(rèn)為 512M）時；

補充：關(guān)于 Lucene 的 Segement：

（1）Lucene 索引是由多個段組成，段本身是一個功能齊全的倒排索引。

（2）段是不可變的，允許 Lucene 將新的文檔增量地添加到索引中，而不用從頭重建索引。

（3）對于每一個搜索請求而言，索引中的所有段都會被搜索，并且每個段會消耗 CPU 的時鐘周、文件句柄和內(nèi)存。這意味著段的數(shù)量越多，搜索性能會越低。

（4）為了解決這個問題，Elasticsearch 會合并小段到一個較大的段，提交新的合并段到磁盤，并刪除那些舊的小段。

#?詳細(xì)描述一下 Elasticsearch 更新和刪除文檔的過程。

（1）刪除和更新也都是寫操作，但是 Elasticsearch 中的文檔是不可變的，因此不能被刪除或者改動以展示其變更；

（2）磁盤上的每個段都有一個相應(yīng)的.del 文件。當(dāng)刪除請求發(fā)送后，文檔并沒有真的被刪除，而是在.del 文件中被標(biāo)記為刪除。該文檔依然能匹配查詢，但是會在結(jié)果中被過濾掉。當(dāng)段合并時，在.del 文件中被標(biāo)記為刪除的文檔將不會被寫入新段。

（3）在新的文檔被創(chuàng)建時，Elasticsearch 會為該文檔指定一個版本號，當(dāng)執(zhí)行更新時，舊版本的文檔在.del 文件中被標(biāo)記為刪除，新版本的文檔被索引到一個新段。舊版本的文檔依然能匹配查詢，但是會在結(jié)果中被過濾掉。

#?詳細(xì)描述一下 Elasticsearch 搜索的過程。

（1）搜索被執(zhí)行成一個兩階段過程，我們稱之為 Query Then Fetch；

（2）在初始查詢階段時，查詢會廣播到索引中每一個分片拷貝（主分片或者副本分片）。每個分片在本地執(zhí)行搜索并構(gòu)建一個匹配文檔的大小為 from + size 的優(yōu)先隊列。

PS：在搜索的時候是會查詢 Filesystem Cache 的，但是有部分?jǐn)?shù)據(jù)還在 MemoryBuffer，所以搜索是近實時的。

（3）每個分片返回各自優(yōu)先隊列中 所有文檔的 ID 和排序值 給協(xié)調(diào)節(jié)點，它合并這些值到自己的優(yōu)先隊列中來產(chǎn)生一個全局排序后的結(jié)果列表。

（4）接下來就是 取回階段，協(xié)調(diào)節(jié)點辨別出哪些文檔需要被取回并向相關(guān)的分片提交多個 GET 請求。每個分片加載并 豐 富 文檔，如果有需要的話，接著返回文檔給協(xié)調(diào)節(jié)點。一旦所有的文檔都被取回了，協(xié)調(diào)節(jié)點返回結(jié)果給客戶端。

（5）補充：Query Then Fetch 的搜索類型在文檔相關(guān)性打分的時候參考的是本分片的數(shù)據(jù)，這樣在文檔數(shù)量較少的時候可能不夠準(zhǔn)確，DFS Query Then Fetch 增加了一個預(yù)查詢的處理，詢問 Term 和 Document frequency，這個評分更準(zhǔn)確，但是性能會變差。*

#?在 Elasticsearch 中，是怎么根據(jù)一個詞找到對應(yīng)的倒排索引的？

（1）Lucene 的索引過程，就是按照全文檢索的基本過程，將倒排表寫成此文件格式的過程。

（2）Lucene 的搜索過程，就是按照此文件格式將索引進(jìn)去的信息讀出來，然后計算每篇文檔打分(score)的過程。

# Elasticsearch 在部署時，對 Linux 的設(shè)置有哪些優(yōu)化方法？

（1）64 GB 內(nèi)存的機器是非常理想的， 但是 32 GB 和 16 GB 機器也是很常見的。少于 8 GB 會適得其反。

（2）如果你要在更快的 CPUs 和更多的核心之間選擇，選擇更多的核心更好。多個內(nèi)核提供的額外并發(fā)遠(yuǎn)勝過稍微快一點點的時鐘頻率。

（3）如果你負(fù)擔(dān)得起 SSD，它將遠(yuǎn)遠(yuǎn)超出任何旋轉(zhuǎn)介質(zhì)?；?SSD 的節(jié)點，查詢和索引性能都有提升。如果你負(fù)擔(dān)得起，SSD 是一個好的選擇。

（4）即使數(shù)據(jù)中心們近在咫尺，也要避免集群跨越多個數(shù)據(jù)中心。絕對要避免集群跨越大的地理距離。

（5）請確保運行你應(yīng)用程序的 JVM 和服務(wù)器的 JVM 是完全一樣的。在 Elasticsearch 的幾個地方，使用 Java 的本地序列化。

（6）通過設(shè)置 gateway.recover_after_nodes、gateway.expected_nodes、gateway.recover_after_time 可以在集群重啟的時候避免過多的分片交換，這可能會讓數(shù)據(jù)恢復(fù)從數(shù)個小時縮短為幾秒鐘。

（7）Elasticsearch 默認(rèn)被配置為使用單播發(fā)現(xiàn)，以防止節(jié)點無意中加入集群。只有在同一臺機器上運行的節(jié)點才會自動組成集群。最好使用單播代替組播。

（8）不要隨意修改垃圾回收器（CMS）和各個線程池的大小。

（9）把你的內(nèi)存的（少于）一半給 Lucene（但不要超過 32 GB！），通過 ES_HEAP_SIZE 環(huán)境變量設(shè)置。

（10）內(nèi)存交換到磁盤對服務(wù)器性能來說是致命的。如果內(nèi)存交換到磁盤上，一個 100 微秒的操作可能變成 10 毫秒。再想想那么多 10 微秒的操作時延累加起來。不難看出 swapping 對于性能是多么可怕。

（11）Lucene 使用了大 量 的文件。同時，Elasticsearch 在節(jié)點和 HTTP 客戶端之間進(jìn)行通信也使用了大量的套接字。所有這一切都需要足夠的文件描述符。你應(yīng)該增加你的文件描述符，設(shè)置一個很大的值，如 64,000。

補充：索引階段性能提升方法

（1）使用批量請求并調(diào)整其大?。好看闻繑?shù)據(jù) 5–15 MB 大是個不錯的起始點。

（2）存儲：使用 SSD

（3）段和合并：Elasticsearch 默認(rèn)值是 20 MB/s，對機械磁盤應(yīng)該是個不錯的設(shè)置。如果你用的是 SSD，可以考慮提高到 100–200 MB/s。如果你在做批量導(dǎo)入，完全不在意搜索，你可以徹底關(guān)掉合并限流。另外還可以增加 index.translog.flush_threshold_size 設(shè)置，從默認(rèn)的 512 MB 到更大一些的值，比如 1 GB，這可以在一次清空觸發(fā)的時候在事務(wù)日志里積累出更大的段。

（4）如果你的搜索結(jié)果不需要近實時的準(zhǔn)確度，考慮把每個索引的 index.refresh_interval 改到 30s。

（5）如果你在做大批量導(dǎo)入，考慮通過設(shè)置 index.number_of_replicas: 0 關(guān)閉副本。

#?對于 GC 方面，在使用 Elasticsearch 時要注意什么？

（1）倒排詞典的索引需要常駐內(nèi)存，無法 GC，需要監(jiān)控 data node 上 segmentmemory 增長趨勢。

（2）各類緩存，field cache, filter cache, indexing cache, bulk queue 等等，要設(shè)置合理的大小，并且要應(yīng)該根據(jù)最壞的情況來看 heap 是否夠用，也就是各類緩存全部占滿的時候，還有 heap 空間可以分配給其他任務(wù)嗎？避免采用 clear cache 等“自欺欺人”的方式來釋放內(nèi)存。

（3）避免返回大量結(jié)果集的搜索與聚合。確實需要大量拉取數(shù)據(jù)的場景，可以采用 scan & scroll api 來實現(xiàn)。

（4）cluster stats 駐留內(nèi)存并無法水平擴展，超大規(guī)模集群可以考慮分拆成多個集群通過 tribe node 連接。

（5）想知道 heap 夠不夠，必須結(jié)合實際應(yīng)用場景，并對集群的 heap 使用情況做持續(xù)的監(jiān)控。

（6）根據(jù)監(jiān)控數(shù)據(jù)理解內(nèi)存需求，合理配置各類 circuit breaker，將內(nèi)存溢出風(fēng)險降低到最低

# 18、Elasticsearch 對于大數(shù)據(jù)量（上億量級）的聚合如何實現(xiàn)？

Elasticsearch 提供的首個近似聚合是 cardinality 度量。它提供一個字段的基數(shù)，即該字段的 distinct 或者 unique 值的數(shù)目。它是基于 HLL 算法的。HLL 會先對我們的輸入作哈希運算，然后根據(jù)哈希運算的結(jié)果中的 bits 做概率估算從而得到基數(shù)。其特點是：可配置的精度，用來控制內(nèi)存的使用（更精確 ＝ 更多內(nèi)存）；小的數(shù)據(jù)集精度是非常高的；我們可以通過配置參數(shù)，來設(shè)置去重需要的固定內(nèi)存使用量。無論數(shù)千還是數(shù)十億的唯一值，內(nèi)存使用量只與你配置的精確度相關(guān)。

# 19、在并發(fā)情況下，Elasticsearch 如果保證讀寫一致？

（1）可以通過版本號使用樂觀并發(fā)控制，以確保新版本不會被舊版本覆蓋，由應(yīng)用層來處理具體的沖突；

（2）另外對于寫操作，一致性級別支持 quorum/one/all，默認(rèn)為 quorum，即只有當(dāng)大多數(shù)分片可用時才允許寫操作。但即使大多數(shù)可用，也可能存在因為網(wǎng)絡(luò)等原因?qū)е聦懭敫北臼。@樣該副本被認(rèn)為故障，分片將會在一個不同的節(jié)點上重建。

（3）對于讀操作，可以設(shè)置 replication 為 sync(默認(rèn))，這使得操作在主分片和副本分片都完成后才會返回；如果設(shè)置 replication 為 async 時，也可以通過設(shè)置搜索請求參數(shù)_preference 為 primary 來查詢主分片，確保文檔是最新版本。

# 20、如何監(jiān)控 Elasticsearch 集群狀態(tài)？

Marvel 讓你可以很簡單的通過 Kibana 監(jiān)控 Elasticsearch。你可以實時查看你的集群健康狀態(tài)和性能，也可以分析過去的集群、索引和節(jié)點指標(biāo)。

# 21、介紹下你們電商搜索的整體技術(shù)架構(gòu)。

#?介紹一下你們的個性化搜索方案？

基于 word2vec 和 Elasticsearch 實現(xiàn)個性化搜索

（1）基于 word2vec、Elasticsearch 和自定義的腳本插件，我們就實現(xiàn)了一個個性化的搜索服務(wù)，相對于原有的實現(xiàn)，新版的點擊率和轉(zhuǎn)化率都有大幅的提升；

（2）基于 word2vec 的商品向量還有一個可用之處，就是可以用來實現(xiàn)相似商品的推薦；

（3）使用 word2vec 來實現(xiàn)個性化搜索或個性化推薦是有一定局限性的，因為它只能處理用戶點擊歷史這樣的時序數(shù)據(jù)，而無法全面的去考慮用戶偏好，這個還是有很大的改進(jìn)和提升的空間；

#?是否了解字典樹？

常用字典數(shù)據(jù)結(jié)構(gòu)如下所示：

Trie 的核心思想是空間換時間，利用字符串的公共前綴來降低查詢時間的開銷以達(dá)到提高效率的目的。它有 3 個基本性質(zhì)：

1）根節(jié)點不包含字符，除根節(jié)點外每一個節(jié)點都只包含一個字符。

2）從根節(jié)點到某一節(jié)點，路徑上經(jīng)過的字符連接起來，為該節(jié)點對應(yīng)的字符串。

3）每個節(jié)點的所有子節(jié)點包含的字符都不相同。

（1）可以看到，trie 樹每一層的節(jié)點數(shù)是 26^i 級別的。所以為了節(jié)省空間，我們還可以用動態(tài)鏈表，或者用數(shù)組來模擬動態(tài)。而空間的花費，不會超過單詞數(shù) × 單詞長度。

（2）實現(xiàn)：對每個結(jié)點開一個字母集大小的數(shù)組，每個結(jié)點掛一個鏈表，使用左兒子右兄弟表示法記錄這棵樹；

（3）對于中文的字典樹，每個節(jié)點的子節(jié)點用一個哈希表存儲，這樣就不用浪費太大的空間，而且查詢速度上可以保留哈希的復(fù)雜度 O(1)。

#?拼寫糾錯是如何實現(xiàn)的？

（1）拼寫糾錯是基于編輯距離來實現(xiàn)；編輯距離是一種標(biāo)準(zhǔn)的方法，它用來表示經(jīng)過插入、刪除和替換操作從一個字符串轉(zhuǎn)換到另外一個字符串的最小操作步數(shù)；

（2）編輯距離的計算過程：比如要計算 batyu 和 beauty 的編輯距離，先創(chuàng)建一個 7×8 的表（batyu 長度為 5，coffee 長度為 6，各加 2），接著，在如下位置填入黑色數(shù)字。其他格的計算過程是取以下三個值的最小值：

如果最上方的字符等于最左方的字符，則為左上方的數(shù)字。否則為左上方的數(shù)字+1。（對于 3,3 來說為 0）

左方數(shù)字+1（對于 3,3 格來說為 2）

上方數(shù)字+1（對于 3,3 格來說為 2）

最終取右下角的值即為編輯距離的值 3。

對于拼寫糾錯，我們考慮構(gòu)造一個度量空間（Metric Space），該空間內(nèi)任何關(guān)系滿足以下三條基本條件：

d(x,y) = 0 -- 假如 x 與 y 的距離為 0，則 x=y

d(x,y) = d(y,x) -- x 到 y 的距離等同于 y 到 x 的距離

d(x,y) + d(y,z) >= d(x,z) -- 三角不等式

（1）根據(jù)三角不等式，則滿足與 query 距離在 n 范圍內(nèi)的另一個字符轉(zhuǎn) B，其與 A 的距離最大為 d+n，最小為 d-n。

（2）BK 樹的構(gòu)造就過程如下：每個節(jié)點有任意個子節(jié)點，每條邊有個值表示編輯距離。所有子節(jié)點到父節(jié)點的邊上標(biāo)注 n 表示編輯距離恰好為 n。比如，我們有棵樹父節(jié)點是”book”和兩個子節(jié)點”cake”和”books”，”book”到”books”的邊標(biāo)號 1，”book”到”cake”的邊上標(biāo)號 4。從字典里構(gòu)造好樹后，無論何時你想插入新單詞時，計算該單詞與根節(jié)點的編輯距離，并且查找數(shù)值為 d(neweord, root)的邊。遞歸得與各子節(jié)點進(jìn)行比較，直到?jīng)]有子節(jié)點，你就可以創(chuàng)建新的子節(jié)點并將新單詞保存在那。比如，插入”boo”到剛才上述例子的樹中，我們先檢查根節(jié)點，查找 d(“book”, “boo”) = 1 的邊，然后檢查標(biāo)號為 1 的邊的子節(jié)點，得到單詞”books”。我們再計算距離 d(“books”, “boo”)=2，則將新單詞插在”books”之后，邊標(biāo)號為 2。

（3）查詢相似詞如下：計算單詞與根節(jié)點的編輯距離 d，然后遞歸查找每個子節(jié)點標(biāo)號為 d-n 到 d+n（包含）的邊。假如被檢查的節(jié)點與搜索單詞的距離 d 小于 n，則返回該節(jié)點并繼續(xù)查詢。比如輸入 cape 且最大容忍距離為 1，則先計算和根的編輯距離 d(“book”, “cape”)=4，然后接著找和根節(jié)點之間編輯距離為 3 到 5 的，這個就找到了 cake 這個節(jié)點，計算 d(“cake”, “cape”)=1，滿足條件所以返回 cake，然后再找和 cake 節(jié)點編輯距離是 0 到 2 的，分別找到 cape 和 cart 節(jié)點，這樣就得到 cape 這個滿足條件的結(jié)果。

·END·

---

特別推薦一個分享架構(gòu)+算法的優(yōu)質(zhì)內(nèi)容，還沒關(guān)注的小伙伴，可以長按關(guān)注一下：

長按訂閱更多精彩▼
如有收獲，點個在看，誠摯感謝