Map-reduce ready distributed file system

• US 9,773,016 B2
• Filed: 11/24/2015
• Issued: 09/26/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): Nguyen, Merilyn
• Application Number:
  US14/951,437
• Publication Number:
  US 20160078052A1
• Time in Patent Office: 672 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 computer implemented map reduce method comprising:

maintaining information about where each of a plurality of containers is located in a container location database (CLDB), wherein a storage pool contains zero or more containers, wherein a cluster node in a plurality of cluster nodes contains one or more storage pools;

structuring data within said containers using a plurality of inodes;

replicating said containers to other cluster nodes with one container designated as master for each replication chain;

storing data in said CTDB as modes in well known containers;

maintaining a database in CLDB nodes, wherein said database contains at least following information about all of said containers;

nodes that have replicas of a container,

an ordering of a replication chain for each container,

wherein updates to said container are sent to a master container for said updated container, and wherein changes to content of said container are propagated to said replicas of said container by said master container;

storing in said CLDB a location of all replicas of said container, a structure of a replication for said container, and an epoch number for each container, wherein said epoch number is incremented each time said structure of said replication for said container is changed, and wherein an epoch'"'"'s changes are noted in a transaction history for each version of said container and gaps are inserted whenever said master container is noted in said replication chain; and

tracing back through transactions that have been applied to each copy when examining said master container and target copies of a same container to determine a point in a history of two containers when the two containers were identical.

2. The method of claim 1, further comprising:

run-length encoding a set of committed transactions, wherein an on-disc state is updated only when a new epoch is begun as a new master is designated, and wherein the transactions are identified by said epoch in which the transactions were performed, as well as by a transaction counter in said container.

3. The method of claim 1, wherein a target container is brought up to date relative to said master container by undoing any changes made to a secondary version of said container because changes on said target container may not all have been applied to said master container.

4. The method of claim 3, wherein once a common ancestor transaction is identified, said secondary version of said container is scanned to find all blocks that have been modified since said common ancestor transaction;

wherein as these blocks are found, said target container over-writes the blocks by requesting these same blocks from said master container;

wherein all blocks in said target container are left either in a state that all blocks in said target container had as of a common ancestor state or in a later state present on said master container; and

wherein all blocks are updated to a current state of said master container.