Invention Grant
- Patent Title: Concurrency control for confluent trees
- Patent Title (中): 汇合树的并发控制
-
Application No.: US12824254Application Date: 2010-06-28
-
Publication No.: US08386421B2Publication Date: 2013-02-26
- Inventor: Colin W. Reid , Philip A. Bernstein
- Applicant: Colin W. Reid , Philip A. Bernstein
- Applicant Address: US WA Redmond
- Assignee: Microsoft Corporation
- Current Assignee: Microsoft Corporation
- Current Assignee Address: US WA Redmond
- Main IPC: G06F7/00
- IPC: G06F7/00

Abstract:
Architecture that addresses the efficient detection of conflicts and the merging of data structures such as trees, when possible. The process of detecting conflicts and merging the trees is a meld operation. Confluent trees offer transactional consistency with some degree of isolation, and scaling out a concurrent system based on confluent trees can be accomplished where the meld operation is more efficient than the transaction computations. Transactions execute optimistically using lazily versioned “intention trees” that efficiently describe dependencies and effects using structure and content version information for each intention subtree. The data structure is modified by melding the intention trees in sequence, which causes each transaction to either commit (producing an incremental new version of the data structure) or abort (identifying a conflict which prevents the intention tree from being melded). The architecture is computationally efficient and completes without needing to access much of each tree.
Public/Granted literature
- US20110320496A1 CONCURRENCY CONTROL FOR CONFLUENT TREES Public/Granted day:2011-12-29
Information query