Methods and apparatus for a distributed database within a network

• US 10,572,455 B2
• Filed: 12/01/2016
• Issued: 02/25/2020
• Est. Priority Date: 08/28/2015
• Status: Active Grant

• Current Assignee: Hedera Hashgraph LLC
• Original Assignee: Swirlds, Inc.
• Inventors: Baird, III, Leemon C.
• Primary Examiner(s): Spieler, William
• Application Number:
  US15/366,584
• Publication Number:
  US 20170308548A1
• Time in Patent Office: 1,181 Days
• CPC Class Codes: G06F 16/182 Distributed file systems
• CPC Class Codes: G06F 16/1834 implemented based on peer-to-peer networks, e.g. gnutella p2p communication protocols H04L67/104
• CPC Class Codes: G06F 16/1837 Management specially adapted to peer-to-peer storage networks topology management mechanisms of peer-to-peer networks H04L67/1042
• 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/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/273 Asynchronous replication or reconciliation
• CPC Class Codes: G06F 16/275 Synchronous replication
• CPC Class Codes: G06F 9/542 Event management; Broadcasting; Multicasting; Notifications
• CPC Class Codes: H04L 67/1097 for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]

Abstract

In some embodiments, an apparatus includes an instance of a distributed database at a first compute device configured to be included within a set of compute devices that implement the distributed database. The apparatus also includes a processor configured to define a first event linked to a first set of events. The processor is configured to receive, from a second compute device from the set of compute devices, a signal representing a second event (1) defined by the second compute device and (2) linked to a second set of events. The processor is configured to identify an order associated with a third set of events based at least one a result of a protocol. The processor is configured to store in the instance of the distributed database the order associated with the third set of events.

Claims

1. An apparatus, comprising:

a memory associated with an instance of a distributed database at a first compute device configured to be included within a plurality of compute devices that implements the distributed database via a network operatively coupled to the plurality of compute devices; and

a processor operatively coupled to the memory,

the processor configured to identify, at a first time, a first distributed database event (1) defined by the first compute device and (2) linked to a first plurality of distributed database events,

the processor configured to receive, at a second time after the first time, a signal representing a second distributed database event (1) defined by a second compute device from the plurality of compute devices and (2) linked to a second plurality of distributed database events,

the processor configured to identify an order of distributed database events within a third plurality of distributed database events based at least in part on a value of a first attribute for each distributed database event from the third plurality of distributed database events, the value of the first attribute for each distributed database event from the third plurality of distributed database events being based on a relationship between that distributed database event and a set of distributed database events including descendants of that distributed database event, each distributed database event from the set of distributed database events being associated with a second attribute that is common with the remaining distributed database events from the set of distributed database events, each distributed database event from the third plurality of distributed database events being from at least one of the first plurality of distributed database events or the second plurality of distributed database events, the third plurality of distributed database events being mutually exclusive of the set of distributed database events,

the processor configured to store in the memory the order associated with the third plurality of distributed database events.

2. The apparatus of claim 1, wherein the value of the first attribute for each distributed database event from the third plurality of distributed database events is based on a number of descendants of that distributed database event included in the set of distributed database events compared to a number of non-descendants of that distributed database event included in the set of distributed database events.

3. The apparatus of claim 1, wherein each distributed database event from the set of distributed database events is defined by a unique compute device from the plurality of compute devices.

4. The apparatus of claim 1, wherein each distributed database event from the set of distributed database events is defined by a unique compute device from the plurality of compute devices,

the processor configured to identify each distributed database event from the set of distributed database events based on each distributed database event from the set of distributed database events being an initial instance the compute device from the plurality of compute devices that defined that distributed database event defined a distributed database event having a particular value for a third attribute, each distributed database event from the set of distributed database events having the particular value for the third attribute.

5. The apparatus of claim 1, wherein the set of distributed database events is a first set of distributed database events, each distributed database event from the first set of distributed database events is defined by a unique compute device from the plurality of compute devices,

the processor configured to identify each distributed database event from the first set of distributed database events based on (1) each distributed database event from the first set of distributed database events being an initial instance the compute device from the plurality of compute devices that defined that distributed database event defined a distributed database event having a particular value for a third attribute and (2) an outcome of an agreement protocol in which a second set of distributed database events indicates that that distributed database event from the first set of distributed database events should be within a third set of distributed database events, the first set of distributed database events being a subset of the third set of distributed database events, each distributed database event from the first set of distributed database events having the particular value for the third attribute.

6. The apparatus of claim 1, wherein each distributed database event from the first plurality of distributed database events and each distributed database event from the second plurality of distributed database events is a sequence of bytes.

7. The apparatus of claim 1, wherein the set of distributed database events is a first set of distributed database events, the processor configured to identify each distributed database event from the first set of distributed database events based on an outcome of an agreement protocol in which a second set of distributed database events indicates that that distributed database event from the first set of distributed database events should be within a third set of distributed database events, the second set of distributed database events meeting a predetermined criterion, the first set of distributed database events being a subset of the third set of distributed database events.

8. The apparatus of claim 1, wherein the set of distributed database events is a first set of distributed database events, the processor configured to identify each distributed database event from the first set of distributed database events based on an outcome of an agreement protocol in which a second set of distributed database events indicates that that distributed database event from the first set of distributed database events should be within a third set of distributed database events, the first set of distributed database events being a subset of the third set of distributed database events,

the processor configured to identify each distributed database event from the second set of distributed database events based on (1) that distributed database event from the second set of distributed database events being a descendent of a fourth set of distributed database events and (2) a number of distributed database events in the fourth set of distributed database events meeting a criterion.

9. The apparatus of claim 1, wherein the set of distributed database events is a first set of distributed database events, the processor configured to identify each distributed database event from the first set of distributed database events based on an outcome of an agreement protocol in which a second set of distributed database events indicates that that distributed database event from the first set of distributed database events should be within a third set of distributed database events, the first set of distributed database events being a subset of the third set of distributed database events,

the processor configured to identify each distributed database event from the second set of distributed database events based on (1) that distributed database event from the second set of distributed database events being a descendent of a fourth set of distributed database events and (2) a number of distributed database events in the fourth set of distributed database events meeting a first criterion,

each distributed database event from the fourth set of distributed database events being an ancestor of a fifth set of distributed database events, each distributed database event from the second set of distributed database events being a descendent of the fifth set of distributed database events,

the processor configured to identify each distributed database event from the fourth set of distributed database events based on a number of distributed database events in the fifth set of distributed database events meeting a second criterion.

10. The apparatus of claim 1, wherein the processor is configured to identify the order associated with the third plurality of distributed database events based at least in part on the value of the first attribute for each distributed database event from the third plurality of distributed database events and a timestamp associated with each distributed database event from the third plurality of distributed database events.

11. The apparatus of claim 1, wherein the processor is configured to identify the order associated with the third plurality of distributed database events based at least in part on the value of the first attribute for each distributed database event from the third plurality of distributed database events and a signature of each distributed database event from the third plurality of distributed database events.

12. The apparatus of claim 1, wherein the set of distributed database events is a first set of distributed database events,

the processor configured to identify each distributed database event from the first set of distributed database events based on an outcome of an agreement protocol in which a second set of distributed database events indicates that that distributed database event from the first set of distributed database events should be within a third set of distributed database events,

each distributed database event from the second set of distributed database events indicating that that distributed database event from the first set of distributed database events should be within the third set of distributed database events based on a value (1) associated with that distributed database event from the first set of distributed database events and (2) identified by a set of ancestors of that distributed database event from the second set of distributed database events.

13. A non-transitory processor-readable medium storing code representing instructions to be executed by a processor, the code comprising code to cause the processor to:

receive a signal representing a plurality of distributed database events including transactions associated with a distributed database;

calculate, for each distributed database event from the plurality of distributed database events, a received round for that distributed database event from the plurality of distributed database events based on a relationship between that distributed database event and a set of distributed database events including descendants of that event, each distributed database event from the set of distributed database events being classified as being famous;

identify an order associated with the plurality of distributed database events based on the received round associated with each distributed database event from the plurality of distributed database events; and

store the order in a memory associated with an instance of a distributed database at a first compute device configured to be included within a plurality of compute devices that implements the distributed database via a network operatively coupled to the plurality of compute devices.

14. The non-transitory processor-readable medium of claim 13, wherein the code to cause the processor to calculate includes code to cause the processor to calculate, for each distributed database event from the plurality of distributed database events, the received round for that distributed database event based on a number of descendants of that event included in the set of distributed database events compared to a number of non-descendants of that event included in the set of distributed database events.

15. The non-transitory processor-readable medium of claim 13, wherein the set of distributed database events is a first set of distributed database events, each distributed database event from the first set of distributed database events is defined by a unique compute device from the plurality of compute devices,

the code further comprising code to cause the processor to:

classify each distributed database event from the first set of distributed database events as famous based on (1) each distributed database event from the first set of distributed database events being an initial instance the compute device from the plurality of compute devices that defined that distributed database event defined a distributed database event having a particular value for an attribute and (2) an outcome of an agreement protocol in which a second set of distributed database events indicates that that distributed database event from the first set of distributed database events should be within a third set of distributed database events, the first set of distributed database events being a subset of the third set of distributed database events, each distributed database event from the first set of distributed database events having the particular value for the attribute.

16. The non-transitory processor-readable medium of claim 13, wherein each distributed database event from the set of distributed database events is defined by a unique compute device from the plurality of compute devices.

17. The non-transitory processor-readable medium of claim 13, wherein the set of distributed database events is a first set of distributed database events, the code further comprising code to cause the processor to:

classify each distributed database event from the first set of distributed database events as famous based on an outcome of an agreement protocol in which a second set of distributed database events indicates that that distributed database event from the first set of distributed database events should be within a third set of distributed database events,

each distributed database event from the second set of distributed database events indicating that that distributed database event from the first set of distributed database events should be within the third set of distributed database events based on a value (1) associated with that distributed database event from the first set of distributed database events and (2) identified by a set of ancestors of that distributed database event from the second set of distributed database events.

18. The non-transitory processor-readable medium of claim 13, wherein the code to cause the processor to identify the order includes code to cause the processor to identify the order associated with the plurality of distributed database events based at least in part on the received round associated with each distributed database event from the plurality of distributed database events and at least one of a timestamp or a signature of each distributed database event from the plurality of distributed database events.

19. A method, comprising:

identifying, at a first time, a first distributed database event (1) defined by a first compute device configured to be included within a plurality of compute devices that implements the distributed database via a network operatively coupled to the plurality of compute devices and (2) linked to a first plurality of distributed database events;

receiving, at a second time after the first time, a signal representing a second distributed database event (1) defined by a second compute device from the plurality of compute devices and (2) linked to a second plurality of distributed database events;

calculating, using a processor associated with an instance of the distributed database, an order associated with a third plurality of distributed database events based at least in part on a value of a first attribute for each distributed database event from the third plurality of distributed database events, the value of the first attribute for each distributed database event from the third plurality of distributed database events being based on a relationship between that distributed database event and a set of distributed database events including descendants of that distributed database event, each distributed database event from the set of distributed database events being associated with a second attribute that is common with the remaining distributed database events from the set of distributed database events, each distributed database event from the third plurality of distributed database events being from at least one of the first plurality of distributed database events or the second plurality of distributed database events; and

storing, in a memory associated with the instance of the distribute database, the order associated with the third plurality of distributed database events.

20. The method of claim 19, wherein each distributed database event from the set of distributed database events is defined by a unique compute device from the plurality of compute devices, the method further comprising:

identifying each distributed database event from the set of distributed database events based on each distributed database event from the set of distributed database events being a first instance the compute device from the plurality of compute devices that defined that distributed database event defined a distributed database event having a particular value for a third attribute, each distributed database event from the set of distributed database events having the particular value for the third attribute.

21. The method of claim 19, wherein the set of distributed database events is a first set of distributed database events, the method further comprising:

identifying each distributed database event from the first set of distributed database events based on an outcome of an agreement protocol in which a second set of distributed database events indicates that that distributed database event from the first set of distributed database events should be within a third set of distributed database events,

each distributed database event from the second set of distributed database events indicating that that distributed database event from the first set of distributed database events should be within the third set of distributed database events based on a value (1) associated with that distributed database event from the first set of distributed database events and (2) identified by a set of ancestors of that distributed database event from the second set of distributed database events.

22. The method of claim 19, further comprising:

calculating the order associated with the third plurality of distributed database events based at least in part on the value of the first attribute for each distributed database event from the third plurality of distributed database events and at least one of a timestamp or a signature of each distributed database event from the third plurality of distributed database events.

23. The method of claim 19, wherein the value of the first attribute for each distributed database event from the third plurality of distributed database events is based on a number of descendants of that event included in the set of distributed database events compared to a number of non-descendants of that event included in the set of distributed database events.