LOGICAL BAND-BASED KEY-VALUE STORAGE STRUCTURE

• US 20190005079A1
• Filed: 06/30/2017
• Published: 01/03/2019
• 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
• Granted Patent: US 10,678,768 B2
• Time in Patent Office: Days
• 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; and

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.

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 instructions, when executed, cause the computing system to populate at least one logical band of the plurality with data for one or more of a logical band header, a logical band entry, a logical band footer, or a logical band journal.

4. The computing system of claim 3, wherein the instructions, when executed, cause the computing system to:

populate the logical band header with a sequence number;

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

populate the footer with one or more of a status token or an error code; and

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

5. The computing system of claim 4, 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.

6. 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.

7. 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 storage system.

8. 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.

9. An apparatus comprising:

a substrate; and

logic coupled to the substrate and 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, 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 wherein the logic is configured at least partly in one or more of configurable logic or fixed-functionality hardware logic to execute an operation involving the key-value pair.

10. The apparatus of claim 9, wherein the logic is to:

populate a logical band header with a sequence number;

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

populate a footer with one or more of a status token or an error code; and

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

11. The apparatus of claim 10, 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.

12. The apparatus of claim 9, wherein the logic is to insert a current address for the key-value pair at the indexing structure.

13. The apparatus of claim 9, wherein the logic 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 the storage system.

14. The apparatus of claim 9, wherein the logic 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.

15. 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; and

execute an operation involving the key-value pair.

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

populate the logical band header with a sequence number;

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

populate the footer with one or more of a status token or an error code; and

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

17. The at least one non-transitory computer readable storage medium of claim 16, 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.

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

19. The at least one non-transitory computer readable storage medium of claim 15, 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.

20. The at least one non-transitory computer readable storage medium of claim 15, 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.

21. 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; and

executing an operation involving the key-value pair.

22. The method of claim 21, further including:

populating the logical band header with a sequence number;

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

populating the footer with one or more of a status token or an error code; and

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

23. The method of claim 22, 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.

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

25. The method of claim 21, 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.