CN1499382A - 廉价冗余磁盘阵列系统中高效高速缓存的实现方法 - Google Patents

Abstract

本发明公开了一种廉价冗余磁盘阵列系统中高效高速缓存的实现方法，包括：设置高速缓存为两级，第一级高速缓存与磁盘阵列采用组相联的映射方式，第二级高速缓存与磁盘阵列采用全相联的映射方式；先在第一级高速缓存中查找所需，若命中，则提取被请求数据；否则，在第二级高速缓存中查找，若命中则提取被请求数据；否则，判断第二级高速缓存是否已满，若未满，将存储被请求数据及其相邻数据放入第二级高速缓存的空闲大块中，将第二级高速缓存中包含被请求数据的小块标注为访问状态，提取被请求数据；若已满，则对第二级高速缓存中的大块进行替换，再提取被请求数据，若其中有小块被标识为访问状态，则将这些小块移到第一级高速缓存中，再进行替换。

Description

廉价冗余磁盘阵列系统中高效高速缓存的实现方法

技术领域

本发明涉及廉价冗余磁盘阵列系统领域，特别是涉及一种廉价冗余磁盘阵列系统中高效高速缓存的实现方法。

背景技术

廉价冗余磁盘阵列(RAID)系统简称磁盘阵列，如今它以其成本低、功耗小、传输速率高等优点，在网络服务器等设备中已得到广泛的应用。在RAID系统中高速缓存(Cache)设计的好坏是影响其系统性能的重要因素。通过Cache可以快速读写数据，能够有效提高系统的输入/输出(I/O)性能。

Cache容量与下一级存储器即磁盘阵列的容量相比是很小的，一般不超过1％，它保存的只是下一级存储器内容的一个子集，Cache与下一级存储器之间内容的交换是以块为单位。

Cache与下级存储器之间典型映射方式有：全相联映射方式(FullyAssociative Mapping)、直接相联映射方式(Direct Mapping)和组相联映射方式(Set Associative Mapping)等。

当一个下级存储器中的块要放到Cache中去，而Cache中允许存放此块的位置都被占满了，这就需要进行替换。常用的替换算法主要如：最不经常使用(LFU，Least Frequently Used)算法、近期最少使用(LRU，Least RecentlyUsed)算法和随机替换(Random Replacement)。

Cache的产生是根据数据访问中的局部性原理，访问存储空间的局部性规律主要包括两个方面：

时间局部性：如果一个存储项被访问，则可能该项会很快被再次访问。

空间局部性：如果一个存储项被访问，则该项及其邻近的项也可能很快被访问。

因此如果利用好局部性原则，并采用合适的Cache组织结构、映射方式和替换策略，可以有效地提高RAID系统的效率。

传统RAID系统中的Cache，基本上采用一级Cache模式，使用LRU替换算法。当一个输入/输出(I/O)请求到达时，首先在Cache中查找，当在Cache中没有命中时，数据直接从磁盘阵列中取出到Cache中。该方法主要好处是容易实现，但由于只有单级Cache，不能同时兼顾时间和空间局部性，这是因为时间和空间局部性是一对矛盾，而在单级Cache中很难协调。另外，现有技术缺乏预取策略，故Cache的不命中率非常高。

综上所述，现有技术虽然算法简单，实现起来较为容易。但是只能在已知了其应用特点的特定应用中，有针对性的采用时间或空间局部性的设计，而不能同时兼顾时间和空间局部性的特点，无法克服时间和空间局部性在单级Cache中存在的固有矛盾，缺乏预取策略，对于通用场合Cache命中率不高，从而降低了系统整体性能。

发明内容

有鉴于此，本发明的目的是提供一种廉价冗余磁盘阵列系统中高效高速缓存的实现方法。通过该方法能够克服在单级Cache中时间和空间局部性之间的固有矛盾，并使其包含预取策略，提高通用场合Cache的命中率，从而提升系统的整体性能。

一种廉价冗余磁盘阵列系统中高效高速缓存的实现方法，该系统至少包括高速缓存和磁盘阵列，包括以下步骤：

设置高速缓存为两级，将第一级高速缓存划分为一个以上的组，每组含有一个以上的小块，并与磁盘阵列采用组相联的映射方式，第二级高速缓存划分为一个以上的大块，每个大块中包含有一个以上的小块，并以大块为基本单位与磁盘阵列采用全相联的映射方式；

数据查找首先在第一级高速缓存中进行，如果命中，则提取被请求数据，否则，在第二级高速缓存中进行数据查找，如果命中，标注被命中的小块为访问状态，提取被请求数据，否则，判断第二级高速缓存是否已满，如果未满，将磁盘阵列中存储被请求数据的逻辑块和其相邻逻辑块中的数据放入第二级高速缓存的空闲大块中，将第二级高速缓存中包含被请求数据的小块标注为访问状态，提取被请求数据，如果已满，用磁盘阵列中存储被请求数据的逻辑块和其相邻逻辑块中的数据替换第二级高速缓存中的大块中的数据，如果被替换的大块中有小块被标识为访问状态，则先将这些小块中的数据移到第一级高速缓存中，再进行替换，提取被请求数据，否则，直接替换，提取被请求数据。

该方法所述磁盘阵列中的每个逻辑单元分别与整个第一级缓存构成组相联映射。

该方法所述磁盘阵列中的每个逻辑单元分配到第二级高速缓存的一部分，并于该部分构成全相联映射，并且磁盘阵列中的每个逻辑单元所分配的第二级高速缓存部分的大小，可根据数据读取过程中的实际情况动态分配。

该方法所述小块是逻辑块。

该方法所述在第一级高速缓存中进行的数据查找具体包括：在第一级高速缓存中，以逻辑单元号和逻辑块地址的组合作为关键字采用哈希算法进行查找，如果未命中，再以逻辑单元号和逻辑块地址的组合作为关键字采用哈希算法进行第二次查找。

该方法所述在第二级高速缓存中进行的数据查找是采用平衡二叉树搜索算法。

该方法所述在第二级高速缓存中进行的数据替换采用近期最少使用算法。

该方法所述将第二级高速缓存中标注成访问状态的小块中的数据移到第一级高速缓存中具体包括：

根据逻辑单元号和逻辑块地址的组合作为哈希替换的关键字进行一次哈希计算，如果对应小块为空，将第二级高速缓存小块中的数据直接移到该小块，否则，进行第二次哈希计算，如果对应小块为空，将第二级高速缓存中小块的数据直接移到该小块，否则，替换该小块中的数据。

该方法进一步包括：在系统刚刚启动时，定时将第二级高速缓存中被标注为访问状态的小块中的数据复制到第一级高速缓存中，将第二级高速缓存中已经复制过的小块标注成未访问状态，如果第一级高速缓存已满，则该过程停止。

该方法进一步包括：预先在第二级高速缓存的每个小块前设置一个特征(flag)位，所述的标注成访问状态是将该小块前的特征(flag)位置1，所述的标注成未访问状态是将该小块前的特征(flag)位置0。

该方法所述的设置高速缓存为两级是通过将一个高速缓存划分成两部分而实现的。

该方法所述的设置高速缓存为两级是采用两个高速缓存实现的。

从上述方案中可以看出，本发明采用两级Cache结构巧妙地克服了时间和空间局部性在单级Cache中存在的固有矛盾，提高了时间局部性数据的生命周期，同时第二级Cache中的预取策略又兼顾到了空间局部性。从而具有普遍的适用性，减少了不必要的频繁换入换出操作，降低了数据查找时间，增加了查找命中率，提高了系统性能。

附图说明

图1为第一级Cache结构示意图；

图2为第一级Cache与下级存储器的组相联映射示意图；

图3为第二级Cache结构示意图；

图4为第二级Cache与下级存储器的全相联映射示意图；

图5为第二级Cache的主要数据结构及关联示意图。

具体实施方式

下面结合附图和具体实施例对本发明再做进一步详细的说明。

当Cache的总容量固定时，针对数据访问所涉及到的时间和空间局部性的优化其实是一对矛盾，这是因为增加存储块大小(block size)与增加Cache中存储块数量(block number)是成反比例的，因此通常有关Cache的设计都要考虑到合适的block size，使block size和block number达到一种折中。

在本发明中综合有关Cache的实现原理、技巧和算法，决定将Cache划分为两级，使Cache的第一级结合时间局部性的特征，具有小的block size而block number很大，而第二级考虑结合空间局部性特征，使其具有大的block size而block number很小。这样同时满足了特定情况下block size和block number的要求，从而很好解决了block size和block number之间的矛盾，使系统性能得到显著提高。

两级Cache构成如下：第一级为与时间相关的Cache，与下级存储器采用组相联映射方式，配置较小的block size和较大的block number，可以以一个基本的逻辑块512字节(bytes)作为其一个存储的小块(SB)，然后再将这些小块分成若干个组(Set)；第二级为与空间相关的Cache，与下级存储器采用全相联映射的方式，由于该级将与预取技术有关，故配置较大的block size和较小的block number，可以将其划分成若干个大块(LB)，使每个大块包含一定数目的逻辑块，即小块。

以上这样配置是考虑到：当在Cache未命中时，被请求的数据及其相邻数据组成一个大块数据，从存储设备移到第二级空间Cache中；当空间Cache中包含若干小块数据的大块数据被替换时，仅仅过去被访问过的几个小块数据被移到第一级时间Cache中，这样有利于降低冲突。在该方案中对于时间Cache不需要预取较大数据块，故采用尽量小的block size，另外还要增大入口数目，即block number，这样可以尽量减少由于频繁换入换出所带来效率降低的问题。对于空间Cache来说，存在包含多个相邻小块的大块有利于发挥预取策略，提高Cache命中率，但大块也不能太大，太大将加大数据传输时间，所以需要在命中率和传输时间之间寻求平衡。

一级和二级Cache具体结构举例说明如下：

一级Cache的结构参见图1所示，在本实施例中，一级Cache总容量取为512M，Cache的每个小块512bytes，将Cache分为1024个组，则每组1024个小块。

一级Cache由下级存储器即磁盘阵列的所有逻辑单元共享，磁盘阵列的任何逻辑单元都可占有整个一级Cache，并与其构成组相联的映射关系。这是考虑到其容量比较小和时间局部性原则，其与逻辑单元之间采用组相联的映射关系。下级存储器的逻辑单元以最大容量512G计算，以1024个小块为一个区，则每区容量512Kbytes，可达1M个区块。一级Cache与下级存储器之间的映射关系参见图2所示。

设一级Cache有a组，每组b块，下级存储器中以a个块为一个区来划分，设k为下级存储块存放到Cache中的组号，j为下级存储块的块号。则有如下关系：

n_c＝a×b                    n_c是Cache中的总的块数

k＝j mod a

其中，a＝1024，b＝1024，j＝逻辑块地址(LBA，Logic Block Address)即小块的块号。在这种方式下，每个下级存储块存放到哪个组中是确定的，至于存在该组中的哪一个块中则是可变的。

考虑到映射方式和时间局部性，并从算法和效率考虑，一级Cache替换以及组内查找算法采用二次哈希(Hash)的方法。

替换时首先根据逻辑单元号(LUN)和逻辑块地址的组合LUN+LBA作为哈希替换的关键字计算一次Hash，若对应小块为空，将第二级高速缓存小块中的数据直接移到该小块；若对应块冲突，再以LUN+LBA作为哈希替换的关键字进行第二次Hash计算，若还冲突，则替换该小块中的数据。

查找时也同样是采用二次Hash算法，即：在第一级高速缓存中，以LUN+LBA作为关键字采用Hash算法进行查找，如果命中，则提取被请求数据，如果未命中，再LUN+LBA作为关键字进行第二次Hash查找，如果命中，则提取被请求数据，如果仍未命中，则按上述方法进行替换。

这种方法的好处是，在保证命中率的同时，既降低了复杂度，又不太影响性能，还避免了复杂的算法和数据控制信息所带来的额外开销。

二级Cache的容量较大，其大小可配置，即总容量可被不同的逻辑单元所瓜分，每个逻辑单元可单独配置所用的二级Cache大小，并与其构成映射关系，并且配置过程可以是动态的，可根据实际的数据读取过程，对各逻辑单元的缓存大小进行动态分配。这样做可以防止整个二级Cache被某个逻辑单元长期占用，而影响其它的逻辑单元工作。参见图3所示，在2GB时，每小块512K，32个小块组成1个大块，最多可分为128K个大块。另外，在每小块前还有4bytes的flag位用来标识该小块的状态。由于flag位很小，在计算字节数时可忽略不记。

参见图4所示，二级Cache与下级存储器采用全相联的映射关系，其基本操作和算法归纳如下：

查找

参见图5所示，二级Cache的查找算法是针对磁盘阵列的每个逻辑单元采用平衡二叉树搜索算法。对应每个逻辑单元都有一个用于查找的平衡二叉树，在每个逻辑单元中以LBA作为关键字对平衡二叉树进行查找。

在查找时，首先根据current指针，与当前预取的数据进行比较，若未命中，再根据root指针，对该LUN对应的整个平衡二叉树中进行查找。当命中时，将对应小块的flag位置1，标识为访问状态，并提取被请求数据。当未命中时，从下级存储器中读取包含小块数据的一个大块数据到二级Cache中，有两种情况，空间满和未满。当空间未满，处理较简单，直接从二级Cache的Free List中获取一大块用于存储数据；当空间满时，则需要替换操作，替换操作采用LRU算法，根据LRU List决定需替换块。最后，根据查找结果，相应更新LRU List、Free List和flag信息。

平衡二叉搜索树算法的好处是相比其他查询算法，具有较高的查询效率。即使在极端情况下，如某个LUN满配置分配，即2GB Cache全部分配给该LUN，此时平均查询次数约为8.5次，比较次数不会太大，速度比较快，况且一般不会出现极端情况。同时，它还可以容易实现预取策略，数据映射限制较少，组织结构极为灵活。

替换

二级Cache的替换算法采用LRU：根据LRU List决定需替换的块，将块中标识为最近被访问过的小块搬移到一级Cache中，然后用新数据替换原来的老数据，根据LBA值重新调整平衡二叉树，使其符合平衡二叉树的定义。最后，更新LRU List和flag信息。

映射

二级Cache采用全相联映射方式，读取的数据可以根据需要放在Cache中任何位置，没有映射规则限制。

搬移

二级Cache的搬移是单向的，即只能将二级Cache中的数据搬移到一级Cache中，由于搬移的触发条件不同，搬移分为两种：

二级Cache替换时的搬移：替换发生时，需要将原数据大块中被访问过的小块搬移到一级Cache中，可根据flag中置1的位将对应小块复制到一级Cache中，具体放在一级Cache的位置可参见前面有关一级Cache替换部分。搬移结束后，将已经搬移过的小块所对应flag位清0。

时钟定时引起的搬移：定时搬移通常是在系统刚刚启动时发生，这时往往在相当一段时间内一级Cache是空的，为了充分利用系统资源，因此设计了定时搬移，当一级缓存已满时，定时搬移将自动停止。RAID系统对应每个LUN都具有一个定时器，定时将二级Cache中最近被访问过的小块数据搬移到一级Cache中，搬移原则同前，即根据flag中置1的位将对应小块复制到一级Cache中，搬移结束后，将已经搬移过的小块所对应flag位清0。

本实施例的算法概括描述如下：

命中在一级Cache即组相联Cache中：

如果小块数据被发现在组相联Cache中，处理较简单，只需提取被请求的数据即可。

命中在全相联空间Cache中：

如果数据被发现在全相联Cache中，需标注一个大块中究竟哪些小块被命中，即将该小块的flag位置1，以便将来大块被替换时，被访问过的小块移到一级Cache中，最后提取被请求的数据。

在两级Cache中都未命中：

如果两级Cache皆未命中，一个包含所需数据的大块将从存储设备中取出，并被放入二级Cache中，具体操作分为两种情况：

空间Cache未满：

空间Cache至少还有一个空闲的项，将磁盘阵列中包含所需数据的逻辑块，即小块及其相邻的小块中的数据，作为一个大块数据从存储设备取出到Cache空闲大块中。这里相邻小块被取出，体现了预取方法。同时所需的小数据块被标识为访问状态，以便将来大块替换时，小数据块移到直接相联Cache中，最后提取该被请求数据。

空间Cache已满：

对二级的空间Cache采用LRU替换策略，若被替换大块数据中有小块数据被标识为访问状态，则这些小块数据被移到一级的直接相联Cache中，再进行替换，提取被请求数据，否则，直接替换，提取被请求数据。这样有利于提高一级时间Cache中小块数据的生命周期，避免频繁换入换出操作。

随着应用不断深入，采用结合时间和空间局部性的两级Cache越来越体现出其优越的性能，根据分析统计，大致可以得出这样一个结论：只需使用一级Cache容量的1/4大小的空间，两级Cache可以获得与一级Cache相同的性能，既节省了成本又提高了性能。

与现有技术相比，本发明的两级Cache比单级Cache具有更好的性能，通常Cache设计不可避免受到诸如Cache容量、算法复杂度等因素限制。而在RAID系统中的Cache，情况有了变化，Cache容量、算法复杂度等限制已经不在是最关键的因素，取而代之的是时间局部性和空间局部性之间的矛盾。为充分发挥Cache作用，更好提高系统性能，采用两级Cache结构则可以克服时间和空间局部性在单级Cache中存在的固有矛盾，从而更大提高时间局部性数据的生命周期，减少不必要的频繁换入换出操作，同时降低了查找时间，提高了系统速度。

下面是对本Cache方案的性能评估：

命中率(Hit Ratio)是系统性能的重要指标，直接反映Cache的效率。下面是通过文件系统中相应文件操作，即分布在不同磁盘上的不同大小文件的常规操作，来统计Cache命中率情况的结果，表格如下：

                表1、二级Cache的性能评估

Times of simulation	Hit ratio ofone-level cache	Hit ratio of proposedtwo-level cache
			1	0.21	0.78
2	0.24	0.77
			3	0.22	0.78
4	0.22	0.77
			5	0.23	0.78
Average hit ratio	0.22	0.78

从统计结果可以看出，本两级Cache方法充分采用了时间和空间局部性，与单级Cache命中率相比，命中率由0.22提高到0.78，效果非常理想。虽然本方案在管理算法方面较为复杂，但算法复杂度不会影响RAID系统整体响应速度。RAID系统具有独立的处理器处理有关算法，不会影响主机性能，同时命中率和命中次数提高降低了数据通讯环节，节省了不必要的访盘所涉及到的寻道、旋转时间等，故算法复杂度几乎不影响系统整体性能。

以上所述，仅为本发明的较佳实施例而已，并非用于限定本发明的保护范围。

Claims (13)

1、一种廉价冗余磁盘阵列系统中高效高速缓存的实现方法，该系统至少包括高速缓存和磁盘阵列，其特征在于，该方法包括以下步骤：

设置高速缓存为两级，将第一级高速缓存划分为一个以上的组，每组含有一个以上的小块，并与磁盘阵列采用组相联的映射方式，第二级高速缓存划分为一个以上的大块，每个大块中包含有一个以上的小块，并以大块为基本单位与磁盘阵列采用全相联的映射方式；

数据查找首先在第一级高速缓存中进行，如果命中，则提取被请求数据，否则，在第二级高速缓存中进行数据查找，如果命中，标注被命中的小块为访问状态，提取被请求数据，否则，判断第二级高速缓存是否已满，如果未满，将磁盘阵列中存储被请求数据的逻辑块和其相邻逻辑块中的数据放入第二级高速缓存的空闲大块中，将第二级高速缓存中包含被请求数据的小块标注为访问状态，提取被请求数据，如果已满，用磁盘阵列中存储被请求数据的逻辑块和其相邻逻辑块中的数据替换第二级高速缓存中的大块中的数据，如果被替换的大块中有小块被标识为访问状态，则先将这些小块中的数据移到第一级高速缓存中，再进行替换，提取被请求数据，否则，直接替换，提取被请求数据。

2、根据权利要求1所述的方法，其特征在于，磁盘阵列中的每个逻辑单元分别与整个第一级缓存构成组相联映射。

3、根据权利要求1所述的方法，其特征在于，磁盘阵列中的每个逻辑单元分配到第二级高速缓存的一部分，并于该部分构成全相联映射。

4、根据权利要求3所述的方法，其特征在于，磁盘阵列中的每个逻辑单元所分配的第二级高速缓存部分的大小，可根据数据读取过程中的实际情况动态分配。

5、根据权利要求1所述的方法，其特征在于，所述小块是逻辑块。

6、根据权利要求1所述的方法，其特征在于，所述在第一级高速缓存中进行的数据查找具体包括：在第一级高速缓存中，以逻辑单元号和逻辑块地址的组合作为关键字采用哈希算法进行查找，如果未命中，再以逻辑单元号和逻辑块地址的组合作为关键字采用哈希算法进行第二次查找。

7、根据权利要求1所述的方法，其特征在于，所述在第二级高速缓存中进行的数据查找是采用平衡二叉树搜索算法。

8、根据权利要求1所述的方法，其特征在于，所述在第二级高速缓存中进行的数据替换采用近期最少使用算法。

9、根据权利要求1所述的方法，其特征在于，所述将第二级高速缓存中标注成访问状态的小块中的数据移到第一级高速缓存中具体包括：

根据逻辑单元号和逻辑块地址的组合作为哈希替换的关键字进行一次哈希计算，如果对应小块为空，将第二级高速缓存小块中的数据直接移到该小块，否则，进行第二次哈希计算，如果对应小块为空，将第二级高速缓存中小块的数据直接移到该小块，否则，替换该小块中的数据。

10、根据权利要求1所述的方法，其特征在于，该方法进一步包括：在系统刚刚启动时，定时将第二级高速缓存中被标注为访问状态的小块中的数据复制到第一级高速缓存中，将第二级高速缓存中已经复制过的小块标注成未访问状态，如果第一级高速缓存已满，则该过程停止。

11、根据权利要求1或10所述的方法，其特征在于，进一步包括：预先在第二级高速缓存的每个小块前设置一个特征(flag)位，所述的标注成访问状态是将该小块前的特征(flag)位置1，所述的标注成未访问状态是将该小块前的特征(flag)位置0。

12、根据权利要求1所述的方法，其特征在于，所述的设置高速缓存为两级是通过将一个高速缓存划分成两部分而实现的。

13、根据权利要求1所述的方法，其特征在于，所述的设置高速缓存为两级是采用两个高速缓存实现的。

Images