公开(公告)号：US20130042052A1

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

申请号：US13208094

申请日：2011-08-11

申请人： John Colgrove ,  John Hayes ,  Ethan Miller ,  Feng Wang

发明人： John Colgrove ,  John Hayes ,  Ethan Miller ,  Feng Wang

IPC分类号： G06F12/10 ,  G06F12/08 ,  G06F12/16 ,  G06F12/00

CPC分类号： G06F12/0246 ,  G06F3/0608 ,  G06F3/061 ,  G06F3/0638 ,  G06F3/0665 ,  G06F3/067 ,  G06F12/0802 ,  G06F12/1009 ,  G06F2212/50 ,  G06F2212/7201

摘要： A system and method for efficiently performing user storage virtualization for data stored in a storage system including a plurality of solid-state storage devices. A data storage subsystem supports multiple mapping tables. Records within a mapping table are arranged in multiple levels. Each level stores pairs of a key value and a pointer value. The levels are sorted by time. New records are inserted in a created newest (youngest) level. No edits are performed in-place. All levels other than the youngest may be read only. The system may further include an overlay table which identifies those keys within the mapping table that are invalid.

摘要翻译： 一种用于对存储在包括多个固态存储设备的存储系统中的数据有效地执行用户存储虚拟化的系统和方法。 数据存储子系统支持多个映射表。 映射表中的记录以多个级别排列。 每个级别存储键值和指针值的对。 级别按时间排序。 新记录插入到创建的最新（最小）级别中。 没有就地进行编辑。 除最小的以外的所有级别可能只读。 该系统还可以包括标识映射表内无效的那些密钥的覆盖表。

公开(公告)号：US08788788B2

公开(公告)日：2014-07-22

申请号：US13208094

申请日：2011-08-11

申请人： John Colgrove ,  John Hayes ,  Ethan Miller ,  Feng Wang

发明人： John Colgrove ,  John Hayes ,  Ethan Miller ,  Feng Wang

IPC分类号： G06F12/08 ,  G06F3/06 ,  G06F12/10

CPC分类号： G06F12/0246 ,  G06F3/0608 ,  G06F3/061 ,  G06F3/0638 ,  G06F3/0665 ,  G06F3/067 ,  G06F12/0802 ,  G06F12/1009 ,  G06F2212/50 ,  G06F2212/7201

摘要： A system and method for efficiently performing user storage virtualization for data stored in a storage system including a plurality of solid-state storage devices. A data storage subsystem supports multiple mapping tables. Records within a mapping table are arranged in multiple levels. Each level stores pairs of a key value and a pointer value. The levels are sorted by time. New records are inserted in a created newest (youngest) level. No edits are performed in-place. All levels other than the youngest may be read only. The system may further include an overlay table which identifies those keys within the mapping table that are invalid.

公开(公告)号：US08645664B1

公开(公告)日：2014-02-04

申请号：US13289765

申请日：2011-11-04

申请人： John Colgrove ,  John Hayes ,  Ethan Miller ,  Feng Wang

发明人： John Colgrove ,  John Hayes ,  Ethan Miller ,  Feng Wang

IPC分类号： G06F12/08

CPC分类号： G06F12/0246 ,  G06F3/0608 ,  G06F3/061 ,  G06F3/0638 ,  G06F3/0665 ,  G06F3/067 ,  G06F12/0802 ,  G06F12/1009 ,  G06F2212/50 ,  G06F2212/7201

摘要： A system and method for efficiently performing user storage virtualization for data stored in a storage system including a plurality of solid-state storage devices. A data storage subsystem supports multiple mapping tables. Records within a mapping table are arranged in multiple levels. Each level stores pairs of a key value and a pointer value. The levels are sorted by time. New records are inserted in a created newest (youngest) level. No edits are performed in-place. All levels other than the youngest may be read only. The system may further include an overlay table which identifies those keys within the mapping table that are invalid.

摘要翻译： 一种用于对存储在包括多个固态存储设备的存储系统中的数据有效地执行用户存储虚拟化的系统和方法。 数据存储子系统支持多个映射表。 映射表中的记录以多个级别排列。 每个级别存储键值和指针值的对。 级别按时间排序。 新记录插入到创建的最新（最小）级别中。 没有就地进行编辑。 除最小的以外的所有级别可能只读。 该系统还可以包括标识映射表内无效的那些密钥的覆盖表。

公开(公告)号：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.

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

公开(公告)号：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.

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

公开(公告)号：US08793467B2

公开(公告)日：2014-07-29

申请号：US13250579

申请日：2011-09-30

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

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

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

CPC分类号： G06F12/1009 ,  G06F3/0608 ,  G06F3/0641 ,  G06F3/0688 ,  G06F12/1036 ,  G06F2212/657

摘要： A system and method for maintaining a mapping table in a data storage subsystem. A data storage subsystem supports multiple mapping tables including a plurality of entries. Each of the entries comprise a tuple including a key. A data storage controller is configured to encode each tuple in the mapping table using a variable length encoding. Additionally, the mapping table may be organized as a plurality of time ordered levels, with each level including one or more mapping table entries. Further, a particular encoding of a plurality of encodings for a given tuple may be selected based at least in part on a size of the given tuple as unencoded, a size of the given tuple as encoded, and a time to encode the given tuple.

摘要翻译： 一种用于在数据存储子系统中维护映射表的系统和方法。 数据存储子系统支持包括多个条目的多个映射表。 每个条目包括包括密钥的元组。 数据存储控制器被配置为使用可变长度编码对映射表中的每个元组进行编码。 另外，映射表可以被组织为多个时间有序的级别，其中每个级别包括一个或多个映射表条目。 此外，可以至少部分地基于给定元组的大小作为未编码，被编码的给定元组的大小和对给定元组进行编码的时间来选择给定元组的多个编码的特定编码。