Method to increase random I/O performance with low memory overheads

A non-transitory computer-readable medium storing instructions, which when executed by one or more processors, cause the one or more processors to:

• in response to a request from a client to access data, retrieve an index entry from an index of storage blocks based on a data identifier of the requested data, wherein the index entry includes a start location of an indexed storage block stored in a device, and information identifying a plurality of sub-block locators, wherein each sub-block locator of the plurality of sub-block locators includes a start offset of a sub-block within the indexed storage block;
• determine which sub-block locator, of the plurality of sub-block locators within the index entry, locates a sub-block containing the requested data based on the start location of the indexed storage block and the data identifier of the requested data;
• without reading the entire indexed storage block, read the sub-block from the device starting at a device location determined based on the start location of the indexed storage block within the device and the sub-block start offset of the determined sub-block locator;
• and
• transmit the requested data read from the sub-block to the client.

A storage management apparatus comprising:

• a cache device or a storage device;
• one or more processors coupled to the cache device or the storage device;
• and
• a memory coupled to the processor for storing instructions, which when executed by the one or more processors, cause the one or more processors to:
• retrieve, in response to a request from a client to access data, an index entry from an index of storage blocks based on a data identifier of the requested data, wherein the index entry includes a start location of an indexed storage block stored in a device, and information identifying a plurality of sub-block locators,
• wherein each sub-block locator of the plurality of sub-block locators includes a start offset of a sub-block within the indexed storage block;
• determine which sub-block locator, of the plurality of sub-block locators within the index entry, locates a sub-block containing the requested data based on the start location of the indexed storage block and the data identifier of the requested data;
• without reading the entire indexed storage block, read the sub-block from the device starting at a device location determined based on the start location of the indexed storage block within the device and the sub-block start offset of the determined sub-block locator;
• and
• transmit the requested data read from the sub-block to the client.