Method and apparatus for eventually consistent delete in a distributed data store

• US 9,305,002 B2
• Filed: 04/20/2015
• Issued: 04/05/2016
• Est. Priority Date: 05/22/2010
• Status: Active Grant

• Current Assignee: Nokia Technologies Oy (Nokia Corporation)
• Original Assignee: Nokia Technologies Oy (Nokia Corporation)
• Inventors: Rambacher, Mark, Bagri, Abhijit, Kosuru, Yekesa
• Primary Examiner(s): Hoang, Son T
• Application Number:
  US14/690,731
• Publication Number:
  US 20150227538A1
• Time in Patent Office: 351 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 16/162 Delete operations erasing in storage systems G06F3/0652
• CPC Class Codes: G06F 16/1873 Versioning file systems, temporal file systems, e.g. file system supporting different historic versions of files
• CPC Class Codes: G06F 16/2322 using timestamps
• 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/275 Synchronous replication

Abstract

Techniques for effective delete operations in a distributed data store with eventually consistent replicated entries include determining to delete a particular entry from the distributed data store. Each entry includes a first field that holds data that indicates a key and a second field that holds data that indicates content associated with the key and a third field that holds data that indicates a version for the content. The method also comprises causing, at least in part, actions that result in marking the particular entry as deleted without removing the particular entry, and updating a version in the third field for the particular entry.

Claims

1. A method comprising:

receiving a request from at least one user to delete at least one entry from a distributed data store, wherein the distribute data store includes one or more replicates for the at least one entry;

causing, at least in part, a marking of the at least one entry as deleted without removing the at least one entry, the one or more replicates, or a combination thereof from the distributed data store in response to the request;

causing, at least in part, an initiation of at least one get command for the at least one entry;

determining that there is at least one exception if one or more returned replicates of the at least one entry do not include an identical content value; and

causing, at least in part, a presentation of at least one notification in at least one user interface based, at least in part, on the at least one exception,

wherein the at least one entry includes, at least in part, a first field that holds a key, a second field that holds content associated with the key, and a third field that holds version information, and

the marking of the at least one entry includes updating the version information held in the third field.

2. A method of claim 1, further comprising:

causing, at least in part, a generation of at least one prompt to request a determination of at least one correct value for the one or more returned replicates from the at least one user,

wherein the at least one notification includes, at least in part, the at least one prompt.

3. A method of claim 2, further comprising:

determining one or more different values for the at least one entry from the one or more returned replicates; and

causing, at least in part, a presentation of the one or more different values in the at least one notification for selection of the at least one correct value by the at least one user.

4. A method of claim 1, further comprising:

causing, at least in part, an initiation of a determination of at least one correct value for the one or more returned replicates; and

causing, at least in part, a generation of at least one error message if the at least one correct value cannot be determined,

wherein the at least one notification includes, at least in part, the at least one error message.

5. A method of claim 4, wherein the determination of the at least one correct value is based, at least in part, on a quorum of the one or more returned replicates, version information associated with the one or more returned replicates, time stamp information associated with the one or more returned replicates, or a combination thereof.

6. A method of claim 1, further comprising:

determining that one or more returned replicates comprise all of the one or more replicates for the at least one entry and that all of the one or more replicates include the identical content value; and

causing, at least in part, a removal of the at least one entry, the one or more replicates, or a combination thereof from the distributed data store.

7. A method of claim 6, further comprising:

causing, at least in part, a transmission of a removal message to one or more nodes of the distributed data store to initiate the removal of the at least one entry, the one or more replicates, or a combination thereof.

8. A method of claim 1, wherein the causing, at least in part, of the marking of the at least one entry as deleted, includes (a) setting data in a delete flag field of the at least one entry to indicate the at least one entry is to be deleted, or (b) setting data in a size field of the at least one entry to indicate zero size.

9. An apparatus comprising:

at least one processor implemented at least partially by hardware; and

at least one memory including computer program code for one or more programs,

the at least one memory and the computer program code configured to, with the at least one processor, cause the apparatus to perform at least the following,

receive a request from at least one user to delete at least one entry from a distributed data store, wherein the distribute data store includes one or more replicates for the at least one entry;

cause, at least in part, a marking of the at least one entry as deleted without removing the at least one entry, the one or more replicates, or a combination thereof from the distributed data store in response to the request;

cause, at least in part, an initiation of at least one get command for the at least one entry;

praciticable

determine that there is at least one exception if one or more returned replicates of the at least one entry do not include an identical content value; and

cause, at least in part, a presentation of at least one notification in at least one user interface based, at least in part, on the at least one exception,

wherein the at least one entry includes, at least in part, a first field that holds a key, a second field that holds content associated with the key, and a third field that holds version information, and

the marking of the at least one entry includes updating the version information held in the third field.

10. An apparatus of claim 9, wherein the apparatus is further caused to:

cause, at least in part, a generation of at least one prompt to request a determination of at least one correct value for the one or more returned replicates from the at least one user,

wherein the at least one notification includes, at least in part, the at least one prompt.

11. An apparatus of claim 10, wherein the apparatus is further caused to:

determine one or more different values for the at least one entry from the one or more returned replicates; and

cause, at least in part, a presentation of the one or more different values in the at least one notification for selection of the at least one correct value by the at least one user.

12. An apparatus of claim 9, wherein the apparatus is further caused to:

cause, at least in part, an initiation of a determination of at least one correct value for the one or more returned replicates; and

cause, at least in part, a generation of at least one error message if the at least one correct value cannot be determined,

wherein the at least one notification includes, at least in part, the at least one error message.

13. An apparatus of claim 12, wherein the determination of the at least one correct value is based, at least in part, on a quorum of the one or more returned replicates, version information associated with the one or more returned replicates, time stamp information associated with the one or more returned replicates, or a combination thereof.

14. An apparatus of claim 9, wherein the apparatus is further caused to:

determine that one or more returned replicates comprise all of the one or more replicates for the at least one entry and that all of the one or more replicates include the identical content value; and

cause, at least in part, a removal of the at least one entry, the one or more replicates, or a combination thereof from the distributed data store.

15. An apparatus of claim 14, wherein the apparatus is further caused to:

cause, at least in part, a transmission of a removal message to one or more nodes of the distributed data store to initiate the removal of the at least one entry, the one or more replicates, or a combination thereof.

16. A non-transitory computer-readable storage medium carrying one or more sequences of one or more instructions which, when executed by one or more processors, cause an apparatus to at least perform the following steps:

receiving a request from at least one user to delete at least one entry from a distributed data store, wherein the distribute data store includes one or more replicates for the at least one entry;

causing, at least in part, a marking of the at least one entry as deleted without removing the at least one entry, the one or more replicates, or a combination thereof from the distributed data store in response to the request;

causing, at least in part, an initiation of at least one get command for the at least one entry;

determining that there is at least one exception if one or more returned replicates of the at least one entry do not include an identical content value; and

causing, at least in part, a presentation of at least one notification in at least one user interface based, at least in part, on the at least one exception,

wherein the at least one entry includes, at least in part, a first field that holds a key, a second field that holds content associated with the key, and a third field that holds version information, and

the marking of the at least one entry includes updating the version information held in the third field.

17. A non-transitory computer-readable storage medium of claim 16, wherein the apparatus is further caused to perform:

causing, at least in part, a generation of at least one prompt to request a determination of at least one correct value for the one or more returned replicates from the at least one user,

wherein the at least one notification includes, at least in part, the at least one prompt.

18. A non-transitory computer-readable storage medium of claim 17, wherein the apparatus is further caused to perform:

determining one or more different values for the at least one entry from the one or more returned replicates; and

causing, at least in part, a presentation of the one or more different values in the at least one notification for selection of the at least one correct value by the at least one user.

19. A non-transitory computer-readable storage medium of claim 16, wherein the apparatus is further caused to perform:

causing, at least in part, an initiation of a determination of at least one correct value for the one or more returned replicates; and

causing, at least in part, a generation of at least one error message if the at least one correct value cannot be determined,

wherein the at least one notification includes, at least in part, the at least one error message.