Methods and systems for efficiently reading a data block from a data seglet with compressed data blocks

Patent metadata

Field	Value
Publication number	US-10027984-B2
Application number	US-201715590438-A
Country	US
Kind code	B2
Filing date	May 9, 2017
Priority date	Nov 30, 2016
Publication date	Jul 17, 2018
Grant date	Jul 17, 2018

Abstract

When data blocks of a data seglet are compressed using a shared dictionary and when the requested data block (or blocks) do not include the last data block of the data seglet, an optimization in the read path may involve decompressing a certain portion of the data seglet from a starting position of the data seglet to a decompression endpoint of the data seglet, but not including the portion of the data seglet following the decompression endpoint. Such technique may involve the storing of a mapping that maps, for each data block within the data seglet, an identifier of the data block to a decompression endpoint that indicates a portion of the data seglet that includes the data block.

First claim

What is claimed is:

1. A method, comprising:
receiving a request for a first data block that is stored on one or more storage units;
determining a data seglet that includes a compressed version of the first data block, wherein the data seglet includes a plurality of compressed data blocks, wherein the plurality of compressed data blocks includes the compressed version of the first data block, and wherein the data seglet includes a starting position and an ending position;
retrieving, from a mapping which maps data blocks to hints, a first hint corresponding to the first data block, the first hint indicating a first decompression endpoint within the data seglet, wherein the first decompression endpoint is located at or after an ending position of the compressed version of the first data block and is located at or before the ending position of the data seglet, wherein the mapping maps a second data block of the data seglet to a second hint indicating a second decompression endpoint within the data seglet, and wherein the first decompression endpoint is different than the second decompression endpoint;
reading at least a portion of the data seglet from the one or more storage units;
decompressing a contiguous portion of the data seglet, the contiguous portion spanning only between the starting position of the data seglet and the first decompression endpoint;
determining a region of the decompressed contiguous portion within which the first data block is located; and
returning the first data block from the determined region of the decompressed contiguous portion.

2. The method of claim 1 , wherein the at least portion of the data seglet that is read consists of the contiguous portion.

3. The method of claim 1 , wherein the at least portion of the data seglet that is read includes an entirety of the data seglet.

4. The method of claim 1 , wherein the first decompression endpoint is located at the ending position of the compressed version of the first data block.

5. The method of claim 1 , wherein the first decompression endpoint is located after the ending position of the compressed version of the first data block.

6. The method of claim 1 , wherein the first decompression endpoint is located before the ending position of the data seglet.

7. The method of claim 1 , wherein the starting position of the data seglet is equal to a starting position of a header of the data seglet.

8. A storage system, comprising:
a plurality of storage units;
a processor communicatively coupled to the storage units; and
a processor-readable medium storing instructions that, when executed by the processor, cause the processor to:
receive a request for a first data block that is stored on one or more of the storage units;
determine a data seglet that includes a compressed version of the first data block, wherein the data seglet includes a plurality of compressed data blocks, wherein the plurality of compressed data blocks includes the compressed version of the first data block, and wherein the data seglet includes a starting position and an ending position;
retrieve, from a mapping which maps data blocks to hints, a first hint corresponding to the first data block, the first hint indicating a first decompression endpoint within the data seglet, wherein the first decompression endpoint is located at or after an ending position of the compressed version of the first data block and is located at or before the ending position of the data seglet, wherein the mapping maps a second data block of the data seglet to a second hint indicating a second decompression endpoint within the data seglet, and wherein the first decompression endpoint is different than the second decompression endpoint;
read at least a portion of the data seglet from the one or more storage units;
decompress a contiguous portion of the data seglet, the contiguous portion spanning only between the starting position of the data seglet and the first decompression endpoint;
determine a region of the decompressed contiguous portion within which the first data block is located; and
return the first data block from the determined region of the decompressed contiguous portion.

9. The storage system of claim 8 , wherein the at least portion of the data seglet that is read consists of the contiguous portion.

10. The storage system of claim 8 , wherein the at least portion of the data seglet that is read includes an entirety of the data seglet.

11. The storage system of claim 8 , wherein the first decompression endpoint is located at the ending position of the compressed version of the first data block.

12. The storage system of claim 8 , wherein the first decompression endpoint is located after the ending position of the compressed version of the first data block.

13. The storage system of claim 8 , wherein the first decompression endpoint is located before the ending position of the data seglet.

14. The storage system of claim 8 , wherein the starting position of the data seglet is equal to a starting position of a header of the data seglet.

15. A non-transitory machine-readable storage medium comprising software instructions that, when executed by a processor, cause the processor to:
receive a request for a first data block that is stored on one or more of a plurality of storage units of a storage system;
determine a data seglet that includes a compressed version of the first data block, wherein the data seglet includes a plurality of compressed data blocks, wherein the plurality of compressed data blocks includes the compressed version of the first data block, and wherein the data seglet includes a starting position and an ending position;
retrieve, from a mapping which maps data blocks to hints, a first hint corresponding to the first data block, the first hint indicating a first decompression endpoint within the data seglet, wherein the first decompression endpoint is located at or after an ending position of the compressed version of the first data block and is located at or before the ending position of the data seglet, wherein the mapping maps a second data block of the data seglet to a second hint indicating a second decompression endpoint within the data seglet, and wherein the first decompression endpoint is different than the second decompression endpoint;
read at least a portion of the data seglet from the one or more storage units;
decompress a contiguous portion of the data seglet, the contiguous portion spanning only from the starting position of the data seglet to the first decompression endpoint;
determine a region of the decompressed contiguous portion within which the first data block is located; and
return the first data block from the determined region of the decompressed contiguous portion.

16. The non-transitory machine-readable storage medium of claim 15 , wherein the at least portion of the data seglet that is read consists of the contiguous portion.

17. The non-transitory machine-readable storage medium of claim 15 , wherein the at least portion of the data seglet that is read includes an entirety of the data seglet.

18. The non-transitory machine-readable storage medium of claim 15 , wherein the first decompression endpoint is located at the ending position of the compressed version of the first data block.

19. The non-transitory machine-readable storage medium of claim 15 , wherein the first decompression endpoint is located after the ending position of the compressed version of the first data block.

20. The non-transitory machine-readable st

Assignees

• Hewlett Packard Entpr Dev Lp

Inventors

• Karaje Gurunatha
• Vu Hy
• Sharma Rajat
• Ramamoorthy Senthil Kumar
• Varadan Srikant

Classifications

• H04N19/42

  characterised by implementation details or hardware specially adapted for video compression or decompression, e.g. dedicated software implementation (H04N19/635 takes precedence) · CPC title

• H04N19/865

  with detection of the former encoding block subdivision in decompressed video · CPC title

• G11C29/40

  using compression techniques · CPC title

• H04N19/66 Primary

  involving data partitioning, i.e. separation of data into packets or partitions according to importance · CPC title

• H04N19/119

  Adaptive subdivision aspects, e.g. subdivision of a picture into rectangular or non-rectangular coding blocks · CPC title