Data management platform

• US 10,162,841 B1
• Filed: 10/27/2014
• Issued: 12/25/2018
• Est. Priority Date: 10/28/2013
• Status: Active Grant

• Current Assignee: Vmware LLC (Broadcom, Inc.)
• Original Assignee: Pivotal Software, Inc. (Broadcom, Inc.)
• Inventors: Kumar, Neeraj, Wale, Sumedh, Smith, Daniel Allen, Chakraborty, Soubhik, Ramnarayanan, Jagannathan
• Primary Examiner(s): Le, Thu Nguyet T
• Application Number:
  US14/524,517
• Time in Patent Office: 1,520 Days
• Field of Search: 707741
• CPC Class Codes: G06F 12/0253 Garbage collection, i.e. reclamation of unreferenced memory
• CPC Class Codes: G06F 16/134 Distributed indices
• CPC Class Codes: G06F 16/178 Techniques for file synchronisation in file systems
• CPC Class Codes: G06F 16/183 Provision of network file services by network file servers, e.g. by using NFS, CIFS network file access protocols H04L67/1097
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/2228 Indexing structures
• CPC Class Codes: G06F 16/2272 Management thereof
• 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 2212/702 Conservative garbage collection
• CPC Class Codes: H04L 67/1097 for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]

Abstract

Methods, systems, and apparatus, including computer programs encoded on computer storage media, for distributed data management. One of the methods includes maintaining, by a first member in a distributed data management system having multiple computing members installed on multiple respective computers, a first garbage collection version vector that includes, for each member in the distributed data management system, a garbage collection version that represents a number of garbage collection processes performed by the member on a respective copy of a replicated data region maintained by the member in the data management system. If the first garbage collection version vector is different than a second garbage collection version vector received from a different provider member, a first replication process is performed that is different than a second replication process that is performed when the first garbage collection version vector matches the second garbage collection version vector.

Claims

1. A computer-implemented method comprising:

maintaining, by a first computing member of a distributed data management system, a data region comprising a plurality of data entry keys and respective data entry values;

maintaining, by the first computing member of the distributed data management system, a plurality of log entries in an event file of an operation log for the data region maintained by the first computing member of the distributed data management system, wherein the event file stores log entries representing respective requests to create or update a respective data entry of the data region, wherein each log entry in the event file has a unique event identifier;

generating, by the first computing member in operational memory, a first index that stores a mapping between data entry values and respective data entry keys;

generating, by the first computing member in non-operational memory, an index reference file that stores a mapping between data entry values occurring in the first index and respective unique event identifiers of log entries representing respective requests to create or update data entry keys to have one of the data entry values occurring in the first index;

receiving, by a second computing member of the distributed data management system, a request to generate a second index in operational memory from the index reference file stored in non-operational memory; and

in response to the request, generating, by the second computing member in operational memory, a second index that stores a mapping between data entry values stored in the index reference file and respective unique event identifiers of log entries stored in the index reference file, and wherein each log entry represented in the second index can be used by the second computing member to restore a mapping between a particular data entry value and one or more data entry keys that was previously represented in the first index.

2. The method of claim 1, further comprising:

receiving, by the second computing member, a request for data entry keys of data entries having a particular data entry value;

obtaining, by the second computing member, one or more unique event identifiers associated with the particular data entry value in the second index;

obtaining, by the second computing member, data entry keys from events associated with the one or more unique event identifiers in the second index; and

providing the obtained data entry keys in response to the request for data entry keys of data entries having the particular data entry value.

3. The method of claim 2, further comprising:

replacing, by the second computing member in the second index, the unique event identifiers with the obtained one or more data entry keys.

4. The method of claim 1, wherein generating the second index comprises:

obtaining, by the second computing member, data identifying data entry keys deleted during the lifetime of the event file; and

filtering, by the second computing member, the data entry keys that were created or updated in the data region during the lifetime of the event file with the data entry keys deleted during the lifetime of the event file.

5. The method of claim 1, wherein the non-operational memory is non-volatile memory stores persisted data regions, and wherein the operational memory is volatile memory that stores operational data.

6. The method of claim 1, further comprising:

determining that an operation log is rolling over by determining that the operation log has created a new event file; and

in response to determining that the operation log is rolling over by determining that the operation log has created the new event file, generating the index reference file.

7. A system comprising:

one or more computers and one or more storage devices storing instructions that are operable, when executed by the one or more computers, to cause the one or more computers to perform operations comprising;

maintaining, by a first computing member of a distributed data management system, a data region comprising a plurality of data entry keys and respective data entry values;

maintaining, by the first computing member of the distributed data management system, a plurality of log entries in an event file of an operation log for the data region maintained by the first computing member of the distributed data management system, wherein the event file stores log entries representing respective requests to create or update a respective data entry of the data region, wherein each log entry in the event file has a unique event identifier;

generating, by the first computing member in operational member, a first index that stores a mapping between data entry values and respective data entry keys;

generating, by the first computing member in non-operational memory, an index reference file that stores a mapping between data entry values occurring in the first index and respective unique event identifiers of log entries representing respective requests to create or update data entry keys to have one of the data entry values occurring in the first index;

receiving, by a second computing member of the distributed data management system, a request to generate a second index in operational memory from the index reference file stored in non-operational memory; and

in response to the request, generating, by the second computing member in operational memory, a second index that stores a mapping between data entry values stored in the index reference file and respective unique event identifiers of log entries stored in the index reference file, and wherein each log entry represented in the second index can be used by the second computing member to restore a mapping between a particular data entry value and one or more data entry keys that was previously represented in the first index.

8. The system of claim 7, wherein the operations further comprise:

receiving, by the second computing member, a request for data entry keys of data entries having a particular data entry value;

obtaining, by the second computing member, one or more unique event identifiers associated with the particular data entry value in the second index;

obtaining, by the second computing member, data entry keys from events associated with the one or more unique event identifiers in the second index; and

providing the obtained data entry keys in response to the request for data entry keys of data entries having the particular data entry value.

9. The system of claim 8, wherein the operations further comprise:

replacing, by the second computing member in the second index, the unique event identifiers with the obtained one or more data entry keys.

10. The system of claim 7, wherein generating the second index comprises:

obtaining, by the second computing member, data identifying data entry keys deleted during the lifetime of the event file; and

filtering, by the second computing member, the data entry keys that were created or updated in the data region during the lifetime of the event file with the data entry keys deleted during the lifetime of the event file.

11. The system of claim 7, wherein the non-operational memory is non-volatile memory stores persisted data regions, and wherein the operational memory is volatile memory that stores operational data.

12. The system of claim 7, wherein the operations further comprise:

determining that an operation log is rolling over by determining that the operation log has created a new event file; and

in response to determining that the operation log is rolling over by determining that the operation log has created the new event file, generating the index reference file.

13. A computer program product, encoded on one or more non-transitory computer storage media, comprising instructions that when executed by one or more computers cause the one or more computers to perform operations comprising:

maintaining, by the first computing member of the distributed data management system, a plurality of log entries in an event file of an operation log for the data region maintained by the first computing member of the distributed data management system, wherein the event file stores log entries representing respective requests to create or update a respective data entry of the data region, wherein each log entry in the event file has a unique event identifier;

generating, by the first computing member in operational memory, a first index that stores a mapping between data entry values and respective data entry keys;

generating, by the first computing member in non-operational memory, an index reference file that stores a mapping between data entry values occurring in the first index and respective unique event identifiers of log entries representing respective requests to create or update data entry keys to have one of the data entry values occurring in the first index;

receiving, by a second computing member of the distributed data management system, a request to generate a second index in operational memory from the index reference file stored in non-operational memory; and

in response to the request, generating, by the second computing member in operational memory, a second index that stores a mapping between data entry values stored in the index reference file and respective unique event identifiers of log entries stored in the index reference file, and wherein each log entry represented in the second index can be used by the second computing member to restore a mapping between a particular data entry value and one or more data entry keys that was previously represented in the first index.

14. The computer program product of claim 13, wherein the operations further comprise:

receiving, by the second computing member, a request for data entry keys of data entries having a particular data entry value;

obtaining, by the second computing member, one or more unique event identifiers associated with the particular data entry value in the second index;

obtaining, by the second computing member, data entry keys from events associated with the one or more unique event identifiers in the second index; and

providing the obtained data entry keys in response to the request for data entry keys of data entries having the particular data entry value.

15. The computer program product of claim 14, wherein the operations further comprise:

replacing, by the second computing member in the second index, the unique event identifiers with the obtained one or more data entry keys.

16. The computer program product of claim 13, wherein generating the second index comprises:

obtaining, by the second computing member, data identifying data entry keys deleted during the lifetime of the event file; and

filtering, by the second computing member, the data entry keys that were created or updated in the data region during the lifetime of the event file with the data entry keys deleted during the lifetime of the event file.

17. The computer program product of claim 13, wherein the non-operational memory is non-volatile memory stores persisted data regions, and wherein the operational memory is volatile memory that stores operational data.

18. The computer program product of claim 13, wherein the operations further comprise:

determining that an operation log is rolling over by determining that the operation log has created a new event file; and

in response to determining that the operation log is rolling over by determining that the operation log has created the new event file, generating the index reference file.