[0079] 以下将结合附图对本发明提供的技术方案作进一步说明，本方法的流程图如附图1所示。
[0080] 一种基于访问局部性的闪存页级地址映射方法，包含地址映射流程和聚类流程。
[0081] 其中，地址映射流程包含以下步骤S1到S6：
[0082] 步骤S1:初始化闪存区和缓冲区，将闪存区划分为数据块DB和映射块MB，将缓冲区分为缓存映射表CMT和全局转换表GTT，具体是：
[0083] 步骤S11:将闪存区进行初始化，将闪存区划分为若干数据块DB和若干映射块MB，其中每个数据块用于存储数据信息，每个映射块用于存储地址映射信息，以便于寻找对应数据块；所有映射块的集合构成全局映射表GMT，闪存区中数据块占用了大部分的块资源，即闪存区中映射块所在资源比例大于数据块；映射块MB由若干映射页组成，映射页由若干映射项组成；
[0084] 步骤S12:将缓冲区进行初始化，将缓冲区划分为CMT表和GTT表，其中GTT表用于存储各映射块在闪存中的位置信息；CMT表包括顺序缓存映射表SCMT，工作缓存映射表WCMT和交换缓存映射表ECMT，三个表均用于记录当前活跃的缓存映射项；
[0085] 上述SCMT用于记录连续的地址映射项，即从连续的逻辑地址映射到相应的连续物理地址的映射项，该连续映射项由逻辑地址LPN、物理地址PPN和映射长度Range三者组成；WCMT和ECMT均用于记录单一逻辑地址到单一物理地址的映射项，该映射项由逻辑地址LPN、物理地址PPN两者组成，其中WCMT用于存储ECMT命中导致的转移映射项，ECMT用于存储初次缓存的地址映射项和WCMT中淘汰的映射项。
[0086] 步骤S2:在闪存区和缓冲区初始化完成后，对每一个到达的地址映射请求Req，根据请求信息中逻辑地址，判断缓冲区是否发生命中，并判断命中类型为未命中，全部命中或部分命中；
[0087] 所述地址映射请求Req的请求信息包含ReqLPN、ReqRange和ReqMode，其中ReqLPN表示请求的逻辑地址，ReqRange表示请求的范围大小，ReqMode表示请求的读写模式。
[0088] 步骤S3:根据命中情况的不同，分别进行不同的缓冲区维护和地址映射查询，具体是：
[0089] 步骤S31:若地址映射请求在缓冲区中全部命中，则将SCMT、WCMT中的命中项转移到当前所在映射表的最近被访问位置(简称MRU位置)，将ECMT中的命中项转移到WCMT的MRU位置；若在映射项加入WCMT前，WCMT已满则根据最近最久未访问策略(简称LRU策略)驱逐LRU位置的映射项到ECMT中；
[0090] 步骤S32:若地址映射请求在缓冲区中部分命中，则将命中部分如同步骤S31中的策略进行缓冲区维护(即如同S31中，将SCMT、WCMT中的命中项转移到当前所在映射表的MRU位置，将ECMT中的命中项转移到WCMT的MRU位置；若在映射项加入WCMT前，WCMT已满则根据LRU策略驱逐LRU位置的映射项到ECMT中)，未命中部分则根据GTT找到缓冲区中的映射块，在映射块中根据请求的ReqLPN找到需要查找的映射项，然后判断该映射项周围是否出现连续地址映射项(连续地址映射项是指逻辑页地址和物理页地址都保持连续的相邻映射项的集合)，若是则将整个连续映射项预取加入SCMT的MRU位置，若否则加入ECMT的MRU位置；若在映射项加入ECMT或SCMT前，ECMT或SCMT已满，则进行LRU策略驱逐LRU位置的映射项到闪存；
[0091] 步骤S33:若地址映射请求在缓冲区中未命中，则采用S32中未命中部分进行缓冲区维护(即如同S32根据GTT找到缓冲区中的映射块，在映射块中根据请求的ReqLPN找到需要查找的映射项，然后判断该映射项周围是否出现连续映射项，若是则将整个连续映射项预取加入SCMT的MRU位置，若否则加入ECMT的MRU位置；若在映射项加入ECMT或SCMT前，ECMT或SCMT已满，则进行LRU策略驱逐LRU位置的映射项到闪存)。
[0092] 本发明区别于其他技术方案采用了顺序地址映射压缩技术，将连续地址映射项压缩为单一的SCMT中的连续映射项，减少了缓冲区空间的损耗，此外连续映射项预取技术使得缓冲区的利用率和映射项的命中率都得到提升；
[0093] 步骤S34:查询地址映射请求Req对应的地址映射项，找到请求项逻辑地址ReqLPN对应的物理地址ReqPPN；
[0094] 步骤S4:对映射请求Req，判断映射请求信息中的ReqMode类型是否为写模式，若是则进入步骤S5，若否则进入步骤S6；
[0095] 步骤S5:对写请求执行异地更新，并将原映射项置为无效，具体是：
[0096] 步骤S51:获取当前的最新聚类中心，根据当前请求逻辑地址的访问频次，计算当前请求逻辑地址访问频次与冷聚中心μc、温聚中心μw和热聚中心μh的距离distance，计算如下：
[0097]
[0098] 其中d为逻辑地址访问频次f和聚类中心μ的维度，fi和μi分别表示访问频次f和聚类中心μ第i维的大小，由于访问频次维度均为一维，因此d为常数1。
[0099] 步骤S52:页面温度评估：
[0100] 根据公式(1)，聚类归属为距离distance最小值所对应的聚集中心，若该聚类归属为冷聚中心则页面评估为冷页，若该聚类归属为温聚中心则页面评估为温页，若该聚类归属为热聚中心则页面评估为热页；根据聚类归属分配相应的写入块，同时将原映射项置为无效。其中写入块为冷写入块CB、温写入块WB或热写入块HB。
[0101] 页面温度评估中的页面是指请求的逻辑地址ReqLPN所指向的页面；
[0102] 区别于现有技术方案，本发明基于页面的访问局部性特征评估页面，将页面的异地更新分配到物理地址不同的块中，使得相同的块中页面具有相似的局部性特征，从而降低页面的垃圾回收开销和访问延迟；
[0103] 步骤S6:返回请求逻辑地址对应的物理地址ReqPPN。
[0104] 聚类流程包含步骤S1，如下所示：
[0105] 步骤S1:采用改进后K‑means聚类方法对映射项进行聚类，得到冷聚中心μc、温聚中心μw和热聚中心μh，具体是：
[0106] 步骤S11:判断当前请求序号与上一次执行聚类时的请求序号间隔是否到达到序号阈值λ，若是则进入步骤S12，否则进入步骤S17。
[0107] 区别于现有聚类方案，本发明采用改进的基于请求间隔周期的聚类来减少聚类的频次，此外聚类算法独立于地址映射请求逻辑，不会对地址映射请求产生阻塞，从而降低聚类对闪存存储系统的性能消耗并降低地址请求的延迟；
[0108] 步骤S12:根据公式(2)计算映射表中的映射项的访问频次fLPN，计算公式如下所示：
[0109]
[0110] 其中n为逻辑地址LPN对应映射项的访问次数，ln(Range)为SCMT中连续映射项的映射范围的对数；
[0111] 进而得到缓冲区中所有映射项的访问频次集合S，如下所示：
[0112] S＝{fmin,…,fLPN…,fmax|min≤LPN≤max，LPN∈CMT} (3)
[0113] 步骤S13:对集合S进行采样，采样结果形成集合Sample；若此次为初次聚类则使用Sample集合中的随机三项作为聚类的初始聚类中心，否则采用上一轮聚类的结果(即冷聚中心μc、温聚中心μw和热聚中心μh)作为初始聚类中心。
[0114] 本发明的初始化优化策略不同于常规聚类，仅在初次聚类中采用随机样本初始化，后续聚类均采用上一轮的聚类结果作为新聚类的初始聚类中心，在访问负载变动不大的情况下可以更快地收敛，此外本方法区别于现有的技术方案在原始映射项访问频次数据基础上进一步进行采样，进一步降低了聚类的性能消耗；
[0115] 步骤S14:计算集合Sample中的所有逻辑地址的访问频次与所有聚类中心的欧氏距离，距离计算如下所示：
[0116]
[0117] 其中d为逻辑地址访问频次f和聚类中心μ的维度，fi和μi表示访问频次f和聚类中心μ第i维的大小，由于访问频次维度均为一维，因此d为常数1。根据计算的距离，将逻辑地址的访问频次分配到距离最近的聚类；
[0118] 步骤S15:对于每一个聚类，根据公式(5)计算新的均值点 作为下一次迭代的聚类中心，然后返回到步骤S14，即步骤S14和S15交替进行，直到前后两次迭代中聚类中心不变，则停止迭代。
[0119]
[0120] 其中 表示当前迭代t中第i个聚类集，k是聚类集的总数。
[0121] 迭代完毕后的均值集合M如下所示：
[0122]
[0123] 其中ω表示聚类迭代停止时的总迭代次数；
[0124] 步骤S16:计算最终的冷聚中心μc、温聚中心μw和热聚中心μh作为最新的聚类结果，计算如下：
[0125]
[0126] 本方法对应的系统模块及其子模块如附图2和附图3所示。
[0127] 一种基于访问局部性的闪存页级地址映射系统，包括缓冲区100，闪存区300，聚类执行模块400，聚类中心模块500以及页面分配模块200；其中缓冲区100包括顺序缓存映射表SCMT101，工作缓存映射表WCMT102，交换缓存映射表ECMT103以及全局转换表GTT104，并对地址映射项进行缓存，以提供快速访问而不必访问闪存区中的映射块302；闪存区包括数据块DB301和映射块MB302，数据块DB301存储数据信息，映射块MB302存储映射项信息，同时对缓冲区未命中的地址映射项提供访问；聚类执行模块400执行聚类操作，通过对映射项聚类得到聚类中心；聚类中心模块500存储并更新当前的聚类中心信息；页面分配模块200根据聚类中心模块500中的信息，对异地更新页面进行页面判别和分配操作。
[0128] 所述SCMT101记录连续的地址映射项，即从连续的逻辑地址映射到相应的连续物理地址的映射项；WCMT102记录单一的地址映射项，映射项来自ECMT103命中导致的转移映射项；ECMT103记录单一的地址映射项，其中存储了初次缓存的地址映射项和WCMT102中淘汰的地址映射项；GTT104记录映射块在闪存中的位置信息。
[0129] 缓冲区100所述缓存是根据地址映射请求在缓冲区中命中情况的不同，分别进行不同的缓冲区维护：若全部命中，则将SCMT101、WCMT102中的命中项转移到所在映射表MRU位置，将ECMT103中的命中项转移到WCMT102的MRU位置；若部分命中，则将命中部分如同全部命中策略进行缓冲区维护，未命中部分则根据GTT104找到对应映射块，在映射块中根据请求的ReqLPN找到需要查找的映射项，然后判断该映射项周围是否出现连续地址映射项，若是则将整个连续映射项预取加入SCMT101的MRU位置，若否则加入ECMT103的MRU位置；若全部未命中，则采用部分命中中未命中策略进行缓冲区维护。
[0130] 若在映射项加入WCMT102前，WCMT102已满则根据LRU策略驱逐LRU位置的映射项到ECMT中；
[0131] 若在映射项加入ECMT103或SCMT101前，ECMT103或SCMT101已满，则进行LRU策略驱逐LRU位置的映射项到闪存区。
[0132] 所述聚类执行模块400包括循环检查模块401、初始化模块402、迭代计算模块403以及更新模块404；
[0133] 循环检查模块401检查当前聚类条件是否已经满足，即当前请求序号与上一次执行聚类时的请求序号间隔是否达到序号阈值λ；
[0134] 初始化模块402对初始聚类中心进行初始化工作，包含初次随机初始化和后续采用上一轮聚类结果初始化；
[0135] 迭代计算模块403进行聚类中的迭代计算部分，即根据公式(2)计算映射表中的映射项的访问频次fLPN，进而得到缓冲区中所有映射项的访问频次集合S；对集合S进行采样，采样结果形成集合Sample；根据公式(4)计算集合Sample中所有逻辑地址的访问频次与所有聚类中心的欧氏距离，将逻辑地址的访问频次分配到距离最近的聚类；对于每一个聚类，根据公式(6)计算新的均值点 作为下一次迭代的聚类中心，直到前后两次迭代中聚类中心不变为止；根据公式(7)获得最终的冷聚中心μc、温聚中心μw和热聚中心μh作为最新的聚类结果。
[0136] 更新模块404对聚类中心模块中的三种聚类中心进行更新操作。
[0137] 所述聚类中心模块500包括冷聚类中心501，温聚类中心502和热聚类中心503；冷聚类中心501是聚类中心中映射项访问频次最小的聚类中心；温聚类中心502是聚类中心中映射项访问频次中等的聚类中心；热聚类中心503是聚类中心中映射项访问频次最大的聚类中心。
[0138] 所述页面分配模块200包括页面判别模块201和写入块分配模块202；页面判别模块根据当前页面与聚类中心模块中各个中心距离情况，判别页面的冷温热属性；写入块分配模块根据页面判别结果分别为不同的页面分配冷写入块CB，温写入块WB以及热写入块HB。
[0139] 采用真实负载仿真平台对本发明的方法和系统进行评估，实验主机配置为英特尔i7 8700K处理器，32GB 3200mhz内存，Ubuntu 10.04LTS操作系统，实验平台选取为基于DiskSim基础上的FlashSim闪存仿真平台，实验数据方面采用了多个真实场景数据集，包括来自金融机构OLAP的数据集Financial1和Financial2，以及来自知名搜索引擎的WebSearch1和WebSearch2数据集。
[0140] 在实验中，采用了DFTL作为对比算法，实验结果表明，相比于DFTL，本发明的方法和系统减少了垃圾回收开销，提升了缓冲区映射表的命中率，减少了块擦除次数。其中，附图4为本方法与对比方法的归一化实验对比图。
[0141] 与现有技术相比，本发明采用了顺序地址映射压缩和预取技术，在维持较低的缓冲区空间开销的情况下，提高了缓冲区命中率，改善了现有页级地址映射方法空间占用高，地址映射命中率低的缺点；此外，本发明开创性地通过页面温度探测和回写聚集机制，动态地将页面划分到访问局部性相似的块中，降低了垃圾回收开销，并减少了垃圾回收对页面访问延迟的影响，提高了页面访问的稳定性；在聚类时采用了访问间隔机制和采样机制，在初始化阶段采用上一轮的聚类结果作为本轮聚类的初始聚类中心，在访问负载变动不大的情况下可以更快地收敛，减少了聚类所需的计算量。
[0142] 以上实施例的说明只是用于帮助理解本发明的方法及其核心思想。对于本技术领域的普通技术人员来说，在不脱离本发明原理的前提下，对本发明进行若干改进和修饰，这些改进和修饰也落入本发明权利要求的保护范围内。
[0143] 对所公开的实施例的上述说明，使本领域专业技术人员能够实现或使用本发明。对这些实施例的多种修改对本领域的专业技术人员来说将是显而易见的，本文中所定义的一般原理可以在不脱离本发明的精神或范围的情况下，在其它实施例中实现。因此，本发明将不会被限制于本文所示的这些实施例，而是要符合与本文所公开的原理和新颖特点相一致的最宽的范围。
.jpg.150x150.jpg)
.jpg.150x150.jpg)
.jpg.150x150.jpg)
.jpg.150x150.jpg)
.jpg.150x150.jpg)
