DECENTRALIZED RECORD EXPIRY

• US 20090089313A1
• Filed: 09/28/2007
• Published: 04/02/2009
• Est. Priority Date: 09/28/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, Bigby, Michael, Bohannon, Philip L.
• Granted Patent: US 7,783,607 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/217 Database tuning G06F16/2282 takes precedence; database performance monitoring G06F11/3409

Abstract

A technique is described that reduces the complexity and resource consumption associated with performing record expiry in a distributed database system. In accordance with the technique, a record is checked to see if it has expired only when it has been accessed for a read or a write. If at the time of a read a record is determined to have expired, then it is not served. If at the time of a write a record is determined to have expired, then the write is treated as an insertion of a new record, and steps are taken to treat the insertion consistently with regard to the previous expired version. A background process is used to delete records that have not been written to or actively deleted by a client after expiration.

Claims

1. A method for automatically deleting an expired record in a distributed database system comprising a plurality of nodes, wherein each node is configured to manage a respective one of a plurality of databases, the method comprising:

receiving a write request for a record at one of the plurality of nodes, wherein the record is part of a partition stored in the database managed by the one of the plurality of nodes;

determining whether the record is expired responsive to receiving the write request;

determining if an incarnation number associated with the partition exceeds an incarnation number stored in the record responsive to determining that the record is expired; and

responsive to determining that the incarnation number associated with the partition exceeds the incarnation number stored in the record,

generating an updated record based on the write request, wherein generating the updated record comprises replacing the incarnation number stored in the record with the incarnation number associated with the partition; and

overwriting the expired record with the updated record.

2. The method of claim 1, wherein generating an updated record based on the write request further comprises setting a sequence number stored in the updated record to an initial value.

3. The method of claim 1, further comprising:

sending a message to the other nodes regarding the overwriting of the expired record with the updated record.

4. The method of claim 1, further comprising:

responsive to determining that the incarnation number associated with the partition does not exceed the incarnation number stored in the record,

deleting the expired record, wherein deleting the expired record comprises sending a message to a remote node to increment an incarnation number associated with a partition stored in the database managed by the remote node,

generating an updated record based on the write request, and

inserting the updated record.

5. The method of claim 3, wherein generating the updated record comprises:

obtaining an incarnation number from a remote node, wherein the incarnation number obtained from the remote node is associated with a partition stored in the database managed by the remote node, and

replacing the incarnation number stored in the record with the incarnation number obtained from the remote node.

6. A distributed database system, comprising:

a plurality of nodes, wherein the plurality of nodes are interconnected via a communication system; and

a plurality of databases, wherein each node in the plurality of nodes is configured to manage a respective one of a plurality of databases;

wherein each node in the plurality of nodes is further configured to receive a write request for a record, wherein the record is part of a partition stored in the database managed by the node, to determine whether the record is expired responsive to receiving the write request, to determine if an incarnation number associated with the partition exceeds an incarnation number stored in the record responsive to determining that the record is expired, and, responsive to determining that the incarnation number associated with the partition exceeds the incarnation number stored in the record, to generate an updated record based on the write request, wherein generating the updated record comprises replacing the incarnation number stored in the record with the incarnation number associated with the partition, and to overwrite the expired record with the updated record.

7. The system of claim 6, wherein each node in the plurality of nodes is configured to generate an updated record based on the write request by setting a sequence number stored in the updated record to an initial value.

8. The system of claim 6, wherein each node in the plurality of nodes is further configured to send a message to the other nodes via the communication system regarding the overwriting of the expired record with the updated record.

9. The system of claim 6, wherein each node in the plurality of nodes is further configured to, responsive to determining that the incarnation number associated with the partition does not exceed the incarnation number stored in the record, delete the expired record, wherein deleting the expired record comprises sending a message to a remote node to increment an incarnation number associated with a partition stored in the database managed by the remote node, to generate an updated record based on the write request, and to inserting the updated record.

10. The system of claim 9, wherein each node in the plurality of nodes is configured to generate the updated record by obtaining an incarnation number from a remote node, wherein the incarnation number obtained from the remote node is associated with a partition stored in the database managed by the remote node, and replacing the incarnation number stored in the record with the incarnation number obtained from the remote node.

11. A method for automatically deleting an expired record in a distributed database system comprising a plurality of nodes, wherein each node is configured to manage a respective one of a plurality of databases, the method comprising:

reading a record at one of the plurality of nodes, wherein the record is part of a partition stored in the database managed by the one of the plurality of nodes;

determining whether the record is expired;

determining if an incarnation number associated with the partition exceeds an incarnation number stored in the record responsive to determining that the record is expired; and

purging the record responsive to determining that the incarnation number associated with the partition exceeds the incarnation number stored in the record.

12. The method of claim 11, further comprising:

sending a message to the other nodes regarding the purging of the record.

13. The method of claim 11, further comprising:

responsive to determining that the incarnation number associated with the partition does not exceed the incarnation number stored in the record,

deleting the expired record, wherein deleting the expired record comprises sending a message to a remote node to increment an incarnation number associated with a partition stored in the database managed by the remote node.

14. A distributed database system, comprising:

a plurality of nodes, wherein the plurality of nodes are interconnected via a communication system; and

a plurality of databases, wherein each node in the plurality of nodes is configured to manage a respective one of a plurality of databases;

wherein each node in the plurality of nodes is further configured to read a record, wherein the record is part of a partition stored in the database managed by the node, to determine whether the record is expired, to determine if an incarnation number associated with the partition exceeds an incarnation number stored in the record responsive to determining that the record is expired, and to purge the record responsive to determining that the incarnation number associated with the partition exceeds the incarnation number stored in the record.

15. The system of claim 14, wherein each node in the plurality of nodes is further configured to send a message to the other nodes regarding the purging of the record.

16. The system of claim 14, wherein each node in the plurality of nodes is further configured to, responsive to determining that the incarnation number associated with the partition does not exceed the incarnation number stored in the record, delete the expired record, wherein deleting the expired record comprises sending a message to a remote node to increment an incarnation number associated with a partition stored in the database managed by the remote node.

17. A method in a distributed database system for determining which of a first version of a record and a second version of a record is the most recent, comprising:

comparing an incarnation number associated with the first version of the record and an incarnation number associated with the second version of the record, wherein each incarnation number represents a version of a partition that existed at the time each record was created; and

responsive to determining that one of the first version of the record or the second version of the record has a greater incarnation number, identifying as the most recent the one of the first version of the record or the second version of the record having the greater incarnation number.

18. The method of claim 17, wherein comparing an incarnation number associated with the first version of the record and an incarnation number associated with the second version of the record comprises:

reading the first version of the record to obtain the incarnation number associated with the first version of the record; and

reading the second version of the record to obtain the incarnation number associated with the second version of the record.

19. The method of claim 17, further comprising:

responsive to determining that the first version of the record and the second version of the record have the same incarnation number,

comparing a sequence number associated with the first version of the record and a sequence number associated with the second version of the record; and

responsive to determining that one of the first version of the record or the second version of the record has a greater sequence number, identifying as the most recent the one of the first version of the record or the second version of the record having the greater sequence number.

20. The method of claim 19, wherein comparing a sequence number associated with the first version of the record and a sequence number associated with the second version of the record comprises:

reading the first version of the record to obtain the sequence number associated with the first version of the record; and

reading the second version of the record to obtain the sequence number associated with the second version of the record.