Solr空间搜索原理分析与实践

前言

在美团CRM系统中，搜索商家的效率与公司的销售额息息相关，为了让BD们更便捷又直观地去搜索商家，美团CRM技术团队基于Solr提供了空间搜索功能，其中移动端周边商家搜索和PC端的地图模式搜索功能为BD们的日常工作带来了很大的便利，大大提升了BD们的工作效率。

在本文中，首先对空间搜索的原理进行简单介绍，然后再结合具体的业务场景去分享美团使用空间搜索的实践。

空间搜索原理

空间搜索，又名Spatial Search，基于空间搜索技术，可以做到：

1）对Point（经纬度）和其他的几何图形建索引

2）根据距离排序

3）根据矩形，圆形或者其他的几何形状过滤搜索结果

在Solr中，空间搜索主要基于GeoHash和Cartesian Tiers 2个概念来实现：

###GeoHash算法

通过GeoHash算法，可以将经纬度的二维坐标变成一个可排序、可比较的的字符串编码。
在编码中的每个字符代表一个区域，并且前面的字符是后面字符的父区域。其算法的过程如下：

####根据经纬度计算GeoHash二进制编码

地球纬度区间是[-90,90]， 如某纬度是39.92324，可以通过下面算法对39.92324进行逼近编码:

1）区间[-90,90]进行二分为[-90,0),[0,90]，称为左右区间，可以确定39.92324属于右区间[0,90]，给标记为1；

2）接着将区间[0,90]进行二分为 [0,45),[45,90]，可以确定39.92324属于左区间 [0,45)，给标记为0；

3）递归上述过程39.92324总是属于某个区间[a,b]。随着每次迭代区间[a,b]总在缩小，并越来越逼近39.928167；

4）如果给定的纬度（39.92324）属于左区间，则记录0，如果属于右区间则记录1，这样随着算法的进行会产生一个序列1011 1000 1100 0111 1001，序列的长度跟给定的区间划分次数有关。

同理，地球经度区间是[-180,180]，对经度116.3906进行编码的过程也类似：

####组码

通过上述计算，纬度产生的编码为1011 1000 1100 0111 1001，经度产生的编码为1101 0010 1100 0100 0100。偶数位放经度，奇数位放纬度，把2串编码组合生成新串：11100 11101 00100 01111 00000 01101 01011 00001。

最后使用用0-9、b-z（去掉a, i, l, o）这32个字母进行base32编码，首先将11100 11101 00100 01111 00000 01101 01011 00001转成十进制 28，29，4，15，0，13，11，1，十进制对应的编码就是wx4g0ec1。同理，将编码转换成经纬度的解码算法与之相反，具体不再赘述。

由上可知，字符串越长，表示的范围越精确。当GeoHash base32编码长度为8时，精度在19米左右，而当编码长度为9时，精度在2米左右，编码长度需要根据数据情况进行选择。不过从GeoHash的编码算法中可以看出它的一个缺点，位于边界两侧的两点，虽然十分接近，但编码会完全不同。实际应用中，可以同时搜索该点所在区域的其他八个区域的点，即可解决这个问题。

###Cartesian Tiers 笛卡尔层

笛卡尔分层模型的思想是将经纬度转换成更大粒度的分层网格，该模型创建了很多的地理层，每一层在前一层的基础上细化切分粒度，每一个网格被分配一个ID，代表一个地理位置。

每层以2的平方递增，所以第一层为4个网格，第二层为16 个，所以整个地图的经纬度将在每层的网格中体现：

那么如何构建这样的索引结构呢，其实很简单，只需要对应笛卡尔层的层数来构建域即可,一个域或坐标对应多个tiers层次。也即是tiers0->field_0，tiers1->field_1,tiers2-field_2,……，tiers19->field_19。（一般20层即可）。每个对应笛卡尔层次的域将根据当前这条记录的经纬度通过笛卡尔算法计算出归属于当前层的网格，然后将gridId（网格唯一标示）以term的方式存入索引。这样每条记录关于笛卡尔0-19的域将都会有一个gridId对应起来。但是查询的时候一般是需要查周边的地址，那么可能周边的范围超过一个网格的范围，那么实际操作过程是根据经纬度和一个距离确定出需要涉及查询的从19-0（从高往低查）若干层对应的若干网格的数据。那么一个经纬度周边地址的查询只需要如下图圆圈内的数据：

由上可知，基于Cartesian Tier的搜索步骤为：
1、根据Cartesian Tier层获得坐标点的地理位置gridId
2、与系统索引gridId匹配计算
3、计算结果集与目标坐标点的距离返回特定范围内的结果集合

使用笛卡尔层，能有效缩减少过滤范围，快速定位坐标点。

基于Solr的空间搜索实践

在Solr中，针对上述的2种原理提供了不同的索引方式去实现，分别是GeohashPrefixTree类和QuadPrefixTree类，其中GeohashPrefixTree对应GeoHash算法(也采用了笛卡尔层的分层思想)，QuadPrefixTree对应笛卡尔层的实现。

GeohashPrefixTree与QuadPrefixTree都继承SpatialPrefixTree这个前缀树基类，都使用了分层策略，主要索引和查询逻辑⼀样。不同点在于它们的maxLevels不一样，获取子cell的方式不一样，GeohashPrefixTree有32个子cell(编码为0-z)，QuadPrefixTree 只有有4个子cell(编码为ABCD。A：左上，B：右上，C：左下，D：右下)。

而在Solr中，默认是使用GeohashPrefixTree的方式，索引下面重点介绍geohash的方式。利用Solr来实现空间搜索主要分为2部分：

1）索引的构建

2）查询

###索引构建

####Step1 定义空间索引类型和字段

在Solr中提供了scheme.xml文件用来定义索引类型和字段，如下所示：

<fieldType  name="location_rpt"     class="solr.SpatialRecursivePrefixTreeFieldType" spatialContextFactory="com.spatial4j.core.context.jts.JtsSpatialContextFactory" distErrPct="0.025" maxDistErr="0.000009" units="degrees"/>

<field name=”poi_location_p"  type="location_rpt"  indexed="true"     stored="true"     multiValued=”false"/>    

对于重要的属性说明如下：

SpatialRecursivePrefixTreeFieldType

用于深度遍历前缀树的FieldType，主要用于获得基于Lucene中的RecursivePrefixTreeStrategy。

JtsSpatialContextFactory

当有Polygon多边形或者linestrings线段时，会使用jts(需要把jts.jar放到solr服务的lib下)，而基本形状使用SpatialContext (spatial4j的类)。

distErrPct

定义非Point图形的精度，范围在0-0.5之间。该值决定了非Point的图形索引或查询时的level(如geohash模式时就是geohash编码的长度)。当为0时取maxLevels，即精度最大,精度越大将花费更多的空间和时间去建索引。

geo

默认为true，值为true的情况下坐标基于球面坐标系，采用Geohash的方式；值为false的情况下坐标基于2D平面的坐标系，采用Euclidean/Cartesian的方式。

worldBounds

世界坐标值：”minX minY maxX maxY”。 geo=true即geohash模式时，该值默认为”-180 -90 180 90”。geo=false即quad时，该值为Java double类型的正负边界，此时需要指定该值，设置成”-180 -90 180 90”。

distCalculator

设置距离计算算法，geo=true默认是haversine，geo=false默认是cartesian(笛卡尔计算方式)，值可以为"lawOfCosines"(余弦定理), "vincentySphere"(文森特球面公式) 或 "cartesian^2"。

prefixTree

Solr将地球映射为网格，prefixTree定义了网格的实现方式，每个网格在下一层中可以分解成多个子网格，geo=true prefixTree只能取GeoHash，geo=false prefixTree可取quad(quadTree一种四分树地理位置索引，对应笛卡尔分层策略)

maxDistErr/maxLevels

maxDistErr定义了索引数据的最高层maxLevels，上述定义为0.000009，根据GeohashUtils.lookupHashLenForWidthHeight(0.000009, 0.000009)算出编码长度为11位，精度在1米左右，直接决定了Point索引的term数。
maxLevels优先级高于maxDistErr,即有maxLevels的话maxDistErr失效。详见SpatialPrefixTreeFactory.init()方法。
不过一般使用maxDistErr。

units

单位是degrees，不适用于geofilt, bbox, or geodist（单位为km）

####Step2 构建索引

构建索引代码示例（在美团主要使用Point类型的索引）：

doc.setField(”poi_location_p",     "32.52162,120.31778") //point类型
或者
doc.setField("poi_location_p",     "POLYGON((120.35330414772034    
31.58268495951037,120.35190939903259     31.57923921490961,120.35330414772034    
31.58268495951037))") //多边形类型

构建流程：

下面主要说明Point类型的term创建过程。

1、将空间索引域的shapeStr解析成相应的Shape（这里指Point，复杂Shape如Polygon要使用JTS中的WTKReader来解析）。

2、创建索引域,具体过程参考org.apache.lucene.spatial.prefix.RecursivePrefixTreeStrategy中的createIndexableFields方法。

a、根据distErrPct字段，计算距离的误差值，对于Point来说默认为0（而对于非Point类型来说，是通过外包矩形中心点到矩形顶点的距离再乘以distErrPct来计算误差值的）

double distErr = SpatialArgs.calcDistanceFromErrPct(shape, distErrPct, ctx);

public static double calcDistanceFromErrPct(Shape shape, double distErrPct, SpatialContext ctx) {
   if (distErrPct < 0 || distErrPct > 0.5) {
      throw new IllegalArgumentException("distErrPct " + distErrPct + " must be between [0 to 0.5]");
   }
   if (distErrPct == 0 || shape instanceof Point) {
      return 0;
   }
   Rectangle bbox = shape.getBoundingBox();
   //Compute the distance from the center to a corner.  Because the distance
   // to a bottom corner vs a top corner can vary in a geospatial scenario,
   // take the closest one (greater precision).
   Point ctr = bbox.getCenter();
   double y = (ctr.getY() >= 0 ? bbox.getMaxY() : bbox.getMinY());
   double diagonalDist = ctx.getDistCalc().distance(ctr, bbox.getMaxX(), y);
   return diagonalDist * distErrPct;
}

b、根据上述计算出的误差值，得到索引的geohash编码长度，对于Point类型来说值为maxLevels。

public int getLevelForDistance(double dist) {
   if (dist == 0)
      return maxLevels;//short circuit
   final int level = GeohashUtils.lookupHashLenForWidthHeight(dist, dist);
   return Math.max(Math.min(level, maxLevels), 1);
}

c、根据编码长度得到满足所有条件的cells（每个cell表示一个前缀值），并将Cells都放在CellTokenStream中，同时构建索引域。Point类型每个Cell表示geohash的一个前缀值。

public List<Cell> getCells(Point p, int detailLevel, boolean inclParents){
   Cell cell = getCell(p, detailLevel);
   if (!inclParents) {
      return Collections.singletonList(cell);
   }

   String endToken = cell.getTokenString();
   assert endToken.length() == detailLevel;
   List<Cell> cells = new ArrayList<Cell>(detailLevel);
   for (int i = 1; i < detailLevel; i++) {
      cells.add(getCell(endToken.substring(0, i)));
   }
   cells.add(cell);
   return cells;
}

Field field = new Field(getFieldName(),
    new CellTokenStream(cells.iterator()), FIELD_TYPE);

3、构建存取域存储索引

if (field.stored()) {
    if (shapeStr == null)
      shapeStr = shapeToString(shape);
    result.add(new StoredField(field.getName(), shapeStr));
}

4、结果

如经纬度41.79452,123.41555，对应的geohash为wxrvb2kqexu（maxLevels=11）, 则其对应的term有11个（如w、wx、wxr、wxrv…）。

###查询

查询语法示例：

q={!geofilt pt=45.15,-93.85 sfield=poi_location_p d=5 score=distance}
q={!bbox pt=45.15,-93.85 sfield=poi_location_p d=5 score=distance}
q=poi_location_p:"Intersects(-74.093 41.042 -69.347 44.558)" //a bounding box (not in WKT) 
q=poi_location_p:"Intersects(POLYGON((-10 30, -40 40, -10 -20, 40 20, 0 0, -10 30)))" //a WKT example 

涉及到的字段说明：

其中有几种常见的Solr支持的几何操作：
WITHIN：在内部
CONTAINS：包含关系
DISJOINT：不相交
Intersects：相交（存在交集）

在美团CRM中，空间搜索日常常见的需求主要分为2类：

1. 范围搜索（在美团CRM中对应周边商家搜索）

范围搜索支持2种范围确定方式：

• geofilt方式：根据搜索半径过滤结果，返回以pt为圆心d为半径的圆内所有点,如左图所示返回圆形内所有点
• bbox方式：根据具体的域过滤结果，不仅返回以pt为圆心d为半径的圆内所有点，还包括域内其他点，返回矩形框内所有点，如右图所示：

  

范围搜索的情况很多，下面列举一些常用场景的查询语法：

• 不需要排序的场景

   fq={!geofilt pt=45.15,-93.85 sfield=geo d=5} 
  
   fq={!bbox pt=45.15,-93.85 sfield=geo d=5} 
  

• 需要排序的场景,较复杂

1) 按距离排序，距离越近排名越高，加上score=distance，其中distance是索引点到坐标点之间的弧度值，系统根据弧度值排序。

&fl=*,score&sort=score asc&q={!geofilt score=distance sfield=poi_location_p pt=54.729696,-98.525391 d=10}。

2) 按距离排序，距离越远排名越高，加上score=reciDistance，其中reciDistance 范围是0~1 采用倒数的方式计算，故与distance的排序刚好相反

&fl=*,score&sort=score asc&q={!geofilt score=reciDistance sfield=poi_location_p pt=54.729696,-98.525391 d=10} 

3) 距离仅作排序不做过滤，在条件中设置filter=false，其中d只是确定形状的作用,不起限制作用。

&fl=*,score&sort=score asc&q={!geofilt score=distance filter=false sfield=poi_location_p pt=54.729696,-98.525391 d=10}

4) 结合关键词查询和距离排序，此时关键字只能作为过滤条件（fq）不能作为查询条件，仅作为过滤域。

&fl=*,score& fq=store_name:农业&sort=score asc&q={!geofilt score=distance sfield=poi_location_p pt=54.729696,-98.525391 d=10}

5) 当关键字和距离都作为排序条件时，可以用qf参数设置权重

&fl=*,score& fq=store_name:农业&sort=score asc&q={!geofilt score=distance sfield=poi_location_p pt=54.729696,-98.525391 d=10} &defType=dismax&qf=store_name^10+poi_location_p^5

2.图形搜索（在美团CRM中对应地图模式搜索）

在美团CRM中主要有以下几种场景：

1) 直线附近1km商家搜索

&fl=*,score&sort=score asc&q=poi_location_p:"Intersects(LINESTRING(116.38263702392578 39.86653357724533,116.4935302734375 39.8578370694061) d=1

2) 正常多边形范围内的商家

&fl=*,score&sort=score asc&q=poi_location_p:"Intersects(POLYGON ((116.37714385986328 39.88392328618825,116.46709442138672 39.86627006289872,116.40392303466797 39.83358644035512,116.33525848388672 39.85124807212413,116.37714385986328 39.88392328618825))) distErrPct=0

3）复杂（如自相交）多边形范围内的商家

对于这种自相交的多边形，Solr默认认为是非法的，会抛出类似这样的异常：
com.spatial4j.core.exception.InvalidShapeException: Self-intersection at or near point (116.4272689819336 39.875755941712825, NaN)，因此在将参数传入solr前，需要基于标准 Douglas-Peucker Algorithm 算法对多边形进行处理，处理后能去掉自相交的部分，效果如示意图所示：

处理后，自相交的部分变为3和6两个点。当然经过处理后的多边形数据会损失一些精确度。

简化前：

POLYGON((116.4272689819336 39.875755941712825,116.50142669677734 39.84966661865515,116.4059829711914 39.83068633533497,116.48357391357422 39.8873480121113,116.47808074951172 39.827258780634594,116.47773742675781 39.8177661982179,116.41319274902344 39.87048617098581,116.4272689819336 39.875755941712825))

简化后：

POLYGON ((116.4272689819336 39.875755941712825,116.45455487823865 39.866156528285366, 116.48357391357422 39.8873480121113, 116.48079281261445 39.85692579689432,116.50142669677734 39.84966661865515,116.47973485573046 39.84535290095104,116.47808074951172 39.827258780634594,116.47773742675781 39.8177661982179,116.45096720829837 39.8396320628827,116.4059829711914 39.83068633533497,116.43551562011505 39.85225289138226,116.41319274902344 39.87048617098581,116.4272689819336 39.875755941712825)）

简化后查询语法变为：

&fl=*,score&sort=score asc&q=poi_location_p:"Intersects(POLYGON ((116.4272689819336 39.875755941712825,116.45455487823865 39.866156528285366, 116.48357391357422 39.8873480121113, 116.48079281261445 39.85692579689432,116.50142669677734 39.84966661865515,116.47973485573046 39.84535290095104,116.47808074951172 39.827258780634594,116.47773742675781 39.8177661982179,116.45096720829837 39.8396320628827,116.4059829711914 39.83068633533497,116.43551562011505 39.85225289138226,116.41319274902344 39.87048617098581,116.4272689819336 39.875755941712825)) distErrPct=0

无论是范围查询还是图形搜索，他们的查询基本流程都类似，主要分为下面2步：

1、解析查询，生成Query树：获得相应的QParse（SpatialFilterQParser）, 对查询串进行语法解析，获得查询串的各个参数，并且获得相应的查询Query（包括相应的Filter），其中也计算了查询Shape的一些属性，如最大索引长度detailLevel。

 Query result = null;
 if (type instanceof SpatialQueryable) {
    double radius = localParams.getDouble(SpatialParams.SPHERE_RADIUS, DistanceUtils.EARTH_MEAN_RADIUS_KM);
    SpatialOptions opts = new SpatialOptions(pointStr, dist, sf, measStr, radius);
    opts.bbox = bbox;
    result = ((SpatialQueryable)type).createSpatialQuery(this, opts);
 }

2、查询：SolrIndexSearch.search()进行创建Weight树和Score树，利用不同的filter和score策略得到符合条件的docIdSet。而对于几种不同的几何图形关系，Solr提供了几种不同的filter类来计算，这些filter都继承AbstractPrefixTreeFilter类，简单来说就是获取与查询Shape相交的所有子Cell，然后再与term进行匹配的过程。

#总结
本文详细分析了空间搜索的原理以及基于Solr的实践，随着移动互联网时代的到来以及lbs技术的普及，空间搜索技术的应用场景会越来越多，同时随着美团的不断发展壮大，越来越多的商家会加入美团这个平台，对于空间搜索的挑战也将越来越大，此文仅仅作为抛砖引玉，空间搜索技术还有很多值得深入挖掘的地方。

#参考

• http://wiki.apache.org/solr/SolrAdaptersForLuceneSpatial4
• https://cwiki.apache.org/confluence/display/solr/Spatial+Search#SpatialSearch-SpatialRecursivePrefixTreeFieldType(abbreviatedasRPT)
• http://lucene.apache.org/
• http://zh.wikipedia.org/wiki/%E9%81%93%E6%A0%BC%E6%8B%89%E6%96%AF-%E6%99%AE%E5%85%8B%E7%AE%97%E6%B3%95
• http://www.vividsolutions.com/jts/JTSHome.htm
• http://en.wikipedia.org/wiki/Well-known_text
• https://github.com/spatial4j/spatial4j
• http://dataknocker.github.io/2014/04/11/solr%E7%A9%BA%E9%97%B4%E7%B4%A2%E5%BC%95%E5%8E%9F%E7%90%86%E5%8F%8A%E6%BA%90%E7%A0%81%E5%88%86%E6%9E%90/

概述前一篇文章(美团Android自动化之旅—生成渠道包)介绍了Android中几种生成渠道包的方式，基本解决了打包慢的问题。但是，随着渠道越来越多，不同渠道对应用的要求也不尽相同。例如，有的渠道要 ...