APPARATUS, SYSTEM, AND METHOD FOR KEY-VALUE POOL IDENTIFIER ENCODING

• US 20130275656A1
• Filed: 08/20/2012
• Published: 10/17/2013
• Est. Priority Date: 04/17/2012
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: Fusion-IO Incorporated (Western Digital Corporation)
• Inventors: Talagala, Nisha, Sundararaman, Swaminathan, Batwara, Ashish, Ramsundar, Bharath
• Granted Patent: US 9,075,710 B2
• Time in Patent Office: Days
• US Class Current: 711/103
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 2212/7201 Logical to physical mapping or translation of blocks or pages
• CPC Class Codes: G06F 3/0604 Improving or facilitating administration, e.g. storage management
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0679 Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]
• CPC Class Codes: G06F 3/0688 Non-volatile semiconductor memory arrays

Abstract

Apparatuses, systems, and methods are disclosed for a key-value store. A method includes encoding a key of a key-value pair into a logical address of a sparse logical address space for a non-volatile medium. A method includes mapping a logical address to a physical location in the non-volatile medium. A method includes storing a value of a key-value pair at a physical location.

Claims

1-14. -14. (canceled)

15. An apparatus comprising:

a key-value mapping module configured to encode a key of a key-value pair into a key address portion of a logical address of a sparse logical address space for non-volatile storage media;

a pool module configured to encode a pool identifier for the key-value pair into a value address portion of the logical address, the value address portion having a number of bits such that the value address portion addresses at least a maximum size key-value pair value; and

a logical-to-physical translation layer configured to map the logical address to a location of at least a portion of the value of the key-value pair in the non-volatile storage media.

16. The apparatus of claim 15, further comprising a client interface module configured to receive one or more key-value store commands for the key-value pair from one or more clients and a device interface module configured to execute one or more primitive operations of a non-volatile storage controller for the non-volatile storage media to fulfill the one or more key-value store commands.

17-25. -25. (canceled)

26. A method comprising:

mapping a key of a key-value pair to a slot within a sparse logical address space of non-volatile memory media;

encoding a pool identifier for the key-value pair as an offset for the key-value pair within the slot; and

determining a logical address for the key-value pair, the logical address associated with the slot and the offset.

27. The method of claim 26, wherein the key is mapped to the slot by hashing the key to form a hash value, the hash value identifying a starting logical address for the slot.

28. The method of claim 26, wherein the pool identifier is encoded as the offset within the slot by encoding the pool identifier into least significant bits of the logical address.

30. The method of claim 26, wherein the sparse logical address space is segmented into a plurality of slots, each of the plurality of slots sized to provide a buffer of at least one logical address between stored key-value pairs in the sparse logical address space.

29. (canceled)

31. A method comprising:

encoding a key of a key-value pair into a logical address within a sparse logical address space for a non-volatile medium;

mapping the logical address to a physical location on the non-volatile medium; and

storing a value of the key-value pair at the physical location.

32. The method of claim 31, wherein encoding the key comprises hashing the key and including a resulting hash value in the logical address.

33. The method of claim 32, further comprising re-hashing the key to a different logical address in response to locating an existing entry for the logical address in a logical-to-physical address mapping structure for the non-volatile medium.

34. The method of claim 31, further comprising creating a buffer of at least one logical address between stored key-value pairs in the sparse logical address space, wherein a storage capacity recovery process for the non-volatile medium is configured to copy the value of the key-value pair and the key-value metadata for the key-value pair to a contiguous location on the non-volatile medium in response to detecting the buffer between the stored key-value pairs during a storage capacity recovery operation for the key-value pair.

35. The method of claim 31, wherein storing the value comprises executing one or more primitive operations of a non-volatile storage controller for the non-volatile medium to atomically store the value and key-value metadata for the key-value pair contiguously at the physical location.

36. The method of claim 31, wherein the logical address comprises a value address portion, bits of the value address portion allocating an address range sized to address at least a maximum size for the value of the key-value pair.

37. The method of claim 31, wherein storing the value comprises storing the value within a logical address range associated with the key-value pair in response to (a) locating an existing logical address entry within the logical address range, the existing logical address entry for a different key-value pair;

and (b) determining that the value will not overlap with a different value associated with the different key-value pair within the logical address range.

38. The method of claim 31, wherein the key of the key-value pair comprises a fingerprint and the value of the key-value pair comprises a deduplication index for the fingerprint.

39. The method of claim 31, further comprising evicting an existing key-value pair for the logical address from the non-volatile medium in response to encoding the key into the logical address, wherein the non-volatile medium is used as a cache.

40. An apparatus comprising:

a key-value mapping module configured to determine a logical address for a key-value pair based on a key of the key-value pair in response to a key-value command;

an exists module configured to determine whether data for the logical address is stored in a non-volatile device based on a logical-to-physical address mapping structure for the non-volatile device; and

a device interface module configured to translate the key-value command to one or more primitive storage operations for the non-volatile device to satisfy the key-value command.

41. The apparatus of claim 40, wherein the one or more primitive storage operations comprise an ATOMIC WRITE operation to store a value of the key-value pair to the non-volatile device in response to the key-value command comprising a PUT command, the ATOMIC WRITE operation configured to store variable sized values of key-value pairs and key-value metadata contiguously in a sequential, log-based data format for the non-volatile device.

42. The apparatus of claim 40, wherein the one or more primitive storage operations comprise a CONDITIONAL WRITE operation to store a value of the key-value pair to the non-volatile device in response to the key-value command comprising a PUT command, the CONDITIONAL WRITE operation configured to store the value in response to the exists module determining that data for the logical address is not already stored in the non-volatile device and to fail in response to the exists module determining that data for the logical address is already stored in the non-volatile device.

43. The apparatus of claim 40, wherein the one or more primitive storage operations comprise a PTRIM operation configured to persistently invalidate the key-value pair from the non-volatile device in response to the key-value command comprising a DELETE command.

44. The apparatus of claim 43, wherein the PTRIM operation is configured to store a persistent indicator on the non-volatile device, the persistent indicator configured to exclude an invalidated key-value pair from reconstructed volatile metadata.

45. The apparatus of claim 40, wherein the one or more primitive storage operations comprise a RANGE READ operation in response to the key-value command comprising a GET command, the RANGE READ operation configured to return a populated range of data for a value of the key-value pair without adding data for an unfilled range.

46. The apparatus of claim 40, wherein existence of an entry for the logical address in the logical-to-physical mapping structure denotes storage of an existing data value for the logical address in the non-volatile device.

47. The apparatus of claim 46, wherein the exists module is configured to determine whether data for the logical address is stored in the non-volatile device using a RANGE EXISTS primitive operation, the RANGE EXISTS primitive operation configured to determine whether data is currently stored by the non-volatile device in an allocated range of logical addresses for the key-value pair by checking for entries in the allocated range in the logical-to-physical address mapping structure.

48. An apparatus comprising:

means for mapping a key of a key-value pair to a logical address for a non-volatile memory medium using a known transform;

means for mapping logical addresses for the non-volatile memory medium to physical locations in the non-volatile memory medium; and

means for writing a value of the key-value pair and associated key-value metadata to the physical location.

49. The apparatus of claim 48, further comprising means for ensuring that a buffer of at least one logical address exists between each key-value pair, the value and the key-value metadata of the key-value pair stored contiguously between the buffers of at least one logical address.

50. The apparatus of claim 48, further comprising means for mapping the key-value pair to a different logical address in response to locating an existing entry for the logical address in a logical-to-physical address mapping structure for the non-volatile memory medium.

51. A computer program product comprising a computer readable storage medium storing computer usable program code executable to perform operations, the operations comprising:

hashing keys of key-value pairs into key address portions of logical addresses of a sparse logical address space for a non-volatile memory device;

dividing the logical addresses into the key address portion and a value address portion, the value address portions configured to segment the sparse logical address space into contiguous data ranges for the key-value pairs; and

maintaining a logical-to-physical address mapping structure mapping the logical addresses to physical locations in the non-volatile memory device.

52. The computer program product of claim 51, wherein the operations further comprise skipping at least one sequential logical address between stored key-value pairs in the sparse logical address space.

53. The computer program product of claim 51, wherein the operations further comprise servicing one or more key-value commands for the key-value pairs using the logical-to-physical address mapping structures and one or more primitive operations for the non-volatile memory device.

54. The computer program product of claim 51, wherein the keys of the key-value pairs comprise deduplication fingerprints and the values of the key-value pairs comprise a deduplication index for the deduplication fingerprints.