Versioned and hierarchical data structures and distributed transactions

US9098470B2 · kind B2 · utility

Assignee

• MICROSOFT TECHNOLOGY LICENSING, LLC · US

Inventors

• Bradley Gene Calder · Bellevue, US
• Niranjan Nilakantan · Redmond, US
• Shashwat Srivastav · Seattle, US
• Jiesheng Wu · Redmond, US
• Abdul Rafay Abbasi · Redmond, US
• Shane Mainali · Duvall, US
• Padmanabha Chakravarthy Uddaraju · Bellevue, US
• Ju Wang · Redmond, US
• Hemal Khatri · Redmond, US
• Arild E. Skjolsvold · Kenmore, US
• Harshawardhan Gadgil · Redmond, US

Key dates

• Filing date: May 23, 2011
• Grant date: Aug 4, 2015
• Expiry date: Dec 29, 2032

Classification

• Technology area (CPC G): Physics
• CPC primary: G06F16/282
• WIPO field: Computer technology
• WIPO sector: Electrical engineering

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.