参考性的一些测试总结啊。geohash是有误差的,不要凭直觉说是精准的。
geohash算法
算法的主要思想是对某一数字通过二分法进行无限逼近,比如纬度lat的区间是[-90,90],假如给定一个纬度值lat:46.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)上述分析过程保证了算法收敛性的同时,再记录一下收敛的过程:如果给定的纬度x(46.5)属于左区间,则记录0,如果属于右区间则记录1,这样随着算法的进行会产生一个序列1011100,序列的长度跟给定的收敛次数N相关。
反过来,如果我们知道了序列1011100,我们就可以分别能确定纬度x(46.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+TPS、100ms以内的响应返回。在单core 2300w下,尽管tps可以达到15左右,但是查询响应时间平均在 500ms+,上线基本上杯具了,为了提升性能,加大cache,此时对内存依赖巨大,伤不起。执行分组500w 或者 1000w,性能有较大提升,满足上线需求。
solr4.1实现的geohash
4.1 中实现的geohash,采取4叉树分grid构建索引,并且支持各种shap查询。 在2300w地理数据下,tps在30左右,对内存依赖大大降低,但是在命中数据较大的场景下,返回时间超过500ms。对于简单的filter过滤,同时配合非地理的搜索请求,请求在100ms以内返回。压测情况下,存在一个不真实问题,就是连续几个耗时的query的话,一下子就落下来了请求tps,内存被一次请求占用空间、时常明显增多,从而不同的query实例对影响波动影响不可忽视。总体相对3.4的实现有优势。
保证稳定的前端地理搜索请求,建议分组1000w以内,内存cache尽量开启到最佳。在4core 8G memory虚拟机环境。
地理搜索优化
filter和sort时候都需要执行地理距离的计算,命中结果数量直接影响响应时间,这是硬伤。此时,有几种距离公式可供选择,分析如下,折中选择就是 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).
球面余弦定理,倍快了, 大约是haversine的2倍,大部分情况下精度差异可以忽略,也就是说余弦法精度低于Haversine
http://en.wikipedia.org/wiki/Spherical_law_of_cosines
影响性能还与数据密度有关
测试中发现,北京、上海、广州这些地区,相同d距离内,命中结果比较大,响应时间也较大。
计算距离与精度关系
距离准确有点慢,距离精度放大,此时速度快。并且filter、sort都是需要距离 1 对1 的计算的,伤不起。丢失精度的话,可以对统一“微区域”做一次距离计算 或者 直接不计算,转为文本相关性控制排序。
测试排查比较麻烦
出来的结果如果精度控制不好,距离计算结果趋同明显,相似结果的"人肉check"不方便,单纯看经纬度,不能直观发现问题。spatial-solr-sandbox-master 开源项目提供了可视界面,还没来得及整合起来,后续再整了。
地理搜索精度比性能更加突出
因为地理搜索更多的是应用在导航、移动终端,查询的时候需求都是周围范围,周围的精度都一般是50m、100m、500m、1000m、1500m、2000m这6个区间。出来的结果在地图上展示靠不靠谱一目了然,并且可以切换到其他地理搜索比对结果,质量精度好坏非常容易比较。上线需慎重,所以说精度比性能更关键。
可能比较理想的质量优化思路
目前看针对具体数据集的分布、查询特征,来具体选择哪种精度距离公式了。精度优先然后优化性能了。一般性的压测作为baseline参考。而这个大前提是数据的经纬度传入是正确的,如果源头都不正确,反应到后续的结果误差就无从处理了。
寻求更优的地理空间模型,对地理数据建模到lucene索引中