Systems and methods of simulating the state of a distributed storage system

Patent metadata

Field	Value
Publication number	US-9659031-B2
Application number	US-201314037298-A
Country	US
Kind code	B2
Filing date	Sep 25, 2013
Priority date	Feb 9, 2010
Publication date	May 23, 2017
Grant date	May 23, 2017

Abstract

A distributed storage system has a plurality of instances. A computer system simulates the state of the distributed storage system. The system obtains a current state of the distributed storage system and replication policies for objects in the distributed storage system. Each replication policy specifies criteria for placing copies of the relevant objects among the plurality of instances. The system receives proposed modifications to the state of the distributed storage system and simulates the state of the distributed storage system over time based on the current state of the distributed storage system, current statistical trends in the state of the distributed storage system, the replication policies for the objects in the distributed storage system, and the proposed modifications to the state of the distributed storage system. One or more reports are generated relating to time evolution of the state of the distributed storage system based on the simulation.

First claim

What is claimed is:

1. 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 for:
obtaining a current state of the distributed storage system and replication policies for 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 criteria for placing copies of the respective object among the plurality of instances;
receiving one or more proposed modifications to the state of the distributed storage system, wherein each respective proposed modification to the state of the distributed storage system includes a respective time at which the respective proposed modification to the state of the distributed storage system is to occur;
simulating the state of the distributed storage system over time based on the current state of the distributed storage system, one or more current statistical trends in the state of the distributed storage system, the replication policies for the objects in the distributed storage system, and the proposed modifications to the state of the distributed storage system; and
generating one or more reports relating to the simulation.

2. The non-transitory computer readable storage medium of claim 1 , wherein the current state of the distributed storage system includes:
current statuses of replication queues at instances of the distributed storage system; or
a list of current replicas of objects in the distributed storage system.

3. The non-transitory computer readable storage medium of claim 1 , wherein a respective proposed modification to the state of the distributed storage system is selected from the group consisting of:
an addition of storage space in the distributed storage system;
an addition of instances of the distributed storage system;
an increase in the amount of data stored in the distributed storage system; and
an addition of network resources in the distributed storage system.

4. The non-transitory computer readable storage medium of claim 1 , wherein a respective proposed modification to the state of the distributed storage system is selected from the group consisting of:
a removal of storage space in the distributed storage system;
a removal of instances of 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; and
a modification to an algorithm that generates replication requests.

5. The non-transitory computer readable storage medium of claim 1 , further comprising implementing at least one of the proposed modifications to the state of the distributed storage system based on the reports.

6. 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 the distributed storage system and replication policies for objects in the distributed storage system, wherein a respective replication policy for a respective object specifies criteria for placing copies of the respective object among the plurality of instances;
receiving one or more proposed modifications to the state of the distributed storage system, wherein each respective proposed modification to the state of the distributed storage system includes a respective time at which the respective proposed modification to the state of the distributed storage system is to occur;
simulating the state of the distributed storage system over time based on the current state of the distributed storage system, one or more current statistical trends in the state of the distributed storage system, the replication policies for the objects in the distributed storage system, and the proposed modifications to the state of the distributed storage system; and
generating one or more reports relating to the simulation.

7. The method of claim 6 , wherein the current state of the distributed storage system includes:
current statuses of replication queues at instances of the distributed storage system; or
a list of current replicas of objects in the distributed storage system.

8. The method of claim 6 , 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; and
current planned maintenance operations zones.

9. The method of claim 6 , wherein a respective proposed modification to the state of the distributed storage system is selected from the group consisting of:
an addition of storage space in the distributed storage system;
an addition of instances of the distributed storage system;
an increase in the amount of data stored in the distributed storage system; and
an addition of network resources in the distributed storage system.

10. The method of claim 6 , wherein a respective proposed modification to the state of the distributed storage system is selected from the group consisting of:
a removal of storage space in the distributed storage system;
a removal of instances of 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; and
a modification to an algorithm that generates replication requests.

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

12. A computer 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 for:
obtaining a current state of the distributed storage system and replication policies for objects in the distributed storage system, wherein a respective replication policy for a respective object specifies criteria for placing copies of the respective object among the plurality of instances;
receiving one or more proposed modifications to the state of the distributed storage system, wherein each respective proposed modification to the state of the distributed storage system includes a respective time at which the respective proposed modification to the state of the distributed storage system is to occur;
simulating the state of the distributed storage system over time based on the current state of the distributed storage system, one or more current statistical trends in the state of the distributed storage system, the replication policies for the objects in the distributed storage system, and the proposed modifications to the state of the distributed storage system; and
generating one or more reports relating to the simulation.

13. The computer system of claim 12 , wherein the current state of the distributed storage system includes:
current statuses of replication queues at instances of the distributed storage system; or
a list of current replicas of objects in the distributed storage system.

14. The computer system of claim 12 , wherein the current state of the distributed stora

Assignees

• Google Inc

Inventors

• Zunger Yonatan
• Drobychev Alexandre
• Kesselman Alexander
• Vickrey Rebekah C
• Dachille Frank Clare
• Datuashvili George

Classifications

• G06F11/2094

  Redundant storage or storage space (G06F11/2056 takes precedence) · CPC title

• G06F17/30215 Primary

  Physics · mapped topic

• G06F11/3457

  Performance evaluation by simulation · CPC title

• H04L67/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] · CPC title

• H04L67/1095 Primary

  Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes · CPC title