Load balancing in a data storage service via data structure redistribution

Patent metadata

Field	Value
Publication number	US-11210235-B2
Application number	US-201916594338-A
Country	US
Kind code	B2
Filing date	Oct 7, 2019
Priority date	Oct 7, 2019
Publication date	Dec 28, 2021
Grant date	Dec 28, 2021

Abstract

The technology described herein is directed towards balancing workload between cluster nodes via redistribution of metadata data structures (e.g., memory tables corresponding to directory table partitions). Workload-related information of a node and its partitions' primary memory tables usage is measured, and if sufficiently high, causes a move of a highly-accessed memory table (corresponding to high workload on a first node) from the first node to a second node that has less workload. The second node can contain a backup (e.g., shallow) memory table to the primary node, whereby the move can be a logical move that transforms the backup memory table into a new instance of the primary memory table on the second node. The first node's primary memory table can be deflated into a backup table on the first node that backs up the new instance of the primary table on the second node.

First claim

What is claimed is:

1. A system, comprising:
a processor, and
a memory that stores executable instructions that, when executed by the processor, facilitate performance of operations, the operations comprising:
maintaining a memory table on a first node, the memory table comprising information corresponding to a current state of entity metadata;
maintaining a shallow memory table on a second node, the shallow memory table comprising a backup of the memory table in a reduced size relative to the memory table;
in response to determining that a first load value of a first workload on the first node is greater than a second load value of a second workload on the second node, logically transferring the memory table from the first node to the second node, the logically transferring comprising processing the memory table on the first node into an instance of the shallow memory table independent of transferring the shallow memory table from the second node to the first node, and the logically transferring comprising processing the shallow memory table on the second node into an instance of the memory table independent of transferring the memory table from the first node to the second node.

2. The system of claim 1 , wherein the entity metadata comprises a tree of entity metadata, and wherein the shallow memory table comprises tree identification information that identifies the tree of entity metadata and digests comprising second information corresponding to locations of records in a journal of the records, and wherein the locations correspond to entity updates applicable to the tree of entity metadata.

3. The system of claim 1 , wherein the entity metadata comprises a tree of entity metadata, wherein the shallow memory table comprises tree identification information that identifies the tree of entity metadata and digests comprising second information corresponding to locations of records in a journal of the records, and wherein the locations correspond to entity updates applicable to the tree of entity metadata.

4. The system of claim 3 , wherein the logically transferring comprises:
deflating the memory table on the first node into the instance of the shallow memory table on the first node.

5. The system of claim 1 , wherein the operations further comprise:
determining the first workload based on a size of the memory table on the first node relative to a memory table buffer size of the first workload and a frequency of buffer dumps from a buffer to a nonvolatile storage.

6. The system of claim 1 , wherein the operations further comprise:
determining the first workload based on a size of the memory table and a frequency of dumps of the memory table to a nonvolatile storage.

7. The system of claim 1 , wherein the operations further comprise:
determining the first workload based on load statistics for a central processing unit.

8. The system of claim 1 , wherein the operations further comprise:
determining the first workload based on measured delay information.

9. The system of claim 1 , wherein the operations further comprise:
maintaining a second shallow memory table on a third node, wherein the second shallow memory table backs up the memory table, and wherein the logically transferring the memory table from the first node to the second node further comprises communicating information to the second node that indicates that the second shallow memory table is maintained on the third node.

10. A system, comprising:
a processor, and
a memory that stores executable instructions that, when executed by the processor, facilitate performance of operations, the operations comprising:
maintaining a first instance of a memory table at a first node of a node cluster, the memory table comprising information representing to a current state of entity metadata;
maintaining a shallow memory table on a second node of the node cluster, the shallow memory table comprising a backup of the memory table in a reduced size relative to the memory table;
accessing the first instance of the memory table to serve first requests for entity metadata from the first node;
determining first workload-related information of the first node;
determining second workload-related information of a second node of the node cluster; and
redistributing node cluster workload, based on the first workload-related information and the second workload-related information, comprising maintaining transforming the shallow memory table into a second instance of the memory table on the second node and accessing the second instance of the memory table to serve second requests for entity metadata from the second node, the transforming being performed independently of transferring the first instance of the memory table from the first node to the second node.

11. The system of claim 10 , wherein the determining the first workload-related information of the first node comprises:
determining a first usage value based on a frequency of first memory table dumps on the first node, and wherein the determining the second workload-related information of the second node comprises determining a second usage value based on a frequency of second memory table dumps on the second node.

12. The system of claim 10 , wherein the determining the first workload-related information of the first node comprises:
determining a first usage value based on a first memory size footprint of the memory table.

13. The system of claim 10 , wherein the entity metadata comprises a tree of entity metadata, wherein the shallow memory table comprises tree identification information that identifies the tree of entity metadata and digests comprising second information corresponding to locations of records in a journal of the records, and wherein the locations correspond to entity updates applicable to the tree of entity metadata.

14. The system of claim 10 , wherein the entity metadata comprises a tree of entity metadata, wherein the shallow memory table comprises tree identification information that identifies the tree of entity metadata and digests comprising second information corresponding to locations of records in a journal of the records, and wherein the locations correspond to entity updates applicable to the tree of entity metadata.

15. A non-transitory machine-readable medium, comprising executable instructions that, when executed by a processor of a first node device of a cluster of node devices, facilitate performance of operations, the operations comprising:
maintaining a first instance of a memory table;
accessing the first instance of the memory table to serve first requests for entity metadata from the first node device;
maintaining a first instance of a shallow memory table at a second node device of the cluster of node devices, the first instance of the shallow memory table comprising data that backs up the first instance of the memory table at the first node device in a reduced size relative to the memory table;
processing the first instance of the memory table at the first node device into a second instance of the shallow memory table at the first node device independently of transferring the first instance of the shallow memory table from the second node device to the first node device;
processing the first instance of the shallow memory table at the second node device into a second instance of the memory table at the second node device independently of transferring the first instance of the memory table from the first node device to the second node device; and
accessing the second instance of the memory table to serve second requests for entity metadata from the secon

Assignees

• Emc Ip Holding Co Llc

Inventors

• Danilov Mikhail
• Buinov Konstantin

Classifications

• G06F12/1009

  using page tables, e.g. page table structures · CPC title

• G06F11/2094

  Redundant storage or storage space (G06F11/2056 takes precedence) · CPC title

• G06F11/3433

  for load management (allocation of a server based on load conditions G06F9/505; load rebalancing G06F9/5083; redistributing the load in a network by a load balancer H04L67/1029) · CPC title

• G06F11/3006

  where the computing system is distributed, e.g. networked systems, clusters, multiprocessor systems (multiprogramming arrangements G06F9/46; allocation of resources G06F9/50) · CPC title

• G06F11/1435

  using file system or storage system metadata · CPC title