Back to results
US 11,144,224 B2Granted
Locality-aware, memory-efficient, time-efficient hot data identification using count-min-sketch for flash or streaming applications
AssigneeDell Products L.P.
InventorSweetesh Singh
Life of this patent
Estimating the term…
Abstract
Extents of data are promoted or demoted between hierarchical storage tiers based on temporal locality of access captured with a primary count-min-sketch based on monitored input-output commands. Extents may also be promoted based on spatial locality of access captured with a secondary count-min-sketch based on the monitored input-output commands. The count-min-sketches may be implemented in a tiering engine of a storage array or in the flash translation layers of solid-state drives. The flash translation layers may generate tiering hints that are provided to a tiering engine.
Claims11
An apparatus comprising:
- a plurality of interconnected computing nodes, each of the computing nodes comprising at least one processor and non-transitory memory;
- a plurality of data storage drives on which extents of data are stored, each data storage drive connected to at least one of the computing nodes, the data storage drives being organized into a plurality of hierarchical tiers differentiated based on performance;
- and
- a tiering engine that:
- prompts selected ones of the extents of data to be promoted or demoted between the tiers based on temporal locality of access captured with a primary count-min-sketch based on monitored input-output commands, wherein the primary count-min-sketch maintains an access count for each accessed logical block address;
- and
- prompts selected ones of the extents to be promoted based on spatial locality of access captured with a secondary count-min-sketch based on the monitored input-output commands, wherein the secondary count-min-sketch maintains an access count for each of a plurality of logical block addresses within a predetermined spatial proximity to an accessed logical block address.
4 more elements
A method comprising:
- in a data storage network comprising a plurality of interconnected computing nodes, each of the computing nodes comprising at least one processor and non-transitory memory, and a plurality of data storage drives on which extents of data are stored, each data storage drive connected to at least one of the computing nodes, the data storage drives being organized into a plurality of hierarchical tiers differentiated based on performance:
- monitoring input-output commands;
- promoting some of the extents of data between the tiers based on temporal locality of access captured with a primary count-min-sketch based on the monitored input-output commands;
- the primary count-min-sketch maintaining an access count for each accessed logical block address;
- promoting selected ones of the extents based on spatial locality of access captured with a secondary count-min-sketch based on the monitored input-output commands, the secondary count-min-sketch maintaining an access count for each of a plurality of logical block addresses within a predetermined spatial proximity to accessed logical block addresses;
- and
- for each access to one of the accessed logical block addresses, incrementing the access count of the one of the accessed logical block addresses of the primary count-min-sketch at a different rate than the access count of the one of the accessed logical block addresses of the secondary count-min-sketch.
4 more elements
Dependencies are inferred from the claim text.