Optimizing Data Management within Key Value Storage

Key-Value SSDs use internal hash tables to map keys to physical flash locations. As the device fills up, these fixed-size tables become congested — collision chains grow, lookups slow down, and the device hits its pair limit before exhausting physical capacity. The standard solution of resizing the hash table requires rehashing every entry, causing latency spikes that are unacceptable for a storage device serving real-time I/O.

The Patent

U.S. Patent 11474699 covers systems and methods for optimizing data management within key-value storage devices. The core innovation is a re-configurable indexing scheme that allows the internal hash index to resize dynamically without the penalty of full-table rehashing. The technique maintains consistent lookup performance regardless of how full the device is.

Technical Approach

The patented scheme enables incremental index growth by splitting hash buckets on demand rather than rehashing the entire table at once. When a bucket becomes too full, only that bucket is split — its entries are redistributed between the original and new bucket, while all other buckets remain unchanged. This bounds the worst-case overhead of any single resize operation, eliminating the latency spikes associated with full rehashing.

Impact

This patent underlies the RHIK system published at HPDC 2023, which demonstrated the practical benefits of this approach on the open-source KV-SSD emulator. By enabling KV-SSDs to maintain performance at high occupancy, the technique makes the devices viable for production workloads where consistent latency matters.

Granted October 2022. U.S. Patent 11474699. Inventors: Manoj P. Saha, Janki Bhimani.