多RAID存储结构中的总线争用模型：M/G/1队列，IO和总线建模

理论计算机科学电子笔记232（2009）5-16www.elsevier.com/locate/entcs分区RAID存储系统中的总线建模Peter Harrisona和Soraya Zertalba伦敦帝国理工学院，南肯辛顿校区，伦敦SW7 2AZ，英国电子邮件：pgh@doc.ic.ac.ukbPRiSM，Universi t'edeVersalilles，45Av. desEtats-Unis，78000Versailes，France电子邮件：Zertal@prism.uvsq.fr摘要提出了一种多RAID存储结构中的总线争用模型。 基于M/G/1排队模型，主要问题是如何确定服务时间分布，以准确地反映高度混合的输入请求流。这是由于不同RAID组织的共存，这些RAID组织会生成几种类型的物理请求（每个RAID级别的读/写），这些请求具有不同的相关大小。大小分布本身通过条带化机制变得更加复杂，在RAID 5中具有完整/大/小条带。我们显示的总线traffic上的系统的整体性能的模型预测和验证对模拟的硬件，使用常见的工作负载假设的影响关键词：多RAID，分区磁盘，M/G/1队列，IO和总线建模，仿真1引言存储系统已经从互连磁盘的小集合发展到由服务于非常大的用户社区的多个应用程序共享的大型磁盘阵列。RAID（独立磁盘冗余阵列）[2]系统是第一个被广泛接受的大规模存储体系结构，为此提出了这些包括一系列RAID变体，以提高访问速度和可靠性（从RAID0到RAID6），以及HPautoRAID [7]，它支持同一存储系统上不同空间位置的两个RAID组织。在[5]的Multi-RAID系统中，不同的RAID配置在相同的磁盘设备上共存，没有物理空间边界，并共同满足动态变化的性能和空间需求。在这种架构上，采用多种方案实现最常用的RAID组织（RAID 0 -1和RAID5），不同类型和大小的请求在通过总线连接到RAID控制器的异步磁盘上并行执行。总线数据传输1571-0661/© 2009 Elsevier B. V.根据CC BY-NC-ND许可证开放访问。doi：10.1016/j.entcs.2009.02.0476P. 哈里森，S。Zertal/Electronic Notes in Theoretical Computer Science 232（2009）5在请求执行过程中的不同步骤中发生，具有广泛的长度范围总线是这些基本上独立的异步并行磁盘的关键共享资源，并且容易拥塞。这样引入的延迟对整个系统响应时间有对这种存储体系结构和相关机制进行建模对于分析它可以提供的性能以及预测它在不同工作负载下的行为非常重要。我们随后详细阐述了磁盘阵列模型并仔细验证了它，特别是在假设磁盘独立操作时出现的特定fork-join问题的近似解[5]。我们通过分别在[14，15]中找到适当的线性和非线性寻道距离分布，将这项工作扩展到现代分区磁盘该领域的其他工作涉及单个RAID级别及其在特定工作模式（正常或降级）下的性能[1，8，10]。其中一些研究集中在传输吞吐量[9]上，这可能受到共享总线带宽的限制在本文中，我们专注于总线连接设备在单RAID组织以及多RAID系统。在第2节中讨论了激发本研究的非常具体的背景特征，在第3节中描述了所提出的模型，在第4节中确定了其参数，主要是矩，使用系统操作原理的详细描述。验证在第5节中显示了对模拟的影响，在第6节中总结了本文。2背景和动机我们使用M/G/1队列对RAID连接总线进行建模-从在各种上下文中生成的流量中提取其输入速率-在磁盘服务期间之前，期间或/和之后。然后，我们评估其对整体IO响应时间的影响。在RAID存储系统中，IO请求 所产生的不同组合可能导致总线上的数据传输到本地，镜像或奇偶校验磁盘;在实际磁盘服务之前，期间或/和之后，在一个或多个不同的磁盘上。服务之前和之后的传输在并行计算机体系结构和特别是网络社区中都得到了很好的研究[13，4];当然，前者更接近我们对RAID存储系统的兴趣。在每个整体磁盘访问的不同步骤中存在的传输将该过程分成由总线延迟分隔的阶段，每个阶段对整个响应时间有不同的事实上，延迟可以改变下一阶段的执行，并且这种影响在具有更复杂的执行方案的多RAID系统中更重要，因此产生更复杂的总线传输。 最简单的情况是RAID 0 -1（条带化）上的读或写请求 镜像RAID）。总线传输只执行一次：在磁盘服务之后执行读取，在磁盘服务之前执行写入，如图1所示。然而，在每种情况下，传输到每个磁盘/从每个磁盘传输的数据块（本机或镜像）的数量是不同的，并且取决于请求类型和大小，如图2和图3所示。1 从RAID0到RAID6，正如伯克利的分类所定义的那样P. 哈里森，S。Zertal/Electronic Notes in Theoretical Computer Science 232（2009）57(a) RAID 01物理读图（b）RAID 01物理写图Fig. 1. RAID0-1服务时间图从B0到B7的8块请求。在RAID 0 -1上，我们可以根据所选的调度策略2读取本机磁盘上的（本机）块或镜像磁盘上的镜像。 在图23所示的示例中，在本机磁盘{磁盘0、磁盘 1、磁盘 2}和镜像版本上读取{B0、B 1、B 2、B 6}剩下的街区。此调度导致磁盘1（本机）和磁盘3（镜像）上的两个连续数据块读取请求以及其他磁盘上的单个数据块读取。本地镜像服务器磁盘0磁盘1磁盘2磁盘3磁盘4磁盘5B6B0B1B2B3B7B4B58块逻辑读取请求磁盘{0，4}上有2个块，其他磁盘上有1个块图二. RAID 0 -1逻辑读RAID 0 -1写请求需要访问关联磁盘上的本机版本和镜像版本8块逻辑请求然后生成到{盘0，盘 1}的三个连续块请求，以写入块{B0，B 3，B 6}的本机版本，以及它们的镜像{disk3，disk 4}来写入相同的镜像版本个街区.本机磁盘{disk2}及其镜像磁盘{disk5}通过两个连续数据块请求{B2，B 5}进行访问。RAID5（分布式奇偶校验）由于其数据和冗余模式而更加复杂。在N个磁盘RAID 5上，条带是（N-1）个数据单元的集合，每个数据单元都由一个相关的奇偶校验单元控制，每个数据单元都位于异盘这也称为完整条带，因为它覆盖了所有磁盘。部分条带是具有奇偶校验块和少于（N-1）个数据块的条带。对于每个条带，无论其宽度如何，都计算奇偶校验条带单元（块），并且以循环方式与磁盘关联RAID 5上的读取类似于2 随机、最短队列、最短搜索距离、.等3 对于所有图，仅在磁盘上指示被访问的块。8P. 哈里森，S。Zertal/Electronic Notes in Theoretical Computer Science 232（2009）5本地镜像服务器磁盘0磁盘1磁盘2磁盘3磁盘4磁盘5B0B3B6B1B4B7B5B2B0B3B6B1B4B7B5B28块逻辑写入请求磁盘{2，5}上2个数据块，其他磁盘上3个数据块图三. RAID 0 -1逻辑写入RAID 0 -1，具有唯一的目标磁盘，而不是在本机目标和镜像目标之间进行选择。然而，写入是完全不同的，而且要复杂得多。根据逻辑请求的大小，当物理请求的大小覆盖条带中的所有数据单元、至少一半的数据条带单元和小于一半的数据条带单元时，生成的条带可以分别是满的、大的或小的。RAID 5写入可能会生成以下三种写入类型的组合：完整写入，后面是大写入或小写入。这三个写请求及其可能的组合中的每个写请求都有适当的奇偶校验计算和涉及不同数量磁盘的预读操作。这些磁盘分别是不用于完整条带写入的磁盘、仅用于大条带写入的非目标磁盘（不受写入请求影响的磁盘）和奇偶校验磁盘以及仅用于小条带写入的具有奇偶校验磁盘的目标磁盘，如图4所示。在组合的情况下（完整后接大条带或小条带），奇偶校验计算根据其两个分量执行。对于读取（在磁盘服务之后）执行一次传输，对于写入，则根据图5中的图表执行一次传输。我们考虑的Multi-RAID是RAID 0 -1和RAID 5的组合，这使得它生成的数据传输非常复杂，如图1和图5所示。3总线响应时间模型我们通过考虑其类型（读/写），其大小（块的数量）和系统的工作负载强度（在每秒逻辑请求的数量方面的到达率）来分析逻辑请求的总线响应时间。我们通过一个传统的M/G/1队列与一个单一的工作负载类，这是所有的IO传输类型和大小的不同的共存RAID组织的聚合在总线上的竞争所造成的延迟建模。由于有多个不同的IO请求输入流到达总线，它们在很大程度上独立运行，因此泊松假设并非不合理[12]。挑战在于估计这些大小的概率分布P. 哈里森，S。Zertal/Electronic Notes in Theoretical Computer Science 232（2009）59磁盘0磁盘1磁盘2磁盘3磁盘4磁盘5完全条带写入Bi，i>=0磁盘0磁盘1磁盘2磁盘3磁盘4磁盘5大条带写入Bi，i>0磁盘0磁盘1磁盘2磁盘3磁盘4磁盘5小条带写入B2和B3Block pre-read Block write见图4。 RAID 5逻辑写入计算这些转移的总到达率，这是一项相当容易的任务。于是，总线响应时间由等待时间Q总线和服务时间S总线组成，服务时间S总线仅取决于所讨论的特定IO传输的大小：T总线=Q总线+S总线=Q总线+K×T其中K是IO传输的大小（以块为单位），与逻辑请求相关，并在第3.2节中估计，T是传输一个块所需的时间，总线带宽的倒数。3.1公交车行驶时间（Q公交车）：我们使用Pollaczek-Khinchin公式[6]，就像在[5]中用于磁盘级别的延迟时间一样，带有总线相关参数：（一）E[Q总线λbusSbus]=的2（1−ρ总线）现在，输电负荷定义为：ρ总线=λ总线×S总线其中，S总线表示平均总线服务时间，并且正如我们稍后将使用的，S总线表示其二阶矩。实际上，我们一般用n个超棒来表示随机变量的n阶矩。B0B2XORB3B4B1B0B2XORB3B4B1B0B2XORB3B4B110P. 哈里森，S。Zertal/Electronic Notes in Theoretical Computer Science 232（2009）5当我们考虑多RAID存储系统时，P. 哈里森，S。Zertal/Electronic Notes in Theoretical Computer Science 232（2009）511奇偶校验盘数据盘(a) 完全条带写入奇偶校验盘非目标数据磁盘目标数据磁盘(b) 大条带写入奇偶校验盘目标数据磁盘(c) 小条带写入图五. RAID5服务时间图源自RAID布局请求的混合，以及由请求的预读、本机和镜像访问生成的 考虑到两种最常用的RAID组织，RAID0-1（镜像和条带化）和RAID5（分布式奇偶校验），总线传输可以详细描述如下4：λ总线=λ总线RAID0− 1+λ总线RAID5哪里λ总线RAID0− 1=λ×Praid0− 1×B（2−pr），以及4 “%”表示模函数。12P. 哈里森，S。Zertal/Electronic Notes in Theoretical Computer Science 232（2009）5（N−⎨⎨λ总线RAID5= λ×PRAID5（pr×B + pw（（cdtfull×N×[B ]）+（cdtlg（N+ 1））+（cdtsm×2（B%（N−1）+ 1）B是逻辑请求布尔参数cdtfull、cdtlg和cdtsm分别表示条带是满的、大的还是小的[5]5。它们是针对RAID 5写请求定义的，取决于逻辑请求大小（B）和RAID 5宽度（N个磁盘）：cdtfull=（[B/（N−1）]> 0），cdtlg=（B%（N−1）>= [N/2]），以及cdtsm=（B%（N−1）[N/2]）<3.2巴士服务时间（S巴士）：总线服务包括通过总线将K个数据块（本地/镜像/冗余）从RAID控制器传输到磁盘设备或从磁盘设备传输到RAID控制器。 数量要传输的数据块的数量取决于请求类型、请求大小和相关的RAID组织，如下所示：对于RAID 0 -1读写操作：⎧W.p.prKR01=⎪102×Bw.p. pW对于RAID5操作，除了读写模式，我们需要区分完整的条带和部分（小或大）条带。因此，我们有：⎧W.p.prKR5= ⎪⎪⎩R5W w.p.pw5我们将“false”解释⎪KP. 哈里森，S。Zertal/Electronic Notes in Theoretical Computer Science 232（2009）513⎪fsmsmfulll全lgR5R01F埃什勒格R5然后，对于每种可能的情况，通过总线传输的RAID 5写入数据（本地和奇偶校验）块的数量（KR5W）可以计算为：⎧Kfif（cdtfull×（1−cdtlg）×（1−cdtsm））⎪⎪⎪⎪如果（cdt）⎪⎪⎨lg×（1−cdt满））KR5W=Ksmif（cdtsm×（1−cdtfull））⎪⎪⎪⎪如果（cdt×cdt），则K+K⎪⎪⎪⎪K+Kif（cdt×cdt）B（N−1）] ×NKlg=N+1Ksm=（（B%（N−1））+ 1）×24公交车延误我们希望计算公交车延误的平均值和方差，因此需要前三个时刻：(i) 要传输的块数（K）：K的第n阶矩就是Kn =Praid01Kn+Praid5Kn其中KR01和KR5的矩分别为nR01=（pr+2npw）Bn.n =prBn+pwcdtfull（1−cdtlg）（1−cdtsm）Kn+（1−cdtfull）cdtlgKn+（1−cdtfull）cdtsmKn+lgsmcdt全cdtlg（Kf+Klg）n+cdt全cdtsm（Kf+Ksm）n(ii) 服务时间（S总线）：巴士服务时间的前三个时刻是：S总线=K×T，S总线=T2×K和S总线=T3×K(iii) 总线队列（Q总线）一阶矩使用Pollaczek-Khinchin公式计算，如公式1所示。二阶矩可以用来评估我们的模型的准确性，并获得为（参见，例如，[5]）：2λ2S λS（二）Q总线=总线+总线Kf=[KK⎪14P. 哈里森，S。Zertal/Electronic Notes in Theoretical Computer Science 232（2009）52（1−ρ总线）2 3（1−ρ总线）P. 哈里森，S。Zertal/Electronic Notes in Theoretical Computer Science 232（2009）5155总线模型验证为了验证我们的模型，我们开发了一个硬件模拟器，代表所有的架构组件和它们执行的功能。该模拟器是事件驱动的，用C语言编写，由3个模块组成：工作负载生成器，逻辑到物理地址转换器和事件（包括IO请求）日志和执行引擎。为了可伸缩性、可移植性和可靠性，执行引擎使用硬件库来表示硬件特征，例如磁盘、连接总线...工作负载生成器和模型共享某些共同的假设：请求地址在存储空间上的均匀分布我们专注于三个参数对总线占用时间的影响：请求类型（读/写），通过改变逻辑请求是读的概率（pr）;逻辑请求大小，通过改变B;和架构配置（即RAID组织），通过考虑排他的RAID 0 - 1，排他的RAID 5或两者的混合物，使用上述模型和事件驱动的模拟器，存储系统由16个FujitsuMAN 3367磁盘连接到40 MB/s宽超SCSI总线。然而，我们首先检查请求大小B和生成的流量（K）之间的关系，它显示了总线争用的重流量源(i) 请求大小与生成的流量对于RAID 5写入，图6确认了请求大小对生成的数据流的重要影响，由于我们考虑的是一个16磁盘存储阵列，组织为RAID 5，因此逻辑请求如果B∈{j+15i，i>0，nj}，则所有的S都是一个整数，其中B∈{j+ 15 i，i≥ 0，j∈[1. 当B∈{j+ 15 i，i ≥ 0，j ∈ [8] }时，得到大条纹.14]}。 所产生的透射率在小条纹阶段期间随着B增加，在大条纹阶段期间随着B增加而减小（因为预读取IO的数量减少），并最终达到完整条带的最低值。图6显示了独占写入请求流（pr= 0）和具有相等比例的读取和写入的混合请求流（pr= 0）的这种效果。5），这与排他读取流（PR= 1）形成对比，对于排他读取流，所生成的传输流在逻辑请求大小上是线性的。对于RAID0-1写入，生成的传输速率与逻辑请求大小B成正比，系数为2。考虑图7中RAID 0 -1和RAID 5比例相等的Multi-RAID存储系统，我们可以看到在排他小写入模式下生成的数据量激增。在这种情况下，产生的总线传输由双RAID 0 -1逻辑请求和四RAID 5逻辑请求组成。(ii) 请求类型为了分析读和写对总线访问行为的影响，我们改变请求是读的概率pr，从0（对于独占读工作负载）到1（对于独占写工作负载），包括0。5、平衡工作量。我们可以在图8中看到RAID 0 -1的变化，模型和16P. 哈里森，S。Zertal/Electronic Notes in Theoretical Computer Science 232（2009）5pr=0pr=0.5pr=1产生的公交车流量（街区）120 120100 10080 8060 6040 4020 2000 5 10 15 20 25 30 35 4045逻辑请求大小（块）00 5 10 15 20 25 30 35 40 45逻辑请求大小（块）图 6.在RAID 5上生成的传输块见图7。Multi-RAID上生成的传输块模拟结果显示出良好的一致性，并表明写入时间随写入比例的增加而增加，这类RAID的传输时间增加了一倍。这也适用于RAID 5，如图9所示，其中对于小的（B= 1）写请求，传输率乘以40.08 0.10.070.060.080.050.060.040.030.040.020.020.010200 300 400 500 600 700 800 9001000到达率（log req/s）01002003004005006007008009001000到达率（log req/s）见图8。请求类型对RAID 0-1的影响（B= 1）见图9。请求类型对RAID 5的影响（B= 1）(iii) 请求大小我们观察了总线在不同请求大小下的行为，从1个块（4KB）到4个块，然后是RAID 0 -1的8个块。图10显示了逻辑请求大小对生成的总线流量的影响，从而对总线排队时间的影响，分析模型和仿真相互验证，显示出良好的一致性。我们选择独占读模式来隔离任何写操作对大小的影响。 我们可以看到，对于8个块的请求，在相对较低的到达率下，等待时间迅速上升（在150 req/s时达到9ms）。RAID5读数与RAID0-1相似;因此图10代表了这两种组织。(iv) 架构配置我们注意到，在独占RAID0-1存储系统、独占RAID5存储系统以及两者以相等比例混合的Multi-RAID中，相同的逻辑请求流产生不同的传输强度。图11清楚地显示了架构配置对生成的事务的影响以及模型和仿真结果的一致性pr=0pr=0.5pr=1Mod_pr1Sim_pr1Mod_pr05Sim_pr05Mod_pr0Sim_pr0Mod_pr1Sim_pr1Mod_pr05Sim_pr05Mod_pr0Sim_pr0产生的公交车流量（街区）平均总线接通时间（ms）平均总线接通时间（ms）P. 哈里森，S。Zertal/Electronic Notes in Theoretical Computer Science 232（2009）517Mod_B1Sim_B1Mod_B4Sim_B4Mod_B8Sim_B8平均总线接通时间（ms）0.2 0.30.250.150.20.1 0.150.10.050.05001002003004005006007008009001000到达率（log req/s）01002003004005006007008009001000到达率（log req/s）见图10。请求大小影响（RAID 0 -1）6结论见图11。架构配置对Q总线本文在层次化多磁盘存储系统模型的基础上增加了一个新的层次：磁盘连接组件模型，并将其与磁盘阵列模型集成在一起。这是我们的智能性能优化虚拟化数据存储系统（IPODS）项目的目标之一。该模型显示出良好的精度与模拟在初步的实验相比需要进一步验证，其中我们考虑具有非均匀地址的请求到达流，以及响应时间的更高时刻和更大的文件大小。然后，应在受控环境中根据实际RAID系统监控的数据验证模型。同样，在更大的计算费用，响应时间分布函数本身可以得到从Pollaczek-Khinchin结果拉普拉斯变换，使用数值逆变器。这可能对验证更加敏感，特别是在尾部。扩展我们的存储体系结构的磁盘矩阵非常大的系统，可以实现使用这项工作，通过添加新的总线组件和相关的连接在模拟器和扩展，ING我们的模型到一个多总线版本使用M/G/N队列。 最后，对RAID系统的控制组件进行建模，包括请求调度机制和数据缓存策略，这些都对网络存储系统的性能有很大的影响。引用[1] S. Chen和D.托斯利raid体系结构的性能评估。IEEE Transactions on Computers，45（10），1996年10月。[2] G.吉布森·D A. Patterson和R. H.卡茨廉价磁盘冗余阵列（RAID）的一个案例。SIGMOD会议记录，1988年6月。[3] J. Xu E. Varki，A. Merchant和X.邱磁盘阵列的综合性能模型。计算机和电信系统建模、分析和仿真国际研讨会（MASCOTS），2003年。[4] Michael J.弗林计算机体系结构流水线和并行处理器设计。琼斯和巴蒂特出版社，1995年。[5] P.G. 哈里森和 S. 泽塔尔排队RAID模型系统与 等待时间最长。业绩评价，2007年。[6] 黄志福 建模基础知识。 John Wiley出版社，1996年。[7] C Staelin J. Wilkes，R. Golding和T.苏利文hp autoRAID分层存储系统。ACM transactions on Computersystems，14，Feb 1996.Mod_RAID01Sim_RAID01Mod_RAID5Sim_RAID5Mod_R01/R5Sim_R01/R5平均总线接通时间（ms）18P. 哈里森，S。Zertal/Electronic Notes in Theoretical Computer Science 232（2009）5[8] E.K. Lee和R.H.卡茨磁盘阵列性能分析模型。在Proc.ACM SIGMETRICS，1993年5月。[9] G. A.阿尔瓦雷斯M. Uysal和A. 商家 现代磁盘阵列的模块化分析吞吐量模型。2001年8月，计算机和电信系统建模、分析和仿真国际研讨会论文集[10] A. Merchant和PS Yu.镜像磁盘中的分析模型或重建时间。业绩评价，1994年5月20日。[11]Sangsoo Park和Heonshik Shin。 为实时应用程序建立严格的磁盘性能模型。实时和嵌入式计算系统和应用（RTCSA），2003年。[12] B.O. Shubert和H. J·拉森工程科学中的概率模型约翰·威利出版社，1979年。[13] A. van de liefvoort和N.萨勃拉曼尼亚具有一般服务时间的单总线多处理机系统IEEE Transactions onComputers，42，Mar 1993.[14] S. Zertal和PG哈里森分区磁盘阵列的多RAID磁盘阵列模型。高性能计算和仿真，2007年。[15] S. Zertal和PG哈里森非线性寻道距离，可在多RAID存储系统中实现分区磁盘寻道时间的最佳精度。高性能计算和仿真，2008年。