1. An apparatus comprising: one or more network interfaces; one or more processors; a first memory operable to store a plurality of data units and a plurality of signature blocks, each data unit comprising a contiguous sequence of observed data chunks; each signature block corresponding to a data unit, and comprising a plurality of chunk signatures for respective data chunks in a corresponding data unit; a second memory operable to store a plurality of chunk signatures, each chunk signature corresponding to an anchor data chunk, each chunk signature being associated with one or more signature blocks stored in the first memory, the second memory further comprising a signature block search space; and logic encoded in one or more tangible media for execution and when executed operable to cause one or more processors to: access a data block; divide the data block into a plurality of data chunks; compute chunk signatures for the plurality of data chunks; identify a plurality of anchor chunks in the plurality of data chunks; access the second memory to identify one or more matching chunk signatures; read one or more signature blocks corresponding to the matching chunk signatures from the first memory into the signature block search space of the second memory; and match one or more computed chunk signatures to chunk signatures of the one or more signature blocks in the signature block search space.