Granted Patent B2

US 12,461,853 · App. 18/365,033 · Granted Nov 4, 2025

Inventors: Pavan Gururaj (Bangalore, IN); Dinesh Babu (Bangalore, IN); Sridhar Sabesan (Bangalore, IN)

Assignee: Western Digital Technologies, Inc.

G06F12/0253G06F12/0891

Abstract

Claims (98)

1 . A data storage device, comprising:

a non-volatile storage medium;

a host interface configured to receive host storage commands from a plurality of host systems; and

a controller configured to:

store, to the non-volatile storage medium, host data units as values indexed by a corresponding key in key-value pairs;

receive, from a first host system of the plurality of host systems, a delete command for a target key-value pair, wherein the target key-value pair comprises a first host identifier for a storing host system that previously stored the target key-value pair;

move, responsive to the delete command, the corresponding key for the target key-value pair to a deleted data structure having a delete order;

add, responsive to the first host system being different than the storing host system, a foreign host indicator to an entry in the deleted data structure for the target key-value pair;

invalidate, during garbage collection, erase blocks corresponding to key-value pairs from the deleted data structure based on the delete order; and

remove, responsive to garbage collection, corresponding keys for the invalidated key-value pairs from the deleted data structure.

2 . The data storage device of claim 1 , wherein the controller is further configured to:

receive, from a second host system of the plurality of host systems, a retrieve command for the target key-value pair after the delete command;

determine, responsive to the retrieve command, that the target key-value pair is not an active key-value pair;

determine, responsive to determining that the target key-value pair is not an active key-value pair, whether the corresponding key for the target key-value pair is in the deleted data structure; and

return, responsive to the corresponding key for the target key-value pair being in the deleted data structure, the key-value pair to the second host system.

3 . The data storage device of claim 2 , wherein the controller is further configured to:

add, responsive to the retrieve command for the target key-value pair determined to be in the deleted data structure, the corresponding key for the target key-value pair to an active key-value pair data structure; and

remove, responsive to the retrieve command for the target key-value pair determined to be in the deleted data structure, the corresponding key for the target key-value pair from the deleted data structure.

4 . The data storage device of claim 2 , wherein the controller is further configured to, responsive to the corresponding key for the target key-value pair not being in the deleted data structure, return a key-not-found notification to the second host system.

5 . The data storage device of claim 1 , wherein the controller is further configured to:

receive, prior to receiving the delete command, a store command for the target key-value pair including the corresponding key and host data unit for the target key-value pair;

determine the first host identifier for the storing host system; and

associate the first host identifier with the host data unit for the target key-value pair.

6 . The data storage device of claim 5 , wherein associating the first host identifier with the host data unit for the target key-value pair comprises:

appending the first host identifier to the host data unit to determine the value for the target key-value pair; and

storing the value for the target key-value pair to the non-volatile storage medium.

7 . The data storage device of claim 6 , wherein the controller is further configured to, responsive to receiving the delete command:

determine the first host identifier from the stored value for the target key-value pair;

determine a second host identifier for the first host system; and

compare the first host identifier to the second host identifier to determine the foreign host indicator to add to the entry in the deleted data structure for the target key-value pair.

8 . The data storage device of claim 7 , wherein the foreign host indicator is selected from:

a first indicator value corresponding to the first host identifier matching the second host identifier; and

a second indicator value corresponding to the first host identifier being different than the second host identifier.

9 . The data storage device of claim 1 , wherein:

the controller is further configured to:

determine the delete order for the deleted data structure; and

select, during garbage collection, a next key-value pair from the deleted data structure to invalidate corresponding erase blocks; and

the delete order is based on at least one priority parameter selected from:

entry order into the deleted data structure;

a memory size of the value for the next key-value pair;

an error rate of an erase block corresponding to the value for the next key-value pair; and

a foreign host indicator.

10 . The data storage device of claim 1 , wherein the controller is further configured to:

determine a deletion condition for the target key-value pair; and

send, based on the deletion condition, a notification message to at least one host system of the plurality of host systems.

11 . A computer-implemented method, comprising:

storing, to a non-volatile storage medium of a data storage device, host data units as values indexed by a corresponding key in key-value pairs;

receiving, by the data storage device and from a first host system of a plurality of host systems, a delete command for a target key-value pair;

moving, by the data storage device and responsive to the delete command, the corresponding key for the target key-value pair to a deleted data structure, wherein the deleted data structure comprises a series of key value entries configured in a delete order;

determining, by the data storage device, a storing host system that previously stored the target key-value pair;

adding, responsive to the first host system being different than the storing host system, a foreign host indicator to the key value entry in the deleted data structure for the target key-value pair;

invalidating, by the data storage device and during garbage collection, erase blocks corresponding to key-value pairs from the deleted data structure based on the delete order; and

removing, by the data storage device and responsive to garbage collection, corresponding keys for invalidated key-value pairs from the deleted data structure.

12 . The computer-implemented method of claim 11 , further comprising:

receiving, from a second host system of the plurality of host systems, a retrieve command for the target key-value pair after the delete command;

determining, responsive to the retrieve command, that the target key-value pair is not an active key-value pair;

determining, responsive to determining that the target key-value pair is not an active key-value pair, whether the corresponding key for the target key-value pair is in the deleted data structure; and

returning, responsive to the corresponding key for the target key-value pair being in the deleted data structure, the key-value pair to the second host system.

13 . The computer-implemented method of claim 12 , further comprising:

adding, responsive to the retrieve command for the target key-value pair determined to be in the deleted data structure, the corresponding key for the target key-value pair to an active key-value pair data structure; and

removing, responsive to the retrieve command for the target key-value pair determined to be in the deleted data structure, the corresponding key for the target key-value pair from the deleted data structure.

14 . The computer-implemented method of claim 12 , further comprising:

returning, responsive to the corresponding key for the target key-value pair not being in the deleted data structure, a key-not-found notification to the second host system.

15 . The computer-implemented method of claim 11 , further comprising:

receiving, prior to receiving the delete command, a store command for the target key-value pair including the corresponding key and host data unit for the target key-value pair;

determining a first host identifier for a storing host system; and

associating the first host identifier with the host data unit for the target key-value pair.

16 . The computer-implemented method of claim 15 , wherein associating the first host identifier with the host data unit for the target key-value pair comprises:

appending the first host identifier to the host data unit to determine the value for the target key-value pair; and

storing the value for the target key-value pair to the non-volatile storage medium.

17 . The computer-implemented method of claim 16 , further comprising, responsive to receiving the delete command:

determining the first host identifier from the stored value for the target key-value pair;

determining a second host identifier for the first host system; and

comparing the first host identifier to the second host identifier to determine the, a foreign host indicator to add to the entry in the deleted data structure for the target key-value pair, wherein the foreign host indicator is selected from:

a first indicator value corresponding to the first host identifier matching the second host identifier; and

a second indicator value corresponding to the first host identifier being different than the second host identifier.

18 . The computer-implemented method of claim 11 , further comprising:

determining the delete order for the deleted data structure; and

selecting, during garbage collection, a next key-value pair from the deleted data structure to invalidate corresponding erase blocks, wherein the delete order is based on at least one priority parameter selected from:

entry order into the deleted data structure;

a memory size of the value for the next key-value pair;

an error rate of an erase block corresponding to the value for the next key-value pair; and

a foreign host indicator.

19 . The computer-implemented method of claim 11 , further comprising:

determining a deletion condition for the target key-value pair; and

sending, based on the deletion condition, a notification message to at least one host system of the plurality of host systems.

20 . A data storage device comprising:

at least one processor;

at least one memory;

a non-volatile storage medium;

a host interface configured to receive host storage commands from a plurality of host systems;

means for storing, to the non-volatile storage medium, host data units as values indexed by a corresponding key in key-value pairs;

means for receiving, from a first host system of the plurality of host systems, a delete command for a target key-value pair;

means for moving, responsive to the delete command, the corresponding key for the target key-value pair to a deleted data structure having a delete order;

means for determining a storing host system that previously stored the target key-value pair;

means for adding, responsive to the first host system being different than the storing host system, a foreign host indicator to a key value entry in the deleted data structure for the target key-value pair;

means for invalidating, during garbage collection, erase blocks corresponding to key-value pairs from the deleted data structure based on the delete order; and

means for removing, responsive to garbage collection, corresponding keys for the invalidated key-value pairs from the deleted data structure.

Assignments (3)

Continuity (2)

References Cited (22)