基于相似度代价计算的内存数据库集群数据划分

谢玉锋+郑禄

摘要：针对内存数据库集群的数据划分，提出了基于相似度计算的内存数据库数据划分算法。该算法首先根据数据相关性对数据作初步简单划分，然后再基于事务相似度计算，得到最佳事务相似性判断标准，对事务进行相关性合并，进而进一步划分数据，得到合理优化的数据划分结果。算法创新地提出根据Rough集原理计算事务相关性，去除了数据库读写系数的影响，对内存数据库集群的数据划分具有一定指导意义。

关键词：内存数据库；相似度；代价计算；Rough集

中图分类号：TP392

文献标识码：A

文章编号：16727800（2017）004018203

0引言

在数据库集群系统中，数据划分和数据分布是系统运行的基础，做好划分和数据分布可以有效提高系统运行效率。随着内存数据库以及内存数据库集群的出现，针对内存数据库集群的数据划分算法也逐步出现，但都是基于传统数据库集群的解决方案，即仅考虑数据相关性。同时对相似性判断标准都是基于经验性判断选择50%为标准。本文提出基于相似度代价计算的内存数据库集群数据划分策略，在数据相关性基础上提出事务相关性规约，并将相似性判断条件扩大到40%～60%范围内，以更准确、精细地进行数据划分。

1数据划分基本概念

数据划分又称为数据分片或者数据分割，是数据库集群的特征之一，是将集群的数据全集划分为独立的数据片段。数据划分必须遵守3个原则：完整性、不相交性和可恢复性。 数据分片方法有3类：水平分片、竖直分片和混合分片。具体分片策略主要有Range分片算法、Round-Robin分片算法、Hybrid-Range分片算法、表达式分片算法、时间分片算法、哈希分片算法等。 目前数据划分算法主要是针对结构化的关系型数据处理，而且处理过程中将磁盘读取代价作为重要参考标准，处理结果比较固定。这样的数据划分策略对内存数据库集群已不再适用。

2基于Rough集理论的相似度矩阵

在Rough集的研究中[1]，事务被表示成统一的信息系统。假定数据库全集R={ r1，r2，r3...，rn}，ri（1≤i≤n）是数据集中的一个元数据，事务集合T={t1，t2，t3…，tm}，tj（1≤j≤m）是事务集合中的一个事务，trij表示数据ri被事务tj访问，由此可得到事务访问数据矩阵RT。

根据Rough集理论，可以将事务访问数据矩阵对应到信息系统中。假设分配到内存数据库集群的数据集合R={r1，r2，r3...，r8}，事务集合T={t1，t2，t3，t4}，构造事务访问数据矩阵，事务访问了元数据记为1，未访问记为0，假设访问情况如表1所示。

根据数据划分基本原理，即数据之间的相关性，初步对数据进行划分，可得到元数据r1、r4相关性比较强，可以作为一个划分，r2、r8作为一个划分，其余作为独立划分，得到划分结果如表2所示。

再根据事务之间的相关性，将事务进行合并。之前的研究都是确定一个相似度标准，基于粒计算的数据分片算法[23]中标准一般为同时访问相同元数据不小于50%。50%是一个经验值，被普遍认为是一个划分值，在实际部署中，尤其是在内存数据库集群部署中，50%作为一个相似度划分标准并不一定合理。由于内存数据库的读取效率成几何倍数提高，可以适当增加数据划分数量，即提升相似度划分标准。所以提出首先根据不同相似度标准所付出的代价作为划分依据对事务进行划分，然后对数据进行第二次划分，以得到更精确的数据划分结果。 假设通过代价计算，得到事务相似性划分标准为不小于60%，此时t2和t3事务可以合并，合并之后结果如表3所示。 再根据数据相关性，对数据进一步划分，此时r2、r5和r8可以归为同一个划分，得到划分结果如表4所示。 经过划分之后，得到划分结果为R={（r1，r4），（r2，r5，r8），（r3），（r6），（r7）}。

3代价计算划分算法

上文提到的代价计算，在数据进行第二次划分时，假设一个集群中有n个数据划分，数据库总访问值记为D，单位为千次/s，第i个数据划分在时间t内的数据访问值为Di。Di来自两方面，数据库的读和写，分别记为Dri和Dwi。Dri和Dwi是两个单位时间内的累计值，设Dri的变化函数为ri（t），Dwi的变化函数记为wi（t）。可以得到：

上述代价计算是基于内存数据库的数据库读写代价，在之前的传统数据划分中，基于代价计算的D值都引入了读写系数Vrwc，即要考虑主存与磁盘之间的I/O代价[5]。但是因为内存数据库在运行过程中，数据都加载到了内存，读和写操作损耗时间大大减少，因而数据库的读写损耗可以忽略。 数据进行初步划分之后，D值计算依据是在不同事务相似度标准下的不同值，之前会简单地将这一标准选择为超过50%。但是通过研究，这一标准并不一定是最佳标准，所以本文将计算标准限定在40%～60%，分别计算不同标准下的D值。通过比较D值变化趋势，得到最佳判定标准，并依据该标准对事物进行合并，最后再将数据进行相关性划分，进而得到最佳的数据划分。具体步骤如下： 第一步：简单数据关联度划分，以数据同时被相同一组事务访问为依据，判断数据是否相关，如果相关则删除矩阵中被相同事务访问的数据节点，算法描述如下：〖HT5"〗算法1 //输入：事务访问数据矩阵 //输出：去除相同事务访问的节点行的事务访问数据矩阵 数组tri[n]临时存放第i行事务访问数据记录 数组trj[n]临时存放第j行事务访问数据记录 1：for（i=1；i≤m；i++） 2：for（j=i+1；j≤m；j++） 3：tri[i-1]=trin//依次扫描得到第i行事务访问数据记录 4：trj[j-1]=trjn//依次扫描得到第j行事务访问数据记录 5： if （tri[n]==trj[n]） then 6：delete trj[n]//合并关联度较强的独立元数据 7：end if 8：end for 9：end for〖HT〗由以上操作得到经过初步数据关联性划分的事务访问数据矩阵RT。 第二步：代价计算，事务相关性划分基于第一步的数据访问矩阵RT，根据事务同时访问数据的相似程度，计算事务相关性，根据代价计算公式得到合理的相似值为C，常数A=0，B=0。算法描述如下：〖HT5"〗算法2 //输入：事务访问数据矩阵 //输出：去除相同事务访问的节点行的事务访问数据矩阵 数组tri[n]临时存放第i行事务访问数据记录 数组trj[n]临时存放第j行事务访问数据记录 1：for（k=1；k≤n；k++）： 2：for（l=k+1；l≤n；l++） 3：trk[m]=trmk//临时记录第k列数据被事务tr访问的m個值 4：trj[m]=trlk//记录第l列数据被事务tr访问的m个值 5：trk[a]∪trl[a]=1，A++；（a取值为0，1，2…m） 6：trk[a]∩trl[a]=1，B++；（a取值为0，1，2…m） 7：if（B/A≥C）then 8：trk[a]=trk[a]∪trl[a]； //对相似事务进行合并 9：delete trl[m]； 7：end if 8：end for 9：end for〖HT〗上一步算法结束之后，根据第一步算法对矩阵再次进行数据相关性划分，算法结束。

4实验结果分析

实验在30台虚拟机上模拟内存数据库集群，模拟数据中有200个事务和1 000个独立元数据。经过第一步算法划分之后合并为800个数据源，在进行代价计算时，得到访问代价跟事务相似性关系如图1所示。 由图1结果可以得到，当事务相似度标准不小于0.52时，较为合理，在该标准下合并事务，事务合并为132个，再次对数据进行关联性划分，得到640个数据划分。通过该算法可以合理划分数据，有效降低集群访问代价。

5结语

本文通过对传统数据库集群数据划分算法进行分析，基于Rough集的新应用[6]，提出了针对内存数据库集群的数据划分算法。该算法有两次数据划分过程，第一次是普通的根据数据相关性进行数据划分，第二次首先对访问数据的事务进行相关性划分。传统划分是直接以同时访问数据超过50%为标准，本文创新地提出针对内存数据库的访问代价计算方法，对事务进行规约，同时针对内存数据库的特点，忽略磁盘I/O代价。该算法能够合理地划分数据，有效降低集群访问代价。 不过本文所提出的代价计算40%～60%也是一个经验值，没有计算和论证在此范围外的情况。此外数据库访问代价值D是一个整体值，可能会出现单个节点的Di很高，而整体D值较低的情况，使单个节点可能超出了负载能力[7]，导致整个集群效率下降。以上两个问题将作为以后研究的重点。

参考文献：

[1]刘清，孙辉，王洪发.粒计算研究现状及基于Rough逻辑语义的粒计算研究[J].计算机学报，2008（4）：543555.

[2]于磊，罗谦，张林林.基于粒计算的数据分片算法的问题发现[J].计算机技术与发展，2011（6）：3235.

[3]吴润秀，吴水秀，刘清.基于粒计算的数据分片算法[J].计算机应用，2007（6）：13881391.

[4]杨晶，刘天时，马刚.分布式数据库数据分片与分配[J].现代电子技术，2006（18）：119121，125.

[5]杨小虎，王新宇，毛明.基于数据划分的分布式模型及其负载均衡算法[J].浙江大学学报：工学版，2008（4）：602607，681.

[6]LIN TY.Granular fuzzy sets：a view from rough set and probability theories[J].International Journal of Fuzzy Systems，2001（2）：373381.

[7]TABIRCA T，TABIRCA S，FREEMAN L，et al.Astatic workload balance scheduling algorithm[C].Proceedings of ICPP，2002：235239.

（責任编辑：黄健）