Clock-based distributed data resolution

摘要

Techniques to generate a distributed data structure using monotonic clock times are described herein. A set of data events are received at a plurality of replica locations and, based on delivery times, creation times, and timeout times, the data events are stored within a convergent replicated data structure. The data events are then ordered within the convergent replicated data structure based on the corresponding timeout times being less than a time value obtained from a locally accessible clock associated with each replica locations. The distributed data structure is then generated from the ordered data events by recursively selecting data events from the replica locations.

主权项

1. A computer-implemented method for generating a distributed message queue, comprising:
under the control of one or more computer systems configured with executable instructions,
receiving, at a set of replica locations, a set of data events, each data event of the set of data events including a corresponding message time and a corresponding timeout time;determining whether each data event of the set of data events is valid based at least in part on comparing a delivery time to the timeout time, the delivery time obtained from a locally accessible clock associated with the replica location, the delivery time corresponding to a time that the data event is received at the replica location;storing the set of data events in an add-only monotonic directed acyclic graph, the add-only monotonic directed acyclic graph comprising a set of nodes, each node of the set of nodes corresponding to a data event of the set of data events, the add-only monotonic directed acyclic graph further comprising a set of directed edges connecting pairs of nodes of the set of nodes, each directed edge in the set of directed edges representing an order of a pair of data events corresponding to the pair of nodes connected by the directed edge; andproducing a consensus order of the set of data events by repeatedly:
selecting, for each replica location of the set of replica locations, a corresponding subgraph of the add-only monotonic directed acyclic graph, each data event of a subset of the set of data events corresponding to the subgraph selected as a result of the timeout time being less than a time value obtained from the locally accessible clock; anddetermining the consensus order based at least in part on a set of most frequent directed edges of the corresponding subgraph from each replica location; andinserting one or more messages into the distributed message queue in an order based at least in part on the consensus order.