Fractal layout of data blocks across multiple devices

Patent metadata

Field	Value
Publication number	US-9405486-B2
Application number	US-201414243421-A
Country	US
Kind code	B2
Filing date	Apr 2, 2014
Priority date	Mar 15, 2012
Publication date	Aug 2, 2016
Grant date	Aug 2, 2016

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.

First claim

What is claimed is:

1. A computing system comprising:
a plurality of storage devices; and
a data storage controller, wherein the data storage controller is configured to:
receive a request to store a consecutive collection of data; and
store the group of data within a region using a fractal pattern, wherein the region spans two or more storage devices of the plurality of storage device.

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 block numbers 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:
receiving a request to store a consecutive collection of data; and
storing the group of data within a region using a fractal pattern, wherein the region spans two or more storage devices of the plurality of storage device.

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 block numbers 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:
receive a request to store a consecutive collection of data; and
store the group of data within a region using a fractal pattern, wherein the region spans two or more storage devices of the plurality of storage device.

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 physical locations in the region using a mapping table.

Assignees

• Pure Storage Inc

Inventors

• Miller Ethan
• Colgrove John
• Hayes John
• Sandvig Cary

Classifications

• G06F3/064

  Management of blocks · CPC title

• G06F12/0292

  using tables or multilevel address translation means (G06F12/023 takes precedence; address translation in virtual memory systems G06F12/10) · CPC title

• G06F3/061

  Improving I/O performance · CPC title

• G06F3/0689

  Disk arrays, e.g. RAID, JBOD · CPC title

• G06F3/0664

  at device level, e.g. emulation of a storage device or system · CPC title