TECHNICAL FIELD

The present disclosure relates generally to directed acyclic graphs (DAGs), and more specifically to determining hierarchical relationships in data.

BACKGROUND

In data storage, determining that a subset of stored data belongs to a particular subtree or other portion of a hierarchy may be useful for purposes such as creating snapshots, quotas, replications, and the like. Accordingly, techniques for effectively determining ancestry are desirable. Existing solutions for determining ancestry include navigating a hierarchy (e.g., a filesystem tree) along all potential paths.

It would therefore be advantageous to provide a solution that would overcome the challenges noted above.

SUMMARY

A summary of several example embodiments of the disclosure follows. This summary is provided for the convenience of the reader to provide a basic understanding of such embodiments and does not wholly define the breadth of the disclosure. This summary is not an extensive overview of all contemplated embodiments, and is intended to neither identify key or critical elements of all embodiments nor to delineate the scope of any or all aspects. Its sole purpose is to present some concepts of one or more embodiments in a simplified form as a prelude to the more detailed description that is presented later. For convenience, the term “some embodiments” or “certain embodiments” may be used herein to refer to a single embodiment or multiple embodiments of the disclosure.

Certain embodiments disclosed herein include a method for determining ancestry in directed acyclic graphs (DAGs). The method comprises: accessing a first node of a plurality of nodes in a DAG to obtain first change time data and ancestry data, wherein the plurality of nodes includes at least one point of interest (POI), wherein each POI is one of the plurality of nodes storing data indicating that the node is a POI, wherein the first node stores closest POI (CPOI) data indicating a CPOI for the first node, wherein the CPOI for the first node is one of the at least one POI that requires the fewest visits when traversing upward in the DAG beginning with the first node, wherein the first change time data indicates a time of a first change to ancestry of the CPOI; accessing a second node of the plurality of storage nodes to obtain second change time data, wherein the second node is the CPOI for the first node indicated in the CPOI data, wherein the second change time data indicates a time of a second change to ancestry of the CPOI, wherein the second change is a most recent change to ancestry of the CPOI; comparing the first change time data with the second change time data; and determining ancestry of the first node, wherein the ancestry of the first node is determined based on the ancestry data when the first change time data matches the second change time data.

Certain embodiments disclosed herein also include a non-transitory computer readable medium having stored thereon causing a processing circuitry to execute a process, the process comprising: accessing a first node of a plurality of nodes in a DAG to obtain first change time data and ancestry data, wherein the plurality of nodes includes at least one point of interest (POI), wherein each POI is one of the plurality of nodes storing data indicating that the node is a POI, wherein the first node stores closest POI (CPOI) data indicating a CPOI for the first node, wherein the CPOI for the first node is one of the at least one POI that requires the fewest visits when traversing upward in the DAG beginning with the first node, wherein the first change time data indicates a time of a first change to ancestry of the CPOI; accessing a second node of the plurality of storage nodes to obtain second change time data, wherein the second node is the CPOI for the first node indicated in the CPOI data, wherein the second change time data indicates a time of a second change to ancestry of the CPOI, wherein the second change is a most recent change to ancestry of the CPOI; comparing the first change time data with the second change time data; and determining ancestry of the first node, wherein the ancestry of the first node is determined based on the ancestry data when the first change time data matches the second change time data.

Certain embodiments disclosed herein also include a system for determining ancestry in directed acyclic graphs (DAGs). The system comprises: a processing circuitry; and a memory, the memory containing instructions that, when executed by the processing circuitry, configure the system to: access a first node of a plurality of nodes in a DAG to obtain first change time data and ancestry data, wherein the plurality of nodes includes at least one point of interest (POI), wherein each POI is one of the plurality of nodes storing data indicating that the node is a POI, wherein the first node stores closest POI (CPOI) data indicating a CPOI for the first node, wherein the CPOI for the first node is one of the at least one POI that requires the fewest visits when traversing upward in the DAG beginning with the first node, wherein the first change time data indicates a time of a first change to ancestry of the CPOI; access a second node of the plurality of storage nodes to obtain second change time data, wherein the second node is the CPOI for the first node indicated in the CPOI data, wherein the second change time data indicates a time of a second change to ancestry of the CPOI, wherein the second change is a most recent change to ancestry of the CPOI; compare the first change time data with the second change time data; and determine ancestry of the first node, wherein the ancestry of the first node is determined based on the ancestry data when the first change time data matches the second change time data.

