郭显娥

（山西大同大学数学与计算机科学学院,山西大同037009）

云计算系统中Key-Value数据管理研究

郭显娥

（山西大同大学数学与计算机科学学院,山西大同037009）

Key-Value数据库是应用于云环境下的典型云存储系统，基于key-value数据模型的研究对大数据管理或称云数据管理系统提出了新的需求与挑战，成为人们关注的热点。本文对key-value数据模型与数据读写方式作了简单介绍，引入了key-value索引机制，重点讨论了key-value查询操作，给出了关于多维点查询的通用算法。

key-value数据模型；索引机制；查询操作

随着大数据、云计算、互联网技术的发展，以PB（1014 terabytes）或EB（100万TB）级的大数据（包括结构化的、半结构化的和非结构化的）应运而生，体现在电子商务、计算机仿真、社交网络、物联网、移动服务等众多领域。传统的关系数据库在数据存储、索引和查询处理等方面很难实现高效性、灵活性和可扩展性，取而代之的是非关系型的、分布式的数据存储系统NoSQL。NoSQL数据库典型产品有:基于Hadoop HDFS的HBas，Amazon公司的Dynamo，Google公司的BigTable等。

在NoSQL数据库中，数据的存储采用弱关系的数据模型，即key-value数据模型。关于keyvalue数据模型的NoSQL数据库系统研究，与NoSQL相关的关系云系统和MapReduce框架的相关研究，已成为人们关注的热点[1-5]。本文将介绍key-value的数据模型与数据的读写方式，索引和查询功能等，重点讨论key-value查询操作，并给出简单的算法。

1 Key-Value数据管理

Key-Value数据管理功能，包括：key-value数据存储、数据读写方式、索引机制与查询功能。

1.1 Key-Value数据存储

Key-Value数据存储可以理解为＜key,value＞二元健值对，即一个key对应一个value值，其中key值和value值的数据类型不限，或许key值为一个文件名，而value取值可以是相应的文件，也许key值为一张图片，而value是图片对应的拍摄时间、地点与主题等，更简单的例子是一个ID号（key值）与对应的教师信息（value值），用表1来描述。

表1 Key-Value 键值对

表1不是简单的二维表，而是key与value的映射关系。Key-Value数据模型是基于健值对的数据存储模型，采用分布式Hash，实现从key至value上的映射。

1.2 读写方式

key-value数据库数据的读写方式，采用面向磁盘的读写方式。如图1所示。

图1 面向磁盘的读写方式

其工作原理是，首先数据被写入内存中，系统返回写入成功，当内存中数据量大时，会被批量写入磁盘文件；其次，在读取数据时，优先访问内存，如果未得到需要的数据，则从磁盘文件读取数据，当返回错误信息时，则要调用日志进行数据恢复。这种磁盘读写方式要求数据库进行定期的数据合并，将过期的冗余数据删除。

1.3 索引机制

基于key-value的存储模型，其索引机制采用的是hash索引和B-tree索引等。

hash索引是指把关键值key直接映射到内存地址，实现快速查询，用公式表示为：ID=H(key)（H是哈希函数）。常见的有链接桶hash，可扩展hash，线性hash等。

B-tree称为多路搜索平衡树，由根节点，分支节点和叶子节点构成，通常将数据存放于leaf node，而任何一个leaf node的最短路径的长度是相同的。由B-tree索引相继研究出R-tree索引与B+-tree索引等。

1.4 查询功能

key-value数据查询分为简单查询和复杂查询。复杂查询留给应用层实现，常用的是MapRe⁃duce框架；简单查询包括单点查询和多维点查询，下面详细介绍这两种查询。

1.4.1 单点查询

单点查询是通过对DB的操作完成的，即数据的查询会按照key值，查询到相关的Key-Value节点，如果没有查询到Key-Value节点，则说明数据不存在，如果查询到Key-Value节点，那么判断Key-Value 节点的状态（set∕get∕delete），如果是 delete，则说明节点被删除，否则，返回value给查询者。

为了提高数据的查询效率，在内存建一张hash表。当存储的数据非常多的时候，系统会根据配置文件中设计的阀值，进行一次rebuild的过程，re⁃build的过程结束后，会在内存生成hash结构。

rebuild过程主要分为三步：排序、截断、建立hash表。主要的数据结构如下：

在HashDB上Key-Value链表达到rebuild的阀值时，会触发rebuild线程的开启，具体的re⁃build的过程为：

Step1：拷贝当前链表到temp指针下，同时记下这时的Key-Value链表的头指针。

Step2：排序，在排序的过程中，去掉冗余的节点。排序采用一种快排的方式。

Step3：截断：把排好序的链表，从中间截断，新建一个HashDB，把较大的那个链表交给这个新建的HashDB管理。

Step4：建立hash表：把Key-Value链表的最大值和最小值填写到管理这个Key-Value链表的HashDB中，把在rebuild过程中，所有新增的数据按照新的hash值加入到这两个Key-Value链表中。

至此，一次rebuild过程结束，同时删除原来的Key-Value链表。

1.4.2 多维点查询

定义1:当键有2个值时，称为二维点，键有多个值时，称为多维点，这里以d维点(d＞2)为例，记为：key=(v1,...,vd)，涉及到多维点的查询叫做多维点查询，d维点查询记为Qd(key)。

关于多维点查询算法的设计思路：

先将多维数据进行划分（划分方案决定查询的效率），采用降维的方法，逐维划分；其次，根据划分方案，将所有数据划分为互不相交的立方体簇群，对于每一个簇群建立相应的B-tree或R-tree索引；最后，将第二步产生的各个B-tree或R-tree合并，生成大的B-tree或R-tree树进行查询。

设B-tree上节点最小多维区域为：{[k1,m1],…,[kd,md]}，（i={1，2…,d}，ki≤vi≤mi）；Ni：表示包含key索引节点的立方体簇集；C：以key为中心、R为边长的最大立方体；Ci:表示在i维度上划分的子簇集。

多维点查询算法描述为：

(4)for i=1 to d do∕∕（d是维数）将立方体C不断分割

(5) 将C在第i个维度上根据ki和mi划分成C0，C1和C2;∕∕C被Ni在各个维度上连续地划分成若干子立方体簇群,搜索的范围将从不同的维度进行分割并发出响应到邻居，即分割结束后其相邻的范围再进行空间分割。如果在该小立方体内无法找到要查询的范围信息，则会发送请求到其相邻的立方体，当相邻立方体收到请求后，会调用同样的算法对内部空间进行分割并索引，直到找到要查询的范围内的节点并最终返回给客户端。

多维点查询的应用，如基于地理位置的服务：输入对象的经度、纬度、时间就可以进行查询；如图片的共享服务；如网购服务等。

2 进一步的研究

为了扩大key-value数据存储的应用，增强key-value存储数据库系统的支持功能，例如海量数据的复杂查询，分布式事务处理能力等。研究者需要进一步地关注以下问题：

（1）根据用户的不同需求，结合云环境的特性，需要改进key哈希的数据分布模式，使其提供灵活的、可优化的海量数据查询定义模型，实现各种复杂查询和数据分析。

（2）在云计算环境下，对海量数据的索引机制需要进一步思考。特别是在构建全局索引，基于线性化技术的索引与基于HugeTable的索引等方面，需要新的研究成果。

（3）为了有效地支持大数据管理与查询处理，将面向批处理的系统（基于MapReduce框架）和面向服务的系统（NoSQL数据库）相结合的应用问题，如Hadoop和Hbase相结合、Hadoop和PNUTS相结合；云环境下数据管理的数据安全问题；支持数据管理的支持系统的能耗问题等，都是目前研究的热点。

3 结束语

随着数据量呈指数级的增长，大数据、云计算、互联网时代的到来，云计算得到了广泛的应用，Key-Value数据库是应用于云环境下的典型云存储系统，被业界广泛关注。本文利用较短的篇幅介绍了Key-Value的数据模型与数据的磁盘读写方式，引入了Key-Value的Hash索引与B-tree索引，较详细地讨论了Key-Value的单点查询与多维点查询功能，最后给出了基于Key-Value数据库的进一步研究课题。

[1]申德荣,于戈.支持大数据管理的NoSQL系统研究综述[J].软件学报,2013,24(8):1786-1803.

[2]张峰.云计算应用服务模式探讨 [J].信息技术与信息化，2012（2）:81-83.

[3]金柏统，王振宇，许文君，等.基于云计算的数据管理[J].电子制作，2014（1）：127.

[4]孟燕，郭冬梅.云计算及基数据存储与管理技术研究[J].信息技术与信息化，2012（7）：73-76.

[5]王珊,萨师煊.数据库系统概论[M].4版,北京:高等教育出版社,2006.

Key-Value Data Management in Cloud Computing System

GUO Xian-e
（School of Mathematics and Computer Science,Shanxi Datong University,Datong Shanxi,037009)

Key-Value database is a typical cloud storage system applied within Cloud Computing environment.Based on re⁃searches on Key-Value data model,the new demands and challenges emerged for big data management,or Cloud Data Management be⁃came the new focal point of this area.This article started with a brief introduction on Key-Value data modeling and data input and out⁃put methods.Then with the combination of Key-Value index mechanism,the author emphasized on Key-Value indexing operation,pro⁃viding a general algorithm on Multidimensional Query.

Key-Value data model;index mechanism;query operation

TP311

A

1674-0874(2015)05-0001-03

2015-02-20

山西大同大学教研项目[X JY-2013207]；山西大同大学校级特色专业建设项目[X TS2004-01]）；山西省高等学校大学生创新创业训练项目[2 015344]

郭显娥(1964-)，女，山西浑源人，硕士，教授，研究方向：数据挖掘。

〔责任编辑 高海〕