Back to results
US 12,688,156 B2Granted
Garbage collection of redundant partitions
AssigneeInternational Business Machines Corporation
InventorsSrikumar Venugopal, Stefano Braghin
Life of this patent
Estimating the term…
Abstract
A method, system, and computer program product for garbage collection of redundant partitions in distributed data management systems are provided. The method stores data across a set of nodes with the data being stored using one or more partitions and the data and the one or more partitions are replicated across the set of nodes. A first partition is determined to be stale at a first node of the set of nodes. The first partition is marked for deletion locally at the first node. A set of deletion votes are determined for the first partition with each node being associated with a deletion vote. The method determines a deletion decision for the first partition on the first node based on the set of deletion votes.
Claims15
A computer-implemented method for garbage collection of redundant partitions in distributed data management systems, the method comprising:
- storing data across a set of nodes in the distributed data management systems, the data being stored using one or more partitions and the data and the one or more partitions being replicated across the set of nodes;
- determining, at a first node of the set of nodes, a first partition is stale by
- identifying a set of access metrics for the first partition, wherein the first partition includes data stored at the first node of the set of nodes,
- determining a freshness value for the first partition based on the set of access metrics, wherein the freshness value is determined by computing a function of usage statistics of the first partition, conditions of the first partition, or attributes of the first partition, wherein the freshness value selected from a group consisting of an exponential decay of access counts, access counts over time, access counts since a last access of the first partition, access counts of the first partition, and replicas of the first partition on other nodes, and
- comparing the freshness value for the first partition with a freshness threshold, wherein the freshness threshold is dynamically generated based on the usage statistics;
- marking the first partition for deletion, the first partition being marked for deletion locally at the first node;
- determining a set of deletion votes for the first partition, each node of the set of nodes being associated with a deletion vote of the set of deletion votes,
- wherein the determining the set of deletion votes further comprises:
- transmitting a deletion indicator from the first node to a remaining subset of nodes of the set of nodes;
- and
- receiving the set of deletion votes from the remaining subset of nodes, each node of the remaining subset of nodes comparing the freshness value for the first partition to a freshness value for a local partition associated with the first partition;
- and
- determining a deletion decision for the first partition on the first node based on the set of deletion votes.
10 more elements
A system for garbage collection of redundant partitions in distributed data management systems, the system comprising:
- one or more processors;
- and
- a computer-readable storage medium, coupled to the one or more processors, storing program instructions that, when executed by the one or more processors, cause the one or more processors to perform operations comprising:
- storing data across a set of nodes in the distributed data management systems, the data being stored using one or more partitions and the data and the one or more partitions being replicated across the set of nodes;
- determining, at a first node of the set of nodes, a first partition is stale by
- identifying a set of access metrics for the first partition, wherein the first partition includes data stored at the first node of the set of nodes,
- determining a freshness value for the first partition based on the set of access metrics, wherein the freshness value is determined by computing a function of usage statistics of the first partition, conditions of the first partition, or attributes of the first partition, wherein the freshness value is selected from a group consisting of an exponential decay of access counts, access counts over time, access counts since a last access of the first partition, access counts of the first partition, and replicas of the first partition on other nodes, and
- comparing the freshness value for the first partition with a freshness threshold, wherein the freshness threshold is dynamically generated based on the usage statistics;
- marking the first partition for deletion, the first partition being marked for deletion locally at the first node;
- determining a set of deletion votes for the first partition, each node of the set of nodes being associated with a deletion vote of the set of deletion votes,
- wherein the determining the set of deletion votes further comprises:
- transmitting a deletion indicator from the first node to a remaining subset of nodes of the set of nodes;
- and
- receiving the set of deletion votes from the remaining subset of nodes, each node of the remaining subset of nodes comparing the freshness value for the first partition to a freshness value for a local partition associated with the first partition;
- and
- determining a deletion decision for the first partition on the first node based on the set of deletion votes.
13 more elements
A computer program product for garbage collection of redundant partitions in distributed data management systems comprising a computer readable storage medium having program instructions embodied therewith, the program instructions being executable by one or more processors to cause the one or more processors to perform operations comprising:
- storing data across a set of nodes in the distributed data management systems, the data being stored using one or more partitions and the data and the one or more partitions being replicated across the set of nodes;
- determining, at a first node of the set of nodes, a first partition is stale by
- identifying a set of access metrics for the first partition, wherein the first partition includes data stored at the first node of the set of nodes,
- determining a freshness value for the first partition based on the set of access metrics, wherein the freshness value is determined by computing a function of usage statistics of the first partition, conditions of the first partition, or attributes of the first partition, wherein the freshness value is selected from a group consisting of an exponential decay of access counts, access counts over time, access counts since a last access of the first partition, access counts of the first partition, and replicas of the first partition on other nodes, and
- comparing the freshness value for the first partition with a freshness threshold, wherein the freshness threshold is dynamically generated based on the usage statistics;
- marking the first partition for deletion, the first partition being marked for deletion locally at the first node;
- determining a set of deletion votes for the first partition, each node of the set of nodes being associated with a deletion vote of the set of deletion votes,
- wherein the determining the set of deletion votes further comprises:
- transmitting a deletion indicator from the first node to a remaining subset of nodes of the set of nodes;
- and
- receiving the set of deletion votes from the remaining subset of nodes, each node of the remaining subset of nodes comparing the freshness value for the first partition to a freshness value for a local partition associated with the first partition;
- and
- determining a deletion decision for the first partition on the first node based on the set of deletion votes.
10 more elements
Dependencies are inferred from the claim text.