Reconciler for a Distributed Storage System

• US 20170011078A1
• Filed: 07/07/2015
• Published: 01/12/2017
• Est. Priority Date: 07/07/2015
• Status: Active Grant

• Current Assignee: NVIDIA Corporation
• Original Assignee: SwiftStack Inc. (NVIDIA Corporation)
• Inventors: GERRARD, Clay, LUSE, Paul, MERRITT, Samuel, DICKINSON, John
• Granted Patent: US 10,061,790 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/182 Distributed file systems
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/2282 Tablespace storage structures; Management thereof

Abstract

A technique is applied to eventually converge on a single data storage strategy for any set of object data which had an inconsistent data storage strategy applied during storage while there was a network partition. This state could occur in instances of a highly available distributed object storage system which can store objects according to multiple data storage strategies. Upon the healing of a network partition, the technique discovers if multiple data storage strategies were applied to the object data stored during a network partition, deterministically identifies which data storage strategy represents the correct strategy, for example based on the log of state transitions requested by the client according to the API contract, and ensures that this strategy is consistently applied to all object data in the collection.

Claims

1. A computer implemented method for storing object data in a distributed object storage system, comprising:

said distributed object storage system storing objects according to multiple data storage strategies;

providing a processor for converging on a single data storage strategy for a set of object data to which an inconsistent data storage strategy is applied during a network partition;

said processor, upon the healing of said network partition, discovering object data stored during said network partition to which multiple data storage strategies were applied;

said processor deterministically identifying a data storage strategy that represents a correct strategy; and

said processor ensuring that said strategy is consistently applied to all of said object data in said distributed object storage system.

2. The method of claim 1, further comprising:

using a log of state transitions requested by a client according to an API contract to identify a data storage strategy that represents a correct strategy.

3. A computer implemented method for discovering and logging misplaced objects in a distributed object storage system, comprising:

providing a processor running at least one container replicator in said distributed object storage system, said container replicator discovering storage policy inconsistencies;

said container replicator recording each transaction in a container database; and

said container replicator adding said inconsistencies to a misplaced objects container.

4. The method of claim 3, further comprising:

said container replicator identifying objects with conflicting storage policies; and

when a conflicting object is identified, said container replicator copying said object'"'"'s row from said container database to a local misplaced objects container.

5. The method of claim 3, further comprising:

said container replicator creating a misplaced objects container when a misplaced objects container does not already exist.

6. The method of claim 3, further comprising:

said container replicator using a log format to record a history of state transitions which result from a series of requests, herein said history is recorded in a plurality of container replicas;

each container replica maintaining a set of three vectors that indicate when the container replica last recorded a PUT or DELETE and when these actions resulted in a change of the container replica'"'"'s status (created or deleted); and

said container replicator comparing log items in said history between two or more containers to determine a representation of said state transaction history which resulted in a current state.

7. The method of claim 3, further comprising:

a container reconciler periodically locating and processing any misplaced objects containers;

said container reconciler examining object rows in each misplaced objects container in descending order and then determining a correct policy; and

said container reconciler making calls to disputed containers and using timestamp information to determine which policy is the correct policy for the container.

8. The method of claim 7, further comprising:

when a container is created, said container reconciler updating PUT and STATUS with a time of that action;

when a container is deleted, said container reconciler updating DELETE with a time of that action;

when a time of a DELETE action is not nil and it is greater than a time of a PUT action, said container reconciler considering said container to be in a DELETED state, otherwise said container is CREATED; and

when status of a container changes from CREATED or DELETED, said container reconciler updating STATUS with a time of said change.

9. The method of claim 7, further comprising:

said container reconciler moving an object from an incorrect policy to the correct policy for the container.

10. The method of claim 7, further comprising:

said container reconciler applying object writes to a correct storage policy;

said container reconciler cleaning up writes to an incorrect storage policy which no longer apply and removing rows from misplaced objects containers;

when all rows are successfully reconciled, said container reconciler deleting any now empty misplaced objects containers; and

said reconciler continuing to process misplaced objects containers until all misplaced objects containers are reconciled and removed.

11. A computer implemented method for correcting container updates in a highly available distributed object storage system, comprising:

a container noticing a conflict;

said container enqueuing information in a shared repository;

a separate, distributed reconciler asynchronously using time/date sync points to determine conflict resolution;

said reconciler moving objects from an incorrect policy to the correct policy; and

when said objects have been repositioned, said reconciler updating container listings accordingly.

12. The method of claim 11, further comprising:

distributing a transaction history of a container'"'"'s life-cycle within said object storage system;

each node within said object storage system communicating with each of its peers to replicate said transaction history between all said nodes;

evaluating the transaction history of a local node and a remote node for an inconsistency during each communication; and

when an inconsistency is found, both nodes applying an update to ensure that subsequent negotiations prefer to accept a current agreement rather than renegotiate.

13. An apparatus for storing object data in a distributed object storage system, wherein said distributed object storage system stores objects according to multiple data storage strategies, said apparatus comprising:

a processor for converging on a single data storage strategy for a set of object data to which an inconsistent data storage strategy is applied during a network partition;

said processor, upon the healing of said network partition, discovering object data stored during said network partition to which multiple data storage strategies were applied;

said processor deterministically identifying a data storage strategy that represents a correct strategy; and

said processor ensuring that said strategy is consistently applied to all of said object data in said distributed object storage system.

14. An apparatus for discovering and logging misplaced objects in a distributed object storage system, comprising:

at least one container replicator in said distributed object storage system, said container replicator discovering storage policy inconsistencies;

said container replicator recording each transaction in a container database; and

said container replicator adding said inconsistencies to a misplaced objects container.