Elasticsearch 在地理信息空間索引的探索和演進(jìn)
作者 ｜ vivo 互聯(lián)網(wǎng)服務(wù)器團(tuán)隊(duì)- Shuai Guangying
本文梳理了Elasticsearch對(duì)于數(shù)值索引實(shí)現(xiàn)方案的升級(jí)和優(yōu)化思考，從2015年至今數(shù)值索引的方案經(jīng)歷了多個(gè)版本的迭代，實(shí)現(xiàn)思路從最初的字符串模擬到KD-Tree，技術(shù)越來(lái)越復(fù)雜，能力越來(lái)越強(qiáng)大，應(yīng)用場(chǎng)景也越來(lái)越豐富。從地理位置信息建模到多維坐標(biāo)，數(shù)據(jù)檢索到數(shù)據(jù)分析洞察都可以看到Elasticsearch的身影。
一、業(yè)務(wù)背景
LBS服務(wù)是當(dāng)前互聯(lián)網(wǎng)重要的一環(huán)，涉及餐飲、娛樂(lè)、打車(chē)、零售等場(chǎng)景。在這些場(chǎng)景中，有很重要的一項(xiàng)基礎(chǔ)能力：搜索附近的POI。比如搜索附近的美食，搜索附近的電影院，搜索附近的專(zhuān)車(chē)，搜索附近的門(mén)店。例如：以某個(gè)坐標(biāo)點(diǎn)為中心查詢(xún)出1km半徑范圍的POI坐標(biāo)，如下圖所示：
Elasticsearch在地理位置信息檢索上具備了毫秒級(jí)響應(yīng)的能力，而毫秒級(jí)響應(yīng)對(duì)于用戶(hù)體驗(yàn)至關(guān)重要。上面的問(wèn)題使用Elasticsearch，只需用到geo_distance查詢(xún)就可以解決業(yè)務(wù)問(wèn)題。使用Elasticsearch的查詢(xún)語(yǔ)法如下：
GET /my_locations/_search
{
"query": {
"bool": {
"must": {
"match_all": {}
},
"filter": {
"geo_distance": {
"distance": "1km",
"pin.location": {
"lat": 40,
"lon": 116
}
}
}
}
}
}
工具的使用是一個(gè)非常簡(jiǎn)單的事情，更有意思在于工具解決問(wèn)題背后的思想。理解了處理問(wèn)題的思想，就可以超然于工具本身，做到舉一反三。本文基于在海量數(shù)據(jù)背景下，如何實(shí)現(xiàn)毫秒級(jí)搜索附近的POI這個(gè)問(wèn)題，探討了Elasticsearch的實(shí)現(xiàn)方案，以及實(shí)現(xiàn)地理位置索引技術(shù)的演進(jìn)過(guò)程。
二、背景知識(shí)
在介紹Elasticsearch的處理方案前，我們首先需要介紹一些背景知識(shí)，主要是3個(gè)問(wèn)題。
1. 如何精確定位一個(gè)地址？
由經(jīng)度、緯度和相對(duì)高度組成的地理坐標(biāo)系，能夠明確標(biāo)示出地球上的任何一個(gè)位置。地球上的經(jīng)度范圍[-180， 180]，緯度范圍[-90，90]。通常以本初子午線(xiàn)(經(jīng)度為0)、赤道(緯度為0)為分界線(xiàn)。對(duì)于大多數(shù)業(yè)務(wù)場(chǎng)景，由經(jīng)緯度組成的二維坐標(biāo)已經(jīng)足以應(yīng)對(duì)業(yè)務(wù)問(wèn)題，可能重慶山城會(huì)有些例外。
2. 如何計(jì)算兩個(gè)地址距離？
對(duì)于平面坐標(biāo)系，由勾股定理可以方便計(jì)算出兩個(gè)點(diǎn)的距離。但是由于地球是一個(gè)不完美球體，且不同位置有不同海拔高度，所以精確計(jì)算兩個(gè)距離位置是一個(gè)非常復(fù)雜的問(wèn)題。在不考慮高度的情況下，二維坐標(biāo)距離通常使用Haversine公式。
這個(gè)公式非常簡(jiǎn)單，只需用到arcsin和cos兩個(gè)高中數(shù)學(xué)公式。其中φ和λ表示兩個(gè)點(diǎn)緯度和經(jīng)度的弧度制度量。其中d即為所求兩個(gè)點(diǎn)的距離，對(duì)應(yīng)的數(shù)學(xué)公式如下(參考維基百科)：
程序員更喜歡看代碼，對(duì)照代碼理解公式更簡(jiǎn)單。相應(yīng)的代碼如下：
// 代碼摘自lucene-core-8.2.0， SloppyMath工具類(lèi)
/**
* Returns the Haversine distance in meters between two points
* given the previous result from {@link #haversinSortKey(double, double, double, double)}
* @return distance in meters.
*/
public static double haversinMeters(double sortKey) {
return TO_METERS * 2 * asin(Math.min(1, Math.sqrt(sortKey * 0.5)));
}
/**
* Returns a sort key for distance. This is less expensive to compute than
* {@link #haversinMeters(double, double, double, double)}, but it always compares the same.
* This can be converted into an actual distance with {@link #haversinMeters(double)}, which
* effectively does the second half of the computation.
*/
public static double haversinSortKey(double lat1, double lon1, double lat2, double lon2) {
double x1 = lat1 * TO_RADIANS;
double x2 = lat2 * TO_RADIANS;
double h1 = 1 - cos(x1 - x2);
double h2 = 1 - cos((lon1 - lon2) * TO_RADIANS);
double h = h1 + cos(x1) * cos(x2) * h2;
// clobber crazy precision so subsequent rounding does not create ties.
return Double.longBitsToDouble(Double.doubleToRawLongBits(h) & 0xFFFFFFFFFFFFFFF8L);
}
// haversin
// TODO: remove these for java 9, they fixed Math.toDegrees()/toRadians() to work just like this.
public static final double TO_RADIANS = Math.PI / 180D;
public static final double TO_DEGREES = 180D / Math.PI;
// Earth's mean radius, in meters and kilometers; see http://earth-info.nga.mil/GandG/publications/tr8350.2/wgs84fin.pdf
private static final double TO_METERS = 6_371_008.7714D; // equatorial radius
private static final double TO_KILOMETERS = 6_371.0087714D; // equatorial radius
/**
* Returns the Haversine distance in meters between two points
* specified in decimal degrees (latitude/longitude). This works correctly
* even if the dateline is between the two points.
* <p>
* Error is at most 4E-1 (40cm) from the actual haversine distance, but is typically
* much smaller for reasonable distances: around 1E-5 (0.01mm) for distances less than
* 1000km.
*
* @param lat1 Latitude of the first point.
* @param lon1 Longitude of the first point.
* @param lat2 Latitude of the second point.
* @param lon2 Longitude of the second point.
* @return distance in meters.
*/
public static double haversinMeters(double lat1, double lon1, double lat2, double lon2) {
return haversinMeters(haversinSortKey(lat1, lon1, lat2, lon2));
}
3. 如何方便在互聯(lián)網(wǎng)分享經(jīng)緯度坐標(biāo)？
Geohash是2008-02-26由Gustavo Niemeyer在自己的個(gè)人博客上公布的算法服務(wù)。其初衷在于通過(guò)對(duì)經(jīng)緯度的編碼對(duì)外提供簡(jiǎn)短的URL標(biāo)識(shí)地圖位置，方便在電子郵件、論壇和網(wǎng)站中使用。
實(shí)際上Geohash的價(jià)值不僅僅是提供簡(jiǎn)短的URL，它更大的價(jià)值在于：
- Geohash給地圖上每個(gè)坐標(biāo)提供了獨(dú)一無(wú)二的ID，這個(gè)唯一ID就相當(dāng)于給每個(gè)地理位置提供了一個(gè)身份證。唯一ID在數(shù)據(jù)庫(kù)中應(yīng)用場(chǎng)景非常豐富。
- 在數(shù)據(jù)庫(kù)中給坐標(biāo)點(diǎn)提供了另一種存儲(chǔ)方式，將二維的坐標(biāo)點(diǎn)轉(zhuǎn)化成為一維的字符串，對(duì)于一維數(shù)據(jù)就可以借助B樹(shù)等索引來(lái)加速查詢(xún)。
- Geohash是一種前綴編碼，位置相近的坐標(biāo)點(diǎn)前綴相同。通過(guò)前綴提供了高性能的鄰近位置POI查詢(xún)，而鄰近位置POI查詢(xún)是LBS服務(wù)的核心能力。
關(guān)于Geohash的編碼規(guī)則，這里不展開(kāi)。這里最關(guān)鍵的點(diǎn)在于：
- Geohash是一種前綴編碼，位置相近的坐標(biāo)點(diǎn)前綴相同。Geohash編碼長(zhǎng)度不同，所覆蓋區(qū)域范圍不同。
在前面知識(shí)的鋪墊下，最簡(jiǎn)單的求一個(gè)坐標(biāo)點(diǎn)指定半徑范圍內(nèi)的坐標(biāo)集合的方案就出爐了。
暴力算法
中心坐標(biāo)點(diǎn)依次跟集合中每個(gè)坐標(biāo)點(diǎn)計(jì)算距離，篩選出符合半徑條件的坐標(biāo)點(diǎn)。
這個(gè)算法大家太熟悉了，就是最常見(jiàn)的暴力(Brute Force)算法。這個(gè)算法在海量數(shù)據(jù)背景下是沒(méi)法滿(mǎn)足毫秒級(jí)響應(yīng)時(shí)間要求的，所以多用于離線(xiàn)計(jì)算。對(duì)于毫秒級(jí)響應(yīng)的業(yè)務(wù)訴求，這個(gè)算法可以基于geohash進(jìn)行改造。
二次篩選
- 基于坐標(biāo)中心點(diǎn)計(jì)算出geohash, 基于半徑確定geohash前綴。
- 通過(guò)Geohash前綴初篩出大致符合要求的坐標(biāo)點(diǎn)(需要將中心點(diǎn)所在Geohash塊周?chē)?個(gè)Geohash塊納入初篩范圍)。
- 對(duì)于初篩結(jié)果使用Haversine公式進(jìn)行二次篩選。
除了上述方案，Elasticsearch在地理信息處理上有哪些奇思妙想呢？
三、方案演進(jìn)
Elasticsearch從2.0版本開(kāi)始支持geo_distance查詢(xún)，到當(dāng)前已更新到7.14版本。
從2015年至今已經(jīng)經(jīng)歷了6年的發(fā)展， 建設(shè)了如下的能力：
技術(shù)迭代大致可以分為3個(gè)階段：
發(fā)展的成效顯著，從性能測(cè)試的結(jié)果可以略窺一二：
總的來(lái)說(shuō)，資源消耗降低的前提下搜索和寫(xiě)入數(shù)據(jù)效率都有大幅度提升。下面就詳細(xì)介紹Elasticsearch對(duì)地理信息索引的思路。
3.1 史前時(shí)代
Elasticsearch是基于Lucene構(gòu)建的搜索引擎。Lucene最開(kāi)始的設(shè)想是一個(gè)全文檢索工具箱，即支持字符串檢索，并沒(méi)有考慮數(shù)值類(lèi)型的處理。其核心思想非常簡(jiǎn)單，將文檔分詞后，為每個(gè)詞構(gòu)建一個(gè)term => array[docIds]的映射。
這樣用戶(hù)輸入關(guān)鍵詞只需要三步就可以獲得想要的結(jié)果：
第一步: 通過(guò)關(guān)鍵詞找到對(duì)應(yīng)的倒排表。這一步簡(jiǎn)單來(lái)說(shuō)就是查詞典。例如：TermQuery.TermWeight 獲取該term的倒排表，讀取docId+freq信息。
第二步: 根據(jù)倒排表得到的docId和詞頻信息對(duì)文檔進(jìn)行打分，返回給用戶(hù)分值最高的TopN結(jié)果。例如：TopScoreDocCollector -- collect()方法，基于小頂堆，保留分?jǐn)?shù)最大的TopN文檔。
第三步: 基于docId查詢(xún)正排表獲取文檔字段明細(xì)信息。
這三步看起來(lái)簡(jiǎn)單，但簡(jiǎn)直是數(shù)據(jù)結(jié)構(gòu)應(yīng)用最佳戰(zhàn)場(chǎng)，它需要綜合考慮磁盤(pán)、內(nèi)存、IO、數(shù)據(jù)結(jié)構(gòu)時(shí)間復(fù)雜度，非常具有挑戰(zhàn)性。
例如：查詞典可以用很多數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)，比如跳躍表，平衡樹(shù)、HashMap等，而Lucene的核心工程師Mike McCandless實(shí)現(xiàn)了一個(gè)只有他自己能懂的FST, 是綜合了有限自動(dòng)機(jī)和前綴樹(shù)的一種數(shù)據(jù)結(jié)構(gòu)，用來(lái)平衡查詢(xún)復(fù)雜度和存儲(chǔ)空間，比HashMap慢，但是空間消耗低。文檔打分通常用小頂堆來(lái)維護(hù)分值最高的N個(gè)結(jié)果，如果有新的文檔打分超過(guò)堆頂，則替換堆頂元素即可。
問(wèn)題：對(duì)于真實(shí)業(yè)務(wù)場(chǎng)景而言，只有字符串匹配查詢(xún)是不夠的，字符串和數(shù)值是應(yīng)用最廣泛的兩種數(shù)據(jù)類(lèi)型。如果需要進(jìn)行區(qū)間查詢(xún)?cè)趺崔k呢？這是一個(gè)數(shù)據(jù)庫(kù)產(chǎn)品非?；A(chǔ)的能力。
Lucene提供了一種適配方案RangeQuery。就是用枚舉來(lái)模擬數(shù)值查詢(xún)。簡(jiǎn)單來(lái)說(shuō)：
RangeQuery=BooleanQuery+TermQuery，所以限制查詢(xún)是整數(shù)且區(qū)間最大不能超過(guò)1024。這種實(shí)現(xiàn)是可以說(shuō)是非常雞肋的，好在Lucene 2.9.0版本真正支持?jǐn)?shù)值查詢(xún)。
LUCENE-1470,LUCENE-1582,LUCENE-1602,LUCENE-1673,LUCENE-1701, LUCENE-1712
Added NumericRangeQuery and NumericRangeFilter, a fast alternative to RangeQuery/RangeFilter for numeric searches. They depend on a specific structure of terms in the index that can be created by indexing using the new NumericField or NumericTokenStream classes. NumericField can only be used for indexing and optionally stores the values as string representation in the doc store. Documents returned from IndexReader/IndexSearcher will return only the String value using the standard Fieldable interface. NumericFields can be sorted on and loaded into the FieldCache. (Uwe Schindler, Yonik Seeley, Mike McCandless)
這個(gè)實(shí)現(xiàn)很強(qiáng)大，支持了int/long/float/double/
short/byte，也不限制查詢(xún)區(qū)間了。它的核心思路是將數(shù)值字節(jié)數(shù)組化，然后利用前綴分層管理區(qū)間。
如下圖所示：
本質(zhì)上還是RangeQuery=
BooleanQuery+TermQuery，只不過(guò)在前面做了一層轉(zhuǎn)換：通過(guò)前綴樹(shù)管理一個(gè)區(qū)間實(shí)現(xiàn)了匹配詞數(shù)量的縮減，而這個(gè)縮減是非常有效的。所以這里就有一個(gè)專(zhuān)家參數(shù)：precisionStep。就是用來(lái)控制每個(gè)數(shù)值字段在分詞是生成term的數(shù)量，生成term數(shù)量越多，區(qū)間控制粒度越細(xì)，占用磁盤(pán)空間越大，查詢(xún)效率通常越高。
例如：如果precisionStep=8,則意味前綴樹(shù)葉子節(jié)點(diǎn)的上層控制著255個(gè)葉子。那么，當(dāng)查詢(xún)范圍在1~511時(shí)，由于跨了相鄰的2個(gè)非葉子節(jié)點(diǎn)，所以需要遍歷511個(gè)term。但是假如查詢(xún)范圍在0~512，又只需遍歷2個(gè)term即可。這樣的實(shí)現(xiàn)用起來(lái)真的有過(guò)山車(chē)的感覺(jué)。
綜上，Elasticsearch核心的Lucene倒排索引是一種經(jīng)典的以不變應(yīng)萬(wàn)變：字符串和數(shù)值索引核心都是查倒排表。理解這個(gè)核心，對(duì)于后面理解地理位置數(shù)據(jù)存儲(chǔ)和查詢(xún)非常關(guān)鍵。接下來(lái)我們以geo_distance的實(shí)現(xiàn)思路為探索主線(xiàn)條，探索一下ES各個(gè)版本的實(shí)現(xiàn)思路。
3.2 Elasticsearch 2.0 版本
這個(gè)版本實(shí)現(xiàn)geo_distance查詢(xún)的思路非常樸素，是建立在數(shù)值區(qū)間查詢(xún)(NumericRangeQuery)的基礎(chǔ)上。它的geo_point類(lèi)型字段其實(shí)是一個(gè)復(fù)合字段，或者說(shuō)是一個(gè)結(jié)構(gòu)體。在底層實(shí)現(xiàn)時(shí)分別用兩個(gè)獨(dú)立字段索引來(lái)避免暴力掃描。即Elasticsearch的geo_point字段在實(shí)現(xiàn)上是lat,lon，加上編碼成的geohash綜合提供檢索聚合功能。
字段定義如下所示：
public static final class GeoPointFieldType extends MappedFieldType {
private MappedFieldType geohashFieldType;
private int geohashPrecision;
private boolean geohashPrefixEnabled;
private MappedFieldType latFieldType;
private MappedFieldType lonFieldType;
public GeoPointFieldType() {}
}算法的執(zhí)行分為三個(gè)階段：
第一步：根據(jù)中心點(diǎn)以及半徑計(jì)算出一個(gè)大致符合需求的矩形區(qū)域，然后利用矩形區(qū)域的最小最大經(jīng)度得到一個(gè)數(shù)值區(qū)間查詢(xún)，利用矩形區(qū)域的最小最大緯度得到一個(gè)區(qū)間查詢(xún)。
核心代碼如下圖所示：
// 計(jì)算經(jīng)緯度坐標(biāo)+距離得到的矩形區(qū)域
// GeoDistance類(lèi)
public static DistanceBoundingCheck distanceBoundingCheck(double sourceLatitude, double sourceLongitude, double distance, DistanceUnit unit) {
// angular distance in radians on a great circle
// assume worst-case: use the minor axis
double radDist = unit.toMeters(distance) / GeoUtils.EARTH_SEMI_MINOR_AXIS;
double radLat = Math.toRadians(sourceLatitude);
double radLon = Math.toRadians(sourceLongitude);
double minLat = radLat - radDist;
double maxLat = radLat + radDist;
double minLon, maxLon;
if (minLat > MIN_LAT && maxLat < MAX_LAT) {
double deltaLon = Math.asin(Math.sin(radDist) / Math.cos(radLat));
minLon = radLon - deltaLon;
if (minLon < MIN_LON) minLon += 2d * Math.PI;
maxLon = radLon + deltaLon;
if (maxLon > MAX_LON) maxLon -= 2d * Math.PI;
} else {
// a pole is within the distance
minLat = Math.max(minLat, MIN_LAT);
maxLat = Math.min(maxLat, MAX_LAT);
minLon = MIN_LON;
maxLon = MAX_LON;
}
GeoPoint topLeft = new GeoPoint(Math.toDegrees(maxLat), Math.toDegrees(minLon));
GeoPoint bottomRight = new GeoPoint(Math.toDegrees(minLat), Math.toDegrees(maxLon));
if (minLon > maxLon) {
return new Meridian180DistanceBoundingCheck(topLeft, bottomRight);
}
return new SimpleDistanceBoundingCheck(topLeft, bottomRight);
}
第二步：兩個(gè)查詢(xún)通過(guò)BooleanQuery組合成一個(gè)取交集的復(fù)合查詢(xún)，以實(shí)現(xiàn)初篩出在經(jīng)緯度所示矩形區(qū)域內(nèi)的docId集合。
核心代碼如下圖所示：
public class IndexedGeoBoundingBoxQuery {
public static Query create(GeoPoint topLeft, GeoPoint bottomRight, GeoPointFieldMapper.GeoPointFieldType fieldType) {
if (!fieldType.isLatLonEnabled()) {
throw new IllegalArgumentException("lat/lon is not enabled (indexed) for field [" + fieldType.names().fullName() + "], can't use indexed filter on it");
}
//checks to see if bounding box crosses 180 degrees
if (topLeft.lon() > bottomRight.lon()) {
return westGeoBoundingBoxFilter(topLeft, bottomRight, fieldType);
} else {
return eastGeoBoundingBoxFilter(topLeft, bottomRight, fieldType);
}
}
private static Query westGeoBoundingBoxFilter(GeoPoint topLeft, GeoPoint bottomRight, GeoPointFieldMapper.GeoPointFieldType fieldType) {
BooleanQuery.Builder filter = new BooleanQuery.Builder();
filter.setMinimumNumberShouldMatch(1);
filter.add(fieldType.lonFieldType().rangeQuery(null, bottomRight.lon(), true, true), Occur.SHOULD);
filter.add(fieldType.lonFieldType().rangeQuery(topLeft.lon(), null, true, true), Occur.SHOULD);
filter.add(fieldType.latFieldType().rangeQuery(bottomRight.lat(), topLeft.lat(), true, true), Occur.MUST);
return new ConstantScoreQuery(filter.build());
}
private static Query eastGeoBoundingBoxFilter(GeoPoint topLeft, GeoPoint bottomRight, GeoPointFieldMapper.GeoPointFieldType fieldType) {
BooleanQuery.Builder filter = new BooleanQuery.Builder();
filter.add(fieldType.lonFieldType().rangeQuery(topLeft.lon(), bottomRight.lon(), true, true), Occur.MUST);
filter.add(fieldType.latFieldType().rangeQuery(bottomRight.lat(), topLeft.lat(), true, true), Occur.MUST);
return new ConstantScoreQuery(filter.build());
}
}第三步：利用FieldData緩存(正向信息)根據(jù)docId獲取矩形區(qū)域中每個(gè)坐標(biāo)點(diǎn)的經(jīng)緯度，然后利用前面的Haversine公式計(jì)算跟中心坐標(biāo)點(diǎn)的距離，進(jìn)行精確篩選，得到符合條件的文檔集合。
核心代碼如下所示：
// GeoDistanceRangeQuery類(lèi)的實(shí)現(xiàn)
@Override
public Weight createWeight(IndexSearcher searcher, boolean needsScores) throws IOException {
final Weight boundingBoxWeight;
if (boundingBoxFilter != null) {
boundingBoxWeight = searcher.createNormalizedWeight(boundingBoxFilter, false);
} else {
boundingBoxWeight = null;
}
return new ConstantScoreWeight(this) {
@Override
public Scorer scorer(LeafReaderContext context) throws IOException {
final DocIdSetIterator approximation;
if (boundingBoxWeight != null) {
approximation = boundingBoxWeight.scorer(context);
} else {
approximation = DocIdSetIterator.all(context.reader().maxDoc());
}
if (approximation == null) {
// if the approximation does not match anything, we're done
return null;
}
final MultiGeoPointValues values = indexFieldData.load(context).getGeoPointValues();
final TwoPhaseIterator twoPhaseIterator = new TwoPhaseIterator(approximation) {
@Override
public boolean matches() throws IOException {
final int doc = approximation.docID();
values.setDocument(doc);
final int length = values.count();
for (int i = 0; i < length; i++) {
GeoPoint point = values.valueAt(i);
if (distanceBoundingCheck.isWithin(point.lat(), point.lon())) {
double d = fixedSourceDistance.calculate(point.lat(), point.lon());
if (d >= inclusiveLowerPoint && d <= inclusiveUpperPoint) {
return true;
}
}
}
return false;
}
};
return new ConstantScoreScorer(this, score(), twoPhaseIterator);
}
};
}
這是一種非常簡(jiǎn)單且直觀的思路實(shí)現(xiàn)了中心點(diǎn)指定半徑范圍POI的搜索能力。
簡(jiǎn)單總結(jié)一下要點(diǎn)：
- 利用中心點(diǎn)坐標(biāo)和半徑確定矩形區(qū)域邊界。
- 利用Bool查詢(xún)綜合兩個(gè)NumericRangeQuery查詢(xún)，實(shí)現(xiàn)矩形區(qū)域初篩。
- 利用Haversine公式計(jì)算中心點(diǎn)和矩形區(qū)域內(nèi)每個(gè)坐標(biāo)點(diǎn)距離，進(jìn)行第二階段過(guò)濾操作，篩選出最終符合條件的docId集合。
方案雖然簡(jiǎn)單，但是畢竟實(shí)現(xiàn)了geo_distance的能力。又不是不能用，對(duì)吧？那么該方案有什么問(wèn)題呢？
3.3 Elasticsearch 2.2 版本
ES2.0版本的實(shí)現(xiàn)有個(gè)問(wèn)題， 就是沒(méi)有很好解決二維組合條件查詢(xún)的數(shù)據(jù)篩選。它是分別獲取符合緯度范圍條件的文檔集合和符合經(jīng)度范圍條件的文檔集合然后進(jìn)行交集，初篩了太多無(wú)效的文檔集合。
它的處理思路用一張圖表示如下：
即選擇了那么多的記錄，最終只有經(jīng)緯度范圍交匯的紅色區(qū)域是初篩的范圍。
針對(duì)上面的問(wèn)題，ES 2.2版本引入特性：基于四叉樹(shù)(Quadtree)的地理位置查詢(xún)(Lucene 5.3版本實(shí)現(xiàn))。
Quadtree并非什么復(fù)雜高深的數(shù)據(jù)結(jié)構(gòu)，相比二叉樹(shù)，多了兩個(gè)子節(jié)點(diǎn)。
作為一種基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)，Quadtree應(yīng)用場(chǎng)景非常廣泛，在圖像處理、空間索引、碰撞檢測(cè)、人生游戲模擬、分形圖像分析等領(lǐng)域都可以看到它的身影。
在Elasticsearch地理位置空間索引問(wèn)題上，Quadtree用來(lái)表示區(qū)間，可以視為前綴樹(shù)的一種。
Region quadtree
The region quadtree represents a partition of space in two dimensions by decomposing the region into four equal quadrants, subquadrants, and so on with each leaf node containing data corresponding to a specific subregion. Each node in the tree either has exactly four children, or has no children (a leaf node). The height of quadtrees that follow this decomposition strategy (i.e. subdividing subquadrants as long as there is interesting data in the subquadrant for which more refinement is desired) is sensitive to and dependent on the spatial distribution of interesting areas in the space being decomposed. The region quadtree is a type of trie.
在區(qū)間劃分上，Quadtree跟geohash的處理思路有些相似。在一維世界，二分可以無(wú)限迭代。同理，在二維世界，四分也可以無(wú)限迭代。下面這個(gè)圖可以非常形象展示Quadtree的區(qū)間劃分過(guò)程。
ES 2.2是如何使用Quadtree來(lái)實(shí)現(xiàn)geo_distance查詢(xún)呢？
通常我們使用一種數(shù)據(jù)結(jié)構(gòu)，是先基于該數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)數(shù)據(jù)，然后查詢(xún)這個(gè)數(shù)據(jù)結(jié)構(gòu)。ES這里使用Quadtree的做法非常巧妙：存儲(chǔ)的時(shí)候沒(méi)有感覺(jué)用到Quadtree，查詢(xún)時(shí)卻用其查詢(xún)方式。
morton編碼：在理解ES的處理思路前，需要科普一個(gè)知識(shí)點(diǎn)，那就是morton編碼。關(guān)于morton編碼，跟geohash類(lèi)似，是一種將二維數(shù)據(jù)按二進(jìn)制位交叉編碼成一維數(shù)據(jù)的一種網(wǎng)格編碼，其用法和特點(diǎn)跟geohash也是類(lèi)似的。對(duì)于64位的morton碼，其經(jīng)緯度定位精度范圍控制到了厘米級(jí)別，對(duì)于地理位置場(chǎng)景而言，是非常非常高的精度了。
數(shù)據(jù)存儲(chǔ)：ES2.2版本之前一個(gè)經(jīng)緯度坐標(biāo)需要三個(gè)字段存儲(chǔ)：lat,lon,geohash。有了Quadtree后，只需要一個(gè)字段存儲(chǔ)就可以了。具體的實(shí)現(xiàn)思路如下：將lat,lon坐標(biāo)進(jìn)行映射，使得經(jīng)緯度的取值范圍從[-180,180]/[-90,90]映射到[0,2147483520](整數(shù)好處理)， 然后處理成一維的mortonHash數(shù)值。對(duì)于數(shù)值字段的處理思路，就又回到了前綴(trie)的思路，就又回到了熟悉的專(zhuān)家參數(shù)precisionStep。在這里的前綴該如何理解？對(duì)于一維數(shù)據(jù)，每個(gè)前綴管理一段區(qū)間，對(duì)于二維數(shù)據(jù)每個(gè)前綴管理一個(gè)二維網(wǎng)格區(qū)域。例如一個(gè)坐標(biāo)點(diǎn)利用precisionStep=9來(lái)劃分前綴，其可視化矩形區(qū)域如下：
(取shift=27,36)
(取shift=36,45)
數(shù)據(jù)查詢(xún)：在查詢(xún)時(shí)，首先將查詢(xún)中心點(diǎn)坐標(biāo)轉(zhuǎn)換成一個(gè)矩形。這個(gè)處理思路我們延續(xù)了ES 2.0的做法，不陌生了。
例如：對(duì)于坐標(biāo)為(116.433322,39.900255)，半徑為1km的點(diǎn)，生成的矩形如下所示：
double centerLon = 116.433322;
double centerLat = 39.900255;
double radiusMeters = 1000.0;
GeoRect geoRect = GeoUtils.circleToBBox(centerLon, centerLat, radiusMeters);
System.out.println( geoRect );
用高德API生成對(duì)應(yīng)的可視化圖形如下：
有了這個(gè)矩形后，后面的做法就跟ES 2.0有些不同了。ES 2.2版本的思路是利用Quadtree對(duì)整個(gè)世界地圖進(jìn)行網(wǎng)格化。具體的流程如下：
Quadtree處理流程
第一步: 以經(jīng)緯度(0,0)為起始中心點(diǎn)，將整個(gè)世界切分成4個(gè)區(qū)塊。并判斷參數(shù)生成的矩形在哪個(gè)區(qū)塊。
第二步: 對(duì)于矩形區(qū)域不在的區(qū)域，略過(guò)。對(duì)于矩形區(qū)域所在的區(qū)塊，繼續(xù)四分，切成4個(gè)區(qū)塊。
第三步: 當(dāng)滿(mǎn)足如下任一條件時(shí)，將相關(guān)的文檔集合收集起來(lái)，作為第一批粗篩的結(jié)果。
- 條件一：切分到正好跟前綴的precisionStep契合，并且quad-cell在矩形內(nèi)部時(shí)。
- 條件二：切分到最小層級(jí)(level=13)時(shí)且quad-cell跟矩形區(qū)域有交集時(shí)。
第四步: 利用lucene的doc_values緩存機(jī)制，獲取每個(gè)docId對(duì)應(yīng)的經(jīng)緯度，利用距離公式計(jì)算是否在半徑范圍內(nèi)，得到最終的結(jié)果。(這個(gè)操作也是常規(guī)思路了)
另外ES在處理時(shí)進(jìn)行了版本兼容。
例如：ES 2.2版本對(duì)于geo_distance的實(shí)現(xiàn)關(guān)鍵點(diǎn)，判斷索引版本是否是V_2_2_0版本以后創(chuàng)建，如果是則直接用Lucene的
GeoPointDistanceQuery查詢(xún)類(lèi)，否則沿用ES 2.0版本的GeoDistanceRangeQuery。
IndexGeoPointFieldData indexFieldData = parseContext.getForField(fieldType);
final Query query;
if (parseContext.indexVersionCreated().before(Version.V_2_2_0)) {
query = new GeoDistanceRangeQuery(point, null, distance, true, false, geoDistance, geoFieldType, indexFieldData, optimizeBbox);
} else {
distance = GeoUtils.maxRadialDistance(point, distance);
query = new GeoPointDistanceQuery(indexFieldData.getFieldNames().indexName(), point.lon(), point.lat(), distance);
}
if (queryName != null) {
parseContext.addNamedQuery(queryName, query);
}
核心代碼參考：GeoPointDistanceQuery、GeoPointRadiusTermsEnum
3.4 Elasticsearch 5.0 版本
方案優(yōu)化的探索是沒(méi)有沒(méi)有止境的，Lucene的核心工程師 Michael McCandless受到論文《Bkd-Tree: A Dynamic Scalable kd-Tree》啟發(fā)，基于BKD tree再次升級(jí)了地理位置數(shù)據(jù)索引建模和查詢(xún)功能。
這個(gè)數(shù)據(jù)結(jié)構(gòu)不僅僅是用于解決地理位置查詢(xún)問(wèn)題，更是數(shù)值類(lèi)數(shù)據(jù)索引建模的通用方案。它可以處理一維的數(shù)值，從byte到BigDecimal, IPv6地址等等；它也可以處理二維乃至于N維的數(shù)據(jù)檢索問(wèn)題。
LUCENE-6825
This can be used for very fast 1D range filtering for numerics, removing the 8 byte (long/double) limit we have today, so e.g. we could efficiently support BigInteger, BigDecimal, IPv6 addresses, etc.
It can also be used for > 1D use cases, like 2D (lat/lon) and 3D (x/y/z with geo3d) geo shape intersection searches.
...
It should give sizable performance gains (smaller index, faster searching) over what we have today, and even over what auto-prefix with efficient numeric terms would do.
在前面的版本中，對(duì)于數(shù)值區(qū)間查詢(xún)的處理思路本質(zhì)上都是term匹配，通過(guò)前綴實(shí)現(xiàn)了一個(gè)term管理一個(gè)區(qū)間，從而降低了區(qū)間查詢(xún)需要遍歷的term數(shù)量。而從ES 5.0版本開(kāi)始，徹底優(yōu)化了數(shù)值查詢(xún)(從一維到N維)，其底層是Lucene 6.0版本實(shí)現(xiàn)的BKD tree的獨(dú)立索引。其實(shí)現(xiàn)不僅降低了內(nèi)存開(kāi)銷(xiāo)，而且提升了檢索和索引速度。
關(guān)于bkd-tree的原理，其大體思路如下。在面對(duì)數(shù)值查詢(xún)區(qū)間查詢(xún)的問(wèn)題上，大體分為兩個(gè)層次：
- 【優(yōu)化內(nèi)存查詢(xún)】：BST(binary-search-tree) > Self-balanced BST > kd-tree。
- 【優(yōu)化外存(硬盤(pán))查詢(xún)】：B-tree > K-D-B-tree > BKD tree。
kd-tree其實(shí)就是多維的BST。例如：
【數(shù)據(jù)存儲(chǔ)】：BKD tree的核心思路是非常簡(jiǎn)單的，將N維點(diǎn)集合形成的矩形空間(southWest,northEast)遞歸分割成更小的矩形空間。跟常見(jiàn)的kd-tree不同，當(dāng)分割到網(wǎng)格區(qū)域里面坐標(biāo)點(diǎn)的數(shù)量小于一定數(shù)量(比如1024)就停止了。
例如：
通過(guò)區(qū)域的分割，確保每個(gè)區(qū)域POI的數(shù)量大致相等。
【數(shù)據(jù)查詢(xún)】：搜索的時(shí)候，就不再是像Quadtree從整個(gè)世界開(kāi)始定位，而是基于當(dāng)前的點(diǎn)集合形成的空間來(lái)查找。例如以geo_distance查詢(xún)?yōu)槔?/p>
其流程如下：
第一步: 中心點(diǎn)坐標(biāo)+半徑生成一個(gè)矩形(shape boundary)。這一步是常規(guī)操作了，前面的版本也都是這么做的。
第二步：該矩形跟BKD tree 葉子節(jié)點(diǎn)形成的矩形(cell)進(jìn)行intersect運(yùn)算，所謂intersect運(yùn)算，就是計(jì)算兩個(gè)矩形的位置關(guān)系：相交、內(nèi)嵌還是不相關(guān)。query和bkd-tree形成的區(qū)域有三種關(guān)系。
- 對(duì)于CELL_CROSSES_QUERY，如果是葉子節(jié)點(diǎn)，則需要判斷cell中的每個(gè)POI是否符合query的查詢(xún)條件；否則查詢(xún)子區(qū)間；
- 對(duì)于CELL_OUTSIDE_QUERY，直接略過(guò)；
- 對(duì)于CELL_INSIDE_QUERY，整個(gè)cell中的POI都滿(mǎn)足查詢(xún)條件。
核心代碼：LatLonPoint/LatLonPointDistanceQuery
3.5 后續(xù)發(fā)展
Geo查詢(xún)能力的迭代和變遷，其實(shí)也是Elasticsearch作為一個(gè)數(shù)據(jù)庫(kù)對(duì)數(shù)值查詢(xún)能力的升級(jí)和優(yōu)化，擴(kuò)展產(chǎn)品的適用場(chǎng)景，讓使用者打破對(duì)Elasticsearch只能做全文檢索的偏見(jiàn)。從全文檢索數(shù)據(jù)庫(kù)擴(kuò)展到分析型數(shù)據(jù)庫(kù)，Elasticsearch還有很長(zhǎng)的路要走。
按照 Michael McCandless的設(shè)想，當(dāng)前的多維數(shù)據(jù)只能是單個(gè)點(diǎn)，但是有些場(chǎng)景需要將形狀作為一個(gè)維度進(jìn)行索引。在這種需求下，需要通過(guò)一種更普適化的k-d tree ，即R-Tree來(lái)實(shí)現(xiàn)。
路漫漫其修遠(yuǎn)兮，ES從2.0版本支持geo-spatial開(kāi)始經(jīng)歷6年的發(fā)展，已經(jīng)走了很遠(yuǎn)，然而依然有很多值得探索的領(lǐng)域和場(chǎng)景。
參考:
