LOGICAL VOLUME SPACE SHARING

• US 20140195761A1
• Filed: 01/09/2013
• Published: 07/10/2014
• Est. Priority Date: 01/09/2013
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: WANG, Wenguang, HORN, Deric S., MAJNEMER, David A.
• Granted Patent: US 9,134,908 B2
• Time in Patent Office: Days
• US Class Current: 711/166
• CPC Class Codes: G06F 3/0607 by facilitating the process of upgrading existing storage systems, e.g. for improving compatibility between host and storage device
• CPC Class Codes: G06F 3/0631 by allocating resources to storage systems
• CPC Class Codes: G06F 3/0644 Management of space entities, e.g. partitions, extents, pools
• CPC Class Codes: G06F 3/0683 Plurality of storage devices
• CPC Class Codes: G06F 3/0689 Disk arrays, e.g. RAID, JBOD

Abstract

Space sharing between logical volumes is achieved through a technique that enables available storage space to be flexibly consumed and released by the logical volumes. Each logical volume is associated with an address tree that defines how available storage space is consumed by the logical volume. The technique involves receiving an input/output (I/O) operation that specifies a logical address within an address tree associated with the logical volume, parsing the address tree to identify an entry therein, if any, that is associated with the logical address, where the entry stores physical address information that is associated with the logical address. If it is determined that the entry exists, then one or more translated I/O operations are generated based on the physical address information and forwarded to a physical device manager to carry out the translated one or more I/O operations.

Claims

1. A computer-implemented method for carrying out an input/output (I/O) operation issued to a logical volume, comprising:

receiving the I/O operation, wherein the I/O operation specifies a logical address within an address tree associated with the logical volume;

parsing the address tree to identify an entry therein, if any, that is associated with the logical address, wherein the entry stores physical address information that is associated with the logical address; and

if the entry exists;

generating one or more translated I/O operations based on the physical address information; and

forwarding the translated one or more I/O operations to a physical device manager to carry out the translated one or more I/O operations.

2. The method of claim 1, further comprising:

if the entry does not exist, and the I/O operation specifies a read request;

returning zero-filled data.

3. The method of claim 1, further comprising:

if the entry does not exist, and the I/O operation specifies a write request;

issuing a request to the physical device manager to allocate a number of blocks specified in the I/O operation;

receiving, from the physical device manager, generated physical address information that specifies reserved storage space sized according to the number of blocks;

generating one or more entries within the address tree that is associated with the logical address;

storing the generated physical address information in the one or more generated entries;

translating the I/O operation into one or more write operations based on the generated physical address information; and

forwarding the write operations to the physical device manager to carry out the write operations.

4. The method of claim 1, wherein, if the I/O operation specifies a trim request and the entry exists, then the step of translating the I/O operation comprises:

generating one or more delete operations based on parameters of the trim request as well as the physical address information; and

forwarding the generated one or more delete operations to the physical device manager to carry out the generated one or more delete operations.

5. The method of claim 4, further comprising:

determining that the trim request invalidates the entry in the address tree; and

replacing the entry with generated one or more new entries that reflect effects of the trim request.

6. The method of claim 1, wherein each entry in the address tree defines an extent within the logical volume, each extent being associated with a starting address within the logical volume as well as a size.

7. The method of claim 1, wherein the address tree is implemented using a B-Tree or a log-structured merge (LSM) tree.

8. A non-transitory computer-readable storage medium storing instructions that, when executed by a processor, cause the processor to implement a method for carrying out an input/output (I/O) operation issued to a logical volume, the method comprising:

receiving the I/O operation, wherein the I/O operation specifies a logical address within an address tree associated with the logical volume;

parsing the address tree to identify an entry therein, if any, that is associated with the logical address, wherein the entry stores physical address information that is associated with the logical address; and

if the entry exists;

generating one or more translated I/O operations based on the physical address information; and

forwarding the translated one or more I/O operations to a physical device manager to carry out the translated one or more I/O operations.

9. The non-transitory computer-readable storage medium of claim 8, further comprising:

if the entry does not exist, and the I/O operation specifies a read request;

returning zero-filled data.

10. The non-transitory computer-readable storage medium of claim 8, further comprising:

if the entry does not exist, and the I/O operation specifies a write request;

issuing a request to the physical device manager to allocate a number of blocks specified in the I/O operation;

receiving, from the physical device manager, generated physical address information that specifies reserved storage space sized according to the number of blocks;

generating one or more entries within the address tree that is associated with the logical address;

storing the generated physical address information in the one or more generated entries;

translating the I/O operation into one or more write operations based on the generated physical address information; and

forwarding the write operations to the physical device manager to carry out the write operations.

11. The non-transitory computer-readable storage medium of claim 8, wherein, if the I/O operation specifies a trim request and the entry exists, then the step of translating the I/O operation comprises:

generating one or more delete operations based on parameters of the trim request as well as the physical address information; and

forwarding the generated one or more delete operations to the physical device manager to carry out the generated one or more delete operations.

12. The non-transitory computer-readable storage medium of claim 11, further comprising:

determining that the trim request invalidates the entry in the address tree; and

replacing the entry with generated one or more new entries that reflect effects of the trim request.

13. The non-transitory computer-readable storage medium of claim 8, wherein each entry in the address tree defines an extent within the logical volume, each extent being associated with a starting address within the logical volume as well as a size.

14. The non-transitory computer-readable storage medium of claim 8, wherein the address tree is implemented using a B-Tree or a log-structured merge (LSM) tree.

15. A system, comprising:

one or more storage devices; and

a processor, configured to implement a method for carrying out an input/output (I/O) operation issued to a logical volume, the method comprising;

receiving the I/O operation, wherein the I/O operation specifies a logical address within an address tree associated with the logical volume;

parsing the address tree to identify an entry therein, if any, that is associated with the logical address, wherein the entry stores physical address information that is associated with the logical address; and

if the entry exists;

generating one or more translated I/O operations based on the physical address information; and

forwarding the translated one or more I/O operations to a physical device manager to carry out the translated one or more I/O operations.

16. The system of claim 15, further comprising:

if the entry does not exist, and the I/O operation specifies a read request;

returning zero-filled data.

17. The system of claim 15, further comprising:

if the entry does not exist, and the I/O operation specifies a write request;

issuing a request to the physical device manager to allocate a number of blocks specified in the I/O operation;

receiving, from the physical device manager, generated physical address information that specifies reserved storage space sized according to the number of blocks;

generating one or more entries within the address tree that is associated with the logical address;

storing the generated physical address information in the one or more generated entries;

translating the I/O operation into one or more write operations based on the generated physical address information; and

forwarding the write operations to the physical device manager to carry out the write operations.

18. The system of claim 15, wherein, if the I/O operation specifies a trim request and the entry exists, then the step of translating the I/O operation comprises:

generating one or more delete operations based on parameters of the trim request as well as the physical address information; and

forwarding the generated one or more delete operations to the physical device manager to carry out the generated one or more delete operations.

19. The system of claim 18, further comprising:

determining that the trim request invalidates the entry in the address tree; and

replacing the entry with generated one or more new entries that reflect effects of the trim request.

20. The system of claim 15, wherein each entry in the address tree defines an extent within the logical volume, each extent being associated with a starting address within the logical volume as well as a size.