BUCKETIZED MULTI-INDEX LOW-MEMORY DATA STRUCTURES

• US 20140310476A1
• Filed: 04/11/2014
• Published: 10/16/2014
• Est. Priority Date: 04/12/2013
• Status: Active Grant

• Current Assignee: NEC Corporation
• Original Assignee: NEC Laboratories America Inc (NEC Corporation)
• Inventors: Kruus, Erik, Ungureanu, Cristian, Xia, Wen
• Granted Patent: US 9,471,500 B2
• Time in Patent Office: Days
• US Class Current: 711/133
• CPC Class Codes: G06F 12/0871 Allocation or management of cache space

Abstract

Systems and methods for generating and storing a data structure for maintaining cache supporting compression and cache-wide deduplication, including generating data structures with fixed size memory regions configured to hold multiple signatures as keys, wherein the number of the fixed size memory regions is bounded. A first mapping is generated from short-length signatures to a storage location and a quantized length measure on a cache storage device; and unused contiguous regions on the cache device are allocated. Metadata and cache page content is retrieved using a single input/output operation; a correctness of a full value of hash functions of uncompressed cache page content is validated; a second mapping is generated from short-length signatures to entries in the first mapping; and verification of whether the cached page content corresponds to a full-length original logical block address using the metadata is performed.

Claims

1. A method for generating and storing a data structure for maintaining a cache supporting compression and a cache-wide deduplication, comprising:

generating data structures with fixed size memory regions configured to hold multiple signatures as keys, wherein the number of the fixed size memory regions is bounded;

generating a first mapping from short-length signatures to a storage location and a quantized length measure on a cache storage device;

retrieving metadata and cache page content using a single input/output operation;

validating a correctness of a full value of one or more hash functions of uncompressed cache page content using the metadata;

generating a second mapping from short-length signatures to entries in the first mapping, wherein one or more pointers to entries in the first mapping are stored in a non-transitory computer readable storage medium; and

verifying whether the cached page content corresponds to a full-length original logical block address (LBA) using the metadata.

2. The method as recited in claim 1, wherein the storage location information and the quantized length measure information is stored in a compressed format.

3. The method as recited in claim 1, wherein the cache page content is stored in a compressed format.

4. The method as recited in claim 1, wherein the first and second mappings are statically sized d-left hash tables with zero internal pointer overhead, wherein the statically sized d-left hash tables are never resized or reallocated.

5. The method as recited in claim 1, wherein unused contiguous regions on the cache device of a predetermined length are allocated.

6. The method as recited in claim 1, wherein the pointer to entries in the first mapping is stored with a lower number of bits than a memory pointer.

7. The method as recited in claim 6, wherein a bounded-length search is employed to locate a matching entry.

8. A system for generating and storing a data structure for maintaining a cache supporting compression and a cache-wide deduplication, comprising:

one or more data structures with fixed size memory regions configured to hold multiple signatures as keys, wherein the number of the fixed size memory regions is bounded;

a mapping generator configured to generate a first mapping from short-length signatures to a storage location and a quantized length measure on a cache storage device, and to generate a second mapping from short-length signatures to entries in the first mapping, wherein one or more pointers to entries in the first mapping are stored;

a content retrieval module configured to retrieve metadata and cache page content using a single input/output operation;

a validation module configured to validate a correctness of a full value of one or more hash functions of uncompressed cache page content using the metadata; and

a verification module configured to verify whether the cached page content corresponds to a full-length original logical block address (LBA) using the metadata.

9. The system as recited in claim 8, wherein the storage location information and the quantized length measure information is stored in a compressed format.

10. The system as recited in claim 8, wherein the cache page content is stored in a compressed format.

11. The system as recited in claim 8, wherein the first and second mappings are statically sized d-left hash tables with zero internal pointer overhead, wherein the statically sized d-left hash tables are never resized or reallocated.

12. The system as recited in claim 8, wherein unused contiguous regions on the cache device of a predetermined length are allocated.

13. The system as recited in claim 8, wherein the pointer to entries in the first mapping is stored with a lower number of bits than a memory pointer.

14. The system as recited in claim 13, wherein a bounded-length search is employed to locate a matching entry.

15. A method for reducing memory and resource costs for a bucketized multi-index data structure, comprising:

storing multiple key types concurrently in one or more individual buckets in a non-transitory computer readable storage medium;

performing a lookup of a first value of information for one or more data positions (DPs) using a first key for one of more content addresses (CAs);

performing a lookup of a second value of information for one or more DPs using a second key for one or more logical block addresses (LBAs) by referring to the CAs;

compressing one or more of LBA information, CA information, and bucket header information, or portions thereof; and

evicting information from buckets to cause a ratio of LBA keys to CA keys in each bucket to approach a global ratio of LBA keys to CA keys.

16. The method as recited in claim 15, wherein the one or more individual buckets are of a fixed total size.

17. The method as recited in claim 15, wherein the fixed total size of the one or more individual buckets enables pointerless operations.

18. The method as recited in claim 15, wherein the compression of the one or more of LBA information, the CA information, and the bucket header information, or portions thereof, is performed on a per-bucket basis.