Openstack database replication

• US 20120233119A1
• Filed: 04/19/2011
• Published: 09/13/2012
• 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
• Granted Patent: US 8,510,267 B2
• Time in Patent Office: Days
• US Class Current: 707/622
• CPC Class Codes: G06F 11/1004 to protect a block of data words, e.g. CRC or checksum G06F11/1076 takes precedence; security arrangements for protecting computers or computer systems against unauthorized activity G06F21/00
• CPC Class Codes: G06F 11/2097 maintaining the standby controller/processing unit updated initialisation or re-synchronisation thereof G06F11/1658 and subgroups
• CPC Class Codes: G06F 16/1744 using compression, e.g. sparse files
• CPC Class Codes: G06F 16/1748 De-duplication implemented within the file system, e.g. based on file segments de-duplication techniques in storage systems for the management of data blocks G06F3/0641
• CPC Class Codes: G06F 16/178 Techniques for file synchronisation in file systems
• CPC Class Codes: G06F 16/2219 Large Object storage; Management thereof
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
• CPC Class Codes: G06F 16/273 Asynchronous replication or reconciliation
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9566 URL specific, e.g. using aliases, detecting broken or misspelled links
• CPC Class Codes: G06F 2201/85 Active fault masking without idle spares active fault masking without idle spare hardware where processing functionality is redundant G06F11/2035
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0626 Reducing size or complexity of storage systems
• CPC Class Codes: G06F 3/0644 Management of space entities, e.g. partitions, extents, pools
• CPC Class Codes: G06F 3/065 Replication mechanisms
• 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 43/106 using time related information in packets, e.g. by adding timestamps
• CPC Class Codes: H04L 65/403 Arrangements for multi-party communication, e.g. for conferences data switching systems for conference H04L12/18; arrangements for connecting several subscribers to a common circuit, i.e. affording conference facilities H04M3/56; television conferencing systems H04N7/15
• CPC Class Codes: H04L 67/06 specially adapted for file transfer, e.g. file transfer protocol [FTP]
• 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]
• CPC Class Codes: H04L 67/5651 : Reducing the amount or size of exchanged application data
• CPC Class Codes: H04L 69/04 : Protocols for data compression, e.g. ROHC

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 distributed information synchronization system, comprising:

a first subsidiary node coupled to a network, the first subsidiary node including a first non-transitory computer-readable medium wherein the first computer-readable medium includes a first structured information repository, and wherein information in the first structured information repository is subject to internal consistency constraints;

a second subsidiary node coupled to a network, the second subsidiary node including a second non-transitory computer-readable medium wherein the second computer-readable medium includes a second structured information repository, and wherein information in the second structured information repository is subject to internal consistency constraints;

a repository synchronizer coupled to the first and second structured information repositories;

the repository synchronizer further including;

a consistency evaluation module adapted to evaluate the differences between the first structured information repository and the second structured information repository;

an internal modification module adapted to modify the internal structures of a structured information repository;

an external replication module adapted to delete a target structured information repository and replace it with a replicated copy of a source structured information repository; and

a threshold comparator;

wherein the repository synchronizer is adapted to;

evaluate the first and second structured information repositories and determine a level of difference and compare the level of difference to a configurable threshold using the threshold comparator;

if the level of difference is above the configurable threshold, modify the internal structures of a selected structured information repository using the internal modification module;

if the level of difference is below the configurable threshold, delete the selected structured information repository and replace it with a replicated copy of a consistent structured information repository using the external replication module.

2. The system of claim 1, wherein the differences between the first and second structured information repositories are caused by changes over time.

3. The system of claim 1, wherein both the first and second structured information repositories include differences, and wherein repository synchronizer uses the internal modification module to synchronize the first information repository and uses the external replication module to synchronize the second information repository.

4. The system of claim 1, wherein the structured information repositories are structured as on-disk databases.

5. The system of claim 4, wherein the databases are relational.

6. The system of claim 4, wherein the databases are structured as one of a tree and a graph.

7. The system of claim 1, wherein the external replication module uses the rsync protocol.

8. The system of claim 1, wherein the internal consistency constraints consist of an order-independent checksum.

9. A method for synchronizing structured information in a distributed system, comprising:

storing a first structured information repository on a first non-transitory computer-readable medium, wherein information in the first structured information repository is subject to internal consistency constraints;

storing a second structured information repository on a second non-transitory computer-readable medium, wherein information in the second structured information repository is subject to internal consistency constraints;

evaluating the differences between the first structured information repository and the second structured information repository to determine a preferred state and a difference measurement quantifying a difference from the preferred state;

determining whether the difference measurement exceeds a configurable threshold;

modifying a selected structured information repository if the difference measurement for the selected structured information repository is less than the configurable threshold, wherein the modification of the selected structured information repository is subject to the internal consistency constraints of the selected structured information repository,

deleting the selected structured information repository if the difference measurement for the selected structured information repository is greater than the configurable threshold, and replacing the selected structured information repository with a replica of a structured information repository in the preferred state,

wherein either modifying the selected structured information repository or deleting and replacing the structured information repository changes the non-transitory computer-readable medium storing the selected structured information repository such that the selected structured information repository is both compliant with its internal consistency constraints and in the preferred state.

10. The method of claim 9, wherein the difference measurement measures changes over time.

11. The method of claim 10, wherein the preferred state is determined by examining all the changes to the first structured information repository up to the time of evaluation.

12. The method of claim 10, wherein the preferred state is determined by including all the changes to multiple structured information repositories up to the time of evaluation.

13. The method of claim 9, wherein the selected structured information repository is the first structured information repository, and the structured information repository in the preferred state is the second structured information repository.

14. The method of claim 9, the method further comprising:

after evaluating the differences between the first structured information repository and the second structured information repository, but before determining whether the difference measurement exceeds a configurable threshold;

determining that both the first structured information repository and the second structured information repository are not in the preferred state;

pre-selecting the structured information repository that is closer to the preferred state and modifying the pre-selected structured information repository to bring the pre-selected structured information repository to the preferred state, subject to the internal consistency requirements of the pre-selected structured information repository, regardless of the configurable threshold.

15. The method of claim 9, wherein replacing the selected structured information repository with a replica of a structured information repository is done via the rsync protocol.

16. The method of claim 9, wherein the internal consistency constraints consist of an order-independent checksum.

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

update a first structured information repository on a first non-transitory computer-readable medium, subject to internal consistency constraints;

update a second structured information repository on a second non-transitory computer-readable medium, subject to internal consistency constraints;

evaluate the differences between the first structured information repository and the second structured information repository to determine a preferred state and a difference measurement quantifying a difference from the preferred state;

determine whether the difference measurement exceeds a configurable threshold;

modify a selected structured information repository if the difference measurement for the selected structured information repository is less than the configurable threshold, subject to the internal consistency constraints of the selected structured information repository,

delete the selected structured information repository if the difference measurement for the selected structured information repository is greater than the configurable threshold, and replace the selected structured information repository with a replica of a structured information repository in the preferred state.

18. The non-transient computer readable medium of claim 17, further including instructions that determine that both the first structured information repository and the second structured information repository are not in the preferred state;

pre-select the structured information repository that is closer to the preferred state and modify the pre-selected structured information repository to bring the pre-selected structured information repository to the preferred state, subject to the internal consistency requirements of the pre-selected structured information repository, regardless of the configurable threshold.

19. The non-transient computer readable medium of claim 17, wherein the instructions modifying the selected structured information repository, when executed, perform a series of set operations on the selected structured information repository.

20. The non-transient computer readable medium of claim 17, wherein the instructions modifying the selected structured information repository, when executed, perform a series of graph operations on the selected structured information repository.