对很少读取的数据的低成本存储

摘要

描述了用于写入一次但很少读取的数据的低成本存储。在一实施例中，一存储设备包括经互连结构连接到服务器的多个硬盘驱动器。该存储设备包括仅能冷却所述硬盘驱动器中的第一子集的冷却系统以及仅能对所述硬盘驱动器中的第二子集供电的供电系统，并且在一些示例中，所述互连结构可仅能对所述硬盘驱动器中的第三子集提供完全带宽。每个子集可仅包括硬盘驱动器的一小部分。可用软件实现的一控制机制被提供，该控制机制控制在任何时间哪些硬盘驱动器是活动的，以便由冷却和供电系统以及互连结构所设置的约束不被违反。

说明书

背景

存在大量的向数据存储设备写入一次然后仅被很少读取的数据，且示例包 括电子邮件的存档存储以及数据的次级地理分布的副本。在该数据被读取的罕 见场合中，要求及时访问，因此使用通常用于冷存储的基于磁带的解决方案(其 中机械臂从库拿取磁带并将它们插入磁带驱动器，在磁带驱动器中磁带被机械 地卷绕到正确的位置)由于高访问延迟而是不合适的。磁带也可能受到环境条 件(如湿度)的影响，因此耐用性可能有限。提供低延迟访问的现有的存储方 案基于物理硬盘和固态驱动器；然而这些具有高功耗且还购买昂贵。

以下描述的各实施例不限于解决已知存储方案的缺点中的任何或全部缺 点的实现。

概述

下面呈现了本发明的简要概述，以便向读者提供基本理解。本概述不是本 公开的穷尽概览，并且不标识本发明的关键/重要元素或描述本说明书的范围。 其唯一的目的是以简化形式呈现此处所公开的精选概念，作为稍后呈现的更详 细的描述的序言。

描述了用于写入一次但很少读取的数据的低成本存储。在一实施例中，一 存储设备包括经互连结构连接到服务器的多个硬盘驱动器。该存储设备包括仅 能冷却所述硬盘驱动器中的第一子集的冷却系统以及仅能对所述硬盘驱动器 中的第二子集供电的供电系统，并且在一些示例中，所述互连结构可仅能对所 述硬盘驱动器中的第三子集提供完全带宽。每个子集可仅包括硬盘驱动器的一 小部分。可用软件实现的一控制机制被提供，该控制机制控制在任何时间哪些 硬盘驱动器是活动的，以便由冷却和供电系统以及互连结构所设置的约束不被 违反。

通过结合附图参考以下详细描述，可易于领会并更好地理解许多附带特 征。

附图简述

根据附图阅读以下具体实施方式，将更好地理解本发明，在附图中：

图1是示例存储设备的示意图；

图2示出示例存储设备的另一示意图；

图3示出第一示例互连结构的示意图；

图4示出第二示例互连结构的示意图；

图5是控制对HDD的访问的示例方法的流程图；

图6是示出存储设备内的域的示意图；

图7是示出实现最大不相交性的示例组构造的示意图；

图8是从上面示出存储设备内HDD的表示的示意图；

图9是在两个服务器情形中从上面示出存储设备内HDD的表示的示意图；

图10示出将数据写到存储设备的示例方法的流程图；

图11示出例示出图10所示的方法中的两种方法之间的差异的示意图；

图12示出在存储设备内调度读取操作的示例方法的流程图；

图13示出存储设备的示例调度时间线；

图14是从存储设备读取数据的另一示例方法的流程图；以及

图15例示出可在其中实现本文所述的控制HDD的方法的各实施例的示例 性的基于计算的设备。

在各个附图中使用相同的附图标记来指代相同的部件。

详细描述

下面结合附图提供的详细描述旨在作为本发明示例的描述，并不旨在表示 可以构建或使用本发明示例的唯一形式。本描述阐述了本发明示例的功能，以 及用于构建和操作本发明示例的步骤的序列。然而，可以通过不同的示例来实 现相同或等效功能和序列。

图1是示例存储设备100的示意图。存储设备100可以是机架规模的设备 (具有标准机架形状因子)或可具有一替代的形状因子。存储设备包括大量硬 盘驱动器(HDD)102(例如超过1000个HDD)以及服务器104。每个HDD102 包括在活动时(即在数据被读取或写入时)高速旋转的盘片(或碟)。为了降 低功耗，盘片可被减速旋转(即停止)；但是存在与加速旋转盘片相关联的延 迟且在盘片减速旋转的同时数据不能被读取或写入。出于下面的描述的目的， 假设该延迟为大约10秒，但是将理解该延迟可以比此更短或更长。

在设备内提供将HDD102与服务器104互连的互连结构106。电源由供电 系统108提供，尽管在图1中被示为单个块，但是供电系统可遍及存储设备100 分布。冷却(用于HDD102)由冷却系统110提供，冷却系统可以是例如使用 一个或多个风扇来推动(推或拉)HDD周围的空气的强制风冷系统。

在存储设备100中，供电系统108和冷却系统110都是显著供应不足的， 使得存储设备100不能支持所有HDD102同时活动(即伴随着它们的盘片旋 转)，相反，供电系统108和冷却系统110仅可支持HDD102的一小部分(如 10％或更少，在一个示例中是8.3％)同时活动。如果存储设备100中的全部 HDD102要同时开始旋转它们的盘片，则将导致存储设备100的故障，因此在 存储设备100内提供了一种控制在任一时候活动的HDD102的数量的机制。该 机制可由服务器104上运行的软件(如调度程序)和/或存储设备100内的控制 逻辑112来提供。

存储设备100内供电系统108和冷却系统110的供应不足(即电源系统和 冷却系统的特性)对可在任何时间活动的HDD102的数量设置了约束，且这些 约束可被称为“硬性约束”，因为如果它们被违反，则存储设备100将(或非常 可能)出故障。取决于存储设备100的设计，可能存在一个或多个其他硬性约 束和/或一个或多个软性约束。软性约束的示例可包括带宽约束(例如从外部网 络到服务器104的接口的最大带宽或互连结构106内的带宽约束)和振动约束。 软性约束的振动不造成存储设备100的故障(或非常可能故障)，但是相反将 劣化性能(如超出带宽约束将减慢对设备的访问)和/或可能造成更长期的损坏 (例如超出振动约束短期不可能造成存储设备的故障，超过较长的时间段，造 成可能最终导致存储设备100的故障的损坏)。这些约束(例如功率和冷却约 束以及可被使用的任何其他约束，诸如由互连结构造成的带宽约束)由服务器 104上运行的软件和/或控制逻辑112来管理。

尽管图1示出服务器104位于存储设备100内，但是在一些示例中，服务 器104可位于存储设备100之外，且在一些示例中，服务器104可位于存储设 备100的远程。此外，尽管图1示出单个服务器104，但是将理解存储设备100 可包括一个以上的服务器(例如为了冗余性目的)，并且在存在多个服务器的 情况下，所有HDD102可被连接到单个服务器104(在服务器故障的情况下 HDD备切换到第二服务器)或者HDD102可被划分成连接到一个服务器的一 子集以及连接到另一服务器的另一(不相交)子集(其中，这些子集可以是固 定的或可随时间动态改变)。在一些示例中，可能有一个以上的互连结构106 以及一个以上的独立服务器104，其中不同的互连结构106将HDD102连接到 多个服务器或连接到不同服务器。这提供了对服务器和/或互连结构故障的应变 能力。

HDD102在此被描述为活动的(即使得它们的盘片旋转)或不活动的(即 它们的盘片不旋转)，不活动的在此也被称为HDD处于待机状态，因为HDD 内的电子设备仍然通电。将理解HDD102可具有两个以上的状态(活动的/不 活动的)，诸如处于从不活动到活动的转换过程中(即盘片正在加速旋转的情 况)、处于从活动到不活动的转换过程中(即盘片正在减速旋转的情况)、完 全关断(即不对电子设备供电)、以及各种其他低功率状态。为了下文描述的 目的，活动的状态被认为包括盘片正在旋转且数据正被读取/写入的状态以及盘 片正在旋转且数据不在正被读取/写入的状态(这可称为“空闲”状态)两者，因 为这两个状态都消耗类似的功率量(如8W)。加速旋转状态在一短时间段上 消耗更大的功率量(如10秒消耗24W)，且可被认为是活动的状态的一部分 (例如出于功率核算的目的)或单独被考虑。在一示例实现中，每个HDD的 状态可按三种状态之一来被跟踪：待机(或不活动的)、加速旋转以及活动的。 将理解，在其他示例中，额外的HDD状态也可被考虑(如减速旋转的第四状 态也可被跟踪，其中这花费非同寻常的时间量来完成)。

图2示出示例存储设备100的另一示意图。该示图示出HDD102的3D安 排，其中每个HDD102可由其(x,y,z)坐标来标识。将理解，HDD102可不 位于实际存储设备100内的规则网格中；但是，如图2所示的这种表示出于下 文讨论的目的而提供了HDD102的逻辑表示。

作为设备设计的结果，存储设备100内的HDD102可被安排成由功率约 束链接的不相交的(或不重叠的)子集，在一示例中，HDD102可被安排在托 盘202中，其中托盘202中的HDD102具有相同的x和z值(以及变化的y值)， 一个托盘在图2中被示为阴影单元格。该功率约束由可被提供给托盘的最大功 率量来设置。在一示例中，该功率约束可指定在单个托盘内仅两个HDD可以 是活动的，且在一些示例中，该约束可被进一步限制为这两个活动的HDD中 仅一个可处于加速旋转状态。尽管图2示出存储设备100具有35个托盘，但 是将理解这仅仅是作为示例，且存储设备100可包括任何数量的托盘。在一示 例中，存储设备可包括72个托盘，且每个托盘可包括16个HDD。

存储设备100内的HDD102可被进一步安排成由冷却约束链接的不相交 的子集(例如它们位于冷却系统110内的相同气流通道中)。在一示例中，HDD 102可被安排成列204，其中一列中的HDD具有相同的x和y值(以及变化的 z值)，一个列在图2中被示为阴影单元格。在一示例中，冷却系统110可迫 使空气进入存储设备100的前面，向上通过列以及在存储设备100的后面排出 (如箭头206所指示的那样)，因此可看到列204中的所有HDD由一冷却约 束链接，因为它们位于通过设备的相同冷却通道上(即同一垂直气流中)。在 一示例中，该冷却约束可指定在单个列中仅一个HDD可以是活动的。尽管图2 示出存储设备100具有35个列，但是将理解这仅仅是作为示例，且存储设备 100可包括任何数量的列。在一示例中，存储设备可包括96个列(每个列可包 括12个HDD)。

如从图2可见，列和托盘并非不相交，在托盘202和列204之间有一个 HDD的重叠。两个约束因此不是独立的。此外，所述两个约束可对在任何时候 在存储设备100中可以是活动的HDD的总数设置不同的上限，在这一情况下 两个上限中的较小值被使用。例如，在包括被安排成每托盘16个HDD以及每 列12个HDD的1152HDD的系统中，功率约束将任何时候活动的HDD的最 大数量设置为144(每托盘2个，共72个托盘)，而冷却约束将任何时候活动 的HDD的最大数量设置为96(每列1个，共96个列)，因此存储设备中任何 时候活动的HDD的数量的总限制是96。

图3示出第一示例互连结构300的示意图。该示例示出用于包括两个服务 器302的存储设备的互连结构，其中第二服务器连接到(或可连接到)所有的 HDD304，例如为了在服务器故障的情况下的冗余性。然而，将理解，对于单 个服务器方案，由虚线轮廓线306环绕的元素可被省略。该示例互连结构300 使用PCIexpress(PCIe)且包括物理上分布在存储设备100内的多个组件 308-314，以便通过用PCB迹线替代线缆来减少线缆的数量(以减少人们错误 连接的可能性)，减少那些PCB迹线的长度(因为PCI信号随着它沿迹线行进 而劣化)，减少所使用的任何线缆的长度(这降低了成本)，以及延长(或优 化)服务器302和HDD304之间的可工作距离。通过在存储设备内对组件的分 布来延长该可工作距离，因为每个PCIe组件修复信号。

如图3中所示，服务器302连接到服务器交换机308，每个服务器有一个 服务器交换机。每个服务器交换机308连接到多个背板交换机310(表示为 BS_n)。在图3中所示的示例中，有6个背板交换机310连接到服务器交换机 308，且在一实现中，该连接(服务器交换机308到每个背板交换机310)可以 是仅有的使用PCB迹线之外的线缆的连接。背板交换机310连接到多个托盘交 换机312(表示为TS_n)，在所示示例中，有12个托盘交换机连接到背板交换 机310。可看到在有两个服务器304的情况下，在互连结构的托盘交换机层没 有复制，每个托盘交换机312连接到两个背板交换机310：连接到第一服务器 的一个背板交换机以及连接到第二服务器的一个背板交换机。由于(对于每个 服务器302)有6个背板交换机310，在图3的示例中总计有72的托盘交换机 312。在一托盘中，有两个SATA控制器314(表示为SC_n)，它们将托盘交换 器312连接到各个硬盘304。如图3中所示，每个SATA控制器314连接到托 盘中一半的HDD。由于在图3中所示的示例中有72个托盘，因此有144个SATA 控制器连接到总计1152个HDD，其中每个SATA控制器连接到8个HDD。

如可参考图3来解释的，该互连结构可提供带宽约束；但是在一些情况下， 在确定哪些HDD可活动的时候，该带宽约束无需被明确考虑，例如如果功率 和冷却约束被满足，则带宽约束也总是被满足。

在图3中所示的示例中，每个HDD304可具有到SATA控制器314的1Gb/s 链接，使得互连结构中该层处的总容量为1152Gb/s。在向上的下一层，每个 SATA控制器314可具有到托盘交换机312的4Gb/s链接，使得互连结构中该 层处的总容量为576Gb/s(前一层的一半)。每个托盘交换机312于是可具有 到背板交换机310的8Gb/s链接，使得互连结构中该层处的总容量为576Gb/s。 每个背板交换机310具有到服务器交换机308的16GB/s链接，使得互连结构 中该层处的总容量为192Gb/s(前一层的三分之一)，且每个服务器交换机308 具有到服务器302的32Gb/s链接。替代地，每个托盘交换机312可具有到背 板交换机310的4GB/s链接(使得该层的总容量仅为288Gb/s或前一层的一 半)，且每个背板交换机310可具有到服务器交换机308的8GB/s链接(使得 该层的总容量仅为96Gb/s，是前一层的三分之一)。这些示例都清楚地说明如 果冷却和功率约束允许活动的全部96个HDD都是活动的，则互连结构300内 没有足够的带宽来对它们全部进行读取和/或写入。因此，在该示例中，在确定 在任何时候哪些HDD活动时，(作为供应不足的互连结构的结果)带宽约束 也可被考虑。如上所述，带宽约束被认为是软性约束，因为它造成拥塞和延迟 且不导致存储设备的故常。

图4示出第二示例互连结构400的示意图，且在该示例中仅示出单个服务 器402；但是该结构可被修改来用于两个服务器(例如通过将最上层多路复用 器中的每一个连接到两个服务器)。该示例互连结构400包括SATA多路复用 器404树，该树连接到服务器402上提供的少数SATA端口且使用SATA内的 热插拔基础设施。在该示例中，该树为6层深，最上层处有两个多路复用器404， 而最底层处有486个多路复用器(其中每个多路复用器连接到多个HDD406)。 将理解，为了清楚起见，并非所有多路复用器404或HDD406都被示于图4 中。在该SATA实现中，在任何时候，仅有一条活动路线通过该树。不活动的 那些HDD在从活动的转换到不活动的状态时被有效地热拔掉，且它们不再被 服务器402可见(或与服务402通信)。这与图3中所示的PCIe方法(互连 结构300)相对照，在图3中存在到每个HDD的直接连接且这使得HDD预先 加电(即对一组HDD加电，同时从另一组HDD读出或向其写入)，而使用图 4中所示的互连结构400是不可能的。尽管图4示出使用SATA多路复用器404， 但是在进一步的示例互连结构中，SATA倍增器可替代地被使用(然而这将增 加互连结构的成本，并且由于SATA倍增器不能被串行连接(daisy-chained)， 它将限制可被连接的HDD的数量)。

如上所述，本文所述(且示于图1和2中)的存储设备100内的电源和冷 却系统是极其供应不足的，使得所有HDD不能被同时加速旋转(即存在不足 的功率和不足的冷却两者)。然而，在标准计算设备中，在启动时HDD被自 动加速旋转且各种进程可能间歇地加速旋转HDD用于其他目的(例如在扫描 文件来查找病毒时、在索引文件以允许在文件内搜索时、在检查盘是否被加密 时、在检查盘故障预测计数器时、在检查盘是否以传统方式已被格式化时等)。 为了在本文所述的存储设备中防止这样，可对每个HDD在服务器内存储一访 问(或“禁止访问”)标志，然后服务器上运行的软件(如操作系统)被修改使 得在一HDD被标记为“禁止访问”时该HDD上的所有操作都失败。这示于图5 中的示例流程图500中。

图5是控制对HDD的访问的示例方法的流程图。当对一HDD的IO请求 被发出时，执行检察以查看该HDD的“禁止访问”标志是否被置位(框502)， 且如果该标志被置位(框502中的“是”)，则该IO请求失败(框504)。然而， 如果该标志未被置位(框502中的“否”)，则该IO请求被正常处理(框506)。 在启动时，所有非引导HDD可将其标志置位(指示出“禁止访问”)，随后， 当HDD在非活动的和活动的状态之间切换时，HDD可将它们的标志复位/置位。 取决于实现，该标志可被设为1或0来指示“禁止访问”。此外，HDD驱动程序 可被修改以改变它在引导序列期间如何发现HDD。这样的经修改的驱动程序被 安排成顺序地对每个HDD加速旋转、探测、标识以及然后减速旋转。现有的 驱动程序可执行HDD的交错式加速旋转，但在加速旋转下一HDD之前不会减 速旋转一个HDD。

如上所述，功率和冷却(以及可能其他)约束限制了在任何时候在存储设 备内可活动的HDD的数量，服务器上运行的软件和/或控制逻辑被用来控制哪 些HDD是活动的(以及在访问标志被使用的情况下设置对应的访问标志)。 返回图2中所示的示例存储设备，存储设备内的HDD可被表示为单元格的规 则网格，每个单元格对应于一HDD102，且每个HDD由一(x,y,z)坐标来引 用。如上所述，冷却约束在列204内起作用，且这可被称为“冷却域”，其中具 有相同x和y坐标的两个HDD共享一冷却域。类似地，功率约束在一托盘内 水平地起作用，且这可被称为“功率域”，其中具有相同x和y坐标的两个HDD 共享一功率域。术语“片”可被使用来指代存储设备中功率和冷却域是独立的最 小部分，具有相同x坐标的HDD位于同一片中，而来自两个不同片的HDD不 能共享功率或冷却域。图6是示出存储设备600内的域的另一示意图，且在该 示例中，片602与存储设备的其余部分分开地被示出。图6还示出片602中HDD 608的功率域604和冷却域606。

在各种示例中，存储设备内的HDD可被逻辑地划分成非重叠的组，其中 每个组包括全部可同时活动且不违反功率和冷却约束的多个HDD。在这样的示 例中，每个HDD是单个组的成员，且将理解某一组不包括可同时活动的全部 HDD(例如多个组可同时是活动的)。在一示例实现中，HDD可被划分成逻 辑组，使得每个组具有相同数量的HDD(例如16个HDD)，且一个组的HDD 可被一起冷却和通电(即它们不违反功率或冷却约束)。在一些示例中，也可 能存在带宽(软性)约束，即一个组的HDD在互连结构内没有带宽冲突，除 非它们使树(例如图3中所示的PCIe树)的根部饱和。

组中的一些将是互斥的，因为它们的HDD的域(冷却和/或功率)重叠且 这些组可被描述为冲突的。不冲突的组可被描述为不相交的且通过对HDD分 组来使HDD的不相交性最大化(即，使一个组内任一HDD不处于与另一组中 的HDD相同的冷却或功率域中的可能性最大化)，随机选择的两个组可同时 活动的可能性增加，且存储设备的吞吐量增加。将组不相交性最大化的一示例 布局是这样的，其中两个组被安排成要么不相交要么完全冲突(即第一组的每 个HDD处于第二组的HDD的冷却和功率域中)。

图7示出实现最大不相交性的示例组构造(每组16个HDD)。图7示出 两个组702、704，每个组中的HDD沿对角线放置以避免组内冲突。可清楚地 看到第一组702中的每个HDD处于第二组704中的HDD的功率域和冷却域两 者中。取第一组702中的示例HDD706，它位于第二组704中的一个HDD708 的功率域中以及第二组中第二HDD710的冷却域中。由于每组包含比单片中的 功率域更多的HDD(与16个HDD相比有12个功率域)(其中在该示例中， 功率域比冷却域少，因此是限制因素)，每个组包括来自两个片712、714的 HDD，该示例中，所述两片在存储设备内彼此邻近。使用图7中所示的示例安 排，就可能构建16个HDD一组的72个完整的组。每组与同一片中的11个组 完全冲突，且可与剩余60个组中的任何组同时地被加速旋转。

如果上述的组布置策略被使用，则标识联合的组(即冲突的组)是一种简 单的操作：当(且仅当)两个组位于相同片时它们共享功率和冷却域。组的行 可被定义为包含与该组相联合的所有组的等价类，且这被示于图8中。图8是 从上面示出存储设备内HDD的表示的示意图。每个单元格802表示一冷却域， 而每一排804表示一片。每一行通过阴影来示出，且由完全重叠功率和冷却域 的16个HDD一组的12个组组成。每一行具有的特性是：来自同一行的组应 被顺序地调度，而来自任两行的组可同时加速旋转并活动(即执行IO)。参考 图8中所示的具体示例，任一行的每个组可与其他行的任何组同时加速旋转， 而6行中的任两行可同时活动。

在包括同时活动的两个服务器(而不是在服务器故障时在服务器之间切 换)的存储设备中，组可被指派给服务器以便防止服务器间调度冲突，且如图 9中所示，可使用片与服务器之间的映射。使用从片到服务器的映射是有益的， 因为片在冷却/功率域方面是独立的，且如图9中所示，行可被重新安排使得任 一片将属于唯一一个服务器。比较图8和9可看到，在图9的多服务器情形中， 行1从第一片绕到第三片(而不是第六片)，以便前三片可被映射到第一服务 器。类似地，行4从第四片绕到第六片(而不是第三片)。

尽管上述的示例示出每组16个HDD的组，但是在其他示例中，可使用不 同大小的组(即不同数量的HDD)。在一些示例中，组的大小可被选择使得它 均匀地划分成同时活动的盘的最大数量(即其因数)(例如在本文所述的许多 示例中是96的因数)，也即是说使得整数数量的组可同时活动，因为这提高 了效率。与仅加速旋转完整的组相比，对一组的一部分(例如半组)加速旋转 是较不有效的且控制起来更复杂，因为任何IO将要求整个组都是活动的。较 小的组大小(即包括较小数量的HDD的组)提高了调度性能，因为组的数量 更大且调度器有更多的自由度来选择下次调度哪一组(见下文参考图12和13 对调度的讨论)。然而，小的组提供了每组(且因此每操作)较少的吞吐量， 且在纠删编码和分条(如下文所述)被使用的情况下导致较大的开销。对于具 有上述架构(72个托盘，每个托盘包括16个HDD，使得总计1152个HDD) 的一个服务器的方案(即在任何时候仅一个服务器在运行)，合理的组大小可 包括16个HDD(在任何时候有6个活动的组)、24个HDD(在任何时候有4 个活动的组)、32个HDD(3个活动的组)或48个HDD(2个活动的组)。 对于两个服务器的情形(同样具有每托盘16个HDD的72个托盘的架构)， 一组中可有16个HDD(每服务器3个旋转组)或24个HDD(每服务器2个 组)。将理解，对于其他架构，可使用不同的组大小。

图10示出将数据写到如本文所述的存储设备的示例方法的流程图。第一 示例方法1000使用如上所述的HDD的组的概念。如方法1000中所示，要被 写到HDD的数据突发段(在被提交给服务器之前)被划分成部分，这些部分 可被称为“区段”(extent)，这些区段由服务器接收(框1002)。区段可以是 可变大小的(例如在由最小和最大大小定义的范围内)，且每个区段大小可以 是例如1GB(或更大)。纠错然后被添加到每个区段(框1004)，且可以使用 任何纠错技术。该纠错可由服务器或外部方添加。在一示例中，纠删编码可被 使用，而在其他示例中，诸如奇偶校验之类的其他方法可被使用。每个区段然 后被写到来自单个组的HDD(框1006)。这意味着在读取该区段时，保证整 个区段被同时读取且将不必在读取某一区段的过程中在组之间切换(即，通过 将第一组转换成不活动的以及加速旋转第二组中的HDD的盘片)(这会增加 显著延迟)。

图10还示出将数据写到本文所述的存储设备的更详细的示例方法1010。 在该方法1010中，单个区段被划分成固定大小的条(框1012)，每个条然后 被划分成固定数量k个块(框1014)，其中k是整数。取决于所使用的纠错技 术，对于每个条，j个块可被添加以编码冗余信息(框1016)，其中j是整数， 使得每个条现在包括(k+j)个块。来自每个条的一块然后被写到来自同一组的 (k+j)个HDD中不同的一个HDD(框1018)。以此方式，跨所有条的全部 块都被写到相同的(k+j)个HDD，且如第一方法1000中那样，每个区段(或 部分)被写到来自单个组的HDD。

该第二方法1010可按照“条堆栈”来被替代地描述。添加了j个冗余块(框 1016中)之后，每个条中具有相同偏移的块被组装成条堆栈(框1020)。例 如，如果有m个条且第一条包括表示为B_1,1,B_1,2,…,B_1,(k+j)的(k+j)个块以及第 m个条包括表示为B_m,1,B_m,2,…,B_m,(k+j)的k+j)个块，则一个条堆栈包括m个块 B_1,1,B_2,1,…,B_m,1，而另一条堆栈包括块B_1,2,B_2,2,…,B_m,2等。如可见，每个条堆 栈包括m个块，其中第x个条堆栈包括来自m个条中每个条的第x个块。每个 条堆栈然后被写到一组内的一不同HDD(框1022)。

图10还示出将数据写到本文所述的存储设备的第三示例方法1030。尽管 第二示例方法1010可被称为“分条”，但是该第三示例方法1030可被称为“分 段”，且该方法1030不使用组的概念(不同于方法1000和1010)。在该示例 方法1030中，区段被划分成n个分段(框1032)，且p个冗余分段被添加(框 1034)。该区段内的每个分段然后被存储在一不同的HDD上(框1036)，即 一个分段在(n+p)个HDD的一个上。在该示例中，(n+p)个HDD不必属 于同一组，但是分段的大小被选择使得从一HDD读取该分段将花费至少10秒 (即至少为加速旋转HDD要花费的时间)且存储分段i+1的HDD应与存储分 段i的HDD同时可旋转。这意味着当读取已使用方法1030被写入的某一区段 时，存储来自一区段的分段1的HDD最初是活动的，且并行地，存储来自同 一区段的分段2的HDD正在加速旋转。当分段2被读取时，存储分段1的HDD 减速旋转(即盘片不再被驱动)，而存储分段3的HDD加速旋转，等等。

图11示出分条(如方法1010中所示)与分段(如方法1030中所示)相 比的示意图。该示图示出了k＝1、j＝1、n＝1以及p＝1的情形。对于(控制对HDD 的写的)调度器而言分段比分条更灵活，因为约束是存储两个连续分段的HDD 必须是一起可旋转的(而不是所有HDD都不得不属于一个组)。然而，分段 的吞吐量被限制到一个HDD的带宽，调度可能更复杂，因为可能存在许多冲 突的并行操作以使得存储设备带宽饱和，且它要求DRAM与最大区段大小成比 例。相反，分条提供了高吞吐量，且调度较不复杂，因为它近乎无视于功率和 冷却约束(因为这些是由组定义来顾及的)；但是，对于调度器来说存在较少 的灵活性，因为存储该区段的所有HDD必须来自一个组(且因此一起可旋转)。

当在前两个示例方法1000、1010中把数据写到各组HDD时(如框1006 和1018那样)，数据(即区段)可被公平地散布在所有组中(“平均填充”)或 一个组可在填充下一组之前被填充数据(“顺序填充”)。在一个实现中，各组 的平均填充被使用。平均填充导致HDD的均衡加载(这使得维护更容易)且 在HDD故障的情况下有较少的数据要重建(因为HDD不可能完全填充数据)； 然而，当存储设备轻度加载时(即每个组存储少量数据)，可能有(比顺序填 充)更低的吞吐量，因为每个活动的HDD有更少的IO。相反，顺序填充在轻 度加载的存储设备中提供了每HDD更多的IO(因为数据将被集中在少数量的 组中)，但是一些HDD可能非常长的时间段是不活动的，且这可能影响HDD 可靠性。

与控制对HDD的写一样，服务器内的调度器控制HDD上的读取操作。图 12示出在存储设备内调度读取操作的示例方法1200的流程图。该方法是用组 的概念，因此可结合用于写数据的方法1000和1010之一来被使用。在接收到 读取操作的突发段时(框1202)，调度器将操作排序成在同一组HDD上操作 的集合(框1204)，然后以最大化吞吐量的顺序来调度操作集合(框1206) (即通过最小化组之间的切换)。在一些示例中，操作可被标记有优先级，在 该情况中，操作的集合可基于吞吐量和优先级两者来被调度(框1206中)。

为了最大化吞吐量，操作的集合可被排序(框1206中)以允许各组被加 速旋转，同时尝试维持互连结构的吞吐量。例如，如果花费10秒来加速旋转 一HDD，则操作的每个集合可被安排成提供至少10秒的IO操作，以便在某一 集合的操作正被执行的同时另一组可被加速旋转。例如，在t＝t₁与t＝t₁+10之间， 操作在组A上被执行且组B中的HDD正加速旋转，然后在t＝t₁+10与t＝t₁+20 之间，操作在组B上被执行且组C中的HDD正加速旋转，等等。只要在互连 结构中有足够的带宽(即至少带宽约束不被违反)，则在不相交的组上操作的 操作的集合可并行地被调度。例如，在t＝t₁与t＝t₁+10之间，操作在组A和D 上被执行且组B和E中的HDD正加速旋转，然后在t＝t₁+10与t＝t₁+20之间， 操作在组B和E上被执行且组C和F中的HDD正加速旋转，等等，其中组A 和D、B和E以及C和F是不相交的。由于带宽约束不是硬性约束，因此在一 些示例中，供应不足的带宽可在各组之间被共享，使得每个组经受到一带宽限 制。例如，如果有各自使用18GB/s的带宽的两个操作且总可用带宽仅为32 Gb/s，则这两个操作可同时地以16Gb/s来被服务，而不是以18Gb/s的完整带 宽来仅仅服务于单个操作。

返回参考图8和9，如果各组HDD被安排成行，则调度器可能意识到这些 行以及哪些行可执行同时的IO(如上所述)。因此，调度器(在框1206中) 可基于这种行知识来对操作的集合分组，且下面的准则也可被使用：来自同一 行的两个组的IO分隔至少10秒，所述至少10秒相当于来自属于其他行的组 的IO。这使得来自同一行的第二组能够在该分隔期间被加速旋转。将理解，尽 管加速旋转时间被假设为10秒，但是如果加速旋转时间是更长或更短的时间 段，则可应用相同的原理。在调度组时(在框1206中)，调度器可例如使用 花费不多的贪婪算法来确定下一次调度哪个组以便最小化空闲时间。

对操作的调度(在框1206中)可在读取操作的突发段(如框1202中接收 到的)内应用，或者替代地一窗口(可按照操作的时间或数量来定义)可被使 用来定义读取操作的队列中有多少操作可被考虑来在同一时间进行重新调都 (例如100或1000个操作的窗口)。在这样的窗口被使用的情况下，即使读 取操作不是在突发段中被接收(即框1202被省略)，图12的方法也可被应用， 且在这样的示例中，重新排序和重新调度(在框1204和1206中)可在保持在 一队列中的接收到的读取操作的窗口上被应用。

在读取操作的队列被重新排序(在框1206中)的情况下，任何时延(如 超过某一阈值时延)可被反馈给请求者(即发送读取请求的实体)。

尽管上面图12的描述涉及读取操作，但是在一些示例中，相同的方法可 被应用于删除操作。

图13示出用于包括图3中所示的每组16个HDD的组以及PCIe互连结构 的存储设备的示例调度时间线1300。对于每组16个HDD的组，2个组能够充 分使用PCIe带宽，因此在任一给定时刻，2个组正在进行IO。在调度时间线 1300中，在每个步骤，调度器选择具有足够IO的组来加速旋转以与两个联合 的(即冲突的)组之间的转换(如所属这可能花费大约10秒)相重叠。

上述方法中的许多方法依赖于存储设备内的HDD被逻辑地安排成固定的 组，其中一组中的HDD可同时活动。然而，在一些示例中，可能没有固定的 组，相反，在任何时间活动的HDD的集合可由服务器内的调度器(或服务器 内的另一元件)基于功率约束、冷却约束、以及在某些示例中的某些其他约束 (如振动约束)来确定。这样的示例使用域的概念(如上参考图2所述)，其 中域是HDD的集合以及在该域上成立的约束的集合。例如，冷却域具有以瓦 特表示的约束，功率域同样。单个HDD是多个域的成员。

每域约束中的每一个被映射到面向HDD的约束的集合，即可被该域容忍 的HDD状态的集合。在上面的示例中，每个HDD被描述为处于两种状态之一 或在一些示例中三种状态之一中，这些状态是：不活动的(即盘片不在旋转， 但电子设备通电)、加速旋转(即盘片在从不旋转到以正确速度旋转的转换过 程中)、以及活动的(即盘片旋转)。如上所述，在一些示例中，可能有更多 的状态被考虑，诸如对于盘片旋转的HDD，在数据正被读取/写入时以及不被 读取/写入时之间相区分。对于功率域，系统内被考虑的每个状态的功率汲取是 已知的，且类似地对于冷却域，每个状态的冷却负荷是已知的。例如，在待机 (或非活动状态，即电子设备通电，盘片不旋转)中，HDD汲取0.7W，在活 动时(盘片旋转)是8W，而在盘片加速旋转时是24W达10秒。因此可对每 个域按照可由该域支持的可能状态来表达预算。返回参考前一示例架构，用于 某一域的功率预算可以是每功率域两个活动的HDD或者一个活动的HDD以及 一个HDD加速旋转，而冷却预算可以是每冷却域一个活动的或者加速旋转 HDD。预算可例如被表达为一状态表或有限状态机。

图14是在(如上所述)使用域的情况下从存储设备读取数据的示例方法 的流程图。在该示例中，当对某一文件的读取请求被接收到时(框1402)，服 务器内的调度器确定为了读取该文件而需要旋转的HDD的集合(框1404)。 该集合可能与当前旋转的HDD不同，因此调度器于是确定从旋转的HDD的当 前集合到旋转的HDD的所要求的集合(这可被称为“目标配置”)的迁移序列， 其中该迁移序列不穿过HDD的任何违反了任何域约束的中间集合(框1406)。 因此这是要求解的最佳化问题，它选择需要被穿过的硬件配置状态的集合以便 到达文件可被读取的配置。一旦迁移序列被确定，它就可被实现(框1408)， 且文件被读取(框1410)。

在实现图14的方法时，读取操作的突发段可被考虑(如上参考图12所述 那样)，且在该情况下，迁移序列可被确定来为该突发段而非单个请求优化吞 吐量。在这样的一示例中，旋转盘片所花费的时间(如10秒)可与先前所述 一样的方式被考虑，且IO请求可被分组成HDD的公共集合上的操作(持续至 少10秒)。

图12和13中所示以及上述的调度，一操作(如访问条堆栈的集合)与需 要被访问的HDD的集合相关联。在两个操作不冲突(即在HDD的集合之间没 有重叠)的情况下，它们可并行执行。然而，如果所有HDD都是冲突的，操 作被顺序处理。然而，如果仅HDD中的一部分冲突，则两个不同的调度机制 可被使用，且在上述方法中，可使用可被称为“非抢先式调度”的机制。

对于“非抢先式调度”，两个冲突的操作之一的100％被处理，而第二个被 推迟(即使这两个操作只有一个HDD冲突)。当冲突已被解决时(例如当第 一操作已被完成时)，第二操作被(完全地)处理。相反，对于“抢先式调度”， 两个冲突的操作之一的100％被处理，而另一操作的非冲突的n％被并行处理， 剩下的(100-n)％被稍后完成。

在可被用于图14所示方法的抢先式调度中，调度是在HDD的粒度上执行 的：调度器决定下一次旋转哪个HDD，而不管哪些操作当前被处理。调度器是 知晓域的，且调度不冲突的HDD。然而，对于非抢先式调度，调度器要么加速 旋转某一操作所需的全部HDD，要么延迟该操作(如果这不可能)。调度器是 无视域的，且关注于操作冲突的避免。

抢先式调度可能具有增加的调度灵活性，但是这导致增加的调度复杂性。 抢先式调度还可能具有更高的吞吐量，但是每操作更高的延迟，因为每个操作 可能要求若干加速旋转次数。抢先式调度还在服务器处使用大的存储器内缓存 以存储待决操作，这增加了存储设备的成本以及降低其可靠性。相反，非抢先 式调度在每操作的吞吐量方面提供了保证，且具有低存储器要求。

在上述方法中的任何方法中(例如在图10、12和14中所示的方法中的任 何方法中)，除了考虑功率和冷却约束之外，也可考虑其他约束(如软性约束) 和其他域。软性约束是这样的约束，即如果被违反则产生次优性能，但是不会 导致硬件故障(而在诸如功率和冷却约束之类的硬性约束的情况下会导致硬件 故障)。软性约束可基于域来被表达，例如故障和物理位置。故障域捕捉HDD 的集合以及它们将同时失败的可能性。物理位置捕捉互连结构的位置特性，且 可按照给定两个HDD则返回介于0和1之间的值V的函数来被表达。值V表 示两个HDD之间的干扰(例如1＝无干扰，而小于1的值表示该关系的强度)。 给定每HDD的额定带宽A，则被同时读取/写入的两个HDD的预期最大吞吐 量是V×A。

图15例示出可被实现为任何形式的计算和/或电子设备且可作为如本文所 述的存储设备内的服务器来操作的示例性基于计算的设备1500的各种组件。

基于计算的设备1500包括一个或多个处理器1502，处理器可以是微处理 器、控制器或用于处理计算机可执行指令以控制设备的操作来充当服务器以及 控制对存储设备内的HDD的读取/写入操作的任何其他合适类型的处理器。在 一些示例中，例如在使用片上系统架构的情况下，处理器1502可包括一个或 多个固定功能块(亦称加速器)，这些固定功能块以硬件(而非软件或固件) 来实现控制HDD的方法的一部分。作为替换或补充，本文所述的功能可至少 部分地由一个或多个硬件逻辑组件来执行。例如且并非限制，可使用的硬件逻 辑组件的说明性类型包括现场可编程门阵列(FPGA)、程序专用集成电路 (ASIC)、程序专用标准产品(ASSP)、片上系统(SOC)系统、复杂可编 程逻辑器件(CPLD)。

可以在基于计算的设备处提供包括操作系统1504的平台软件或任何其他 合适的平台软件以使得应用软件1506和调度器1508能够在该设备上被执行。 可以使用可由基于计算的设备1500访问的任何计算机可读介质来提供计算机 可执行指令。计算机可读介质可以包括例如诸如存储器1510等计算机存储介 质和通信介质。诸如存储器1510等计算机存储介质包括以用于存储如计算机 可读指令、数据结构、程序模块或其他数据等信息的任何方法或技术实现的易 失性和非易失性、可移动和不可移动介质。计算机存储介质包括但不限于， RAM、ROM、EPROM、EEPROM、闪存或其他存储器技术、CD-ROM、数字 多功能盘(DVD)或其他光存储、磁带盒、磁带、磁盘存储或其他磁存储设备， 或者可用于存储信息以供计算设备访问的任何其他非传输介质。相反，通信介 质可以以诸如载波或其他传输机构等已调制数据信号来体现计算机可读指令、 数据结构、程序模块或者其他数据。如本文所定义的，计算机存储介质不包括 通信介质。因此，计算机存储介质不应被解释为本质上是传播信号。传播信号 可存在于计算机存储介质中，但是传播信号本身不是计算机存储介质的示例。 虽然在基于计算的设备1500中示出了计算机存储介质(存储器1510)，然而 应当理解，该存储可以是分布式的或位于远处并经由网络或其他通信链路(例 如，使用通信接口1512)来访问。

在一些示例中，基于计算的设备1500可被远程地管理，且在该情况下， 通信接口1512可被安排成接收来自远程管理实体的管理指令以及向远程管理 实体提供状态/更新信息。

存储器1510可进一步包括可被用于为存储设备中的每个HDD存储访问标 志(如上文参考图5所述)的数据存储1514。

基于计算的设备1500还包括被安排成经互连结构将信号输出到背板交换 机中的每个背板交换机的服务器交换机1516(如上文参考图3或4所述)。这 些信号控制HDD的状态且也在向HDD写入或从HDD读取时被使用。替代地， 在基于SATA的互连结构400被使用的情况下，服务器交换机1516被HDD控 制器替代，HDD控制器提供多个SATA端口，每个SATA端口连接到树的最 上层处的一SATA多路复用器404。

基于计算的设备1500还可包括被安排成向显示设备输出显示信息的输入/ 输出控制器，该显示设备可与基于计算的设备分开或集成。该显示信息可以提 供图形用户界面。输入/输出控制器还可被安排成接收并处理来自诸如用户输入 设备(例如，鼠标、键盘、相机、话筒、或其他传感器)之类的一个或多个设 备的输入。在一些示例中，用户输入设备可以检测语音输入、用户姿势或其他 用户动作，并且可以提供自然用户界面(NUI)。在一实施例中，如果显示设 备是触敏显示设备，则它也可充当用户输入设备。输入/输出控制器还可向除了 显示设备之外的设备输出数据。

输入/输出控制器、显示设备以及用户输入设备(在提供的情况下)中的任 一者可包括使用户能够按自然的、免受诸如鼠标、键盘、遥控器等输入设备所 强加的人工约束的方式与基于计算的设备交互的NUI技术。可以提供的NUI 技术的示例包括但不限于依赖于语音和/或话音识别、触摸和/或指示笔识别(触 敏显示器)、屏幕上和屏幕附近的姿势识别、空中姿势、头部和眼睛跟踪、语 音和话音、视觉、触摸、姿势以及机器智能的那些技术。可被使用NUI技术的 其他示例包括意图和目的理解系统，使用深度相机(如立体相机系统、红外相 机系统、RGB相机系统、以及这些的组合)的运动姿势检测系统，使用加速度 计/陀螺仪，面部识别，3D显示，头部、眼睛和注视跟踪的运动姿势检测，沉 浸式增强现实和虚拟现实系统，以及用于使用电场传感电极(EEG和相关方法) 的感测大脑活动的技术。

在上面的示例中，约束是由对存储设备的设计来设置的，且因此可被认为 是固定的。在组被使用的情况下，这些是由约束确定的且可因此也被认为是固 定的。然而，在硬件故障的情况下，服务器可被安排成修改约束(因此组(在 组被使用的情况下))，使得存储设备能够继续运行，即使性能可能劣化。例 如，存储设备可包括6个供电单元，每个对若干托盘供电(例如对12个托盘 供电)，在某一供电单元失败的情况下，存储设备内的另一供电单元可在更多 数量的托盘之间(例如24个托盘之间)被共享，且约束和/或组可被动态地适 配来响应于此。在用更有效的硬件替代任何硬件(如HDD)时，约束/组也可 被修改(例如被动态地适配)(例如与更有效的HDD相关联的功率和/或冷却 约束可能不同，允许更大或不同大小的组)。

在硬件故障的情况下，除了适配约束和/或组之外或者代替适配约束和/或 组，可能存在在存储设备内操作的一个或多个恢复机制。示例包括：在一组内 的保持备用容量来处理HDD故障(例如每组包括比用于每个操作的HDD多1 或2的HDD)，保持HDD的备用组来用于冗余性目的(例如可切换到该备用 组来替换经受到HDD故障的组)，以及跨其他组来分散负荷。

虽然在本文中将本发明的示例描述并例示为在包括一个或两个服务器的 存储设备中实现，但是所描述的系统是作为示例而非限制来提供的。如本领域 的技术人员将理解的，本发明的示例适合于应用在各种各样的不同类型的存储 系统中，例如多个存储设备可位于同处(例如在数据中心中)且在故障的情况 下存在资源(例如供电单元)的某种共享。此外，尽管两个示例互连结构300、 400在上文被描述，互连结构的替代设计可被使用。

如上所述，在一些示例中，服务器104可位于存储设备100的其余部分的 远程。在这样的示例中，控制逻辑112可被提供在存储设备100内且被安排成 响应于从远程服务器接收到的信号经互连结构106向HDD102提供控制信号。

上述存储设备旨在用于对HDD的最小读取/写入访问，因此被配置成将大 多数HDD保持在休眠(即不活动的)状态，在该状态中它们消耗最少功率(电 子设备通电但盘片不旋转)。HDD仅被带出该状态来最初写数据，检查数据完 整性或检索数据；然而由于存储设备所针对来设计的数据类型是存档，因此检 索操作预期是最少的。因此，存储设备可被设计成使用最少功率和相关联的冷 却。对于包括1152个HDD的示例配置(如上所述)，存储设备可被设计成使 用2.4kW或少于(带有相似存储容量的)现有存储设备的25％。这要求(存储 设备内)较少的功率分布、较小的风扇，以及允许HDD的更大堆叠密度，造 成较低量的冷却(如强制气流)通过存储设备。如上所述，本文所述的存储设 备是供应不足的，使得它们不能对设备中的所有HDD提供足够的功率和/或冷 却(即，它们物理上不能使所有HDD同时加速旋转)。在一示例中，在任何 时候，该存储设备仅对HDD中活动的大约10％或更少(如8.3％)提供足够的 功率和冷却。这种供应不足降低了功耗并因此降低了设备的运行花费，且设备 的降低的带宽也可有助于运行成本的进一步降低。所允许的HDD的更高的堆 叠密度以及功率和冷却基础设施中的减少有助于购买存储设备的较低的初始 成本(例如较低的费用支出)。

上述的存储设备提供了物理硬件和软件被一起设计的设备的示例，使得软 件(控制逻辑)防止存储设备进入某一集合的HDD活动的状态，该状态将由 于不足的功率和/或冷却造成整个设备的故障。

此处所使用的术语“计算机”或“基于计算的设备”是指带有处理能力以便它 可以执行指令的任何设备。本领域技术人员可以理解，这样的处理能力被结合 到许多不同设备，并且因此术语每个“计算机”和“基于计算的设备”包括个人电 脑、服务器、移动电话(包括智能电话)、平板电脑、机顶盒、媒体播放器、 游戏控制台、个人数字助理和许多其它设备。

本文描述的方法可由有形存储介质上的机器可读形式的软件来执行，例如 计算机程序的形式，该计算机程序包括在该程序在计算机上运行时适用于执行 本文描述的任何方法的所有步骤的计算机程序代码装置并且其中该计算机程 序可被包括在计算机可读介质上。有形存储介质的示例包括计算机存储设备， 计算机存储设备包括计算机可读介质，诸如盘(disk)、拇指型驱动器、存储 器等而不包括所传播的信号。传播信号可存在于有形存储介质中，但是传播信 号本身不是有形存储介质的示例。软件可适于在并行处理器或串行处理器上执 行以使得各方法步骤可以按任何合适的次序或同时执行。

这承认，软件可以是有价值的，单独地可交换的商品。它旨在包含运行于 或者控制“哑”或标准硬件以实现所需功能的软件。它还旨在包含例如用于设计 硅芯片，或者用于配置通用可编程芯片的HDL(硬件描述语言)软件等“描述” 或者定义硬件配置以实现期望功能的软件。

本领域技术人员会认识到，用于存储程序指令的存储设备可分布在网络 上。例如，远程计算机可以存储被描述为软件的进程的示例。本地或终端计算 机可以访问远程计算机并下载软件的一部分或全部以运行程序。可另选地，本 地计算机可以根据需要下载软件的片段，或在本地终端上执行一些软件指令， 并在远程计算机(或计算机网络)上执行另一些软件指令。本领域的技术人员 还将认识到，通过利用本领域的技术人员已知的传统技术，软件指令的全部， 或一部分可以通过诸如DSP、可编程逻辑阵列等等之类的专用电路来实现。

对精通本技术的人显而易见的是，此处给出的任何范围或设备值可以被扩 展或改变，而不会丢失寻求的效果。

尽管用结构特征和/或方法动作专用的语言描述了本主题，但可以理解，所 附权利要求书中定义的主题不必限于上述具体特征或动作。更确切而言，上述 具体特征和动作是作为实现权利要求的示例形式公开的。

可以理解，上文所描述的优点可以涉及一个实施例或可以涉及多个实施 例。各实施例不仅限于解决任何或全部所陈述的问题的那些实施例或具有任何 或全部所陈述的优点那些实施例。将进一步理解，对“一”项目的引用指的是那 些项目中的一个或多个。

此处所描述的方法的步骤可以在适当的情况下以任何合适的顺序，或同时 实现。另外，在不偏离此处所描述的主题的精神和范围的情况下，可以从任何 一个方法中删除各单独的框。上文所描述的任何示例的各方面可以与所描述的 其他示例中的任何示例的各方面相结合，以构成进一步的示例，而不会丢失寻 求的效果。

此处使用了术语“包括”旨在包括已标识的方法的框或元件，但是这样的框 或元件不包括排它性的列表，方法或设备可以包含额外的框或元件。

术语“子集”在本文中被用于指代一合适的子集，也就是说使得一子集不等 价于原集合且必定排除该集合的至少一个成员。

可以理解，上面的描述只是作为示例给出并且本领域的技术人员可以做出 各种修改。以上说明、示例和数据提供了对各示例性实施例的结构和使用的全 面描述。虽然上文以一定的详细度或参考一个或多个单独实施例描述了各实施 例，但是，在不偏离本说明书的精神或范围的情况下，本领域的技术人员可以 对所公开的实施例作出很多更改。