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

1、基于相似度代价计算的内存数据库集群数据划分摘要：针对内存数据库集群的数据划分，提出了基于相似度计算的内存数据库数据划分算法。该算法首先根据数据相关性对数据作初步简单划分，然后再基于事务相似度计算，得到最正确事务相似性判断标准，对事务进展相关性合并，进而进一步划分数据，得到合理优化的数据划分结果。算法创新地提出根据Rough集原理计算事务相关性，去除了数据库读写系数的影响，对内存数据库集群的数据划分具有一定指导意义。关键词：内存数据库；相似度；代价计算；Rough集中图分类号：TP392文献标识码：A文章编号：1672780020210040182030引言在数据库集群系统中，数据划分和数据分布

2、是系统运行的根底，做好划分和数据分布可以有效进步系统运行效率。随着内存数据库以及内存数据库集群的出现，针对内存数据库集群的数据划分算法也逐步出现，但都是基于传统数据库集群的解决方案，即仅考虑数据相关性。同时对相似性判断标准都是基于经历性判断选择50%为标准。本文提出基于相似度代价计算的内存数据库集群数据划分策略，在数据相关性根底上提出事务相关性规约，并将相似性判断条件扩大到40%60%范围内，以更准确、精细地进展数据划分。1数据划分根本概念数据划分又称为数据分片或者数据分割，是数据库集群的特征之一，是将集群的数据全集划分为独立的数据片段。数据划分必须遵守3个原那么：完好性、不相交性和可恢复性。

3、 数据分片方法有3类：程度分片、竖直分片和混合分片。详细分片策略主要有Range分片算法、Round-Robin分片算法、Hybrid-Range分片算法、表达式分片算法、时间分片算法、哈希分片算法等。 目前数据划分算法主要是针对构造化的关系型数据处理，而且处理过程中将磁盘读取代价作为重要参考标准，处理结果比较固定。这样的数据划分策略对内存数据库集群已不再适用。2基于Rough集理论的相似度矩阵在Rough集的研究中1，事务被表示成统一的信息系统。假定数据库全集R= r1，r2，r3.，rn，ri1in是数据集中的一个元数据，事务集合T=t1，t2，t3，tm，tj1jm是事务集合中的一个事务

4、，trij表示数据ri被事务tj访问，由此可得到事务访问数据矩阵RT。根据Rough集理论，可以将事务访问数据矩阵对应到信息系统中。假设分配到内存数据库集群的数据集合R=r1，r2，r3.，r8，事务集合T=t1，t2，t3，t4，构造事务访问数据矩阵，事务访问了元数据记为1，未访问记为0，假设访问情况如表1所示。根据数据划分根本原理，即数据之间的相关性，初步对数据进展划分，可得到元数据r1、r4相关性比较强，可以作为一个划分，r2、r8作为一个划分，其余作为独立划分，得到划分结果如表2所示。再根据事务之间的相关性，将事务进展合并。之前的研究都是确定一个相似度标准，基于粒计算的数据分片算法23

5、中标准一般为同时访问一样元数据不小于50%。50%是一个经历值，被普遍认为是一个划分值，在实际部署中，尤其是在内存数据库集群部署中，50%作为一个相似度划分标准并不一定合理。由于内存数据库的读取效率成几何倍数进步，可以适当增加数据划分数量，即提升相似度划分标准。所以提出首先根据不同相似度标准所付出的代价作为划分根据对事务进展划分，然后对数据进展第二次划分，以得到更准确的数据划分结果。 假设通过代价计算，得到事务相似性划分标准为不小于60%，此时t2和t3事务可以合并，合并之后结果如表3所示。 再根据数据相关性，对数据进一步划分，此时r2、r5和r8可以归为同一个划分，得到划分结果如表4所示。

6、经过划分之后，得到划分结果为R=r1，r4，r2，r5，r8，r3，r6，r7。3代价计算划分算法上文提到的代价计算，在数据进展第二次划分时，假设一个集群中有n个数据划分，数据库总访问值记为D，单位为千次/s，第i个数据划分在时间t内的数据访问值为Di。Di来自两方面，数据库的读和写，分别记为Dri和Dwi。Dri和Dwi是两个单位时间内的累计值，设Dri的变化函数为rit，Dwi的变化函数记为wit。可以得到：上述代价计算是基于内存数据库的数据库读写代价，在之前的传统数据划分中，基于代价计算的D值都引入了读写系数Vrwc，即要考虑主存与磁盘之间的I/O代价5。但是因为内存数据库在运行过程中，

7、数据都加载到了内存，读和写操作损耗时间大大减少，因此数据库的读写损耗可以忽略。 数据进展初步划分之后，D值计算根据是在不同事务相似度标准下的不同值，之前会简单地将这一标准选择为超过50%。但是通过研究，这一标准并不一定是最正确标准，所以本文将计算标准限定在40%60%，分别计算不同标准下的D值。通过比较D值变化趋势，得到最正确断定标准，并根据该标准对事物进展合并，最后再将数据进展相关性划分，进而得到最正确的数据划分。详细步骤如下： 第一步：简单数据关联度划分，以数据同时被一样一组事务访问为根据，判断数据是否相关，假设相关那么删除矩阵中被一样事务访问的数据节点，算法描绘如下：HT5算法1 /输入

8、：事务访问数据矩阵 /输出：去除一样事务访问的节点行的事务访问数据矩阵 数组trin临时存放第i行事务访问数据记录 数组trjn临时存放第j行事务访问数据记录 1：fori=1；im；i+ 2：forj=i+1；jm；j+ 3：trii-1=trin/依次扫描得到第i行事务访问数据记录 4：trjj-1=trjn/依次扫描得到第j行事务访问数据记录 5： if trin=trjn then 6：delete trjn/合并关联度较强的独立元数据 7：end if 8：end for 9：end forHT由以上操作得到经过初步数据关联性划分的事务访问数据矩阵RT。 第二步：代价计算，事务相关性

9、划分基于第一步的数据访问矩阵RT，根据事务同时访问数据的相似程度，计算事务相关性，根据代价计算公式得到合理的相似值为C，常数A=0，B=0。算法描绘如下：HT5算法2 /输入：事务访问数据矩阵 /输出：去除一样事务访问的节点行的事务访问数据矩阵 数组trin临时存放第i行事务访问数据记录 数组trjn临时存放第j行事务访问数据记录 1：fork=1；kn；k+： 2：forl=k+1；ln；l+ 3：trkm=trmk/临时记录第k列数据被事务tr访问的m值 4：trjm=trlk/记录第l列数据被事务tr访问的m个值 5：trkatrla=1，A+；a取值为0，1，2m 6：trkatrla

10、=1，B+；a取值为0，1，2m 7：ifB/ACthen 8：trka=trkatrla； /对相似事务进展合并 9：delete trlm； 7：end if 8：end for 9：end forHT上一步算法完毕之后，根据第一步算法对矩阵再次进展数据相关性划分，算法完毕。 4实验结果分析实验在30台虚拟机上模拟内存数据库集群，模拟数据中有200个事务和1 000个独立元数据。经过第一步算法划分之后合并为800个数据源，在进展代价计算时，得到访问代价跟事务相似性关系如图1所示。 由图1结果可以得到，当事务相似度标准不小于0.52时，较为合理，在该标准下合并事务，事务合并为132个，再次对

11、数据进展关联性划分，得到640个数据划分。通过该算法可以合理划分数据，有效降低集群访问代价。5结语本文通过对传统数据库集群数据划分算法进展分析，基于Rough集的新应用6，提出了针对内存数据库集群的数据划分算法。该算法有两次数据划分过程，第一次是普通的根据数据相关性进展数据划分，第二次首先对访问数据的事务进展相关性划分。传统划分是直接以同时访问数据超过50%为标准，本文创新地提出针对内存数据库的访问代价计算方法，对事务进展规约，同时针对内存数据库的特点，忽略磁盘I/O代价。该算法可以合理地划分数据，有效降低集群访问代价。 不过本文所提出的代价计算40%60%也是一个经历值，没有计算和论证在此范

12、围外的情况。此外数据库访问代价值D是一个整体值，可能会出现单个节点的Di很高，而整体D值较低的情况，使单个节点可能超出了负载才能7，导致整个集群效率下降。以上两个问题将作为以后研究的重点。参考文献：1刘清，孙辉，王洪发.粒计算研究现状及基于Rough逻辑语义的粒计算研究J.计算机学报，20214：543555.2于磊，罗谦，张林林.基于粒计算的数据分片算法的问题发现J.计算机技术与开展，20216：3235.3吴润秀，吴水秀，刘清.基于粒计算的数据分片算法J.计算机应用，20076：13881391.4杨晶，刘天时，马刚.分布式数据库数据分片与分配J.现代电子技术，200618：119121，125.5杨小虎，王新宇，毛明.基于数据划分的分布式模型及其负载平衡算法J.浙江大学学报：工学版，20214：602607，681.6LIN TY.Granular fuzzy sets：a view from rough set and probability theoriesJ.International Journal