OBJECT REPLICATION FRAMEWORK FOR A DISTRIBUTED COMPUTING ENVIRONMENT

• US 20140089619A1
• Filed: 09/27/2012
• Published: 03/27/2014
• Est. Priority Date: 09/27/2012
• Status: Active Application

• Current Assignee: Infinera Corp.
• Original Assignee: Infinera Corp.
• Inventors: Misra, Mohit, Kunjidhapatham, Ashok, Lu, Biao, Pithewan, Khuzema, KHANNA, Vinay
• Application Number:
  US13/629,191
• Publication Number:
  US 20140089619A1
• Time in Patent Office: Days
• US Class Current: 711/166
• CPC Class Codes: G06F 16/273 Asynchronous replication or reconciliation
• CPC Class Codes: G06F 3/0652 Erasing, e.g. deleting, data cleaning, moving of data to a wastebasket

Abstract

A device may receive information that identifies a data item and a data item operation. The device may store a first sequence identifier, a data item reference that references the data item, and an operation reference that references the operation. The first sequence identifier may reference the data item and operation references, and may indicate an order in which the first sequence identifier is stored. The device may store the data item in a memory location, may store an identification of the memory location, may remove a reference to the data item by a previous sequence identifier, and/or may add the data item, may modify the data item, or may delete the data item depending on whether the operation is an add operation, a modify operation, or a delete operation. The device may transmit, to a slave device, the first sequence identifier, the data item reference, and the operation reference.

Claims

1. A device, comprising:

one or more processors to;

receive information that identifies a data item;

receive information that identifies an operation to perform on the data item, the operation comprising at least one of an add operation, a modify operation, or a delete operation;

store, in a memory, a first sequence identifier, a data item reference that references the data item, and an operation reference that references the operation, the first sequence identifier referencing the data item reference and the operation reference and indicating an order in which the first sequence identifier is stored;

determine that the operation is one of the add operation, the modify operation, or the delete operation;

if the operation is the add operation;

store the data item in the memory at a first memory location; and

associate information that identifies the first memory location with the first sequence identifier;

if the operation is the modify operation;

modify the data item in the memory to create a modified data item;

store the modified data item in the memory at a second memory location;

associate information that identifies the second memory location with the first sequence identifier; and

remove, from the memory, a first reference to the data item by a first previous sequence identifier that references the data item, the first previous sequence identifier being stored before the first sequence identifier; and

if the operation is the delete operation;

delete the data item from the memory; and

remove, from the memory, a second reference to the data item by a second previous sequence identifier that references the data item, the second previous sequence identifier being stored before the first sequence identifier; and

transmit, to a slave device, the first sequence identifier, the data item reference, and the operation reference.

2. The device of claim 1, where the operation is the delete operation, and the one or more processors are further to:

receive a deletion trigger, the deletion trigger indicating that an amount of time that has passed, since the first sequence identifier was stored, satisfies a threshold; and

remove, from the memory, the first sequence identifier, the data item reference, and the operation reference.

3. The device of claim 1, where the one or more processors are further to:

determine a most recently transmitted sequence identifier; and

where the one or more processors, when transmitting the first sequence identifier, are further to;

transmit the first sequence identifier based on the most recently transmitted sequence identifier, the first sequence identifier being stored in the memory after the most recently transmitted sequence identifier.

4. The device of claim 3, where the one or more processors are further to:

determine a plurality of sequence identifiers stored in the memory after the most recently transmitted sequence identifier;

determine a set of sequence identifiers, of the plurality of sequence identifiers, based on a quantity of the plurality of sequence identifiers satisfying a threshold; and

where the one or more processors, when transmitting the first sequence identifier, are further to;

transmit, to the slave device, the set of sequence identifiers, a data item referenced by each of the set of sequence identifiers, and an operation referenced by each of the set of sequence identifiers.

5. The device of claim 1, where the one or more processors are further to:

receive a request, from the slave device, that identifies one or more sequence identifiers; and

where the one or more processors, when transmitting the first sequence identifier, are further to;

transmit the first sequence identifier based on the first sequence identifier being identified in the request.

6. The device of claim 5, where the slave device is further to:

receive a first indication of a first most recently transmitted sequence identifier;

receive a second indication of a second most recently transmitted sequence identifier, the second indication being received after the first indication;

determine the one or more sequence identifiers based on the first most recently transmitted sequence identifier and the second most recently transmitted sequence identifier.

7. The device of claim 1, where the one or more processors are further to:

receive, from the slave device, a second sequence identifier;

determine that the second sequence identifier references an empty entry; and

send, based on the determination, a flush indication to the slave device, where the flush indication causes the slave device to delete all sequence identifiers from a memory of the slave device.

8. A computer-readable medium for storing instructions, the instructions comprising:

one or more instructions that, when executed by a processor, cause the processor to;

receive information that identifies a data item;

receive information that identifies an operation to perform on the data item, the operation comprising at least one of an add operation, a modify operation, or a delete operation;

store, in a memory, a first sequence identifier, a data item reference that references the data item, and an operation reference that references the operation, the first sequence identifier referencing the data item reference and the operation reference and indicating an order in which the first sequence identifier is stored;

determine that the operation is one of the add operation, the modify operation, or the delete operation;

if the operation is the add operation;

store the data item in the memory at a first memory location; and

associate information that identifies the first memory location with the first sequence identifier;

if the operation is the modify operation;

modify the data item in the memory to create a modified data item;

store the modified data item in the memory at a second memory location;

associate information that identifies the second memory location with the first sequence identifier; and

remove, from the memory, a first reference to the data item by a first previous sequence identifier that references the data item, the first previous sequence identifier being stored before the first sequence identifier; and

if the operation is the delete operation;

delete the data item from the memory; and

remove, from the memory, a second reference to the data item by a second previous sequence identifier that references the data item, the second previous sequence identifier being stored before the first sequence identifier; and

transmit, to a slave device, the first sequence identifier, the data item reference, and the operation reference.

9. The computer-readable medium of claim 8, where the operation is the delete operation, and the one or more instructions further cause the processor to:

receive a deletion trigger, the deletion trigger indicating that an amount of time that has passed, since the first sequence identifier was stored, satisfies a threshold; and

remove, from the memory, the first sequence identifier, the data item reference, and the operation reference.

10. The computer-readable medium of claim 8, where the one or more instructions further cause the processor to:

determine a most recently transmitted sequence identifier; and

where the one or more instructions, when causing the processor to transmit the first sequence identifier, further cause the processor to;

transmit the first sequence identifier based on the most recently transmitted sequence identifier, the first sequence identifier being stored in the memory after the most recently transmitted sequence identifier.

11. The computer-readable medium of claim 10, where the one or more instructions further cause the processor to:

determine a plurality of sequence identifiers stored in the memory after the most recently transmitted sequence identifier;

determine a set of sequence identifiers, of the plurality of sequence identifiers, based on a quantity of the plurality of sequence identifiers satisfying a threshold; and

where the one or more instructions, when causing the processor to transmit the first sequence identifier, further cause the processor to;

transmit, to the slave device, the set of sequence identifiers, a data item referenced by each of the set of sequence identifiers, and an operation referenced by each of the set of sequence identifiers.

12. The computer-readable medium of claim 8, where the one or more instructions further cause the processor to:

receive a request, from the slave device, that identifies one or more sequence identifiers; and

where the one or more instructions, when causing the processor to transmit the first sequence identifier, further cause the processor to;

transmit the first sequence identifier based on the first sequence identifier being identified in the request.

13. The computer-readable medium of claim 12, where the one or more instructions further cause the processor to:

transmit a first indication of a first most recently transmitted sequence identifier; and

transmit a second indication of a second most recently transmitted sequence identifier, the second indication being transmitted after the first indication;

the first indication and the second indication allowing the slave device to determine the one or more sequence identifiers based on the first most recently transmitted sequence identifier and the second most recently transmitted sequence identifier.

14. The computer-readable medium of claim 8, where the one or more one or more instructions further cause the processor to:

receive, from the slave device, a second sequence identifier;

determine that the second sequence identifier references an empty entry; and

send, based on the determination, a flush indication to the slave device, where the flush indication causes the slave device to delete all sequence identifiers from a memory of the slave device.

15. A method, comprising:

receiving, by a master device, information that identifies a data item;

receiving, by the master device, information that identifies an operation to perform on the data item, the operation comprising a modify operation;

storing, in a memory of the master device, a first sequence identifier, a data item reference that references the data item, and an operation reference that references the operation, the first sequence identifier referencing the data item reference and the operation reference and indicating an order in which the first sequence identifier is stored;

determining, by the master device, that the operation is the modify operation;

modifying, by the master device, the data item in the memory to create a modified data item;

storing, by the master device, the modified data item in the memory at a memory location;

associating, by the master device, information that identifies the memory location with the first sequence identifier; and

removing, from the memory of the master device, a reference to the data item by a first previous sequence identifier that references the data item, the first previous sequence identifier being stored before the first sequence identifier; and

transmitting, by the master device and to a slave device, the first sequence identifier, the data item reference, and the operation reference.

16. The method of claim 15, further comprising:

determining a most recently transmitted sequence identifier; and

where transmitting the first sequence identifier further comprises;

transmitting the first sequence identifier based on the most recently transmitted sequence identifier, the first sequence identifier being stored in the memory after the most recently transmitted sequence identifier.

17. The method of claim 16, further comprising:

determining a plurality of sequence identifiers stored in the memory after the most recently transmitted sequence identifier;

determining a set of sequence identifiers, of the plurality of sequence identifiers, based on a quantity of the plurality of sequence identifiers satisfying a threshold; and

where transmitting the first sequence identifier further comprises;

transmitting, to the slave device, the set of sequence identifiers, a data item referenced by each of the set of sequence identifiers, and an operation referenced by each of the set of sequence identifiers.

18. The method of claim 15, further comprising:

receiving a request, from the slave device, that identifies one or more sequence identifiers; and

where transmitting the first sequence identifier further comprises;

transmitting the first sequence identifier based on the first sequence identifier being identified in the request.

19. The method of claim 18, further comprising:

transmitting a first indication of a first most recently transmitted sequence identifier; and

transmitting a second indication of a second most recently transmitted sequence identifier, the second indication being transmitted after the first indication;

the first indication and the second indication allowing the slave device to determine the one or more sequence identifiers based on the first most recently transmitted sequence identifier and the second most recently transmitted sequence identifier.

20. The method of claim 15, further comprising:

receiving, from the slave device, a second sequence identifier;

determining that the second sequence identifier references an empty entry; and

sending, based on the determination, a flush indication to the slave device, where the flush indication causes the slave device to delete all sequence identifiers from a memory of the slave device.