Massively scalable object storage system

• US 9,021,137 B2
• Filed: 10/07/2013
• Issued: 04/28/2015
• Est. Priority Date: 03/08/2011
• Status: Expired due to Fees

• Current Assignee: Rackspace US Incorporated (Apollo Global Management, Inc.)
• Original Assignee: Rackspace US Incorporated (Apollo Global Management, Inc.)
• Inventors: Barton, Michael, Reese, Will, Dickinson, John A., Payne, Jay B., Thier, Charles B., Holt, Gregory
• Primary Examiner(s): Meky, Moustafa M
• Application Number:
  US14/047,332
• Publication Number:
  US 20140040505A1
• Time in Patent Office: 568 Days
• Field of Search: 709200-203, 709217-227, 709/248, 375/355, 370/401, 370/503
• US Class Current: 709/248
• CPC Class Codes: G06F 1/12 Synchronisation of different clock signals provided by a plurality of clock generators
• CPC Class Codes: G06F 16/2322 using timestamps
• CPC Class Codes: G06F 16/24573 using data annotations, e.g. user-defined metadata
• CPC Class Codes: G06F 16/275 Synchronous replication
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 2201/82 Solving problems relating to consistency ensuring consistency in mirrored systems G06F11/2064
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: G06F 3/0671 In-line storage system
• CPC Class Codes: H04L 67/1095 Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes
• 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

Several different embodiments of a massively scalable object storage system are described. The object storage system is particularly useful for storage in a cloud computing installation whereby shared servers provide resources, software, and data to computers and other devices on demand. In several embodiments, the object storage system includes a ring implementation used to associate object storage commands with particular physical servers such that certain guarantees of consistency, availability, and performance can be met. In other embodiments, the object storage system includes a synchronization protocol used to order operations across a distributed system. In a third set of embodiments, the object storage system includes a metadata management system. In a fourth set of embodiments, the object storage system uses a structured information synchronization system. Features from each set of embodiments can be used to improve the performance and scalability of a cloud computing object storage system.

Claims

1. A method for coordinating events in a distributed system, comprising:

synchronizing a master clock to coordinated universal time within a master skew threshold;

synchronizing a first local clock at a first gateway with the master clock within a system skew threshold, and synchronizing a second local clock at a second gateway with the master clock within the system skew threshold;

receiving, at the first gateway, a first request to manipulate a non-volatile data storage, and marking the first request with the time of reception according to the first local clock, with a granularity at least equal to the system skew threshold;

receiving, at the second gateway, a second request to manipulate the non-volatile data storage, and marking the second request with the time of reception according to the second local clock, with a granularity at least equal to the system skew threshold;

evaluate the first request and the second request to determine if they are unambiguously ordered by determining if the first request and the second request are temporally ordered with a granularity greater than the system skew threshold;

if the first request and the second request are unambiguously ordered, modifying the non-volatile data storage as directed in the later request; and

if the first request and the second request are not unambiguously ordered, modifying the non-volatile data storage as directed by a deterministic tiebreaker.

2. The method of claim 1, wherein the master skew threshold is less than or equal to a tenth of a second.

3. The method of claim 1, wherein the system skew threshold is less than or equal to a millisecond.

4. The method of claim 1, wherein the system skew threshold is less than or equal to a microsecond.

5. The method of claim 1, wherein the tiebreaker prevents modification of the non-volatile data storage.

6. The method of claim 1, wherein the tiebreaker measures the latency between the first gateway and a first address where the first request originated, and further measures the latency between the second gateway and a second address where the second request originated, and modifies the non-volatile storage according to the request exhibiting lower latency.

7. The method of claim 1, wherein the tiebreaker measures the geographic distance between the first gateway and a first address where the first request originated, and further measures the geographic distance between the second gateway and a second address where the second request originated, and modifies the non-volatile storage according to the request originating from a geographically closer address.

8. The method of claim 1, wherein the tiebreaker evaluates whether a merged request can be created including both the changes associated with the first request and the changes associated with the second request, and if so, modifies the non-volatile storage according to merged request.

9. A non-transient computer readable medium containing executable instructions, which when executed on a processor:

synchronizes a first local clock with a second local clock within a system skew threshold;

receives a first request to manipulate a system resource and marks the first request with the time of reception according to the first local clock, with a granularity at least equal to the system skew threshold;

receives a second request to manipulate the system resource and marks the second request with the time of reception according to the second local clock, with a granularity at least equal to the system skew threshold;

evaluates the first request and the second request to determine if they are unambiguously ordered by determining if the first request and the second request are temporally ordered with a granularity greater than the system skew threshold;

if the first request and the second request are unambiguously ordered, manipulates the system resource as directed in the later request; and

if the first request and the second request are not unambiguously ordered, executes tiebreaker instructions controlling the system resource; and

returns a success or error depending on the outcome of the tiebreaker instructions.

10. The non-transient computer readable medium of claim 9, wherein the tiebreaker instructions attempt to create a merged request, and returns success if the system resource can be manipulated according to the merged request, and error otherwise.

11. The non-transient computer readable medium of claim 9, wherein system skew threshold is less than or equal to one millisecond.