Back to results
US 10,310,748 B2Granted
Determining data locality in a distributed system using aggregation of locality summaries
AssigneePivotal Software, Inc.
InventorsHarshad Deshmukh, Adalbert Gerald Soosai Raj, Jignesh M. Patel
Life of this patent
Estimating the term…
Abstract
This specification describes methods, systems, and computer program products for maintaining data representing where each data block of multiple data blocks are stored among multiple computing nodes. Each computing node generates a respective locality summary based on locally stored data blocks, and submits the locality summary to a controlling computing node.
Claims33
A computer-implemented method comprising:
- storing locally in main memory of each computing node of a plurality of computing nodes, by each respective computing node of the plurality of computing nodes, respective data blocks, wherein each data block is a piece of data, wherein each data block is associated with a respective block identifier that is a unique identifier over all data blocks stored on all computing nodes, and each data block is one of a plurality of data blocks;
- determining, by each computing node of the plurality of computing nodes, one or more block identifiers of data blocks stored locally in main memory of the computing node;
- generating, by each computing node of the plurality of computing nodes, a respective locality summary having n positions and n corresponding values, wherein n is an integer less than a total number of the data blocks, wherein the respective locality summary represents which of the plurality of data blocks are stored locally by the computing node, and wherein generating the locality summary includes mapping each of the one or more block identifiers stored by the computing node to a respective position in the locality summary and setting a value at the respective position in the locality summary;
- and
- sending, by each computing node of the plurality of computing nodes to a controller computing node, the respective locality summary generated by the computing node.
2 more elements
A computer-implemented method comprising:
- receiving, by a controller computing node, locality summaries from a plurality of computing nodes, wherein each locality summary identifies which of a plurality of data blocks are stored locally on a respective computing node by mapping each of one or more block identifiers identifying a respective locally stored data block to a respective position in the locality summary and setting a value at the respective position in the locality summary;
- receiving, by the controller computing node, a request to identify which computing node locally stores a particular data block identified by a particular block identifier;
- mapping the particular block identifier to a particular position in received locality summaries;
- determining, by the controller computing node, which of the particular computing nodes provided a locality summary having a value set at the particular position;
- and
- requesting, from each computing node of the particular computing nodes, data indicating whether or not the computing node locally stores the particular data block.
3 more elements
A system comprising:
- one or more computers and one or more storage devices storing instructions that are operable, when executed by the one or more computers, to cause the one or more computers to perform operations comprising:
- storing locally in main memory of each computing node of a plurality of computing nodes, by each respective computing node of the plurality of computing nodes, respective data blocks, wherein each data block is a piece of data, wherein each data block is associated with a respective block identifier that is a unique identifier over all data blocks stored on all computing nodes, and each data block is one of a plurality of data blocks;
- determining, by each computing node of the plurality of computing nodes, one or more block identifiers of data blocks stored locally in main memory of the computing node;
- generating, by each computing node of the plurality of computing nodes, a respective locality summary having n positions and n corresponding values, wherein n is an integer less than a total number of the data blocks, wherein the respective locality summary represents which of the plurality of data blocks are stored locally by the computing node, and wherein generating the locality summary includes mapping each of the one or more block identifiers stored by the computing node to a respective position in the locality summary and setting a value at the respective position in the locality summary;
- and
- sending, by each computing node of the plurality of computing nodes to a controller computing node, the respective locality summary generated by the computing node.
3 more elements
A system comprising:
- one or more computers and one or more storage devices storing instructions that are operable, when executed by the one or more computers, to cause the one or more computers to perform operations comprising:
- receiving, by a controller computing node, locality summaries from a plurality of computing nodes, wherein each locality summary identifies which of a plurality of data blocks are stored locally on a respective computing node by mapping each of one or more block identifiers identifying a respective locally stored data block to a respective position in the locality summary and setting a value at the respective position in the locality summary;
- receiving, by the controller computing node, a request to identify which computing node locally stores a particular data block identified by a particular block identifier;
- mapping, by the controller computing node, the particular block identifier to a particular position in received locality summaries;
- determining, by the controller computing node, which of the particular computing nodes provided a locality summary having a value set at the particular position;
- and
- requesting, by the controller computing node and from each computing node of the particular computing nodes, data indicating whether or not the computing node locally stores the particular data block.
4 more elements
A computer program product, encoded on one or more non-transitory computer storage media, comprising instructions that when executed by one or more computers cause the one or more computers to perform operations comprising:
- storing locally in main memory of each computing node of a plurality of computing nodes, by each respective computing node of the plurality of computing nodes, respective data blocks, wherein each data block is a piece of data, wherein each data block is associated with a respective block identifier that is a unique identifier over all data blocks stored on all computing nodes, and each data block is one of a plurality of data blocks
- determining, by each computing node of the plurality of computing nodes, one or more block identifiers of data blocks stored locally in main memory of the computing node;
- generating, by each computing node of the plurality of computing nodes, a respective locality summary having n positions and n corresponding values, wherein n is an integer less than a total number of the data blocks, wherein the respective locality summary represents which of the plurality of data blocks are stored locally by the computing node, and wherein generating the locality summary includes mapping each of the one or more block identifiers stored by the computing node to a respective position in the locality summary and setting a value at the respective position in the locality summary;
- and
- sending, by each computing node of the plurality of computing nodes to a controller computing node, the respective locality summary generated by the computing node.
2 more elements
A computer program product, encoded on one or more non-transitory computer storage media, comprising instructions that when executed by one or more computers cause the one or more computers to perform operations comprising:
- receiving, by a controller computing node, locality summaries from a plurality of computing nodes, wherein each locality summary identifies which of a plurality of data blocks are stored locally on a respective computing node by mapping each of one or more block identifiers identifying a respective locally stored data block to a respective position in the locality summary and setting a value at the respective position in the locality summary;
- receiving, by the controller computing node, a request to identify which computing node locally stores a particular data block identified by a particular block identifier;
- mapping the particular block identifier to a particular position in received locality summaries;
- determining, by the controller computing node, which of the particular computing nodes provided a locality summary having a value set at the particular position;
- and
- requesting, from each computing node of the particular computing nodes, data indicating whether or not the computing node locally stores the particular data block.
3 more elements
Dependencies are inferred from the claim text.