Distributed data management system

• US 9,122,713 B2
• Filed: 08/06/2013
• Issued: 09/01/2015
• Est. Priority Date: 07/28/2005
• Status: Active Grant

• Current Assignee: Pivotal Software, Inc. (Broadcom, Inc.)
• Original Assignee: Pivotal Software, Inc. (Broadcom, Inc.)
• Inventors: Okamoto, Russell
• Primary Examiner(s): TRUONG, CAM Y T
• Application Number:
  US13/959,748
• Publication Number:
  US 20140195566A1
• Time in Patent Office: 756 Days
• Field of Search: 707/626, 707/704, 718/105
• US Class Current: 1/1
• CPC Class Codes: G06F 16/00 Information retrieval; Database structures therefor; File system structures therefor
• CPC Class Codes: G06F 16/214 Database migration support

Abstract

A distributed data management system has multiple virtual machine nodes operating on multiple computers that are in communication with each other over a computer network. Each virtual machine node includes at least one data store or “bucket” for receiving data. A digital hash map data structure is stored in a computer readable medium of at least one of the multiple computers to configure the multiple virtual machine nodes and buckets to provide concurrent, non-blocking access to data in the buckets, the digital hash map data structure including a mapping between the virtual machine nodes and the buckets. The distributed data management system employing dynamic scalability in which one or more buckets from a virtual machine node reaching a memory capacity threshold are transferred to another virtual machine node that is below its memory capacity threshold.

Claims

1. A method comprising:

storing, in a global data structure in at least one database management node of a plurality database management nodes of a distributed data management system, data entries mapping each logical data store of a plurality of logical data stores to a corresponding one of the database management nodes in which the logical data store is stored;

storing a data object in a first logical data store of the logical data stores, wherein the first logical data store corresponds to a key value of the data object, and wherein the first logical data store corresponds to a first database management node;

and upon adding a new database management node to the distributed data management system, performing rebalancing actions, the rebalancing actions comprising;

determining that the first data management node is a fullest node storing most data among the plurality database management nodes;

in response to the determining, sending requests from the first database management node to one or more of the database management nodes and the new database management node to determine whether anyone of the database management nodes and the new database management node has memory to accommodate the first logical data store;

receiving a reply by the first database management node and from the new database management node, the reply affirming that the new database management node has memory to accommodate the first logical data store;

migrating the first logical data store from the first database management node to the new database management node to rebalance memory consumption among the new database management node and the database management nodes; and

upon completion of the migrating, updating the data entries in the global data structure to map the first logical database to the new database management node, wherein, during performance of the rebalance actions, the data management system allows concurrent and non-blocking access to data objects stored in other logical data stores that are not involved in the migration and blocks access to the first logical data store.

2. The method of claim 1, wherein the global data structure is divided into partitions that are each stored in a different database management node.

3. The method of claim 1, further comprising hashing a received key value identifying the data object, wherein a resulting hash value identifies the logical data store in which the data object is stored.

4. The method of claim 1, wherein the first logical data store stores a data object and corresponds to a key value of the data object.

5. The method of claim 4, the updating the data entries comprising updating the data entries by the new database management node upon completion of the migrating.

6. The method of claim 1, the updating the data entries comprising updating the data entries by the first database management node upon completion of the migrating, including removing a mapping between the first logical data store and the first database management node.

7. The method of claim 6, further comprising, upon completion of the migrating, forwarding requests to the first data store from the first database management node to the new database management node.

8. A non-transitory computer-readable storage medium storing instructions that, when executed, cause a plurality of computers in communication with each other over a computer network to perform operations comprising:

storing, in a global data structure in at least one database management node of a plurality database management nodes of a distributed data management system, data entries mapping each logical data store of plurality of logical data store to a corresponding one of the database management nodes in which the logical data store is stored;

storing a data object in a first logical data store of the logical data stores, wherein the first logical data store corresponds to a key value of the data object, and wherein the first logical data store corresponds to a first database management node;

and upon adding a new database management node to the distributed data management system, performing rebalancing actions, the rebalancing actions comprising;

determining that the first data management node is a fullest node storing most data among the plurality database management nodes;

in response to the determining, sending requests from the first database management node to one or more of the database management nodes and the new database management node to determine whether anyone of the database management nodes and the new database management node has memory to accommodate the first logical data store;

receiving a reply by the first database management node and from the new database management node, the reply affirming that the new database management node has memory to accommodate the first logical data store;

migrating the first logical data store from the first database management node to the new database management node to rebalance memory consumption among the new database management node and the database management nodes; and

upon completion of the migrating, updating the data entries in the global data structure to map the first logical database to the new database management node, wherein, during performance of the rebalance actions, the data management system allows concurrent and non-blocking access to data objects stored in other logical data stores that are not involved in the migration and blocks access to the first logical data store.

9. The non-transitory computer-readable storage medium of claim 8, wherein the global data structure is configured to provide an identity of a database management node storing a logical data store in which the data object is stored upon receipt of a key value identifying a data object.

10. The non-transitory computer-readable storage medium of claim 8, the operations comprising hashing a received key value identifying a data object, wherein a resulting hash value identifies a logical data store in which the data object is stored.

11. The non-transitory computer-readable storage medium of claim 8, wherein the at least one of the database management nodes maintaining the global data structure further maintains a cache comprising recently accessed data objects.

12. The non-transitory computer-readable storage medium of claim 11, the operations further comprising, upon receiving a request for a value of a data object that is stored in the cache, transmitting the value to a database management node that stores a logical data store corresponding to the data object in order to confirm that the value of the data object stored in the cache is current.

13. The non-transitory computer-readable storage medium of claim 8, the updating the data entries comprising:

updating the data entries by the new database management node upon completion of the migrating; and

updating the data entries by the first database management node upon completion of the migrating, including removing a mapping between the first logical data store and the first database management node.

14. The non-transitory computer-readable storage medium of claim 8, wherein the first logical data store stores a data object and corresponds to a key value of the data object.

15. A distributed data management system comprising:

a plurality of computers, each computer including a memory and in communication with each other over a computer network; and

a non-transitory computer-readable storage medium storing instructions that, when executed, cause the computers to perform operations comprising;

storing, in a global data structure in at least one database management node of a plurality database management nodes of a distributed data management system, data entries mapping each logical data store of a plurality of logical data stores to a corresponding one of the database management nodes in which the logical data store is stored;

storing a data object in a first logical data store of the logical data stores, wherein the first logical data store corresponds to a key value of the data object, and wherein the first logical data store corresponds to a first database management node;

and upon adding a new database management node to the distributed data management system, performing rebalancing actions, the rebalancing actions comprising;

determining that the first data management node is a fullest node storing most data among the plurality database management nodes;

in response to the determining, sending requests from the first database management node to one or more of the database management nodes and the new database management node to determine whether anyone of the database management nodes and the new database management node has memory to accommodate the first logical data store;

receiving a reply by the first database management node and from the new database management node, the reply affirming that the new database management node has memory to accommodate the first logical data store;

migrating the first logical data store from the first database management node to the new database management node to rebalance memory consumption among the new database management node and the database management nodes; and

upon completion of the migrating, updating the data entries in the global data structure to map the first logical database to the new database management node, wherein, during performance of the rebalance actions, the data management system allows concurrent and non-blocking access to data objects stored in other logical data stores that are not involved in the migration and blocks access to the first logical data store.

16. The distributed data management system of claim 15, wherein the global data structure is divided into partitions that are each stored in a different database management node.

17. The distributed data management system of claim 15, the operations comprising hashing a received key value identifying the data object, wherein a resulting hash value identifies the first logical data store in which the data object is stored.

18. The distributed data management system of claim 15, wherein the at least one of the database management nodes storing the global data structure further maintains a cache comprising recently accessed data objects.

19. The distributed data management system of claim 18, the operations comprising, upon receiving a request for a value of a data object that is stored in the cache, transmitting the value to a database management node that stores a logical data store corresponding to the data object in order to confirm that the value of the data object stored in the cache is current.

20. The distributed data management system of claim 15, wherein the first logical data store stores a data object and corresponds to a key value of the data object.