Two-level hierarchical log structured array architecture using coordinated garbage collection for flash arrays

1. A method, in an array controller of a two-level hierarchical log structured array architecture for a non-volatile memory array, wherein the two-level hierarchical log structured array (LSA) architecture comprises an array-level LSA in the array controller and a node-level LSA in each node of the non-volatile memory array, for coordinated garbage collection, the method comprising:

maintaining host logical block address (LBA) to node LBA mapping in an array controller connected to a plurality of nodes, wherein a host data processing system issues access requests to host LBA and wherein the mapping maps a host LBA space to a node LBA space of a plurality of nodes;

making overprovisioned space in the node LBA space of the plurality of nodes available to the array-level LSA;

adding additional overprovisioned space at each node LBA space; and

initiating array-level garbage collection at the array-level LSA.

2. The method of claim 1 , wherein the additional overprovisioned space at each node LBA space is not visible in the host LBA space.

3. The method of claim 1 , wherein the additional overprovisioned space at each node LBA space comprises a number of block stripes at which node-level garbage collection is started plus two times a number of block stripes the node-level garbage collection can have in flight for the node-level garbage collection.

4. The method of claim 3 , wherein the additional overprovisioned space at each node LBA space corresponds to a maximum free capacity in a node plus two times a maximum node stripe size.

5. The method of claim 1 , wherein the array-level garbage collection uses a cyclic buffer garbage collection policy on the array-level LSA.

6. The method of claim 1 , wherein the array-level controller maintains the host LBA to node LBA mapping on a page granularity.

7. The method of claim 1 , wherein each node maintains a node LBA to physical block address (PBA) mapping table.

8. The method of claim 1 , further comprising:

responsive to array-level garbage collection or an overwrite invalidating a host LBA, sending an invalidation notification command from the array controller to a node of the corresponding node LBA, wherein the invalidation notification command notifies the node that the corresponding node LBA is invalid.

9. The method of claim 1 , wherein initiating array-level garbage collection at the array-level LSA comprises initiating cyclic buffer garbage collection for each of a plurality of heat level LSA zones independently.

10. The method of claim 9 , wherein the array-level LSA and the node-level LSA agree on a heat level for each node LBA.

11. A computer program product, in an array controller of a two-level hierarchical log structured array architecture for a non-volatile memory array, wherein the two-level hierarchical log structured array (LSA) architecture comprises an array-level LSA in the array controller and a node-level LSA in each node of the non-volatile memory array, for coordinated garbage collection, comprising a computer readable storage medium having a computer readable program stored therein, wherein the computer readable program, when executed on an array controller, causes the array controller to:

maintain host logical block address (LBA) to node LBA mapping in an array controller connected to a plurality of nodes, wherein a host data processing system issues access requests to host LBA and wherein the mapping maps a host LBA space to a node LBA space of a plurality of nodes;

make overprovisioned space in the node LBA space of the plurality of nodes available to the array-level LSA;

add additional overprovisioned space at each node LBA space; and

initiate array-level garbage collection at the array-level LSA.

12. The computer program product of claim 11 , wherein the additional overprovisioned space at each node LBA space comprises a number of block stripes at which node-level garbage collection is started plus two times a number of block stripes the node-level garbage collection can have in flight for the node-level garbage collection and wherein the additional overprovisioned space at each node LBA space corresponds to a maximum free capacity in a node plus two times a maximum node stripe size.

13. The computer program product of claim 11 , wherein the array-level garbage collection uses a cyclic buffer garbage collection policy on the array-level LSA.

14. The computer program product of claim 11 , wherein the computer readable program further causes the array controller to:

responsive to array-level garbage collection or an overwrite invalidating a host LBA, send an invalidation notification command from the array controller to a node of the corresponding node LBA, wherein the invalidation notification command notifies the node that the corresponding node LBA is invalid.

15. The computer program product of claim 11 , wherein initiating array-level garbage collection at the array-level LSA comprises initiating cyclic buffer garbage collection for each of a plurality of heat level LSA zones independently.

16. An array controller of a two-level hierarchical log structured array architecture for a non-volatile memory array, wherein the two-level hierarchical log structured array (LSA) architecture comprises an array-level LSA in the array controller and a node-level LSA in each node of the non-volatile memory array, for coordinated garbage collection, comprising:

a processor; and

a memory coupled to the processor, wherein the memory comprises instructions which, when executed by the processor, cause the processor to:

maintain host logical block address (LBA) to node LBA mapping in an array controller connected to a plurality of nodes, wherein a host data processing system issues access requests to host LBA and wherein the mapping maps a host LBA space to a node LBA space of a plurality of nodes;

make overprovisioned space in the node LBA space of the plurality of nodes available to the array-level LSA;

add additional overprovisioned space at each node LBA space; and

initiate array-level garbage collection at the array-level LSA.

17. The array controller of claim 16 , wherein the additional overprovisioned space at each node LBA space comprises a number of block stripes at which node-level garbage collection is started plus two times a number of block stripes the node-level garbage collection can have in flight for the node-level garbage collection and wherein the additional overprovisioned space at each node LBA space corresponds to a maximum free capacity in a node plus two times a maximum node stripe size.

18. The array controller of claim 16 , wherein the array-level garbage collection uses a cyclic buffer garbage collection policy on the array-level LSA.

19. The array controller of claim 16 , wherein the instructions further cause the processor to:

responsive to array-level garbage collection or an overwrite invalidating a host LBA, send an invalidation notification command from the array controller to a node of the corresponding node LBA, wherein the invalidation notification command notifies the node that the corresponding node LBA is invalid.

20. The array controller of claim 16 , wherein initiating array-level garbage collection at the array-level LSA comprises initiating cyclic buffer garbage collection for each of a plurality of heat level LSA zones independently.