Distributed raid over shared multi-queued storage devices

• US 9,521,201 B2
• Filed: 01/18/2016
• Issued: 12/13/2016
• Est. Priority Date: 09/15/2014
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: E8 Storage Systems Ltd. (Amazon.com, Inc.)
• Inventors: Ori, Zivan
• Primary Examiner(s): NGUYEN, PHUOC H
• Application Number:
  US14/997,600
• Publication Number:
  US 20160134703A1
• Time in Patent Office: 330 Days
• Field of Search: 711/114
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0653 Monitoring storage devices or systems
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: H04L 67/1097 for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]

Abstract

A method for data storage includes, in a system that includes multiple servers and multiple storage devices, holding in a server a definition of a stripe that includes multiple memory locations on the storage devices, to be used by the servers for storing multiple data elements and at least a redundancy element calculated over the data elements. One or more of the data elements in the stripe are modified by the server, by executing in the storage devices an atomic command, which updates the redundancy element to reflect the modified data elements only if a current redundancy element stored in the storage devices reflects the multiple data elements prior to modification of the data elements, and storing the modified data elements in the storage devices only in response to successful completion of the atomic command.

Claims

1. A method for data storage, comprising:

in a system that comprises multiple servers and multiple storage devices, holding in a server a definition of a stripe that comprises multiple memory locations on the storage devices, to be used by the servers for storing multiple data elements and at least a redundancy element calculated over the data elements; and

modifying, by the server, one or more of the data elements in the stripe by;

executing in the storage devices an atomic command, which updates the redundancy element to reflect the modified data elements only if a current redundancy element stored in the storage devices reflects the multiple data elements prior to modification of the data elements; and

storing the modified data elements in the storage devices only in response to successful completion of the atomic command.

2. The method according to claim 1, wherein modifying the data elements comprises caching the modified data elements, the current redundancy element and the updated redundancy element in an interim memory, and committing the modified data elements and the updated redundancy element from the interim memory to the storage devices only in response to the successful completion of the atomic command.

3. The method according to claim 2, wherein the interim memory and the server belong to different failure domains of the system.

4. The method according to claim 1, wherein the stripe is accessible to at least one additional server, and wherein modifying the data elements is performed by the server without communication with the additional server.

5. The method according to claim 1, wherein modifying the data elements comprises reading current data elements and the current redundancy element from the storage devices, and updating the redundancy element based on the current data elements, the modified data elements and the current redundancy element.

6. The method according to claim 5, wherein modifying the data elements comprises, in response to failure of the atomic command, re-reading the current data elements and the current redundancy element from the storage devices, re-calculating the redundancy element and re-attempting to update the redundancy element using the atomic command.

7. The method according to claim 1, wherein storing the data elements and the redundancy element comprises storing respective timestamps with the data elements, and storing with the redundancy element a list of the timestamps of the data elements over which the redundancy element was calculated.

8. The method according to claim 7, and comprising, prior to modifying the data elements, verifying that the timestamps of the data elements prior to the modification match the list of timestamps stored with the current redundancy element in the storage devices.

9. A data storage apparatus, comprising:

an interface configured to communicate with multiple storage devices; and

a processor, which is configured to hold a definition of a stripe that comprises multiple memory locations on the storage devices to be used for storing multiple data elements and at least a redundancy element calculated over the data elements, and to modify one or more of the data elements in the stripe by;

executing in the storage devices an atomic command, which updates the redundancy element to reflect the modified data elements only if a current redundancy element stored in the storage devices reflects the multiple data elements prior to modification of the data elements; and

storing the modified data elements in the storage devices only in response to successful completion of the atomic command.

10. The apparatus according to claim 9, wherein the processor is configured to cache the modified data elements, the current redundancy element and the updated redundancy element in an interim memory, and to commit the modified data elements and the updated redundancy element from the interim memory to the storage devices only in response to the successful completion of the atomic command.

11. The apparatus according to claim 10, wherein the interim memory and the apparatus belong to different failure domains.

12. The apparatus according to claim 9, wherein the stripe is accessible to at least one additional data storage apparatus, and wherein the processor is configured to modify the data elements without communication with the additional data storage apparatus.

13. The apparatus according to claim 9, wherein the processor is configured to modify the data elements by reading current data elements and the current redundancy element from the storage devices, and updating the redundancy element based on the current data elements, the modified data elements and the current redundancy element.

14. The apparatus according to claim 13, wherein, in response to failure of the atomic command, the processor is configured to re-read the current data elements and the current redundancy element from the storage devices, to re-calculate the redundancy element and to re-attempt updating the redundancy element using the atomic command.

15. The apparatus according to claim 9, wherein the processor is configured to store respective timestamps with the data elements, and to store with the redundancy element a list of the timestamps of the data elements over which the redundancy element was calculated.

16. The apparatus according to claim 15, wherein, prior to modifying the data elements, the processor is configured to verify that the timestamps of the data elements prior to the modification match the list of timestamps stored with the current redundancy element in the storage devices.

17. A computing system, comprising:

multiple storage devices; and

multiple servers, wherein at least one of the servers is configured to hold a definition of a stripe that comprises multiple memory locations on the storage devices to be used by the servers for storing multiple data elements and at least a redundancy element calculated over the data elements, and to modify one or more of the data elements in the stripe by;

executing in the storage devices an atomic command, which updates the redundancy element to reflect the modified data elements only if a current redundancy element stored in the storage devices reflects the multiple data elements prior to modification of the data elements; and

storing the modified data elements in the storage devices only in response to successful completion of the atomic command.

18. The system according to claim 17, wherein the one of the servers is configured to cache the modified data elements, the current redundancy element and the updated redundancy element in an interim memory, and to commit the modified data elements and the updated redundancy element from the interim memory to the storage devices only in response to the successful completion of the atomic command.

19. The system according to claim 17, wherein the stripe is accessible to at least one additional server, and wherein the one of the servers is configured to modify the data elements without communication with the additional server.

20. The system according to claim 17, wherein the one of the servers is configured to store respective timestamps with the data elements, and to store with the redundancy element a list of the timestamps of the data elements over which the redundancy element was calculated.

21. The apparatus according to claim 20, wherein, prior to modifying the data elements, the one of the servers is configured to verify that the timestamps of the data elements prior to the modification match the list of timestamps stored with the current redundancy element in the storage devices.

22. A method for data storage, comprising:

in a system that comprises multiple servers and multiple storage devices, holding in a server a definition of a stripe that comprises multiple memory locations on the storage devices, to be used by the servers for storing multiple data elements and at least a redundancy element calculated over the data elements; and

modifying, by the server, one or more of the data elements in the stripe by;

under a lock on at least part of the stripe, updating the redundancy element in the storage devices to reflect the modified data elements only if a current redundancy element stored in the storage devices reflects the multiple data elements prior to modification of the data elements; and

storing the modified data elements in the storage devices only in response to successful completion of the updating of the redundancy element.