Methods and systems for metadata reduction in paged direct mapping key-value stores

A Key-Value data storage system, comprising:

• a storage device, the storage device being configured to store user data at a first addressing granularity, the user data being accessible via a Key-Value system;
• a memory;
• at least one processor;
• a plurality of processes spawned by the processor, the plurality of processes comprising processing logic to:
• store Value data in a storage device at a first addressing granularity that defines address locations using a first number of bits, each Value data corresponding to a Key and being stored along with a respective header in at least one of a plurality of addressing units within the storage device without regard to addressing unit boundaries;
• store a respective header offset value at a predetermined location within at least one of the addressing units, each header offset value determining an offset from an addressing boundary of the addressing unit to a first header within the addressing unit;
• maintain, in the storage device, full mapping metadata that associates a Key to a location and to a size of each Value data stored in the storage device and to an extra bit that indicates whether an additional addressing unit is to be read beyond that determined based on the size, the location being specified at a second addressing granularity that defines address locations using a second number of bits that is less than the first number of bits;
• using a user key, page a portion of the full mapping metadata from the storage device into the memory,
• read the location, the size, and the extra bit corresponding to the user key from the paged-in portion of the full mapping metadata, and
• using the location, the size, and the extra bit read from the paged-in portion of the full mapping metadata, scan at least one addressing unit in the storage device corresponding to the location based on the header offset to find the first header and a first Value data and subsequent headers and subsequent Value data, if present, in the scanned at least one addressing unit.

A computer-implemented method of implementing a Key-Value storage system, the computer-implemented method comprising:

• storing Value data in a storage device at a first addressing granularity that defines address locations using a first number of bits, each Value data corresponding to a Key and being stored along with a respective header in at least one of a plurality of addressing units within the storage device without regard to addressing unit boundaries;
• maintaining, in the storage device, full mapping metadata that associates a Key to a location and to a size of each Value data stored in the storage device and to an extra bit that indicates whether an additional addressing unit is to be read beyond that determined based on the size, the location being specified at a second addressing granularity that defines address locations using a second number of bits that is less than the first number of bits, the size being encoded such that a precision of smaller value data is higher than a precision of comparatively larger value data;
• using a user key, paging a portion of the full mapping metadata from the storage device into a memory;
• reading the location, the size, and the extra bit corresponding to the user key from the paged-in portion of the full mapping metadata, and
• using the location, the size, and the extra bit, read from the paged-in portion of the full mapping metadata, scanning at least one addressing unit in the storage device corresponding to the location based on a header offset to find the first header and a first Value data and subsequent headers and subsequent Value data, if present, in the scanned at least one addressing unit.