面向混合存储系统的低内存开销热点数据识别方法

面向混合存储系统的低内存开销热点数据识别方法
【技术领域】
[0001] 本发明设及大规模混合存储技术领域，尤其设及一种面向混合存储系统的低内存 开销热点数据识别方法。
【背景技术】
[0002] 当前的大规模存储系统对性能和成本都提出了较高的要求，混合存储架构则是一 种能够同时满足该些需求的解决方案。混合存储系统中通过容量较小、性能较高的高端设 备保证性能，同时利用性能较低、价格便宜的低端设备降低成本，因而在该样的异构存储系 统中，高端设备一般用来保存频繁访问的热点数据、低端设备则用来保存不常访问的冷数 据，但要实现该一优化措施在很大程度上则需要依赖于热点数据的准确识别。
[0003] 热点数据一般是通过对数据访问的历史作统计分析识别出来，基于该一原理目前 从业者设计实行了大量的热点数据识别方法。原则上，大部分缓存替换策略都属于热点数 据识别方法，其中WLFU(Least化equentlyUsed)策略最具代表性。在LFU策略中，为每 一份数据维护一个计数器，当一份数据被访问时，其对应的计数器递增1 ;计数器数值较大 的数据即为热点数据。但该种方法需要为每一份数据维护一个整数类型的计数器，内存开 销较大。
[0004] BloomFilter(布隆过滤器）是一种低内存开销的数据结构，它可用来记录访问 历史，所W可用于热点数据识别。BloomFilter维护一个位数组和k个哈希函数，其中，位 数组中的所有位初始化为0。当一个页面被访问时，k个哈希函数根据该页面的页面号X计 算出k个数值hi (X)，h2(X)，…，hk (X)，该k个数值分别对应位数组中k个位，只要将该k个 位都置为1，就可将页面X记录到了BloomFilter中。BloomFilter能够W很低的空间开 销记录很多的访问页面，但它并不能直接用于热点数据识别中，具有包括W下两点原因；
[0005]l)BloomFilter不能记录对数据的重复访问；不管页面X被访问了多少次，Bloom FiIter仅仅将X对应的k个位hi(X)，h2(X)，…，hk(X)置为1，而没有采取任何措施记录X被 访问的次数。由于没有访问次数信息，BloomFilter无法从访问历史中识别出热点数据。
[0006] 2)BloomFilter只能不断地记录新的页面，而不能删除已经记录在BloomFilter 中的任何页面，导致记录的访问历史越来越长；而实际上，早期的访问历史对热点数据识别 已经没有利用价值，记录过长的访问历史反而会增加内存开销。
[0007] 为了克服W上BloomFilter存在的两大缺陷，有研究人员提出利用多个Bloom Filter来记录访问历史的方法，该方法被称为多BloomFilter方法（MultipleBloom Filters方法），简称MBFs方法。当一个页面X被访问时，从其维护的多个BloomFilter中 选择一个还没有记录X的BloomFilter,并将X记录在该选定的BloomFilter中。该样， 一个被多次访问的页面将会被记录到多个BloomFilter中，从而被识别为热点数据。另外， MBFs方法周期性的选择一个BloomFilter,将其位数组中的所有位清零，从而删除了记录 在该BloomFilter中的所有页面，借此方法删除早期的访问历史。
[000引 MBFs方法虽然能够借助多个BloomFilter记录页面的访问次数，并通过周期性 的清除一个BloomFilter删除早期的访问历史，从而能够高效地从访问历史中识别出热点 数据；但是，MBFs方法也存在两方面的缺陷；一方面，由于采用多个BloomFilter数据结 构，MBFs方法的内存开销仍然较高；另一方面，MBFs能够记录的页面访问次数的范围有限； 假定MBFs方法维护n个BloomFilter,对于特定页面，该方法能为其记录的最大访问次数 为n;如果该页面的访问次数超过n，则超出部分的访问信息不能记录在BloomFilter中， 使得丢失了会一部分热点信息。MBFs方法在上述两方面的缺陷由于不可同时弥补，即增加 访问次数的计数范围（n)必然会导致内存开销的增加，因此MBFs方法也很难应用到大规模 混合存储系统中。

【发明内容】

[0009] 本发明要解决的技术问题是克服现有技术的不足，提供一种实现方法简单、内存 开销低、能够实现大数据量的热点数据识别、且识别准确度高的面向混合存储系统的低内 存开销热点数据识别方法。
[0010] 为解决上述技术问题，本发明提出的技术方案为：
[0011] 一种面向混合存储系统的低内存开销热点数据识别方法，具体实施步骤为：
[0012]1)定义超大计数容量的布隆过滤器UBFOJltra-countingBloomFilter)，所述超 大计数容量的布隆过滤器UBF通过位数组W及映射各页面至所述位数组的k个哈希函数记 录页面的各次访问；初始化所述位数组为0并设定各个哈希函数；
[0013] 2)当页面X被访问时，通过所述位数组查询页面X的热度，所述页面X的热度为页 面X在位数组的对应k个位中值为1的位数；
[0014] 3)判断页面X的热度是否小于预设的首次记录阔值t，首次记录阔值t小于哈希 函数的个数k，若为是，判定页面X尚未记录在UBF，针对页面X在位数组的k个对应位，通 过将其中t个位由0翻转为1记录页面X;否则判定页面X已记录在UBF中，针对页面X在 位数组的k个对应位，通过将其中一个值为0的位按第一预设概率翻转为1进行页面X的 重复访问计数；
[001引 4)比较页面X的热度与指定的热度阔值的大小，若页面X的热度大于热度阔值，页 面X对应的数据识别为热点数据；跳转执行步骤2)。
[0016] 优选地，所述步骤3)中第一预设概率为1/2^，其中h为页面X的热度，t为首次 记录阔值。
[0017] 优选地，所述步骤3)中将一个值为0的位翻转为1前还包括针对一些1位进行随 机清零的步骤，具体步骤为；统计待翻转为1的位所在字节中值为1的位的数目m，根据统 计得到的数目mW第二预设概率将待翻转为1的位所在字节的各个位清零。
[001引优选地，所述第二预设概率为l/8-m，其中m为待翻转为1的位所在字节中值为1 的位的数目。
[0019] 优选地，所述步骤2)的具体步骤为：
[0020] 2. 1)当页面X接收到被访问请求时，初始化计数器i和热度h为0,跳转执行步骤 2.2)；
[0021]2. 2)计算页面X对应的第i个哈希函数的值hi (X)，检测页面X在所述位数组中 对应第hi(X)位的值，若检测到对应第hi(X)位的值为1，则跳转执行步骤2. 3);若检测到对 应第hi(X)位的值为0,则跳转执行步骤2. 4);
[0022] 2. 3)将热度h加1，跳转执行步骤2. 4);
[0023] 2. 4)将计数器i加1，跳转执行步骤2. 2)，直至计数器i的值等于哈希函数的个数 k，将热度h作为页面X的热度输出，跳转执行步骤3)。
[0024] 优选地，所述步骤1)中初始化所述位数组的具体步骤为：
[0025] 1. 1)设定哈希函数的个数kW及需要记录的访问历史长度n;
[0026] 1. 2)根据设定的哈希函数的个数k、访问历史长度n计算所述位数组所需的存储 空间大小，在内存中为所述位数组申请一片对应大小的存储空间；
[0027] 1. 3)将所述位数组对应的存储空间初始化为0。
[002引优选地，所述位数组所需的存储空间与kXn成正比，其中k为哈希函数的个数，n为需要记录的访问历史长度。
[0029] 优选地，所述步骤4)还包括根据页面X的热度按式（1)调整指定的热度阔值大小 W用于下一次热点数据识别的步骤巧）；
[0030]
(1)
[003U其中，h表示页面X的热度，NewT虹eshold表示调整后的热度阔值，T虹eshold表 示调整前的热度阔值，063^6地0巧3肖63表示预先设定的需要识别出的热点页面的数目。
[0032] 优选地，所述步骤5)还包括当页面X识别为热点数据时，按式（2)上调所述调整 后的热度阔值，得到最终调整后的热度阔值用于下一次热点数据识别的步骤；
[0033]
(2)
[0034] 其中，h表示页面X的热度，Newl'虹eshold表示调整后的热度阔值，Newl'虹eshold' 表示最终调整后的热度阔值，〇63山6地0巧3肖63表示预先设定的需要识别出的热点页面的 数目。
[0035] 与现有技术相比，本发明的优点在于：
[0036] 1)本发明通过定义超大计数容量的布隆过滤器UBF数据结构记录页面的各次访 问，只需通过小于哈希函数个数的t位信息即可记录一个页面，能够降低内存开销，同时通 过将页面对应位中的0位W-定概率翻转为1来进行页面的重复访存计数，仅需维护一个 超大计数容量的布隆过滤器UBF即可实现页面的多次访问 记录，从而能够在实现低内存开 销的同时实现大数据量的热点数据识别，有效提高了热点数据识别准确度及效率。
[0037] 2)本发明进一步在将0位翻转为1前W-定的概率将待翻转为1的位的所有字节 清零，使不频繁访问数据的热度逐步下降，最终在访问历史中消失，从而有效清除掉长时间 未被访问的历史数据。
[003引 3)本发明进一步根据页面的热度动态调整热度阔值，每当一个页面被访问时，根 据访问页面的热度h调整热度阔值化reshold，使热度阔值化reshold的值依据负载调整为 负载中所出现的页面的热度平均值，其中当热度h大于热度阔值化reshold时，上调热度阔 值化reshold的值；当热度h小于热度阔值化reshold时，下调热度阔值化reshold的值， 从而使得热点数据的识别能够自适应于负载的变化，提高热点数据识别的灵活性。
[0039] 4)本发明进一步根据页面的热度动态调整热度阔值，每当一个页面被识别为热点 数据时，上调热度阔值化reshold的值，通过不断上调的热度阔值化reshold使得识别出的 热点数据是整个负载中最热的数据。
【附图说明】
[0040] 图1是本实施例面向混合存储系统的低内存开销热点数据识别方法的实现流程 示意图。
【具体实施方式】
[0041] W下结合说明书附图和具体优选的实施例对本发明作进一步描述，但并不因此而 限制本发明的保护范围。
[0042] 如图1所示，本实施例面向混合存储系统的低内存开销热点数据识别方法，具体 实施步骤为：
[0043] 1)定义UBF及初始化；定义超大计数容量的布隆过滤器UBF，超大计数容量的布隆 过滤器UBF通过位数组W及映射各页面至位数组的k个哈希函数记录页面的访问次数；初 始化位数组为0并设定各个哈希函数；
[0044] 2)查询页面热度；当页面X接收到被访问请求时，通过位数组查询页面X的热度， 页面X的热度为页面X在位数组的对应k个位中值为1的位数；
[0045] 3)将页面加入UBF;判断页面X的热度是否小于预设的首次记录阔值t，首次记录 阔值t小于哈希函数的个数k，若为是，判定页面X尚未记录在UBF中，针对页面X在位数组 的k个对应位，通过将其中t个位由0翻转为1记录页面X;否则判定页面X已记录在UBF 中，针对页面X在位数组的k个对应位，通过将其中一个值为0的位按第一预设概率翻转为 1进行页面X的重复访问计数；
[0046] 4)热点数据识别：比较页面X的热度与指定的热度阔值的大小，若页面X的热度 大于热度阔值，页面X对应的数据识别为热点数据，否则页面X对应的数据识别为冷数据； 跳转执行步骤2)。
[0047] 本实施例中，设计实现一种能够W很低的内存开销记录访问历史的数据结构，该 数据结构通过位数组中k个位记录对应页面的访问次数，具有超大的计数容量，因而称为 超大计数容量的布隆过滤器UBF(Ultra-countingBloomFilter)。通过维护一个超大计数 容量的布隆过滤器UBF就可实现超大范围的页面访问历史记录，从而动态的识别出频繁访 问的热点数据，为混合存储系统中的数据布局提供指导。
[0048] 本实施例中，步骤1)中初始化位数组的具体步骤为：
[0049] 1. 1)设定哈希函数的个数kW及需要记录的访问历史长度n;
[0化0] 1. 2)根据设定的哈希函数的个数k、访问历史长度n计算位数组所需的存储空间 大小，在内存中为位数组申请一片对应大小的存储空间；
[0化1] 1. 3)将位数组对应的存储空间初始化为0。
[0052] 哈希函数的个数k、需要记录的访问历史长度n具体可根据内存资源、上层应用程 序需求等实际应用需求进行设置，当应用负载中数据被访问的次数较多时，则可设置较大 的k值W记录更多的访问次数；在内存资源充足的前提下，访问历史的长度n则设置越大越 好，n即为所记录的访问历史中所包含的页面数。
[005引本实施例中，位数组所需的存储空间中与kXn成正比，即位数组所包含的位的数 目与kXn成正比，则根据哈希函数的个数k、需要记录的访问历史长度n即可计算出UBF所 需的位数组的大小。在内存中申请一块内存空间作为位数组，再将位数组中的所有位初始 化为0，假定位数组中位的数目为化Xn，则在内存中申请一片化Xn/8字节的存储空间，并 将位数组对应的区域清零；同时初始化设定k个映射各页面X的哈希函数hi (X)，h2 (X)，… ，hk(x)，完成超大计数容量的布隆过滤器UBF的初始化。
[0化4] 本实施例中，步骤2)的具体步骤为；
[0化5] 2. 1)当页面X被访问时，初始化计数器i和热度h为0,跳转执行步骤2. 2);
[0化6] 2. 2)计算页面X对应的第i个哈希函数的值hi (X)，检测页面X在位数组中对应 第Mx)位的值，若检对应第hi(x)位的值为1，贝1J固巧专执行步骤2.如；若检巧UI^IJ对应第hi(X)位的值为0,则跳转执行步骤2. 4);
[0化7] 2. 3)将热度h加1，跳转执行步骤2. 4);
[0化引 2. 4)将计数器i加1，跳转执行步骤2. 2)，直至计数器i的值等于哈希函数的个数k，将热度h作为页面X的热度输出，跳转执行步骤3)。
[0059] 页面X在UBF的位数组中对应k个化该k个位中值为1的位数即定义为页面X 的热度。则当接收到上层应用对页面X的请求后，依次检测页面X在位数组中对应的k个 位，统计出该k个位中值为1的数目即得到页面X的热度h，再将页面X加入位数组中W记 录当前对页面X的访问。
[0060] 将页面X加入UBF的位数组中存在两种情况；第一种情况是页面X还尚未记录在 UBF的位数组中，此时是将页面X首次加入到UBF中进行首次记录；第二种情况是页面X已 经被记录在UBF的位数组中，此时是需要增加页面X的重复访问计数。本实施例中，步骤3) 具体通过当前页面的热度hW及预设的首次记录阔值t的比较确定执行上述哪种情况，即 通过首次记录阔值t判别一个页面是否已记录在UBF的位数组中，首次记录阔值t具体的 设置可显著小于k。
[0061] 当页面的热度h小于首次记录阔值t时，则执行第一种情况，否则执行第二种情 况。对于第一种情况，即页面X在UBF中尚未记录，则将位数组的k个对应位中t个位由0 翻转为1记录页面X，该样，页面X被加入后，其对应的k个位中至少有t个为1;当页面X 被再次访问时，页面的热度h不再小于t，则执行第二种情况。对于第二种情况，即页面X在 UBF中已记录，此时仅需要增加重复访问记录，则在位数组的k个对应位中选择一个值为0 的位按第一预设概率翻转为1W进行重复访问计数，即记录对页面X的访问次数。
[0062] 采用上述方法，本实施例只需t位信息就可表示一个页面X是否记录在UBF中，相 比于传统的L即策略中需要为每个页面维护一个整数计数器W记录访问次数，且每个整数 计数器需占据数十位内存空间，能够有效降低内存开销。本实施例也仅需要维护一个UBF W实现页面的各次访问记录，因而其内存开销也显著低于需要维护多个BloomFilter的 MBFs方案。
[0063] 本实施例通过将k位中一个0位W-定概率翻转为1来进行重复访问计数，对页 面X的各次访问均被记录在UBF的k个对应位中。即便对页面X的访问次数呈指数增长时， 在UBF中与页面X对应的1位的个数也仅呈线性增长，使得通过线性增长的位信息即可记 录指数增长的访问次数，具有超大计数范围，从而在实现低内存开销的同时实现大数据量 的热点数据识别。由于计数范围的空前增长，也可w显著提高热点数据识别准确度及效率。 而传统的MBFs方案需要维护n个BloomFilter,且最多能记录的页面访问次数仅为n，当 页面X的访问次数超过n时，后续的访问将不能记录在MBFs中，从而导致热点信息丢失。
[0064] 本实施例中，第一预设概率为1/2^，其中h为当前页面的热度，t为次记录阔值。 即当对页面X需要进行重复访问计数时，将页面X在位数组的k个对应位中的一个值为0 的位按1/2^的概率翻转为1，从而对于特定页面X，仅仅利用几位信息即可记录应用程序 对页面X的数百次访问。
[00化]本实施例中，步骤3)中将一个0位翻转为1前还包括针对一些1位进行随机清零 的步骤，具体步骤为；统计待翻转为1的位所在字节中值为1的位的数目m，根据统计得到 的数目mW第二预设概率将待翻转为1的位所在字节的各个位清零。对于那些曾经出现在 访问历史中、但很久没有被访问的页面，如果将其在位数组中对应的"1"位慢慢地翻转为 0,可W使其热度逐步下降，最终会在访问历史中消失，有效清除掉长时间未被访问而没有 任何价值的早期访问历史数据。
[0066] 本实施例中，第二预设概率为l/8-m，其中m为待翻转为1的位所在字节中值为1 的位的数目。即对于特定的一个位，将该位由0翻转为1之前，先统计该位所在的字节中1 的个数m，再Wl/8-m的概率将该字节的所有位清零，然后执行将该特定 位由0翻转为1的 操作。
[0067] 本实施例通过指定的热度阔值化reshold识别页面是否为热点数据，若页面X的 热度h大于指定的热度阔值化reshold，则说明页面X为热点页面，页面X对应的数据为热 数据，应该保存在高端设备上；若页面X的热度h小于指定的热度阔值化reshold，则说明X 为不频繁访问页面，页面X对应的数据为不频繁访问数据，即为冷数据，应该保存在低端设 备上。得到热点数据识别结果后，将该识别结果返回混合存储系统中，根据热点数据指导混 合存储系统中的数据布局。
[0068] 本实施例中，步骤4)还包括根据页面X的热度按式（1)调整指定的热度阔值的大 小W用于下一次热点数据识别的步骤；
[0069]
(1)
[0070] 其中，h表示页面X的热度，NewT虹eshold表示调整后的热度阔值，T虹eshold表 示调整前的热度阔值，〇63^6地0巧3肖63表示预先设定的需要识别出的热点页面的数目。假 设在一个两级的分层存储系统中，应用程序需要将最热的1000个页面保存在第一级存储 层次，则Desire地o1:Pages设定为1000。
[0071] 本实施例中，通过页面X的热度对指定的热度阔值化reshold作动态调整，如式 (1)所示为本实施例动态调整的第一种规则。第一种规则中，每当一个页面被访问时，根 据页面X的热度按照式（1)调整热度阔值化reshold，当页面X的热度h的值大于热度阔 值化reshold时，上调热度阔值化reshold，即新的阔值将会增加；反之，当页面X的热度h 的值小于热度阔值化reshold时，下调热度阔值化reshold，即新的阔值将会减少。通过上 述第一种规则可W将热度阔值化reshold调整为负载中所出现页面的热度平均值，从而使 得热度阔值化reshold能够动态自适应于负载，提高热点数据识别中对于不同负载的灵活 性。
[0072]本实施例中，步骤5)还包括当页面X识别为热点数据时，按式（2)上调调整后的 热度阔值，得到最终调整后的热度阔值用于下一次热点数据识别的步骤；
[007引
（2)
[0074] 其中，h表示页面X的热度，Newl'虹eshold表示调整后的热度阔值，Newl'虹eshold' 表示最终调整后的热度阔值，〇63山6地0巧3肖63表示预先设定的需要识别出的热点页面的 数目。
[0075] 如式（2)所示为本实施例动态调整的第二种规则，当一个页面被识别为热点数据 时，即页面的热度h的值大于热度阔值化reshold时，上调热度阔值化reshold。由于如果 大量的页面被识别为热点数据，则说明热度阔值化reshold过低，应该适当增加阔值，W从 该些热点页面中找出热度更高的页面，因而通过上述第二条规则可W在每找出一个热点页 面时增加热度阔值化reshold的值，使热度阔值化reshold的值逐步提高，一些热度不太高 的热点数据将可能重新被判定识别为冷数据，因而最终能够从大量的热点页面中筛选出最 热的数据，从而确保通过调整的热度阔值化reshold可W从较热的数据中识别出最热的数 据。而传统的MBFs方法中，由于只能设定一个静态阔值，因而不具灵活性，访问次数超过该 静态阔值的页面均被识别为热点数据，无法更新得到最热的数据。
[0076] 上述只是本发明的较佳实施例，并非对本发明作任何形式上的限制。虽然本发明 已W较佳实施例揭露如上，然而并非用W限定本发明。任何熟悉本领域的技术人员，在不脱 离本发明技术方案范围的情况下，都可利用上述揭示的技术内容对本发明技术方案做出许 多可能的变动和修饰，或修改为等同变化的等效实施例。因此，凡是未脱离本发明技术方案 的内容，依据本发明技术实质对W上实施例所做的任何简单修改、等同变化及修饰，均应落 在本发明技术方案保护的范围内。
【主权项】
1. 一种面向混合存储系统的低内存开销热点数据识别方法，其特征在于具体实施步骤 为： 1) 定义超大计数容量的布隆过滤器UBF，所述超大计数容量的布隆过滤器UBF通过位 数组以及映射各页面至所述位数组的k个哈希函数记录页面的访问次数；初始化所述位数 组为O并设定各个哈希函数； 2) 当页面X被访问时，通过所述位数组查询页面X的热度，所述页面X的热度为页面X 在位数组的对应k个位中值为1的位数； 3) 判断页面X的热度是否小于预设的首次记录阈值t，其中首次记录阈值t小于哈希 函数的个数k，若为是，判定页面X尚未记录在UBF中，针对页面X在位数组的k个对应位， 通过将其中t个位由O翻转为1记录页面X ;否则判定页面X已记录在UBF中，针对页面X 在位数组的k个对应位，通过将其中一个值为O的位按第一预设概率翻转为1进行页面X 的重复访问计数； 4) 比较页面X的热度与指定的热度阈值的大小，若页面X的热度大于热度阈值，则页面 X对应的数据识别为热点数据；跳转执行步骤2)。2. 根据权利要求1所述的面向混合存储系统的低内存开销热点数据识别方法，其特征 在于：所述步骤3)中第一预设概率为l/2h'其中h为页面X的热度，t为首次记录阈值。3. 根据权利要求2所述的面向混合存储系统的低内存开销热点数据识别方法，其特征 在于，所述步骤3)中将一个值为O的位翻转为1前还包括进行随机清零的步骤，具体步骤 为：统计待翻转为1的位所在字节中值为1的位的数目m，根据统计得到的数目m以第二预 设概率将待翻转为1的位所在字节的各个位清零。4. 根据权利要求3所述的面向混合存储系统的低内存开销热点数据识别方法，其特征 在于：所述第二预设概率为l/8-m，其中m为待翻转为1的位所在字节中值为1的位的数目。5. 根据权利要求所述4的面向混合存储系统的低内存开销热点数据识别方法，其特征 在于，所述步骤2)的具体步骤为： 2. 1)当页面X被访问时，初始化计数器i和热度h为0,跳转执行步骤2. 2); 2. 2)计算页面X对应的第i个哈希函数的值h (X)，并检测页面X在所述位数组中对 应第比(X)位的值，若检测到对应第Iii (X)位的值为1，则跳转执行步骤2. 3);若检测到对应 第比(X)位的值为0,则跳转执行步骤2. 4); 2. 3)将热度h加1，跳转执行步骤2. 4); 2.4)将计数器i加1，跳转执行步骤2. 2)，直至计数器i的值等于哈希函数的个数k， 将热度h作为页面X的热度输出，跳转执行步骤3)。6. 根据权利要求5所述的面向混合存储系统的低内存开销热点数据识别方法，其特征 在于，所述步骤1)中初始化所述位数组的具体步骤为： I. 1)设定哈希函数的个数k以及需要记录的访问历史长度η ; 1. 2)根据设定的哈希函数的个数k、访问历史长度η计算所述位数组所需的存储空间 大小，在内存中为所述位数组申请一片对应大小的存储空间； 1. 3)将所述位数组对应的存储空间初始化为0。7. 根据权利要求6所述的面向混合存储系统的低内存开销热点数据识别方法，其特征 在于：所述位数组所需的存储空间与kXn成正比，其中k为哈希函数的个数，η为需要记录 的访问历史长度。8. 根据权利要求1~7中任意一项所述的面向混合存储系统的低内存开销热点数据识 别方法，其特征在于，所述步骤4)还包括根据页面X的热度按式（1)调整指定的热度阈值 大小以用于下一次热点数据识别的步骤（5);其中，h表示页面X的热度，NewThreshold表示调整后的热度阈值，Threshold表示调 整前的热度阈值，DesiredHotPages表示预先设定的需要识别出的热点页面的数目。9. 根据权利要求8所述的面向混合存储系统的低内存开销热点数据识别方法，其特征 在于，所述步骤5)还包括当页面X识别为热点数据时，按式（2)上调所述调整后的热度阈 值，得到最终调整后的热度阈值用于下一次热点数据识别的步骤；其中，h表示页面X的热度，NewThreshold表示调整后的热度阈值，NewThreshold'表 示最终调整后的热度阈值，DesiredHotPages表示预先设定的需要识别出的热点页面的数 目。
【专利摘要】本发明公开一种面向混合存储系统的低内存开销热点数据识别方法，具体步骤为：1)定义超大计数容量的布隆过滤器UBF记录页面的访问次数；2)当页面x被访问时，查询页面x的热度；3)若x尚未记录在UBF中，通过将UBF中x对应的若干位由0翻转为1记录x；若x已经记录在UBF中，则通过将UBF中x对应的一个0位以一定概率翻转为1，从而增加x的热度；4)比较页面x的热度与指定的热度阈值的大小，若页面x的热度大于热度阈值，页面x对应的数据识别为热点数据；跳转执行步骤2)。本发明具有内存开销低、能够实现大数据量的热点数据识别且识别准确度高的优点。
【IPC分类】G06F12/08, G06F17/30
【公开号】CN104881369
【申请号】CN201510236366
【发明人】肖侬, 陈志广, 卢宇彤, 周恩强, 张伟, 董勇
【申请人】中国人民解放军国防科学技术大学
【公开日】2015年9月2日
【申请日】2015年5月11日