Using a tree structure to segment and distribute records across one or more decentralized, acyclic graphs of cryptographic hash pointers
Provided is a process including: receiving, with one or more processors, a first request to store a record from a computing entity; encoding, with one or more processors, the record in a first plurality of segments; arranging, with one or more processors, the first plurality of segments in respective content nodes of a first content graph, wherein at least some content nodes of the first content graph have two or more content edges of the first content graph pointing to two or more respective other content nodes of the first content graph; and storing, with one or more processors, the content nodes of the first content graph in a verification graph.
1. A tangible, non-transitory, machine-readable medium storing instructions that when executed by one or more processors effectuate operations configured to expedite retrieval of records written to persistent storage, the operations comprising:
receiving, with one or more processors, a first request to store a record from a computing entity;
encoding, with one or more processors, the record in a first plurality of segments;
arranging, with one or more processors, the first plurality of segments in respective content nodes of a first content graph, wherein:
each segment is stored in a different content node of the first content graph;
directed content edges of the first content graph connect respective pairs of the content nodes of the first content graph;
the directed content edges define a plurality of directed paths through the first content graph by which each of the segments is reachable from a first root content node of the first content graph; and
at least some content nodes of the first content graph have two or more directed content edges of the first content graph pointing to two or more respective other content nodes of the first content graph;
storing, with one or more processors, the content nodes of the first content graph in a verification graph, wherein:
the verification graph comprises a plurality of verification nodes;
the content nodes and the directed content edges are stored as content of the verification nodes; and
respective pairs of the verification nodes are connected by respective directed verification edges; and
returning, with one or more processors, a first identifier of the first root content node to the computing entity, wherein the first identifier identifies a verification node of the verification graph storing the first root content node.
2. The medium of claim 1 , wherein:
the first content graph includes a binary tree that accounts for at least half of the content nodes of the first content graph.
3. The medium of claim 2 , wherein:
the first content graph is a balanced binary tree.
4. The medium of claim 1 , wherein:
the first content graph includes a skip list defined by the directed content edges of the first content graph.
5. The medium of claim 1 , wherein:
the first content graph defines k-ary tree in which each content node of the k-ary tree has fewer k or fewer child content nodes, wherein k is 3 or larger.
6. The medium of claim 5 , wherein:
the first content graph includes three or more levels of hierarchy.
7. The medium of claim 5 , wherein:
at least half of the content nodes of the k-ary tree have 2 or more child nodes.
8. The medium of claim 5 , wherein arranging the first plurality of segments in the first content graph comprises iteratively, in a plurality of iterations, executing operations comprising:
obtaining a set of the first plurality of segments to be arranged;
determining a size of the set;
selecting 1/k of the size of the set from the set to form a selected subset;
arranging the selected subset in a current level of a hierarchy of the first content graph;
removing the selected subset from the set of the first plurality of segments to be arranged; and
designating a next level higher than the current level of the hierarchy as the current level.
9. The medium of claim 8 , wherein:
the selected subset is a sequential collection of segments of the record;
the selected subset precedes unselected members of the set in the record; and
a last segment of the record is stored in the first root content node.
10. The medium of claim 1 , wherein:
the first content graph comprises means for storing segmented data to facilitate concurrent retrieval.
11. The medium of claim 1 , wherein:
the record is a file;
the first identifier distinguishes the first root content node from other content nodes of the first content graph; and
the first request is a request to write the file to persistent storage from a security driver of an operating system of a user computing device.
12. The medium of claim 1 , the operations comprising:
receiving a second request to store a revised version of the record from the computing entity, the second request being associated with the first identifier of the first root content node;
encoding the revised version of the record in a second plurality of revised segments, wherein a first subset of the revised segments are identical to corresponding ones of the first plurality of segments and a second subset of the revised segments are different from corresponding ones of the first plurality of segments;
arranging the second subset in a second content graph that partially overlaps the first content graph, wherein:
the overlap includes at least some content nodes storing respective segments of the first subset previously stored in the verification graph;
the second content graph includes a second root content node;
the second content graph does not include the first root content node;
both content nodes storing the second subset and the at least some content nodes storing respective segments of the first subset are reachable in the second content graph from the second root content node; and
content nodes storing the second subset are not reachable from the first root content node of the first content graph;
storing the second subset in the verification graph without re-writing the at least some content nodes storing respective segments of the first subset to the verification graph; and
returning a second identifier of the second root content node to the computing entity.
13. The medium of claim 12 , the operations further comprising:
identifying the second subset by comparing respective cryptographic hashes of the first plurality of segments and the revised segments without retrieving the record from storage in the verification graph.
14. The medium of claim 1 , wherein:
the respective directed verification edges correspond to cryptographic hash pointers based on content of respective verification nodes to which respective cryptographic hash pointers point; and
content of verification nodes includes respective cryptographic hash values of respective cryptographic hash pointers of respective edges of respective verification nodes.
15. The medium of claim 1 , wherein:
the verification graph includes a plurality of different directed acyclic graphs of cryptographic hash pointers; and
different portions of the first content graph are stored as content of verification nodes of the different directed acyclic graphs of cryptographic hash pointers.
16. The medium of claim 1 , wherein:
encoding the record in a first plurality of segments comprises partitioning a bitstream of a file into the first plurality of segments; and
segments of the first plurality of segments are respective subsequences of the bitstream.
17. The medium of claim 1 , wherein:
encoding the record in the first plurality of segments comprises applying linear coding to the record.
18. The medium of claim 1 , the operations further comprising:
receiving a request to read the record from persistent storage, the request including the first identifier of the first root content node; and
traversing the first content graph from the first root content node to retrieve every content node of the first content graph from the verification graph, wherein at least some of the content nodes are retrieved concurrently.
19. The medium of claim 1 , wherein:
read latency of the record from the verification graph scales at less than O (n) in big O notation, where n is a number of segments of the first purality of segments; and
traversing the first content graph comprises performing a breadth first traversal of the first content graph.
20. A method, comprising:
receiving, with one or more processors, a first request to store a record from a computing entity;
encoding, with one or more processors, the record in a first plurality of segments;
arranging, with one or more processors, the first plurality of segments in respective content nodes of a first content graph, wherein:
each segment is stored in a different content node of the first content graph;
directed content edges of the first content graph connect respective pairs of the content nodes of the first content graph;
the directed content edges define a plurality of directed paths through the first content graph by which each of the segments is reachable from a first root content node of the first content graph; and
at least some content nodes of the first content graph have two or more directed content edges of the first content graph pointing to two or more respective other content nodes of the first content graph;
storing, with one or more processors, the content nodes of the first content graph in a verification graph, wherein:
the verification graph comprises a plurality of verification nodes;
the content nodes and directed content edges are stored as content of the verification nodes; and
respective pairs of the verification nodes are connected by respective directed verification edges; and
returning, with one or more processors, a first identifier of the first root content node to the computing entity, wherein the first identifier identifies a verification node of the verification graph storing the first root content node.
21. The method of claim 20 , wherein:
the first content graph includes a binary tree that accounts for at least half of the content nodes of the first content graph.
22. The method of claim 21 , wherein:
the first content graph is a balanced binary tree.
23. The method of claim 20 , wherein:
the first content graph includes a skip list defined by the directed content edges of the first content graph.
24. The method of claim 20 , wherein:
the first content graph defines k-ary tree in which each content node of the k-ary tree has fewer k or fewer child content nodes, wherein k is 3 or larger.
25. The method of claim 24 , wherein:
the first content graph includes three or more levels of hierarchy.
26. The method of claim 24 , wherein:
at least half of the content nodes of the k-ary tree have 2 or more child nodes.
27. The method of claim 24 , wherein arranging the first plurality of segments in the first content graph comprises iteratively, in a plurality of iterations:
obtaining a set of the first plurality of segments to be arranged;
determining a size of the set;
selecting 1/k of the size of the set from the set to form a selected subset;
arranging the selected subset in a current level of a hierarchy of the first content graph;
removing the selected subset from the set of the first plurality of segments to be arranged; and
designating a next level higher than the current level of the hierarchy as the current level.
28. The method of claim 27 , wherein:
the selected subset is a sequential collection of segments of the record;
the selected subset precedes unselected members of the set in the record; and
a last segment of the record is stored in the first root content node.
29. The method of claim 20 , wherein:
the first content graph comprises means for storing segmented data to facilitate concurrent retrieval.
30. The method of claim 20 , wherein:
the record is a file;
the first identifier distinguishes the first root content node from other content nodes of the first content graph; and
the first request is a request to write the file to persistent storage from a security driver of an operating system of a user computing device.
31. The method of claim 20 , further comprising:
receiving a second request to store a revised version of the record from the computing entity, the second request being associated with the first identifier of the first root content node;
encoding the revised version of the record in a second plurality of revised segments, wherein a first subset of the revised segments are identical to corresponding ones of the first plurality of segments and a second subset of the revised segments are different from corresponding ones of the first plurality of segments;
arranging the second subset in a second content graph that partially overlaps the first content graph, wherein:
the overlap includes at least some content nodes storing respective segments of the first subset previously stored in the verification graph;
the second content graph includes a second root content node;
the second content graph does not include the first root content node;
both content nodes storing the second subset and the at least some content nodes storing respective segments of the first subset are reachable in the second content graph from the second root content node; and
content nodes storing the second subset are not reachable from the first root content node of the first content graph;
storing the second subset in the verification graph without re-writing the at least some content nodes storing respective segments of the first subset to the verification graph; and
returning a second identifier of the second root content node to the computing entity.
32. The method of claim 31 , further comprising:
identifying the second subset by comparing respective cryptographic hashes of the first plurality of segments and the revised segments without retrieving the record from storage in the verification graph.
33. The method of claim 20 , wherein:
the respective directed verification edges correspond to cryptographic hash pointers based on content of respective verification nodes to which respective cryptographic hash pointers point; and
content of verification nodes includes respective cryptographic hash values of respective cryptographic hash pointers of respective edges of respective verification nodes.
34. The method of claim 20 , wherein:
the verification graph includes a plurality of different directed acyclic graphs of cryptographic hash pointers; and
different portions of the first content graph are stored as content of verification nodes of the different directed acyclic graphs of cryptographic hash pointers.
35. The method of claim 20 , wherein:
encoding the record in the first plurality of segments comprises partitioning a bitstream of a file into the first plurality of segments; and
segments of the first plurality of segments are respective subsequences of the bitstream.
36. The method of claim 20 , wherein:
encoding the record in the first plurality of segments comprises applying linear coding to the record.
37. The method of claim 20 , further comprising:
receiving a request to read the record from persistent storage, the request including the first identifier of the first root content node; and
traversing the first content graph from the first root content node to retrieve every content node of the first content graph from the verification graph, wherein at least some of the content nodes are retrieved concurrently.
38. The method of claim 20 , wherein:
read latency of the record from the verification graph scales at less than O(n) in big O notation, where n is a number of segments of the first plurality of segments; and
traversing the first content graph comprises performing a breadth first traversal of the first content graph.