Back to results
US 12,748,536 B2Granted
Optimized selective scanning of overlap-table in storage memories for sequential data
AssigneeSanDisk Technologies LLC
InventorsShay Benisty, Ariel Navon
Life of this patent
Estimating the term…
Abstract
A dual bitmap solution can be beneficial for reducing full cache scans due to data overlap issues that occur using an overlap mechanism. One bitmap is geared towards random read workloads while the other bitmap is geared towards sequential read workloads. When a read command is received, the appropriate bitmap is checked to see if a full scan is necessary. Only if a relevant bit of the bitmap indicates that there is an overlap will the full scan occur. The relevant bit corresponds to the data for a corresponding read command. The bitmaps can be maintained in parallel or the data storage device can switch between maintaining either a bitmap directed to sequential read workloads or a bitmap directed to random read workloads.
Claims18
A data storage device, comprising:
- a memory device;
- and
- a controller coupled to the memory device, wherein the controller is configured to:
- receive a read command;
- detect whether the read command is a sequential read command or a random read command;
- maintain a single cache occupation bitmap that is either a sequential read workload based cache occupation bitmap or a random read workload based cache occupation bitmap, wherein the controller is configured to switch between maintaining the sequential read workload based cache occupation bitmap and the random read workload based cache occupation bitmap based on detecting either a random read workload or a sequential read workload;
- search the single cache occupation bitmap;
- determine whether a full cache scan is necessary, wherein determining whether a full cache scan is necessary comprises determining whether one or more bits of the single cache occupation bitmap has a value of 0 or 1, the one or more bits corresponding to the read command;
- either:
- perform the full cache scan when it is determined to be necessary;
- or
- omit the full cache scan when it is determined to be unnecessary, wherein the full cache scan is omitted when the one or more bits of the single cache occupation bitmap has a value of 0;
- and
- respond to the received read command by delivering data associated with the read command from the memory device to a host device after performing the full cache scan or omitting the full cache scan.
11 more elements
A data storage device, comprising:
- a memory device;
- and
- a controller coupled to the memory device, wherein the controller is configured to:
- maintain a single cache occupation bitmap that is either a sequential read workload based cache occupation bitmap or a random read workload based cache occupation bitmap;
- search the single cache occupation bitmap;
- determine whether a full cache scan is necessary for one or more read commands, including a first, second, and third read command, wherein the determining whether a full cache scan is necessary comprises determining whether one or more bits of the single cache occupation bitmap has a value of 0 or 1, the one or more bits corresponding to the first, second, and third read commands, wherein the full cache scan is omitted when the one or more bits of the single cache occupation bitmap has a value of 0, and wherein the full cache scan is performed when the one or more bits of the single cache occupation bitmap has a value of 1;
- determine that a full cache scan is necessary for the first read command of the one or more read commands;
- determine that a full cache scan is not necessary for the second read command of the one or more read commands;
- upon determining that the full cache scan is not necessary for the second read command, respond to the second read command by delivering data associated with the second read command from the memory device to a host device without performing the full cache scan;
- determine that a full cache scan is necessary for the third read command of the one or more read commands, wherein the first read command, the second read command, and the third read command are received in order;
- perform a full cache scan for the first read command and the third read command, wherein the full cache scan for the first read command occurs after determining that the full cache scan is not necessary for the second read command;
- and
- respond to the first and third read commands by delivering data associated with the first and third read commands from the memory device to the host device after performing the full cache scan.
10 more elements
A data storage device, comprising:
- means to store data;
- and
- a controller coupled to the means to store data, wherein the controller is configured to:
- maintain a first cache occupation bitmap, the first cache occupation bitmap being a sequential read workload based cache occupation bitmap;
- maintain a second cache occupation bitmap for sequential read workloads, the second cache occupation bitmap being a random read workload based cache occupation bitmap;
- receive a read command;
- determine whether a collision is detected for the read command in one or more of the first cache occupation bitmap and the second cache occupation bitmap;
- determine whether to perform a full cache scan, wherein the controller is configured to perform a full cache scan when the collision is detected in both the first cache occupation bitmap and the second cache occupation bitmap, wherein a full cache scan is omitted when no collision is detected;
- either:
- perform the full cache scan when a collision is detected;
- or
- omit the full cache scan when no collision is detected;
- deliver data associated with the read command to a host device after performing the full cache scan or omitting the full cache scan;
- and
- switch between maintaining the first cache occupation bitmap and the second cache occupation bitmap based on detecting either a random read workload or a sequential read workload.
12 more elements
Dependencies are inferred from the claim text.