APPEND-BASED SHARED PERSISTENT STORAGE

• US 20100191919A1
• Filed: 01/27/2009
• Published: 07/29/2010
• Est. Priority Date: 01/27/2009
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Reid, Colin W., Bernstein, Philip A.
• Granted Patent: US 8,347,050 B2
• Time in Patent Office: Days
• US Class Current: 711/141
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 2212/1036 Life time enhancement
• CPC Class Codes: G06F 2212/7211 Wear leveling
• CPC Class Codes: G06F 3/0623 in relation to content
• CPC Class Codes: G06F 3/0638 Organizing or formatting or addressing of data
• CPC Class Codes: G06F 3/0659 Command handling arrangements, e.g. command buffers, queues, command scheduling
• CPC Class Codes: G06F 3/0679 Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]
• CPC Class Codes: G06F 3/0688 Non-volatile semiconductor memory arrays

Abstract

A shared storage system is described herein that is based on an append-only model of updating a storage device to allow multiple computers to access storage with lighter-weight synchronization than traditional systems and to reduce wear on flash-based storage devices. Appending data allows multiple computers to write to the same storage device without interference and without synchronization between the computers. Computers can also safely read a written page without using synchronization because the system limits how data can be changed once written. The system may record a log of append operations performed and ensure idempotence by storing a key specified by the caller in the log along with each log entry. The system also provides broadcasts about appended data to computers so that coordination between computers can occur without direct communication between the computers.

Claims

1. A computer-implemented method for synchronized, shared access to a storage device, the method comprising:

receiving a request from a caller to store data to the storage device, wherein the request specifies an append operation and does not specify an address to which to store the data;

writing the data in the request to a next available address so that multiple callers can write data to the storage device at the same time without synchronizing with one another, wherein the next available address is a sequential storage address of the storage device that is subsequent to a previously written address;

incrementing the next available address for subsequent append operations;

returning the address to which the data was written to the caller,

wherein the preceding steps are performed by at least one processor.

2. The method of claim 1 wherein the request includes a key that distinguishes the data from other data and further comprising writing the address to which the data was written and the key specified in the request to a log of append operations.

3. The method of claim 2 further comprising:

before writing the data, looking up the key in the log of append operations that includes pairs of keys and addresses where data associated with the keys is stored; and

if the key is found in the log, returning the address from the log.

4. The method of claim 1 wherein the request includes an address returned to the caller by a previous append operation, and further comprising:

before writing the data, comparing the received address to a lowest address in any log entry stored in a log of previous append operations; and

if the received address is lower than the lowest address stored in the log, returning the lowest address stored in the log to the caller.

5. The method of claim 1 wherein the request includes a concurrency range within which the caller requests storage of the data, and further comprising, if the next address to which the component will append data is not within the concurrency range specified in the request, returning an error indicating that the concurrency range cannot be satisfied.

6. The method of claim 1 wherein the storage device is a flash-based memory device that exhibits wear when data is erased.

7. A computer system for sharing one or more storage devices among multiple computers, the system comprising:

a processor and memory configured to execute software instructions;

a communication component configured to send and receive communications over a network between the system and one or more computers that store data with the system;

an application-programming interface (API) component configured to provide an application interface that computers can invoke over the network using a predefined protocol for appending pages to the storage devices;

an append component configured to handle append operation requests received from computers through the API component, wherein handling append operation requests includes receiving an append request, retrieving a next page location, storing data from the append request to the next page location, and incrementing the next page location;

a device manager component configured to manage the storage devices 180 associated with the system; and

one or more storage devices that provide persistent storage.

8. The system of claim 7 wherein the communication component includes redundant network interfaces for communicating with computers along multiple communication channels and wherein the append component is further configured to receive at least some requests concurrently on multiple communications channels sent redundantly from the same computer.

9. The system of claim 7 further comprising a log component configured to store a log of each successful append operation so that computers can verify whether a computer has already written data corresponding to a key specified in an append request.

10. The system of claim 7 wherein the append component is further configured to respond to the append request by providing the address at which the append component stored the page.

11. The system of claim 7 further comprising a read component configured to handle read operation requests received from computers, wherein a computer can read a page of stored data by providing the address of the stored data through the API component to the read component.

12. The system of claim 7 further comprising an erase component configured to handle erase operation requests received from computers, wherein a computer cannot modify pages except by erasing a whole page.

13. The system of claim 7 wherein the append component is further configured to check the log component for an entry with a key matching the key in the append request before writing the data.

14. The system of claim 7 wherein the device manager component is further configured to route requests received from other components to an appropriate storage device based on a segment identifier received in an operation request.

15. The system of claim 7 further comprising an update component configured to provide updates about data written to the storage devices to computers sharing the storage devices.

16. The system of claim 15 wherein an append request specifies whether the update component sends information about the append request to computers sharing the storage devices.

17. A computer-readable storage medium comprising instructions for controlling a computer system to distribute updates of a storage device to multiple computers sharing the storage device, wherein the instructions, when executed, cause a processor to perform actions comprising:

detecting an update event that signals that there is new data with which to update the computers;

composing update data, wherein the update data includes an address at which the new data is stored in the storage device; and

sending the composed update data to the multiple computers, wherein each of the computers coordinates sharing of the storage device by receiving the update data and without communicating directly with the other computers,

wherein the update data includes information that a receiving computer can use to determine whether an append operation of the receiving computer modifies a data structure shared with other computers through the shared storage device.

18. The computer-readable medium of claim 17 wherein the detected update event comprises receiving an append request with an update indication set that indicates whether information about the append request is sent to other computers.

19. The computer-readable medium of claim 17 further comprising if the receiving computer determines that an append operation of the receiving computer modifies a data structure shared with other computers through the shared storage device after another computer modified the shared data structure, retrying the append operation.

20. The computer-readable medium of claim 17 further comprising receiving a request to read the new data from the storage device, wherein the request to read includes the address at which the new data is stored.