Logical band-based key-value storage structure

• US 10,678,768 B2
• Filed: 06/30/2017
• Issued: 06/09/2020
• Est. Priority Date: 06/30/2017
• Status: Active Grant

• Current Assignee: SK Hynix NAND Product Solutions Corporation (SK Hynix Inc.)
• Original Assignee: Intel Corporation
• Inventors: Li, Peng, Trika, Sanjeev
• Primary Examiner(s): Lee, Wilson
• Application Number:
  US15/639,651
• Publication Number:
  US 20190005079A1
• Time in Patent Office: 1,075 Days
• Field of Search: None
• CPC Class Codes: G06F 16/2272 Management thereof

Abstract

Systems, apparatuses and methods may store data. A system may include a processor communicatively coupled to an indexing structure and a datastore log separate from the indexing structure. The indexing structure may store key data corresponding to a key of a key-value pair and an address for the key-value pair. The datastore log may store the key-value pair at the address in a logical band of a plurality of independent logical bands. In addition, the system may include a memory device coupled to the processor. The memory device may include instructions, which when executed by the processor, may cause the system to execute an operation involving the key-value pair.

Claims

1. A computing system comprising:

a processor communicatively coupled to an indexing structure and a datastore log separate from the indexing structure, wherein the indexing structure is to store key data corresponding to a key of a key-value pair and an address for the key-value pair, and wherein the datastore log is to store the key-value pair at the address in a logical band of a plurality of independent logical bands;

one or more memory devices coupled to the processor, the one or more memory devices including instructions, which when executed by the processor, cause the computing system to;

execute an operation involving the key-value pair;

populate at least one logical band of the plurality of independent logical bands with data for a logical band footer so that the logical band footer is to include one or more of a status token or an error code;

populate the at least one logical band with data for one or more of a logical band header, a logical band entry or a logical band journal;

populate the logical band header with a sequence number;

populate the logical band entry with data for a logical band entry header; and

populate the logical band journal with a hash table entry when the indexing structure is a hash table.

2. The computing system of claim 1, wherein the instructions, when executed, cause the computing system to map the datastore log to one or more of a file system, logical block addressing, or storage device physical bands to divide the datastore log into the plurality of independent logical bands.

3. The computing system of claim 1, wherein the logical band entry header is to include a type field, a key length field, a value length field, the key-value pair, and an error code for the key-value pair.

4. The computing system of claim 1, wherein the instructions, when executed, cause the computing system to insert a current address for the key-value pair at the indexing structure.

5. The computing system of claim 1, wherein the instructions, when executed, cause the computing system to:

update an invalidity datastore with an invalidity count and with an erase count when the erase count is to be tracked;

update a logical band linked list with a clean logical band or a closed logical band and obtain a next clean logical band from the logical band linked list when needed; and

update statistic information in a statistics datastore for the computing system.

6. The computing system of claim 1, wherein the instructions, when executed, cause the computing system to:

select a target logical band based on an invalidity count and an erase count, and relocate all valid key-value pairs from the target logical band to a current logical band and erase the target logical band; and

recover one or more of a last opened logical band, a most recent indexing structure, or a most recent system level datastore.

7. A storage system comprising:

a memory that includes an indexing structure and a datastore log separate from the indexing structure, wherein the indexing structure is to store key data corresponding to a key of a key-value pair and an address for the key-value pair, wherein the datastore log is to store the key-value pair at the address in a logical band of a plurality of independent logical bands; and

a memory controller communicatively coupled to the memory, and wherein the memory controller is configured in circuitry to;

execute an operation involving the key-value pair;

populate a footer of at least one logical band of the plurality of independent logical bands with one or more of a status token or an error code;

populate a logical band header with a sequence number;

populate a logical band entry with data for a logical band entry header; and

populate a logical band journal with a hash table entry when the indexing structure is a hash table.

8. The storage system of claim 7, wherein the logical band entry header is to include a type field, a key length field, a value length field, the key-value pair, and an error code for the key-value pair.

9. The storage system of claim 7, wherein the memory controller is to insert a current address for the key-value pair at the indexing structure.

10. The storage system of claim 7, wherein the memory controller is to:

update an invalidity datastore with an invalidity count and with an erase count when the erase count is to be tracked;

update a logical band linked list with a clean logical band or a closed logical band and obtain a next clean logical band from the logical band linked list when needed; and

update statistic information in a statistics datastore for a storage system.

11. The storage system of claim 7, wherein the memory controller is to:

select a target logical band based on an invalidity count and an erase count, and relocate all valid key-value pairs from the target logical band to a current logical band and erase the target logical band; and

recover one or more of a last opened logical band, a most recent indexing structure, or a most recent system level datastore.

12. At least one non-transitory computer readable storage medium comprising a set of instructions, which when executed by a processor, cause the processor to:

store in an indexing structure key data corresponding to a key of a key-value pair and an address for the key-value pair;

store in a datastore log separate from the indexing structure the key-value pair at the address in a logical band of a plurality of independent logical bands;

execute an operation involving the key-value pair;

populate a footer of at least one logical band of the plurality of independent logical bands with one or more of a status token or an error code;

populate a logical band header with a sequence number;

populate a logical band entry with data for a logical band entry header; and

populate a logical band journal with a hash table entry when the indexing structure is a hash table.

13. The at least one non-transitory computer readable storage medium of claim 12, wherein the logical band entry header is to include a type field, a key length field, a value length field, the key-value pair, and an error code for the key-value pair.

14. The at least one non-transitory computer readable storage medium of claim 12, wherein the instructions, when executed, cause the processor to insert a current address for the key-value pair at the indexing structure.

15. The at least one non-transitory computer readable storage medium of claim 12, wherein the instructions, when executed, cause the processor to:

update an invalidity datastore with an invalidity count and with an erase count when the erase count is to be tracked;

update a logical band linked list with a clean logical band or a closed logical band and obtain a next clean logical band from the logical band linked list when needed; and

update statistic information in a statistics datastore for a storage system.

16. The at least one non-transitory computer readable storage medium of claim 12, wherein the instructions, when executed, cause the processor to:

select a target logical band based on an invalidity count and an erase count, and relocate all valid key-value pairs from the target logical band to a current logical band and erase the target logical band; and

recover one or more of a last opened logical band, a most recent indexing structure, or a most recent system level datastore.

17. A method comprising:

storing in an indexing structure key data corresponding to a key of a key-value pair and an address for the key-value pair;

storing in a datastore log separate from the indexing structure the key-value pair at the address in a logical band of a plurality of independent logical bands;

executing an operation involving the key-value pair;

populating a footer of at least one logical band of the plurality of independent logical bands with one or more of a status token or an error code;

populating a logical band header with a sequence number;

populating a logical band entry with data for a logical band entry header; and

populating a logical band journal with a hash table entry when the indexing structure is a hash table.

18. The method of claim 17, wherein the logical band entry header is to include a type field, a key length field, a value length field, the key-value pair, and an error code for the key-value pair.

19. The method of claim 17, further including inserting a current address for the key-value pair at the indexing structure.

20. The method of claim 17, further including:

selecting a target logical band based on an invalidity count and an erase count, and relocating all valid key-value pairs from the target logical band to a current logical band and erase the target logical band; and

recovering one or more of a last opened logical band, a most recent indexing structure, or a most recent system level datastore.