# US 11,442,632 B2 · Rebalancing of user accounts among partitions of a storage service

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 11,442,632 B2
- Document ID: US11442632B2
- Status: Granted
- Kind: B2
- Application number: 16/137,372
- Filed: 2018-09-20
- Published: 2019-10-03
- Granted: 2022-09-13
- Earliest claimed: 2018-04-02
- Assignees: Apple Inc.
- Applicants: Apple Inc.
- Inventors: Nicolas A. Favre-Felix; Alexander Shraer; Ori Herrnstadt; Nathan L. Williams
- Web page: https://patentgrep.com/patent/US11442632B2

## CPC

- G06F 3/0605: {by facilitating the interaction with a user or administrator}
- G06F 3/0617: {in relation to availability}
- G06F 3/0631: {by allocating resources to storage systems}
- G06F 3/0659: {Command handling arrangements, e.g. command buffers, queues, command scheduling}
- G06F 3/067: {Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]}
- G06F 3/0673: {Single storage device}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

This application relates to load balancing for a number of partitions of a network-based storage service. Each partition includes a number of server devices and/or network devices located in a data center and configured to provide access to storage resources hosted within the data center. User accounts are assigned to a particular partition such that requests related to a particular user account are routed to that partition. Periodically, a load balancing algorithm is executed to re-assign user accounts to different partitions to rebalance resource consumption across the different partitions. The load balancing algorithm can balance resource consumption for any number of resource types by generating a vector of resource utilization parameters for each user account, sorting the plurality of user accounts into clusters based on the vectors, and mapping at least some user accounts to different partitions.

## Claims

### Claim 1

A method for balancing resource utilization among a plurality of partitions of a storage service, the method comprising:
establishing a plurality of user account clusters;
for each user account of a plurality of user accounts associated with the storage service:
generating a respective vector for the user account by populating the respective vector with resource utilization parameters for the user account,
wherein:
the respective vector includes, for each tenant of a plurality of tenants associated with the storage service, a respective dimension that stores at least one value that is representative of interactions that take place between the user account and the tenant, and
each tenant of the plurality of tenants is a respective service that is implemented within the storage service;
sorting, based on the respective vector, the user account into a particular user account cluster of the plurality of user account clusters; and
for each user account cluster of the plurality of user account clusters:
mapping each user account in the user account cluster into a respective one of the partitions of the plurality of partitions of the storage service.

### Claim 2 (depends on 1)

The method of claim 1, wherein generating the respective vector for a given user account of the plurality of user accounts further comprises, prior to populating the respective vector with the resource utilization parameters for the give n user account:
identifying the resource utilization parameters for the given user account.

### Claim 3 (depends on 1)

The method of claim 1, wherein the sorting comprises:
sorting each user account of the plurality of user accounts into a respective n-dimensional bucket based on the resource utilization parameters in the respective vector.

### Claim 4 (depends on 3)

The method of claim 3, wherein the n-dimensional buckets are at least two-dimensional.

### Claim 5 (depends on 3)

The method of claim 3, wherein mapping the user accounts comprises, for each n-dimensional bucket:
calculating a number of user accounts associated with each partition in the plurality of partitions included in the n-dimensional bucket;
calculating a metric value for each partition in the plurality of partitions included in the n-dimensional bucket; and
mapping at least one user account in a partition having a metric value greater than a threshold value to a different partition having a metric value less than the threshold value.

### Claim 6 (depends on 5)

The method of claim 5, wherein:
the metric value comprises a ratio of the number of user accounts included in the partition to an average number of user accounts per partition for the n-dimensional bucket, and
the threshold value is 1.

### Claim 7 (depends on 3)

The method of claim 3, wherein sorting user accounts into the n-dimensional buckets based on the resource utilization parameters comprises:
for each resource utilization parameter having a range of values between a minimum value and a maximum value, subdividing the range of values into a number of non-overlapping subranges such that, for each subrange, a number of user accounts included in a set of user accounts that correspond with the subrange is less than a first threshold value and an aggregate resource consumption of the set of user accounts that correspond with the subrange is less than a second threshold value;
associating each n-dimensional bucket with a particular subrange for each resource utilization parameter; and
sorting the user accounts into the n-dimensional buckets based on values for the resource utilization parameters corresponding to each user account.

### Claim 8 (depends on 2)

The method of claim 2, wherein the resource utilization parameters comprise one or more of:
a storage resource utilization parameter;
a read I/O utilization parameter; and
a write I/O utilization parameter.

### Claim 9 (depends on 2)

The method of claim 2, wherein determining resource utilization parameters for the user account comprises:
determining a storage resource utilization parameter for each tenant of the plurality of tenants associated with the user account.

### Claim 10 (depends on 9)

The method of claim 9, wherein a value for each storage resource utilization parameter in n resource utilization parameters for a particular user account corresponds with an amount of data stored in a particular partition of the storage service for a particular tenant in n tenants.

### Claim 11

At least one non-transitory computer-readable medium storing computer instructions that, when executed by at least one processor included in a computing device, cause the computing device to balance resource utilization among a plurality of partitions of a storage service, by carrying out steps that include:
establishing a plurality of user account clusters;
for each user account of a plurality of user accounts associated with the storage service:
generating a respective vector for the user account by populating the respective vector with resource utilization parameters for the user account,
wherein:
the respective vector includes, for each tenant of a plurality of tenants associated with the storage service, a respective dimension that stores at least one value that is representative of interactions that take place between the user account and the tenant, and
each tenant of the plurality of tenants is a respective service that is implemented within the storage service;
sorting, based on the respective vector, the user account into a particular user account cluster of the plurality of user account clusters; and
for each user account cluster of the plurality of user account clusters:
mapping each user account in the user account cluster into a respective one of the partitions of the plurality of partitions of the storage service.

### Claim 12 (depends on 11)

The at least one non-transitory computer-readable medium of claim 11, wherein generating the respective vector for a given user account of the plurality of user accounts further comprises, prior to populating the respective vector with the resource utilization parameters for the given user account:
identifying the resource utilization parameters for the given user account.

### Claim 13 (depends on 11)

The at least one non-transitory computer-readable medium of claim 11, wherein the sorting comprises:
sorting each user account of the plurality of user accounts into a respective n-dimensional bucket based on the resource utilization parameters in the respective vector.

### Claim 14

A computing device configured to balance resource utilization among a plurality of partitions of a storage service, the computing device comprising:
at least one processor; and
at least one memory storing instructions that, when executed by the at least one processor, cause the computing device to carry out steps that include:
establishing a plurality of user account clusters;
for each user account of a plurality of user accounts associated with the storage service:
generating a respective vector for the user account by populating the respective vector with resource utilization parameters for the user account, wherein:
the respective vector includes, for each tenant of a plurality of tenants associated with the storage service, a respective dimension that stores at least one value that is representative of interactions that take place between the user account and the tenant, and
each tenant of the plurality of tenants is a respective service that is implemented within the storage service;
sorting, based on the respective vector, the user account into a particular user account cluster of the plurality of user account clusters; and
for each user account cluster of the plurality of user account clusters:
mapping each user account in the user account cluster into a respective one of the partitions of the plurality of partitions of the storage service.

### Claim 15 (depends on 14)

The computing device of claim 14, wherein generating the respective vector for a given user account of the plurality of user accounts further comprises, prior to populating the respective vector with the resource utilization parameters for the given user account:
identifying the resource utilization parameters for the given user account.

### Claim 16 (depends on 14)

The computing device of claim 14, wherein the sorting comprises:
sorting each user account of the plurality of user accounts into a respective n-dimensional bucket based on the resource utilization parameters in the respective vector.

### Claim 17 (depends on 16)

The computing device of claim 16, wherein the n-dimensional buckets are at least two-dimensional.

### Claim 18 (depends on 16)

The computing device of claim 16, wherein mapping the user accounts comprises, for each n-dimensional bucket:
calculating a number of user accounts associated with each partition in the plurality of partitions included in the n-dimensional bucket;
calculating a metric value for each partition in the plurality of partitions included in the n-dimensional bucket; and
mapping at least one user account in a partition having a metric value greater than a threshold value to a different partition having a metric value less than the threshold value.

### Claim 19 (depends on 18)

The computing device of claim 18, wherein:
the metric value comprises a ratio of the number of user accounts included in the partition to an average number of user accounts per partition for the n-dimensional bucket, and
the threshold value is 1.

### Claim 20 (depends on 16)

The computing device of claim 16, wherein sorting user accounts into the n-dimensional buckets based on the resource utilization parameters comprises:
for each resource utilization parameter having a range of values between a minimum value and a maximum value, subdividing the range of values into a number of non-overlapping subranges such that, for each subrange, a number of user accounts included in a set of user accounts that correspond with the subrange is less than a first threshold value and an aggregate resource consumption of the set of user accounts that correspond with the subrange is less than a second threshold value;
associating each n-dimensional bucket with a particular subrange for each resource utilization parameter; and
sorting the user accounts into the n-dimensional buckets based on values for the resource utilization parameters corresponding to each user account.