Distributed cache system utilizing multiple erasure codes

Patent metadata

Field	Value
Publication number	US-9817713-B2
Application number	US-201615016014-A
Country	US
Kind code	B2
Filing date	Feb 4, 2016
Priority date	Feb 4, 2016
Publication date	Nov 14, 2017
Grant date	Nov 14, 2017

Abstract

One embodiment provides a method comprising, for at least one data block, selecting an erasure code from a plurality of erasure codes based on at least one property of the at least one data block and information relating to a data cache, and encoding, utilizing at least one hardware processor, the at least one data block with the selected erasure code. The information relating to the data cache includes cache space usage of the data cache.

First claim

What is claimed is:

1. A method comprising:
at a cache system supporting a plurality of erasure codes with different reliability and storage overhead requirements:
adaptively coding at least one data block by:
selecting an erasure code from the plurality of erasure codes based on at least one property of the at least one data block and information relating to a data cache of the cache system, wherein the information relating to the data cache includes cache space usage of the data cache; and
encoding, utilizing at least one hardware processor, the at least one data block with the selected erasure code, wherein the encoded at least one data block is inserted into the data cache, and the encoded at least one data block results in one of increased recovery performance in the data cache, increased data redundancy in the data cache, or decreased storage overhead in the data cache.

2. The method of claim 1 , wherein the at least one property indicates at least one of the following: whether the at least one data block has at least one backup copy maintained on at least one hardware storage back-end device, and a number of times the at least one data block is accessed from the data cache.

3. The method of claim 1 , wherein the encoded at least one data block is inserted into a hardware cache of the data cache.

4. The method of claim 1 , wherein the plurality of erasure codes comprise at least one of the following: a high fault tolerance erasure code that increases data redundancy in the data cache, a low fault tolerance erasure code that decreases data redundancy in the data cache, a fast erasure code that increases recovery performance in the data cache, and a compact erasure code that decreases storage overhead in the data cache.

5. The method of claim 1 , the method further comprising:
for at least one new data block for insertion into the data cache:
encoding the at least one new data block with a high fault tolerance erasure code that increases data redundancy in the data cache; and
inserting the at least one new data block encoded with the high fault tolerance erasure code into the data cache.

6. The method of claim 2 the method further comprising:
in response to determining, based on the at least one property, the at least one data block does not have at least one backup copy maintained on at least one hardware storage back-end device:
encoding the at least one data block with a high fault tolerance erasure code that increases data redundancy in the data cache; and
inserting the at least one data block encoded with the high fault tolerance erasure code into the data cache.

7. The method of claim 1 , the method further comprising:
in response to destaging of at least one additional data block encoded with a high fault tolerance erasure code that increases data redundancy in the data cache:
converting the at least one additional data block to a low fault tolerance erasure code that decreases data redundancy in the data cache.

8. The method of claim 2 , the method further comprising:
in response to determining, based on the at least one property, the at least one data block does have at least one backup copy maintained on at least one hardware storage back-end device:
determining whether the at least one data block is a hot block based on the number of times the at least one data block is accessed in the data cache; and
in response to determining the at least one data block is not a hot block, reclaiming cache space of the data cache by upcoding the at least one data block to a compact erasure code that decreases storage overhead in the data cache.

9. The method of claim 2 , the method further comprising:
in response to determining, based on the at least one property, the at least one data block does have at least one backup copy maintained on at least one hardware storage back-end device:
determining whether the at least one data block is a hot block based on the number of times the at least one data block is accessed in the data cache; and
in response to determining the at least one data block is a hot block, minimizing traffic bandwidth during recovery by downcoding the at least one data block to a fast erasure code that increases recovery performance in the data cache.

10. The method of claim 2 , the method further comprising:
for the at least one data block:
determining whether the number of times the at least one data block is accessed in the data cache has increased; and
in response to determining the number of times the at least one data block is accessed in the data cache has increased, minimizing traffic bandwidth during recovery by converting the at least one data block to a fast erasure code that increases recovery performance in the data cache.

11. The method of claim 1 , the method further comprising:
in response to destaging of at least one additional data block:
determining whether a first erasure code that the at least one additional data block is encoded with is the same as a second erasure code utilized at a hardware storage back-end device; and
in response to determining that the first erasure code and the second erasure code are the same, destaging at least one parity block corresponding to the at least one additional data block.

12. A system comprising a computer processor, a computer-readable hardware storage device, and program code embodied with the computer-readable hardware storage device for execution by the computer processor to implement a method comprising:
at a cache system supporting a plurality of erasure codes with different reliability and storage overhead requirements:
adaptively coding at least one data block by:
selecting an erasure code from the plurality of erasure codes based on at least one property of the at least one data block and information relating to a data cache of the cache system, wherein the information relating to the data cache includes cache space usage of the data cache; and
encoding, utilizing at least one hardware processor, the at least one data block with the selected erasure code, wherein the encoded at least one data block is inserted into the data cache, and the encoded at least one data block results in one of increased recovery performance in the data cache, increased data redundancy in the data cache, or decreased storage overhead in the data cache.

13. The system of claim 12 , wherein the at least one property indicates at least one of the following:
whether the at least one data block has at least one backup copy maintained on at least one hardware storage back-end device, and a number of times the at least one data block is accessed from the data cache.

14. The system of claim 13 , wherein the plurality of erasure codes comprise at least one of the following: a high fault tolerance erasure code that increases data redundancy in the data cache, a low fault tolerance erasure code that decreases data redundancy in the data cache, a fast erasure code that increases recovery performance in the data cache, and a compact erasure code that decreases storage overhead in the data cache.

15. The system of claim 14 , wherein the method further comprises:
for at least one new data block for insertion into the data cache:
encoding the at least one new data block with a high fault tolerance erasure code that increases data redundancy in the data cache; and
inserting the at least one new data block encoded with the high fault tolerance erasure code into the data cache.

16. The system of claim 14 , wherein the method further comprises:
in response to determining, based on the at least one p

Assignees

• IBM

Inventors

• Gupta Aayush
• Saxena Mohit

Classifications

• H03M13/154

  Error and erasure correction, e.g. by using the error and erasure locator or Forney polynomial · CPC title

• G06F11/1064 Primary

  in cache or content addressable memories · CPC title

• G06F12/0802

  Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches · CPC title

• G06F2212/1032

  Reliability improvement, data loss prevention, degraded operation etc · CPC title

• H03M13/3761

  using code combining, i.e. using combining of codeword portions which may have been transmitted separately, e.g. Digital Fountain codes, Raptor codes or Luby Transform [LT] codes · CPC title