Massively scalable object storage system

• US 9,626,420 B2
• Filed: 04/24/2015
• Issued: 04/18/2017
• Est. Priority Date: 03/08/2011
• Status: Active Grant

• 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/695,847
• Publication Number:
  US 20150227606A1
• Time in Patent Office: 725 Days
• 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 system for coordinating events in a distributed system, comprising:

a plurality of subsidiary nodes coupled to a network, each subsidiary node including at least one processor, a computer-readable medium, and a communications interface, wherein information in a first subsidiary node needs to be synchronized with information in a second subsidiary node in response to a time-varying series of requests;

a first gateway including a first local clock and a first communications interface;

a second gateway including a second local clock and a second communications interface;

a timekeeping node coupled to the network, the timekeeping node including a master clock; and

a synchronization rectifier coupled to the first and second subsidiary nodes;

wherein the timekeeping node is coupled to the first and second gateways and reduces clock skew between the master clock, the first local clock, and the second local clock below a configurable threshold;

wherein the first gateway timestamps a first request received over the first communications interface according to the time of the first local clock with a granularity at least equal to the configurable threshold;

wherein the second gateway timestamps a second request received over the second communications interface according to the time of the second local clock with a granularity at least equal to the configurable threshold;

wherein synchronization between the first subsidiary node and the second subsidiary node is controlled by the synchronization rectifier if the first request and the second request are separated by a time smaller than the configurable threshold; and

wherein the configurable threshold is based on analyzing a pattern of accesses to the information in the first and second subsidiary nodes over time.

2. The system of claim 1, wherein synchronization between the first subsidiary node and the second subsidiary node is controlled by the later-occurring request if the first request and the second request are separated by a time greater than the configurable threshold.

3. The system of claim 2, wherein the system further comprises a replicator that copies information between the first subsidiary node and the second subsidiary node at a third time, wherein the replicator copies information between the second subsidiary node and the first subsidiary node at a fourth time, wherein the synchronization rectifier controls synchronization by ordering the requests according to which of the third and fourth times comes first.

4. The system of claim 1, wherein the synchronization rectifier controls synchronization by returning an error and preventing either request from completing.

5. The system of claim 4, wherein the returned error requests manual intervention.

6. The system of claim 1, wherein the synchronization rectifier controls synchronization by using geolocation associated with the request and ordering the requests according to geographical proximity.

7. The system of claim 6, wherein the geolocation associated with the request corresponds to a geolocation of the requesting IP address.

8. The system of claim 1, wherein the synchronization rectifier controls synchronization by using latency measurements between the first gateway and the first request, and the second gateway and the second request, and ordering the requests according to observed latency.

9. The system of claim 1, wherein the synchronization rectifier controls synchronization by ordering the requests according to information contained in HTTP headers.

10. The system of claim 1, wherein the synchronization rectifier controls synchronization by ordering the requests according to information contained in the body of the request.

11. The system of claim 1, wherein the configurable threshold is less than or equal to a millisecond.

12. The system of claim 1, wherein the configurable threshold is less than or equal to a microsecond.

13. The system of claim 1, wherein the timestamp on the first request is stored as metadata.

14. The system of claim 1, wherein the timestamp on the second request is stored as metadata.

15. The system of claim 1, wherein the synchronization rectifier detects the attempted simultaneous access of the information in the first subsidiary node and the information in the second subsidiary node.

16. The system of claim 15, wherein the synchronization rectifier controls synchronization by returning an error.

17. The system of claim 16, wherein the synchronization rectifier prevents the first and second requests from completing.

18. The system of claim 15, wherein the synchronization rectifier evaluates the first and second requests to determine whether the first and second requests can be merged.

19. The system of claim 18, wherein the synchronization rectifier determines that the first and second requests can be merged.

20. The system of claim 19, wherein the synchronization rectifier controls synchronization by granting the first and second requests.