公开(公告)号：US11249999B2

公开(公告)日：2022-02-15

申请号：US16206595

申请日：2018-11-30

Applicant: Pure Storage, Inc.

Inventor： John Colgrove ,  Ethan L. Miller ,  Neil Amar Vachharajani ,  Feng Wang

IPC: G06F16/2455 ,  G06F16/22

Abstract: Methods and apparatus for determining if a value is stored in a hash table is provided. The method includes breaking the value into address bits, prefix bits, and signature bits. The method includes determining a container in a compressed index at an address specified by the address bits, the container comprised of a prefix table with bits set corresponding to the prefix bits determined by aggregate values associated with the container and a signature table containing the signature bits determined by the aggregate values associated with the container. The method includes determining a result based on a function of the prefix and signature tables and the determined prefix and signature bits.

公开(公告)号：US10565183B1

公开(公告)日：2020-02-18

申请号：US15338746

申请日：2016-10-31

Applicant: PURE STORAGE, INC.

Inventor： John Colgrove ,  Ronald Karr ,  Vinay K. Perneti ,  Feng Wang

IPC: G06F16/23 ,  G06F16/22 ,  G06F16/25

Abstract: A data block may be received. Hash values correspond to portions of the data block may be generated. A determination that none of the plurality of hash values matches with another hash value associated with a previously received data block may be made. In response to determining that none of the plurality of hash values match with the other hash value associated with the previously received data block, a subset of the plurality of hash values may be stored based on a first alignment and a second alignment.

公开(公告)号：US10228865B1

公开(公告)日：2019-03-12

申请号：US15967408

申请日：2018-04-30

Applicant: PURE STORAGE, INC.

Inventor： John Colgrove ,  John Hayes ,  Bo Hong ,  Feng Wang ,  Ethan Miller ,  Craig Harmer

IPC: G06F3/06

Abstract: A system and method for effectively 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 characteristics of corresponding storage devices are used to schedule I/O requests to the storage devices in order to maintain relatively consistent response times at predicted times. Should a device exhibit an unscheduled behavior which may be indicative of the device being in an unknown state, the scheduler may schedule one or more reactive operations on the device configured to cause the device to enter a known state.

公开(公告)号：US09983822B1

公开(公告)日：2018-05-29

申请号：US15339673

申请日：2016-10-31

Applicant: Pure Storage, Inc.

Inventor： Ronald Karr ,  Ethan L. Miller ,  Cary A. Sandvig ,  Feng Wang ,  Wei Zhang

IPC: G06F17/30 ,  G06F3/06

CPC classification number: G06F3/0641 ,  G06F3/0608 ,  G06F3/0611 ,  G06F3/0652 ,  G06F3/067 ,  G06F3/0685

Abstract: The method generates a first deduplication map (DDM) level of a DDM pyramid. The DDM pyramid identifies locations of data stored in the persistent storage resource of the deduplication system. The method further determines a first false positive rate target for a first index summary (IS) level of an index pyramid based on a memory footprint for the first IS level and an aggregate false positive rate target for the index pyramid. The first IS level accelerates lookup into the first DDM level. The first false positive rate target indicates a rate that a hit for a value found in the first IS level is not found in the first DDM level. The method also generates the first IS level with a first false positive rate based on the determined first false positive rate target.

公开(公告)号：US09864769B2

公开(公告)日：2018-01-09

申请号：US14569624

申请日：2014-12-12

Applicant: PURE Storage, Inc.

Inventor： Marco Sanvido ,  Richard Hankins ,  John Hayes ,  Steve Hodgson ,  Feng Wang ,  Sergey Zhuravlev ,  Andrew Kleinerman

IPC: G06F17/30 ,  G06F3/06

CPC classification number: G06F17/30324 ,  G06F3/0608 ,  G06F3/0641 ,  G06F3/067

Abstract: A system and method for efficiently storing data in a storage system. A data storage subsystem includes multiple data storage locations on multiple storage devices in addition to at least one mapping table. A data storage controller determines whether data to store in the storage subsystem has one or more patterns of data intermingled with non-pattern data within an allocated block. Rather than store the one or more pattern on the storage devices, the controller stores information in a header on the storage devices. The information includes at least an offset for the first instance of a pattern, a pattern length, and an identification of the pattern. The data may be reconstructed for a corresponding read request from the information stored in the header.

公开(公告)号：US09588699B1

公开(公告)日：2017-03-07

申请号：US15004500

申请日：2016-01-22

Applicant: Pure Storage, Inc.

Inventor： John Colgrove ,  John Hayes ,  Bo Hong ,  Feng Wang ,  Ethan Miller ,  Craig Harmer

IPC: G06F3/06 ,  G06F11/07

CPC classification number: G06F3/0611 ,  G06F3/061 ,  G06F3/0613 ,  G06F3/0617 ,  G06F3/0634 ,  G06F3/0659 ,  G06F3/0665 ,  G06F3/0688 ,  G06F3/0689 ,  G06F11/0751 ,  G06F11/076 ,  G06F11/1076

Abstract: A system and method for effectively 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 characteristics of corresponding storage devices are used to schedule I/O requests to the storage devices in order to maintain relatively consistent response times at predicted times. Should a device exhibit an unscheduled behavior which may be indicative of the device being in an unknown state, the scheduler may schedule one or more reactive operations on the device configured to cause the device to enter a known state.

Abstract translation: 一种用于在多个固态存储设备之间有效地调度读取和写入操作的系统和方法。 计算机系统包括经由网络彼此耦合的客户端计算机和数据存储阵列。 数据存储阵列利用固态驱动器和闪存单元进行数据存储。 数据存储阵列中的存储控制器包括I / O调度器。 相应的存储设备的特性用于将I / O请求调度到存储设备，以便在预测时间内保持相对一致的响应时间。 如果设备呈现可能指示设备处于未知状态的非计划行为，则调度器可以对被配置为使设备进入已知状态的设备上的一个或多个无效操作进行调度。

公开(公告)号：US09436396B2

公开(公告)日：2016-09-06

申请号：US14513007

申请日：2014-10-13

Applicant: PURE Storage, Inc.

Inventor： John Colgrove ,  John Hayes ,  Bo Hong ,  Feng Wang ,  Ethan Miller ,  Craig Harmer

IPC: G06F3/06 ,  G06F11/07 ,  G06F11/10 ,  G06F12/08

CPC classification number: G06F3/0619 ,  G06F3/061 ,  G06F3/0613 ,  G06F3/0646 ,  G06F3/0659 ,  G06F3/0665 ,  G06F3/0688 ,  G06F3/0689 ,  G06F11/0727 ,  G06F11/0751 ,  G06F11/1076 ,  G06F12/0804 ,  G06F2003/0697

Abstract: A system and method for effectively 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 storage controller is configured to receive a read request targeted to the data storage medium, and identify at least a first storage device of the plurality of storage devices which contains data targeted by the read request. In response to either detecting or predicting the first storage device will exhibit variable performance, the controller is configured to generate a reconstruct read request configured to obtain the data from one or more devices of the plurality of storage devices other than the first storage device.

公开(公告)号：US20130346720A1

公开(公告)日：2013-12-26

申请号：US14015308

申请日：2013-08-30

Applicant: PURE Storage, Inc.

Inventor： John Colgrove ,  John Hayes ,  Ethan Miller ,  Cary Sandvig ,  Joseph S. Hasbani ,  Feng Wang

IPC: G06F12/02

CPC classification number: G06F12/0253 ,  G06F3/0608 ,  G06F3/061 ,  G06F3/0641 ,  G06F3/065 ,  G06F3/0665 ,  G06F3/067 ,  G06F3/0688 ,  G06F17/30156 ,  G06F2212/702

Abstract: 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.