OPPORTUNISTIC CLEARING OF SYNC STATES ASSOCIATED WITH A DATABASE

• US 20140006348A1
• Filed: 06/27/2012
• Published: 01/02/2014
• Est. Priority Date: 06/27/2012
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Akinyemi, Adedeji Olumuyiwa
• Granted Patent: US 9,990,378 B2
• Time in Patent Office: Days
• US Class Current: 707/632
• CPC Class Codes: G06F 16/21 Design, administration or maintenance of databases
• 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

Abstract

Systems and techniques of the management of the metadata of a database are presented. A provider is in communication with a database and a set of consumers of the database. Data may be changed by addition, editing or deletion from the database and such changes are recorded and/or maintained by the provider on a list of changes. The changes on this list may be associated with a sync token. The provider may also maintain a list of consumers and associate with each consumer a last sync token which describes when the last sync request and update on the database was made with the consumer. Data which is deleted from the database is recorded with a tombstone. The tombstone is maintained on the list of changes until all consumers have been made aware of the deletion—then the tombstone may be deleted from the list of changes.

Claims

1. A method for managing the metadata of a database, said database comprising a set of data, each said data capable of being added, changed and deleted from said database, and wherein said metadata managed by at least one provider, said provider capable of communicating with a set of consumers, the steps of said method comprising:

maintaining a list of changes to said database, said changes associated with a sync token;

maintaining a list of consumers of said database, said list of consumers associated with a last sync token for each said consumer;

adding a tombstone to said list of changes when data is deleted from said database, said tombstone having its associated sync token in said list of changes;

reading a request for sync from one of said consumers;

updating said one of said consumers with metadata added to said list of changes to said database since said last sync token; and

if all consumers have been updated with said sync token associated with said tombstone, deleting said tombstone from said list of changes to said database.

2. The method of claim 1 wherein said step of maintaining a list of changes to said database further comprises maintaining a list of changes to data, said changes comprising one of a group, said group comprising:

adding, editing and deleting said data.

3. The method of claim 1 wherein said step of maintaining a list of consumers of said database further comprises adding new consumers granted initial access to said database.

4. The method of claim 1 wherein said step of maintaining a list of consumers of said database further comprises deleting consumers denied further access to said database.

5. The method of claim 1 wherein said step of maintaining a list of consumers of said database further comprises deleting consumers that have not requested access to the database after a time period.

6. The method of claim 1 wherein the step of reading a request for sync from one of said consumers further comprises reading a request to access data from said database by said consumer.

7. The method of claim 1 wherein the step of reading a request for sync from one of said consumers further comprises reading a request to access the metadata of said database by said consumer.

8. The method of claim 1 wherein the step of reading a request for sync from one of said consumers further comprises reading a sync token encoded within said request for sync.

9. The method of claim 1 wherein said step of updating said one of said consumers with metadata added to said list of changes to said database since said last sync token further comprises:

comparing the last sync token associated with said consumer and the final sync token associated with said list of changes to said database; and

updating said consumer with data regarding said changes if the last sync token is smaller than said final sync token.

10. The method of claim 1 wherein the step of deleting said tombstone from said list of changes to said database further comprises deleting said tombstone if all consumers comprises one of group, said group comprising:

consumers who have their last sync token at least equal to the sync token associated with the deleted data sync token and consumers who have been deleted from said list of consumers.

11. A system for managing the metadata of a database, said system comprising:

a provider, said provider further comprising a processor and memory;

a database, said database in communication with said provider and said provider is capable of maintaining a list of changes to said database and said provider is further capable of adding a tombstone for a data deleted from said database, said tombstone added to said list of changes to said database;

wherein said provider is in communications with a set of consumers, said consumers requesting to sync with said database; and

said provider is capable of maintaining a list of said consumers; and

further wherein said provider is capable of deleting said tombstone when all consumers have been made aware of said deletion of said data.

12. The system of claim 11 wherein said list of changes to said database comprises a table of sync database changes and associated sync tokens for each said database change.

13. The system of claim 12 wherein said list of consumers further comprises a table of consumers and associated last sync tokens for each said consumer.

14. The system of claim 13 wherein said list of consumers further comprises an associated last sync timestamp, said last sync timestamp recording the last time that said consumer requested a sync with said database.

15. The system of claim 12 wherein said provider is capable list of changes to said database comprise entries regarding changes to data within said database, said changes comprising a group, said group comprising:

an addition, an edit and a deletion.

16. The system of claim 13 wherein said provider is capable of removing a consumer from said list of consumers if said consumer has not made a sync request within a given time period.

17. A computer readable storage medium that is not a transient signal, said computer readable storage medium having computer-executable instructions stored thereon that, when executed by a processor, cause said processor to execute:

a method for managing the allocation of a plurality of memory elements stored within one or more lockless list structures, said lockless list structures accessible within an operating system environment of a multicore processor, the steps of said method comprising the step of;

maintaining a list of changes to said database, said changes associated with a sync token;

maintaining a list of consumers of said database, said list of consumers associated with a last sync token for each said consumer;

adding a tombstone to said list of changes when data is deleted from said database, said tombstone having its associated sync token in said list of changes;

reading a request for sync from one of said consumers;

updating said one of said consumers with metadata added to said list of changes to said database since said last sync token; and

if all consumers have been updated with said sync token associated with said tombstone, deleting said tombstone from said list of changes to said database.

18. The computer readable storage medium of claim 17 wherein said step of maintaining a list of changes to said database further comprises maintaining a list of changes to data, said changes comprising one of a group, said group comprising:

adding, editing and deleting said data.

19. The computer readable storage medium of claim 18 wherein the step of reading a request for sync from one of said consumers further comprises reading a request to access the metadata of said database by said consumer.

20. The computer readable storage medium of claim 19 wherein the step of deleting said tombstone from said list of changes to said database further comprises deleting said tombstone if all consumers comprises one of group, said group comprising:

consumers who have their last sync token at least equal to the sync token associated with the deleted data sync token and consumers who have been deleted from said list of consumers.