Metadata management for fixed content distributed data storage

• US 7,657,581 B2
• Filed: 07/27/2005
• Issued: 02/02/2010
• Est. Priority Date: 07/29/2004
• Status: Active Grant

• Current Assignee: Hitachi Vantara, LLC (Hitachi, Ltd.)
• Original Assignee: Archivas, Inc. (Hitachi, Ltd.)
• Inventors: Orenstein, Jack A., Chavez, David E.
• Primary Examiner(s): Alam; Hosain T
• Assistant Examiner(s): Yen; Syling
• Application Number:
  US11/190,402
• Publication Number:
  US 20060026219A1
• Time in Patent Office: 1,651 Days
• Field of Search: 711/162, 711/165, 711/114, 707/201, 707/10, 707/202, 707/203, 707/204, 709/203, 713/165, 713/170, 713/176, 705/51
• US Class Current: 707/661
• CPC Class Codes: G06F 11/2097 maintaining the standby controller/processing unit updated initialisation or re-synchronisation thereof G06F11/1658 and subgroups
• 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

Abstract

An archival storage cluster of preferably symmetric nodes includes a metadata management system that organizes and provides access to given metadata, preferably in the form of metadata objects. Each metadata object may have a unique name, and metadata objects are organized into regions. Preferably, a region is selected by hashing one or more object attributes (e.g., the object'"'"'s name) and extracting a given number of bits of the resulting hash value. The number of bits may be controlled by a configuration parameter. Each region is stored redundantly. A region comprises a set of region copies. In particular, there is one authoritative copy of the region, and zero or more backup copies. The number of backup copies may be controlled by a configuration parameter. Region copies are distributed across the nodes of the cluster so as to balance the number of authoritative region copies per node, as well as the number of total region copies per node. Backup region copies are maintained synchronized to their associated authoritative region copy.

Claims

1. In a redundant array of independent nodes networked together, wherein each node executes an instance of an application that provides object-based storage, a metadata management method, comprising:

storing metadata objects in a set of regions distributed across the array, wherein a given region is identified by hashing a metadata object attribute and extracting a given set of bits of a resulting hash value;

generating a map that, for each region, identifies a node that stores an authoritative copy of the region and thereby is responsible for receiving and responding to update requests directed to the region, and that further identifies zero or more nodes that each store a backup copy of the region and thereby are capable of acting as backup region copies to the authoritative region copy, wherein the map is generated by the following sub-steps;

performing a census across at least a subset of the independent nodes networked together to determine which regions are located on which nodes currently in the array and, for each such region, a timestamp associated with a last update processed at the region; and

based on the timestamps, deleting obsolete regions to generate the map;

distributing the map across the array of independent nodes so that each node has an identical, global view of where the authoritative and backup region copies are located;

upon receiving a request to update a given metadata object, using the map to identify the authoritative region copy for the metadata object;

processing the update request;

if synchronization between the authoritative region copy and at least one of its associated backup region copies cannot be maintained as the update is processed, issuing a new map so that each node continues to have an identical, global view of where the authoritative and backup region copies are located.

2. The method as described in claim 1 wherein the update request is processed by committing the update in the authoritative copy of the region, and issuing the update request to each of the zero or more backup copies of the region.

3. The method as described in claim 2 wherein an acknowledgement is issued from the backup region upon receipt of the update request, irrespective of whether a backup request is committed.

4. The method as described in claim 1 wherein synchronization cannot be maintained because of a failure associated with one of:

a backup region copy or the authoritative region copy.

5. The method as described in claim 1 further including:

as the number of independent nodes increases, incrementally partitioning the map.

6. The method as described in claim 5 wherein the map is incrementally partitioned by adjusting a given first hash value while maintaining a second given hash value unchanged.

7. The method as described in claim 6 wherein the given first hash value is adjusted by adding a bit to the hash value.

8. The method as described in claim 1 wherein region copies are distributed across nodes to balance a number of authoritative region copies per node.

9. The method as described in claim 1 wherein region copies are distributed across nodes to balance a number of authoritative region copies per node, and to balance a total number of region copies per node.

10. The method as described in claim 1 wherein a number of backup copies of a given region is configurable.

11. The method as described in claim 1 wherein the step of issuing a new map includes promoting a backup region copy to be the authoritative region copy.

12. The method as described in claim 11 wherein the region further comprises an incomplete region copy, wherein an incomplete region copy is ineligible to be promoted to being a backup region copy.

13. The method as described in claim 1 wherein the step of issuing a new map includes one of:

deleting a region copy, creating a region copy, promoting a backup region copy to be authoritative, promoting an incomplete region copy to a backup region copy, and demoting an authoritative region copy to a backup region copy.

14. A method, operative in a redundant array of independent nodes networked together, wherein metadata objects are stored in a set of regions distributed across the array, and wherein a given region is identified by hashing a metadata object attribute and extracting a given set of bits of a resulting hash value, comprising:

generating a map that, for each region, identifies a node that stores an authoritative copy of the region and thereby is responsible for receiving and responding to requests directed to the region, and that further identifies zero or more nodes that each store a backup copy of the region and thereby are capable of acting as backup region copies to the authoritative region copy, wherein the map is generated by the following sub-steps;

performing a census across at least a subset of the independent nodes networked together to determine which regions are located on which nodes currently in the array and, for each such region, a timestamp associated with a last update processed at the region; and

based on the timestamps, deleting obsolete regions to generate the map;

distributing the map across the array of independent nodes so that each node has an identical, global view of where the authoritative and backup region copies are located, wherein, upon its distribution, the map has associated therewith a guarantee that a given authoritative region copy and its associated zero or more backup region copies are deemed to be synchronized; and

issuing a new map and distributing the new map across the array if the guarantee cannot continue to be assumed so that each node continues to have an identical, global view of where the authoritative and backup region copies are located.

15. The method as described in claim 14 wherein the new map promotes a backup region copy to being the authoritative region copy for a given region if, due to a failure, a region does not have an authoritative region copy.

16. The method as described in claim 14 wherein the new map deletes an excess backup region copy if a region has more than a configurable amber of backup region copies.

17. The method as described in claim 14 wherein the new map creates a new incomplete region copy if, due to a failure or a promotion, a region has fewer that a configurable number of backup region copies.

18. The method as described in claim 14 wherein the new map reassigns a region copy from one node to another node.

19. The method as described in claim 18 wherein the region copy that is reassigned is an authoritative region copy.

20. An apparatus for use in a redundant array of independent nodes networked together, wherein metadata objects are stored in a set of regions distributed across the array, and wherein a given region is identified by hashing a metadata object attribute and extracting a given set of bits of a resulting hash value, comprising:

one or more processors;

a virtual machine executed by at least one processor;

a database;

a map stored in the database, wherein, for each region, the map identifies a node that stores an authoritative copy of the region and thereby is responsible for receiving and responding to update requests directed to the region, and that further identifies zero or more nodes that each store a backup copy of the region and thereby are capable of acting as backup region copies to the authoritative region copy, where the map has associated therewith a guarantee that a given authoritative region copy and its associated zero or more backup region copies are deemed to be synchronized, the map being replaceable by a new map if the guarantee cannot continue to be assumed;

one or more region manager processes executed in the virtual machine, wherein a given region copy is associated with its own region manager process;

a metadata manager process executed by a processor for generating and managing the one or more region manager processes, wherein the metadata manager process is adapted to assume a leadership role in which it performs a census across at least a subset of the independent nodes networked together to determine which regions are located on which nodes currently in the array and, for each such region, any timestamp associated with a last update processed at the region, the metadata manager process using results of the census to identify obsolete regions to thereby generate the map or the new map, wherein the map or the new map is distributed across the array of independent nodes so that each node can maintain an identical, global view of where the authoritative and backup region copies are located; and

a client process executed by a processor for receiving and responding to an update request.