Location assignment daemon (LAD) simulation system and method

• US 8,560,292 B2
• Filed: 02/07/2011
• Issued: 10/15/2013
• Est. Priority Date: 02/09/2010
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Zunger, Yonatan, Drobychev, Alexandre, Kesselman, Alexander, Vickrey, Rebekah C., Dachille, Frank C., Datuashvili, George
• Primary Examiner(s): Shah, Kamini S
• Assistant Examiner(s): Hann, Jay B
• Application Number:
  US13/022,236
• Publication Number:
  US 20110196664A1
• Time in Patent Office: 981 Days
• Field of Search: None
• US Class Current: 703/13
• CPC Class Codes: G06F 11/2094 Redundant storage or storage space G06F11/2056 takes precedence
• CPC Class Codes: G06F 11/3457 Performance evaluation by simulation
• CPC Class Codes: G06F 13/10 Program control for peripheral devices G06F13/14 - G06F13/42 take precedence
• CPC Class Codes: G06F 16/1748 De-duplication implemented within the file system, e.g. based on file segments de-duplication techniques in storage systems for the management of data blocks G06F3/0641
• CPC Class Codes: G06F 16/1844 Management specifically adapted to replicated file systems
• CPC Class Codes: G06G 7/62 for electric systems or apparatus G06G7/78 takes precedence
• CPC Class Codes: H04L 67/1095 Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes
• CPC Class Codes: H04L 67/1097 for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]

Abstract

A system and method for simulating a state of a distributed storage system is provided. A current state of a distributed storage system and replication policies for the objects in the distributed storage system is obtained. Proposed modifications to the current state of the distributed storage system are received. The state of the distributed storage system is simulated over time based on the current state of the distributed storage system, the replication policies for the objects in the distributed storage system, and the proposed modifications to the current state of the distributed storage system. Then reports relating to the time evolution of the current state of the distributed storage system are generated based on the simulation.

Claims

1. A computer-implemented method for simulating a state of a distributed storage system having a plurality of instances, comprising:

at a computer system including one or more processors and memory storing one or more programs for execution by the one or more processors;

obtaining a current state of a distributed storage system and replication policies for the objects in the distributed storage system, wherein a respective replication policy for a respective object specifies parameters for allocating copies of the respective object among the plurality of instances;

receiving proposed modifications to the current state of the distributed storage system;

simulating the state of the distributed storage system over time based on the current state of the distributed storage system, the replication policies for the objects in the distributed storage system, and the proposed modifications to the current state of the distributed storage system; and

generating reports relating to the time evolution of the current state of the distributed storage system based on the simulation;

wherein a respective proposed modification to the current state of the distributed storage system includes information relating to the respective proposed modification to the current state of the distributed storage system and a time at which the respective proposed modification to the current state of the distributed storage system is to occur.

2. The method of claim 1, wherein the current state of the distributed storage system includes:

a current network state;

current user quotas for storage space in the distributed storage system;

storage space in the distributed storage system that are currently used by users;

current storage space available at instances of the distributed storage system;

current statuses of replication queues at instances of the distributed storage system;

current planned maintenance operations zones; and

a list of current replicas of objects in the distributed storage system.

3. The method of claim 1, wherein a respective proposed modification to the current state of the distributed storage system is selected from the group consisting of:

an addition of storage space in the distributed storage system;

a removal of storage space in the distributed storage system;

an addition of instances of the distributed storage system;

a removal of instances of the distributed storage system;

an increase in the amount of data stored in the distributed storage system;

a decrease in the amount of data stored in the distributed storage system;

a modification to replication policies for objects in the distributed storage system;

an addition of network resources in the distributed storage system; and

a modification to an algorithm that generates replication requests.

4. The method of claim 1, further comprising implementing at least one of the proposed modifications to the current state of the distributed storage system based on the reports.

5. A system for simulating a state of a distributed storage system having a plurality of instances, comprising:

one or more processors;

memory; and

one or more programs stored in the memory, the one or more programs comprising instructions to;

obtain a current state of a distributed storage system and replication policies for the objects in the distributed storage system, wherein a respective replication policy for a respective object specifies parameters for allocating copies of the respective object among the plurality of instances;

receive proposed modifications to the current state of the distributed storage system;

simulate the state of the distributed storage system over time based on the current state of the distributed storage system, the replication policies for the objects in the distributed storage system, and the proposed modifications to the current state of the distributed storage system; and

generate reports relating to the time evolution of the current state of the distributed storage system based on the simulation;

wherein a respective proposed modification to the current state of the distributed storage system includes information relating to the respective proposed modification to the current state of the distributed storage system and a time at which the respective proposed modification to the current state of the distributed storage system is to occur.

6. The system of claim 5, wherein the current state of the distributed storage system includes:

a current network state;

current user quotas for storage space in the distributed storage system;

storage space in the distributed storage system that are currently used by users;

current storage space available at instances of the distributed storage system;

current statuses of replication queues at instances of the distributed storage system;

current planned maintenance operations zones; and

a list of current replicas of objects in the distributed storage system.

7. The system of claim 5, wherein a respective proposed modification to the current state of the distributed storage system is selected from the group consisting of:

an addition of storage space in the distributed storage system;

a removal of storage space in the distributed storage system;

an addition of instances of the distributed storage system;

a removal of instances of the distributed storage system;

an increase in the amount of data stored in the distributed storage system;

a decrease in the amount of data stored in the distributed storage system;

a modification to replication policies for objects in the distributed storage system;

an addition of network resources in the distributed storage system; and

a modification to an algorithm that generates replication requests.

8. The system of claim 5, further comprising instructions to implement at least one of the proposed modifications to the current state of the distributed storage system based on the reports.

9. A non-transitory computer readable storage medium storing one or more programs configured for execution by a computer, the one or more programs comprising instructions to:

obtain a current state of a distributed storage system and replication policies for the objects in the distributed storage system, wherein the distributed storage system includes a plurality of instances, and wherein a respective replication policy for a respective object specifies parameters for allocating copies of the respective object among the plurality of instances;

receive proposed modifications to the current state of the distributed storage system;

simulate the state of the distributed storage system over time based on the current state of the distributed storage system, the replication policies for the objects in the distributed storage system, and the proposed modifications to the current state of the distributed storage system; and

generate reports relating to the time evolution of the current state of the distributed storage system based on the simulation;

wherein a respective proposed modification to the current state of the distributed storage system includes information relating to the respective proposed modification to the current state of the distributed storage system and a time at which the respective proposed modification to the current state of the distributed storage system is to occur.

10. The computer readable storage medium of claim 9, wherein the current state of the distributed storage system includes:

a current network state;

current user quotas for storage space in the distributed storage system;

storage space in the distributed storage system that are currently used by users;

current storage space available at instances of the distributed storage system;

current statuses of replication queues at instances of the distributed storage system;

current planned maintenance operations zones; and

a list of current replicas of objects in the distributed storage system.

11. The computer readable storage medium of claim 9, wherein a respective proposed modification to the current state of the distributed storage system is selected from the group consisting of:

an addition of storage space in the distributed storage system;

a removal of storage space in the distributed storage system;

an addition of instances of the distributed storage system;

a removal of instances of the distributed storage system;

an increase in the amount of data stored in the distributed storage system;

a decrease in the amount of data stored in the distributed storage system;

a modification to replication policies for objects in the distributed storage system;

an addition of network resources in the distributed storage system; and

a modification to an algorithm that generates replication requests.

12. The computer readable storage medium of claim 9, further comprising instructions to implement at least one of the proposed modifications to the current state of the distributed storage system based on the reports.