Database replication using collaborative data transfers

• US 8,719,345 B2
• Filed: 05/11/2012
• Issued: 05/06/2014
• Est. Priority Date: 05/11/2012
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Reguna, Sudeep, Khan, Feroz Alam, Patel, Kant C.
• Primary Examiner(s): Ly, Anh-Vu
• Assistant Examiner(s): BOOK, PHYLLIS A
• Application Number:
  US13/469,262
• Publication Number:
  US 20130304816A1
• Time in Patent Office: 725 Days
• Field of Search: 709201-207, 709217-219, 709230-232, 709235-237, 707609-615, 707/622, 707/624, 707/625, 707/633, 707/634, 707/637, 707/802, 707807-809, 707/827, 707/828
• US Class Current: 709/204
• CPC Class Codes: H04L 67/1076 Resource dissemination mechanisms or network resource keeping policies for optimal resource availability in the overlay network
• CPC Class Codes: H04L 67/108 characterised by resources being split in blocks or fragments
• CPC Class Codes: H04L 67/1095 Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes

Abstract

Techniques are described herein for propagating continuously generated data from a seed to a plurality of peers without requiring the seed to send the new data to all peers, and without establishing static sender/receiver relationships between the peers. The data generated by the seed is divided into a number of “windows”, where each window is divided into a number of “pieces”. The seed sends the data piece-by-piece to different peers. The peer to which the seed sends any given piece may be selected at random. The peers exchange pieces until all pieces of a window are obtained by each peer. When a peer receives all pieces of a window, the pieces are applied at the peer, and the process repeats for the next window.

Claims

1. A method comprising:

causing a seed that continuously generates data to send the data to a plurality of peers;

wherein the data is divided into windows, and each window is divided into pieces;

wherein the seed sends the data on a piece-by-piece basis;

wherein the seed sends each piece to fewer than all of the plurality of peers;

a) causing each peer of the plurality of peers to maintain metadata that indicates;

pieces, belonging to an active window, that have been received by the peer from the seed, wherein the active window is a window;

for which the peer has not received all of the pieces; and

that has been open longer, within the peer, than any other open window within the peer;

pieces, belonging to the active window, that are available from each other peer;

b) based on the metadata, each peer requesting pieces that the peer does not yet have, belonging to the active window, from other peers until each peer has all pieces that belong to the active window;

c) each peer, in response to receiving a piece belonging to the active window, informing the other peers about having received the piece; and

d) after a peer has received all pieces of the active window and the active window has been closed, the peer establishing as a new active window, the open window that has been open longer, within the peer, than any other open window within the peer, and repeating steps (a) to (c) for the new active window;

wherein the method is performed by one or more computing devices.

2. The method of claim 1 wherein the seed sends each piece to one or more randomly selected peers of the plurality of peers.

3. The method of claim 1 wherein the seed sends each piece to exactly one peer of the plurality of peers.

4. The method of claim 1 wherein the seed sends each piece to one or more peers that are selected from the plurality of peers on a round-robin basis.

5. The method of claim 1 wherein each peer applies the pieces that belong to any given window only after receiving all pieces of that given window.

6. The method of claim 1 wherein the seed continues to send pieces for a window that follows the active window to the peers while the peers are exchanging with each other pieces from the active window.

7. The method of claim 1 wherein the seed is a primary database, the data generated by the seed contains changes that are made by transactions executed against the primary database, and the peers are standby databases that maintain replicas of data from the primary database.

8. The method of claim 1 wherein the step of each peer requesting pieces that the peer does not yet have includes each peer:

determining which piece, that the peer does not yet have, is available from the fewest peers; and

requesting the piece that the peer does not yet have that is available from the fewest peers.

9. The method of claim 8 wherein, if there is a tie among pieces that are available from the fewest peers, randomly selecting a piece from among the pieces involved in the tie.

10. The method of claim 1 wherein, if the piece that a peer selects to request is available from multiple peers, then the peer selecting randomly which peer, among the multiple peers, from which to request the piece.

11. One or more non-transitory storage media storing instructions which, when executed by one or more computing devices, cause performance of a method comprising:

causing a seed that continuously generates data to send the data to a plurality of peers;

wherein the data is divided into windows, and each window is divided into pieces;

wherein the seed sends the data on a piece-by-piece basis;

wherein the seed sends each piece to fewer than all of the plurality of peers;

a) causing each peer of the plurality of peers to maintain metadata that indicates;

pieces, belonging to an active window, that have been received by the peer from the seed, wherein the active window is a window;

for which the peer has not received all of the pieces; and

that has been open longer, within the peer, than any other open window within the peer;

pieces, belonging to the active window, that are available from each other peer;

b) based on the metadata, each peer requesting pieces that the peer does not yet have, belonging to the active window, from other peers until each peer has all pieces that belong to the active window;

c) each peer, in response to receiving a piece belonging to the active window, informing the other peers about having received the piece; and

d) after a peer has received all pieces of the active window and the active window has been closed, the peer establishing as a new active window, the open window that has been open longer, within the peer, than any other open window within the peer, and repeating steps (a) to (c) for the new active window.

12. The one or more non-transitory storage media of claim 11 wherein the seed sends each piece to one or more randomly selected peers of the plurality of peers.

13. The one or more non-transitory storage media of claim 11 wherein the seed sends each piece to exactly one peer of the plurality of peers.

14. The one or more non-transitory storage media of claim 11 wherein the seed sends each piece to one or more peers that are selected from the plurality of peers on a round-robin basis.

15. The one or more non-transitory storage media of claim 11 wherein each peer applies the pieces that belong to any given window only after receiving all pieces of that given window.

16. The one or more non-transitory storage media of claim 11 wherein the seed continues to send pieces for a window that follows the active window to the peers while the peers are exchanging with each other pieces from the active window.

17. The one or more non-transitory storage media of claim 11 wherein the seed is a primary database, the data generated by the seed contains changes that are made by transactions executed against the primary database, and the peers are standby databases that maintain replicas of data from the primary database.

18. The one or more non-transitory storage media of claim 11 wherein the step of each peer requesting pieces that the peer does not yet have includes each peer:

determining which piece, that the peer does not yet have, is available from the fewest peers; and

requesting the piece that the peer does not yet have that is available from the fewest peers.

19. The one or more non-transitory storage media of claim 18 wherein, if there is a tie among pieces that are available from the fewest peers, randomly selecting a piece from among the pieces involved in the tie.

20. The one or more non-transitory storage media of claim 11 wherein, if the piece that a peer selects to request is available from multiple peers, then the peer selecting randomly which peer, among the multiple peers, from which to request the piece.