面向大规模空间信息的高性能缓存设计方法

摘要

本发明公布了一种面向大规模空间信息的高性能缓存设计方法，包括：所有的数据都在分布式环境的内存中进行组织和管理；将所有的空间信息以地理要素为单位进行统一组织和管理；将空间分成不同层次、不同区域的空间格网，并使用Geohash算法进行编码；采用基于磁盘顺序访问的全量数据持久化和增量数据持久化相结合的方式进行持久化操作。本发明所述的技术方案，能够充分利用内存访问效率高的优势，提供较高的地理空间数据的访问性能，满足支持大规模并发的数据访问需求。

说明书

技术领域

本发明属于高性能地理信息计算领域，具体涉及一种在服务端多台机器的分布式环境中 面向大规模空间信息的高性能缓存设计方法。

背景技术

随着互联网以及移动技术的发展，越来越多的信息和地理位置相关，越来越多的人可以 通过网络访问地理信息。这对于访问地理位置信息的性能提出了高要求。目前通用的基于硬 盘的空间数据存储，都存在着硬盘访问性能较低的瓶颈。另一方面，硬件技术仍在迅速发展， 内存的容量不断变大，而价格却不断下降。这使得大量数据放在内存中成为可能。而基于内 存的数据访问效率远远高于基于硬盘的数据访问。

目前，地理信息大部分是以文件格式（如shp、mif等文件格式）或者空间数据库的形式 （如PostGIS，Oracle Spatial等）存储在硬盘上。硬盘的数据访问的性能较低，远低于内存 的访问效率。使用内存存储的内存数据库中，有的产品添加了空间索引信息，可以存储空间 数据，如BerkeleyDB采用R树作为空间索引。但是受限于严格的数据库的事务以及完整性 约束，其数据访问性能大打折扣。

最近流行的NoSQL数据库中，CouchDB和MongoDB添加了GeoHash作为空间索引用 来支持空间查询，二者可以利用内存进行部分数据的缓存，但是仍然以硬盘存储为主，而且 仅支持点状数据的查询，没有复杂的几何数据结构支持。Redis实现了全量数据放在内存中的 方案，提供超高性能的数据访问，但是Redis目前不支持空间索引，因此难以支持地理信息 的查询。

发明内容

本发明的目的是在服务端多台机器中提供一种基于分布式内存的面向大规模空间信息的 缓存设计方法。该方法能够充分利用内存访问效率高的优势，提供较高的地理空间数据的访 问性能，满足大规模并发的数据访问需求。

本发明提供的技术方案如下：

一种面向大规模空间信息的高性能缓存设计方法，其特征是，所述设计方法包括以下几 个方面：

1）数据组织方式：所有的数据都在分布式环境的内存中进行组织和管理；将所有的空间 信息以地理要素为单位进行统一组织和管理，在分布式内存中，每个地理要素按照（Key， Value）对的形式进行组织，其中每个Key值，是一个字符串，包含地理要素所在的专题图层 名和图层名内唯一的标识，每个Value是一块连续的内存区域，顺次保存了地理要素的属性 名和属性值；

2）空间索引方式：将空间分成不同层次、不同区域的空间格网，并使用Geohash算法进 行编码；每个空间格网按照地理要素的方式进行存储，称之为格网要素，格网要素的Key值 是该空间格网对应的区域经过Geohash编码之后的字符串，格网要素的Value值包含了与该 格网相交的地理要素的信息；每一个与该格网要素相交的图层作为该格网要素的一个属性， 属性名是图层名称，属性值是图层中在这个格网区域中的要素的Key值的数组；对空间的查 询通过哈希映射来实现。

所述的高性能缓存设计方法，其特征是，所述设计方法进一步包括：

3）持久化方式：采用基于磁盘顺序访问的全量数据持久化和增量数据持久化相结合的方 式进行持久化操作。

所述的高性能缓存设计方法，其特征是，所述Key和Value之间经过两步哈希映射，第 一步采用分布式哈希算法，从Key映射到节点机器；第二步在第一步映射到的节点机器上， 从Key值映射到内存地址。

所述的高性能缓存设计方法，其特征是，数据修改时，在被修改的地理要素上加锁，同 一时间，只能有一个客户端对要素进行修改。

所述的高性能缓存设计方法，其特征是，空间查询时，首先将要查找的区域经过Geohash 转换成相交的格网要素的Key值，再将格网要素的Key值经过所述的两步哈希映射到节点机 器的内存中，进而找到格网要素的Value值；在格网要素的Value值中通过属性名查找某类别 的地理要素的Key值；通过Key值再查找相应的地理要素。

所述的高性能缓存设计方法，其特征是，所述持久化方式包括：

3.1）全量数据持久化：每隔一段设定的时间，缓存将内存中全量的数据，顺序地写入硬 盘中；

3.2）增量持久化：每两次内存快照中间，保存每条对数据进行修改的请求，以日志的形 式，顺序地写入到磁盘中。

所述的高性能缓存设计方法，其特征是，所述持久化方式进一步包括：

3.3）缓存重建：当服务故障后，先从硬盘中导入最近一次的内存快照，然后按快照后的 日志信息重新模拟请求，来进行缓存重建。

本发明的有益效果：本发明所述的技术方案，能够充分利用内存访问效率高的优势，提 供较高的地理空间数据的访问性能，满足支持大规模并发的数据访问需求。

附图说明

图1本发明方法示意图。

具体实施方式

本发明提供的技术方案具体包含如下三个方面：数据组织、空间索引、异步持久化（如 图1所示）。

1.数据组织

传统数据库中的地理要素数据是以图层作为组织单位，地理要素存储为图层中的一条记 录。对于图层中的某个地理要素的操作，要确保满足该图层的事务特征以及完整性约束。本 发明中数据组织的特点在于取消图层作为数据组织单位的作用，进而舍去传统数据库中对于 表的复杂的事务以及完整性的约束。将所有的地理空间信息以地理要素为单位进行统一地组 织和管理。

（1.1）缓存开始工作时，会从传统空间数据库或者文件中逐条读取地理要素。

（1.2）在分布式内存中，地理要素通过（Key，Value）对的形式进行组织。

（1.3）地理要素的Key是一个字符串，可以由应用程序自己定制，但是必须包含传统矢 量格式中的图层名称和地理要素唯一ID，能够根据表名和记录的ID直接找到相应的key。

（1.4）地理要素的Value是一块内存区域，顺次保存地理要素的属性名和属性值。

（1.5）地理要素的Key和Value地址之间通过哈希函数进行映射。映射的过程分两步， 第一步是从地理要素对节点的映射，采用分布式哈希算法（distributed Hash Table， http://en.wikipedia.org/wiki/Distributed_hash_table），根据地理要素的Key值找到存有该地理要 素的节点机器；第二步是在第一步的基础上，根据地理要素的Key值根据哈希算法计算出在 这个节点机器的内存中地址。

（1.6）数据的添加、删除、更新以地理要素为单位。数据修改时的锁也是以地理要素为 单位。同一时间，对于同一个地理要素，只能有一个客户端进行修改。

2.空间索引

传统的空间数据组织中，常用四叉树、R树数据结构作为空间索引。以上两种空间索引 能够显著加速空间查找，时间代价为O(log(n))。但是存在两个问题：动态更新时，维护空间 索引的成本较大；不利于分布式的扩展。本发明设计采用GeoHash （http://en.wikipedia.org/wiki/Geohash）算法构建空间索引。将空间划分成不同层次、不同区 域的格网，并对格网进行Geohash编码。每个格网中保存在其中的地理要素的Key值，使得 空间查询效率在O(1)复杂度，同时动态更新数据时，维护空间索引的代价较小。本发明中的 空间索引设计包含以下几个方面：

（2.1）将空间分成不同层次，不同区域的格网，并使用Geohash算法进行编码。

（2.2）每一个格网以前面第1部分中地理要素形式来管理，满足从第1.1~1.6所述的特 征。下文中每个表示格网的地理要素简称为格网要素。

（2.3）格网要素的Key值是该格网对应的空间格网区域经过Geohash编码之后的字符串。

（2.4）格网要素的Value值是该格网包含的地理要素信息。每一个与该格网要素相交的 图层名为该格网要素的一个属性，属性名是图层名，属性值是图层中在这个格网区域中的地 理要素的Key值的数组。

（2.5）空间查询时，通过格网索引找到地理要素的Key值，再通过Key值进行哈希（Hash） 找到地理要素的实际内存地址。因此本设计中空间索引和数据的存储相分离，即空间索引中 没有保存数据的内存地址，而是通过Key值作为媒介。

（2.6）索引更新。当地理要素的几何属性修改时，先通过修改前的坐标找到对应的格网 要素，删除对该地理要素的引用。然后在修改后的坐标对应的格网要素中添加对该地理要素 的引用。

3.持久化

由于内存中的数据断电丢失，因此需要将数据持久化到硬盘中，以防备服务器故障导致 的数据丢失。因为持久化的过程需要和磁盘交互，IO效率较低。而在磁盘数据访问中，由于 磁头寻道的时间远大于磁头读取块数据的时间，因此顺序访问的效率远高于随即访问的效率。 本发明设计中，为了使持久化过程不影响缓存系统的性能，本设计采用基于磁盘顺序访问的 全量数据持久化和增量数据持久化相结合的方式。其中：

(3.1)全量数据持久化。每隔一段设定的时间，缓存会将内存快照，即内存中全量的数据， 顺序地写入硬盘中。

(3.2)增量持久化。每两次内存快照中间，会保存每条对数据进行修改的请求，以日志的 形式，顺序地写入到磁盘中。

(3.3)缓存重建。当服务故障后，先从硬盘中导入最近一次的内存快照，然后按快照后的 日志信息重新模拟请求，来进行缓存重建。

下面举例说明，在本发明设计中，一个地理要素是如何存储在分布式缓存中以及如何进 行空间查找的。设定某个系统有5台电脑，每台电脑有8G内存。有一个图层为“school”， 其中包含一条记录id为1001，名称name为“北京大学”，几何坐标geom为（116.0，40.0）， 别名alias“北大”，地址address为“北京市海淀区颐和园路5号”，电话tele-number为“62751186”。 那么这条记录在缓存中存储为一个地理要素（设为A），A的Key值可以是：“xxxschool:1001”， Value是一整块保存了其属性的内存区域保存了如下内容：“name:北京大学 |geom.:(116.0,40.0)|alias:北大|address:北京市海淀区颐和园路5号|tele-number:62751186”。进行 哈希映射时，根据A的Key值按照分布式哈希算法找到相应的节点机器为第4台。然后在第 四台节点机器中，再对这个Key值进行哈希映射得到一个内存地址来存储Value值。同时假 如根据Geohash算法得到与A几何位置相交的格网的Geohash字符串是“144285098”，然后 查看对应的格网要素（设为B）是否存在，如果B存在，那么在B的Value中，“school”属 性中增加A的Key值字符串；如果B不存在，则创建这个格网要素B，并添加“school”属 性以及A的Key值。