Map-reduce ready distributed file system

• US 10,146,793 B2
• Filed: 08/03/2017
• Issued: 12/04/2018
• Est. Priority Date: 06/19/2010
• Status: Active Grant

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: MapR Technologies, Inc. (Hewlett-Packard Enterprise Company)
• Inventors: Srivas, Mandayam C., Ravindra, Pindikura, Saradhi, Uppaluri Vijaya, Pande, Arvind Arun, Sanapala, Chandra Guru Kiran Babu, Renu, Lohit Vijaya, Vellanki, Vivekanand, Kavacheri, Sathya, Hadke, Amit Ashoke
• Primary Examiner(s): NGUYEN, MERILYN P
• Application Number:
  US15/668,666
• Publication Number:
  US 20170329798A1
• Time in Patent Office: 488 Days
• CPC Class Codes: G06F 16/10 File systems; File servers
• 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/178 Techniques for file synchronisation in file systems
• CPC Class Codes: G06F 16/182 Distributed file systems
• CPC Class Codes: G06F 16/1844 Management specifically adapted to replicated file systems
• CPC Class Codes: G06F 16/1865 Transactional file systems
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/23 Updating
• CPC Class Codes: G06F 16/235 Update request formulation
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
• CPC Class Codes: G06F 16/273 Asynchronous replication or reconciliation
• CPC Class Codes: G06F 16/275 Synchronous replication
• CPC Class Codes: G06F 8/658 Incremental updates; Differential updates
• CPC Class Codes: H04L 65/102 Gateways arrangements for connecting between networks having differing types of switching systems, e.g. gateways, H04L12/66

Abstract

A map-reduce compatible distributed file system that consists of successive component layers that each provide the basis on which the next layer is built provides transactional read-write-update semantics with file chunk replication and huge file-create rates. Containers provide the fundamental basis for data replication, relocation, and transactional updates. A container location database allows containers to be found among all file servers, as well as defining precedence among replicas of containers to organize transactional updates of container contents. Volumes facilitate control of data placement, creation of snapshots and mirrors, and retention of a variety of control and policy information. Also addressed is the use of distributed transactions in a map-reduce system; the use of local and distributed snapshots; replication, including techniques for reconciling the divergence of replicated data after a crash; and mirroring.

Claims

1. A system to avoid data loss comprising:

a plurality of cluster nodes storing a plurality of containers comprising file system objects;

a plurality of replicated containers, each replicated container in the plurality of replicated containers comprising a copy of a container in the plurality of containers, the replicated container stored on a first cluster node in the plurality of cluster nodes different from a second cluster node in the plurality of cluster nodes storing the container; and

a replication chain associated with each container in the plurality of containers to avoid data loss, the replication chain comprising a master container and a slave container, the master container being an initial container in the replication chain, wherein the replication chain for the container is changed if a cluster node holding the replicated container is taken out of service, or if the cluster node holding the replicated container returns to service, wherein the master container receives an update to the slave container and propagates the update to the replication chain;

a storage pool including;

a block allocation bitmap indicating which blocks in a disk are in use;

a transaction log comprising a list of pointers to disk regions that hold log data;

a container map comprising a mapping from a container identification (id) to a container specification of the container in the storage pool; and

a super-block containing offsets to starting points of the block allocation bitmap, the transaction log, and the container map.

2. The system of claim 1, the container comprising an inode stored as a local file.

3. The system of claim 2, the inode comprising an owner of the container, permissions of the container, a parent file identifier of the container, an object type of the container, a size of the container, a direct data pointer, an indirect data pointer, and a version number.

4. The system of claim 1, the container representing a local file that contains bytes entirely within the container.

5. The system of claim 1, the container representing a chunked file that contains bytes across the plurality of containers.

6. The system of claim 1, comprising a container location database (CLDB) including:

the cluster node containing the replicated container;

a version of the container available on the cluster node; and

an ordering of the replication chain for the container.

7. The system of claim 1, an ordering of the replication chain arranged in a linear replication pattern, in which the cluster node containing the master container propagates the update to an initial slave cluster node that contains the replicated container;

and

wherein the initial slave cluster node propagates the update to a second slave cluster node that contains another replicated container.

8. The system of claim 1, an ordering of the replication chain arranged in a star replication pattern, in which the cluster node containing the master container propagates the update directly and simultaneously to all other cluster nodes containing the replicated container.

9. The system of claim 1, the block allocation bitmap comprising a second list of pointers to contiguous disk regions that contain bitmap data.

10. The system of claim 1, the container specification comprising a bit to indicate whether the container has been marked as copy-on-write, where the container is located on the disk, and a list of snapshots of the container.

11. The system of claim 1, further comprising:

a distributed transaction in a form of a snapshot of a file system volume, consisting of directories and files spread over a number of containers;

wherein data and meta-data for a volume are organized into a name container and zero or more data containers; and

wherein cross-container references to the data are segregated into the name container while keeping the data in data containers.

12. The system of claim 1, comprising a key-value object relating a key at least one of a directory, container location map, or an offset map in a compressed file.

13. A method comprising:

configuring a plurality of cluster nodes to store a plurality of containers including file system objects;

configuring a plurality of replicated containers, wherein each replicated container in the plurality of replicated containers includes a copy of a container in the plurality of containers, the replicated container stored on a first cluster node in the plurality of cluster nodes different from a second cluster node in the plurality of cluster nodes storing the container; and

configuring a replication chain associated with each container in the plurality of containers to avoid data loss and to include a master container and a slave container, the master container being an initial container in the replication chain, wherein the replication chain for the container is changed if a cluster node holding the replicated container is taken out of service, or if the cluster node holding the replicated container returns to service, wherein the master container receives an update to the slave container and propagates the update to the replication chain;

contacting a container location database (CLDB) when the cluster node containing an out-of-date replicated container joins an existing replication chain;

when the CLDB determines that a number of replicated containers in the replication chain is sufficient, instructing the cluster node to discard the out-of-date replicated container;

when the CLDB determines that the number of replicated containers in the replication chain is insufficient, assigning the out-of-date replicated container to the replication chain; and

when the CLDB determines that the number of replicated containers in the replication chain is insufficient, in response to assigning the out-of-date replicated container to the replication chain, resynchronizing the out-of-date replicated container up to a current state.

14. The method of claim 13, comprising:

in response to receiving the update, locking a particular portion of a file being updated to guarantee that the update that changes a same portion of the file are transactionally serialized.

15. The method of claim 13, comprising:

acknowledging the update to the container once enough of the plurality of cluster nodes containing the plurality of replicated containers have acknowledged a receipt of the update.

16. The method of claim 13, comprising:

increasing parallelism by assigning a serial update identifier, by the master container, to each update in a plurality of updates, when the plurality of updates is pending at a same time.

17. The method of claim 13, comprising:

applying a plurality of updates to each replicated container in the plurality of replicated containers in different order; and

reporting to a client that only updates that have been acknowledged by all of the plurality of replicated containers have been committed.

18. The method of claim 13, comprising:

resynchronizing a potentially out-of-date replicated container to the current state of the master container.