Dynamic Data Reorganization to Accommodate Growth Across Replicated Databases

• US 20090157762A1
• Filed: 12/14/2007
• Published: 06/18/2009
• Est. Priority Date: 12/14/2007
• Status: Active Grant

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Srivastava, Utkarsh, Weaver, Daniel, Cooper, Brian, Yerneni, Ramana V., Bigby, Michael, Feng, Andrew, Call, Bryan, Bohannon, Philip, Ramakrishnan, Raghu, Lomax, David
• Granted Patent: US 7,958,088 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/273 Asynchronous replication or reconciliation

Abstract

Methods and apparatuses are provided for dynamically reorganizing the data within a replicated database system. One method, for example, includes performing a split operation across a plurality of replicated databases with regard to an existing partition therein, wherein the existing partition comprises a plurality of data records and the two new partitions each include at least a portion of the plurality of data records, and allowing at least one type of access to the plurality of data records during the split operation.

Claims

1. A method comprising:

determining that at least one existing partition within a database provided through a plurality of replicated databases is to be split into at least two new partitions;

performing a split operation that is to be applied across said plurality of replicated databases with regard to said existing partition, wherein said existing partition comprises a plurality of data records and said at least two new partitions each comprise at least a portion of said plurality of data records; and

during said split operation, allowing at least one type of access to said plurality of data records.

2. The method as recited in claim 1, wherein determining that said existing partition is to be split into at least two new partitions comprises determining that said existing partition is to be split into at least two new partitions using at least one of said plurality of replicated databases.

3. The method as recited in claim 1, wherein at least one of said at least one type of access comprises at least one operation selected from a group of operations comprising a read operation, an update operation, an insert operation, and a delete operation.

4. The method as recited in claim 1, wherein performing said split operation comprises providing a PREPARE message to said plurality of replicated databases indicating that said existing partition is to be split into said at least two new partitions.

5. The method as recited in claim 4, wherein performing said split operation comprises, in response to said PREPARE message, having each of said plurality of databases that agrees to said split operation respond with a PREPARED message.

6. The method as recited in claim 5, wherein performing said split operation comprises, in response to said PREPARED messages from each of said plurality of replicated databases, providing a COMMIT message to said plurality of replicated databases.

7. The method as recited in claim 6, wherein performing said split operation comprises, in response to said COMMIT message, each of said plurality of replicated databases completes said split operation by operatively associating said at least two new partitions with said database and operatively disassociating said existing partition with said database.

8. The method as recited in claim 7, wherein performing said split operation comprises, in response to said COMMIT message, each of said plurality of replicated databases providing an ENDOFTOPIC message to each of said plurality of replicated databases, said ENDOFTOPIC message being associated with said existing partition.

9. The method as recited in claim 8, wherein performing said split operation comprises, in response to said ENDOFTOPIC message from each of said plurality of replicated databases, for each of said replicated databases creating at least a fuzzy copy of each of said at least two new partitions.

10. The method as recited in claim 9, wherein performing said split operation comprises, in response to said COMMIT message, at least one of said plurality of replicated databases providing at least one update message to said plurality of replicated databases, said at least one update message being associated with at least one data record in one of said at least two new partitions.

11. The method as recited in claim 10 wherein, performing said split operation comprises, for each of said plurality of replicated databases, storing said at least one update message and applying said stored update message to said at least one data record in one of said at least two new partitions to change at least one said fuzzy copy into a sharp copy.

12. The method as recited in claim 8, wherein performing said split operation comprises, in response to said ENDOFTOPIC message from each of said plurality of replicated databases, for each of said replicated databases creating a sharp copy of each of said at least two new partitions.

13. The method as recited in claim 4, wherein performing said split operation comprises, in response to said PREPARE message, for each of said plurality of databases that is unable to support said split operation providing a REJECTED message to said plurality of databases.

14. The method as recited in claim 13, wherein performing said split operation comprises, in response to at least one said REJECTED message, providing an ABORT message to said plurality of replicated databases.

15. A system comprising:

a management system; and

a plurality of replicated databases, said plurality of replicated databases being operatively coupled together and to said management system, and wherein said management system initiates a split operation that is to be applied across said plurality of replicated databases with regard to at least one existing partition comprising a plurality of data records, said split operation being configured to split said at least one existing partition into at least two new partitions each comprising at least a portion of said plurality of data records, and wherein during said split operation at least one type of access is provided to said plurality of data records.

16. The system as recited in claim 15, wherein at least one of said plurality of replicated databases comprises said management system at least with regard to said at least one existing partition.

17. The system as recited in claim 15, wherein as part of said split operation said management system provides a PREPARE message to said plurality of replicated databases indicating that said existing partition is to be split into said at least two new partitions.

18. The system as recited in claim 17, wherein, in response to said PREPARE message, each of said plurality of databases that agrees to said split operation provides a PREPARED message to at least said management system, wherein, in response to said PREPARED messages from each of said plurality of replicated databases, said management system provides a COMMIT message to said plurality of replicated databases, and wherein, in response to said COMMIT message each of said plurality of replicated databases completes said split operation by operatively associating said at least two new partitions with said replicated database and operatively disassociating said existing partition with said replicated database.

21. The system as recited in claim 17, wherein, in response to said PREPARE message, each of said plurality of databases that is unable to support said split operation provides a REJECTED message to said plurality of databases, and wherein, in response to at least one said REJECTED message, said management system an ABORT message to said plurality of replicated databases and said split operation is cancelled.

19. The system as recited in claim A5, wherein, in response to said COMMIT message each of said plurality of replicated databases provides an ENDOFTOPIC message to each of said plurality of replicated databases, said ENDOFTOPIC message being associated with said existing partition, wherein, in response to said COMMIT message at least one of said plurality of replicated databases provides at least one update message to said plurality of replicated databases, said at least one update message being associated with at least one data record in one of said at least two new partitions, and, wherein, each of said plurality of replicated databases store said at least one update message applies said stored update message to said at least one data record in one of said at least two new partitions in response to said ENDOFTOPIC message from each of said plurality of replicated databases.

20. The system as recited in claim 19, wherein, in response to said ENDOFTOPIC message from each of said plurality of replicated databases, each of said replicated databases creates at least a fuzzy copy or at least one sharp copy of each of said at least two new partitions while continuing to provide said at least one type of access to said existing partition

22. A computer program product, comprising computer-readable medium comprising instructions for causing a processing unit to:

perform a split operation that is to being applied across a plurality of replicated databases with regard to an existing partition therein, wherein said existing partition comprises a plurality of data records and said at least two new partitions each comprise at least a portion of said plurality of data records; and

allow at least one type of access to said plurality of data records during said split operation.