Distributing data blocks across a plurality of storage devices

• US 9,792,045 B1
• Filed: 05/03/2016
• Issued: 10/17/2017
• Est. Priority Date: 03/15/2012
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Pure Storage, Inc.
• Inventors: Miller, Ethan, Colgrove, John, Hayes, John, Sandvig, Cary
• Primary Examiner(s): Rojas, Midys
• Application Number:
  US15/144,885
• Time in Patent Office: 532 Days
• Field of Search: None
• CPC Class Codes: G06F 12/00 Accessing, addressing or allocating within memory systems or architectures digital input from, or digital output to record carriers, e.g. to disk storage units, G06F3/06
• CPC Class Codes: G06F 12/0292 using tables or multilevel address translation means G06F12/023 takes precedence; address translation in virtual memory systems G06F12/10
• CPC Class Codes: G06F 12/06 Addressing a physical block of locations, e.g. base addressing, module addressing, memory dedication G06F12/08 takes precedence
• CPC Class Codes: G06F 12/10 Address translation
• CPC Class Codes: G06F 12/1009 using page tables, e.g. page table structures
• CPC Class Codes: G06F 12/1027 using associative or pseudo-associative address translation means, e.g. translation look-aside buffer [TLB]
• CPC Class Codes: G06F 2212/1044 Space efficiency improvement
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0664 at device level, e.g. emulation of a storage device or system
• CPC Class Codes: G06F 3/0665 at area level, e.g. provisioning of virtual or logical volumes
• CPC Class Codes: G06F 3/0683 Plurality of storage devices
• CPC Class Codes: G06F 3/0689 Disk arrays, e.g. RAID, JBOD

Abstract

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 2^k by 2^k square, then the region is broken up into one or more 2^k by 2^k squares. Any remaining sub-region is centered within a 2^k by 2^k square, the 2^k by 2^k 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.

Claims

1. A computing system comprising:

a plurality of storage devices; and

a data storage controller, wherein the data storage controller is configured to;

map virtual block numbers to logical addresses corresponding to physical locations in a region using a fractal pattern, and wherein the region spans two or more storage devices of the plurality of storage devices.

2. The computing system as recited in claim 1, wherein the region is represented by a two-dimensional grid, wherein a first dimension is measured in blocks, and wherein a second dimension is measured in storage devices.

3. The computing system as recited in claim 1, wherein the data storage controller is configured to map virtual addresses to logical address corresponding to physical locations in the region using a mapping table.

4. The computing system as recited in claim 3, wherein the mapping table is initialized using a space-filling curve.

5. The computing system as recited in claim 1, wherein the region is a square with a side length equal to 2^k, where k is a positive integer greater than one.

6. The computing system as recited in claim 1, wherein the region is a rectangle of size A by B with M blocks, wherein A, B, and M are integers greater than zero, and wherein the data storage controller is further configured to:

center the region within a square of side length equal to 2^k, wherein k is a positive integer greater than one, wherein the square includes N blocks, wherein N is an integer greater than zero, and wherein at least one of A or B is less than 2^k.

7. The computing system as recited in claim 1, wherein the region is a rectangle of size A by B with M blocks, wherein A, B, and M are integers greater than zero, and wherein the data storage controller is further configured to:

partition the region into one or more square regions, wherein each square region has a side length equal to 2^k, wherein k is a positive integer greater than one, and wherein k may vary for the one or more smaller square regions.

8. The computing system as recited in claim 7, wherein a leftover region remains after partitioning the region into one or more square regions, wherein the leftover region is a rectangle of size C by D with P blocks, wherein C, D, and P are integers greater than zero, and wherein the data storage controller is further configured to:

center the leftover region within a square of side length equal to 2^j, wherein j is a positive integer greater than one, wherein the square includes N blocks, wherein N is an integer greater than zero, and wherein at least one of C or D is less than 2^j.

9. A method for use in a computing system including a plurality of storage devices, the method comprising mapping virtual block numbers to logical addresses corresponding to physical locations in a region using a fractal pattern, wherein the region spans two or more storage devices of the plurality of storage devices.

10. The method as recited in claim 9, wherein the region is represented by a two-dimensional grid, wherein a first dimension is measured in blocks, and wherein a second dimension is measured in storage devices.

11. The method as recited in claim 9, wherein the data storage controller is configured to map virtual addresses to logical addresses corresponding to physical locations in the region using a mapping table.

12. The method as recited in claim 11, wherein the mapping table is initialized using a space-filling curve.

13. The method as recited in claim 9, wherein the region is a square with a side length equal to 2^k, and where k is a positive integer greater than one.

14. The method as recited in claim 9, wherein the region is a rectangle of size A by B with M blocks, where A, B, and M are integers greater than zero, the method further comprising:

centering the region within a square of side length equal to 2^k, wherein k is a positive integer greater than one, wherein the square includes N blocks, where N is an integer greater than zero and a least one of A or B is less than 2^k.

15. A non-transitory computer readable storage medium comprising program instructions, wherein said program instructions are executable to map virtual block numbers to logical addresses corresponding to physical locations in a region of a storage system including a plurality of storage devices using a fractal pattern, wherein the region spans two or more of the plurality of storage devices.

16. The non-transitory computer readable storage medium as recited in claim 15, wherein the region is represented by a two-dimensional grid, wherein a first dimension is measured in blocks, and wherein a second dimension is measured in storage devices.

17. The non-transitory computer readable storage medium as recited in claim 15, wherein the data storage controller is configured to map virtual block numbers to logical addresses corresponding to physical locations in the region using a mapping table.