# US 12,001,481 B2 · Graph-organized file system

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 12,001,481 B2
- Document ID: US12001481B2
- Status: Granted
- Kind: B2
- Application number: 17/719,550
- Filed: 2022-04-13
- Published: 2023-10-19
- Granted: 2024-06-04
- Earliest claimed: 2022-04-13
- Assignees: Oracle International Corporation
- Applicants: Oracle International Corporation
- Inventors: Armando Antonio Garduno Hernandez
- Web page: https://patentgrep.com/patent/US12001481B2

## CPC

- G06F 16/9024: {Graphs; Linked lists (G06F16/9027 takes precedence)}
- G06F 16/13: File access structures, e.g. distributed indices (arrangements of input from, or output to, record carriers G06F3/06)
- G06F 16/182: Distributed file systems
- G06F 16/185: Hierarchical storage management [HSM] systems, e.g. file migration or policies thereof (details of archiving G06F16/11)
- G06F 16/192: {Implementing virtual folder structures}
- H04L 67/10: in which an application is distributed across nodes in the network (software deployment G06F8/60; multiprogramming arrangements G06F9/46)
- 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]
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

Techniques are described herein for a graph-organized file system (GOFS) implemented by an operating system of a computing system. A GOFS represents a data graph with graph components comprising a plurality of nodes and one or more relationships between the nodes. Each node of the graph may be associated with content (of any kind) and/or relationships (of any kind) between the node and other nodes in the graph. Data for a GOFS is stored in a GOFS partition in persistent storage. In the GOFS partition, nodes are represented using “gnode” data structures (also referred to herein as “gnodes”), each of which comprises a content field for node content data and an edge field for edge data representing relationships between nodes. According to various embodiments, a GOFS partition includes dedicated space for each of: a superblock, graph metadata, a block bitmap, a gnode bitmap, a gnode table, and data blocks.

## Claims

### Claim 1

A computer-executed method comprising:
in kernel space of one or more computing devices, maintaining a graph-organized file system (GOFS) that represents a graph with a plurality of graph components comprising a plurality of nodes and one or more relationships for the plurality of nodes;
wherein each gnode data structure, of a plurality of gnode data structures that represents the plurality of nodes, comprises a content field for node content and an edge field for relationships between said each node and other nodes of the plurality of nodes;
wherein said plurality of gnode data structures includes a set of gnode data structures that each represent a file node, said set of gnode data structures including multiple gnode data structures, wherein said set of gnode data structures includes a particular gnode data structure;
wherein the edge field of said particular gnode data structure specifies an edge relationship between the file node of said particular gnode data structure and a file node of at least one gnode data structure of said set of gnode data structures;
wherein data for the GOFS is stored in a GOFS partition, in persistent storage accessible by a particular computing device of the one or more computing devices, that comprises dedicated space for one or more of: a superblock, metadata, a block bitmap, a gnode bitmap, a gnode table, and data blocks;
receiving, by an operating system of the particular computing device, a file system command for the GOFS from an application in a user space; and
the operating system executing the file system command using the GOFS partition.

### Claim 2 (depends on 1)

The computer-executed method of claim 1, wherein:
the particular computing device maintains a first portion of the graph;
the one or more computing devices comprises a second computing device that maintains a second portion of the graph stored in a second GOFS partition in persistent storage accessible by the second computing device; and
the method further comprises:
receiving, by a second operating system of the second computing device, a second file system command for the GOFS, and
the second operating system executing the file system command using the second GOFS partition.

### Claim 3 (depends on 1)

The computer-executed method of claim 1, wherein:
the file system command is received at a file system command interface of the operating system;
the operating system executing the file system command using the GOFS partition is performed responsive to the file system command interface determining that the file system command is for the GOFS; and
the method further comprises:
receiving, at the file system command interface, a second file system command;
the file system command interface determining whether the second file system command is for the GOFS or for a hierarchically-organized file system;
responsive to determining that the second file system command is for the GOFS, the file system command interface causing the second file system command to be executed using the GOFS partition; and
responsive to determining that the second file system command is for a hierarchically-organized file system, the file system command interface communicating the second file system command to a virtual file system switch to cause the second file system command to be executed for the hierarchically-organized file system.

### Claim 4 (depends on 1)

The computer-executed method of claim 1, wherein:
the gnode table comprises a plurality of slots storing the plurality of gnode data structures;
each gnode data structure of the plurality of gnode data structures further comprises a plurality of fields, each field of the plurality of fields storing one of:
one or more in-structure metadata values of one or more node attributes for a represented node,
one or more flags for the represented node,
mode data for the represented node,
owner data for the represented node,
timestamps for the represented node,
size data for the represented node, or
a count of edges originating at the represented node.

### Claim 5 (depends on 1)

The computer-executed method of claim 1, wherein a particular content field, of a particular gnode data structure that represents a particular node of the graph, comprises one of: content data for the particular node, or one or more pointers to one or more data blocks in the GOFS partition storing content data for the particular node.

### Claim 6 (depends on 5)

The computer-executed method of claim 5, wherein the particular gnode data structure comprises a content interpretation flag that indicates whether the content field should be interpreted as (a) content data for the particular node, or (b) one or more pointers.

### Claim 7 (depends on 1)

The computer-executed method of claim 1, wherein a particular edge field, of a particular gnode data structure that represents a particular node of the graph, comprises one or more pointers to one or more edge entry data structures representing one or more edges, of the graph, originating at the particular node.

### Claim 8 (depends on 7)

The computer-executed method of claim 7, wherein, for each edge entry data structure, of the one or more edge entry data structures:
said each edge entry data structure (a) identifies a particular destination node of the graph as a destination node of an edge represented by said each edge entry data structure, and (b) represents a component of a particular relationship, of the one or more relationships, between the particular node and the particular destination node;
wherein the particular relationship is further represented by a second edge entry data structure, associated with the particular destination node, that identifies the particular node as the destination node of an edge represented by the second edge entry data structure.

### Claim 9 (depends on 7)

The computer-executed method of claim 7, wherein each edge entry data structure, of the one or more edge entry data structures, comprises one or more flags for an edge represented by said each edge entry, the one or more flags comprising one or more of: a traversable flag, an operating system-specific hidden flag, a user-specific hidden flag, or a visited flag.

### Claim 10 (depends on 9)

The computer-executed method of claim 9, wherein:
a particular edge entry data structure, of the one or more edge entry data structures, that identifies a second node as a destination node of a hidden edge comprises a particular flag field with an operating system-specific hidden flag that indicates that the particular edge entry data structure is hidden;
the second node is associated with a second edge entry representing an unhidden edge originating at the second node and terminating at the particular node;
the method further comprises:
detecting an instruction to delete the particular node;
in response to detecting the instruction to delete the particular node, deleting the particular node comprising:
using the particular edge entry data structure to identify the second node, and
removing the second edge entry from the second node.

### Claim 11 (depends on 3)

The computer-executed method of claim 3, wherein:
the superblock identifies a root node of the graph;
the superblock further identifies a name of the root node;
the file system command includes an absolute path to a node of the graph;
the method further comprises interpreting the absolute path based on the root node identified by the superblock.

### Claim 12 (depends on 11)

The computer-executed method of claim 11, wherein the root node identified by the superblock is a particular node of the graph, the method further comprising:
receiving, at the file system command interface, a second file system command to change the root node of the graph to a second node of the graph that is different than the particular node;
responsive to receiving the second file system command, causing the superblock to identify the second node as the root node of the graph;
after changing the root node to the second node:
receiving, at the file system command interface, a third file system command that includes a second absolute path to a node of the graph, and
interpreting the second absolute path based on the second node that is identified as the root node by the superblock.

### Claim 13 (depends on 1)

The computer-executed method of claim 1, wherein:
said receiving the file system command from the application comprises receiving the file system command via a command-line interface;
the file system command comprises instructions for one of:
adding or modifying a node in the graph;
adding or modifying a relationship between nodes of the graph;
adding or modifying content associated with a node of the graph;
adding or modifying metadata for a node of the graph;
adding or modifying metadata for a relationship of the graph; or
adding or modifying metadata for the superblock.

### Claim 14

One or more non-transitory computer-readable media storing one or more sequences of instructions that, when executed by one or more processors, cause:
in kernel space of one or more computing devices, maintaining a graph-organized file system (GOFS) that represents a graph with a plurality of graph components comprising a plurality of nodes and one or more relationships for the plurality of nodes;
wherein each gnode data structure, of a plurality of gnode data structures that represents the plurality of nodes, comprises a content field for node content and an edge field for relationships between said each node and other nodes of the plurality of nodes;
wherein said plurality of gnode data structures includes a set of gnode data structures that each represent a file node, said set of gnode data structures including multiple gnode data structures, wherein said set of gnode data structures includes a particular gnode data structure;
wherein the edge field of said particular gnode data structure specifies an edge relationship between the file node of said particular gnode data structure and a file node of at least one gnode data structure of said set of gnode data structures;
wherein data for the GOFS is stored in a GOFS partition, in persistent storage accessible by a particular computing device of the one or more computing devices, that comprises dedicated space for one or more of: a superblock, metadata, a block bitmap, a gnode bitmap, a gnode table, and data blocks;
receiving, by an operating system of the particular computing device, a file system command for the GOFS from an application in a user space; and
the operating system executing the file system command using the GOFS partition.

### Claim 15 (depends on 14)

The one or more non-transitory computer-readable media of claim 14, wherein:
the particular computing device maintains a first portion of the graph;
the one or more computing devices comprises a second computing device that maintains a second portion of the graph stored in a second GOFS partition in persistent storage accessible by the second computing device; and
the one or more sequences of instructions further comprise instructions that, when executed by one or more processors, cause:
receiving, by a second operating system of the second computing device, a second file system command for the GOFS, and
the second operating system executing the file system command using the second GOFS partition.

### Claim 16 (depends on 14)

The one or more non-transitory computer-readable media of claim 14, wherein:
the file system command is received at a file system command interface of the operating system;
the operating system executing the file system command using the GOFS partition is performed responsive to the file system command interface determining that the file system command is for the GOFS; and
the one or more sequences of instructions further comprise instructions that, when executed by one or more processors, cause:
receiving, at the file system command interface, a second file system command;
the file system command interface determining whether the second file system command is for the GOFS or for a hierarchically-organized file system;
responsive to determining that the second file system command is for the GOFS, the file system command interface causing the second file system command to be executed using the GOFS partition; and
responsive to determining that the second file system command is for a hierarchically-organized file system, the file system command interface communicating the second file system command to a virtual file system switch to cause the second file system command to be executed for the hierarchically-organized file system.

### Claim 17 (depends on 16)

The one or more non-transitory computer-readable media of claim 16, wherein:
the superblock identifies a root node of the graph;
the superblock further identifies a name of the root node;
the file system command includes an absolute path to a node of the graph;
the one or more sequences of instructions include instructions that, when executed by one or more processors, cause interpreting the absolute path based on the root node identified by the superblock.

### Claim 18 (depends on 17)

The one or more non-transitory computer-readable media of claim 17, wherein the root node identified by the superblock is a particular node of the graph, the one or more sequences of instructions include instructions that, when executed by one or more processors, cause:
receiving, at the file system command interface, a second file system command to change the root node of the graph to a second node of the graph that is different than the particular node;
responsive to receiving the second file system command, causing the superblock to identify the second node as the root node of the graph;
after changing the root node to the second node:
receiving, at the file system command interface, a third file system command that includes a second absolute path to a node of the graph, and
interpreting the second absolute path based on the second node that is identified as the root node by the superblock.

### Claim 19 (depends on 14)

The one or more non-transitory computer-readable media of claim 14, wherein:
the gnode table comprises a plurality of slots storing the plurality of gnode data structures;
each gnode data structure of the plurality of gnode data structures further comprises a plurality of fields, each field of the plurality of fields storing one of:
one or more in-structure metadata values of one or more node attributes for a represented node,
one or more flags for the represented node,
mode data for the represented node,
owner data for the represented node,
timestamps for the represented node,
size data for the represented node, or
a count of edges originating at the represented node.

### Claim 20 (depends on 14)

The one or more non-transitory computer-readable media of claim 14, wherein a particular content field, of a particular gnode data structure that represents a particular node of the graph, comprises one of: content data for the particular node, or one or more pointers to one or more data blocks in the GOFS partition storing content data for the particular node.

### Claim 21 (depends on 20)

The one or more non-transitory computer-readable media of claim 20, wherein the particular gnode data structure comprises a content interpretation flag that indicates whether the content field should be interpreted as (a) content data for the particular node, or (b) one or more pointers.

### Claim 22 (depends on 14)

The one or more non-transitory computer-readable media of claim 14, wherein a particular edge field, of a particular gnode data structure that represents a particular node of the graph, comprises one or more pointers to one or more edge entry data structures representing one or more edges, of the graph, originating at the particular node.

### Claim 23 (depends on 22)

The one or more non-transitory computer-readable media of claim 22, wherein, for each edge entry data structure, of the one or more edge entry data structures:
said each edge entry data structure (a) identifies a particular destination node of the graph as a destination node of an edge represented by said each edge entry data structure, and (b) represents a component of a particular relationship, of the one or more relationships, between the particular node and the particular destination node;
wherein the particular relationship is further represented by a second edge entry data structure, associated with the particular destination node, that identifies the particular node as the destination node of an edge represented by the second edge entry data structure.

### Claim 24 (depends on 22)

The one or more non-transitory computer-readable media of claim 22, wherein each edge entry data structure, of the one or more edge entry data structures, comprises one or more flags for an edge represented by said each edge entry, the one or more flags comprising one or more of: a traversable flag, an operating system-specific hidden flag, a user-specific hidden flag, or a visited flag.

### Claim 25 (depends on 24)

The one or more non-transitory computer-readable media of claim 24, wherein:
a particular edge entry data structure, of the one or more edge entry data structures, that identifies a second node as a destination node of a hidden edge comprises a particular flag field with an operating system-specific hidden flag that indicates that the particular edge entry data structure is hidden;
the second node is associated with a second edge entry representing an unhidden edge originating at the second node and terminating at the particular node;
the one or more sequences of instructions include instructions that, when executed by one or more processors, cause:
detecting an instruction to delete the particular node;
in response to detecting the instruction to delete the particular node, deleting the particular node comprising:
using the particular edge entry data structure to identify the second node, and
removing the second edge entry from the second node.

### Claim 26 (depends on 14)

The one or more non-transitory computer-readable media of claim 14, wherein:
said receiving the file system command from the application comprises receiving the file system command via a command-line interface;
the file system command comprises instructions for one of:
adding or modifying a node in the graph;
adding or modifying a relationship between nodes of the graph;
adding or modifying content associated with a node of the graph;
adding or modifying metadata for a node of the graph;
adding or modifying metadata for a relationship of the graph; or adding or modifying metadata for the superblock.