Systems and Methods for Organizing Data

• US 20170061032A1
• Filed: 08/18/2016
• Published: 03/02/2017
• Est. Priority Date: 08/26/2015
• Status: Abandoned Application

• Current Assignee: Exablox Corp. (StorageCraft Technology Corporation)
• Original Assignee: Exablox Corp. (StorageCraft Technology Corporation)
• Inventors: Fitzhardinge, Jeremy
• Application Number:
  US15/240,885
• Publication Number:
  US 20170061032A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/128 Details of file system snapshots on the file-level, e.g. snapshot creation, administration, deletion use of snapshots for error detection or correction G06F11/14, G06F11/16
• CPC Class Codes: G06F 16/1873 Versioning file systems, temporal file systems, e.g. file system supporting different historic versions of files
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 16/9027 Trees

Abstract

Provided are systems and methods for organizing data. An example method includes providing a content-addressable object store to keep data objects representing pieces of the data. The method further includes associating with the data objects. Each node of the directed graph is immutable and associated with either a data object or a metadata object storing list of references to data objects or further metadata objects. When the data objects are modified, a further directed graph is associated with the data objects. The further directed graph is a modification to and shares nodes with the directed graph. Roots of the directed graphs are published in a consensus store. The method includes managing roots associated with the directed graphs and provides access to snapshots associated with the modification of the data objects.

Claims

1. A computer-implemented method for organizing data, the method comprising:

providing a content-addressable object store to keep data objects, each of the data objects representing a piece of the data, an address of each of the data objects being a function of the piece of the data;

associating at least one directed graph with the data objects, each node of the directed graph being immutable and associated with one of an object from the data objects and a metadata object, the metadata object storing at least a list of references to one or more;

objects from the data objects or further metadata objects; and

when the data objects are modified;

associating at least one further directed graph with the data objects, the at least one further directed graph being a modification to and sharing at least one node with the at least one directed graph; and

publishing a root of the at least one further directed graph in a consensus store to provide access to snapshots associated with the modification of the data objects via published roots associated with the at least one directed graph and the at least one further directed graph.

2. The method of claim 1, further comprising associating at least one root from the published roots with a timestamp.

3. The method of claim 1, further comprising associating at least one of the published roots with a type of a directed graph the at least one root is referencing to.

4. The method of claim 3, wherein the directed graph includes an acyclic graph reflecting a directory structure of a file system.

5. The method of claim 3, wherein the directed graph includes a B+tree.

6. The method of claim 1, further comprising associating at least one of the published roots with a snapshot identifier.

7. The method of claim 6, further comprising providing a B+tree in the consensus store, wherein nodes of the B+tree are operable to store the published roots.

8. The method of claim 7, further comprising indexing the nodes in the B+tree by the snapshot identifiers.

9. The method of claim 1, further comprising cloning the at least one further directed graph by republishing the root of the at least one further directed graph under a new name in the consensus store.

10. The method of claim 1, further comprising rolling back modification of the data objects to a pre-determined point by removing roots published after the pre-determined point.

16. The system of claim 1, wherein the method further comprises associating at least one of the published roots with a snapshot identifier.

17. The system of claim 16, wherein the method further comprises providing a B+tree in the consensus store, wherein nodes of the B+tree are operable to store the published roots.

18. The system of claim 17, wherein the method further comprises indexing the nodes in the B+tree by the snapshot identifiers.

11. A system for organizing data, the system comprising:

at least one processor; and

a memory communicatively coupled to the at least one processor, the memory storing instructions, which, when executed by the at least one processor, perform a method comprising;

providing a content-addressable object store to keep data objects, each of the data objects representing a piece of the data, an address of each of the data objects being a function of the piece of the data;

associating at least one directed graph with the data objects, each node of the directed graph being immutable and associated with one of an object from the data objects and a metadata object, the metadata object storing at least a list of references to one or more;

objects from the data objects or further metadata objects; and

when the data objects are modified;

associating at least one further directed graph with the data objects, the at least one further directed graph being a modification to and sharing at least one node with the at least one directed graph; and

publishing a root of the at least one further directed graph in a consensus store to provide access to snapshots associated with the modification of the data objects via published roots associated with the at least one directed graph and the at least one further directed graph.

12. The system of claim 11, wherein the method further comprises associating at least one root from the published roots with a timestamp.

13. The system of claim 11, wherein the method further comprises associating at least one of the published roots with a type of a directed graph the at least one root is referencing to.

14. The system of claim 13, wherein the directed graph includes an acyclic graph reflecting a directory structure of a file system.

15. The system of claim 13, wherein the directed graph includes a B+tree.

19. The system of claim 11, wherein the method further comprises:

cloning the at least one further directed graph by republishing the root of the at least one further directed graph under a new name in the consensus store; and

rolling back modification of the data objects to a pre-determined point by removing roots published after the pre-determined point.

20. A non-transitory computer-readable storage medium having embodied thereon instructions, which, when executed by one or more processors, perform a method for organizing data, the method comprising:

providing a content-addressable object store to keep data objects, each of the data objects representing a piece of the data, an address of each of the data objects being a function of the piece of the data;

associating at least one directed graph with the data objects, each node of the directed graph being immutable and associated with one of an object from the data objects and a metadata object, the metadata object storing at least a list of references to one or more;

objects from the data objects or further metadata objects; and

when the data objects are modified;

associating at least one further directed graph with the data objects, the at least one further directed graph being a modification to and sharing at least one node with the at least one directed graph; and

publishing a root of the at least one further directed graph in a consensus store to provide access to snapshots associated with the modification of the data objects via published roots associated with the at least one directed graph and the at least one further directed graph.