Method and apparatus for enabling larger memory capacity than physical memory size

A method of storing data in memory associated with a dedupe engine, the method comprising:

• identifying the data to be stored;
• determining a first hash value corresponding to where the data should be stored in a hash table in the memory utilizing a first hash function;
• storing the data at a location in the hash table corresponding to the first hash value;
• determining a second hash value also corresponding to where the data should be stored utilizing a second hash function smaller than the first hash function;
• storing the first hash value in a translation table in the memory;
• and
• storing the second hash value in a signature table in the memory.

A dedupe module comprising:

• a read cache;
• a dedupe engine to receive a data retrieval request from a host system;
• and
• memory, the memory comprising:
• a translation table;
• and
• a combined data structure comprising:
• a hash table comprising a plurality of hash buckets, each hash bucket comprising a plurality of physical lines, each physical line storing data;
• a reference counter table comprising a plurality of reference counter buckets, each reference counter bucket comprising a plurality of reference counters;
• and
• a plurality of hash cylinders, each hash cylinder comprising one of the hash buckets and one of the reference counter buckets, wherein the data retrieval request causes the dedupe engine to:
• identify a logical address of the data;
• identify a physical line ID (PLID) of the data in accordance with the logical address by looking up at least a portion of the logical address in the translation table;
• locate a respective physical line of the plurality of physical lines, the respective physical line corresponding to the PLID;
• and
• retrieve the data from the respective physical line, the retrieving of the data comprising copying a respective hash cylinder of the plurality of hash cylinders to the read cache, the respective hash cylinder comprising:
• a respective hash bucket of the plurality of hash buckets, the respective hash bucket comprising the respective physical line;
• and
• a respective reference counter bucket of the plurality of reference counter buckets, the respective reference counter bucket comprising a respective reference counter associated with the respective physical line.

A dedupe module comprising:

• a host interface;
• a transfer manager to receive data transfer requests from a host system via the host interface;
• and
• a plurality of partitions, each partition comprising:
• a dedupe engine to receive partition data requests from the transfer manager;
• a plurality of memory controllers;
• a memory manager between the dedupe engine and the memory controller;
• and
• a plurality of memory modules, each memory module being coupled to one of the memory controllers.

A dedupe module comprising:

• a read cache;
• memory, the memory comprising:
• a translation table;
• and
• a hash table comprising a plurality of hash buckets, each hash bucket comprising a plurality of physical lines, each physical line storing data;
• and
• a reference counter table comprising a plurality of reference counter buckets, each reference counter bucket comprising a plurality of reference counters;
• and
• a dedupe engine to identify V virtual buckets for a first hash bucket of the plurality of hash buckets, the virtual buckets being others of the plurality of hash buckets that are nearby the first hash bucket, the virtual buckets to store some of the first hash bucket's data when the first hash bucket is full, V being an integer that is dynamically set based on how full the first hash bucket's virtual buckets are.