学术大讲堂 |（七）如何应用大数据技术秒杀一个貌似不可能的任务

学术大讲堂

下面我介绍的是大范围高精度栅格可视化的方案，它是我们结合大数据技术解决实际应用问题的一个典型例子，看着有点标题党的味道，其实这里我们想强调的是，我们设计和实现这个方案时，一开始直接调用HBASE检索，看着要检索的数据量，多达数百万，还真是觉得不可能几秒内完成任务。所以这个技术难题，或者说是省公司的业务需求提出来以后很长时间以来我们迟迟没有解决。

直到今年上半年，我们一点点地分析和优化，应用分布式处理的思路去逐步搭建了一个自主研发的可视化专用集群，才很好解决了问题。而在这个过程中，我们一方面对Map-Reduce原理、分布集群的管理等hadoop技术框架有了更深刻的理解，另一方面，也对大数据分布式技术所能提供的算力之强大，有相当震撼的感受。

我们所面临的任务，简单来说就是“基于电子地图的移动网络覆盖质量可视化”。

这里面需要用到的最关键最核心的数据，就是“基于位置的网络信号强度”。

拿到数据后，我们要进行可视化展现了。如果数据量少的话，那么，最直接就展现就是打点：在图上什么位置，指标是多少，就用不同的色系去着色。就象这张图，就是我们生产系统上对研究院旁边的华南师范大学校园的路测数据打点可视化。

当数据量多了之后，打点就解决不了问题了，大量的点会重叠在一起，看不出问题来，所以就引入我们今天要讨论的主角：栅格化展现，也就是在栅格内取数据的统计均值。

另外，关于可视化数据的处理，不管打点还是栅格化，理论上都可以采用两种不同的处理方式。 一种是预切图，就是预先基于数据生成图片，其优点是加载速度极快，另一种是实时生成，就是需要展示时才去获取数据进行渲染，其优点是展示处理灵活，效果丰富多样。

好，任务的内容我们基本介绍清楚了，那么我们初始的解决方案是如何的呢？

首先，最基础的，就是我们的栅格划分，直接看代码，可以有最直观的理解。这是我们判断某个经纬度点归属哪一个栅格的函数。简单地说就是以某个点为原点，然后根据指定经纬度计算与原点的差值跨了多少个栅格，并且把经度方向的编码和纬度方向的编码串起来。

栅格的划分是整理栅格化展示的理论基础，有了它，我们就可以进行数据预处理了。后台的数据预处理包括以下步骤：

MR数据定位

分级汇总

按KEY排序（HBASE）

而前台进行实时展示的处理流程包括以下步骤：

计算关注区域的外接矩形

计算外接矩形内包含的所有栅格的KEY

剔除在关注区域外的栅格

从HBASE查询出所需栅格的数据

基于在线电子地图的Canvas渲染 （在Browser侧的处理)

上述方案存在着以下的不足之处

1．栅格设计的粒度较粗，显示精度低

2．采用KEY枚举的方式查询HBASE，效率较低（右图查询曲线图）栅格数据只进行了简单的按栅格号排序方式存储，在查询小量栅格时性能高，但查询数十万甚至数百万的大量栅格时，由于需要进行逐个栅格检索，检索性能极其低下。

3．关注范围较大时，栅格数据量庞大，服务端处理压力剧增,极易引起WEB服务端内存溢出故障一个营销服务中心，80多万栅格量，直接导致服务端OOM挂死

4．栅格数据量大时，客户端处理压力大。即使运用了canvas高效渲染技术，依靠客户端进行单机处理依然十分耗时。一般情况下最多只能处理数万个栅格的可视化。

所以，最终归结的问题就是：能否/如何实现高精度（象素级）大范围（市、省） 的网络覆盖质量 实时（3秒内） 可视化？

• 优化1——重构栅格，提供象素级别的精细度

根据APGS的定位精度，确定最小栅格为20米（广东境内理论上多达4.5亿个）

栅格级别使用逐级倍增的设计，每个级别均可根据前一个级别直接汇总得到，减少计算量。

根据每个级别下的地图象素距离，选择对应栅格级别：取小于象素距离的最大值。

• 优化2——重组栅格数据的存储结构，实现批量检索。

全高分辨率下，清象素量多达200多万（1920*1080=2，073，600）一般来说，栅格数据的存储结构可以有以下几种方式：

直接编码/链式编码/游程编码/块式编码/四叉树编码

我们对直接编码进行改进采用方阵64*64=4096个栅格合并到一个KEY的方式存储。设某栅格：[经度编号m][纬度编号n]，其对应的KEY=(floor(m/64)+ m%64)*100000+(floor(n/64)+ m%64)

可以看出合并后，需要检索的KEY量大幅减少为：2，073，600/4096 = 506

• 优化3——分布式栅格查询

当栅格量增加到一两百万时，HBASE批量查询耗时快速增长，所以，我们优化为使用分布式并行处理查询两百万栅格，可在2秒内完成。

• 优化4——增加分区设计，提供更优的分布特性

增加KEY的分区设计，使用以下公式确保任意相邻的栅格组不会放在HBASE的同一个REGION SERVER。

栅格组的KEY设计为：[前缀P][经度编号M][纬度编号N]

其中前缀P=（N*j+M）%（j*k） (j,k为正整数），栅格组按P值进行分区存储。

HBASE分区具有以下特性：每一个P值对应一个分区，每一个分区被分配到集群上不同的主机。

所以此机制可保证任意一个小于或等于j*k的矩阵内，P值不会重复，实现良好的分布性。

右图：前缀P=（N*8+M）%64，即j=8,k=8的前缀分布示例。此时P的取值为00-63，共64种，在任意8*8矩阵内，P值不会重复。

• 优化5——采用分布式并行处理实现图片的生成

支持透明度的PNG图片生成是计算密集型任务，比较耗时（所需处理时间大概是JPG的6-7倍）。

集群主机虽然是多核，但CPU主频不高。从图上可看出，调测集群为CUP为1.2G，而我们开发主机为则是3.6G）。

使用5个节点，每节点运行3个worker进程的分布式生成PNG图片（每个栅格组作为一张子图），耗时大幅减少。

栅格边长大于3个象素时，子图会比较少，需要把象素式渲染改为画笔式渲染。

• 优化6——构建从经纬度到象素坐标的快速映射矩阵

经纬度到象素坐标的标准转换过程：

经纬度--》墨卡托投影坐标--》当前屏幕象素坐标，从转换公式可以看出，这是个非线性转换，需要比较复杂的计算。

逐个点转换，1920*1080=200多万个点，比较耗时（实测开销大约为2-3秒）

我们构建纵向和横向映射矩阵，只需转换1920+1080=3000次，其他栅格直接从映射矩阵检索出转换结果（开销可压缩为小于100ms）。

这个图片以我们可视化的总体效果。

最后，小结一下我们大栅格可视化模块的优势：

充分运用计算机集群算力，采用完全分布式的架构完成从数据检索到切片图生成的全过程，实现了全高清分辨率下象素级栅格图的高效可视化功能。

通过重构栅格数据组织结构，把栅格数据进行分组聚合和比邻分区，把数据检索效率提升了10倍以上。

png图片生成是计算密集型任务，而多数PC服务器的CPU主频并不高，执行图片生成任务比较耗时，通过分布式图片生成的方案有效解决两者的矛盾。

运用射线法实现了栅格是否在目标区域的快速判断

设计了X轴方向和Y轴方向两个映射矩阵，实现从栅格号到象素位置的精确而快速定位。

切片图实时生成，满足每个用户的个性化渲染需求。

自研的分布式集群整合到zookeeper统一管理，提供高可用性和易管理性。

从这个组件的开发和优化过程，我们可总结出以下经验：

1.基于大数据的前台应用设计，需要把前台和后台融会贯通，统筹设计。

2.尽可能地把处理任务放在客户端完成，减轻服务端的压力。

3.大数据高耗时的任务则转移到后台，以分布式地架构执行。

— 完 —