×

Using a tree structure to segment and distribute records across one or more decentralized, acyclic graphs of cryptographic hash pointers

  • US 10,505,740 B2
  • Filed: 12/05/2018
  • Issued: 12/10/2019
  • Est. Priority Date: 06/02/2015
  • Status: Active Grant
First Claim
Patent Images

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 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 content edges are stored as content of the verification nodes;

    respective pairs of the verification nodes are connected by respective directed verification edges; and

    the verification graph is configured to indicate tampering with any of a plurality of records stored in the verification graph;

    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;

    receiving a request to read the record from persistent storage, the request indicating the first identifier of the root content node; and

    traversing the content graph from the first root content node to retrieve every content node of the content graph from the verification graph, wherein at least some of the content nodes are retrieved concurrently, wherein;

    the verification graph includes a plurality cryptographic hash pointers;

    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 the segments.

View all claims
  • 1 Assignment
Timeline View
Assignment View
    ×
    ×