MANAGING DEPENDENCIES BETWEEN OPERATIONS IN A DISTRIBUTED SYSTEM
First Claim
1. A method of operation of a computer for managing time dependencies in a distributed system including two or more subsystems with each subsystem including at least one event, wherein the computer comprises a central control unit, a storage system, and a network interface device, comprising the steps of:
- receiving by the central control unit through the network interface device two or more events from the two or more subsystems;
building by the central control unit an event dependency graph, wherein the event dependency graph includes a plurality of vertices with each vertex representing an event and a plurality of edges with each edge representing a happens-before relationship;
storing the event dependency graph in the storage system;
tracking by the central control unit dependencies between the two or more events that traverse the two or more subsystems;
selecting by the central control unit an order of the two or more events as late as possible; and
executing in each subsystem the two or more events according to the order selected by the central control unit.
1 Assignment
0 Petitions
Accused Products
Abstract
An efficient fault-tolerant event ordering service as well as a simplified approach to transaction processing based on global event ordering determines the order of interdependent operations in a distributed system. The fault-tolerant event ordering service externalizes the task of tracking dependencies to capture a global view of dependencies between a set of distributed operations in a distributed system. A novel protocol referred to as linear transactions coordinates distributed transactions with Atomicity, Consistency, Isolation, Durability (ACID) semantics on top of a sharded data store. The linear transactions protocol achieves scalability by distributing the coordination task to only those servers that hold relevant data for each transaction and achieves high performance by serializing only those transactions whose concurrent execution could potentially yield a violation of ACID semantics.
-
Citations
20 Claims
-
1. A method of operation of a computer for managing time dependencies in a distributed system including two or more subsystems with each subsystem including at least one event, wherein the computer comprises a central control unit, a storage system, and a network interface device, comprising the steps of:
-
receiving by the central control unit through the network interface device two or more events from the two or more subsystems; building by the central control unit an event dependency graph, wherein the event dependency graph includes a plurality of vertices with each vertex representing an event and a plurality of edges with each edge representing a happens-before relationship; storing the event dependency graph in the storage system; tracking by the central control unit dependencies between the two or more events that traverse the two or more subsystems; selecting by the central control unit an order of the two or more events as late as possible; and executing in each subsystem the two or more events according to the order selected by the central control unit. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)
-
-
13. A method of operation for coordinating distributed transactions on top of a sharded, distributed data store in a network, wherein the network comprises a plurality of servers and a plurality of clients, comprising the steps of:
-
selecting by a client one or more keys to obtain selected keys, wherein the selected keys deterministically determine a chain for each transaction of a plurality of transactions; mapping by the client each selected key using a key-value store; processing by the client each transaction through its corresponding chain through a forward pass and a backward pass; checking each transaction of the plurality with one or more concurrent transactions; applying by each server of the plurality of servers write keys for which the server is mapped to the key-value store; assigning an order to each transaction of the plurality of transactions; and executing each transaction of the plurality of transactions. - View Dependent Claims (14, 15, 16, 17, 18, 19, 20)
-
Specification