Balancing data distribution in a fault-tolerant storage system
AssigneeDropbox, Inc.
InventorKevin P. Modzelewski
Life of this patent
Estimating the term…
Abstract
The disclosed embodiments relate to a system for managing replicated copies of data items in a storage system. During operation, the system obtains a current configuration of the storage system, wherein the current configuration specifies locations of replicated copies of data items. Next, the system analyzes the current configuration to identify possible movements of copies of data items among locations in the storage system. The system then assigns utilities to the identified movements, wherein a utility assigned to a movement reflects a change in reliability resulting from the movement. Finally, the system selects a utility-maximizing set of movements and performs the utility-maximizing set of movements to improve the reliability of the storage system.
Claims20
A computer-implemented method for managing replicated copies of data items in a storage system, the method comprising:
- obtaining a current configuration of the storage system, wherein the current configuration specifies locations of replicated copies of data items;
- analyzing the current configuration to identify possible movements of copies of data items among locations in the storage system;
- assigning utilities to the identified movements, wherein a utility assigned to a movement reflects a change in reliability resulting from the movement;
- selecting a utility-maximizing set of movements;
- and
- performing the utility-maximizing set of movements to improve reliability of the storage system.
A non-transitory computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for managing replicated copies of data items in a storage system, the method comprising:
- obtaining a current configuration of the storage system, wherein the current configuration specifies locations of replicated copies of data items;
- analyzing the current configuration to identify possible movements of copies of data items among locations in the storage system;
- assigning utilities to the identified movements, wherein a utility assigned to a movement reflects a change in reliability resulting from the movement;
- selecting a utility-maximizing set of movements;
- and
- performing the utility-maximizing set of movements to improve reliability of the storage system.
A system that manages replicated copies of data items, comprising:
- a storage system configured to store replicated copies of data items, wherein the storage system is organized hierarchically and includes a plurality of storage devices;
- and
- a controller for the storage system wherein the controller is configured to,
- obtain a current configuration of the storage system, wherein the current configuration specifies locations of replicated copies of data items;
- analyze the current configuration to identify possible movements of copies of data items among locations in the storage system;
- assign utilities to the identified movements, wherein a utility assigned to a movement reflects a change in reliability resulting from the movement;
- select a utility-maximizing set of movements;
- and
- perform the utility-maximizing set of movements to improve reliability of the storage system.
Dependencies are inferred from the claim text.