法律状态公告日
法律状态信息
法律状态
2022-03-22
专利权的转移 IPC(主分类):G06F12/02 专利号:ZL2017100224044 登记生效日:20220310 变更事项:专利权人 变更前权利人:湖州优研知识产权服务有限公司 变更后权利人:苏州意烁电子有限公司 变更事项:地址 变更前权利人:313000 浙江省湖州市南浔区南浔镇朝阳路666号南浔科技创业园一层1020室 变更后权利人:215000 江苏省苏州市苏州工业园区东环路1518号新苏大厦411室
专利申请权、专利权的转移
2020-03-20
授权
授权
2017-07-14
实质审查的生效 IPC(主分类):G06F12/02 申请日:20170112
实质审查的生效
2017-06-20
公开
公开
技术领域
本发明属于固态硬盘数据存储技术领域,尤其涉及一种融合多种机器学习算法的固态硬盘热数据识别方法。
背景技术
近年来,随着固态硬盘SSD(Solid State Disk,SSD)设计技术的不断进步,相比传统的机械硬盘,SSD显示出具有读写速度快、功耗低、体积小、防震抗摔、便于携带等方面的优势,它已经在许多领域开始替代传统机械硬盘。
闪存具有三大特性:1)按页(page)、块(block)、平面(plane)的结构进行组织;提供读、写和擦除3种操作;页是读/写的最小单位;块是擦除的最小单位。2)闪存擦除后只能写一次,即所谓的写前擦除,这造成闪存不能原地更新,否则会带来巨大的开销。3)闪存每个存储单元的编程/擦除(P/E)次数有限,超过擦除次数后该存储单元存储数据不再可靠。隐藏闪存上述特性,使得这些不方便的特性对用户而言透明,在SSD的设计中,一般要提供一个中间软件转换层实现对闪存的管理,称为闪存转换层FTL(Flash TranslationLayer)。
FTL一般由地址映射、垃圾回收和磨损均衡三个模块组成。地址映射负责将来自文件系统的逻辑地址转换为闪存中的物理地址;垃圾回收负责将回收块中的有效数据复制到新的物理块中,将回收块擦除后重新利用;磨损均衡负责保证每个块的磨损速率尽量一致,防止部分块因磨损过快而提前损坏。
为实现高效的垃圾回收,避免在垃圾回收过程中复制过多的有效数据,FTL需要有效地把频繁更新的数据(即热数据)和非频繁更新的数据(即冷数据)分开,即热数据识别。在闪存的数据管理中,一方面,热数据识别技术可以将识别出来的热数据聚集到同一个块中来提高垃圾回收效率,减少垃圾回收的开销;另一方面,热数据识别技术可以将热数据分配到擦除次数较少的块中,防止某些块因为频繁擦除而磨损过快,改善闪存的磨损均衡。因此,热数据识别对提高SSD的性能非常关键。
然而,目前现存的SSD热数据识别方法存在下面两个方面的问题:
(1)内存开销大。目前大部分的热数据识别机制均是采用识别NAND闪存中热数据页的思想,这些机制的核心原理就是给每个页增添一个页访问计数器,在一定时间段内记录与NAND闪存页相对应的逻辑页地址的读写操作次数。如果读写操作次数大于设定的阈值,则该页被判定为热页,否则,则判定为冷页。为每个页设置了一个计数器,这样方式需要消耗大量的内存空间,对内存空间有限的固态硬盘来说,这种方式显然是不太适用的。
(2)准确度低。常用的固态硬盘的冷热数据识别机制包括基于请求大小、访问模式、最近最少使用、布农滤波等方法。这些方法考虑因素比较单一,没能综合考虑负载的局部性特征,热数据识别的准确度不高。此外,布农滤波方法还存在假阳性问题,即将不属于不在集合内的数据错误判定为在集合内。
发明内容
本发明公开了一种融合多种机器学习算法的固态硬盘热数据识别方法,以克服现有方法的上述缺陷。该方法能在较小的内存开销前提下,提高冷热数据识别率。
本发明解决其技术问题所采用的技术方案包括以下步骤:
步骤1、使用K-means聚类(K=2,即2均值聚类)根据当前负载大小进行分类;利用K-means聚类算法根据当前请求的负载大小对数据进行分类,分为C1(小请求类)和C2(大请求类)两类,若当前请求大小属于C1,则判定当前请求为热数据;反之为冷数据。
步骤2、使用K近邻分类算法根据当前请求的逻辑地址进行分类。
由K-means聚类方法得到两个已知类别属性的两类样本C1和C2,然后根据K近邻分类算法,从C1和C2中取K个与当前待分类的请求的逻辑页号(LPN)最接近的请求,然后根据K个请求的LPN中大多数LPN所属的类别来判定当前LPN所属的类别。如果K个LPN中大多数属于C1,则当前LPN属于C1(热数据);否则,属于C2(冷数据)。
步骤3、对比步骤1和步骤2的两种分类方式对当前请求的冷热性的分类结果。
如果K-means聚类和K近邻分类两种方式对当前请求的类别的分类结果一致,则识别过程结束;如果不一致,则执行步骤4。
步骤4、采用最近邻原则对分类结果进行修正。
从K个最近邻的LPN中找到与当前LPN的距离dist最小的LPN,以该LPN所属的类别来作为当前请求的类别。
本发明的有益效果在于:
本发明提出的融合多种机器学习算法的热数据识别方法,仅需保存有限的数据信息,内存开销低,非常有利于实际的运用。同时,与现有热数据识别方法比较,还能提高热数据识别准确率,而且能够适应不同的负载。
附图说明
图1:融合多种机器学习算法的热数据识别方法示意图。
图2:根据请求大小采用2均值聚类算法进行冷热数据识别示意图。
图3:根据请求的逻辑地址采用K近邻分类算法进行冷热数据识别示意图。
具体实施方式
下面结合附图通过具体实例对本发明作进一步的详细说明。以请求序列的冷热识别为例,示例详细描述了本发明方法识别热数据的流程。示例中,为了方便阐述作如下设置:
固态硬盘转换层(FTL)接收到的请求R格式为(type,LPN,size),设K近邻分类方法中K的值取5,且已经访问过的10个请求已经被分为热数据C1和冷数据C2两类:C1:{(w,12,1),(w,35,4),(w,41,2),(w,41,5),(r,12,4)},基于请求大小的聚类中心为3.2;C2:{(w,20,7),(r,38,9),(w,14,12),(r,53,8),(r,30,10)},聚类中心为9.2。即将访问的请求顺序为:r1(w,42,7),r2(w,24,3),r3(w,41,7),r4(r,29,11)。
实施例1:
当请求r1(r,42,7)到来时,操作过程如图1所示:
步骤1.使用K-means聚类(K=2,即2均值聚类)根据当前负载大小进行分类。K-means根据负载大小进行冷热数据识别,示意图如图2所示,r1的请求大小为7,离C2的聚类中心近,由K-means聚类算法判别为C2类。K-means算法的具体流程如下:
步骤1.1:初始化2个聚类中心(m1,m2);
步骤1.2:对每个请求ri,根据请求大小找到离它最近的聚类中心,将其分配到该类中;
步骤1.3:重新计算C1和C2的聚类中心,
步骤1.4:计算聚类误差平方和准则函数,
步骤1.5:直到f值收敛,则输出C1、C2和m1、m2,算法结束;否则,重复步骤1.2和步骤1.3,直到f收敛。
步骤2.使用K近邻分类对当前负载逻辑地址进行分类,如图3所示。根据r1的LPN采用K近邻分类算法从C1和C2中找到的5个最近邻LPN为:41、41、38、35、53,因为5个最近邻有3个为C1类,判定R1为C1类。K近邻分类算法的具体流程如下:
步骤2.1:初始化K值;
步骤2.2:计算当前LPN与C1、C2中每个样本的LPN之间的距离dist。样本间的“近邻”使用欧式距离测量,设两个样本的逻辑地址LPN分别为x和x’,则x与x’之间的欧式距离定义为:dist(x,x')=|x-x'|;
步骤2.3:重复步骤2.2直到计算完当前LPN与所有样本间的距离dist;
步骤2.4:对所有的dist进行升序排列,选出前K个最近邻的样本;
步骤2.5:统计K个最近邻样本中每个类别出现的次数;
步骤2.6:选择出现频率最大的类别作为当前请求的类别。
步骤3.对比两种分类方式对当前请求的冷热性的判定结果。有上述判定结果可以发现,两种方式的判定结果产生了矛盾,因此,我们需要对判定结果进行修正,执行步骤4。
步骤4.采用最近邻原则对分类结果进行修正。根据最近邻原则,选取最近邻LPN=41做参考,因为LPN=41属于C1类,因此,最终判定R1为C1类,并更新C1类的LPN为{12,35,41,41,12,42},聚类中心更新为3.83。
实施例2:
当请求R2(w,24,3)到来时,根据图1中步骤1,R2的请求大小为3,离C1的聚类中心近,由K-means聚类算法判别为C1类;根据图1中步骤2,对请求R2的LPN采用K近邻分类算法从C1和C2中找到的5个最近邻LPN为:20、30、14、35、12,因为5个最近邻中有3个是属于C2类,判定R2为C2类。由图1的步骤3可知,此时判定结果也产生了矛盾。因此,执行步骤4,选取最近邻LPN=20做参考,因为LPN=20属于C2类,因此,最终判定R2为C2类,并更新C2类实体,为了简便,后面我们仅表示类中的LPN的值,更新为{20,38,14,53,30},聚类中心为8.16。
实施例3:
当请求R3(w,41,7)到来时,根据图1中步骤1,R3的请求大小为7,离C2的聚类中心近,由K-means判定为C2类根据图1中步骤2,对请求R3的LPN采用K近邻分类算法从C1和C2中找到的5个最近邻LPN为:41、41、42、38、35,因为5个最近邻中有4个是属于C1类,判定R3为C1类;根据图1中步骤3,此时判定结果也产生了矛盾。因此,执行步骤4,我们选取最近邻LPN=41做参考,因为LPN=41属于C1类,因此,最终判定R3为C1类,更新C1类的LPN为{12,35,41,41,41,12,42,24},聚类中心为4.12。
实施例4:
当请求R4(r,29,11)到来时,根据图1中步骤1,R4的请求大小为11,离C2的聚类中心近,由K-means聚类算法判别为C2类;根据图1中步骤2,对请求R4的LPN采用K近邻分类算法从C1和C2中找到的5个最近邻LPN为:30、24、35、20、38,因为5个最近邻中有3个是属于C2类,判定R4为C2类。根据图1中步骤3,两种方法判定结果一致,R4确实属于C2类,更新C2类的LPN为{20,38,14,53,30,29},聚类中心为8.57。
机译: 一种或多种使用多种识别方法的库存(二手的或新的)库存跟踪系统(可选但不限于RFID)和数据库管理系统
机译: 用于检测一种或多种基因差异表达,测量受试物质对一种或多种基因表达的影响的组合,组合物,装置和方法,以及用于筛选预后,操纵预后的方法基因组(genom)对人类或动物而言,而不是动物基因组的表达。调节一种或多种差异表达基因的表达,选择一种或多种动物,并产生抗体,物质,转基因动物,计算机系统,分离和纯化的抗体,试剂盒,用于传达信息的介质。数据和polinucleot u00ecdeo预后者的数据的使用
机译: 预防或治疗肿瘤特异性人乳头瘤病毒的药物,其至少含有一种或多种乳头瘤病毒的蛋白L1和至少一种蛋白质与一种或多种乳头瘤病毒的融合蛋白,其制备方法