Fractal layout of data blocks across multiple devices

• US 8,719,540 B1
• Filed: 03/15/2012
• Issued: 05/06/2014
• 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:
  US13/421,336
• Time in Patent Office: 782 Days
• Field of Search: 711/173, 711/202, 711/203, 711/217
• US Class Current: 711/173
• 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 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 a space-filling curve is utilized to generate the block numbers in the fractal pattern.

4. The computing system as recited in claim 3, wherein the space-filling curve is a Hilbert space-filling curve.

5. The computing system as recited in claim 4, 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 4, 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;

generate a first block number for each of the N blocks of the square utilizing the Hilbert space-filling curve, wherein the first block numbers are numbered from 0 to N−

1;

discard blocks outside of the centered region; and

renumber each of the M blocks of the region with a second block number, wherein the second block numbers are numbered from 0 to M−

1 according to an ascending sequential order of the first block numbers of the M blocks.

7. The computing system as recited in claim 6, wherein the data storage controller is further configured to discard the first block numbers subsequent to renumbering the M blocks of the region.

8. The computing system as recited in claim 6, wherein the data storage controller is further configured to generate and store a layout of the second block numbers prior to the layout being utilizing for accessing the physical locations in the region.

9. The computing system as recited in claim 4, 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; and

generate block numbers for each of the one or more smaller square regions utilizing the Hilbert space-filling curve.

10. The computing system as recited in claim 9, 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;

generate a first block number for each of the N blocks of the square utilizing the Hilbert space-filling curve, wherein the first block numbers are numbered from 0 to N−

1;

discard blocks outside of the centered region; and

renumber each of the P blocks of the leftover region with a second block number, wherein the second block numbers are numbered from 0 to P−

1 according to an ascending sequential order of the first block numbers of the P blocks.

11. A method for use in a computing system including a plurality of storage devices, the method comprising mapping virtual block numbers 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.

12. The method as recited in claim 11, 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.

13. The method as recited in claim 11, wherein a space-filling curve is utilized to generate the block numbers in the fractal pattern.

14. The method as recited in claim 13, wherein the space-filling curve is a Hilbert space-filling curve.

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

16. The method as recited in claim 14, 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;

generating a first block number for each of the N blocks of the square utilizing the Hilbert space-filling curve, wherein the first block numbers are numbered from 0 to N−

1;

discarding blocks outside of the centered region; and

renumbering each of the M blocks of the region with a second block number, wherein the second block numbers are numbered from 0 to M−

1 according to an ascending sequential order of the first block numbers of the M blocks.

17. The method as recited in claim 16, the method further comprising discarding the first block numbers subsequent to renumbering each of the M blocks of the region.

18. A non-transitory computer readable storage medium comprising program instructions, wherein said program instructions are executable to map virtual block numbers 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.

19. The non-transitory computer readable storage medium as recited in claim 18, 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.

20. The non-transitory computer readable storage medium as recited in claim 19, wherein a space-filling curve is utilized to generate the block numbers in the fractal pattern.