Fragmenting data for the purposes of persistent storage across multiple immutable data structures

• US 9,881,176 B2
• Filed: 08/11/2017
• Issued: 01/30/2018
• Est. Priority Date: 06/02/2015
• Status: Active Grant

• Current Assignee: Altr Solutions, Inc.
• Original Assignee: Altr Solutions, Inc.
• Inventors: Goldfarb, Scott Nathaniel, Beecham, James Douglas, Struttmann, Christopher Edward
• Primary Examiner(s): VO, TRUONG V
• Application Number:
  US15/675,490
• Publication Number:
  US 20170364698A1
• Time in Patent Office: 172 Days
• CPC Class Codes: G06F 16/9014 hash tables
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 21/6218 to a system of files or objects, e.g. local or distributed file system or database
• CPC Class Codes: G06F 2221/2107 File encryption
• CPC Class Codes: H04L 9/3239 involving non-keyed hash functions, e.g. modification detection codes [MDCs], MD5, SHA or RIPEMD

Abstract

Provided is a process including: receiving one or more write requests; selecting a first subset of the values as corresponding to higher-security fields; segmenting a first value in the first subset; instructing a first computing device to store a first subset of segments among the plurality of segments in memory; and instructing a second computing device to store a second subset of segments among the plurality of segments in memory.

Claims

1. A tangible, non-transitory, machine-readable medium storing instructions that when executed by one or more processors effectuate operations comprising:

receiving, with one or more processors, one or more write requests to write a plurality of values to a plurality of fields in one or more tuples of a relational database, different ones of the values corresponding to different ones of the fields;

selecting, with one or more processors, a first subset of the values based on the first subset of values corresponding to fields in a first subset of the fields, the first subset of fields being designated as higher-security fields than a second subset of fields among the plurality of fields;

segmenting, with one or more processors, a first value in the first subset of values into a plurality of segments, each segment having a subset of information in the first value and different segments having different subsets of the information in the first value, the write request having an indication that the first value is to be written to a given field of a given tuple;

instructing, with one or more processors, via a network, a first computing device to store a first subset of segments among the plurality of segments in memory;

instructing, with one or more processors, via a network, a second computing device to store a second subset of segments among the plurality of segments in memory, wherein;

the first computing device does not have access to the second subset of segments; and

the second computing device does not have access to the first subset of segments; and

causing, with one or more processors, the relational database to store the second subset of the values and one or more pointers to at least some of the segments, wherein;

the first subset of the values is not written to the relational database in response to the one or more write requests; and

the one or more pointers are stored in the relational database in association with the given field of the given tuple to which the one or more write requests request the first value be written.

2. The medium of claim 1, wherein:

the first segment is stored at the first computing device with a pointer to the second segment; and

the pointer or a value associated with pointer indicates the second segment is stored at the second computing device, wherein the second computing device is one of a plurality of computing devices storing an instance of the second segment.

3. The medium of claim 1, wherein:

the one or more pointers are a single pointer to the first segment and indicate, or are associated with a value that indicates, the first segment is stored at the first computing device.

4. The medium of claim 1, wherein the one or more pointers include:

a first pointer to the first segment that indicates, or is associated with a value that indicates, the first segment is stored at the first computing device; and

a second pointer to the second segment that indicates, or is associated with a value that indicates, the second segment is stored at the second computing device.

5. The medium of claim 1, wherein:

five or more segments among the plurality of segments are stored on five or more different computing devices;

the five or more different computing devices include the first computing device and the second computing device; and

the five or more computing devices do not store or otherwise have access to at least three of the five or more segments.

6. The medium of claim 1, wherein:

the segments are stored on three or more computing devices as content nodes of a content directed acyclic graph, the content directed acyclic graph including edges defined by pointers from segments to other segments.

7. The medium of claim 6, wherein:

the directed acyclic graph comprises a linked list of three or more nodes.

8. The medium of claim 6, wherein:

the directed acyclic graph comprises a skip list with 1,000 or more nodes.

9. The medium of claim 6, wherein:

the directed acyclic graph comprises a binary tree.

10. The medium of claim 6, wherein:

the content directed acyclic graph is distributed among a plurality of validation directed acyclic graphs;

the validation directed acyclic graphs each comprise a plurality of validation nodes linked by validation edges;

the validation directed acyclic graphs each store different subsets of the content nodes as validation node attributes of different ones of the validation nodes;

validation edges of the validation directed acyclic graphs are defined, at least in part, by cryptographic hash pointers linking between validation nodes of the validation directed acyclic graph; and

the cryptographic hash pointers indicate whether one or more validation node attributes of a respective validation node to which respective cryptographic hash pointers point has been modified by encoding a cryptographic hash value based on the one or more validation node attributes of the validation node to which the respective cryptographic hash pointer points; and

validation node attributes of at least some of the validation nodes include the cryptographic hash values.

11. The medium of claim 10, wherein:

a given one of the validation directed acyclic graphs comprises a linked list of validation nodes having pointers to respective binary trees of validation nodes; and

a given one of the segments is stored as a validation node attribute of a leaf validation node of a given one of the binary trees.

12. The medium of claim 10, wherein:

each of the validation directed acyclic graphs comprises a respective linked list of validation nodes having pointers to respective binary trees of validation nodes; and

the content directed acyclic graph is a linked list of pointers between leaf validation nodes of binary trees among the validation directed acyclic graphs.

13. The medium of claim 10, wherein:

the cryptographic hash is an SHA-256 hash of one or more attributes of an adjacent validation node in a respective validation directed acyclic graph.

14. The medium of claim 1, comprising:

after an application queries the relational database, receiving a query response from the relational database that includes at least some of the one or more pointers;

in response to receiving the query response, determining that at least some of the query response is stored outside of the relational database;

in response to the determination, requesting, based on the at least some of the one or more pointers, the plurality of segments from a plurality of computing devices including the first computing device and the second computing device;

combining the plurality of segments to form the first value;

forming a revised version of the query response in which the at least some of the one or more pointers are replaced by the first value; and

providing the revised version of the query response to the application.

15. The medium of claim 14, wherein requesting the plurality of segments comprises:

requesting a first segment identified by the at least some of the one or more pointers;

receiving the first segment and a first associated pointer to a second segment;

requesting the second segment at a computing device indicated by the first associated pointer or value associated therewith;

receiving the second segment and a second associated pointer to a third segment;

requesting the third segment at a computing device indicated by the third associated segment; and

receiving a third segment.

16. The medium of claim 14, comprising:

determining a rate at which data is requested from the relational database; and

determining that the rate exceeds a threshold; and

in response to the determination, delaying providing at least part of the revised version of the query response to the application.

17. The medium of claim 14, wherein:

each segment is stored on three or more different computing devices responsive to the write request; and

after receiving the query response, the value of a given segment retrieved from the three or more different computing devices is determined based on a value of the given segment determined to be returned by a majority of the three or more different computing devices.

18. The medium of claim 14, comprising:

writing a record describing at least part of the query or the query response to a blockchain ledger, the record being associated with an identifier of a user that caused the query.

19. The medium of claim 1, comprising:

steps for intercepting exchanges between an application and a relational database;

steps for fragmenting data;

steps for storing fragmented data in a plurality of immutable data structures;

steps for preventing data from being undetectably modified; and

steps for reading data distributed among a plurality of immutable data structures.

20. A method, comprising:

receiving, with one or more processors, one or more write requests to write a plurality of values to a plurality of fields in one or more tuples of a relational database, different ones of the values corresponding to different ones of the fields;

selecting, with one or more processors, a first subset of the values based on the first subset of values corresponding to fields in a first subset of the fields, the first subset of fields being designated as higher-security fields than a second subset of fields among the plurality of fields;

segmenting, with one or more processors, a first value in the first subset of values into a plurality of segments, each segment having a subset of information in the first value and different segments having different subsets of the information in the first value, the write request having an indication that the first value is to be written to a given field of a given tuple;

instructing, with one or more processors, via a network, a first computing device to store a first subset of segments among the plurality of segments in memory;

instructing, with one or more processors, via a network, a second computing device to store a second subset of segments among the plurality of segments in memory, wherein;

the first computing device does not have access to the second subset of segments; and

the second computing device does not have access to the first subset of segments; and

causing, with one or more processors, the relational database to store the second subset of the values and one or more pointers to at least some of the segments, wherein;

the first subset of the values is not written to the relational database in response to the one or more write requests; and

the one or more pointers are stored in the relational database in association with the given field of the given tuple to which the one or more write requests request the first value be written.