Replicated database distribution for workload balancing after cluster reconfiguration

Patent metadata

Field	Value
Publication number	US-10102086-B2
Application number	US-201414577629-A
Country	US
Kind code	B2
Filing date	Dec 19, 2014
Priority date	Dec 19, 2014
Publication date	Oct 16, 2018
Grant date	Oct 16, 2018

Abstract

A computer-implemented method for distributing a plurality of data partitions among a cluster of computer nodes includes dividing a database into a plurality of primary partitions, storing the primary partitions on a plurality of nodes associated with a computer network, duplicating the primary partitions to create a plurality of secondary partitions and storing the secondary partitions on the nodes, wherein the primary and secondary partitions are substantially evenly distributed among the nodes, each secondary partition is stored on a different node than its corresponding primary partition, diversity exists with respect to each secondary partition and the node where it is stored, the primary partitions are available to serve a system workload, and one or more secondary partitions corresponding to one or more primary partitions of a failed node are available to be upgraded to primary status to maintain workload balancing and data availability after one of the computer nodes fails.

First claim

What is claimed is:

1. A method for distributing a plurality of data partitions among a plurality of computer nodes, comprising:
dividing a database into a plurality of primary partitions;
storing each of the primary partitions on a respective node of a plurality of nodes so that the primary partitions are distributed substantially evenly among the nodes and wherein the primary partitions are available to serve a system workload;
duplicating each of the primary partitions to create corresponding respective secondary partitions;
for each of the secondary partitions:
identifying a node of the plurality of nodes that does not store the primary partition corresponding to the secondary partition; and
storing the secondary partition on the identified node;

after failure or dissociation of one node of the plurality of nodes, upgrading one or more secondary partitions corresponding to one or more primary partitions of the failed or dissociated node to primary status; and
redistributing one or more secondary partitions corresponding to the one or more primary partitions of the failed or dissociated node by performing operations including:
duplicating the one or more upgraded secondary partitions to create one or more corresponding further secondary partitions; and
for each of the one or more corresponding further secondary partitions, identifying a further node of the plurality of nodes that does not store the upgraded secondary partition corresponding to the further secondary partition and wherein storage of the corresponding further secondary partition on the further node would not result in two or more of the secondary partitions, including the one or more further secondary partitions, stored on the further node being stored together as primary partitions on a common node; and
storing the corresponding further secondary partition on the identified further node.

2. The method of claim 1 , wherein:
the storing of the primary partitions on the nodes uses a round-robin algorithm; and
the identifying of the node of the plurality of nodes uses a modified round-robin algorithm that selects, as the identified node, a first node provided by the round-robin algorithm for which storage of the secondary partition on the identified node would not result the secondary partition and the primary partition corresponding to the secondary partition being stored together on the identified node.

3. The method of claim 1 , further comprising:
determining a number of transfers of data partitions to and from a first node during the redistribution each of the one or more secondary partitions; and
determining that the number of transfers does not exceed a threshold and, based thereon, storing the corresponding further secondary partition on the first node, wherein the storing is part of the redistribution after the failed or disassociated node has failed or has become disassociated from a cluster.

4. The method of claim 3 , further comprising upgrading a second secondary partition on a second node to be a primary partition on the second node, wherein the second node is a surviving node that remains available after the failed or disassociated node has failed or has become disassociated from the cluster.

5. The method of claim 3 , wherein storing the corresponding further secondary partition on the first node further comprises determining that storage of the corresponding further secondary partition on a second node would result in two or more of the secondary partitions of the second node being stored together as primary partitions on a common node and, based thereon, storing the corresponding further secondary partition on the first node.

6. The method of claim 1 , wherein identifying the node of the plurality of nodes that does not store the primary partition corresponding to the secondary partition further includes determining that storage of the secondary partition on the identified node would not result in two or more of the secondary partitions stored on the identified node being stored together as primary partitions on another node.

7. A computer-readable medium storing instructions for distributing a plurality of data partitions among a plurality of computer nodes, that when executed by one or more processors cause the processors to perform operations comprising:
dividing a database into a plurality of primary partitions;
storing each of the primary partitions on a respective node of a plurality of nodes so that the primary partitions are distributed substantially evenly among the nodes and wherein the primary partitions are available to serve a system workload;
duplicating each of the primary partitions to create corresponding respective secondary partitions;
for each of the secondary partitions:
identifying a node of the plurality of nodes that does not store the primary partition corresponding to the secondary partition; and
storing the secondary partitions on the identified node;

after failure or disassociation of a node of the plurality of nodes, upgrading one or more secondary partitions corresponding to one or more primary partitions of the failed or disassociated node to primary status; and
redistributing secondary partitions corresponding to the one or more primary partitions of the failed or disassociated node by causing the processors to perform operations including:
duplicating the one or more upgraded secondary partitions to create one or more corresponding further secondary partitions; and
for each of the one or more corresponding further secondary partitions, identifying a further node of the plurality of nodes that does not store the upgraded secondary partition corresponding to the further secondary partition and wherein storage of the corresponding further secondary partition on the further node would not result in two or more of the secondary partitions, including the one or more further secondary partitions, stored on the further node being stored together as primary partitions on a common node; and
storing the corresponding further secondary partition on the identified further node.

8. The computer-readable medium of claim 7 , wherein:
the storing of the primary partitions on the nodes uses a round-robin algorithm; and
the identifying of the node of the plurality of nodes uses a modified round-robin algorithm that selects, as the identified node, a first node provided by the round-robin algorithm for which storage of the secondary partition on the identified node would not result in the secondary partition and the primary partition corresponding to the secondary partition being stored together on the identified node.

9. The computer-readable medium of claim 7 , wherein the operations further comprise:
determining a number of transfers of data partitions to and from a first node during the redistribution of the secondary partitions; and
determining that the number of transfers does not exceed a threshold and, based thereon, storing the corresponding further secondary partition on the first node, wherein the storing is part of the redistribution after the failed or disassociated node has failed or has become disassociated from a cluster.

10. The computer-readable medium of claim 7 , wherein the operations further comprise upgrading a second secondary partition on a second node to be a primary partition on the second node, wherein the second node is a surviving node that remains available after the failed or disassociated node has failed or has become disassociated from a cluster.

11. The computer-readable medium of claim 9 , wherein the operations further comprise:
determining that storage of the corresponding further secondary partition on a second node would resul

Assignees

• Futurewei Technologies Inc

Inventors

• Cai Le

Classifications

• 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

• G06F11/2048

  where the redundant components share neither address space nor persistent storage · CPC title

• G06F17/30584

  Physics · mapped topic

• H04L67/1034

  Reaction to server failures by a load balancer · CPC title

• G06F11/2097

  maintaining the standby controller/processing unit updated (initialisation or re-synchronisation thereof G06F11/1658 and subgroups) · CPC title