基于HBase的支持频繁更新与多用户并发的R树

R-tree for Frequent Updates and Multi-user Concurrent Accesses Based on HBase

基于位置服务的应用已经进入大数据时代,传统基于位置服务的技术面临系统扩展性、性能等方面的挑战。云计算技术是大数据处理的基础,索引是优化查询的重要手段。尽管目前已存在大量的研究成果,但尚未有HBase上的支持频繁更新与多用户并发的R树索引。针对移动对象索引的频繁更新与多用户并发的需求,文中提出了基于HBase的支持频繁更新与多用户并发的R树索引,它只索引包含移动对象的网格,避免了频繁更新问题;进一步基于HBase的数据行与数据分区的组织与读写特性,对R树的节点进行重组,并对网格Z-order编码,从而减少了对HBase的读写操作,提高了查询效率;最后提出了基于ZooKeeper分布式读写锁的优化策略,提高了索引的吞吐量。实验结果表明,与网格索引相比,在数据非均匀的情况下,所提策略的查询吞吐量提高了25%~50%,更新吞吐量约在同一数量级;与分布式共享锁索引相比,分布式读写锁索引的吞吐量提高了近40%。

Application based on location based service（LBS）has entered the era of big data.Traditional location based service techniques face new challenges such as scalability,performance,etc.Cloud computing technology is the basis of big data processing and index is an important way to optimize query.Although there exist a large number of research results,as far as we know,there is no R-tree index which supports frequent updates and multi-user concurrent accesses based on HBase.According to the above characteristics of moving objects,this paper proposed a new R-tree index which supports frequent updates and multi-user concurrent accesses based on HBase.In this new index,the R-tree only indexes the grid which contains the moving object to avoide the problem of frequent updating effectively.Furthermore,based on the organization of HBase data rows and I/O characteristics of data partitions,this paper reorganized the nodes and encoded the grid cells with z-order,which reduce the read and write operations of HBase and improve the query efficiency.Finally,it proposed an optimization strategy for distributed read and write locks based on Zookeeper,which improves the throughput of new indexes.The experimental results show that the query throughput of the proposed strategy is improved by 25%~50% and the update throughput is about the same level in the case of uneven data compared with the grid index.Compared with the index using distri-buted shared locks,the query throughput of the index using distributed read and write locks is increased by nearly 40%.