公开(公告)号：US20130046949A1

公开(公告)日：2013-02-21

申请号：US13211288

申请日：2011-08-16

申请人： John Colgrove ,  John Hayes ,  Ethan Miller ,  Cary Sandvig

发明人： John Colgrove ,  John Hayes ,  Ethan Miller ,  Cary Sandvig

IPC分类号： G06F12/00

CPC分类号： G06F3/0644 ,  G06F3/0608 ,  G06F3/0619 ,  G06F3/064 ,  G06F3/065 ,  G06F3/0665 ,  G06F3/0668 ,  G06F3/067

摘要： A system and method for maintaining a mapping table in a data storage subsystem. A data storage subsystem supports multiple mapping tables. Records within a mapping table are arranged in multiple levels which may be logically ordered by time. Each level stores pairs of a key value and a pointer value. New records are inserted in a created new (youngest) level. All levels other than the youngest may be read only. In response to detecting a flattening condition, a data storage controller is configured to identify a group of two or more adjacent levels of the plurality of levels for flattening which are logically adjacent in time. A new level is created and one or more records stored within the group are stored in the new level, in response to detecting each of the one or more records stores a unique key among keys stored within the group.

摘要翻译： 一种用于在数据存储子系统中维护映射表的系统和方法。 数据存储子系统支持多个映射表。 映射表内的记录以多个级别排列，可以按时间逻辑排序。 每个级别存储键值和指针值的对。 新记录插入到创建的新（最年轻）级别中。 除最小的以外的所有级别可能只读。 响应于检测到平坦化状况，数据存储控制器被配置为识别在时间上在逻辑上相邻的用于平坦化的多个级别中的两个或更多个相邻级别的组。 响应于检测到一个或多个记录中的每一个在存储在组内的密钥之间存储唯一密钥，创建新级别并存储在组内的一个或多个记录在新级中。

公开(公告)号：US08719540B1

公开(公告)日：2014-05-06

申请号：US13421336

申请日：2012-03-15

申请人： Ethan Miller ,  John Colgrove ,  John Hayes ,  Cary Sandvig

发明人： Ethan Miller ,  John Colgrove ,  John Hayes ,  Cary Sandvig

IPC分类号： G06F12/00 ,  G06F13/00

CPC分类号： G06F3/0608 ,  G06F3/061 ,  G06F3/0619 ,  G06F3/064 ,  G06F3/0664 ,  G06F3/0665 ,  G06F3/0683 ,  G06F3/0689 ,  G06F12/00 ,  G06F12/0292 ,  G06F12/06 ,  G06F12/10 ,  G06F12/1009 ,  G06F12/1027 ,  G06F2212/1044

摘要： A system, method, and computer-readable storage medium for mapping block numbers within a region to physical locations within a storage system. Block numbers are mapped within a region according to a fractal-based space-filling curve. If the region is not a 2k by 2k square, then the region is broken up into one or more 2k by 2k squares. Any remaining sub-region is centered within a 2k by 2k square, the 2k by 2k square is numbered using a fractal-based space-filling curve, and then the sub-region is renumbered by assigning numbers based on the order of the original block numbers of the sub-region.

摘要翻译： 一种用于将区域内的块号映射到存储系统内的物理位置的系统，方法和计算机可读存储介质。 块号根据基于分形的空间填充曲线在一个区域内映射。 如果该区域不是2k乘2k平方，那么该区域被分解成一个或多个2k乘2k的正方形。 任何剩余的子区域居中在2k×2k平方的范围内，使用基于分形的空间填充曲线编号2k×2k平方，然后通过基于原始块的顺序分配编号来重新编号子区域 子区域的数量。

公开(公告)号：US20130097380A1

公开(公告)日：2013-04-18

申请号：US13273858

申请日：2011-10-14

申请人： John Colgrove ,  John Hayes ,  Ethan Miller ,  Joseph S. Hasbani ,  Cary Sandvig

发明人： John Colgrove ,  John Hayes ,  Ethan Miller ,  Joseph S. Hasbani ,  Cary Sandvig

IPC分类号： G06F12/02 ,  G06F12/08 ,  G06F7/00

CPC分类号： G06F17/30371 ,  G06F3/0608 ,  G06F3/0619 ,  G06F3/0637 ,  G06F3/0641 ,  G06F3/067 ,  G06F3/0689 ,  G06F17/30156 ,  G06F17/30159 ,  G06F17/30952

摘要： A system and method for managing multiple fingerprint tables in a deduplicating storage system. A computer system includes a storage medium, a first fingerprint table comprising a first plurality of entries, and a second fingerprint table comprising a second plurality of entries. Each of the first plurality of entries and the second plurality of entries are configured to store fingerprint related data corresponding to data stored in the storage medium. A storage controller is configured to select the first fingerprint table for storage of entries corresponding to data stored in the data storage medium that has been deemed more likely to be successfully deduplicated than other data stored in the data storage medium; and select the second fingerprint table for storage of entries corresponding to data stored in the data storage medium that has been deemed less likely to be successfully deduplicated than other data stored in the storage medium.

摘要翻译： 一种用于在重复数据删除存储系统中管理多个指纹表的系统和方法。 计算机系统包括存储介质，包括第一多个条目的第一指纹表以及包括第二多个条目的第二指纹表。 第一多个条目和第二多个条目中的每一个被配置为存储与存储在存储介质中的数据相对应的指纹相关数据。 存储控制器被配置为选择第一指纹表以存储与被存储在数据存储介质中的数据相对应的条目，该数据被认为更可能成功地被重复数据删除的数据比存储在数据存储介质中的其他数据; 并且选择第二指纹表以存储与存储在数据存储介质中的数据相对应的条目，所述数据被认为不太可能成功地被重复数据删除，而不是存储在存储介质中的数据。

公开(公告)号：US08930307B2

公开(公告)日：2015-01-06

申请号：US13250570

申请日：2011-09-30

申请人： John Colgrove ,  John Hayes ,  Ethan Miller ,  Joseph S. Hasbani ,  Cary Sandvig

发明人： John Colgrove ,  John Hayes ,  Ethan Miller ,  Joseph S. Hasbani ,  Cary Sandvig

IPC分类号： G06F7/00 ,  G06F17/00 ,  G06F17/30 ,  G06F3/06

CPC分类号： G06F3/0608 ,  G06F3/0641 ,  G06F3/0688 ,  G06F17/30097 ,  G06F17/30159

摘要： A system and method for efficiently removing duplicate data blocks at a fine-granularity from a storage array. A data storage subsystem supports multiple deduplication tables. Table entries in one deduplication table have the highest associated probability of being deduplicated. Table entries may move from one deduplication table to another as the probabilities change. Additionally, a table entry may be evicted from all deduplication tables if a corresponding estimated probability falls below a given threshold. The probabilities are based on attributes associated with a data component and attributes associated with a virtual address corresponding to a received storage access request. A strategy for searches of the multiple deduplication tables may also be determined by the attributes associated with a given storage access request.

摘要翻译： 一种用于从存储阵列以细粒度有效地去除重复数据块的系统和方法。 数据存储子系统支持多个重复数据删除表。 一个重复数据删除表中的表项具有重复数据删除的相关概率最高。 随着概率的变化，表项可以从一个重复数据删除表移动到另一个。 另外，如果相应的估计概率低于给定阈值，则表条目可以从所有重复数据删除表中逐出。 概率基于与数据组件相关联的属性以及与对应于接收到的存储访问请求的虚拟地址相关联的属性。 用于搜索多个重复数据删除表的策略也可以由与给定存储访问请求相关联的属性来确定。

公开(公告)号：US08806160B2

公开(公告)日：2014-08-12

申请号：US13211288

申请日：2011-08-16

申请人： John Colgrove ,  John Hayes ,  Ethan Miller ,  Cary Sandvig

发明人： John Colgrove ,  John Hayes ,  Ethan Miller ,  Cary Sandvig

IPC分类号： G06F12/00 ,  G06F3/06

CPC分类号： G06F3/0644 ,  G06F3/0608 ,  G06F3/0619 ,  G06F3/064 ,  G06F3/065 ,  G06F3/0665 ,  G06F3/0668 ,  G06F3/067

摘要： A system and method for maintaining a mapping table in a data storage subsystem. A data storage subsystem supports multiple mapping tables. Records within a mapping table are arranged in multiple levels which may be logically ordered by time. Each level stores pairs of a key value and a pointer value. New records are inserted in a created new (youngest) level. All levels other than the youngest may be read only. In response to detecting a flattening condition, a data storage controller is configured to identify a group of two or more adjacent levels of the plurality of levels for flattening which are logically adjacent in time. A new level is created and one or more records stored within the group are stored in the new level, in response to detecting each of the one or more records stores a unique key among keys stored within the group.

摘要翻译： 一种用于在数据存储子系统中维护映射表的系统和方法。 数据存储子系统支持多个映射表。 映射表内的记录以多个级别排列，可以按时间逻辑排序。 每个级别存储键值和指针值的对。 新记录插入到创建的新（最年轻）级别中。 除最小的以外的所有级别可能只读。 响应于检测到平坦化状况，数据存储控制器被配置为识别在时间上在逻辑上相邻的用于平坦化的多个级别中的两个或更多个相邻级别的组。 响应于检测到一个或多个记录中的每一个在存储在组内的密钥之间存储唯一密钥，创建新级别并存储在组内的一个或多个记录在新级中。

公开(公告)号：US20130086006A1

公开(公告)日：2013-04-04

申请号：US13250570

申请日：2011-09-30

申请人： John Colgrove ,  John Hayes ,  Ethan Miller ,  Joseph S. Hasbani ,  Cary Sandvig

发明人： John Colgrove ,  John Hayes ,  Ethan Miller ,  Joseph S. Hasbani ,  Cary Sandvig

IPC分类号： G06F17/30

CPC分类号： G06F3/0608 ,  G06F3/0641 ,  G06F3/0688 ,  G06F17/30097 ,  G06F17/30159

摘要： A system and method for efficiently removing duplicate data blocks at a fine-granularity from a storage array. A data storage subsystem supports multiple deduplication tables. Table entries in one deduplication table have the highest associated probability of being deduplicated. Table entries may move from one deduplication table to another as the probabilities change. Additionally, a table entry may be evicted from all deduplication tables if a corresponding estimated probability falls below a given threshold. The probabilities are based on attributes associated with a data component and attributes associated with a virtual address corresponding to a received storage access request. A strategy for searches of the multiple deduplication tables may also be determined by the attributes associated with a given storage access request.

摘要翻译： 一种用于从存储阵列以细粒度有效地去除重复数据块的系统和方法。 数据存储子系统支持多个重复数据删除表。 一个重复数据删除表中的表项具有重复数据删除的相关概率最高。 随着概率的变化，表项可以从一个重复数据删除表移动到另一个。 另外，如果相应的估计概率低于给定阈值，则表条目可以从所有重复数据删除表中逐出。 概率基于与数据组件相关联的属性以及与对应于接收到的存储访问请求的虚拟地址相关联的属性。 用于搜索多个重复数据删除表的策略也可以由与给定存储访问请求相关联的属性来确定。

公开(公告)号：US08589640B2

公开(公告)日：2013-11-19

申请号：US13273858

申请日：2011-10-14

申请人： John Colgrove ,  John Hayes ,  Ethan Miller ,  Joseph S. Hasbani ,  Cary Sandvig

发明人： John Colgrove ,  John Hayes ,  Ethan Miller ,  Joseph S. Hasbani ,  Cary Sandvig

IPC分类号： G06F12/00 ,  G06F7/00

CPC分类号： G06F17/30371 ,  G06F3/0608 ,  G06F3/0619 ,  G06F3/0637 ,  G06F3/0641 ,  G06F3/067 ,  G06F3/0689 ,  G06F17/30156 ,  G06F17/30159 ,  G06F17/30952

摘要： A system and method for managing multiple fingerprint tables in a deduplicating storage system. A computer system includes a storage medium, a first fingerprint table comprising a first plurality of entries, and a second fingerprint table comprising a second plurality of entries. Each of the first plurality of entries and the second plurality of entries are configured to store fingerprint related data corresponding to data stored in the storage medium. A storage controller is configured to select the first fingerprint table for storage of entries corresponding to data stored in the data storage medium that has been deemed more likely to be successfully deduplicated than other data stored in the data storage medium; and select the second fingerprint table for storage of entries corresponding to data stored in the data storage medium that has been deemed less likely to be successfully deduplicated than other data stored in the storage medium.

摘要翻译： 一种用于在重复数据删除存储系统中管理多个指纹表的系统和方法。 计算机系统包括存储介质，包括第一多个条目的第一指纹表以及包括第二多个条目的第二指纹表。 第一多个条目和第二多个条目中的每一个被配置为存储与存储在存储介质中的数据相对应的指纹相关数据。 存储控制器被配置为选择第一指纹表以存储与被存储在数据存储介质中的数据相对应的条目，该数据被认为更可能成功地被重复数据删除的数据比存储在数据存储介质中的其他数据; 并且选择第二指纹表以存储与存储在数据存储介质中的数据相对应的条目，所述数据被认为不太可能成功地被重复数据删除，而不是存储在存储介质中的数据。

公开(公告)号：US08527544B1

公开(公告)日：2013-09-03

申请号：US13340119

申请日：2011-12-29

申请人： John Colgrove ,  John Hayes ,  Ethan Miller ,  Cary Sandvig ,  Joseph S. Hasbani ,  Feng Wang

发明人： John Colgrove ,  John Hayes ,  Ethan Miller ,  Cary Sandvig ,  Joseph S. Hasbani ,  Feng Wang

IPC分类号： G06F17/30

CPC分类号： G06F12/0253 ,  G06F3/0608 ,  G06F3/061 ,  G06F3/0641 ,  G06F3/065 ,  G06F3/0665 ,  G06F3/067 ,  G06F3/0688 ,  G06F17/30156 ,  G06F2212/702

摘要： A system and method for performing garbage collection. A system includes a storage medium, a first table including entries which map a virtual address to locations in the storage medium, and a second table with entries which include a reverse mapping of a physical address in a data storage medium to one or more virtual addresses. A storage controller is configured to perform garbage collection. During garbage collection, the controller is configured to identify one or more entries in the second table which correspond to a segment to be garbage collected. In response to determining the first table includes a valid mapping for a virtual address included in an entry of the one of the one or more entries, the controller is configured to copy data from a first location identified in the entry to a second location in the data storage medium, and reclaim the first storage location.

摘要翻译： 一种用于执行垃圾收集的系统和方法。 系统包括存储介质，包括将虚拟地址映射到存储介质中的位置的条目的第一表以及包括数据存储介质中的物理地址与一个或多个虚拟地址的反向映射的条目的第二表 。 存储控制器被配置为执行垃圾收集。 在垃圾收集期间，控制器被配置为识别第二表中与要被垃圾收集的段相对应的一个或多个条目。 响应于确定第一表包括包含在一个或多个条目中的一个条目的条目中的虚拟地址的有效映射，控制器被配置为将数据从条目中标识的第一位置复制到第 数据存储介质，并回收第一存储位置。

公开(公告)号：US08468318B2

公开(公告)日：2013-06-18

申请号：US12882877

申请日：2010-09-15

申请人： John Colgrove ,  John Hayes ,  Bo Hong ,  Feng Wang ,  Ethan Miller ,  Craig Harmer

发明人： John Colgrove ,  John Hayes ,  Bo Hong ,  Feng Wang ,  Ethan Miller ,  Craig Harmer

IPC分类号： G06F12/00

CPC分类号： G06F3/0611 ,  G06F3/06 ,  G06F3/061 ,  G06F3/0613 ,  G06F3/0629 ,  G06F3/0653 ,  G06F3/0655 ,  G06F3/0656 ,  G06F3/0659 ,  G06F3/0683 ,  G06F3/0688 ,  G06F3/0689 ,  G06F12/0238 ,  G06F12/0246 ,  G06F12/08 ,  G06F12/0802 ,  G06F12/0891 ,  G06F2003/0697 ,  G06F2212/60

摘要： A system and method for scheduling read and write operations among a plurality of solid-state storage devices. A computer system comprises client computers and data storage arrays coupled to one another via a network. A data storage array utilizes solid-state drives and Flash memory cells for data storage. A storage controller within a data storage array comprises an I/O scheduler. The data storage controller is configured to receive requests targeted to the data storage medium, said requests including a first type of operation and a second type of operation. The controller is further configured to schedule requests of the first type for immediate processing by said plurality of storage devices, and queue requests of the second type for later processing by the plurality of storage devices. Operations of the first type may correspond to operations with an expected relatively low latency, and operations of the second type may correspond to operations with an expected relatively high latency.

公开(公告)号：US20120079190A1

公开(公告)日：2012-03-29

申请号：US12892895

申请日：2010-09-28

申请人： John Colgrove ,  John Hayes ,  Bo Hong ,  Ethan Miller

发明人： John Colgrove ,  John Hayes ,  Bo Hong ,  Ethan Miller

IPC分类号： G06F12/14 ,  G06F12/00

CPC分类号： G06F11/1076 ,  G06F3/0605 ,  G06F3/0688 ,  G06F11/3034 ,  G06F11/3055 ,  G06F2211/1057 ,  G06F2211/1059

摘要： A system and method for offset protection data in a RAID array. A computer system comprises client computers and data storage arrays coupled to one another via a network. A data storage array utilizes solid-state drives and Flash memory cells for data storage. A storage controller within a data storage array is configured to store user data in a first page of a first storage device of the plurality of storage devices; generate intra-device protection data corresponding to the user data, and store the intra-device protection data at a first offset within the first page. The controller is further configured to generate inter-device protection data corresponding to the first page, and store the inter-device protection data at a second offset within a second page in a second storage device of the plurality of storage devices, wherein the first offset is different from the second offset.

摘要翻译： RAID阵列中偏移保护数据的系统和方法。 计算机系统包括经由网络彼此耦合的客户端计算机和数据存储阵列。 数据存储阵列利用固态驱动器和闪存单元进行数据存储。 数据存储阵列中的存储控制器被配置为将用户数据存储在多个存储设备中的第一存储设备的第一页中; 生成对应于用户数据的设备内保护数据，并将设备内保护数据存储在第一页内的第一偏移处。 所述控制器还被配置为产生对应于所述第一页的设备间保护数据，并且将所述设备间保护数据存储在所述多个存储设备中的第二存储设备中的第二页内的第二偏移处，其中所述第一偏移 与第二偏移不同。