Versioned and hierarchical data structures and distributed transactions

• US 10,242,026 B2
• Filed: 07/08/2015
• Issued: 03/26/2019
• Est. Priority Date: 05/23/2011
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Calder, Bradley Gene, Nilakantan, Niranjan, Srivastav, Shashwat, Wu, Jiesheng, Abbasi, Abdul Rafay, Mainali, Shane, Uddaraju, Padmanabha Chakravarthy, Wang, Ju, Khatri, Hemal, Skjolsvold, Arild, Gadgil, Harshawardhan
• Primary Examiner(s): Somers, Marc S
• Application Number:
  US14/794,555
• Publication Number:
  US 20160070720A1
• Time in Patent Office: 1,357 Days
• CPC Class Codes: G06F 11/2094 Redundant storage or storage space G06F11/2056 takes precedence
• CPC Class Codes: G06F 16/178 Techniques for file synchronisation in file systems
• CPC Class Codes: G06F 16/1787 Details of non-transparently synchronising file systems
• CPC Class Codes: G06F 16/184 implemented as replicated file system
• CPC Class Codes: G06F 16/1844 Management specifically adapted to replicated file systems
• 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/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/282 Hierarchical databases, e.g. IMS, LDAP data stores or Lotus Notes

Abstract

Presented herein are methods of replicating versioned and hierarchical data structures, as well as data structures representing complex transactions. Due to interdependencies between data entities and a lack of guaranteed message ordering, simple replication methods employed for simple data types cannot be used. Operations on data structures exhibit dependencies between the messages making up the operations. This strategy can be extended to various types of complex transactions by considering certain messages to depend on other messages or on the existence of other entries at the data store. Regardless of origin, these dependencies can be enforced by suspending the processing of messages with unsatisfied dependencies until all of its dependencies have been met. Alternately, transactions can be committed immediately, creating entities that include versioned identifiers for each of their dependencies. These entities can then be garbage collected of the parent objects are not subsequently created.

Claims

1. A computer-implemented method in a distributed computing environment utilizing a processor and memory for processing transactions in a replicated storage environment, the method comprising:

receiving and processing, at a secondary data store, a plurality of messages of a distributed transaction from one or more primary data stores, each message of the plurality of messages containing a distributed transaction identifier;

determining that the distributed transaction identifier in each of the plurality of messages corresponds to the distributed transaction;

receiving, at the secondary data store, a commit-distributed-transaction message, the commit-distributed-transaction message containing the distributed transaction identifier and an indicator that is part of the distributed transaction, the indicator being a count of messages making up the distributed transaction;

postponing the processing of the plurality of messages and the commit-distributed-transaction message in the distributed transaction based on determining from the indicator obtained from the received commit-distributed-transaction message that each message that is part of the distributed transaction has not been received; and

after the commit-distributed-transaction message has been received and based on determining from the indicator obtained from the received commit-distributed-transaction message that each message that is part of the distributed transaction has been received, resuming the processing of the plurality of messages and the commit-distributed-transaction message and committing the distributed transaction at the secondary data store, the determining that each message that is part of the distributed transaction has been received comprises comparing, at the secondary data store, a received message count to the count of messages extracted from the commit-distributed-transaction message.

2. The computer-implemented method of claim 1, wherein the determining that each message that is part of the distributed transaction has not been received comprises comparing, at the secondary data store, the received message count to the count of messages extracted from the commit-distributed-transaction message.

3. The computer-implemented method of claim 1, wherein the commit-distributed-transaction message was sent to the secondary data store after all of the messages of the distributed transaction.

4. The computer-implemented method of claim 1, wherein the method further comprises incrementing, at the secondary data store, the received message count based on receiving a message of the plurality of messages at the secondary data store, wherein the comparing is performed using the incremented received message count.

5. The computer-implemented method of claim 1, wherein the distributed transaction is committed atomically.

6. The computer-implemented method of claim 1, wherein the determining that the distributed transaction identifier in each of the plurality of messages corresponds to the distributed transaction comprises:

extracting the distributed transaction identifier from the commit-distributed-transaction message; and

comparing the distributed transaction identifier of each message of the plurality of messages to the extracted distributed transaction identifier.

7. The method of claim 1, wherein the commit-distributed-transaction message is received at the secondary data store after at least one of the plurality of messages.

8. The method of claim 1, wherein the distributed transaction is committed at the one or more primary data stores prior to the secondary data store receiving at least some of the plurality of messages.

9. A computer-implemented system in a distributed computing environment, the computer-implemented system comprising a processor and memory configured to perform a method for processing transactions in a replicated storage environment, the method comprising:

receiving and processing, at a secondary data store, a plurality of messages of a distributed transaction from one or more primary data stores, each message of the plurality of messages containing a distributed transaction identifier;

determining that the distributed transaction identifier in each of the plurality of messages corresponds to the distributed transaction;

receiving, at the secondary data store, a commit-distributed-transaction message, the commit-distributed-transaction message containing the distributed transaction identifier and an indicator that specifies each message that is part of the distributed transaction, the indicator being a list comprising an individual transaction identifier of each transaction making up the distributed transaction;

postponing the processing of the plurality of messages and the commit-distributed-transaction message in the distributed transaction based on determining from the indicator obtained from the received commit-distributed transaction message that each message that is part of the distributed transaction has not been received; and

after the commit-distributed-transaction message has been received and based on determining from the indicator obtained from the received commit-distributed transaction message that each message that is part of the distributed transaction has been received, using the plurality of messages to cause resuming of the processing and committal of the distributed transaction at the secondary data store.

10. The computer-implemented system of claim 9, wherein the individual transaction identifier of each transaction is included in a corresponding message of the distributed transaction.

11. The computer-implemented system of claim 9, wherein the determining from the indicator that each message that is part of the distributed transaction has been received comprises marking the individual transaction identifier of each transaction as having been received from the plurality of messages.

12. The computer-implemented system of claim 9, wherein the distributed transaction is committed atomically.

13. The computer-implemented system of claim 9, wherein the determining that the distributed transaction identifier in each of the plurality of messages corresponds to the distributed transaction comprises:

extracting the distributed transaction identifier from the commit-distributed-transaction message; and

comparing the distributed transaction identifier of each message of the plurality of messages to the extracted distributed transaction identifier.

14. The computer-implemented system of claim 9, wherein the distributed transaction is committed at the one or more primary data stores prior to the secondary data store receiving at least some of the plurality of messages.

15. A computer-implemented method in a distributed computing environment utilizing a processor and memory for processing transactions in a replicated storage environment, the method comprising:

receiving, at a secondary data store, a plurality of messages from one or more primary data stores, each message of the plurality of messages containing a distributed transaction identifier;

determining that the distributed transaction identifier in each of the plurality of messages corresponds to a distributed transaction, a designated message of the plurality of messages comprising an object replication message including an object name of an object, and identifiers for one or more parent objects of the object, each parent object identifier comprising a parent object name and a parent object version;

receiving, at the secondary data store, a commit-distributed-transaction message, the commit-distributed-transaction message containing the distributed transaction identifier and an indicator for the plurality of the messages;

postponing processing of the plurality of messages and the commit-distributed-transaction message in the distributed transaction based on the indicator indicating that each of the plurality of messages corresponding to the distributed transaction has not been received;

determining a full object identifier of the object from the object replication message based on the object name, the parent object name for each parent object identifier, and the parent object version for each parent object identifier, the full object identifier identifying the object and each of the one or more parent objects; and

after the commit-distributed-transaction message has been received and the indicator indicates that each of the plurality of messages corresponding to the distributed transaction has been received, using the plurality of messages to cause the distributed transaction to be committed at the secondary data store, wherein the object corresponding to the determined full object identifier is created independently of whether the one or more parent objects exist at the secondary data store.

16. The computer-implemented method of claim 15, wherein a version of the object is determined to be a live version of the object based on at least the following criteria being satisfied:

the version of the object exists at the secondary data store;

for each parent object of the one or more parent objects, a version of the parent object corresponding to the parent object version exists at the secondary data store; and

the version of the object is a most recent version of the object at the secondary data store that satisfies the first two criteria.

17. The computer-implemented method of claim 15, further comprising:

determining that one or more versions of the object at the secondary data store are not live; and

based on the determining, garbage collecting the one or more versions of the object determined not to be live.

18. The computer-implemented method of claim 15, wherein the full object identifier is included in the object replication message.

19. The computer-implemented method of claim 15, wherein the full object identifier comprises identifiers of all parent objects of the object.

20. The computer-implemented method of claim 15, wherein each of the one or more parent objects is a container object and the object is stored in the container object.