VAST DATA LTD.

A system and method for using free space for recovering erasure coding data sets. The method includes segmenting at least one erasure coding data set into at least one stripe based on an erasure coding scheme, wherein each erasure coding data set includes chunks, wherein the chunks include chunks of systematic data and chunks of parity data; distributing the at least one stripe across non-volatile memory nodes based on the erasure coding scheme, wherein each non-volatile memory node is a unit of a non-volatile storage device; and upon a first failure of one of the non-volatile memory nodes: detecting that at least one of the non-volatile memory nodes that is not failed includes a first free space that does not currently store user data; and performing a first recovery process for recovering a first portion of the at least one erasure coding data set, based on the first free space.

A large-scale storage system is provided. The large-scale system includes a plurality of compute nodes; a plurality of storage nodes; and a communication fabric for providing a communication infrastructure between the plurality of compute nodes and the plurality of storage nodes; wherein each compute node of the plurality of compute nodes is configured to independently perform at least a storage operation on any of the storage nodes in a persistent manner, and wherein each storage node of the plurality of storage nodes provides physical storage space of the large-scale storage system.

A system and method for erasure coding. The method includes distributing a plurality of data chunks according to a mirroring scheme, wherein the plurality of data chunks is distributed as a plurality of rows among a plurality of non-volatile memory (NVM) nodes, wherein the mirroring scheme defines a plurality of groups, each group including a subset of the plurality of data chunks, wherein each data chunk in a group has a role corresponding to a relative position of the data chunk within the group, wherein data chunks included in the plurality of groups having the same relative positions within their respective groups have the same role, wherein each row of the plurality of rows includes at least one summation data chunk that is a function of at least one data chunk included in the row and of at least one extra data chunk included in at least one other row.

A system and method for determining ancestry in directed acyclic graphs (DAGs). The method includes 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, wherein the first change time data indicates a time of a first change to ancestry of the closest point of interest (CPOI); accessing a CPOI of the first node to obtain second change time data, wherein the second change time data indicates a time of 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.

Systems and methods for scalable locking. A method includes adding a first lock entry representing a pending lock to a first tree, the first lock entry indicating a range to be locked; checking at least a portion of at least one second tree to determine whether a conflicting lock exists for the first lock entry among at least one second lock entry based on the range to be locked, wherein each of the first tree and the at least one second tree is a data structure including a plurality of nodes representing at least a plurality of attributes, wherein the plurality of attributes of the at least one second tree includes the at least one second lock entry; committing the pending lock when no conflicting lock exists; and resolving the pending lock based on a resolution of the conflicting lock when a conflicting lock exists.

A distributed storage system. The distributed storage system includes a plurality of storage nodes (DNodes), wherein the DNodes are configured to store a plurality of elements and a plurality of data blocks, wherein each element is a persistent metadata structure, wherein at least one of the elements store at least one attribute, wherein the at least one attribute includes a plurality of pointers; and a plurality of compute nodes (CNodes), wherein each CNode has access to each of the DNodes, wherein each CNode is assigned to a respective at least one cluster of a plurality of clusters, wherein each CNode is configured to receive at least a portion of access commands directed to the respective at least one cluster and to execute the received access commands based on the plurality of elements.

A storage system. The storage system includes a data store including a plurality of data blocks; and an element store, the element store including a plurality of element trees, wherein each element tree includes a plurality of metadata blocks containing pointers, wherein data of the plurality of data blocks is read by navigating at least one of the plurality of element trees, wherein the element store includes a first level and at least one second level, wherein the first level is shared among the plurality of plurality of element trees.

A storage system. The storage system includes a plurality of storage nodes (DNodes), wherein the DNodes are configured to store a plurality of elements and a plurality of data blocks, wherein each element is a persistent metadata structure, wherein at least one of the elements store at least one attribute, wherein the at least one attribute includes a plurality of pointers, wherein at least one of the data blocks is stored in at least one of the elements when the at least one of the data blocks has a size below a threshold size; and a plurality of compute nodes (CNodes), wherein each CNode has access to each of the DNodes, wherein each CNode is configured to receive an access command and to execute the access command based on the elements.

A system and method for scalable storage. The method includes placing a lock on a portion of a storage node, wherein placing the lock further comprises replacing a first value stored in the storage node with a second value using an atomic operation, wherein the atomic operation replaces the first value with the second value when the first value indicates an empty lock status, wherein the second value indicates an active lock status; allocating a storage location in the storage node by updating metadata stored in the locked portion of the storage node when the lock has been placed; and releasing the lock, wherein releasing the lock further comprises replacing the second value with a third value, wherein the third value indicates the empty lock status.

A system and method for using free space to improve erasure code locality. The method includes logically segmenting an erasure coding data set into a stripe based on an erasure coding scheme, wherein the erasure coding data set includes a plurality of chunks, wherein the plurality of chunks includes a plurality of chunks of systematic data and a plurality of chunks of parity data, wherein the stripe includes free user data; and distributing the stripe across a plurality of non-volatile memory nodes based on the erasure coding scheme, wherein the free user data is stored in at least one memory location among the plurality of non-volatile memory nodes, wherein each non-volatile node is a unit of non-volatile memory.