好久沒(méi)看書(shū)了剂跟，最近閑來(lái)無(wú)事劳较，針對(duì)ES的range查詢(xún)的一些毛刺問(wèn)題，想辦法如何去降低（避免是避免不了了）浩聋。無(wú)意中在ES的官網(wǎng)看到一篇博客观蜗，光看標(biāo)題肯定就覺(jué)的吊炸天了吧。
推薦閱讀
Numeric and Date Ranges in Elasticsearch: Just Another Brick in the Wall
話說(shuō)Elasticsearch 5.2 開(kāi)始就引入了integer_range,float_range, long_range,double_range和date_range衣洁，好吧墓捻，老實(shí)說(shuō)，之前從來(lái)沒(méi)有關(guān)心過(guò)它坊夫。直到有一天突然想到一個(gè)問(wèn)題.....
需求
話說(shuō)砖第，在電商系統(tǒng)里，其實(shí)很多的庫(kù)都會(huì)有檔期的概念环凿，專(zhuān)場(chǎng)會(huì)有始末時(shí)間梧兼，商品打折也有，總結(jié)就是很多的表都會(huì)有類(lèi)似一個(gè)xxx_start_time 和xxx_end_time這兩個(gè)冬冬智听。
好羽杰，那么我們通常要篩選出一批商品列表渡紫，專(zhuān)場(chǎng)列表，上架列表等等考赛，我們就需要分別對(duì)start 和end做range操作惕澎，那自然而然就用到下面這樣的搜索：
"bool": {
"filter": [
{
"range": {
"merchand.show_from": {
"lt": "1533026579999"
}
}
},
{
"range": {
"merchan.show_to": {
"gt": "1533026579999"
}
}
}
]
}
大家都知道Lucene6.0 開(kāi)始對(duì)于數(shù)字類(lèi)型用的是一種新的BKD-Tree 數(shù)據(jù)結(jié)構(gòu)，整棵樹(shù)首先是不會(huì)完全常駐內(nèi)存颜骤，并且通過(guò)range計(jì)算時(shí)對(duì)于數(shù)據(jù)集大時(shí)唧喉，build 出 bit set 和build scorer都需要不少時(shí)間。
上面的例子忍抽，輸入的僅僅只是一個(gè)時(shí)間點(diǎn)八孝，但是其實(shí)查詢(xún)的是分別對(duì)兩個(gè)字段做了range，假如第一個(gè)range從10億集合中得出結(jié)果集是10w鸠项，耗時(shí)50ms干跛，第二個(gè)range也同樣從10億集合得出10w，耗時(shí)50ms锈锤，（這里我們暫且忽略doc values 的情形驯鳖，先討論兩個(gè)都走索引闲询，最壞情況＞妹狻）而最后做完交集可能只有幾十個(gè)doc id 命中了。那其實(shí)是不是很冤枉扭弧，因?yàn)闀r(shí)間都耗在無(wú)謂地對(duì)那些結(jié)果集做bit set 和build scorer阎姥。
后來(lái)我在想，有沒(méi)有一種類(lèi)似GeoLatLonPoint這樣的數(shù)據(jù)結(jié)構(gòu)鸽捻，可以把 start_time呼巴，end_time 都可以塞入一個(gè)字段中，那么其實(shí)我查詢(xún)的話通過(guò)對(duì)區(qū)間來(lái)做結(jié)果集篩查御蒲，往往就能大大壓縮return 的集合衣赶。
那么結(jié)果就是如開(kāi)篇所示，用ES的long_range,或者date_range 來(lái)解決這類(lèi)問(wèn)題厚满。那么上面的類(lèi)型merchand.show_from``merchand.show_to 可能就變成了 merchand.show_period 字段府瞄，那么要索引這個(gè)字段的時(shí)候可能就要用類(lèi)似 merchand.show_period:{"gte":"2015-10-31","lte":"2015-11-1"}。
好了碘箍，這里就不做什么quick start example了遵馆，這不是文章的重點(diǎn)，有興趣的照著上面文章做就好了丰榴。下面來(lái)一起去探討一下ES這種類(lèi)型在Lucene 6的實(shí)現(xiàn)货邓。
The Evolution of Numeric Range Filters in Apache Lucene
推薦閱讀
The Evolution of Numeric Range Filters in Apache Lucene
我們先暫且飛回去2年前的2016 年，在Lucene 6.0 出來(lái)之前四濒，任何東西都是text换况，包括數(shù)字职辨，舉個(gè)例子，17复隆，2拨匆，23，要搜大于10怎么辦呢挽拂？ 2肯定會(huì)被檢索出來(lái)的惭每，那Lucene的折中就是在前面補(bǔ)0，最后變成了 017亏栈，002台腥，023，這樣對(duì)詞條多range就不會(huì)錯(cuò)了绒北，但是性能可想而知了黎侈。
然后到了后來(lái)，隨著地圖等應(yīng)用闷游，在Lucene 有了一種稱(chēng)為 geo-spatial search峻汉，Lucene 增加了一種稱(chēng)為 block KD (BKD) tree data structure, for fast multi-dimensional point filtering這群人發(fā)現(xiàn)，這種數(shù)據(jù)結(jié)構(gòu)在做這種二維地理位置搜索脐往，臨近距離查詢(xún)等搜索時(shí)休吠，性能非常好。
It offers box, distance (Haversine earth surface distance) and polygon filtering, and even includes a unique (versus Lucene's other geo-spatial implementations) very fast nearest neighbor search, something KD-trees are especially good at. It also offers fast distance sorting, using doc values. Lucene's nightly geo-spatial benchmarks compare the performance of our three fastest geo-spatial implementations.
又再后來(lái)业簿，這群人又發(fā)現(xiàn)瘤礁，這個(gè)結(jié)構(gòu)不僅是做2D，3D Search 性能很好梅尤，并且做1D numerics case 性能也是非常好
While the initial goal was fast geo-spatial 2D (latitude, longitude) and 3D (x, y, z) searching, we quickly realized that this data structure also works very well for the 1D numerics case.
那么結(jié)果你就猜到了柜思，Lucene 6 開(kāi)始，BKD Tree 就作為number type 的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)巷燥。
深入Lucene的 BKD Tree
這節(jié)我們就看看Lucene 的BKD Tree是怎么實(shí)現(xiàn)的赡盘，用Lucene團(tuán)隊(duì)說(shuō)就是：
The k-d tree variant we implemented is the block k-d tree which is specifically designed for efficient IO, such that most of the data structure resides in on-disk blocks, with a small in-heap binary tree index structure to locate the blocks at search time
傳統(tǒng)的 k-d tree的話，最大弊端就是插入一個(gè)節(jié)點(diǎn)時(shí)需要重新均衡缰揪，為了解決這個(gè)問(wèn)題所以Lucene采用了Block 的K-D tree
這里要知道的一個(gè)概念是陨享，整個(gè)樹(shù)是不會(huì)常駐HEAP的，每個(gè)節(jié)點(diǎn)作為葉子存在于block邀跃，并且HEAP先只保留文件的起始位移霉咨，起始每一個(gè)節(jié)點(diǎn)的下面也是一個(gè)完整的K-D tree，這就可以解決局部update的問(wèn)題拍屑。
具體到HEAP中的一個(gè)節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)途戒，用的是一個(gè)編碼過(guò)的byte[], 總共長(zhǎng)度是16個(gè)字節(jié)，,每一個(gè)的byte用的是unsigned 256僵驰，Lucene當(dāng)前支持最大是4維度喷斋，每個(gè)維度支持一個(gè)區(qū)間唁毒，也就是說(shuō)如果是二維的表達(dá)，那么將會(huì)是用第1星爪，2個(gè)bytes表示 二維的第一個(gè)數(shù)字浆西，第5，6字節(jié)表達(dá)二維的第二個(gè)數(shù)字顽腾，維度升高以此類(lèi)推近零。這個(gè)例子將在下面會(huì)再介紹。
Dimensional points are more general than numeric tries because arbitrary
byte[](unsigned, base 256) values up to 16 bytes in length and up to 8 dimensions can be indexed, versus just 4 or 8 byte numeric values with numeric tries. This makes support for IPv6 internet addresses and up to 128 bitBigIntegereasy.
查詢(xún)的時(shí)候抄肖，其實(shí)也是同樣的在一棵樹(shù)里找區(qū)間的一個(gè)過(guò)程久信，如果這個(gè)值還是小于當(dāng)前子樹(shù)的邊界，那就再去load sub tree漓摩，以此類(lèi)推裙士，那么在一維數(shù)字里，其實(shí)就轉(zhuǎn)變成了找數(shù)字區(qū)間的過(guò)程管毙，這個(gè)過(guò)程很容易展開(kāi)成 2D腿椎， 3D甚至4D的情形，比如2D的搜索夭咬，可以在1D的區(qū)間里每一個(gè)元素相對(duì)于第2維都是一個(gè)垂直的維度轉(zhuǎn)換啃炸。
這里同樣提到一點(diǎn)，之所以在范圍查詢(xún) BKD tree 搜索非持宀海快肮帐，是因?yàn)樵谠绞敲芗膮^(qū)域咖驮，子樹(shù)包好的子葉子會(huì)越多边器，這樣略過(guò)（或者說(shuō)橫跨過(guò)）一整片區(qū)域就會(huì)越快
K-d trees are fast because they naturally adapt to each data set's particular distribution, using small leaf blocks where the indexed values are dense: notice how central London, where there is a higher density of points, is assigned smaller leaf cells. K-d trees also naturally find the right tradeoff of how deeply to recurse, by splitting up the dimensional space, versus at what point simply scanning the full-precision values in one cell is appropriate. This is in contrast to legacy numeric fields which always index the same precision levels for every value (4 terms for a long value, by default) regardless of how the points are distributed.
更具體的 BKD tree的搜索算法我并沒(méi)有深入去Lucene的源碼去看，我找到另外一個(gè)兄弟寫(xiě)了一個(gè)類(lèi)似的算法演繹我覺(jué)得已經(jīng)很好理解了托修，大家可以看看
https://github.com/zzboy/lucene/blob/master/lucene_6_bkd_tree.md
這里截取其中一個(gè)高維查詢(xún)過(guò)程高維場(chǎng)景
有了一維場(chǎng)景忘巧，非常容易推廣到高維的場(chǎng)景。
構(gòu)建過(guò)程
step 1: 選擇一個(gè)維度睦刃，將數(shù)據(jù)按照該維度排序砚嘴，數(shù)據(jù)量大的話使用外排序。 step 2: 選取中位數(shù)作為根節(jié)點(diǎn)的split value涩拙，除此以外际长，根節(jié)點(diǎn)需要記錄下是哪一個(gè)維度的split value。 step 3: 前面兩步將數(shù)據(jù)集劃分成兩部分兴泥，分別對(duì)兩部分重復(fù)step 1工育、step 2，構(gòu)造根節(jié)點(diǎn)的左右子樹(shù)搓彻。 step 4: 持續(xù)上述遞歸構(gòu)造過(guò)程直到節(jié)點(diǎn)關(guān)聯(lián)的數(shù)據(jù)數(shù)集數(shù)量小于某個(gè)閾值如绸。
回過(guò)來(lái)看ES的 long_range的實(shí)現(xiàn)
在上面已經(jīng)說(shuō)過(guò)了嘱朽，每一個(gè)point的表達(dá)是用16字節(jié)表示，在ES的一個(gè)long_range里怔接，其實(shí)分別用了下面的d1,D1來(lái)表示一個(gè)插入數(shù)據(jù)的min和max搪泳，也就是一個(gè)一維的range 在Lucene里其實(shí)用了一個(gè)2維的point來(lái)去保存，這個(gè)和GeoPoint其實(shí)是一個(gè)概念扼脐，如下面這個(gè)例子岸军，如果我插入了一個(gè)range 是5~15 的period，那么它就是保存在下面的的
和D1構(gòu)成的point
ES的查詢(xún)模式其實(shí)并沒(méi)有自己實(shí)現(xiàn)了什么瓦侮，從代碼來(lái)看凛膏，都只是對(duì)Lucene的封裝，用的也是Lucene自帶的幾種模式：WITHIN脏榆，CONTAINS等猖毫；根據(jù)模式最終會(huì)轉(zhuǎn)換成一些原生查詢(xún)。
性能
既然知道了ES的幾種range其實(shí)用的是它的2D運(yùn)算結(jié)構(gòu)须喂，那么就看看 Lucene BKD Tree的2D性能如何吁断。
詳細(xì)測(cè)試從https://www.elastic.co/blog/lucene-points-6.0 看
從圖中看，和GeoPoint一樣坞生，除了性能提高仔役，其實(shí)占用空間和占用HEAP來(lái)看都是非常有優(yōu)勢(shì)。
1D的性能我就不介紹了是己。
回到原始需求來(lái)
回到我最初的這個(gè)需求來(lái)又兵，從上面blog中提到說(shuō)提到的性能提升來(lái)，和我所糾結(jié)的這個(gè)問(wèn)題似乎沒(méi)有太大的關(guān)系卒废，我的初衷是如何能避免2次無(wú)謂的range出大量的臨時(shí)數(shù)據(jù)沛厨，而從ES的long_range 使用的是BKD Tree 的2D保存實(shí)現(xiàn)來(lái)看，對(duì)于區(qū)間范圍查詢(xún)可能并沒(méi)有剩掉多少運(yùn)算摔认∧嫫ぃ或者這么說(shuō)，Lucene的BKD Tree它在解決特定的場(chǎng)景確實(shí)能有非常好的性能参袱，但是并不一定是我這個(gè)場(chǎng)景电谣。
當(dāng)然，我目前還沒(méi)有對(duì)生產(chǎn)的數(shù)據(jù)重構(gòu)做一個(gè)該場(chǎng)景下的龐大的索引去測(cè)一下性能抹蚀，所以下面的觀點(diǎn)是我的一些猜測(cè)：
- 從Lucene實(shí)現(xiàn)知道剿牺，其實(shí)這個(gè)結(jié)構(gòu)并不是常駐HEAP的，那么分別保存兩個(gè)Tree 和通過(guò)2D結(jié)構(gòu)保存到同一個(gè)Tree环壤，不關(guān)加載還是運(yùn)算晒来，我覺(jué)得性能都應(yīng)該是會(huì)有提升的，這一點(diǎn)很容易理解镐捧。
- 就看Lucene的實(shí)現(xiàn)了潜索，通過(guò)在同一個(gè)樹(shù)上搜索臭增，其實(shí)很多東西可以?xún)?yōu)化，至少我這么認(rèn)為竹习，舉個(gè)例子誊抛，就拿
long_range來(lái)說(shuō)，假設(shè)我保存的是1-3整陌，2-4拗窃，3-5，4-6泌辫，5-7随夸，6-8假入我搜索2-5那么如果是老式的不相干的數(shù)，第一個(gè)字段根據(jù)range會(huì)先搜出2震放，3宾毒，4，5殿遂，6 第2個(gè)range查詢(xún)會(huì)搜出3诈铛，4，5墨礁，最后交集是2-4幢竹，3-5但是如果采用2D結(jié)構(gòu)，其實(shí)我第一個(gè)range可以自動(dòng)轉(zhuǎn)化成 >2,<5 一下子就得出2恩静，3焕毫，4，然后逐個(gè)進(jìn)行2D再?gòu)?D樹(shù)遞歸查找驶乾，這樣運(yùn)算量就少很多了邑飒。
當(dāng)然這是我自己的一些猜測(cè)。
有機(jī)會(huì)我會(huì)嘗試把我們的一些區(qū)間類(lèi)型用這種range類(lèi)型替換去測(cè)一下并驗(yàn)證性能轻掩。大家有興趣的可以期待幸乒。
題外話
在看Lucene BDK Tree的時(shí)候搜出了Solr 的一些實(shí)現(xiàn)懦底，發(fā)現(xiàn)在DateRangeField 這里是有差異的唇牧，在Solr 的DateRangeField 其實(shí)用的是Lucene 的DateRangeType，本質(zhì)是text實(shí)現(xiàn)來(lái)的聚唐，而ES的 date_range 看了ES的代碼可以發(fā)現(xiàn)本質(zhì)還是用了Lucene 的Long_range丐重，這一點(diǎn)有些差異，有興趣的可以查看下面幾篇Solr的文章,也是挺有意思的
