Systems and methods for distributed atomic storage operations

• US 10,019,320 B2
• Filed: 06/06/2014
• Issued: 07/10/2018
• Est. Priority Date: 10/18/2013
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Inventors: Talagala, Nisha, Das, Dhananjoy, Sundararaman, Swaminathan, Batwara, Ashish, Piggin, Nick
• Primary Examiner(s): Lo, Ann J
• Assistant Examiner(s): Warren, Tracy A
• Application Number:
  US14/298,791
• Publication Number:
  US 20150113326A1
• Time in Patent Office: 1,495 Days
• Field of Search: 711155
• CPC Class Codes: G06F 11/1441 Resetting or repowering
• CPC Class Codes: G06F 11/1443 Transmit or communication errors
• CPC Class Codes: G06F 11/2094 Redundant storage or storage space G06F11/2056 takes precedence
• 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/0688 Non-volatile semiconductor memory arrays

Abstract

An aggregation module combines a plurality of logical address spaces to form a conglomerated address space. The logical address spaces comprising the conglomerated address space may correspond to different respective storage modules and/or storage devices. An atomic aggregation module coordinates atomic storage operations within the conglomerated address space, and which span multiple storage modules. The aggregation module may identify the storage modules used to implement the atomic storage request, assign a sequence indicator to the atomic storage request, and issue atomic storage requests (sub-requests) to the storage modules. The storage modules may be configured to store a completion tag comprising the sequence indicator upon completing the sub-requests issued thereto. The aggregation module may identify incomplete atomic storage requests based on the completion information stored on the storage modules.

Claims

1. A method, comprising:

assigning two or more storage controllers of a storage system to an atomic storage request, each of the two or more storage controllers assigned to implement respective sub-requests of the atomic storage request based on associations between addresses of the atomic storage request and logical address spaces managed by respective storage controllers of the storage system;

generating completion metadata for the atomic storage request, the completion metadata comprising one or more of;

a number of storage controllers assigned to the atomic storage request and an identifier of each of the assigned storage controllers; and

configuring each storage controller of the assigned storage controllers to store the completion metadata generated for the atomic storage request in response to completing implementation of the respective sub-requests assigned to the storage controller.

2. The method of claim 1, further comprising:

determining a count of storage controllers having stored the completion metadata generated for the atomic storage request; and

comparing the determined count to the number of storage controllers assigned to the atomic storage request included in the completion metadata generated for the atomic storage request.

3. The method of claim 1, further comprising:

acquiring storage controller identifiers from storage controllers of the storage system determined to have stored the completion metadata generated for the atomic storage request; and

determining whether each identifier included in the completion metadata generated for the atomic storage request corresponds to a storage controller identifier of the acquired storage controller identifiers.

4. The method of claim 1, further comprising:

requesting the completion metadata generated for the atomic storage request from each of the plurality of storage controllers of the storage system;

receiving the completion metadata generated for the atomic storage request from one or more of the storage controllers of the storage system in response to the requesting; and

determining whether the atomic storage request was successfully completed within the storage system by one or more of;

comparing a count of the one or more storage controllers to the number of storage controllers assigned to the atomic storage request included in the completion metadata generated for the atomic storage request; and

determining whether each identifier included in the completion metadata generated for the atomic storage request corresponds to a storage controller of the one or more storage controllers.

5. The method of claim 1, further comprising:

issuing the respective sub-requests to the assigned storage controllers, wherein issuing the respective sub-requests comprises translating addresses of the atomic storage request to logical addresses of the logical address spaces managed by the assigned storage controllers.

6. The method of claim 1, further comprising:

determining whether the atomic storage request was successfully completed, the determining comprising;

requesting last completion metadata written by each of the storage controllers of the storage system;

identifying, in completion metadata received in response to the requesting, completion metadata comprising a sequence indicator of the atomic storage request; and

using the identified completion metadata to determine whether the atomic storage request was successfully completed.

7. The method of claim 6, further comprising:

determining that the atomic storage request was successfully completed in response to one or more of;

receiving completion metadata comprising the sequence indicator of the atomic storage request from the number of storage controllers assigned to the atomic storage request; and

receiving completion metadata comprising the sequence indicator of the atomic storage request from storage controllers corresponding to each storage controller assigned to the atomic storage request.

8. The method of claim 6, further comprising:

determining that the atomic storage request was not completed successfully in response to one or more of;

receiving completion metadata comprising the sequence indicator of the atomic storage request from fewer than the number of storage controllers assigned to the atomic storage request; and

determining that an identifier included in the completion metadata generated for the atomic storage request does not correspond to a storage controller from which completion metadata comprising the sequence identifier of the atomic storage request was received.

9. The method of claim 8, further comprising:

instructing one or more of the storage controllers of the storage system to invalidate data pertaining to the atomic storage request.

10. The method of claim 6, further comprising:

determining whether the atomic storage request was successfully completed in response to detecting an invalid shutdown.

11. An apparatus, comprising:

an atomic aggregation module configured to;

assign respective atomic storage operations of an atomic storage request to two or more storage modules of a storage system comprising a plurality of storage modules; and

generate a transaction completion tag for the atomic storage request, the transaction completion tag comprising a sequence indicator and one or more of;

a number of storage modules assigned to implement atomic storage operations of the atomic storage request, and identifiers of the two or more storage modules in the storage system; and

an aggregation storage module configured to cause each storage module of the two or more storage modules to;

write the transaction completion tag generated for the atomic storage request in non-volatile storage of the storage module in response to completing the respective atomic storage operations assigned to the storage module.

12. The apparatus of claim 11, wherein:

the atomic storage request corresponds to identifiers of an aggregate address space corresponding to a plurality of logical address spaces of respective storage modules of the storage system; and

the atomic aggregation module is configured to select the two or more storage modules to implement the respective atomic storage operations of the atomic storage request based on associations between the identifiers of the atomic storage request and the logical address spaces of the respective storage modules of the storage system.

13. The apparatus of claim 11, further comprising:

a recovery agent configured to;

request transaction completion tags from each storage module of the storage system; and

determine whether the atomic storage request was completed successfully based on transaction completion tags received in response to the request.

14. The apparatus of claim 13, wherein the recovery agent is configured to determine that the request completed successfully in response to one or more of:

determining that transaction completion tags comprising the sequence indicator of the atomic storage request were received from the number of storage modules assigned to implement atomic storage operations of the atomic storage request;

determining that transaction completion tags comprising the sequence indicator of the atomic storage request were received from storage modules corresponding to each of the identifiers included in the transaction completion tag generated for the atomic storage request.

15. The apparatus of claim 13, wherein the recovery agent is configured to determine that the atomic storage request is incomplete in response to one or more of:

determining that transaction completion tags comprising the sequence indicator of the atomic storage request were received from fewer than the number of storage modules assigned to implement the atomic storage operations of the atomic storage request; and

determining that one or more of the identifiers included in the transaction completion tag does not correspond to a storage module from which a transaction completion tag comprising the sequence indicator of the atomic storage request was received.

16. The apparatus of claim 15, wherein the recovery agent is configured to instruct the storage modules of the storage system to invalidate data pertaining to the atomic storage request.

17. The apparatus of claim 11, further comprising:

a recovery agent configured to inform a first one of the two or more storage modules that the atomic storage request failed in response to determining that a second one of the two or more storage modules failed to store the transaction completion tag generated for the atomic storage request.

18. The apparatus of claim 11, further comprising:

a recovery agent configured to;

access transaction completion tags stored within non-volatile storage of the storage modules; and

determine whether the atomic storage request was fully completed based on the accessed transaction completion tags.

19. The apparatus of claim 11, further comprising:

a recovery agent configured to;

determine that the atomic storage request was completed on each of the two or more storage modules in response to determining that each of the two or more storage modules stored the completion tag of the atomic storage request on respective storage devices of the two or more storage modules.

20. The apparatus of claim 11, wherein each of the storage modules comprises an atomic storage module configured to identify and/or invalidate data of failed atomic storage operations performed on the storage module.

21. A non-transitory computer-readable storage medium comprising computer-readable program code configured for execution by a processor to cause a computing device to perform operations, the operations comprising:

combining a plurality of logical address spaces to form a virtual address space, each logical address space corresponding to a respective storage layer configured to perform storage operations pertaining to the logical address space on persistent storage of the storage layer;

selecting two or more of the storage layers to implement an atomic storage request, each of the two or more storage layers being assigned to implement a respective portion of the atomic storage request based on mappings between virtual identifiers of the atomic storage request and the logical address spaces corresponding to the storage layers; and

providing completion data for the atomic storage request to each of the selected storage layers, the completion data comprising a completion sequence number and one or more of;

a number of the selected storage layers, and an identifier of each of the selected storage layers,

wherein each storage layer of the selected storage layers is configured to write the provided completion data to the persistent storage of the storage layer in response to the storage layer completing the respective portion of the atomic storage request assigned to the storage layer.

22. The non-transitory computer-readable storage medium of claim 21, wherein each storage layer of the selected storage layers is assigned to implement the respective portion of the atomic storage request that maps to the logical address space corresponding to the storage layer.

23. The non-transitory computer-readable storage medium of claim 21, the operations further comprising:

translating virtual identifiers of a portion of the atomic storage request assigned to a particular storage layer of the selected storage layers to logical identifiers within the logical address space of the particular storage layer; and

sending an atomic sub-request comprising the translated logical identifiers to the particular storage layer, the atomic sub-request configured to cause the particular storage layer to implement the portion of the atomic storage request assigned to the particular storage layer on the persistent storage of the particular storage layer.

24. The non-transitory computer-readable storage medium of claim 21, the operations further comprising:

determining whether each storage layer of the selected storage layers completed the portion of the atomic storage request assigned to the storage layer, by;

accessing completion data stored on persistent storage of the storage layers; and

determining one or more of;

whether a number storage layers storing completion data comprising the completion sequence indicator of the atomic storage request corresponds to the number of the selected storage layers, included in the provided completion data for the atomic storage request; and

whether each identifier included in the provided completion data for the atomic storage request corresponds to a storage layer storing completion data comprising the completion sequence number of the atomic storage request.

25. The non-transitory computer-readable storage medium of claim 21, the operations further comprising:

issuing respective atomic sub-requests to the selected storage layers, each atomic sub-request configured to cause a respective storage layer of the selected storage layers to implement the portion of the atomic storage request assigned to the storage layer; and

determining whether the atomic storage request was fully completed based on completion data stored on the persistence storage of the storage layers.