Map-reduce ready distributed file system

• US 9,798,735 B2
• Filed: 12/16/2016
• Issued: 10/24/2017
• 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): Herndon, Heather
• Assistant Examiner(s): NGUYEN, MERILYN P
• Application Number:
  US15/381,733
• Publication Number:
  US 20170116221A1
• Time in Patent Office: 312 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 map-reduce compatible distributed file system comprising replicated containers preventing data loss comprising:

a container location database (CLDB) configured to maintain information about where each of a plurality of containers is located;

a plurality of cluster nodes, each cluster node containing one or more storage pools, each storage pool containing zero or more containers; and

a plurality of inodes for structuring said file system objects within said containers;

wherein said containers comprise file system objects, and said replicated containers preventing data loss comprise said containers replicated to other cluster nodes with one container designated as master container for each replication chain controlling transactions for said replication chain, said replication chain arranged in a linear pattern, a star pattern, or any combination of said linear and said star pattern, wherein said replication chain for said container is changed if a node holding any replica fails or is taken out of service, or if a node that previously contained a replica returns to service;

wherein said maintained information about where each of said plurality of containers is located that is maintained in said CLDB is stored as inodes in containers;

wherein said CLDB inodes are configured to maintain a database that contains at least following information about all of said containers;

nodes that have replicas of a container; and

an ordering of said replication chain for said container;

wherein updates to said container are sent to said master container for said updated container;

wherein changes to content of said container are propagated to said replicas of said container by said master container;

wherein some file system objects are larger than a single container; and

wherein some file system objects are spread over a larger number of nodes than a set represented by said replication chain of a single container.

2. The system of claim 1, wherein said replication chain is arranged in a linear replication pattern, in which a node holding said master container of said container propagates updates to a first slave node that contains another replica;

and

wherein said first slave node, in turn, propagates updates to a second slave node that contains a third replica of said container.

3. The system of claim 1, wherein said replication chain is arranged in a star replication pattern, in which a node containing said master container of a container propagates updates directly and simultaneously to all other nodes containing replicas of said container.

4. The system of claim 1, wherein when an update is received by a node containing said master container of said container, a lock is taken on a particular portion of a file being updated to guarantee that updates that change a same portion of said file are transactionally serialized;

and

wherein updates are made consistently on all replicas of said container.

5. The system of claim 1, wherein a number of update transactions that are allowed to be pending for a single file is limited to increase amount of parallelism available for updates.

6. The system of claim 1, wherein updates to said containers are acknowledged once enough of said nodes containing replicas have acknowledged that they have received said update.

7. The system of claim 1, wherein multiple updates are pending at a same time to increase potential parallelism, but all updates to said container are assigned a serial update identifier by said master container.

8. The system of claim 1, wherein updates are applied on different replicas in different orders, but only updates that have been acknowledged by all replicas are reported back to a client as committed.

9. The system of claim 1, wherein, before reporting an update as completed, all updates with smaller update identifiers are also completed.

10. The system of claim 1, wherein potentially out-of-date replicas are resynchronized to a current state of said master container of said container.

11. The system of claim 1, wherein when a node containing an out-of-date replica joins an existing replica chain, said node containing said out-of-date replica contacts said CLDB;

wherein said CLDB may decide that enough replicas are already known, in which case said node is instructed to discard said replica; and

wherein said CLDB may also assign said out-of-date replica to said replication chain, at which point a resynchronization process is executed to bring said out-of-date container up to a current state.

12. The system of claim 1, wherein when a set of failing nodes does not include a node containing said master container, failing nodes are removed from said replication chain, but said master container survives;

and

wherein all other replicas are considered to be out-of-date.

13. The system of claim 1, wherein a file chunk and an original inode are updated in a coordinated fashion.

14. The system of claim 1, wherein an original inode and multiple file chunks are updated together.

15. 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 all data and meta-data for a volume is organized into a single name container and zero or more data containers; and

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