Memory efficient indexing for disk-based compression

A network device comprising:

• one or more disk drives;
• and
• logic to
• store data to the one or more disk drives;
• and
• maintain a lookup table that stores signatures that are used to determine when a block of data has been previously processed by the network device and compress the block of data when the data is transmitted over a network, the lookup table including a bucketed hash table where each bucket in the hash table is structured as a linked-list of entries and corresponds to an index of the hash table, each of the entries including a signature of a block of data and an identifier indicating where on the one or more disk drives the block of data is stored.

A network device comprising:

• means for receiving a stream of data;
• means for generating a signature for a plurality of fixed length overlapping windows of the stream of data;
• means for selecting a predetermined number of the generated signatures for each Ln-byte segment of the data stream, wherein Ln is greater than a length of each of the windows;
• and
• means for storing the selected signatures in a bucketed hash table that includes a linked-list of entries for each bucket.

A method performed in a first network device comprising:

• generating a signature for a block of data in a data stream;
• matching the generated signature to signatures stored in a bucketed hash table in which hash table collisions are stored in a linked-list structure, the matching including comparing the signature to a plurality of previously stored signatures in a bucket of the hash table that corresponds to the generated signature;
• matching the block of data to a previously stored block of data when a match of the signature is detected in the bucketed hash table;
• and
• transmitting a reference to the block of data to a second network device when a match is detected in the bucketed hash table and the block of data is matched to the previously stored block of data.

A method comprising:

• receiving a stream of data;
• storing the stream on one or more hard disk drives;
• generating a signature for each of a plurality of fixed length overlapping windows in the stream;
• sampling the generated signatures using probabilistic sampling to reduce a number of the generated signatures;
• selecting one signature from the sampled signatures for each predetermined length of data in the stream;
• storing the selected one signature in a hash table in which hash table collisions are handled by adding the signature to a linked list at the colliding hash table bucket;
• and
• using the hash table to determine when a subsequently received block of data in the stream is stored on the one or more hard disk drives;
• and
• transmitting a reference to the subsequently received block of data in place of the actual subsequently received block of data.