【攜程旅行網(wǎng) 吳曉剛】

上周番捂，在某多多搬磚的一位朋友在微信上找我咨詢(xún)摸袁，說(shuō)他們公司一個(gè)ES集群從2.4升級(jí)到5.5以后惕虑，一個(gè)很簡(jiǎn)單的Query查詢(xún)耗時(shí)突然從幾十毫秒，變成800-1000毫秒睛挚，幾十倍的性能下降邪蛔！原始問(wèn)題鏈接:# Why my search slow?

這個(gè)查詢(xún)非常簡(jiǎn)單，就是3個(gè)過(guò)濾條件求交集而已:

{
      "from": 0,
      "size": 10,
      "query": {
      "bool": {
      "filter": [
        {
          "terms": {
            "goods_id": [
              "262628158"
            ],
            "boost": 1.0
          }
        },
        {
          "terms": {
            "status": [
              "2",
              "4"
            ],
            "boost": 1.0
          }
        },
        {
          "range": {
            "create_time": {
              "from": "1514027649",
              "to": "1514632449",
              "include_lower": true,
              "include_upper": true,
              "boost": 1.0
            }
          }
        }
      ],
      "disable_coord": false,
      "adjust_pure_negative": true,
      "boost": 1.0
    }
  },
  "sort": [
    {
      "create_time": {
        "order": "desc"
      }
    }
  ]
}

通過(guò)profile查看竞川，發(fā)現(xiàn)耗時(shí)主要在status字段過(guò)濾是build_scorer這個(gè)階段店溢。

對(duì)方同時(shí)提到叁熔，只要去掉"status":["2", "4"]這個(gè)查詢(xún)條件，速度就會(huì)恢復(fù)正常床牧。進(jìn)一步詢(xún)問(wèn)后得知荣回，查詢(xún)的索引文檔總量相當(dāng)巨大，達(dá)到16億條戈咳，而status字段只有幾個(gè)不同的數(shù)字心软，在mapping里被定義為數(shù)值型short。

我的第一反應(yīng)著蛙，status只有幾個(gè)值删铃，意味著該字段的filter得到的結(jié)果集是海量的√けぃ可能是處理這個(gè)大結(jié)果集的代價(jià)很高造成的緩慢猎唁，但是具體什么原因我一時(shí)也說(shuō)不上來(lái)。

腦子里開(kāi)始翻查ES 2.x -> 5.x升級(jí)對(duì)于數(shù)值類(lèi)型和Term Query有何重大變化顷蟆？想起來(lái)兩點(diǎn):

1. Lucene6.0引入了重新設(shè)計(jì)的數(shù)值類(lèi)型的索引結(jié)構(gòu)诫隅，不再采用倒排索，而是使用了更適合范圍查找的Block K-d Tree帐偎。 ES從5.0開(kāi)始引入這種新結(jié)構(gòu)逐纬。(參考: searching-numb3rs-in-5.0）
2. Term Query由于通常非常快削樊，從5.1.1開(kāi)始不再被緩存到Query Cache

顯然這個(gè)status這個(gè)字段不用于范圍查找豁生，字段類(lèi)型設(shè)置上keyword比number更合理。 但我也沒(méi)想明白為何number在這場(chǎng)景下查詢(xún)會(huì)慢這么多漫贞，所以我也稍稍有些懷疑2.x緩存了Term Query是造成性能差異的原因甸箱。 當(dāng)時(shí)讓朋友做了個(gè)測(cè)試，將TermQuery換成RangeQuery绕辖，被告知速度飛快摇肌，只要幾十個(gè)毫秒，并且多執(zhí)行幾次后更是快到只有幾個(gè)毫秒了仪际。(因?yàn)镽angeQuery反復(fù)執(zhí)行會(huì)被Cache起來(lái))。

隔天昵骤，朋友根據(jù)建議將status先改為keyword树碱，重新索引數(shù)據(jù)后，查詢(xún)性能奇跡般的恢復(fù)到正常变秦，所以基本可以確定和緩存無(wú)關(guān)了成榜。

恰巧社區(qū)也有人在經(jīng)歷同樣的問(wèn)題: Elastic對(duì)類(lèi)似枚舉數(shù)據(jù)的搜索性能優(yōu)化 ，看起來(lái)是個(gè)普遍現(xiàn)象蹦玫，值得研究找出問(wèn)題根源赎婚。

花了幾天的時(shí)間參閱技術(shù)文檔刘绣，也粗略讀了一下ES/Lucene相關(guān)代碼后，總算搞清楚了問(wèn)題的來(lái)龍去脈挣输。 本文將對(duì)相關(guān)技術(shù)細(xì)節(jié)做分析纬凤，然后回答下面3個(gè)問(wèn)題:

1. 為什么ES5.x里對(duì)數(shù)值型字段做TermQuery可能會(huì)很慢?
2. 為何Profile里顯示的耗時(shí)幾乎全部在build_scorer?
3. 為什么對(duì)同樣的數(shù)值型字段做RangeQuery卻又很快了？

為更好的理解這個(gè)問(wèn)題撩嚼，先談一下幾點(diǎn)預(yù)備知識(shí):

• ES2.x和5.x的數(shù)值類(lèi)型分別是如何索引的
• Block k-d tree的基本概念和Lucene實(shí)現(xiàn)
• Queries/filters執(zhí)行的先后順序及結(jié)果合并是怎樣做的

ES2.x和5.x的數(shù)值類(lèi)型分別是如何索引的

ES5.x之前用到的Lucene版本停士，實(shí)際上只能夠索引文本類(lèi)型的數(shù)據(jù)，表面上被定義為數(shù)值類(lèi)型的字段完丽，在暗地里都被轉(zhuǎn)換成了字符串恋技，編排成了倒排索引。例如:

這種結(jié)構(gòu)對(duì)于精確的數(shù)值查詢(xún)速度還是比較快的逻族，直接從倒排索引根據(jù)查找的term拿到postings list就好了蜻底。 但類(lèi)似range: [50, 100]這樣的范圍查找就比較麻煩了，Lucene在找到對(duì)應(yīng)的term后聘鳞，只能將其轉(zhuǎn)換成50 OR 51 OR 52 ... OR 100這樣Bool查詢(xún)薄辅。可想而知搁痛，這個(gè)多條件OR查詢(xún)開(kāi)銷(xiāo)很高长搀，執(zhí)行很慢。所以L(fǎng)ucene在創(chuàng)建索引的時(shí)候鸡典，會(huì)自動(dòng)產(chǎn)生一些類(lèi)似50x75 這樣的特殊Term源请，指向包含在該范圍的文檔列表，從而可以將查詢(xún)優(yōu)化成類(lèi)似50x75 OR 76x99 OR 100 這種形式彻况。但是這種優(yōu)化在字段的不同值很多谁尸，查詢(xún)范圍很大的時(shí)候，依然很無(wú)力纽甘。 因此早期版本的Lucene和ES的范圍查詢(xún)性能一只被詬病良蛮。

Lucene從6.0開(kāi)始引入了Block k-d tree來(lái)重新設(shè)計(jì)數(shù)值類(lèi)型的索引結(jié)構(gòu)，其目標(biāo)是讓數(shù)值型數(shù)據(jù)索引的結(jié)構(gòu)更緊湊悍赢，搜索速度更快决瞳。這種數(shù)據(jù)結(jié)構(gòu)是為多維數(shù)值字段設(shè)計(jì)的，可以高效的用于諸如地理位置這類(lèi)數(shù)據(jù)的快速過(guò)濾左权，但同樣適用于單維度的數(shù)值型皮胡。

Block k-d tree的基本概念和Lucene實(shí)現(xiàn)

基本思想就是將一個(gè)N維的空間，不斷選定包含值最多的維度做2分切割赏迟，反復(fù)迭代屡贺，直到切分出來(lái)的空間單元(cell)包含的值數(shù)量小于某個(gè)數(shù)值。 對(duì)于單維度的數(shù)據(jù)，實(shí)際上就是簡(jiǎn)單的對(duì)所有值做一個(gè)排序甩栈，然后反復(fù)從中間做切分泻仙，生成一個(gè)類(lèi)似于B-tree這樣的結(jié)構(gòu)。和傳統(tǒng)的B-tree不同的是量没，他的葉子結(jié)點(diǎn)存儲(chǔ)的不是單值玉转，而是一組值的集合，也就是是所謂的一個(gè)Block允蜈。每個(gè)Block內(nèi)部包含的值數(shù)量控制在512- 1024個(gè)冤吨，保證值在block之間盡量均勻分布。 其數(shù)據(jù)結(jié)構(gòu)大致看起來(lái)是這樣的:

block b-tree.jpg

Lucene將這顆B-tree的非葉子結(jié)點(diǎn)部分放在內(nèi)存里饶套，而葉子結(jié)點(diǎn)緊緊相鄰存放在磁盤(pán)上漩蟆。當(dāng)作range查詢(xún)的時(shí)候，內(nèi)存里的B-tree可以幫助快速定位到滿(mǎn)足查詢(xún)條件的葉子結(jié)點(diǎn)塊在磁盤(pán)上的位置妓蛮，之后對(duì)葉子結(jié)點(diǎn)塊的讀取幾乎都是順序的怠李。

要注意一點(diǎn)，不是簡(jiǎn)單的將拿到的所有塊合并就可以得到想要的docID結(jié)果集蛤克，因?yàn)椴樵?xún)的上下邊界不一定剛好落在兩端block的上下邊界上捺癞。 所以如果需要拿到range filter的結(jié)果集，就要對(duì)于兩端的block內(nèi)的docid做掃描构挤，將他們的值和range的上下邊界做比較髓介，挑選出match的docid集合。

Queries/filters執(zhí)行的先后順序及結(jié)果合并是怎樣做的

ES的Queries/filters執(zhí)行順序比較復(fù)雜筋现，并非按照Query里條件的排列順序來(lái)挨個(gè)執(zhí)行唐础；也不是某些人想象的那樣，每個(gè)filter/Query都獨(dú)立執(zhí)行矾飞，拿到各自的結(jié)果集以后一膨，再做結(jié)果集的合并。 在elasticsearch-query-execution-order 這篇博客里對(duì)這個(gè)主題做了比較詳細(xì)的介紹洒沦。

簡(jiǎn)單來(lái)說(shuō)豹绪，ES會(huì)先通過(guò)調(diào)用每個(gè)查詢(xún)的cost()函數(shù)估算一下該查詢(xún)的代價(jià)，然后選擇代價(jià)最小的查詢(xún)作為起點(diǎn)申眼，在其圈定的docid集合上生成一個(gè)迭代器瞒津。然后反復(fù)迭代，根據(jù)和其他條件之間是AND還是OR的關(guān)系括尸，再去決定結(jié)果集合并的方式仲智。

這個(gè)結(jié)果集的迭代，以及合并姻氨，就是上面鏈接里提到的nextdoc()和advance()等操作。 比較復(fù)雜的地方是這些操作根據(jù)數(shù)據(jù)類(lèi)型的不同和查詢(xún)類(lèi)型的不同剪验，ES都有針對(duì)性的進(jìn)行操作優(yōu)化肴焊，同樣的操作有些可能是在內(nèi)存中進(jìn)行前联，有些則可能直接在磁盤(pán)上操作。

以最常見(jiàn)的keyword字段做TermQuery為例娶眷，其cost就是Term Frequency似嗤，這個(gè)值可以直接從倒排索引讀取。 Frequency越高的Term届宠，其postings list就越長(zhǎng)烁落，迭代起來(lái)的代價(jià)就越高。 所以如果對(duì)多個(gè)TermQuery做AND合并豌注，就會(huì)選擇Frequency最低的Term伤塌，以其postings list為起點(diǎn)做迭代(nextdoc)。 Postings list是按照docid順序存放的轧铁，并且在數(shù)據(jù)結(jié)構(gòu)上還增加了跳表來(lái)加快advance()操作每聪。因此多個(gè)postings list的合并可以直接操作磁盤(pán)上的數(shù)據(jù)而不會(huì)引起過(guò)多的隨機(jī)IO，加上ES5.0以后對(duì)于索引數(shù)據(jù)采取了mmap file的方式訪(fǎng)問(wèn)齿风，熱數(shù)據(jù)讀取引發(fā)的磁盤(pán)IO愈發(fā)的少药薯。 這也是為什么5.1.1之后取消了TermQuery的cache，因?yàn)樵谔砗蚈S page cache的加持下救斑，直接合并磁盤(pán)上的postings list已經(jīng)非惩荆快了。 取消對(duì)其cache后脸候，可以減少構(gòu)造cache的開(kāi)銷(xiāo)穷娱，并且將寶貴的cache空間留給代價(jià)更高的filter，一定程度上可以提升ES整體性能纪他。

有了這些預(yù)備知識(shí)鄙煤，再來(lái)解答文首拋出的3個(gè)問(wèn)題。

1. 為什么ES5.x里對(duì)數(shù)值型字段做TermQuery可能會(huì)很慢?

首先茶袒，用戶(hù)范例查詢(xún)里還有其他更加selective的TermQuery梯刚，cost更低，因此迭代器從選擇從這個(gè)低代價(jià)的Query作為起點(diǎn)開(kāi)始執(zhí)行; 其次薪寓，因?yàn)閿?shù)值型字段在5.x里沒(méi)有采用倒排表索引亡资， 而是以value為序，將docid切分到不同的block里面向叉。對(duì)應(yīng)的锥腻，數(shù)值型字段的TermQuery被轉(zhuǎn)換為了PointRangeQuery。這個(gè)Query利用Block k-d tree進(jìn)行范圍查找速度非衬富眩快瘦黑，但是滿(mǎn)足查詢(xún)條件的docid集合在磁盤(pán)上并非向Postlings list那樣按照docid順序存放，也就無(wú)法實(shí)現(xiàn)postings list上借助跳表做蛙跳的操作。 要實(shí)現(xiàn)對(duì)docid集合的快速advance操作幸斥，只能將docid集合拿出來(lái)匹摇，做一些再處理。 這個(gè)處理過(guò)程在org.apache.lucene.search.PointRangeQuery#createWeight這個(gè)方法里可以讀取到甲葬。 這里就不貼冗長(zhǎng)的代碼了廊勃，主要邏輯就是在創(chuàng)建scorer對(duì)象的時(shí)候，順帶先將滿(mǎn)足查詢(xún)條件的docid都選出來(lái)经窖，然后構(gòu)造成一個(gè)代表docid集合的bitset坡垫，這個(gè)過(guò)程和構(gòu)造Query cache的過(guò)程非常類(lèi)似。 之后advance操作画侣，就是在這個(gè)bitset上完成的冰悠。

2. 為何Profile里顯示的耗時(shí)幾乎全部在build_scorer?

回答第一個(gè)問(wèn)題的時(shí)候提到了，如果查看PointRangeQuery的源碼棉钧，構(gòu)造scorer對(duì)象的構(gòu)造過(guò)程包含了bitset的生成過(guò)程屿脐，所以耗時(shí)的實(shí)際上是構(gòu)造一個(gè)巨大的bitset并在上面生成一個(gè)迭代器。

3. 為什么對(duì)同樣的數(shù)值型字段做RangeQuery卻又很快了?

從上面數(shù)值型字段的Block k-d tree的特性可以看出宪卿，rangeQuery的結(jié)果集比較小的時(shí)候的诵，其構(gòu)造bitset的代價(jià)很低，不管是從他開(kāi)始迭代做nextdoc()佑钾，或者從其他結(jié)果集開(kāi)始迭代西疤，對(duì)其做advance，都會(huì)比較快休溶。 但是如果rangeQuery的結(jié)果集非常巨大代赁，則構(gòu)造bitset的過(guò)程會(huì)大大延緩scorer對(duì)象的構(gòu)造過(guò)程，造成結(jié)果合并過(guò)程緩慢兽掰。
這個(gè)問(wèn)題官方其實(shí)早已經(jīng)意識(shí)到了芭碍，所以從ES5.4開(kāi)始，引入了indexOrDocValuesQuery作為對(duì)RangeQuery的優(yōu)化孽尽。（參考: better-query-planning-for-range-queries-in-elasticsearch）窖壕。 這個(gè)Query包裝了上面的PointRangeQuery和SortedSetDocValuesRangeQuery，并且會(huì)根據(jù)Rang查詢(xún)的數(shù)據(jù)集大小杉女，以及要做的合并操作類(lèi)型瞻讽，決定用哪種Query。 如果Range的代價(jià)小熏挎，可以用來(lái)引領(lǐng)合并過(guò)程速勇，就走PointRangeQuery，直接構(gòu)造bitset來(lái)進(jìn)行迭代坎拐。 而如果range的代價(jià)高烦磁，構(gòu)造bitset太慢养匈，就使用SortedSetDocValuesRangeQuery。 這個(gè)Query利用了DocValues這種全局docID序个初，并包含每個(gè)docid對(duì)應(yīng)value的數(shù)據(jù)結(jié)構(gòu)來(lái)做文檔的匹配乖寒。 當(dāng)給定一個(gè)docid的時(shí)候，一次隨機(jī)磁盤(pán)訪(fǎng)問(wèn)就可以定位到該id對(duì)應(yīng)的value院溺，從而可以判斷該doc是否match。 因此它非常適合從其他查詢(xún)條件得到的一個(gè)小結(jié)果集作為迭代起點(diǎn)磅轻，對(duì)于每個(gè)docid一次調(diào)用其內(nèi)部的matches()函數(shù)判斷匹配與否珍逸。也就是說(shuō)， 5.4新增的indexOrDocValuesQuery將Range查詢(xún)過(guò)程中的順序訪(fǎng)問(wèn)任務(wù)扔給Block k-d Tree索引聋溜，將隨機(jī)訪(fǎng)任務(wù)交給doc values谆膳。
值得注意的是目前這個(gè)優(yōu)化只針對(duì)RangeQuery！對(duì)于TermQuery撮躁，因?yàn)閷?shí)際的復(fù)雜性漱病，還未做類(lèi)似的優(yōu)化，也就導(dǎo)致同樣的字段把曼，Term和Range Query的性能差異極大杨帽。

小結(jié):

1. 在ES5.x里，一定要注意數(shù)值類(lèi)型是否需要做范圍查詢(xún)嗤军，看似數(shù)值注盈，但其實(shí)都是做Term或者Terms匹配的，應(yīng)該定義為keyword字段叙赚。典型的例子就是索引web日志時(shí)常見(jiàn)的HTTP Status code老客。
2. 如果RangeQuery的結(jié)果集很大，并且還需要和其他更加selective的查詢(xún)條件做AND的震叮，應(yīng)該升級(jí)到ES5.4+胧砰，該版本在底層引入的indexOrDocValuesQuery，可以極大提升該場(chǎng)景下RangeQuery的查詢(xún)速度苇瓣。