Solr&lucene 默认的spatial search性能总结

简介: 假期重新把之前在新浪博客里面的文字梳理了下,搬到这里。介绍地理搜索性能优化的一些经验。

参考性的一些测试总结啊。geohash是有误差的,不要凭直觉说是精准的。

geohash算法

算法的主要思想是对某一数字通过二分法进行无限逼近,比如纬度lat的区间是[-90,90],假如给定一个纬度值lat46.5,可以通过下面算法对46.5进行无限逼近:

 1)把区间[-90,90]进行二分为[-90,0),[0,90],称为左右区间,可以确定46.5属于右区间[0,90]

 2)递归上述过程46.5总是属于某个区间,无论第几次迭代46.5总是属于某个区间[a,b]。随着每次迭代区间[a,b]总在缩小,根据极限可知[a,b]会收敛到46.5,用δ来描述就是,任意给定一个ε,总存在一个N使得:δ=|x-a/2N |< ε,x为任意给定的纬度

 3)上述分析过程保证了算法收敛性的同时,再记录一下收敛的过程:如果给定的纬度x46.5)属于左区间,则记录0,如果属于右区间则记录1,这样随着算法的进行会产生一个序列1011100,序列的长度跟给定的收敛次数N相关。

反过来,如果我们知道了序列1011100,我们就可以分别能确定纬度x46.5)属于哪个更小的迭代区间,也就是说该算法是可逆的

 4)算法的精度:显然的是,不可能让计算机执行无穷计算,加入执行N此计算,则x属于的区间长度为(b-a)/2N+1 ,以纬度计算为例,则为180/2N,误差近似计算为:err= 180/2N+1 =90/2N ,如果N=20,则误差最大为:0.00009。但无论如何这样表明Geohash是一种近似算法。


solr3.4实现的geohash fieldtype实现

geohash默认是没有grid的,尽管lucene有相关接口,而solr没有暴露,正直solr spatial争论期啊。而是将经纬度转为对应的 trie类型域分别隐藏构建,查询的时候更加坐标点、d,在spatialqueryparse里面,准确说是geohash fieldtype createfield中,会生成对应精度的trie区间查询、维度的trie区间查询。这个实现在单core 100w级索引规模下,满足上线需求:50+TPS100ms以内的响应返回。在单core 2300w下,尽管tps可以达到15左右,但是查询响应时间平均在 500ms+,上线基本上杯具了,为了提升性能,加大cache,此时对内存依赖巨大,伤不起。执行分组500w 或者 1000w,性能有较大提升,满足上线需求。


solr4.1实现的geohash  

4.1 中实现的geohash,采取4叉树分grid构建索引,并且支持各种shap查询。  2300w地理数据下,tps30左右,对内存依赖大大降低,但是在命中数据较大的场景下,返回时间超过500ms。对于简单的filter过滤,同时配合非地理的搜索请求,请求在100ms以内返回。压测情况下,存在一个不真实问题,就是连续几个耗时的query的话,一下子就落下来了请求tps,内存被一次请求占用空间、时常明显增多,从而不同的query实例对影响波动影响不可忽视。总体相对3.4的实现有优势。

   
保证稳定的前端地理搜索请求,建议分组1000w以内,内存cache尽量开启到最佳。在4core 8G memory虚拟机环境。


地理搜索优化

filtersort时候都需要执行地理距离的计算,命中结果数量直接影响响应时间,这是硬伤。此时,有几种距离公式可供选择,分析如下,折中选择就是 Haversine 距离计算了。

Lucene 包含了根据大圆(Haversine)公式计算距离的工具(参见 DistanceUtils DistanceFieldComparatorSource),


Solr 包含几个用于计算距离的FunctionQuery 函数:

大圆(Haversine Geohash Haversine

Euclidean  Squared Euclidean

http://en.wikipedia.org/wiki/Euclidean_distance 欧几里德距离公式

vectorDistance  向量距离

Manhattan 和其他p-norm

曼哈顿距离 http://en.wiktionary.org/wiki/Manhattan_distance

常见距离公式如下

http://stackoverflow.com/questions/2096385/formulas-to-calculate-geo-proximity/2097779#2097779

大圆距离公式

Vincenty 公式 假设地球 扁圆球体

Haversine 公式


球面余弦法

Vincenty 公式 是死慢,但是很精准( 0.5 毫米)。http://en.wikipedia.org/wiki/Vincenty's_formulae


Haversine 半正式公式always快,相比Vincenty 公式,我能够运行计算在大约 6 万秒,这是或多或少可以接受满足我的需要。

http://en.wikipedia.org/wiki/Haversine_formula

haversin(θ) = sin2(θ/2).


球面余弦定理倍快了, 大约是haversine2倍,大部分情况下精度差异可以忽略,也就是说余弦法精度低于Haversine

 http://en.wikipedia.org/wiki/Spherical_law_of_cosines


影响性能还与数据密度有关

    测试中发现,北京、上海、广州这些地区,相同d距离内,命中结果比较大,响应时间也较大。


计算距离与精度关系

距离准确有点慢,距离精度放大,此时速度快。并且filtersort都是需要距离 1 1 的计算的,伤不起。丢失精度的话,可以对统一微区域做一次距离计算 或者 直接不计算,转为文本相关性控制排序。


测试排查比较麻烦

出来的结果如果精度控制不好,距离计算结果趋同明显,相似结果的"人肉check"不方便,单纯看经纬度,不能直观发现问题。spatial-solr-sandbox-master 开源项目提供了可视界面,还没来得及整合起来,后续再整了。


地理搜索精度比性能更加突出

因为地理搜索更多的是应用在导航、移动终端,查询的时候需求都是周围范围,周围的精度都一般是50m100m500m1000m1500m2000m6个区间。出来的结果在地图上展示靠不靠谱一目了然,并且可以切换到其他地理搜索比对结果,质量精度好坏非常容易比较。上线需慎重,所以说精度比性能更关键。


可能比较理想的质量优化思路

目前看针对具体数据集的分布、查询特征,来具体选择哪种精度距离公式了。精度优先然后优化性能了。一般性的压测作为baseline参考。而这个大前提是数据的经纬度传入是正确的,如果源头都不正确,反应到后续的结果误差就无从处理了。


寻求更优的地理空间模型,对地理数据建模到lucene索引中

 

目录
相关文章
|
6月前
|
Java Apache 索引
10 Lucene索引库查询 - queryparser查询
10 Lucene索引库查询 - queryparser查询
22 0
|
8月前
|
XML 搜索推荐 安全
lucene、solr、es的区别以及应用场景
@[TOC](目录) Lucene、Solr 和 Elasticsearch(ES) 都是基于 Lucene 引擎的搜索引擎,它们之间有相似之处,但也有一些不同之处。 Lucene 是一个低级别的搜索引擎库,它提供了一种用于创建和维护全文索引的 API,以及一些搜索和排序算法。Lucene 主要用于构建自定义搜索引擎,例如在 Java 应用程序中使用。 Solr 是 Lucene 的一个扩展,它提供了一个完整的搜索引擎框架,包括了索引、搜索、排序、过滤等功能。Solr 旨在为大规模数据集提供高性能的全文搜索功能,因此它支持分布式搜索、实时搜索和自定义排序和过滤器等功能。 Elasticsear
128 0
|
存储 自然语言处理 算法
Elasticsearch Query DSL之全文检索(Full text queries)上篇
Elasticsearch Query DSL之全文检索(Full text queries)上篇
Elasticsearch Query DSL之全文检索(Full text queries)上篇
|
自然语言处理 Java 关系型数据库
Elasticsearch Query DSL之全文检索(Full text queries)下篇
Elasticsearch Query DSL之全文检索(Full text queries)下篇
|
缓存 Java 索引
Solr&Lucene cache简要汇总
假期重新把之前在新浪博客里面的文字梳理了下,搬到这里。本文汇总Solr Lucene cache相关内容。撇开系统结构、架构这些整体性的分析,纯粹从使用方面做梳理。
185 0
Solr&Lucene cache简要汇总
|
Java 数据格式
Solr4.1 spatial solrj search demo
假期重新把之前在新浪博客里面的文字梳理了下,搬到这里。本文介绍solr的地理搜索Demo。
132 0
|
SQL 机器学习/深度学习 自然语言处理
全面解剖 Solr query 到lucene query
假期重新把之前在新浪博客里面的文字梳理了下,搬到这里。围绕从顶之下,从粗到西的关系认识solr 查询流程和实现细节。最低下定位到queryparse的实现。整个过程围绕信息检索这一思路展开,而不是工程实现来看这个问题。目的从整体结构上认识查询这一块的抽象。这样有具体需求的时候,可以知晓参照按个query、从哪个点注入系统中比较省事,而无需侵入solr、lucene底层。
224 0
全面解剖 Solr query 到lucene query
|
存储 算法 Java
Lucene/Solr Optimize相关总结
假期重新把之前在新浪博客里面的文字梳理了下,搬到这里。
148 0
|
测试技术
solr&lucene spatial search 大规模地理搜索性能堪忧
假期重新把之前在新浪博客里面的文字梳理了下,搬到这里。最早发布时间2013年的时候。以下内容非最新版本的性能表现。
101 0
|
自然语言处理
Lucene QueryParser的一个"解析异常"
假期重新梳理了下之前在新浪博客的历史文档(新浪博客已下线),将一些内容重新搬到这里。 本文Lucene QueryParser的一个解析异常分析。
89 0