US 10,372,370 B2Granted

Metadata load distribution management

AssigneeWestern Digital Technologies, Inc.

InventorsFrederik Jacqueline Luc De Schrijver, Lien Joke Boelaert, Joris Custers, Carl Rene D'Halluin

Life of this patent

Estimating the term…

Loading patent…

Abstract

A computer-implemented method for redistributing data between memory clusters in a key value store. The data is redistributed according to a load balancing algorithm. Memory clusters are sorted into lists according to the number of intervals each cluster contains. Migration jobs are created by the load balancing algorithm to push data fragments from a larger cluster to a smaller cluster. Data fragments, or intervals, are selected for migration according to corresponding data fragments on a target cluster or the number of occupying data fragments on a target cluster. The redistribution of data helps avoid fragmentation of key ranges of intervals, decrease the overall number of non-adjacent key ranges, and to conform to the routing table requirements.

Claims20

Dependent claims

A computer-implemented method comprising:

creating a first list of clusters and a second list of clusters based upon a size of each cluster in the first list and the second list, wherein:
each cluster in the first list and each cluster in the second list includes at least one interval of data fragments in ordered key ranges;
the first list includes one or more clusters that store more data than an upper threshold;
and
the second list includes one or more clusters that store less data than a lower threshold;
attempting to identify an adjacent target interval of a target cluster in the second list, wherein the adjacent target interval of the target cluster in the second list includes a first key range adjacent to a second key range of a source interval of a source cluster in the first list;
and
responsive to identifying the adjacent target interval of the target cluster in the second list that is adjacent to the source interval of the source cluster in the first list, moving at least a portion of the source interval from the source cluster in the first list to the adjacent target interval of the target cluster in the second list, wherein the moved portion of the source interval and the adjacent target interval are combined into a single final interval.

5 more elements

A system comprising:

a key value store configured to store a plurality of clusters of data, wherein each cluster of the plurality of clusters of data includes at least one interval of data fragments in ordered key ranges;
and
a storage controller comprising:
a load balancing planner configured to:
create a first list of clusters and a second list of clusters based upon a size of each cluster in the first list and the second list, wherein:
the first list includes one or more clusters that store more data than an upper threshold;
and
the second list includes one or more clusters that store less data than a lower threshold;
attempt to identify an adjacent target interval of a target cluster in the second list, wherein the adjacent target interval of the target cluster in the second list includes a first key range adjacent to a second key range of a source interval of a source cluster in the first list;
and
responsive to identifying the adjacent target interval of the target cluster in the second list that is adjacent to the source interval of the source cluster in the first list, move at least a portion of the source interval from the source cluster in the first list to the adjacent target interval of the target cluster in the second list, wherein the moved portion of the source interval and the adjacent target interval are combined into a single final interval.

8 more elements

A system comprising:

means for creating a first list of clusters and a second list of clusters based upon a size of each interval in the first list and the second list, wherein:
each cluster in the first list and each cluster in the second list includes at least one interval of data fragments in ordered key ranges;
the first list includes one or more clusters that store more data than an upper threshold;
and
the second list includes one or more clusters that store less data than a lower threshold;
means for attempting to identify an adjacent target interval of a target cluster in the second list, wherein the adjacent target interval of the target cluster in the second list includes a first key range adjacent to a second key range of a source interval of a source cluster in the first list;
and
responsive to identifying the adjacent target interval of the target cluster in the second list that is adjacent to the source interval of the source cluster in the first list, means for moving at least a portion of the source interval from the source cluster in the first list to the adjacent target interval of the target cluster in the second list, wherein the moved portion of the source interval and the adjacent target interval are combined into a single final interval.

5 more elements

Dependencies are inferred from the claim text.

Facts

Application: 15/629,497Filed 21 Jun 2017
Published: US 2018/0373456 A127 Dec 2018
Granted: 6 Aug 2019
Term ends: Not estimatedThe source records don’t support an estimate.

Classification6 codes

G06F 3/0647
Horizontal data movement in storage systems, i.e. moving data in between storage devices or systems: migration mechanisms
G06F 3/061
Specifically adapted to achieve a particular effect: improving I/O performance
G06F 3/0611
Improving I/O performance: in relation to response time
G06F 3/0646
Making use of a particular technique: horizontal data movement in storage systems, i.e. moving data in between storage devices or systems

Family

US 2018/0373456 A1Pre-grant publication · published 27 Dec 2018
US 10,372,370 B2This patent

From the US filing history. Foreign family members aren’t listed.

Timeline

Citations

Open elsewhere

Building an agent or pulling many patents? Use the API or MCP server instead of scraping pages. Get an API key