Managing a distributed database across a plurality of clusters

Patent metadata

Field	Value
Publication number	US-9607071-B2
Application number	US-201414200611-A
Country	US
Kind code	B2
Filing date	Mar 7, 2014
Priority date	Mar 7, 2014
Publication date	Mar 28, 2017
Grant date	Mar 28, 2017

Abstract

A multi-cluster database management system is disclosed that distributes and manages data across a multi-cluster database through the use of cluster partitions. The multi-cluster database management system assigns cluster partitions to clusters of the multi-cluster database. The multi-cluster database management system can evenly or substantially evenly divide the cluster partitions and associated data among the clusters of the multi-cluster database. The multi-cluster database management system can scale in or out by adding or removing clusters from the multi-cluster database when needed or desired. Once a cluster is added or removed, the multi-cluster database management system re-balances the cluster partitions and the associated data across the clusters of the modified multi-cluster database.

First claim

I claim:

1. A method of managing a multi-cluster database comprising:
distributing a plurality of cluster partitions among a plurality of database clusters, each database cluster including a plurality of database nodes;
allocating a node key space among the plurality of database nodes of each database cluster of the plurality of database clusters;
storing data in the database nodes of the corresponding database clusters by identifying an assigned database cluster of the plurality of database clusters based on the plurality of cluster partitions and identifying an assigned node of the assigned database cluster based on the node key space;
modifying the plurality of database clusters by adding or removing one or more database clusters;
re-distributing the plurality of cluster partitions among the modified plurality of database clusters while maintaining the allocation of the node key space among the plurality of database nodes of each database cluster of the plurality of database clusters; and
moving, by at least one processor, at least a portion of the data between the modified plurality of database clusters based on the re-distribution of the plurality of cluster partitions.

2. The method as recited in claim 1 , further comprising assigning key identifiers of a cluster key space to the cluster partitions of the plurality of cluster partitions.

3. The method as recited in claim 2 , further comprising mapping data to cluster partitions of the plurality of cluster partitions and corresponding database clusters by performing steps comprising:
identifying an identifier associated with a piece of data;
determining a key identifier of the cluster key space for the piece of data based on the identifier;
identifying a cluster partition of the plurality of cluster partitions to which the key identifier of the cluster key space is assigned; and
identifying a database cluster of the plurality of database clusters to which the identified cluster partition is assigned.

4. The method as recited in claim 3 , further comprising assigning key identifiers of the node key space to the plurality of database nodes of each database cluster.

5. The method as recited in claim 4 , further comprising mapping the piece of data to a database node of the identified database cluster, wherein mapping the piece of data to the database node of the identified database cluster comprises:
determining a key identifier of the node key space for the piece of data based on the identifier; and
identifying the database node of the identified database cluster to which the key identifier of the node key space is assigned.

6. The method as recited in claim 5 , wherein:
determining the key identifier of the cluster key space for the piece of data based on the identifier comprises performing a hash on the identifier and calculating the key identifier of the cluster key space using a first set of bits of the hash; and
determining the key identifier of the node key space for the piece of data based on the identifier comprises calculating the key identifier of the node key space using a second set of bits of the hash.

7. The method as recited in claim 5 , wherein re-distributing the plurality of cluster partitions among the modified plurality of database clusters comprises re-assigning the identified cluster partition from the identified database cluster to another database cluster of the plurality of database clusters.

8. The method as recited in claim 7 , wherein moving at least a portion of the data between the modified plurality of database clusters based on the re-distribution of the plurality of cluster partitions comprises moving the piece of data from the identified database node of the identified database cluster to another database node of the another database cluster.

9. The method as recited in claim 4 , wherein assigning key identifiers of the node key space to the plurality of database nodes of each database cluster comprises indirectly assigning the key identifiers of the node key space to the plurality of database nodes.

10. A system comprising:
at least one processor; and
at least one non-transitory computer readable storage medium storing instructions thereon that, when executed by the at least one processor, cause the system to:
distribute a plurality of cluster partitions among a plurality of database clusters, each database cluster including a plurality of database nodes;
allocate a node key space among the plurality of database nodes of each database cluster of the plurality of database clusters;
store data in the database nodes of the corresponding database clusters by identifying an assigned database cluster of the plurality of database clusters based on the plurality of cluster partitions and identifying an assigned node of the assigned database cluster based on the node key space;
modify the plurality of database clusters by adding or removing one or more database clusters;
re-distribute the plurality of cluster partitions among the modified plurality of database clusters while maintaining the allocation of the node key space among the plurality of database nodes of each database cluster of the plurality of database clusters; and
balance the data across the modified plurality of database clusters based on the re-distribution of the plurality of cluster partitions.

11. The system as recited in claim 10 , wherein the instructions, when executed by the at least one processor, cause the system to balance the data across the modified plurality of database clusters by moving at least a portion of the data between the database clusters of the modified plurality of database clusters based on the re-distribution of the plurality of cluster partitions.

12. The system as recited in claim 10 , wherein the instructions, when executed by the at least one processor, cause the system to map the data to cluster partitions of the plurality of cluster partitions and corresponding database clusters by:
identifying an identifier associated with a piece of data;
determining a key identifier of a cluster key space for the piece of data based on the identifier;
identifying a cluster partition of the plurality of cluster partitions to which the key identifier of the cluster key space is assigned;
identifying a database cluster of the plurality of database clusters to which the identified cluster partition is assigned;
determining a key identifier of the node key space for the piece of data based on the identifier; and
identifying a database node of the identified database cluster to which the key identifier of the node key space is assigned.

13. The system as recited in claim 12 , wherein the instructions, when executed by the at least one processor, further cause the system to:
determine the key identifier of the cluster key space for the piece of data based on the identifier by performing a hash on the identifier and calculating the key identifier of the cluster key space using a first set of bits of the hash; and
determine the key identifier of the node key space for the piece of data based on the identifier by calculating the key identifier of the node key space using a second set of bits of the hash.

14. A non-transitory computer readable medium storing instructions thereon that, when executed by at least one processor, cause a computer system to:
distribute a plurality of cluster partitions among a plurality of database clusters, each database cluster including a plurality of database nodes;
allocate a node key space among the plurality of database nodes of each database cluster of the plurality of database clusters;
store data in the databa

Assignees

• Adobe Systems Inc

Inventors

• Stringham Russell R

Classifications

• G06F16/9535

  Search customisation based on user profiles and personalisation · CPC title

• G06F16/2255

  Hash tables · CPC title

• G06F16/955

  using information identifiers, e.g. uniform resource locators [URL] · CPC title

• G06F16/35

  Clustering; Classification · CPC title

• G06F16/278 Primary

  Data partitioning, e.g. horizontal or vertical partitioning · CPC title