用于顺序传输优化存储装置的卷级冗余编码技术

摘要

本文描述和提出的技术包括用于使用冗余编码技术将数据档案的原始数据在数据存储系统上进行存储、索引和检索的系统和方法。例如，诸如纠删码的冗余码可应用于档案(诸如从计算资源服务提供商的客户接收到的档案)，以便允许存储在最少的卷上可用的单个档案的原始数据，诸如数据存储系统的那些数据，同时保留可用性、耐用性以及由应用所述冗余码而赋予的其他保证。可实现稀疏索引技术，以便一旦存储就减少用于定位所述原始数据的索引的占用空间。

权利要求

1.一种计算机实现的方法，其包括：

在被配置有可执行指令的一个或多个计算机系统的控制下，处理将要存储在多个卷上的多个档案，以便：

根据由所述多个档案共享的至少一个标准来对所述多个档案进行分类；以及确定所述分类的多个档案中的哪些档案将被存储在所述多个卷中的每个卷上；

生成所述多个卷的索引，所述索引中的每个索引反映将要存储在所述多个卷中的相应卷上的所述分类的多个档案的子集；

将所述分类的多个档案和所述生成的索引存储在所述多个卷的子集上，从而生成多个碎片；

将冗余码应用至所述分类的多个档案和所述生成的索引以生成编码的碎片；以及将所述编码的碎片存储在所述多个卷的所述子集外的对应卷上。

2.如权利要求1所述的计算机实现的方法，其还包括通过从所述多个卷的所述子集中检索所述子集来响应对所述原始数据的至少一个子集的请求。

3.如权利要求1所述的计算机实现的方法，其还包括如果所述多个碎片中的碎片被检测为不可用，使用具有所述多个碎片的子集的所述编码的碎片中的至少一个来重新生成所述不可用碎片。

4.如权利要求1所述的计算机实现的方法，其中所述冗余码是包含单位矩阵的纠删码。

5.一种系统，其包括：

至少一个计算装置，所述至少一个计算装置被配置来实现一个或多个服务，其中所述一个或多个服务被配置来：以预定顺序对多个档案进行分类，以便以所述预定顺序存储在多个卷上；

使用冗余码来处理所述多个档案，以便生成多个碎片，所述多个碎片的子集包括所述多个档案的原始数据；以及将所述碎片存储在所述多个卷上，以使得所述多个卷的子集包含所述原始数据。

6.如权利要求5所述的系统，其中所述碎片被存储成使得所述多个档案中的相应档案的所述原始数据被完全存储在所述多个卷的所述子集的单个卷内。

7.如权利要求5所述的系统，其中所述碎片被存储成使得所述多个档案中的相应档案的所述原始数据被存储在所述多个卷的所述子集的至多两个卷内。

8.如权利要求5所述的系统，其中所述一个或多个服务包括由所述系统提供的档案存储服务。

9.如权利要求5所述的系统，其中所述多个卷中的每个卷对应于多个存储装置中的一个存储装置。

10.如权利要求5所述的系统，其中所述一个或多个服务还被配置来生成所述多个卷的索引，所述索引中的每个索引反映将要存储在所述多个卷中的相应卷上的所述分类的多个档案的子集。

11.如权利要求10所述的系统，其中所述一个或多个服务还被配置来：使用所述冗余码来处理所述索引，以便将所述索引中的每个索引包含在相应的碎片中；以及存储所述碎片，以使得所述多个卷中的每个卷包含所述处理的索引中的相应索引。

12.如权利要求5所述的系统，其中所述一个或多个服务还被配置来如果所述多个碎片的所述子集中的碎片被检测为不可用，使用所述多个碎片的第二子集来重新生成使用所述冗余码的所述不可用碎片。

13.一种系统，其包括：

至少一个计算装置，所述至少一个计算装置被配置来实现一个或多个服务，其中所述一个或多个服务被配置来：确定其中多个档案将要被存储在多个卷上的所述多个档案的顺序；

通过向至少所述多个档案应用冗余码来生成多个碎片，所述多个碎片中的每个碎片对应于所述多个卷中的卷，以使得：所述多个碎片的子集包含所述多个档案的原始数据，并且所述多个碎片的所述子集被存储在所述多个卷上，以使得所述多个档案被以所述多个碎片的所述子集内的所述确定的顺序来表示；以及将所述多个碎片存储在所述多个卷中的对应卷上。

14.如权利要求13所述的系统，其中所述指令还包括在由所述一个或多个处理器执行时致使所述计算机系统通过对具有所述计算机系统的一个或多个客户的共同所有权的所述多个档案的子集进行分组来确定所述多个档案的所述顺序的指令。

15.如权利要求13所述的系统，其中所述指令还包括在由所述一个或多个处理器执行时致使所述计算机系统通过经由多个属性将所述多个档案顺序分类或者经由所述多个档案中的每个档案由所述计算机系统接收的时间对所述多个档案顺序分类中的至少一个来确定所述多个档案的所述顺序的指令。

说明书

用于顺序传输优化存储装置的卷级冗余编码技术

[0001] 相关申请的交叉引用

[0002] 本申请要求2014年12月19日提交的题为“用于顺序传输优化存储装置的卷级冗余编码技术(VOLUME-LEVEL REDUNDANCY CODING TECHNIQUES FOR SEQUENTIAL TRANSFER OPTIMIZED STORAGE DEVICES)”的共同未决的美国专利申请号14/578,130的优先权，所述专利申请的全部内容以引用的方式并入本文。

背景技术

[0003] 网络计算和存储的使用近年来一直在增长。用于网络计算和存储的资源通常由利用计算机、服务器和存储驱动器的大规模网络的计算资源提供商来提供，以使客户端(包括内容提供商、在线商家等)能够托管和执行各种应用和web服务。传统上使用现场服务器和存储设备来托管其网站并将内容存储并流式传输给其客户的内容提供商和在线商家通常放弃现场托管和存储，并且转而使用计算资源提供商的资源。网络计算的使用允许内容提供商和在线商家等有效地且自适应地满足他们的计算需求，由此由内容提供商和在线商家所使用的计算和存储资源被根据需要并且根据他们的需要而添加或从由计算资源提供商所提供的大型池中移除。

[0004] 网络计算和存储的增长以及依赖于网络计算和存储的实体数量的伴随的增加已增加优化网络计算和存储系统上的数据性能和完整性的重要性。例如，数据档案系统和服务可使用各种类型的纠错和容错方案，诸如实现冗余编码和数据分片。此外，相对于其他数据存储装置，通过使用与随机存取存储装置相比在顺序存储上快得多的数据存储装置或介质，可减轻持续增加的数据量的容量和成本。

附图说明

[0005] 将参考附图描述根据本公开的各种实施方案，在附图中：

[0006] 图1示意性地示出根据一些实施方案的可将档案原始数据存储在实现冗余码的数据存储系统上的环境；

[0007] 图2示意性地示出根据一些实施方案的用于将档案原始数据存储在数据存储系统的多个数据存储区上的各种工作流程；

[0008] 图3示意性地示出根据一些实施方案的用于索引和定位存储在数据存储系统上的数据的各种工作流程；

[0009] 图4示意性地示出根据一些实施方案的用于处理、索引、存储和检索存储在数据存储系统上的数据的示例性过程；

[0010] 图5示意性地示出根据一些实施方案的用于索引存储在冗余编码数据存储系统上的原始数据的示例性过程；

[0011] 图6示意性地示出根据一些实施方案的包括可实现数据存储和索引技术的计算资源服务提供商的环境；

[0012] 图7示意性地示出根据一些实施方案的能够实现各种数据存储和索引技术的数据存储服务；并且

[0013] 图8示出可实现各种实施方案的环境。

具体实施方式

[0014] 在以下描述中，将描述各种实施方案。出于解释的目的，将阐述具体的配置和细节，以便提供各实施方案的透彻理解。然而，对于本领域技术人员还将明显的是，在没有具体细节的情况下也可实行各实施方案。此外，为了不使所描述的实施方案晦涩，可能会省略或简化众所周知的特征。

[0015] 本文描述和提出的技术包括用于使用冗余编码技术将数据档案(“档案”)的原始数据存储在数据存储系统上的系统和方法。例如，诸如纠删码的冗余码可应用于传入档案(诸如从实现本文描述的存储技术的计算资源服务提供商的客户接收到的档案)，以便允许存储在最少的卷上可用的单个档案的原始数据，诸如数据存储系统的那些数据，同时保留可用性、耐用性以及由应用冗余码而赋予的其他保证。

[0016] 在一些实施方案中，通过由计算资源服务提供商的一个或多个资源提供的诸如档案存储服务的服务来从计算资源服务提供商的客户接收档案，诸如包含任何数量和性质的数据的客户档案。档案可根据一个或多个常见属性(诸如客户的身份、上传时间和/或例如由档案存储服务接收的时间)进行分类。可执行这种分类，以便最小化存储任何给定档案的卷的数量。在一些实施方案中，档案的原始数据被存储为跨多个卷的多个碎片，其数量(在某些情况下可能具有一对一关系的碎片或卷的数量)可根据各种因素来预先确定，包括使用冗余码重建原始数据所需的总碎片数。

[0017] 在一些实施方案中，可结合例如将要存储档案的顺序来生成一个或多个标记，如结合上文所述的分类确定的。在一些实施方案中，可针对多个卷中的每个卷生成索引，并且在这类实施方案中，可反映存储在其应用的相应卷上的档案。标记可以是任何适当的类型，并且可包括稀疏标记。在使用稀疏标记的实施方案中，索引(例如，针对给定卷)可指向存储或将要存储在例如此卷上的档案的子集。可在任何基础上和任何适当的间隔内选择子集。实例可包括位于卷的x个块或字节的间隔处的档案的标识或者在n个档案的间隔处的档案的标识，其中x或n可由例如档案存储服务或其管理员来预先确定。

[0018] 在一些实施方案中，稀疏索引与关于档案分类顺序的信息结合使用，以便定位档案，而不需要使用密集索引，例如在给定卷上考虑每个档案的索引。这种分类顺序相关信息可驻留在卷上，或者在一些实施方案中可驻留在与卷分离的实体上。类似地，索引可存储在它们应用到的相同的卷上，或者在一些实施方案中与这类卷分开存储。在将分类顺序相关信息和/或索引存储在适用卷上的实施方案中，分类顺序相关信息和/或索引可被包含在档案的原始数据中并且作为碎片随其存储，如前所述。

[0019] 在一些实施方案中，档案的原始数据(以及在标记被存储在卷上的实施方案中，标记)由与例如档案存储服务相关联的实体使用冗余码(诸如纠删码)来进行处理，以便生成可用于重新生成原始数据的冗余编码碎片以及(如果适用的话)标记。在一些实施方案中，冗余码可利用数学函数矩阵(“生成矩阵”)，其一部分可包括单位矩阵。在一些这类实施方案中，冗余编码碎片可至少部分地对应于在单位矩阵之外的生成矩阵的部分。如此生成的冗余编码碎片可存储在另外的卷中。卷的总数可包括承载原始数据(和标记)的卷以及包含冗余编码碎片的卷。

[0020] 在一些实施方案中，根据本文描述的技术存储的档案的检索可由诸如在计算资源服务提供商的客户的控制下的客户端装置和/或由其提供的档案存储服务的实体来请求，如贯穿本公开内容更详细地描述的。响应于此请求，数据存储系统(例如，包括上述卷并且提供档案存储服务的系统)可基于关于存储在卷上的档案的分类顺序的信息来定位档案位于其上的特定卷。此后，可使用索引或标记来定位特定卷，从而从卷读取并提供给请求实体。在采用稀疏索引的实施方案中，分类顺序信息可用于定位相继在所请求的档案之前的最近位置(或档案)，从而从此位置或档案顺序地读取此卷，直到找到所请求的档案。

[0021] 在一些实施方案中，如果卷中的一个卷或其上存储的碎片被检测为损坏、丢失或以其他方式不可用，那么可使用应用于在第一实例中生成碎片的冗余码来生成新的碎片。在一些实施方案中，新的碎片可以是不可用碎片的复制，诸如可以是在碎片包含档案的原始数据的情况下。在一些实施方案中，新的碎片可从由例如与冗余码相关联的生成矩阵产生的一组潜在碎片中选择，以便在内容上不同于不可用碎片(诸如可以是不可用碎片是从冗余码生成的碎片并且因此不包含档案的原始数据的情况)。在这种情况下，在某些实施方案中，可产生全新的卷，而不是碎片。

[0022] 图1示意性地示出根据一些实施方案的可将档案原始数据存储在实现冗余编码的数据存储系统上的环境。一个或多个客户端实体102(诸如在计算资源服务提供商的客户的控制下的客户端实体)将档案104提交到数据存储系统106以便进行存储。客户端实体102可以是能够与数据存储系统诸如通过网络(包括互联网)进行数据交易的任何实体。实例包括物理计算系统(例如，服务器、台式计算机、膝上型计算机，瘦客户端、以及诸如智能手机和平板电脑的手持装置)、(例如，可由计算资源服务提供商使用与其相关联的一个或多个资源来提供的)虚拟计算系统、服务(例如，诸如通过应用程序编程接口调用连接到数据存储系统106的那些服务、web服务调用或其他编程方法)等。

[0023] 数据存储系统106可以是能够处理以便进行存储并且与一个或多个资源交接以导致存储处理数据的任何计算资源或这类资源的集合。实例包括物理计算系统(例如，服务器、台式计算机、膝上型计算机，瘦客户端、以及诸如智能手机和平板电脑的手持装置)、(例如，可由计算资源服务提供商使用与其相关联的一个或多个资源来提供的)虚拟计算系统、服务(例如，诸如通过应用程序编程接口调用连接到数据存储系统106的那些服务、web服务调用或其他编程方法)等。在一些实施方案中，数据存储系统106的资源以及数据存储系统106本身可以是计算资源服务提供商的一个或多个资源，诸如下文进一步详细描述的。在一些实施方案中，数据存储系统106和/或计算资源服务提供商提供一个或多个档案存储服务和/或数据存储服务，诸如在下文进一步描述的那些，客户端实体102可通过这些服务来进行数据(诸如档案104)交易。

[0024] 档案104可包含任何格式的任何数量的数据。例如，档案104可以是单个文件，或者在一些实施方案中可包含多个文件。档案104可由例如客户端装置102加密，或者在一些实施方案中，可在接收到档案104之后，诸如在数据存储系统106和/或计算资源服务提供商的客户请求时，由数据存储系统106的部件加密。

[0025] 数据存储系统106可根据一个或多个标准对档案104进行分类(并且在多个标准用于分类的情况下，可顺序地并且以适合于实现的任何顺序对这些标准进行分类)。这种标准可以是一些或所有档案的共同属性，并且可包括客户的身份、(例如，由客户端装置102)上传和/或(由数据存储系统106)接收的时间、档案大小、预期体积和/或相对于档案边界的碎片边界(例如，以便最小化跨碎片和/或卷损坏的档案数量)等。如上所述，可执行这种分类，以便最小化存储任何给定档案的卷的数量。可使用这类技术，例如以在从多个卷检索数据的开销大于从多个卷并行化检索的益处的实施方案中来优化存储。关于分类顺序的信息可例如由数据存储系统106维持，以用于本文进一步详细描述的技术。

[0026] 如前所述，在一些实施方案中，可结合例如将要存储档案的顺序来生成一个或多个标记，如结合上文所述的分类确定的。索引可以是单个索引或者可以是多部分索引，并且可以是任何适当的架构，并且可根据任何适当的方法来生成。例如，索引可以是位图索引、密集索引、稀疏索引或反向索引。使用多个标记的实施方案可根据例如通过数据存储系统106存储的档案104的特性来实现不同类型的标记。例如，数据存储系统106可为特定大小的档案生成密集索引(索引本身的大小相对于存储在给定卷上的档案的数量可能较小)，并且还可为所述特定大小的档案生成稀疏索引(索引大小与档案大小的比例增加)。

[0027] 数据存储系统106被连接到或包括一个或多个卷108，在卷108上存储档案104，并且在一些实施方案中存储所生成的索引。卷108可以是能够存储或寻址存储在其中的数据的任何逻辑容器或物理容器。在一些实施方案中，卷108可与它们所在的数据存储装置(并且在一些实施方案中实际上可能是数据存储装置本身)在一对一的基础上进行映射。在一些实施方案中，卷108的大小和/或数量可独立于它们驻留在其上的数据存储装置的容量(例如，一组卷可各自具有固定大小，以使得第二组卷可驻留在与第一组卷相同的数据存储装置上)。数据存储装置可包括能够存储数据的任何资源或资源集合，诸如计算资源服务提供商的那些资源，并且可以是物理的、虚拟的或两者的某种组合。

[0028] 如前所述，在一些实施方案中，可针对多个卷中的每个卷108生成一个或多个标记，并且在这类实施方案中，可反映存储在其应用的相应卷108上的档案。在使用稀疏标记的实施方案中，给定卷的稀疏索引可指向存储或将要存储在卷108上的档案104的子集，诸如可被确定为基于先前提及的分类技术而存储在卷108上的那些档案104。在稀疏索引中将要被索引的卷的子集可在任何适当的基础上并且以任何适当的间隔来进行选择。例如，稀疏索引可识别将要(例如，独立于档案本身的边界和/或数量)在卷的每x个块或字节处定位的档案。作为另一实例，稀疏索引可识别将要存储在卷108上的每一第n个档案。如可设想的，标记(无论是稀疏的还是其他的)可在将档案实际存储在相应卷上之前进行确定。在一些实施方案中，可在卷上保留空间，以便在档案104被写入卷108之后生成和/或写入适当的标记。

[0029] 在一些实施方案中，稀疏索引与关于档案分类顺序的信息结合使用，以便定位档案，而不需要使用密集索引，例如在给定卷108上考虑每个档案104的索引。这种分类顺序相关信息可驻留在卷108上，或者在一些实施方案中可驻留在与卷108分离的实体上，诸如在计算资源服务提供商的数据存储区或其他资源中。类似地，索引可存储在它们应用到的相同的卷108上，或者在一些实施方案中与这类卷108分开存储。

[0030] 如所提及的，档案104被一位一位地(例如，档案的“原始数据”)存储在多个卷108的子集上。同样如上所述，适当的标记也可存储在多个卷108的适用子集上。档案的原始数据被存储为跨多个卷的多个碎片，其数量(在某些情况下可能具有一对一关系的碎片或卷的数量)可根据各种因素来预先确定，包括使用冗余码重建原始数据所需的总碎片数。在一些实施方案中，用于存储档案的原始数据的卷的数量是从由来自原始数据的冗余码生成的多个碎片中重构原始数据所需的碎片的数量。作为实例，图1示出五个卷，其中三个包含原始数据110，并且其中两个包含派生数据112，诸如冗余编码数据。在示出的实例中，所使用的冗余码可能需要任意三个碎片来重新生成原始数据，并且因此，可使用三个卷的数量来写入原始数据(甚至在冗余码的任何应用之前)。

[0031] 承载原始数据110的卷108可各自包含或被认为是它们自己的碎片。在将分类顺序相关信息和/或索引存储在适用卷108上的实施方案中，分类顺序相关信息和/或索引可被包含在档案的原始数据中并且作为碎片存储，如前所述。在示出的实例中，原始数据110在三个相关联的卷108上被存储为三个碎片(其可包括相应的标记)。在一些实施方案中，原始数据110(以及在标记被存储在卷上的实施方案中，标记)由与例如档案存储服务相关联的实体使用冗余码(诸如纠删码)来进行处理，以便生成包含编码信息而不是档案的原始数据的剩余碎片。原始数据110可在分类之后的任何时间使用冗余码进行处理，诸如在与这种存储同时存储在卷上之前或者在这种存储之后。

[0032] 这种编码信息可以是从原始数据派生的任何数学计算的信息，并且取决于所应用的特定冗余码。如上所述，冗余码可包括纠删码(诸如在线代码、卢比变换码、raptor码、奇偶校验码、里德-所罗门码、柯西码、抗删除系统码、再生码或最大距离可分离码)或者其他前向纠错码。在一些实施方案中，冗余码可实现实现数学函数以生成与应用冗余码的原始数据相关的多个编码对象的生成矩阵。在一些这类实施方案中，使用单位矩阵，其中不应用数学函数，并且允许原始数据(以及适用的索引)直接通过。在这类实施方案中，因此可设想，承载原始数据(和索引)的卷可对应于通过应用的冗余码的生成矩阵的单位矩阵行通过所述原始数据编码的对象，而承载派生数据的卷对应于生成矩阵的其他行。在图1所示的实例中，五个卷108包括具有对应于档案110的原始数据的碎片的三个卷，而两个卷具有对应于派生数据112的碎片。在此实例中，应用的冗余码可能导致数据以3∶5方案存储，其中需要五个存储的碎片中的任意三个碎片来重新生成原始数据，而不管所选择的三个碎片是否包含原始数据或派生数据。

[0033] 在一些实施方案中，如果卷108中的一个卷或其上存储的碎片被检测为损坏、丢失或以其他方式不可用，那么可使用应用于在第一实例中生成碎片的冗余码来生成新的碎片。新的碎片可存储在相同的卷或不同的卷上，这取决于例如碎片是否出于除了卷故障之外的原因而不可用。新的碎片可由例如数据存储系统106通过使用重新生成存储在所有卷上的原始数据(以及(如果适用)索引)所需的剩余碎片的数量、重新生成所述原始数据以及替换原始数据的对应于不可用的部分(在不可用碎片包含原始数据的情况下)、或者重新应用冗余码以便为新的碎片提供派生数据来生成。

[0034] 如前所述，在一些实施方案中，新的碎片可以是不可用碎片的复制，诸如可以是在不可用碎片包含档案的原始数据的情况下。在一些实施方案中，新的碎片可从由例如与冗余码相关联的生成矩阵产生的一组潜在碎片中选择，以便在内容上不同于不可用碎片(诸如可以是不可用碎片是从冗余码生成的碎片并且因此不包含档案的原始数据的情况)。

[0035] 在一些实施方案中，根据本文描述的技术存储的档案的检索可由诸如在计算资源服务提供商的客户的控制下的客户端实体102和/或由其提供的档案存储服务的实体来请求，如贯穿本公开内容更详细地描述的。响应于此请求，数据存储系统106可基于关于存储在卷108上的档案104的分类顺序的信息来定位档案104位于其上的特定卷108。此后，可使用索引或标记来定位特定档案，从而从卷读取并提供给请求客户端实体102。在采用稀疏索引的实施方案中，分类顺序信息可用于定位相继在所请求的档案之前的最近位置(或档案)，从而从此位置或档案顺序读取此卷，直到找到所请求的档案。在采用多种类型的标记的实施方案中，数据存储系统106可基于评估用于在第一实例中部署多种类型的标记的标准来最初确定哪些标记包含用于请求档案的最有效的位置信息。例如，如果特定大小的档案以稀疏索引进行索引，并且等于或大于此大小的档案被以平行密集索引进行索引，那么数据存储系统106可首先确定所请求的档案的大小，并且如果所请求的档案大于或等于上述大小边界，就可使用密集索引，以便更快地获得所请求档案的精确位置。

[0036] 图2示意性地示出根据一些实施方案的用于将档案原始数据存储在数据存储系统的多个数据存储区上的各种工作流程。在一些实施方案中，数据存储系统202可类似于上文结合图1描述的数据存储系统106，其包括或连接到多个卷204，卷204也可类似于上文结合图1描述的卷108。档案206，诸如从结合图1描述的客户端实体102接收到的档案，由数据存储系统202根据本文进一步详细描述的技术来进行处理。

[0037] 如前所述，数据存储系统202可根据一个或多个标准对档案206进行分类(并且在多个标准用于分类的情况下，可顺序地并且以适合于实现的任何顺序对这些标准进行分类)。这种标准可以是一些或所有档案的共同属性，并且可包括客户的身份、由客户定义的抽象概念(例如，与同一客户的多个档案相关联的较大数据对象)、上传时间和/或接收时间、档案大小、预期体积和/或相对于档案边界的碎片边界(例如，以便最小化跨碎片和/或卷损坏的档案数量)、档案本身的唯一标识符等。如前所述，可执行这种分类，以便最小化存储任何给定档案的卷的数量。例如，可基于预期的卷大小来对较大的档案进行分类，以使得较大的档案被较早地存储在卷中，并且越来越小的档案被稍后存储在卷中。可使用这类技术，例如以在从多个卷检索数据的开销大于从多个卷并行化检索的益处的实施方案中来优化存储。例如，使用可移动介质的装置可能会在介质发生物理变化时致使显著的延迟惩罚，并且分类顺序可连结并分配档案，以便最小化检索档案所需的可移动介质的数量。如前所述，关于分类顺序的信息可例如由数据存储系统202维持，以用于本文进一步详细描述的技术。

[0038] 在一些实施方案中，数据存储系统202可对档案206进行两次或更多次的分类，其中的至少一个档案可对应于数据存储系统202和/或卷204本身的各种特性。例如，第一分类可易于发生档案206在一个或多个卷204上的实际存储，根据边界、存储空间和其他卷特征对档案进行分类以便优化档案206的存储，并且第二分类可重新分类发往每个卷204的那些档案，从而影响卷204内的实际存储。在此实例中，任一种或两种分类可包括以上描述的一个或多个标准。

[0039] 如前所述(例如，结合图1)，在一些实施方案中，可针对多个卷中的每个卷204生成一种或多种类型的一个或多个标记，并且在这类实施方案中，可反映存储在其应用的相应卷204上的档案。在一些实施方案中，索引与关于档案206的分类顺序的信息结合使用，以便定位档案，而不需要使用密集索引，例如在给定卷108上考虑每个档案104的索引。这种分类顺序相关信息可驻留在卷204上，或者在一些实施方案中可驻留在与卷204分离的实体上，诸如在计算资源服务提供商的数据存储区或其他资源中。类似地，索引可存储在它们应用到的相同的卷204上，或者在一些实施方案中与这类卷204分开存储。

[0040] 如所提及的，档案206的原始数据212被存储在多个卷204的子集上，并且卷的子集的数量可等于冗余码重新生成原始数据所需的最小碎片数。同样如所提及的，适当的标记也可与所存储的档案208的原始数据212结合地存储在多个卷208的适用子集上。档案的原始数据被存储为跨多个卷的多个碎片，其数量(在某些情况下可能具有一对一关系的碎片或卷的数量)可根据各种因素来预先确定，包括使用冗余码重建原始数据所需的总碎片数。作为实例，图2示出五个卷，其中三个包含存储档案208的原始数据212(对应于传入档案
206)，并且其中两个包含从应用的冗余码的数学函数派生的数据214。在示出的实例中，所使用的冗余码可能需要任意三个碎片来重新生成原始数据，并且因此，可使用三个卷的数量来写入原始数据(在冗余码的任何应用之前)。

[0041] 与先前讨论的类似，存储存储档案208的原始数据212的卷204被在卷级处由与例如档案存储服务相关联的实体使用冗余码(诸如纠删码)来进行处理，以便生成包含编码信息而不是档案的原始数据的剩余碎片214。如前所述，原始数据212可在分类之后的任何时间使用冗余码进行处理，诸如在与这种存储同时存储在卷上之前或者在这种存储之后。如阴影档案210所示，在某些情况下，给定的档案可能由于大小、放置等而在两个(或可能更多的)卷204之间断开。在冗余码被应用于卷级的实施方案中(例如，承载档案的原始数据的卷的全部内容被认为是由冗余码处理的单个数据对象)，所示档案210的原始数据所驻留的两个卷(或碎片)中的一个的故障可不需要重建两个卷，而仅需要重建不可用的卷。

[0042] 编码信息214可以是从原始数据212派生的任何数学计算的信息，并且取决于所应用的特定冗余码。在一些实施方案中，冗余码可实现实现数学函数以生成与应用冗余码的原始数据相关的多个编码对象的生成矩阵。在一些这类实施方案中，使用单位矩阵，其中不应用数学函数，并且允许原始数据(以及适用的索引)直接通过。因此可设想，承载原始数据(和索引)208的卷可对应于通过应用的冗余码的生成矩阵的单位矩阵行通过所述原始数据编码的对象，而承载派生数据214的卷对应于生成矩阵的其他行。

[0043] 与先前讨论的类似，如果卷204中的一个卷或其上存储的碎片被检测为损坏、丢失或以其他方式不可用，那么可使用应用于在第一实例中生成碎片的冗余码来生成新的碎片。新的碎片可存储在相同的卷或不同的卷上，这取决于例如碎片是否出于除了卷故障之外的原因而不可用。新的碎片可由例如数据存储系统202通过使用重新生成存储在所有卷上的原始数据(以及(如果适用)索引)所需的剩余碎片的数量、重新生成所述原始数据以及替换原始数据的对应于不可用的部分(在不可用碎片包含原始数据的情况下)、或者重新应用冗余码以便为新的碎片提供派生数据来生成。

[0044] 如前所述，在一些实施方案中，新的碎片可以是不可用碎片的复制，诸如可以是在不可用碎片包含档案的原始数据的情况下。在一些实施方案中，新的碎片可从由例如与冗余码相关联的生成矩阵产生的一组潜在碎片中选择，以便在内容上不同于不可用碎片(诸如可以是不可用碎片是从冗余码生成的碎片并且因此不包含档案的原始数据的情况)。

[0045] 图3示意性地示出根据一些实施方案的用于索引和定位存储在数据存储系统上的数据的各种工作流程。代表性的卷302在一些实施方案中类似于上文结合图1和图2所述的卷，其存储包含例如从客户接收的原始数据306的多个档案304，所述客户诸如数据存储系统或数据存储系统附接到的计算资源服务提供商的其他资源和/或服务的客户。档案304可结合上文结合图1和图2所述的技术之一来进行分类，并且关于分类顺序的信息可由例如与卷302直接或间接连接的资源来维持。相对于随机数据访问，卷302可驻留在针对顺序数据访问而优化的一个或多个存储装置上(或由其组成)。

[0046] 如前所述，在一些实施方案中，可结合例如将要存储档案的顺序来生成一个或多个标记308，如先前结合所述分类确定的。索引可以是单个索引或者可以是多部分索引，并且可以是任何适当的架构，并且可根据任何适当的方法来生成。例如，索引可以是位图索引、密集索引、稀疏索引或反向索引。使用多个标记的实施方案可根据例如将要存储在卷302中的档案304的特性来实现不同类型的标记。例如，卷302可为特定大小的档案利用密集索引(索引本身的大小相对于存储在给定卷上的档案的数量可能较小)，并且还可为所述特定大小的档案生成稀疏索引(索引大小与档案大小的比例增加)。

[0047] 在使用稀疏标记的实施方案中，给定卷的稀疏索引308可指向子索引310，其继而标记所述卷上的代表性位置。子索引310可以是指向以预定间隔驻留的数据的抽象概念。在一些实施方案中，子索引310可以是附加数据或元数据，其与卷相关联地(或在一些实施方案中，直接在此卷上)并且以预定间隔存储。在这类实施方案中，可设想的是，子索引310可以与上文结合图1和图2针对索引和档案的原始数据所述的类似方式作为碎片的部分存储在卷上。

[0048] 在一些实施方案中，预定间隔可以是块、字节或其他数据单位。例如，子索引可识别将要(例如，独立于档案本身的边界和/或数量)在卷的每x个块或字节处定位的档案。在一些实施方案中，预定间隔可通过卷的数量来描述。例如，子索引可指向将要存储在卷302上的每一第n个档案。如可设想的，稀疏索引308(并且在一些实施方案中，子索引310)可在档案304与这种存储同时存储之前或者在这种存储之后的时间生成和/或写入。在一些实施方案中，稀疏索引308和子索引310可例如在已存储档案304之后存储在卷上的保留空间中。

[0049] 在一些实施方案中，稀疏索引308与关于档案304的预定分类顺序的信息结合使用，以便定位特定档案。如前所述，这种分类顺序相关信息可驻留在卷302上，或者在一些实施方案中可驻留在与卷302分离的实体上，诸如在计算资源服务提供商的数据存储区或其他资源中。请求存储在卷302上的给定档案的实体可基于分类顺序相关信息并通过读取索引308来确定相继在卷302上的所请求的档案之前的最近的子索引。请求的实体可随后使卷302从所述子索引310的位置顺序地读取，直到所请求的档案被定位并被完全读取。

[0050] 在采用多种类型的标记的实施方案中，请求的实体可基于评估用于在第一实例中部署多种类型的标记的标准来最初确定哪些标记包含用于请求档案的最有效的位置信息。例如，如果特定大小的档案以稀疏索引进行索引，并且等于或大于此大小的档案被以平行密集索引进行索引，那么请求的实体可首先确定所请求的档案的大小，并且如果所请求的档案大于或等于上述大小边界，就可使用密集索引来支持稀疏索引，以便更快地获得所请求档案的精确位置。

[0051] 图4示意性地示出根据一些实施方案的用于处理、索引、存储和检索存储在数据存储系统上的数据的示例性过程。在步骤402处，诸如实现用于存储档案的冗余码的数据存储系统的资源基于例如将要应用于档案的冗余码来确定多个卷中的哪个子集(例如，数量)是必需的，以便重新创建将要存储的原始数据。例如，根据上文结合至少图1和图2所描述的技术，这种信息可通过预先确定纠删码的参数而得到，所述参数具有重新生成原始数据所需的碎片的特定比率，从其导出通过应用纠删码而生成的碎片的总数。

[0052] 在步骤404处，将原始数据，诸如从例如数据存储系统或计算资源服务提供商的客户接收的档案的原始数据如上文结合图1和图2进一步详细描述的那样通过例如数据存储系统或相关联实体来进行分类。例如，如前所述，分类顺序可在传入数据的一个或多个属性上实现。

[0053] 在步骤406处，针对原始数据，由例如数据存储系统生成一个或多个标记，诸如稀疏标记。如先前结合至少图1至图3所讨论的，对于给定卷可存在多于一个索引，并且这类并行索引可根据档案和/或正在存储的原始数据的性质而具有不同的类型。

[0054] 在步骤408处，将原始数据例如由数据存储系统存储在结合步骤402确定的卷的子集上，并且按步骤404中确定的顺序来存储。此外，在步骤410处，将在步骤406中生成的索引例如通过数据存储系统而存储在适当的实体上。如前所述，索引可被存储为其上存储原始数据的碎片的一部分，或者在一些实施方案中，可存储在与维持所述卷的资源分开的资源上。

[0055] 在步骤412处，将冗余码例如通过数据存储系统而应用到确定的卷的子集(例如，如先前结合图1至图3所讨论的碎片)，并且将包含从冗余码的应用派生的数据的附加碎片存储在结合步骤402确定的子集之外的预定量的卷上。例如，如前所述，存储原始数据的卷(例如，碎片)与总卷量(包括存储在本步骤412中生成的派生数据的那些卷)的比率可由本文应用的冗余码的恢复/编码比率来指定。

[0056] 在步骤414处，在正常操作中，可直接从存储原始数据的卷的子集中例如通过数据存储系统来检索所请求的数据，而不需要(例如通过冗余码来)从存储在步骤412中生成的派生数据的卷中进行检索和进一步处理。然而，在步骤416处，如果确定任何卷例如由数据存储系统不可用，那么数据存储系统可通过从剩余碎片的定数重构原始数据来生成替换碎片，并且使用冗余码重新编码以产生替换碎片。如先前结合图1至图3所讨论的，替换碎片可与被检测为不可用的碎片相同或不同。

[0057] 图5示意性地示出根据一些实施方案的用于索引存储在冗余编码数据存储系统上的原始数据的示例性过程。在步骤502处，类似于结合图4描述的过程400的步骤404，通过例如数据存储系统来处理原始数据，以确定在卷上包含原始数据的档案的存储顺序。如上文结合图1至图4所讨论的，关于分类顺序的信息可维持在例如卷上或者与所述卷分开的实体上。

[0058] 在步骤504处，由例如数据存储系统生成一个或多个标记，诸如稀疏标记，并且指向识别此卷上的预定位置的子索引。可基于特定实现方式的参数(诸如卷的大小、(例如，顺序地)读取和/或写入卷的速度、每个卷的档案数等)来预先确定位置。如前所述，子索引可以是抽象概念，或者在一些实施方案中，可以是存储在所述卷上或与所述卷相关联的数据或元数据元素。

[0059] 在步骤506处，将在步骤502中分类的原始数据通过数据存储系统存储在卷上，其中子索引与在步骤504中提到的预定位置相关联、指向或存储在所述预定位置处。在步骤508处，将在步骤504中生成的索引通过数据存储系统存储在与卷相关联的资源上，或者在一些实施方案中，根据上文结合至少图1至图4描述的技术而存储在卷本身上。

[0060] 在步骤510处，对于存储在卷上的原始数据的子集，通过卷或者与卷相关联的数据存储系统来接收诸如来自客户端实体或连接到数据存储系统和/或卷的其他实体的请求。如前所述，数据存储系统和/或请求实体可访问关于在步骤502中确定的原始数据的分类顺序的信息，并且在利用稀疏索引的实施方案中，可在步骤512处使用索引来定位适当的子索引。如前所述，在一些实施方案中，适当的子索引是由相继在卷上所存储的原始数据的所请求子集之前的子索引标记的最接近的位置。一旦在步骤512中确定子索引，那么在步骤514处，从由适当的子索引所指示的位置(例如，通过实现卷的数据存储系统或存储装置)顺序地读取卷，直到定位并检索到原始数据的所请求的子集。

[0061] 图6示出根据至少一个实施方案的连接到计算资源服务提供商的客户的实例。计算资源服务提供商602可向客户604提供各种服务，并且客户604可通过接口626与计算资源服务提供商602通信，所述接口626可以是web服务接口或任何其他类型的客户接口。虽然图6示出用于计算资源服务提供商602的服务的一个接口626，但是每个服务可具有其自己的接口，并且通常服务的子集可具有除了接口626之外的或作为接口626的替代的对应的接口。客户604可以是可利用由计算资源服务提供商602提供的一个或多个服务来为其员工维护并传递信息的可位于各种地理位置处的组织。另外，客户604可以是利用计算资源服务提供商602的服务将内容递送到远程定位的工作组的个体。如图6所示，客户604可通过网络
606与计算资源服务提供商602通信，由此网络606可以是诸如互联网、内联网或互联网服务供应商(ISP)网络的通信网络。从客户604到计算资源服务提供商602的一些通信可致使计算资源服务提供商602根据所描述的一个或多个实施方案或其变型来进行操作。

[0062] 计算资源服务提供商602可向其客户提供各种计算资源服务。在此实例中，由计算资源服务提供商602提供的服务包括虚拟计算机系统服务608、块级数据存储服务610、密码服务612、按需数据存储服务614、通知服务616、认证系统618、策略管理服务620、任务服务622、以及一种或多种其他服务624。应注意，并非所描述的所有实施方案都包括参考图6描述的服务608-624，并且除了明确描述的服务之外或作为其替代，可提供附加服务。如所描述的，服务608-624中的每一个可包括使得客户604能够通过web服务请求向各种服务提交适当配置的API调用的一个或多个web服务接口。此外，每种服务可包括一个或多个服务接口，所述一个或多个服务接口使服务能够彼此相互访问(例如，使虚拟计算机系统服务608的虚拟计算机系统能够将数据存储在按需数据存储服务614中或检索来自按需数据存储服务614的数据，和/或访问由块级数据存储服务610提供的一个或多个块级数据存储装置)。

[0063] 虚拟计算机系统服务608可以是被配置来代表客户604实例化虚拟机实例的计算资源的集合。客户604可与虚拟计算机系统服务608(通过适当配置和认证的API调用)交互，以提供和操作在由计算资源服务提供商602托管和操作的物理计算装置上实例化的虚拟计算机系统。虚拟计算机系统可用于各种目的，诸如作为支持网站的服务器来操作、操作业务应用程序，或者一般地，充当客户的计算能力。用于虚拟计算机系统的其他应用可用来支持数据库应用、电子商务应用、业务应用和/或其他应用。虽然在图6中示出虚拟计算机系统服务608，但是可在计算资源服务提供商602中利用任何其他计算机系统或计算机系统服务，诸如不采用虚拟化或实例化的计算机系统或计算机系统服务，而是在专用或共享计算机/服务器和/或其他物理装置上提供计算资源。

[0064] 块级数据存储服务610可包括一个或多个计算资源，所述一个或多个计算资源共同操作以使用块级存储装置(和/或其虚拟化)来为客户604存储数据。块级数据存储服务610的块级存储装置可例如可操作地附接到由虚拟计算机系统服务608提供的虚拟计算机系统，以用作所述计算机系统的逻辑单元(例如虚拟驱动器)。块级存储装置可使得能够永久存储由对应的虚拟计算机系统使用/产生的数据，其中虚拟计算机系统服务608仅可提供短暂的数据存储。

[0065] 计算资源服务提供商602还包括密码服务612。密码服务612可利用计算资源服务提供商602的一个或多个存储服务来以加密形式存储客户的密钥，由此密钥可用于解密客户612的仅可由密码服务612的特定装置访问的密钥。

[0066] 计算资源服务提供商602还包括按需数据存储服务614。按需数据存储服务614可以是被配置来同步地处理存储和/或访问数据的请求的计算资源的集合。按需数据存储服务614可使用使得按需数据存储服务614能够快速定位和检索数据的计算资源(例如，数据库)来操作，以允许响应于对数据的请求来提供数据。例如，按需数据存储服务614可维持存储的数据，其方式使得当检索到对数据对象的请求时，可响应于所述请求来提供数据对象(或者可开始数据对象的流式传输)。如上所述，存储在按需数据存储服务614中的数据可被组织成数据对象。除了可能对大小进行某些限制之外，数据对象可具有任意大小。因此，按需数据存储服务614可存储不同大小的多个数据对象。按需数据存储服务614可操作为将数据对象与数据对象的标识符相关联的键值存储区，所述数据对象的标识符可由客户604使用，以检索或执行与由按需数据存储服务614存储的数据对象有关的其他操作。

[0067] 在图6所示的环境中，包括通知服务616。通知服务616可包括共同配置来提供web服务或其他接口和基于浏览器的管理控制台的计算资源的集合。管理控制台可用于对客户寻求以接收通知、配置应用程序(或人员)、订阅客户端主题、发布消息或配置通过客户端选择的协议(即超文本传输协议(HTTP)、电子邮件和短消息服务(SMS)等)的消息递送的主题进行配置。通知服务系统616可使用“推送”机制为客户端提供通知，而不需要为新信息和更新定期检查或“轮询”。通知服务616还可用于各种目的，诸如监控虚拟计算机系统服务608中执行的应用程序、工作流程系统、对时间敏感的信息的更新、移动应用程序和许多其他应用程序。

[0068] 如图6中所示，在各种实施方案中，计算资源服务提供商602包括认证系统618和策略管理服务620。在一个实施方案中，认证系统618是被配置来执行涉及对客户的用户进行认证的操作的计算机系统(即，计算资源的集合)。例如，服务608-616和620-624中的一个可将来自用户的信息提供给认证系统618，以作为回报接收指示用户请求是否是可信的信息。

[0069] 策略管理服务620在一个实施方案中是被配置来代表计算资源服务提供商602的客户(诸如客户604)来管理策略的计算机系统。策略管理服务620可包括使得客户能够提交与策略管理有关的请求的接口。这类请求例如可以是增加、删除、更改或另外修改用于客户的策略的请求，或针对其他管理动作(诸如提供现有策略的库存等)的请求。

[0070] 在各种实施方案中，计算资源服务提供商602还配备有任务服务622。任务服务622被配置来从客户604接收任务包并且使得能够如任务包所指示地执行任务。任务服务622可被配置来使用计算资源服务提供商602的任何资源来执行任务，诸如一个或多个实例化的虚拟机或虚拟主机。任务服务624可配置一个或多个实例化的虚拟机或虚拟主机以根据客户604的要求来使用所选择的操作系统和/或选择的执行应用来操作。

[0071] 计算资源服务提供商602至少部分地基于其客户604的需要另外维护一个或多个其他服务624。例如，计算资源服务提供商602可维持用于其客户604的数据库服务。数据库服务可以是计算资源的集合，所述数据库服务共同操作来运行用于一名或多名客户604的一个或多个数据库。客户604可通过利用适当配置的API调用来操作和管理来自数据库服务的数据库。这继而可允许客户604维持并潜在地按比例调节数据库中的操作。其他服务包括但不限于对象级存档数据存储服务、管理和/或监测其他服务的服务。

[0072] 计算资源服务提供商602还包括档案存储服务624。档案存储服务624可包括共同操作来提供用于数据归档和客户数据备份的存储的计算资源的集合。数据可包括可被组合以形成档案的一个或多个数据文件。档案存储服务624可被配置来持续地存储可能不经常访问的数据，并且对所述数据的长的检索时间对于利用档案存储服务624的客户来说是可接受的。客户可与档案存储服务624(例如，通过适当配置的对档案存储服务624进行的API调用)进行交互，以生成一个或多个档案、上传并检索一个或多个档案或者监视一个或多个档案的生成、上传或检索。

[0073] 计算资源服务提供商602至少部分地基于其客户604的需要另外维护一个或多个其他服务626。例如，计算资源服务提供商602可维持用于其客户604的数据库服务。数据库服务可以是计算资源的集合，所述数据库服务共同操作来运行用于一名或多名客户604的一个或多个数据库。客户604可通过利用适当配置的API调用来操作和管理来自数据库服务的数据库。这继而可允许客户604维持并潜在地按比例调节数据库中的操作。其他服务包括但不限于对象级存档数据存储服务、管理和/或监测其他服务的服务。

[0074] 图7示出根据各种实施方案的数据存储服务的说明性实例。数据存储服务700可以是用于操作诸如上文结合图6所述的按需数据存储服务的计算资源提供商的服务。如图7所示，数据存储服务700包括各种子系统，诸如请求处理子系统702和管理子系统704。数据存储服务700还可包括多个数据存储服务器706和元数据存储装置708，元数据存储装置708可存储关于存储在所述数据存储服务器706中的各种数据对象的元数据。在一个实施方案中，请求处理子系统702是计算资源的集合，诸如共同配置来处理提交给数据存储服务700的请求的web服务器和应用服务器。请求处理子系统702例如可包括提供web服务接口以使得数据存储服务700的客户能够提交将要由数据存储服务700处理的请求的一个或多个web服务器。请求处理子系统702可包括被配置来进行与请求的处理相关的各种确定的计算机系统，诸如策略是否允许满足请求、请求是否是真实的(例如，使用合适的密钥来进行电子签名)等等。

[0075] 请求处理子系统的部件可与数据存储服务700的其他部件(例如，通过网络通信)进行交互。例如，提交给请求处理子系统702的一些请求可涉及可包括由数据存储服务器706存储的数据对象的计算资源的管理。请求处理子系统702例如可接收并处理用于修改计算资源的请求。例如，在一些实例中，数据对象被逻辑地组织成逻辑数据容器。与逻辑数据容器相关联的数据对象可例如被认为在逻辑数据容器中。对数据处理子系统702的请求可包括用于创建逻辑数据容器、删除逻辑数据容器、提供逻辑数据容器的库存、提供或更新关于一个或多个逻辑数据容器的访问控制策略等的请求。

[0076] 所述请求在由请求处理子系统702接收时可由管理子系统704进行处理。如果适用，由请求处理子系统702和/或管理子系统704处理的各种请求可导致管理子系统704更新与数据对象和存储在元数据存储区708中的逻辑数据容器相关联的元数据。可由请求处理子系统702处理的其他请求包括用于执行与数据对象相关的操作的请求。例如，请求可包括用于将数据对象上传到数据存储服务700、用于从数据存储服务700下载数据对象、用于删除由数据存储服务700存储的数据对象和/或可执行的其他操作的请求。

[0077] 由请求处理子系统702处理的涉及数据对象的操作(上传、下载、删除等)的请求可包括请求处理子系统702与一个或多个数据存储服务器706之间的交互。数据存储服务器706可以是与用于数据对象的持久化的一个或多个存储装置通信地耦合的计算机系统。例如，为了处理上传数据对象的请求，请求处理子系统可向数据存储服务器706传输数据以便进行永久存储。然而，应注意，在一些实施方案中，客户端(例如，客户)计算机系统可直接将数据传输到数据存储服务器706，而不是通过请求处理子系统中的服务器。

[0078] 在一些实施方案中，请求处理子系统702将数据传输到多个数据存储服务器706，以用于冗余存储数据的目的，以允许在单个数据存储服务器706和/或相关联的数据存储装置发生故障的情况下可恢复数据。例如，在一些实施方案中，请求处理子系统使用诸如纠删编码的编码方案中的冗余性来将数据对象解构成存储在数据存储服务器706中的多个部分。所述部分可被配置成使得如果对特定数量的部分的访问丢失，然而仍可从保持可访问的剩余部分重构数据对象。

[0079] 为了能够在请求处理子系统702与数据存储服务器706之间有效地传输数据和/或通常能够快速处理请求，请求处理子系统702可包括一个或多个数据库，所述一个或多个数据库实现在数据存储服务器706中的数据的位置。例如，请求处理子系统702可操作键值存储库，所述键值存储库用于将数据对象的标识符与数据存储服务器706中的位置相关联，以便访问数据对象的数据。

[0080] 图8示出用于实现根据各个实施方案的各方面的示例性环境800的各方面。如将了解，尽管出于解释目的使用基于web的环境，但是可视情况使用不同环境来实现各个实施方案。环境包括电子客户端装置802，所述电子客户端装置802可包括可操作来通过适当网络804发送和/或接收请求、消息或信息并且在一些实施方案中将信息传送回装置用户的任意适当装置。此类客户端装置的实例包括个人计算机、手机、手持式消息传送装置，膝上型计算机、平板计算机、机顶盒，个人数据助理、嵌入式计算机系统、电子书阅读器等。网络可包括任意适当网络，包括内部网、互联网、蜂窝网、局域网、卫星网或任意其他此类网络和/或上述网络的组合。用于这种系统的部件可至少部分地取决于所选择的网络和/或环境的类型。用于通过此类网络通信的协议和部件是众所周知的，因而本文将不再详细论述。通过网络的通信可通过有线或无线连接及其组合来实现。在此实例中，网络包括互联网，因为环境包括用于接收请求并且响应于所述请求而提供内容的web服务器806，但是对于其他网络来说，可使用服务类似目的替代装置，如本领域普通技术人员所显而易见的。

[0081] 说明性环境包括至少一个应用服务器808和数据存储区810。应当理解，可存在可链接起来或以其他方式配置的若干应用服务器、层或其他元件、过程或部件，这些应用服务器、层或其他元件、过程或部件可交互来执行诸如从适当的数据存储区获得数据的任务。如本文所使用的服务器可以各种方式实现，诸如硬件装置或虚拟计算机系统。在一些上下文中，服务器可指在计算机系统上执行的编程模块。如本文所使用的，除非另行指出或从上下文中明确可知，术语“数据存储区”是指能够存储、访问和检索数据的任意装置或装置组合，所述装置或装置组合可包括任意标准、分布式、虚拟或集群式环境中的任意组合和任意数目的数据服务器、数据库、数据存储装置和数据存储介质。应用服务器可包括任何适当硬件、软件和固件，所述硬件、软件和固件视执行客户端装置的一个或多个应用程序的各方面的需要而与数据存储区集成、处理应用程序的一些或所有数据访问和业务逻辑。应用程序服务器可提供与数据存储区协作的存取控制服务，并且能够生成可用于提供给用户的内容，所述内容包括但不限于文本、图片、音频、视频和/或其他内容，所述内容可以超文本标记语言(“HTML”)、可扩展标记语言(“XML”)、JavaScript、层叠样式表(“CSS”)或另一种适当客户端结构化语言的形式由web服务器提供给用户。传送给客户端装置的内容可由客户端装置处理，以便提供呈一种或多种形式的内容，所述形式包括但不限于用户可通过听觉、视觉和/或通过其他感觉(包括触觉、味觉和/或嗅觉)来感知的形式。全部请求和响应的处理以及客户端装置802与应用服务器808之间的内容递送可由web服务器使用以下PHP来处理：在这个实例中为超文本预处理器(“PHP”)、Python、Ruby、Perl、Java、HTML、XML或另一种适当服务器端结构化语言。应当理解，web服务器和应用服务器不是必要的，且仅仅是示例性部件，因为本文所论述的结构化代码可在如本文其他地方所论述的任意适当装置或主机上执行。此外，除非上下文另外清楚规定，否则如由单个装置执行的本文所述的操作可由可形成分布式和/或虚拟系统的多个装置共同执行。

[0082] 数据存储区810可包括用于存储与本公开的特定方面相关的数据的若干单独数据表、数据库、数据文档、动态数据存储方案和/或其他数据存储机构和介质。例如，所示数据存储区可包括用于存储生成数据812和用户信息816的机构，生成数据812和用户信息816可用于提供用于生成端的内容。数据存储区还被示出为包括用于存储日志数据814的机构，日志数据814可用于报告、分析或其他此类目的。应当理解，可能存在可能需要存储在数据存储区中的许多其他方面，如页面图像信息和访问权信息，所述方面可视情况存储在上文列出的机构中的任意机构中或存储在数据存储810中的额外机构中。数据存储区810可通过与其相关联的逻辑来操作，以便从应用服务器808接收指令，并且响应于所述指令而获得、更新或以其他方式处理数据。应用程序服务器808可响应于所接收指令提供静态数据、动态数据或静态数据和动态数据的组合。动态数据(诸如web日志(博客)、购物应用程序、新闻服务以及其他这类应用程序中使用的数据)可由如本文所描述的服务器端结构化语言生成，或者可由在应用程序服务器上操作或在其控制下的内容管理系统(“CMS”)提供。在一个实例中，用户通过由用户操作的装置可提交针对某种类型的项目的搜索请求。在这种情况下，数据存储区可能访问用户信息来验证用户的身份，并且可访问目录详细信息以获得关于所述类型的项目的信息。随后，可将信息诸如以网页上的结果列表的形式返回给用户，用户能够通过用户装置802上的浏览器来查看所述网页。可在浏览器的专用页面或窗口中查看感兴趣的特定项目的信息。然而，应当注意，本公开的实施方案不一定限于网页的上内容，但是可更一般地适用于处理基本请求，其中请求不一定是针对内容的请求。

[0083] 每个服务器通常将包括提供用于此服务器的基本管理和操作的可执行程序指令的操作系统，并且通常将包括计算机可读存储介质(例如，硬盘、随机存取存储器、只读存储器等)，其存储当由服务器的处理器执行时允许服务器执行其预期功能的指令。服务器的操作系统和基本功能的合适实现方式是已知的或可商购获得的，并且由本领域普通技术人员特别是根据本文的本公开而容易地实现。

[0084] 在一个实施方案中，环境是利用通过通信链路、使用一个或多个计算机网络或直接连接来互连的多个计算机系统和部件的分布式和/或虚拟计算环境。然而，本领域普通技术人员应了解，这种系统可在具有比图8中所示的部件更少或更多数量的部件的系统中同样顺利地操作。因此，图8中的系统800的描绘本质上应视为说明性的，并且不限制本公开的范围。

[0085] 各种实施方案还可在各种各样的操作环境中实现，所述操作环境在一些情况下可包括可用于操作多个应用中的任何一个的一个或多个用户计算机、计算装置或处理装置。用户或客户端装置可包括许多通用个人计算机中的任何一个，诸如运行标准操作系统的台式机、膝上计算机或平板计算机，以及运行移动软件的蜂窝、无线和手持装置，并且能够支持多个网络和消息传送协议。这种系统还可包括运行多种可商购获得的操作系统和其他已知应用程序中的任何一种的许多工作站，以用于诸如开发和数据库管理的目的。这些装置还可包括其他电子装置，诸如虚拟终端、瘦客户端、游戏系统和能够通过网络进行通信的其他装置。这些装置还可包括虚拟装置，诸如虚拟机、管理程序和能够通过网络通信的其他虚拟装置。

[0086] 本公开的各种实施方案利用本领域技术人员可能熟悉的至少一种网络来支持使用多种可商购得的协议中的任一种进行通信，所述协议诸如传输控制协议/互联网协议(″TCP/IP″)、用户数据报协议(″UDP″)、在开放系统互连(″OSI″)模型的各个层中操作的协议、文件传送协议(″FTP″)、通用即插即用(″UpnP″)、网络文件系统(″NFS″)、公共互联网文件系统(″CIFS″)以及AppleTalk。网络可以是例如局域网、广域网、虚拟专用网、互联网、内部网、外部网、公共交换电话网、红外网、无线网、卫星网以及上述网络的任何组合。

[0087] 在利用web服务器的实施方案中，web服务器可以运行多种服务器或中间层级应用程序中的任一种，包括超文本传送协议(″HTTP″)服务器、FTP服务器、通用网关接口(″CGI″)服务器、数据服务器、Java服务器、Apache服务器和业务应用程序服务器。服务器还能够响应于来自用户装置的请求而执行程序或脚本，诸如通过执行可实现为以任何编程语言(诸如 C、C#或C++)或任何脚本语言(诸如Ruby、PHP、Perl、Python或TCL)以及其组合写成的一个或多个脚本或程序的一个或多个web应用程序。服务器也可包括数据库服务器，包括但不限于，可从 和 商购获得的数据库服务器、以及开源服务器(诸如MySQL、Postgres、SQLite、MongoDB)，以及能够存储、检索和访问结构化数据或非结构化数据的任何其他服务器。数据库服务器可包括基于表格的服务器、基于文件的服务器、非结构化服务器、关系式服务器、非关系式服务器或这些和/或其他数据库服务器的组合。

[0088] 环境可包括如上文所论述的各种各样的数据存储区以及其他存储器和存储介质。这些可驻留在各种位置，诸如在存储介质上，所述存储介质在一个或多个计算机的本地(和/或驻留在其中)，或者远离网络中的任何或所有计算机。在一组特定实施方案中，信息可驻留在本领域技术人员熟悉的存储区域网络(“SAN”)中。类似地，在适当情况下，用于执行归因于计算机、服务器或其他网络装置的功能的任何必要文件可在本地和/或远程存储。
在系统包括计算机化装置的情况下，每个这种装置可包括可通过总线电耦合的硬件元件，所述元件包括例如至少一个中央处理单元(“CPU”或“处理器”)、至少一个输入装置(例如，鼠标、键盘、控制器、触摸屏或小键盘)和至少一个输出装置(例如，显示装置、打印机或扬声器)。这种系统还可包括诸如磁盘驱动器，光存储装置和诸如随机存取存储器(“RAM”)或只读存储器(“ROM”)的固态存储装置、以及可移动媒体装置、存储卡、闪存卡等的一个或多个存储装置。

[0089] 此类装置还可包括计算机可读存储介质读取器、通信设备(例如，调制解调器、网卡(无线或有线)、红外线通信设备等)和如上所述的工作存储器。计算机可读存储介质读取器可与表示远程、本地、固定和/或可移动存储装置以及用于临时和/或更永久地包含、存储、发送和检索计算机可读信息的存储介质的计算机可读存储介质连接或被配置来接收所述计算机可读存储介质。系统和各种装置通常还将包括位于至少一个工作存储器装置内的许多软件应用、模块、服务或其他元件，包括诸如客户端应用或网络浏览器的操作系统和应用程序。应当理解，替代实施方案可具有与上述不同的许多变化。例如，还可使用定制硬件并且/或者特定元件可在硬件、软件(包括便携式软件，例如小程序)或两者中实现。此外，可采用与其他计算装置(诸如网络输入/输出装置)的连接。

[0090] 用于包含代码或代码部分的存储介质和计算机可读介质可包括本领域中已知或使用的任何适当的介质，所述介质包括存储介质和通信介质，诸如但不限于以任何方法或技术实现用于存储和/或传输信息的易失性和非易失性、可移动和不可移动介质，所述信息诸如计算机可读指令、数据结构、程序模块或其他数据，所述介质包括RAM、ROM、电可擦除可编程只读存储器(“EEPROM”)、闪速存储器或其他存储器技术、光盘只读存储器(“CD-ROM”)、数字通用盘(DVD)或其他光存储装置、磁带盒、磁带、磁盘存储装置或其他磁存储装置或者可用来存储所需信息并且可由系统装置访问的任何其他介质。基于本文所提供的公开内容和教义，本领域普通技术人员将了解实现各个实施方案的其他方式和/或方法。

[0091] 因此，说明书和附图相应地视为说明性而非限制性意义。然而，显而易见的是，在不脱离如权利要求所阐述的本发明的更广泛的精神和范围的情况下，可进行各种修改和改变。

[0092] 其他变化在本公开的精神内。因此，虽然所公开的技术易于进行各种修改和替代构造，但是其某些示出的实施方案在附图中示出并已在上文详细描述。然而，应当理解，不意图将本发明限制为所公开的一种多多种具体形式，相反，本发明旨在覆盖落入本发明的精神和范围内的所有修改、替代构造和等效物，如所附权利要求中所限定的。

[0093] 在描述公开的实施方案(特别是在所附权利要求的上下文中)的上下文中使用术语“一个”和“一种”以及“所述”以及类似的指示物应被解释为涵盖单数和复数，除非本文另外指明或上下文明显矛盾。术语“包括”、“具有”、“包含”和“含有”均被解释为开放式术语(即意味着“包括但不限于”)，除非另有说明。术语“连接的”在未经修改且涉及物理连接的情况下，应解释为部分地或整体地包含在内、附接到或接合在一起，即使会有一些物件介于其间。除非本文另有说明，否则本文的值的范围的叙述仅用于作为单独参考落在所述范围内的每个单独值的速记方法，并且将每个单独数值并入本说明书中，如同本文单独列举每个单独数值一样。术语“组”(例如，“一组项目”)或“子集”的使用除非另有说明或与上下文相矛盾，否则应被解释为包括一个或多个成员的非空集合。此外，除非另有说明或与上下文相矛盾，否则对应集合的术语“子集”不一定表示对应集合的适当子集，但子集和对应集合可相等。

[0094] 除非另外特别规定或另外与上下文矛盾，否则连接性语言，诸如具有形式“A、B、以及C中的至少一个”或“A、B以及C中的至少一个”的短语与上下文一起理解为一般用来呈现项目、术语等可以是A或B或C，或A和B和C的集合的任何非空子集。例如，在具有三个成员的集的说明性实例中，连接性短语“A、B、和C中的至少一个”和“A、B和C中的至少一个”是指以下集中的任一集：{A}、{B}、{C}、{A，B}、{A，C}、{B，C}、{A，B，C}。因此，此类连接性语言一般并非意图暗示某些实施方案需要A中的至少一个、B中的至少一个以及C中的至少一个每个存在。

[0095] 本文所描述的进程的操作可以任何合适的顺序执行，除非本文另外指明或者否则上下文明显矛盾。本文所描述的进程(或其变型和/或其组合)可在配置有可执行指令的一个或多个计算机系统的控制下执行，并且可被实现为通过硬件或其组合在一个或多个处理器上共同执行的代码(例如，可执行指令、一个或多个计算机程序或一个或多个应用程序)。代码可存储在计算机可读存储介质上，例如以包括可由一个或多个处理器执行的多条指令的计算机程序的形式进行存储。计算机可读存储介质可以是非暂时性的。

[0096] 本文所提供的任何和所有实例或示例性语言(例如“诸如”)的使用仅旨在更好地说明本发明的实施方案，并且不对本发明的范围构成限制，除非另有说明。说明书中的任何语言都不应解读为指示任何未要求保护的要素是实施本发明所必需的。

[0097] 本文描述了本公开的实施方案，包括本发明人已知的用于执行本发明的最佳模式。在阅读前面的描述之后，这些实施方案的变型对于本领域普通技术人员来说可能变得显而易见。本发明人期望本领域技术人员在适当情况下使用这种变型，并且本发明人希望本公开的实施方案以不同于本文具体描述的方式来实施。因此，本公开的范围包括根据适用法律允许的所附权利要求中所述的主题的所有修改和等效物。此外，除非本文另外指明或者否则上下文明显矛盾，否则所有可能变型的上述元素的任何组合都包含在本公开的范围内。

[0098] 本文所引用的所有参考文献(包括出版物、专利申请和专利)据此以引用方式并入，其程度等同于每个参考文献单独地且具体地被表示为以引用方式并入本文并且以其全文在本文得以陈述。

[0099] 本公开的实施方案可鉴于以下条款来描述：

[0100] 1.一种计算机实现的方法，其包括：

[0101] 在被配置有可执行指令的一个或多个计算机系统的控制下，

[0102] 处理将要存储在多个卷上的多个档案，以便：

[0103] 根据由所述多个档案共享的至少一个标准来对所述多个档案进行分类；以及[0104] 确定所述分类的多个档案中的哪些档案将被存储在所述多个卷中的每个卷上；

[0105] 生成所述多个卷的索引，所述索引中的每个索引反映将要存储在所述多个卷中的相应卷上的所述分类的多个档案的子集；

[0106] 将所述分类的多个档案和所述生成的索引存储在所述多个卷的子集上，从而生成多个碎片；

[0107] 将冗余码应用至所述分类的多个档案和所述生成的索引以生成编码的碎片；以及[0108] 将所述编码的碎片存储在所述多个卷的所述子集外的对应卷上。

[0109] 2.如条款1所述的计算机实现的方法，其还包括通过从所述多个卷的所述子集中检索所述子集来响应对所述原始数据的至少一个子集的请求。

[0110] 3.如条款1或2所述的计算机实现的方法，其还包括如果所述多个碎片中的碎片被检测为不可用，使用具有所述多个碎片的子集的所述编码的碎片中的至少一个来重新生成所述不可用碎片。

[0111] 4.如条款1-3中任一项所述的计算机实现的方法，其中所述冗余码是包含单位矩阵的纠删码。

[0112] 5.一种系统，其包括：

[0113] 至少一个计算装置，所述至少一个计算装置被配置来实现一个或多个服务，其中所述一个或多个服务被配置来：

[0114] 以预定顺序对多个档案进行分类，以便以所述预定顺序存储在多个卷上；

[0115] 使用冗余码来处理所述多个档案，以便生成多个碎片，所述多个碎片的子集包括所述多个档案的原始数据；以及

[0116] 将所述碎片存储在所述多个卷上，以使得所述多个卷的子集包含所述原始数据。

[0117] 6.如条款5所述的系统，其中所述碎片被存储成使得所述多个档案中的相应档案的所述原始数据被完全存储在所述多个卷的所述子集的单个卷内。

[0118] 7.如条款5或6所述的系统，其中所述碎片被存储成使得所述多个档案中的相应档案的所述原始数据被存储在所述多个卷的所述子集的至多两个卷内。

[0119] 8.如条款5-7中任一项所述的系统，其中所述一个或多个服务包括由所述系统提供的档案存储服务。

[0120] 9.如条款5-8中任一项所述的系统，其中所述多个卷中的每个卷对应于多个存储装置中的一个存储装置。

[0121] 10.如条款5-9中任一项所述的系统，其中所述一个或多个服务还被配置来生成所述多个卷的索引，所述索引中的每个索引反映将要存储在所述多个卷中的相应卷上的所述分类的多个档案的子集。

[0122] 11.如条款10所述的系统，其中所述一个或多个服务还被配置来：

[0123] 使用所述冗余码来处理所述索引，以便将所述索引中的每个索引包含在相应的碎片中；以及

[0124] 存储所述碎片，以使得所述多个卷中的每个卷包含所述处理的索引中的相应索引。

[0125] 12.如条款5-11中任一项所述的系统，其中所述一个或多个服务还被配置来如果所述多个碎片的所述子集中的碎片被检测为不可用，使用所述多个碎片的第二子集来重新生成使用所述冗余码的所述不可用碎片。

[0126] 13.一种非暂时性计算机可读存储介质，其具有存储在其上的可执行指令，所述可执行指令当由计算机系统的一个或多个处理器执行时，致使所述计算机系统至少：

[0127] 确定其中多个档案将要被存储在多个卷上的所述多个档案的顺序；

[0128] 通过向至少所述多个档案应用冗余码来生成多个碎片，所述多个碎片中的每个碎片对应于所述多个卷中的卷，以使得：

[0129] 所述多个碎片的子集包含所述多个档案的原始数据，并且

[0130] 所述多个碎片的所述子集被存储在所述多个卷上，以使得所述多个档案被以所述多个碎片的所述子集内的所述确定的顺序来表示；以及

[0131] 将所述多个碎片存储在所述多个卷中的对应卷上。

[0132] 14.如条款13所述的非暂时性计算机可读存储介质，其中所述指令还包括当由所述一个或多个处理器执行时致使所述计算机系统生成所述多个卷的索引的指令，所述索引中的每个索引反映将要以所述确定的顺序存储在所述多个卷中的相应卷上的多个档案的子集。

[0133] 15.如条款14所述的非暂时性计算机可读存储介质，其中所述指令还包括当由所述一个或多个处理器执行时致使所述计算机系统通过进一步将所述冗余码应用于所述索引来生成所述多个碎片以便在所述多个碎片中的每个碎片中包含相应的索引的指令。

[0134] 16.如条款13-15中任一项所述的非暂时性计算机可读存储介质，其中所述指令还包括在由所述一个或多个处理器执行时致使所述计算机系统通过对具有所述计算机系统的一个或多个客户的共同所有权的所述多个档案的子集进行分组来确定所述多个档案的所述顺序的指令。

[0135] 17.如条款13-16中任一项所述的非暂时性计算机可读存储介质，其中所述指令还包括在由所述一个或多个处理器执行时致使所述计算机系统通过经由多个属性将所述多个档案顺序分类来确定所述多个档案的所述顺序的指令。

[0136] 18.如条款13-17中任一项所述的非暂时性计算机可读存储介质，其中所述指令还包括在由所述一个或多个处理器执行时致使所述计算机系统通过经由所述多个档案中的每个档案由所述计算机系统接收的时间对所述多个档案进行分类来确定所述多个档案的所述顺序的指令。

[0137] 19.如条款13-18中任一项所述的非暂时性计算机可读存储介质，其中所述指令还包括在由所述一个或多个处理器执行时致使所述计算机系统如果所述多个碎片中的碎片被检测为不可用，使用所述多个碎片中的剩余碎片的至少子集来重新生成所述不可用碎片的指令。

[0138] 20.如条款13-19中任一项所述的非暂时性计算机可读存储介质，其中所述冗余码是纠删码，所述纠删码当应用于所述多个档案时生成所述多个碎片的所述子集，以使得所述子集对应于包含所述原始数据的单位矩阵。