Massively scalable object storage system

• US 9,898,521 B2
• Filed: 04/17/2017
• Issued: 02/20/2018
• 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:
  US15/489,615
• Publication Number:
  US 20170220662A1
• Time in Patent Office: 309 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
• 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 subsidiary node including a first local clock, the first local clock being set according to a first timeserver;

a second subsidiary node including a second local clock, the second local clock being set according to a second timeserver;

a first synchronization rectifier minimizing differences in time between the first timeserver and the second timeserver;

wherein the first local clock and the second local clock are synchronized to within an error window ε

, where ε

is greater than the maximum clock skew between the first local clock and the second local clock as determined by the first synchronization rectifier; and

wherein the synchronization rectifier implements an arbiter to resolve observed time conflicts in the distributed system.

2. The system of claim 1, wherein the arbiter implements a state machine based on the Paxos algorithm.

3. The system of claim 1, wherein the arbiter implements an algorithm designed to identify erroneous updates.

4. The system of claim 3, wherein the algorithm designed to identify erroneous updates is based on the Byzantine Generals algorithm.

5. The system of claim 1, wherein the absolute time is guaranteed to be within the error window designated by ε

.

6. The system of claim 1, wherein the maximum time deviation between the first local clock and the second local clock is denoted by t, and ε

≧

2t.

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

a geographically distributed storage across which data can be replicated, the geographically distributed storage comprising at least a first zone and a second zone, the two zones communicatively coupled with each other, wherein each zone is defined by a probable correlated loss of access or data;

each zone including a storage management server, a storage pool, a timeserver, and a synchronization rectifier,

the storage pool comprising a plurality of storage nodes, including at least a first storage node and a second storage node, each storage node including at least one processor, a computer-readable medium, a communications interface, and a local clock;

wherein each storage zone associates a timestamp with the data received in a time-varying series of requests to interact with the storage pool;

wherein each timestamp associated with a received datum is provided according to a rectified time, the rectified time being adjusted by the synchronization rectifier in response to values provided by at least the local timeserver; and

wherein the synchronization rectifier implements an arbiter to resolve observed time conflicts between a local timeserver and a geographically remote timeserver.

8. The system of claim 7, wherein a local clock and a geographically remote clock are synchronized to within an error window ε

, where ε

is greater than the maximum clock skew between the local clock and the geographically remote clock as determined by a synchronization rectifier.

9. The system of claim 7, wherein one of the time-varying requests results in a response subject to synchronization between the first storage node and the second storage node;

and wherein the synchronization is performed according to the Paxos algorithm.

10. The system of claim 7, wherein the synchronization rectifier implements an algorithm designed to identify erroneous updates from one or more timeservers.

11. The system of claim 10, wherein a local clock is synchronized based upon the time provided by the synchronization rectifier.

12. The system of claim 10, wherein the algorithm designed to identify erroneous updates is based on the Byzantine Generals algorithm.

13. The system of claim 8, wherein a read-only request returns data that has an associated timestamp greater than or equal to the local time−

ε

.

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

providing a geographically distributed storage across which data can be replicated, the geographically distributed storage comprising at least a first zone and a second zone, the two zones communicatively coupled with each other, wherein each zone is defined by a probable correlated loss of access or data;

providing within each zone a timeserver and a plurality of subsidiary nodes coupled to a communications network, each subsidiary node including at least one processor, a computer-readable medium, and a communications interface, a first subsidiary node including a first local clock and a second subsidiary node including a second local clock;

minimizing the differences in time between a first timeserver in the first zone and a second timeserver in the second zone via a first synchronization rectifier, such that the first local clock and the second local clock in the first zone are synchronized to within an error window ε

, where ε

is greater than a maximum clock skew as determined by the first synchronization rectifier; and

wherein the synchronization rectifier implements an arbiter to resolve observed time conflicts between the first timeserver and the second timeserver in the distributed system.

15. The system of claim 14, wherein a third local clock in the second zone is synchronized with the first local clock and the second local clock to within ε

.

16. The system of claim 14, wherein the arbiter implements an algorithm designed to identify erroneous updates.

17. The system of claim 16, wherein the algorithm designed to identify erroneous updates is based on the Byzantine Generals algorithm.

18. The system of claim 14, wherein the absolute time is guaranteed to be within the error window designated by ε

.

19. The system of claim 14, wherein the maximum time deviation between the first local clock and the second local clock is denoted by t, and ε

≧

2t.

20. The system of claim 14, further comprising receiving a request to access data stored in the system.